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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gdb-6.8/] [bfd/] [hash.c] - Blame information for rev 298

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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