]>
Commit | Line | Data |
---|---|---|
ccc6cda3 | 1 | /* hashlib.c -- functions to manage and access hash tables for bash. */ |
726f6388 | 2 | |
3185942a | 3 | /* Copyright (C) 1987,1989,1991,1995,1998,2001,2003,2005,2006,2008,2009 Free Software Foundation, Inc. |
726f6388 | 4 | |
3185942a | 5 | This file is part of GNU Bash, the Bourne Again SHell. |
726f6388 | 6 | |
3185942a JA |
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. | |
726f6388 | 11 | |
3185942a JA |
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. | |
726f6388 | 16 | |
3185942a JA |
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 | */ | |
726f6388 | 20 | |
bb70624e | 21 | #include <config.h> |
726f6388 | 22 | |
d166f048 | 23 | #include "bashansi.h" |
726f6388 | 24 | |
ccc6cda3 | 25 | #if defined (HAVE_UNISTD_H) |
cce855bc JA |
26 | # ifdef _MINIX |
27 | # include <sys/types.h> | |
28 | # endif | |
ccc6cda3 JA |
29 | # include <unistd.h> |
30 | #endif | |
726f6388 | 31 | |
d166f048 JA |
32 | #include <stdio.h> |
33 | ||
ccc6cda3 JA |
34 | #include "shell.h" |
35 | #include "hashlib.h" | |
726f6388 | 36 | |
7117c2d2 JA |
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)) | |
f73dda09 | 40 | |
7117c2d2 | 41 | static BUCKET_CONTENTS *copy_bucket_array __P((BUCKET_CONTENTS *, sh_string_func_t *)); |
726f6388 JA |
42 | |
43 | /* Make a new hash table with BUCKETS number of buckets. Initialize | |
44 | each slot in the table to NULL. */ | |
45 | HASH_TABLE * | |
7117c2d2 | 46 | hash_create (buckets) |
726f6388 JA |
47 | int buckets; |
48 | { | |
ccc6cda3 | 49 | HASH_TABLE *new_table; |
7117c2d2 | 50 | register int i; |
726f6388 | 51 | |
ccc6cda3 | 52 | new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE)); |
726f6388 JA |
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; | |
7117c2d2 JA |
60 | |
61 | for (i = 0; i < buckets; i++) | |
62 | new_table->bucket_array[i] = (BUCKET_CONTENTS *)NULL; | |
63 | ||
726f6388 JA |
64 | return (new_table); |
65 | } | |
66 | ||
f73dda09 | 67 | int |
7117c2d2 | 68 | hash_size (table) |
f73dda09 JA |
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)) | |
7117c2d2 JA |
99 | : NULL; |
100 | n->khash = e->khash; | |
f73dda09 JA |
101 | n->times_found = e->times_found; |
102 | n->next = (BUCKET_CONTENTS *)NULL; | |
103 | } | |
104 | ||
105 | return new_bucket; | |
106 | } | |
107 | ||
108 | HASH_TABLE * | |
7117c2d2 | 109 | hash_copy (table, cpdata) |
f73dda09 JA |
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 | ||
7117c2d2 | 119 | new_table = hash_create (table->nbuckets); |
f73dda09 JA |
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 | ||
d233b485 CR |
128 | /* This is the best 32-bit string hash function I found. It's one of the |
129 | Fowler-Noll-Vo family (FNV-1). | |
130 | ||
131 | The magic is in the interesting relationship between the special prime | |
132 | 16777619 (2^24 + 403) and 2^32 and 2^8. */ | |
133 | ||
134 | #define FNV_OFFSET 2166136261 | |
135 | #define FNV_PRIME 16777619 | |
136 | ||
137 | /* If you want to use 64 bits, use | |
138 | FNV_OFFSET 14695981039346656037 | |
139 | FNV_PRIMT 1099511628211 | |
140 | */ | |
141 | ||
7117c2d2 JA |
142 | /* The `khash' check below requires that strings that compare equally with |
143 | strcmp hash to the same value. */ | |
144 | unsigned int | |
145 | hash_string (s) | |
146 | const char *s; | |
147 | { | |
148 | register unsigned int i; | |
726f6388 | 149 | |
d233b485 | 150 | for (i = FNV_OFFSET; *s; s++) |
7117c2d2 | 151 | { |
d233b485 | 152 | i *= FNV_PRIME; |
7117c2d2 JA |
153 | i ^= *s; |
154 | } | |
155 | ||
156 | return i; | |
157 | } | |
158 | ||
159 | /* Return the location of the bucket which should contain the data | |
160 | for STRING. TABLE is a pointer to a HASH_TABLE. */ | |
726f6388 JA |
161 | |
162 | int | |
7117c2d2 | 163 | hash_bucket (string, table) |
f73dda09 | 164 | const char *string; |
726f6388 JA |
165 | HASH_TABLE *table; |
166 | { | |
7117c2d2 | 167 | unsigned int h; |
726f6388 | 168 | |
7117c2d2 | 169 | return (HASH_BUCKET (string, table, h)); |
726f6388 JA |
170 | } |
171 | ||
7117c2d2 JA |
172 | /* Return a pointer to the hashed item. If the HASH_CREATE flag is passed, |
173 | create a new hash table entry for STRING, otherwise return NULL. */ | |
726f6388 | 174 | BUCKET_CONTENTS * |
7117c2d2 | 175 | hash_search (string, table, flags) |
f73dda09 | 176 | const char *string; |
726f6388 | 177 | HASH_TABLE *table; |
7117c2d2 | 178 | int flags; |
726f6388 JA |
179 | { |
180 | BUCKET_CONTENTS *list; | |
7117c2d2 JA |
181 | int bucket; |
182 | unsigned int hv; | |
726f6388 | 183 | |
7117c2d2 | 184 | if (table == 0 || ((flags & HASH_CREATE) == 0 && HASH_ENTRIES (table) == 0)) |
726f6388 JA |
185 | return (BUCKET_CONTENTS *)NULL; |
186 | ||
7117c2d2 | 187 | bucket = HASH_BUCKET (string, table, hv); |
726f6388 | 188 | |
0001803f | 189 | for (list = table->bucket_array ? table->bucket_array[bucket] : 0; list; list = list->next) |
726f6388 | 190 | { |
a0c0a00f | 191 | /* This is the comparison function */ |
7117c2d2 | 192 | if (hv == list->khash && STREQ (list->key, string)) |
726f6388 JA |
193 | { |
194 | list->times_found++; | |
195 | return (list); | |
196 | } | |
726f6388 | 197 | } |
7117c2d2 JA |
198 | |
199 | if (flags & HASH_CREATE) | |
200 | { | |
201 | list = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS)); | |
202 | list->next = table->bucket_array[bucket]; | |
203 | table->bucket_array[bucket] = list; | |
204 | ||
205 | list->data = NULL; | |
206 | list->key = (char *)string; /* XXX fix later */ | |
207 | list->khash = hv; | |
208 | list->times_found = 0; | |
209 | ||
210 | table->nentries++; | |
211 | return (list); | |
212 | } | |
213 | ||
726f6388 JA |
214 | return (BUCKET_CONTENTS *)NULL; |
215 | } | |
216 | ||
217 | /* Remove the item specified by STRING from the hash table TABLE. | |
218 | The item removed is returned, so you can free its contents. If | |
219 | the item isn't in this table NULL is returned. */ | |
220 | BUCKET_CONTENTS * | |
7117c2d2 | 221 | hash_remove (string, table, flags) |
f73dda09 | 222 | const char *string; |
726f6388 | 223 | HASH_TABLE *table; |
7117c2d2 | 224 | int flags; |
726f6388 | 225 | { |
7117c2d2 | 226 | int bucket; |
726f6388 | 227 | BUCKET_CONTENTS *prev, *temp; |
7117c2d2 | 228 | unsigned int hv; |
726f6388 | 229 | |
7117c2d2 | 230 | if (table == 0 || HASH_ENTRIES (table) == 0) |
726f6388 JA |
231 | return (BUCKET_CONTENTS *)NULL; |
232 | ||
7117c2d2 | 233 | bucket = HASH_BUCKET (string, table, hv); |
726f6388 | 234 | prev = (BUCKET_CONTENTS *)NULL; |
7117c2d2 | 235 | for (temp = table->bucket_array[bucket]; temp; temp = temp->next) |
726f6388 | 236 | { |
7117c2d2 | 237 | if (hv == temp->khash && STREQ (temp->key, string)) |
726f6388 JA |
238 | { |
239 | if (prev) | |
240 | prev->next = temp->next; | |
241 | else | |
7117c2d2 | 242 | table->bucket_array[bucket] = temp->next; |
726f6388 JA |
243 | |
244 | table->nentries--; | |
245 | return (temp); | |
246 | } | |
247 | prev = temp; | |
726f6388 JA |
248 | } |
249 | return ((BUCKET_CONTENTS *) NULL); | |
250 | } | |
251 | ||
252 | /* Create an entry for STRING, in TABLE. If the entry already | |
7117c2d2 | 253 | exists, then return it (unless the HASH_NOSRCH flag is set). */ |
726f6388 | 254 | BUCKET_CONTENTS * |
7117c2d2 | 255 | hash_insert (string, table, flags) |
726f6388 JA |
256 | char *string; |
257 | HASH_TABLE *table; | |
7117c2d2 | 258 | int flags; |
726f6388 JA |
259 | { |
260 | BUCKET_CONTENTS *item; | |
ccc6cda3 | 261 | int bucket; |
7117c2d2 | 262 | unsigned int hv; |
726f6388 | 263 | |
ccc6cda3 | 264 | if (table == 0) |
7117c2d2 | 265 | table = hash_create (0); |
726f6388 | 266 | |
7117c2d2 JA |
267 | item = (flags & HASH_NOSRCH) ? (BUCKET_CONTENTS *)NULL |
268 | : hash_search (string, table, 0); | |
269 | ||
270 | if (item == 0) | |
726f6388 | 271 | { |
7117c2d2 | 272 | bucket = HASH_BUCKET (string, table, hv); |
726f6388 | 273 | |
7117c2d2 JA |
274 | item = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS)); |
275 | item->next = table->bucket_array[bucket]; | |
276 | table->bucket_array[bucket] = item; | |
726f6388 | 277 | |
7117c2d2 | 278 | item->data = NULL; |
726f6388 | 279 | item->key = string; |
7117c2d2 | 280 | item->khash = hv; |
726f6388 | 281 | item->times_found = 0; |
7117c2d2 JA |
282 | |
283 | table->nentries++; | |
726f6388 JA |
284 | } |
285 | ||
286 | return (item); | |
287 | } | |
288 | ||
ccc6cda3 JA |
289 | /* Remove and discard all entries in TABLE. If FREE_DATA is non-null, it |
290 | is a function to call to dispose of a hash item's data. Otherwise, | |
291 | free() is called. */ | |
292 | void | |
7117c2d2 | 293 | hash_flush (table, free_data) |
ccc6cda3 | 294 | HASH_TABLE *table; |
f73dda09 | 295 | sh_free_func_t *free_data; |
ccc6cda3 JA |
296 | { |
297 | int i; | |
298 | register BUCKET_CONTENTS *bucket, *item; | |
299 | ||
7117c2d2 | 300 | if (table == 0 || HASH_ENTRIES (table) == 0) |
d166f048 JA |
301 | return; |
302 | ||
ccc6cda3 JA |
303 | for (i = 0; i < table->nbuckets; i++) |
304 | { | |
305 | bucket = table->bucket_array[i]; | |
306 | ||
307 | while (bucket) | |
308 | { | |
309 | item = bucket; | |
310 | bucket = bucket->next; | |
311 | ||
312 | if (free_data) | |
313 | (*free_data) (item->data); | |
314 | else | |
315 | free (item->data); | |
316 | free (item->key); | |
317 | free (item); | |
318 | } | |
319 | table->bucket_array[i] = (BUCKET_CONTENTS *)NULL; | |
320 | } | |
7117c2d2 JA |
321 | |
322 | table->nentries = 0; | |
ccc6cda3 JA |
323 | } |
324 | ||
d166f048 JA |
325 | /* Free the hash table pointed to by TABLE. */ |
326 | void | |
7117c2d2 | 327 | hash_dispose (table) |
d166f048 JA |
328 | HASH_TABLE *table; |
329 | { | |
330 | free (table->bucket_array); | |
331 | free (table); | |
332 | } | |
333 | ||
7117c2d2 JA |
334 | void |
335 | hash_walk (table, func) | |
726f6388 | 336 | HASH_TABLE *table; |
7117c2d2 | 337 | hash_wfunc *func; |
726f6388 | 338 | { |
7117c2d2 JA |
339 | register int i; |
340 | BUCKET_CONTENTS *item; | |
341 | ||
342 | if (table == 0 || HASH_ENTRIES (table) == 0) | |
343 | return; | |
344 | ||
345 | for (i = 0; i < table->nbuckets; i++) | |
346 | { | |
347 | for (item = hash_items (i, table); item; item = item->next) | |
348 | if ((*func) (item) < 0) | |
349 | return; | |
350 | } | |
726f6388 JA |
351 | } |
352 | ||
7117c2d2 | 353 | #if defined (DEBUG) || defined (TEST_HASHING) |
cce855bc | 354 | void |
7117c2d2 | 355 | hash_pstats (table, name) |
d166f048 JA |
356 | HASH_TABLE *table; |
357 | char *name; | |
358 | { | |
359 | register int slot, bcount; | |
360 | register BUCKET_CONTENTS *bc; | |
361 | ||
362 | if (name == 0) | |
363 | name = "unknown hash table"; | |
364 | ||
365 | fprintf (stderr, "%s: %d buckets; %d items\n", name, table->nbuckets, table->nentries); | |
366 | ||
367 | /* Print out a count of how many strings hashed to each bucket, so we can | |
368 | see how even the distribution is. */ | |
369 | for (slot = 0; slot < table->nbuckets; slot++) | |
370 | { | |
7117c2d2 | 371 | bc = hash_items (slot, table); |
d166f048 JA |
372 | |
373 | fprintf (stderr, "\tslot %3d: ", slot); | |
374 | for (bcount = 0; bc; bc = bc->next) | |
28ef6c31 | 375 | bcount++; |
d166f048 JA |
376 | |
377 | fprintf (stderr, "%d\n", bcount); | |
378 | } | |
379 | } | |
cce855bc | 380 | #endif |
d166f048 | 381 | |
726f6388 JA |
382 | #ifdef TEST_HASHING |
383 | ||
7117c2d2 | 384 | /* link with xmalloc.o and lib/malloc/libmalloc.a */ |
726f6388 JA |
385 | #undef NULL |
386 | #include <stdio.h> | |
387 | ||
f73dda09 JA |
388 | #ifndef NULL |
389 | #define NULL 0 | |
390 | #endif | |
391 | ||
392 | HASH_TABLE *table, *ntable; | |
726f6388 | 393 | |
7117c2d2 JA |
394 | int interrupt_immediately = 0; |
395 | ||
396 | int | |
397 | signal_is_trapped (s) | |
398 | int s; | |
726f6388 | 399 | { |
7117c2d2 JA |
400 | return (0); |
401 | } | |
402 | ||
403 | void | |
404 | programming_error (const char *format, ...) | |
405 | { | |
406 | abort(); | |
407 | } | |
408 | ||
409 | void | |
410 | fatal_error (const char *format, ...) | |
411 | { | |
412 | abort(); | |
726f6388 JA |
413 | } |
414 | ||
a0c0a00f CR |
415 | void |
416 | internal_warning (const char *format, ...) | |
417 | { | |
418 | } | |
419 | ||
726f6388 JA |
420 | main () |
421 | { | |
422 | char string[256]; | |
423 | int count = 0; | |
424 | BUCKET_CONTENTS *tt; | |
425 | ||
a0c0a00f CR |
426 | #if defined (TEST_NBUCKETS) |
427 | table = hash_create (TEST_NBUCKETS); | |
428 | #else | |
7117c2d2 | 429 | table = hash_create (0); |
a0c0a00f | 430 | #endif |
ccc6cda3 | 431 | |
726f6388 JA |
432 | for (;;) |
433 | { | |
434 | char *temp_string; | |
435 | if (fgets (string, sizeof (string), stdin) == 0) | |
28ef6c31 | 436 | break; |
726f6388 | 437 | if (!*string) |
28ef6c31 | 438 | break; |
726f6388 | 439 | temp_string = savestring (string); |
7117c2d2 | 440 | tt = hash_insert (temp_string, table, 0); |
726f6388 JA |
441 | if (tt->times_found) |
442 | { | |
443 | fprintf (stderr, "You have already added item `%s'\n", string); | |
444 | free (temp_string); | |
445 | } | |
446 | else | |
447 | { | |
448 | count++; | |
449 | } | |
450 | } | |
ccc6cda3 | 451 | |
7117c2d2 | 452 | hash_pstats (table, "hash test"); |
f73dda09 | 453 | |
7117c2d2 JA |
454 | ntable = hash_copy (table, (sh_string_func_t *)NULL); |
455 | hash_flush (table, (sh_free_func_t *)NULL); | |
456 | hash_pstats (ntable, "hash copy test"); | |
f73dda09 | 457 | |
d166f048 | 458 | exit (0); |
726f6388 JA |
459 | } |
460 | ||
461 | #endif /* TEST_HASHING */ |