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

Subversion Repositories open8_urisc

[/] [open8_urisc/] [trunk/] [gnu/] [binutils/] [bfd/] [hash.c] - Blame information for rev 14

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 14 khays
/* hash.c -- hash table routines for BFD
2
   Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005,
3
   2006, 2007, 2009, 2010, 2011  Free Software Foundation, Inc.
4
   Written by Steve Chamberlain <sac@cygnus.com>
5
 
6
   This file is part of BFD, the Binary File Descriptor library.
7
 
8
   This program is free software; you can redistribute it and/or modify
9
   it under the terms of the GNU General Public License as published by
10
   the Free Software Foundation; either version 3 of the License, or
11
   (at your option) any later version.
12
 
13
   This program is distributed in the hope that it will be useful,
14
   but WITHOUT ANY WARRANTY; without even the implied warranty of
15
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
   GNU General Public License for more details.
17
 
18
   You should have received a copy of the GNU General Public License
19
   along with this program; if not, write to the Free Software
20
   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
21
   MA 02110-1301, USA.  */
22
 
23
#include "sysdep.h"
24
#include "bfd.h"
25
#include "libbfd.h"
26
#include "objalloc.h"
27
#include "libiberty.h"
28
 
29
/*
30
SECTION
31
        Hash Tables
32
 
33
@cindex Hash tables
34
        BFD provides a simple set of hash table functions.  Routines
35
        are provided to initialize a hash table, to free a hash table,
36
        to look up a string in a hash table and optionally create an
37
        entry for it, and to traverse a hash table.  There is
38
        currently no routine to delete an string from a hash table.
39
 
40
        The basic hash table does not permit any data to be stored
41
        with a string.  However, a hash table is designed to present a
42
        base class from which other types of hash tables may be
43
        derived.  These derived types may store additional information
44
        with the string.  Hash tables were implemented in this way,
45
        rather than simply providing a data pointer in a hash table
46
        entry, because they were designed for use by the linker back
47
        ends.  The linker may create thousands of hash table entries,
48
        and the overhead of allocating private data and storing and
49
        following pointers becomes noticeable.
50
 
51
        The basic hash table code is in <<hash.c>>.
52
 
53
@menu
54
@* Creating and Freeing a Hash Table::
55
@* Looking Up or Entering a String::
56
@* Traversing a Hash Table::
57
@* Deriving a New Hash Table Type::
58
@end menu
59
 
60
INODE
61
Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables
62
SUBSECTION
63
        Creating and freeing a hash table
64
 
65
@findex bfd_hash_table_init
66
@findex bfd_hash_table_init_n
67
        To create a hash table, create an instance of a <<struct
68
        bfd_hash_table>> (defined in <<bfd.h>>) and call
69
        <<bfd_hash_table_init>> (if you know approximately how many
70
        entries you will need, the function <<bfd_hash_table_init_n>>,
71
        which takes a @var{size} argument, may be used).
72
        <<bfd_hash_table_init>> returns <<FALSE>> if some sort of
73
        error occurs.
74
 
75
@findex bfd_hash_newfunc
76
        The function <<bfd_hash_table_init>> take as an argument a
77
        function to use to create new entries.  For a basic hash
78
        table, use the function <<bfd_hash_newfunc>>.  @xref{Deriving
79
        a New Hash Table Type}, for why you would want to use a
80
        different value for this argument.
81
 
82
@findex bfd_hash_allocate
83
        <<bfd_hash_table_init>> will create an objalloc which will be
84
        used to allocate new entries.  You may allocate memory on this
85
        objalloc using <<bfd_hash_allocate>>.
86
 
87
@findex bfd_hash_table_free
88
        Use <<bfd_hash_table_free>> to free up all the memory that has
89
        been allocated for a hash table.  This will not free up the
90
        <<struct bfd_hash_table>> itself, which you must provide.
91
 
92
@findex bfd_hash_set_default_size
93
        Use <<bfd_hash_set_default_size>> to set the default size of
94
        hash table to use.
95
 
96
INODE
97
Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables
98
SUBSECTION
99
        Looking up or entering a string
100
 
101
@findex bfd_hash_lookup
102
        The function <<bfd_hash_lookup>> is used both to look up a
103
        string in the hash table and to create a new entry.
104
 
105
        If the @var{create} argument is <<FALSE>>, <<bfd_hash_lookup>>
106
        will look up a string.  If the string is found, it will
107
        returns a pointer to a <<struct bfd_hash_entry>>.  If the
108
        string is not found in the table <<bfd_hash_lookup>> will
109
        return <<NULL>>.  You should not modify any of the fields in
110
        the returns <<struct bfd_hash_entry>>.
111
 
112
        If the @var{create} argument is <<TRUE>>, the string will be
113
        entered into the hash table if it is not already there.
114
        Either way a pointer to a <<struct bfd_hash_entry>> will be
115
        returned, either to the existing structure or to a newly
116
        created one.  In this case, a <<NULL>> return means that an
117
        error occurred.
118
 
119
        If the @var{create} argument is <<TRUE>>, and a new entry is
120
        created, the @var{copy} argument is used to decide whether to
121
        copy the string onto the hash table objalloc or not.  If
122
        @var{copy} is passed as <<FALSE>>, you must be careful not to
123
        deallocate or modify the string as long as the hash table
124
        exists.
125
 
126
INODE
127
Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables
128
SUBSECTION
129
        Traversing a hash table
130
 
131
@findex bfd_hash_traverse
132
        The function <<bfd_hash_traverse>> may be used to traverse a
133
        hash table, calling a function on each element.  The traversal
134
        is done in a random order.
135
 
136
        <<bfd_hash_traverse>> takes as arguments a function and a
137
        generic <<void *>> pointer.  The function is called with a
138
        hash table entry (a <<struct bfd_hash_entry *>>) and the
139
        generic pointer passed to <<bfd_hash_traverse>>.  The function
140
        must return a <<boolean>> value, which indicates whether to
141
        continue traversing the hash table.  If the function returns
142
        <<FALSE>>, <<bfd_hash_traverse>> will stop the traversal and
143
        return immediately.
144
 
145
INODE
146
Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables
147
SUBSECTION
148
        Deriving a new hash table type
149
 
150
        Many uses of hash tables want to store additional information
151
        which each entry in the hash table.  Some also find it
152
        convenient to store additional information with the hash table
153
        itself.  This may be done using a derived hash table.
154
 
155
        Since C is not an object oriented language, creating a derived
156
        hash table requires sticking together some boilerplate
157
        routines with a few differences specific to the type of hash
158
        table you want to create.
159
 
160
        An example of a derived hash table is the linker hash table.
161
        The structures for this are defined in <<bfdlink.h>>.  The
162
        functions are in <<linker.c>>.
163
 
164
        You may also derive a hash table from an already derived hash
165
        table.  For example, the a.out linker backend code uses a hash
166
        table derived from the linker hash table.
167
 
168
@menu
169
@* Define the Derived Structures::
170
@* Write the Derived Creation Routine::
171
@* Write Other Derived Routines::
172
@end menu
173
 
174
INODE
175
Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type
176
SUBSUBSECTION
177
        Define the derived structures
178
 
179
        You must define a structure for an entry in the hash table,
180
        and a structure for the hash table itself.
181
 
182
        The first field in the structure for an entry in the hash
183
        table must be of the type used for an entry in the hash table
184
        you are deriving from.  If you are deriving from a basic hash
185
        table this is <<struct bfd_hash_entry>>, which is defined in
186
        <<bfd.h>>.  The first field in the structure for the hash
187
        table itself must be of the type of the hash table you are
188
        deriving from itself.  If you are deriving from a basic hash
189
        table, this is <<struct bfd_hash_table>>.
190
 
191
        For example, the linker hash table defines <<struct
192
        bfd_link_hash_entry>> (in <<bfdlink.h>>).  The first field,
193
        <<root>>, is of type <<struct bfd_hash_entry>>.  Similarly,
194
        the first field in <<struct bfd_link_hash_table>>, <<table>>,
195
        is of type <<struct bfd_hash_table>>.
196
 
197
INODE
198
Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type
199
SUBSUBSECTION
200
        Write the derived creation routine
201
 
202
        You must write a routine which will create and initialize an
203
        entry in the hash table.  This routine is passed as the
204
        function argument to <<bfd_hash_table_init>>.
205
 
206
        In order to permit other hash tables to be derived from the
207
        hash table you are creating, this routine must be written in a
208
        standard way.
209
 
210
        The first argument to the creation routine is a pointer to a
211
        hash table entry.  This may be <<NULL>>, in which case the
212
        routine should allocate the right amount of space.  Otherwise
213
        the space has already been allocated by a hash table type
214
        derived from this one.
215
 
216
        After allocating space, the creation routine must call the
217
        creation routine of the hash table type it is derived from,
218
        passing in a pointer to the space it just allocated.  This
219
        will initialize any fields used by the base hash table.
220
 
221
        Finally the creation routine must initialize any local fields
222
        for the new hash table type.
223
 
224
        Here is a boilerplate example of a creation routine.
225
        @var{function_name} is the name of the routine.
226
        @var{entry_type} is the type of an entry in the hash table you
227
        are creating.  @var{base_newfunc} is the name of the creation
228
        routine of the hash table type your hash table is derived
229
        from.
230
 
231
EXAMPLE
232
 
233
.struct bfd_hash_entry *
234
.@var{function_name} (struct bfd_hash_entry *entry,
235
.                     struct bfd_hash_table *table,
236
.                     const char *string)
237
.{
238
.  struct @var{entry_type} *ret = (@var{entry_type} *) entry;
239
.
240
. {* Allocate the structure if it has not already been allocated by a
241
.    derived class.  *}
242
.  if (ret == NULL)
243
.    {
244
.      ret = bfd_hash_allocate (table, sizeof (* ret));
245
.      if (ret == NULL)
246
.        return NULL;
247
.    }
248
.
249
. {* Call the allocation method of the base class.  *}
250
.  ret = ((@var{entry_type} *)
251
.        @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string));
252
.
253
. {* Initialize the local fields here.  *}
254
.
255
.  return (struct bfd_hash_entry *) ret;
256
.}
257
 
258
DESCRIPTION
259
        The creation routine for the linker hash table, which is in
260
        <<linker.c>>, looks just like this example.
261
        @var{function_name} is <<_bfd_link_hash_newfunc>>.
262
        @var{entry_type} is <<struct bfd_link_hash_entry>>.
263
        @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation
264
        routine for a basic hash table.
265
 
266
        <<_bfd_link_hash_newfunc>> also initializes the local fields
267
        in a linker hash table entry: <<type>>, <<written>> and
268
        <<next>>.
269
 
270
INODE
271
Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type
272
SUBSUBSECTION
273
        Write other derived routines
274
 
275
        You will want to write other routines for your new hash table,
276
        as well.
277
 
278
        You will want an initialization routine which calls the
279
        initialization routine of the hash table you are deriving from
280
        and initializes any other local fields.  For the linker hash
281
        table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>.
282
 
283
        You will want a lookup routine which calls the lookup routine
284
        of the hash table you are deriving from and casts the result.
285
        The linker hash table uses <<bfd_link_hash_lookup>> in
286
        <<linker.c>> (this actually takes an additional argument which
287
        it uses to decide how to return the looked up value).
288
 
289
        You may want a traversal routine.  This should just call the
290
        traversal routine of the hash table you are deriving from with
291
        appropriate casts.  The linker hash table uses
292
        <<bfd_link_hash_traverse>> in <<linker.c>>.
293
 
294
        These routines may simply be defined as macros.  For example,
295
        the a.out backend linker hash table, which is derived from the
296
        linker hash table, uses macros for the lookup and traversal
297
        routines.  These are <<aout_link_hash_lookup>> and
298
        <<aout_link_hash_traverse>> in aoutx.h.
299
*/
300
 
