1 /* hash.c -- hash table maintenance
2 Copyright (C) 1995, 1999, 2007-2012 Free Software Foundation, Inc.
3 Written by Greg McGary <gkm@gnu.ai.mit.edu>
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3, or (at your option)
8 any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include <config.h>
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <xalloc.h>
23 #include <error.h>
24
25 #include "idu-hash.h"
26 #include "xnls.h"
27
28 static void hash_rehash (struct hash_table* ht);
29 static unsigned long round_up_2 (unsigned long rough);
30
31 /* Implement double hashing with open addressing. The table size is
32 always a power of two. The secondary (`increment') hash function
33 is forced to return an odd-value, in order to be relatively prime
34 to the table size. This guarantees that the increment can
35 potentially hit every slot in the table during collision
36 resolution. */
37
38 void *hash_deleted_item = &hash_deleted_item;
39
40 /* Force the table size to be a power of two, possibly rounding up the
41 given size. */
42
43 void
hash_init(struct hash_table * ht,unsigned long size,hash_func_t hash_1,hash_func_t hash_2,hash_cmp_func_t hash_cmp)44 hash_init (struct hash_table* ht, unsigned long size,
45 hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)
46 {
47 ht->ht_size = round_up_2 (size);
48 ht->ht_empty_slots = ht->ht_size;
49 ht->ht_vec = xcalloc (ht->ht_size, sizeof(struct token *));
50 if (ht->ht_vec == 0)
51 error (EXIT_FAILURE, 0, _("can't allocate %ld bytes for hash table: memory exhausted"),
52 ht->ht_size * sizeof(struct token *));
53 ht->ht_capacity = ht->ht_size * 15 / 16; /* 93.75% loading factor */
54 ht->ht_fill = 0;
55 ht->ht_collisions = 0;
56 ht->ht_lookups = 0;
57 ht->ht_rehashes = 0;
58 ht->ht_hash_1 = hash_1;
59 ht->ht_hash_2 = hash_2;
60 ht->ht_compare = hash_cmp;
61 }
62
63 /* Load an array of items into `ht'. */
64
65 void
hash_load(struct hash_table * ht,void * item_table,unsigned long cardinality,unsigned long size)66 hash_load (struct hash_table* ht, void *item_table, unsigned long cardinality, unsigned long size)
67 {
68 char *items = (char *) item_table;
69 while (cardinality--)
70 {
71 hash_insert (ht, items);
72 items += size;
73 }
74 }
75
76 /* Returns the address of the table slot matching `key'. If `key' is
77 not found, return the address of an empty slot suitable for
78 inserting `key'. The caller is responsible for incrementing
79 ht_fill on insertion. */
80
81 void **
hash_find_slot(struct hash_table * ht,void const * key)82 hash_find_slot (struct hash_table* ht, void const *key)
83 {
84 void **slot;
85 void **deleted_slot = 0;
86 unsigned int hash_2 = 0;
87 unsigned int hash_1 = (*ht->ht_hash_1) (key);
88
89 ht->ht_lookups++;
90 for (;;)
91 {
92 hash_1 %= ht->ht_size;
93 slot = &ht->ht_vec[hash_1];
94
95 if (*slot == 0)
96 return (deleted_slot ? deleted_slot : slot);
97 if (*slot == hash_deleted_item)
98 {
99 if (deleted_slot == 0)
100 deleted_slot = slot;
101 }
102 else
103 {
104 if (key == *slot)
105 return slot;
106 if ((*ht->ht_compare) (key, *slot) == 0)
107 return slot;
108 ht->ht_collisions++;
109 }
110 if (!hash_2)
111 hash_2 = (*ht->ht_hash_2) (key) | 1;
112 hash_1 += hash_2;
113 }
114 }
115
116 void *
hash_find_item(struct hash_table * ht,void const * key)117 hash_find_item (struct hash_table* ht, void const *key)
118 {
119 void **slot = hash_find_slot (ht, key);
120 return ((HASH_VACANT (*slot)) ? 0 : *slot);
121 }
122
123 void *
hash_insert(struct hash_table * ht,void * item)124 hash_insert (struct hash_table* ht, void *item)
125 {
126 void **slot = hash_find_slot (ht, item);
127 void *old_item = slot ? *slot : 0;
128 hash_insert_at (ht, item, slot);
129 return ((HASH_VACANT (old_item)) ? 0 : old_item);
130 }
131
132 void *
hash_insert_at(struct hash_table * ht,void * item,void const * slot)133 hash_insert_at (struct hash_table* ht, void *item, void const *slot)
134 {
135 void *old_item = *(void **) slot;
136 if (HASH_VACANT (old_item))
137 {
138 ht->ht_fill++;
139 if (old_item == 0)
140 ht->ht_empty_slots--;
141 old_item = item;
142 }
143 *(void const **) slot = item;
144 if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity)
145 {
146 hash_rehash (ht);
147 return (void *) hash_find_slot (ht, item);
148 }
149 else
150 return (void *) slot;
151 }
152
153 void *
hash_delete(struct hash_table * ht,void const * item)154 hash_delete (struct hash_table* ht, void const *item)
155 {
156 void **slot = hash_find_slot (ht, item);
157 return hash_delete_at (ht, slot);
158 }
159
160 void *
hash_delete_at(struct hash_table * ht,void const * slot)161 hash_delete_at (struct hash_table* ht, void const *slot)
162 {
163 void *item = *(void **) slot;
164 if (!HASH_VACANT (item))
165 {
166 *(void const **) slot = hash_deleted_item;
167 ht->ht_fill--;
168 return item;
169 }
170 else
171 return 0;
172 }
173
174 void
hash_free_items(struct hash_table * ht)175 hash_free_items (struct hash_table* ht)
176 {
177 void **vec = ht->ht_vec;
178 void **end = &vec[ht->ht_size];
179 for (; vec < end; vec++)
180 {
181 void *item = *vec;
182 if (!HASH_VACANT (item))
183 free (item);
184 *vec = 0;
185 }
186 ht->ht_fill = 0;
187 ht->ht_empty_slots = ht->ht_size;
188 }
189
190 void
hash_delete_items(struct hash_table * ht)191 hash_delete_items (struct hash_table* ht)
192 {
193 void **vec = ht->ht_vec;
194 void **end = &vec[ht->ht_size];
195 for (; vec < end; vec++)
196 *vec = 0;
197 ht->ht_fill = 0;
198 ht->ht_collisions = 0;
199 ht->ht_lookups = 0;
200 ht->ht_rehashes = 0;
201 ht->ht_empty_slots = ht->ht_size;
202 }
203
204 void
hash_free(struct hash_table * ht,int free_items)205 hash_free (struct hash_table* ht, int free_items)
206 {
207 if (free_items)
208 hash_free_items (ht);
209 else
210 {
211 ht->ht_fill = 0;
212 ht->ht_empty_slots = ht->ht_size;
213 }
214 free (ht->ht_vec);
215 ht->ht_vec = 0;
216 ht->ht_capacity = 0;
217 }
218
219 void
hash_map(struct hash_table * ht,hash_map_func_t map)220 hash_map (struct hash_table *ht, hash_map_func_t map)
221 {
222 void **slot;
223 void **end = &ht->ht_vec[ht->ht_size];
224
225 for (slot = ht->ht_vec; slot < end; slot++)
226 {
227 if (!HASH_VACANT (*slot))
228 (*map) (*slot);
229 }
230 }
231
232 /* Double the size of the hash table in the event of overflow... */
233
234 static void
hash_rehash(struct hash_table * ht)235 hash_rehash (struct hash_table* ht)
236 {
237 unsigned long old_ht_size = ht->ht_size;
238 void **old_vec = ht->ht_vec;
239 void **ovp;
240
241 if (ht->ht_fill >= ht->ht_capacity)
242 {
243 ht->ht_size *= 2;
244 ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
245 }
246 ht->ht_rehashes++;
247 ht->ht_vec = xcalloc (ht->ht_size, sizeof(struct token *));
248
249 for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
250 {
251 if (! HASH_VACANT (*ovp))
252 {
253 void **slot = hash_find_slot (ht, *ovp);
254 *slot = *ovp;
255 }
256 }
257 ht->ht_empty_slots = ht->ht_size - ht->ht_fill;
258 free (old_vec);
259 }
260
261 void
hash_print_stats(struct hash_table const * ht,FILE * out_FILE)262 hash_print_stats (struct hash_table const *ht, FILE *out_FILE)
263 {
264 fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
265 100.0 * (double) ht->ht_fill / (double) ht->ht_size);
266 fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
267 fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
268 (ht->ht_lookups
269 ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
270 : 0));
271 }
272
273 /* Dump all items into a NULL-terminated vector. Use the
274 user-supplied vector, or malloc one. */
275
276 void**
hash_dump(struct hash_table const * ht,void ** vector_0,qsort_cmp_t compare)277 hash_dump (struct hash_table const *ht, void **vector_0, qsort_cmp_t compare)
278 {
279 void **vector;
280 void **slot;
281 void **end = &ht->ht_vec[ht->ht_size];
282
283 if (vector_0 == 0)
284 vector_0 = xmalloc (sizeof (void *) * (ht->ht_fill + 1));
285 vector = vector_0;
286
287 for (slot = ht->ht_vec; slot < end; slot++)
288 if (!HASH_VACANT (*slot))
289 *vector++ = *slot;
290 *vector = 0;
291
292 if (compare)
293 qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
294 return vector_0;
295 }
296
297 /* Round a given number up to the nearest power of 2. */
298
299 static unsigned long _GL_ATTRIBUTE_CONST
round_up_2(unsigned long rough)300 round_up_2 (unsigned long rough)
301 {
302 int round;
303
304 round = 1;
305 while (rough)
306 {
307 round <<= 1;
308 rough >>= 1;
309 }
310 return round;
311 }
312