1 /* Routines for name->symbol lookups in GDB. 2 3 Copyright (C) 2003, 2007, 2008, 2009, 2010, 2011 4 Free Software Foundation, Inc. 5 6 Contributed by David Carlton <carlton@bactrian.org> and by Kealia, 7 Inc. 8 9 This file is part of GDB. 10 11 This program is free software; you can redistribute it and/or modify 12 it under the terms of the GNU General Public License as published by 13 the Free Software Foundation; either version 3 of the License, or 14 (at your option) any later version. 15 16 This program is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License for more details. 20 21 You should have received a copy of the GNU General Public License 22 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 23 24 #include "defs.h" 25 #include <ctype.h> 26 #include "gdb_obstack.h" 27 #include "symtab.h" 28 #include "buildsym.h" 29 #include "gdb_assert.h" 30 #include "dictionary.h" 31 32 /* This file implements dictionaries, which are tables that associate 33 symbols to names. They are represented by an opaque type 'struct 34 dictionary'. That type has various internal implementations, which 35 you can choose between depending on what properties you need 36 (e.g. fast lookup, order-preserving, expandable). 37 38 Each dictionary starts with a 'virtual function table' that 39 contains the functions that actually implement the various 40 operations that dictionaries provide. (Note, however, that, for 41 the sake of client code, we also provide some functions that can be 42 implemented generically in terms of the functions in the vtable.) 43 44 To add a new dictionary implementation <impl>, what you should do 45 is: 46 47 * Add a new element DICT_<IMPL> to dict_type. 48 49 * Create a new structure dictionary_<impl>. If your new 50 implementation is a variant of an existing one, make sure that 51 their structs have the same initial data members. Define accessor 52 macros for your new data members. 53 54 * Implement all the functions in dict_vector as static functions, 55 whose name is the same as the corresponding member of dict_vector 56 plus _<impl>. You don't have to do this for those members where 57 you can reuse existing generic functions 58 (e.g. add_symbol_nonexpandable, free_obstack) or in the case where 59 your new implementation is a variant of an existing implementation 60 and where the variant doesn't affect the member function in 61 question. 62 63 * Define a static const struct dict_vector dict_<impl>_vector. 64 65 * Define a function dict_create_<impl> to create these 66 gizmos. Add its declaration to dictionary.h. 67 68 To add a new operation <op> on all existing implementations, what 69 you should do is: 70 71 * Add a new member <op> to struct dict_vector. 72 73 * If there is useful generic behavior <op>, define a static 74 function <op>_something_informative that implements that behavior. 75 (E.g. add_symbol_nonexpandable, free_obstack.) 76 77 * For every implementation <impl> that should have its own specific 78 behavior for <op>, define a static function <op>_<impl> 79 implementing it. 80 81 * Modify all existing dict_vector_<impl>'s to include the appropriate 82 member. 83 84 * Define a function dict_<op> that looks up <op> in the dict_vector 85 and calls the appropriate function. Add a declaration for 86 dict_<op> to dictionary.h. */ 87 88 /* An enum representing the various implementations of dictionaries. 89 Used only for debugging. */ 90 91 enum dict_type 92 { 93 /* Symbols are stored in a fixed-size hash table. */ 94 DICT_HASHED, 95 /* Symbols are stored in an expandable hash table. */ 96 DICT_HASHED_EXPANDABLE, 97 /* Symbols are stored in a fixed-size array. */ 98 DICT_LINEAR, 99 /* Symbols are stored in an expandable array. */ 100 DICT_LINEAR_EXPANDABLE 101 }; 102 103 /* The virtual function table. */ 104 105 struct dict_vector 106 { 107 /* The type of the dictionary. This is only here to make debugging 108 a bit easier; it's not actually used. */ 109 enum dict_type type; 110 /* The function to free a dictionary. */ 111 void (*free) (struct dictionary *dict); 112 /* Add a symbol to a dictionary, if possible. */ 113 void (*add_symbol) (struct dictionary *dict, struct symbol *sym); 114 /* Iterator functions. */ 115 struct symbol *(*iterator_first) (const struct dictionary *dict, 116 struct dict_iterator *iterator); 117 struct symbol *(*iterator_next) (struct dict_iterator *iterator); 118 /* Functions to iterate over symbols with a given name. */ 119 struct symbol *(*iter_match_first) (const struct dictionary *dict, 120 const char *name, 121 symbol_compare_ftype *equiv, 122 struct dict_iterator *iterator); 123 struct symbol *(*iter_match_next) (const char *name, 124 symbol_compare_ftype *equiv, 125 struct dict_iterator *iterator); 126 /* A size function, for maint print symtabs. */ 127 int (*size) (const struct dictionary *dict); 128 }; 129 130 /* Now comes the structs used to store the data for different 131 implementations. If two implementations have data in common, put 132 the common data at the top of their structs, ordered in the same 133 way. */ 134 135 struct dictionary_hashed 136 { 137 int nbuckets; 138 struct symbol **buckets; 139 }; 140 141 struct dictionary_hashed_expandable 142 { 143 /* How many buckets we currently have. */ 144 int nbuckets; 145 struct symbol **buckets; 146 /* How many syms we currently have; we need this so we will know 147 when to add more buckets. */ 148 int nsyms; 149 }; 150 151 struct dictionary_linear 152 { 153 int nsyms; 154 struct symbol **syms; 155 }; 156 157 struct dictionary_linear_expandable 158 { 159 /* How many symbols we currently have. */ 160 int nsyms; 161 struct symbol **syms; 162 /* How many symbols we can store before needing to reallocate. */ 163 int capacity; 164 }; 165 166 /* And now, the star of our show. */ 167 168 struct dictionary 169 { 170 const struct dict_vector *vector; 171 union 172 { 173 struct dictionary_hashed hashed; 174 struct dictionary_hashed_expandable hashed_expandable; 175 struct dictionary_linear linear; 176 struct dictionary_linear_expandable linear_expandable; 177 } 178 data; 179 }; 180 181 /* Accessor macros. */ 182 183 #define DICT_VECTOR(d) (d)->vector 184 185 /* These can be used for DICT_HASHED_EXPANDABLE, too. */ 186 187 #define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets 188 #define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets 189 #define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i] 190 191 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms 192 193 /* These can be used for DICT_LINEAR_EXPANDABLEs, too. */ 194 195 #define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms 196 #define DICT_LINEAR_SYMS(d) (d)->data.linear.syms 197 #define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i] 198 199 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \ 200 (d)->data.linear_expandable.capacity 201 202 /* The initial size of a DICT_*_EXPANDABLE dictionary. */ 203 204 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10 205 206 /* This calculates the number of buckets we'll use in a hashtable, 207 given the number of symbols that it will contain. */ 208 209 #define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1) 210 211 /* Accessor macros for dict_iterators; they're here rather than 212 dictionary.h because code elsewhere should treat dict_iterators as 213 opaque. */ 214 215 /* The dictionary that the iterator is associated to. */ 216 #define DICT_ITERATOR_DICT(iter) (iter)->dict 217 /* For linear dictionaries, the index of the last symbol returned; for 218 hashed dictionaries, the bucket of the last symbol returned. */ 219 #define DICT_ITERATOR_INDEX(iter) (iter)->index 220 /* For hashed dictionaries, this points to the last symbol returned; 221 otherwise, this is unused. */ 222 #define DICT_ITERATOR_CURRENT(iter) (iter)->current 223 224 /* Declarations of functions for vectors. */ 225 226 /* Functions that might work across a range of dictionary types. */ 227 228 static void add_symbol_nonexpandable (struct dictionary *dict, 229 struct symbol *sym); 230 231 static void free_obstack (struct dictionary *dict); 232 233 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE 234 dictionaries. */ 235 236 static struct symbol *iterator_first_hashed (const struct dictionary *dict, 237 struct dict_iterator *iterator); 238 239 static struct symbol *iterator_next_hashed (struct dict_iterator *iterator); 240 241 static struct symbol *iter_match_first_hashed (const struct dictionary *dict, 242 const char *name, 243 symbol_compare_ftype *compare, 244 struct dict_iterator *iterator); 245 246 static struct symbol *iter_match_next_hashed (const char *name, 247 symbol_compare_ftype *compare, 248 struct dict_iterator *iterator); 249 250 static unsigned int dict_hash (const char *string); 251 252 /* Functions only for DICT_HASHED. */ 253 254 static int size_hashed (const struct dictionary *dict); 255 256 /* Functions only for DICT_HASHED_EXPANDABLE. */ 257 258 static void free_hashed_expandable (struct dictionary *dict); 259 260 static void add_symbol_hashed_expandable (struct dictionary *dict, 261 struct symbol *sym); 262 263 static int size_hashed_expandable (const struct dictionary *dict); 264 265 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE 266 dictionaries. */ 267 268 static struct symbol *iterator_first_linear (const struct dictionary *dict, 269 struct dict_iterator *iterator); 270 271 static struct symbol *iterator_next_linear (struct dict_iterator *iterator); 272 273 static struct symbol *iter_match_first_linear (const struct dictionary *dict, 274 const char *name, 275 symbol_compare_ftype *compare, 276 struct dict_iterator *iterator); 277 278 static struct symbol *iter_match_next_linear (const char *name, 279 symbol_compare_ftype *compare, 280 struct dict_iterator *iterator); 281 282 static int size_linear (const struct dictionary *dict); 283 284 /* Functions only for DICT_LINEAR_EXPANDABLE. */ 285 286 static void free_linear_expandable (struct dictionary *dict); 287 288 static void add_symbol_linear_expandable (struct dictionary *dict, 289 struct symbol *sym); 290 291 /* Various vectors that we'll actually use. */ 292 293 static const struct dict_vector dict_hashed_vector = 294 { 295 DICT_HASHED, /* type */ 296 free_obstack, /* free */ 297 add_symbol_nonexpandable, /* add_symbol */ 298 iterator_first_hashed, /* iterator_first */ 299 iterator_next_hashed, /* iterator_next */ 300 iter_match_first_hashed, /* iter_name_first */ 301 iter_match_next_hashed, /* iter_name_next */ 302 size_hashed, /* size */ 303 }; 304 305 static const struct dict_vector dict_hashed_expandable_vector = 306 { 307 DICT_HASHED_EXPANDABLE, /* type */ 308 free_hashed_expandable, /* free */ 309 add_symbol_hashed_expandable, /* add_symbol */ 310 iterator_first_hashed, /* iterator_first */ 311 iterator_next_hashed, /* iterator_next */ 312 iter_match_first_hashed, /* iter_name_first */ 313 iter_match_next_hashed, /* iter_name_next */ 314 size_hashed_expandable, /* size */ 315 }; 316 317 static const struct dict_vector dict_linear_vector = 318 { 319 DICT_LINEAR, /* type */ 320 free_obstack, /* free */ 321 add_symbol_nonexpandable, /* add_symbol */ 322 iterator_first_linear, /* iterator_first */ 323 iterator_next_linear, /* iterator_next */ 324 iter_match_first_linear, /* iter_name_first */ 325 iter_match_next_linear, /* iter_name_next */ 326 size_linear, /* size */ 327 }; 328 329 static const struct dict_vector dict_linear_expandable_vector = 330 { 331 DICT_LINEAR_EXPANDABLE, /* type */ 332 free_linear_expandable, /* free */ 333 add_symbol_linear_expandable, /* add_symbol */ 334 iterator_first_linear, /* iterator_first */ 335 iterator_next_linear, /* iterator_next */ 336 iter_match_first_linear, /* iter_name_first */ 337 iter_match_next_linear, /* iter_name_next */ 338 size_linear, /* size */ 339 }; 340 341 /* Declarations of helper functions (i.e. ones that don't go into 342 vectors). */ 343 344 static struct symbol *iterator_hashed_advance (struct dict_iterator *iter); 345 346 static void insert_symbol_hashed (struct dictionary *dict, 347 struct symbol *sym); 348 349 static void expand_hashtable (struct dictionary *dict); 350 351 /* The creation functions. */ 352 353 /* Create a dictionary implemented via a fixed-size hashtable. All 354 memory it uses is allocated on OBSTACK; the environment is 355 initialized from SYMBOL_LIST. */ 356 357 struct dictionary * 358 dict_create_hashed (struct obstack *obstack, 359 const struct pending *symbol_list) 360 { 361 struct dictionary *retval; 362 int nsyms = 0, nbuckets, i; 363 struct symbol **buckets; 364 const struct pending *list_counter; 365 366 retval = obstack_alloc (obstack, sizeof (struct dictionary)); 367 DICT_VECTOR (retval) = &dict_hashed_vector; 368 369 /* Calculate the number of symbols, and allocate space for them. */ 370 for (list_counter = symbol_list; 371 list_counter != NULL; 372 list_counter = list_counter->next) 373 { 374 nsyms += list_counter->nsyms; 375 } 376 nbuckets = DICT_HASHTABLE_SIZE (nsyms); 377 DICT_HASHED_NBUCKETS (retval) = nbuckets; 378 buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *)); 379 memset (buckets, 0, nbuckets * sizeof (struct symbol *)); 380 DICT_HASHED_BUCKETS (retval) = buckets; 381 382 /* Now fill the buckets. */ 383 for (list_counter = symbol_list; 384 list_counter != NULL; 385 list_counter = list_counter->next) 386 { 387 for (i = list_counter->nsyms - 1; i >= 0; --i) 388 { 389 insert_symbol_hashed (retval, list_counter->symbol[i]); 390 } 391 } 392 393 return retval; 394 } 395 396 /* Create a dictionary implemented via a hashtable that grows as 397 necessary. The dictionary is initially empty; to add symbols to 398 it, call dict_add_symbol(). Call dict_free() when you're done with 399 it. */ 400 401 extern struct dictionary * 402 dict_create_hashed_expandable (void) 403 { 404 struct dictionary *retval; 405 406 retval = xmalloc (sizeof (struct dictionary)); 407 DICT_VECTOR (retval) = &dict_hashed_expandable_vector; 408 DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY; 409 DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY, 410 sizeof (struct symbol *)); 411 DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0; 412 413 return retval; 414 } 415 416 /* Create a dictionary implemented via a fixed-size array. All memory 417 it uses is allocated on OBSTACK; the environment is initialized 418 from the SYMBOL_LIST. The symbols are ordered in the same order 419 that they're found in SYMBOL_LIST. */ 420 421 struct dictionary * 422 dict_create_linear (struct obstack *obstack, 423 const struct pending *symbol_list) 424 { 425 struct dictionary *retval; 426 int nsyms = 0, i, j; 427 struct symbol **syms; 428 const struct pending *list_counter; 429 430 retval = obstack_alloc (obstack, sizeof (struct dictionary)); 431 DICT_VECTOR (retval) = &dict_linear_vector; 432 433 /* Calculate the number of symbols, and allocate space for them. */ 434 for (list_counter = symbol_list; 435 list_counter != NULL; 436 list_counter = list_counter->next) 437 { 438 nsyms += list_counter->nsyms; 439 } 440 DICT_LINEAR_NSYMS (retval) = nsyms; 441 syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *)); 442 DICT_LINEAR_SYMS (retval) = syms; 443 444 /* Now fill in the symbols. Start filling in from the back, so as 445 to preserve the original order of the symbols. */ 446 for (list_counter = symbol_list, j = nsyms - 1; 447 list_counter != NULL; 448 list_counter = list_counter->next) 449 { 450 for (i = list_counter->nsyms - 1; 451 i >= 0; 452 --i, --j) 453 { 454 syms[j] = list_counter->symbol[i]; 455 } 456 } 457 458 return retval; 459 } 460 461 /* Create a dictionary implemented via an array that grows as 462 necessary. The dictionary is initially empty; to add symbols to 463 it, call dict_add_symbol(). Call dict_free() when you're done with 464 it. */ 465 466 struct dictionary * 467 dict_create_linear_expandable (void) 468 { 469 struct dictionary *retval; 470 471 retval = xmalloc (sizeof (struct dictionary)); 472 DICT_VECTOR (retval) = &dict_linear_expandable_vector; 473 DICT_LINEAR_NSYMS (retval) = 0; 474 DICT_LINEAR_EXPANDABLE_CAPACITY (retval) 475 = DICT_EXPANDABLE_INITIAL_CAPACITY; 476 DICT_LINEAR_SYMS (retval) 477 = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval) 478 * sizeof (struct symbol *)); 479 480 return retval; 481 } 482 483 /* The functions providing the dictionary interface. */ 484 485 /* Free the memory used by a dictionary that's not on an obstack. (If 486 any.) */ 487 488 void 489 dict_free (struct dictionary *dict) 490 { 491 (DICT_VECTOR (dict))->free (dict); 492 } 493 494 /* Add SYM to DICT. DICT had better be expandable. */ 495 496 void 497 dict_add_symbol (struct dictionary *dict, struct symbol *sym) 498 { 499 (DICT_VECTOR (dict))->add_symbol (dict, sym); 500 } 501 502 /* Initialize ITERATOR to point at the first symbol in DICT, and 503 return that first symbol, or NULL if DICT is empty. */ 504 505 struct symbol * 506 dict_iterator_first (const struct dictionary *dict, 507 struct dict_iterator *iterator) 508 { 509 return (DICT_VECTOR (dict))->iterator_first (dict, iterator); 510 } 511 512 /* Advance ITERATOR, and return the next symbol, or NULL if there are 513 no more symbols. */ 514 515 struct symbol * 516 dict_iterator_next (struct dict_iterator *iterator) 517 { 518 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator))) 519 ->iterator_next (iterator); 520 } 521 522 struct symbol * 523 dict_iter_name_first (const struct dictionary *dict, 524 const char *name, 525 struct dict_iterator *iterator) 526 { 527 return dict_iter_match_first (dict, name, strcmp_iw, iterator); 528 } 529 530 struct symbol * 531 dict_iter_name_next (const char *name, struct dict_iterator *iterator) 532 { 533 return dict_iter_match_next (name, strcmp_iw, iterator); 534 } 535 536 struct symbol * 537 dict_iter_match_first (const struct dictionary *dict, 538 const char *name, symbol_compare_ftype *compare, 539 struct dict_iterator *iterator) 540 { 541 return (DICT_VECTOR (dict))->iter_match_first (dict, name, 542 compare, iterator); 543 } 544 545 struct symbol * 546 dict_iter_match_next (const char *name, symbol_compare_ftype *compare, 547 struct dict_iterator *iterator) 548 { 549 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator))) 550 ->iter_match_next (name, compare, iterator); 551 } 552 553 int 554 dict_size (const struct dictionary *dict) 555 { 556 return (DICT_VECTOR (dict))->size (dict); 557 } 558 559 /* Now come functions (well, one function, currently) that are 560 implemented generically by means of the vtable. Typically, they're 561 rarely used. */ 562 563 /* Test to see if DICT is empty. */ 564 565 int 566 dict_empty (struct dictionary *dict) 567 { 568 struct dict_iterator iter; 569 570 return (dict_iterator_first (dict, &iter) == NULL); 571 } 572 573 574 /* The functions implementing the dictionary interface. */ 575 576 /* Generic functions, where appropriate. */ 577 578 static void 579 free_obstack (struct dictionary *dict) 580 { 581 /* Do nothing! */ 582 } 583 584 static void 585 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym) 586 { 587 internal_error (__FILE__, __LINE__, 588 _("dict_add_symbol: non-expandable dictionary")); 589 } 590 591 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */ 592 593 static struct symbol * 594 iterator_first_hashed (const struct dictionary *dict, 595 struct dict_iterator *iterator) 596 { 597 DICT_ITERATOR_DICT (iterator) = dict; 598 DICT_ITERATOR_INDEX (iterator) = -1; 599 return iterator_hashed_advance (iterator); 600 } 601 602 static struct symbol * 603 iterator_next_hashed (struct dict_iterator *iterator) 604 { 605 struct symbol *next; 606 607 next = DICT_ITERATOR_CURRENT (iterator)->hash_next; 608 609 if (next == NULL) 610 return iterator_hashed_advance (iterator); 611 else 612 { 613 DICT_ITERATOR_CURRENT (iterator) = next; 614 return next; 615 } 616 } 617 618 static struct symbol * 619 iterator_hashed_advance (struct dict_iterator *iterator) 620 { 621 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 622 int nbuckets = DICT_HASHED_NBUCKETS (dict); 623 int i; 624 625 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i) 626 { 627 struct symbol *sym = DICT_HASHED_BUCKET (dict, i); 628 629 if (sym != NULL) 630 { 631 DICT_ITERATOR_INDEX (iterator) = i; 632 DICT_ITERATOR_CURRENT (iterator) = sym; 633 return sym; 634 } 635 } 636 637 return NULL; 638 } 639 640 static struct symbol * 641 iter_match_first_hashed (const struct dictionary *dict, const char *name, 642 symbol_compare_ftype *compare, 643 struct dict_iterator *iterator) 644 { 645 unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict); 646 struct symbol *sym; 647 648 DICT_ITERATOR_DICT (iterator) = dict; 649 650 /* Loop through the symbols in the given bucket, breaking when SYM 651 first matches. If SYM never matches, it will be set to NULL; 652 either way, we have the right return value. */ 653 654 for (sym = DICT_HASHED_BUCKET (dict, hash_index); 655 sym != NULL; 656 sym = sym->hash_next) 657 { 658 /* Warning: the order of arguments to compare matters! */ 659 if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0) 660 { 661 break; 662 } 663 664 } 665 666 DICT_ITERATOR_CURRENT (iterator) = sym; 667 return sym; 668 } 669 670 static struct symbol * 671 iter_match_next_hashed (const char *name, symbol_compare_ftype *compare, 672 struct dict_iterator *iterator) 673 { 674 struct symbol *next; 675 676 for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next; 677 next != NULL; 678 next = next->hash_next) 679 { 680 if (compare (SYMBOL_SEARCH_NAME (next), name) == 0) 681 break; 682 } 683 684 DICT_ITERATOR_CURRENT (iterator) = next; 685 686 return next; 687 } 688 689 /* Insert SYM into DICT. */ 690 691 static void 692 insert_symbol_hashed (struct dictionary *dict, 693 struct symbol *sym) 694 { 695 unsigned int hash_index; 696 struct symbol **buckets = DICT_HASHED_BUCKETS (dict); 697 698 hash_index = 699 dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict); 700 sym->hash_next = buckets[hash_index]; 701 buckets[hash_index] = sym; 702 } 703 704 static int 705 size_hashed (const struct dictionary *dict) 706 { 707 return DICT_HASHED_NBUCKETS (dict); 708 } 709 710 /* Functions only for DICT_HASHED_EXPANDABLE. */ 711 712 static void 713 free_hashed_expandable (struct dictionary *dict) 714 { 715 xfree (DICT_HASHED_BUCKETS (dict)); 716 xfree (dict); 717 } 718 719 static void 720 add_symbol_hashed_expandable (struct dictionary *dict, 721 struct symbol *sym) 722 { 723 int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict); 724 725 if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict)) 726 expand_hashtable (dict); 727 728 insert_symbol_hashed (dict, sym); 729 DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms; 730 } 731 732 static int 733 size_hashed_expandable (const struct dictionary *dict) 734 { 735 return DICT_HASHED_EXPANDABLE_NSYMS (dict); 736 } 737 738 static void 739 expand_hashtable (struct dictionary *dict) 740 { 741 int old_nbuckets = DICT_HASHED_NBUCKETS (dict); 742 struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict); 743 int new_nbuckets = 2*old_nbuckets + 1; 744 struct symbol **new_buckets = xcalloc (new_nbuckets, 745 sizeof (struct symbol *)); 746 int i; 747 748 DICT_HASHED_NBUCKETS (dict) = new_nbuckets; 749 DICT_HASHED_BUCKETS (dict) = new_buckets; 750 751 for (i = 0; i < old_nbuckets; ++i) 752 { 753 struct symbol *sym, *next_sym; 754 755 sym = old_buckets[i]; 756 if (sym != NULL) 757 { 758 for (next_sym = sym->hash_next; 759 next_sym != NULL; 760 next_sym = sym->hash_next) 761 { 762 insert_symbol_hashed (dict, sym); 763 sym = next_sym; 764 } 765 766 insert_symbol_hashed (dict, sym); 767 } 768 } 769 770 xfree (old_buckets); 771 } 772 773 /* Produce an unsigned hash value from STRING0 that is consistent 774 with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match. 775 That is, two identifiers equivalent according to any of those three 776 comparison operators hash to the same value. */ 777 778 static unsigned int 779 dict_hash (const char *string0) 780 { 781 /* The Ada-encoded version of a name P1.P2...Pn has either the form 782 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi 783 are lower-cased identifiers). The <suffix> (which can be empty) 784 encodes additional information about the denoted entity. This 785 routine hashes such names to msymbol_hash_iw(Pn). It actually 786 does this for a superset of both valid Pi and of <suffix>, but 787 in other cases it simply returns msymbol_hash_iw(STRING0). */ 788 789 const char *string; 790 unsigned int hash; 791 792 string = string0; 793 if (*string == '_') 794 { 795 if (strncmp (string, "_ada_", 5) == 0) 796 string += 5; 797 else 798 return msymbol_hash_iw (string0); 799 } 800 801 hash = 0; 802 while (*string) 803 { 804 switch (*string) 805 { 806 case '$': 807 case '.': 808 case 'X': 809 if (string0 == string) 810 return msymbol_hash_iw (string0); 811 else 812 return hash; 813 case ' ': 814 case '(': 815 return msymbol_hash_iw (string0); 816 case '_': 817 if (string[1] == '_' && string != string0) 818 { 819 int c = string[2]; 820 821 if ((c < 'a' || c > 'z') && c != 'O') 822 return hash; 823 hash = 0; 824 string += 2; 825 break; 826 } 827 /* FALL THROUGH */ 828 default: 829 hash = hash * 67 + *string - 113; 830 string += 1; 831 break; 832 } 833 } 834 return hash; 835 } 836 837 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */ 838 839 static struct symbol * 840 iterator_first_linear (const struct dictionary *dict, 841 struct dict_iterator *iterator) 842 { 843 DICT_ITERATOR_DICT (iterator) = dict; 844 DICT_ITERATOR_INDEX (iterator) = 0; 845 return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL; 846 } 847 848 static struct symbol * 849 iterator_next_linear (struct dict_iterator *iterator) 850 { 851 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 852 853 if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict)) 854 return NULL; 855 else 856 return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator)); 857 } 858 859 static struct symbol * 860 iter_match_first_linear (const struct dictionary *dict, 861 const char *name, symbol_compare_ftype *compare, 862 struct dict_iterator *iterator) 863 { 864 DICT_ITERATOR_DICT (iterator) = dict; 865 DICT_ITERATOR_INDEX (iterator) = -1; 866 867 return iter_match_next_linear (name, compare, iterator); 868 } 869 870 static struct symbol * 871 iter_match_next_linear (const char *name, symbol_compare_ftype *compare, 872 struct dict_iterator *iterator) 873 { 874 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 875 int i, nsyms = DICT_LINEAR_NSYMS (dict); 876 struct symbol *sym, *retval = NULL; 877 878 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i) 879 { 880 sym = DICT_LINEAR_SYM (dict, i); 881 if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0) 882 { 883 retval = sym; 884 break; 885 } 886 } 887 888 DICT_ITERATOR_INDEX (iterator) = i; 889 890 return retval; 891 } 892 893 static int 894 size_linear (const struct dictionary *dict) 895 { 896 return DICT_LINEAR_NSYMS (dict); 897 } 898 899 /* Functions only for DICT_LINEAR_EXPANDABLE. */ 900 901 static void 902 free_linear_expandable (struct dictionary *dict) 903 { 904 xfree (DICT_LINEAR_SYMS (dict)); 905 xfree (dict); 906 } 907 908 909 static void 910 add_symbol_linear_expandable (struct dictionary *dict, 911 struct symbol *sym) 912 { 913 int nsyms = ++DICT_LINEAR_NSYMS (dict); 914 915 /* Do we have enough room? If not, grow it. */ 916 if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) 917 { 918 DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2; 919 DICT_LINEAR_SYMS (dict) 920 = xrealloc (DICT_LINEAR_SYMS (dict), 921 DICT_LINEAR_EXPANDABLE_CAPACITY (dict) 922 * sizeof (struct symbol *)); 923 } 924 925 DICT_LINEAR_SYM (dict, nsyms - 1) = sym; 926 } 927