Sat Mar 23 17:52:49 1996 Ulrich Drepper <drepper@gnu.ai.mit.edu>
[kopensolaris-gnu/glibc.git] / locale / programs / simple-hash.c
1 /* hash - implement simple hashing table with string based keys.
2    Copyright (C) 1994, 1995, 1996 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
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
18
19 #ifdef HAVE_CONFIG_H
20 # include <config.h>
21 #endif
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <sys/types.h>
27
28 #if HAVE_OBSTACK
29 # include <obstack.h>
30 #else
31 # include "obstack.h"
32 #endif
33
34 #ifdef HAVE_VALUES_H
35 # include <values.h>
36 #endif
37
38 #include "simple-hash.h"
39
40 #define obstack_chunk_alloc xmalloc
41 #define obstack_chunk_free free
42
43 #ifndef BITSPERBYTE
44 # define BITSPERBYTE 8
45 #endif
46
47 #ifndef LONGBITS
48 # define LONGBITS (sizeof (long) * BITSPERBYTE)
49 #endif
50
51 #ifndef bcopy
52 # define bcopy(s, d, n) memcpy ((d), (s), (n))
53 #endif
54
55 void *xmalloc __P ((size_t __n));
56
57 typedef struct hash_entry
58 {
59   unsigned long used;
60   const void *key;
61   size_t keylen;
62   void *data;
63   struct hash_entry *next;
64 }
65 hash_entry;
66
67 /* Prototypes for local functions.  */
68 static void insert_entry_2 __P ((hash_table *htab, const void *key,
69                                  size_t keylen, unsigned long hval,
70                                  size_t idx, void *data));
71 static size_t lookup __P ((hash_table *htab, const void *key, size_t keylen,
72                            unsigned long int hval));
73 static size_t lookup_2 __P ((hash_table *htab, const void *key,
74                              size_t keylen, unsigned long int hval));
75 static unsigned long compute_hashval __P ((const void *key, size_t keylen));
76 static int is_prime __P ((unsigned long int candidate));
77
78
79 int
80 init_hash (htab, init_size)
81      hash_table *htab;
82      unsigned long int init_size;
83 {
84   /* We need the size to be a prime.  */
85   init_size = next_prime (init_size);
86
87   /* Initialize the data structure.  */
88   htab->size = init_size;
89   htab->filled = 0;
90   htab->first = NULL;
91   htab->table = (void *) xmalloc ((init_size + 1) * sizeof (hash_entry));
92   if (htab->table == NULL)
93     return -1;
94
95   memset (htab->table, '\0', (init_size + 1) * sizeof (hash_entry));
96   obstack_init (&htab->mem_pool);
97
98   return 0;
99 }
100
101
102 int
103 delete_hash (htab)
104      hash_table *htab;
105 {
106   free (htab->table);
107   obstack_free (&htab->mem_pool, NULL);
108   return 0;
109 }
110
111
112 int
113 insert_entry (htab, key, keylen, data)
114      hash_table *htab;
115      const void *key;
116      size_t keylen;
117      void *data;
118 {
119   unsigned long int hval = compute_hashval (key, keylen);
120   hash_entry *table = (hash_entry *) htab->table;
121   size_t idx = lookup (htab, key, keylen, hval);
122
123   if (table[idx].used)
124     /* We don't want to overwrite the old value.  */
125     return -1;
126   else
127     {
128       /* An empty bucket has been found.  */
129       insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
130                       keylen, hval, idx, data);
131       return 0;
132     }
133 }
134
135 static void
136 insert_entry_2 (htab, key, keylen, hval, idx, data)
137      hash_table *htab;
138      const void *key;
139      size_t keylen;
140      unsigned long int hval;
141      size_t idx;
142      void *data;
143 {
144   hash_entry *table = (hash_entry *) htab->table;
145
146   table[idx].used = hval;
147   table[idx].key = key;
148   table[idx].keylen = keylen;
149   table[idx].data = data;
150
151       /* List the new value in the list.  */
152   if ((hash_entry *) htab->first == NULL)
153     {
154       table[idx].next = &table[idx];
155       *(hash_entry **) &htab->first = &table[idx];
156     }
157   else
158     {
159       table[idx].next = ((hash_entry *) htab->first)->next;
160       ((hash_entry *) htab->first)->next = &table[idx];
161       *(hash_entry **) &htab->first = &table[idx];
162     }
163
164   ++htab->filled;
165   if (100 * htab->filled > 90 * htab->size)
166     {
167       /* Table is filled more than 90%.  Resize the table.  */
168       unsigned long int old_size = htab->size;
169
170       htab->size = next_prime (htab->size * 2);
171       htab->filled = 0;
172       htab->first = NULL;
173       htab->table = (void *) xmalloc ((1 + htab->size)
174                                       * sizeof (hash_entry));
175       memset (htab->table, '\0', (1 + htab->size) * sizeof (hash_entry));
176
177       for (idx = 1; idx <= old_size; ++idx)
178         if (table[idx].used)
179           insert_entry_2 (htab, table[idx].key, table[idx].keylen,
180                           table[idx].used,
181                           lookup_2 (htab, table[idx].key, table[idx].keylen,
182                                     table[idx].used),
183                           table[idx].data);
184
185       free (table);
186     }
187 }
188
189
190 int
191 find_entry (htab, key, keylen, result)
192      hash_table *htab;
193      const void *key;
194      size_t keylen;
195      void **result;
196 {
197   hash_entry *table = (hash_entry *) htab->table;
198   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
199
200   if (table[idx].used == 0)
201     return -1;
202
203   *result = table[idx].data;
204   return 0;
205 }
206
207
208 int
209 set_entry (htab, key, keylen, newval)
210      hash_table *htab;
211      const void *key;
212      size_t keylen;
213      void *newval;
214 {
215   hash_entry *table = (hash_entry *) htab->table;
216   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
217
218   if (table[idx].used == 0)
219     return -1;
220
221   table[idx].data = newval;
222   return 0;
223 }
224
225
226 int
227 iterate_table (htab, ptr, key, keylen, data)
228      hash_table *htab;
229      void **ptr;
230      const void **key;
231      size_t *keylen;
232      void **data;
233 {
234   if (*ptr == NULL)
235     {
236       if (htab->first == NULL)
237         return -1;
238       *ptr = (void *) ((hash_entry *) htab->first)->next;
239     }
240   else
241     {
242       if (*ptr == htab->first)
243         return -1;
244       *ptr = (void *) (((hash_entry *) *ptr)->next);
245     }
246
247   *key = ((hash_entry *) *ptr)->key;
248   *keylen = ((hash_entry *) *ptr)->keylen;
249   *data = ((hash_entry *) *ptr)->data;
250   return 0;
251 }
252
253
254 static size_t
255 lookup (htab, key, keylen, hval)
256      hash_table *htab;
257      const void *key;
258      size_t keylen;
259      unsigned long hval;
260 {
261   unsigned long hash;
262   size_t idx;
263   hash_entry *table = (hash_entry *) htab->table;
264
265   /* First hash function: simply take the modul but prevent zero.  */
266   hash = 1 + hval % htab->size;
267
268   idx = hash;
269
270   if (table[idx].used)
271     {
272       if (table[idx].used == hval && table[idx].keylen == keylen
273           && memcmp (key, table[idx].key, keylen) == 0)
274         return idx;
275
276       /* Second hash function as suggested in [Knuth].  */
277       hash = 1 + hval % (htab->size - 2);
278
279       do
280         {
281           if (idx <= hash)
282             idx = htab->size + idx - hash;
283           else
284             idx -= hash;
285
286           /* If entry is found use it.  */
287           if (table[idx].used == hval && table[idx].keylen == keylen
288               && memcmp (key, table[idx].key, keylen) == 0)
289             return idx;
290         }
291       while (table[idx].used);
292     }
293   return idx;
294 }
295
296
297 /* References:
298    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
299    [Knuth]            The Art of Computer Programming, part3 (6.4) */
300
301 static size_t
302 lookup_2 (htab, key, keylen, hval)
303      hash_table *htab;
304      const void *key;
305      size_t keylen;
306      unsigned long int hval;
307 {
308   unsigned long int hash;
309   size_t idx;
310   hash_entry *table = (hash_entry *) htab->table;
311
312   /* First hash function: simply take the modul but prevent zero.  */
313   hash = 1 + hval % htab->size;
314
315   idx = hash;
316
317   if (table[idx].used)
318     {
319       if (table[idx].used == hval && table[idx].keylen == keylen
320           && memcmp (table[idx].key, key, keylen) == 0)
321         return idx;
322
323       /* Second hash function as suggested in [Knuth].  */
324       hash = 1 + hval % (htab->size - 2);
325
326       do
327         {
328           if (idx <= hash)
329             idx = htab->size + idx - hash;
330           else
331             idx -= hash;
332
333           /* If entry is found use it.  */
334           if (table[idx].used == hval && table[idx].keylen == keylen
335               && memcmp (table[idx].key, key, keylen) == 0)
336             return idx;
337         }
338       while (table[idx].used);
339     }
340   return idx;
341 }
342
343
344 static unsigned long
345 compute_hashval (key, keylen)
346      const void *key;
347      size_t keylen;
348 {
349   size_t cnt;
350   unsigned long int hval, g;
351
352   /* Compute the hash value for the given string.  The algorithm
353      is taken from [Aho,Sethi,Ullman].  */
354   cnt = 0;
355   hval = keylen;
356   while (cnt < keylen)
357     {
358       hval <<= 4;
359       hval += (unsigned long int) *(((char *) key) + cnt++);
360       g = hval & ((unsigned long) 0xf << (LONGBITS - 4));
361       if (g != 0)
362         {
363           hval ^= g >> (LONGBITS - 8);
364           hval ^= g;
365         }
366     }
367   return hval != 0 ? hval : ~((unsigned long) 0);
368 }
369
370
371 unsigned long
372 next_prime (seed)
373      unsigned long int seed;
374 {
375   /* Make it definitely odd.  */
376   seed |= 1;
377
378   while (!is_prime (seed))
379     seed += 2;
380
381   return seed;
382 }
383
384
385 static int
386 is_prime (candidate)
387      unsigned long int candidate;
388 {
389   /* No even number and none less than 10 will be passed here.  */
390   unsigned long int divn = 3;
391   unsigned long int sq = divn * divn;
392
393   while (sq < candidate && candidate % divn != 0)
394     {
395       ++divn;
396       sq += 4 * divn;
397       ++divn;
398     }
399
400   return candidate % divn != 0;
401 }