1 /* hash.c -- hash table routines for BFD 2 Copyright (C) 1993-2020 Free Software Foundation, Inc. 3 Written by Steve Chamberlain <sac@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 BFD_ASSERT (string != NULL); 439 hash = 0; 440 len = 0; 441 s = (const unsigned char *) string; 442 while ((c = *s++) != '\0') 443 { 444 hash += c + (c << 17); 445 hash ^= hash >> 2; 446 } 447 len = (s - (const unsigned char *) string) - 1; 448 hash += len + (len << 17); 449 hash ^= hash >> 2; 450 if (lenp != NULL) 451 *lenp = len; 452 return hash; 453 } 454 455 /* Look up a string in a hash table. */ 456 457 struct bfd_hash_entry * 458 bfd_hash_lookup (struct bfd_hash_table *table, 459 const char *string, 460 bfd_boolean create, 461 bfd_boolean copy) 462 { 463 unsigned long hash; 464 struct bfd_hash_entry *hashp; 465 unsigned int len; 466 unsigned int _index; 467 468 hash = bfd_hash_hash (string, &len); 469 _index = hash % table->size; 470 for (hashp = table->table[_index]; 471 hashp != NULL; 472 hashp = hashp->next) 473 { 474 if (hashp->hash == hash 475 && strcmp (hashp->string, string) == 0) 476 return hashp; 477 } 478 479 if (! create) 480 return NULL; 481 482 if (copy) 483 { 484 char *new_string; 485 486 new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory, 487 len + 1); 488 if (!new_string) 489 { 490 bfd_set_error (bfd_error_no_memory); 491 return NULL; 492 } 493 memcpy (new_string, string, len + 1); 494 string = new_string; 495 } 496 497 return bfd_hash_insert (table, string, hash); 498 } 499 500 /* Insert an entry in a hash table. */ 501 502 struct bfd_hash_entry * 503 bfd_hash_insert (struct bfd_hash_table *table, 504 const char *string, 505 unsigned long hash) 506 { 507 struct bfd_hash_entry *hashp; 508 unsigned int _index; 509 510 hashp = (*table->newfunc) (NULL, table, string); 511 if (hashp == NULL) 512 return NULL; 513 hashp->string = string; 514 hashp->hash = hash; 515 _index = hash % table->size; 516 hashp->next = table->table[_index]; 517 table->table[_index] = hashp; 518 table->count++; 519 520 if (!table->frozen && table->count > table->size * 3 / 4) 521 { 522 unsigned long newsize = higher_prime_number (table->size); 523 struct bfd_hash_entry **newtable; 524 unsigned int hi; 525 unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *); 526 527 /* If we can't find a higher prime, or we can't possibly alloc 528 that much memory, don't try to grow the table. */ 529 if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize) 530 { 531 table->frozen = 1; 532 return hashp; 533 } 534 535 newtable = ((struct bfd_hash_entry **) 536 objalloc_alloc ((struct objalloc *) table->memory, alloc)); 537 if (newtable == NULL) 538 { 539 table->frozen = 1; 540 return hashp; 541 } 542 memset (newtable, 0, alloc); 543 544 for (hi = 0; hi < table->size; hi ++) 545 while (table->table[hi]) 546 { 547 struct bfd_hash_entry *chain = table->table[hi]; 548 struct bfd_hash_entry *chain_end = chain; 549 550 while (chain_end->next && chain_end->next->hash == chain->hash) 551 chain_end = chain_end->next; 552 553 table->table[hi] = chain_end->next; 554 _index = chain->hash % newsize; 555 chain_end->next = newtable[_index]; 556 newtable[_index] = chain; 557 } 558 table->table = newtable; 559 table->size = newsize; 560 } 561 562 return hashp; 563 } 564 565 /* Rename an entry in a hash table. */ 566 567 void 568 bfd_hash_rename (struct bfd_hash_table *table, 569 const char *string, 570 struct bfd_hash_entry *ent) 571 { 572 unsigned int _index; 573 struct bfd_hash_entry **pph; 574 575 _index = ent->hash % table->size; 576 for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next) 577 if (*pph == ent) 578 break; 579 if (*pph == NULL) 580 abort (); 581 582 *pph = ent->next; 583 ent->string = string; 584 ent->hash = bfd_hash_hash (string, NULL); 585 _index = ent->hash % table->size; 586 ent->next = table->table[_index]; 587 table->table[_index] = ent; 588 } 589 590 /* Replace an entry in a hash table. */ 591 592 void 593 bfd_hash_replace (struct bfd_hash_table *table, 594 struct bfd_hash_entry *old, 595 struct bfd_hash_entry *nw) 596 { 597 unsigned int _index; 598 struct bfd_hash_entry **pph; 599 600 _index = old->hash % table->size; 601 for (pph = &table->table[_index]; 602 (*pph) != NULL; 603 pph = &(*pph)->next) 604 { 605 if (*pph == old) 606 { 607 *pph = nw; 608 return; 609 } 610 } 611 612 abort (); 613 } 614 615 /* Allocate space in a hash table. */ 616 617 void * 618 bfd_hash_allocate (struct bfd_hash_table *table, 619 unsigned int size) 620 { 621 void * ret; 622 623 ret = objalloc_alloc ((struct objalloc *) table->memory, size); 624 if (ret == NULL && size != 0) 625 bfd_set_error (bfd_error_no_memory); 626 return ret; 627 } 628 629 /* Base method for creating a new hash table entry. */ 630 631 struct bfd_hash_entry * 632 bfd_hash_newfunc (struct bfd_hash_entry *entry, 633 struct bfd_hash_table *table, 634 const char *string ATTRIBUTE_UNUSED) 635 { 636 if (entry == NULL) 637 entry = (struct bfd_hash_entry *) bfd_hash_allocate (table, 638 sizeof (* entry)); 639 return entry; 640 } 641 642 /* Traverse a hash table. */ 643 644 void 645 bfd_hash_traverse (struct bfd_hash_table *table, 646 bfd_boolean (*func) (struct bfd_hash_entry *, void *), 647 void * info) 648 { 649 unsigned int i; 650 651 table->frozen = 1; 652 for (i = 0; i < table->size; i++) 653 { 654 struct bfd_hash_entry *p; 655 656 for (p = table->table[i]; p != NULL; p = p->next) 657 if (! (*func) (p, info)) 658 goto out; 659 } 660 out: 661 table->frozen = 0; 662 } 663 664 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 684 table. These functions support adding strings to a string table, 685 returning the byte offset, and writing out the table. 686 687 Possible improvements: 688 + look for strings matching trailing substrings of other strings 689 + better data structures? balanced trees? 690 + look at reducing memory use elsewhere -- maybe if we didn't have 691 to construct the entire symbol table at once, we could get by 692 with smaller amounts of VM? (What effect does that have on the 693 string table reductions?) */ 694 695 /* An entry in the strtab hash table. */ 696 697 struct strtab_hash_entry 698 { 699 struct bfd_hash_entry root; 700 /* Index in string table. */ 701 bfd_size_type index; 702 /* Next string in strtab. */ 703 struct strtab_hash_entry *next; 704 }; 705 706 /* The strtab hash table. */ 707 708 struct bfd_strtab_hash 709 { 710 struct bfd_hash_table table; 711 /* Size of strtab--also next available index. */ 712 bfd_size_type size; 713 /* First string in strtab. */ 714 struct strtab_hash_entry *first; 715 /* Last string in strtab. */ 716 struct strtab_hash_entry *last; 717 /* Whether to precede strings with a two byte length, as in the 718 XCOFF .debug section. */ 719 bfd_boolean xcoff; 720 }; 721 722 /* Routine to create an entry in a strtab. */ 723 724 static struct bfd_hash_entry * 725 strtab_hash_newfunc (struct bfd_hash_entry *entry, 726 struct bfd_hash_table *table, 727 const char *string) 728 { 729 struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry; 730 731 /* Allocate the structure if it has not already been allocated by a 732 subclass. */ 733 if (ret == NULL) 734 ret = (struct strtab_hash_entry *) bfd_hash_allocate (table, 735 sizeof (* ret)); 736 if (ret == NULL) 737 return NULL; 738 739 /* Call the allocation method of the superclass. */ 740 ret = (struct strtab_hash_entry *) 741 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string); 742 743 if (ret) 744 { 745 /* Initialize the local fields. */ 746 ret->index = (bfd_size_type) -1; 747 ret->next = NULL; 748 } 749 750 return (struct bfd_hash_entry *) ret; 751 } 752 753 /* Look up an entry in an strtab. */ 754 755 #define strtab_hash_lookup(t, string, create, copy) \ 756 ((struct strtab_hash_entry *) \ 757 bfd_hash_lookup (&(t)->table, (string), (create), (copy))) 758 759 /* Create a new strtab. */ 760 761 struct bfd_strtab_hash * 762 _bfd_stringtab_init (void) 763 { 764 struct bfd_strtab_hash *table; 765 bfd_size_type amt = sizeof (* table); 766 767 table = (struct bfd_strtab_hash *) bfd_malloc (amt); 768 if (table == NULL) 769 return NULL; 770 771 if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc, 772 sizeof (struct strtab_hash_entry))) 773 { 774 free (table); 775 return NULL; 776 } 777 778 table->size = 0; 779 table->first = NULL; 780 table->last = NULL; 781 table->xcoff = FALSE; 782 783 return table; 784 } 785 786 /* Create a new strtab in which the strings are output in the format 787 used in the XCOFF .debug section: a two byte length precedes each 788 string. */ 789 790 struct bfd_strtab_hash * 791 _bfd_xcoff_stringtab_init (void) 792 { 793 struct bfd_strtab_hash *ret; 794 795 ret = _bfd_stringtab_init (); 796 if (ret != NULL) 797 ret->xcoff = TRUE; 798 return ret; 799 } 800 801 /* Free a strtab. */ 802 803 void 804 _bfd_stringtab_free (struct bfd_strtab_hash *table) 805 { 806 bfd_hash_table_free (&table->table); 807 free (table); 808 } 809 810 /* Get the index of a string in a strtab, adding it if it is not 811 already present. If HASH is FALSE, we don't really use the hash 812 table, and we don't eliminate duplicate strings. If COPY is true 813 then store a copy of STR if creating a new entry. */ 814 815 bfd_size_type 816 _bfd_stringtab_add (struct bfd_strtab_hash *tab, 817 const char *str, 818 bfd_boolean hash, 819 bfd_boolean copy) 820 { 821 struct strtab_hash_entry *entry; 822 823 if (hash) 824 { 825 entry = strtab_hash_lookup (tab, str, TRUE, copy); 826 if (entry == NULL) 827 return (bfd_size_type) -1; 828 } 829 else 830 { 831 entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table, 832 sizeof (* entry)); 833 if (entry == NULL) 834 return (bfd_size_type) -1; 835 if (! copy) 836 entry->root.string = str; 837 else 838 { 839 size_t len = strlen (str) + 1; 840 char *n; 841 842 n = (char *) bfd_hash_allocate (&tab->table, len); 843 if (n == NULL) 844 return (bfd_size_type) -1; 845 memcpy (n, str, len); 846 entry->root.string = n; 847 } 848 entry->index = (bfd_size_type) -1; 849 entry->next = NULL; 850 } 851 852 if (entry->index == (bfd_size_type) -1) 853 { 854 entry->index = tab->size; 855 tab->size += strlen (str) + 1; 856 if (tab->xcoff) 857 { 858 entry->index += 2; 859 tab->size += 2; 860 } 861 if (tab->first == NULL) 862 tab->first = entry; 863 else 864 tab->last->next = entry; 865 tab->last = entry; 866 } 867 868 return entry->index; 869 } 870 871 /* Get the number of bytes in a strtab. */ 872 873 bfd_size_type 874 _bfd_stringtab_size (struct bfd_strtab_hash *tab) 875 { 876 return tab->size; 877 } 878 879 /* Write out a strtab. ABFD must already be at the right location in 880 the file. */ 881 882 bfd_boolean 883 _bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab) 884 { 885 bfd_boolean xcoff; 886 struct strtab_hash_entry *entry; 887 888 xcoff = tab->xcoff; 889 890 for (entry = tab->first; entry != NULL; entry = entry->next) 891 { 892 const char *str; 893 size_t len; 894 895 str = entry->root.string; 896 len = strlen (str) + 1; 897 898 if (xcoff) 899 { 900 bfd_byte buf[2]; 901 902 /* The output length includes the null byte. */ 903 bfd_put_16 (abfd, (bfd_vma) len, buf); 904 if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2) 905 return FALSE; 906 } 907 908 if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len) 909 return FALSE; 910 } 911 912 return TRUE; 913 } 914