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
129
130
|
/* 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)
{
memset(table, 0, sizeof(*table));
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];
}
|
