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