301
/* The default number of entries to use when creating a hash table.  */
302
#define DEFAULT_SIZE 4051
303
 
304
/* The following function returns a nearest prime number which is
305
   greater than N, and near a power of two.  Copied from libiberty.
306
   Returns zero for ridiculously large N to signify an error.  */
307
 
308
static unsigned long
309
higher_prime_number (unsigned long n)
310
{
311
  /* These are primes that are near, but slightly smaller than, a
312
     power of two.  */
313
  static const unsigned long primes[] =
314
    {
315
      (unsigned long) 31,
316
      (unsigned long) 61,
317
      (unsigned long) 127,
318
      (unsigned long) 251,
319
      (unsigned long) 509,
320
      (unsigned long) 1021,
321
      (unsigned long) 2039,
322
      (unsigned long) 4093,
323
      (unsigned long) 8191,
324
      (unsigned long) 16381,
325
      (unsigned long) 32749,
326
      (unsigned long) 65521,
327
      (unsigned long) 131071,
328
      (unsigned long) 262139,
329
      (unsigned long) 524287,
330
      (unsigned long) 1048573,
331
      (unsigned long) 2097143,
332
      (unsigned long) 4194301,
333
      (unsigned long) 8388593,
334
      (unsigned long) 16777213,
335
      (unsigned long) 33554393,
336
      (unsigned long) 67108859,
337
      (unsigned long) 134217689,
338
      (unsigned long) 268435399,
339
      (unsigned long) 536870909,
340
      (unsigned long) 1073741789,
341
      (unsigned long) 2147483647,
342
                                        /* 4294967291L */
343
      ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
344
  };
345
 
346
  const unsigned long *low = &primes[0];
347
  const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])];
