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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [binutils-2.18.50/] [bfd/] [hash.c] - Blame information for rev 156

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* hash.c -- hash table routines for BFD
2
   Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005,
3
   2006, 2007 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
    (unsigned long) 127,
315
    (unsigned long) 2039,
316
    (unsigned long) 32749,
317
    (unsigned long) 65521,
318
    (unsigned long) 131071,
319
    (unsigned long) 262139,
320
    (unsigned long) 524287,
321
    (unsigned long) 1048573,
322
    (unsigned long) 2097143,
323
    (unsigned long) 4194301,
324
    (unsigned long) 8388593,
325
    (unsigned long) 16777213,
326
    (unsigned long) 33554393,
327
    (unsigned long) 67108859,
328
    (unsigned long) 134217689,
329
    (unsigned long) 268435399,
330
    (unsigned long) 536870909,
331
    (unsigned long) 1073741789,
332
    (unsigned long) 2147483647,
333
                                        /* 4294967291L */
334
    ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
335
  };
336
 
337
  const unsigned long *low = &primes[0];
338
  const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])];
339
 
340
  while (low != high)
341
    {
342
      const unsigned long *mid = low + (high - low) / 2;
343
      if (n >= *mid)
344
        low = mid + 1;
345
      else
346
        high = mid;
347
    }
348
 
349
  if (n >= *low)
350
    return 0;
351
 
352
  return *low;
353
}
354
 
355
static size_t bfd_default_hash_table_size = DEFAULT_SIZE;
356
 
357
/* Create a new hash table, given a number of entries.  */
358
 
359
bfd_boolean
360
bfd_hash_table_init_n (struct bfd_hash_table *table,
361
                       struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
362
                                                          struct bfd_hash_table *,
363
                                                          const char *),
364
                       unsigned int entsize,
365
                       unsigned int size)
366
{
367
  unsigned int alloc;
368
 
369
  alloc = size * sizeof (struct bfd_hash_entry *);
370
 
371
  table->memory = (void *) objalloc_create ();
372
  if (table->memory == NULL)
373
    {
374
      bfd_set_error (bfd_error_no_memory);
375
      return FALSE;
376
    }
377
  table->table = objalloc_alloc ((struct objalloc *) table->memory, alloc);
378
  if (table->table == NULL)
379
    {
380
      bfd_set_error (bfd_error_no_memory);
381
      return FALSE;
382
    }
383
  memset ((void *) table->table, 0, alloc);
384
  table->size = size;
385
  table->entsize = entsize;
386
  table->count = 0;
387
  table->frozen = 0;
388
  table->newfunc = newfunc;
389
  return TRUE;
390
}
391
 
392
/* Create a new hash table with the default number of entries.  */
393
 
394
bfd_boolean
395
bfd_hash_table_init (struct bfd_hash_table *table,
396
                     struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *,
397
                                                        struct bfd_hash_table *,
398
                                                        const char *),
399
                     unsigned int entsize)
400
{
401
  return bfd_hash_table_init_n (table, newfunc, entsize,
402
                                bfd_default_hash_table_size);
403
}
404
 
405
/* Free a hash table.  */
406
 
407
void
408
bfd_hash_table_free (struct bfd_hash_table *table)
409
{
410
  objalloc_free (table->memory);
411
  table->memory = NULL;
412
}
413
 
414
/* Look up a string in a hash table.  */
415
 
416
struct bfd_hash_entry *
417
bfd_hash_lookup (struct bfd_hash_table *table,
418
                 const char *string,
419
                 bfd_boolean create,
420
                 bfd_boolean copy)
