1 /* Copyright (C) 2000, 2001, 2002 Red Hat, Inc.
2 Written by Ulrich Drepper <drepper@redhat.com>, 2000.
3
4 This program is Open Source software; you can redistribute it and/or
5 modify it under the terms of the Open Software License version 1.0 as
6 published by the Open Source Initiative.
7
8 You should have received a copy of the Open Software License along
9 with this program; if not, you may obtain a copy of the Open Software
10 License version 1.0 from http://www.opensource.org/licenses/osl.php or
11 by writing the Open Source Initiative c/o Lawrence Rosen, Esq.,
12 3001 King Ranch Road, Ukiah, CA 95482. */
13
14 #include <assert.h>
15 #include <stdlib.h>
16 #include <system.h>
17
18 /* Before including this file the following macros must be defined:
19
20 NAME name of the hash table structure.
21 TYPE data type of the hash table entries
22 COMPARE comparison function taking two pointers to TYPE objects
23
24 The following macros if present select features:
25
26 ITERATE iterating over the table entries is possible
27 REVERSE iterate in reverse order of insert
28 */
29
30
31 static size_t
lookup(htab,hval,val)32 lookup (htab, hval, val)
33 NAME *htab;
34 unsigned long int hval;
35 TYPE val;
36 {
37 /* First hash function: simply take the modul but prevent zero. */
38 size_t idx = 1 + hval % htab->size;
39
40 if (htab->table[idx].hashval != 0)
41 {
42 unsigned long int hash;
43
44 if (htab->table[idx].hashval == hval
45 && COMPARE (htab->table[idx].data, val) == 0)
46 return idx;
47
48 /* Second hash function as suggested in [Knuth]. */
49 hash = 1 + hval % (htab->size - 2);
50
51 do
52 {
53 if (idx <= hash)
54 idx = htab->size + idx - hash;
55 else
56 idx -= hash;
57
58 /* If entry is found use it. */
59 if (htab->table[idx].hashval == hval
60 && COMPARE (htab->table[idx].data, val) == 0)
61 return idx;
62 }
63 while (htab->table[idx].hashval);
64 }
65 return idx;
66 }
67
68
69 static void
insert_entry_2(NAME * htab,unsigned long int hval,size_t idx,TYPE data)70 insert_entry_2 (NAME *htab, unsigned long int hval, size_t idx, TYPE data)
71 {
72 #ifdef ITERATE
73 if (htab->table[idx].hashval == 0)
74 {
75 # ifdef REVERSE
76 htab->table[idx].next = htab->first;
77 htab->first = &htab->table[idx];
78 # else
79 /* Add the new value to the list. */
80 if (htab->first == NULL)
81 htab->first = htab->table[idx].next = &htab->table[idx];
82 else
83 {
84 htab->table[idx].next = htab->first->next;
85 htab->first = htab->first->next = &htab->table[idx];
86 }
87 # endif
88 }
89 #endif
90
91 htab->table[idx].hashval = hval;
92 htab->table[idx].data = data;
93
94 ++htab->filled;
95 if (100 * htab->filled > 90 * htab->size)
96 {
97 /* Table is filled more than 90%. Resize the table. */
98 #ifdef ITERATE
99 __typeof__ (htab->first) first;
100 # ifndef REVERSE
101 __typeof__ (htab->first) runp;
102 # endif
103 #else
104 unsigned long int old_size = htab->size;
105 #endif
106 #define _TABLE(name) \
107 name##_ent *table = htab->table
108 #define TABLE(name) _TABLE (name)
109 TABLE(NAME);
110
111 htab->size = next_prime (htab->size * 2);
112 htab->filled = 0;
113 #ifdef ITERATE
114 first = htab->first;
115 htab->first = NULL;
116 #endif
117 htab->table = calloc ((1 + htab->size), sizeof (htab->table[0]));
118 if (htab->table == NULL)
119 {
120 /* We cannot enlarge the table. Live with what we got. This
121 might lead to an infinite loop at some point, though. */
122 htab->table = table;
123 return;
124 }
125
126 /* Add the old entries to the new table. When iteration is
127 supported we maintain the order. */
128 #ifdef ITERATE
129 # ifdef REVERSE
130 while (first != NULL)
131 {
132 insert_entry_2 (htab, first->hashval,
133 lookup (htab, first->hashval, first->data),
134 first->data);
135
136 first = first->next;
137 }
138 # else
139 assert (first != NULL);
140 runp = first = first->next;
141 do
142 insert_entry_2 (htab, runp->hashval,
143 lookup (htab, runp->hashval, runp->data), runp->data);
144 while ((runp = runp->next) != first);
145 # endif
146 #else
147 for (idx = 1; idx <= old_size; ++idx)
148 if (table[idx].hashval != 0)
149 insert_entry_2 (htab, table[idx].hashval,
150 lookup (htab, table[idx].hashval, table[idx].data),
151 table[idx].data);
152 #endif
153
154 free (table);
155 }
156 }
157
158
159 int
160 #define INIT(name) _INIT (name)
161 #define _INIT(name) \
162 name##_init
163 INIT(NAME) (htab, init_size)
164 NAME *htab;
165 unsigned long int init_size;
166 {
167 /* We need the size to be a prime. */
168 init_size = next_prime (init_size);
169
170 /* Initialize the data structure. */
171 htab->size = init_size;
172 htab->filled = 0;
173 #ifdef ITERATE
174 htab->first = NULL;
175 #endif
176 htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0]));
177 if (htab->table == NULL)
178 return -1;
179
180 return 0;
181 }
182
183
184 int
185 #define FREE(name) _FREE (name)
186 #define _FREE(name) \
187 name##_free
188 FREE(NAME) (htab)
189 NAME *htab;
190 {
191 free (htab->table);
192 return 0;
193 }
194
195
196 int
197 #define INSERT(name) _INSERT (name)
198 #define _INSERT(name) \
199 name##_insert
200 INSERT(NAME) (htab, hval, data)
201 NAME *htab;
202 unsigned long int hval;
203 TYPE data;
204 {
205 size_t idx;
206
207 /* Make the hash value nonzero. */
208 hval = hval ?: 1;
209
210 idx = lookup (htab, hval, data);
211
212 if (htab->table[idx].hashval != 0)
213 /* We don't want to overwrite the old value. */
214 return -1;
215
216 /* An empty bucket has been found. */
217 insert_entry_2 (htab, hval, idx, data);
218 return 0;
219 }
220
221
222 #ifdef OVERWRITE
223 int
224 #define INSERT(name) _INSERT (name)
225 #define _INSERT(name) \
226 name##_overwrite
227 INSERT(NAME) (htab, hval, data)
228 NAME *htab;
229 unsigned long int hval;
230 TYPE data;
231 {
232 size_t idx;
233
234 /* Make the hash value nonzero. */
235 hval = hval ?: 1;
236
237 idx = lookup (htab, hval, data);
238
239 /* The correct bucket has been found. */
240 insert_entry_2 (htab, hval, idx, data);
241 return 0;
242 }
243 #endif
244
245
246 TYPE
247 #define FIND(name) _FIND (name)
248 #define _FIND(name) \
249 name##_find
250 FIND(NAME) (htab, hval, val)
251 NAME *htab;
252 unsigned long int hval;
253 TYPE val;
254 {
255 size_t idx;
256
257 /* Make the hash value nonzero. */
258 hval = hval ?: 1;
259
260 idx = lookup (htab, hval, val);
261
262 if (htab->table[idx].hashval == 0)
263 return NULL;
264
265 return htab->table[idx].data;
266 }
267
268
269 #ifdef ITERATE
270 # define ITERATEFCT(name) _ITERATEFCT (name)
271 # define _ITERATEFCT(name) \
272 name##_iterate
273 TYPE
274 ITERATEFCT(NAME) (htab, ptr)
275 NAME *htab;
276 void **ptr;
277 {
278 void *p = *ptr;
279
280 # define TYPENAME(name) _TYPENAME (name)
281 # define _TYPENAME(name) name##_ent
282
283 # ifdef REVERSE
284 if (p == NULL)
285 p = htab->first;
286 else
287 p = ((TYPENAME(NAME) *) p)->next;
288
289 if (p == NULL)
290 {
291 *ptr = NULL;
292 return NULL;
293 }
294 # else
295 if (p == NULL)
296 {
297 if (htab->first == NULL)
298 return NULL;
299 p = htab->first->next;
300 }
301 else
302 {
303 if (p == htab->first)
304 return NULL;
305
306 p = ((TYPENAME(NAME) *) p)->next;
307 }
308 # endif
309
310 /* Prepare the next element. If possible this will pull the data
311 into the cache, for reading. */
312 __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2);
313
314 return ((TYPENAME(NAME) *) (*ptr = p))->data;
315 }
316 #endif
317