hash.c revision 33965
1/* hash.c -- hash table routines for BFD 2 Copyright (C) 1993, 94, 95, 1997 Free Software Foundation, Inc. 3 Written by Steve Chamberlain <sac@cygnus.com> 4 5This file is part of BFD, the Binary File Descriptor library. 6 7This program is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2 of the License, or 10(at your option) any later version. 11 12This program is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with this program; if not, write to the Free Software 19Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 20 21#include "bfd.h" 22#include "sysdep.h" 23#include "libbfd.h" 24#include "objalloc.h" 25 26/* 27SECTION 28 Hash Tables 29 30@cindex Hash tables 31 BFD provides a simple set of hash table functions. Routines 32 are provided to initialize a hash table, to free a hash table, 33 to look up a string in a hash table and optionally create an 34 entry for it, and to traverse a hash table. There is 35 currently no routine to delete an string from a hash table. 36 37 The basic hash table does not permit any data to be stored 38 with a string. However, a hash table is designed to present a 39 base class from which other types of hash tables may be 40 derived. These derived types may store additional information 41 with the string. Hash tables were implemented in this way, 42 rather than simply providing a data pointer in a hash table 43 entry, because they were designed for use by the linker back 44 ends. The linker may create thousands of hash table entries, 45 and the overhead of allocating private data and storing and 46 following pointers becomes noticeable. 47 48 The basic hash table code is in <<hash.c>>. 49 50@menu 51@* Creating and Freeing a Hash Table:: 52@* Looking Up or Entering a String:: 53@* Traversing a Hash Table:: 54@* Deriving a New Hash Table Type:: 55@end menu 56 57INODE 58Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables 59SUBSECTION 60 Creating and freeing a hash table 61 62@findex bfd_hash_table_init 63@findex bfd_hash_table_init_n 64 To create a hash table, create an instance of a <<struct 65 bfd_hash_table>> (defined in <<bfd.h>>) and call 66 <<bfd_hash_table_init>> (if you know approximately how many 67 entries you will need, the function <<bfd_hash_table_init_n>>, 68 which takes a @var{size} argument, may be used). 69 <<bfd_hash_table_init>> returns <<false>> if some sort of 70 error occurs. 71 72@findex bfd_hash_newfunc 73 The function <<bfd_hash_table_init>> take as an argument a 74 function to use to create new entries. For a basic hash 75 table, use the function <<bfd_hash_newfunc>>. @xref{Deriving 76 a New Hash Table Type} for why you would want to use a 77 different value for this argument. 78 79@findex bfd_hash_allocate 80 <<bfd_hash_table_init>> will create an objalloc which will be 81 used to allocate new entries. You may allocate memory on this 82 objalloc using <<bfd_hash_allocate>>. 83 84@findex bfd_hash_table_free 85 Use <<bfd_hash_table_free>> to free up all the memory that has 86 been allocated for a hash table. This will not free up the 87 <<struct bfd_hash_table>> itself, which you must provide. 88 89INODE 90Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables 91SUBSECTION 92 Looking up or entering a string 93 94@findex bfd_hash_lookup 95 The function <<bfd_hash_lookup>> is used both to look up a 96 string in the hash table and to create a new entry. 97 98 If the @var{create} argument is <<false>>, <<bfd_hash_lookup>> 99 will look up a string. If the string is found, it will 100 returns a pointer to a <<struct bfd_hash_entry>>. If the 101 string is not found in the table <<bfd_hash_lookup>> will 102 return <<NULL>>. You should not modify any of the fields in 103 the returns <<struct bfd_hash_entry>>. 104 105 If the @var{create} argument is <<true>>, the string will be 106 entered into the hash table if it is not already there. 107 Either way a pointer to a <<struct bfd_hash_entry>> will be 108 returned, either to the existing structure or to a newly 109 created one. In this case, a <<NULL>> return means that an 110 error occurred. 111 112 If the @var{create} argument is <<true>>, and a new entry is 113 created, the @var{copy} argument is used to decide whether to 114 copy the string onto the hash table objalloc or not. If 115 @var{copy} is passed as <<false>>, you must be careful not to 116 deallocate or modify the string as long as the hash table 117 exists. 118 119INODE 120Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables 121SUBSECTION 122 Traversing a hash table 123 124@findex bfd_hash_traverse 125 The function <<bfd_hash_traverse>> may be used to traverse a 126 hash table, calling a function on each element. The traversal 127 is done in a random order. 128 129 <<bfd_hash_traverse>> takes as arguments a function and a 130 generic <<void *>> pointer. The function is called with a 131 hash table entry (a <<struct bfd_hash_entry *>>) and the 132 generic pointer passed to <<bfd_hash_traverse>>. The function 133 must return a <<boolean>> value, which indicates whether to 134 continue traversing the hash table. If the function returns 135 <<false>>, <<bfd_hash_traverse>> will stop the traversal and 136 return immediately. 137 138INODE 139Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables 140SUBSECTION 141 Deriving a new hash table type 142 143 Many uses of hash tables want to store additional information 144 which each entry in the hash table. Some also find it 145 convenient to store additional information with the hash table 146 itself. This may be done using a derived hash table. 147 148 Since C is not an object oriented language, creating a derived 149 hash table requires sticking together some boilerplate 150 routines with a few differences specific to the type of hash 151 table you want to create. 152 153 An example of a derived hash table is the linker hash table. 154 The structures for this are defined in <<bfdlink.h>>. The 155 functions are in <<linker.c>>. 156 157 You may also derive a hash table from an already derived hash 158 table. For example, the a.out linker backend code uses a hash 159 table derived from the linker hash table. 160 161@menu 162@* Define the Derived Structures:: 163@* Write the Derived Creation Routine:: 164@* Write Other Derived Routines:: 165@end menu 166 167INODE 168Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type 169SUBSUBSECTION 170 Define the derived structures 171 172 You must define a structure for an entry in the hash table, 173 and a structure for the hash table itself. 174 175 The first field in the structure for an entry in the hash 176 table must be of the type used for an entry in the hash table 177 you are deriving from. If you are deriving from a basic hash 178 table this is <<struct bfd_hash_entry>>, which is defined in 179 <<bfd.h>>. The first field in the structure for the hash 180 table itself must be of the type of the hash table you are 181 deriving from itself. If you are deriving from a basic hash 182 table, this is <<struct bfd_hash_table>>. 183 184 For example, the linker hash table defines <<struct 185 bfd_link_hash_entry>> (in <<bfdlink.h>>). The first field, 186 <<root>>, is of type <<struct bfd_hash_entry>>. Similarly, 187 the first field in <<struct bfd_link_hash_table>>, <<table>>, 188 is of type <<struct bfd_hash_table>>. 189 190INODE 191Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type 192SUBSUBSECTION 193 Write the derived creation routine 194 195 You must write a routine which will create and initialize an 196 entry in the hash table. This routine is passed as the 197 function argument to <<bfd_hash_table_init>>. 198 199 In order to permit other hash tables to be derived from the 200 hash table you are creating, this routine must be written in a 201 standard way. 202 203 The first argument to the creation routine is a pointer to a 204 hash table entry. This may be <<NULL>>, in which case the 205 routine should allocate the right amount of space. Otherwise 206 the space has already been allocated by a hash table type 207 derived from this one. 208 209 After allocating space, the creation routine must call the 210 creation routine of the hash table type it is derived from, 211 passing in a pointer to the space it just allocated. This 212 will initialize any fields used by the base hash table. 213 214 Finally the creation routine must initialize any local fields 215 for the new hash table type. 216 217 Here is a boilerplate example of a creation routine. 218 @var{function_name} is the name of the routine. 219 @var{entry_type} is the type of an entry in the hash table you 220 are creating. @var{base_newfunc} is the name of the creation 221 routine of the hash table type your hash table is derived 222 from. 223 224EXAMPLE 225 226.struct bfd_hash_entry * 227.@var{function_name} (entry, table, string) 228. struct bfd_hash_entry *entry; 229. struct bfd_hash_table *table; 230. const char *string; 231.{ 232. struct @var{entry_type} *ret = (@var{entry_type} *) entry; 233. 234. {* Allocate the structure if it has not already been allocated by a 235. derived class. *} 236. if (ret == (@var{entry_type} *) NULL) 237. { 238. ret = ((@var{entry_type} *) 239. bfd_hash_allocate (table, sizeof (@var{entry_type}))); 240. if (ret == (@var{entry_type} *) NULL) 241. return NULL; 242. } 243. 244. {* Call the allocation method of the base class. *} 245. ret = ((@var{entry_type} *) 246. @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string)); 247. 248. {* Initialize the local fields here. *} 249. 250. return (struct bfd_hash_entry *) ret; 251.} 252 253DESCRIPTION 254 The creation routine for the linker hash table, which is in 255 <<linker.c>>, looks just like this example. 256 @var{function_name} is <<_bfd_link_hash_newfunc>>. 257 @var{entry_type} is <<struct bfd_link_hash_entry>>. 258 @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation 259 routine for a basic hash table. 260 261 <<_bfd_link_hash_newfunc>> also initializes the local fields 262 in a linker hash table entry: <<type>>, <<written>> and 263 <<next>>. 264 265INODE 266Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type 267SUBSUBSECTION 268 Write other derived routines 269 270 You will want to write other routines for your new hash table, 271 as well. 272 273 You will want an initialization routine which calls the 274 initialization routine of the hash table you are deriving from 275 and initializes any other local fields. For the linker hash 276 table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>. 277 278 You will want a lookup routine which calls the lookup routine 279 of the hash table you are deriving from and casts the result. 280 The linker hash table uses <<bfd_link_hash_lookup>> in 281 <<linker.c>> (this actually takes an additional argument which 282 it uses to decide how to return the looked up value). 283 284 You may want a traversal routine. This should just call the 285 traversal routine of the hash table you are deriving from with 286 appropriate casts. The linker hash table uses 287 <<bfd_link_hash_traverse>> in <<linker.c>>. 288 289 These routines may simply be defined as macros. For example, 290 the a.out backend linker hash table, which is derived from the 291 linker hash table, uses macros for the lookup and traversal 292 routines. These are <<aout_link_hash_lookup>> and 293 <<aout_link_hash_traverse>> in aoutx.h. 294*/ 295 296/* The default number of entries to use when creating a hash table. */ 297#define DEFAULT_SIZE (4051) 298 299/* Create a new hash table, given a number of entries. */ 300 301boolean 302bfd_hash_table_init_n (table, newfunc, size) 303 struct bfd_hash_table *table; 304 struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *, 305 struct bfd_hash_table *, 306 const char *)); 307 unsigned int size; 308{ 309 unsigned int alloc; 310 311 alloc = size * sizeof (struct bfd_hash_entry *); 312 313 table->memory = (PTR) objalloc_create (); 314 if (table->memory == NULL) 315 { 316 bfd_set_error (bfd_error_no_memory); 317 return false; 318 } 319 table->table = ((struct bfd_hash_entry **) 320 objalloc_alloc ((struct objalloc *) table->memory, alloc)); 321 if (table->table == NULL) 322 { 323 bfd_set_error (bfd_error_no_memory); 324 return false; 325 } 326 memset ((PTR) table->table, 0, alloc); 327 table->size = size; 328 table->newfunc = newfunc; 329 return true; 330} 331 332/* Create a new hash table with the default number of entries. */ 333 334boolean 335bfd_hash_table_init (table, newfunc) 336 struct bfd_hash_table *table; 337 struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *, 338 struct bfd_hash_table *, 339 const char *)); 340{ 341 return bfd_hash_table_init_n (table, newfunc, DEFAULT_SIZE); 342} 343 344/* Free a hash table. */ 345 346void 347bfd_hash_table_free (table) 348 struct bfd_hash_table *table; 349{ 350 objalloc_free ((struct objalloc *) table->memory); 351 table->memory = NULL; 352} 353 354/* Look up a string in a hash table. */ 355 356struct bfd_hash_entry * 357bfd_hash_lookup (table, string, create, copy) 358 struct bfd_hash_table *table; 359 const char *string; 360 boolean create; 361 boolean copy; 362{ 363 register const unsigned char *s; 364 register unsigned long hash; 365 register unsigned int c; 366 struct bfd_hash_entry *hashp; 367 unsigned int len; 368 unsigned int index; 369 370 hash = 0; 371 len = 0; 372 s = (const unsigned char *) string; 373 while ((c = *s++) != '\0') 374 { 375 hash += c + (c << 17); 376 hash ^= hash >> 2; 377 ++len; 378 } 379 hash += len + (len << 17); 380 hash ^= hash >> 2; 381 382 index = hash % table->size; 383 for (hashp = table->table[index]; 384 hashp != (struct bfd_hash_entry *) NULL; 385 hashp = hashp->next) 386 { 387 if (hashp->hash == hash 388 && strcmp (hashp->string, string) == 0) 389 return hashp; 390 } 391 392 if (! create) 393 return (struct bfd_hash_entry *) NULL; 394 395 hashp = (*table->newfunc) ((struct bfd_hash_entry *) NULL, table, string); 396 if (hashp == (struct bfd_hash_entry *) NULL) 397 return (struct bfd_hash_entry *) NULL; 398 if (copy) 399 { 400 char *new; 401 402 new = (char *) objalloc_alloc ((struct objalloc *) table->memory, 403 len + 1); 404 if (!new) 405 { 406 bfd_set_error (bfd_error_no_memory); 407 return (struct bfd_hash_entry *) NULL; 408 } 409 strcpy (new, string); 410 string = new; 411 } 412 hashp->string = string; 413 hashp->hash = hash; 414 hashp->next = table->table[index]; 415 table->table[index] = hashp; 416 417 return hashp; 418} 419 420/* Replace an entry in a hash table. */ 421 422void 423bfd_hash_replace (table, old, nw) 424 struct bfd_hash_table *table; 425 struct bfd_hash_entry *old; 426 struct bfd_hash_entry *nw; 427{ 428 unsigned int index; 429 struct bfd_hash_entry **pph; 430 431 index = old->hash % table->size; 432 for (pph = &table->table[index]; 433 (*pph) != (struct bfd_hash_entry *) NULL; 434 pph = &(*pph)->next) 435 { 436 if (*pph == old) 437 { 438 *pph = nw; 439 return; 440 } 441 } 442 443 abort (); 444} 445 446/* Base method for creating a new hash table entry. */ 447 448/*ARGSUSED*/ 449struct bfd_hash_entry * 450bfd_hash_newfunc (entry, table, string) 451 struct bfd_hash_entry *entry; 452 struct bfd_hash_table *table; 453 const char *string; 454{ 455 if (entry == (struct bfd_hash_entry *) NULL) 456 entry = ((struct bfd_hash_entry *) 457 bfd_hash_allocate (table, sizeof (struct bfd_hash_entry))); 458 return entry; 459} 460 461/* Allocate space in a hash table. */ 462 463PTR 464bfd_hash_allocate (table, size) 465 struct bfd_hash_table *table; 466 unsigned int size; 467{ 468 PTR ret; 469 470 ret = objalloc_alloc ((struct objalloc *) table->memory, size); 471 if (ret == NULL && size != 0) 472 bfd_set_error (bfd_error_no_memory); 473 return ret; 474} 475 476/* Traverse a hash table. */ 477 478void 479bfd_hash_traverse (table, func, info) 480 struct bfd_hash_table *table; 481 boolean (*func) PARAMS ((struct bfd_hash_entry *, PTR)); 482 PTR info; 483{ 484 unsigned int i; 485 486 for (i = 0; i < table->size; i++) 487 { 488 struct bfd_hash_entry *p; 489 490 for (p = table->table[i]; p != NULL; p = p->next) 491 { 492 if (! (*func) (p, info)) 493 return; 494 } 495 } 496} 497 498/* A few different object file formats (a.out, COFF, ELF) use a string 499 table. These functions support adding strings to a string table, 500 returning the byte offset, and writing out the table. 501 502 Possible improvements: 503 + look for strings matching trailing substrings of other strings 504 + better data structures? balanced trees? 505 + look at reducing memory use elsewhere -- maybe if we didn't have 506 to construct the entire symbol table at once, we could get by 507 with smaller amounts of VM? (What effect does that have on the 508 string table reductions?) */ 509 510/* An entry in the strtab hash table. */ 511 512struct strtab_hash_entry 513{ 514 struct bfd_hash_entry root; 515 /* Index in string table. */ 516 bfd_size_type index; 517 /* Next string in strtab. */ 518 struct strtab_hash_entry *next; 519}; 520 521/* The strtab hash table. */ 522 523struct bfd_strtab_hash 524{ 525 struct bfd_hash_table table; 526 /* Size of strtab--also next available index. */ 527 bfd_size_type size; 528 /* First string in strtab. */ 529 struct strtab_hash_entry *first; 530 /* Last string in strtab. */ 531 struct strtab_hash_entry *last; 532 /* Whether to precede strings with a two byte length, as in the 533 XCOFF .debug section. */ 534 boolean xcoff; 535}; 536 537static struct bfd_hash_entry *strtab_hash_newfunc 538 PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *)); 539 540/* Routine to create an entry in a strtab. */ 541 542static struct bfd_hash_entry * 543strtab_hash_newfunc (entry, table, string) 544 struct bfd_hash_entry *entry; 545 struct bfd_hash_table *table; 546 const char *string; 547{ 548 struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry; 549 550 /* Allocate the structure if it has not already been allocated by a 551 subclass. */ 552 if (ret == (struct strtab_hash_entry *) NULL) 553 ret = ((struct strtab_hash_entry *) 554 bfd_hash_allocate (table, sizeof (struct strtab_hash_entry))); 555 if (ret == (struct strtab_hash_entry *) NULL) 556 return NULL; 557 558 /* Call the allocation method of the superclass. */ 559 ret = ((struct strtab_hash_entry *) 560 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string)); 561 562 if (ret) 563 { 564 /* Initialize the local fields. */ 565 ret->index = (bfd_size_type) -1; 566 ret->next = NULL; 567 } 568 569 return (struct bfd_hash_entry *) ret; 570} 571 572/* Look up an entry in an strtab. */ 573 574#define strtab_hash_lookup(t, string, create, copy) \ 575 ((struct strtab_hash_entry *) \ 576 bfd_hash_lookup (&(t)->table, (string), (create), (copy))) 577 578/* Create a new strtab. */ 579 580struct bfd_strtab_hash * 581_bfd_stringtab_init () 582{ 583 struct bfd_strtab_hash *table; 584 585 table = ((struct bfd_strtab_hash *) 586 bfd_malloc (sizeof (struct bfd_strtab_hash))); 587 if (table == NULL) 588 return NULL; 589 590 if (! bfd_hash_table_init (&table->table, strtab_hash_newfunc)) 591 { 592 free (table); 593 return NULL; 594 } 595 596 table->size = 0; 597 table->first = NULL; 598 table->last = NULL; 599 table->xcoff = false; 600 601 return table; 602} 603 604/* Create a new strtab in which the strings are output in the format 605 used in the XCOFF .debug section: a two byte length precedes each 606 string. */ 607 608struct bfd_strtab_hash * 609_bfd_xcoff_stringtab_init () 610{ 611 struct bfd_strtab_hash *ret; 612 613 ret = _bfd_stringtab_init (); 614 if (ret != NULL) 615 ret->xcoff = true; 616 return ret; 617} 618 619/* Free a strtab. */ 620 621void 622_bfd_stringtab_free (table) 623 struct bfd_strtab_hash *table; 624{ 625 bfd_hash_table_free (&table->table); 626 free (table); 627} 628 629/* Get the index of a string in a strtab, adding it if it is not 630 already present. If HASH is false, we don't really use the hash 631 table, and we don't eliminate duplicate strings. */ 632 633bfd_size_type 634_bfd_stringtab_add (tab, str, hash, copy) 635 struct bfd_strtab_hash *tab; 636 const char *str; 637 boolean hash; 638 boolean copy; 639{ 640 register struct strtab_hash_entry *entry; 641 642 if (hash) 643 { 644 entry = strtab_hash_lookup (tab, str, true, copy); 645 if (entry == NULL) 646 return (bfd_size_type) -1; 647 } 648 else 649 { 650 entry = ((struct strtab_hash_entry *) 651 bfd_hash_allocate (&tab->table, 652 sizeof (struct strtab_hash_entry))); 653 if (entry == NULL) 654 return (bfd_size_type) -1; 655 if (! copy) 656 entry->root.string = str; 657 else 658 { 659 char *n; 660 661 n = (char *) bfd_hash_allocate (&tab->table, strlen (str) + 1); 662 if (n == NULL) 663 return (bfd_size_type) -1; 664 entry->root.string = n; 665 } 666 entry->index = (bfd_size_type) -1; 667 entry->next = NULL; 668 } 669 670 if (entry->index == (bfd_size_type) -1) 671 { 672 entry->index = tab->size; 673 tab->size += strlen (str) + 1; 674 if (tab->xcoff) 675 { 676 entry->index += 2; 677 tab->size += 2; 678 } 679 if (tab->first == NULL) 680 tab->first = entry; 681 else 682 tab->last->next = entry; 683 tab->last = entry; 684 } 685 686 return entry->index; 687} 688 689/* Get the number of bytes in a strtab. */ 690 691bfd_size_type 692_bfd_stringtab_size (tab) 693 struct bfd_strtab_hash *tab; 694{ 695 return tab->size; 696} 697 698/* Write out a strtab. ABFD must already be at the right location in 699 the file. */ 700 701boolean 702_bfd_stringtab_emit (abfd, tab) 703 register bfd *abfd; 704 struct bfd_strtab_hash *tab; 705{ 706 register boolean xcoff; 707 register struct strtab_hash_entry *entry; 708 709 xcoff = tab->xcoff; 710 711 for (entry = tab->first; entry != NULL; entry = entry->next) 712 { 713 register const char *str; 714 register size_t len; 715 716 str = entry->root.string; 717 len = strlen (str) + 1; 718 719 if (xcoff) 720 { 721 bfd_byte buf[2]; 722 723 /* The output length includes the null byte. */ 724 bfd_put_16 (abfd, len, buf); 725 if (bfd_write ((PTR) buf, 1, 2, abfd) != 2) 726 return false; 727 } 728 729 if (bfd_write ((PTR) str, 1, len, abfd) != len) 730 return false; 731 } 732 733 return true; 734} 735