421
{
422
  const unsigned char *s;
423
  unsigned long hash;
424
  unsigned int c;
425
  struct bfd_hash_entry *hashp;
426
  unsigned int len;
427
  unsigned int index;
428
 
429
  hash = 0;
430
  len = 0;
431
  s = (const unsigned char *) string;
432
  while ((c = *s++) != '\0')
433
    {
434
      hash += c + (c << 17);
435
      hash ^= hash >> 2;
436
    }
437
  len = (s - (const unsigned char *) string) - 1;
438
  hash += len + (len << 17);
439
  hash ^= hash >> 2;
440
 
441
  index = hash % table->size;
442
  for (hashp = table->table[index];
443
       hashp != NULL;
444
       hashp = hashp->next)
445
    {
446
      if (hashp->hash == hash
447
          && strcmp (hashp->string, string) == 0)
448
        return hashp;
449
    }
450
 
451
  if (! create)
452
    return NULL;
453
 
454
  if (copy)
455
    {
456
      char *new;
457
 
458
      new = objalloc_alloc ((struct objalloc *) table->memory, len + 1);
459
      if (!new)
460
        {
461
          bfd_set_error (bfd_error_no_memory);
462
          return NULL;
463
        }
464
      memcpy (new, string, len + 1);
465
      string = new;
466
    }
467
 
468
  return bfd_hash_insert (table, string, hash);
469
}
470
 
471
/* Insert an entry in a hash table.  */
472
 
473
struct bfd_hash_entry *
474
bfd_hash_insert (struct bfd_hash_table *table,
475
                 const char *string,
476
                 unsigned long hash)
477
{
478
  struct bfd_hash_entry *hashp;
479
  unsigned int index;
480
 
481
  hashp = (*table->newfunc) (NULL, table, string);
482
  if (hashp == NULL)
483
    return NULL;
484
  hashp->string = string;
485
  hashp->hash = hash;
486
  index = hash % table->size;
487
  hashp->next = table->table[index];
488
  table->table[index] = hashp;
489
  table->count++;
490
 
491
  if (!table->frozen && table->count > table->size * 3 / 4)
492
    {
493
      unsigned long newsize = higher_prime_number (table->size);
494
      struct bfd_hash_entry **newtable;
495
      unsigned int hi;
496
      unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *);
497
 
498
      /* If we can't find a higher prime, or we can't possibly alloc
499
         that much memory, don't try to grow the table.  */
500
      if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize)
501
        {
502
          table->frozen = 1;
503
          return hashp;
504
        }
505
 
506
      newtable = ((struct bfd_hash_entry **)
507
                  objalloc_alloc ((struct objalloc *) table->memory, alloc));
508
      if (newtable == NULL)
509
        {
510
          table->frozen = 1;
511
          return hashp;
512
        }
513
      memset ((PTR) newtable, 0, alloc);
514
 
515
      for (hi = 0; hi < table->size; hi ++)
516
        while (table->table[hi])
517
          {
518
            struct bfd_hash_entry *chain = table->table[hi];
519
            struct bfd_hash_entry *chain_end = chain;
520
 
521
            while (chain_end->next && chain_end->next->hash == chain->hash)
522
              chain_end = chain_end->next;
523
 
524
            table->table[hi] = chain_end->next;
525
            index = chain->hash % newsize;
526
            chain_end->next = newtable[index];
527
            newtable[index] = chain;
528
          }
529
      table->table = newtable;
530
      table->size = newsize;
531
    }
532
 
533
  return hashp;
534
}
535
 
536
/* Replace an entry in a hash table.  */
537
 
538
void
539
bfd_hash_replace (struct bfd_hash_table *table,
540
                  struct bfd_hash_entry *old,
541
                  struct bfd_hash_entry *nw)
542
{
543
  unsigned int index;
544
  struct bfd_hash_entry **pph;
545
 
546
  index = old->hash % table->size;
547
  for (pph = &table->table[index];
548
       (*pph) != NULL;
549
       pph = &(*pph)->next)
550
    {
551
      if (*pph == old)
552
        {
553
          *pph = nw;
554
          return;
555
        }
556
    }
557
 
558
  abort ();
559
}
560
 
561
/* Allocate space in a hash table.  */
562
 
563
void *
564
bfd_hash_allocate (struct bfd_hash_table *table,
565
                   unsigned int size)
566
{
567
  void * ret;
568
 
569
  ret = objalloc_alloc ((struct objalloc *) table->memory, size);
570
  if (ret == NULL && size != 0)
571
    bfd_set_error (bfd_error_no_memory);
572
  return ret;
573
}
574
 
575
/* Base method for creating a new hash table entry.  */
576
 
577
struct bfd_hash_entry *
578
bfd_hash_newfunc (struct bfd_hash_entry *entry,
579
                  struct bfd_hash_table *table,
580
                  const char *string ATTRIBUTE_UNUSED)
