1 /* Routines for name->symbol lookups in GDB. 2 3 Copyright (C) 2003-2013 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 /* Utility to add a list of symbols to a dictionary. 502 DICT must be an expandable dictionary. */ 503 504 void 505 dict_add_pending (struct dictionary *dict, const struct pending *symbol_list) 506 { 507 const struct pending *list; 508 int i; 509 510 for (list = symbol_list; list != NULL; list = list->next) 511 { 512 for (i = 0; i < list->nsyms; ++i) 513 dict_add_symbol (dict, list->symbol[i]); 514 } 515 } 516 517 /* Initialize ITERATOR to point at the first symbol in DICT, and 518 return that first symbol, or NULL if DICT is empty. */ 519 520 struct symbol * 521 dict_iterator_first (const struct dictionary *dict, 522 struct dict_iterator *iterator) 523 { 524 return (DICT_VECTOR (dict))->iterator_first (dict, iterator); 525 } 526 527 /* Advance ITERATOR, and return the next symbol, or NULL if there are 528 no more symbols. */ 529 530 struct symbol * 531 dict_iterator_next (struct dict_iterator *iterator) 532 { 533 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator))) 534 ->iterator_next (iterator); 535 } 536 537 struct symbol * 538 dict_iter_name_first (const struct dictionary *dict, 539 const char *name, 540 struct dict_iterator *iterator) 541 { 542 return dict_iter_match_first (dict, name, strcmp_iw, iterator); 543 } 544 545 struct symbol * 546 dict_iter_name_next (const char *name, struct dict_iterator *iterator) 547 { 548 return dict_iter_match_next (name, strcmp_iw, iterator); 549 } 550 551 struct symbol * 552 dict_iter_match_first (const struct dictionary *dict, 553 const char *name, symbol_compare_ftype *compare, 554 struct dict_iterator *iterator) 555 { 556 return (DICT_VECTOR (dict))->iter_match_first (dict, name, 557 compare, iterator); 558 } 559 560 struct symbol * 561 dict_iter_match_next (const char *name, symbol_compare_ftype *compare, 562 struct dict_iterator *iterator) 563 { 564 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator))) 565 ->iter_match_next (name, compare, iterator); 566 } 567 568 int 569 dict_size (const struct dictionary *dict) 570 { 571 return (DICT_VECTOR (dict))->size (dict); 572 } 573 574 /* Now come functions (well, one function, currently) that are 575 implemented generically by means of the vtable. Typically, they're 576 rarely used. */ 577 578 /* Test to see if DICT is empty. */ 579 580 int 581 dict_empty (struct dictionary *dict) 582 { 583 struct dict_iterator iter; 584 585 return (dict_iterator_first (dict, &iter) == NULL); 586 } 587 588 589 /* The functions implementing the dictionary interface. */ 590 591 /* Generic functions, where appropriate. */ 592 593 static void 594 free_obstack (struct dictionary *dict) 595 { 596 /* Do nothing! */ 597 } 598 599 static void 600 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym) 601 { 602 internal_error (__FILE__, __LINE__, 603 _("dict_add_symbol: non-expandable dictionary")); 604 } 605 606 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */ 607 608 static struct symbol * 609 iterator_first_hashed (const struct dictionary *dict, 610 struct dict_iterator *iterator) 611 { 612 DICT_ITERATOR_DICT (iterator) = dict; 613 DICT_ITERATOR_INDEX (iterator) = -1; 614 return iterator_hashed_advance (iterator); 615 } 616 617 static struct symbol * 618 iterator_next_hashed (struct dict_iterator *iterator) 619 { 620 struct symbol *next; 621 622 next = DICT_ITERATOR_CURRENT (iterator)->hash_next; 623 624 if (next == NULL) 625 return iterator_hashed_advance (iterator); 626 else 627 { 628 DICT_ITERATOR_CURRENT (iterator) = next; 629 return next; 630 } 631 } 632 633 static struct symbol * 634 iterator_hashed_advance (struct dict_iterator *iterator) 635 { 636 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 637 int nbuckets = DICT_HASHED_NBUCKETS (dict); 638 int i; 639 640 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i) 641 { 642 struct symbol *sym = DICT_HASHED_BUCKET (dict, i); 643 644 if (sym != NULL) 645 { 646 DICT_ITERATOR_INDEX (iterator) = i; 647 DICT_ITERATOR_CURRENT (iterator) = sym; 648 return sym; 649 } 650 } 651 652 return NULL; 653 } 654 655 static struct symbol * 656 iter_match_first_hashed (const struct dictionary *dict, const char *name, 657 symbol_compare_ftype *compare, 658 struct dict_iterator *iterator) 659 { 660 unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict); 661 struct symbol *sym; 662 663 DICT_ITERATOR_DICT (iterator) = dict; 664 665 /* Loop through the symbols in the given bucket, breaking when SYM 666 first matches. If SYM never matches, it will be set to NULL; 667 either way, we have the right return value. */ 668 669 for (sym = DICT_HASHED_BUCKET (dict, hash_index); 670 sym != NULL; 671 sym = sym->hash_next) 672 { 673 /* Warning: the order of arguments to compare matters! */ 674 if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0) 675 { 676 break; 677 } 678 679 } 680 681 DICT_ITERATOR_CURRENT (iterator) = sym; 682 return sym; 683 } 684 685 static struct symbol * 686 iter_match_next_hashed (const char *name, symbol_compare_ftype *compare, 687 struct dict_iterator *iterator) 688 { 689 struct symbol *next; 690 691 for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next; 692 next != NULL; 693 next = next->hash_next) 694 { 695 if (compare (SYMBOL_SEARCH_NAME (next), name) == 0) 696 break; 697 } 698 699 DICT_ITERATOR_CURRENT (iterator) = next; 700 701 return next; 702 } 703 704 /* Insert SYM into DICT. */ 705 706 static void 707 insert_symbol_hashed (struct dictionary *dict, 708 struct symbol *sym) 709 { 710 unsigned int hash_index; 711 struct symbol **buckets = DICT_HASHED_BUCKETS (dict); 712 713 hash_index = 714 dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict); 715 sym->hash_next = buckets[hash_index]; 716 buckets[hash_index] = sym; 717 } 718 719 static int 720 size_hashed (const struct dictionary *dict) 721 { 722 return DICT_HASHED_NBUCKETS (dict); 723 } 724 725 /* Functions only for DICT_HASHED_EXPANDABLE. */ 726 727 static void 728 free_hashed_expandable (struct dictionary *dict) 729 { 730 xfree (DICT_HASHED_BUCKETS (dict)); 731 xfree (dict); 732 } 733 734 static void 735 add_symbol_hashed_expandable (struct dictionary *dict, 736 struct symbol *sym) 737 { 738 int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict); 739 740 if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict)) 741 expand_hashtable (dict); 742 743 insert_symbol_hashed (dict, sym); 744 DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms; 745 } 746 747 static int 748 size_hashed_expandable (const struct dictionary *dict) 749 { 750 return DICT_HASHED_EXPANDABLE_NSYMS (dict); 751 } 752 753 static void 754 expand_hashtable (struct dictionary *dict) 755 { 756 int old_nbuckets = DICT_HASHED_NBUCKETS (dict); 757 struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict); 758 int new_nbuckets = 2*old_nbuckets + 1; 759 struct symbol **new_buckets = xcalloc (new_nbuckets, 760 sizeof (struct symbol *)); 761 int i; 762 763 DICT_HASHED_NBUCKETS (dict) = new_nbuckets; 764 DICT_HASHED_BUCKETS (dict) = new_buckets; 765 766 for (i = 0; i < old_nbuckets; ++i) 767 { 768 struct symbol *sym, *next_sym; 769 770 sym = old_buckets[i]; 771 if (sym != NULL) 772 { 773 for (next_sym = sym->hash_next; 774 next_sym != NULL; 775 next_sym = sym->hash_next) 776 { 777 insert_symbol_hashed (dict, sym); 778 sym = next_sym; 779 } 780 781 insert_symbol_hashed (dict, sym); 782 } 783 } 784 785 xfree (old_buckets); 786 } 787 788 /* Produce an unsigned hash value from STRING0 that is consistent 789 with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match. 790 That is, two identifiers equivalent according to any of those three 791 comparison operators hash to the same value. */ 792 793 static unsigned int 794 dict_hash (const char *string0) 795 { 796 /* The Ada-encoded version of a name P1.P2...Pn has either the form 797 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi 798 are lower-cased identifiers). The <suffix> (which can be empty) 799 encodes additional information about the denoted entity. This 800 routine hashes such names to msymbol_hash_iw(Pn). It actually 801 does this for a superset of both valid Pi and of <suffix>, but 802 in other cases it simply returns msymbol_hash_iw(STRING0). */ 803 804 const char *string; 805 unsigned int hash; 806 807 string = string0; 808 if (*string == '_') 809 { 810 if (strncmp (string, "_ada_", 5) == 0) 811 string += 5; 812 else 813 return msymbol_hash_iw (string0); 814 } 815 816 hash = 0; 817 while (*string) 818 { 819 /* Ignore "TKB" suffixes. 820 821 These are used by Ada for subprograms implementing a task body. 822 For instance for a task T inside package Pck, the name of the 823 subprogram implementing T's body is `pck__tTKB'. We need to 824 ignore the "TKB" suffix because searches for this task body 825 subprogram are going to be performed using `pck__t' (the encoded 826 version of the natural name `pck.t'). */ 827 if (strcmp (string, "TKB") == 0) 828 return hash; 829 830 switch (*string) 831 { 832 case '$': 833 case '.': 834 case 'X': 835 if (string0 == string) 836 return msymbol_hash_iw (string0); 837 else 838 return hash; 839 case ' ': 840 case '(': 841 return msymbol_hash_iw (string0); 842 case '_': 843 if (string[1] == '_' && string != string0) 844 { 845 int c = string[2]; 846 847 if ((c < 'a' || c > 'z') && c != 'O') 848 return hash; 849 hash = 0; 850 string += 2; 851 break; 852 } 853 /* FALL THROUGH */ 854 default: 855 hash = SYMBOL_HASH_NEXT (hash, *string); 856 string += 1; 857 break; 858 } 859 } 860 return hash; 861 } 862 863 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */ 864 865 static struct symbol * 866 iterator_first_linear (const struct dictionary *dict, 867 struct dict_iterator *iterator) 868 { 869 DICT_ITERATOR_DICT (iterator) = dict; 870 DICT_ITERATOR_INDEX (iterator) = 0; 871 return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL; 872 } 873 874 static struct symbol * 875 iterator_next_linear (struct dict_iterator *iterator) 876 { 877 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 878 879 if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict)) 880 return NULL; 881 else 882 return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator)); 883 } 884 885 static struct symbol * 886 iter_match_first_linear (const struct dictionary *dict, 887 const char *name, symbol_compare_ftype *compare, 888 struct dict_iterator *iterator) 889 { 890 DICT_ITERATOR_DICT (iterator) = dict; 891 DICT_ITERATOR_INDEX (iterator) = -1; 892 893 return iter_match_next_linear (name, compare, iterator); 894 } 895 896 static struct symbol * 897 iter_match_next_linear (const char *name, symbol_compare_ftype *compare, 898 struct dict_iterator *iterator) 899 { 900 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 901 int i, nsyms = DICT_LINEAR_NSYMS (dict); 902 struct symbol *sym, *retval = NULL; 903 904 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i) 905 { 906 sym = DICT_LINEAR_SYM (dict, i); 907 if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0) 908 { 909 retval = sym; 910 break; 911 } 912 } 913 914 DICT_ITERATOR_INDEX (iterator) = i; 915 916 return retval; 917 } 918 919 static int 920 size_linear (const struct dictionary *dict) 921 { 922 return DICT_LINEAR_NSYMS (dict); 923 } 924 925 /* Functions only for DICT_LINEAR_EXPANDABLE. */ 926 927 static void 928 free_linear_expandable (struct dictionary *dict) 929 { 930 xfree (DICT_LINEAR_SYMS (dict)); 931 xfree (dict); 932 } 933 934 935 static void 936 add_symbol_linear_expandable (struct dictionary *dict, 937 struct symbol *sym) 938 { 939 int nsyms = ++DICT_LINEAR_NSYMS (dict); 940 941 /* Do we have enough room? If not, grow it. */ 942 if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) 943 { 944 DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2; 945 DICT_LINEAR_SYMS (dict) 946 = xrealloc (DICT_LINEAR_SYMS (dict), 947 DICT_LINEAR_EXPANDABLE_CAPACITY (dict) 948 * sizeof (struct symbol *)); 949 } 950 951 DICT_LINEAR_SYM (dict, nsyms - 1) = sym; 952 } 953