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