Fixes to build_w32.bat for building with MSVC 64bit.
[make.git] / hash.c
bloba4df1f606c5c6a534d1557a684f43eda607e2aa9
1 /* hash.c -- hash table maintenance
2 Copyright (C) 1995, 1999, 2002 Free Software Foundation, Inc.
3 Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org>
5 GNU Make is free software; you can redistribute it and/or modify it under the
6 terms of the GNU General Public License as published by the Free Software
7 Foundation; either version 3 of the License, or (at your option) any later
8 version.
10 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
11 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
12 A PARTICULAR PURPOSE. See the GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License along with
15 this program. If not, see <http://www.gnu.org/licenses/>. */
17 #include "make.h"
18 #include "hash.h"
20 #define CALLOC(t, n) ((t *) calloc (sizeof (t), (n)))
21 #define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n)))
22 #define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n)))
23 #define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n)))
25 static void hash_rehash __P((struct hash_table* ht));
26 static unsigned long round_up_2 __P((unsigned long rough));
28 /* Implement double hashing with open addressing. The table size is
29 always a power of two. The secondary (`increment') hash function
30 is forced to return an odd-value, in order to be relatively prime
31 to the table size. This guarantees that the increment can
32 potentially hit every slot in the table during collision
33 resolution. */
35 void *hash_deleted_item = &hash_deleted_item;
37 /* Force the table size to be a power of two, possibly rounding up the
38 given size. */
40 void
41 hash_init (struct hash_table *ht, unsigned long size,
42 hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)
44 ht->ht_size = round_up_2 (size);
45 ht->ht_empty_slots = ht->ht_size;
46 ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size);
47 if (ht->ht_vec == 0)
49 fprintf (stderr, _("can't allocate %lu bytes for hash table: memory exhausted"),
50 ht->ht_size * (unsigned long) sizeof (struct token *));
51 exit (1);
54 ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */
55 ht->ht_fill = 0;
56 ht->ht_collisions = 0;
57 ht->ht_lookups = 0;
58 ht->ht_rehashes = 0;
59 ht->ht_hash_1 = hash_1;
60 ht->ht_hash_2 = hash_2;
61 ht->ht_compare = hash_cmp;
64 /* Load an array of items into `ht'. */
66 void
67 hash_load (struct hash_table *ht, void *item_table,
68 unsigned long cardinality, unsigned long size)
70 char *items = (char *) item_table;
71 while (cardinality--)
73 hash_insert (ht, items);
74 items += size;
78 /* Returns the address of the table slot matching `key'. If `key' is
79 not found, return the address of an empty slot suitable for
80 inserting `key'. The caller is responsible for incrementing
81 ht_fill on insertion. */
83 void **
84 hash_find_slot (struct hash_table *ht, const void *key)
86 void **slot;
87 void **deleted_slot = 0;
88 unsigned int hash_2 = 0;
89 unsigned int hash_1 = (*ht->ht_hash_1) (key);
91 ht->ht_lookups++;
92 for (;;)
94 hash_1 &= (ht->ht_size - 1);
95 slot = &ht->ht_vec[hash_1];
97 if (*slot == 0)
98 return (deleted_slot ? deleted_slot : slot);
99 if (*slot == hash_deleted_item)
101 if (deleted_slot == 0)
102 deleted_slot = slot;
104 else
106 if (key == *slot)
107 return slot;
108 if ((*ht->ht_compare) (key, *slot) == 0)
109 return slot;
110 ht->ht_collisions++;
112 if (!hash_2)
113 hash_2 = (*ht->ht_hash_2) (key) | 1;
114 hash_1 += hash_2;
118 void *
119 hash_find_item (struct hash_table *ht, const void *key)
121 void **slot = hash_find_slot (ht, key);
122 return ((HASH_VACANT (*slot)) ? 0 : *slot);
125 void *
126 hash_insert (struct hash_table *ht, const void *item)
128 void **slot = hash_find_slot (ht, item);
129 const void *old_item = *slot;
130 hash_insert_at (ht, item, slot);
131 return (void *)((HASH_VACANT (old_item)) ? 0 : old_item);
134 void *
135 hash_insert_at (struct hash_table *ht, const void *item, const void *slot)
137 const void *old_item = *(void **) slot;
138 if (HASH_VACANT (old_item))
140 ht->ht_fill++;
141 if (old_item == 0)
142 ht->ht_empty_slots--;
143 old_item = item;
145 *(void const **) slot = item;
146 if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity)
148 hash_rehash (ht);
149 return (void *) hash_find_slot (ht, item);
151 else
152 return (void *) slot;
155 void *
156 hash_delete (struct hash_table *ht, const void *item)
158 void **slot = hash_find_slot (ht, item);
159 return hash_delete_at (ht, slot);
162 void *
163 hash_delete_at (struct hash_table *ht, const void *slot)
165 void *item = *(void **) slot;
166 if (!HASH_VACANT (item))
168 *(void const **) slot = hash_deleted_item;
169 ht->ht_fill--;
170 return item;
172 else
173 return 0;
176 void
177 hash_free_items (struct hash_table *ht)
179 void **vec = ht->ht_vec;
180 void **end = &vec[ht->ht_size];
181 for (; vec < end; vec++)
183 void *item = *vec;
184 if (!HASH_VACANT (item))
185 free (item);
186 *vec = 0;
188 ht->ht_fill = 0;
189 ht->ht_empty_slots = ht->ht_size;
192 void
193 hash_delete_items (struct hash_table *ht)
195 void **vec = ht->ht_vec;
196 void **end = &vec[ht->ht_size];
197 for (; vec < end; vec++)
198 *vec = 0;
199 ht->ht_fill = 0;
200 ht->ht_collisions = 0;
201 ht->ht_lookups = 0;
202 ht->ht_rehashes = 0;
203 ht->ht_empty_slots = ht->ht_size;
206 void
207 hash_free (struct hash_table *ht, int free_items)
209 if (free_items)
210 hash_free_items (ht);
211 else
213 ht->ht_fill = 0;
214 ht->ht_empty_slots = ht->ht_size;
216 free (ht->ht_vec);
217 ht->ht_vec = 0;
218 ht->ht_capacity = 0;
221 void
222 hash_map (struct hash_table *ht, hash_map_func_t map)
224 void **slot;
225 void **end = &ht->ht_vec[ht->ht_size];
227 for (slot = ht->ht_vec; slot < end; slot++)
229 if (!HASH_VACANT (*slot))
230 (*map) (*slot);
234 void
235 hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg)
237 void **slot;
238 void **end = &ht->ht_vec[ht->ht_size];
240 for (slot = ht->ht_vec; slot < end; slot++)
242 if (!HASH_VACANT (*slot))
243 (*map) (*slot, arg);
247 /* Double the size of the hash table in the event of overflow... */
249 static void
250 hash_rehash (struct hash_table *ht)
252 unsigned long old_ht_size = ht->ht_size;
253 void **old_vec = ht->ht_vec;
254 void **ovp;
256 if (ht->ht_fill >= ht->ht_capacity)
258 ht->ht_size *= 2;
259 ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
261 ht->ht_rehashes++;
262 ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size);
264 for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
266 if (! HASH_VACANT (*ovp))
268 void **slot = hash_find_slot (ht, *ovp);
269 *slot = *ovp;
272 ht->ht_empty_slots = ht->ht_size - ht->ht_fill;
273 free (old_vec);
276 void
277 hash_print_stats (struct hash_table *ht, FILE *out_FILE)
279 /* GKM FIXME: honor NO_FLOAT */
280 fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
281 100.0 * (double) ht->ht_fill / (double) ht->ht_size);
282 fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
283 fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
284 (ht->ht_lookups
285 ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
286 : 0));
289 /* Dump all items into a NULL-terminated vector. Use the
290 user-supplied vector, or malloc one. */
292 void **
293 hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
295 void **vector;
296 void **slot;
297 void **end = &ht->ht_vec[ht->ht_size];
299 if (vector_0 == 0)
300 vector_0 = MALLOC (void *, ht->ht_fill + 1);
301 vector = vector_0;
303 for (slot = ht->ht_vec; slot < end; slot++)
304 if (!HASH_VACANT (*slot))
305 *vector++ = *slot;
306 *vector = 0;
308 if (compare)
309 qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
310 return vector_0;
313 /* Round a given number up to the nearest power of 2. */
315 static unsigned long
316 round_up_2 (unsigned long n)
318 n |= (n >> 1);
319 n |= (n >> 2);
320 n |= (n >> 4);
321 n |= (n >> 8);
322 n |= (n >> 16);
324 #if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295
325 /* We only need this on systems where unsigned long is >32 bits. */
326 n |= (n >> 32);
327 #endif
329 return n + 1;