1 /* Copyright 2012-present Facebook, Inc.
2 * Licensed under the Apache License, Version 2.0 */
3
4 #include "watchman.h"
5
6 // Re-implementing hash tables again :-/
7
8 struct watchman_hash_bucket {
9 struct watchman_hash_bucket *next, *prev;
10 w_ht_val_t key, value;
11 };
12
13 struct watchman_hash_table {
14 uint32_t nelems;
15 uint32_t table_size;
16 struct watchman_hash_bucket **table;
17 const struct watchman_hash_funcs *funcs;
18 };
19
w_ht_new(uint32_t size_hint,const struct watchman_hash_funcs * funcs)20 w_ht_t *w_ht_new(uint32_t size_hint, const struct watchman_hash_funcs *funcs)
21 {
22 w_ht_t *ht = calloc(1, sizeof(*ht));
23
24 if (!ht) {
25 return NULL;
26 }
27
28 ht->table_size = next_power_2(size_hint);
29 ht->table = calloc(ht->table_size, sizeof(void*));
30 if (!ht->table) {
31 free(ht);
32 return NULL;
33 }
34
35 ht->funcs = funcs;
36 return ht;
37 }
38
w_ht_free_entries(w_ht_t * ht)39 void w_ht_free_entries(w_ht_t *ht)
40 {
41 struct watchman_hash_bucket *b;
42 uint32_t slot;
43
44 for (slot = 0; slot < ht->table_size; slot++) {
45 while (ht->table[slot]) {
46 b = ht->table[slot];
47 ht->table[slot] = b->next;
48
49 if (ht->funcs && ht->funcs->del_val) {
50 ht->funcs->del_val(b->value);
51 }
52 if (ht->funcs && ht->funcs->del_key) {
53 ht->funcs->del_key(b->key);
54 }
55 free(b);
56 }
57 }
58 ht->nelems = 0;
59 }
60
w_ht_free(w_ht_t * ht)61 void w_ht_free(w_ht_t *ht)
62 {
63 struct watchman_hash_bucket *b;
64 uint32_t slot;
65
66 for (slot = 0; slot < ht->table_size; slot++) {
67 while (ht->table[slot]) {
68 b = ht->table[slot];
69 ht->table[slot] = b->next;
70
71 if (ht->funcs && ht->funcs->del_val) {
72 ht->funcs->del_val(b->value);
73 }
74 if (ht->funcs && ht->funcs->del_key) {
75 ht->funcs->del_key(b->key);
76 }
77 free(b);
78 }
79 }
80 free(ht->table);
81 free(ht);
82 }
83
compute_hash(w_ht_t * ht,w_ht_val_t key)84 static inline uint32_t compute_hash(w_ht_t *ht, w_ht_val_t key)
85 {
86 if (ht->funcs && ht->funcs->hash_key) {
87 return ht->funcs->hash_key(key);
88 }
89 return (uint32_t)key;
90 }
91
equal_key(w_ht_t * ht,w_ht_val_t a,w_ht_val_t b)92 static inline bool equal_key(w_ht_t *ht, w_ht_val_t a, w_ht_val_t b)
93 {
94 if (ht->funcs && ht->funcs->equal_key) {
95 return ht->funcs->equal_key(a, b);
96 }
97 return a == b;
98 }
99
resize(w_ht_t * ht,uint32_t newsize)100 static void resize(w_ht_t *ht, uint32_t newsize)
101 {
102 struct watchman_hash_bucket **table;
103 uint32_t slot;
104
105 table = calloc(newsize, sizeof(void*));
106 if (!table) {
107 return;
108 }
109
110 // Don't log from in here, as we may be called with
111 // the client lock held, and attempting to lock in
112 // here will deadlock with ourselves!
113
114 for (slot = 0; slot < ht->table_size; slot++) {
115 while (ht->table[slot]) {
116 struct watchman_hash_bucket *b = ht->table[slot];
117 uint32_t nslot;
118
119 ht->table[slot] = b->next;
120
121 nslot = compute_hash(ht, b->key) & (newsize - 1);
122 b->prev = NULL;
123 b->next = table[nslot];
124 if (b->next) {
125 b->next->prev = b;
126 }
127 table[nslot] = b;
128 }
129 }
130 free(ht->table);
131 ht->table = table;
132 ht->table_size = newsize;
133 }
134
w_ht_set(w_ht_t * ht,w_ht_val_t key,w_ht_val_t value)135 bool w_ht_set(w_ht_t *ht, w_ht_val_t key, w_ht_val_t value)
136 {
137 return w_ht_insert(ht, key, value, false);
138 }
139
w_ht_replace(w_ht_t * ht,w_ht_val_t key,w_ht_val_t value)140 bool w_ht_replace(w_ht_t *ht, w_ht_val_t key, w_ht_val_t value)
141 {
142 return w_ht_insert(ht, key, value, true);
143 }
144
145 /* Compute the ideal table size.
146 * Hash table literature suggests that the ideal load factor for a
147 * table is approximately 0.7.
148 * Our ideal size is therefore a bit larger, and rounded up to
149 * a power of 2 */
ideal_size(w_ht_t * ht)150 static inline uint32_t ideal_size(w_ht_t *ht)
151 {
152 return next_power_2(ht->nelems * 3 / 2);
153 }
154
w_ht_insert(w_ht_t * ht,w_ht_val_t key,w_ht_val_t value,bool replace)155 bool w_ht_insert(w_ht_t *ht, w_ht_val_t key, w_ht_val_t value, bool replace)
156 {
157 struct watchman_hash_bucket *b;
158 uint32_t slot = compute_hash(ht, key) & (ht->table_size - 1);
159 uint32_t ideal;
160
161 for (b = ht->table[slot]; b; b = b->next) {
162 if (equal_key(ht, key, b->key)) {
163 if (!replace) {
164 errno = EEXIST;
165 return false;
166 }
167
168 /* copy the value before we delete the old one, in case
169 * the values somehow reference the same thing; we don't
170 * want to delete it from under ourselves */
171 if (ht->funcs && ht->funcs->copy_val) {
172 value = ht->funcs->copy_val(value);
173 }
174 if (ht->funcs && ht->funcs->del_val) {
175 ht->funcs->del_val(b->value);
176 }
177 b->value = value;
178
179 return true;
180 }
181 }
182
183 b = malloc(sizeof(*b));
184 if (!b) {
185 errno = ENOMEM;
186 return false;
187 }
188
189 if (ht->funcs && ht->funcs->copy_key) {
190 key = ht->funcs->copy_key(key);
191 }
192 if (ht->funcs && ht->funcs->copy_val) {
193 value = ht->funcs->copy_val(value);
194 }
195 b->key = key;
196 b->value = value;
197 b->prev = NULL;
198 b->next = ht->table[slot];
199 if (b->next) {
200 b->next->prev = b;
201 }
202 ht->table[slot] = b;
203 ht->nelems++;
204
205 ideal = ideal_size(ht);
206 if (ht->nelems > ideal) {
207 resize(ht, ideal);
208 }
209
210 return true;
211 }
212
w_ht_get(w_ht_t * ht,w_ht_val_t key)213 w_ht_val_t w_ht_get(w_ht_t *ht, w_ht_val_t key)
214 {
215 w_ht_val_t val = 0;
216
217 w_ht_lookup(ht, key, &val, false);
218 return val;
219 }
220
w_ht_lookup(w_ht_t * ht,w_ht_val_t key,w_ht_val_t * val,bool copy)221 bool w_ht_lookup(w_ht_t *ht, w_ht_val_t key, w_ht_val_t *val, bool copy)
222 {
223 struct watchman_hash_bucket *b;
224 uint32_t slot = compute_hash(ht, key) & (ht->table_size - 1);
225
226 for (b = ht->table[slot]; b; b = b->next) {
227 if (equal_key(ht, key, b->key)) {
228 if (copy && ht->funcs && ht->funcs->copy_val) {
229 *val = ht->funcs->copy_val(b->value);
230 } else {
231 *val = b->value;
232 }
233 return true;
234 }
235 }
236
237 return false;
238 }
239
delete_bucket(w_ht_t * ht,struct watchman_hash_bucket * b,int slot,bool do_resize)240 static inline void delete_bucket(w_ht_t *ht,
241 struct watchman_hash_bucket *b, int slot,
242 bool do_resize)
243 {
244 if (b->next) {
245 b->next->prev = b->prev;
246 }
247 if (b->prev) {
248 b->prev->next = b->next;
249 }
250 if (b == ht->table[slot]) {
251 ht->table[slot] = b->next;
252 }
253 if (ht->funcs && ht->funcs->del_key) {
254 ht->funcs->del_key(b->key);
255 }
256 if (ht->funcs && ht->funcs->del_val) {
257 ht->funcs->del_val(b->value);
258 }
259 free(b);
260 ht->nelems--;
261
262 if (do_resize) {
263 uint32_t shrink = ideal_size(ht);
264
265 if (ht->table_size > shrink) {
266 resize(ht, shrink);
267 }
268 }
269 }
270
perform_delete(w_ht_t * ht,w_ht_val_t key,bool do_resize)271 static bool perform_delete(w_ht_t *ht, w_ht_val_t key, bool do_resize)
272 {
273 struct watchman_hash_bucket *b;
274 uint32_t slot = compute_hash(ht, key) & (ht->table_size - 1);
275
276 for (b = ht->table[slot]; b; b = b->next) {
277 if (equal_key(ht, key, b->key)) {
278 delete_bucket(ht, b, slot, do_resize);
279 return true;
280 }
281 }
282 return false;
283 }
284
w_ht_del(w_ht_t * ht,w_ht_val_t key)285 bool w_ht_del(w_ht_t *ht, w_ht_val_t key)
286 {
287 return perform_delete(ht, key, true);
288 }
289
w_ht_size(w_ht_t * ht)290 uint32_t w_ht_size(w_ht_t *ht)
291 {
292 return ht->nelems;
293 }
294
w_ht_num_buckets(w_ht_t * ht)295 uint32_t w_ht_num_buckets(w_ht_t *ht)
296 {
297 return ht->table_size;
298 }
299
w_ht_first(w_ht_t * ht,w_ht_iter_t * iter)300 bool w_ht_first(w_ht_t *ht, w_ht_iter_t *iter)
301 {
302 if (!ht) return false;
303 if (!ht->nelems) return false;
304
305 iter->slot = (uint32_t)-1;
306 iter->ptr = NULL;
307
308 return w_ht_next(ht, iter);
309 }
310
w_ht_next(w_ht_t * ht,w_ht_iter_t * iter)311 bool w_ht_next(w_ht_t *ht, w_ht_iter_t *iter)
312 {
313 struct watchman_hash_bucket *b = iter->ptr;
314
315 if (iter->slot != (uint32_t)-1 && iter->slot >= ht->table_size) {
316 return false;
317 }
318
319 if (b && b->next) {
320 iter->ptr = b->next;
321 } else {
322 do {
323 iter->slot++;
324 if (iter->slot >= ht->table_size) {
325 return false;
326 }
327 iter->ptr = ht->table[iter->slot];
328 } while (!iter->ptr);
329 }
330
331 if (iter->ptr) {
332 b = iter->ptr;
333 iter->key = b->key;
334 iter->value = b->value;
335
336 return true;
337 }
338
339 return false;
340 }
341
342 /* iterator aware delete */
w_ht_iter_del(w_ht_t * ht,w_ht_iter_t * iter)343 bool w_ht_iter_del(w_ht_t *ht, w_ht_iter_t *iter)
344 {
345 struct watchman_hash_bucket *b;
346
347 b = iter->ptr;
348 if (!iter->ptr) {
349 return false;
350 }
351
352 /* walk back to the prior iterm, because ht_next will be used
353 * to walk forwards; we want to land on the next item and not skip
354 * it */
355 if (b->prev) {
356 iter->ptr = b->prev;
357 } else {
358 /* we were the front of that bucket slot, arrange for iteration
359 * to find the front of it again */
360 iter->ptr = NULL;
361 }
362
363 delete_bucket(ht, b, iter->slot, false);
364
365 return true;
366 }
367
w_ht_string_copy(w_ht_val_t key)368 w_ht_val_t w_ht_string_copy(w_ht_val_t key)
369 {
370 w_string_addref(w_ht_val_ptr(key));
371 return key;
372 }
373
w_ht_string_del(w_ht_val_t key)374 void w_ht_string_del(w_ht_val_t key)
375 {
376 w_string_delref(w_ht_val_ptr(key));
377 }
378
w_ht_string_equal(w_ht_val_t a,w_ht_val_t b)379 bool w_ht_string_equal(w_ht_val_t a, w_ht_val_t b)
380 {
381 return w_string_equal(w_ht_val_ptr(a), w_ht_val_ptr(b));
382 }
383
w_ht_string_hash(w_ht_val_t key)384 uint32_t w_ht_string_hash(w_ht_val_t key)
385 {
386 return ((w_string_t*)w_ht_val_ptr(key))->hval;
387 }
388
389 const struct watchman_hash_funcs w_ht_string_funcs = {
390 w_ht_string_copy,
391 w_ht_string_del,
392 w_ht_string_equal,
393 w_ht_string_hash,
394 NULL,
395 NULL
396 };
397
398 const struct watchman_hash_funcs w_ht_string_val_funcs = {
399 NULL, // copy_key
400 NULL, // del_key
401 NULL, // equal_key
402 NULL, // hash_key
403 w_ht_string_copy, // copy_val
404 w_ht_string_del // del_val
405 };
406
407 const struct watchman_hash_funcs w_ht_dict_funcs = {
408 w_ht_string_copy,
409 w_ht_string_del,
410 w_ht_string_equal,
411 w_ht_string_hash,
412 w_ht_string_copy,
413 w_ht_string_del
414 };
415
416 /* vim:ts=2:sw=2:et:
417 */
418