1#include <assert.h>
2#include <limits.h>
3#include <stdbool.h>
4#include <stdint.h>
5#include <stdlib.h>
6#include <string.h>
7#include "util.h"
8#include "htab.h"
9
10struct hashtable {
11 size_t len, cap;
12 struct hashtablekey *keys;
13 void **vals;
14};
15
16void
17htabkey(struct hashtablekey *k, const char *s, size_t n)
18{
19 k->str = s;
20 k->len = n;
21 k->hash = rapidhashv1(s, n);
22}
23
24struct hashtable *
25mkhtab(size_t cap)
26{
27 struct hashtable *h;
28 size_t i;
29
30 assert(!(cap & (cap - 1)));
31 h = xmalloc(sizeof(*h));
32 h->len = 0;
33 h->cap = cap;
34 h->keys = xreallocarray(NULL, cap, sizeof(h->keys[0]));
35 h->vals = xreallocarray(NULL, cap, sizeof(h->vals[0]));
36 for (i = 0; i < cap; ++i)
37 h->keys[i].str = NULL;
38
39 return h;
40}
41
42void
43delhtab(struct hashtable *h, void del(void *))
44{
45 size_t i;
46
47 if (!h)
48 return;
49 if (del) {
50 for (i = 0; i < h->cap; ++i) {
51 if (h->keys[i].str)
52 del(h->vals[i]);
53 }
54 }
55 free(h->keys);
56 free(h->vals);
57 free(h);
58}
59
60static bool
61keyequal(struct hashtablekey *k1, struct hashtablekey *k2)
62{
63 if (k1->hash != k2->hash || k1->len != k2->len)
64 return false;
65 return memcmp(k1->str, k2->str, k1->len) == 0;
66}
67
68static size_t
69keyindex(struct hashtable *h, struct hashtablekey *k)
70{
71 size_t i;
72
73 i = k->hash & (h->cap - 1);
74 while (h->keys[i].str && !keyequal(&h->keys[i], k))
75 i = (i + 1) & (h->cap - 1);
76 return i;
77}
78
79void **
80htabput(struct hashtable *h, struct hashtablekey *k)
81{
82 struct hashtablekey *oldkeys;
83 void **oldvals;
84 size_t i, j, oldcap;
85
86 if (h->cap / 2 < h->len) {
87 oldkeys = h->keys;
88 oldvals = h->vals;
89 oldcap = h->cap;
90 h->cap *= 2;
91 h->keys = xreallocarray(NULL, h->cap, sizeof(h->keys[0]));
92 h->vals = xreallocarray(NULL, h->cap, sizeof(h->vals[0]));
93 for (i = 0; i < h->cap; ++i)
94 h->keys[i].str = NULL;
95 for (i = 0; i < oldcap; ++i) {
96 if (oldkeys[i].str) {
97 j = keyindex(h, &oldkeys[i]);
98 h->keys[j] = oldkeys[i];
99 h->vals[j] = oldvals[i];
100 }
101 }
102 free(oldkeys);
103 free(oldvals);
104 }
105 i = keyindex(h, k);
106 if (!h->keys[i].str) {
107 h->keys[i] = *k;
108 h->vals[i] = NULL;
109 ++h->len;
110 }
111
112 return &h->vals[i];
113}
114
115void *
116htabget(struct hashtable *h, struct hashtablekey *k)
117{
118 size_t i;
119
120 i = keyindex(h, k);
121 return h->keys[i].str ? h->vals[i] : NULL;
122}
123
124static inline uint_least32_t
125getle32(const void *p)
126{
127 const unsigned char *b = p;
128 uint_least32_t v;
129
130 v = b[0] & 0xfful;
131 v |= (b[1] & 0xfful) << 8;
132 v |= (b[2] & 0xfful) << 16;
133 v |= (b[3] & 0xfful) << 24;
134 return v;
135}
136
137static inline uint_least64_t
138getle64(const void *p)
139{
140 const unsigned char *b = p;
141 uint_least64_t v;
142
143 v = b[0] & 0xffull;
144 v |= (b[1] & 0xffull) << 8;
145 v |= (b[2] & 0xffull) << 16;
146 v |= (b[3] & 0xffull) << 24;
147 v |= (b[4] & 0xffull) << 32;
148 v |= (b[5] & 0xffull) << 40;
149 v |= (b[6] & 0xffull) << 48;
150 v |= (b[7] & 0xffull) << 56;
151 return v;
152}
153
154#if __STDC_VERSION__ >= 202311L && BITINT_MAXWIDTH >= 128
155#define uint128 unsigned _BitInt(128)
156#elif __SIZEOF_INT128__
157#define uint128 __uint128_t
158#endif
159
160static inline void
161mum(uint64_t *a, uint64_t *b)
162{
163#ifdef uint128
164 uint128 r;
165
166 r = *a;
167 r *= *b;
168 *a = r;
169 *b = r >> 64;
170#else
171 uint64_t al, ah, bl, bh, rl, rh;
172 uint64_t ll, lh, hl, hh, m;
173
174 al = (uint32_t)*a;
175 bl = (uint32_t)*b;
176 ah = *a >> 32;
177 bh = *b >> 32;
178 ll = al * bl;
179 lh = al * bh;
180 hl = ah * bl;
181 hh = ah * bh;
182
183 m = (ll >> 32) + lh + (hl & 0xffffffff);
184 rl = ll & 0xffffffff | m << 32;
185 rh = hh + (m >> 32) + (hl >> 32);
186 *a = rl;
187 *b = rh;
188#endif
189}
190
191static inline uint64_t
192mix(uint64_t a, uint64_t b)
193{
194 mum(&a, &b);
195 return a ^ b;
196}
197
198uint64_t
199rapidhashv1(const void *ptr, size_t len)
200{
201 static const uint64_t secret[] = {
202 0x2d358dccaa6c78a5ull,
203 0x8bb84b93962eacc9ull,
204 0x4b33a62ed433d4a3ull,
205 };
206 uint64_t seed[3];
207 const unsigned char *pos, *end;
208 int i;
209
210 pos = ptr;
211 end = pos + len;
212 seed[0] = 0xbdd89aa982704029ull;
213 seed[0] ^= mix(seed[0] ^ secret[0], secret[1]) ^ len;
214 if (len == 0) {
215 seed[1] = seed[2] = 0;
216 } else if (len < 4) {
217 seed[1] = (uint64_t)pos[0] << 56 | (uint64_t)pos[len > 1] << 32 | end[-1];
218 seed[2] = 0;
219 } else if (len <= 16) {
220 seed[1] = (uint64_t)getle32(pos) << 32 | getle32(end - 4);
221 if (len >= 8)
222 pos += 4, end -= 4;
223 seed[2] = (uint64_t)getle32(pos) << 32 | getle32(end - 4);
224 } else {
225 seed[1] = seed[2] = seed[0];
226 if (len > 48) {
227 do {
228 for (i = 0; i < 3; ++i, pos += 16)
229 seed[i] = mix(getle64(pos) ^ secret[i], getle64(pos + 8) ^ seed[i]);
230 } while (end - pos >= 48);
231 seed[0] ^= seed[1] ^ seed[2];
232 }
233 if (end - pos > 16) {
234 seed[0] ^= secret[1];
235 do seed[0] = mix(getle64(pos) ^ secret[2], getle64(pos + 8) ^ seed[0]);
236 while (pos += 16, end - pos > 16);
237 }
238 seed[1] = getle64(end - 16);
239 seed[2] = getle64(end - 8);
240 }
241 seed[1] ^= secret[1];
242 seed[2] ^= seed[0];
243 mum(&seed[1], &seed[2]);
244 return mix(seed[1] ^ secret[0] ^ len, seed[2] ^ secret[1]);
245}
