1 /* Routines for name->symbol lookups in GDB.
3 Copyright (C) 2003, 2007-2012 Free Software Foundation, Inc.
5 Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
8 This file is part of GDB.
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.
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.
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/>. */
25 #include "gdb_obstack.h"
28 #include "gdb_assert.h"
29 #include "dictionary.h"
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).
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.)
43 To add a new dictionary implementation <impl>, what you should do
46 * Add a new element DICT_<IMPL> to dict_type.
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.
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
62 * Define a static const struct dict_vector dict_<impl>_vector.
64 * Define a function dict_create_<impl> to create these
65 gizmos. Add its declaration to dictionary.h.
67 To add a new operation <op> on all existing implementations, what
70 * Add a new member <op> to struct dict_vector.
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.)
76 * For every implementation <impl> that should have its own specific
77 behavior for <op>, define a static function <op>_<impl>
80 * Modify all existing dict_vector_<impl>'s to include the appropriate
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. */
87 /* An enum representing the various implementations of dictionaries.
88 Used only for debugging. */
92 /* Symbols are stored in a fixed-size hash table. */
94 /* Symbols are stored in an expandable hash table. */
95 DICT_HASHED_EXPANDABLE,
96 /* Symbols are stored in a fixed-size array. */
98 /* Symbols are stored in an expandable array. */
99 DICT_LINEAR_EXPANDABLE
102 /* The virtual function table. */
106 /* The type of the dictionary. This is only here to make debugging
107 a bit easier; it's not actually used. */
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,
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);
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
134 struct dictionary_hashed
137 struct symbol **buckets;
140 struct dictionary_hashed_expandable
142 /* How many buckets we currently have. */
144 struct symbol **buckets;
145 /* How many syms we currently have; we need this so we will know
146 when to add more buckets. */
150 struct dictionary_linear
153 struct symbol **syms;
156 struct dictionary_linear_expandable
158 /* How many symbols we currently have. */
160 struct symbol **syms;
161 /* How many symbols we can store before needing to reallocate. */
165 /* And now, the star of our show. */
169 const struct dict_vector *vector;
172 struct dictionary_hashed hashed;
173 struct dictionary_hashed_expandable hashed_expandable;
174 struct dictionary_linear linear;
175 struct dictionary_linear_expandable linear_expandable;
180 /* Accessor macros. */
182 #define DICT_VECTOR(d) (d)->vector
184 /* These can be used for DICT_HASHED_EXPANDABLE, too. */
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]
190 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
192 /* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
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]
198 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
199 (d)->data.linear_expandable.capacity
201 /* The initial size of a DICT_*_EXPANDABLE dictionary. */
203 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
205 /* This calculates the number of buckets we'll use in a hashtable,
206 given the number of symbols that it will contain. */
208 #define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
210 /* Accessor macros for dict_iterators; they're here rather than
211 dictionary.h because code elsewhere should treat dict_iterators as
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
223 /* Declarations of functions for vectors. */
225 /* Functions that might work across a range of dictionary types. */
227 static void add_symbol_nonexpandable (struct dictionary *dict,
230 static void free_obstack (struct dictionary *dict);
232 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
235 static struct symbol *iterator_first_hashed (const struct dictionary *dict,
236 struct dict_iterator *iterator);
238 static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
240 static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
242 symbol_compare_ftype *compare,
243 struct dict_iterator *iterator);
245 static struct symbol *iter_match_next_hashed (const char *name,
246 symbol_compare_ftype *compare,
247 struct dict_iterator *iterator);
249 static unsigned int dict_hash (const char *string);
251 /* Functions only for DICT_HASHED. */
253 static int size_hashed (const struct dictionary *dict);
255 /* Functions only for DICT_HASHED_EXPANDABLE. */
257 static void free_hashed_expandable (struct dictionary *dict);
259 static void add_symbol_hashed_expandable (struct dictionary *dict,
262 static int size_hashed_expandable (const struct dictionary *dict);
264 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
267 static struct symbol *iterator_first_linear (const struct dictionary *dict,
268 struct dict_iterator *iterator);
270 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
272 static struct symbol *iter_match_first_linear (const struct dictionary *dict,
274 symbol_compare_ftype *compare,
275 struct dict_iterator *iterator);
277 static struct symbol *iter_match_next_linear (const char *name,
278 symbol_compare_ftype *compare,
279 struct dict_iterator *iterator);
281 static int size_linear (const struct dictionary *dict);
283 /* Functions only for DICT_LINEAR_EXPANDABLE. */
285 static void free_linear_expandable (struct dictionary *dict);
287 static void add_symbol_linear_expandable (struct dictionary *dict,
290 /* Various vectors that we'll actually use. */
292 static const struct dict_vector dict_hashed_vector =
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 */
304 static const struct dict_vector dict_hashed_expandable_vector =
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 */
316 static const struct dict_vector dict_linear_vector =
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 */
328 static const struct dict_vector dict_linear_expandable_vector =
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 */
340 /* Declarations of helper functions (i.e. ones that don't go into
343 static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
345 static void insert_symbol_hashed (struct dictionary *dict,
348 static void expand_hashtable (struct dictionary *dict);
350 /* The creation functions. */
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. */
357 dict_create_hashed (struct obstack *obstack,
358 const struct pending *symbol_list)
360 struct dictionary *retval;
361 int nsyms = 0, nbuckets, i;
362 struct symbol **buckets;
363 const struct pending *list_counter;
365 retval = obstack_alloc (obstack, sizeof (struct dictionary));
366 DICT_VECTOR (retval) = &dict_hashed_vector;
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)
373 nsyms += list_counter->nsyms;
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;
381 /* Now fill the buckets. */
382 for (list_counter = symbol_list;
383 list_counter != NULL;
384 list_counter = list_counter->next)
386 for (i = list_counter->nsyms - 1; i >= 0; --i)
388 insert_symbol_hashed (retval, list_counter->symbol[i]);
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
400 extern struct dictionary *
401 dict_create_hashed_expandable (void)
403 struct dictionary *retval;
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;
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. */
421 dict_create_linear (struct obstack *obstack,
422 const struct pending *symbol_list)
424 struct dictionary *retval;
426 struct symbol **syms;
427 const struct pending *list_counter;
429 retval = obstack_alloc (obstack, sizeof (struct dictionary));
430 DICT_VECTOR (retval) = &dict_linear_vector;
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)
437 nsyms += list_counter->nsyms;
439 DICT_LINEAR_NSYMS (retval) = nsyms;
440 syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *));
441 DICT_LINEAR_SYMS (retval) = syms;
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)
449 for (i = list_counter->nsyms - 1;
453 syms[j] = list_counter->symbol[i];
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
466 dict_create_linear_expandable (void)
468 struct dictionary *retval;
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 *));
482 /* The functions providing the dictionary interface. */
484 /* Free the memory used by a dictionary that's not on an obstack. (If
488 dict_free (struct dictionary *dict)
490 (DICT_VECTOR (dict))->free (dict);
493 /* Add SYM to DICT. DICT had better be expandable. */
496 dict_add_symbol (struct dictionary *dict, struct symbol *sym)
498 (DICT_VECTOR (dict))->add_symbol (dict, sym);
501 /* Utility to add a list of symbols to a dictionary.
502 DICT must be an expandable dictionary. */
505 dict_add_pending (struct dictionary *dict, const struct pending *symbol_list)
507 const struct pending *list;
510 for (list = symbol_list; list != NULL; list = list->next)
512 for (i = 0; i < list->nsyms; ++i)
513 dict_add_symbol (dict, list->symbol[i]);
517 /* Initialize ITERATOR to point at the first symbol in DICT, and
518 return that first symbol, or NULL if DICT is empty. */
521 dict_iterator_first (const struct dictionary *dict,
522 struct dict_iterator *iterator)
524 return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
527 /* Advance ITERATOR, and return the next symbol, or NULL if there are
531 dict_iterator_next (struct dict_iterator *iterator)
533 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
534 ->iterator_next (iterator);
538 dict_iter_name_first (const struct dictionary *dict,
540 struct dict_iterator *iterator)
542 return dict_iter_match_first (dict, name, strcmp_iw, iterator);
546 dict_iter_name_next (const char *name, struct dict_iterator *iterator)
548 return dict_iter_match_next (name, strcmp_iw, iterator);
552 dict_iter_match_first (const struct dictionary *dict,
553 const char *name, symbol_compare_ftype *compare,
554 struct dict_iterator *iterator)
556 return (DICT_VECTOR (dict))->iter_match_first (dict, name,
561 dict_iter_match_next (const char *name, symbol_compare_ftype *compare,
562 struct dict_iterator *iterator)
564 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
565 ->iter_match_next (name, compare, iterator);
569 dict_size (const struct dictionary *dict)
571 return (DICT_VECTOR (dict))->size (dict);
574 /* Now come functions (well, one function, currently) that are
575 implemented generically by means of the vtable. Typically, they're
578 /* Test to see if DICT is empty. */
581 dict_empty (struct dictionary *dict)
583 struct dict_iterator iter;
585 return (dict_iterator_first (dict, &iter) == NULL);
589 /* The functions implementing the dictionary interface. */
591 /* Generic functions, where appropriate. */
594 free_obstack (struct dictionary *dict)
600 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
602 internal_error (__FILE__, __LINE__,
603 _("dict_add_symbol: non-expandable dictionary"));
606 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
608 static struct symbol *
609 iterator_first_hashed (const struct dictionary *dict,
610 struct dict_iterator *iterator)
612 DICT_ITERATOR_DICT (iterator) = dict;
613 DICT_ITERATOR_INDEX (iterator) = -1;
614 return iterator_hashed_advance (iterator);
617 static struct symbol *
618 iterator_next_hashed (struct dict_iterator *iterator)
622 next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
625 return iterator_hashed_advance (iterator);
628 DICT_ITERATOR_CURRENT (iterator) = next;
633 static struct symbol *
634 iterator_hashed_advance (struct dict_iterator *iterator)
636 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
637 int nbuckets = DICT_HASHED_NBUCKETS (dict);
640 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
642 struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
646 DICT_ITERATOR_INDEX (iterator) = i;
647 DICT_ITERATOR_CURRENT (iterator) = sym;
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)
660 unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict);
663 DICT_ITERATOR_DICT (iterator) = dict;
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. */
669 for (sym = DICT_HASHED_BUCKET (dict, hash_index);
671 sym = sym->hash_next)
673 /* Warning: the order of arguments to compare matters! */
674 if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
681 DICT_ITERATOR_CURRENT (iterator) = sym;
685 static struct symbol *
686 iter_match_next_hashed (const char *name, symbol_compare_ftype *compare,
687 struct dict_iterator *iterator)
691 for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
693 next = next->hash_next)
695 if (compare (SYMBOL_SEARCH_NAME (next), name) == 0)
699 DICT_ITERATOR_CURRENT (iterator) = next;
704 /* Insert SYM into DICT. */
707 insert_symbol_hashed (struct dictionary *dict,
710 unsigned int hash_index;
711 struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
714 dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict);
715 sym->hash_next = buckets[hash_index];
716 buckets[hash_index] = sym;
720 size_hashed (const struct dictionary *dict)
722 return DICT_HASHED_NBUCKETS (dict);
725 /* Functions only for DICT_HASHED_EXPANDABLE. */
728 free_hashed_expandable (struct dictionary *dict)
730 xfree (DICT_HASHED_BUCKETS (dict));
735 add_symbol_hashed_expandable (struct dictionary *dict,
738 int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
740 if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
741 expand_hashtable (dict);
743 insert_symbol_hashed (dict, sym);
744 DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
748 size_hashed_expandable (const struct dictionary *dict)
750 return DICT_HASHED_EXPANDABLE_NSYMS (dict);
754 expand_hashtable (struct dictionary *dict)
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 *));
763 DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
764 DICT_HASHED_BUCKETS (dict) = new_buckets;
766 for (i = 0; i < old_nbuckets; ++i)
768 struct symbol *sym, *next_sym;
770 sym = old_buckets[i];
773 for (next_sym = sym->hash_next;
775 next_sym = sym->hash_next)
777 insert_symbol_hashed (dict, sym);
781 insert_symbol_hashed (dict, sym);
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. */
794 dict_hash (const char *string0)
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). */
810 if (strncmp (string, "_ada_", 5) == 0)
813 return msymbol_hash_iw (string0);
819 /* Ignore "TKB" suffixes.
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)
835 if (string0 == string)
836 return msymbol_hash_iw (string0);
841 return msymbol_hash_iw (string0);
843 if (string[1] == '_' && string != string0)
847 if ((c < 'a' || c > 'z') && c != 'O')
855 hash = SYMBOL_HASH_NEXT (hash, *string);
863 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
865 static struct symbol *
866 iterator_first_linear (const struct dictionary *dict,
867 struct dict_iterator *iterator)
869 DICT_ITERATOR_DICT (iterator) = dict;
870 DICT_ITERATOR_INDEX (iterator) = 0;
871 return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
874 static struct symbol *
875 iterator_next_linear (struct dict_iterator *iterator)
877 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
879 if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
882 return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
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)
890 DICT_ITERATOR_DICT (iterator) = dict;
891 DICT_ITERATOR_INDEX (iterator) = -1;
893 return iter_match_next_linear (name, compare, iterator);
896 static struct symbol *
897 iter_match_next_linear (const char *name, symbol_compare_ftype *compare,
898 struct dict_iterator *iterator)
900 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
901 int i, nsyms = DICT_LINEAR_NSYMS (dict);
902 struct symbol *sym, *retval = NULL;
904 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
906 sym = DICT_LINEAR_SYM (dict, i);
907 if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
914 DICT_ITERATOR_INDEX (iterator) = i;
920 size_linear (const struct dictionary *dict)
922 return DICT_LINEAR_NSYMS (dict);
925 /* Functions only for DICT_LINEAR_EXPANDABLE. */
928 free_linear_expandable (struct dictionary *dict)
930 xfree (DICT_LINEAR_SYMS (dict));
936 add_symbol_linear_expandable (struct dictionary *dict,
939 int nsyms = ++DICT_LINEAR_NSYMS (dict);
941 /* Do we have enough room? If not, grow it. */
942 if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
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 *));
951 DICT_LINEAR_SYM (dict, nsyms - 1) = sym;