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