1/* hash - implement simple hashing table with string based keys.
2   Copyright (C) 1994-1995, 2000-2004 Free Software Foundation, Inc.
3   Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
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 Foundation,
17   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
18
19#if HAVE_CONFIG_H
20# include <config.h>
21#endif
22
23/* Specification.  */
24#include "hash.h"
25
26#include <stdlib.h>
27#include <string.h>
28#include <stdio.h>
29#include <limits.h>
30#include <sys/types.h>
31
32#include <obstack.h>
33
34#include "xalloc.h"
35
36#define obstack_chunk_alloc xmalloc
37#define obstack_chunk_free free
38
39typedef struct hash_entry
40{
41  unsigned long used;
42  const void *key;
43  size_t keylen;
44  void *data;
45  struct hash_entry *next;
46}
47hash_entry;
48
49/* Forward declaration of local functions.  */
50static void insert_entry_2 (hash_table *htab,
51			    const void *key, size_t keylen,
52			    unsigned long int hval, size_t idx, void *data);
53static size_t lookup (hash_table *htab,
54		      const void *key, size_t keylen,
55		      unsigned long int hval);
56static unsigned long compute_hashval (const void *key, size_t keylen);
57static int is_prime (unsigned long int candidate);
58
59
60int
61init_hash (hash_table *htab, unsigned long int init_size)
62{
63  /* We need the size to be a prime.  */
64  init_size = next_prime (init_size);
65
66  /* Initialize the data structure.  */
67  htab->size = init_size;
68  htab->filled = 0;
69  htab->first = NULL;
70  htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry));
71
72  obstack_init (&htab->mem_pool);
73
74  return 0;
75}
76
77
78int
79delete_hash (hash_table *htab)
80{
81  free (htab->table);
82  obstack_free (&htab->mem_pool, NULL);
83  return 0;
84}
85
86
87int
88insert_entry (hash_table *htab, const void *key, size_t keylen, void *data)
89{
90  unsigned long int hval = compute_hashval (key, keylen);
91  hash_entry *table = (hash_entry *) htab->table;
92  size_t idx = lookup (htab, key, keylen, hval);
93
94  if (table[idx].used)
95    /* We don't want to overwrite the old value.  */
96    return -1;
97  else
98    {
99      /* An empty bucket has been found.  */
100      insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
101		      keylen, hval, idx, data);
102      return 0;
103    }
104}
105
106static void
107insert_entry_2 (hash_table *htab,
108		const void *key, size_t keylen,
109		unsigned long int hval, size_t idx, void *data)
110{
111  hash_entry *table = (hash_entry *) htab->table;
112
113  table[idx].used = hval;
114  table[idx].key = key;
115  table[idx].keylen = keylen;
116  table[idx].data = data;
117
118  /* List the new value in the list.  */
119  if ((hash_entry *) htab->first == NULL)
120    {
121      table[idx].next = &table[idx];
122      *(hash_entry **) &htab->first = &table[idx];
123    }
124  else
125    {
126      table[idx].next = ((hash_entry *) htab->first)->next;
127      ((hash_entry *) htab->first)->next = &table[idx];
128      *(hash_entry **) &htab->first = &table[idx];
129    }
130
131  ++htab->filled;
132  if (100 * htab->filled > 75 * htab->size)
133    {
134      /* Table is filled more than 75%.  Resize the table.  */
135      unsigned long int old_size = htab->size;
136
137      htab->size = next_prime (htab->size * 2);
138      htab->filled = 0;
139      htab->first = NULL;
140      htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));
141
142      for (idx = 1; idx <= old_size; ++idx)
143	if (table[idx].used)
144	  insert_entry_2 (htab, table[idx].key, table[idx].keylen,
145			  table[idx].used,
146			  lookup (htab, table[idx].key, table[idx].keylen,
147				  table[idx].used),
148			  table[idx].data);
149
150      free (table);
151    }
152}
153
154
155int
156find_entry (hash_table *htab, const void *key, size_t keylen, void **result)
157{
158  hash_entry *table = (hash_entry *) htab->table;
159  size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
160
161  if (table[idx].used == 0)
162    return -1;
163
164  *result = table[idx].data;
165  return 0;
166}
167
168
169int
170iterate_table (hash_table *htab, void **ptr, const void **key, size_t *keylen,
171	       void **data)
172{
173  if (*ptr == NULL)
174    {
175      if (htab->first == NULL)
176	return -1;
177      *ptr = (void *) ((hash_entry *) htab->first)->next;
178    }
179  else
180    {
181      if (*ptr == htab->first)
182	return -1;
183      *ptr = (void *) (((hash_entry *) *ptr)->next);
184    }
185
186  *key = ((hash_entry *) *ptr)->key;
187  *keylen = ((hash_entry *) *ptr)->keylen;
188  *data = ((hash_entry *) *ptr)->data;
189  return 0;
190}
191
192
193/* References:
194   [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
195   [Knuth]	      The Art of Computer Programming, part3 (6.4) */
196
197static size_t
198lookup (hash_table *htab,
199	const void *key, size_t keylen,
200	unsigned long int hval)
201{
202  unsigned long int hash;
203  size_t idx;
204  hash_entry *table = (hash_entry *) htab->table;
205
206  /* First hash function: simply take the modul but prevent zero.  */
207  hash = 1 + hval % htab->size;
208
209  idx = hash;
210
211  if (table[idx].used)
212    {
213      if (table[idx].used == hval && table[idx].keylen == keylen
214	  && memcmp (table[idx].key, key, keylen) == 0)
215	return idx;
216
217      /* Second hash function as suggested in [Knuth].  */
218      hash = 1 + hval % (htab->size - 2);
219
220      do
221	{
222	  if (idx <= hash)
223	    idx = htab->size + idx - hash;
224	  else
225	    idx -= hash;
226
227	  /* If entry is found use it.  */
228	  if (table[idx].used == hval && table[idx].keylen == keylen
229	      && memcmp (table[idx].key, key, keylen) == 0)
230	    return idx;
231	}
232      while (table[idx].used);
233    }
234  return idx;
235}
236
237
238static unsigned long
239compute_hashval (const void *key, size_t keylen)
240{
241  size_t cnt;
242  unsigned long int hval;
243
244  /* Compute the hash value for the given string.  The algorithm
245     is taken from [Aho,Sethi,Ullman].  */
246  cnt = 0;
247  hval = keylen;
248  while (cnt < keylen)
249    {
250      hval = (hval << 9) | (hval >> (sizeof (unsigned long) * CHAR_BIT - 9));
251      hval += (unsigned long int) *(((const char *) key) + cnt++);
252    }
253  return hval != 0 ? hval : ~((unsigned long) 0);
254}
255
256
257unsigned long
258next_prime (unsigned long int seed)
259{
260  /* Make it definitely odd.  */
261  seed |= 1;
262
263  while (!is_prime (seed))
264    seed += 2;
265
266  return seed;
267}
268
269
270static int
271is_prime (unsigned long int candidate)
272{
273  /* No even number and none less than 10 will be passed here.  */
274  unsigned long int divn = 3;
275  unsigned long int sq = divn * divn;
276
277  while (sq < candidate && candidate % divn != 0)
278    {
279      ++divn;
280      sq += 4 * divn;
281      ++divn;
282    }
283
284  return candidate % divn != 0;
285}
286