1 /* A generic hash table package. */
10 # define ZALLOC(Ht, N) obstack_alloc (&(ht->ht_obstack), (N))
12 # define ZALLOC(Ht, N) malloc ((N))
15 #define BUCKET_HEAD(ht, idx) ((ht)->hash_table[(idx)])
17 static void hash_free_0 (HT *, int);
21 unsigned long candidate;
23 /* No even number and none less than 10 will be passed here. */
24 unsigned long divn = 3;
25 unsigned long sq = divn * divn;
27 while (sq < candidate && (candidate % divn))
34 return (candidate % divn);
37 /* Round a given number up to the nearest prime. */
40 next_prime (candidate)
41 unsigned long candidate;
43 /* Make it definitely odd. */
46 while (!is_prime (candidate))
53 hash_free_entry (HT *ht, HASH_ENT *e)
56 e->next = ht->hash_free_entry_list;
57 ht->hash_free_entry_list = e;
61 hash_allocate_entry (HT *ht)
64 if (ht->hash_free_entry_list)
66 new = ht->hash_free_entry_list;
67 ht->hash_free_entry_list = new->next;
71 new = (HASH_ENT *) ZALLOC (ht, sizeof (HASH_ENT));
77 hash_get_n_slots_used (const HT *ht)
79 return ht->hash_n_slots_used;
85 hash_rehash (HT *ht, unsigned int new_table_size)
90 if (ht->hash_table_size <= 0 || new_table_size == 0)
93 ht_new = hash_initialize (new_table_size, ht->hash_key_freer,
94 ht->hash_hash, ht->hash_key_comparator);
99 for (i = 0; i < ht->hash_table_size; i++)
101 HASH_ENT *p = BUCKET_HEAD (ht, i);
102 for ( /* empty */ ; p; p = p->next)
105 const void *already_in_table;
106 already_in_table = hash_insert_if_absent (ht_new, p->key, &failed);
107 assert (failed == 0 && already_in_table == 0);
114 assert (hash_table_ok (ht_new));
119 /* FIXME: fill in ht_new->n_slots_used and other statistics fields. */
127 hash_get_max_chain_length (HT *ht)
130 unsigned int max_chain_length = 0;
132 if (!ht->hash_dirty_max_chain_length)
133 return ht->hash_max_chain_length;
135 for (i = 0; i < ht->hash_table_size; i++)
137 unsigned int chain_length = 0;
138 HASH_ENT *p = BUCKET_HEAD (ht, i);
139 for ( /* empty */ ; p; p = p->next)
141 if (chain_length > max_chain_length)
142 max_chain_length = chain_length;
145 ht->hash_max_chain_length = max_chain_length;
146 ht->hash_dirty_max_chain_length = 0;
147 return ht->hash_max_chain_length;
151 hash_get_n_keys (const HT *ht)
153 return ht->hash_n_keys;
157 hash_get_table_size (const HT *ht)
159 return ht->hash_table_size;
162 /* CANDIDATE_TABLE_SIZE need not be prime. If WHEN_TO_REHASH (FIXME: add
163 this parameter) is positive, when that percentage of table entries have
164 been used, the table size is increased; then a new, larger table
165 (GROW_FACTOR (FIXME: maybe add this parameter) times larger than the previous
166 size) is allocated and all entries in the old table are rehashed into
167 the new, larger one. The old table is freed. If WHEN_TO_REHASH is zero
168 or negative, the table is never resized.
170 The function returns non-zero
171 - if CANDIDATE_TABLE_SIZE is zero or negative
172 - if KEY_COMPARATOR or HASH is null
173 - if it was unable to allocate sufficient storage for the hash table
174 - if WHEN_TO_REHASH is zero or negative
175 Otherwise it returns zero. */
178 hash_initialize (unsigned int candidate_table_size,
179 Hash_key_freer_type key_freer,
180 unsigned int (*hash) (const void *, unsigned int),
181 int (*key_comparator) (const void *, const void *))
185 unsigned int table_size;
187 if (candidate_table_size <= 0)
190 if (hash == NULL || key_comparator == NULL)
193 ht = (HT *) malloc (sizeof (HT));
197 table_size = next_prime (candidate_table_size);
198 ht->hash_table = (HASH_ENT **) malloc (table_size * sizeof (HASH_ENT *));
199 if (ht->hash_table == NULL)
202 for (i = 0; i < table_size; i++)
204 BUCKET_HEAD (ht, i) = NULL;
207 ht->hash_free_entry_list = NULL;
208 ht->hash_table_size = table_size;
209 ht->hash_hash = hash;
210 ht->hash_key_comparator = key_comparator;
211 ht->hash_key_freer = key_freer;
212 ht->hash_n_slots_used = 0;
213 ht->hash_max_chain_length = 0;
215 ht->hash_dirty_max_chain_length = 0;
217 obstack_init (&(ht->ht_obstack));
223 /* This private function is used to help with insertion and deletion.
224 If E does *not* compare equal to the key of any entry in the table,
226 When E matches an entry in the table, return a pointer to the matching
227 entry. When DELETE is non-zero and E matches an entry in the table,
228 unlink the matching entry. Set *CHAIN_LENGTH to the number of keys
229 that have hashed to the bucket E hashed to. */
232 hash_find_entry (HT *ht, const void *e, unsigned int *table_idx,
233 unsigned int *chain_length, int delete)
239 idx = ht->hash_hash (e, ht->hash_table_size);
240 assert (idx < ht->hash_table_size);
245 prev = ht->hash_table[idx];
251 if (ht->hash_key_comparator (e, prev->key) == 0)
254 ht->hash_table[idx] = prev->next;
263 if (ht->hash_key_comparator (e, p->key) == 0)
277 prev->next = p->next;
282 /* Return non-zero if E is already in the table, zero otherwise. */
285 hash_query_in_table (const HT *ht, const void *e)
290 idx = ht->hash_hash (e, ht->hash_table_size);
291 assert (idx < ht->hash_table_size);
292 for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
293 if (ht->hash_key_comparator (e, p->key) == 0)
299 hash_lookup (const HT *ht, const void *e)
304 idx = ht->hash_hash (e, ht->hash_table_size);
305 assert (idx < ht->hash_table_size);
306 for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
307 if (ht->hash_key_comparator (e, p->key) == 0)
312 /* If E matches an entry already in the hash table, don't modify the
313 table and return a pointer to the matched entry. If E does not
314 match any item in the table, insert E and return NULL.
315 If the storage required for insertion cannot be allocated
316 set *FAILED to non-zero and return NULL. */
319 hash_insert_if_absent (HT *ht, const void *e, int *failed)
324 unsigned int chain_length;
326 assert (e != NULL); /* Can't insert a NULL key. */
329 ent = hash_find_entry (ht, e, &idx, &chain_length, 0);
332 /* E matches a key from an entry already in the table. */
336 new = hash_allocate_entry (ht);
343 new->key = (void *) e;
344 new->next = BUCKET_HEAD (ht, idx);
345 BUCKET_HEAD (ht, idx) = new;
347 if (chain_length == 0)
348 ++(ht->hash_n_slots_used);
350 /* The insertion has just increased chain_length by 1. */
353 if (chain_length > ht->hash_max_chain_length)
354 ht->hash_max_chain_length = chain_length;
357 if ((double) ht->hash_n_keys / ht->hash_table_size > 0.80)
359 unsigned int new_size;
360 new_size = next_prime (2 * ht->hash_table_size + 1);
361 *failed = hash_rehash (ht, new_size);
365 assert (hash_table_ok (ht));
371 /* If E is already in the table, remove it and return a pointer to
372 the just-deleted key (the user may want to deallocate its storage).
373 If E is not in the table, don't modify the table and return NULL. */
376 hash_delete_if_present (HT *ht, const void *e)
381 unsigned int chain_length;
383 ent = hash_find_entry (ht, e, &idx, &chain_length, 1);
387 if (ent->next == NULL && chain_length == 1)
388 --(ht->hash_n_slots_used);
393 ht->hash_dirty_max_chain_length = 1;
394 if (ent->next == NULL && chain_length < ht->hash_max_chain_length)
395 ht->hash_dirty_max_chain_length = 0;
397 hash_free_entry (ht, ent);
400 assert (hash_table_ok (ht));
406 hash_print_statistics (const HT *ht, FILE *stream)
408 unsigned int n_slots_used;
410 unsigned int max_chain_length;
413 err = hash_get_statistics (ht, &n_slots_used, &n_keys, &max_chain_length);
415 fprintf (stream, "table size: %d\n", ht->hash_table_size);
416 fprintf (stream, "# slots used: %u (%.2f%%)\n", n_slots_used,
417 (100.0 * n_slots_used) / ht->hash_table_size);
418 fprintf (stream, "# keys: %u\n", n_keys);
419 fprintf (stream, "max chain length: %u\n", max_chain_length);
422 /* If there is *NO* table (so, no meaningful stats) return non-zero
423 and don't reference the argument pointers. Otherwise compute the
424 performance statistics and return non-zero. */
427 hash_get_statistics (const HT *ht,
428 unsigned int *n_slots_used,
429 unsigned int *n_keys,
430 unsigned int *max_chain_length)
434 if (ht == NULL || ht->hash_table == NULL)
437 *max_chain_length = 0;
441 for (i = 0; i < ht->hash_table_size; i++)
443 unsigned int chain_length = 0;
446 p = BUCKET_HEAD (ht, i);
450 for (; p; p = p->next)
453 *n_keys += chain_length;
454 if (chain_length > *max_chain_length)
455 *max_chain_length = chain_length;
461 hash_table_ok (HT *ht)
464 unsigned int n_slots_used;
466 unsigned int max_chain_length;
468 if (ht == NULL || ht->hash_table == NULL)
471 code = hash_get_statistics (ht, &n_slots_used, &n_keys,
475 || n_slots_used != ht->hash_n_slots_used
476 || n_keys != ht->hash_n_keys
477 || max_chain_length != hash_get_max_chain_length (ht))
483 /* See hash_do_for_each_2 (below) for a variant. */
486 hash_do_for_each (HT *ht, void (*f) (void *e, void *aux), void *aux)
491 assert (hash_table_ok (ht));
494 if (ht->hash_table == NULL)
497 for (i = 0; i < ht->hash_table_size; i++)
500 for (p = BUCKET_HEAD (ht, i); p; p = p->next)
507 /* Just like hash_do_for_each, except that function F returns an int
508 that can signal (when non-zero) we should return early. */
511 hash_do_for_each_2 (HT *ht, int (*f) (void *e, void *aux), void *aux)
516 assert (hash_table_ok (ht));
519 if (ht->hash_table == NULL)
522 for (i = 0; i < ht->hash_table_size; i++)
525 for (p = BUCKET_HEAD (ht, i); p; p = p->next)
529 return_code = (*f) (p->key, aux);
530 if (return_code != 0)
537 /* For each entry in the bucket addressed by BUCKET_KEY of the hash
538 table HT, invoke the function F. If F returns non-zero, stop
539 iterating and return that value. Otherwise, apply F to all entries
540 in the selected bucket and return zero. The AUX argument to this
541 function is passed as the last argument in each invocation of F.
542 The first argument to F is BUCKET_KEY, and the second is the key of
543 an entry in the selected bucket. */
546 hash_do_for_each_in_selected_bucket (HT *ht, const void *bucket_key,
547 int (*f) (const void *bucket_key,
555 assert (hash_table_ok (ht));
558 if (ht->hash_table == NULL)
561 idx = ht->hash_hash (bucket_key, ht->hash_table_size);
563 for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
567 return_code = (*f) (bucket_key, p->key, aux);
568 if (return_code != 0)
575 /* Make all buckets empty, placing any chained entries on the free list.
576 As with hash_free, apply the user-specified function key_freer
577 (if it's not NULL) to the keys of any affected entries. */
585 for (i = 0; i < ht->hash_table_size; i++)
587 HASH_ENT *tail = NULL;
588 HASH_ENT *head = BUCKET_HEAD (ht, i);
590 /* Free any keys and get tail pointer to last entry in chain. */
591 for (p = head; p; p = p->next)
593 if (ht->hash_key_freer != NULL)
594 ht->hash_key_freer (p->key);
595 p->key = NULL; /* Make sure no one tries to use this key later. */
598 BUCKET_HEAD (ht, i) = NULL;
600 /* If there's a chain in this bucket, tack it onto the
601 beginning of the free list. */
604 assert (tail != NULL && tail->next == NULL);
605 tail->next = ht->hash_free_entry_list;
606 ht->hash_free_entry_list = head;
609 ht->hash_n_slots_used = 0;
610 ht->hash_max_chain_length = 0;
612 ht->hash_dirty_max_chain_length = 0;
615 /* Free all storage associated with HT that functions in this package
616 have allocated. If a key_freer function has been supplied (when HT
617 was created), this function applies it to the key of each entry before
618 freeing that entry. */
621 hash_free_0 (HT *ht, int free_user_data)
623 if (free_user_data && ht->hash_key_freer != NULL)
627 for (i = 0; i < ht->hash_table_size; i++)
632 for (p = BUCKET_HEAD (ht, i); p; p = next)
635 ht->hash_key_freer (p->key);
641 obstack_free (&(ht->ht_obstack), NULL);
645 for (i = 0; i < ht->hash_table_size; i++)
650 for (p = BUCKET_HEAD (ht, i); p; p = next)
658 ht->hash_free_entry_list = NULL;
659 free (ht->hash_table);
672 hash_print (const HT *ht)
676 for (i = 0; i < ht->hash_table_size; i++)
680 if (BUCKET_HEAD (ht, i) != NULL)
683 for (p = BUCKET_HEAD (ht, i); p; p = p->next)
685 char *s = (char *) p->key;
695 hash_get_key_list (const HT *ht, unsigned int bufsize, void **buf)
700 for (i = 0; i < ht->hash_table_size; i++)
704 for (p = BUCKET_HEAD (ht, i); p; p = p->next)
713 /* Return the first key in the table. If the table is empty, return NULL. */
716 hash_get_first (const HT *ht)
721 if (ht->hash_n_keys == 0)
724 for (idx = 0; idx < ht->hash_table_size; idx++)
726 if ((p = BUCKET_HEAD (ht, idx)) != NULL)
732 /* Return the key in the entry following the entry whose key matches E.
733 If there is the only one key in the table and that key matches E,
734 return the matching key. If E is not in the table, return NULL. */
737 hash_get_next (const HT *ht, const void *e)
742 idx = ht->hash_hash (e, ht->hash_table_size);
743 assert (idx < ht->hash_table_size);
744 for (p = BUCKET_HEAD (ht, idx); p != NULL; p = p->next)
746 if (ht->hash_key_comparator (e, p->key) == 0)
756 /* E is the last or only key in the bucket chain. */
757 if (ht->hash_n_keys == 1)
759 /* There is only one key in the table, and it matches E. */
765 idx = (idx + 1) % ht->hash_table_size;
766 if ((p = BUCKET_HEAD (ht, idx)) != NULL)
769 while (idx != bucket);
774 /* E is not in the table. */