348
 
349
  while (low != high)
350
    {
351
      const unsigned long *mid = low + (high - low) / 2;
352
      if (n >= *mid)
353
        low = mid + 1;
354
      else
355
        high = mid;
356
    }
357
 
358
  if (n >= *low)
359
    return 0;
360
 
361
  return *low;
362
}
363
 
364
static unsigned long bfd_default_hash_table_size = DEFAULT_SIZE;
365
 
366
/* Create a new hash table, given a number of entries.  */
367
 
368
bfd_boolean
369
bfd_hash_table_init_n (struct bfd_hash_table *table,
370
                       struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
371
                                                          struct bfd_hash_table *,
372
                                                          const char *),
373
                       unsigned int entsize,
374
                       unsigned int size)
375
{
376
  unsigned long alloc;
377
 
378
  alloc = size;
379
  alloc *= sizeof (struct bfd_hash_entry *);
380
  if (alloc / sizeof (struct bfd_hash_entry *) != size)
381
    {
382
      bfd_set_error (bfd_error_no_memory);
383
      return FALSE;
384
    }
385
 
386
  table->memory = (void *) objalloc_create ();
387
  if (table->memory == NULL)
388
    {
389
      bfd_set_error (bfd_error_no_memory);
390
      return FALSE;
391
    }
392
  table->table = (struct bfd_hash_entry **)
393
      objalloc_alloc ((struct objalloc *) table->memory, alloc);
394
  if (table->table == NULL)
395
    {
396
      bfd_set_error (bfd_error_no_memory);
397
      return FALSE;
398
    }
399
  memset ((void *) table->table, 0, alloc);
400
  table->size = size;
401
  table->entsize = entsize;
402
  table->count = 0;
403
  table->frozen = 0;
404
  table->newfunc = newfunc;
405
  return TRUE;
406
}
407
 
