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