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