1 /* hash.c -- hash table routines for BFD 2 Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005, 3 2006, 2007, 2009 Free Software Foundation, Inc. 4 Written by Steve Chamberlain <sac@cygnus.com> 5 6 This file is part of BFD, the Binary File Descriptor library. 7 8 This program is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3 of the License, or 11 (at your option) any later version. 12 13 This program is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with this program; if not, write to the Free Software 20 Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, 21 MA 02110-1301, USA. */ 22 23 #include "sysdep.h" 24 #include "bfd.h" 25 #include "libbfd.h" 26 #include "objalloc.h" 27 #include "libiberty.h" 28 29 /* 30 SECTION 31 Hash Tables 32 33 @cindex Hash tables 34 BFD provides a simple set of hash table functions. Routines 35 are provided to initialize a hash table, to free a hash table, 36 to look up a string in a hash table and optionally create an 37 entry for it, and to traverse a hash table. There is 38 currently no routine to delete an string from a hash table. 39 40 The basic hash table does not permit any data to be stored 41 with a string. However, a hash table is designed to present a 42 base class from which other types of hash tables may be 43 derived. These derived types may store additional information 44 with the string. Hash tables were implemented in this way, 45 rather than simply providing a data pointer in a hash table 46 entry, because they were designed for use by the linker back 47 ends. The linker may create thousands of hash table entries, 48 and the overhead of allocating private data and storing and 49 following pointers becomes noticeable. 50 51 The basic hash table code is in <<hash.c>>. 52 53 @menu 54 @* Creating and Freeing a Hash Table:: 55 @* Looking Up or Entering a String:: 56 @* Traversing a Hash Table:: 57 @* Deriving a New Hash Table Type:: 58 @end menu 59 60 INODE 61 Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables 62 SUBSECTION 63 Creating and freeing a hash table 64 65 @findex bfd_hash_table_init 66 @findex bfd_hash_table_init_n 67 To create a hash table, create an instance of a <<struct 68 bfd_hash_table>> (defined in <<bfd.h>>) and call 69 <<bfd_hash_table_init>> (if you know approximately how many 70 entries you will need, the function <<bfd_hash_table_init_n>>, 71 which takes a @var{size} argument, may be used). 72 <<bfd_hash_table_init>> returns <<FALSE>> if some sort of 73 error occurs. 74 75 @findex bfd_hash_newfunc 76 The function <<bfd_hash_table_init>> take as an argument a 77 function to use to create new entries. For a basic hash 78 table, use the function <<bfd_hash_newfunc>>. @xref{Deriving 79 a New Hash Table Type}, for why you would want to use a 80 different value for this argument. 81 82 @findex bfd_hash_allocate 83 <<bfd_hash_table_init>> will create an objalloc which will be 84 used to allocate new entries. You may allocate memory on this 85 objalloc using <<bfd_hash_allocate>>. 86 87 @findex bfd_hash_table_free 88 Use <<bfd_hash_table_free>> to free up all the memory that has 89 been allocated for a hash table. This will not free up the 90 <<struct bfd_hash_table>> itself, which you must provide. 91 92 @findex bfd_hash_set_default_size 93 Use <<bfd_hash_set_default_size>> to set the default size of 94 hash table to use. 95 96 INODE 97 Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables 98 SUBSECTION 99 Looking up or entering a string 100 101 @findex bfd_hash_lookup 102 The function <<bfd_hash_lookup>> is used both to look up a 103 string in the hash table and to create a new entry. 104 105 If the @var{create} argument is <<FALSE>>, <<bfd_hash_lookup>> 106 will look up a string. If the string is found, it will 107 returns a pointer to a <<struct bfd_hash_entry>>. If the 108 string is not found in the table <<bfd_hash_lookup>> will 109 return <<NULL>>. You should not modify any of the fields in 110 the returns <<struct bfd_hash_entry>>. 111 112 If the @var{create} argument is <<TRUE>>, the string will be 113 entered into the hash table if it is not already there. 114 Either way a pointer to a <<struct bfd_hash_entry>> will be 115 returned, either to the existing structure or to a newly 116 created one. In this case, a <<NULL>> return means that an 117 error occurred. 118 119 If the @var{create} argument is <<TRUE>>, and a new entry is 120 created, the @var{copy} argument is used to decide whether to 121 copy the string onto the hash table objalloc or not. If 122 @var{copy} is passed as <<FALSE>>, you must be careful not to 123 deallocate or modify the string as long as the hash table 124 exists. 125 126 INODE 127 Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables 128 SUBSECTION 129 Traversing a hash table 130 131 @findex bfd_hash_traverse 132 The function <<bfd_hash_traverse>> may be used to traverse a 133 hash table, calling a function on each element. The traversal 134 is done in a random order. 135 136 <<bfd_hash_traverse>> takes as arguments a function and a 137 generic <<void *>> pointer. The function is called with a 138 hash table entry (a <<struct bfd_hash_entry *>>) and the 139 generic pointer passed to <<bfd_hash_traverse>>. The function 140 must return a <<boolean>> value, which indicates whether to 141 continue traversing the hash table. If the function returns 142 <<FALSE>>, <<bfd_hash_traverse>> will stop the traversal and 143 return immediately. 144 145 INODE 146 Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables 147 SUBSECTION 148 Deriving a new hash table type 149 150 Many uses of hash tables want to store additional information 151 which each entry in the hash table. Some also find it 152 convenient to store additional information with the hash table 153 itself. This may be done using a derived hash table. 154 155 Since C is not an object oriented language, creating a derived 156 hash table requires sticking together some boilerplate 157 routines with a few differences specific to the type of hash 158 table you want to create. 159 160 An example of a derived hash table is the linker hash table. 161 The structures for this are defined in <<bfdlink.h>>. The 162 functions are in <<linker.c>>. 163 164 You may also derive a hash table from an already derived hash 165 table. For example, the a.out linker backend code uses a hash 166 table derived from the linker hash table. 167 168 @menu 169 @* Define the Derived Structures:: 170 @* Write the Derived Creation Routine:: 171 @* Write Other Derived Routines:: 172 @end menu 173 174 INODE 175 Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type 176 SUBSUBSECTION 177 Define the derived structures 178 179 You must define a structure for an entry in the hash table, 180 and a structure for the hash table itself. 181 182 The first field in the structure for an entry in the hash 183 table must be of the type used for an entry in the hash table 184 you are deriving from. If you are deriving from a basic hash 185 table this is <<struct bfd_hash_entry>>, which is defined in 186 <<bfd.h>>. The first field in the structure for the hash 187 table itself must be of the type of the hash table you are 188 deriving from itself. If you are deriving from a basic hash 189 table, this is <<struct bfd_hash_table>>. 190 191 For example, the linker hash table defines <<struct 192 bfd_link_hash_entry>> (in <<bfdlink.h>>). The first field, 193 <<root>>, is of type <<struct bfd_hash_entry>>. Similarly, 194 the first field in <<struct bfd_link_hash_table>>, <<table>>, 195 is of type <<struct bfd_hash_table>>. 196 197 INODE 198 Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type 199 SUBSUBSECTION 200 Write the derived creation routine 201 202 You must write a routine which will create and initialize an 203 entry in the hash table. This routine is passed as the 204 function argument to <<bfd_hash_table_init>>. 205 206 In order to permit other hash tables to be derived from the 207 hash table you are creating, this routine must be written in a 208 standard way. 209 210 The first argument to the creation routine is a pointer to a 211 hash table entry. This may be <<NULL>>, in which case the 212 routine should allocate the right amount of space. Otherwise 213 the space has already been allocated by a hash table type 214 derived from this one. 215 216 After allocating space, the creation routine must call the 217 creation routine of the hash table type it is derived from, 218 passing in a pointer to the space it just allocated. This 219 will initialize any fields used by the base hash table. 220 221 Finally the creation routine must initialize any local fields 222 for the new hash table type. 223 224 Here is a boilerplate example of a creation routine. 225 @var{function_name} is the name of the routine. 226 @var{entry_type} is the type of an entry in the hash table you 227 are creating. @var{base_newfunc} is the name of the creation 228 routine of the hash table type your hash table is derived 229 from. 230 231 EXAMPLE 232 233 .struct bfd_hash_entry * 234 .@var{function_name} (struct bfd_hash_entry *entry, 235 . struct bfd_hash_table *table, 236 . const char *string) 237 .{ 238 . struct @var{entry_type} *ret = (@var{entry_type} *) entry; 239 . 240 . {* Allocate the structure if it has not already been allocated by a 241 . derived class. *} 242 . if (ret == NULL) 243 . { 244 . ret = bfd_hash_allocate (table, sizeof (* ret)); 245 . if (ret == NULL) 246 . return NULL; 247 . } 248 . 249 . {* Call the allocation method of the base class. *} 250 . ret = ((@var{entry_type} *) 251 . @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string)); 252 . 253 . {* Initialize the local fields here. *} 254 . 255 . return (struct bfd_hash_entry *) ret; 256 .} 257 258 DESCRIPTION 259 The creation routine for the linker hash table, which is in 260 <<linker.c>>, looks just like this example. 261 @var{function_name} is <<_bfd_link_hash_newfunc>>. 262 @var{entry_type} is <<struct bfd_link_hash_entry>>. 263 @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation 264 routine for a basic hash table. 265 266 <<_bfd_link_hash_newfunc>> also initializes the local fields 267 in a linker hash table entry: <<type>>, <<written>> and 268 <<next>>. 269 270 INODE 271 Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type 272 SUBSUBSECTION 273 Write other derived routines 274 275 You will want to write other routines for your new hash table, 276 as well. 277 278 You will want an initialization routine which calls the 279 initialization routine of the hash table you are deriving from 280 and initializes any other local fields. For the linker hash 281 table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>. 282 283 You will want a lookup routine which calls the lookup routine 284 of the hash table you are deriving from and casts the result. 285 The linker hash table uses <<bfd_link_hash_lookup>> in 286 <<linker.c>> (this actually takes an additional argument which 287 it uses to decide how to return the looked up value). 288 289 You may want a traversal routine. This should just call the 290 traversal routine of the hash table you are deriving from with 291 appropriate casts. The linker hash table uses 292 <<bfd_link_hash_traverse>> in <<linker.c>>. 293 294 These routines may simply be defined as macros. For example, 295 the a.out backend linker hash table, which is derived from the 296 linker hash table, uses macros for the lookup and traversal 297 routines. These are <<aout_link_hash_lookup>> and 298 <<aout_link_hash_traverse>> in aoutx.h. 299 */ 300 301 /* The default number of entries to use when creating a hash table. */ 302 #define DEFAULT_SIZE 4051 303 304 /* The following function returns a nearest prime number which is 305 greater than N, and near a power of two. Copied from libiberty. 306 Returns zero for ridiculously large N to signify an error. */ 307 308 static unsigned long 309 higher_prime_number (unsigned long n) 310 { 311 /* These are primes that are near, but slightly smaller than, a 312 power of two. */ 313 static const unsigned long primes[] = { 314 (unsigned long) 127, 315 (unsigned long) 2039, 316 (unsigned long) 32749, 317 (unsigned long) 65521, 318 (unsigned long) 131071, 319 (unsigned long) 262139, 320 (unsigned long) 524287, 321 (unsigned long) 1048573, 322 (unsigned long) 2097143, 323 (unsigned long) 4194301, 324 (unsigned long) 8388593, 325 (unsigned long) 16777213, 326 (unsigned long) 33554393, 327 (unsigned long) 67108859, 328 (unsigned long) 134217689, 329 (unsigned long) 268435399, 330 (unsigned long) 536870909, 331 (unsigned long) 1073741789, 332 (unsigned long) 2147483647, 333 /* 4294967291L */ 334 ((unsigned long) 2147483647) + ((unsigned long) 2147483644), 335 }; 336 337 const unsigned long *low = &primes[0]; 338 const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])]; 339 340 while (low != high) 341 { 342 const unsigned long *mid = low + (high - low) / 2; 343 if (n >= *mid) 344 low = mid + 1; 345 else 346 high = mid; 347 } 348 349 if (n >= *low) 350 return 0; 351 352 return *low; 353 } 354 355 static size_t bfd_default_hash_table_size = DEFAULT_SIZE; 356 357 /* Create a new hash table, given a number of entries. */ 358 359 bfd_boolean 360 bfd_hash_table_init_n (struct bfd_hash_table *table, 361 struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, 362 struct bfd_hash_table *, 363 const char *), 364 unsigned int entsize, 365 unsigned int size) 366 { 367 unsigned int alloc; 368 369 alloc = size * sizeof (struct bfd_hash_entry *); 370 371 table->memory = (void *) objalloc_create (); 372 if (table->memory == NULL) 373 { 374 bfd_set_error (bfd_error_no_memory); 375 return FALSE; 376 } 377 table->table = (struct bfd_hash_entry **) 378 objalloc_alloc ((struct objalloc *) table->memory, alloc); 379 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 objalloc_free ((struct objalloc *) table->memory); 412 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 char *new_string; 458 459 new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory, 460 len + 1); 461 if (!new_string) 462 { 463 bfd_set_error (bfd_error_no_memory); 464 return NULL; 465 } 466 memcpy (new_string, string, len + 1); 467 string = new_string; 468 } 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 entry = (struct bfd_hash_entry *) bfd_hash_allocate (table, 586 sizeof (* entry)); 587 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 ret = (struct strtab_hash_entry *) bfd_hash_allocate (table, 682 sizeof (* ret)); 683 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 table = (struct bfd_strtab_hash *) bfd_malloc (amt); 715 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 entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table, 778 sizeof (* entry)); 779 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 n = (char *) bfd_hash_allocate (&tab->table, strlen (str) + 1); 788 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 } 858