gdb/
[deliverable/binutils-gdb.git] / gdb / dictionary.c
1 /* Routines for name->symbol lookups in GDB.
2
3 Copyright (C) 2003, 2007, 2008, 2009, 2010 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 "gdb_obstack.h"
25 #include "symtab.h"
26 #include "buildsym.h"
27 #include "gdb_assert.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 */
87
88 /* An enum representing the various implementations of dictionaries.
89 Used only for debugging. */
90
91 enum dict_type
92 {
93 /* Symbols are stored in a fixed-size hash table. */
94 DICT_HASHED,
95 /* Symbols are stored in an expandable hash table. */
96 DICT_HASHED_EXPANDABLE,
97 /* Symbols are stored in a fixed-size array. */
98 DICT_LINEAR,
99 /* Symbols are stored in an expandable array. */
100 DICT_LINEAR_EXPANDABLE
101 };
102
103 /* The virtual function table. */
104
105 struct dict_vector
106 {
107 /* The type of the dictionary. This is only here to make debugging
108 a bit easier; it's not actually used. */
109 enum dict_type type;
110 /* The function to free a dictionary. */
111 void (*free) (struct dictionary *dict);
112 /* Add a symbol to a dictionary, if possible. */
113 void (*add_symbol) (struct dictionary *dict, struct symbol *sym);
114 /* Iterator functions. */
115 struct symbol *(*iterator_first) (const struct dictionary *dict,
116 struct dict_iterator *iterator);
117 struct symbol *(*iterator_next) (struct dict_iterator *iterator);
118 /* Functions to iterate over symbols with a given name. */
119 struct symbol *(*iter_name_first) (const struct dictionary *dict,
120 const char *name,
121 struct dict_iterator *iterator);
122 struct symbol *(*iter_name_next) (const char *name,
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
133 struct dictionary_hashed
134 {
135 int nbuckets;
136 struct symbol **buckets;
137 };
138
139 struct dictionary_hashed_expandable
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
149 struct dictionary_linear
150 {
151 int nsyms;
152 struct symbol **syms;
153 };
154
155 struct dictionary_linear_expandable
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
166 struct dictionary
167 {
168 const struct dict_vector *vector;
169 union
170 {
171 struct dictionary_hashed hashed;
172 struct dictionary_hashed_expandable hashed_expandable;
173 struct dictionary_linear linear;
174 struct dictionary_linear_expandable linear_expandable;
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_name_first_hashed (const struct dictionary *dict,
240 const char *name,
241 struct dict_iterator *iterator);
242
243 static struct symbol *iter_name_next_hashed (const char *name,
244 struct dict_iterator *iterator);
245
246 /* Functions only for DICT_HASHED. */
247
248 static int size_hashed (const struct dictionary *dict);
249
250 /* Functions only for DICT_HASHED_EXPANDABLE. */
251
252 static void free_hashed_expandable (struct dictionary *dict);
253
254 static void add_symbol_hashed_expandable (struct dictionary *dict,
255 struct symbol *sym);
256
257 static int size_hashed_expandable (const struct dictionary *dict);
258
259 /* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE
260 dictionaries. */
261
262 static struct symbol *iterator_first_linear (const struct dictionary *dict,
263 struct dict_iterator *iterator);
264
265 static struct symbol *iterator_next_linear (struct dict_iterator *iterator);
266
267 static struct symbol *iter_name_first_linear (const struct dictionary *dict,
268 const char *name,
269 struct dict_iterator *iterator);
270
271 static struct symbol *iter_name_next_linear (const char *name,
272 struct dict_iterator *iterator);
273
274 static int size_linear (const struct dictionary *dict);
275
276 /* Functions only for DICT_LINEAR_EXPANDABLE. */
277
278 static void free_linear_expandable (struct dictionary *dict);
279
280 static void add_symbol_linear_expandable (struct dictionary *dict,
281 struct symbol *sym);
282
283 /* Various vectors that we'll actually use. */
284
285 static const struct dict_vector dict_hashed_vector =
286 {
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_name_first_hashed, /* iter_name_first */
293 iter_name_next_hashed, /* iter_name_next */
294 size_hashed, /* size */
295 };
296
297 static const struct dict_vector dict_hashed_expandable_vector =
298 {
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_name_first_hashed, /* iter_name_first */
305 iter_name_next_hashed, /* iter_name_next */
306 size_hashed_expandable, /* size */
307 };
308
309 static const struct dict_vector dict_linear_vector =
310 {
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_name_first_linear, /* iter_name_first */
317 iter_name_next_linear, /* iter_name_next */
318 size_linear, /* size */
319 };
320
321 static const struct dict_vector dict_linear_expandable_vector =
322 {
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_name_first_linear, /* iter_name_first */
329 iter_name_next_linear, /* iter_name_next */
330 size_linear, /* size */
331 };
332
333 /* Declarations of helper functions (i.e. ones that don't go into
334 vectors). */
335
336 static struct symbol *iterator_hashed_advance (struct dict_iterator *iter);
337
338 static void insert_symbol_hashed (struct dictionary *dict,
339 struct symbol *sym);
340
341 static void expand_hashtable (struct dictionary *dict);
342
343 /* The creation functions. */
344
345 /* Create a dictionary implemented via a fixed-size hashtable. All
346 memory it uses is allocated on OBSTACK; the environment is
347 initialized from SYMBOL_LIST. */
348
349 struct dictionary *
350 dict_create_hashed (struct obstack *obstack,
351 const struct pending *symbol_list)
352 {
353 struct dictionary *retval;
354 int nsyms = 0, nbuckets, i;
355 struct symbol **buckets;
356 const struct pending *list_counter;
357
358 retval = obstack_alloc (obstack, sizeof (struct dictionary));
359 DICT_VECTOR (retval) = &dict_hashed_vector;
360
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)
365 {
366 nsyms += list_counter->nsyms;
367 }
368 nbuckets = DICT_HASHTABLE_SIZE (nsyms);
369 DICT_HASHED_NBUCKETS (retval) = nbuckets;
370 buckets = obstack_alloc (obstack, nbuckets * sizeof (struct symbol *));
371 memset (buckets, 0, nbuckets * sizeof (struct symbol *));
372 DICT_HASHED_BUCKETS (retval) = buckets;
373
374 /* Now fill the buckets. */
375 for (list_counter = symbol_list;
376 list_counter != NULL;
377 list_counter = list_counter->next)
378 {
379 for (i = list_counter->nsyms - 1; i >= 0; --i)
380 {
381 insert_symbol_hashed (retval, list_counter->symbol[i]);
382 }
383 }
384
385 return retval;
386 }
387
388 /* Create a dictionary implemented via a hashtable that grows as
389 necessary. The dictionary is initially empty; to add symbols to
390 it, call dict_add_symbol(). Call dict_free() when you're done with
391 it. */
392
393 extern struct dictionary *
394 dict_create_hashed_expandable (void)
395 {
396 struct dictionary *retval;
397
398 retval = xmalloc (sizeof (struct dictionary));
399 DICT_VECTOR (retval) = &dict_hashed_expandable_vector;
400 DICT_HASHED_NBUCKETS (retval) = DICT_EXPANDABLE_INITIAL_CAPACITY;
401 DICT_HASHED_BUCKETS (retval) = xcalloc (DICT_EXPANDABLE_INITIAL_CAPACITY,
402 sizeof (struct symbol *));
403 DICT_HASHED_EXPANDABLE_NSYMS (retval) = 0;
404
405 return retval;
406 }
407
408 /* Create a dictionary implemented via a fixed-size array. All memory
409 it uses is allocated on OBSTACK; the environment is initialized
410 from the SYMBOL_LIST. The symbols are ordered in the same order
411 that they're found in SYMBOL_LIST. */
412
413 struct dictionary *
414 dict_create_linear (struct obstack *obstack,
415 const struct pending *symbol_list)
416 {
417 struct dictionary *retval;
418 int nsyms = 0, i, j;
419 struct symbol **syms;
420 const struct pending *list_counter;
421
422 retval = obstack_alloc (obstack, sizeof (struct dictionary));
423 DICT_VECTOR (retval) = &dict_linear_vector;
424
425 /* Calculate the number of symbols, and allocate space for them. */
426 for (list_counter = symbol_list;
427 list_counter != NULL;
428 list_counter = list_counter->next)
429 {
430 nsyms += list_counter->nsyms;
431 }
432 DICT_LINEAR_NSYMS (retval) = nsyms;
433 syms = obstack_alloc (obstack, nsyms * sizeof (struct symbol *));
434 DICT_LINEAR_SYMS (retval) = syms;
435
436 /* Now fill in the symbols. Start filling in from the back, so as
437 to preserve the original order of the symbols. */
438 for (list_counter = symbol_list, j = nsyms - 1;
439 list_counter != NULL;
440 list_counter = list_counter->next)
441 {
442 for (i = list_counter->nsyms - 1;
443 i >= 0;
444 --i, --j)
445 {
446 syms[j] = list_counter->symbol[i];
447 }
448 }
449
450 return retval;
451 }
452
453 /* Create a dictionary implemented via an array that grows as
454 necessary. The dictionary is initially empty; to add symbols to
455 it, call dict_add_symbol(). Call dict_free() when you're done with
456 it. */
457
458 struct dictionary *
459 dict_create_linear_expandable (void)
460 {
461 struct dictionary *retval;
462
463 retval = xmalloc (sizeof (struct dictionary));
464 DICT_VECTOR (retval) = &dict_linear_expandable_vector;
465 DICT_LINEAR_NSYMS (retval) = 0;
466 DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
467 = DICT_EXPANDABLE_INITIAL_CAPACITY;
468 DICT_LINEAR_SYMS (retval)
469 = xmalloc (DICT_LINEAR_EXPANDABLE_CAPACITY (retval)
470 * sizeof (struct symbol *));
471
472 return retval;
473 }
474
475 /* The functions providing the dictionary interface. */
476
477 /* Free the memory used by a dictionary that's not on an obstack. (If
478 any.) */
479
480 void
481 dict_free (struct dictionary *dict)
482 {
483 (DICT_VECTOR (dict))->free (dict);
484 }
485
486 /* Add SYM to DICT. DICT had better be expandable. */
487
488 void
489 dict_add_symbol (struct dictionary *dict, struct symbol *sym)
490 {
491 (DICT_VECTOR (dict))->add_symbol (dict, sym);
492 }
493
494 /* Initialize ITERATOR to point at the first symbol in DICT, and
495 return that first symbol, or NULL if DICT is empty. */
496
497 struct symbol *
498 dict_iterator_first (const struct dictionary *dict,
499 struct dict_iterator *iterator)
500 {
501 return (DICT_VECTOR (dict))->iterator_first (dict, iterator);
502 }
503
504 /* Advance ITERATOR, and return the next symbol, or NULL if there are
505 no more symbols. */
506
507 struct symbol *
508 dict_iterator_next (struct dict_iterator *iterator)
509 {
510 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
511 ->iterator_next (iterator);
512 }
513
514 struct symbol *
515 dict_iter_name_first (const struct dictionary *dict,
516 const char *name,
517 struct dict_iterator *iterator)
518 {
519 return (DICT_VECTOR (dict))->iter_name_first (dict, name, iterator);
520 }
521
522 struct symbol *
523 dict_iter_name_next (const char *name, struct dict_iterator *iterator)
524 {
525 return (DICT_VECTOR (DICT_ITERATOR_DICT (iterator)))
526 ->iter_name_next (name, iterator);
527 }
528
529 int
530 dict_size (const struct dictionary *dict)
531 {
532 return (DICT_VECTOR (dict))->size (dict);
533 }
534
535 /* Now come functions (well, one function, currently) that are
536 implemented generically by means of the vtable. Typically, they're
537 rarely used. */
538
539 /* Test to see if DICT is empty. */
540
541 int
542 dict_empty (struct dictionary *dict)
543 {
544 struct dict_iterator iter;
545
546 return (dict_iterator_first (dict, &iter) == NULL);
547 }
548
549
550 /* The functions implementing the dictionary interface. */
551
552 /* Generic functions, where appropriate. */
553
554 static void
555 free_obstack (struct dictionary *dict)
556 {
557 /* Do nothing! */
558 }
559
560 static void
561 add_symbol_nonexpandable (struct dictionary *dict, struct symbol *sym)
562 {
563 internal_error (__FILE__, __LINE__,
564 _("dict_add_symbol: non-expandable dictionary"));
565 }
566
567 /* Functions for DICT_HASHED and DICT_HASHED_EXPANDABLE. */
568
569 static struct symbol *
570 iterator_first_hashed (const struct dictionary *dict,
571 struct dict_iterator *iterator)
572 {
573 DICT_ITERATOR_DICT (iterator) = dict;
574 DICT_ITERATOR_INDEX (iterator) = -1;
575 return iterator_hashed_advance (iterator);
576 }
577
578 static struct symbol *
579 iterator_next_hashed (struct dict_iterator *iterator)
580 {
581 struct symbol *next;
582
583 next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
584
585 if (next == NULL)
586 return iterator_hashed_advance (iterator);
587 else
588 {
589 DICT_ITERATOR_CURRENT (iterator) = next;
590 return next;
591 }
592 }
593
594 static struct symbol *
595 iterator_hashed_advance (struct dict_iterator *iterator)
596 {
597 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
598 int nbuckets = DICT_HASHED_NBUCKETS (dict);
599 int i;
600
601 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
602 {
603 struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
604
605 if (sym != NULL)
606 {
607 DICT_ITERATOR_INDEX (iterator) = i;
608 DICT_ITERATOR_CURRENT (iterator) = sym;
609 return sym;
610 }
611 }
612
613 return NULL;
614 }
615
616 static struct symbol *
617 iter_name_first_hashed (const struct dictionary *dict,
618 const char *name,
619 struct dict_iterator *iterator)
620 {
621 unsigned int hash_index
622 = msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict);
623 struct symbol *sym;
624
625 DICT_ITERATOR_DICT (iterator) = dict;
626
627 /* Loop through the symbols in the given bucket, breaking when SYM
628 first matches. If SYM never matches, it will be set to NULL;
629 either way, we have the right return value. */
630
631 for (sym = DICT_HASHED_BUCKET (dict, hash_index);
632 sym != NULL;
633 sym = sym->hash_next)
634 {
635 /* Warning: the order of arguments to strcmp_iw matters! */
636 if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
637 {
638 break;
639 }
640
641 }
642
643 DICT_ITERATOR_CURRENT (iterator) = sym;
644 return sym;
645 }
646
647 static struct symbol *
648 iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
649 {
650 struct symbol *next;
651
652 for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
653 next != NULL;
654 next = next->hash_next)
655 {
656 if (strcmp_iw (SYMBOL_SEARCH_NAME (next), name) == 0)
657 break;
658 }
659
660 DICT_ITERATOR_CURRENT (iterator) = next;
661
662 return next;
663 }
664
665 /* Insert SYM into DICT. */
666
667 static void
668 insert_symbol_hashed (struct dictionary *dict,
669 struct symbol *sym)
670 {
671 unsigned int hash_index;
672 struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
673
674 hash_index = (msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym))
675 % DICT_HASHED_NBUCKETS (dict));
676 sym->hash_next = buckets[hash_index];
677 buckets[hash_index] = sym;
678 }
679
680 static int
681 size_hashed (const struct dictionary *dict)
682 {
683 return DICT_HASHED_NBUCKETS (dict);
684 }
685
686 /* Functions only for DICT_HASHED_EXPANDABLE. */
687
688 static void
689 free_hashed_expandable (struct dictionary *dict)
690 {
691 xfree (DICT_HASHED_BUCKETS (dict));
692 xfree (dict);
693 }
694
695 static void
696 add_symbol_hashed_expandable (struct dictionary *dict,
697 struct symbol *sym)
698 {
699 int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
700
701 if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
702 expand_hashtable (dict);
703
704 insert_symbol_hashed (dict, sym);
705 DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
706 }
707
708 static int
709 size_hashed_expandable (const struct dictionary *dict)
710 {
711 return DICT_HASHED_EXPANDABLE_NSYMS (dict);
712 }
713
714 static void
715 expand_hashtable (struct dictionary *dict)
716 {
717 int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
718 struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
719 int new_nbuckets = 2*old_nbuckets + 1;
720 struct symbol **new_buckets = xcalloc (new_nbuckets,
721 sizeof (struct symbol *));
722 int i;
723
724 DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
725 DICT_HASHED_BUCKETS (dict) = new_buckets;
726
727 for (i = 0; i < old_nbuckets; ++i)
728 {
729 struct symbol *sym, *next_sym;
730
731 sym = old_buckets[i];
732 if (sym != NULL)
733 {
734 for (next_sym = sym->hash_next;
735 next_sym != NULL;
736 next_sym = sym->hash_next)
737 {
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
751 static struct symbol *
752 iterator_first_linear (const struct dictionary *dict,
753 struct dict_iterator *iterator)
754 {
755 DICT_ITERATOR_DICT (iterator) = dict;
756 DICT_ITERATOR_INDEX (iterator) = 0;
757 return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
758 }
759
760 static struct symbol *
761 iterator_next_linear (struct dict_iterator *iterator)
762 {
763 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
764
765 if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
766 return NULL;
767 else
768 return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
769 }
770
771 static struct symbol *
772 iter_name_first_linear (const struct dictionary *dict,
773 const char *name,
774 struct dict_iterator *iterator)
775 {
776 DICT_ITERATOR_DICT (iterator) = dict;
777 DICT_ITERATOR_INDEX (iterator) = -1;
778
779 return iter_name_next_linear (name, iterator);
780 }
781
782 static struct symbol *
783 iter_name_next_linear (const char *name, struct dict_iterator *iterator)
784 {
785 const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
786 int i, nsyms = DICT_LINEAR_NSYMS (dict);
787 struct symbol *sym, *retval = NULL;
788
789 for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
790 {
791 sym = DICT_LINEAR_SYM (dict, i);
792 if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
793 {
794 retval = sym;
795 break;
796 }
797 }
798
799 DICT_ITERATOR_INDEX (iterator) = i;
800
801 return retval;
802 }
803
804 static int
805 size_linear (const struct dictionary *dict)
806 {
807 return DICT_LINEAR_NSYMS (dict);
808 }
809
810 /* Functions only for DICT_LINEAR_EXPANDABLE. */
811
812 static void
813 free_linear_expandable (struct dictionary *dict)
814 {
815 xfree (DICT_LINEAR_SYMS (dict));
816 xfree (dict);
817 }
818
819
820 static void
821 add_symbol_linear_expandable (struct dictionary *dict,
822 struct symbol *sym)
823 {
824 int nsyms = ++DICT_LINEAR_NSYMS (dict);
825
826 /* Do we have enough room? If not, grow it. */
827 if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict))
828 {
829 DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
830 DICT_LINEAR_SYMS (dict)
831 = xrealloc (DICT_LINEAR_SYMS (dict),
832 DICT_LINEAR_EXPANDABLE_CAPACITY (dict)
833 * sizeof (struct symbol *));
834 }
835
836 DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
837 }
This page took 0.046773 seconds and 4 git commands to generate.