Home | History | Annotate | Download | only in dist

Lines Matching refs:ht

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