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/* 29SECTION 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 59INODE 60Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables 61SUBSECTION 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 95INODE 96Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables 97SUBSECTION 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 125INODE 126Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables 127SUBSECTION 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 144INODE 145Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables 146SUBSECTION 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 173INODE 174Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type 175SUBSUBSECTION 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 196INODE 197Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type 198SUBSUBSECTION 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 230EXAMPLE 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 257DESCRIPTION 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 269INODE 270Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type 271SUBSUBSECTION 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 307static unsigned long 308higher_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 363static unsigned long bfd_default_hash_table_size = DEFAULT_SIZE; 364 365/* Create a new hash table, given a number of entries. */ 366 367bfd_boolean 368bfd_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 410bfd_boolean 411bfd_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 423void 424bfd_hash_table_free (struct bfd_hash_table *table) 425{ 426 objalloc_free ((struct objalloc *) table->memory); 427 table->memory = NULL; 428} 429 430static inline unsigned long 431bfd_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 457struct bfd_hash_entry * 458bfd_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 502struct bfd_hash_entry * 503bfd_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 567void 568bfd_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 592void 593bfd_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 617void * 618bfd_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 631struct bfd_hash_entry * 632bfd_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 644void 645bfd_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 664unsigned long 665bfd_hash_set_default_size (unsigned long hash_size) 666{ 667 /* These silly_size values result in around 1G and 32M of memory 668 being allocated for the table of pointers. Note that the number 669 of elements allocated will be almost twice the size of any power 670 of two chosen here. */ 671 unsigned long silly_size = sizeof (size_t) > 4 ? 0x4000000 : 0x400000; 672 if (hash_size > silly_size) 673 hash_size = silly_size; 674 else if (hash_size != 0) 675 hash_size--; 676 hash_size = higher_prime_number (hash_size); 677 BFD_ASSERT (hash_size != 0); 678 bfd_default_hash_table_size = hash_size; 679 return bfd_default_hash_table_size; 680} 681 682/* A few different object file formats (a.out, COFF, ELF) use a string 683 table. These functions support adding strings to a string table, 684 returning the byte offset, and writing out the table. 685 686 Possible improvements: 687 + look for strings matching trailing substrings of other strings 688 + better data structures? balanced trees? 689 + look at reducing memory use elsewhere -- maybe if we didn't have 690 to construct the entire symbol table at once, we could get by 691 with smaller amounts of VM? (What effect does that have on the 692 string table reductions?) */ 693 694/* An entry in the strtab hash table. */ 695 696struct strtab_hash_entry 697{ 698 struct bfd_hash_entry root; 699 /* Index in string table. */ 700 bfd_size_type index; 701 /* Next string in strtab. */ 702 struct strtab_hash_entry *next; 703}; 704 705/* The strtab hash table. */ 706 707struct bfd_strtab_hash 708{ 709 struct bfd_hash_table table; 710 /* Size of strtab--also next available index. */ 711 bfd_size_type size; 712 /* First string in strtab. */ 713 struct strtab_hash_entry *first; 714 /* Last string in strtab. */ 715 struct strtab_hash_entry *last; 716 /* Whether to precede strings with a two byte length, as in the 717 XCOFF .debug section. */ 718 bfd_boolean xcoff; 719}; 720 721/* Routine to create an entry in a strtab. */ 722 723static struct bfd_hash_entry * 724strtab_hash_newfunc (struct bfd_hash_entry *entry, 725 struct bfd_hash_table *table, 726 const char *string) 727{ 728 struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry; 729 730 /* Allocate the structure if it has not already been allocated by a 731 subclass. */ 732 if (ret == NULL) 733 ret = (struct strtab_hash_entry *) bfd_hash_allocate (table, 734 sizeof (* ret)); 735 if (ret == NULL) 736 return NULL; 737 738 /* Call the allocation method of the superclass. */ 739 ret = (struct strtab_hash_entry *) 740 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string); 741 742 if (ret) 743 { 744 /* Initialize the local fields. */ 745 ret->index = (bfd_size_type) -1; 746 ret->next = NULL; 747 } 748 749 return (struct bfd_hash_entry *) ret; 750} 751 752/* Look up an entry in an strtab. */ 753 754#define strtab_hash_lookup(t, string, create, copy) \ 755 ((struct strtab_hash_entry *) \ 756 bfd_hash_lookup (&(t)->table, (string), (create), (copy))) 757 758/* Create a new strtab. */ 759 760struct bfd_strtab_hash * 761_bfd_stringtab_init (void) 762{ 763 struct bfd_strtab_hash *table; 764 size_t amt = sizeof (* table); 765 766 table = (struct bfd_strtab_hash *) bfd_malloc (amt); 767 if (table == NULL) 768 return NULL; 769 770 if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc, 771 sizeof (struct strtab_hash_entry))) 772 { 773 free (table); 774 return NULL; 775 } 776 777 table->size = 0; 778 table->first = NULL; 779 table->last = NULL; 780 table->xcoff = FALSE; 781 782 return table; 783} 784 785/* Create a new strtab in which the strings are output in the format 786 used in the XCOFF .debug section: a two byte length precedes each 787 string. */ 788 789struct bfd_strtab_hash * 790_bfd_xcoff_stringtab_init (void) 791{ 792 struct bfd_strtab_hash *ret; 793 794 ret = _bfd_stringtab_init (); 795 if (ret != NULL) 796 ret->xcoff = TRUE; 797 return ret; 798} 799 800/* Free a strtab. */ 801 802void 803_bfd_stringtab_free (struct bfd_strtab_hash *table) 804{ 805 bfd_hash_table_free (&table->table); 806 free (table); 807} 808 809/* Get the index of a string in a strtab, adding it if it is not 810 already present. If HASH is FALSE, we don't really use the hash 811 table, and we don't eliminate duplicate strings. If COPY is true 812 then store a copy of STR if creating a new entry. */ 813 814bfd_size_type 815_bfd_stringtab_add (struct bfd_strtab_hash *tab, 816 const char *str, 817 bfd_boolean hash, 818 bfd_boolean copy) 819{ 820 struct strtab_hash_entry *entry; 821 822 if (hash) 823 { 824 entry = strtab_hash_lookup (tab, str, TRUE, copy); 825 if (entry == NULL) 826 return (bfd_size_type) -1; 827 } 828 else 829 { 830 entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table, 831 sizeof (* entry)); 832 if (entry == NULL) 833 return (bfd_size_type) -1; 834 if (! copy) 835 entry->root.string = str; 836 else 837 { 838 size_t len = strlen (str) + 1; 839 char *n; 840 841 n = (char *) bfd_hash_allocate (&tab->table, len); 842 if (n == NULL) 843 return (bfd_size_type) -1; 844 memcpy (n, str, len); 845 entry->root.string = n; 846 } 847 entry->index = (bfd_size_type) -1; 848 entry->next = NULL; 849 } 850 851 if (entry->index == (bfd_size_type) -1) 852 { 853 entry->index = tab->size; 854 tab->size += strlen (str) + 1; 855 if (tab->xcoff) 856 { 857 entry->index += 2; 858 tab->size += 2; 859 } 860 if (tab->first == NULL) 861 tab->first = entry; 862 else 863 tab->last->next = entry; 864 tab->last = entry; 865 } 866 867 return entry->index; 868} 869 870/* Get the number of bytes in a strtab. */ 871 872bfd_size_type 873_bfd_stringtab_size (struct bfd_strtab_hash *tab) 874{ 875 return tab->size; 876} 877 878/* Write out a strtab. ABFD must already be at the right location in 879 the file. */ 880 881bfd_boolean 882_bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab) 883{ 884 bfd_boolean xcoff; 885 struct strtab_hash_entry *entry; 886 887 xcoff = tab->xcoff; 888 889 for (entry = tab->first; entry != NULL; entry = entry->next) 890 { 891 const char *str; 892 size_t len; 893 894 str = entry->root.string; 895 len = strlen (str) + 1; 896 897 if (xcoff) 898 { 899 bfd_byte buf[2]; 900 901 /* The output length includes the null byte. */ 902 bfd_put_16 (abfd, (bfd_vma) len, buf); 903 if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2) 904 return FALSE; 905 } 906 907 if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len) 908 return FALSE; 909 } 910 911 return TRUE; 912} 913