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 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. */ 423 int statbuf[STATBUFSIZE]; 424 425 /* Human farts here. */ 426 char answer[100]; 427 428 /* We test many hash tables at once. */ 429 char *hashtable[TABLES]; 430 431 /* Points to current hash_control. */ 432 char *h; 433 char **pp; 434 char *p; 435 char *name; 436 char *value; 437 int size; 438 int used; 439 char command; 440 441 /* Number 0:TABLES-1 of current hashed symbol table. */ 442 int number; 443 444 int 445 main () 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 command = TOLOWER (command); /* Ecch! */ 461 switch (command) 462 { 463 case '#': 464 printf ("old hash table #=%d.\n", number); 465 whattable (); 466 break; 467 case '?': 468 for (pp = hashtable; pp < hashtable + TABLES; pp++) 469 { 470 printf ("address of hash table #%d control block is %xx\n", 471 pp - hashtable, *pp); 472 } 473 break; 474 case 'a': 475 hash_traverse (h, applicatee); 476 break; 477 case 'd': 478 hash_traverse (h, destroy); 479 hash_die (h); 480 break; 481 case 'f': 482 p = hash_find (h, name = what ("symbol")); 483 printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT"); 484 break; 485 case 'h': 486 printf ("# show old, select new default hash table number\n"); 487 printf ("? display all hashtable control block addresses\n"); 488 printf ("a apply a simple display-er to each symbol in table\n"); 489 printf ("d die: destroy hashtable\n"); 490 printf ("f find value of nominated symbol\n"); 491 printf ("h this help\n"); 492 printf ("i insert value into symbol\n"); 493 printf ("j jam value into symbol\n"); 494 printf ("n new hashtable\n"); 495 printf ("r replace a value with another\n"); 496 printf ("s say what %% of table is used\n"); 497 printf ("q exit this program\n"); 498 printf ("x delete a symbol from table, report its value\n"); 499 break; 500 case 'i': 501 p = hash_insert (h, name = what ("symbol"), value = what ("value")); 502 if (p) 503 { 504 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, 505 p); 506 } 507 break; 508 case 'j': 509 p = hash_jam (h, name = what ("symbol"), value = what ("value")); 510 if (p) 511 { 512 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p); 513 } 514 break; 515 case 'n': 516 h = hashtable[number] = (char *) hash_new (); 517 break; 518 case 'q': 519 exit (EXIT_SUCCESS); 520 case 'r': 521 p = hash_replace (h, name = what ("symbol"), value = what ("value")); 522 printf ("old value was \"%s\"\n", p ? p : "{}"); 523 break; 524 case 's': 525 hash_say (h, statbuf, STATBUFSIZE); 526 for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++) 527 { 528 printf ("%d ", *ip); 529 } 530 printf ("\n"); 531 break; 532 case 'x': 533 p = hash_delete (h, name = what ("symbol")); 534 printf ("old value was \"%s\"\n", p ? p : "{}"); 535 break; 536 default: 537 printf ("I can't understand command \"%c\"\n", command); 538 break; 539 } 540 } 541 } 542 543 char * 544 what (description) 545 char *description; 546 { 547 printf (" %s : ", description); 548 gets (answer); 549 return xstrdup (answer); 550 } 551 552 void 553 destroy (string, value) 554 char *string; 555 char *value; 556 { 557 free (string); 558 free (value); 559 } 560 561 void 562 applicatee (string, value) 563 char *string; 564 char *value; 565 { 566 printf ("%.20s-%.20s\n", string, value); 567 } 568 569 /* Determine number: what hash table to use. 570 Also determine h: points to hash_control. */ 571 572 void 573 whattable () 574 { 575 for (;;) 576 { 577 printf (" what hash table (%d:%d) ? ", 0, TABLES - 1); 578 gets (answer); 579 sscanf (answer, "%d", &number); 580 if (number >= 0 && number < TABLES) 581 { 582 h = hashtable[number]; 583 if (!h) 584 { 585 printf ("warning: current hash-table-#%d. has no hash-control\n", number); 586 } 587 return; 588 } 589 else 590 { 591 printf ("invalid hash table number: %d\n", number); 592 } 593 } 594 } 595 596 #endif /* TEST */ 597