408
/* Create a new hash table with the default number of entries.  */
409
 
410
bfd_boolean
411
bfd_hash_table_init (struct bfd_hash_table *table,
412
                     struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
413
                                                        struct bfd_hash_table *,
414
                                                        const char *),
415
                     unsigned int entsize)
416
{
417
  return bfd_hash_table_init_n (table, newfunc, entsize,
418
                                bfd_default_hash_table_size);
419
}
420
 
421
/* Free a hash table.  */
422
 
423
void
424
bfd_hash_table_free (struct bfd_hash_table *table)
425
{
426
  objalloc_free ((struct objalloc *) table->memory);
427
  table->memory = NULL;
428
}
429
 
430
static inline unsigned long
431
bfd_hash_hash (const char *string, unsigned int *lenp)
432
{
433
  const unsigned char *s;
434
  unsigned long hash;
435
  unsigned int len;
436
  unsigned int c;
437
 
438
  hash = 0;
439
  len = 0;
440
  s = (const unsigned char *) string;
441
  while ((c = *s++) != '\0')
442
    {
443
      hash += c + (c << 17);
444
      hash ^= hash >> 2;
445
    }
446
  len = (s - (const unsigned char *) string) - 1;
447
  hash += len + (len << 17);
448
  hash ^= hash >> 2;
449
  if (lenp != NULL)
450
    *lenp = len;
451
  return hash;
452
}
453
 
