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 1, 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, 675 Mass Ave, Cambridge, MA 02139, USA. */
23 #if defined (HAVE_STRING_H)
25 #else /* !HAVE_STRING_H */
27 #endif /* !HAVE_STRING_H */
29 #if defined (HAVE_STDLIB_H)
32 # include "ansi_stdlib.h"
33 #endif /* HAVE_STDLIB_H */
35 #if defined (HAVE_UNISTD_H)
42 /* Zero the buckets in TABLE. */
44 initialize_hash_table (table)
48 for (i = 0; i < table->nbuckets; i++)
49 table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
52 /* Make a new hash table with BUCKETS number of buckets. Initialize
53 each slot in the table to NULL. */
55 make_hash_table (buckets)
58 HASH_TABLE *new_table;
60 new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE));
62 buckets = DEFAULT_HASH_BUCKETS;
64 new_table->bucket_array =
65 (BUCKET_CONTENTS **)xmalloc (buckets * sizeof (BUCKET_CONTENTS *));
66 new_table->nbuckets = buckets;
67 new_table->nentries = 0;
68 initialize_hash_table (new_table);
72 /* Return the location of the bucket which should contain the data
73 for STRING. TABLE is a pointer to a HASH_TABLE. */
75 #define ALL_ONES (~((unsigned long) 0))
76 #define BITS(h, n) ((unsigned long)(h) & ~(ALL_ONES << (n)))
79 hash_string (string, table)
83 register unsigned int i = 0;
86 i = (i << 2) + *string++;
88 return (BITS (i, 31) % table->nbuckets);
91 /* Return a pointer to the hashed item, or NULL if the item
94 find_hash_item (string, table)
98 BUCKET_CONTENTS *list;
102 return (BUCKET_CONTENTS *)NULL;
104 which_bucket = hash_string (string, table);
106 for (list = table->bucket_array[which_bucket]; list; list = list->next)
108 if (STREQ (list->key, string))
114 return (BUCKET_CONTENTS *)NULL;
117 /* Remove the item specified by STRING from the hash table TABLE.
118 The item removed is returned, so you can free its contents. If
119 the item isn't in this table NULL is returned. */
121 remove_hash_item (string, table)
126 BUCKET_CONTENTS *prev, *temp;
129 return (BUCKET_CONTENTS *)NULL;
131 the_bucket = hash_string (string, table);
132 prev = (BUCKET_CONTENTS *)NULL;
133 for (temp = table->bucket_array[the_bucket]; temp; temp = temp->next)
135 if (STREQ (temp->key, string))
138 prev->next = temp->next;
140 table->bucket_array[the_bucket] = temp->next;
147 return ((BUCKET_CONTENTS *) NULL);
150 /* Create an entry for STRING, in TABLE. If the entry already
151 exists, then return it. */
153 add_hash_item (string, table)
157 BUCKET_CONTENTS *item;
161 table = make_hash_table (0);
163 if ((item = find_hash_item (string, table)) == 0)
165 bucket = hash_string (string, table);
166 item = table->bucket_array[bucket];
168 while (item && item->next)
173 item->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
178 table->bucket_array[bucket] =
179 (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS));
180 item = table->bucket_array[bucket];
183 item->data = (char *)NULL;
184 item->next = (BUCKET_CONTENTS *)NULL;
187 item->times_found = 0;
193 /* Remove and discard all entries in TABLE. If FREE_DATA is non-null, it
194 is a function to call to dispose of a hash item's data. Otherwise,
197 flush_hash_table (table, free_data)
199 VFunction *free_data;
202 register BUCKET_CONTENTS *bucket, *item;
204 for (i = 0; i < table->nbuckets; i++)
206 bucket = table->bucket_array[i];
211 bucket = bucket->next;
214 (*free_data) (item->data);
220 table->bucket_array[i] = (BUCKET_CONTENTS *)NULL;
224 /* Return the bucket_contents list of bucket BUCKET in TABLE. If
225 TABLE doesn't have BUCKET buckets, return NULL. */
226 #undef get_hash_bucket
228 get_hash_bucket (bucket, table)
232 if (table && bucket < table->nbuckets)
233 return (table->bucket_array[bucket]);
235 return (BUCKET_CONTENTS *)NULL;
250 char *result = (char *)malloc (bytes);
253 fprintf (stderr, "hash: out of virtual memory\n");
265 table = make_hash_table (NBUCKETS);
270 if (fgets (string, sizeof (string), stdin) == 0)
274 temp_string = savestring (string);
275 tt = add_hash_item (temp_string, table);
278 fprintf (stderr, "You have already added item `%s'\n", string);
287 printf ("You have entered %d (%d) items. The distribution is:\n",
288 table->nentries, count);
290 /* Print out a count of how many strings hashed to each bucket, so we can
291 see how even the distribution is. */
292 for (count = 0; count < table->nbuckets; count++)
295 register BUCKET_CONTENTS *list = get_hash_bucket (count, table);
297 printf ("slot %3d: ", count);
300 for (bcount = 0; list; list = list->next)
303 printf ("%d\n", bcount);
308 #endif /* TEST_HASHING */