OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gdb-7.1/] [gdb/] [dictionary.c] - Blame information for rev 227

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 227 jeremybenn
/* 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
  const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
582
  struct symbol *next;
583
 
584
  next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
585
 
586
  if (next == NULL)
587
    return iterator_hashed_advance (iterator);
588
  else
589
    {
590
      DICT_ITERATOR_CURRENT (iterator) = next;
591
      return next;
592
    }
593
}
594
 
595
static struct symbol *
596
iterator_hashed_advance (struct dict_iterator *iterator)
597
{
598
  const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
599
  int nbuckets = DICT_HASHED_NBUCKETS (dict);
600
  int i;
601
 
602
  for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nbuckets; ++i)
603
    {
604
      struct symbol *sym = DICT_HASHED_BUCKET (dict, i);
605
 
606
      if (sym != NULL)
607
        {
608
          DICT_ITERATOR_INDEX (iterator) = i;
609
          DICT_ITERATOR_CURRENT (iterator) = sym;
610
          return sym;
611
        }
612
    }
613
 
614
  return NULL;
615
}
616
 
617
static struct symbol *
618
iter_name_first_hashed (const struct dictionary *dict,
619
                        const char *name,
620
                        struct dict_iterator *iterator)
621
{
622
  unsigned int hash_index
623
    = msymbol_hash_iw (name) % DICT_HASHED_NBUCKETS (dict);
624
  struct symbol *sym;
625
 
626
  DICT_ITERATOR_DICT (iterator) = dict;
627
 
628
  /* Loop through the symbols in the given bucket, breaking when SYM
629
     first matches.  If SYM never matches, it will be set to NULL;
630
     either way, we have the right return value.  */
631
 
632
  for (sym = DICT_HASHED_BUCKET (dict, hash_index);
633
       sym != NULL;
634
       sym = sym->hash_next)
635
    {
636
      /* Warning: the order of arguments to strcmp_iw matters!  */
637
      if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
638
        {
639
          break;
640
        }
641
 
642
    }
643
 
644
  DICT_ITERATOR_CURRENT (iterator) = sym;
645
  return sym;
646
}
647
 
648
static struct symbol *
649
iter_name_next_hashed (const char *name, struct dict_iterator *iterator)
650
{
651
  struct symbol *next;
652
 
653
  for (next = DICT_ITERATOR_CURRENT (iterator)->hash_next;
654
       next != NULL;
655
       next = next->hash_next)
656
    {
657
      if (strcmp_iw (SYMBOL_SEARCH_NAME (next), name) == 0)
658
        break;
659
    }
660
 
661
  DICT_ITERATOR_CURRENT (iterator) = next;
662
 
663
  return next;
664
}
665
 
666
/* Insert SYM into DICT.  */
667
 
668
static void
669
insert_symbol_hashed (struct dictionary *dict,
670
                      struct symbol *sym)
671
{
672
  unsigned int hash_index;
673
  struct symbol **buckets = DICT_HASHED_BUCKETS (dict);
674
 
675
  hash_index = (msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym))
676
                % DICT_HASHED_NBUCKETS (dict));
677
  sym->hash_next = buckets[hash_index];
678
  buckets[hash_index] = sym;
679
}
680
 
681
static int
682
size_hashed (const struct dictionary *dict)
683
{
684
  return DICT_HASHED_NBUCKETS (dict);
685
}
686
 
687
/* Functions only for DICT_HASHED_EXPANDABLE.  */
688
 
689
static void
690
free_hashed_expandable (struct dictionary *dict)
691
{
692
  xfree (DICT_HASHED_BUCKETS (dict));
693
  xfree (dict);
694
}
695
 
696
static void
697
add_symbol_hashed_expandable (struct dictionary *dict,
698
                              struct symbol *sym)
699
{
700
  int nsyms = ++DICT_HASHED_EXPANDABLE_NSYMS (dict);
701
 
702
  if (DICT_HASHTABLE_SIZE (nsyms) > DICT_HASHED_NBUCKETS (dict))
703
    expand_hashtable (dict);
704
 
705
  insert_symbol_hashed (dict, sym);
706
  DICT_HASHED_EXPANDABLE_NSYMS (dict) = nsyms;
707
}
708
 
709
static int
710
size_hashed_expandable (const struct dictionary *dict)
711
{
712
  return DICT_HASHED_EXPANDABLE_NSYMS (dict);
713
}
714
 
