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
5This program is free software; you can redistribute it and/or modify
6it under the terms of the GNU General Public License as published by
7the Free Software Foundation; either version 2, or (at your option)
8any later version.
9
10This program is distributed in the hope that it will be useful,
11but WITHOUT ANY WARRANTY; without even the implied warranty of
12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13GNU General Public License for more details.
14
15You should have received a copy of the GNU General Public License along with
16this program; see the file COPYING.  If not, write to the Free Software
17Foundation, 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
27static void hash_rehash __P((struct hash_table* ht));
28static 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
37void *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
42void
43hash_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
68void
69hash_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
85void **
86hash_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
120void *
121hash_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
127void *
128hash_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
136void *
137hash_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
157void *
158hash_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
164void *
165hash_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
178void
179hash_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
194void
195hash_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
208void
209hash_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
223void
224hash_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
236void
237hash_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
251static void
252hash_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
278void
279hash_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
294void **
295hash_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
317static unsigned long
318round_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