Sat Feb 17 11:29:29 1996 David Mosberger-Tang <davidm@azstarnet.com>
[kopensolaris-gnu/glibc.git] / locale / locfile-hash.c
1 /* Copyright (C) 1995 Free Software Foundation, Inc.
2
3 The GNU C Library is free software; you can redistribute it and/or
4 modify it under the terms of the GNU Library General Public License as
5 published by the Free Software Foundation; either version 2 of the
6 License, or (at your option) any later version.
7
8 The GNU C Library is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11 Library General Public License for more details.
12
13 You should have received a copy of the GNU Library General Public
14 License along with the GNU C Library; see the file COPYING.LIB.  If
15 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
16 Cambridge, MA 02139, USA.  */
17
18 #include <obstack.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <values.h>
22
23 #include "hash.h"
24
25 #define obstack_chunk_alloc xmalloc
26 #define obstack_chunk_free free
27
28 void *xmalloc (size_t n);
29
30 typedef struct hash_entry
31   {
32     int used;
33     char *key;
34     void *data;
35     struct hash_entry *next;
36   }
37 hash_entry;
38
39 /* Prototypes for local functions.  */
40 static size_t lookup (hash_table *htab, const char *key, size_t keylen,
41                       unsigned long hval);
42 static unsigned long compute_hashval(const char *key, size_t keylen);
43 static unsigned long next_prime(unsigned long seed);
44 static int is_prime(unsigned long candidate);
45
46
47 int
48 init_hash(hash_table *htab, unsigned long init_size)
49 {
50   /* We need the size to be a prime.  */
51   init_size = next_prime (init_size);
52
53   /* Initialize the data structure.  */
54   htab->size = init_size;
55   htab->filled = 0;
56   htab->first = NULL;
57   htab->table = calloc (init_size + 1, sizeof (hash_entry));
58   obstack_init (&htab->mem_pool);
59
60   return htab->table == NULL;
61 }
62
63
64 int
65 delete_hash(hash_table *htab)
66 {
67   free (htab->table);
68   obstack_free (&htab->mem_pool, NULL);
69   return 0;
70 }
71
72
73 int
74 insert_entry (hash_table *htab, const char *key, size_t keylen, void *data)
75 {
76   unsigned long hval = compute_hashval (key, keylen);
77   hash_entry *table = (hash_entry *) htab->table;
78   size_t idx = lookup (htab, key, keylen, hval);
79
80   if (table[idx].used)
81     /* We don't want to overwrite the old value.  */
82     return 1;
83   else
84     {
85       hash_entry **p;
86
87       /* An empty bucket has been found.  */
88       table[idx].used = hval;
89       table[idx].key = obstack_copy0 (&htab->mem_pool, key, keylen);
90       table[idx].data = data;
91
92       /* List the new value in the ordered list.  */
93       for (p = (hash_entry **) &htab->first; *p != NULL && (*p)->data < data;
94            p = &(*p)->next);
95       if (*p == NULL || (*p)->data > data)
96         /* Insert new value in the list.  */
97         {
98           table[idx].next = *p;
99           *p = &table[idx];
100         }
101
102       ++htab->filled;
103       if (100 * htab->filled > 90 * htab->size)
104         {
105           /* Resize the table.  */
106           unsigned long old_size = htab->size;
107
108           htab->size = next_prime (htab->size * 2);
109           htab->filled = 0;
110           htab->first = NULL;
111           htab->table = calloc (htab->size, sizeof (hash_entry));
112
113           for (idx = 1; idx <= old_size; ++idx)
114             if (table[idx].used)
115               insert_entry (htab, table[idx].key, strlen(table[idx].key),
116                             table[idx].data);
117
118           free (table);
119         }
120       return 0;
121     }
122   /* NOTREACHED */
123 }
124
125
126 int
127 find_entry (hash_table *htab, const char *key, size_t keylen, void **result)
128 {
129   hash_entry *table = (hash_entry *) htab->table;
130   size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));
131   int retval;
132
133   retval = table[idx].used;
134   *result = retval ? table[idx].data : NULL;
135
136   return retval;
137 }
138
139
140 int
141 iterate_table (hash_table *htab, void **ptr, void **result)
142 {
143   if (*ptr == NULL)
144     *ptr = (void *) htab->first;
145   else
146     {
147       *ptr = (void *) (((hash_entry *) *ptr)->next);
148       if (*ptr == NULL)
149         return 0;
150     }
151
152   *result = ((hash_entry *) *ptr)->data;
153   return 1;
154 }
155
156
157 static size_t
158 lookup (hash_table *htab, const char *key, size_t keylen, unsigned long hval)
159 {
160   unsigned long hash;
161   size_t idx;
162   hash_entry *table = (hash_entry *) htab->table;
163
164   /* First hash function: simply take the modul but prevent zero.  */
165   hash = 1 + hval % htab->size;
166
167   idx = hash;
168   
169   if (table[idx].used)
170     {
171       if (table[idx].used == hval && table[idx].key[keylen] == '\0'
172           && strncmp (key, table[idx].key, keylen) == 0)
173         return idx;
174
175       /* Second hash function as suggested in [Knuth].  */
176       hash = 1 + hash % (htab->size - 2);
177
178       do
179         {
180           if (idx <= hash)
181             idx = htab->size + idx - hash;
182           else
183             idx -= hash;
184
185           /* If entry is found use it.  */
186           if (table[idx].used == hval && table[idx].key[keylen] == '\0'
187               && strncmp (key, table[idx].key, keylen) == 0)
188             return idx;
189         }
190       while (table[idx].used);
191     }
192   return idx;
193 }
194
195
196 static unsigned long
197 compute_hashval(const char *key, size_t keylen)
198 {
199   size_t cnt;
200   unsigned long hval, g;
201   /* Compute the hash value for the given string.  */
202   cnt = 0;
203   hval = keylen;
204   while (cnt < keylen)
205     {
206       hval <<= 4;
207       hval += key[cnt++];
208       g = hval & (0xfL << (LONGBITS - 4));
209       if (g != 0)
210         {
211           hval ^= g >> (LONGBITS - 8);
212           hval ^= g;
213         }
214     }
215   return hval;
216 }
217
218
219 static unsigned long
220 next_prime(unsigned long seed)
221 {
222   /* Make it definitely odd.  */
223   seed |= 1;
224
225   while (!is_prime (seed))
226     seed += 2;
227
228   return seed;
229 }
230
231
232 static int
233 is_prime(unsigned long candidate)
234 {
235   /* No even number and none less than 10 will be passwd here.  */
236   unsigned long div = 3;
237   unsigned long sq = div * div;
238
239   while (sq < candidate && candidate % div != 0)
240     {
241       ++div;
242       sq += 4 * div;
243       ++div;
244     }
245
246   return candidate % div != 0;
247 }
248
249 /*
250  * Local Variables:
251  *  mode:c
252  *  c-basic-offset:2
253  * End:
254  */