454
/* Look up a string in a hash table.  */
455
 
456
struct bfd_hash_entry *
457
bfd_hash_lookup (struct bfd_hash_table *table,
458
                 const char *string,
459
                 bfd_boolean create,
460
                 bfd_boolean copy)
461
{
462
  unsigned long hash;
463
  struct bfd_hash_entry *hashp;
464
  unsigned int len;
465
  unsigned int _index;
466
 
467
  hash = bfd_hash_hash (string, &len);
468
  _index = hash % table->size;
469
  for (hashp = table->table[_index];
470
       hashp != NULL;
471
       hashp = hashp->next)
472
    {
473
      if (hashp->hash == hash
474
          && strcmp (hashp->string, string) == 0)
475
        return hashp;
476
    }
477
 
478
  if (! create)
479
    return NULL;
480
 
481
  if (copy)
482
    {
483
      char *new_string;
484
 
485
      new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory,
486
                                            len + 1);
487
      if (!new_string)
488
        {
489
          bfd_set_error (bfd_error_no_memory);
490
          return NULL;
491
        }
492
      memcpy (new_string, string, len + 1);
493
      string = new_string;
494
    }
495
 
496
  return bfd_hash_insert (table, string, hash);
497
}
498
 
499
/* Insert an entry in a hash table.  */
500
 
501
struct bfd_hash_entry *
502
bfd_hash_insert (struct bfd_hash_table *table,
503
                 const char *string,
504
                 unsigned long hash)
505
{
506
  struct bfd_hash_entry *hashp;
507
  unsigned int _index;
508
 
509
  hashp = (*table->newfunc) (NULL, table, string);
510
  if (hashp == NULL)
511
    return NULL;
512
  hashp->string = string;
513
  hashp->hash = hash;
514
  _index = hash % table->size;
515
  hashp->next = table->table[_index];
516
  table->table[_index] = hashp;
517
  table->count++;
518
 
519
  if (!table->frozen && table->count > table->size * 3 / 4)
520
    {
521
      unsigned long newsize = higher_prime_number (table->size);
522
      struct bfd_hash_entry **newtable;
523
      unsigned int hi;
524
      unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *);
525
 
526
      /* If we can't find a higher prime, or we can't possibly alloc
527
         that much memory, don't try to grow the table.  */
528
      if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize)
529
        {
530
          table->frozen = 1;
531
          return hashp;
532
        }
533
 
