(add_to_readlist): Take locale pointer as extra parameter from which
[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, 2000 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 extern void *xmalloc (size_t __n);
57 extern void *xcalloc (size_t __n, size_t __m);
58
59 typedef struct hash_entry
60 {
61   unsigned long used;
62   const void *key;
63   size_t keylen;
64   void *data;
65   struct hash_entry *next;
66 }
67 hash_entry;
68
69 /* Prototypes for local functions.  */
70 static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen,
71                             unsigned long hval, size_t idx, void *data);
72 static size_t lookup (hash_table *htab, const void *key, size_t keylen,
73                       unsigned long int hval);
74 static size_t lookup_2 (hash_table *htab, const void *key, size_t keylen,
75                         unsigned long int hval);
76 static unsigned long compute_hashval (const void *key, size_t keylen);
77 static int is_prime (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 *) xcalloc (init_size + 1, sizeof (hash_entry));
93   if (htab->table == NULL)
94     return -1;
95
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 *) xcalloc (1 + htab->size, sizeof (hash_entry));
174
175       for (idx = 1; idx <= old_size; ++idx)
176         if (table[idx].used)
177           insert_entry_2 (htab, table[idx].key, table[idx].keylen,
178                           table[idx].used,
179                           lookup_2 (htab, table[idx].key, table[idx].keylen,
180                                     table[idx].used),
181                           table[idx].data);
182
183       free (table);
184     }
185 }
186
187
188 int
189 find_entry (htab, key, keylen, result)
190      hash_table *htab;
191      const void *key;
192      size_t keylen;
193      void **result;
194 {
195   hash_entry *table = (hash_entry *) htab->table;
196   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
197
198   if (table[idx].used == 0)
199     return -1;
200
201   *result = table[idx].data;
202   return 0;
203 }
204
205
206 int
207 set_entry (htab, key, keylen, newval)
208      hash_table *htab;
209      const void *key;
210      size_t keylen;
211      void *newval;
212 {
213   hash_entry *table = (hash_entry *) htab->table;
214   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
215
216   if (table[idx].used == 0)
217     return -1;
218
219   table[idx].data = newval;
220   return 0;
221 }
222
223
224 int
225 iterate_table (htab, ptr, key, keylen, data)
226      hash_table *htab;
227      void **ptr;
228      const void **key;
229      size_t *keylen;
230      void **data;
231 {
232   if (*ptr == NULL)
233     {
234       if (htab->first == NULL)
235         return -1;
236       *ptr = (void *) ((hash_entry *) htab->first)->next;
237     }
238   else
239     {
240       if (*ptr == htab->first)
241         return -1;
242       *ptr = (void *) (((hash_entry *) *ptr)->next);
243     }
244
245   *key = ((hash_entry *) *ptr)->key;
246   *keylen = ((hash_entry *) *ptr)->keylen;
247   *data = ((hash_entry *) *ptr)->data;
248   return 0;
249 }
250
251
252 static size_t
253 lookup (htab, key, keylen, hval)
254      hash_table *htab;
255      const void *key;
256      size_t keylen;
257      unsigned long hval;
258 {
259   unsigned long hash;
260   size_t idx;
261   hash_entry *table = (hash_entry *) htab->table;
262
263   /* First hash function: simply take the modul but prevent zero.  */
264   hash = 1 + hval % htab->size;
265
266   idx = hash;
267
268   if (table[idx].used)
269     {
270       if (table[idx].used == hval && table[idx].keylen == keylen
271           && memcmp (key, table[idx].key, keylen) == 0)
272         return idx;
273
274       /* Second hash function as suggested in [Knuth].  */
275       hash = 1 + hval % (htab->size - 2);
276
277       do
278         {
279           if (idx <= hash)
280             idx = htab->size + idx - hash;
281           else
282             idx -= hash;
283
284           /* If entry is found use it.  */
285           if (table[idx].used == hval && table[idx].keylen == keylen
286               && memcmp (key, table[idx].key, keylen) == 0)
287             return idx;
288         }
289       while (table[idx].used);
290     }
291   return idx;
292 }
293
294
295 /* References:
296    [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
297    [Knuth]            The Art of Computer Programming, part3 (6.4) */
298
299 static size_t
300 lookup_2 (htab, key, keylen, hval)
301      hash_table *htab;
302      const void *key;
303      size_t keylen;
304      unsigned long int hval;
305 {
306   unsigned long int hash;
307   size_t idx;
308   hash_entry *table = (hash_entry *) htab->table;
309
310   /* First hash function: simply take the modul but prevent zero.  */
311   hash = 1 + hval % htab->size;
312
313   idx = hash;
314
315   if (table[idx].used)
316     {
317       if (table[idx].used == hval && table[idx].keylen == keylen
318           && memcmp (table[idx].key, key, keylen) == 0)
319         return idx;
320
321       /* Second hash function as suggested in [Knuth].  */
322       hash = 1 + hval % (htab->size - 2);
323
324       do
325         {
326           if (idx <= hash)
327             idx = htab->size + idx - hash;
328           else
329             idx -= hash;
330
331           /* If entry is found use it.  */
332           if (table[idx].used == hval && table[idx].keylen == keylen
333               && memcmp (table[idx].key, key, keylen) == 0)
334             return idx;
335         }
336       while (table[idx].used);
337     }
338   return idx;
339 }
340
341
342 static unsigned long
343 compute_hashval (key, keylen)
344      const void *key;
345      size_t keylen;
346 {
347   size_t cnt;
348   unsigned long int hval, g;
349
350   /* Compute the hash value for the given string.  The algorithm
351      is taken from [Aho,Sethi,Ullman].  */
352   cnt = 0;
353   hval = keylen;
354   while (cnt < keylen)
355     {
356       hval <<= 4;
357       hval += (unsigned long int) *(((char *) key) + cnt++);
358       g = hval & ((unsigned long) 0xf << (LONGBITS - 4));
359       if (g != 0)
360         {
361           hval ^= g >> (LONGBITS - 8);
362           hval ^= g;
363         }
364     }
365   return hval != 0 ? hval : ~((unsigned long) 0);
366 }
367
368
369 unsigned long
370 next_prime (seed)
371      unsigned long int seed;
372 {
373   /* Make it definitely odd.  */
374   seed |= 1;
375
376   while (!is_prime (seed))
377     seed += 2;
378
379   return seed;
380 }
381
382
383 static int
384 is_prime (candidate)
385      unsigned long int candidate;
386 {
387   /* No even number and none less than 10 will be passed here.  */
388   unsigned long int divn = 3;
389   unsigned long int sq = divn * divn;
390
391   while (sq < candidate && candidate % divn != 0)
392     {
393       ++divn;
394       sq += 4 * divn;
395       ++divn;
396     }
397
398   return candidate % divn != 0;
399 }