581
{
582
  if (entry == NULL)
583
    entry = bfd_hash_allocate (table, sizeof (* entry));
584
  return entry;
585
}
586
 
587
/* Traverse a hash table.  */
588
 
589
void
590
bfd_hash_traverse (struct bfd_hash_table *table,
591
                   bfd_boolean (*func) (struct bfd_hash_entry *, void *),
592
                   void * info)
593
{
594
  unsigned int i;
595
 
596
  table->frozen = 1;
597
  for (i = 0; i < table->size; i++)
598
    {
599
      struct bfd_hash_entry *p;
600
 
601
      for (p = table->table[i]; p != NULL; p = p->next)
602
        if (! (*func) (p, info))
603
          goto out;
604
    }
605
 out:
606
  table->frozen = 0;
607
}
608
 
609
void
610
bfd_hash_set_default_size (bfd_size_type hash_size)
611
{
612
  /* Extend this prime list if you want more granularity of hash table size.  */
613
  static const bfd_size_type hash_size_primes[] =
614
    {
615
      251, 509, 1021, 2039, 4051, 8599, 16699, 32749
616
    };
617
  size_t index;
618
 
619
  /* Work out best prime number near the hash_size.  */
620
  for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
621
    if (hash_size <= hash_size_primes[index])
622
      break;
623
 
624
  bfd_default_hash_table_size = hash_size_primes[index];
625
}
626
 
627
/* A few different object file formats (a.out, COFF, ELF) use a string
628
   table.  These functions support adding strings to a string table,
629
   returning the byte offset, and writing out the table.
630
 
631
   Possible improvements:
632
   + look for strings matching trailing substrings of other strings
633
   + better data structures?  balanced trees?
634
   + look at reducing memory use elsewhere -- maybe if we didn't have
635
     to construct the entire symbol table at once, we could get by
636
     with smaller amounts of VM?  (What effect does that have on the
637
     string table reductions?)  */
638
 
639
/* An entry in the strtab hash table.  */
640
 
641
struct strtab_hash_entry
642
{
643
  struct bfd_hash_entry root;
644
  /* Index in string table.  */
645
  bfd_size_type index;
646
  /* Next string in strtab.  */
647
  struct strtab_hash_entry *next;
648
};
649
 
650
/* The strtab hash table.  */
651
 
652
struct bfd_strtab_hash
653
{
654
  struct bfd_hash_table table;
655
  /* Size of strtab--also next available index.  */
656
  bfd_size_type size;
657
  /* First string in strtab.  */
658
  struct strtab_hash_entry *first;
659
  /* Last string in strtab.  */
660
  struct strtab_hash_entry *last;
661
  /* Whether to precede strings with a two byte length, as in the
662
     XCOFF .debug section.  */
663
  bfd_boolean xcoff;
664
};
665
 
666
/* Routine to create an entry in a strtab.  */
667
 
668
static struct bfd_hash_entry *
669
strtab_hash_newfunc (struct bfd_hash_entry *entry,
670
                     struct bfd_hash_table *table,
671
                     const char *string)
672
{
673
  struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry;
674
 
675
  /* Allocate the structure if it has not already been allocated by a
676
     subclass.  */
677
  if (ret == NULL)
678
    ret = bfd_hash_allocate (table, sizeof (* ret));
679
  if (ret == NULL)
680
    return NULL;
681
 
682
  /* Call the allocation method of the superclass.  */
683
  ret = (struct strtab_hash_entry *)
684
         bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
685
 
686
  if (ret)
687
    {
688
      /* Initialize the local fields.  */
689
      ret->index = (bfd_size_type) -1;
690
      ret->next = NULL;
691
    }
692
 
693
  return (struct bfd_hash_entry *) ret;
694
}
695
 
696
/* Look up an entry in an strtab.  */
697
 
698
#define strtab_hash_lookup(t, string, create, copy) \
699
  ((struct strtab_hash_entry *) \
700
   bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
701
 
702
/* Create a new strtab.  */
703
 
704
struct bfd_strtab_hash *
705
_bfd_stringtab_init (void)
706
{
707
  struct bfd_strtab_hash *table;
708
  bfd_size_type amt = sizeof (* table);
709
 
710
  table = bfd_malloc (amt);
711
  if (table == NULL)
712
    return NULL;
713
 
714
  if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
715
                            sizeof (struct strtab_hash_entry)))