534
      newtable = ((struct bfd_hash_entry **)
535
                  objalloc_alloc ((struct objalloc *) table->memory, alloc));
536
      if (newtable == NULL)
537
        {
538
          table->frozen = 1;
539
          return hashp;
540
        }
541
      memset ((PTR) newtable, 0, alloc);
542
 
543
      for (hi = 0; hi < table->size; hi ++)
544
        while (table->table[hi])
545
          {
546
            struct bfd_hash_entry *chain = table->table[hi];
547
            struct bfd_hash_entry *chain_end = chain;
548
 
549
            while (chain_end->next && chain_end->next->hash == chain->hash)
550
              chain_end = chain_end->next;
551
 
552
            table->table[hi] = chain_end->next;
553
            _index = chain->hash % newsize;
554
            chain_end->next = newtable[_index];
555
            newtable[_index] = chain;
556
          }
557
      table->table = newtable;
558
      table->size = newsize;
559
    }
560
 
561
  return hashp;
562
}
563
 
564
/* Rename an entry in a hash table.  */
565
 
566
void
567
bfd_hash_rename (struct bfd_hash_table *table,
568
                 const char *string,
569
                 struct bfd_hash_entry *ent)
570
{
571
  unsigned int _index;
572
  struct bfd_hash_entry **pph;
573
 
574
  _index = ent->hash % table->size;
575
  for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next)
576
    if (*pph == ent)
577
      break;
578
  if (*pph == NULL)
579
    abort ();
580
 
581
  *pph = ent->next;
582
  ent->string = string;
583
  ent->hash = bfd_hash_hash (string, NULL);
584
  _index = ent->hash % table->size;
585
  ent->next = table->table[_index];
586
  table->table[_index] = ent;
587
}
588
 
589
/* Replace an entry in a hash table.  */
590
 
591
void
592
bfd_hash_replace (struct bfd_hash_table *table,
593
                  struct bfd_hash_entry *old,
594
                  struct bfd_hash_entry *nw)
595
{
596
  unsigned int _index;
597
  struct bfd_hash_entry **pph;
598
 
599
  _index = old->hash % table->size;
600
  for (pph = &table->table[_index];
601
       (*pph) != NULL;
602
       pph = &(*pph)->next)
603
    {
604
      if (*pph == old)
605
        {
606
          *pph = nw;
607
          return;
608
        }
609
    }
610
 
611
  abort ();
612
}
613
 
614
/* Allocate space in a hash table.  */
615
 
616
void *
617
bfd_hash_allocate (struct bfd_hash_table *table,
618
                   unsigned int size)
619
{
620
  void * ret;
621
 
622
  ret = objalloc_alloc ((struct objalloc *) table->memory, size);
623
  if (ret == NULL && size != 0)
624
    bfd_set_error (bfd_error_no_memory);
625
  return ret;
626
}
627
 
628
/* Base method for creating a new hash table entry.  */
629
 
630
struct bfd_hash_entry *
631
bfd_hash_newfunc (struct bfd_hash_entry *entry,
632
                  struct bfd_hash_table *table,
633
                  const char *string ATTRIBUTE_UNUSED)
634
{
635
  if (entry == NULL)
636
    entry = (struct bfd_hash_entry *) bfd_hash_allocate (table,
637
                                                         sizeof (* entry));
638
  return entry;
639
}
640
 
641
/* Traverse a hash table.  */
642
 
643
void
644
bfd_hash_traverse (struct bfd_hash_table *table,
645
                   bfd_boolean (*func) (struct bfd_hash_entry *, void *),
646
                   void * info)
647
{
648
  unsigned int i;
649
 
650
  table->frozen = 1;
651
  for (i = 0; i < table->size; i++)
652
    {
653
      struct bfd_hash_entry *p;
654
 
655
      for (p = table->table[i]; p != NULL; p = p->next)
656
        if (! (*func) (p, info))
657
          goto out;
658
    }
659
 out:
660
  table->frozen = 0;
661
}
662
 
