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