27 static void hash_rehash __P((struct hash_table* ht));
43 hash_init (struct hash_table *ht, unsigned long size,  in hash_init()  argument
46   ht->ht_size = round_up_2 (size);  in hash_init()
47   ht->ht_empty_slots = ht->ht_size;  in hash_init()
48   ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size);  in hash_init()
49   if (ht->ht_vec == 0)  in hash_init()
52 	       ht->ht_size * sizeof(struct token *));  in hash_init()
56   ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */  in hash_init()
57   ht->ht_fill = 0;  in hash_init()
58   ht->ht_collisions = 0;  in hash_init()
59   ht->ht_lookups = 0;  in hash_init()
60   ht->ht_rehashes = 0;  in hash_init()
61   ht->ht_hash_1 = hash_1;  in hash_init()
62   ht->ht_hash_2 = hash_2;  in hash_init()
63   ht->ht_compare = hash_cmp;  in hash_init()
69 hash_load (struct hash_table *ht, void *item_table,  in hash_load()  argument
75       hash_insert (ht, items);  in hash_load()
86 hash_find_slot (struct hash_table *ht, const void *key)  in hash_find_slot()  argument
91   unsigned int hash_1 = (*ht->ht_hash_1) (key);  in hash_find_slot()
93   ht->ht_lookups++;  in hash_find_slot()
96       hash_1 &= (ht->ht_size - 1);  in hash_find_slot()
97       slot = &ht->ht_vec[hash_1];  in hash_find_slot()
110 	  if ((*ht->ht_compare) (key, *slot) == 0)  in hash_find_slot()
112 	  ht->ht_collisions++;  in hash_find_slot()
115 	  hash_2 = (*ht->ht_hash_2) (key) | 1;  in hash_find_slot()
121 hash_find_item (struct hash_table *ht, const void *key)  in hash_find_item()  argument
123   void **slot = hash_find_slot (ht, key);  in hash_find_item()
128 hash_insert (struct hash_table *ht, const void *item)  in hash_insert()  argument
130   void **slot = hash_find_slot (ht, item);  in hash_insert()
132   hash_insert_at (ht, item, slot);  in hash_insert()
137 hash_insert_at (struct hash_table *ht, const void *item, const void *slot)  in hash_insert_at()  argument
142       ht->ht_fill++;  in hash_insert_at()
144 	ht->ht_empty_slots--;  in hash_insert_at()
148   if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity)  in hash_insert_at()
150       hash_rehash (ht);  in hash_insert_at()
151       return (void *) hash_find_slot (ht, item);  in hash_insert_at()
158 hash_delete (struct hash_table *ht, const void *item)  in hash_delete()  argument
160   void **slot = hash_find_slot (ht, item);  in hash_delete()
161   return hash_delete_at (ht, slot);  in hash_delete()
165 hash_delete_at (struct hash_table *ht, const void *slot)  in hash_delete_at()  argument
171       ht->ht_fill--;  in hash_delete_at()
179 hash_free_items (struct hash_table *ht)  in hash_free_items()  argument
181   void **vec = ht->ht_vec;  in hash_free_items()
182   void **end = &vec[ht->ht_size];  in hash_free_items()
190   ht->ht_fill = 0;  in hash_free_items()
191   ht->ht_empty_slots = ht->ht_size;  in hash_free_items()
195 hash_delete_items (struct hash_table *ht)  in hash_delete_items()  argument
197   void **vec = ht->ht_vec;  in hash_delete_items()
198   void **end = &vec[ht->ht_size];  in hash_delete_items()
201   ht->ht_fill = 0;  in hash_delete_items()
202   ht->ht_collisions = 0;  in hash_delete_items()
203   ht->ht_lookups = 0;  in hash_delete_items()
204   ht->ht_rehashes = 0;  in hash_delete_items()
205   ht->ht_empty_slots = ht->ht_size;  in hash_delete_items()
209 hash_free (struct hash_table *ht, int free_items)  in hash_free()  argument
212     hash_free_items (ht);  in hash_free()
215       ht->ht_fill = 0;  in hash_free()
216       ht->ht_empty_slots = ht->ht_size;  in hash_free()
218   free (ht->ht_vec);  in hash_free()
219   ht->ht_vec = 0;  in hash_free()
220   ht->ht_capacity = 0;  in hash_free()
224 hash_map (struct hash_table *ht, hash_map_func_t map)  in hash_map()  argument
227   void **end = &ht->ht_vec[ht->ht_size];  in hash_map()
229   for (slot = ht->ht_vec; slot < end; slot++)  in hash_map()
237 hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg)  in hash_map_arg()  argument
240   void **end = &ht->ht_vec[ht->ht_size];  in hash_map_arg()
242   for (slot = ht->ht_vec; slot < end; slot++)  in hash_map_arg()
252 hash_rehash (struct hash_table *ht)  in hash_rehash()  argument
254   unsigned long old_ht_size = ht->ht_size;  in hash_rehash()
255   void **old_vec = ht->ht_vec;  in hash_rehash()
258   if (ht->ht_fill >= ht->ht_capacity)  in hash_rehash()
260       ht->ht_size *= 2;  in hash_rehash()
261       ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);  in hash_rehash()
263   ht->ht_rehashes++;  in hash_rehash()
264   ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size);  in hash_rehash()
270 	  void **slot = hash_find_slot (ht, *ovp);  in hash_rehash()
274   ht->ht_empty_slots = ht->ht_size - ht->ht_fill;  in hash_rehash()
279 hash_print_stats (struct hash_table *ht, FILE *out_FILE)  in hash_print_stats()  argument
282   fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,  in hash_print_stats()
283 	   100.0 * (double) ht->ht_fill / (double) ht->ht_size);  in hash_print_stats()
284   fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);  in hash_print_stats()
285   fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,  in hash_print_stats()
286 	   (ht->ht_lookups  in hash_print_stats()
287 	    ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)  in hash_print_stats()
295 hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)  in hash_dump()  argument
299   void **end = &ht->ht_vec[ht->ht_size];  in hash_dump()
302     vector_0 = MALLOC (void *, ht->ht_fill + 1);  in hash_dump()
305   for (slot = ht->ht_vec; slot < end; slot++)  in hash_dump()
311     qsort (vector_0, ht->ht_fill, sizeof (void *), compare);  in hash_dump()