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