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