]>
Commit | Line | Data |
---|---|---|
ccc6cda3 | 1 | /* hashlib.c -- functions to manage and access hash tables for bash. */ |
726f6388 JA |
2 | |
3 | /* Copyright (C) 1987, 1989, 1991 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 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 | |
10 | version. | |
11 | ||
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 | |
15 | for more details. | |
16 | ||
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. */ | |
20 | ||
ccc6cda3 | 21 | #include "config.h" |
726f6388 JA |
22 | |
23 | #if defined (HAVE_STRING_H) | |
24 | # include <string.h> | |
25 | #else /* !HAVE_STRING_H */ | |
26 | # include <strings.h> | |
27 | #endif /* !HAVE_STRING_H */ | |
28 | ||
29 | #if defined (HAVE_STDLIB_H) | |
30 | # include <stdlib.h> | |
31 | #else | |
32 | # include "ansi_stdlib.h" | |
33 | #endif /* HAVE_STDLIB_H */ | |
34 | ||
ccc6cda3 JA |
35 | #if defined (HAVE_UNISTD_H) |
36 | # include <unistd.h> | |
37 | #endif | |
726f6388 | 38 | |
ccc6cda3 JA |
39 | #include "shell.h" |
40 | #include "hashlib.h" | |
726f6388 JA |
41 | |
42 | /* Zero the buckets in TABLE. */ | |
43 | static void | |
44 | initialize_hash_table (table) | |
45 | HASH_TABLE *table; | |
46 | { | |
47 | register int i; | |
48 | for (i = 0; i < table->nbuckets; i++) | |
49 | table->bucket_array[i] = (BUCKET_CONTENTS *)NULL; | |
50 | } | |
51 | ||
52 | /* Make a new hash table with BUCKETS number of buckets. Initialize | |
53 | each slot in the table to NULL. */ | |
54 | HASH_TABLE * | |
55 | make_hash_table (buckets) | |
56 | int buckets; | |
57 | { | |
ccc6cda3 | 58 | HASH_TABLE *new_table; |
726f6388 | 59 | |
ccc6cda3 | 60 | new_table = (HASH_TABLE *)xmalloc (sizeof (HASH_TABLE)); |
726f6388 JA |
61 | if (buckets == 0) |
62 | buckets = DEFAULT_HASH_BUCKETS; | |
63 | ||
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); | |
69 | return (new_table); | |
70 | } | |
71 | ||
726f6388 JA |
72 | /* Return the location of the bucket which should contain the data |
73 | for STRING. TABLE is a pointer to a HASH_TABLE. */ | |
74 | ||
75 | #define ALL_ONES (~((unsigned long) 0)) | |
76 | #define BITS(h, n) ((unsigned long)(h) & ~(ALL_ONES << (n))) | |
77 | ||
78 | int | |
79 | hash_string (string, table) | |
80 | char *string; | |
81 | HASH_TABLE *table; | |
82 | { | |
83 | register unsigned int i = 0; | |
84 | ||
85 | while (*string) | |
86 | i = (i << 2) + *string++; | |
87 | ||
88 | return (BITS (i, 31) % table->nbuckets); | |
89 | } | |
90 | ||
91 | /* Return a pointer to the hashed item, or NULL if the item | |
92 | can't be found. */ | |
93 | BUCKET_CONTENTS * | |
94 | find_hash_item (string, table) | |
95 | char *string; | |
96 | HASH_TABLE *table; | |
97 | { | |
98 | BUCKET_CONTENTS *list; | |
99 | int which_bucket; | |
100 | ||
ccc6cda3 | 101 | if (table == 0) |
726f6388 JA |
102 | return (BUCKET_CONTENTS *)NULL; |
103 | ||
104 | which_bucket = hash_string (string, table); | |
105 | ||
ccc6cda3 | 106 | for (list = table->bucket_array[which_bucket]; list; list = list->next) |
726f6388 JA |
107 | { |
108 | if (STREQ (list->key, string)) | |
109 | { | |
110 | list->times_found++; | |
111 | return (list); | |
112 | } | |
726f6388 JA |
113 | } |
114 | return (BUCKET_CONTENTS *)NULL; | |
115 | } | |
116 | ||
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. */ | |
120 | BUCKET_CONTENTS * | |
121 | remove_hash_item (string, table) | |
122 | char *string; | |
123 | HASH_TABLE *table; | |
124 | { | |
125 | int the_bucket; | |
126 | BUCKET_CONTENTS *prev, *temp; | |
127 | ||
ccc6cda3 | 128 | if (table == 0) |
726f6388 JA |
129 | return (BUCKET_CONTENTS *)NULL; |
130 | ||
131 | the_bucket = hash_string (string, table); | |
132 | prev = (BUCKET_CONTENTS *)NULL; | |
ccc6cda3 | 133 | for (temp = table->bucket_array[the_bucket]; temp; temp = temp->next) |
726f6388 JA |
134 | { |
135 | if (STREQ (temp->key, string)) | |
136 | { | |
137 | if (prev) | |
138 | prev->next = temp->next; | |
139 | else | |
140 | table->bucket_array[the_bucket] = temp->next; | |
141 | ||
142 | table->nentries--; | |
143 | return (temp); | |
144 | } | |
145 | prev = temp; | |
726f6388 JA |
146 | } |
147 | return ((BUCKET_CONTENTS *) NULL); | |
148 | } | |
149 | ||
150 | /* Create an entry for STRING, in TABLE. If the entry already | |
151 | exists, then return it. */ | |
152 | BUCKET_CONTENTS * | |
153 | add_hash_item (string, table) | |
154 | char *string; | |
155 | HASH_TABLE *table; | |
156 | { | |
157 | BUCKET_CONTENTS *item; | |
ccc6cda3 | 158 | int bucket; |
726f6388 | 159 | |
ccc6cda3 | 160 | if (table == 0) |
726f6388 JA |
161 | table = make_hash_table (0); |
162 | ||
163 | if ((item = find_hash_item (string, table)) == 0) | |
164 | { | |
ccc6cda3 | 165 | bucket = hash_string (string, table); |
726f6388 JA |
166 | item = table->bucket_array[bucket]; |
167 | ||
168 | while (item && item->next) | |
169 | item = item->next; | |
170 | ||
171 | if (item) | |
172 | { | |
173 | item->next = (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS)); | |
174 | item = item->next; | |
175 | } | |
176 | else | |
177 | { | |
178 | table->bucket_array[bucket] = | |
179 | (BUCKET_CONTENTS *)xmalloc (sizeof (BUCKET_CONTENTS)); | |
180 | item = table->bucket_array[bucket]; | |
181 | } | |
182 | ||
183 | item->data = (char *)NULL; | |
184 | item->next = (BUCKET_CONTENTS *)NULL; | |
185 | item->key = string; | |
186 | table->nentries++; | |
187 | item->times_found = 0; | |
188 | } | |
189 | ||
190 | return (item); | |
191 | } | |
192 | ||
ccc6cda3 JA |
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, | |
195 | free() is called. */ | |
196 | void | |
197 | flush_hash_table (table, free_data) | |
198 | HASH_TABLE *table; | |
199 | VFunction *free_data; | |
200 | { | |
201 | int i; | |
202 | register BUCKET_CONTENTS *bucket, *item; | |
203 | ||
204 | for (i = 0; i < table->nbuckets; i++) | |
205 | { | |
206 | bucket = table->bucket_array[i]; | |
207 | ||
208 | while (bucket) | |
209 | { | |
210 | item = bucket; | |
211 | bucket = bucket->next; | |
212 | ||
213 | if (free_data) | |
214 | (*free_data) (item->data); | |
215 | else | |
216 | free (item->data); | |
217 | free (item->key); | |
218 | free (item); | |
219 | } | |
220 | table->bucket_array[i] = (BUCKET_CONTENTS *)NULL; | |
221 | } | |
222 | } | |
223 | ||
726f6388 JA |
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 | |
227 | BUCKET_CONTENTS * | |
228 | get_hash_bucket (bucket, table) | |
229 | int bucket; | |
230 | HASH_TABLE *table; | |
231 | { | |
232 | if (table && bucket < table->nbuckets) | |
233 | return (table->bucket_array[bucket]); | |
234 | else | |
235 | return (BUCKET_CONTENTS *)NULL; | |
236 | } | |
237 | ||
238 | #ifdef TEST_HASHING | |
239 | ||
240 | #undef NULL | |
241 | #include <stdio.h> | |
242 | ||
243 | HASH_TABLE *table; | |
244 | #define NBUCKETS 107 | |
245 | ||
246 | char * | |
247 | xmalloc (bytes) | |
248 | int bytes; | |
249 | { | |
250 | char *result = (char *)malloc (bytes); | |
251 | if (!result) | |
252 | { | |
ccc6cda3 | 253 | fprintf (stderr, "hash: out of virtual memory\n"); |
726f6388 JA |
254 | abort (); |
255 | } | |
256 | return (result); | |
257 | } | |
258 | ||
259 | main () | |
260 | { | |
261 | char string[256]; | |
262 | int count = 0; | |
263 | BUCKET_CONTENTS *tt; | |
264 | ||
265 | table = make_hash_table (NBUCKETS); | |
ccc6cda3 | 266 | |
726f6388 JA |
267 | for (;;) |
268 | { | |
269 | char *temp_string; | |
270 | if (fgets (string, sizeof (string), stdin) == 0) | |
271 | break; | |
272 | if (!*string) | |
273 | break; | |
274 | temp_string = savestring (string); | |
275 | tt = add_hash_item (temp_string, table); | |
276 | if (tt->times_found) | |
277 | { | |
278 | fprintf (stderr, "You have already added item `%s'\n", string); | |
279 | free (temp_string); | |
280 | } | |
281 | else | |
282 | { | |
283 | count++; | |
284 | } | |
285 | } | |
ccc6cda3 | 286 | |
726f6388 JA |
287 | printf ("You have entered %d (%d) items. The distribution is:\n", |
288 | table->nentries, count); | |
289 | ||
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++) | |
293 | { | |
294 | int bcount; | |
295 | register BUCKET_CONTENTS *list = get_hash_bucket (count, table); | |
ccc6cda3 | 296 | |
726f6388 JA |
297 | printf ("slot %3d: ", count); |
298 | bcount = 0; | |
299 | ||
300 | for (bcount = 0; list; list = list->next) | |
301 | bcount++; | |
302 | ||
303 | printf ("%d\n", bcount); | |
304 | } | |
305 | exit (0); | |
306 | } | |
307 | ||
308 | #endif /* TEST_HASHING */ |