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