716
    {
717
      free (table);
718
      return NULL;
719
    }
720
 
721
  table->size = 0;
722
  table->first = NULL;
723
  table->last = NULL;
724
  table->xcoff = FALSE;
725
 
726
  return table;
727
}
728
 
729
/* Create a new strtab in which the strings are output in the format
730
   used in the XCOFF .debug section: a two byte length precedes each
731
   string.  */
732
 
733
struct bfd_strtab_hash *
734
_bfd_xcoff_stringtab_init (void)
735
{
736
  struct bfd_strtab_hash *ret;
737
 
738
  ret = _bfd_stringtab_init ();
739
  if (ret != NULL)
740
    ret->xcoff = TRUE;
741
  return ret;
742
}
743
 
744
/* Free a strtab.  */
745
 
746
void
747
_bfd_stringtab_free (struct bfd_strtab_hash *table)
748
{
749
  bfd_hash_table_free (&table->table);
750
  free (table);
751
}
752
 
753
/* Get the index of a string in a strtab, adding it if it is not
754
   already present.  If HASH is FALSE, we don't really use the hash
755
   table, and we don't eliminate duplicate strings.  */
756
 
757
bfd_size_type
758
_bfd_stringtab_add (struct bfd_strtab_hash *tab,
759
                    const char *str,
760
                    bfd_boolean hash,
761
                    bfd_boolean copy)
762
{
763
  struct strtab_hash_entry *entry;
764
 
765
  if (hash)
766
    {
767
      entry = strtab_hash_lookup (tab, str, TRUE, copy);
768
      if (entry == NULL)
769
        return (bfd_size_type) -1;
770
    }
771
  else
772
    {
773
      entry = bfd_hash_allocate (&tab->table, sizeof (* entry));
774
      if (entry == NULL)
775
        return (bfd_size_type) -1;
776
      if (! copy)
777
        entry->root.string = str;
778
      else
779
        {
780
          char *n;
781
 
782
          n = bfd_hash_allocate (&tab->table, strlen (str) + 1);
783
          if (n == NULL)
784
            return (bfd_size_type) -1;
785
          entry->root.string = n;
786
        }
787
      entry->index = (bfd_size_type) -1;
788
      entry->next = NULL;
789
    }
790
 
791
  if (entry->index == (bfd_size_type) -1)
792
    {
793
      entry->index = tab->size;
794
      tab->size += strlen (str) + 1;
795
      if (tab->xcoff)
796
        {
797
          entry->index += 2;
798
          tab->size += 2;
799
        }
800
      if (tab->first == NULL)
801
        tab->first = entry;
802
      else
803
        tab->last->next = entry;
804
      tab->last = entry;
805
    }
806
 
807
  return entry->index;
808
}
809
 
810
/* Get the number of bytes in a strtab.  */
811
 
812
bfd_size_type
813
_bfd_stringtab_size (struct bfd_strtab_hash *tab)
814
{
815
  return tab->size;
816
}
817
 
818
/* Write out a strtab.  ABFD must already be at the right location in
819
   the file.  */
820
 
821
bfd_boolean
822
_bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab)
823
{
824
  bfd_boolean xcoff;
825
  struct strtab_hash_entry *entry;
826
 
827
  xcoff = tab->xcoff;
828
 
829
  for (entry = tab->first; entry != NULL; entry = entry->next)
830
    {
831
      const char *str;
832
      size_t len;
833
 
834
      str = entry->root.string;
835
      len = strlen (str) + 1;
836
 
837
      if (xcoff)
838
        {
839
          bfd_byte buf[2];
840
 
841
          /* The output length includes the null byte.  */
842
          bfd_put_16 (abfd, (bfd_vma) len, buf);
843
          if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2)
844
            return FALSE;
845
        }
846
 
847
      if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len)
848
        return FALSE;
849
    }
850
 
851
  return TRUE;
852
}

powered by: WebSVN 2.1.0

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