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>
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 2, 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 along with
16 this program; see the file COPYING.  If not, write to the Free Software
17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.  */
18 
19 #include "make.h"
20 #include "hash.h"
21 
22 #define	CALLOC(t, n) ((t *) calloc (sizeof (t), (n)))
23 #define MALLOC(t, n) ((t *) xmalloc (sizeof (t) * (n)))
24 #define REALLOC(o, t, n) ((t *) xrealloc ((o), sizeof (t) * (n)))
25 #define CLONE(o, t, n) ((t *) memcpy (MALLOC (t, (n)), (o), sizeof (t) * (n)))
26 
27 static void hash_rehash __P((struct hash_table* ht));
28 static unsigned long round_up_2 __P((unsigned long rough));
29 
30 /* Implement double hashing with open addressing.  The table size is
31    always a power of two.  The secondary (`increment') hash function
32    is forced to return an odd-value, in order to be relatively prime
33    to the table size.  This guarantees that the increment can
34    potentially hit every slot in the table during collision
35    resolution.  */
36 
37 void *hash_deleted_item = &hash_deleted_item;
38 
39 /* Force the table size to be a power of two, possibly rounding up the
40    given size.  */
41 
42 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)43 hash_init (struct hash_table *ht, unsigned long size,
44            hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)
45 {
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)
50     {
51       fprintf (stderr, _("can't allocate %ld bytes for hash table: memory exhausted"),
52 	       ht->ht_size * sizeof(struct token *));
53       exit (1);
54     }
55 
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;
64 }
65 
66 /* Load an array of items into `ht'.  */
67 
68 void
hash_load(struct hash_table * ht,void * item_table,unsigned long cardinality,unsigned long size)69 hash_load (struct hash_table *ht, void *item_table,
70            unsigned long cardinality, unsigned long size)
71 {
72   char *items = (char *) item_table;
73   while (cardinality--)
74     {
75       hash_insert (ht, items);
76       items += size;
77     }
78 }
79 
80 /* Returns the address of the table slot matching `key'.  If `key' is
81    not found, return the address of an empty slot suitable for
82    inserting `key'.  The caller is responsible for incrementing
83    ht_fill on insertion.  */
84 
85 void **
hash_find_slot(struct hash_table * ht,const void * key)86 hash_find_slot (struct hash_table *ht, const void *key)
87 {
88   void **slot;
89   void **deleted_slot = 0;
90   unsigned int hash_2 = 0;
91   unsigned int hash_1 = (*ht->ht_hash_1) (key);
92 
93   ht->ht_lookups++;
94   for (;;)
95     {
96       hash_1 &= (ht->ht_size - 1);
97       slot = &ht->ht_vec[hash_1];
98 
99       if (*slot == 0)
100 	return (deleted_slot ? deleted_slot : slot);
101       if (*slot == hash_deleted_item)
102 	{
103 	  if (deleted_slot == 0)
104 	    deleted_slot = slot;
105 	}
106       else
107 	{
108 	  if (key == *slot)
109 	    return slot;
110 	  if ((*ht->ht_compare) (key, *slot) == 0)
111 	    return slot;
112 	  ht->ht_collisions++;
113 	}
114       if (!hash_2)
115 	  hash_2 = (*ht->ht_hash_2) (key) | 1;
116       hash_1 += hash_2;
117     }
118 }
119 
120 void *
hash_find_item(struct hash_table * ht,const void * key)121 hash_find_item (struct hash_table *ht, const void *key)
122 {
123   void **slot = hash_find_slot (ht, key);
124   return ((HASH_VACANT (*slot)) ? 0 : *slot);
125 }
126 
127 void *
hash_insert(struct hash_table * ht,const void * item)128 hash_insert (struct hash_table *ht, const void *item)
129 {
130   void **slot = hash_find_slot (ht, item);
131   const void *old_item = slot ? *slot : 0;
132   hash_insert_at (ht, item, slot);
133   return (void *)((HASH_VACANT (old_item)) ? 0 : old_item);
134 }
135 
136 void *
hash_insert_at(struct hash_table * ht,const void * item,const void * slot)137 hash_insert_at (struct hash_table *ht, const void *item, const void *slot)
138 {
139   const void *old_item = *(void **) slot;
140   if (HASH_VACANT (old_item))
141     {
142       ht->ht_fill++;
143       if (old_item == 0)
144 	ht->ht_empty_slots--;
145       old_item = item;
146     }
147   *(void const **) slot = item;
148   if (ht->ht_empty_slots < ht->ht_size - ht->ht_capacity)
149     {
150       hash_rehash (ht);
151       return (void *) hash_find_slot (ht, item);
152     }
153   else
154     return (void *) slot;
155 }
156 
157 void *
hash_delete(struct hash_table * ht,const void * item)158 hash_delete (struct hash_table *ht, const void *item)
159 {
160   void **slot = hash_find_slot (ht, item);
161   return hash_delete_at (ht, slot);
162 }
163 
164 void *
hash_delete_at(struct hash_table * ht,const void * slot)165 hash_delete_at (struct hash_table *ht, const void *slot)
166 {
167   void *item = *(void **) slot;
168   if (!HASH_VACANT (item))
169     {
170       *(void const **) slot = hash_deleted_item;
171       ht->ht_fill--;
172       return item;
173     }
174   else
175     return 0;
176 }
177 
178 void
hash_free_items(struct hash_table * ht)179 hash_free_items (struct hash_table *ht)
180 {
181   void **vec = ht->ht_vec;
182   void **end = &vec[ht->ht_size];
183   for (; vec < end; vec++)
184     {
185       void *item = *vec;
186       if (!HASH_VACANT (item))
187 	free (item);
188       *vec = 0;
189     }
190   ht->ht_fill = 0;
191   ht->ht_empty_slots = ht->ht_size;
192 }
193 
194 void
hash_delete_items(struct hash_table * ht)195 hash_delete_items (struct hash_table *ht)
196 {
197   void **vec = ht->ht_vec;
198   void **end = &vec[ht->ht_size];
199   for (; vec < end; vec++)
200     *vec = 0;
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;
206 }
207 
208 void
hash_free(struct hash_table * ht,int free_items)209 hash_free (struct hash_table *ht, int free_items)
210 {
211   if (free_items)
212     hash_free_items (ht);
213   else
214     {
215       ht->ht_fill = 0;
216       ht->ht_empty_slots = ht->ht_size;
217     }
218   free (ht->ht_vec);
219   ht->ht_vec = 0;
220   ht->ht_capacity = 0;
221 }
222 
223 void
hash_map(struct hash_table * ht,hash_map_func_t map)224 hash_map (struct hash_table *ht, hash_map_func_t map)
225 {
226   void **slot;
227   void **end = &ht->ht_vec[ht->ht_size];
228 
229   for (slot = ht->ht_vec; slot < end; slot++)
230     {
231       if (!HASH_VACANT (*slot))
232 	(*map) (*slot);
233     }
234 }
235 
236 void
hash_map_arg(struct hash_table * ht,hash_map_arg_func_t map,void * arg)237 hash_map_arg (struct hash_table *ht, hash_map_arg_func_t map, void *arg)
238 {
239   void **slot;
240   void **end = &ht->ht_vec[ht->ht_size];
241 
242   for (slot = ht->ht_vec; slot < end; slot++)
243     {
244       if (!HASH_VACANT (*slot))
245 	(*map) (*slot, arg);
246     }
247 }
248 
249 /* Double the size of the hash table in the event of overflow... */
250 
251 static void
hash_rehash(struct hash_table * ht)252 hash_rehash (struct hash_table *ht)
253 {
254   unsigned long old_ht_size = ht->ht_size;
255   void **old_vec = ht->ht_vec;
256   void **ovp;
257 
258   if (ht->ht_fill >= ht->ht_capacity)
259     {
260       ht->ht_size *= 2;
261       ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
262     }
263   ht->ht_rehashes++;
264   ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size);
265 
266   for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
267     {
268       if (! HASH_VACANT (*ovp))
269 	{
270 	  void **slot = hash_find_slot (ht, *ovp);
271 	  *slot = *ovp;
272 	}
273     }
274   ht->ht_empty_slots = ht->ht_size - ht->ht_fill;
275   free (old_vec);
276 }
277 
278 void
hash_print_stats(struct hash_table * ht,FILE * out_FILE)279 hash_print_stats (struct hash_table *ht, FILE *out_FILE)
280 {
281   /* GKM FIXME: honor NO_FLOAT */
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)
288 	    : 0));
289 }
290 
291 /* Dump all items into a NULL-terminated vector.  Use the
292    user-supplied vector, or malloc one.  */
293 
294 void **
hash_dump(struct hash_table * ht,void ** vector_0,qsort_cmp_t compare)295 hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
296 {
297   void **vector;
298   void **slot;
299   void **end = &ht->ht_vec[ht->ht_size];
300 
301   if (vector_0 == 0)
302     vector_0 = MALLOC (void *, ht->ht_fill + 1);
303   vector = vector_0;
304 
305   for (slot = ht->ht_vec; slot < end; slot++)
306     if (!HASH_VACANT (*slot))
307       *vector++ = *slot;
308   *vector = 0;
309 
310   if (compare)
311     qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
312   return vector_0;
313 }
314 
315 /* Round a given number up to the nearest power of 2. */
316 
317 static unsigned long
round_up_2(unsigned long n)318 round_up_2 (unsigned long n)
319 {
320   n |= (n >> 1);
321   n |= (n >> 2);
322   n |= (n >> 4);
323   n |= (n >> 8);
324   n |= (n >> 16);
325 
326 #if !defined(HAVE_LIMITS_H) || ULONG_MAX > 4294967295
327   /* We only need this on systems where unsigned long is >32 bits.  */
328   n |= (n >> 32);
329 #endif
330 
331   return n + 1;
332 }
333