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