1 /* Routines for name->symbol lookups in GDB.
3 Copyright (C) 2003, 2007, 2008, 2009, 2010 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.
89 /* An enum representing the various implementations of dictionaries.
90 Used only for debugging. */
94 /* Symbols are stored in a fixed-size hash table. */
96 /* Symbols are stored in an expandable hash table. */
97 DICT_HASHED_EXPANDABLE,
98 /* Symbols are stored in a fixed-size array. */
100 /* Symbols are stored in an expandable array. */
101 DICT_LINEAR_EXPANDABLE
104 /* The virtual function table. */
108 /* The type of the dictionary. This is only here to make debugging
109 a bit easier; it's not actually used. */
111 /* The function to free a dictionary. */
112 void (*free) (struct dictionary *dict);
113 /* Add a symbol to a dictionary, if possible. */
114 void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
115 /* Iterator functions. */
116 struct symbol *(*iterator_first) (const struct dictionary *dict,
117 struct dict_iterator *iterator);
118 struct symbol *(*iterator_next) (struct dict_iterator *iterator);
119 /* Functions to iterate over symbols with a given name. */
120 struct symbol *(*iter_match_first) (const struct dictionary *dict,
122 int (*equiv) (const char *,
124 struct dict_iterator *iterator);
125 struct symbol *(*iter_match_next) (const char *name,
126 int (*equiv) (const char *,
128 struct dict_iterator *iterator);
129 /* A size function, for maint print symtabs. */
130 int (*size) (const struct dictionary *dict);
133 /* Now comes the structs used to store the data for different
134 implementations. If two implementations have data in common, put
135 the common data at the top of their structs, ordered in the same
138 struct dictionary_hashed
141 struct symbol **buckets;
144 struct dictionary_hashed_expandable
146 /* How many buckets we currently have. */
148 struct symbol **buckets;
149 /* How many syms we currently have; we need this so we will know
150 when to add more buckets. */
154 struct dictionary_linear
157 struct symbol **syms;
160 struct dictionary_linear_expandable
162 /* How many symbols we currently have. */
164 struct symbol **syms;
165 /* How many symbols we can store before needing to reallocate. */
169 /* And now, the star of our show. */
173 const struct dict_vector *vector;
176 struct dictionary_hashed hashed;
177 struct dictionary_hashed_expandable hashed_expandable;
178 struct dictionary_linear linear;
179 struct dictionary_linear_expandable linear_expandable;
184 /* Accessor macros. */
186 #define DICT_VECTOR(d) (d)->vector
188 /* These can be used for DICT_HASHED_EXPANDABLE, too. */
190 #define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
191 #define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
192 #define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
194 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
196 /* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
198 #define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
199 #define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
200 #define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
202 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
203 (d)->data.linear_expandable.capacity
205 /* The initial size of a DICT_*_EXPANDABLE dictionary. */
207 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
209 /* This calculates the number of buckets we'll use in a hashtable,
210 given the number of symbols that it will contain. */
212 #define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
214 /* Accessor macros for dict_iterators; they're here rather than
215 dictionary.h because code elsewhere should treat dict_iterators as
218 /* The dictionary that the iterator is associated to. */
219 #define DICT_ITERATOR_DICT(iter) (iter)->dict
220 /* For linear dictionaries, the index of the last symbol returned; for
221 hashed dictionaries, the bucket of the last symbol returned. */
222 #define DICT_ITERATOR_INDEX(iter) (iter)->index
223 /* For hashed dictionaries, this points to the last symbol returned;
224 otherwise, this is unused. */
225 #define DICT_ITERATOR_CURRENT(iter) (iter)->current
227 /* Declarations of functions for vectors. */
229 /* Functions that might work across a range of dictionary types. */
231 static void add_symbol_nonexpandable (struct dictionary *dict,
234 static void free_obstack (struct dictionary *dict);
236 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
239 static struct symbol *iterator_first_hashed (const struct dictionary *dict,
240 struct dict_iterator *iterator);
242 static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
244 static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
246 int (*compare) (const char *,
248 struct dict_iterator *iterator);
250 static struct symbol *iter_match_next_hashed (const char *name,
251 int (*compare) (const char *,
253 struct dict_iterator *iterator);
255 static unsigned int dict_hash (const char *string);
257 /* Functions only for DICT_HASHED. */
259 static int size_hashed (const struct dictionary *dict);
261 /* Functions only for DICT_HASHED_EXPANDABLE. */
263 static void free_hashed_expandable (struct dictionary *dict);
265 static void add_symbol_hashed_expandable (struct dictionary *dict,
268 static int size_hashed_expandable (const struct dictionary *dict);
270 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
273 static struct symbol *iterator_first_linear (const struct dictionary *dict,
274 struct dict_iterator *iterator);
276 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
278 static struct symbol *iter_match_first_linear (const struct dictionary *dict,
280 int (*compare) (const char *,
282 struct dict_iterator *iterator);
284 static struct symbol *iter_match_next_linear (const char *name,
285 int (*compare) (const char *,
287 struct dict_iterator *iterator);
289 static int size_linear (const struct dictionary *dict);
291 /* Functions only for DICT_LINEAR_EXPANDABLE. */
293 static void free_linear_expandable (struct dictionary *dict);
295 static void add_symbol_linear_expandable (struct dictionary *dict,
298 /* Various vectors that we'll actually use. */
300 static const struct dict_vector dict_hashed_vector =
302 DICT_HASHED, /* type */
303 free_obstack, /* free */
304 add_symbol_nonexpandable, /* add_symbol */
305 iterator_first_hashed, /* iterator_first */
306 iterator_next_hashed, /* iterator_next */
307 iter_match_first_hashed, /* iter_name_first */
308 iter_match_next_hashed, /* iter_name_next */
309 size_hashed, /* size */
312 static const struct dict_vector dict_hashed_expandable_vector =
314 DICT_HASHED_EXPANDABLE, /* type */
315 free_hashed_expandable, /* free */
316 add_symbol_hashed_expandable, /* add_symbol */
317 iterator_first_hashed, /* iterator_first */
318 iterator_next_hashed, /* iterator_next */
319 iter_match_first_hashed, /* iter_name_first */
320 iter_match_next_hashed, /* iter_name_next */
321 size_hashed_expandable, /* size */
324 static const struct dict_vector dict_linear_vector =
326 DICT_LINEAR, /* type */
327 free_obstack, /* free */
328 add_symbol_nonexpandable, /* add_symbol */
329 iterator_first_linear, /* iterator_first */
330 iterator_next_linear, /* iterator_next */
331 iter_match_first_linear, /* iter_name_first */
332 iter_match_next_linear, /* iter_name_next */
333 size_linear, /* size */
336 static const struct dict_vector dict_linear_expandable_vector =
338 DICT_LINEAR_EXPANDABLE, /* type */
339 free_linear_expandable, /* free */
340 add_symbol_linear_expandable, /* add_symbol */
341 iterator_first_linear, /* iterator_first */
342 iterator_next_linear, /* iterator_next */
343 iter_match_first_linear, /* iter_name_first */
344 iter_match_next_linear, /* iter_name_next */
345 size_linear, /* size */
348 /* Declarations of helper functions (i.e. ones that don't go into
351 static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
353 static void insert_symbol_hashed (struct dictionary *dict,
356 static void expand_hashtable (struct dictionary *dict);
358 /* The creation functions. */
360 /* Create a dictionary implemented via a fixed-size hashtable. All
361 memory it uses is allocated on OBSTACK; the environment is
362 initialized from SYMBOL_LIST. */
365 dict_create_hashed (struct obstack *obstack,
366 const struct pending *symbol_list)
368 struct dictionary *retval;
369 int nsyms = 0, nbuckets, i;
370 struct symbol **buckets;
371 const struct pending *list_counter;
373 retval = obstack_alloc (obstack, sizeof (struct dictionary));
374 DICT_VECTOR (retval) = &dict_hashed_vector;
376 /* Calculate the number of symbols, and allocate space for them. */
377 for (list_counter = symbol_list;
378 list_counter != NULL;
379 list_counter = list_counter->next)
381 nsyms += list_counter->nsyms;
383 nbuckets = DICT_HASHTABLE_SIZE (nsyms);
384 DICT_HASHED_NBUCKETS (retval) = nbuckets;
385 buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *));
386 memset (buckets, 0, nbuckets * sizeof (struct symbol *));
387 DICT_HASHED_BUCKETS (retval) = buckets;
389 /* Now fill the buckets. */
390 for (list_counter = symbol_list;
391 list_counter != NULL;
392 list_counter = list_counter->next)
394 for (i = list_counter->nsyms - 1; i >= 0; --i)
396 insert_symbol_hashed (retval, list_counter->symbol[i]);
403 /* Create a dictionary implemented via a hashtable that grows as
404 necessary. The dictionary is initially empty; to add symbols to
405 it, call dict_add_symbol(). Call dict_free() when you're done with
408 extern struct dictionary *
409 dict_create_hashed_expandable (void)
411 struct dictionary *retval;
413 retval = xmalloc (sizeof (struct dictionary));
414 DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
415 DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
416 DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY,
417 sizeof (struct symbol *));
418 DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
423 /* Create a dictionary implemented via a fixed-size array. All memory
424 it uses is allocated on OBSTACK; the environment is initialized
425 from the SYMBOL_LIST. The symbols are ordered in the same order
426 that they're found in SYMBOL_LIST. */
429 dict_create_linear (struct obstack *obstack,
430 const struct pending *symbol_list)
432 struct dictionary *retval;
434 struct symbol **syms;
435 const struct pending *list_counter;
437 retval = obstack_alloc (obstack, sizeof (struct dictionary));
438 DICT_VECTOR (retval) = &dict_linear_vector;
440 /* Calculate the number of symbols, and allocate space for them. */
441 for (list_counter = symbol_list;
442 list_counter != NULL;
443 list_counter = list_counter->next)
445 nsyms += list_counter->nsyms;
447 DICT_LINEAR_NSYMS (retval) = nsyms;
448 syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *));
449 DICT_LINEAR_SYMS (retval) = syms;
451 /* Now fill in the symbols. Start filling in from the back, so as
452 to preserve the original order of the symbols. */
453 for (list_counter = symbol_list, j = nsyms - 1;
454 list_counter != NULL;
455 list_counter = list_counter->next)
457 for (i = list_counter->nsyms - 1;
461 syms[j] = list_counter->symbol[i];
468 /* Create a dictionary implemented via an array that grows as
469 necessary. The dictionary is initially empty; to add symbols to
470 it, call dict_add_symbol(). Call dict_free() when you're done with
474 dict_create_linear_expandable (void)
476 struct dictionary *retval;
478 retval = xmalloc (sizeof (struct dictionary));
479 DICT_VECTOR (retval) = &dict_linear_expandable_vector;
480 DICT_LINEAR_NSYMS (retval) = 0;
481 DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
482 = DICT_EXPANDABLE_INITIAL_CAPACITY;
483 DICT_LINEAR_SYMS (retval)
484 = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
485 * sizeof (struct symbol *));
490 /* The functions providing the dictionary interface. */
492 /* Free the memory used by a dictionary that's not on an obstack. (If
496 dict_free (struct dictionary *dict)
498 (DICT_VECTOR (dict))->free (dict);
501 /* Add SYM to DICT. DICT had better be expandable. */
504 dict_add_symbol (struct dictionary *dict, struct symbol *sym)
506 (DICT_VECTOR (dict))->add_symbol (dict, sym);
509 /* Initialize ITERATOR to point at the first symbol in DICT, and
510 return that first symbol, or NULL if DICT is empty. */
513 dict_iterator_first (const struct dictionary *dict,
514 struct dict_iterator *iterator)
516 return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
519 /* Advance ITERATOR, and return the next symbol, or NULL if there are
523 dict_iterator_next (struct dict_iterator *iterator)
525 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
526 ->iterator_next (iterator);
530 dict_iter_name_first (const struct dictionary *dict,
532 struct dict_iterator *iterator)
534 return dict_iter_match_first (dict, name, strcmp_iw, iterator);
538 dict_iter_name_next (const char *name, struct dict_iterator *iterator)
540 return dict_iter_match_next (name, strcmp_iw, iterator);
544 dict_iter_match_first (const struct dictionary *dict,
546 int (*compare) (const char *, const char *),
547 struct dict_iterator *iterator)
549 return (DICT_VECTOR (dict))->iter_match_first (dict, name, compare, iterator);
553 dict_iter_match_next (const char *name,
554 int (*compare) (const char *, const char *),
555 struct dict_iterator *iterator)
557 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
558 ->iter_match_next (name, compare, iterator);
562 dict_size (const struct dictionary *dict)
564 return (DICT_VECTOR (dict))->size (dict);
567 /* Now come functions (well, one function, currently) that are
568 implemented generically by means of the vtable. Typically, they're
571 /* Test to see if DICT is empty. */
574 dict_empty (struct dictionary *dict)
576 struct dict_iterator iter;
578 return (dict_iterator_first (dict, &iter) == NULL);
582 /* The functions implementing the dictionary interface. */
584 /* Generic functions, where appropriate. */
587 free_obstack (struct dictionary *dict)
593 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
595 internal_error (__FILE__, __LINE__,
596 _("dict_add_symbol: non-expandable dictionary"));
599 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
601 static struct symbol *
602 iterator_first_hashed (const struct dictionary *dict,
603 struct dict_iterator *iterator)
605 DICT_ITERATOR_DICT (iterator) = dict;
606 DICT_ITERATOR_INDEX (iterator) = -1;
607 return iterator_hashed_advance (iterator);
610 static struct symbol *
611 iterator_next_hashed (struct dict_iterator *iterator)
615 next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
618 return iterator_hashed_advance (iterator);
621 DICT_ITERATOR_CURRENT (iterator) = next;
626 static struct symbol *
627 iterator_hashed_advance (struct dict_iterator *iterator)
629 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
630 int nbuckets = DICT_HASHED_NBUCKETS (dict);
633 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
635 struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
639 DICT_ITERATOR_INDEX (iterator) = i;
640 DICT_ITERATOR_CURRENT (iterator) = sym;
648 static struct symbol *
649 iter_match_first_hashed (const struct dictionary *dict,
651 int (*compare) (const char *, const char *),
652 struct dict_iterator *iterator)
654 unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict);
657 DICT_ITERATOR_DICT (iterator) = dict;
659 /* Loop through the symbols in the given bucket, breaking when SYM
660 first matches. If SYM never matches, it will be set to NULL;
661 either way, we have the right return value. */
663 for (sym = DICT_HASHED_BUCKET (dict, hash_index);
665 sym = sym->hash_next)
667 /* Warning: the order of arguments to compare matters! */
668 if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
675 DICT_ITERATOR_CURRENT (iterator) = sym;
679 static struct symbol *
680 iter_match_next_hashed (const char *name,
681 int (*compare) (const char *, const char *),
682 struct dict_iterator *iterator)
686 for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
688 next = next->hash_next)
690 if (compare (SYMBOL_SEARCH_NAME (next), name) == 0)
694 DICT_ITERATOR_CURRENT (iterator) = next;
699 /* Insert SYM into DICT. */
702 insert_symbol_hashed (struct dictionary *dict,
705 unsigned int hash_index;
706 struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
709 dict_hash (SYMBOL_SEARCH_NAME (sym)) % DICT_HASHED_NBUCKETS (dict);
710 sym->hash_next = buckets[hash_index];
711 buckets[hash_index] = sym;
715 size_hashed (const struct dictionary *dict)
717 return DICT_HASHED_NBUCKETS (dict);
720 /* Functions only for DICT_HASHED_EXPANDABLE. */
723 free_hashed_expandable (struct dictionary *dict)
725 xfree (DICT_HASHED_BUCKETS (dict));
730 add_symbol_hashed_expandable (struct dictionary *dict,
733 int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
735 if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
736 expand_hashtable (dict);
738 insert_symbol_hashed (dict, sym);
739 DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
743 size_hashed_expandable (const struct dictionary *dict)
745 return DICT_HASHED_EXPANDABLE_NSYMS (dict);
749 expand_hashtable (struct dictionary *dict)
751 int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
752 struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
753 int new_nbuckets = 2*old_nbuckets + 1;
754 struct symbol **new_buckets = xcalloc (new_nbuckets,
755 sizeof (struct symbol *));
758 DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
759 DICT_HASHED_BUCKETS (dict) = new_buckets;
761 for (i = 0; i < old_nbuckets; ++i)
763 struct symbol *sym, *next_sym;
765 sym = old_buckets[i];
768 for (next_sym = sym->hash_next;
770 next_sym = sym->hash_next)
772 insert_symbol_hashed (dict, sym);
776 insert_symbol_hashed (dict, sym);
783 /* Produce an unsigned hash value from STRING0 that is consistent
784 with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
785 That is, two identifiers equivalent according to any of those three
786 comparison operators hash to the same value. */
789 dict_hash (const char *string)
791 /* The Ada-encoded version of a name P1.P2...Pn has either the form
792 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
793 are lower-cased identifiers). The <suffix> (which can be empty)
794 encodes additional information about the denoted entity. This
795 routine hashes such names to msymbol_hash_iw(Pn). It actually
796 does this for a superset of both valid Pi and of <suffix>, but
797 in other cases it simply returns msymbol_hash_iw(STRING0). */
802 if (*string == '_' && strncmp (string, "_ada_", 5) == 0)
819 if (string[1] == '_')
821 if (((c = string[2]) < 'a' || c > 'z') && c != 'O')
829 hash = hash * 67 + *string - 113;
837 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
839 static struct symbol *
840 iterator_first_linear (const struct dictionary *dict,
841 struct dict_iterator *iterator)
843 DICT_ITERATOR_DICT (iterator) = dict;
844 DICT_ITERATOR_INDEX (iterator) = 0;
845 return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
848 static struct symbol *
849 iterator_next_linear (struct dict_iterator *iterator)
851 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
853 if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
856 return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
859 static struct symbol *
860 iter_match_first_linear (const struct dictionary *dict,
862 int (*compare) (const char *, const char *),
863 struct dict_iterator *iterator)
865 DICT_ITERATOR_DICT (iterator) = dict;
866 DICT_ITERATOR_INDEX (iterator) = -1;
868 return iter_match_next_linear (name, compare, iterator);
871 static struct symbol *
872 iter_match_next_linear (const char *name,
873 int (*compare) (const char *, const char *),
874 struct dict_iterator *iterator)
876 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
877 int i, nsyms = DICT_LINEAR_NSYMS (dict);
878 struct symbol *sym, *retval = NULL;
880 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
882 sym = DICT_LINEAR_SYM (dict, i);
883 if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
890 DICT_ITERATOR_INDEX (iterator) = i;
896 size_linear (const struct dictionary *dict)
898 return DICT_LINEAR_NSYMS (dict);
901 /* Functions only for DICT_LINEAR_EXPANDABLE. */
904 free_linear_expandable (struct dictionary *dict)
906 xfree (DICT_LINEAR_SYMS (dict));
912 add_symbol_linear_expandable (struct dictionary *dict,
915 int nsyms = ++DICT_LINEAR_NSYMS (dict);
917 /* Do we have enough room? If not, grow it. */
918 if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
920 DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
921 DICT_LINEAR_SYMS (dict)
922 = xrealloc (DICT_LINEAR_SYMS (dict),
923 DICT_LINEAR_EXPANDABLE_CAPACITY (dict)
924 * sizeof (struct symbol *));
927 DICT_LINEAR_SYM (dict, nsyms - 1) = sym;