summaryrefslogtreecommitdiff
path: root/lib/util/str_table.c
blob: 6363c81e32e447c9486c4b7ec4ff7cf14c777e63 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/* SPDX-License-Identifier: GPL-3.0-or-later */
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include "str_table.h"

/* R5 hash function (borrowed from reiserfs) */
static uint32_t strhash(const char *s)
{
	const signed char *str = (const signed char *)s;
	uint32_t a = 0;

	while (*str != '\0') {
		a += *str << 4;
		a += *str >> 4;
		a *= 11;
		str++;
	}

	return a;
}

static int strings_grow(str_table_t *table)
{
	size_t newsz;
	void *new;

	if (table->num_strings < table->max_strings)
		return 0;

	newsz = table->max_strings ? (table->max_strings * 2) : 16;
	new = realloc(table->strings, sizeof(table->strings[0]) * newsz);

	if (new == NULL) {
		perror("growing string table");
		return -1;
	}

	table->strings = new;
	table->max_strings = newsz;
	return 0;
}

int str_table_init(str_table_t *table, size_t size)
{
	table->buckets = calloc(size, sizeof(table->buckets[0]));
	table->num_buckets = size;

	if (table->buckets == NULL) {
		perror("initializing string table");
		return -1;
	}

	return 0;
}

void str_table_cleanup(str_table_t *table)
{
	str_bucket_t *bucket;
	size_t i;

	for (i = 0; i < table->num_buckets; ++i) {
		while (table->buckets[i] != NULL) {
			bucket = table->buckets[i];
			table->buckets[i] = bucket->next;

			free(bucket->str);
			free(bucket);
		}
	}

	free(table->buckets);
	free(table->strings);
	memset(table, 0, sizeof(*table));
}

int str_table_get_index(str_table_t *table, const char *str, size_t *idx)
{
	str_bucket_t *bucket;
	uint32_t hash;
	size_t index;

	hash = strhash(str);
	index = hash % table->num_buckets;
	bucket = table->buckets[index];

	while (bucket != NULL) {
		if (strcmp(bucket->str, str) == 0) {
			*idx = bucket->index;
			return 0;
		}

		bucket = bucket->next;
	}

	if (strings_grow(table))
		return -1;

	bucket = calloc(1, sizeof(*bucket));
	if (bucket == NULL)
		goto fail_oom;

	bucket->str = strdup(str);
	if (bucket->str == NULL)
		goto fail_oom;

	bucket->index = table->num_strings;
	table->strings[table->num_strings++] = bucket->str;
	*idx = bucket->index;

	bucket->next = table->buckets[index];
	table->buckets[index] = bucket;
	return 0;
fail_oom:
	free(bucket);
	perror("allocating hash table bucket");
	return -1;
}

const char *str_table_get_string(str_table_t *table, size_t index)
{
	if (index >= table->num_strings)
		return NULL;

	return table->strings[index];
}