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, 2009, 2011, 2013 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 = bfd_hash_set_default_size (size); 82 } 83 84 /* Create a hash table. This return a control block. */ 85 86 struct hash_control * 87 hash_new_sized (unsigned long size) 88 { 89 unsigned long alloc; 90 struct hash_control *ret; 91 92 ret = (struct hash_control *) xmalloc (sizeof *ret); 93 obstack_begin (&ret->memory, chunksize); 94 alloc = size * sizeof (struct hash_entry *); 95 ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc); 96 memset (ret->table, 0, alloc); 97 ret->size = size; 98 99 #ifdef HASH_STATISTICS 100 ret->lookups = 0; 101 ret->hash_compares = 0; 102 ret->string_compares = 0; 103 ret->insertions = 0; 104 ret->replacements = 0; 105 ret->deletions = 0; 106 #endif 107 108 return ret; 109 } 110 111 struct hash_control * 112 hash_new (void) 113 { 114 return hash_new_sized (gas_hash_table_size); 115 } 116 117 /* Delete a hash table, freeing all allocated memory. */ 118 119 void 120 hash_die (struct hash_control *table) 121 { 122 obstack_free (&table->memory, 0); 123 free (table); 124 } 125 126 /* Look up a string in a hash table. This returns a pointer to the 127 hash_entry, or NULL if the string is not in the table. If PLIST is 128 not NULL, this sets *PLIST to point to the start of the list which 129 would hold this hash entry. If PHASH is not NULL, this sets *PHASH 130 to the hash code for KEY. 131 132 Each time we look up a string, we move it to the start of the list 133 for its hash code, to take advantage of referential locality. */ 134 135 static struct hash_entry * 136 hash_lookup (struct hash_control *table, const char *key, size_t len, 137 struct hash_entry ***plist, unsigned long *phash) 138 { 139 unsigned long hash; 140 size_t n; 141 unsigned int c; 142 unsigned int hindex; 143 struct hash_entry **list; 144 struct hash_entry *p; 145 struct hash_entry *prev; 146 147 #ifdef HASH_STATISTICS 148 ++table->lookups; 149 #endif 150 151 hash = 0; 152 for (n = 0; n < len; n++) 153 { 154 c = key[n]; 155 hash += c + (c << 17); 156 hash ^= hash >> 2; 157 } 158 hash += len + (len << 17); 159 hash ^= hash >> 2; 160 161 if (phash != NULL) 162 *phash = hash; 163 164 hindex = hash % table->size; 165 list = table->table + hindex; 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 (strncmp (p->string, key, len) == 0 && p->string[len] == '\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 207 const char * 208 hash_insert (struct hash_control *table, const char *key, void *val) 209 { 210 struct hash_entry *p; 211 struct hash_entry **list; 212 unsigned long hash; 213 214 p = hash_lookup (table, key, strlen (key), &list, &hash); 215 if (p != NULL) 216 return "exists"; 217 218 #ifdef HASH_STATISTICS 219 ++table->insertions; 220 #endif 221 222 p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); 223 p->string = key; 224 p->hash = hash; 225 p->data = val; 226 227 p->next = *list; 228 *list = p; 229 230 return NULL; 231 } 232 233 /* Insert or replace an entry in a hash table. This returns NULL on 234 success. On error, it returns a printable string indicating the 235 error. If an entry already exists, its value is replaced. */ 236 237 const char * 238 hash_jam (struct hash_control *table, const char *key, void *val) 239 { 240 struct hash_entry *p; 241 struct hash_entry **list; 242 unsigned long hash; 243 244 p = hash_lookup (table, key, strlen (key), &list, &hash); 245 if (p != NULL) 246 { 247 #ifdef HASH_STATISTICS 248 ++table->replacements; 249 #endif 250 251 p->data = val; 252 } 253 else 254 { 255 #ifdef HASH_STATISTICS 256 ++table->insertions; 257 #endif 258 259 p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); 260 p->string = key; 261 p->hash = hash; 262 p->data = val; 263 264 p->next = *list; 265 *list = p; 266 } 267 268 return NULL; 269 } 270 271 /* Replace an existing entry in a hash table. This returns the old 272 value stored for the entry. If the entry is not found in the hash 273 table, this does nothing and returns NULL. */ 274 275 void * 276 hash_replace (struct hash_control *table, const char *key, void *value) 277 { 278 struct hash_entry *p; 279 void *ret; 280 281 p = hash_lookup (table, key, strlen (key), NULL, NULL); 282 if (p == NULL) 283 return NULL; 284 285 #ifdef HASH_STATISTICS 286 ++table->replacements; 287 #endif 288 289 ret = p->data; 290 291 p->data = value; 292 293 return ret; 294 } 295 296 /* Find an entry in a hash table, returning its value. Returns NULL 297 if the entry is not found. */ 298 299 void * 300 hash_find (struct hash_control *table, const char *key) 301 { 302 struct hash_entry *p; 303 304 p = hash_lookup (table, key, strlen (key), NULL, NULL); 305 if (p == NULL) 306 return NULL; 307 308 return p->data; 309 } 310 311 /* As hash_find, but KEY is of length LEN and is not guaranteed to be 312 NUL-terminated. */ 313 314 void * 315 hash_find_n (struct hash_control *table, const char *key, size_t len) 316 { 317 struct hash_entry *p; 318 319 p = hash_lookup (table, key, len, NULL, NULL); 320 if (p == NULL) 321 return NULL; 322 323 return p->data; 324 } 325 326 /* Delete an entry from a hash table. This returns the value stored 327 for that entry, or NULL if there is no such entry. */ 328 329 void * 330 hash_delete (struct hash_control *table, const char *key, int freeme) 331 { 332 struct hash_entry *p; 333 struct hash_entry **list; 334 335 p = hash_lookup (table, key, strlen (key), &list, NULL); 336 if (p == NULL) 337 return NULL; 338 339 if (p != *list) 340 abort (); 341 342 #ifdef HASH_STATISTICS 343 ++table->deletions; 344 #endif 345 346 *list = p->next; 347 348 if (freeme) 349 obstack_free (&table->memory, p); 350 351 return p->data; 352 } 353 354 /* Traverse a hash table. Call the function on every entry in the 355 hash table. */ 356 357 void 358 hash_traverse (struct hash_control *table, 359 void (*pfn) (const char *key, void *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 375 void 376 hash_print_statistics (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. */ 424 int statbuf[STATBUFSIZE]; 425 426 /* Human farts here. */ 427 char answer[100]; 428 429 /* We test many hash tables at once. */ 430 char *hashtable[TABLES]; 431 432 /* Points to current hash_control. */ 433 char *h; 434 char **pp; 435 char *p; 436 char *name; 437 char *value; 438 int size; 439 int used; 440 char command; 441 442 /* Number 0:TABLES-1 of current hashed symbol table. */ 443 int number; 444 445 int 446 main () 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 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 544 char * 545 what (description) 546 char *description; 547 { 548 printf (" %s : ", description); 549 gets (answer); 550 return xstrdup (answer); 551 } 552 553 void 554 destroy (string, value) 555 char *string; 556 char *value; 557 { 558 free (string); 559 free (value); 560 } 561 562 void 563 applicatee (string, value) 564 char *string; 565 char *value; 566 { 567 printf ("%.20s-%.20s\n", string, value); 568 } 569 570 /* Determine number: what hash table to use. 571 Also determine h: points to hash_control. */ 572 573 void 574 whattable () 575 { 576 for (;;) 577 { 578 printf (" what hash table (%d:%d) ? ", 0, TABLES - 1); 579 gets (answer); 580 sscanf (answer, "%d", &number); 581 if (number >= 0 && number < TABLES) 582 { 583 h = hashtable[number]; 584 if (!h) 585 { 586 printf ("warning: current hash-table-#%d. has no hash-control\n", number); 587 } 588 return; 589 } 590 else 591 { 592 printf ("invalid hash table number: %d\n", number); 593 } 594 } 595 } 596 597 #endif /* TEST */ 598