[bison.git] / lib / hash.c

/* hash.c -- hash table maintenance
   Copyright (C) 1995 Free Software Foundation, Inc.
   Written by Greg McGary <gkm@gnu.ai.mit.edu>

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/

#include <config.h>
#include <stdio.h>
#include "hash.h"
#include "error.h"
#include "system.h"
#include "xalloc.h"

static void hash_rehash __P((struct hash_table* ht));
static unsigned long round_up_2 __P((unsigned long rough));

/* Implement double hashing with open addressing.  The table size is
   always a power of two.  The secondary (`increment') hash function
   is forced to return an odd-value, in order to be relatively prime
   to the table size.  This guarantees that the increment can
   potentially hit every slot in the table during collision
   resolution.  */

void *hash_deleted_item = &hash_deleted_item;

/* Force the table size to be a power of two, possibly rounding up the
   given size.  */

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)
{
  ht->ht_size = round_up_2 (size);
  if (ht->ht_size > (128 * 1024)) /* prevent size from getting out of hand */
    ht->ht_size /= 2;
  ht->ht_vec = (void**) XCALLOC (struct token *, ht->ht_size);
  if (ht->ht_vec == 0)
    error (1, 0, _("can't allocate %ld bytes for hash table: memory exhausted"),
	   ht->ht_size * sizeof(struct token *));
  ht->ht_capacity = ht->ht_size * 15 / 16; /* 93.75% loading factor */
  ht->ht_fill = 0;
  ht->ht_collisions = 0;
  ht->ht_lookups = 0;
  ht->ht_rehashes = 0;
  ht->ht_hash_1 = hash_1;
  ht->ht_hash_2 = hash_2;
  ht->ht_compare = hash_cmp;
}

/* Load an array of items into `ht'.  */

void
hash_load (struct hash_table* ht, void *item_table, unsigned long cardinality, unsigned long size)
{
  char *items = (char *) item_table;
  while (cardinality--)
    {
      hash_insert (ht, items);
      items += size;
    }
}

/* Returns the address of the table slot matching `key'.  If `key' is
   not found, return the address of an empty slot suitable for
   inserting `key'.  The caller is responsible for incrementing
   ht_fill on insertion.  */

void **
hash_find_slot (struct hash_table* ht, void const *key)
{
  void **slot;
  void **deleted_slot = 0;
  unsigned int hash_2 = 0;
  unsigned int hash_1 = (*ht->ht_hash_1) (key);

  ht->ht_lookups++;
  for (;;)
    {
      hash_1 %= ht->ht_size;
      slot = &ht->ht_vec[hash_1];

      if (*slot == 0)
	return slot;
      if (*slot == hash_deleted_item)
	{
	  if (deleted_slot == 0)
	    deleted_slot = slot;
	}
      else
	{
	  if (key == *slot)
	    return slot;
	  if ((*ht->ht_compare) (key, *slot) == 0)
	    return slot;
	  ht->ht_collisions++;
	}
      if (!hash_2)
	  hash_2 = (*ht->ht_hash_2) (key) | 1;
      hash_1 += hash_2;
    }
}

void *
hash_find_item (struct hash_table* ht, void const *key)
{
  void **slot = hash_find_slot (ht, key);
  return ((HASH_VACANT (*slot)) ? 0 : *slot);
}

void *
hash_insert (struct hash_table* ht, void *item)
{
  void **slot = hash_find_slot (ht, item);
  return hash_insert_at (ht, item, slot);
}

void *
hash_insert_at (struct hash_table* ht, void *item, void const *slot)
{
  void *old_item = *(void **) slot;
  if (HASH_VACANT (old_item))
    {
      ht->ht_fill++;
      old_item = item;
    }
  *(void const **) slot = item;
  if (ht->ht_fill >= ht->ht_capacity)
    hash_rehash (ht);
  return old_item;
}

void *
hash_delete (struct hash_table* ht, void const *item)
{
  void **slot = hash_find_slot (ht, item);
  return hash_delete_at (ht, slot);
}

void *
hash_delete_at (struct hash_table* ht, void const *slot)
{
  void *item = *(void **) slot;
  if (!HASH_VACANT (item))
    {
      *(void const **) slot = hash_deleted_item;
      ht->ht_fill--;
      return item;
    }
  else
    return 0;
}

void
hash_free_items (struct hash_table* ht)
{
  void **vec = ht->ht_vec;
  void **end = &vec[ht->ht_size];
  for (; vec < end; vec++)
    {
      void *item = *vec;
      if (!HASH_VACANT (item))
	free (item);
      *vec = 0;
    }
  ht->ht_fill = 0;
}

void
hash_delete_items (struct hash_table* ht)
{
  void **vec = ht->ht_vec;
  void **end = &vec[ht->ht_size];
  for (; vec < end; vec++)
    *vec = 0;
  ht->ht_fill = 0;
  ht->ht_collisions = 0;
  ht->ht_lookups = 0;
  ht->ht_rehashes = 0;
}

