1 /* Routines for name->symbol lookups in GDB.
3 Copyright (C) 2003-2017 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
,
118 const lookup_name_info
&name
,
119 struct dict_iterator
*iterator
);
120 struct symbol
*(*iter_match_next
) (const lookup_name_info
&name
,
121 struct dict_iterator
*iterator
);
122 /* A size function, for maint print symtabs. */
123 int (*size
) (const struct dictionary
*dict
);
126 /* Now comes the structs used to store the data for different
127 implementations. If two implementations have data in common, put
128 the common data at the top of their structs, ordered in the same
131 struct dictionary_hashed
134 struct symbol
**buckets
;
137 struct dictionary_hashed_expandable
139 /* How many buckets we currently have. */
141 struct symbol
**buckets
;
142 /* How many syms we currently have; we need this so we will know
143 when to add more buckets. */
147 struct dictionary_linear
150 struct symbol
**syms
;
153 struct dictionary_linear_expandable
155 /* How many symbols we currently have. */
157 struct symbol
**syms
;
158 /* How many symbols we can store before needing to reallocate. */
162 /* And now, the star of our show. */
166 const struct language_defn
*language
;
167 const struct dict_vector
*vector
;
170 struct dictionary_hashed hashed
;
171 struct dictionary_hashed_expandable hashed_expandable
;
172 struct dictionary_linear linear
;
173 struct dictionary_linear_expandable linear_expandable
;
178 /* Accessor macros. */
180 #define DICT_VECTOR(d) (d)->vector
181 #define DICT_LANGUAGE(d) (d)->language
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
,
240 const lookup_name_info
&name
,
241 struct dict_iterator
*iterator
);
243 static struct symbol
*iter_match_next_hashed (const lookup_name_info
&name
,
244 struct dict_iterator
*iterator
);
246 /* Functions only for DICT_HASHED. */
248 static int size_hashed (const struct dictionary
*dict
);
250 /* Functions only for DICT_HASHED_EXPANDABLE. */
252 static void free_hashed_expandable (struct dictionary
*dict
);
254 static void add_symbol_hashed_expandable (struct dictionary
*dict
,
257 static int size_hashed_expandable (const struct dictionary
*dict
);
259 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
262 static struct symbol
*iterator_first_linear (const struct dictionary
*dict
,
263 struct dict_iterator
*iterator
);
265 static struct symbol
*iterator_next_linear (struct dict_iterator
*iterator
);
267 static struct symbol
*iter_match_first_linear (const struct dictionary
*dict
,
268 const lookup_name_info
&name
,
269 struct dict_iterator
*iterator
);
271 static struct symbol
*iter_match_next_linear (const lookup_name_info
&name
,
272 struct dict_iterator
*iterator
);
274 static int size_linear (const struct dictionary
*dict
);
276 /* Functions only for DICT_LINEAR_EXPANDABLE. */
278 static void free_linear_expandable (struct dictionary
*dict
);
280 static void add_symbol_linear_expandable (struct dictionary
*dict
,
283 /* Various vectors that we'll actually use. */
285 static const struct dict_vector dict_hashed_vector
=
287 DICT_HASHED
, /* type */
288 free_obstack
, /* free */
289 add_symbol_nonexpandable
, /* add_symbol */
290 iterator_first_hashed
, /* iterator_first */
291 iterator_next_hashed
, /* iterator_next */
292 iter_match_first_hashed
, /* iter_name_first */
293 iter_match_next_hashed
, /* iter_name_next */
294 size_hashed
, /* size */
297 static const struct dict_vector dict_hashed_expandable_vector
=
299 DICT_HASHED_EXPANDABLE
, /* type */
300 free_hashed_expandable
, /* free */
301 add_symbol_hashed_expandable
, /* add_symbol */
302 iterator_first_hashed
, /* iterator_first */
303 iterator_next_hashed
, /* iterator_next */
304 iter_match_first_hashed
, /* iter_name_first */
305 iter_match_next_hashed
, /* iter_name_next */
306 size_hashed_expandable
, /* size */
309 static const struct dict_vector dict_linear_vector
=
311 DICT_LINEAR
, /* type */
312 free_obstack
, /* free */
313 add_symbol_nonexpandable
, /* add_symbol */
314 iterator_first_linear
, /* iterator_first */
315 iterator_next_linear
, /* iterator_next */
316 iter_match_first_linear
, /* iter_name_first */
317 iter_match_next_linear
, /* iter_name_next */
318 size_linear
, /* size */
321 static const struct dict_vector dict_linear_expandable_vector
=
323 DICT_LINEAR_EXPANDABLE
, /* type */
324 free_linear_expandable
, /* free */
325 add_symbol_linear_expandable
, /* add_symbol */
326 iterator_first_linear
, /* iterator_first */
327 iterator_next_linear
, /* iterator_next */
328 iter_match_first_linear
, /* iter_name_first */
329 iter_match_next_linear
, /* iter_name_next */
330 size_linear
, /* size */
333 /* Declarations of helper functions (i.e. ones that don't go into
336 static struct symbol
*iterator_hashed_advance (struct dict_iterator
*iter
);
338 static void insert_symbol_hashed (struct dictionary
*dict
,
341 static void expand_hashtable (struct dictionary
*dict
);
343 /* The creation functions. */
345 /* See dictionary.h. */
348 dict_create_hashed (struct obstack
*obstack
,
349 enum language language
,
350 const struct pending
*symbol_list
)
352 struct dictionary
*retval
;
353 int nsyms
= 0, nbuckets
, i
;
354 struct symbol
**buckets
;
355 const struct pending
*list_counter
;
357 retval
= XOBNEW (obstack
, struct dictionary
);
358 DICT_VECTOR (retval
) = &dict_hashed_vector
;
359 DICT_LANGUAGE (retval
) = language_def (language
);
361 /* Calculate the number of symbols, and allocate space for them. */
362 for (list_counter
= symbol_list
;
363 list_counter
!= NULL
;
364 list_counter
= list_counter
->next
)
366 nsyms
+= list_counter
->nsyms
;
368 nbuckets
= DICT_HASHTABLE_SIZE (nsyms
);
369 DICT_HASHED_NBUCKETS (retval
) = nbuckets
;
370 buckets
= XOBNEWVEC (obstack
, struct symbol
*, nbuckets
);
371 memset (buckets
, 0, nbuckets
* sizeof (struct symbol
*));
372 DICT_HASHED_BUCKETS (retval
) = buckets
;
374 /* Now fill the buckets. */
375 for (list_counter
= symbol_list
;
376 list_counter
!= NULL
;
377 list_counter
= list_counter
->next
)
379 for (i
= list_counter
->nsyms
- 1; i
>= 0; --i
)
381 insert_symbol_hashed (retval
, list_counter
->symbol
[i
]);
388 /* See dictionary.h. */
390 extern struct dictionary
*
391 dict_create_hashed_expandable (enum language language
)
393 struct dictionary
*retval
= XNEW (struct dictionary
);
395 DICT_VECTOR (retval
) = &dict_hashed_expandable_vector
;
396 DICT_LANGUAGE (retval
) = language_def (language
);
397 DICT_HASHED_NBUCKETS (retval
) = DICT_EXPANDABLE_INITIAL_CAPACITY
;
398 DICT_HASHED_BUCKETS (retval
) = XCNEWVEC (struct symbol
*,
399 DICT_EXPANDABLE_INITIAL_CAPACITY
);
400 DICT_HASHED_EXPANDABLE_NSYMS (retval
) = 0;
405 /* See dictionary.h. */
408 dict_create_linear (struct obstack
*obstack
,
409 enum language language
,
410 const struct pending
*symbol_list
)
412 struct dictionary
*retval
;
414 struct symbol
**syms
;
415 const struct pending
*list_counter
;
417 retval
= XOBNEW (obstack
, struct dictionary
);
418 DICT_VECTOR (retval
) = &dict_linear_vector
;
419 DICT_LANGUAGE (retval
) = language_def (language
);
421 /* Calculate the number of symbols, and allocate space for them. */
422 for (list_counter
= symbol_list
;
423 list_counter
!= NULL
;
424 list_counter
= list_counter
->next
)
426 nsyms
+= list_counter
->nsyms
;
428 DICT_LINEAR_NSYMS (retval
) = nsyms
;
429 syms
= XOBNEWVEC (obstack
, struct symbol
*, nsyms
);
430 DICT_LINEAR_SYMS (retval
) = syms
;
432 /* Now fill in the symbols. Start filling in from the back, so as
433 to preserve the original order of the symbols. */
434 for (list_counter
= symbol_list
, j
= nsyms
- 1;
435 list_counter
!= NULL
;
436 list_counter
= list_counter
->next
)
438 for (i
= list_counter
->nsyms
- 1;
442 syms
[j
] = list_counter
->symbol
[i
];
449 /* See dictionary.h. */
452 dict_create_linear_expandable (enum language language
)
454 struct dictionary
*retval
= XNEW (struct dictionary
);
456 DICT_VECTOR (retval
) = &dict_linear_expandable_vector
;
457 DICT_LANGUAGE (retval
) = language_def (language
);
458 DICT_LINEAR_NSYMS (retval
) = 0;
459 DICT_LINEAR_EXPANDABLE_CAPACITY (retval
) = DICT_EXPANDABLE_INITIAL_CAPACITY
;
460 DICT_LINEAR_SYMS (retval
)
461 = XNEWVEC (struct symbol
*, DICT_LINEAR_EXPANDABLE_CAPACITY (retval
));
466 /* The functions providing the dictionary interface. */
468 /* Free the memory used by a dictionary that's not on an obstack. (If
472 dict_free (struct dictionary
*dict
)
474 (DICT_VECTOR (dict
))->free (dict
);
477 /* Add SYM to DICT. DICT had better be expandable. */
480 dict_add_symbol (struct dictionary
*dict
, struct symbol
*sym
)
482 (DICT_VECTOR (dict
))->add_symbol (dict
, sym
);
485 /* Utility to add a list of symbols to a dictionary.
486 DICT must be an expandable dictionary. */
489 dict_add_pending (struct dictionary
*dict
, const struct pending
*symbol_list
)
491 const struct pending
*list
;
494 for (list
= symbol_list
; list
!= NULL
; list
= list
->next
)
496 for (i
= 0; i
< list
->nsyms
; ++i
)
497 dict_add_symbol (dict
, list
->symbol
[i
]);
501 /* Initialize ITERATOR to point at the first symbol in DICT, and
502 return that first symbol, or NULL if DICT is empty. */
505 dict_iterator_first (const struct dictionary
*dict
,
506 struct dict_iterator
*iterator
)
508 return (DICT_VECTOR (dict
))->iterator_first (dict
, iterator
);
511 /* Advance ITERATOR, and return the next symbol, or NULL if there are
515 dict_iterator_next (struct dict_iterator
*iterator
)
517 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator
)))
518 ->iterator_next (iterator
);
522 dict_iter_match_first (const struct dictionary
*dict
,
523 const lookup_name_info
&name
,
524 struct dict_iterator
*iterator
)
526 return (DICT_VECTOR (dict
))->iter_match_first (dict
, name
, iterator
);
530 dict_iter_match_next (const lookup_name_info
&name
,
531 struct dict_iterator
*iterator
)
533 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator
)))
534 ->iter_match_next (name
, iterator
);
538 dict_size (const struct dictionary
*dict
)
540 return (DICT_VECTOR (dict
))->size (dict
);
543 /* Now come functions (well, one function, currently) that are
544 implemented generically by means of the vtable. Typically, they're
547 /* Test to see if DICT is empty. */
550 dict_empty (struct dictionary
*dict
)
552 struct dict_iterator iter
;
554 return (dict_iterator_first (dict
, &iter
) == NULL
);
558 /* The functions implementing the dictionary interface. */
560 /* Generic functions, where appropriate. */
563 free_obstack (struct dictionary
*dict
)
569 add_symbol_nonexpandable (struct dictionary
*dict
, struct symbol
*sym
)
571 internal_error (__FILE__
, __LINE__
,
572 _("dict_add_symbol: non-expandable dictionary"));
575 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
577 static struct symbol
*
578 iterator_first_hashed (const struct dictionary
*dict
,
579 struct dict_iterator
*iterator
)
581 DICT_ITERATOR_DICT (iterator
) = dict
;
582 DICT_ITERATOR_INDEX (iterator
) = -1;
583 return iterator_hashed_advance (iterator
);
586 static struct symbol
*
587 iterator_next_hashed (struct dict_iterator
*iterator
)
591 next
= DICT_ITERATOR_CURRENT (iterator
)->hash_next
;
594 return iterator_hashed_advance (iterator
);
597 DICT_ITERATOR_CURRENT (iterator
) = next
;
602 static struct symbol
*
603 iterator_hashed_advance (struct dict_iterator
*iterator
)
605 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
606 int nbuckets
= DICT_HASHED_NBUCKETS (dict
);
609 for (i
= DICT_ITERATOR_INDEX (iterator
) + 1; i
< nbuckets
; ++i
)
611 struct symbol
*sym
= DICT_HASHED_BUCKET (dict
, i
);
615 DICT_ITERATOR_INDEX (iterator
) = i
;
616 DICT_ITERATOR_CURRENT (iterator
) = sym
;
624 static struct symbol
*
625 iter_match_first_hashed (const struct dictionary
*dict
,
626 const lookup_name_info
&name
,
627 struct dict_iterator
*iterator
)
629 const language_defn
*lang
= DICT_LANGUAGE (dict
);
630 unsigned int hash_index
= (name
.search_name_hash (lang
->la_language
)
631 % DICT_HASHED_NBUCKETS (dict
));
632 symbol_name_matcher_ftype
*matches_name
633 = language_get_symbol_name_matcher (lang
, name
);
636 DICT_ITERATOR_DICT (iterator
) = dict
;
638 /* Loop through the symbols in the given bucket, breaking when SYM
639 first matches. If SYM never matches, it will be set to NULL;
640 either way, we have the right return value. */
642 for (sym
= DICT_HASHED_BUCKET (dict
, hash_index
);
644 sym
= sym
->hash_next
)
646 /* Warning: the order of arguments to compare matters! */
647 if (matches_name (SYMBOL_SEARCH_NAME (sym
), name
, NULL
))
651 DICT_ITERATOR_CURRENT (iterator
) = sym
;
655 static struct symbol
*
656 iter_match_next_hashed (const lookup_name_info
&name
,
657 struct dict_iterator
*iterator
)
659 const language_defn
*lang
= DICT_LANGUAGE (DICT_ITERATOR_DICT (iterator
));
660 symbol_name_matcher_ftype
*matches_name
661 = language_get_symbol_name_matcher (lang
, name
);
664 for (next
= DICT_ITERATOR_CURRENT (iterator
)->hash_next
;
666 next
= next
->hash_next
)
668 if (matches_name (SYMBOL_SEARCH_NAME (next
), name
, NULL
))
672 DICT_ITERATOR_CURRENT (iterator
) = next
;
677 /* Insert SYM into DICT. */
680 insert_symbol_hashed (struct dictionary
*dict
,
683 unsigned int hash_index
;
685 struct symbol
**buckets
= DICT_HASHED_BUCKETS (dict
);
687 /* We don't want to insert a symbol into a dictionary of a different
688 language. The two may not use the same hashing algorithm. */
689 gdb_assert (SYMBOL_LANGUAGE (sym
) == DICT_LANGUAGE (dict
)->la_language
);
691 hash
= search_name_hash (SYMBOL_LANGUAGE (sym
), SYMBOL_SEARCH_NAME (sym
));
692 hash_index
= hash
% DICT_HASHED_NBUCKETS (dict
);
693 sym
->hash_next
= buckets
[hash_index
];
694 buckets
[hash_index
] = sym
;
698 size_hashed (const struct dictionary
*dict
)
700 return DICT_HASHED_NBUCKETS (dict
);
703 /* Functions only for DICT_HASHED_EXPANDABLE. */
706 free_hashed_expandable (struct dictionary
*dict
)
708 xfree (DICT_HASHED_BUCKETS (dict
));
713 add_symbol_hashed_expandable (struct dictionary
*dict
,
716 int nsyms
= ++DICT_HASHED_EXPANDABLE_NSYMS (dict
);
718 if (DICT_HASHTABLE_SIZE (nsyms
) > DICT_HASHED_NBUCKETS (dict
))
719 expand_hashtable (dict
);
721 insert_symbol_hashed (dict
, sym
);
722 DICT_HASHED_EXPANDABLE_NSYMS (dict
) = nsyms
;
726 size_hashed_expandable (const struct dictionary
*dict
)
728 return DICT_HASHED_EXPANDABLE_NSYMS (dict
);
732 expand_hashtable (struct dictionary
*dict
)
734 int old_nbuckets
= DICT_HASHED_NBUCKETS (dict
);
735 struct symbol
**old_buckets
= DICT_HASHED_BUCKETS (dict
);
736 int new_nbuckets
= 2 * old_nbuckets
+ 1;
737 struct symbol
**new_buckets
= XCNEWVEC (struct symbol
*, new_nbuckets
);
740 DICT_HASHED_NBUCKETS (dict
) = new_nbuckets
;
741 DICT_HASHED_BUCKETS (dict
) = new_buckets
;
743 for (i
= 0; i
< old_nbuckets
; ++i
)
745 struct symbol
*sym
, *next_sym
;
747 sym
= old_buckets
[i
];
750 for (next_sym
= sym
->hash_next
;
752 next_sym
= sym
->hash_next
)
754 insert_symbol_hashed (dict
, sym
);
758 insert_symbol_hashed (dict
, sym
);
765 /* See dictionary.h. */
768 default_search_name_hash (const char *string0
)
770 /* The Ada-encoded version of a name P1.P2...Pn has either the form
771 P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
772 are lower-cased identifiers). The <suffix> (which can be empty)
773 encodes additional information about the denoted entity. This
774 routine hashes such names to msymbol_hash_iw(Pn). It actually
775 does this for a superset of both valid Pi and of <suffix>, but
776 in other cases it simply returns msymbol_hash_iw(STRING0). */
784 if (startswith (string
, "_ada_"))
787 return msymbol_hash_iw (string0
);
798 if (string0
== string
)
799 return msymbol_hash_iw (string0
);
804 return msymbol_hash_iw (string0
);
806 if (string
[1] == '_' && string
!= string0
)
810 if ((c
< 'a' || c
> 'z') && c
!= 'O')
818 /* Ignore "TKB" suffixes.
820 These are used by Ada for subprograms implementing a task body.
821 For instance for a task T inside package Pck, the name of the
822 subprogram implementing T's body is `pck__tTKB'. We need to
823 ignore the "TKB" suffix because searches for this task body
824 subprogram are going to be performed using `pck__t' (the encoded
825 version of the natural name `pck.t'). */
826 if (strcmp (string
, "TKB") == 0)
831 hash
= SYMBOL_HASH_NEXT (hash
, *string
);
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 lookup_name_info
&name
,
862 struct dict_iterator
*iterator
)
864 DICT_ITERATOR_DICT (iterator
) = dict
;
865 DICT_ITERATOR_INDEX (iterator
) = -1;
867 return iter_match_next_linear (name
, iterator
);
870 static struct symbol
*
871 iter_match_next_linear (const lookup_name_info
&name
,
872 struct dict_iterator
*iterator
)
874 const struct dictionary
*dict
= DICT_ITERATOR_DICT (iterator
);
875 const language_defn
*lang
= DICT_LANGUAGE (dict
);
876 symbol_name_matcher_ftype
*matches_name
877 = language_get_symbol_name_matcher (lang
, name
);
879 int i
, nsyms
= DICT_LINEAR_NSYMS (dict
);
880 struct symbol
*sym
, *retval
= NULL
;
882 for (i
= DICT_ITERATOR_INDEX (iterator
) + 1; i
< nsyms
; ++i
)
884 sym
= DICT_LINEAR_SYM (dict
, i
);
886 if (matches_name (SYMBOL_SEARCH_NAME (sym
), name
, NULL
))
893 DICT_ITERATOR_INDEX (iterator
) = i
;
899 size_linear (const struct dictionary
*dict
)
901 return DICT_LINEAR_NSYMS (dict
);
904 /* Functions only for DICT_LINEAR_EXPANDABLE. */
907 free_linear_expandable (struct dictionary
*dict
)
909 xfree (DICT_LINEAR_SYMS (dict
));
915 add_symbol_linear_expandable (struct dictionary
*dict
,
918 int nsyms
= ++DICT_LINEAR_NSYMS (dict
);
920 /* Do we have enough room? If not, grow it. */
921 if (nsyms
> DICT_LINEAR_EXPANDABLE_CAPACITY (dict
))
923 DICT_LINEAR_EXPANDABLE_CAPACITY (dict
) *= 2;
924 DICT_LINEAR_SYMS (dict
)
925 = XRESIZEVEC (struct symbol
*, DICT_LINEAR_SYMS (dict
),
926 DICT_LINEAR_EXPANDABLE_CAPACITY (dict
));
929 DICT_LINEAR_SYM (dict
, nsyms
- 1) = sym
;