1130803Smarcel/* Routines for name->symbol lookups in GDB. 2130803Smarcel 3130803Smarcel Copyright 2003 Free Software Foundation, Inc. 4130803Smarcel 5130803Smarcel Contributed by David Carlton <carlton@bactrian.org> and by Kealia, 6130803Smarcel Inc. 7130803Smarcel 8130803Smarcel This file is part of GDB. 9130803Smarcel 10130803Smarcel This program is free software; you can redistribute it and/or modify 11130803Smarcel it under the terms of the GNU General Public License as published by 12130803Smarcel the Free Software Foundation; either version 2 of the License, or (at 13130803Smarcel your option) any later version. 14130803Smarcel 15130803Smarcel This program is distributed in the hope that it will be useful, but 16130803Smarcel WITHOUT ANY WARRANTY; without even the implied warranty of 17130803Smarcel MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 18130803Smarcel General Public License for more details. 19130803Smarcel 20130803Smarcel You should have received a copy of the GNU General Public License 21130803Smarcel along with this program; if not, write to the Free Software 22130803Smarcel Foundation, Inc., 59 Temple Place - Suite 330, 23130803Smarcel Boston, MA 02111-1307, USA. */ 24130803Smarcel 25130803Smarcel#include "defs.h" 26130803Smarcel#include "gdb_obstack.h" 27130803Smarcel#include "symtab.h" 28130803Smarcel#include "buildsym.h" 29130803Smarcel#include "gdb_assert.h" 30130803Smarcel#include "dictionary.h" 31130803Smarcel 32130803Smarcel/* This file implements dictionaries, which are tables that associate 33130803Smarcel symbols to names. They are represented by an opaque type 'struct 34130803Smarcel dictionary'. That type has various internal implementations, which 35130803Smarcel you can choose between depending on what properties you need 36130803Smarcel (e.g. fast lookup, order-preserving, expandable). 37130803Smarcel 38130803Smarcel Each dictionary starts with a 'virtual function table' that 39130803Smarcel contains the functions that actually implement the various 40130803Smarcel operations that dictionaries provide. (Note, however, that, for 41130803Smarcel the sake of client code, we also provide some functions that can be 42130803Smarcel implemented generically in terms of the functions in the vtable.) 43130803Smarcel 44130803Smarcel To add a new dictionary implementation <impl>, what you should do 45130803Smarcel is: 46130803Smarcel 47130803Smarcel * Add a new element DICT_<IMPL> to dict_type. 48130803Smarcel 49130803Smarcel * Create a new structure dictionary_<impl>. If your new 50130803Smarcel implementation is a variant of an existing one, make sure that 51130803Smarcel their structs have the same initial data members. Define accessor 52130803Smarcel macros for your new data members. 53130803Smarcel 54130803Smarcel * Implement all the functions in dict_vector as static functions, 55130803Smarcel whose name is the same as the corresponding member of dict_vector 56130803Smarcel plus _<impl>. You don't have to do this for those members where 57130803Smarcel you can reuse existing generic functions 58130803Smarcel (e.g. add_symbol_nonexpandable, free_obstack) or in the case where 59130803Smarcel your new implementation is a variant of an existing implementation 60130803Smarcel and where the variant doesn't affect the member function in 61130803Smarcel question. 62130803Smarcel 63130803Smarcel * Define a static const struct dict_vector dict_<impl>_vector. 64130803Smarcel 65130803Smarcel * Define a function dict_create_<impl> to create these 66130803Smarcel gizmos. Add its declaration to dictionary.h. 67130803Smarcel 68130803Smarcel To add a new operation <op> on all existing implementations, what 69130803Smarcel you should do is: 70130803Smarcel 71130803Smarcel * Add a new member <op> to struct dict_vector. 72130803Smarcel 73130803Smarcel * If there is useful generic behavior <op>, define a static 74130803Smarcel function <op>_something_informative that implements that behavior. 75130803Smarcel (E.g. add_symbol_nonexpandable, free_obstack.) 76130803Smarcel 77130803Smarcel * For every implementation <impl> that should have its own specific 78130803Smarcel behavior for <op>, define a static function <op>_<impl> 79130803Smarcel implementing it. 80130803Smarcel 81130803Smarcel * Modify all existing dict_vector_<impl>'s to include the appropriate 82130803Smarcel member. 83130803Smarcel 84130803Smarcel * Define a function dict_<op> that looks up <op> in the dict_vector 85130803Smarcel and calls the appropriate function. Add a declaration for 86130803Smarcel dict_<op> to dictionary.h. 87130803Smarcel 88130803Smarcel*/ 89130803Smarcel 90130803Smarcel/* An enum representing the various implementations of dictionaries. 91130803Smarcel Used only for debugging. */ 92130803Smarcel 93130803Smarcelenum dict_type 94130803Smarcel { 95130803Smarcel /* Symbols are stored in a fixed-size hash table. */ 96130803Smarcel DICT_HASHED, 97130803Smarcel /* Symbols are stored in an expandable hash table. */ 98130803Smarcel DICT_HASHED_EXPANDABLE, 99130803Smarcel /* Symbols are stored in a fixed-size array. */ 100130803Smarcel DICT_LINEAR, 101130803Smarcel /* Symbols are stored in an expandable array. */ 102130803Smarcel DICT_LINEAR_EXPANDABLE 103130803Smarcel }; 104130803Smarcel 105130803Smarcel/* The virtual function table. */ 106130803Smarcel 107130803Smarcelstruct dict_vector 108130803Smarcel{ 109130803Smarcel /* The type of the dictionary. This is only here to make debugging 110130803Smarcel a bit easier; it's not actually used. */ 111130803Smarcel enum dict_type type; 112130803Smarcel /* The function to free a dictionary. */ 113130803Smarcel void (*free) (struct dictionary *dict); 114130803Smarcel /* Add a symbol to a dictionary, if possible. */ 115130803Smarcel void (*add_symbol) (struct dictionary *dict, struct symbol *sym); 116130803Smarcel /* Iterator functions. */ 117130803Smarcel struct symbol *(*iterator_first) (const struct dictionary *dict, 118130803Smarcel struct dict_iterator *iterator); 119130803Smarcel struct symbol *(*iterator_next) (struct dict_iterator *iterator); 120130803Smarcel /* Functions to iterate over symbols with a given name. */ 121130803Smarcel struct symbol *(*iter_name_first) (const struct dictionary *dict, 122130803Smarcel const char *name, 123130803Smarcel struct dict_iterator *iterator); 124130803Smarcel struct symbol *(*iter_name_next) (const char *name, 125130803Smarcel struct dict_iterator *iterator); 126130803Smarcel /* A size function, for maint print symtabs. */ 127130803Smarcel int (*size) (const struct dictionary *dict); 128130803Smarcel}; 129130803Smarcel 130130803Smarcel/* Now comes the structs used to store the data for different 131130803Smarcel implementations. If two implementations have data in common, put 132130803Smarcel the common data at the top of their structs, ordered in the same 133130803Smarcel way. */ 134130803Smarcel 135130803Smarcelstruct dictionary_hashed 136130803Smarcel{ 137130803Smarcel int nbuckets; 138130803Smarcel struct symbol **buckets; 139130803Smarcel}; 140130803Smarcel 141130803Smarcelstruct dictionary_hashed_expandable 142130803Smarcel{ 143130803Smarcel /* How many buckets we currently have. */ 144130803Smarcel int nbuckets; 145130803Smarcel struct symbol **buckets; 146130803Smarcel /* How many syms we currently have; we need this so we will know 147130803Smarcel when to add more buckets. */ 148130803Smarcel int nsyms; 149130803Smarcel}; 150130803Smarcel 151130803Smarcelstruct dictionary_linear 152130803Smarcel{ 153130803Smarcel int nsyms; 154130803Smarcel struct symbol **syms; 155130803Smarcel}; 156130803Smarcel 157130803Smarcelstruct dictionary_linear_expandable 158130803Smarcel{ 159130803Smarcel /* How many symbols we currently have. */ 160130803Smarcel int nsyms; 161130803Smarcel struct symbol **syms; 162130803Smarcel /* How many symbols we can store before needing to reallocate. */ 163130803Smarcel int capacity; 164130803Smarcel}; 165130803Smarcel 166130803Smarcel/* And now, the star of our show. */ 167130803Smarcel 168130803Smarcelstruct dictionary 169130803Smarcel{ 170130803Smarcel const struct dict_vector *vector; 171130803Smarcel union 172130803Smarcel { 173130803Smarcel struct dictionary_hashed hashed; 174130803Smarcel struct dictionary_hashed_expandable hashed_expandable; 175130803Smarcel struct dictionary_linear linear; 176130803Smarcel struct dictionary_linear_expandable linear_expandable; 177130803Smarcel } 178130803Smarcel data; 179130803Smarcel}; 180130803Smarcel 181130803Smarcel/* Accessor macros. */ 182130803Smarcel 183130803Smarcel#define DICT_VECTOR(d) (d)->vector 184130803Smarcel 185130803Smarcel/* These can be used for DICT_HASHED_EXPANDABLE, too. */ 186130803Smarcel 187130803Smarcel#define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets 188130803Smarcel#define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets 189130803Smarcel#define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i] 190130803Smarcel 191130803Smarcel#define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms 192130803Smarcel 193130803Smarcel/* These can be used for DICT_LINEAR_EXPANDABLEs, too. */ 194130803Smarcel 195130803Smarcel#define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms 196130803Smarcel#define DICT_LINEAR_SYMS(d) (d)->data.linear.syms 197130803Smarcel#define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i] 198130803Smarcel 199130803Smarcel#define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \ 200130803Smarcel (d)->data.linear_expandable.capacity 201130803Smarcel 202130803Smarcel/* The initial size of a DICT_*_EXPANDABLE dictionary. */ 203130803Smarcel 204130803Smarcel#define DICT_EXPANDABLE_INITIAL_CAPACITY 10 205130803Smarcel 206130803Smarcel/* This calculates the number of buckets we'll use in a hashtable, 207130803Smarcel given the number of symbols that it will contain. */ 208130803Smarcel 209130803Smarcel#define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1) 210130803Smarcel 211130803Smarcel/* Accessor macros for dict_iterators; they're here rather than 212130803Smarcel dictionary.h because code elsewhere should treat dict_iterators as 213130803Smarcel opaque. */ 214130803Smarcel 215130803Smarcel/* The dictionary that the iterator is associated to. */ 216130803Smarcel#define DICT_ITERATOR_DICT(iter) (iter)->dict 217130803Smarcel/* For linear dictionaries, the index of the last symbol returned; for 218130803Smarcel hashed dictionaries, the bucket of the last symbol returned. */ 219130803Smarcel#define DICT_ITERATOR_INDEX(iter) (iter)->index 220130803Smarcel/* For hashed dictionaries, this points to the last symbol returned; 221130803Smarcel otherwise, this is unused. */ 222130803Smarcel#define DICT_ITERATOR_CURRENT(iter) (iter)->current 223130803Smarcel 224130803Smarcel/* Declarations of functions for vectors. */ 225130803Smarcel 226130803Smarcel/* Functions that might work across a range of dictionary types. */ 227130803Smarcel 228130803Smarcelstatic void add_symbol_nonexpandable (struct dictionary *dict, 229130803Smarcel struct symbol *sym); 230130803Smarcel 231130803Smarcelstatic void free_obstack (struct dictionary *dict); 232130803Smarcel 233130803Smarcel/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE 234130803Smarcel dictionaries. */ 235130803Smarcel 236130803Smarcelstatic struct symbol *iterator_first_hashed (const struct dictionary *dict, 237130803Smarcel struct dict_iterator *iterator); 238130803Smarcel 239130803Smarcelstatic struct symbol *iterator_next_hashed (struct dict_iterator *iterator); 240130803Smarcel 241130803Smarcelstatic struct symbol *iter_name_first_hashed (const struct dictionary *dict, 242130803Smarcel const char *name, 243130803Smarcel struct dict_iterator *iterator); 244130803Smarcel 245130803Smarcelstatic struct symbol *iter_name_next_hashed (const char *name, 246130803Smarcel struct dict_iterator *iterator); 247130803Smarcel 248130803Smarcel/* Functions only for DICT_HASHED. */ 249130803Smarcel 250130803Smarcelstatic int size_hashed (const struct dictionary *dict); 251130803Smarcel 252130803Smarcel/* Functions only for DICT_HASHED_EXPANDABLE. */ 253130803Smarcel 254130803Smarcelstatic void free_hashed_expandable (struct dictionary *dict); 255130803Smarcel 256130803Smarcelstatic void add_symbol_hashed_expandable (struct dictionary *dict, 257130803Smarcel struct symbol *sym); 258130803Smarcel 259130803Smarcelstatic int size_hashed_expandable (const struct dictionary *dict); 260130803Smarcel 261130803Smarcel/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE 262130803Smarcel dictionaries. */ 263130803Smarcel 264130803Smarcelstatic struct symbol *iterator_first_linear (const struct dictionary *dict, 265130803Smarcel struct dict_iterator *iterator); 266130803Smarcel 267130803Smarcelstatic struct symbol *iterator_next_linear (struct dict_iterator *iterator); 268130803Smarcel 269130803Smarcelstatic struct symbol *iter_name_first_linear (const struct dictionary *dict, 270130803Smarcel const char *name, 271130803Smarcel struct dict_iterator *iterator); 272130803Smarcel 273130803Smarcelstatic struct symbol *iter_name_next_linear (const char *name, 274130803Smarcel struct dict_iterator *iterator); 275130803Smarcel 276130803Smarcelstatic int size_linear (const struct dictionary *dict); 277130803Smarcel 278130803Smarcel/* Functions only for DICT_LINEAR_EXPANDABLE. */ 279130803Smarcel 280130803Smarcelstatic void free_linear_expandable (struct dictionary *dict); 281130803Smarcel 282130803Smarcelstatic void add_symbol_linear_expandable (struct dictionary *dict, 283130803Smarcel struct symbol *sym); 284130803Smarcel 285130803Smarcel/* Various vectors that we'll actually use. */ 286130803Smarcel 287130803Smarcelstatic const struct dict_vector dict_hashed_vector = 288130803Smarcel { 289130803Smarcel DICT_HASHED, /* type */ 290130803Smarcel free_obstack, /* free */ 291130803Smarcel add_symbol_nonexpandable, /* add_symbol */ 292130803Smarcel iterator_first_hashed, /* iteractor_first */ 293130803Smarcel iterator_next_hashed, /* iterator_next */ 294130803Smarcel iter_name_first_hashed, /* iter_name_first */ 295130803Smarcel iter_name_next_hashed, /* iter_name_next */ 296130803Smarcel size_hashed, /* size */ 297130803Smarcel }; 298130803Smarcel 299130803Smarcelstatic const struct dict_vector dict_hashed_expandable_vector = 300130803Smarcel { 301130803Smarcel DICT_HASHED_EXPANDABLE, /* type */ 302130803Smarcel free_hashed_expandable, /* free */ 303130803Smarcel add_symbol_hashed_expandable, /* add_symbol */ 304130803Smarcel iterator_first_hashed, /* iteractor_first */ 305130803Smarcel iterator_next_hashed, /* iterator_next */ 306130803Smarcel iter_name_first_hashed, /* iter_name_first */ 307130803Smarcel iter_name_next_hashed, /* iter_name_next */ 308130803Smarcel size_hashed_expandable, /* size */ 309130803Smarcel }; 310130803Smarcel 311130803Smarcelstatic const struct dict_vector dict_linear_vector = 312130803Smarcel { 313130803Smarcel DICT_LINEAR, /* type */ 314130803Smarcel free_obstack, /* free */ 315130803Smarcel add_symbol_nonexpandable, /* add_symbol */ 316130803Smarcel iterator_first_linear, /* iteractor_first */ 317130803Smarcel iterator_next_linear, /* iterator_next */ 318130803Smarcel iter_name_first_linear, /* iter_name_first */ 319130803Smarcel iter_name_next_linear, /* iter_name_next */ 320130803Smarcel size_linear, /* size */ 321130803Smarcel }; 322130803Smarcel 323130803Smarcelstatic const struct dict_vector dict_linear_expandable_vector = 324130803Smarcel { 325130803Smarcel DICT_LINEAR_EXPANDABLE, /* type */ 326130803Smarcel free_linear_expandable, /* free */ 327130803Smarcel add_symbol_linear_expandable, /* add_symbol */ 328130803Smarcel iterator_first_linear, /* iteractor_first */ 329130803Smarcel iterator_next_linear, /* iterator_next */ 330130803Smarcel iter_name_first_linear, /* iter_name_first */ 331130803Smarcel iter_name_next_linear, /* iter_name_next */ 332130803Smarcel size_linear, /* size */ 333130803Smarcel }; 334130803Smarcel 335130803Smarcel/* Declarations of helper functions (i.e. ones that don't go into 336130803Smarcel vectors). */ 337130803Smarcel 338130803Smarcelstatic struct symbol *iterator_hashed_advance (struct dict_iterator *iter); 339130803Smarcel 340130803Smarcelstatic void insert_symbol_hashed (struct dictionary *dict, 341130803Smarcel struct symbol *sym); 342130803Smarcel 343130803Smarcelstatic void expand_hashtable (struct dictionary *dict); 344130803Smarcel 345130803Smarcel/* The creation functions. */ 346130803Smarcel 347130803Smarcel/* Create a dictionary implemented via a fixed-size hashtable. All 348130803Smarcel memory it uses is allocated on OBSTACK; the environment is 349130803Smarcel initialized from SYMBOL_LIST. */ 350130803Smarcel 351130803Smarcelstruct dictionary * 352130803Smarceldict_create_hashed (struct obstack *obstack, 353130803Smarcel const struct pending *symbol_list) 354130803Smarcel{ 355130803Smarcel struct dictionary *retval; 356130803Smarcel int nsyms = 0, nbuckets, i; 357130803Smarcel struct symbol **buckets; 358130803Smarcel const struct pending *list_counter; 359130803Smarcel 360130803Smarcel retval = obstack_alloc (obstack, sizeof (struct dictionary)); 361130803Smarcel DICT_VECTOR (retval) = &dict_hashed_vector; 362130803Smarcel 363130803Smarcel /* Calculate the number of symbols, and allocate space for them. */ 364130803Smarcel for (list_counter = symbol_list; 365130803Smarcel list_counter != NULL; 366130803Smarcel list_counter = list_counter->next) 367130803Smarcel { 368130803Smarcel nsyms += list_counter->nsyms; 369130803Smarcel } 370130803Smarcel nbuckets = DICT_HASHTABLE_SIZE (nsyms); 371130803Smarcel DICT_HASHED_NBUCKETS (retval) = nbuckets; 372130803Smarcel buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *)); 373130803Smarcel memset (buckets, 0, nbuckets * sizeof (struct symbol *)); 374130803Smarcel DICT_HASHED_BUCKETS (retval) = buckets; 375130803Smarcel 376130803Smarcel /* Now fill the buckets. */ 377130803Smarcel for (list_counter = symbol_list; 378130803Smarcel list_counter != NULL; 379130803Smarcel list_counter = list_counter->next) 380130803Smarcel { 381130803Smarcel for (i = list_counter->nsyms - 1; i >= 0; --i) 382130803Smarcel { 383130803Smarcel insert_symbol_hashed (retval, list_counter->symbol[i]); 384130803Smarcel } 385130803Smarcel } 386130803Smarcel 387130803Smarcel return retval; 388130803Smarcel} 389130803Smarcel 390130803Smarcel/* Create a dictionary implemented via a hashtable that grows as 391130803Smarcel necessary. The dictionary is initially empty; to add symbols to 392130803Smarcel it, call dict_add_symbol(). Call dict_free() when you're done with 393130803Smarcel it. */ 394130803Smarcel 395130803Smarcelextern struct dictionary * 396130803Smarceldict_create_hashed_expandable (void) 397130803Smarcel{ 398130803Smarcel struct dictionary *retval; 399130803Smarcel 400130803Smarcel retval = xmalloc (sizeof (struct dictionary)); 401130803Smarcel DICT_VECTOR (retval) = &dict_hashed_expandable_vector; 402130803Smarcel DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY; 403130803Smarcel DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY, 404130803Smarcel sizeof (struct symbol *)); 405130803Smarcel DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0; 406130803Smarcel 407130803Smarcel return retval; 408130803Smarcel} 409130803Smarcel 410130803Smarcel/* Create a dictionary implemented via a fixed-size array. All memory 411130803Smarcel it uses is allocated on OBSTACK; the environment is initialized 412130803Smarcel from the SYMBOL_LIST. The symbols are ordered in the same order 413130803Smarcel that they're found in SYMBOL_LIST. */ 414130803Smarcel 415130803Smarcelstruct dictionary * 416130803Smarceldict_create_linear (struct obstack *obstack, 417130803Smarcel const struct pending *symbol_list) 418130803Smarcel{ 419130803Smarcel struct dictionary *retval; 420130803Smarcel int nsyms = 0, i, j; 421130803Smarcel struct symbol **syms; 422130803Smarcel const struct pending *list_counter; 423130803Smarcel 424130803Smarcel retval = obstack_alloc (obstack, sizeof (struct dictionary)); 425130803Smarcel DICT_VECTOR (retval) = &dict_linear_vector; 426130803Smarcel 427130803Smarcel /* Calculate the number of symbols, and allocate space for them. */ 428130803Smarcel for (list_counter = symbol_list; 429130803Smarcel list_counter != NULL; 430130803Smarcel list_counter = list_counter->next) 431130803Smarcel { 432130803Smarcel nsyms += list_counter->nsyms; 433130803Smarcel } 434130803Smarcel DICT_LINEAR_NSYMS (retval) = nsyms; 435130803Smarcel syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *)); 436130803Smarcel DICT_LINEAR_SYMS (retval) = syms; 437130803Smarcel 438130803Smarcel /* Now fill in the symbols. Start filling in from the back, so as 439130803Smarcel to preserve the original order of the symbols. */ 440130803Smarcel for (list_counter = symbol_list, j = nsyms - 1; 441130803Smarcel list_counter != NULL; 442130803Smarcel list_counter = list_counter->next) 443130803Smarcel { 444130803Smarcel for (i = list_counter->nsyms - 1; 445130803Smarcel i >= 0; 446130803Smarcel --i, --j) 447130803Smarcel { 448130803Smarcel syms[j] = list_counter->symbol[i]; 449130803Smarcel } 450130803Smarcel } 451130803Smarcel 452130803Smarcel return retval; 453130803Smarcel} 454130803Smarcel 455130803Smarcel/* Create a dictionary implemented via an array that grows as 456130803Smarcel necessary. The dictionary is initially empty; to add symbols to 457130803Smarcel it, call dict_add_symbol(). Call dict_free() when you're done with 458130803Smarcel it. */ 459130803Smarcel 460130803Smarcelstruct dictionary * 461130803Smarceldict_create_linear_expandable (void) 462130803Smarcel{ 463130803Smarcel struct dictionary *retval; 464130803Smarcel 465130803Smarcel retval = xmalloc (sizeof (struct dictionary)); 466130803Smarcel DICT_VECTOR (retval) = &dict_linear_expandable_vector; 467130803Smarcel DICT_LINEAR_NSYMS (retval) = 0; 468130803Smarcel DICT_LINEAR_EXPANDABLE_CAPACITY (retval) 469130803Smarcel = DICT_EXPANDABLE_INITIAL_CAPACITY; 470130803Smarcel DICT_LINEAR_SYMS (retval) 471130803Smarcel = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval) 472130803Smarcel * sizeof (struct symbol *)); 473130803Smarcel 474130803Smarcel return retval; 475130803Smarcel} 476130803Smarcel 477130803Smarcel/* The functions providing the dictionary interface. */ 478130803Smarcel 479130803Smarcel/* Free the memory used by a dictionary that's not on an obstack. (If 480130803Smarcel any.) */ 481130803Smarcel 482130803Smarcelvoid 483130803Smarceldict_free (struct dictionary *dict) 484130803Smarcel{ 485130803Smarcel (DICT_VECTOR (dict))->free (dict); 486130803Smarcel} 487130803Smarcel 488130803Smarcel/* Add SYM to DICT. DICT had better be expandable. */ 489130803Smarcel 490130803Smarcelvoid 491130803Smarceldict_add_symbol (struct dictionary *dict, struct symbol *sym) 492130803Smarcel{ 493130803Smarcel (DICT_VECTOR (dict))->add_symbol (dict, sym); 494130803Smarcel} 495130803Smarcel 496130803Smarcel/* Initialize ITERATOR to point at the first symbol in DICT, and 497130803Smarcel return that first symbol, or NULL if DICT is empty. */ 498130803Smarcel 499130803Smarcelstruct symbol * 500130803Smarceldict_iterator_first (const struct dictionary *dict, 501130803Smarcel struct dict_iterator *iterator) 502130803Smarcel{ 503130803Smarcel return (DICT_VECTOR (dict))->iterator_first (dict, iterator); 504130803Smarcel} 505130803Smarcel 506130803Smarcel/* Advance ITERATOR, and return the next symbol, or NULL if there are 507130803Smarcel no more symbols. */ 508130803Smarcel 509130803Smarcelstruct symbol * 510130803Smarceldict_iterator_next (struct dict_iterator *iterator) 511130803Smarcel{ 512130803Smarcel return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator))) 513130803Smarcel ->iterator_next (iterator); 514130803Smarcel} 515130803Smarcel 516130803Smarcelstruct symbol * 517130803Smarceldict_iter_name_first (const struct dictionary *dict, 518130803Smarcel const char *name, 519130803Smarcel struct dict_iterator *iterator) 520130803Smarcel{ 521130803Smarcel return (DICT_VECTOR (dict))->iter_name_first (dict, name, iterator); 522130803Smarcel} 523130803Smarcel 524130803Smarcelstruct symbol * 525130803Smarceldict_iter_name_next (const char *name, struct dict_iterator *iterator) 526130803Smarcel{ 527130803Smarcel return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator))) 528130803Smarcel ->iter_name_next (name, iterator); 529130803Smarcel} 530130803Smarcel 531130803Smarcelint 532130803Smarceldict_size (const struct dictionary *dict) 533130803Smarcel{ 534130803Smarcel return (DICT_VECTOR (dict))->size (dict); 535130803Smarcel} 536130803Smarcel 537130803Smarcel/* Now come functions (well, one function, currently) that are 538130803Smarcel implemented generically by means of the vtable. Typically, they're 539130803Smarcel rarely used. */ 540130803Smarcel 541130803Smarcel/* Test to see if DICT is empty. */ 542130803Smarcel 543130803Smarcelint 544130803Smarceldict_empty (struct dictionary *dict) 545130803Smarcel{ 546130803Smarcel struct dict_iterator iter; 547130803Smarcel 548130803Smarcel return (dict_iterator_first (dict, &iter) == NULL); 549130803Smarcel} 550130803Smarcel 551130803Smarcel 552130803Smarcel/* The functions implementing the dictionary interface. */ 553130803Smarcel 554130803Smarcel/* Generic functions, where appropriate. */ 555130803Smarcel 556130803Smarcelstatic void 557130803Smarcelfree_obstack (struct dictionary *dict) 558130803Smarcel{ 559130803Smarcel /* Do nothing! */ 560130803Smarcel} 561130803Smarcel 562130803Smarcelstatic void 563130803Smarceladd_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym) 564130803Smarcel{ 565130803Smarcel internal_error (__FILE__, __LINE__, 566130803Smarcel "dict_add_symbol: non-expandable dictionary"); 567130803Smarcel} 568130803Smarcel 569130803Smarcel/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */ 570130803Smarcel 571130803Smarcelstatic struct symbol * 572130803Smarceliterator_first_hashed (const struct dictionary *dict, 573130803Smarcel struct dict_iterator *iterator) 574130803Smarcel{ 575130803Smarcel DICT_ITERATOR_DICT (iterator) = dict; 576130803Smarcel DICT_ITERATOR_INDEX (iterator) = -1; 577130803Smarcel return iterator_hashed_advance (iterator); 578130803Smarcel} 579130803Smarcel 580130803Smarcelstatic struct symbol * 581130803Smarceliterator_next_hashed (struct dict_iterator *iterator) 582130803Smarcel{ 583130803Smarcel const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 584130803Smarcel struct symbol *next; 585130803Smarcel 586130803Smarcel next = DICT_ITERATOR_CURRENT (iterator)->hash_next; 587130803Smarcel 588130803Smarcel if (next == NULL) 589130803Smarcel return iterator_hashed_advance (iterator); 590130803Smarcel else 591130803Smarcel { 592130803Smarcel DICT_ITERATOR_CURRENT (iterator) = next; 593130803Smarcel return next; 594130803Smarcel } 595130803Smarcel} 596130803Smarcel 597130803Smarcelstatic struct symbol * 598130803Smarceliterator_hashed_advance (struct dict_iterator *iterator) 599130803Smarcel{ 600130803Smarcel const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 601130803Smarcel int nbuckets = DICT_HASHED_NBUCKETS (dict); 602130803Smarcel int i; 603130803Smarcel 604130803Smarcel for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i) 605130803Smarcel { 606130803Smarcel struct symbol *sym = DICT_HASHED_BUCKET (dict, i); 607130803Smarcel 608130803Smarcel if (sym != NULL) 609130803Smarcel { 610130803Smarcel DICT_ITERATOR_INDEX (iterator) = i; 611130803Smarcel DICT_ITERATOR_CURRENT (iterator) = sym; 612130803Smarcel return sym; 613130803Smarcel } 614130803Smarcel } 615130803Smarcel 616130803Smarcel return NULL; 617130803Smarcel} 618130803Smarcel 619130803Smarcelstatic struct symbol * 620130803Smarceliter_name_first_hashed (const struct dictionary *dict, 621130803Smarcel const char *name, 622130803Smarcel struct dict_iterator *iterator) 623130803Smarcel{ 624130803Smarcel unsigned int hash_index 625130803Smarcel = msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict); 626130803Smarcel struct symbol *sym; 627130803Smarcel 628130803Smarcel DICT_ITERATOR_DICT (iterator) = dict; 629130803Smarcel 630130803Smarcel /* Loop through the symbols in the given bucket, breaking when SYM 631130803Smarcel first matches. If SYM never matches, it will be set to NULL; 632130803Smarcel either way, we have the right return value. */ 633130803Smarcel 634130803Smarcel for (sym = DICT_HASHED_BUCKET (dict, hash_index); 635130803Smarcel sym != NULL; 636130803Smarcel sym = sym->hash_next) 637130803Smarcel { 638130803Smarcel /* Warning: the order of arguments to strcmp_iw matters! */ 639130803Smarcel if (strcmp_iw (SYMBOL_NATURAL_NAME (sym), name) == 0) 640130803Smarcel { 641130803Smarcel break; 642130803Smarcel } 643130803Smarcel 644130803Smarcel } 645130803Smarcel 646130803Smarcel DICT_ITERATOR_CURRENT (iterator) = sym; 647130803Smarcel return sym; 648130803Smarcel} 649130803Smarcel 650130803Smarcelstatic struct symbol * 651130803Smarceliter_name_next_hashed (const char *name, struct dict_iterator *iterator) 652130803Smarcel{ 653130803Smarcel struct symbol *next; 654130803Smarcel 655130803Smarcel for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next; 656130803Smarcel next != NULL; 657130803Smarcel next = next->hash_next) 658130803Smarcel { 659130803Smarcel if (strcmp_iw (SYMBOL_NATURAL_NAME (next), name) == 0) 660130803Smarcel break; 661130803Smarcel } 662130803Smarcel 663130803Smarcel DICT_ITERATOR_CURRENT (iterator) = next; 664130803Smarcel 665130803Smarcel return next; 666130803Smarcel} 667130803Smarcel 668130803Smarcel/* Insert SYM into DICT. */ 669130803Smarcel 670130803Smarcelstatic void 671130803Smarcelinsert_symbol_hashed (struct dictionary *dict, 672130803Smarcel struct symbol *sym) 673130803Smarcel{ 674130803Smarcel unsigned int hash_index; 675130803Smarcel struct symbol **buckets = DICT_HASHED_BUCKETS (dict); 676130803Smarcel 677130803Smarcel hash_index = (msymbol_hash_iw (SYMBOL_NATURAL_NAME (sym)) 678130803Smarcel % DICT_HASHED_NBUCKETS (dict)); 679130803Smarcel sym->hash_next = buckets[hash_index]; 680130803Smarcel buckets[hash_index] = sym; 681130803Smarcel} 682130803Smarcel 683130803Smarcelstatic int 684130803Smarcelsize_hashed (const struct dictionary *dict) 685130803Smarcel{ 686130803Smarcel return DICT_HASHED_NBUCKETS (dict); 687130803Smarcel} 688130803Smarcel 689130803Smarcel/* Functions only for DICT_HASHED_EXPANDABLE. */ 690130803Smarcel 691130803Smarcelstatic void 692130803Smarcelfree_hashed_expandable (struct dictionary *dict) 693130803Smarcel{ 694130803Smarcel xfree (DICT_HASHED_BUCKETS (dict)); 695130803Smarcel xfree (dict); 696130803Smarcel} 697130803Smarcel 698130803Smarcelstatic void 699130803Smarceladd_symbol_hashed_expandable (struct dictionary *dict, 700130803Smarcel struct symbol *sym) 701130803Smarcel{ 702130803Smarcel int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict); 703130803Smarcel 704130803Smarcel if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict)) 705130803Smarcel expand_hashtable (dict); 706130803Smarcel 707130803Smarcel insert_symbol_hashed (dict, sym); 708130803Smarcel DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms; 709130803Smarcel} 710130803Smarcel 711130803Smarcelstatic int 712130803Smarcelsize_hashed_expandable (const struct dictionary *dict) 713130803Smarcel{ 714130803Smarcel return DICT_HASHED_EXPANDABLE_NSYMS (dict); 715130803Smarcel} 716130803Smarcel 717130803Smarcelstatic void 718130803Smarcelexpand_hashtable (struct dictionary *dict) 719130803Smarcel{ 720130803Smarcel int old_nbuckets = DICT_HASHED_NBUCKETS (dict); 721130803Smarcel struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict); 722130803Smarcel int new_nbuckets = 2*old_nbuckets + 1; 723130803Smarcel struct symbol **new_buckets = xcalloc (new_nbuckets, 724130803Smarcel sizeof (struct symbol *)); 725130803Smarcel int i; 726130803Smarcel 727130803Smarcel DICT_HASHED_NBUCKETS (dict) = new_nbuckets; 728130803Smarcel DICT_HASHED_BUCKETS (dict) = new_buckets; 729130803Smarcel 730130803Smarcel for (i = 0; i < old_nbuckets; ++i) { 731130803Smarcel struct symbol *sym, *next_sym; 732130803Smarcel 733130803Smarcel sym = old_buckets[i]; 734130803Smarcel if (sym != NULL) { 735130803Smarcel for (next_sym = sym->hash_next; 736130803Smarcel next_sym != NULL; 737130803Smarcel next_sym = sym->hash_next) { 738130803Smarcel insert_symbol_hashed (dict, sym); 739130803Smarcel sym = next_sym; 740130803Smarcel } 741130803Smarcel 742130803Smarcel insert_symbol_hashed (dict, sym); 743130803Smarcel } 744130803Smarcel } 745130803Smarcel 746130803Smarcel xfree (old_buckets); 747130803Smarcel} 748130803Smarcel 749130803Smarcel/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */ 750130803Smarcel 751130803Smarcelstatic struct symbol * 752130803Smarceliterator_first_linear (const struct dictionary *dict, 753130803Smarcel struct dict_iterator *iterator) 754130803Smarcel{ 755130803Smarcel DICT_ITERATOR_DICT (iterator) = dict; 756130803Smarcel DICT_ITERATOR_INDEX (iterator) = 0; 757130803Smarcel return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL; 758130803Smarcel} 759130803Smarcel 760130803Smarcelstatic struct symbol * 761130803Smarceliterator_next_linear (struct dict_iterator *iterator) 762130803Smarcel{ 763130803Smarcel const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 764130803Smarcel 765130803Smarcel if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict)) 766130803Smarcel return NULL; 767130803Smarcel else 768130803Smarcel return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator)); 769130803Smarcel} 770130803Smarcel 771130803Smarcelstatic struct symbol * 772130803Smarceliter_name_first_linear (const struct dictionary *dict, 773130803Smarcel const char *name, 774130803Smarcel struct dict_iterator *iterator) 775130803Smarcel{ 776130803Smarcel DICT_ITERATOR_DICT (iterator) = dict; 777130803Smarcel DICT_ITERATOR_INDEX (iterator) = -1; 778130803Smarcel 779130803Smarcel return iter_name_next_linear (name, iterator); 780130803Smarcel} 781130803Smarcel 782130803Smarcelstatic struct symbol * 783130803Smarceliter_name_next_linear (const char *name, struct dict_iterator *iterator) 784130803Smarcel{ 785130803Smarcel const struct dictionary *dict = DICT_ITERATOR_DICT (iterator); 786130803Smarcel int i, nsyms = DICT_LINEAR_NSYMS (dict); 787130803Smarcel struct symbol *sym, *retval = NULL; 788130803Smarcel 789130803Smarcel for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i) 790130803Smarcel { 791130803Smarcel sym = DICT_LINEAR_SYM (dict, i); 792130803Smarcel if (strcmp_iw (SYMBOL_NATURAL_NAME (sym), name) == 0) 793130803Smarcel { 794130803Smarcel retval = sym; 795130803Smarcel break; 796130803Smarcel } 797130803Smarcel } 798130803Smarcel 799130803Smarcel DICT_ITERATOR_INDEX (iterator) = i; 800130803Smarcel 801130803Smarcel return retval; 802130803Smarcel} 803130803Smarcel 804130803Smarcelstatic int 805130803Smarcelsize_linear (const struct dictionary *dict) 806130803Smarcel{ 807130803Smarcel return DICT_LINEAR_NSYMS (dict); 808130803Smarcel} 809130803Smarcel 810130803Smarcel/* Functions only for DICT_LINEAR_EXPANDABLE. */ 811130803Smarcel 812130803Smarcelstatic void 813130803Smarcelfree_linear_expandable (struct dictionary *dict) 814130803Smarcel{ 815130803Smarcel xfree (DICT_LINEAR_SYMS (dict)); 816130803Smarcel xfree (dict); 817130803Smarcel} 818130803Smarcel 819130803Smarcel 820130803Smarcelstatic void 821130803Smarceladd_symbol_linear_expandable (struct dictionary *dict, 822130803Smarcel struct symbol *sym) 823130803Smarcel{ 824130803Smarcel int nsyms = ++DICT_LINEAR_NSYMS (dict); 825130803Smarcel 826130803Smarcel /* Do we have enough room? If not, grow it. */ 827130803Smarcel if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) { 828130803Smarcel DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2; 829130803Smarcel DICT_LINEAR_SYMS (dict) 830130803Smarcel = xrealloc (DICT_LINEAR_SYMS (dict), 831130803Smarcel DICT_LINEAR_EXPANDABLE_CAPACITY (dict) 832130803Smarcel * sizeof (struct symbol *)); 833130803Smarcel } 834130803Smarcel 835130803Smarcel DICT_LINEAR_SYM (dict, nsyms - 1) = sym; 836130803Smarcel} 837