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.
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.
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.
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. */
27 #include <sys/types.h>
39 #include "simple-hash.h"
41 #define obstack_chunk_alloc malloc
42 #define obstack_chunk_free free
45 # define BITSPERBYTE 8
49 # define LONGBITS (sizeof (long) * BITSPERBYTE)
53 # define bcopy(s, d, n) memcpy ((d), (s), (n))
56 extern void *xmalloc (size_t __n
);
57 extern void *xcalloc (size_t __n
, size_t __m
);
59 typedef struct hash_entry
65 struct hash_entry
*next
;
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
);
81 init_hash (htab
, init_size
)
83 unsigned long int init_size
;
85 /* We need the size to be a prime. */
86 init_size
= next_prime (init_size
);
88 /* Initialize the data structure. */
89 htab
->size
= init_size
;
92 htab
->table
= (void *) xcalloc (init_size
+ 1, sizeof (hash_entry
));
93 if (htab
->table
== NULL
)
96 obstack_init (&htab
->mem_pool
);
107 obstack_free (&htab
->mem_pool
, NULL
);
113 insert_entry (htab
, key
, keylen
, data
)
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
);
124 /* We don't want to overwrite the old value. */
128 /* An empty bucket has been found. */
129 insert_entry_2 (htab
, obstack_copy (&htab
->mem_pool
, key
, keylen
),
130 keylen
, hval
, idx
, data
);
136 insert_entry_2 (htab
, key
, keylen
, hval
, idx
, data
)
140 unsigned long int hval
;
144 hash_entry
*table
= (hash_entry
*) htab
->table
;
146 table
[idx
].used
= hval
;
147 table
[idx
].key
= key
;
148 table
[idx
].keylen
= keylen
;
149 table
[idx
].data
= data
;
151 /* List the new value in the list. */
152 if ((hash_entry
*) htab
->first
== NULL
)
154 table
[idx
].next
= &table
[idx
];
155 *(hash_entry
**) &htab
->first
= &table
[idx
];
159 table
[idx
].next
= ((hash_entry
*) htab
->first
)->next
;
160 ((hash_entry
*) htab
->first
)->next
= &table
[idx
];
161 *(hash_entry
**) &htab
->first
= &table
[idx
];
165 if (100 * htab
->filled
> 90 * htab
->size
)
167 /* Table is filled more than 90%. Resize the table. */
168 unsigned long int old_size
= htab
->size
;
170 htab
->size
= next_prime (htab
->size
* 2);
173 htab
->table
= (void *) xcalloc (1 + htab
->size
, sizeof (hash_entry
));
175 for (idx
= 1; idx
<= old_size
; ++idx
)
177 insert_entry_2 (htab
, table
[idx
].key
, table
[idx
].keylen
,
179 lookup_2 (htab
, table
[idx
].key
, table
[idx
].keylen
,
189 find_entry (htab
, key
, keylen
, result
)
195 hash_entry
*table
= (hash_entry
*) htab
->table
;
196 size_t idx
= lookup (htab
, key
, keylen
, compute_hashval (key
, keylen
));
198 if (table
[idx
].used
== 0)
201 *result
= table
[idx
].data
;
207 set_entry (htab
, key
, keylen
, newval
)
213 hash_entry
*table
= (hash_entry
*) htab
->table
;
214 size_t idx
= lookup (htab
, key
, keylen
, compute_hashval (key
, keylen
));
216 if (table
[idx
].used
== 0)
219 table
[idx
].data
= newval
;
225 iterate_table (htab
, ptr
, key
, keylen
, data
)
234 if (htab
->first
== NULL
)
236 *ptr
= (void *) ((hash_entry
*) htab
->first
)->next
;
240 if (*ptr
== htab
->first
)
242 *ptr
= (void *) (((hash_entry
*) *ptr
)->next
);
245 *key
= ((hash_entry
*) *ptr
)->key
;
246 *keylen
= ((hash_entry
*) *ptr
)->keylen
;
247 *data
= ((hash_entry
*) *ptr
)->data
;
253 lookup (htab
, key
, keylen
, hval
)
261 hash_entry
*table
= (hash_entry
*) htab
->table
;
263 /* First hash function: simply take the modul but prevent zero. */
264 hash
= 1 + hval
% htab
->size
;
270 if (table
[idx
].used
== hval
&& table
[idx
].keylen
== keylen
271 && memcmp (key
, table
[idx
].key
, keylen
) == 0)
274 /* Second hash function as suggested in [Knuth]. */
275 hash
= 1 + hval
% (htab
->size
- 2);
280 idx
= htab
->size
+ idx
- hash
;
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)
289 while (table
[idx
].used
);
296 [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
297 [Knuth] The Art of Computer Programming, part3 (6.4) */
300 lookup_2 (htab
, key
, keylen
, hval
)
304 unsigned long int hval
;
306 unsigned long int hash
;
308 hash_entry
*table
= (hash_entry
*) htab
->table
;
310 /* First hash function: simply take the modul but prevent zero. */
311 hash
= 1 + hval
% htab
->size
;
317 if (table
[idx
].used
== hval
&& table
[idx
].keylen
== keylen
318 && memcmp (table
[idx
].key
, key
, keylen
) == 0)
321 /* Second hash function as suggested in [Knuth]. */
322 hash
= 1 + hval
% (htab
->size
- 2);
327 idx
= htab
->size
+ idx
- hash
;
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)
336 while (table
[idx
].used
);
343 compute_hashval (key
, keylen
)
348 unsigned long int hval
, g
;
350 /* Compute the hash value for the given string. The algorithm
351 is taken from [Aho,Sethi,Ullman]. */
357 hval
+= (unsigned long int) *(((char *) key
) + cnt
++);
358 g
= hval
& ((unsigned long) 0xf << (LONGBITS
- 4));
361 hval
^= g
>> (LONGBITS
- 8);
365 return hval
!= 0 ? hval
: ~((unsigned long) 0);
371 unsigned long int seed
;
373 /* Make it definitely odd. */
376 while (!is_prime (seed
))
385 unsigned long int candidate
;
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
;
391 while (sq
< candidate
&& candidate
% divn
!= 0)
398 return candidate
% divn
!= 0;