Keep the command line on the heap to avoid stack overflow.
[make.git] / hash.c
blobe04b1bbe22d72df215bf7f75436f818d244c1d17
1 /* hash.c -- hash table maintenance
2 Copyright (C) 1995, 1999, 2002, 2010 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;