void
hash_free (struct hash_table* ht, int free_items)
{
  if (free_items)
    hash_free_items (ht);
  free (ht->ht_vec);
  ht->ht_vec = 0;
  ht->ht_fill = 0;
  ht->ht_capacity = 0;
}

void
hash_map (struct hash_table *ht, hash_map_func_t map)
{
  void **slot;
  void **end = &ht->ht_vec[ht->ht_size];

  for (slot = ht->ht_vec; slot < end; slot++)
    {
      if (!HASH_VACANT (*slot))
	(*map) (*slot);
    }
}

/* Double the size of the hash table in the event of overflow... */

static void
hash_rehash (struct hash_table* ht)
{
  unsigned long old_ht_size = ht->ht_size;
  void **old_vec = ht->ht_vec;
  void **ovp;
  void **slot;

  ht->ht_size *= 2;
  ht->ht_rehashes++;
  ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
  ht->ht_vec = (void **) XCALLOC (struct token *, ht->ht_size);

  for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
    {
      if (*ovp == 0)
	continue;
      slot = hash_find_slot (ht, *ovp);
      *slot = *ovp;
    }
  free (old_vec);
}

void
hash_print_stats (struct hash_table *ht, FILE *out_FILE)
{
  fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
	   100.0 * (double) ht->ht_fill / (double) ht->ht_size);
  fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
  fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
	   (ht->ht_lookups
	    ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
	    : 0));
}

/* Dump all items into a NULL-terminated vector.  Use the
   user-supplied vector, or malloc one.  */

void**
hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
{
  void **vector;
  void **slot;
  void **end = &ht->ht_vec[ht->ht_size];

  if (vector_0 == 0)
    vector_0 = XMALLOC (void *, ht->ht_fill + 1);
  vector = vector_0;

  for (slot = ht->ht_vec; slot < end; slot++)
    if (!HASH_VACANT (*slot))
      *vector++ = *slot;
  *vector = 0;

  if (compare)
    qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
  return vector_0;
}

/* Round a given number up to the nearest power of 2. */

static unsigned long
round_up_2 (unsigned long rough)
{
  int round;

  round = 1;
  while (rough)
    {
      round <<= 1;
      rough >>= 1;
    }
  return round;
}
Commit	Line	Data
68bd3b6b RA	1	/* hash.c -- hash table maintenance
	2	Copyright (C) 1995 Free Software Foundation, Inc.
	3	Written by Greg McGary <gkm@gnu.ai.mit.edu>
	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
	16	along with this program; if not, write to the Free Software
	17	Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
	18	*/
	19
	20	#include <config.h>
	21	#include <stdio.h>
	22	#include "hash.h"
	23	#include "error.h"
	24	#include "system.h"
	25	#include "xalloc.h"
	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
	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	if (ht->ht_size > (128 * 1024)) /* prevent size from getting out of hand */
	48	ht->ht_size /= 2;
	49	ht->ht_vec = (void*) XCALLOC (struct token , ht->ht_size);
	50	if (ht->ht_vec == 0)
	51	error (1, 0, _("can't allocate %ld bytes for hash table: memory exhausted"),
	52	ht->ht_size * sizeof(struct token *));
	53	ht->ht_capacity = ht->ht_size * 15 / 16; /* 93.75% loading factor */
	54	ht->ht_fill = 0;
	55	ht->ht_collisions = 0;
	56	ht->ht_lookups = 0;
	57	ht->ht_rehashes = 0;
	58	ht->ht_hash_1 = hash_1;
	59	ht->ht_hash_2 = hash_2;
	60	ht->ht_compare = hash_cmp;
	61	}
	62
	63	/* Load an array of items into `ht'. */
	64
