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 symbol_compare_ftype
*equiv
,
123 struct dict_iterator
*iterator
);
124 struct symbol
*(*iter_match_next
) (const char *name
,
125 symbol_compare_ftype
*equiv
,
126 struct dict_iterator
*iterator
);
127 /* A size function, for maint print symtabs. */
128 int (*size
) (const struct dictionary
*dict
);
131 /* Now comes the structs used to store the data for different
132 implementations. If two implementations have data in common, put
133 the common data at the top of their structs, ordered in the same
136 struct dictionary_hashed
139 struct symbol
**buckets
;
142 struct dictionary_hashed_expandable
144 /* How many buckets we currently have. */
146 struct symbol
**buckets
;
147 /* How many syms we currently have; we need this so we will know
148 when to add more buckets. */
152 struct dictionary_linear
155 struct symbol
**syms
;
158 struct dictionary_linear_expandable
160 /* How many symbols we currently have. */
162 struct symbol
**syms
;
163 /* How many symbols we can store before needing to reallocate. */
167 /* And now, the star of our show. */
171 const struct dict_vector
*vector
;
174 struct dictionary_hashed hashed
;
175 struct dictionary_hashed_expandable hashed_expandable
;
176 struct dictionary_linear linear
;
177 struct dictionary_linear_expandable linear_expandable
;
182 /* Accessor macros. */
184 #define DICT_VECTOR(d) (d)->vector
186 /* These can be used for DICT_HASHED_EXPANDABLE, too. */
188 #define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
189 #define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
190 #define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
192 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
194 /* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
196 #define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
197 #define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
198 #define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
200 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
201 (d)->data.linear_expandable.capacity
203 /* The initial size of a DICT_*_EXPANDABLE dictionary. */
205 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
207 /* This calculates the number of buckets we'll use in a hashtable,
208 given the number of symbols that it will contain. */
210 #define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
212 /* Accessor macros for dict_iterators; they're here rather than
213 dictionary.h because code elsewhere should treat dict_iterators as
216 /* The dictionary that the iterator is associated to. */
217 #define DICT_ITERATOR_DICT(iter) (iter)->dict
218 /* For linear dictionaries, the index of the last symbol returned; for
219 hashed dictionaries, the bucket of the last symbol returned. */
220 #define DICT_ITERATOR_INDEX(iter) (iter)->index
221 /* For hashed dictionaries, this points to the last symbol returned;
222 otherwise, this is unused. */
223 #define DICT_ITERATOR_CURRENT(iter) (iter)->current
225 /* Declarations of functions for vectors. */
227 /* Functions that might work across a range of dictionary types. */
229 static void add_symbol_nonexpandable (struct dictionary
*dict
,
232 static void free_obstack (struct dictionary
*dict
);
234 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
237 static struct symbol
*iterator_first_hashed (const struct dictionary
*dict
,
238 struct dict_iterator
*iterator
);
240 static struct symbol
*iterator_next_hashed (struct dict_iterator
*iterator
);
242 static struct symbol
*iter_match_first_hashed (const struct dictionary
*dict
,
244 symbol_compare_ftype
*compare
,
245 struct dict_iterator
*iterator
);
247 static struct symbol
*iter_match_next_hashed (const char *name
,
248 symbol_compare_ftype
*compare
,
249 struct dict_iterator
*iterator
);
251 static unsigned int dict_hash (const char *string
);
253 /* Functions only for DICT_HASHED. */
255 static int size_hashed (const struct dictionary
*dict
);
257 /* Functions only for DICT_HASHED_EXPANDABLE. */
259 static void free_hashed_expandable (struct dictionary
*dict
);
261 static void add_symbol_hashed_expandable (struct dictionary
*dict
,
264 static int size_hashed_expandable (const struct dictionary
*dict
);
266 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
269 static struct symbol
*iterator_first_linear (const struct dictionary
*dict
,
270 struct dict_iterator
*iterator
);
272 static struct symbol
*iterator_next_linear (struct dict_iterator
*iterator
);
274 static struct symbol
*iter_match_first_linear (const struct dictionary
*dict
,
276 symbol_compare_ftype
*compare
,
277 struct dict_iterator
*iterator
);
279 static struct symbol
*iter_match_next_linear (const char *name
,
280 symbol_compare_ftype
*compare
,
281 struct dict_iterator
*iterator
);
283 static int size_linear (const struct dictionary
*dict
);
285 /* Functions only for DICT_LINEAR_EXPANDABLE. */
287 static void free_linear_expandable (struct dictionary
*dict
);
289 static void add_symbol_linear_expandable (struct dictionary
*dict
,
292 /* Various vectors that we'll actually use. */
294 static const struct dict_vector dict_hashed_vector
=
296 DICT_HASHED
, /* type */
297 free_obstack
, /* free */
298 add_symbol_nonexpandable
, /* add_symbol */
299 iterator_first_hashed
, /* iterator_first */
300 iterator_next_hashed
, /* iterator_next */
301 iter_match_first_hashed
, /* iter_name_first */
302 iter_match_next_hashed
, /* iter_name_next */
303 size_hashed
, /* size */
306 static const struct dict_vector dict_hashed_expandable_vector
=
308 DICT_HASHED_EXPANDABLE
, /* type */
309 free_hashed_expandable
, /* free */
310 add_symbol_hashed_expandable
, /* add_symbol */
311 iterator_first_hashed
, /* iterator_first */
312 iterator_next_hashed
, /* iterator_next */
313 iter_match_first_hashed
, /* iter_name_first */
314 iter_match_next_hashed
, /* iter_name_next */
315 size_hashed_expandable
, /* size */
318 static const struct dict_vector dict_linear_vector
=
320 DICT_LINEAR
, /* type */
321 free_obstack
, /* free */
322 add_symbol_nonexpandable
, /* add_symbol */
323 iterator_first_linear
, /* iterator_first */
324 iterator_next_linear
, /* iterator_next */
325 iter_match_first_linear
, /* iter_name_first */
326 iter_match_next_linear
, /* iter_name_next */
327 size_linear
, /* size */
330 static const struct dict_vector dict_linear_expandable_vector
=
332 DICT_LINEAR_EXPANDABLE
, /* type */
333 free_linear_expandable
, /* free */
334 add_symbol_linear_expandable
, /* add_symbol */
335 iterator_first_linear
, /* iterator_first */
336 iterator_next_linear
, /* iterator_next */
337 iter_match_first_linear
, /* iter_name_first */
338 iter_match_next_linear
, /* iter_name_next */
339 size_linear
, /* size */
342 /* Declarations of helper functions (i.e. ones that don't go into
345 static struct symbol
*iterator_hashed_advance (struct dict_iterator
*iter
);
347 static void insert_symbol_hashed (struct dictionary
*dict
,
350 static void expand_hashtable (struct dictionary
*dict
);
352 /* The creation functions. */
354 /* Create a dictionary implemented via a fixed-size hashtable. All
355 memory it uses is allocated on OBSTACK; the environment is
356 initialized from SYMBOL_LIST. */
359 dict_create_hashed (struct obstack
*obstack
,
360 const struct pending
*symbol_list
)
362 struct dictionary
*retval
;
363 int nsyms
= 0, nbuckets
, i
;
364 struct symbol
**buckets
;
365 const struct pending
*list_counter
;
367 retval
= obstack_alloc (obstack
, sizeof (struct dictionary
));
368 DICT_VECTOR (retval
) = &dict_hashed_vector
;
370 /* Calculate the number of symbols, and allocate space for them. */
371 for (list_counter
= symbol_list
;
372 list_counter
!= NULL
;
373 list_counter
= list_counter
->next
)
375 nsyms
+= list_counter
->nsyms
;
377 nbuckets
= DICT_HASHTABLE_SIZE (nsyms
);
378 DICT_HASHED_NBUCKETS (retval
) = nbuckets
;
379 buckets
= obstack_alloc (obstack
, nbuckets
* sizeof (struct symbol
*));
380 memset (buckets
, 0, nbuckets
* sizeof (struct symbol
*));
381 DICT_HASHED_BUCKETS (retval
) = buckets
;
383 /* Now fill the buckets. */
384 for (list_counter
= symbol_list
;
385 list_counter
!= NULL
;
386 list_counter
= list_counter
->next
)
388 for (i
= list_counter
->nsyms
- 1; i
>= 0; --i
)
390 insert_symbol_hashed (retval
, list_counter
->symbol
[i
]);
397 /* Create a dictionary implemented via a hashtable that grows as
398 necessary. The dictionary is initially empty; to add symbols to
399 it, call dict_add_symbol(). Call dict_free() when you're done with
402 extern struct dictionary
*
403 dict_create_hashed_expandable (void)
405 struct dictionary
*retval
;
407 retval
= xmalloc (sizeof (struct dictionary
));
408 DICT_VECTOR (retval
) = &dict_hashed_expandable_vector
;
409 DICT_HASHED_NBUCKETS (retval
) = DICT_EXPANDABLE_INITIAL_CAPACITY
;
410 DICT_HASHED_BUCKETS (retval
) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY
,
411 sizeof (struct symbol
*));
412 DICT_HASHED_EXPANDABLE_NSYMS (retval
) = 0;
417 /* Create a dictionary implemented via a fixed-size array. All memory
418 it uses is allocated on OBSTACK; the environment is initialized
419 from the SYMBOL_LIST. The symbols are ordered in the same order
420 that they're found in SYMBOL_LIST. */
423 dict_create_linear (struct obstack
*obstack
,
424 const struct pending
*symbol_list
)
426 struct dictionary
*retval
;
428 struct symbol
**syms
;
429 const struct pending
*list_counter
;
431 retval
= obstack_alloc (obstack
, sizeof (struct dictionary
));
432 DICT_VECTOR (retval
) = &dict_linear_vector
;
434 /* Calculate the number of symbols, and allocate space for them. */
435 for (list_counter
= symbol_list
;
436 list_counter
!= NULL
;
437 list_counter
= list_counter
->next
)
439 nsyms
+= list_counter
->nsyms
;
441 DICT_LINEAR_NSYMS (retval
) = nsyms
;
442 syms
= obstack_alloc (obstack
, nsyms
* sizeof (struct symbol
*));
443 DICT_LINEAR_SYMS (retval
) = syms
;
445 /* Now fill in the symbols. Start filling in from the back, so as
446 to preserve the original order of the symbols. */
447 for (list_counter
= symbol_list
, j
= nsyms
- 1;
448 list_counter
!= NULL
;
449 list_counter
= list_counter
->next
)
451 for (i
= list_counter
->nsyms
- 1;
455 syms
[j
] = list_counter
->symbol
[i
];
462 /* Create a dictionary implemented via an array that grows as
463 necessary. The dictionary is initially empty; to add symbols to
464 it, call dict_add_symbol(). Call dict_free() when you're done with
468 dict_create_linear_expandable (void)
470 struct dictionary
*retval
;
472 retval
= xmalloc (sizeof (struct dictionary
));
473 DICT_VECTOR (retval
) = &dict_linear_expandable_vector
;
474 DICT_LINEAR_NSYMS (retval
) = 0;
475 DICT_LINEAR_EXPANDABLE_CAPACITY (retval
)
476 = DICT_EXPANDABLE_INITIAL_CAPACITY
;
477 DICT_LINEAR_SYMS (retval
)
478 = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval
)
479 * sizeof (struct symbol
*));
484 /* The functions providing the dictionary interface. */
486 /* Free the memory used by a dictionary that's not on an obstack. (If
490 dict_free (struct dictionary
*dict
)
492 (DICT_VECTOR (dict
))->free (dict
);
495 /* Add SYM to DICT. DICT had better be expandable. */
498 dict_add_symbol (struct dictionary
*dict
, struct symbol
*sym
)
500 (DICT_VECTOR (dict
))->add_symbol (dict
, sym
);
503 /* Initialize ITERATOR to point at the first symbol in DICT, and
504 return that first symbol, or NULL if DICT is empty. */
507 dict_iterator_first (const struct dictionary
*dict
,
508 struct dict_iterator
*iterator
)
510 return (DICT_VECTOR (dict
))->iterator_first (dict
, iterator
);
513 /* Advance ITERATOR, and return the next symbol, or NULL if there are
517 dict_iterator_next (struct dict_iterator
*iterator
)
519 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator
)))
520 ->iterator_next (iterator
);
524 dict_iter_name_first (const struct dictionary
*dict
,
526 struct dict_iterator
*iterator
)
528 return dict_iter_match_first (dict
, name
, strcmp_iw
, iterator
);
532 dict_iter_name_next (const char *name
, struct dict_iterator
*iterator
)
534 return dict_iter_match_next (name
, strcmp_iw
, iterator
);
538 dict_iter_match_first (const struct dictionary
*dict
,
539 const char *name
, symbol_compare_ftype
*compare
,
540 struct dict_iterator
*iterator
)
542 return (DICT_VECTOR (dict
))->iter_match_first (dict
, name
, compare
, iterator
);
546 dict_iter_match_next (const char *name
, symbol_compare_ftype
*compare
,
547 struct dict_iterator
*iterator
)
549 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator
)))
550 ->iter_match_next (name
, compare
, iterator
);
554 dict_size (const struct dictionary
*dict
)
556 return (DICT_VECTOR (dict
))->size (dict
);
559 /* Now come functions (well, one function, currently) that are
560 implemented generically by means of the vtable. Typically, they're
563 /* Test to see if DICT is empty. */
566 dict_empty (struct dictionary
*dict
)
568 struct dict_iterator iter
;
570 return (dict_iterator_first (dict
, &iter
) == NULL
);
574 /* The functions implementing the dictionary interface. */
576 /* Generic functions, where appropriate. */
579 free_obstack (struct dictionary
*dict
)
585 add_symbol_nonexpandable (struct dictionary
*dict
, struct symbol
*sym
)
587 internal_error (__FILE__
, __LINE__
,
588 _("dict_add_symbol: non-expandable dictionary"));
591 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
593 static struct symbol
*
594 iterator_first_hashed (const struct dictionary
*dict
,
595 struct dict_iterator
*iterator
)
597 DICT_ITERATOR_DICT (iterator
) = dict
;
598 DICT_ITERATOR_INDEX (iterator
) = -1;
599 return iterator_hashed_advance (iterator
);
602 static struct symbol
*
603 iterator_next_hashed (struct dict_iterator
*iterator
)
607 next
= DICT_ITERATOR_CURRENT (iterator
)->hash_next
;
610 return iterator_hashed_advance (iterator
);
613 DICT_ITERATOR_CURRENT (iterator
) = next
;
618 static struct symbol
*
619 iterator_hashed_advance (struct dict_iterator
*iterator
)
621 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
622 int nbuckets
= DICT_HASHED_NBUCKETS (dict
);
625 for (i
= DICT_ITERATOR_INDEX (iterator
) + 1; i
< nbuckets
; ++i
)
627 struct symbol
*sym
= DICT_HASHED_BUCKET (dict
, i
);
631 DICT_ITERATOR_INDEX (iterator
) = i
;
632 DICT_ITERATOR_CURRENT (iterator
) = sym
;
640 static struct symbol
*
641 iter_match_first_hashed (const struct dictionary
*dict
, const char *name
,
642 symbol_compare_ftype
*compare
,
643 struct dict_iterator
*iterator
)
645 unsigned int hash_index
= dict_hash (name
) % DICT_HASHED_NBUCKETS (dict
);
648 DICT_ITERATOR_DICT (iterator
) = dict
;
650 /* Loop through the symbols in the given bucket, breaking when SYM
651 first matches. If SYM never matches, it will be set to NULL;
652 either way, we have the right return value. */
654 for (sym
= DICT_HASHED_BUCKET (dict
, hash_index
);
656 sym
= sym
->hash_next
)
658 /* Warning: the order of arguments to compare matters! */
659 if (compare (SYMBOL_SEARCH_NAME (sym
), name
) == 0)
666 DICT_ITERATOR_CURRENT (iterator
) = sym
;
670 static struct symbol
*
671 iter_match_next_hashed (const char *name
, symbol_compare_ftype
*compare
,
672 struct dict_iterator
*iterator
)
676 for (next
= DICT_ITERATOR_CURRENT (iterator
)->hash_next
;
678 next
= next
->hash_next
)
680 if (compare (SYMBOL_SEARCH_NAME (next
), name
) == 0)
684 DICT_ITERATOR_CURRENT (iterator
) = next
;
689 /* Insert SYM into DICT. */
692 insert_symbol_hashed (struct dictionary
*dict
,
695 unsigned int hash_index
;
696 struct symbol
**buckets
= DICT_HASHED_BUCKETS (dict
);
699 dict_hash (SYMBOL_SEARCH_NAME (sym
)) % DICT_HASHED_NBUCKETS (dict
);
700 sym
->hash_next
= buckets
[hash_index
];
701 buckets
[hash_index
] = sym
;
705 size_hashed (const struct dictionary
*dict
)
707 return DICT_HASHED_NBUCKETS (dict
);
710 /* Functions only for DICT_HASHED_EXPANDABLE. */
713 free_hashed_expandable (struct dictionary
*dict
)
715 xfree (DICT_HASHED_BUCKETS (dict
));
720 add_symbol_hashed_expandable (struct dictionary
*dict
,
723 int nsyms
= ++DICT_HASHED_EXPANDABLE_NSYMS (dict
);
725 if (DICT_HASHTABLE_SIZE (nsyms
) > DICT_HASHED_NBUCKETS (dict
))
726 expand_hashtable (dict
);
728 insert_symbol_hashed (dict
, sym
);
729 DICT_HASHED_EXPANDABLE_NSYMS (dict
) = nsyms
;
733 size_hashed_expandable (const struct dictionary
*dict
)
735 return DICT_HASHED_EXPANDABLE_NSYMS (dict
);
739 expand_hashtable (struct dictionary
*dict
)
741 int old_nbuckets
= DICT_HASHED_NBUCKETS (dict
);
742 struct symbol
**old_buckets
= DICT_HASHED_BUCKETS (dict
);
743 int new_nbuckets
= 2*old_nbuckets
+ 1;
744 struct symbol
**new_buckets
= xcalloc (new_nbuckets
,
745 sizeof (struct symbol
*));
748 DICT_HASHED_NBUCKETS (dict
) = new_nbuckets
;
749 DICT_HASHED_BUCKETS (dict
) = new_buckets
;
751 for (i
= 0; i
< old_nbuckets
; ++i
)
753 struct symbol
*sym
, *next_sym
;
755 sym
= old_buckets
[i
];
758 for (next_sym
= sym
->hash_next
;
760 next_sym
= sym
->hash_next
)
762 insert_symbol_hashed (dict
, sym
);
766 insert_symbol_hashed (dict
, sym
);
773 /* Produce an unsigned hash value from STRING0 that is consistent
774 with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
775 That is, two identifiers equivalent according to any of those three
776 comparison operators hash to the same value. */
779 dict_hash (const char *string0
)
781 /* The Ada-encoded version of a name P1.P2...Pn has either the form
782 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
783 are lower-cased identifiers). The <suffix> (which can be empty)
784 encodes additional information about the denoted entity. This
785 routine hashes such names to msymbol_hash_iw(Pn). It actually
786 does this for a superset of both valid Pi and of <suffix>, but
787 in other cases it simply returns msymbol_hash_iw(STRING0). */
795 if (strncmp (string
, "_ada_", 5) == 0)
798 return msymbol_hash_iw (string0
);
809 if (string0
== string
)
810 return msymbol_hash_iw (string0
);
815 return msymbol_hash_iw (string0
);
817 if (string
[1] == '_' && string
!= string0
)
821 if ((c
< '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
,
861 const char *name
, symbol_compare_ftype
*compare
,
862 struct dict_iterator
*iterator
)
864 DICT_ITERATOR_DICT (iterator
) = dict
;
865 DICT_ITERATOR_INDEX (iterator
) = -1;
867 return iter_match_next_linear (name
, compare
, iterator
);
870 static struct symbol
*
871 iter_match_next_linear (const char *name
, symbol_compare_ftype
*compare
,
872 struct dict_iterator
*iterator
)
874 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
875 int i
, nsyms
= DICT_LINEAR_NSYMS (dict
);
876 struct symbol
*sym
, *retval
= NULL
;
878 for (i
= DICT_ITERATOR_INDEX (iterator
) + 1; i
< nsyms
; ++i
)
880 sym
= DICT_LINEAR_SYM (dict
, i
);
881 if (compare (SYMBOL_SEARCH_NAME (sym
), name
) == 0)
888 DICT_ITERATOR_INDEX (iterator
) = i
;
894 size_linear (const struct dictionary
*dict
)
896 return DICT_LINEAR_NSYMS (dict
);
899 /* Functions only for DICT_LINEAR_EXPANDABLE. */
902 free_linear_expandable (struct dictionary
*dict
)
904 xfree (DICT_LINEAR_SYMS (dict
));
910 add_symbol_linear_expandable (struct dictionary
*dict
,
913 int nsyms
= ++DICT_LINEAR_NSYMS (dict
);
915 /* Do we have enough room? If not, grow it. */
916 if (nsyms
> DICT_LINEAR_EXPANDABLE_CAPACITY (dict
))
918 DICT_LINEAR_EXPANDABLE_CAPACITY (dict
) *= 2;
919 DICT_LINEAR_SYMS (dict
)
920 = xrealloc (DICT_LINEAR_SYMS (dict
),
921 DICT_LINEAR_EXPANDABLE_CAPACITY (dict
)
922 * sizeof (struct symbol
*));
925 DICT_LINEAR_SYM (dict
, nsyms
- 1) = sym
;