1 /* Routines for name->symbol lookups in GDB.
3 Copyright (C) 2003-2015 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 "dictionary.h"
30 /* This file implements dictionaries, which are tables that associate
31 symbols to names. They are represented by an opaque type 'struct
32 dictionary'. That type has various internal implementations, which
33 you can choose between depending on what properties you need
34 (e.g. fast lookup, order-preserving, expandable).
36 Each dictionary starts with a 'virtual function table' that
37 contains the functions that actually implement the various
38 operations that dictionaries provide. (Note, however, that, for
39 the sake of client code, we also provide some functions that can be
40 implemented generically in terms of the functions in the vtable.)
42 To add a new dictionary implementation <impl>, what you should do
45 * Add a new element DICT_<IMPL> to dict_type.
47 * Create a new structure dictionary_<impl>. If your new
48 implementation is a variant of an existing one, make sure that
49 their structs have the same initial data members. Define accessor
50 macros for your new data members.
52 * Implement all the functions in dict_vector as static functions,
53 whose name is the same as the corresponding member of dict_vector
54 plus _<impl>. You don't have to do this for those members where
55 you can reuse existing generic functions
56 (e.g. add_symbol_nonexpandable, free_obstack) or in the case where
57 your new implementation is a variant of an existing implementation
58 and where the variant doesn't affect the member function in
61 * Define a static const struct dict_vector dict_<impl>_vector.
63 * Define a function dict_create_<impl> to create these
64 gizmos. Add its declaration to dictionary.h.
66 To add a new operation <op> on all existing implementations, what
69 * Add a new member <op> to struct dict_vector.
71 * If there is useful generic behavior <op>, define a static
72 function <op>_something_informative that implements that behavior.
73 (E.g. add_symbol_nonexpandable, free_obstack.)
75 * For every implementation <impl> that should have its own specific
76 behavior for <op>, define a static function <op>_<impl>
79 * Modify all existing dict_vector_<impl>'s to include the appropriate
82 * Define a function dict_<op> that looks up <op> in the dict_vector
83 and calls the appropriate function. Add a declaration for
84 dict_<op> to dictionary.h. */
86 /* An enum representing the various implementations of dictionaries.
87 Used only for debugging. */
91 /* Symbols are stored in a fixed-size hash table. */
93 /* Symbols are stored in an expandable hash table. */
94 DICT_HASHED_EXPANDABLE
,
95 /* Symbols are stored in a fixed-size array. */
97 /* Symbols are stored in an expandable array. */
98 DICT_LINEAR_EXPANDABLE
101 /* The virtual function table. */
105 /* The type of the dictionary. This is only here to make debugging
106 a bit easier; it's not actually used. */
108 /* The function to free a dictionary. */
109 void (*free
) (struct dictionary
*dict
);
110 /* Add a symbol to a dictionary, if possible. */
111 void (*add_symbol
) (struct dictionary
*dict
, struct symbol
*sym
);
112 /* Iterator functions. */
113 struct symbol
*(*iterator_first
) (const struct dictionary
*dict
,
114 struct dict_iterator
*iterator
);
115 struct symbol
*(*iterator_next
) (struct dict_iterator
*iterator
);
116 /* Functions to iterate over symbols with a given name. */
117 struct symbol
*(*iter_match_first
) (const struct dictionary
*dict
,
119 symbol_compare_ftype
*equiv
,
120 struct dict_iterator
*iterator
);
121 struct symbol
*(*iter_match_next
) (const char *name
,
122 symbol_compare_ftype
*equiv
,
123 struct dict_iterator
*iterator
);
124 /* A size function, for maint print symtabs. */
125 int (*size
) (const struct dictionary
*dict
);
128 /* Now comes the structs used to store the data for different
129 implementations. If two implementations have data in common, put
130 the common data at the top of their structs, ordered in the same
133 struct dictionary_hashed
136 struct symbol
**buckets
;
139 struct dictionary_hashed_expandable
141 /* How many buckets we currently have. */
143 struct symbol
**buckets
;
144 /* How many syms we currently have; we need this so we will know
145 when to add more buckets. */
149 struct dictionary_linear
152 struct symbol
**syms
;
155 struct dictionary_linear_expandable
157 /* How many symbols we currently have. */
159 struct symbol
**syms
;
160 /* How many symbols we can store before needing to reallocate. */
164 /* And now, the star of our show. */
168 const struct dict_vector
*vector
;
171 struct dictionary_hashed hashed
;
172 struct dictionary_hashed_expandable hashed_expandable
;
173 struct dictionary_linear linear
;
174 struct dictionary_linear_expandable linear_expandable
;
179 /* Accessor macros. */
181 #define DICT_VECTOR(d) (d)->vector
183 /* These can be used for DICT_HASHED_EXPANDABLE, too. */
185 #define DICT_HASHED_NBUCKETS(d) (d)->data.hashed.nbuckets
186 #define DICT_HASHED_BUCKETS(d) (d)->data.hashed.buckets
187 #define DICT_HASHED_BUCKET(d,i) DICT_HASHED_BUCKETS (d) [i]
189 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
191 /* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
193 #define DICT_LINEAR_NSYMS(d) (d)->data.linear.nsyms
194 #define DICT_LINEAR_SYMS(d) (d)->data.linear.syms
195 #define DICT_LINEAR_SYM(d,i) DICT_LINEAR_SYMS (d) [i]
197 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
198 (d)->data.linear_expandable.capacity
200 /* The initial size of a DICT_*_EXPANDABLE dictionary. */
202 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
204 /* This calculates the number of buckets we'll use in a hashtable,
205 given the number of symbols that it will contain. */
207 #define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
209 /* Accessor macros for dict_iterators; they're here rather than
210 dictionary.h because code elsewhere should treat dict_iterators as
213 /* The dictionary that the iterator is associated to. */
214 #define DICT_ITERATOR_DICT(iter) (iter)->dict
215 /* For linear dictionaries, the index of the last symbol returned; for
216 hashed dictionaries, the bucket of the last symbol returned. */
217 #define DICT_ITERATOR_INDEX(iter) (iter)->index
218 /* For hashed dictionaries, this points to the last symbol returned;
219 otherwise, this is unused. */
220 #define DICT_ITERATOR_CURRENT(iter) (iter)->current
222 /* Declarations of functions for vectors. */
224 /* Functions that might work across a range of dictionary types. */
226 static void add_symbol_nonexpandable (struct dictionary
*dict
,
229 static void free_obstack (struct dictionary
*dict
);
231 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
234 static struct symbol
*iterator_first_hashed (const struct dictionary
*dict
,
235 struct dict_iterator
*iterator
);
237 static struct symbol
*iterator_next_hashed (struct dict_iterator
*iterator
);
239 static struct symbol
*iter_match_first_hashed (const struct dictionary
*dict
,
241 symbol_compare_ftype
*compare
,
242 struct dict_iterator
*iterator
);
244 static struct symbol
*iter_match_next_hashed (const char *name
,
245 symbol_compare_ftype
*compare
,
246 struct dict_iterator
*iterator
);
248 static unsigned int dict_hash (const char *string
);
250 /* Functions only for DICT_HASHED. */
252 static int size_hashed (const struct dictionary
*dict
);
254 /* Functions only for DICT_HASHED_EXPANDABLE. */
256 static void free_hashed_expandable (struct dictionary
*dict
);
258 static void add_symbol_hashed_expandable (struct dictionary
*dict
,
261 static int size_hashed_expandable (const struct dictionary
*dict
);
263 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
266 static struct symbol
*iterator_first_linear (const struct dictionary
*dict
,
267 struct dict_iterator
*iterator
);
269 static struct symbol
*iterator_next_linear (struct dict_iterator
*iterator
);
271 static struct symbol
*iter_match_first_linear (const struct dictionary
*dict
,
273 symbol_compare_ftype
*compare
,
274 struct dict_iterator
*iterator
);
276 static struct symbol
*iter_match_next_linear (const char *name
,
277 symbol_compare_ftype
*compare
,
278 struct dict_iterator
*iterator
);
280 static int size_linear (const struct dictionary
*dict
);
282 /* Functions only for DICT_LINEAR_EXPANDABLE. */
284 static void free_linear_expandable (struct dictionary
*dict
);
286 static void add_symbol_linear_expandable (struct dictionary
*dict
,
289 /* Various vectors that we'll actually use. */
291 static const struct dict_vector dict_hashed_vector
=
293 DICT_HASHED
, /* type */
294 free_obstack
, /* free */
295 add_symbol_nonexpandable
, /* add_symbol */
296 iterator_first_hashed
, /* iterator_first */
297 iterator_next_hashed
, /* iterator_next */
298 iter_match_first_hashed
, /* iter_name_first */
299 iter_match_next_hashed
, /* iter_name_next */
300 size_hashed
, /* size */
303 static const struct dict_vector dict_hashed_expandable_vector
=
305 DICT_HASHED_EXPANDABLE
, /* type */
306 free_hashed_expandable
, /* free */
307 add_symbol_hashed_expandable
, /* add_symbol */
308 iterator_first_hashed
, /* iterator_first */
309 iterator_next_hashed
, /* iterator_next */
310 iter_match_first_hashed
, /* iter_name_first */
311 iter_match_next_hashed
, /* iter_name_next */
312 size_hashed_expandable
, /* size */
315 static const struct dict_vector dict_linear_vector
=
317 DICT_LINEAR
, /* type */
318 free_obstack
, /* free */
319 add_symbol_nonexpandable
, /* add_symbol */
320 iterator_first_linear
, /* iterator_first */
321 iterator_next_linear
, /* iterator_next */
322 iter_match_first_linear
, /* iter_name_first */
323 iter_match_next_linear
, /* iter_name_next */
324 size_linear
, /* size */
327 static const struct dict_vector dict_linear_expandable_vector
=
329 DICT_LINEAR_EXPANDABLE
, /* type */
330 free_linear_expandable
, /* free */
331 add_symbol_linear_expandable
, /* add_symbol */
332 iterator_first_linear
, /* iterator_first */
333 iterator_next_linear
, /* iterator_next */
334 iter_match_first_linear
, /* iter_name_first */
335 iter_match_next_linear
, /* iter_name_next */
336 size_linear
, /* size */
339 /* Declarations of helper functions (i.e. ones that don't go into
342 static struct symbol
*iterator_hashed_advance (struct dict_iterator
*iter
);
344 static void insert_symbol_hashed (struct dictionary
*dict
,
347 static void expand_hashtable (struct dictionary
*dict
);
349 /* The creation functions. */
351 /* Create a dictionary implemented via a fixed-size hashtable. All
352 memory it uses is allocated on OBSTACK; the environment is
353 initialized from SYMBOL_LIST. */
356 dict_create_hashed (struct obstack
*obstack
,
357 const struct pending
*symbol_list
)
359 struct dictionary
*retval
;
360 int nsyms
= 0, nbuckets
, i
;
361 struct symbol
**buckets
;
362 const struct pending
*list_counter
;
364 retval
= XOBNEW (obstack
, struct dictionary
);
365 DICT_VECTOR (retval
) = &dict_hashed_vector
;
367 /* Calculate the number of symbols, and allocate space for them. */
368 for (list_counter
= symbol_list
;
369 list_counter
!= NULL
;
370 list_counter
= list_counter
->next
)
372 nsyms
+= list_counter
->nsyms
;
374 nbuckets
= DICT_HASHTABLE_SIZE (nsyms
);
375 DICT_HASHED_NBUCKETS (retval
) = nbuckets
;
376 buckets
= XOBNEWVEC (obstack
, struct symbol
*, nbuckets
);
377 memset (buckets
, 0, nbuckets
* sizeof (struct symbol
*));
378 DICT_HASHED_BUCKETS (retval
) = buckets
;
380 /* Now fill the buckets. */
381 for (list_counter
= symbol_list
;
382 list_counter
!= NULL
;
383 list_counter
= list_counter
->next
)
385 for (i
= list_counter
->nsyms
- 1; i
>= 0; --i
)
387 insert_symbol_hashed (retval
, list_counter
->symbol
[i
]);
394 /* Create a dictionary implemented via a hashtable that grows as
395 necessary. The dictionary is initially empty; to add symbols to
396 it, call dict_add_symbol(). Call dict_free() when you're done with
399 extern struct dictionary
*
400 dict_create_hashed_expandable (void)
402 struct dictionary
*retval
= XNEW (struct dictionary
);
404 DICT_VECTOR (retval
) = &dict_hashed_expandable_vector
;
405 DICT_HASHED_NBUCKETS (retval
) = DICT_EXPANDABLE_INITIAL_CAPACITY
;
406 DICT_HASHED_BUCKETS (retval
) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY
,
407 sizeof (struct symbol
*));
408 DICT_HASHED_EXPANDABLE_NSYMS (retval
) = 0;
413 /* Create a dictionary implemented via a fixed-size array. All memory
414 it uses is allocated on OBSTACK; the environment is initialized
415 from the SYMBOL_LIST. The symbols are ordered in the same order
416 that they're found in SYMBOL_LIST. */
419 dict_create_linear (struct obstack
*obstack
,
420 const struct pending
*symbol_list
)
422 struct dictionary
*retval
;
424 struct symbol
**syms
;
425 const struct pending
*list_counter
;
427 retval
= XOBNEW (obstack
, struct dictionary
);
428 DICT_VECTOR (retval
) = &dict_linear_vector
;
430 /* Calculate the number of symbols, and allocate space for them. */
431 for (list_counter
= symbol_list
;
432 list_counter
!= NULL
;
433 list_counter
= list_counter
->next
)
435 nsyms
+= list_counter
->nsyms
;
437 DICT_LINEAR_NSYMS (retval
) = nsyms
;
438 syms
= XOBNEWVEC (obstack
, struct symbol
*, nsyms
);
439 DICT_LINEAR_SYMS (retval
) = syms
;
441 /* Now fill in the symbols. Start filling in from the back, so as
442 to preserve the original order of the symbols. */
443 for (list_counter
= symbol_list
, j
= nsyms
- 1;
444 list_counter
!= NULL
;
445 list_counter
= list_counter
->next
)
447 for (i
= list_counter
->nsyms
- 1;
451 syms
[j
] = list_counter
->symbol
[i
];
458 /* Create a dictionary implemented via an array that grows as
459 necessary. The dictionary is initially empty; to add symbols to
460 it, call dict_add_symbol(). Call dict_free() when you're done with
464 dict_create_linear_expandable (void)
466 struct dictionary
*retval
= XNEW (struct dictionary
);
468 DICT_VECTOR (retval
) = &dict_linear_expandable_vector
;
469 DICT_LINEAR_NSYMS (retval
) = 0;
470 DICT_LINEAR_EXPANDABLE_CAPACITY (retval
)
471 = DICT_EXPANDABLE_INITIAL_CAPACITY
;
472 DICT_LINEAR_SYMS (retval
)
473 = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval
)
474 * sizeof (struct symbol
*));
479 /* The functions providing the dictionary interface. */
481 /* Free the memory used by a dictionary that's not on an obstack. (If
485 dict_free (struct dictionary
*dict
)
487 (DICT_VECTOR (dict
))->free (dict
);
490 /* Add SYM to DICT. DICT had better be expandable. */
493 dict_add_symbol (struct dictionary
*dict
, struct symbol
*sym
)
495 (DICT_VECTOR (dict
))->add_symbol (dict
, sym
);
498 /* Utility to add a list of symbols to a dictionary.
499 DICT must be an expandable dictionary. */
502 dict_add_pending (struct dictionary
*dict
, const struct pending
*symbol_list
)
504 const struct pending
*list
;
507 for (list
= symbol_list
; list
!= NULL
; list
= list
->next
)
509 for (i
= 0; i
< list
->nsyms
; ++i
)
510 dict_add_symbol (dict
, list
->symbol
[i
]);
514 /* Initialize ITERATOR to point at the first symbol in DICT, and
515 return that first symbol, or NULL if DICT is empty. */
518 dict_iterator_first (const struct dictionary
*dict
,
519 struct dict_iterator
*iterator
)
521 return (DICT_VECTOR (dict
))->iterator_first (dict
, iterator
);
524 /* Advance ITERATOR, and return the next symbol, or NULL if there are
528 dict_iterator_next (struct dict_iterator
*iterator
)
530 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator
)))
531 ->iterator_next (iterator
);
535 dict_iter_name_first (const struct dictionary
*dict
,
537 struct dict_iterator
*iterator
)
539 return dict_iter_match_first (dict
, name
, strcmp_iw
, iterator
);
543 dict_iter_name_next (const char *name
, struct dict_iterator
*iterator
)
545 return dict_iter_match_next (name
, strcmp_iw
, iterator
);
549 dict_iter_match_first (const struct dictionary
*dict
,
550 const char *name
, symbol_compare_ftype
*compare
,
551 struct dict_iterator
*iterator
)
553 return (DICT_VECTOR (dict
))->iter_match_first (dict
, name
,
558 dict_iter_match_next (const char *name
, symbol_compare_ftype
*compare
,
559 struct dict_iterator
*iterator
)
561 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator
)))
562 ->iter_match_next (name
, compare
, iterator
);
566 dict_size (const struct dictionary
*dict
)
568 return (DICT_VECTOR (dict
))->size (dict
);
571 /* Now come functions (well, one function, currently) that are
572 implemented generically by means of the vtable. Typically, they're
575 /* Test to see if DICT is empty. */
578 dict_empty (struct dictionary
*dict
)
580 struct dict_iterator iter
;
582 return (dict_iterator_first (dict
, &iter
) == NULL
);
586 /* The functions implementing the dictionary interface. */
588 /* Generic functions, where appropriate. */
591 free_obstack (struct dictionary
*dict
)
597 add_symbol_nonexpandable (struct dictionary
*dict
, struct symbol
*sym
)
599 internal_error (__FILE__
, __LINE__
,
600 _("dict_add_symbol: non-expandable dictionary"));
603 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
605 static struct symbol
*
606 iterator_first_hashed (const struct dictionary
*dict
,
607 struct dict_iterator
*iterator
)
609 DICT_ITERATOR_DICT (iterator
) = dict
;
610 DICT_ITERATOR_INDEX (iterator
) = -1;
611 return iterator_hashed_advance (iterator
);
614 static struct symbol
*
615 iterator_next_hashed (struct dict_iterator
*iterator
)
619 next
= DICT_ITERATOR_CURRENT (iterator
)->hash_next
;
622 return iterator_hashed_advance (iterator
);
625 DICT_ITERATOR_CURRENT (iterator
) = next
;
630 static struct symbol
*
631 iterator_hashed_advance (struct dict_iterator
*iterator
)
633 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
634 int nbuckets
= DICT_HASHED_NBUCKETS (dict
);
637 for (i
= DICT_ITERATOR_INDEX (iterator
) + 1; i
< nbuckets
; ++i
)
639 struct symbol
*sym
= DICT_HASHED_BUCKET (dict
, i
);
643 DICT_ITERATOR_INDEX (iterator
) = i
;
644 DICT_ITERATOR_CURRENT (iterator
) = sym
;
652 static struct symbol
*
653 iter_match_first_hashed (const struct dictionary
*dict
, const char *name
,
654 symbol_compare_ftype
*compare
,
655 struct dict_iterator
*iterator
)
657 unsigned int hash_index
= dict_hash (name
) % DICT_HASHED_NBUCKETS (dict
);
660 DICT_ITERATOR_DICT (iterator
) = dict
;
662 /* Loop through the symbols in the given bucket, breaking when SYM
663 first matches. If SYM never matches, it will be set to NULL;
664 either way, we have the right return value. */
666 for (sym
= DICT_HASHED_BUCKET (dict
, hash_index
);
668 sym
= sym
->hash_next
)
670 /* Warning: the order of arguments to compare matters! */
671 if (compare (SYMBOL_SEARCH_NAME (sym
), name
) == 0)
678 DICT_ITERATOR_CURRENT (iterator
) = sym
;
682 static struct symbol
*
683 iter_match_next_hashed (const char *name
, symbol_compare_ftype
*compare
,
684 struct dict_iterator
*iterator
)
688 for (next
= DICT_ITERATOR_CURRENT (iterator
)->hash_next
;
690 next
= next
->hash_next
)
692 if (compare (SYMBOL_SEARCH_NAME (next
), name
) == 0)
696 DICT_ITERATOR_CURRENT (iterator
) = next
;
701 /* Insert SYM into DICT. */
704 insert_symbol_hashed (struct dictionary
*dict
,
707 unsigned int hash_index
;
708 struct symbol
**buckets
= DICT_HASHED_BUCKETS (dict
);
711 dict_hash (SYMBOL_SEARCH_NAME (sym
)) % DICT_HASHED_NBUCKETS (dict
);
712 sym
->hash_next
= buckets
[hash_index
];
713 buckets
[hash_index
] = sym
;
717 size_hashed (const struct dictionary
*dict
)
719 return DICT_HASHED_NBUCKETS (dict
);
722 /* Functions only for DICT_HASHED_EXPANDABLE. */
725 free_hashed_expandable (struct dictionary
*dict
)
727 xfree (DICT_HASHED_BUCKETS (dict
));
732 add_symbol_hashed_expandable (struct dictionary
*dict
,
735 int nsyms
= ++DICT_HASHED_EXPANDABLE_NSYMS (dict
);
737 if (DICT_HASHTABLE_SIZE (nsyms
) > DICT_HASHED_NBUCKETS (dict
))
738 expand_hashtable (dict
);
740 insert_symbol_hashed (dict
, sym
);
741 DICT_HASHED_EXPANDABLE_NSYMS (dict
) = nsyms
;
745 size_hashed_expandable (const struct dictionary
*dict
)
747 return DICT_HASHED_EXPANDABLE_NSYMS (dict
);
751 expand_hashtable (struct dictionary
*dict
)
753 int old_nbuckets
= DICT_HASHED_NBUCKETS (dict
);
754 struct symbol
**old_buckets
= DICT_HASHED_BUCKETS (dict
);
755 int new_nbuckets
= 2*old_nbuckets
+ 1;
756 struct symbol
**new_buckets
= xcalloc (new_nbuckets
,
757 sizeof (struct symbol
*));
760 DICT_HASHED_NBUCKETS (dict
) = new_nbuckets
;
761 DICT_HASHED_BUCKETS (dict
) = new_buckets
;
763 for (i
= 0; i
< old_nbuckets
; ++i
)
765 struct symbol
*sym
, *next_sym
;
767 sym
= old_buckets
[i
];
770 for (next_sym
= sym
->hash_next
;
772 next_sym
= sym
->hash_next
)
774 insert_symbol_hashed (dict
, sym
);
778 insert_symbol_hashed (dict
, sym
);
785 /* Produce an unsigned hash value from STRING0 that is consistent
786 with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
787 That is, two identifiers equivalent according to any of those three
788 comparison operators hash to the same value. */
791 dict_hash (const char *string0
)
793 /* The Ada-encoded version of a name P1.P2...Pn has either the form
794 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
795 are lower-cased identifiers). The <suffix> (which can be empty)
796 encodes additional information about the denoted entity. This
797 routine hashes such names to msymbol_hash_iw(Pn). It actually
798 does this for a superset of both valid Pi and of <suffix>, but
799 in other cases it simply returns msymbol_hash_iw(STRING0). */
807 if (startswith (string
, "_ada_"))
810 return msymbol_hash_iw (string0
);
816 /* Ignore "TKB" suffixes.
818 These are used by Ada for subprograms implementing a task body.
819 For instance for a task T inside package Pck, the name of the
820 subprogram implementing T's body is `pck__tTKB'. We need to
821 ignore the "TKB" suffix because searches for this task body
822 subprogram are going to be performed using `pck__t' (the encoded
823 version of the natural name `pck.t'). */
824 if (strcmp (string
, "TKB") == 0)
832 if (string0
== string
)
833 return msymbol_hash_iw (string0
);
838 return msymbol_hash_iw (string0
);
840 if (string
[1] == '_' && string
!= string0
)
844 if ((c
< 'a' || c
> 'z') && c
!= 'O')
852 hash
= SYMBOL_HASH_NEXT (hash
, *string
);
860 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
862 static struct symbol
*
863 iterator_first_linear (const struct dictionary
*dict
,
864 struct dict_iterator
*iterator
)
866 DICT_ITERATOR_DICT (iterator
) = dict
;
867 DICT_ITERATOR_INDEX (iterator
) = 0;
868 return DICT_LINEAR_NSYMS (dict
) ? DICT_LINEAR_SYM (dict
, 0) : NULL
;
871 static struct symbol
*
872 iterator_next_linear (struct dict_iterator
*iterator
)
874 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
876 if (++DICT_ITERATOR_INDEX (iterator
) >= DICT_LINEAR_NSYMS (dict
))
879 return DICT_LINEAR_SYM (dict
, DICT_ITERATOR_INDEX (iterator
));
882 static struct symbol
*
883 iter_match_first_linear (const struct dictionary
*dict
,
884 const char *name
, symbol_compare_ftype
*compare
,
885 struct dict_iterator
*iterator
)
887 DICT_ITERATOR_DICT (iterator
) = dict
;
888 DICT_ITERATOR_INDEX (iterator
) = -1;
890 return iter_match_next_linear (name
, compare
, iterator
);
893 static struct symbol
*
894 iter_match_next_linear (const char *name
, symbol_compare_ftype
*compare
,
895 struct dict_iterator
*iterator
)
897 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
898 int i
, nsyms
= DICT_LINEAR_NSYMS (dict
);
899 struct symbol
*sym
, *retval
= NULL
;
901 for (i
= DICT_ITERATOR_INDEX (iterator
) + 1; i
< nsyms
; ++i
)
903 sym
= DICT_LINEAR_SYM (dict
, i
);
904 if (compare (SYMBOL_SEARCH_NAME (sym
), name
) == 0)
911 DICT_ITERATOR_INDEX (iterator
) = i
;
917 size_linear (const struct dictionary
*dict
)
919 return DICT_LINEAR_NSYMS (dict
);
922 /* Functions only for DICT_LINEAR_EXPANDABLE. */
925 free_linear_expandable (struct dictionary
*dict
)
927 xfree (DICT_LINEAR_SYMS (dict
));
933 add_symbol_linear_expandable (struct dictionary
*dict
,
936 int nsyms
= ++DICT_LINEAR_NSYMS (dict
);
938 /* Do we have enough room? If not, grow it. */
939 if (nsyms
> DICT_LINEAR_EXPANDABLE_CAPACITY (dict
))
941 DICT_LINEAR_EXPANDABLE_CAPACITY (dict
) *= 2;
942 DICT_LINEAR_SYMS (dict
)
943 = xrealloc (DICT_LINEAR_SYMS (dict
),
944 DICT_LINEAR_EXPANDABLE_CAPACITY (dict
)
945 * sizeof (struct symbol
*));
948 DICT_LINEAR_SYM (dict
, nsyms
- 1) = sym
;