715
static void
716
expand_hashtable (struct dictionary *dict)
717
{
718
  int old_nbuckets = DICT_HASHED_NBUCKETS (dict);
719
  struct symbol **old_buckets = DICT_HASHED_BUCKETS (dict);
720
  int new_nbuckets = 2*old_nbuckets + 1;
721
  struct symbol **new_buckets = xcalloc (new_nbuckets,
722
                                         sizeof (struct symbol *));
723
  int i;
724
 
725
  DICT_HASHED_NBUCKETS (dict) = new_nbuckets;
726
  DICT_HASHED_BUCKETS (dict) = new_buckets;
727
 
728
  for (i = 0; i < old_nbuckets; ++i) {
729
    struct symbol *sym, *next_sym;
730
 
731
    sym = old_buckets[i];
732
    if (sym != NULL) {
733
      for (next_sym = sym->hash_next;
734
           next_sym != NULL;
735
           next_sym = sym->hash_next) {
736
        insert_symbol_hashed (dict, sym);
737
        sym = next_sym;
738
      }
739
 
740
      insert_symbol_hashed (dict, sym);
741
    }
742
  }
743
 
744
  xfree (old_buckets);
745
}
746
 
747
/* Functions for DICT_LINEAR and DICT_LINEAR_EXPANDABLE.  */
748
 
749
static struct symbol *
750
iterator_first_linear (const struct dictionary *dict,
751
                       struct dict_iterator *iterator)
752
{
753
  DICT_ITERATOR_DICT (iterator) = dict;
754
  DICT_ITERATOR_INDEX (iterator) = 0;
755
  return DICT_LINEAR_NSYMS (dict) ? DICT_LINEAR_SYM (dict, 0) : NULL;
756
}
757
 
758
static struct symbol *
759
iterator_next_linear (struct dict_iterator *iterator)
760
{
761
  const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
762
 
763
  if (++DICT_ITERATOR_INDEX (iterator) >= DICT_LINEAR_NSYMS (dict))
764
    return NULL;
765
  else
766
    return DICT_LINEAR_SYM (dict, DICT_ITERATOR_INDEX (iterator));
767
}
768
 
769
static struct symbol *
770
iter_name_first_linear (const struct dictionary *dict,
771
                        const char *name,
772
                        struct dict_iterator *iterator)
773
{
774
  DICT_ITERATOR_DICT (iterator) = dict;
775
  DICT_ITERATOR_INDEX (iterator) = -1;
776
 
777
  return iter_name_next_linear (name, iterator);
778
}
779
 
780
static struct symbol *
781
iter_name_next_linear (const char *name, struct dict_iterator *iterator)
782
{
783
  const struct dictionary *dict = DICT_ITERATOR_DICT (iterator);
784
  int i, nsyms = DICT_LINEAR_NSYMS (dict);
785
  struct symbol *sym, *retval = NULL;
786
 
787
  for (i = DICT_ITERATOR_INDEX (iterator) + 1; i < nsyms; ++i)
788
    {
789
      sym = DICT_LINEAR_SYM (dict, i);
790
      if (strcmp_iw (SYMBOL_SEARCH_NAME (sym), name) == 0)
791
        {
792
          retval = sym;
793
          break;
794
        }
795
    }
796
 
797
  DICT_ITERATOR_INDEX (iterator) = i;
798
 
799
  return retval;
800
}
801
 
802
static int
803
size_linear (const struct dictionary *dict)
804
{
805
  return DICT_LINEAR_NSYMS (dict);
806
}
807
 
808
/* Functions only for DICT_LINEAR_EXPANDABLE.  */
809
 
810
static void
811
free_linear_expandable (struct dictionary *dict)
812
{
813
  xfree (DICT_LINEAR_SYMS (dict));
814
  xfree (dict);
815
}
816
 
817
 
818
static void
819
add_symbol_linear_expandable (struct dictionary *dict,
820
                              struct symbol *sym)
821
{
822
  int nsyms = ++DICT_LINEAR_NSYMS (dict);
823
 
824
  /* Do we have enough room?  If not, grow it.  */
825
  if (nsyms > DICT_LINEAR_EXPANDABLE_CAPACITY (dict)) {
826
    DICT_LINEAR_EXPANDABLE_CAPACITY (dict) *= 2;
827
    DICT_LINEAR_SYMS (dict)
828
      = xrealloc (DICT_LINEAR_SYMS (dict),
829
                  DICT_LINEAR_EXPANDABLE_CAPACITY (dict)
830
                  * sizeof (struct symbol *));
831
  }
832
 
833
  DICT_LINEAR_SYM (dict, nsyms - 1) = sym;
834
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.