65	void
66	hash_load (struct hash_table* ht, void *item_table, unsigned long cardinality, unsigned long size)
67	{
68	char items = (char ) item_table;
69	while (cardinality--)
70	{
71	hash_insert (ht, items);
72	items += size;
73	}
74	}
75
76	/* Returns the address of the table slot matching `key'. If `key' is
77	not found, return the address of an empty slot suitable for
78	inserting `key'. The caller is responsible for incrementing
79	ht_fill on insertion. */
80
81	void **
82	hash_find_slot (struct hash_table* ht, void const *key)
83	{
84	void **slot;
85	void **deleted_slot = 0;
86	unsigned int hash_2 = 0;
87	unsigned int hash_1 = (*ht->ht_hash_1) (key);
88
89	ht->ht_lookups++;
90	for (;;)
91	{
92	hash_1 %= ht->ht_size;
93	slot = &ht->ht_vec[hash_1];
94
95	if (*slot == 0)
96	return slot;
97	if (*slot == hash_deleted_item)
98	{
99	if (deleted_slot == 0)
100	deleted_slot = slot;
101	}
102	else
103	{
104	if (key == *slot)
105	return slot;
106	if ((ht->ht_compare) (key, slot) == 0)
107	return slot;
108	ht->ht_collisions++;
109	}
110	if (!hash_2)
111	hash_2 = (*ht->ht_hash_2) (key) \| 1;
112	hash_1 += hash_2;
113	}
114	}
115
116	void *
117	hash_find_item (struct hash_table* ht, void const *key)
118	{
119	void **slot = hash_find_slot (ht, key);
120	return ((HASH_VACANT (slot)) ? 0 : slot);
121	}
122
123	void *
124	hash_insert (struct hash_table* ht, void *item)
125	{
126	void **slot = hash_find_slot (ht, item);
127	return hash_insert_at (ht, item, slot);
128	}
129
130	void *
131	hash_insert_at (struct hash_table* ht, void item, void const slot)
132	{
133	void old_item = (void **) slot;
134	if (HASH_VACANT (old_item))
135	{
136	ht->ht_fill++;
137	old_item = item;
138	}
139	(void const *) slot = item;
140	if (ht->ht_fill >= ht->ht_capacity)
141	hash_rehash (ht);
142	return old_item;
143	}
144
145	void *
146	hash_delete (struct hash_table* ht, void const *item)
147	{
148	void **slot = hash_find_slot (ht, item);
149	return hash_delete_at (ht, slot);
150	}
151
152	void *
153	hash_delete_at (struct hash_table* ht, void const *slot)
154	{
155	void item = (void **) slot;
156	if (!HASH_VACANT (item))
157	{
158	(void const *) slot = hash_deleted_item;
159	ht->ht_fill--;
160	return item;
161	}
162	else
163	return 0;
164	}
165
166	void
167	hash_free_items (struct hash_table* ht)
168	{
169	void **vec = ht->ht_vec;
170	void **end = &vec[ht->ht_size];
171	for (; vec < end; vec++)
172	{
173	void item = vec;
174	if (!HASH_VACANT (item))
175	free (item);
176	*vec = 0;
177	}
178	ht->ht_fill = 0;
179	}
180
181	void
182	hash_delete_items (struct hash_table* ht)
183	{
184	void **vec = ht->ht_vec;
185	void **end = &vec[ht->ht_size];
186	for (; vec < end; vec++)
187	*vec = 0;
188	ht->ht_fill = 0;
189	ht->ht_collisions = 0;
190	ht->ht_lookups = 0;
191	ht->ht_rehashes = 0;
192	}
193
194	void
195	hash_free (struct hash_table* ht, int free_items)
196	{
197	if (free_items)
198	hash_free_items (ht);
199	free (ht->ht_vec);
200	ht->ht_vec = 0;
201	ht->ht_fill = 0;
202	ht->ht_capacity = 0;
203	}
204
205	void
206	hash_map (struct hash_table *ht, hash_map_func_t map)
207	{
208	void **slot;
209	void **end = &ht->ht_vec[ht->ht_size];
210
211	for (slot = ht->ht_vec; slot < end; slot++)
212	{
213	if (!HASH_VACANT (*slot))
214	(map) (slot);
215	}
216	}
217
218	/* Double the size of the hash table in the event of overflow... */
219
220	static void
221	hash_rehash (struct hash_table* ht)
222	{
223	unsigned long old_ht_size = ht->ht_size;
224	void **old_vec = ht->ht_vec;
225	void **ovp;
226	void **slot;
227
228	ht->ht_size *= 2;
229	ht->ht_rehashes++;
230	ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
231	ht->ht_vec = (void *) XCALLOC (struct token , ht->ht_size);
232
233	for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
234	{
235	if (*ovp == 0)
236	continue;
237	slot = hash_find_slot (ht, *ovp);
238	slot = ovp;
239	}
240	free (old_vec);
241	}
242
243	void
244	hash_print_stats (struct hash_table ht, FILE out_FILE)
245	{
246	fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
247	100.0 * (double) ht->ht_fill / (double) ht->ht_size);
248	fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
249	fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
250	(ht->ht_lookups
251	? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
252	: 0));
253	}
254
255	/* Dump all items into a NULL-terminated vector. Use the
256	user-supplied vector, or malloc one. */
257
258	void**
259	hash_dump (struct hash_table ht, void *vector_0, qsort_cmp_t compare)
260	{
261	void **vector;
262	void **slot;
263	void **end = &ht->ht_vec[ht->ht_size];
264
265	if (vector_0 == 0)
266	vector_0 = XMALLOC (void *, ht->ht_fill + 1);
267	vector = vector_0;
268
269	for (slot = ht->ht_vec; slot < end; slot++)
270	if (!HASH_VACANT (*slot))
271	vector++ = slot;
272	*vector = 0;
273
274	if (compare)
275	qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
276	return vector_0;
277	}
278
279	/* Round a given number up to the nearest power of 2. */
280
281	static unsigned long
282	round_up_2 (unsigned long rough)
283	{
284	int round;
285
286	round = 1;
287	while (rough)
288	{
289	round <<= 1;
290	rough >>= 1;
291	}
292	return round;
293	}