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