663
unsigned long
664
bfd_hash_set_default_size (unsigned long hash_size)
665
{
666
  /* Extend this prime list if you want more granularity of hash table size.  */
667
  static const unsigned long hash_size_primes[] =
668
    {
669
      31, 61, 127, 251, 509, 1021, 2039, 4091, 8191, 16381, 32749, 65537
670
    };
671
  unsigned int _index;
672
 
673
  /* Work out best prime number near the hash_size.  */
674
  for (_index = 0; _index < ARRAY_SIZE (hash_size_primes) - 1; ++_index)
675
    if (hash_size <= hash_size_primes[_index])
676
      break;
677
 
678
  bfd_default_hash_table_size = hash_size_primes[_index];
679
  return bfd_default_hash_table_size;
680
}
681
 
682
/* A few different object file formats (a.out, COFF, ELF) use a string
683
   table.  These functions support adding strings to a string table,
684
   returning the byte offset, and writing out the table.
685
 
686
   Possible improvements:
687
   + look for strings matching trailing substrings of other strings
688
   + better data structures?  balanced trees?
689
   + look at reducing memory use elsewhere -- maybe if we didn't have
690
     to construct the entire symbol table at once, we could get by
691
     with smaller amounts of VM?  (What effect does that have on the
692
     string table reductions?)  */
693
 
694
/* An entry in the strtab hash table.  */
695
 
696
struct strtab_hash_entry
697
{
698
  struct bfd_hash_entry root;
699
  /* Index in string table.  */
700
  bfd_size_type index;
701
  /* Next string in strtab.  */
702
  struct strtab_hash_entry *next;
703
};
704
 
705
/* The strtab hash table.  */
706
 
707
struct bfd_strtab_hash
708
{
709
  struct bfd_hash_table table;
710
  /* Size of strtab--also next available index.  */
711
  bfd_size_type size;
712
  /* First string in strtab.  */
713
  struct strtab_hash_entry *first;
714
  /* Last string in strtab.  */
715
  struct strtab_hash_entry *last;
716
  /* Whether to precede strings with a two byte length, as in the
717
     XCOFF .debug section.  */
718
  bfd_boolean xcoff;
719
};
720
 
721
/* Routine to create an entry in a strtab.  */
722
 
723
static struct bfd_hash_entry *
724
strtab_hash_newfunc (struct bfd_hash_entry *entry,
725
                     struct bfd_hash_table *table,
726
                     const char *string)
727
{
728
  struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;
729
 
730
  /* Allocate the structure if it has not already been allocated by a
731
     subclass.  */
732
  if (ret == NULL)
733
    ret = (struct strtab_hash_entry *) bfd_hash_allocate (table,
734
                                                          sizeof (* ret));
735
  if (ret == NULL)
736
    return NULL;
737
 
738
  /* Call the allocation method of the superclass.  */
739
  ret = (struct strtab_hash_entry *)
740
         bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
741
 
742
  if (ret)
743
    {
744
      /* Initialize the local fields.  */
745
      ret->index = (bfd_size_type) -1;
746
      ret->next = NULL;
747
    }
748
 
749
  return (struct bfd_hash_entry *) ret;
750
}
751
 
752
/* Look up an entry in an strtab.  */
753
 
754
#define strtab_hash_lookup(t, string, create, copy) \
755
  ((struct strtab_hash_entry *) \
756
   bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
757
 
758
/* Create a new strtab.  */
759
 
760
struct bfd_strtab_hash *
761
_bfd_stringtab_init (void)
762
{
763
  struct bfd_strtab_hash *table;
764
  bfd_size_type amt = sizeof (* table);
765
 
766
  table = (struct bfd_strtab_hash *) bfd_malloc (amt);
767
  if (table == NULL)
768
    return NULL;
769
 
770
  if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
771
                            sizeof (struct strtab_hash_entry)))
