hash.c revision 78828
1/* hash.c -- gas hash table code 2 Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999, 3 2000 4 Free Software Foundation, Inc. 5 6 This file is part of GAS, the GNU Assembler. 7 8 GAS is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 2, or (at your option) 11 any later version. 12 13 GAS is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GAS; see the file COPYING. If not, write to the Free 20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 21 02111-1307, USA. */ 22 23/* This version of the hash table code is a wholescale replacement of 24 the old hash table code, which was fairly bad. This is based on 25 the hash table code in BFD, but optimized slightly for the 26 asssembler. The assembler does not need to derive structures that 27 are stored in the hash table. Instead, it always stores a pointer. 28 The assembler uses the hash table mostly to store symbols, and we 29 don't need to confuse the symbol structure with a hash table 30 structure. */ 31 32#include "as.h" 33#include "obstack.h" 34 35/* The default number of entries to use when creating a hash table. */ 36 37#define DEFAULT_SIZE (4051) 38 39/* An entry in a hash table. */ 40 41struct hash_entry { 42 /* Next entry for this hash code. */ 43 struct hash_entry *next; 44 /* String being hashed. */ 45 const char *string; 46 /* Hash code. This is the full hash code, not the index into the 47 table. */ 48 unsigned long hash; 49 /* Pointer being stored in the hash table. */ 50 PTR data; 51}; 52 53/* A hash table. */ 54 55struct hash_control { 56 /* The hash array. */ 57 struct hash_entry **table; 58 /* The number of slots in the hash table. */ 59 unsigned int size; 60 /* An obstack for this hash table. */ 61 struct obstack memory; 62 63#ifdef HASH_STATISTICS 64 /* Statistics. */ 65 unsigned long lookups; 66 unsigned long hash_compares; 67 unsigned long string_compares; 68 unsigned long insertions; 69 unsigned long replacements; 70 unsigned long deletions; 71#endif /* HASH_STATISTICS */ 72}; 73 74/* Create a hash table. This return a control block. */ 75 76struct hash_control * 77hash_new () 78{ 79 unsigned int size; 80 struct hash_control *ret; 81 unsigned int alloc; 82 83 size = DEFAULT_SIZE; 84 85 ret = (struct hash_control *) xmalloc (sizeof *ret); 86 obstack_begin (&ret->memory, chunksize); 87 alloc = size * sizeof (struct hash_entry *); 88 ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc); 89 memset (ret->table, 0, alloc); 90 ret->size = size; 91 92#ifdef HASH_STATISTICS 93 ret->lookups = 0; 94 ret->hash_compares = 0; 95 ret->string_compares = 0; 96 ret->insertions = 0; 97 ret->replacements = 0; 98 ret->deletions = 0; 99#endif 100 101 return ret; 102} 103 104/* Delete a hash table, freeing all allocated memory. */ 105 106void 107hash_die (table) 108 struct hash_control *table; 109{ 110 obstack_free (&table->memory, 0); 111 free (table); 112} 113 114/* Look up a string in a hash table. This returns a pointer to the 115 hash_entry, or NULL if the string is not in the table. If PLIST is 116 not NULL, this sets *PLIST to point to the start of the list which 117 would hold this hash entry. If PHASH is not NULL, this sets *PHASH 118 to the hash code for KEY. 119 120 Each time we look up a string, we move it to the start of the list 121 for its hash code, to take advantage of referential locality. */ 122 123static struct hash_entry *hash_lookup PARAMS ((struct hash_control *, 124 const char *, 125 struct hash_entry ***, 126 unsigned long *)); 127 128static struct hash_entry * 129hash_lookup (table, key, plist, phash) 130 struct hash_control *table; 131 const char *key; 132 struct hash_entry ***plist; 133 unsigned long *phash; 134{ 135 register unsigned long hash; 136 unsigned int len; 137 register const unsigned char *s; 138 register unsigned int c; 139 unsigned int index; 140 struct hash_entry **list; 141 struct hash_entry *p; 142 struct hash_entry *prev; 143 144#ifdef HASH_STATISTICS 145 ++table->lookups; 146#endif 147 148 hash = 0; 149 len = 0; 150 s = (const unsigned char *) key; 151 while ((c = *s++) != '\0') 152 { 153 hash += c + (c << 17); 154 hash ^= hash >> 2; 155 ++len; 156 } 157 hash += len + (len << 17); 158 hash ^= hash >> 2; 159 160 if (phash != NULL) 161 *phash = hash; 162 163 index = hash % table->size; 164 list = table->table + index; 165 166 if (plist != NULL) 167 *plist = list; 168 169 prev = NULL; 170 for (p = *list; p != NULL; p = p->next) 171 { 172#ifdef HASH_STATISTICS 173 ++table->hash_compares; 174#endif 175 176 if (p->hash == hash) 177 { 178#ifdef HASH_STATISTICS 179 ++table->string_compares; 180#endif 181 182 if (strcmp (p->string, key) == 0) 183 { 184 if (prev != NULL) 185 { 186 prev->next = p->next; 187 p->next = *list; 188 *list = p; 189 } 190 191 return p; 192 } 193 } 194 195 prev = p; 196 } 197 198 return NULL; 199} 200 201/* Insert an entry into a hash table. This returns NULL on success. 202 On error, it returns a printable string indicating the error. It 203 is considered to be an error if the entry already exists in the 204 hash table. */ 205 206const char * 207hash_insert (table, key, value) 208 struct hash_control *table; 209 const char *key; 210 PTR value; 211{ 212 struct hash_entry *p; 213 struct hash_entry **list; 214 unsigned long hash; 215 216 p = hash_lookup (table, key, &list, &hash); 217 if (p != NULL) 218 return "exists"; 219 220#ifdef HASH_STATISTICS 221 ++table->insertions; 222#endif 223 224 p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); 225 p->string = key; 226 p->hash = hash; 227 p->data = value; 228 229 p->next = *list; 230 *list = p; 231 232 return NULL; 233} 234 235/* Insert or replace an entry in a hash table. This returns NULL on 236 success. On error, it returns a printable string indicating the 237 error. If an entry already exists, its value is replaced. */ 238 239const char * 240hash_jam (table, key, value) 241 struct hash_control *table; 242 const char *key; 243 PTR value; 244{ 245 struct hash_entry *p; 246 struct hash_entry **list; 247 unsigned long hash; 248 249 p = hash_lookup (table, key, &list, &hash); 250 if (p != NULL) 251 { 252#ifdef HASH_STATISTICS 253 ++table->replacements; 254#endif 255 256 p->data = value; 257 } 258 else 259 { 260#ifdef HASH_STATISTICS 261 ++table->insertions; 262#endif 263 264 p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); 265 p->string = key; 266 p->hash = hash; 267 p->data = value; 268 269 p->next = *list; 270 *list = p; 271 } 272 273 return NULL; 274} 275 276/* Replace an existing entry in a hash table. This returns the old 277 value stored for the entry. If the entry is not found in the hash 278 table, this does nothing and returns NULL. */ 279 280PTR 281hash_replace (table, key, value) 282 struct hash_control *table; 283 const char *key; 284 PTR value; 285{ 286 struct hash_entry *p; 287 PTR ret; 288 289 p = hash_lookup (table, key, NULL, NULL); 290 if (p == NULL) 291 return NULL; 292 293#ifdef HASH_STATISTICS 294 ++table->replacements; 295#endif 296 297 ret = p->data; 298 299 p->data = value; 300 301 return ret; 302} 303 304/* Find an entry in a hash table, returning its value. Returns NULL 305 if the entry is not found. */ 306 307PTR 308hash_find (table, key) 309 struct hash_control *table; 310 const char *key; 311{ 312 struct hash_entry *p; 313 314 p = hash_lookup (table, key, NULL, NULL); 315 if (p == NULL) 316 return NULL; 317 318 return p->data; 319} 320 321/* Delete an entry from a hash table. This returns the value stored 322 for that entry, or NULL if there is no such entry. */ 323 324PTR 325hash_delete (table, key) 326 struct hash_control *table; 327 const char *key; 328{ 329 struct hash_entry *p; 330 struct hash_entry **list; 331 332 p = hash_lookup (table, key, &list, NULL); 333 if (p == NULL) 334 return NULL; 335 336 if (p != *list) 337 abort (); 338 339#ifdef HASH_STATISTICS 340 ++table->deletions; 341#endif 342 343 *list = p->next; 344 345 /* Note that we never reclaim the memory for this entry. If gas 346 ever starts deleting hash table entries in a big way, this will 347 have to change. */ 348 349 return p->data; 350} 351 352/* Traverse a hash table. Call the function on every entry in the 353 hash table. */ 354 355void 356hash_traverse (table, pfn) 357 struct hash_control *table; 358 void (*pfn) PARAMS ((const char *key, PTR value)); 359{ 360 unsigned int i; 361 362 for (i = 0; i < table->size; ++i) 363 { 364 struct hash_entry *p; 365 366 for (p = table->table[i]; p != NULL; p = p->next) 367 (*pfn) (p->string, p->data); 368 } 369} 370 371/* Print hash table statistics on the specified file. NAME is the 372 name of the hash table, used for printing a header. */ 373 374void 375hash_print_statistics (f, name, table) 376 FILE *f ATTRIBUTE_UNUSED; 377 const char *name ATTRIBUTE_UNUSED; 378 struct hash_control *table ATTRIBUTE_UNUSED; 379{ 380#ifdef HASH_STATISTICS 381 unsigned int i; 382 unsigned long total; 383 unsigned long empty; 384 385 fprintf (f, "%s hash statistics:\n", name); 386 fprintf (f, "\t%lu lookups\n", table->lookups); 387 fprintf (f, "\t%lu hash comparisons\n", table->hash_compares); 388 fprintf (f, "\t%lu string comparisons\n", table->string_compares); 389 fprintf (f, "\t%lu insertions\n", table->insertions); 390 fprintf (f, "\t%lu replacements\n", table->replacements); 391 fprintf (f, "\t%lu deletions\n", table->deletions); 392 393 total = 0; 394 empty = 0; 395 for (i = 0; i < table->size; ++i) 396 { 397 struct hash_entry *p; 398 399 if (table->table[i] == NULL) 400 ++empty; 401 else 402 { 403 for (p = table->table[i]; p != NULL; p = p->next) 404 ++total; 405 } 406 } 407 408 fprintf (f, "\t%g average chain length\n", (double) total / table->size); 409 fprintf (f, "\t%lu empty slots\n", empty); 410#endif 411} 412 413#ifdef TEST 414 415/* This test program is left over from the old hash table code. */ 416 417/* Number of hash tables to maintain (at once) in any testing. */ 418#define TABLES (6) 419 420/* We can have 12 statistics. */ 421#define STATBUFSIZE (12) 422 423/* Display statistics here. */ 424int statbuf[STATBUFSIZE]; 425 426/* Human farts here. */ 427char answer[100]; 428 429/* We test many hash tables at once. */ 430char *hashtable[TABLES]; 431 432/* Points to curent hash_control. */ 433char *h; 434char **pp; 435char *p; 436char *name; 437char *value; 438int size; 439int used; 440char command; 441 442/* Number 0:TABLES-1 of current hashed symbol table. */ 443int number; 444 445int 446main () 447{ 448 void applicatee (); 449 void destroy (); 450 char *what (); 451 int *ip; 452 453 number = 0; 454 h = 0; 455 printf ("type h <RETURN> for help\n"); 456 for (;;) 457 { 458 printf ("hash_test command: "); 459 gets (answer); 460 command = answer[0]; 461 if (isupper (command)) 462 command = tolower (command); /* Ecch! */ 463 switch (command) 464 { 465 case '#': 466 printf ("old hash table #=%d.\n", number); 467 whattable (); 468 break; 469 case '?': 470 for (pp = hashtable; pp < hashtable + TABLES; pp++) 471 { 472 printf ("address of hash table #%d control block is %xx\n", 473 pp - hashtable, *pp); 474 } 475 break; 476 case 'a': 477 hash_traverse (h, applicatee); 478 break; 479 case 'd': 480 hash_traverse (h, destroy); 481 hash_die (h); 482 break; 483 case 'f': 484 p = hash_find (h, name = what ("symbol")); 485 printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT"); 486 break; 487 case 'h': 488 printf ("# show old, select new default hash table number\n"); 489 printf ("? display all hashtable control block addresses\n"); 490 printf ("a apply a simple display-er to each symbol in table\n"); 491 printf ("d die: destroy hashtable\n"); 492 printf ("f find value of nominated symbol\n"); 493 printf ("h this help\n"); 494 printf ("i insert value into symbol\n"); 495 printf ("j jam value into symbol\n"); 496 printf ("n new hashtable\n"); 497 printf ("r replace a value with another\n"); 498 printf ("s say what %% of table is used\n"); 499 printf ("q exit this program\n"); 500 printf ("x delete a symbol from table, report its value\n"); 501 break; 502 case 'i': 503 p = hash_insert (h, name = what ("symbol"), value = what ("value")); 504 if (p) 505 { 506 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, 507 p); 508 } 509 break; 510 case 'j': 511 p = hash_jam (h, name = what ("symbol"), value = what ("value")); 512 if (p) 513 { 514 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p); 515 } 516 break; 517 case 'n': 518 h = hashtable[number] = (char *) hash_new (); 519 break; 520 case 'q': 521 exit (EXIT_SUCCESS); 522 case 'r': 523 p = hash_replace (h, name = what ("symbol"), value = what ("value")); 524 printf ("old value was \"%s\"\n", p ? p : "{}"); 525 break; 526 case 's': 527 hash_say (h, statbuf, STATBUFSIZE); 528 for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++) 529 { 530 printf ("%d ", *ip); 531 } 532 printf ("\n"); 533 break; 534 case 'x': 535 p = hash_delete (h, name = what ("symbol")); 536 printf ("old value was \"%s\"\n", p ? p : "{}"); 537 break; 538 default: 539 printf ("I can't understand command \"%c\"\n", command); 540 break; 541 } 542 } 543} 544 545char * 546what (description) 547 char *description; 548{ 549 char *retval; 550 char *malloc (); 551 552 printf (" %s : ", description); 553 gets (answer); 554 /* Will one day clean up answer here. */ 555 retval = malloc (strlen (answer) + 1); 556 if (!retval) 557 { 558 error ("room"); 559 } 560 (void) strcpy (retval, answer); 561 return (retval); 562} 563 564void 565destroy (string, value) 566 char *string; 567 char *value; 568{ 569 free (string); 570 free (value); 571} 572 573void 574applicatee (string, value) 575 char *string; 576 char *value; 577{ 578 printf ("%.20s-%.20s\n", string, value); 579} 580 581/* Determine number: what hash table to use. 582 Also determine h: points to hash_control. */ 583 584void 585whattable () 586{ 587 for (;;) 588 { 589 printf (" what hash table (%d:%d) ? ", 0, TABLES - 1); 590 gets (answer); 591 sscanf (answer, "%d", &number); 592 if (number >= 0 && number < TABLES) 593 { 594 h = hashtable[number]; 595 if (!h) 596 { 597 printf ("warning: current hash-table-#%d. has no hash-control\n", number); 598 } 599 return; 600 } 601 else 602 { 603 printf ("invalid hash table number: %d\n", number); 604 } 605 } 606} 607 608#endif /* TEST */ 609