3 /*
4 * Simple linear hashing implementation
5 *
6 * Linear hashing is a hash table algorithm by Witold Litwin (1980)
7 * which grows the table on demand without rehashing existing objects.
8 *
9 * This implementation employs a conventional hash function C whose
10 * output length is assumed to be greater than the order of the table,
11 * i.e. the base-2 logarithm of the number of slots. Hash collisions
12 * are resolved by chaining.
13 *
14 * The hash table consists in fact of two tables which are consecutive
15 * in memory. Each table represents N = 1 << n many slots of the
16 * table. Example (n = 2, N = 4):
17 *
18 * [....][....]
19 * 0123 4567
20 *
21 * In what follows, we refer to the two tables as the lower table and
22 * the higher table.
23 *
24 * C gives rise to a sequence of hash functions C_k via C_k(key) :=
25 * lower k bits of C(key). In terms of C_k the lower and higher hash
26 * functions, h and H, are defined by h = C_n and H = C_{n+1}. Hence
27 * h(key) always corresponds to a slot in the lower table while H(key)
28 * corresponds to a slot in either table. Both functions are trivial to
29 * compute given C(key).
30 *
31 * The algorithm also maintains a split position s which corresponds to
32 * a slot of the lower table and starts out at zero.
33 *
34 * [s...][....]
35 * 0123 4567
36 *
37 * The linear hash function L is defined by L(key) = H(key) if h(key)
38 * < s, and L(key) = h(key) otherwise. In other words, L(key) is either
39 * the lower or the higher hash value, depending on the relation between
40 * the lower hash value and s. The higher hash function applies for all
41 * keys whose lower hash value is smaller than s. Initially we have L = h.
42 *
43 * On insertion, if the table load is large, the chain of entries which
44 * hash to s is split by transitioning from h to H.
45 *
46 * For an existing key, we have either H(key) = h(key) or H(key) =
47 * h(key) + 1 << n. That is, the most significant bit of H(key) tells
48 * whether this entry must be moved from its slot in the low table to the
49 * corresponding slot in the high table. Approximately half the entries
50 * will be moved this way. To reflect the fact that from now on L(key)
51 * = H(key) for all keys with h(key) = s, s is increased by one.
52 *
53 * Each time s reaches 1 << n, the upper bound of the lower table, we
54 * have L = H. In this case the hash table size is doubled, and the split
55 * position is reset to zero. Moreover, h and H are redefined as h :=
56 * C_{n+1} (i.e., the new h becomes the former H), and H := C_{n+2}. This
57 * means the table order n has increased by one, and a new round begins.
58 *
59 * This implementation includes an API for iterating over all entries
60 * in the hash table which avoids callback functions. Instead an opaque
61 * iterator structure is provided together with a set of functions that
62 * create or operate on such a structure.
63 *
64 * While shrinking a linear hash table can performed essentially
65 * by reversing the steps for growing described above, this is not
66 * implemented since it is not needed for tfortune.
67 */
69 #include "tf.h"
71 struct lh_slot {
72 struct linhash_item item;
73 uint32_t hash;
74 struct lh_slot *next;
75 };
77 struct linhash_table {
78 struct lh_slot **slots;
79 unsigned order;
80 uint32_t num_items; /* how many items have been inserted so far. */
81 uint32_t split_position;
82 };
84 struct linhash_iterator {
85 /* these are used regardless of whether comp is NULL */
86 struct linhash_table *t;
87 uint32_t idx;
88 /* comp == NULL means: iterate in hash order */
89 linhash_comparator *comp;
90 /* only used if comp == NULL */
91 struct lh_slot *head, *prev, *next;
92 /* only used if comp != NULL */
93 struct linhash_item **items;
94 bool reverse;
95 };
97 static uint32_t lh_num_slots_low(const struct linhash_table *t)
98 {
99 return (uint32_t)1 << t->order;
100 }
102 static uint32_t lh_num_slots_high(const struct linhash_table *t)
103 {
104 return lh_num_slots_low(t) * 2;
105 }
107 static uint32_t lh_index_low(uint32_t hash, const struct linhash_table *t)
108 {
109 return hash % lh_num_slots_low(t);
110 }
112 static uint32_t lh_index_high(uint32_t hash, const struct linhash_table *t)
113 {
114 return hash % lh_num_slots_high(t);
115 }
117 static bool lh_must_grow(const struct linhash_table *t)
118 {
119 return t->num_items >= lh_num_slots_high(t) / 2;
120 }
122 /* The simple DJB (Daniel J Bernstein) hash is good enough here. */
123 static uint32_t lh_hash(const char *data)
124 {
125 uint32_t h = 5381;
126 const unsigned char *c = (typeof(c))data;
128 while (*(c++))
129 h = h * 33 + *c;
130 return h;
131 }
133 /*
134 * Create a new table for linear hashing.
135 *
136 * The order argument determines the initial number of slots: it is given by 2
137 * << order. The hash table grows on demand, and the point of linear hashing is
138 * the ability to cheaply grow the table, so specifying anything greater than
139 * zero is probably not necessary.
140 *
141 * The functtion returns an opaque pointer which serves as the handle to the
142 * newly created hash table. Most functions of the linhash API take such a
143 * pointer to know the table to operate on. This function either succeeds or
144 * terminates, it never returns NULL.
145 */
146 struct linhash_table *linhash_new(uint32_t order)
147 {
148 struct linhash_table *t;
149 uint32_t ns;
151 DEBUG_LOG("creating order %u hash table\n", order);
152 t = xmalloc(sizeof(*t));
153 t->order = order;
154 t->num_items = 0;
155 t->split_position = 0;
156 ns = lh_num_slots_high(t);
157 t->slots = xcalloc(ns * sizeof(*t->slots));
158 return t;
159 }
161 static uint32_t lh_index(uint32_t hash, const struct linhash_table *t)
162 {
163 uint32_t low = lh_index_low(hash, t);
165 if (low >= t->split_position)
166 return low;
167 return lh_index_high(hash, t);
168 }
170 static void lh_split_slot(struct linhash_table *t)
171 {
172 struct lh_slot *prev, *next, *s;
173 uint32_t sp = t->split_position;
175 DEBUG_LOG("splitting slot %u\n", sp);
176 for (prev = NULL, s = t->slots[sp]; s;) {
177 uint32_t idx = lh_index_high(s->hash, t);
178 if (idx == sp) {
179 prev = s;
180 s = s->next;
181 continue;
182 }
183 DEBUG_LOG("moving %s up from slot %u to slot %u\n",
184 s->item.key, sp, idx);
185 if (t->slots[sp] == s)
186 t->slots[sp] = s->next;
187 if (prev)
188 prev->next = s->next;
189 next = s->next;
190 s->next = t->slots[idx];
191 t->slots[idx] = s;
192 s = next;
193 }
194 DEBUG_LOG("slot %u has been split\n", sp);
195 if (!t->slots[sp])
196 DEBUG_LOG("slot #%u has become empty\n", sp);
197 }
199 static void lh_grow_table(struct linhash_table *t)
200 {
201 uint32_t idx, ns;
203 DEBUG_LOG("growing hash table to order %u\n", ++t->order);
204 ns = lh_num_slots_high(t);
205 t->slots = xrealloc(t->slots, ns * sizeof(*t->slots));
206 idx = lh_num_slots_low(t);
207 memset(t->slots + idx, 0, (ns - idx) * sizeof(*t->slots));
208 }
210 static struct lh_slot *lh_lookup(const char *key,
211 const struct linhash_table *t, uint32_t *hashp, uint32_t *idxp,
212 struct lh_slot **prevp)
213 {
214 struct lh_slot *s, *prev;
215 uint32_t hash, idx;
217 if (!t)
218 return NULL;
219 hash = lh_hash(key);
220 idx = lh_index(hash, t);
221 //DEBUG_LOG("key %s, hash: %u, idx: %u\n", key, hash, idx);
222 if (hashp)
223 *hashp = hash;
224 if (idxp)
225 *idxp = idx;
226 for (s = t->slots[idx], prev = NULL; s; prev = s, s = s->next) {
227 //DEBUG_LOG("comparing %s vs. %s\n", key, s->item.key);
228 if (strcmp(s->item.key, key))
229 continue;
230 /* found it */
231 if (prevp)
232 *prevp = prev;
233 return s;
234 }
235 if (prevp)
236 *prevp = NULL;
237 return NULL;
238 }
240 /**
241 * Find the entry identified by a key.
242 *
243 * \param key The key to look up.
244 * \param t Where to look up the key.
245 */
246 struct linhash_item *linhash_lookup(const char *key,
247 const struct linhash_table *t)
248 {
249 struct lh_slot *s = lh_lookup(key, t, NULL, NULL, NULL);
251 if (!s)
252 return NULL;
253 return &s->item;
254 }
256 static void *lh_remove(struct lh_slot *s, struct lh_slot *prev, uint32_t idx, struct linhash_table *t)
257 {
258 void *obj;
260 if (!s)
261 return NULL;
262 t->num_items--;
263 obj = s->item.object;
264 if (prev)
265 prev->next = s->next;
266 else
267 t->slots[idx] = s->next;
268 free(s);
269 return obj;
270 }
272 /* Note: This renders all existing iterators stale. */
273 void *linhash_remove(const char *key, struct linhash_table *t)
274 {
275 uint32_t idx;
276 struct lh_slot *prev, *s = lh_lookup(key, t, NULL, &idx, &prev);
278 return lh_remove(s, prev, idx, t);
279 }
281 static void *lh_iterator_remove_current(struct linhash_iterator *iter)
282 {
283 void *obj;
285 assert(!iter->comp);
287 return NULL;
288 obj = lh_remove(iter->head, iter->prev, iter->idx, iter->t);
290 return obj;
291 }
293 static struct lh_slot *lh_first_nonempty_slot(uint32_t *idxp,
294 const struct linhash_table *t)
295 {
296 uint32_t ns = lh_num_slots_high(t);
298 for (; *idxp < ns; (*idxp)++)
299 if (t->slots[*idxp])
300 return t->slots[*idxp];
301 return NULL;
302 }
304 static void lh_iter_init(struct linhash_iterator *iter, uint32_t idx)
305 {
306 iter->idx = idx;
307 iter->prev = NULL;
311 }
313 /*
315 * removed with lh_iterator_remove_current(), iter->head points to its
316 * predecessor in the list.
317 */
318 void linhash_iterator_next(struct linhash_iterator *iter)
319 {
320 if (iter->comp) {
321 if (iter->reverse)
322 iter->idx--;
323 else
324 iter->idx++;
325 return;
326 }
327 if (iter->next) {
330 iter->next = iter->next->next;
331 return;
332 }
333 lh_iter_init(iter, iter->idx + 1);
334 }
336 struct linhash_item *linhash_iterator_item(const struct linhash_iterator *iter)
337 {
338 if (iter->comp) {
339 if (iter->idx >= iter->t->num_items)
340 return NULL;
341 return iter->items[iter->idx];
342 }
344 return NULL;
346 }
348 void linhash_iterator_free(struct linhash_iterator *iter)
349 {
350 if (!iter)
351 return;
352 if (iter->comp)
353 free(iter->items);
354 free(iter);
355 }
357 /* always succeeds. reverse order is only respected if a comparator is given. */
358 struct linhash_iterator *linhash_iterator_new(struct linhash_table *t,
359 linhash_comparator *comp, bool reverse_sort_order)
360 {
361 struct linhash_iterator *iter = xmalloc(sizeof(*iter)), *iter2;
362 struct linhash_item *item;
363 unsigned n;
365 iter->t = t;
366 iter->comp = comp;
367 if (!comp) {
368 lh_iter_init(iter, 0);
369 return iter;
370 }
371 iter->reverse = reverse_sort_order;
372 iter2 = linhash_iterator_new(t, NULL, false);
373 iter->items = xmalloc(t->num_items * sizeof(struct linhash_item *));
374 for (
375 n = 0;
376 (item = linhash_iterator_item(iter2));
377 linhash_iterator_next(iter2)
378 )
379 iter->items[n++] = item;
380 linhash_iterator_free(iter2);
381 qsort(iter->items, t->num_items, sizeof(struct linhash_iter *),
382 (int (*)(const void *, const void *))comp);
383 iter->idx = reverse_sort_order? t->num_items - 1 : 0;
384 return iter;
385 }
387 /* Deallocate the resources occupied by the given hash table. */
388 void linhash_free(struct linhash_table *t)
389 {
390 struct linhash_iterator *iter;
391 struct linhash_item *itemp;
393 if (!t)
394 return;
395 for (
396 iter = linhash_iterator_new(t, NULL, false);
397 (itemp = linhash_iterator_item(iter));
398 linhash_iterator_next(iter)
399 )
400 lh_iterator_remove_current(iter);
401 linhash_iterator_free(iter);
402 assert(t->num_items == 0);
403 free(t->slots);
404 free(t);
405 }
407 /* returns item in first arg if key already exists */
408 int linhash_insert(struct linhash_item *item, struct linhash_table *t,
409 void ***object)
410 {
411 struct lh_slot *s;
412 uint32_t idx, hash;
414 s = lh_lookup(item->key, t, &hash, &idx, NULL);
415 if (s) {
416 if (object)
417 *object = &s->item.object;
418 return -E_LH_EXIST;
419 }
420 s = xmalloc(sizeof(*s));
421 s->item = *item;
422 s->hash = hash;
423 DEBUG_LOG("inserting item #%u, key: %s, hash: %u, idx: %u\n",
424 t->num_items, item->key, hash, idx);
425 s->next = t->slots[idx];
426 t->slots[idx] = s;
427 t->num_items++;
429 if (!lh_must_grow(t)) {
430 DEBUG_LOG("no need to grow\n");
431 return 0;
432 }
433 lh_split_slot(t);
434 t->split_position++;
435 if (t->split_position < lh_num_slots_low(t))
436 return 1;
437 t->split_position = 0;
438 lh_grow_table(t);
439 return 2;
440 }
442 uint32_t linhash_num_items(const struct linhash_table *t)
443 {
444 return t->num_items;
445 }
447 char *linhash_statistics(const struct linhash_table *t)
448 {
449 uint32_t min_fill = -1, max_fill = 0, n, idx, ns;
450 uint32_t fill_count[11] = {0};
451 char *result;
453 ns = lh_num_slots_low(t) + t->split_position;
454 for (idx = 0; idx < ns; idx++) {
455 struct lh_slot *s;
456 for (n = 0, s = t->slots[idx]; s; s = s->next, n++)
457 ; /* nothing */
458 min_fill = MIN(min_fill, n);
459 max_fill = MAX(max_fill, n);
460 fill_count[n < 10? n : 10]++;
461 }
462 xasprintf(&result,
463 "order............... %2u\n"
464 "num slots........... %u\n"
465 "num items (table)... %u\n"
467 "min fill............ %2u\n"
468 "max fill............ %2u\n"
469 "max count[0]....... %3u%% (%u)\n"
470 "max count[1]....... %3u%% (%u)\n"
471 "max count[2]....... %3u%% (%u)\n"
472 "max count[3]....... %3u%% (%u)\n"
473 "max count[4]....... %3u%% (%u)\n"
474 "max count[5]....... %3u%% (%u)\n"
475 "max count[6]....... %3u%% (%u)\n"
476 "max count[7]....... %3u%% (%u)\n"
477 "max count[8]....... %3u%% (%u)\n"
478 "max count[9]....... %3u%% (%u)\n"
479 "max count[10+]..... %3u%% (%u)\n"
480 ,
481 t->order,
482 ns,
483 t->num_items,
484 (t->num_items * 100 + (ns / 2)) / ns,
485 min_fill,
486 max_fill,
487 100 * fill_count[0] / ns, fill_count[0],
488 100 * fill_count[1] / ns, fill_count[1],
489 100 * fill_count[2] / ns, fill_count[2],
490 100 * fill_count[3] / ns, fill_count[3],
491 100 * fill_count[4] / ns, fill_count[4],
492 100 * fill_count[5] / ns, fill_count[5],
493 100 * fill_count[6] / ns, fill_count[6],
494 100 * fill_count[7] / ns, fill_count[7],
495 100 * fill_count[8] / ns, fill_count[8],
496 100 * fill_count[9] / ns, fill_count[9],
497 100 * fill_count[10] / ns, fill_count[10]
498 );
499 return result;
500 }