772
    {
773
      free (table);
774
      return NULL;
775
    }
776
 
777
  table->size = 0;
778
  table->first = NULL;
779
  table->last = NULL;
780
  table->xcoff = FALSE;
781
 
782
  return table;
783
}
784
 
785
/* Create a new strtab in which the strings are output in the format
786
   used in the XCOFF .debug section: a two byte length precedes each
787
   string.  */
788
 
789
struct bfd_strtab_hash *
790
_bfd_xcoff_stringtab_init (void)
791
{
792
  struct bfd_strtab_hash *ret;
793
 
794
  ret = _bfd_stringtab_init ();
795
  if (ret != NULL)
796
    ret->xcoff = TRUE;
797
  return ret;
798
}
799
 
800
/* Free a strtab.  */
801
 
802
void
803
_bfd_stringtab_free (struct bfd_strtab_hash *table)
804
{
805
  bfd_hash_table_free (&table->table);
806
  free (table);
807
}
808
 
809
/* Get the index of a string in a strtab, adding it if it is not
810
   already present.  If HASH is FALSE, we don't really use the hash
811
   table, and we don't eliminate duplicate strings.  */
812
 
813
bfd_size_type
814
_bfd_stringtab_add (struct bfd_strtab_hash *tab,
815
                    const char *str,
816
                    bfd_boolean hash,
817
                    bfd_boolean copy)
818
{
819
  struct strtab_hash_entry *entry;
820
 
821
  if (hash)
822
    {
823
      entry = strtab_hash_lookup (tab, str, TRUE, copy);
824
      if (entry == NULL)
825
        return (bfd_size_type) -1;
826
    }
827
  else
828
    {
829
      entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table,
830
                                                              sizeof (* entry));
831
      if (entry == NULL)
832
        return (bfd_size_type) -1;
833
      if (! copy)
834
        entry->root.string = str;
835
      else
836
        {
837
          char *n;
838
 
839
          n = (char *) bfd_hash_allocate (&tab->table, strlen (str) + 1);
840
          if (n == NULL)
841
            return (bfd_size_type) -1;
842
          entry->root.string = n;
843
        }
844
      entry->index = (bfd_size_type) -1;
845
      entry->next = NULL;
846
    }
847
 
848
  if (entry->index == (bfd_size_type) -1)
849
    {
850
      entry->index = tab->size;
851
      tab->size += strlen (str) + 1;
852
      if (tab->xcoff)
853
        {
854
          entry->index += 2;
855
          tab->size += 2;
856
        }
857
      if (tab->first == NULL)
858
        tab->first = entry;
859
      else
860
        tab->last->next = entry;
861
      tab->last = entry;
862
    }
863
 
864
  return entry->index;
865
}
866
 
867
/* Get the number of bytes in a strtab.  */
868
 
869
bfd_size_type
870
_bfd_stringtab_size (struct bfd_strtab_hash *tab)
871
{
872
  return tab->size;
873
}
874
 
875
/* Write out a strtab.  ABFD must already be at the right location in
876
   the file.  */
877
 
878
bfd_boolean
879
_bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab)
880
{
881
  bfd_boolean xcoff;
882
  struct strtab_hash_entry *entry;
883
 
884
  xcoff = tab->xcoff;
885
 
886
  for (entry = tab->first; entry != NULL; entry = entry->next)
887
    {
888
      const char *str;
889
      size_t len;
890
 
891
      str = entry->root.string;
892
      len = strlen (str) + 1;
893
 
894
      if (xcoff)
895
        {
896
          bfd_byte buf[2];
897
 
898
          /* The output length includes the null byte.  */
899
          bfd_put_16 (abfd, (bfd_vma) len, buf);
900
          if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2)
901
            return FALSE;
902
        }
903
 
904
      if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len)
905
        return FALSE;
906
    }
907
 
908
  return TRUE;
909
}

powered by: WebSVN 2.1.0

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