1 /* Implement simple hashing table with string based keys.
2 Copyright (C) 1994-1997,2000,2001,2002,2005 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, October 1994.
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License version 2 as
8 published by the Free Software Foundation.
10 This program 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
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software Foundation,
17 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
26 #include <sys/types.h>
38 #include "simple-hash.h"
40 #define obstack_chunk_alloc malloc
41 #define obstack_chunk_free free
44 # define BITSPERBYTE 8
48 # define bcopy(s, d, n) memcpy ((d), (s), (n))
53 extern void *xmalloc (size_t __n
);
54 extern void *xcalloc (size_t __n
, size_t __m
);
56 typedef struct hash_entry
62 struct hash_entry
*next
;
66 /* Prototypes for local functions. */
67 static void insert_entry_2 (hash_table
*htab
, const void *key
, size_t keylen
,
68 unsigned long hval
, size_t idx
, void *data
);
69 static size_t lookup (const hash_table
*htab
, const void *key
, size_t keylen
,
70 unsigned long int hval
);
71 static int is_prime (unsigned long int candidate
);
75 init_hash (htab
, init_size
)
77 unsigned long int init_size
;
79 /* We need the size to be a prime. */
80 init_size
= next_prime (init_size
);
82 /* Initialize the data structure. */
83 htab
->size
= init_size
;
86 htab
->table
= (void *) xcalloc (init_size
+ 1, sizeof (hash_entry
));
87 if (htab
->table
== NULL
)
90 obstack_init (&htab
->mem_pool
);
101 obstack_free (&htab
->mem_pool
, NULL
);
107 insert_entry (htab
, key
, keylen
, data
)
113 unsigned long int hval
= compute_hashval (key
, keylen
);
114 hash_entry
*table
= (hash_entry
*) htab
->table
;
115 size_t idx
= lookup (htab
, key
, keylen
, hval
);
118 /* We don't want to overwrite the old value. */
122 /* An empty bucket has been found. */
123 insert_entry_2 (htab
, obstack_copy (&htab
->mem_pool
, key
, keylen
),
124 keylen
, hval
, idx
, data
);
130 insert_entry_2 (htab
, key
, keylen
, hval
, idx
, data
)
134 unsigned long int hval
;
138 hash_entry
*table
= (hash_entry
*) htab
->table
;
140 table
[idx
].used
= hval
;
141 table
[idx
].key
= key
;
142 table
[idx
].keylen
= keylen
;
143 table
[idx
].data
= data
;
145 /* List the new value in the list. */
146 if ((hash_entry
*) htab
->first
== NULL
)
148 table
[idx
].next
= &table
[idx
];
149 htab
->first
= &table
[idx
];
153 table
[idx
].next
= ((hash_entry
*) htab
->first
)->next
;
154 ((hash_entry
*) htab
->first
)->next
= &table
[idx
];
155 htab
->first
= &table
[idx
];
159 if (100 * htab
->filled
> 75 * htab
->size
)
161 /* Table is filled more than 75%. Resize the table.
162 Experiments have shown that for best performance, this threshold
163 must lie between 40% and 85%. */
164 unsigned long int old_size
= htab
->size
;
166 htab
->size
= next_prime (htab
->size
* 2);
169 htab
->table
= (void *) xcalloc (1 + htab
->size
, sizeof (hash_entry
));
171 for (idx
= 1; idx
<= old_size
; ++idx
)
173 insert_entry_2 (htab
, table
[idx
].key
, table
[idx
].keylen
,
175 lookup (htab
, table
[idx
].key
, table
[idx
].keylen
,
185 find_entry (htab
, key
, keylen
, result
)
186 const hash_table
*htab
;
191 hash_entry
*table
= (hash_entry
*) htab
->table
;
192 size_t idx
= lookup (htab
, key
, keylen
, compute_hashval (key
, keylen
));
194 if (table
[idx
].used
== 0)
197 *result
= table
[idx
].data
;
203 set_entry (htab
, key
, keylen
, newval
)
209 hash_entry
*table
= (hash_entry
*) htab
->table
;
210 size_t idx
= lookup (htab
, key
, keylen
, compute_hashval (key
, keylen
));
212 if (table
[idx
].used
== 0)
215 table
[idx
].data
= newval
;
221 iterate_table (htab
, ptr
, key
, keylen
, data
)
222 const hash_table
*htab
;
230 if (htab
->first
== NULL
)
232 *ptr
= (void *) ((hash_entry
*) htab
->first
)->next
;
236 if (*ptr
== htab
->first
)
238 *ptr
= (void *) (((hash_entry
*) *ptr
)->next
);
241 *key
= ((hash_entry
*) *ptr
)->key
;
242 *keylen
= ((hash_entry
*) *ptr
)->keylen
;
243 *data
= ((hash_entry
*) *ptr
)->data
;
249 [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
250 [Knuth] The Art of Computer Programming, part3 (6.4) */
253 lookup (htab
, key
, keylen
, hval
)
254 const hash_table
*htab
;
257 unsigned long int hval
;
259 unsigned long int hash
;
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 (table
[idx
].key
, 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 (table
[idx
].key
, key
, keylen
) == 0)
289 while (table
[idx
].used
);
297 unsigned long int seed
;
299 /* Make it definitely odd. */
302 while (!is_prime (seed
))
311 unsigned long int candidate
;
313 /* No even number and none less than 10 will be passed here. */
314 unsigned long int divn
= 3;
315 unsigned long int sq
= divn
* divn
;
317 while (sq
< candidate
&& candidate
% divn
!= 0)
324 return candidate
% divn
!= 0;