1.5.1
by Matthias Klose
Import upstream version 4.3~rc1 |
1 |
/* hashlib.c -- functions to manage and access hash tables for bash. */
|
2 |
||
3 |
/* Copyright (C) 1987,1989,1991,1995,1998,2001,2003,2005,2006,2008,2009 Free Software Foundation, Inc.
|
|
4 |
||
5 |
This file is part of GNU Bash, the Bourne Again SHell.
|
|
6 |
||
7 |
Bash is free software: you can redistribute it and/or modify
|
|
8 |
it under the terms of the GNU General Public License as published by
|
|
9 |
the Free Software Foundation, either version 3 of the License, or
|
|
10 |
(at your option) any later version.
|
|
11 |
||
12 |
Bash is distributed in the hope that it will be useful,
|
|
13 |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
14 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
15 |
GNU General Public License for more details.
|
|
16 |
||
17 |
You should have received a copy of the GNU General Public License
|
|
18 |
along with Bash. If not, see <http://www.gnu.org/licenses/>.
|
|
19 |
*/
|
|
20 |
||
21 |
#include <config.h> |
|
22 |
||
23 |
#include "bashansi.h" |
|
24 |
||
25 |
#if defined (HAVE_UNISTD_H)
|
|
26 |
# ifdef _MINIX
|
|
27 |
# include <sys/types.h>
|
|
28 |
# endif
|
|
29 |
# include <unistd.h>
|
|
30 |
#endif
|
|
31 |
||
32 |
#include <stdio.h> |
|
33 |
||
34 |
#include "shell.h" |
|
35 |
#include "hashlib.h" |
|
36 |
||
37 |
/* Rely on properties of unsigned division (unsigned/int -> unsigned) and
|
|
38 |
don't discard the upper 32 bits of the value, if present. */
|
|
39 |
#define HASH_BUCKET(s, t, h) (((h) = hash_string (s)) & ((t)->nbuckets - 1))
|
|
40 |
||
41 |
static BUCKET_CONTENTS *copy_bucket_array __P((BUCKET_CONTENTS *, sh_string_func_t *)); |
|
42 |
||
43 |
/* Make a new hash table with BUCKETS number of buckets. Initialize
|
|
44 |
each slot in the table to NULL. */
|
|
45 |
HASH_TABLE * |
|
46 |
hash_create (buckets) |
|
47 |
int buckets; |
|
48 |
{
|
|
49 |
HASH_TABLE *new_table; |
|
50 |
register int i; |
|
51 |
||
52 |
new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE)); |
|
53 |
if (buckets == 0) |
|
54 |
buckets = DEFAULT_HASH_BUCKETS; |
|
55 |
||
56 |
new_table->bucket_array = |
|
57 |
(BUCKET_CONTENTS **)xmalloc (buckets * sizeof (BUCKET_CONTENTS *)); |
|
58 |
new_table->nbuckets = buckets; |
|
59 |
new_table->nentries = 0; |
|
60 |
||
61 |
for (i = 0; i < buckets; i++) |
|
62 |
new_table->bucket_array[i] = (BUCKET_CONTENTS *)NULL; |
|
63 |
||
64 |
return (new_table); |
|
65 |
}
|
|
66 |
||
67 |
int
|
|
68 |
hash_size (table) |
|
69 |
HASH_TABLE *table; |
|
70 |
{
|
|
71 |
return (HASH_ENTRIES(table)); |
|
72 |
}
|
|
73 |
||
74 |
static BUCKET_CONTENTS * |
|
75 |
copy_bucket_array (ba, cpdata) |
|
76 |
BUCKET_CONTENTS *ba; |
|
77 |
sh_string_func_t *cpdata; /* data copy function */ |
|
78 |
{
|
|
79 |
BUCKET_CONTENTS *new_bucket, *n, *e; |
|
80 |
||
81 |
if (ba == 0) |
|
82 |
return ((BUCKET_CONTENTS *)0); |
|
83 |
||
84 |
for (n = (BUCKET_CONTENTS *)0, e = ba; e; e = e->next) |
|
85 |
{
|
|
86 |
if (n == 0) |
|
87 |
{
|
|
88 |
new_bucket = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS)); |
|
89 |
n = new_bucket; |
|
90 |
}
|
|
91 |
else
|
|
92 |
{
|
|
93 |
n->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS)); |
|
94 |
n = n->next; |
|
95 |
}
|
|
96 |
||
97 |
n->key = savestring (e->key); |
|
98 |
n->data = e->data ? (cpdata ? (*cpdata) (e->data) : savestring (e->data)) |
|
99 |
: NULL; |
|
100 |
n->khash = e->khash; |
|
101 |
n->times_found = e->times_found; |
|
102 |
n->next = (BUCKET_CONTENTS *)NULL; |
|
103 |
}
|
|
104 |
||
105 |
return new_bucket; |
|
106 |
}
|
|
107 |
||
108 |
HASH_TABLE * |
|
109 |
hash_copy (table, cpdata) |
|
110 |
HASH_TABLE *table; |
|
111 |
sh_string_func_t *cpdata; |
|
112 |
{
|
|
113 |
HASH_TABLE *new_table; |
|
114 |
int i; |
|
115 |
||
116 |
if (table == 0) |
|
117 |
return ((HASH_TABLE *)NULL); |
|
118 |
||
119 |
new_table = hash_create (table->nbuckets); |
|
120 |
||
121 |
for (i = 0; i < table->nbuckets; i++) |
|
122 |
new_table->bucket_array[i] = copy_bucket_array (table->bucket_array[i], cpdata); |
|
123 |
||
124 |
new_table->nentries = table->nentries; |
|
125 |
return new_table; |
|
126 |
}
|
|
127 |
||
128 |
/* The `khash' check below requires that strings that compare equally with
|
|
129 |
strcmp hash to the same value. */
|
|
130 |
unsigned int |
|
131 |
hash_string (s) |
|
132 |
const char *s; |
|
133 |
{
|
|
134 |
register unsigned int i; |
|
135 |
||
136 |
/* This is the best string hash function I found.
|
|
137 |
||
138 |
The magic is in the interesting relationship between the special prime
|
|
139 |
16777619 (2^24 + 403) and 2^32 and 2^8. */
|
|
140 |
||
141 |
for (i = 0; *s; s++) |
|
142 |
{
|
|
143 |
i *= 16777619; |
|
144 |
i ^= *s; |
|
145 |
}
|
|
146 |
||
147 |
return i; |
|
148 |
}
|
|
149 |
||
150 |
/* Return the location of the bucket which should contain the data
|
|
151 |
for STRING. TABLE is a pointer to a HASH_TABLE. */
|
|
152 |
||
153 |
int
|
|
154 |
hash_bucket (string, table) |
|
155 |
const char *string; |
|
156 |
HASH_TABLE *table; |
|
157 |
{
|
|
158 |
unsigned int h; |
|
159 |
||
160 |
return (HASH_BUCKET (string, table, h)); |
|
161 |
}
|
|
162 |
||
163 |
/* Return a pointer to the hashed item. If the HASH_CREATE flag is passed,
|
|
164 |
create a new hash table entry for STRING, otherwise return NULL. */
|
|
165 |
BUCKET_CONTENTS * |
|
166 |
hash_search (string, table, flags) |
|
167 |
const char *string; |
|
168 |
HASH_TABLE *table; |
|
169 |
int flags; |
|
170 |
{
|
|
171 |
BUCKET_CONTENTS *list; |
|
172 |
int bucket; |
|
173 |
unsigned int hv; |
|
174 |
||
175 |
if (table == 0 || ((flags & HASH_CREATE) == 0 && HASH_ENTRIES (table) == 0)) |
|
176 |
return (BUCKET_CONTENTS *)NULL; |
|
177 |
||
178 |
bucket = HASH_BUCKET (string, table, hv); |
|
179 |
||
180 |
for (list = table->bucket_array ? table->bucket_array[bucket] : 0; list; list = list->next) |
|
181 |
{
|
|
182 |
if (hv == list->khash && STREQ (list->key, string)) |
|
183 |
{
|
|
184 |
list->times_found++; |
|
185 |
return (list); |
|
186 |
}
|
|
187 |
}
|
|
188 |
||
189 |
if (flags & HASH_CREATE) |
|
190 |
{
|
|
191 |
list = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS)); |
|
192 |
list->next = table->bucket_array[bucket]; |
|
193 |
table->bucket_array[bucket] = list; |
|
194 |
||
195 |
list->data = NULL; |
|
196 |
list->key = (char *)string; /* XXX fix later */ |
|
197 |
list->khash = hv; |
|
198 |
list->times_found = 0; |
|
199 |
||
200 |
table->nentries++; |
|
201 |
return (list); |
|
202 |
}
|
|
203 |
||
204 |
return (BUCKET_CONTENTS *)NULL; |
|
205 |
}
|
|
206 |
||
207 |
/* Remove the item specified by STRING from the hash table TABLE.
|
|
208 |
The item removed is returned, so you can free its contents. If
|
|
209 |
the item isn't in this table NULL is returned. */
|
|
210 |
BUCKET_CONTENTS * |
|
211 |
hash_remove (string, table, flags) |
|
212 |
const char *string; |
|
213 |
HASH_TABLE *table; |
|
214 |
int flags; |
|
215 |
{
|
|
216 |
int bucket; |
|
217 |
BUCKET_CONTENTS *prev, *temp; |
|
218 |
unsigned int hv; |
|
219 |
||
220 |
if (table == 0 || HASH_ENTRIES (table) == 0) |
|
221 |
return (BUCKET_CONTENTS *)NULL; |
|
222 |
||
223 |
bucket = HASH_BUCKET (string, table, hv); |
|
224 |
prev = (BUCKET_CONTENTS *)NULL; |
|
225 |
for (temp = table->bucket_array[bucket]; temp; temp = temp->next) |
|
226 |
{
|
|
227 |
if (hv == temp->khash && STREQ (temp->key, string)) |
|
228 |
{
|
|
229 |
if (prev) |
|
230 |
prev->next = temp->next; |
|
231 |
else
|
|
232 |
table->bucket_array[bucket] = temp->next; |
|
233 |
||
234 |
table->nentries--; |
|
235 |
return (temp); |
|
236 |
}
|
|
237 |
prev = temp; |
|
238 |
}
|
|
239 |
return ((BUCKET_CONTENTS *) NULL); |
|
240 |
}
|
|
241 |
||
242 |
/* Create an entry for STRING, in TABLE. If the entry already
|
|
243 |
exists, then return it (unless the HASH_NOSRCH flag is set). */
|
|
244 |
BUCKET_CONTENTS * |
|
245 |
hash_insert (string, table, flags) |
|
246 |
char *string; |
|
247 |
HASH_TABLE *table; |
|
248 |
int flags; |
|
249 |
{
|
|
250 |
BUCKET_CONTENTS *item; |
|
251 |
int bucket; |
|
252 |
unsigned int hv; |
|
253 |
||
254 |
if (table == 0) |
|
255 |
table = hash_create (0); |
|
256 |
||
257 |
item = (flags & HASH_NOSRCH) ? (BUCKET_CONTENTS *)NULL |
|
258 |
: hash_search (string, table, 0); |
|
259 |
||
260 |
if (item == 0) |
|
261 |
{
|
|
262 |
bucket = HASH_BUCKET (string, table, hv); |
|
263 |
||
264 |
item = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS)); |
|
265 |
item->next = table->bucket_array[bucket]; |
|
266 |
table->bucket_array[bucket] = item; |
|
267 |
||
268 |
item->data = NULL; |
|
269 |
item->key = string; |
|
270 |
item->khash = hv; |
|
271 |
item->times_found = 0; |
|
272 |
||
273 |
table->nentries++; |
|
274 |
}
|
|
275 |
||
276 |
return (item); |
|
277 |
}
|
|
278 |
||
279 |
/* Remove and discard all entries in TABLE. If FREE_DATA is non-null, it
|
|
280 |
is a function to call to dispose of a hash item's data. Otherwise,
|
|
281 |
free() is called. */
|
|
282 |
void
|
|
283 |
hash_flush (table, free_data) |
|
284 |
HASH_TABLE *table; |
|
285 |
sh_free_func_t *free_data; |
|
286 |
{
|
|
287 |
int i; |
|
288 |
register BUCKET_CONTENTS *bucket, *item; |
|
289 |
||
290 |
if (table == 0 || HASH_ENTRIES (table) == 0) |
|
291 |
return; |
|
292 |
||
293 |
for (i = 0; i < table->nbuckets; i++) |
|
294 |
{
|
|
295 |
bucket = table->bucket_array[i]; |
|
296 |
||
297 |
while (bucket) |
|
298 |
{
|
|
299 |
item = bucket; |
|
300 |
bucket = bucket->next; |
|
301 |
||
302 |
if (free_data) |
|
303 |
(*free_data) (item->data); |
|
304 |
else
|
|
305 |
free (item->data); |
|
306 |
free (item->key); |
|
307 |
free (item); |
|
308 |
}
|
|
309 |
table->bucket_array[i] = (BUCKET_CONTENTS *)NULL; |
|
310 |
}
|
|
311 |
||
312 |
table->nentries = 0; |
|
313 |
}
|
|
314 |
||
315 |
/* Free the hash table pointed to by TABLE. */
|
|
316 |
void
|
|
317 |
hash_dispose (table) |
|
318 |
HASH_TABLE *table; |
|
319 |
{
|
|
320 |
free (table->bucket_array); |
|
321 |
free (table); |
|
322 |
}
|
|
323 |
||
324 |
void
|
|
325 |
hash_walk (table, func) |
|
326 |
HASH_TABLE *table; |
|
327 |
hash_wfunc *func; |
|
328 |
{
|
|
329 |
register int i; |
|
330 |
BUCKET_CONTENTS *item; |
|
331 |
||
332 |
if (table == 0 || HASH_ENTRIES (table) == 0) |
|
333 |
return; |
|
334 |
||
335 |
for (i = 0; i < table->nbuckets; i++) |
|
336 |
{
|
|
337 |
for (item = hash_items (i, table); item; item = item->next) |
|
338 |
if ((*func) (item) < 0) |
|
339 |
return; |
|
340 |
}
|
|
341 |
}
|
|
342 |
||
343 |
#if defined (DEBUG) || defined (TEST_HASHING)
|
|
344 |
void
|
|
345 |
hash_pstats (table, name) |
|
346 |
HASH_TABLE *table; |
|
347 |
char *name; |
|
348 |
{
|
|
349 |
register int slot, bcount; |
|
350 |
register BUCKET_CONTENTS *bc; |
|
351 |
||
352 |
if (name == 0) |
|
353 |
name = "unknown hash table"; |
|
354 |
||
355 |
fprintf (stderr, "%s: %d buckets; %d items\n", name, table->nbuckets, table->nentries); |
|
356 |
||
357 |
/* Print out a count of how many strings hashed to each bucket, so we can
|
|
358 |
see how even the distribution is. */
|
|
359 |
for (slot = 0; slot < table->nbuckets; slot++) |
|
360 |
{
|
|
361 |
bc = hash_items (slot, table); |
|
362 |
||
363 |
fprintf (stderr, "\tslot %3d: ", slot); |
|
364 |
for (bcount = 0; bc; bc = bc->next) |
|
365 |
bcount++; |
|
366 |
||
367 |
fprintf (stderr, "%d\n", bcount); |
|
368 |
}
|
|
369 |
}
|
|
370 |
#endif
|
|
371 |
||
372 |
#ifdef TEST_HASHING
|
|
373 |
||
374 |
/* link with xmalloc.o and lib/malloc/libmalloc.a */
|
|
375 |
#undef NULL
|
|
376 |
#include <stdio.h> |
|
377 |
||
378 |
#ifndef NULL
|
|
379 |
#define NULL 0
|
|
380 |
#endif
|
|
381 |
||
382 |
HASH_TABLE *table, *ntable; |
|
383 |
||
384 |
int interrupt_immediately = 0; |
|
385 |
||
386 |
int
|
|
387 |
signal_is_trapped (s) |
|
388 |
int s; |
|
389 |
{
|
|
390 |
return (0); |
|
391 |
}
|
|
392 |
||
393 |
void
|
|
394 |
programming_error (const char *format, ...) |
|
395 |
{
|
|
396 |
abort(); |
|
397 |
}
|
|
398 |
||
399 |
void
|
|
400 |
fatal_error (const char *format, ...) |
|
401 |
{
|
|
402 |
abort(); |
|
403 |
}
|
|
404 |
||
405 |
main () |
|
406 |
{
|
|
407 |
char string[256]; |
|
408 |
int count = 0; |
|
409 |
BUCKET_CONTENTS *tt; |
|
410 |
||
411 |
table = hash_create (0); |
|
412 |
||
413 |
for (;;) |
|
414 |
{
|
|
415 |
char *temp_string; |
|
416 |
if (fgets (string, sizeof (string), stdin) == 0) |
|
417 |
break; |
|
418 |
if (!*string) |
|
419 |
break; |
|
420 |
temp_string = savestring (string); |
|
421 |
tt = hash_insert (temp_string, table, 0); |
|
422 |
if (tt->times_found) |
|
423 |
{
|
|
424 |
fprintf (stderr, "You have already added item `%s'\n", string); |
|
425 |
free (temp_string); |
|
426 |
}
|
|
427 |
else
|
|
428 |
{
|
|
429 |
count++; |
|
430 |
}
|
|
431 |
}
|
|
432 |
||
433 |
hash_pstats (table, "hash test"); |
|
434 |
||
435 |
ntable = hash_copy (table, (sh_string_func_t *)NULL); |
|
436 |
hash_flush (table, (sh_free_func_t *)NULL); |
|
437 |
hash_pstats (ntable, "hash copy test"); |
|
438 |
||
439 |
exit (0); |
|
440 |
}
|
|
441 |
||
442 |
#endif /* TEST_HASHING */ |