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
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/>. */
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
35 void *hash_deleted_item = &hash_deleted_item;
37 /* Force the table size to be a power of two, possibly rounding up the
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);
49 fprintf (stderr, _("can't allocate %lu bytes for hash table: memory exhausted"),
50 ht->ht_size * (unsigned long) sizeof (struct token *));
54 ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */
56 ht->ht_collisions = 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'. */
67 hash_load (struct hash_table *ht, void *item_table,
68 unsigned long cardinality, unsigned long size)
70 char *items = (char *) item_table;
73 hash_insert (ht, items);
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. */
84 hash_find_slot (struct hash_table *ht, const void *key)
87 void **deleted_slot = 0;
88 unsigned int hash_2 = 0;
89 unsigned int hash_1 = (*ht->ht_hash_1) (key);
94 hash_1 &= (ht->ht_size - 1);
95 slot = &ht->ht_vec[hash_1];
98 return (deleted_slot ? deleted_slot : slot);
99 if (*slot == hash_deleted_item)
101 if (deleted_slot == 0)
108 if ((*ht->ht_compare) (key, *slot) == 0)
113 hash_2 = (*ht->ht_hash_2) (key) | 1;
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);
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);
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))
142 ht->ht_empty_slots--;
145 *(void const **) slot = item;
146 if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity)
149 return (void *) hash_find_slot (ht, item);
152 return (void *) slot;
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);
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;
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++)
184 if (!HASH_VACANT (item))
189 ht->ht_empty_slots = ht->ht_size;
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++)
200 ht->ht_collisions = 0;
203 ht->ht_empty_slots = ht->ht_size;
207 hash_free (struct hash_table *ht, int free_items)
210 hash_free_items (ht);
214 ht->ht_empty_slots = ht->ht_size;
222 hash_map (struct hash_table *ht, hash_map_func_t map)
225 void **end = &ht->ht_vec[ht->ht_size];
227 for (slot = ht->ht_vec; slot < end; slot++)
229 if (!HASH_VACANT (*slot))
235 hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg)
238 void **end = &ht->ht_vec[ht->ht_size];
240 for (slot = ht->ht_vec; slot < end; slot++)
242 if (!HASH_VACANT (*slot))
247 /* Double the size of the hash table in the event of overflow... */
250 hash_rehash (struct hash_table *ht)
252 unsigned long old_ht_size = ht->ht_size;
253 void **old_vec = ht->ht_vec;
256 if (ht->ht_fill >= ht->ht_capacity)
259 ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
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);
272 ht->ht_empty_slots = ht->ht_size - ht->ht_fill;
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,
285 ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
289 /* Dump all items into a NULL-terminated vector. Use the
290 user-supplied vector, or malloc one. */
293 hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
297 void **end = &ht->ht_vec[ht->ht_size];
300 vector_0 = MALLOC (void *, ht->ht_fill + 1);
303 for (slot = ht->ht_vec; slot < end; slot++)
304 if (!HASH_VACANT (*slot))
309 qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
313 /* Round a given number up to the nearest power of 2. */
316 round_up_2 (unsigned long n)
324 #if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295
325 /* We only need this on systems where unsigned long is >32 bits. */