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];
}
|
