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