1 /* hash.c -- hash table routines for BFD 2 Copyright (C) 1993-2014 Free Software Foundation, Inc. 3 Written by Steve Chamberlain <sac (at) cygnus.com> 4 5 This file is part of BFD, the Binary File Descriptor library. 6 7 This program is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3 of the License, or 10 (at your option) any later version. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, 20 MA 02110-1301, USA. */ 21 22 #include "sysdep.h" 23 #include "bfd.h" 24 #include "libbfd.h" 25 #include "objalloc.h" 26 #include "libiberty.h" 27 28 /* 29 SECTION 30 Hash Tables 31 32 @cindex Hash tables 33 BFD provides a simple set of hash table functions. Routines 34 are provided to initialize a hash table, to free a hash table, 35 to look up a string in a hash table and optionally create an 36 entry for it, and to traverse a hash table. There is 37 currently no routine to delete an string from a hash table. 38 39 The basic hash table does not permit any data to be stored 40 with a string. However, a hash table is designed to present a 41 base class from which other types of hash tables may be 42 derived. These derived types may store additional information 43 with the string. Hash tables were implemented in this way, 44 rather than simply providing a data pointer in a hash table 45 entry, because they were designed for use by the linker back 46 ends. The linker may create thousands of hash table entries, 47 and the overhead of allocating private data and storing and 48 following pointers becomes noticeable. 49 50 The basic hash table code is in <<hash.c>>. 51 52 @menu 53 @* Creating and Freeing a Hash Table:: 54 @* Looking Up or Entering a String:: 55 @* Traversing a Hash Table:: 56 @* Deriving a New Hash Table Type:: 57 @end menu 58 59 INODE 60 Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables 61 SUBSECTION 62 Creating and freeing a hash table 63 64 @findex bfd_hash_table_init 65 @findex bfd_hash_table_init_n 66 To create a hash table, create an instance of a <<struct 67 bfd_hash_table>> (defined in <<bfd.h>>) and call 68 <<bfd_hash_table_init>> (if you know approximately how many 69 entries you will need, the function <<bfd_hash_table_init_n>>, 70 which takes a @var{size} argument, may be used). 71 <<bfd_hash_table_init>> returns <<FALSE>> if some sort of 72 error occurs. 73 74 @findex bfd_hash_newfunc 75 The function <<bfd_hash_table_init>> take as an argument a 76 function to use to create new entries. For a basic hash 77 table, use the function <<bfd_hash_newfunc>>. @xref{Deriving 78 a New Hash Table Type}, for why you would want to use a 79 different value for this argument. 80 81 @findex bfd_hash_allocate 82 <<bfd_hash_table_init>> will create an objalloc which will be 83 used to allocate new entries. You may allocate memory on this 84 objalloc using <<bfd_hash_allocate>>. 85 86 @findex bfd_hash_table_free 87 Use <<bfd_hash_table_free>> to free up all the memory that has 88 been allocated for a hash table. This will not free up the 89 <<struct bfd_hash_table>> itself, which you must provide. 90 91 @findex bfd_hash_set_default_size 92 Use <<bfd_hash_set_default_size>> to set the default size of 93 hash table to use. 94 95 INODE 96 Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables 97 SUBSECTION 98 Looking up or entering a string 99 100 @findex bfd_hash_lookup 101 The function <<bfd_hash_lookup>> is used both to look up a 102 string in the hash table and to create a new entry. 103 104 If the @var{create} argument is <<FALSE>>, <<bfd_hash_lookup>> 105 will look up a string. If the string is found, it will 106 returns a pointer to a <<struct bfd_hash_entry>>. If the 107 string is not found in the table <<bfd_hash_lookup>> will 108 return <<NULL>>. You should not modify any of the fields in 109 the returns <<struct bfd_hash_entry>>. 110 111 If the @var{create} argument is <<TRUE>>, the string will be 112 entered into the hash table if it is not already there. 113 Either way a pointer to a <<struct bfd_hash_entry>> will be 114 returned, either to the existing structure or to a newly 115 created one. In this case, a <<NULL>> return means that an 116 error occurred. 117 118 If the @var{create} argument is <<TRUE>>, and a new entry is 119 created, the @var{copy} argument is used to decide whether to 120 copy the string onto the hash table objalloc or not. If 121 @var{copy} is passed as <<FALSE>>, you must be careful not to 122 deallocate or modify the string as long as the hash table 123 exists. 124 125 INODE 126 Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables 127 SUBSECTION 128 Traversing a hash table 129 130 @findex bfd_hash_traverse 131 The function <<bfd_hash_traverse>> may be used to traverse a 132 hash table, calling a function on each element. The traversal 133 is done in a random order. 134 135 <<bfd_hash_traverse>> takes as arguments a function and a 136 generic <<void *>> pointer. The function is called with a 137 hash table entry (a <<struct bfd_hash_entry *>>) and the 138 generic pointer passed to <<bfd_hash_traverse>>. The function 139 must return a <<boolean>> value, which indicates whether to 140 continue traversing the hash table. If the function returns 141 <<FALSE>>, <<bfd_hash_traverse>> will stop the traversal and 142 return immediately. 143 144 INODE 145 Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables 146 SUBSECTION 147 Deriving a new hash table type 148 149 Many uses of hash tables want to store additional information 150 which each entry in the hash table. Some also find it 151 convenient to store additional information with the hash table 152 itself. This may be done using a derived hash table. 153 154 Since C is not an object oriented language, creating a derived 155 hash table requires sticking together some boilerplate 156 routines with a few differences specific to the type of hash 157 table you want to create. 158 159 An example of a derived hash table is the linker hash table. 160 The structures for this are defined in <<bfdlink.h>>. The 161 functions are in <<linker.c>>. 162 163 You may also derive a hash table from an already derived hash 164 table. For example, the a.out linker backend code uses a hash 165 table derived from the linker hash table. 166 167 @menu 168 @* Define the Derived Structures:: 169 @* Write the Derived Creation Routine:: 170 @* Write Other Derived Routines:: 171 @end menu 172 173 INODE 174 Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type 175 SUBSUBSECTION 176 Define the derived structures 177 178 You must define a structure for an entry in the hash table, 179 and a structure for the hash table itself. 180 181 The first field in the structure for an entry in the hash 182 table must be of the type used for an entry in the hash table 183 you are deriving from. If you are deriving from a basic hash 184 table this is <<struct bfd_hash_entry>>, which is defined in 185 <<bfd.h>>. The first field in the structure for the hash 186 table itself must be of the type of the hash table you are 187 deriving from itself. If you are deriving from a basic hash 188 table, this is <<struct bfd_hash_table>>. 189 190 For example, the linker hash table defines <<struct 191 bfd_link_hash_entry>> (in <<bfdlink.h>>). The first field, 192 <<root>>, is of type <<struct bfd_hash_entry>>. Similarly, 193 the first field in <<struct bfd_link_hash_table>>, <<table>>, 194 is of type <<struct bfd_hash_table>>. 195 196 INODE 197 Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type 198 SUBSUBSECTION 199 Write the derived creation routine 200 201 You must write a routine which will create and initialize an 202 entry in the hash table. This routine is passed as the 203 function argument to <<bfd_hash_table_init>>. 204 205 In order to permit other hash tables to be derived from the 206 hash table you are creating, this routine must be written in a 207 standard way. 208 209 The first argument to the creation routine is a pointer to a 210 hash table entry. This may be <<NULL>>, in which case the 211 routine should allocate the right amount of space. Otherwise 212 the space has already been allocated by a hash table type 213 derived from this one. 214 215 After allocating space, the creation routine must call the 216 creation routine of the hash table type it is derived from, 217 passing in a pointer to the space it just allocated. This 218 will initialize any fields used by the base hash table. 219 220 Finally the creation routine must initialize any local fields 221 for the new hash table type. 222 223 Here is a boilerplate example of a creation routine. 224 @var{function_name} is the name of the routine. 225 @var{entry_type} is the type of an entry in the hash table you 226 are creating. @var{base_newfunc} is the name of the creation 227 routine of the hash table type your hash table is derived 228 from. 229 230 EXAMPLE 231 232 .struct bfd_hash_entry * 233 .@var{function_name} (struct bfd_hash_entry *entry, 234 . struct bfd_hash_table *table, 235 . const char *string) 236 .{ 237 . struct @var{entry_type} *ret = (@var{entry_type} *) entry; 238 . 239 . {* Allocate the structure if it has not already been allocated by a 240 . derived class. *} 241 . if (ret == NULL) 242 . { 243 . ret = bfd_hash_allocate (table, sizeof (* ret)); 244 . if (ret == NULL) 245 . return NULL; 246 . } 247 . 248 . {* Call the allocation method of the base class. *} 249 . ret = ((@var{entry_type} *) 250 . @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string)); 251 . 252 . {* Initialize the local fields here. *} 253 . 254 . return (struct bfd_hash_entry *) ret; 255 .} 256 257 DESCRIPTION 258 The creation routine for the linker hash table, which is in 259 <<linker.c>>, looks just like this example. 260 @var{function_name} is <<_bfd_link_hash_newfunc>>. 261 @var{entry_type} is <<struct bfd_link_hash_entry>>. 262 @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation 263 routine for a basic hash table. 264 265 <<_bfd_link_hash_newfunc>> also initializes the local fields 266 in a linker hash table entry: <<type>>, <<written>> and 267 <<next>>. 268 269 INODE 270 Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type 271 SUBSUBSECTION 272 Write other derived routines 273 274 You will want to write other routines for your new hash table, 275 as well. 276 277 You will want an initialization routine which calls the 278 initialization routine of the hash table you are deriving from 279 and initializes any other local fields. For the linker hash 280 table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>. 281 282 You will want a lookup routine which calls the lookup routine 283 of the hash table you are deriving from and casts the result. 284 The linker hash table uses <<bfd_link_hash_lookup>> in 285 <<linker.c>> (this actually takes an additional argument which 286 it uses to decide how to return the looked up value). 287 288 You may want a traversal routine. This should just call the 289 traversal routine of the hash table you are deriving from with 290 appropriate casts. The linker hash table uses 291 <<bfd_link_hash_traverse>> in <<linker.c>>. 292 293 These routines may simply be defined as macros. For example, 294 the a.out backend linker hash table, which is derived from the 295 linker hash table, uses macros for the lookup and traversal 296 routines. These are <<aout_link_hash_lookup>> and 297 <<aout_link_hash_traverse>> in aoutx.h. 298 */ 299 300 /* The default number of entries to use when creating a hash table. */ 301 #define DEFAULT_SIZE 4051 302 303 /* The following function returns a nearest prime number which is 304 greater than N, and near a power of two. Copied from libiberty. 305 Returns zero for ridiculously large N to signify an error. */ 306 307 static unsigned long 308 higher_prime_number (unsigned long n) 309 { 310 /* These are primes that are near, but slightly smaller than, a 311 power of two. */ 312 static const unsigned long primes[] = 313 { 314 (unsigned long) 31, 315 (unsigned long) 61, 316 (unsigned long) 127, 317 (unsigned long) 251, 318 (unsigned long) 509, 319 (unsigned long) 1021, 320 (unsigned long) 2039, 321 (unsigned long) 4093, 322 (unsigned long) 8191, 323 (unsigned long) 16381, 324 (unsigned long) 32749, 325 (unsigned long) 65521, 326 (unsigned long) 131071, 327 (unsigned long) 262139, 328 (unsigned long) 524287, 329 (unsigned long) 1048573, 330 (unsigned long) 2097143, 331 (unsigned long) 4194301, 332 (unsigned long) 8388593, 333 (unsigned long) 16777213, 334 (unsigned long) 33554393, 335 (unsigned long) 67108859, 336 (unsigned long) 134217689, 337 (unsigned long) 268435399, 338 (unsigned long) 536870909, 339 (unsigned long) 1073741789, 340 (unsigned long) 2147483647, 341 /* 4294967291L */ 342 ((unsigned long) 2147483647) + ((unsigned long) 2147483644), 343 }; 344 345 const unsigned long *low = &primes[0]; 346 const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])]; 347 348 while (low != high) 349 { 350 const unsigned long *mid = low + (high - low) / 2; 351 if (n >= *mid) 352 low = mid + 1; 353 else 354 high = mid; 355 } 356 357 if (n >= *low) 358 return 0; 359 360 return *low; 361 } 362 363 static unsigned long bfd_default_hash_table_size = DEFAULT_SIZE; 364 365 /* Create a new hash table, given a number of entries. */ 366 367 bfd_boolean 368 bfd_hash_table_init_n (struct bfd_hash_table *table, 369 struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, 370 struct bfd_hash_table *, 371 const char *), 372 unsigned int entsize, 373 unsigned int size) 374 { 375 unsigned long alloc; 376 377 alloc = size; 378 alloc *= sizeof (struct bfd_hash_entry *); 379 if (alloc / sizeof (struct bfd_hash_entry *) != size) 380 { 381 bfd_set_error (bfd_error_no_memory); 382 return FALSE; 383 } 384 385 table->memory = (void *) objalloc_create (); 386 if (table->memory == NULL) 387 { 388 bfd_set_error (bfd_error_no_memory); 389 return FALSE; 390 } 391 table->table = (struct bfd_hash_entry **) 392 objalloc_alloc ((struct objalloc *) table->memory, alloc); 393 if (table->table == NULL) 394 { 395 bfd_hash_table_free (table); 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 (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 665 bfd_hash_set_default_size (unsigned long hash_size) 666 { 667 /* Extend this prime list if you want more granularity of hash table size. */ 668 static const unsigned long hash_size_primes[] = 669 { 670 31, 61, 127, 251, 509, 1021, 2039, 4091, 8191, 16381, 32749, 65537 671 }; 672 unsigned int _index; 673 674 /* Work out best prime number near the hash_size. */ 675 for (_index = 0; _index < ARRAY_SIZE (hash_size_primes) - 1; ++_index) 676 if (hash_size <= hash_size_primes[_index]) 677 break; 678 679 bfd_default_hash_table_size = hash_size_primes[_index]; 680 return bfd_default_hash_table_size; 681 } 682 683 /* A few different object file formats (a.out, COFF, ELF) use a string 685 table. These functions support adding strings to a string table, 686 returning the byte offset, and writing out the table. 687 688 Possible improvements: 689 + look for strings matching trailing substrings of other strings 690 + better data structures? balanced trees? 691 + look at reducing memory use elsewhere -- maybe if we didn't have 692 to construct the entire symbol table at once, we could get by 693 with smaller amounts of VM? (What effect does that have on the 694 string table reductions?) */ 695 696 /* An entry in the strtab hash table. */ 697 698 struct strtab_hash_entry 699 { 700 struct bfd_hash_entry root; 701 /* Index in string table. */ 702 bfd_size_type index; 703 /* Next string in strtab. */ 704 struct strtab_hash_entry *next; 705 }; 706 707 /* The strtab hash table. */ 708 709 struct bfd_strtab_hash 710 { 711 struct bfd_hash_table table; 712 /* Size of strtab--also next available index. */ 713 bfd_size_type size; 714 /* First string in strtab. */ 715 struct strtab_hash_entry *first; 716 /* Last string in strtab. */ 717 struct strtab_hash_entry *last; 718 /* Whether to precede strings with a two byte length, as in the 719 XCOFF .debug section. */ 720 bfd_boolean xcoff; 721 }; 722 723 /* Routine to create an entry in a strtab. */ 724 725 static struct bfd_hash_entry * 726 strtab_hash_newfunc (struct bfd_hash_entry *entry, 727 struct bfd_hash_table *table, 728 const char *string) 729 { 730 struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry; 731 732 /* Allocate the structure if it has not already been allocated by a 733 subclass. */ 734 if (ret == NULL) 735 ret = (struct strtab_hash_entry *) bfd_hash_allocate (table, 736 sizeof (* ret)); 737 if (ret == NULL) 738 return NULL; 739 740 /* Call the allocation method of the superclass. */ 741 ret = (struct strtab_hash_entry *) 742 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string); 743 744 if (ret) 745 { 746 /* Initialize the local fields. */ 747 ret->index = (bfd_size_type) -1; 748 ret->next = NULL; 749 } 750 751 return (struct bfd_hash_entry *) ret; 752 } 753 754 /* Look up an entry in an strtab. */ 755 756 #define strtab_hash_lookup(t, string, create, copy) \ 757 ((struct strtab_hash_entry *) \ 758 bfd_hash_lookup (&(t)->table, (string), (create), (copy))) 759 760 /* Create a new strtab. */ 761 762 struct bfd_strtab_hash * 763 _bfd_stringtab_init (void) 764 { 765 struct bfd_strtab_hash *table; 766 bfd_size_type amt = sizeof (* table); 767 768 table = (struct bfd_strtab_hash *) bfd_malloc (amt); 769 if (table == NULL) 770 return NULL; 771 772 if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc, 773 sizeof (struct strtab_hash_entry))) 774 { 775 free (table); 776 return NULL; 777 } 778 779 table->size = 0; 780 table->first = NULL; 781 table->last = NULL; 782 table->xcoff = FALSE; 783 784 return table; 785 } 786 787 /* Create a new strtab in which the strings are output in the format 788 used in the XCOFF .debug section: a two byte length precedes each 789 string. */ 790 791 struct bfd_strtab_hash * 792 _bfd_xcoff_stringtab_init (void) 793 { 794 struct bfd_strtab_hash *ret; 795 796 ret = _bfd_stringtab_init (); 797 if (ret != NULL) 798 ret->xcoff = TRUE; 799 return ret; 800 } 801 802 /* Free a strtab. */ 803 804 void 805 _bfd_stringtab_free (struct bfd_strtab_hash *table) 806 { 807 bfd_hash_table_free (&table->table); 808 free (table); 809 } 810 811 /* Get the index of a string in a strtab, adding it if it is not 812 already present. If HASH is FALSE, we don't really use the hash 813 table, and we don't eliminate duplicate strings. If COPY is true 814 then store a copy of STR if creating a new entry. */ 815 816 bfd_size_type 817 _bfd_stringtab_add (struct bfd_strtab_hash *tab, 818 const char *str, 819 bfd_boolean hash, 820 bfd_boolean copy) 821 { 822 struct strtab_hash_entry *entry; 823 824 if (hash) 825 { 826 entry = strtab_hash_lookup (tab, str, TRUE, copy); 827 if (entry == NULL) 828 return (bfd_size_type) -1; 829 } 830 else 831 { 832 entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table, 833 sizeof (* entry)); 834 if (entry == NULL) 835 return (bfd_size_type) -1; 836 if (! copy) 837 entry->root.string = str; 838 else 839 { 840 size_t len = strlen (str) + 1; 841 char *n; 842 843 n = (char *) bfd_hash_allocate (&tab->table, len); 844 if (n == NULL) 845 return (bfd_size_type) -1; 846 memcpy (n, str, len); 847 entry->root.string = n; 848 } 849 entry->index = (bfd_size_type) -1; 850 entry->next = NULL; 851 } 852 853 if (entry->index == (bfd_size_type) -1) 854 { 855 entry->index = tab->size; 856 tab->size += strlen (str) + 1; 857 if (tab->xcoff) 858 { 859 entry->index += 2; 860 tab->size += 2; 861 } 862 if (tab->first == NULL) 863 tab->first = entry; 864 else 865 tab->last->next = entry; 866 tab->last = entry; 867 } 868 869 return entry->index; 870 } 871 872 /* Get the number of bytes in a strtab. */ 873 874 bfd_size_type 875 _bfd_stringtab_size (struct bfd_strtab_hash *tab) 876 { 877 return tab->size; 878 } 879 880 /* Write out a strtab. ABFD must already be at the right location in 881 the file. */ 882 883 bfd_boolean 884 _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab) 885 { 886 bfd_boolean xcoff; 887 struct strtab_hash_entry *entry; 888 889 xcoff = tab->xcoff; 890 891 for (entry = tab->first; entry != NULL; entry = entry->next) 892 { 893 const char *str; 894 size_t len; 895 896 str = entry->root.string; 897 len = strlen (str) + 1; 898 899 if (xcoff) 900 { 901 bfd_byte buf[2]; 902 903 /* The output length includes the null byte. */ 904 bfd_put_16 (abfd, (bfd_vma) len, buf); 905 if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2) 906 return FALSE; 907 } 908 909 if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len) 910 return FALSE; 911 } 912 913 return TRUE; 914 } 915