Bug Summary

File:src/gnu/usr.bin/binutils/gdb/dictionary.c
Warning:line 583, column 28
Value stored to 'dict' during its initialization is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name dictionary.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/binutils/obj/gdb -resource-dir /usr/local/lib/clang/13.0.0 -D PIE_DEFAULT=1 -I . -I /usr/src/gnu/usr.bin/binutils/gdb -I /usr/src/gnu/usr.bin/binutils/gdb/config -D LOCALEDIR="/usr/share/locale" -D HAVE_CONFIG_H -I /usr/src/gnu/usr.bin/binutils/gdb/../include/opcode -I ../bfd -I /usr/src/gnu/usr.bin/binutils/gdb/../bfd -I /usr/src/gnu/usr.bin/binutils/gdb/../include -I ../intl -I /usr/src/gnu/usr.bin/binutils/gdb/../intl -D MI_OUT=1 -D TUI=1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/gnu/usr.bin/binutils/obj/gdb -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fgnuc-version=4.2.1 -fcommon -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/gnu/usr.bin/binutils/gdb/dictionary.c
1/* Routines for name->symbol lookups in GDB.
2
3 Copyright 2003 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 2 of the License, or (at
13 your option) any later version.
14
15 This program is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 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, write to the Free Software
22 Foundation, Inc., 59 Temple Place - Suite 330,
23 Boston, MA 02111-1307, USA. */
24
25#include "defs.h"
26#include "gdb_obstack.h"
27#include "symtab.h"
28#include "buildsym.h"
29#include "gdb_assert.h"
30#include "dictionary.h"
31
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).
37
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.)
43
44 To add a new dictionary implementation <impl>, what you should do
45 is:
46
47 * Add a new element DICT_<IMPL> to dict_type.
48
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.
53
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
61 question.
62
63 * Define a static const struct dict_vector dict_<impl>_vector.
64
65 * Define a function dict_create_<impl> to create these
66 gizmos. Add its declaration to dictionary.h.
67
68 To add a new operation <op> on all existing implementations, what
69 you should do is:
70
71 * Add a new member <op> to struct dict_vector.
72
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.)
76
77 * For every implementation <impl> that should have its own specific
78 behavior for <op>, define a static function <op>_<impl>
79 implementing it.
80
81 * Modify all existing dict_vector_<impl>'s to include the appropriate
82 member.
83
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.
87
88*/
89
90/* An enum representing the various implementations of dictionaries.
91 Used only for debugging. */
92
93enum dict_type
94 {
95 /* Symbols are stored in a fixed-size hash table. */
96 DICT_HASHED,
97 /* Symbols are stored in an expandable hash table. */
98 DICT_HASHED_EXPANDABLE,
99 /* Symbols are stored in a fixed-size array. */
100 DICT_LINEAR,
101 /* Symbols are stored in an expandable array. */
102 DICT_LINEAR_EXPANDABLE
103 };
104
105/* The virtual function table. */
106
107struct dict_vector
108{
109 /* The type of the dictionary. This is only here to make debugging
110 a bit easier; it's not actually used. */
111 enum dict_type type;
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_name_first) (const struct dictionary *dict,
122 const char *name,
123 struct dict_iterator *iterator);
124 struct symbol *(*iter_name_next) (const char *name,
125 struct dict_iterator *iterator);
126 /* A size function, for maint print symtabs. */
127 int (*size) (const struct dictionary *dict);
128};
129
130/* Now comes the structs used to store the data for different
131 implementations. If two implementations have data in common, put
132 the common data at the top of their structs, ordered in the same
133 way. */
134
135struct dictionary_hashed
136{
137 int nbuckets;
138 struct symbol **buckets;
139};
140
141struct dictionary_hashed_expandable
142{
143 /* How many buckets we currently have. */
144 int nbuckets;
145 struct symbol **buckets;
146 /* How many syms we currently have; we need this so we will know
147 when to add more buckets. */
148 int nsyms;
149};
150
151struct dictionary_linear
152{
153 int nsyms;
154 struct symbol **syms;
155};
156
157struct dictionary_linear_expandable
158{
159 /* How many symbols we currently have. */
160 int nsyms;
161 struct symbol **syms;
162 /* How many symbols we can store before needing to reallocate. */
163 int capacity;
164};
165
166/* And now, the star of our show. */
167
168struct dictionary
169{
170 const struct dict_vector *vector;
171 union
172 {
173 struct dictionary_hashed hashed;
174 struct dictionary_hashed_expandable hashed_expandable;
175 struct dictionary_linear linear;
176 struct dictionary_linear_expandable linear_expandable;
177 }
178 data;
179};
180
181/* Accessor macros. */
182
183#define DICT_VECTOR(d)(d)->vector (d)->vector
184
185/* These can be used for DICT_HASHED_EXPANDABLE, too. */
186
187#define DICT_HASHED_NBUCKETS(d)(d)->data.hashed.nbuckets (d)->data.hashed.nbuckets
188#define DICT_HASHED_BUCKETS(d)(d)->data.hashed.buckets (d)->data.hashed.buckets
189#define DICT_HASHED_BUCKET(d,i)(d)->data.hashed.buckets [i] DICT_HASHED_BUCKETS (d)(d)->data.hashed.buckets [i]
190
191#define DICT_HASHED_EXPANDABLE_NSYMS(d)(d)->data.hashed_expandable.nsyms (d)->data.hashed_expandable.nsyms
192
193/* These can be used for DICT_LINEAR_EXPANDABLEs, too. */
194
195#define DICT_LINEAR_NSYMS(d)(d)->data.linear.nsyms (d)->data.linear.nsyms
196#define DICT_LINEAR_SYMS(d)(d)->data.linear.syms (d)->data.linear.syms
197#define DICT_LINEAR_SYM(d,i)(d)->data.linear.syms [i] DICT_LINEAR_SYMS (d)(d)->data.linear.syms [i]
198
199#define DICT_LINEAR_EXPANDABLE_CAPACITY(d)(d)->data.linear_expandable.capacity \
200 (d)->data.linear_expandable.capacity
201
202/* The initial size of a DICT_*_EXPANDABLE dictionary. */
203
204#define DICT_EXPANDABLE_INITIAL_CAPACITY10 10
205
206/* This calculates the number of buckets we'll use in a hashtable,
207 given the number of symbols that it will contain. */
208
209#define DICT_HASHTABLE_SIZE(n)((n)/5 + 1) ((n)/5 + 1)
210
211/* Accessor macros for dict_iterators; they're here rather than
212 dictionary.h because code elsewhere should treat dict_iterators as
213 opaque. */
214
215/* The dictionary that the iterator is associated to. */
216#define DICT_ITERATOR_DICT(iter)(iter)->dict (iter)->dict
217/* For linear dictionaries, the index of the last symbol returned; for
218 hashed dictionaries, the bucket of the last symbol returned. */
219#define DICT_ITERATOR_INDEX(iter)(iter)->index (iter)->index
220/* For hashed dictionaries, this points to the last symbol returned;
221 otherwise, this is unused. */
222#define DICT_ITERATOR_CURRENT(iter)(iter)->current (iter)->current
223
224/* Declarations of functions for vectors. */
225
226/* Functions that might work across a range of dictionary types. */
227
228static void add_symbol_nonexpandable (struct dictionary *dict,
229 struct symbol *sym);
230
231static void free_obstack (struct dictionary *dict);
232
233/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE
234 dictionaries. */
235
236static struct symbol *iterator_first_hashed (const struct dictionary *dict,
237 struct dict_iterator *iterator);
238
239static struct symbol *iterator_next_hashed (struct dict_iterator *iterator);
240
241static struct symbol *iter_name_first_hashed (const struct dictionary *dict,
242 const char *name,
243 struct dict_iterator *iterator);
244
245static struct symbol *iter_name_next_hashed (const char *name,
246 struct dict_iterator *iterator);
247
248/* Functions only for DICT_HASHED. */
249
250static int size_hashed (const struct dictionary *dict);
251
252/* Functions only for DICT_HASHED_EXPANDABLE. */
253
254static void free_hashed_expandable (struct dictionary *dict);
255
256static void add_symbol_hashed_expandable (struct dictionary *dict,
257 struct symbol *sym);
258
259static int size_hashed_expandable (const struct dictionary *dict);
260
261/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
262 dictionaries. */
263
264static struct symbol *iterator_first_linear (const struct dictionary *dict,
265 struct dict_iterator *iterator);
266
267static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
268
269static struct symbol *iter_name_first_linear (const struct dictionary *dict,
270 const char *name,
271 struct dict_iterator *iterator);
272
273static struct symbol *iter_name_next_linear (const char *name,
274 struct dict_iterator *iterator);
275
276static int size_linear (const struct dictionary *dict);
277
278/* Functions only for DICT_LINEAR_EXPANDABLE. */
279
280static void free_linear_expandable (struct dictionary *dict);
281
282static void add_symbol_linear_expandable (struct dictionary *dict,
283 struct symbol *sym);
284
285/* Various vectors that we'll actually use. */
286
287static const struct dict_vector dict_hashed_vector =
288 {
289 DICT_HASHED, /* type */
290 free_obstack, /* free */
291 add_symbol_nonexpandable, /* add_symbol */
292 iterator_first_hashed, /* iteractor_first */
293 iterator_next_hashed, /* iterator_next */
294 iter_name_first_hashed, /* iter_name_first */
295 iter_name_next_hashed, /* iter_name_next */
296 size_hashed, /* size */
297 };
298
299static const struct dict_vector dict_hashed_expandable_vector =
300 {
301 DICT_HASHED_EXPANDABLE, /* type */
302 free_hashed_expandable, /* free */
303 add_symbol_hashed_expandable, /* add_symbol */
304 iterator_first_hashed, /* iteractor_first */
305 iterator_next_hashed, /* iterator_next */
306 iter_name_first_hashed, /* iter_name_first */
307 iter_name_next_hashed, /* iter_name_next */
308 size_hashed_expandable, /* size */
309 };
310
311static const struct dict_vector dict_linear_vector =
312 {
313 DICT_LINEAR, /* type */
314 free_obstack, /* free */
315 add_symbol_nonexpandable, /* add_symbol */
316 iterator_first_linear, /* iteractor_first */
317 iterator_next_linear, /* iterator_next */
318 iter_name_first_linear, /* iter_name_first */
319 iter_name_next_linear, /* iter_name_next */
320 size_linear, /* size */
321 };
322
323static const struct dict_vector dict_linear_expandable_vector =
324 {
325 DICT_LINEAR_EXPANDABLE, /* type */
326 free_linear_expandable, /* free */
327 add_symbol_linear_expandable, /* add_symbol */
328 iterator_first_linear, /* iteractor_first */
329 iterator_next_linear, /* iterator_next */
330 iter_name_first_linear, /* iter_name_first */
331 iter_name_next_linear, /* iter_name_next */
332 size_linear, /* size */
333 };
334
335/* Declarations of helper functions (i.e. ones that don't go into
336 vectors). */
337
338static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
339
340static void insert_symbol_hashed (struct dictionary *dict,
341 struct symbol *sym);
342
343static void expand_hashtable (struct dictionary *dict);
344
345/* The creation functions. */
346
347/* Create a dictionary implemented via a fixed-size hashtable. All
348 memory it uses is allocated on OBSTACK; the environment is
349 initialized from SYMBOL_LIST. */
350
351struct dictionary *
352dict_create_hashed (struct obstack *obstack,
353 const struct pending *symbol_list)
354{
355 struct dictionary *retval;
356 int nsyms = 0, nbuckets, i;
357 struct symbol **buckets;
358 const struct pending *list_counter;
359
360 retval = obstack_alloc (obstack, sizeof (struct dictionary))__extension__ ({ struct obstack *__h = (obstack); __extension__
({ struct obstack *__o = (__h); int __len = ((sizeof (struct
dictionary))); if (__o->chunk_limit - __o->next_free <
__len) _obstack_newchunk (__o, __len); ((__o)->next_free +=
(__len)); (void) 0; }); __extension__ ({ struct obstack *__o1
= (__h); void *value; value = (void *) __o1->object_base;
if (__o1->next_free == value) __o1->maybe_empty_object
= 1; __o1->next_free = (((((__o1->next_free) - (char *
) 0)+__o1->alignment_mask) & ~ (__o1->alignment_mask
)) + (char *) 0); if (__o1->next_free - (char *)__o1->chunk
> __o1->chunk_limit - (char *)__o1->chunk) __o1->
next_free = __o1->chunk_limit; __o1->object_base = __o1
->next_free; value; }); });
361 DICT_VECTOR (retval)(retval)->vector = &dict_hashed_vector;
362
363 /* Calculate the number of symbols, and allocate space for them. */
364 for (list_counter = symbol_list;
365 list_counter != NULL((void*)0);
366 list_counter = list_counter->next)
367 {
368 nsyms += list_counter->nsyms;
369 }
370 nbuckets = DICT_HASHTABLE_SIZE (nsyms)((nsyms)/5 + 1);
371 DICT_HASHED_NBUCKETS (retval)(retval)->data.hashed.nbuckets = nbuckets;
372 buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *))__extension__ ({ struct obstack *__h = (obstack); __extension__
({ struct obstack *__o = (__h); int __len = ((nbuckets * sizeof
(struct symbol *))); if (__o->chunk_limit - __o->next_free
< __len) _obstack_newchunk (__o, __len); ((__o)->next_free
+= (__len)); (void) 0; }); __extension__ ({ struct obstack *
__o1 = (__h); void *value; value = (void *) __o1->object_base
; if (__o1->next_free == value) __o1->maybe_empty_object
= 1; __o1->next_free = (((((__o1->next_free) - (char *
) 0)+__o1->alignment_mask) & ~ (__o1->alignment_mask
)) + (char *) 0); if (__o1->next_free - (char *)__o1->chunk
> __o1->chunk_limit - (char *)__o1->chunk) __o1->
next_free = __o1->chunk_limit; __o1->object_base = __o1
->next_free; value; }); });
373 memset (buckets, 0, nbuckets * sizeof (struct symbol *));
374 DICT_HASHED_BUCKETS (retval)(retval)->data.hashed.buckets = buckets;
375
376 /* Now fill the buckets. */
377 for (list_counter = symbol_list;
378 list_counter != NULL((void*)0);
379 list_counter = list_counter->next)
380 {
381 for (i = list_counter->nsyms - 1; i >= 0; --i)
382 {
383 insert_symbol_hashed (retval, list_counter->symbol[i]);
384 }
385 }
386
387 return retval;
388}
389
390/* Create a dictionary implemented via a hashtable that grows as
391 necessary. The dictionary is initially empty; to add symbols to
392 it, call dict_add_symbol(). Call dict_free() when you're done with
393 it. */
394
395extern struct dictionary *
396dict_create_hashed_expandable (void)
397{
398 struct dictionary *retval;
399
400 retval = xmalloc (sizeof (struct dictionary));
401 DICT_VECTOR (retval)(retval)->vector = &dict_hashed_expandable_vector;
402 DICT_HASHED_NBUCKETS (retval)(retval)->data.hashed.nbuckets = DICT_EXPANDABLE_INITIAL_CAPACITY10;
403 DICT_HASHED_BUCKETS (retval)(retval)->data.hashed.buckets = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY10,
404 sizeof (struct symbol *));
405 DICT_HASHED_EXPANDABLE_NSYMS (retval)(retval)->data.hashed_expandable.nsyms = 0;
406
407 return retval;
408}
409
410/* Create a dictionary implemented via a fixed-size array. All memory
411 it uses is allocated on OBSTACK; the environment is initialized
412 from the SYMBOL_LIST. The symbols are ordered in the same order
413 that they're found in SYMBOL_LIST. */
414
415struct dictionary *
416dict_create_linear (struct obstack *obstack,
417 const struct pending *symbol_list)
418{
419 struct dictionary *retval;
420 int nsyms = 0, i, j;
421 struct symbol **syms;
422 const struct pending *list_counter;
423
424 retval = obstack_alloc (obstack, sizeof (struct dictionary))__extension__ ({ struct obstack *__h = (obstack); __extension__
({ struct obstack *__o = (__h); int __len = ((sizeof (struct
dictionary))); if (__o->chunk_limit - __o->next_free <
__len) _obstack_newchunk (__o, __len); ((__o)->next_free +=
(__len)); (void) 0; }); __extension__ ({ struct obstack *__o1
= (__h); void *value; value = (void *) __o1->object_base;
if (__o1->next_free == value) __o1->maybe_empty_object
= 1; __o1->next_free = (((((__o1->next_free) - (char *
) 0)+__o1->alignment_mask) & ~ (__o1->alignment_mask
)) + (char *) 0); if (__o1->next_free - (char *)__o1->chunk
> __o1->chunk_limit - (char *)__o1->chunk) __o1->
next_free = __o1->chunk_limit; __o1->object_base = __o1
->next_free; value; }); });
425 DICT_VECTOR (retval)(retval)->vector = &dict_linear_vector;
426
427 /* Calculate the number of symbols, and allocate space for them. */
428 for (list_counter = symbol_list;
429 list_counter != NULL((void*)0);
430 list_counter = list_counter->next)
431 {
432 nsyms += list_counter->nsyms;
433 }
434 DICT_LINEAR_NSYMS (retval)(retval)->data.linear.nsyms = nsyms;
435 syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *))__extension__ ({ struct obstack *__h = (obstack); __extension__
({ struct obstack *__o = (__h); int __len = ((nsyms * sizeof
(struct symbol *))); if (__o->chunk_limit - __o->next_free
< __len) _obstack_newchunk (__o, __len); ((__o)->next_free
+= (__len)); (void) 0; }); __extension__ ({ struct obstack *
__o1 = (__h); void *value; value = (void *) __o1->object_base
; if (__o1->next_free == value) __o1->maybe_empty_object
= 1; __o1->next_free = (((((__o1->next_free) - (char *
) 0)+__o1->alignment_mask) & ~ (__o1->alignment_mask
)) + (char *) 0); if (__o1->next_free - (char *)__o1->chunk
> __o1->chunk_limit - (char *)__o1->chunk) __o1->
next_free = __o1->chunk_limit; __o1->object_base = __o1
->next_free; value; }); });
436 DICT_LINEAR_SYMS (retval)(retval)->data.linear.syms = syms;
437
438 /* Now fill in the symbols. Start filling in from the back, so as
439 to preserve the original order of the symbols. */
440 for (list_counter = symbol_list, j = nsyms - 1;
441 list_counter != NULL((void*)0);
442 list_counter = list_counter->next)
443 {
444 for (i = list_counter->nsyms - 1;
445 i >= 0;
446 --i, --j)
447 {
448 syms[j] = list_counter->symbol[i];
449 }
450 }
451
452 return retval;
453}
454
455/* Create a dictionary implemented via an array that grows as
456 necessary. The dictionary is initially empty; to add symbols to
457 it, call dict_add_symbol(). Call dict_free() when you're done with
458 it. */
459
460struct dictionary *
461dict_create_linear_expandable (void)
462{
463 struct dictionary *retval;
464
465 retval = xmalloc (sizeof (struct dictionary));
466 DICT_VECTOR (retval)(retval)->vector = &dict_linear_expandable_vector;
467 DICT_LINEAR_NSYMS (retval)(retval)->data.linear.nsyms = 0;
468 DICT_LINEAR_EXPANDABLE_CAPACITY (retval)(retval)->data.linear_expandable.capacity
469 = DICT_EXPANDABLE_INITIAL_CAPACITY10;
470 DICT_LINEAR_SYMS (retval)(retval)->data.linear.syms
471 = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval)(retval)->data.linear_expandable.capacity
472 * sizeof (struct symbol *));
473
474 return retval;
475}
476
477/* The functions providing the dictionary interface. */
478
479/* Free the memory used by a dictionary that's not on an obstack. (If
480 any.) */
481
482void
483dict_free (struct dictionary *dict)
484{
485 (DICT_VECTOR (dict)(dict)->vector)->free (dict);
486}
487
488/* Add SYM to DICT. DICT had better be expandable. */
489
490void
491dict_add_symbol (struct dictionary *dict, struct symbol *sym)
492{
493 (DICT_VECTOR (dict)(dict)->vector)->add_symbol (dict, sym);
494}
495
496/* Initialize ITERATOR to point at the first symbol in DICT, and
497 return that first symbol, or NULL if DICT is empty. */
498
499struct symbol *
500dict_iterator_first (const struct dictionary *dict,
501 struct dict_iterator *iterator)
502{
503 return (DICT_VECTOR (dict)(dict)->vector)->iterator_first (dict, iterator);
504}
505
506/* Advance ITERATOR, and return the next symbol, or NULL if there are
507 no more symbols. */
508
509struct symbol *
510dict_iterator_next (struct dict_iterator *iterator)
511{
512 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator))((iterator)->dict)->vector)
513 ->iterator_next (iterator);
514}
515
516struct symbol *
517dict_iter_name_first (const struct dictionary *dict,
518 const char *name,
519 struct dict_iterator *iterator)
520{
521 return (DICT_VECTOR (dict)(dict)->vector)->iter_name_first (dict, name, iterator);
522}
523
524struct symbol *
525dict_iter_name_next (const char *name, struct dict_iterator *iterator)
526{
527 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator))((iterator)->dict)->vector)
528 ->iter_name_next (name, iterator);
529}
530
531int
532dict_size (const struct dictionary *dict)
533{
534 return (DICT_VECTOR (dict)(dict)->vector)->size (dict);
535}
536
537/* Now come functions (well, one function, currently) that are
538 implemented generically by means of the vtable. Typically, they're
539 rarely used. */
540
541/* Test to see if DICT is empty. */
542
543int
544dict_empty (struct dictionary *dict)
545{
546 struct dict_iterator iter;
547
548 return (dict_iterator_first (dict, &iter) == NULL((void*)0));
549}
550
551
552/* The functions implementing the dictionary interface. */
553
554/* Generic functions, where appropriate. */
555
556static void
557free_obstack (struct dictionary *dict)
558{
559 /* Do nothing! */
560}
561
562static void
563add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
564{
565 internal_error (__FILE__"/usr/src/gnu/usr.bin/binutils/gdb/dictionary.c", __LINE__565,
566 "dict_add_symbol: non-expandable dictionary");
567}
568
569/* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
570
571static struct symbol *
572iterator_first_hashed (const struct dictionary *dict,
573 struct dict_iterator *iterator)
574{
575 DICT_ITERATOR_DICT (iterator)(iterator)->dict = dict;
576 DICT_ITERATOR_INDEX (iterator)(iterator)->index = -1;
577 return iterator_hashed_advance (iterator);
578}
579
580static struct symbol *
581iterator_next_hashed (struct dict_iterator *iterator)
582{
583 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator)(iterator)->dict;
Value stored to 'dict' during its initialization is never read
584 struct symbol *next;
585
586 next = DICT_ITERATOR_CURRENT (iterator)(iterator)->current->hash_next;
587
588 if (next == NULL((void*)0))
589 return iterator_hashed_advance (iterator);
590 else
591 {
592 DICT_ITERATOR_CURRENT (iterator)(iterator)->current = next;
593 return next;
594 }
595}
596
597static struct symbol *
598iterator_hashed_advance (struct dict_iterator *iterator)
599{
600 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator)(iterator)->dict;
601 int nbuckets = DICT_HASHED_NBUCKETS (dict)(dict)->data.hashed.nbuckets;
602 int i;
603
604 for (i = DICT_ITERATOR_INDEX (iterator)(iterator)->index + 1; i < nbuckets; ++i)
605 {
606 struct symbol *sym = DICT_HASHED_BUCKET (dict, i)(dict)->data.hashed.buckets [i];
607
608 if (sym != NULL((void*)0))
609 {
610 DICT_ITERATOR_INDEX (iterator)(iterator)->index = i;
611 DICT_ITERATOR_CURRENT (iterator)(iterator)->current = sym;
612 return sym;
613 }
614 }
615
616 return NULL((void*)0);
617}
618
619static struct symbol *
620iter_name_first_hashed (const struct dictionary *dict,
621 const char *name,
622 struct dict_iterator *iterator)
623{
624 unsigned int hash_index
625 = msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict)(dict)->data.hashed.nbuckets;
626 struct symbol *sym;
627
628 DICT_ITERATOR_DICT (iterator)(iterator)->dict = dict;
629
630 /* Loop through the symbols in the given bucket, breaking when SYM
631 first matches. If SYM never matches, it will be set to NULL;
632 either way, we have the right return value. */
633
634 for (sym = DICT_HASHED_BUCKET (dict, hash_index)(dict)->data.hashed.buckets [hash_index];
635 sym != NULL((void*)0);
636 sym = sym->hash_next)
637 {
638 /* Warning: the order of arguments to strcmp_iw matters! */
639 if (strcmp_iw (SYMBOL_SEARCH_NAME (sym)(symbol_search_name (&(sym)->ginfo)), name) == 0)
640 {
641 break;
642 }
643
644 }
645
646 DICT_ITERATOR_CURRENT (iterator)(iterator)->current = sym;
647 return sym;
648}
649
650static struct symbol *
651iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
652{
653 struct symbol *next;
654
655 for (next = DICT_ITERATOR_CURRENT (iterator)(iterator)->current->hash_next;
656 next != NULL((void*)0);
657 next = next->hash_next)
658 {
659 if (strcmp_iw (SYMBOL_SEARCH_NAME (next)(symbol_search_name (&(next)->ginfo)), name) == 0)
660 break;
661 }
662
663 DICT_ITERATOR_CURRENT (iterator)(iterator)->current = next;
664
665 return next;
666}
667
668/* Insert SYM into DICT. */
669
670static void
671insert_symbol_hashed (struct dictionary *dict,
672 struct symbol *sym)
673{
674 unsigned int hash_index;
675 struct symbol **buckets = DICT_HASHED_BUCKETS (dict)(dict)->data.hashed.buckets;
676
677 hash_index = (msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym)(symbol_search_name (&(sym)->ginfo)))
678 % DICT_HASHED_NBUCKETS (dict)(dict)->data.hashed.nbuckets);
679 sym->hash_next = buckets[hash_index];
680 buckets[hash_index] = sym;
681}
682
683static int
684size_hashed (const struct dictionary *dict)
685{
686 return DICT_HASHED_NBUCKETS (dict)(dict)->data.hashed.nbuckets;
687}
688
689/* Functions only for DICT_HASHED_EXPANDABLE. */
690
691static void
692free_hashed_expandable (struct dictionary *dict)
693{
694 xfree (DICT_HASHED_BUCKETS (dict)(dict)->data.hashed.buckets);
695 xfree (dict);
696}
697
698static void
699add_symbol_hashed_expandable (struct dictionary *dict,
700 struct symbol *sym)
701{
702 int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict)(dict)->data.hashed_expandable.nsyms;
703
704 if (DICT_HASHTABLE_SIZE (nsyms)((nsyms)/5 + 1) > DICT_HASHED_NBUCKETS (dict)(dict)->data.hashed.nbuckets)
705 expand_hashtable (dict);
706
707 insert_symbol_hashed (dict, sym);
708 DICT_HASHED_EXPANDABLE_NSYMS (dict)(dict)->data.hashed_expandable.nsyms = nsyms;
709}
710
711static int
712size_hashed_expandable (const struct dictionary *dict)
713{
714 return DICT_HASHED_EXPANDABLE_NSYMS (dict)(dict)->data.hashed_expandable.nsyms;
715}
716
717static void
718expand_hashtable (struct dictionary *dict)
719{
720 int old_nbuckets = DICT_HASHED_NBUCKETS (dict)(dict)->data.hashed.nbuckets;
721 struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict)(dict)->data.hashed.buckets;
722 int new_nbuckets = 2*old_nbuckets + 1;
723 struct symbol **new_buckets = xcalloc (new_nbuckets,
724 sizeof (struct symbol *));
725 int i;
726
727 DICT_HASHED_NBUCKETS (dict)(dict)->data.hashed.nbuckets = new_nbuckets;
728 DICT_HASHED_BUCKETS (dict)(dict)->data.hashed.buckets = new_buckets;
729
730 for (i = 0; i < old_nbuckets; ++i) {
731 struct symbol *sym, *next_sym;
732
733 sym = old_buckets[i];
734 if (sym != NULL((void*)0)) {
735 for (next_sym = sym->hash_next;
736 next_sym != NULL((void*)0);
737 next_sym = sym->hash_next) {
738 insert_symbol_hashed (dict, sym);
739 sym = next_sym;
740 }
741
742 insert_symbol_hashed (dict, sym);
743 }
744 }
745
746 xfree (old_buckets);
747}
748
749/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE. */
750
751static struct symbol *
752iterator_first_linear (const struct dictionary *dict,
753 struct dict_iterator *iterator)
754{
755 DICT_ITERATOR_DICT (iterator)(iterator)->dict = dict;
756 DICT_ITERATOR_INDEX (iterator)(iterator)->index = 0;
757 return DICT_LINEAR_NSYMS (dict)(dict)->data.linear.nsyms ? DICT_LINEAR_SYM (dict, 0)(dict)->data.linear.syms [0] : NULL((void*)0);
758}
759
760static struct symbol *
761iterator_next_linear (struct dict_iterator *iterator)
762{
763 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator)(iterator)->dict;
764
765 if (++DICT_ITERATOR_INDEX (iterator)(iterator)->index >= DICT_LINEAR_NSYMS (dict)(dict)->data.linear.nsyms)
766 return NULL((void*)0);
767 else
768 return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator))(dict)->data.linear.syms [(iterator)->index];
769}
770
771static struct symbol *
772iter_name_first_linear (const struct dictionary *dict,
773 const char *name,
774 struct dict_iterator *iterator)
775{
776 DICT_ITERATOR_DICT (iterator)(iterator)->dict = dict;
777 DICT_ITERATOR_INDEX (iterator)(iterator)->index = -1;
778
779 return iter_name_next_linear (name, iterator);
780}
781
782static struct symbol *
783iter_name_next_linear (const char *name, struct dict_iterator *iterator)
784{
785 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator)(iterator)->dict;
786 int i, nsyms = DICT_LINEAR_NSYMS (dict)(dict)->data.linear.nsyms;
787 struct symbol *sym, *retval = NULL((void*)0);
788
789 for (i = DICT_ITERATOR_INDEX (iterator)(iterator)->index + 1; i < nsyms; ++i)
790 {
791 sym = DICT_LINEAR_SYM (dict, i)(dict)->data.linear.syms [i];
792 if (strcmp_iw (SYMBOL_SEARCH_NAME (sym)(symbol_search_name (&(sym)->ginfo)), name) == 0)
793 {
794 retval = sym;
795 break;
796 }
797 }
798
799 DICT_ITERATOR_INDEX (iterator)(iterator)->index = i;
800
801 return retval;
802}
803
804static int
805size_linear (const struct dictionary *dict)
806{
807 return DICT_LINEAR_NSYMS (dict)(dict)->data.linear.nsyms;
808}
809
810/* Functions only for DICT_LINEAR_EXPANDABLE. */
811
812static void
813free_linear_expandable (struct dictionary *dict)
814{
815 xfree (DICT_LINEAR_SYMS (dict)(dict)->data.linear.syms);
816 xfree (dict);
817}
818
819
820static void
821add_symbol_linear_expandable (struct dictionary *dict,
822 struct symbol *sym)
823{
824 int nsyms = ++DICT_LINEAR_NSYMS (dict)(dict)->data.linear.nsyms;
825
826 /* Do we have enough room? If not, grow it. */
827 if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)(dict)->data.linear_expandable.capacity) {
828 DICT_LINEAR_EXPANDABLE_CAPACITY (dict)(dict)->data.linear_expandable.capacity *= 2;
829 DICT_LINEAR_SYMS (dict)(dict)->data.linear.syms
830 = xrealloc (DICT_LINEAR_SYMS (dict)(dict)->data.linear.syms,
831 DICT_LINEAR_EXPANDABLE_CAPACITY (dict)(dict)->data.linear_expandable.capacity
832 * sizeof (struct symbol *));
833 }
834
835 DICT_LINEAR_SYM (dict, nsyms - 1)(dict)->data.linear.syms [nsyms - 1] = sym;
836}