1 /* hashlib.c -- functions to manage and access hash tables for bash. */
3 /* Copyright (C) 1987, 1989, 1991 Free Software Foundation, Inc.
5 This file is part of GNU Bash, the Bourne Again SHell.
7 Bash is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 Bash is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License along
18 with Bash; see the file COPYING. If not, write to the Free Software
19 Foundation, 59 Temple Place, Suite 330, Boston, MA 02111 USA. */
25 #if defined (HAVE_UNISTD_H)
27 # include <sys/types.h>
37 static void initialize_hash_table __P((HASH_TABLE *));
38 static BUCKET_CONTENTS *copy_bucket_array __P((BUCKET_CONTENTS *, sh_string_func_t *));
40 /* Zero the buckets in TABLE. */
42 initialize_hash_table (table)
46 for (i = 0; i < table->nbuckets; i++)
47 table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
50 /* Make a new hash table with BUCKETS number of buckets. Initialize
51 each slot in the table to NULL. */
53 make_hash_table (buckets)
56 HASH_TABLE *new_table;
58 new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE));
60 buckets = DEFAULT_HASH_BUCKETS;
62 new_table->bucket_array =
63 (BUCKET_CONTENTS **)xmalloc (buckets * sizeof (BUCKET_CONTENTS *));
64 new_table->nbuckets = buckets;
65 new_table->nentries = 0;
66 initialize_hash_table (new_table);
71 hash_table_nentries (table)
74 return (HASH_ENTRIES(table));
77 static BUCKET_CONTENTS *
78 copy_bucket_array (ba, cpdata)
80 sh_string_func_t *cpdata; /* data copy function */
82 BUCKET_CONTENTS *new_bucket, *n, *e;
85 return ((BUCKET_CONTENTS *)0);
87 for (n = (BUCKET_CONTENTS *)0, e = ba; e; e = e->next)
91 new_bucket = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
96 n->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
100 n->key = savestring (e->key);
101 n->data = e->data ? (cpdata ? (*cpdata) (e->data) : savestring (e->data))
103 n->times_found = e->times_found;
104 n->next = (BUCKET_CONTENTS *)NULL;
111 copy_hash_table (table, cpdata)
113 sh_string_func_t *cpdata;
115 HASH_TABLE *new_table;
119 return ((HASH_TABLE *)NULL);
121 new_table = make_hash_table (table->nbuckets);
123 for (i = 0; i < table->nbuckets; i++)
124 new_table->bucket_array[i] = copy_bucket_array (table->bucket_array[i], cpdata);
126 new_table->nentries = table->nentries;
130 /* Return the location of the bucket which should contain the data
131 for STRING. TABLE is a pointer to a HASH_TABLE. */
134 /* A possibly better distribution may be obtained by initializing i to
135 ~0UL and using i = (i * 31) + *string++ as the step */
137 #define ALL_ONES (~((unsigned long) 0))
138 #define BITS(h, n) ((unsigned long)(h) & ~(ALL_ONES << (n)))
142 hash_string (string, table)
146 register unsigned int i = 0;
149 i = (i << 2) + *string++;
152 return (BITS (i, 31) % table->nbuckets);
154 /* Rely on properties of unsigned division (unsigned/int -> unsigned) and
155 don't discard the upper 32 bits of the value, if present. */
156 return (i % table->nbuckets);
160 /* Return a pointer to the hashed item, or NULL if the item
163 find_hash_item (string, table)
167 BUCKET_CONTENTS *list;
171 return (BUCKET_CONTENTS *)NULL;
173 which_bucket = hash_string (string, table);
175 for (list = table->bucket_array[which_bucket]; list; list = list->next)
177 if (STREQ (list->key, string))
183 return (BUCKET_CONTENTS *)NULL;
186 /* Remove the item specified by STRING from the hash table TABLE.
187 The item removed is returned, so you can free its contents. If
188 the item isn't in this table NULL is returned. */
190 remove_hash_item (string, table)
195 BUCKET_CONTENTS *prev, *temp;
198 return (BUCKET_CONTENTS *)NULL;
200 the_bucket = hash_string (string, table);
201 prev = (BUCKET_CONTENTS *)NULL;
202 for (temp = table->bucket_array[the_bucket]; temp; temp = temp->next)
204 if (STREQ (temp->key, string))
207 prev->next = temp->next;
209 table->bucket_array[the_bucket] = temp->next;
216 return ((BUCKET_CONTENTS *) NULL);
219 /* Create an entry for STRING, in TABLE. If the entry already
220 exists, then return it. */
222 add_hash_item (string, table)
226 BUCKET_CONTENTS *item;
230 table = make_hash_table (0);
232 if ((item = find_hash_item (string, table)) == 0)
234 bucket = hash_string (string, table);
235 item = table->bucket_array[bucket];
237 while (item && item->next)
242 item->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
247 table->bucket_array[bucket] =
248 (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
249 item = table->bucket_array[bucket];
252 item->data = (char *)NULL;
253 item->next = (BUCKET_CONTENTS *)NULL;
256 item->times_found = 0;
262 /* Remove and discard all entries in TABLE. If FREE_DATA is non-null, it
263 is a function to call to dispose of a hash item's data. Otherwise,
266 flush_hash_table (table, free_data)
268 sh_free_func_t *free_data;
271 register BUCKET_CONTENTS *bucket, *item;
276 for (i = 0; i < table->nbuckets; i++)
278 bucket = table->bucket_array[i];
283 bucket = bucket->next;
286 (*free_data) (item->data);
292 table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
296 /* Free the hash table pointed to by TABLE. */
298 dispose_hash_table (table)
301 free (table->bucket_array);
305 /* No longer necessary; everything uses the macro */
307 /* Return the bucket_contents list of bucket BUCKET in TABLE. If
308 TABLE doesn't have BUCKET buckets, return NULL. */
309 #undef get_hash_bucket
311 get_hash_bucket (bucket, table)
315 if (table && bucket < table->nbuckets)
316 return (table->bucket_array[bucket]);
318 return (BUCKET_CONTENTS *)NULL;
324 print_table_stats (table, name)
328 register int slot, bcount;
329 register BUCKET_CONTENTS *bc;
332 name = "unknown hash table";
334 fprintf (stderr, "%s: %d buckets; %d items\n", name, table->nbuckets, table->nentries);
336 /* Print out a count of how many strings hashed to each bucket, so we can
337 see how even the distribution is. */
338 for (slot = 0; slot < table->nbuckets; slot++)
340 bc = get_hash_bucket (slot, table);
342 fprintf (stderr, "\tslot %3d: ", slot);
343 for (bcount = 0; bc; bc = bc->next)
346 fprintf (stderr, "%d\n", bcount);
360 HASH_TABLE *table, *ntable;
367 void *result = malloc (bytes);
370 fprintf (stderr, "hash: out of virtual memory\n");
382 table = make_hash_table (NBUCKETS);
387 if (fgets (string, sizeof (string), stdin) == 0)
391 temp_string = savestring (string);
392 tt = add_hash_item (temp_string, table);
395 fprintf (stderr, "You have already added item `%s'\n", string);
404 print_table_stats (table, "hash test");
406 ntable = copy_hash_table (table, (sh_string_func_t *)NULL);
407 flush_hash_table (table, (sh_free_func_t *)NULL);
408 print_table_stats (ntable, "hash copy test");
413 #endif /* TEST_HASHING */