GDB (xrefs)
/tmp/gdb-7.10/gdb/dictionary.c
Go to the documentation of this file.
1 /* Routines for name->symbol lookups in GDB.
2 
3  Copyright (C) 2003-2015 Free Software Foundation, Inc.
4 
5  Contributed by David Carlton <carlton@bactrian.org> and by Kealia,
6  Inc.
7 
8  This file is part of GDB.
9 
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.
14 
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.
19 
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/>. */
22 
23 #include "defs.h"
24 #include <ctype.h>
25 #include "gdb_obstack.h"
26 #include "symtab.h"
27 #include "buildsym.h"
28 #include "dictionary.h"
29 
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).
35 
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.)
41 
42  To add a new dictionary implementation <impl>, what you should do
43  is:
44 
45  * Add a new element DICT_<IMPL> to dict_type.
46 
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.
51 
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
59  question.
60 
61  * Define a static const struct dict_vector dict_<impl>_vector.
62 
63  * Define a function dict_create_<impl> to create these
64  gizmos. Add its declaration to dictionary.h.
65 
66  To add a new operation <op> on all existing implementations, what
67  you should do is:
68 
69  * Add a new member <op> to struct dict_vector.
70 
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.)
74 
75  * For every implementation <impl> that should have its own specific
76  behavior for <op>, define a static function <op>_<impl>
77  implementing it.
78 
79  * Modify all existing dict_vector_<impl>'s to include the appropriate
80  member.
81 
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. */
85 
86 /* An enum representing the various implementations of dictionaries.
87  Used only for debugging. */
88 
90  {
91  /* Symbols are stored in a fixed-size hash table. */
93  /* Symbols are stored in an expandable hash table. */
95  /* Symbols are stored in a fixed-size array. */
97  /* Symbols are stored in an expandable array. */
99  };
100 
101 /* The virtual function table. */
102 
104 {
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 char *name,
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);
126 };
127 
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
131  way. */
132 
134 {
135  int nbuckets;
136  struct symbol **buckets;
137 };
138 
140 {
141  /* How many buckets we currently have. */
142  int nbuckets;
143  struct symbol **buckets;
144  /* How many syms we currently have; we need this so we will know
145  when to add more buckets. */
146  int nsyms;
147 };
148 
150 {
151  int nsyms;
152  struct symbol **syms;
153 };
154 
156 {
157  /* How many symbols we currently have. */
158  int nsyms;
159  struct symbol **syms;
160  /* How many symbols we can store before needing to reallocate. */
161  int capacity;
162 };
163 
164 /* And now, the star of our show. */
165 
167 {
168  const struct dict_vector *vector;
169  union
170  {
175  }
176  data;
177 };
178 
179 /* Accessor macros. */
180 
181 #define DICT_VECTOR(d) (d)->vector
182 
183 /* These can be used for DICT_HASHED_EXPANDABLE, too. */
184 
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]
188 
189 #define DICT_HASHED_EXPANDABLE_NSYMS(d) (d)->data.hashed_expandable.nsyms
190 
191 /* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
192 
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]
196 
197 #define DICT_LINEAR_EXPANDABLE_CAPACITY(d) \
198  (d)->data.linear_expandable.capacity
199 
200 /* The initial size of a DICT_*_EXPANDABLE dictionary. */
201 
202 #define DICT_EXPANDABLE_INITIAL_CAPACITY 10
203 
204 /* This calculates the number of buckets we'll use in a hashtable,
205  given the number of symbols that it will contain. */
206 
207 #define DICT_HASHTABLE_SIZE(n) ((n)/5 + 1)
208 
209 /* Accessor macros for dict_iterators; they're here rather than
210  dictionary.h because code elsewhere should treat dict_iterators as
211  opaque. */
212 
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
221 
222 /* Declarations of functions for vectors. */
223 
224 /* Functions that might work across a range of dictionary types. */
225 
226 static void add_symbol_nonexpandable (struct dictionary *dict,
227  struct symbol *sym);
228 
229 static void free_obstack (struct dictionary *dict);
230 
231 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
232  dictionaries. */
233 
234 static struct symbol *iterator_first_hashed (const struct dictionary *dict,
235  struct dict_iterator *iterator);
236 
237 static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
238 
239 static struct symbol *iter_match_first_hashed (const struct dictionary *dict,
240  const char *name,
241  symbol_compare_ftype *compare,
242  struct dict_iterator *iterator);
243 
244 static struct symbol *iter_match_next_hashed (const char *name,
245  symbol_compare_ftype *compare,
246  struct dict_iterator *iterator);
247 
248 static unsigned int dict_hash (const char *string);
249 
250 /* Functions only for DICT_HASHED. */
251 
252 static int size_hashed (const struct dictionary *dict);
253 
254 /* Functions only for DICT_HASHED_EXPANDABLE. */
255 
256 static void free_hashed_expandable (struct dictionary *dict);
257 
258 static void add_symbol_hashed_expandable (struct dictionary *dict,
259  struct symbol *sym);
260 
261 static int size_hashed_expandable (const struct dictionary *dict);
262 
263 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
264  dictionaries. */
265 
266 static struct symbol *iterator_first_linear (const struct dictionary *dict,
267  struct dict_iterator *iterator);
268 
269 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
270 
271 static struct symbol *iter_match_first_linear (const struct dictionary *dict,
272  const char *name,
273  symbol_compare_ftype *compare,
274  struct dict_iterator *iterator);
275 
276 static struct symbol *iter_match_next_linear (const char *name,
277  symbol_compare_ftype *compare,
278  struct dict_iterator *iterator);
279 
280 static int size_linear (const struct dictionary *dict);
281 
282 /* Functions only for DICT_LINEAR_EXPANDABLE. */
283 
284 static void free_linear_expandable (struct dictionary *dict);
285 
286 static void add_symbol_linear_expandable (struct dictionary *dict,
287  struct symbol *sym);
288 
289 /* Various vectors that we'll actually use. */
290 
291 static const struct dict_vector dict_hashed_vector =
292  {
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 */
301  };
302 
303 static const struct dict_vector dict_hashed_expandable_vector =
304  {
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 */
313  };
314 
315 static const struct dict_vector dict_linear_vector =
316  {
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 */
325  };
326 
327 static const struct dict_vector dict_linear_expandable_vector =
328  {
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 */
337  };
338 
339 /* Declarations of helper functions (i.e. ones that don't go into
340  vectors). */
341 
342 static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
343 
344 static void insert_symbol_hashed (struct dictionary *dict,
345  struct symbol *sym);
346 
347 static void expand_hashtable (struct dictionary *dict);
348 
349 /* The creation functions. */
350 
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. */
354 
355 struct dictionary *
356 dict_create_hashed (struct obstack *obstack,
357  const struct pending *symbol_list)
358 {
359  struct dictionary *retval;
360  int nsyms = 0, nbuckets, i;
361  struct symbol **buckets;
362  const struct pending *list_counter;
363 
364  retval = obstack_alloc (obstack, sizeof (struct dictionary));
365  DICT_VECTOR (retval) = &dict_hashed_vector;
366 
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)
371  {
372  nsyms += list_counter->nsyms;
373  }
374  nbuckets = DICT_HASHTABLE_SIZE (nsyms);
375  DICT_HASHED_NBUCKETS (retval) = nbuckets;
376  buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *));
377  memset (buckets, 0, nbuckets * sizeof (struct symbol *));
378  DICT_HASHED_BUCKETS (retval) = buckets;
379 
380  /* Now fill the buckets. */
381  for (list_counter = symbol_list;
382  list_counter != NULL;
383  list_counter = list_counter->next)
384  {
385  for (i = list_counter->nsyms - 1; i >= 0; --i)
386  {
387  insert_symbol_hashed (retval, list_counter->symbol[i]);
388  }
389  }
390 
391  return retval;
392 }
393 
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
397  it. */
398 
399 extern struct dictionary *
401 {
402  struct dictionary *retval;
403 
404  retval = xmalloc (sizeof (struct dictionary));
408  sizeof (struct symbol *));
409  DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
410 
411  return retval;
412 }
413 
414 /* Create a dictionary implemented via a fixed-size array. All memory
415  it uses is allocated on OBSTACK; the environment is initialized
416  from the SYMBOL_LIST. The symbols are ordered in the same order
417  that they're found in SYMBOL_LIST. */
418 
419 struct dictionary *
420 dict_create_linear (struct obstack *obstack,
421  const struct pending *symbol_list)
422 {
423  struct dictionary *retval;
424  int nsyms = 0, i, j;
425  struct symbol **syms;
426  const struct pending *list_counter;
427 
428  retval = obstack_alloc (obstack, sizeof (struct dictionary));
429  DICT_VECTOR (retval) = &dict_linear_vector;
430 
431  /* Calculate the number of symbols, and allocate space for them. */
432  for (list_counter = symbol_list;
433  list_counter != NULL;
434  list_counter = list_counter->next)
435  {
436  nsyms += list_counter->nsyms;
437  }
438  DICT_LINEAR_NSYMS (retval) = nsyms;
439  syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *));
440  DICT_LINEAR_SYMS (retval) = syms;
441 
442  /* Now fill in the symbols. Start filling in from the back, so as
443  to preserve the original order of the symbols. */
444  for (list_counter = symbol_list, j = nsyms - 1;
445  list_counter != NULL;
446  list_counter = list_counter->next)
447  {
448  for (i = list_counter->nsyms - 1;
449  i >= 0;
450  --i, --j)
451  {
452  syms[j] = list_counter->symbol[i];
453  }
454  }
455 
456  return retval;
457 }
458 
459 /* Create a dictionary implemented via an array that grows as
460  necessary. The dictionary is initially empty; to add symbols to
461  it, call dict_add_symbol(). Call dict_free() when you're done with
462  it. */
463 
464 struct dictionary *
466 {
467  struct dictionary *retval;
468 
469  retval = xmalloc (sizeof (struct dictionary));
471  DICT_LINEAR_NSYMS (retval) = 0;
474  DICT_LINEAR_SYMS (retval)
476  * sizeof (struct symbol *));
477 
478  return retval;
479 }
480 
481 /* The functions providing the dictionary interface. */
482 
483 /* Free the memory used by a dictionary that's not on an obstack. (If
484  any.) */
485 
486 void
487 dict_free (struct dictionary *dict)
488 {
489  (DICT_VECTOR (dict))->free (dict);
490 }
491 
492 /* Add SYM to DICT. DICT had better be expandable. */
493 
494 void
495 dict_add_symbol (struct dictionary *dict, struct symbol *sym)
496 {
497  (DICT_VECTOR (dict))->add_symbol (dict, sym);
498 }
499 
500 /* Utility to add a list of symbols to a dictionary.
501  DICT must be an expandable dictionary. */
502 
503 void
504 dict_add_pending (struct dictionary *dict, const struct pending *symbol_list)
505 {
506  const struct pending *list;
507  int i;
508 
509  for (list = symbol_list; list != NULL; list = list->next)
510  {
511  for (i = 0; i < list->nsyms; ++i)
512  dict_add_symbol (dict, list->symbol[i]);
513  }
514 }
515 
516 /* Initialize ITERATOR to point at the first symbol in DICT, and
517  return that first symbol, or NULL if DICT is empty. */
518 
519 struct symbol *
520 dict_iterator_first (const struct dictionary *dict,
521  struct dict_iterator *iterator)
522 {
523  return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
524 }
525 
526 /* Advance ITERATOR, and return the next symbol, or NULL if there are
527  no more symbols. */
528 
529 struct symbol *
531 {
532  return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
533  ->iterator_next (iterator);
534 }
535 
536 struct symbol *
537 dict_iter_name_first (const struct dictionary *dict,
538  const char *name,
539  struct dict_iterator *iterator)
540 {
541  return dict_iter_match_first (dict, name, strcmp_iw, iterator);
542 }
543 
544 struct symbol *
545 dict_iter_name_next (const char *name, struct dict_iterator *iterator)
546 {
547  return dict_iter_match_next (name, strcmp_iw, iterator);
548 }
549 
550 struct symbol *
551 dict_iter_match_first (const struct dictionary *dict,
552  const char *name, symbol_compare_ftype *compare,
553  struct dict_iterator *iterator)
554 {
555  return (DICT_VECTOR (dict))->iter_match_first (dict, name,
556  compare, iterator);
557 }
558 
559 struct symbol *
561  struct dict_iterator *iterator)
562 {
563  return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
564  ->iter_match_next (name, compare, iterator);
565 }
566 
567 int
568 dict_size (const struct dictionary *dict)
569 {
570  return (DICT_VECTOR (dict))->size (dict);
571 }
572 
573 /* Now come functions (well, one function, currently) that are
574  implemented generically by means of the vtable. Typically, they're
575  rarely used. */
576 
577 /* Test to see if DICT is empty. */
578 
579 int
580 dict_empty (struct dictionary *dict)
581 {
582  struct dict_iterator iter;
583 
584  return (dict_iterator_first (dict, &iter) == NULL);
585 }
586 
587 
588 /* The functions implementing the dictionary interface. */
589 
590 /* Generic functions, where appropriate. */
591 
592 static void
594 {
595  /* Do nothing! */
596 }
597 
598 static void
600 {
601  internal_error (__FILE__, __LINE__,
602  _("dict_add_symbol: non-expandable dictionary"));
603 }
604 
605 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
606 
607 static struct symbol *
608 iterator_first_hashed (const struct dictionary *dict,
609  struct dict_iterator *iterator)
610 {
611  DICT_ITERATOR_DICT (iterator) = dict;
612  DICT_ITERATOR_INDEX (iterator) = -1;
613  return iterator_hashed_advance (iterator);
614 }
615 
616 static struct symbol *
618 {
619  struct symbol *next;
620 
621  next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
622 
623  if (next == NULL)
624  return iterator_hashed_advance (iterator);
625  else
626  {
627  DICT_ITERATOR_CURRENT (iterator) = next;
628  return next;
629  }
630 }
631 
632 static struct symbol *
634 {
635  const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
636  int nbuckets = DICT_HASHED_NBUCKETS (dict);
637  int i;
638 
639  for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
640  {
641  struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
642 
643  if (sym != NULL)
644  {
645  DICT_ITERATOR_INDEX (iterator) = i;
646  DICT_ITERATOR_CURRENT (iterator) = sym;
647  return sym;
648  }
649  }
650 
651  return NULL;
652 }
653 
654 static struct symbol *
655 iter_match_first_hashed (const struct dictionary *dict, const char *name,
656  symbol_compare_ftype *compare,
657  struct dict_iterator *iterator)
658 {
659  unsigned int hash_index = dict_hash (name) % DICT_HASHED_NBUCKETS (dict);
660  struct symbol *sym;
661 
662  DICT_ITERATOR_DICT (iterator) = dict;
663 
664  /* Loop through the symbols in the given bucket, breaking when SYM
665  first matches. If SYM never matches, it will be set to NULL;
666  either way, we have the right return value. */
667 
668  for (sym = DICT_HASHED_BUCKET (dict, hash_index);
669  sym != NULL;
670  sym = sym->hash_next)
671  {
672  /* Warning: the order of arguments to compare matters! */
673  if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
674  {
675  break;
676  }
677 
678  }
679 
680  DICT_ITERATOR_CURRENT (iterator) = sym;
681  return sym;
682 }
683 
684 static struct symbol *
686  struct dict_iterator *iterator)
687 {
688  struct symbol *next;
689 
690  for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
691  next != NULL;
692  next = next->hash_next)
693  {
694  if (compare (SYMBOL_SEARCH_NAME (next), name) == 0)
695  break;
696  }
697 
698  DICT_ITERATOR_CURRENT (iterator) = next;
699 
700  return next;
701 }
702 
703 /* Insert SYM into DICT. */
704 
705 static void
707  struct symbol *sym)
708 {
709  unsigned int hash_index;
710  struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
711 
712  hash_index =
714  sym->hash_next = buckets[hash_index];
715  buckets[hash_index] = sym;
716 }
717 
718 static int
719 size_hashed (const struct dictionary *dict)
720 {
721  return DICT_HASHED_NBUCKETS (dict);
722 }
723 
724 /* Functions only for DICT_HASHED_EXPANDABLE. */
725 
726 static void
728 {
729  xfree (DICT_HASHED_BUCKETS (dict));
730  xfree (dict);
731 }
732 
733 static void
735  struct symbol *sym)
736 {
737  int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
738 
739  if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
740  expand_hashtable (dict);
741 
742  insert_symbol_hashed (dict, sym);
743  DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
744 }
745 
746 static int
747 size_hashed_expandable (const struct dictionary *dict)
748 {
749  return DICT_HASHED_EXPANDABLE_NSYMS (dict);
750 }
751 
752 static void
754 {
755  int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
756  struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
757  int new_nbuckets = 2*old_nbuckets + 1;
758  struct symbol **new_buckets = xcalloc (new_nbuckets,
759  sizeof (struct symbol *));
760  int i;
761 
762  DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
763  DICT_HASHED_BUCKETS (dict) = new_buckets;
764 
765  for (i = 0; i < old_nbuckets; ++i)
766  {
767  struct symbol *sym, *next_sym;
768 
769  sym = old_buckets[i];
770  if (sym != NULL)
771  {
772  for (next_sym = sym->hash_next;
773  next_sym != NULL;
774  next_sym = sym->hash_next)
775  {
776  insert_symbol_hashed (dict, sym);
777  sym = next_sym;
778  }
779 
780  insert_symbol_hashed (dict, sym);
781  }
782  }
783 
784  xfree (old_buckets);
785 }
786 
787 /* Produce an unsigned hash value from STRING0 that is consistent
788  with strcmp_iw, strcmp, and, at least on Ada symbols, wild_match.
789  That is, two identifiers equivalent according to any of those three
790  comparison operators hash to the same value. */
791 
792 static unsigned int
793 dict_hash (const char *string0)
794 {
795  /* The Ada-encoded version of a name P1.P2...Pn has either the form
796  P1__P2__...Pn<suffix> or _ada_P1__P2__...Pn<suffix> (where the Pi
797  are lower-cased identifiers). The <suffix> (which can be empty)
798  encodes additional information about the denoted entity. This
799  routine hashes such names to msymbol_hash_iw(Pn). It actually
800  does this for a superset of both valid Pi and of <suffix>, but
801  in other cases it simply returns msymbol_hash_iw(STRING0). */
802 
803  const char *string;
804  unsigned int hash;
805 
806  string = string0;
807  if (*string == '_')
808  {
809  if (startswith (string, "_ada_"))
810  string += 5;
811  else
812  return msymbol_hash_iw (string0);
813  }
814 
815  hash = 0;
816  while (*string)
817  {
818  /* Ignore "TKB" suffixes.
819 
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)
827  return hash;
828 
829  switch (*string)
830  {
831  case '$':
832  case '.':
833  case 'X':
834  if (string0 == string)
835  return msymbol_hash_iw (string0);
836  else
837  return hash;
838  case ' ':
839  case '(':
840  return msymbol_hash_iw (string0);
841  case '_':
842  if (string[1] == '_' && string != string0)
843  {
844  int c = string[2];
845 
846  if ((c < 'a' || c > 'z') && c != 'O')
847  return hash;
848  hash = 0;
849  string += 2;
850  break;
851  }
852  /* FALL THROUGH */
853  default:
854  hash = SYMBOL_HASH_NEXT (hash, *string);
855  string += 1;
856  break;
857  }
858  }
859  return hash;
860 }
861 
862 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
863 
864 static struct symbol *
865 iterator_first_linear (const struct dictionary *dict,
866  struct dict_iterator *iterator)
867 {
868  DICT_ITERATOR_DICT (iterator) = dict;
869  DICT_ITERATOR_INDEX (iterator) = 0;
870  return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
871 }
872 
873 static struct symbol *
875 {
876  const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
877 
878  if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
879  return NULL;
880  else
881  return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
882 }
883 
884 static struct symbol *
886  const char *name, symbol_compare_ftype *compare,
887  struct dict_iterator *iterator)
888 {
889  DICT_ITERATOR_DICT (iterator) = dict;
890  DICT_ITERATOR_INDEX (iterator) = -1;
891 
892  return iter_match_next_linear (name, compare, iterator);
893 }
894 
895 static struct symbol *
897  struct dict_iterator *iterator)
898 {
899  const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
900  int i, nsyms = DICT_LINEAR_NSYMS (dict);
901  struct symbol *sym, *retval = NULL;
902 
903  for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
904  {
905  sym = DICT_LINEAR_SYM (dict, i);
906  if (compare (SYMBOL_SEARCH_NAME (sym), name) == 0)
907  {
908  retval = sym;
909  break;
910  }
911  }
912 
913  DICT_ITERATOR_INDEX (iterator) = i;
914 
915  return retval;
916 }
917 
918 static int
919 size_linear (const struct dictionary *dict)
920 {
921  return DICT_LINEAR_NSYMS (dict);
922 }
923 
924 /* Functions only for DICT_LINEAR_EXPANDABLE. */
925 
926 static void
928 {
929  xfree (DICT_LINEAR_SYMS (dict));
930  xfree (dict);
931 }
932 
933 
934 static void
936  struct symbol *sym)
937 {
938  int nsyms = ++DICT_LINEAR_NSYMS (dict);
939 
940  /* Do we have enough room? If not, grow it. */
941  if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
942  {
944  DICT_LINEAR_SYMS (dict)
945  = xrealloc (DICT_LINEAR_SYMS (dict),
947  * sizeof (struct symbol *));
948  }
949 
950  DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
951 }
const char * string
Definition: signals.c:50
static struct symbol * iterator_first_linear(const struct dictionary *dict, struct dict_iterator *iterator)
Definition: dictionary.c:865
#define DICT_HASHED_EXPANDABLE_NSYMS(d)
Definition: dictionary.c:189
static const struct dict_vector dict_linear_expandable_vector
Definition: dictionary.c:327
struct dictionary * dict_create_hashed(struct obstack *obstack, const struct pending *symbol_list)
Definition: dictionary.c:356
static struct @39 symbol_list[]
#define DICT_LINEAR_SYM(d, i)
Definition: dictionary.c:195
void dict_free(struct dictionary *dict)
Definition: dictionary.c:487
void xfree(void *)
Definition: common-utils.c:97
struct dictionary_hashed_expandable hashed_expandable
Definition: dictionary.c:172
struct dictionary * dict_create_linear_expandable(void)
Definition: dictionary.c:465
int strcmp_iw(const char *string1, const char *string2)
Definition: utils.c:2511
struct symbol * hash_next
Definition: symtab.h:782
const struct dict_vector * vector
Definition: dictionary.c:168
static void expand_hashtable(struct dictionary *dict)
Definition: dictionary.c:753
static struct symbol * iterator_hashed_advance(struct dict_iterator *iter)
Definition: dictionary.c:633
void internal_error(const char *file, int line, const char *fmt,...)
Definition: errors.c:50
struct symbol * dict_iter_match_first(const struct dictionary *dict, const char *name, symbol_compare_ftype *compare, struct dict_iterator *iterator)
Definition: dictionary.c:551
int(* size)(const struct dictionary *dict)
Definition: dictionary.c:125
#define DICT_HASHED_BUCKET(d, i)
Definition: dictionary.c:187
#define DICT_LINEAR_SYMS(d)
Definition: dictionary.c:194
void(* add_symbol)(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:111
struct symbol * symbol[PENDINGSIZE]
Definition: buildsym.h:102
#define DICT_ITERATOR_CURRENT(iter)
Definition: dictionary.c:220
static void add_symbol_linear_expandable(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:935
#define _(String)
Definition: gdb_locale.h:40
#define DICT_ITERATOR_DICT(iter)
Definition: dictionary.c:214
#define DICT_HASHED_NBUCKETS(d)
Definition: dictionary.c:185
static const struct dict_vector dict_linear_vector
Definition: dictionary.c:315
static void free_hashed_expandable(struct dictionary *dict)
Definition: dictionary.c:727
dict_type
Definition: dictionary.c:89
const char *const name
Definition: aarch64-tdep.c:68
struct symbol ** syms
Definition: dictionary.c:152
struct dictionary_hashed hashed
Definition: dictionary.c:171
#define DICT_LINEAR_NSYMS(d)
Definition: dictionary.c:193
int nsyms
Definition: buildsym.h:101
struct pending * next
Definition: buildsym.h:100
void dict_add_pending(struct dictionary *dict, const struct pending *symbol_list)
Definition: dictionary.c:504
#define DICT_EXPANDABLE_INITIAL_CAPACITY
Definition: dictionary.c:202
static struct symbol * iterator_next_hashed(struct dict_iterator *iterator)
Definition: dictionary.c:617
static const struct dict_vector dict_hashed_expandable_vector
Definition: dictionary.c:303
#define SYMBOL_HASH_NEXT(hash, c)
Definition: minsyms.h:154
#define DICT_LINEAR_EXPANDABLE_CAPACITY(d)
Definition: dictionary.c:197
struct symbol ** buckets
Definition: dictionary.c:143
struct symbol ** buckets
Definition: dictionary.c:136
struct dictionary * dict_create_linear(struct obstack *obstack, const struct pending *symbol_list)
Definition: dictionary.c:420
static int size_linear(const struct dictionary *dict)
Definition: dictionary.c:919
static int startswith(const char *string, const char *pattern)
Definition: common-utils.h:75
static struct symbol * iter_match_first_linear(const struct dictionary *dict, const char *name, symbol_compare_ftype *compare, struct dict_iterator *iterator)
Definition: dictionary.c:885
static struct symbol * iterator_first_hashed(const struct dictionary *dict, struct dict_iterator *iterator)
Definition: dictionary.c:608
static void add_symbol(struct symbol *, struct symtab *, struct block *)
Definition: mdebugread.c:4598
int dict_empty(struct dictionary *dict)
Definition: dictionary.c:580
union dictionary::@50 data
void * xmalloc(YYSIZE_T)
struct symbol * dict_iterator_next(struct dict_iterator *iterator)
Definition: dictionary.c:530
enum dict_type type
Definition: dictionary.c:107
unsigned long hash(const void *addr, int length)
Definition: bcache.c:98
static void add_symbol_hashed_expandable(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:734
static void free_linear_expandable(struct dictionary *dict)
Definition: dictionary.c:927
PTR xrealloc(PTR ptr, size_t size)
Definition: common-utils.c:51
const char const char int
Definition: command.h:229
int( symbol_compare_ftype)(const char *string1, const char *string2)
Definition: symfile.h:41
struct symbol * dict_iter_match_next(const char *name, symbol_compare_ftype *compare, struct dict_iterator *iterator)
Definition: dictionary.c:560
#define DICT_VECTOR(d)
Definition: dictionary.c:181
struct dictionary_linear linear
Definition: dictionary.c:173
void(* free)(struct dictionary *dict)
Definition: dictionary.c:109
static struct symbol * iter_match_next_hashed(const char *name, symbol_compare_ftype *compare, struct dict_iterator *iterator)
Definition: dictionary.c:685
void dict_add_symbol(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:495
struct dictionary * dict_create_hashed_expandable(void)
Definition: dictionary.c:400
static int size_hashed_expandable(const struct dictionary *dict)
Definition: dictionary.c:747
static void insert_symbol_hashed(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:706
static const struct dict_vector dict_hashed_vector
Definition: dictionary.c:291
#define SYMBOL_SEARCH_NAME(symbol)
Definition: symtab.h:269
struct symbol * dict_iter_name_first(const struct dictionary *dict, const char *name, struct dict_iterator *iterator)
Definition: dictionary.c:537
static unsigned int dict_hash(const char *string)
Definition: dictionary.c:793
Definition: symtab.h:703
int dict_size(const struct dictionary *dict)
Definition: dictionary.c:568
#define DICT_HASHTABLE_SIZE(n)
Definition: dictionary.c:207
struct symbol * dict_iter_name_next(const char *name, struct dict_iterator *iterator)
Definition: dictionary.c:545
const struct dictionary * dict
Definition: dictionary.h:105
PTR xcalloc(size_t number, size_t size)
Definition: common-utils.c:71
static struct symbol * iter_match_next_linear(const char *name, symbol_compare_ftype *compare, struct dict_iterator *iterator)
Definition: dictionary.c:896
static void add_symbol_nonexpandable(struct dictionary *dict, struct symbol *sym)
Definition: dictionary.c:599
static int size_hashed(const struct dictionary *dict)
Definition: dictionary.c:719
static struct symbol * iter_match_first_hashed(const struct dictionary *dict, const char *name, symbol_compare_ftype *compare, struct dict_iterator *iterator)
Definition: dictionary.c:655
struct dictionary_linear_expandable linear_expandable
Definition: dictionary.c:174
static void free_obstack(struct dictionary *dict)
Definition: dictionary.c:593
struct symbol * dict_iterator_first(const struct dictionary *dict, struct dict_iterator *iterator)
Definition: dictionary.c:520
unsigned int msymbol_hash_iw(const char *string)
Definition: minsyms.c:83
static struct symbol * iterator_next_linear(struct dict_iterator *iterator)
Definition: dictionary.c:874
#define DICT_HASHED_BUCKETS(d)
Definition: dictionary.c:186
#define DICT_ITERATOR_INDEX(iter)
Definition: dictionary.c:217