1 /* Implement simple hashing table with string based keys.
2 Copyright (C) 1994-2016 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 as published
8 by the Free Software Foundation; version 2 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, see <http://www.gnu.org/licenses/>. */
28 #include <sys/types.h>
36 #include "simple-hash.h"
38 #define obstack_chunk_alloc malloc
39 #define obstack_chunk_free free
42 # define BITSPERBYTE 8
45 #define hashval_t uint32_t
48 #include <programs/xmalloc.h>
50 typedef struct hash_entry
56 struct hash_entry
*next
;
60 /* Prototypes for local functions. */
61 static void insert_entry_2 (hash_table
*htab
, const void *key
, size_t keylen
,
62 unsigned long hval
, size_t idx
, void *data
);
63 static size_t lookup (const hash_table
*htab
, const void *key
, size_t keylen
,
64 unsigned long int hval
);
65 static int is_prime (unsigned long int candidate
);
69 init_hash (hash_table
*htab
, unsigned long int init_size
)
71 /* We need the size to be a prime. */
72 init_size
= next_prime (init_size
);
74 /* Initialize the data structure. */
75 htab
->size
= init_size
;
78 htab
->table
= (void *) xcalloc (init_size
+ 1, sizeof (hash_entry
));
79 if (htab
->table
== NULL
)
82 obstack_init (&htab
->mem_pool
);
89 delete_hash (hash_table
*htab
)
92 obstack_free (&htab
->mem_pool
, NULL
);
98 insert_entry (hash_table
*htab
, const void *key
, size_t keylen
, void *data
)
100 unsigned long int hval
= compute_hashval (key
, keylen
);
101 hash_entry
*table
= (hash_entry
*) htab
->table
;
102 size_t idx
= lookup (htab
, key
, keylen
, hval
);
105 /* We don't want to overwrite the old value. */
109 /* An empty bucket has been found. */
110 insert_entry_2 (htab
, obstack_copy (&htab
->mem_pool
, key
, keylen
),
111 keylen
, hval
, idx
, data
);
117 insert_entry_2 (hash_table
*htab
, const void *key
, size_t keylen
,
118 unsigned long int hval
, size_t idx
, void *data
)
120 hash_entry
*table
= (hash_entry
*) htab
->table
;
122 table
[idx
].used
= hval
;
123 table
[idx
].key
= key
;
124 table
[idx
].keylen
= keylen
;
125 table
[idx
].data
= data
;
127 /* List the new value in the list. */
128 if ((hash_entry
*) htab
->first
== NULL
)
130 table
[idx
].next
= &table
[idx
];
131 htab
->first
= &table
[idx
];
135 table
[idx
].next
= ((hash_entry
*) htab
->first
)->next
;
136 ((hash_entry
*) htab
->first
)->next
= &table
[idx
];
137 htab
->first
= &table
[idx
];
141 if (100 * htab
->filled
> 75 * htab
->size
)
143 /* Table is filled more than 75%. Resize the table.
144 Experiments have shown that for best performance, this threshold
145 must lie between 40% and 85%. */
146 unsigned long int old_size
= htab
->size
;
148 htab
->size
= next_prime (htab
->size
* 2);
151 htab
->table
= (void *) xcalloc (1 + htab
->size
, sizeof (hash_entry
));
153 for (idx
= 1; idx
<= old_size
; ++idx
)
155 insert_entry_2 (htab
, table
[idx
].key
, table
[idx
].keylen
,
157 lookup (htab
, table
[idx
].key
, table
[idx
].keylen
,
167 find_entry (const hash_table
*htab
, const void *key
, size_t keylen
,
170 hash_entry
*table
= (hash_entry
*) htab
->table
;
171 size_t idx
= lookup (htab
, key
, keylen
, compute_hashval (key
, keylen
));
173 if (table
[idx
].used
== 0)
176 *result
= table
[idx
].data
;
182 set_entry (hash_table
*htab
, const void *key
, size_t keylen
, void *newval
)
184 hash_entry
*table
= (hash_entry
*) htab
->table
;
185 size_t idx
= lookup (htab
, key
, keylen
, compute_hashval (key
, keylen
));
187 if (table
[idx
].used
== 0)
190 table
[idx
].data
= newval
;
196 iterate_table (const hash_table
*htab
, void **ptr
, const void **key
,
197 size_t *keylen
, void **data
)
201 if (htab
->first
== NULL
)
203 *ptr
= (void *) ((hash_entry
*) htab
->first
)->next
;
207 if (*ptr
== htab
->first
)
209 *ptr
= (void *) (((hash_entry
*) *ptr
)->next
);
212 *key
= ((hash_entry
*) *ptr
)->key
;
213 *keylen
= ((hash_entry
*) *ptr
)->keylen
;
214 *data
= ((hash_entry
*) *ptr
)->data
;
220 [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
221 [Knuth] The Art of Computer Programming, part3 (6.4) */
224 lookup (const hash_table
*htab
, const void *key
, size_t keylen
,
225 unsigned long int hval
)
227 unsigned long int hash
;
229 hash_entry
*table
= (hash_entry
*) htab
->table
;
231 /* First hash function: simply take the modul but prevent zero. */
232 hash
= 1 + hval
% htab
->size
;
238 if (table
[idx
].used
== hval
&& table
[idx
].keylen
== keylen
239 && memcmp (table
[idx
].key
, key
, keylen
) == 0)
242 /* Second hash function as suggested in [Knuth]. */
243 hash
= 1 + hval
% (htab
->size
- 2);
248 idx
= htab
->size
+ idx
- hash
;
252 /* If entry is found use it. */
253 if (table
[idx
].used
== hval
&& table
[idx
].keylen
== keylen
254 && memcmp (table
[idx
].key
, key
, keylen
) == 0)
257 while (table
[idx
].used
);
264 next_prime (unsigned long int seed
)
266 /* Make it definitely odd. */
269 while (!is_prime (seed
))
277 is_prime (unsigned long int candidate
)
279 /* No even number and none less than 10 will be passed here. */
280 unsigned long int divn
= 3;
281 unsigned long int sq
= divn
* divn
;
283 while (sq
< candidate
&& candidate
% divn
!= 0)
290 return candidate
% divn
!= 0;