1 /* Routines for name->symbol lookups in GDB.
3 Copyright (C) 2003, 2007, 2008, 2009, 2010, 2011
4 Free Software Foundation, Inc.
6 Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
9 This file is part of GDB.
11 This program is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 3 of the License, or
14 (at your option) any later version.
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
21 You should have received a copy of the GNU General Public License
22 along with this program. If not, see <http://www.gnu.org/licenses/>. */
26 #include "gdb_obstack.h"
29 #include "gdb_assert.h"
30 #include "dictionary.h"
32 /* This file implements dictionaries, which are tables that associate
33 symbols to names. They are represented by an opaque type 'struct
34 dictionary'. That type has various internal implementations, which
35 you can choose between depending on what properties you need
36 (e.g. fast lookup, order-preserving, expandable).
38 Each dictionary starts with a 'virtual function table' that
39 contains the functions that actually implement the various
40 operations that dictionaries provide. (Note, however, that, for
41 the sake of client code, we also provide some functions that can be
42 implemented generically in terms of the functions in the vtable.)
44 To add a new dictionary implementation <impl>, what you should do
47 * Add a new element DICT_<IMPL> to dict_type.
49 * Create a new structure dictionary_<impl>. If your new
50 implementation is a variant of an existing one, make sure that
51 their structs have the same initial data members. Define accessor
52 macros for your new data members.
54 * Implement all the functions in dict_vector as static functions,
55 whose name is the same as the corresponding member of dict_vector
56 plus _<impl>. You don't have to do this for those members where
57 you can reuse existing generic functions
58 (e.g. add_symbol_nonexpandable, free_obstack) or in the case where
59 your new implementation is a variant of an existing implementation
60 and where the variant doesn't affect the member function in
63 * Define a static const struct dict_vector dict_<impl>_vector.
65 * Define a function dict_create_<impl> to create these
66 gizmos. Add its declaration to dictionary.h.
68 To add a new operation <op> on all existing implementations, what
71 * Add a new member <op> to struct dict_vector.
73 * If there is useful generic behavior <op>, define a static
74 function <op>_something_informative that implements that behavior.
75 (E.g. add_symbol_nonexpandable, free_obstack.)
77 * For every implementation <impl> that should have its own specific
78 behavior for <op>, define a static function <op>_<impl>
81 * Modify all existing dict_vector_<impl>'s to include the appropriate
84 * Define a function dict_<op> that looks up <op> in the dict_vector
85 and calls the appropriate function. Add a declaration for
86 dict_<op> to dictionary.h.
90 /* An enum representing the various implementations of dictionaries.
91 Used only for debugging. */
95 /* Symbols are stored in a fixed-size hash table. */
97 /* Symbols are stored in an expandable hash table. */
98 DICT_HASHED_EXPANDABLE
,
99 /* Symbols are stored in a fixed-size array. */
101 /* Symbols are stored in an expandable array. */
102 DICT_LINEAR_EXPANDABLE
105 /* The virtual function table. */
109 /* The type of the dictionary. This is only here to make debugging
110 a bit easier; it's not actually used. */
112 /* The function to free a dictionary. */
113 void (*free
) (struct dictionary
*dict
);
114 /* Add a symbol to a dictionary, if possible. */
115 void (*add_symbol
) (struct dictionary
*dict
, struct symbol
*sym
);
116 /* Iterator functions. */
117 struct symbol
*(*iterator_first
) (const struct dictionary
*dict
,
118 struct dict_iterator
*iterator
);
119 struct symbol
*(*iterator_next
) (struct dict_iterator
*iterator
);
120 /* Functions to iterate over symbols with a given name. */
121 struct symbol
*(*iter_match_first
) (const struct dictionary
*dict
,
123 symbol_compare_ftype
*equiv
,
124 struct dict_iterator
*iterator
);
125 struct symbol
*(*iter_match_next
) (const char *name
,
126 symbol_compare_ftype
*equiv
,
127 struct dict_iterator
*iterator
);
128 /* A size function, for maint print symtabs. */
129 int (*size
) (const struct dictionary
*dict
);
132 /* Now comes the structs used to store the data for different
133 implementations. If two implementations have data in common, put
134 the common data at the top of their structs, ordered in the same
137 struct dictionary_hashed
140 struct symbol
**buckets
;
143 struct dictionary_hashed_expandable
145 /* How many buckets we currently have. */
147 struct symbol
**buckets
;
148 /* How many syms we currently have; we need this so we will know
149 when to add more buckets. */
153 struct dictionary_linear
156 struct symbol
**syms
;
159 struct dictionary_linear_expandable
161 /* How many symbols we currently have. */
163 struct symbol
**syms
;
164 /* How many symbols we can store before needing to reallocate. */
168 /* And now, the star of our show. */
172 const struct dict_vector
*vector
;
175 struct dictionary_hashed hashed
;
176 struct dictionary_hashed_expandable hashed_expandable
;
177 struct dictionary_linear linear
;
178 struct dictionary_linear_expandable linear_expandable
;
183 /* Accessor macros. */
185 #define DICT_VECTOR(d) (d)->vector
187 /* These can be used for DICT_HASHED_EXPANDABLE, too. */
189 #define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
190 #define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
191 #define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
193 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
195 /* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
197 #define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
198 #define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
199 #define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
201 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
202 (d)->data.linear_expandable.capacity
204 /* The initial size of a DICT_*_EXPANDABLE dictionary. */
206 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
208 /* This calculates the number of buckets we'll use in a hashtable,
209 given the number of symbols that it will contain. */
211 #define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
213 /* Accessor macros for dict_iterators; they're here rather than
214 dictionary.h because code elsewhere should treat dict_iterators as
217 /* The dictionary that the iterator is associated to. */
218 #define DICT_ITERATOR_DICT(iter) (iter)->dict
219 /* For linear dictionaries, the index of the last symbol returned; for
220 hashed dictionaries, the bucket of the last symbol returned. */
221 #define DICT_ITERATOR_INDEX(iter) (iter)->index
222 /* For hashed dictionaries, this points to the last symbol returned;
223 otherwise, this is unused. */
224 #define DICT_ITERATOR_CURRENT(iter) (iter)->current
226 /* Declarations of functions for vectors. */
228 /* Functions that might work across a range of dictionary types. */
230 static void add_symbol_nonexpandable (struct dictionary
*dict
,
233 static void free_obstack (struct dictionary
*dict
);
235 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
238 static struct symbol
*iterator_first_hashed (const struct dictionary
*dict
,
239 struct dict_iterator
*iterator
);
241 static struct symbol
*iterator_next_hashed (struct dict_iterator
*iterator
);
243 static struct symbol
*iter_match_first_hashed (const struct dictionary
*dict
,
245 symbol_compare_ftype
*compare
,
246 struct dict_iterator
*iterator
);
248 static struct symbol
*iter_match_next_hashed (const char *name
,
249 symbol_compare_ftype
*compare
,
250 struct dict_iterator
*iterator
);
252 static unsigned int dict_hash (const char *string
);
254 /* Functions only for DICT_HASHED. */
256 static int size_hashed (const struct dictionary
*dict
);
258 /* Functions only for DICT_HASHED_EXPANDABLE. */
260 static void free_hashed_expandable (struct dictionary
*dict
);
262 static void add_symbol_hashed_expandable (struct dictionary
*dict
,
265 static int size_hashed_expandable (const struct dictionary
*dict
);
267 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
270 static struct symbol
*iterator_first_linear (const struct dictionary
*dict
,
271 struct dict_iterator
*iterator
);
273 static struct symbol
*iterator_next_linear (struct dict_iterator
*iterator
);
275 static struct symbol
*iter_match_first_linear (const struct dictionary
*dict
,
277 symbol_compare_ftype
*compare
,
278 struct dict_iterator
*iterator
);
280 static struct symbol
*iter_match_next_linear (const char *name
,
281 symbol_compare_ftype
*compare
,
282 struct dict_iterator
*iterator
);
284 static int size_linear (const struct dictionary
*dict
);
286 /* Functions only for DICT_LINEAR_EXPANDABLE. */
288 static void free_linear_expandable (struct dictionary
*dict
);
290 static void add_symbol_linear_expandable (struct dictionary
*dict
,
293 /* Various vectors that we'll actually use. */
295 static const struct dict_vector dict_hashed_vector
=
297 DICT_HASHED
, /* type */
298 free_obstack
, /* free */
299 add_symbol_nonexpandable
, /* add_symbol */
300 iterator_first_hashed
, /* iterator_first */
301 iterator_next_hashed
, /* iterator_next */
302 iter_match_first_hashed
, /* iter_name_first */
303 iter_match_next_hashed
, /* iter_name_next */
304 size_hashed
, /* size */
307 static const struct dict_vector dict_hashed_expandable_vector
=
309 DICT_HASHED_EXPANDABLE
, /* type */
310 free_hashed_expandable
, /* free */
311 add_symbol_hashed_expandable
, /* add_symbol */
312 iterator_first_hashed
, /* iterator_first */
313 iterator_next_hashed
, /* iterator_next */
314 iter_match_first_hashed
, /* iter_name_first */
315 iter_match_next_hashed
, /* iter_name_next */
316 size_hashed_expandable
, /* size */
319 static const struct dict_vector dict_linear_vector
=
321 DICT_LINEAR
, /* type */
322 free_obstack
, /* free */
323 add_symbol_nonexpandable
, /* add_symbol */
324 iterator_first_linear
, /* iterator_first */
325 iterator_next_linear
, /* iterator_next */
326 iter_match_first_linear
, /* iter_name_first */
327 iter_match_next_linear
, /* iter_name_next */
328 size_linear
, /* size */
331 static const struct dict_vector dict_linear_expandable_vector
=
333 DICT_LINEAR_EXPANDABLE
, /* type */
334 free_linear_expandable
, /* free */
335 add_symbol_linear_expandable
, /* add_symbol */
336 iterator_first_linear
, /* iterator_first */
337 iterator_next_linear
, /* iterator_next */
338 iter_match_first_linear
, /* iter_name_first */
339 iter_match_next_linear
, /* iter_name_next */
340 size_linear
, /* size */
343 /* Declarations of helper functions (i.e. ones that don't go into
346 static struct symbol
*iterator_hashed_advance (struct dict_iterator
*iter
);
348 static void insert_symbol_hashed (struct dictionary
*dict
,
351 static void expand_hashtable (struct dictionary
*dict
);
353 /* The creation functions. */
355 /* Create a dictionary implemented via a fixed-size hashtable. All
356 memory it uses is allocated on OBSTACK; the environment is
357 initialized from SYMBOL_LIST. */
360 dict_create_hashed (struct obstack
*obstack
,
361 const struct pending
*symbol_list
)
363 struct dictionary
*retval
;
364 int nsyms
= 0, nbuckets
, i
;
365 struct symbol
**buckets
;
366 const struct pending
*list_counter
;
368 retval
= obstack_alloc (obstack
, sizeof (struct dictionary
));
369 DICT_VECTOR (retval
) = &dict_hashed_vector
;
371 /* Calculate the number of symbols, and allocate space for them. */
372 for (list_counter
= symbol_list
;
373 list_counter
!= NULL
;
374 list_counter
= list_counter
->next
)
376 nsyms
+= list_counter
->nsyms
;
378 nbuckets
= DICT_HASHTABLE_SIZE (nsyms
);
379 DICT_HASHED_NBUCKETS (retval
) = nbuckets
;
380 buckets
= obstack_alloc (obstack
, nbuckets
* sizeof (struct symbol
*));
381 memset (buckets
, 0, nbuckets
* sizeof (struct symbol
*));
382 DICT_HASHED_BUCKETS (retval
) = buckets
;
384 /* Now fill the buckets. */
385 for (list_counter
= symbol_list
;
386 list_counter
!= NULL
;
387 list_counter
= list_counter
->next
)
389 for (i
= list_counter
->nsyms
- 1; i
>= 0; --i
)
391 insert_symbol_hashed (retval
, list_counter
->symbol
[i
]);
398 /* Create a dictionary implemented via a hashtable that grows as
399 necessary. The dictionary is initially empty; to add symbols to
400 it, call dict_add_symbol(). Call dict_free() when you're done with
403 extern struct dictionary
*
404 dict_create_hashed_expandable (void)
406 struct dictionary
*retval
;
408 retval
= xmalloc (sizeof (struct dictionary
));
409 DICT_VECTOR (retval
) = &dict_hashed_expandable_vector
;
410 DICT_HASHED_NBUCKETS (retval
) = DICT_EXPANDABLE_INITIAL_CAPACITY
;
411 DICT_HASHED_BUCKETS (retval
) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY
,
412 sizeof (struct symbol
*));
413 DICT_HASHED_EXPANDABLE_NSYMS (retval
) = 0;
418 /* Create a dictionary implemented via a fixed-size array. All memory
419 it uses is allocated on OBSTACK; the environment is initialized
420 from the SYMBOL_LIST. The symbols are ordered in the same order
421 that they're found in SYMBOL_LIST. */
424 dict_create_linear (struct obstack
*obstack
,
425 const struct pending
*symbol_list
)
427 struct dictionary
*retval
;
429 struct symbol
**syms
;
430 const struct pending
*list_counter
;
432 retval
= obstack_alloc (obstack
, sizeof (struct dictionary
));
433 DICT_VECTOR (retval
) = &dict_linear_vector
;
435 /* Calculate the number of symbols, and allocate space for them. */
436 for (list_counter
= symbol_list
;
437 list_counter
!= NULL
;
438 list_counter
= list_counter
->next
)
440 nsyms
+= list_counter
->nsyms
;
442 DICT_LINEAR_NSYMS (retval
) = nsyms
;
443 syms
= obstack_alloc (obstack
, nsyms
* sizeof (struct symbol
*));
444 DICT_LINEAR_SYMS (retval
) = syms
;
446 /* Now fill in the symbols. Start filling in from the back, so as
447 to preserve the original order of the symbols. */
448 for (list_counter
= symbol_list
, j
= nsyms
- 1;
449 list_counter
!= NULL
;
450 list_counter
= list_counter
->next
)
452 for (i
= list_counter
->nsyms
- 1;
456 syms
[j
] = list_counter
->symbol
[i
];
463 /* Create a dictionary implemented via an array that grows as
464 necessary. The dictionary is initially empty; to add symbols to
465 it, call dict_add_symbol(). Call dict_free() when you're done with
469 dict_create_linear_expandable (void)
471 struct dictionary
*retval
;
473 retval
= xmalloc (sizeof (struct dictionary
));
474 DICT_VECTOR (retval
) = &dict_linear_expandable_vector
;
475 DICT_LINEAR_NSYMS (retval
) = 0;
476 DICT_LINEAR_EXPANDABLE_CAPACITY (retval
)
477 = DICT_EXPANDABLE_INITIAL_CAPACITY
;
478 DICT_LINEAR_SYMS (retval
)
479 = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval
)
480 * sizeof (struct symbol
*));
485 /* The functions providing the dictionary interface. */
487 /* Free the memory used by a dictionary that's not on an obstack. (If
491 dict_free (struct dictionary
*dict
)
493 (DICT_VECTOR (dict
))->free (dict
);
496 /* Add SYM to DICT. DICT had better be expandable. */
499 dict_add_symbol (struct dictionary
*dict
, struct symbol
*sym
)
501 (DICT_VECTOR (dict
))->add_symbol (dict
, sym
);
504 /* Initialize ITERATOR to point at the first symbol in DICT, and
505 return that first symbol, or NULL if DICT is empty. */
508 dict_iterator_first (const struct dictionary
*dict
,
509 struct dict_iterator
*iterator
)
511 return (DICT_VECTOR (dict
))->iterator_first (dict
, iterator
);
514 /* Advance ITERATOR, and return the next symbol, or NULL if there are
518 dict_iterator_next (struct dict_iterator
*iterator
)
520 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator
)))
521 ->iterator_next (iterator
);
525 dict_iter_name_first (const struct dictionary
*dict
,
527 struct dict_iterator
*iterator
)
529 return dict_iter_match_first (dict
, name
, strcmp_iw
, iterator
);
533 dict_iter_name_next (const char *name
, struct dict_iterator
*iterator
)
535 return dict_iter_match_next (name
, strcmp_iw
, iterator
);
539 dict_iter_match_first (const struct dictionary
*dict
,
540 const char *name
, symbol_compare_ftype
*compare
,
541 struct dict_iterator
*iterator
)
543 return (DICT_VECTOR (dict
))->iter_match_first (dict
, name
, compare
, iterator
);
547 dict_iter_match_next (const char *name
, symbol_compare_ftype
*compare
,
548 struct dict_iterator
*iterator
)
550 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator
)))
551 ->iter_match_next (name
, compare
, iterator
);
555 dict_size (const struct dictionary
*dict
)
557 return (DICT_VECTOR (dict
))->size (dict
);
560 /* Now come functions (well, one function, currently) that are
561 implemented generically by means of the vtable. Typically, they're
564 /* Test to see if DICT is empty. */
567 dict_empty (struct dictionary
*dict
)
569 struct dict_iterator iter
;
571 return (dict_iterator_first (dict
, &iter
) == NULL
);
575 /* The functions implementing the dictionary interface. */
577 /* Generic functions, where appropriate. */
580 free_obstack (struct dictionary
*dict
)
586 add_symbol_nonexpandable (struct dictionary
*dict
, struct symbol
*sym
)
588 internal_error (__FILE__
, __LINE__
,
589 _("dict_add_symbol: non-expandable dictionary"));
592 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
594 static struct symbol
*
595 iterator_first_hashed (const struct dictionary
*dict
,
596 struct dict_iterator
*iterator
)
598 DICT_ITERATOR_DICT (iterator
) = dict
;
599 DICT_ITERATOR_INDEX (iterator
) = -1;
600 return iterator_hashed_advance (iterator
);
603 static struct symbol
*
604 iterator_next_hashed (struct dict_iterator
*iterator
)
608 next
= DICT_ITERATOR_CURRENT (iterator
)->hash_next
;
611 return iterator_hashed_advance (iterator
);
614 DICT_ITERATOR_CURRENT (iterator
) = next
;
619 static struct symbol
*
620 iterator_hashed_advance (struct dict_iterator
*iterator
)
622 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
623 int nbuckets
= DICT_HASHED_NBUCKETS (dict
);
626 for (i
= DICT_ITERATOR_INDEX (iterator
) + 1; i
< nbuckets
; ++i
)
628 struct symbol
*sym
= DICT_HASHED_BUCKET (dict
, i
);
632 DICT_ITERATOR_INDEX (iterator
) = i
;
633 DICT_ITERATOR_CURRENT (iterator
) = sym
;
641 static struct symbol
*
642 iter_match_first_hashed (const struct dictionary
*dict
, const char *name
,
643 symbol_compare_ftype
*compare
,
644 struct dict_iterator
*iterator
)
646 unsigned int hash_index
= dict_hash (name
) % DICT_HASHED_NBUCKETS (dict
);
649 DICT_ITERATOR_DICT (iterator
) = dict
;
651 /* Loop through the symbols in the given bucket, breaking when SYM
652 first matches. If SYM never matches, it will be set to NULL;
653 either way, we have the right return value. */
655 for (sym
= DICT_HASHED_BUCKET (dict
, hash_index
);
657 sym
= sym
->hash_next
)
659 /* Warning: the order of arguments to compare matters! */
660 if (compare (SYMBOL_SEARCH_NAME (sym
), name
) == 0)
667 DICT_ITERATOR_CURRENT (iterator
) = sym
;
671 static struct symbol
*
672 iter_match_next_hashed (const char *name
, symbol_compare_ftype
*compare
,
673 struct dict_iterator
*iterator
)
677 for (next
= DICT_ITERATOR_CURRENT (iterator
)->hash_next
;
679 next
= next
->hash_next
)
681 if (compare (SYMBOL_SEARCH_NAME (next
), name
) == 0)
685 DICT_ITERATOR_CURRENT (iterator
) = next
;
690 /* Insert SYM into DICT. */
693 insert_symbol_hashed (struct dictionary
*dict
,
696 unsigned int hash_index
;
697 struct symbol
**buckets
= DICT_HASHED_BUCKETS (dict
);
700 dict_hash (SYMBOL_SEARCH_NAME (sym
)) % DICT_HASHED_NBUCKETS (dict
);
701 sym
->hash_next
= buckets
[hash_index
];
702 buckets
[hash_index
] = sym
;
706 size_hashed (const struct dictionary
*dict
)
708 return DICT_HASHED_NBUCKETS (dict
);
711 /* Functions only for DICT_HASHED_EXPANDABLE. */
714 free_hashed_expandable (struct dictionary
*dict
)
716 xfree (DICT_HASHED_BUCKETS (dict
));
721 add_symbol_hashed_expandable (struct dictionary
*dict
,
724 int nsyms
= ++DICT_HASHED_EXPANDABLE_NSYMS (dict
);
726 if (DICT_HASHTABLE_SIZE (nsyms
) > DICT_HASHED_NBUCKETS (dict
))
727 expand_hashtable (dict
);
729 insert_symbol_hashed (dict
, sym
);
730 DICT_HASHED_EXPANDABLE_NSYMS (dict
) = nsyms
;
734 size_hashed_expandable (const struct dictionary
*dict
)
736 return DICT_HASHED_EXPANDABLE_NSYMS (dict
);
740 expand_hashtable (struct dictionary
*dict
)
742 int old_nbuckets
= DICT_HASHED_NBUCKETS (dict
);
743 struct symbol
**old_buckets
= DICT_HASHED_BUCKETS (dict
);
744 int new_nbuckets
= 2*old_nbuckets
+ 1;
745 struct symbol
**new_buckets
= xcalloc (new_nbuckets
,
746 sizeof (struct symbol
*));
749 DICT_HASHED_NBUCKETS (dict
) = new_nbuckets
;
750 DICT_HASHED_BUCKETS (dict
) = new_buckets
;
752 for (i
= 0; i
< old_nbuckets
; ++i
)
754 struct symbol
*sym
, *next_sym
;
756 sym
= old_buckets
[i
];
759 for (next_sym
= sym
->hash_next
;
761 next_sym
= sym
->hash_next
)
763 insert_symbol_hashed (dict
, sym
);
767 insert_symbol_hashed (dict
, sym
);
774 /* Produce an unsigned hash value from STRING0 that is consistent
775 with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
776 That is, two identifiers equivalent according to any of those three
777 comparison operators hash to the same value. */
780 dict_hash (const char *string0
)
782 /* The Ada-encoded version of a name P1.P2...Pn has either the form
783 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
784 are lower-cased identifiers). The <suffix> (which can be empty)
785 encodes additional information about the denoted entity. This
786 routine hashes such names to msymbol_hash_iw(Pn). It actually
787 does this for a superset of both valid Pi and of <suffix>, but
788 in other cases it simply returns msymbol_hash_iw(STRING0). */
796 if (strncmp (string
, "_ada_", 5) == 0)
799 return msymbol_hash_iw (string0
);
810 if (string0
== string
)
811 return msymbol_hash_iw (string0
);
816 return msymbol_hash_iw (string0
);
818 if (string
[1] == '_' && string
!= string0
)
822 if ((c
< 'a' || c
> 'z') && c
!= 'O')
830 hash
= hash
* 67 + *string
- 113;
838 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
840 static struct symbol
*
841 iterator_first_linear (const struct dictionary
*dict
,
842 struct dict_iterator
*iterator
)
844 DICT_ITERATOR_DICT (iterator
) = dict
;
845 DICT_ITERATOR_INDEX (iterator
) = 0;
846 return DICT_LINEAR_NSYMS (dict
) ? DICT_LINEAR_SYM (dict
, 0) : NULL
;
849 static struct symbol
*
850 iterator_next_linear (struct dict_iterator
*iterator
)
852 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
854 if (++DICT_ITERATOR_INDEX (iterator
) >= DICT_LINEAR_NSYMS (dict
))
857 return DICT_LINEAR_SYM (dict
, DICT_ITERATOR_INDEX (iterator
));
860 static struct symbol
*
861 iter_match_first_linear (const struct dictionary
*dict
,
862 const char *name
, symbol_compare_ftype
*compare
,
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
, symbol_compare_ftype
*compare
,
873 struct dict_iterator
*iterator
)
875 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
876 int i
, nsyms
= DICT_LINEAR_NSYMS (dict
);
877 struct symbol
*sym
, *retval
= NULL
;
879 for (i
= DICT_ITERATOR_INDEX (iterator
) + 1; i
< nsyms
; ++i
)
881 sym
= DICT_LINEAR_SYM (dict
, i
);
882 if (compare (SYMBOL_SEARCH_NAME (sym
), name
) == 0)
889 DICT_ITERATOR_INDEX (iterator
) = i
;
895 size_linear (const struct dictionary
*dict
)
897 return DICT_LINEAR_NSYMS (dict
);
900 /* Functions only for DICT_LINEAR_EXPANDABLE. */
903 free_linear_expandable (struct dictionary
*dict
)
905 xfree (DICT_LINEAR_SYMS (dict
));
911 add_symbol_linear_expandable (struct dictionary
*dict
,
914 int nsyms
= ++DICT_LINEAR_NSYMS (dict
);
916 /* Do we have enough room? If not, grow it. */
917 if (nsyms
> DICT_LINEAR_EXPANDABLE_CAPACITY (dict
))
919 DICT_LINEAR_EXPANDABLE_CAPACITY (dict
) *= 2;
920 DICT_LINEAR_SYMS (dict
)
921 = xrealloc (DICT_LINEAR_SYMS (dict
),
922 DICT_LINEAR_EXPANDABLE_CAPACITY (dict
)
923 * sizeof (struct symbol
*));
926 DICT_LINEAR_SYM (dict
, nsyms
- 1) = sym
;