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 /* Zero the buckets in TABLE. */
39 initialize_hash_table (table)
43 for (i = 0; i < table->nbuckets; i++)
44 table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
47 /* Make a new hash table with BUCKETS number of buckets. Initialize
48 each slot in the table to NULL. */
50 make_hash_table (buckets)
53 HASH_TABLE *new_table;
55 new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE));
57 buckets = DEFAULT_HASH_BUCKETS;
59 new_table->bucket_array =
60 (BUCKET_CONTENTS **)xmalloc (buckets * sizeof (BUCKET_CONTENTS *));
61 new_table->nbuckets = buckets;
62 new_table->nentries = 0;
63 initialize_hash_table (new_table);
67 /* Return the location of the bucket which should contain the data
68 for STRING. TABLE is a pointer to a HASH_TABLE. */
70 /* A possibly better distribution may be obtained by initializing i to
71 ~0UL and using i = (i * 31) + *string++ as the step */
73 #define ALL_ONES (~((unsigned long) 0))
74 #define BITS(h, n) ((unsigned long)(h) & ~(ALL_ONES << (n)))
77 hash_string (string, table)
81 register unsigned int i = 0;
84 i = (i << 2) + *string++;
86 return (BITS (i, 31) % table->nbuckets);
89 /* Return a pointer to the hashed item, or NULL if the item
92 find_hash_item (string, table)
96 BUCKET_CONTENTS *list;
100 return (BUCKET_CONTENTS *)NULL;
102 which_bucket = hash_string (string, table);
104 for (list = table->bucket_array[which_bucket]; list; list = list->next)
106 if (STREQ (list->key, string))
112 return (BUCKET_CONTENTS *)NULL;
115 /* Remove the item specified by STRING from the hash table TABLE.
116 The item removed is returned, so you can free its contents. If
117 the item isn't in this table NULL is returned. */
119 remove_hash_item (string, table)
124 BUCKET_CONTENTS *prev, *temp;
127 return (BUCKET_CONTENTS *)NULL;
129 the_bucket = hash_string (string, table);
130 prev = (BUCKET_CONTENTS *)NULL;
131 for (temp = table->bucket_array[the_bucket]; temp; temp = temp->next)
133 if (STREQ (temp->key, string))
136 prev->next = temp->next;
138 table->bucket_array[the_bucket] = temp->next;
145 return ((BUCKET_CONTENTS *) NULL);
148 /* Create an entry for STRING, in TABLE. If the entry already
149 exists, then return it. */
151 add_hash_item (string, table)
155 BUCKET_CONTENTS *item;
159 table = make_hash_table (0);
161 if ((item = find_hash_item (string, table)) == 0)
163 bucket = hash_string (string, table);
164 item = table->bucket_array[bucket];
166 while (item && item->next)
171 item->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
176 table->bucket_array[bucket] =
177 (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
178 item = table->bucket_array[bucket];
181 item->data = (char *)NULL;
182 item->next = (BUCKET_CONTENTS *)NULL;
185 item->times_found = 0;
191 /* Remove and discard all entries in TABLE. If FREE_DATA is non-null, it
192 is a function to call to dispose of a hash item's data. Otherwise,
195 flush_hash_table (table, free_data)
197 VFunction *free_data;
200 register BUCKET_CONTENTS *bucket, *item;
205 for (i = 0; i < table->nbuckets; i++)
207 bucket = table->bucket_array[i];
212 bucket = bucket->next;
215 (*free_data) (item->data);
221 table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
225 /* Free the hash table pointed to by TABLE. */
227 dispose_hash_table (table)
230 free (table->bucket_array);
234 /* No longer necessary; everything uses the macro */
236 /* Return the bucket_contents list of bucket BUCKET in TABLE. If
237 TABLE doesn't have BUCKET buckets, return NULL. */
238 #undef get_hash_bucket
240 get_hash_bucket (bucket, table)
244 if (table && bucket < table->nbuckets)
245 return (table->bucket_array[bucket]);
247 return (BUCKET_CONTENTS *)NULL;
253 print_table_stats (table, name)
257 register int slot, bcount;
258 register BUCKET_CONTENTS *bc;
261 name = "unknown hash table";
263 fprintf (stderr, "%s: %d buckets; %d items\n", name, table->nbuckets, table->nentries);
265 /* Print out a count of how many strings hashed to each bucket, so we can
266 see how even the distribution is. */
267 for (slot = 0; slot < table->nbuckets; slot++)
269 bc = get_hash_bucket (slot, table);
271 fprintf (stderr, "\tslot %3d: ", slot);
272 for (bcount = 0; bc; bc = bc->next)
275 fprintf (stderr, "%d\n", bcount);
292 char *result = (char *)malloc (bytes);
295 fprintf (stderr, "hash: out of virtual memory\n");
307 table = make_hash_table (NBUCKETS);
312 if (fgets (string, sizeof (string), stdin) == 0)
316 temp_string = savestring (string);
317 tt = add_hash_item (temp_string, table);
320 fprintf (stderr, "You have already added item `%s'\n", string);
329 print_table_stats (table, "hash test");
333 #endif /* TEST_HASHING */