1/* A type-safe hash table template. 2 Copyright (C) 2012-2015 Free Software Foundation, Inc. 3 Contributed by Lawrence Crowl <crowl@google.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21 22/* This file implements a typed hash table. 23 The implementation borrows from libiberty's htab_t in hashtab.h. 24 25 26 INTRODUCTION TO TYPES 27 28 Users of the hash table generally need to be aware of three types. 29 30 1. The type being placed into the hash table. This type is called 31 the value type. 32 33 2. The type used to describe how to handle the value type within 34 the hash table. This descriptor type provides the hash table with 35 several things. 36 37 - A typedef named 'value_type' to the value type (from above). 38 39 - A static member function named 'hash' that takes a value_type 40 pointer and returns a hashval_t value. 41 42 - A typedef named 'compare_type' that is used to test when an value 43 is found. This type is the comparison type. Usually, it will be the 44 same as value_type. If it is not the same type, you must generally 45 explicitly compute hash values and pass them to the hash table. 46 47 - A static member function named 'equal' that takes a value_type 48 pointer and a compare_type pointer, and returns a bool. 49 50 - A static function named 'remove' that takes an value_type pointer 51 and frees the memory allocated by it. This function is used when 52 individual elements of the table need to be disposed of (e.g., 53 when deleting a hash table, removing elements from the table, etc). 54 55 3. The type of the hash table itself. (More later.) 56 57 In very special circumstances, users may need to know about a fourth type. 58 59 4. The template type used to describe how hash table memory 60 is allocated. This type is called the allocator type. It is 61 parameterized on the value type. It provides four functions. 62 63 - A static member function named 'data_alloc'. This function 64 allocates the data elements in the table. 65 66 - A static member function named 'data_free'. This function 67 deallocates the data elements in the table. 68 69 Hash table are instantiated with two type arguments. 70 71 * The descriptor type, (2) above. 72 73 * The allocator type, (4) above. In general, you will not need to 74 provide your own allocator type. By default, hash tables will use 75 the class template xcallocator, which uses malloc/free for allocation. 76 77 78 DEFINING A DESCRIPTOR TYPE 79 80 The first task in using the hash table is to describe the element type. 81 We compose this into a few steps. 82 83 1. Decide on a removal policy for values stored in the table. 84 This header provides class templates for the two most common 85 policies. 86 87 * typed_free_remove implements the static 'remove' member function 88 by calling free(). 89 90 * typed_noop_remove implements the static 'remove' member function 91 by doing nothing. 92 93 You can use these policies by simply deriving the descriptor type 94 from one of those class template, with the appropriate argument. 95 96 Otherwise, you need to write the static 'remove' member function 97 in the descriptor class. 98 99 2. Choose a hash function. Write the static 'hash' member function. 100 101 3. Choose an equality testing function. In most cases, its two 102 arguments will be value_type pointers. If not, the first argument must 103 be a value_type pointer, and the second argument a compare_type pointer. 104 105 106 AN EXAMPLE DESCRIPTOR TYPE 107 108 Suppose you want to put some_type into the hash table. You could define 109 the descriptor type as follows. 110 111 struct some_type_hasher : typed_noop_remove <some_type> 112 // Deriving from typed_noop_remove means that we get a 'remove' that does 113 // nothing. This choice is good for raw values. 114 { 115 typedef some_type value_type; 116 typedef some_type compare_type; 117 static inline hashval_t hash (const value_type *); 118 static inline bool equal (const value_type *, const compare_type *); 119 }; 120 121 inline hashval_t 122 some_type_hasher::hash (const value_type *e) 123 { ... compute and return a hash value for E ... } 124 125 inline bool 126 some_type_hasher::equal (const value_type *p1, const compare_type *p2) 127 { ... compare P1 vs P2. Return true if they are the 'same' ... } 128 129 130 AN EXAMPLE HASH_TABLE DECLARATION 131 132 To instantiate a hash table for some_type: 133 134 hash_table <some_type_hasher> some_type_hash_table; 135 136 There is no need to mention some_type directly, as the hash table will 137 obtain it using some_type_hasher::value_type. 138 139 You can then used any of the functions in hash_table's public interface. 140 See hash_table for details. The interface is very similar to libiberty's 141 htab_t. 142 143 144 EASY DESCRIPTORS FOR POINTERS 145 146 The class template pointer_hash provides everything you need to hash 147 pointers (as opposed to what they point to). So, to instantiate a hash 148 table over pointers to whatever_type, 149 150 hash_table <pointer_hash <whatever_type>> whatever_type_hash_table; 151 152 153 HASH TABLE ITERATORS 154 155 The hash table provides standard C++ iterators. For example, consider a 156 hash table of some_info. We wish to consume each element of the table: 157 158 extern void consume (some_info *); 159 160 We define a convenience typedef and the hash table: 161 162 typedef hash_table <some_info_hasher> info_table_type; 163 info_table_type info_table; 164 165 Then we write the loop in typical C++ style: 166 167 for (info_table_type::iterator iter = info_table.begin (); 168 iter != info_table.end (); 169 ++iter) 170 if ((*iter).status == INFO_READY) 171 consume (&*iter); 172 173 Or with common sub-expression elimination: 174 175 for (info_table_type::iterator iter = info_table.begin (); 176 iter != info_table.end (); 177 ++iter) 178 { 179 some_info &elem = *iter; 180 if (elem.status == INFO_READY) 181 consume (&elem); 182 } 183 184 One can also use a more typical GCC style: 185 186 typedef some_info *some_info_p; 187 some_info *elem_ptr; 188 info_table_type::iterator iter; 189 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter) 190 if (elem_ptr->status == INFO_READY) 191 consume (elem_ptr); 192 193*/ 194 195 196#ifndef TYPED_HASHTAB_H 197#define TYPED_HASHTAB_H 198 199#include "ggc.h" 200#include "hashtab.h" 201#include <new> 202 203template<typename, typename, typename> class hash_map; 204template<typename, typename> class hash_set; 205 206/* The ordinary memory allocator. */ 207/* FIXME (crowl): This allocator may be extracted for wider sharing later. */ 208 209template <typename Type> 210struct xcallocator 211{ 212 static Type *data_alloc (size_t count); 213 static void data_free (Type *memory); 214}; 215 216 217/* Allocate memory for COUNT data blocks. */ 218 219template <typename Type> 220inline Type * 221xcallocator <Type>::data_alloc (size_t count) 222{ 223 return static_cast <Type *> (xcalloc (count, sizeof (Type))); 224} 225 226 227/* Free memory for data blocks. */ 228 229template <typename Type> 230inline void 231xcallocator <Type>::data_free (Type *memory) 232{ 233 return ::free (memory); 234} 235 236 237/* Helpful type for removing with free. */ 238 239template <typename Type> 240struct typed_free_remove 241{ 242 static inline void remove (Type *p); 243}; 244 245 246/* Remove with free. */ 247 248template <typename Type> 249inline void 250typed_free_remove <Type>::remove (Type *p) 251{ 252 free (p); 253} 254 255 256/* Helpful type for a no-op remove. */ 257 258template <typename Type> 259struct typed_noop_remove 260{ 261 static inline void remove (Type *p); 262}; 263 264 265/* Remove doing nothing. */ 266 267template <typename Type> 268inline void 269typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED) 270{ 271} 272 273 274/* Pointer hash with a no-op remove method. */ 275 276template <typename Type> 277struct pointer_hash : typed_noop_remove <Type> 278{ 279 typedef Type *value_type; 280 typedef Type *compare_type; 281 typedef int store_values_directly; 282 283 static inline hashval_t hash (const value_type &); 284 285 static inline bool equal (const value_type &existing, 286 const compare_type &candidate); 287}; 288 289template <typename Type> 290inline hashval_t 291pointer_hash <Type>::hash (const value_type &candidate) 292{ 293 /* This is a really poor hash function, but it is what the current code uses, 294 so I am reusing it to avoid an additional axis in testing. */ 295 return (hashval_t) ((intptr_t)candidate >> 3); 296} 297 298template <typename Type> 299inline bool 300pointer_hash <Type>::equal (const value_type &existing, 301 const compare_type &candidate) 302{ 303 return existing == candidate; 304} 305 306/* Hasher for entry in gc memory. */ 307 308template<typename T> 309struct ggc_hasher 310{ 311 typedef T value_type; 312 typedef T compare_type; 313 typedef int store_values_directly; 314 315 static void remove (T) {} 316 317 static void 318 ggc_mx (T p) 319 { 320 extern void gt_ggc_mx (T &); 321 gt_ggc_mx (p); 322 } 323 324 static void 325 pch_nx (T &p) 326 { 327 extern void gt_pch_nx (T &); 328 gt_pch_nx (p); 329 } 330 331 static void 332 pch_nx (T &p, gt_pointer_operator op, void *cookie) 333 { 334 op (&p, cookie); 335 } 336}; 337 338/* Hasher for cache entry in gc memory. */ 339 340template<typename T> 341struct ggc_cache_hasher 342{ 343 typedef T value_type; 344 typedef T compare_type; 345 typedef int store_values_directly; 346 347 static void remove (T &) {} 348 349 /* Entries are weakly held because this is for caches. */ 350 351 static void ggc_mx (T &) {} 352 353 static void 354 pch_nx (T &p) 355 { 356 extern void gt_pch_nx (T &); 357 gt_pch_nx (p); 358 } 359 360 static void 361 pch_nx (T &p, gt_pointer_operator op, void *cookie) 362 { 363 op (&p, cookie); 364 } 365 366 /* Clear out entries if they are about to be gc'd. */ 367 368 static void 369 handle_cache_entry (T &e) 370 { 371 if (e != HTAB_EMPTY_ENTRY && e != HTAB_DELETED_ENTRY && !ggc_marked_p (e)) 372 e = static_cast<T> (HTAB_DELETED_ENTRY); 373 } 374}; 375 376 377/* Table of primes and their inversion information. */ 378 379struct prime_ent 380{ 381 hashval_t prime; 382 hashval_t inv; 383 hashval_t inv_m2; /* inverse of prime-2 */ 384 hashval_t shift; 385}; 386 387extern struct prime_ent const prime_tab[]; 388 389 390/* Functions for computing hash table indexes. */ 391 392extern unsigned int hash_table_higher_prime_index (unsigned long n) 393 ATTRIBUTE_PURE; 394 395/* Return X % Y using multiplicative inverse values INV and SHIFT. 396 397 The multiplicative inverses computed above are for 32-bit types, 398 and requires that we be able to compute a highpart multiply. 399 400 FIX: I am not at all convinced that 401 3 loads, 2 multiplications, 3 shifts, and 3 additions 402 will be faster than 403 1 load and 1 modulus 404 on modern systems running a compiler. */ 405 406inline hashval_t 407mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift) 408{ 409 hashval_t t1, t2, t3, t4, q, r; 410 411 t1 = ((uint64_t)x * inv) >> 32; 412 t2 = x - t1; 413 t3 = t2 >> 1; 414 t4 = t1 + t3; 415 q = t4 >> shift; 416 r = x - (q * y); 417 418 return r; 419} 420 421/* Compute the primary table index for HASH given current prime index. */ 422 423inline hashval_t 424hash_table_mod1 (hashval_t hash, unsigned int index) 425{ 426 const struct prime_ent *p = &prime_tab[index]; 427 gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32); 428 return mul_mod (hash, p->prime, p->inv, p->shift); 429} 430 431/* Compute the secondary table index for HASH given current prime index. */ 432 433inline hashval_t 434hash_table_mod2 (hashval_t hash, unsigned int index) 435{ 436 const struct prime_ent *p = &prime_tab[index]; 437 gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32); 438 return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift); 439} 440 441/* The below is some template meta programming to decide if we should use the 442 hash table partial specialization that directly stores value_type instead of 443 pointers to value_type. If the Descriptor type defines the type 444 Descriptor::store_values_directly then values are stored directly otherwise 445 pointers to them are stored. */ 446template<typename T> struct notype { typedef void type; }; 447 448template<typename T, typename = void> 449struct storage_tester 450{ 451 static const bool value = false; 452}; 453 454template<typename T> 455struct storage_tester<T, typename notype<typename 456 T::store_values_directly>::type> 457{ 458 static const bool value = true; 459}; 460 461 template<typename Traits> 462 struct has_is_deleted 463{ 464 template<typename U, bool (*)(U &)> struct helper {}; 465 template<typename U> static char test (helper<U, U::is_deleted> *); 466 template<typename U> static int test (...); 467 static const bool value = sizeof (test<Traits> (0)) == sizeof (char); 468}; 469 470template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> 471struct is_deleted_helper 472{ 473 static inline bool 474 call (Type &v) 475 { 476 return Traits::is_deleted (v); 477 } 478}; 479 480template<typename Type, typename Traits> 481struct is_deleted_helper<Type *, Traits, false> 482{ 483 static inline bool 484 call (Type *v) 485 { 486 return v == HTAB_DELETED_ENTRY; 487 } 488}; 489 490 template<typename Traits> 491 struct has_is_empty 492{ 493 template<typename U, bool (*)(U &)> struct helper {}; 494 template<typename U> static char test (helper<U, U::is_empty> *); 495 template<typename U> static int test (...); 496 static const bool value = sizeof (test<Traits> (0)) == sizeof (char); 497}; 498 499template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> 500struct is_empty_helper 501{ 502 static inline bool 503 call (Type &v) 504 { 505 return Traits::is_empty (v); 506 } 507}; 508 509template<typename Type, typename Traits> 510struct is_empty_helper<Type *, Traits, false> 511{ 512 static inline bool 513 call (Type *v) 514 { 515 return v == HTAB_EMPTY_ENTRY; 516 } 517}; 518 519 template<typename Traits> 520 struct has_mark_deleted 521{ 522 template<typename U, void (*)(U &)> struct helper {}; 523 template<typename U> static char test (helper<U, U::mark_deleted> *); 524 template<typename U> static int test (...); 525 static const bool value = sizeof (test<Traits> (0)) == sizeof (char); 526}; 527 528template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> 529struct mark_deleted_helper 530{ 531 static inline void 532 call (Type &v) 533 { 534 Traits::mark_deleted (v); 535 } 536}; 537 538template<typename Type, typename Traits> 539struct mark_deleted_helper<Type *, Traits, false> 540{ 541 static inline void 542 call (Type *&v) 543 { 544 v = static_cast<Type *> (HTAB_DELETED_ENTRY); 545 } 546}; 547 548 template<typename Traits> 549 struct has_mark_empty 550{ 551 template<typename U, void (*)(U &)> struct helper {}; 552 template<typename U> static char test (helper<U, U::mark_empty> *); 553 template<typename U> static int test (...); 554 static const bool value = sizeof (test<Traits> (0)) == sizeof (char); 555}; 556 557template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> 558struct mark_empty_helper 559{ 560 static inline void 561 call (Type &v) 562 { 563 Traits::mark_empty (v); 564 } 565}; 566 567template<typename Type, typename Traits> 568struct mark_empty_helper<Type *, Traits, false> 569{ 570 static inline void 571 call (Type *&v) 572 { 573 v = static_cast<Type *> (HTAB_EMPTY_ENTRY); 574 } 575}; 576 577/* User-facing hash table type. 578 579 The table stores elements of type Descriptor::value_type, or pointers to 580 objects of type value_type if the descriptor does not define the type 581 store_values_directly. 582 583 It hashes values with the hash member function. 584 The table currently works with relatively weak hash functions. 585 Use typed_pointer_hash <Value> when hashing pointers instead of objects. 586 587 It compares elements with the equal member function. 588 Two elements with the same hash may not be equal. 589 Use typed_pointer_equal <Value> when hashing pointers instead of objects. 590 591 It removes elements with the remove member function. 592 This feature is useful for freeing memory. 593 Derive from typed_null_remove <Value> when not freeing objects. 594 Derive from typed_free_remove <Value> when doing a simple object free. 595 596 Specify the template Allocator to allocate and free memory. 597 The default is xcallocator. 598 599 Storage is an implementation detail and should not be used outside the 600 hash table code. 601 602*/ 603template <typename Descriptor, 604 template<typename Type> class Allocator= xcallocator, 605 bool Storage = storage_tester<Descriptor>::value> 606class hash_table 607{ 608}; 609 610template <typename Descriptor, 611 template<typename Type> class Allocator> 612class hash_table<Descriptor, Allocator, false> 613{ 614 typedef typename Descriptor::value_type value_type; 615 typedef typename Descriptor::compare_type compare_type; 616 617public: 618 hash_table (size_t); 619 ~hash_table (); 620 621 /* Current size (in entries) of the hash table. */ 622 size_t size () const { return m_size; } 623 624 /* Return the current number of elements in this hash table. */ 625 size_t elements () const { return m_n_elements - m_n_deleted; } 626 627 /* Return the current number of elements in this hash table. */ 628 size_t elements_with_deleted () const { return m_n_elements; } 629 630 /* This function clears all entries in the given hash table. */ 631 void empty (); 632 633 /* This function clears a specified SLOT in a hash table. It is 634 useful when you've already done the lookup and don't want to do it 635 again. */ 636 637 void clear_slot (value_type **); 638 639 /* This function searches for a hash table entry equal to the given 640 COMPARABLE element starting with the given HASH value. It cannot 641 be used to insert or delete an element. */ 642 value_type *find_with_hash (const compare_type *, hashval_t); 643 644/* Like find_slot_with_hash, but compute the hash value from the element. */ 645 value_type *find (const value_type *value) 646 { 647 return find_with_hash (value, Descriptor::hash (value)); 648 } 649 650 value_type **find_slot (const value_type *value, insert_option insert) 651 { 652 return find_slot_with_hash (value, Descriptor::hash (value), insert); 653 } 654 655 /* This function searches for a hash table slot containing an entry 656 equal to the given COMPARABLE element and starting with the given 657 HASH. To delete an entry, call this with insert=NO_INSERT, then 658 call clear_slot on the slot returned (possibly after doing some 659 checks). To insert an entry, call this with insert=INSERT, then 660 write the value you want into the returned slot. When inserting an 661 entry, NULL may be returned if memory allocation fails. */ 662 value_type **find_slot_with_hash (const compare_type *comparable, 663 hashval_t hash, enum insert_option insert); 664 665 /* This function deletes an element with the given COMPARABLE value 666 from hash table starting with the given HASH. If there is no 667 matching element in the hash table, this function does nothing. */ 668 void remove_elt_with_hash (const compare_type *, hashval_t); 669 670/* Like remove_elt_with_hash, but compute the hash value from the element. */ 671 void remove_elt (const value_type *value) 672 { 673 remove_elt_with_hash (value, Descriptor::hash (value)); 674 } 675 676 /* This function scans over the entire hash table calling CALLBACK for 677 each live entry. If CALLBACK returns false, the iteration stops. 678 ARGUMENT is passed as CALLBACK's second argument. */ 679 template <typename Argument, 680 int (*Callback) (value_type **slot, Argument argument)> 681 void traverse_noresize (Argument argument); 682 683 /* Like traverse_noresize, but does resize the table when it is too empty 684 to improve effectivity of subsequent calls. */ 685 template <typename Argument, 686 int (*Callback) (value_type **slot, Argument argument)> 687 void traverse (Argument argument); 688 689 class iterator 690 { 691 public: 692 iterator () : m_slot (NULL), m_limit (NULL) {} 693 694 iterator (value_type **slot, value_type **limit) : 695 m_slot (slot), m_limit (limit) {} 696 697 inline value_type *operator * () { return *m_slot; } 698 void slide (); 699 inline iterator &operator ++ (); 700 bool operator != (const iterator &other) const 701 { 702 return m_slot != other.m_slot || m_limit != other.m_limit; 703 } 704 705 private: 706 value_type **m_slot; 707 value_type **m_limit; 708 }; 709 710 iterator begin () const 711 { 712 iterator iter (m_entries, m_entries + m_size); 713 iter.slide (); 714 return iter; 715 } 716 717 iterator end () const { return iterator (); } 718 719 double collisions () const 720 { 721 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0; 722 } 723 724private: 725 726 value_type **find_empty_slot_for_expand (hashval_t); 727 void expand (); 728 729 /* Table itself. */ 730 typename Descriptor::value_type **m_entries; 731 732 size_t m_size; 733 734 /* Current number of elements including also deleted elements. */ 735 size_t m_n_elements; 736 737 /* Current number of deleted elements in the table. */ 738 size_t m_n_deleted; 739 740 /* The following member is used for debugging. Its value is number 741 of all calls of `htab_find_slot' for the hash table. */ 742 unsigned int m_searches; 743 744 /* The following member is used for debugging. Its value is number 745 of collisions fixed for time of work with the hash table. */ 746 unsigned int m_collisions; 747 748 /* Current size (in entries) of the hash table, as an index into the 749 table of primes. */ 750 unsigned int m_size_prime_index; 751}; 752 753template<typename Descriptor, template<typename Type> class Allocator> 754hash_table<Descriptor, Allocator, false>::hash_table (size_t size) : 755 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0) 756{ 757 unsigned int size_prime_index; 758 759 size_prime_index = hash_table_higher_prime_index (size); 760 size = prime_tab[size_prime_index].prime; 761 762 m_entries = Allocator <value_type*> ::data_alloc (size); 763 gcc_assert (m_entries != NULL); 764 m_size = size; 765 m_size_prime_index = size_prime_index; 766} 767 768template<typename Descriptor, template<typename Type> class Allocator> 769hash_table<Descriptor, Allocator, false>::~hash_table () 770{ 771 for (size_t i = m_size - 1; i < m_size; i--) 772 if (m_entries[i] != HTAB_EMPTY_ENTRY && m_entries[i] != HTAB_DELETED_ENTRY) 773 Descriptor::remove (m_entries[i]); 774 775 Allocator <value_type *> ::data_free (m_entries); 776} 777 778/* Similar to find_slot, but without several unwanted side effects: 779 - Does not call equal when it finds an existing entry. 780 - Does not change the count of elements/searches/collisions in the 781 hash table. 782 This function also assumes there are no deleted entries in the table. 783 HASH is the hash value for the element to be inserted. */ 784 785template<typename Descriptor, template<typename Type> class Allocator> 786typename hash_table<Descriptor, Allocator, false>::value_type ** 787hash_table<Descriptor, Allocator, false> 788::find_empty_slot_for_expand (hashval_t hash) 789{ 790 hashval_t index = hash_table_mod1 (hash, m_size_prime_index); 791 size_t size = m_size; 792 value_type **slot = m_entries + index; 793 hashval_t hash2; 794 795 if (*slot == HTAB_EMPTY_ENTRY) 796 return slot; 797 gcc_checking_assert (*slot != HTAB_DELETED_ENTRY); 798 799 hash2 = hash_table_mod2 (hash, m_size_prime_index); 800 for (;;) 801 { 802 index += hash2; 803 if (index >= size) 804 index -= size; 805 806 slot = m_entries + index; 807 if (*slot == HTAB_EMPTY_ENTRY) 808 return slot; 809 gcc_checking_assert (*slot != HTAB_DELETED_ENTRY); 810 } 811} 812 813/* The following function changes size of memory allocated for the 814 entries and repeatedly inserts the table elements. The occupancy 815 of the table after the call will be about 50%. Naturally the hash 816 table must already exist. Remember also that the place of the 817 table entries is changed. If memory allocation fails, this function 818 will abort. */ 819 820template<typename Descriptor, template<typename Type> class Allocator> 821void 822hash_table<Descriptor, Allocator, false>::expand () 823{ 824 value_type **oentries = m_entries; 825 unsigned int oindex = m_size_prime_index; 826 size_t osize = size (); 827 value_type **olimit = oentries + osize; 828 size_t elts = elements (); 829 830 /* Resize only when table after removal of unused elements is either 831 too full or too empty. */ 832 unsigned int nindex; 833 size_t nsize; 834 if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) 835 { 836 nindex = hash_table_higher_prime_index (elts * 2); 837 nsize = prime_tab[nindex].prime; 838 } 839 else 840 { 841 nindex = oindex; 842 nsize = osize; 843 } 844 845 value_type **nentries = Allocator <value_type *> ::data_alloc (nsize); 846 gcc_assert (nentries != NULL); 847 m_entries = nentries; 848 m_size = nsize; 849 m_size_prime_index = nindex; 850 m_n_elements -= m_n_deleted; 851 m_n_deleted = 0; 852 853 value_type **p = oentries; 854 do 855 { 856 value_type *x = *p; 857 858 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) 859 { 860 value_type **q = find_empty_slot_for_expand (Descriptor::hash (x)); 861 862 *q = x; 863 } 864 865 p++; 866 } 867 while (p < olimit); 868 869 Allocator <value_type *> ::data_free (oentries); 870} 871 872template<typename Descriptor, template<typename Type> class Allocator> 873void 874hash_table<Descriptor, Allocator, false>::empty () 875{ 876 size_t size = m_size; 877 value_type **entries = m_entries; 878 int i; 879 880 for (i = size - 1; i >= 0; i--) 881 if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY) 882 Descriptor::remove (entries[i]); 883 884 /* Instead of clearing megabyte, downsize the table. */ 885 if (size > 1024*1024 / sizeof (PTR)) 886 { 887 int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR)); 888 int nsize = prime_tab[nindex].prime; 889 890 Allocator <value_type *> ::data_free (m_entries); 891 m_entries = Allocator <value_type *> ::data_alloc (nsize); 892 m_size = nsize; 893 m_size_prime_index = nindex; 894 } 895 else 896 memset (entries, 0, size * sizeof (value_type *)); 897 m_n_deleted = 0; 898 m_n_elements = 0; 899} 900 901/* This function clears a specified SLOT in a hash table. It is 902 useful when you've already done the lookup and don't want to do it 903 again. */ 904 905template<typename Descriptor, template<typename Type> class Allocator> 906void 907hash_table<Descriptor, Allocator, false>::clear_slot (value_type **slot) 908{ 909 gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size () 910 || *slot == HTAB_EMPTY_ENTRY 911 || *slot == HTAB_DELETED_ENTRY)); 912 913 Descriptor::remove (*slot); 914 915 *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); 916 m_n_deleted++; 917} 918 919/* This function searches for a hash table entry equal to the given 920 COMPARABLE element starting with the given HASH value. It cannot 921 be used to insert or delete an element. */ 922 923template<typename Descriptor, template<typename Type> class Allocator> 924typename hash_table<Descriptor, Allocator, false>::value_type * 925hash_table<Descriptor, Allocator, false> 926::find_with_hash (const compare_type *comparable, hashval_t hash) 927{ 928 m_searches++; 929 size_t size = m_size; 930 hashval_t index = hash_table_mod1 (hash, m_size_prime_index); 931 932 value_type *entry = m_entries[index]; 933 if (entry == HTAB_EMPTY_ENTRY 934 || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable))) 935 return entry; 936 937 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); 938 for (;;) 939 { 940 m_collisions++; 941 index += hash2; 942 if (index >= size) 943 index -= size; 944 945 entry = m_entries[index]; 946 if (entry == HTAB_EMPTY_ENTRY 947 || (entry != HTAB_DELETED_ENTRY 948 && Descriptor::equal (entry, comparable))) 949 return entry; 950 } 951} 952 953/* This function searches for a hash table slot containing an entry 954 equal to the given COMPARABLE element and starting with the given 955 HASH. To delete an entry, call this with insert=NO_INSERT, then 956 call clear_slot on the slot returned (possibly after doing some 957 checks). To insert an entry, call this with insert=INSERT, then 958 write the value you want into the returned slot. When inserting an 959 entry, NULL may be returned if memory allocation fails. */ 960 961template<typename Descriptor, template<typename Type> class Allocator> 962typename hash_table<Descriptor, Allocator, false>::value_type ** 963hash_table<Descriptor, Allocator, false> 964::find_slot_with_hash (const compare_type *comparable, hashval_t hash, 965 enum insert_option insert) 966{ 967 if (insert == INSERT && m_size * 3 <= m_n_elements * 4) 968 expand (); 969 970 m_searches++; 971 972 value_type **first_deleted_slot = NULL; 973 hashval_t index = hash_table_mod1 (hash, m_size_prime_index); 974 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); 975 value_type *entry = m_entries[index]; 976 size_t size = m_size; 977 if (entry == HTAB_EMPTY_ENTRY) 978 goto empty_entry; 979 else if (entry == HTAB_DELETED_ENTRY) 980 first_deleted_slot = &m_entries[index]; 981 else if (Descriptor::equal (entry, comparable)) 982 return &m_entries[index]; 983 984 for (;;) 985 { 986 m_collisions++; 987 index += hash2; 988 if (index >= size) 989 index -= size; 990 991 entry = m_entries[index]; 992 if (entry == HTAB_EMPTY_ENTRY) 993 goto empty_entry; 994 else if (entry == HTAB_DELETED_ENTRY) 995 { 996 if (!first_deleted_slot) 997 first_deleted_slot = &m_entries[index]; 998 } 999 else if (Descriptor::equal (entry, comparable)) 1000 return &m_entries[index]; 1001 } 1002 1003 empty_entry: 1004 if (insert == NO_INSERT) 1005 return NULL; 1006 1007 if (first_deleted_slot) 1008 { 1009 m_n_deleted--; 1010 *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY); 1011 return first_deleted_slot; 1012 } 1013 1014 m_n_elements++; 1015 return &m_entries[index]; 1016} 1017 1018/* This function deletes an element with the given COMPARABLE value 1019 from hash table starting with the given HASH. If there is no 1020 matching element in the hash table, this function does nothing. */ 1021 1022template<typename Descriptor, template<typename Type> class Allocator> 1023void 1024hash_table<Descriptor, Allocator, false> 1025::remove_elt_with_hash (const compare_type *comparable, hashval_t hash) 1026{ 1027 value_type **slot = find_slot_with_hash (comparable, hash, NO_INSERT); 1028 if (*slot == HTAB_EMPTY_ENTRY) 1029 return; 1030 1031 Descriptor::remove (*slot); 1032 1033 *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); 1034 m_n_deleted++; 1035} 1036 1037/* This function scans over the entire hash table calling CALLBACK for 1038 each live entry. If CALLBACK returns false, the iteration stops. 1039 ARGUMENT is passed as CALLBACK's second argument. */ 1040 1041template<typename Descriptor, template<typename Type> class Allocator> 1042template<typename Argument, 1043 int (*Callback) (typename hash_table<Descriptor, Allocator, 1044 false>::value_type **slot, 1045 Argument argument)> 1046void 1047hash_table<Descriptor, Allocator, false>::traverse_noresize (Argument argument) 1048{ 1049 value_type **slot = m_entries; 1050 value_type **limit = slot + size (); 1051 1052 do 1053 { 1054 value_type *x = *slot; 1055 1056 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) 1057 if (! Callback (slot, argument)) 1058 break; 1059 } 1060 while (++slot < limit); 1061} 1062 1063/* Like traverse_noresize, but does resize the table when it is too empty 1064 to improve effectivity of subsequent calls. */ 1065 1066template <typename Descriptor, 1067 template <typename Type> class Allocator> 1068template <typename Argument, 1069 int (*Callback) (typename hash_table<Descriptor, Allocator, 1070 false>::value_type **slot, 1071 Argument argument)> 1072void 1073hash_table<Descriptor, Allocator, false>::traverse (Argument argument) 1074{ 1075 size_t size = m_size; 1076 if (elements () * 8 < size && size > 32) 1077 expand (); 1078 1079 traverse_noresize <Argument, Callback> (argument); 1080} 1081 1082/* Slide down the iterator slots until an active entry is found. */ 1083 1084template<typename Descriptor, template<typename Type> class Allocator> 1085void 1086hash_table<Descriptor, Allocator, false>::iterator::slide () 1087{ 1088 for ( ; m_slot < m_limit; ++m_slot ) 1089 { 1090 value_type *x = *m_slot; 1091 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) 1092 return; 1093 } 1094 m_slot = NULL; 1095 m_limit = NULL; 1096} 1097 1098/* Bump the iterator. */ 1099 1100template<typename Descriptor, template<typename Type> class Allocator> 1101inline typename hash_table<Descriptor, Allocator, false>::iterator & 1102hash_table<Descriptor, Allocator, false>::iterator::operator ++ () 1103{ 1104 ++m_slot; 1105 slide (); 1106 return *this; 1107} 1108 1109/* A partial specialization used when values should be stored directly. */ 1110 1111template <typename Descriptor, 1112 template<typename Type> class Allocator> 1113class hash_table<Descriptor, Allocator, true> 1114{ 1115 typedef typename Descriptor::value_type value_type; 1116 typedef typename Descriptor::compare_type compare_type; 1117 1118public: 1119 explicit hash_table (size_t, bool ggc = false); 1120 ~hash_table (); 1121 1122 /* Create a hash_table in gc memory. */ 1123 1124 static hash_table * 1125 create_ggc (size_t n) 1126 { 1127 hash_table *table = ggc_alloc<hash_table> (); 1128 new (table) hash_table (n, true); 1129 return table; 1130 } 1131 1132 /* Current size (in entries) of the hash table. */ 1133 size_t size () const { return m_size; } 1134 1135 /* Return the current number of elements in this hash table. */ 1136 size_t elements () const { return m_n_elements - m_n_deleted; } 1137 1138 /* Return the current number of elements in this hash table. */ 1139 size_t elements_with_deleted () const { return m_n_elements; } 1140 1141 /* This function clears all entries in the given hash table. */ 1142 void empty (); 1143 1144 /* This function clears a specified SLOT in a hash table. It is 1145 useful when you've already done the lookup and don't want to do it 1146 again. */ 1147 1148 void clear_slot (value_type *); 1149 1150 /* This function searches for a hash table entry equal to the given 1151 COMPARABLE element starting with the given HASH value. It cannot 1152 be used to insert or delete an element. */ 1153 value_type &find_with_hash (const compare_type &, hashval_t); 1154 1155/* Like find_slot_with_hash, but compute the hash value from the element. */ 1156 value_type &find (const value_type &value) 1157 { 1158 return find_with_hash (value, Descriptor::hash (value)); 1159 } 1160 1161 value_type *find_slot (const value_type &value, insert_option insert) 1162 { 1163 return find_slot_with_hash (value, Descriptor::hash (value), insert); 1164 } 1165 1166 /* This function searches for a hash table slot containing an entry 1167 equal to the given COMPARABLE element and starting with the given 1168 HASH. To delete an entry, call this with insert=NO_INSERT, then 1169 call clear_slot on the slot returned (possibly after doing some 1170 checks). To insert an entry, call this with insert=INSERT, then 1171 write the value you want into the returned slot. When inserting an 1172 entry, NULL may be returned if memory allocation fails. */ 1173 value_type *find_slot_with_hash (const compare_type &comparable, 1174 hashval_t hash, enum insert_option insert); 1175 1176 /* This function deletes an element with the given COMPARABLE value 1177 from hash table starting with the given HASH. If there is no 1178 matching element in the hash table, this function does nothing. */ 1179 void remove_elt_with_hash (const compare_type &, hashval_t); 1180 1181/* Like remove_elt_with_hash, but compute the hash value from the element. */ 1182 void remove_elt (const value_type &value) 1183 { 1184 remove_elt_with_hash (value, Descriptor::hash (value)); 1185 } 1186 1187 /* This function scans over the entire hash table calling CALLBACK for 1188 each live entry. If CALLBACK returns false, the iteration stops. 1189 ARGUMENT is passed as CALLBACK's second argument. */ 1190 template <typename Argument, 1191 int (*Callback) (value_type *slot, Argument argument)> 1192 void traverse_noresize (Argument argument); 1193 1194 /* Like traverse_noresize, but does resize the table when it is too empty 1195 to improve effectivity of subsequent calls. */ 1196 template <typename Argument, 1197 int (*Callback) (value_type *slot, Argument argument)> 1198 void traverse (Argument argument); 1199 1200 class iterator 1201 { 1202 public: 1203 iterator () : m_slot (NULL), m_limit (NULL) {} 1204 1205 iterator (value_type *slot, value_type *limit) : 1206 m_slot (slot), m_limit (limit) {} 1207 1208 inline value_type &operator * () { return *m_slot; } 1209 void slide (); 1210 inline iterator &operator ++ (); 1211 bool operator != (const iterator &other) const 1212 { 1213 return m_slot != other.m_slot || m_limit != other.m_limit; 1214 } 1215 1216 private: 1217 value_type *m_slot; 1218 value_type *m_limit; 1219 }; 1220 1221 iterator begin () const 1222 { 1223 iterator iter (m_entries, m_entries + m_size); 1224 iter.slide (); 1225 return iter; 1226 } 1227 1228 iterator end () const { return iterator (); } 1229 1230 double collisions () const 1231 { 1232 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0; 1233 } 1234 1235private: 1236 template<typename T> friend void gt_ggc_mx (hash_table<T> *); 1237 template<typename T> friend void gt_pch_nx (hash_table<T> *); 1238 template<typename T> friend void 1239 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *); 1240 template<typename T, typename U, typename V> friend void 1241 gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *); 1242 template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *, 1243 gt_pointer_operator, 1244 void *); 1245 template<typename T> friend void gt_pch_nx (hash_table<T> *, 1246 gt_pointer_operator, void *); 1247 1248 value_type *alloc_entries (size_t n) const; 1249 value_type *find_empty_slot_for_expand (hashval_t); 1250 void expand (); 1251 static bool is_deleted (value_type &v) 1252 { 1253 return is_deleted_helper<value_type, Descriptor>::call (v); 1254 } 1255 static bool is_empty (value_type &v) 1256 { 1257 return is_empty_helper<value_type, Descriptor>::call (v); 1258 } 1259 1260 static void mark_deleted (value_type &v) 1261 { 1262 return mark_deleted_helper<value_type, Descriptor>::call (v); 1263 } 1264 1265 static void mark_empty (value_type &v) 1266 { 1267 return mark_empty_helper<value_type, Descriptor>::call (v); 1268 } 1269 1270 /* Table itself. */ 1271 typename Descriptor::value_type *m_entries; 1272 1273 size_t m_size; 1274 1275 /* Current number of elements including also deleted elements. */ 1276 size_t m_n_elements; 1277 1278 /* Current number of deleted elements in the table. */ 1279 size_t m_n_deleted; 1280 1281 /* The following member is used for debugging. Its value is number 1282 of all calls of `htab_find_slot' for the hash table. */ 1283 unsigned int m_searches; 1284 1285 /* The following member is used for debugging. Its value is number 1286 of collisions fixed for time of work with the hash table. */ 1287 unsigned int m_collisions; 1288 1289 /* Current size (in entries) of the hash table, as an index into the 1290 table of primes. */ 1291 unsigned int m_size_prime_index; 1292 1293 /* if m_entries is stored in ggc memory. */ 1294 bool m_ggc; 1295}; 1296 1297template<typename Descriptor, template<typename Type> class Allocator> 1298hash_table<Descriptor, Allocator, true>::hash_table (size_t size, bool ggc) : 1299 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0), 1300 m_ggc (ggc) 1301{ 1302 unsigned int size_prime_index; 1303 1304 size_prime_index = hash_table_higher_prime_index (size); 1305 size = prime_tab[size_prime_index].prime; 1306 1307 m_entries = alloc_entries (size); 1308 m_size = size; 1309 m_size_prime_index = size_prime_index; 1310} 1311 1312template<typename Descriptor, template<typename Type> class Allocator> 1313hash_table<Descriptor, Allocator, true>::~hash_table () 1314{ 1315 for (size_t i = m_size - 1; i < m_size; i--) 1316 if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i])) 1317 Descriptor::remove (m_entries[i]); 1318 1319 if (!m_ggc) 1320 Allocator <value_type> ::data_free (m_entries); 1321 else 1322 ggc_free (m_entries); 1323} 1324 1325/* This function returns an array of empty hash table elements. */ 1326 1327template<typename Descriptor, template<typename Type> class Allocator> 1328inline typename hash_table<Descriptor, Allocator, true>::value_type * 1329hash_table<Descriptor, Allocator, true>::alloc_entries (size_t n) const 1330{ 1331 value_type *nentries; 1332 1333 if (!m_ggc) 1334 nentries = Allocator <value_type> ::data_alloc (n); 1335 else 1336 nentries = ::ggc_cleared_vec_alloc<value_type> (n); 1337 1338 gcc_assert (nentries != NULL); 1339 for (size_t i = 0; i < n; i++) 1340 mark_empty (nentries[i]); 1341 1342 return nentries; 1343} 1344 1345/* Similar to find_slot, but without several unwanted side effects: 1346 - Does not call equal when it finds an existing entry. 1347 - Does not change the count of elements/searches/collisions in the 1348 hash table. 1349 This function also assumes there are no deleted entries in the table. 1350 HASH is the hash value for the element to be inserted. */ 1351 1352template<typename Descriptor, template<typename Type> class Allocator> 1353typename hash_table<Descriptor, Allocator, true>::value_type * 1354hash_table<Descriptor, Allocator, true> 1355::find_empty_slot_for_expand (hashval_t hash) 1356{ 1357 hashval_t index = hash_table_mod1 (hash, m_size_prime_index); 1358 size_t size = m_size; 1359 value_type *slot = m_entries + index; 1360 hashval_t hash2; 1361 1362 if (is_empty (*slot)) 1363 return slot; 1364#ifdef ENABLE_CHECKING 1365 gcc_checking_assert (!is_deleted (*slot)); 1366#endif 1367 1368 hash2 = hash_table_mod2 (hash, m_size_prime_index); 1369 for (;;) 1370 { 1371 index += hash2; 1372 if (index >= size) 1373 index -= size; 1374 1375 slot = m_entries + index; 1376 if (is_empty (*slot)) 1377 return slot; 1378#ifdef ENABLE_CHECKING 1379 gcc_checking_assert (!is_deleted (*slot)); 1380#endif 1381 } 1382} 1383 1384/* The following function changes size of memory allocated for the 1385 entries and repeatedly inserts the table elements. The occupancy 1386 of the table after the call will be about 50%. Naturally the hash 1387 table must already exist. Remember also that the place of the 1388 table entries is changed. If memory allocation fails, this function 1389 will abort. */ 1390 1391 template<typename Descriptor, template<typename Type> class Allocator> 1392void 1393hash_table<Descriptor, Allocator, true>::expand () 1394{ 1395 value_type *oentries = m_entries; 1396 unsigned int oindex = m_size_prime_index; 1397 size_t osize = size (); 1398 value_type *olimit = oentries + osize; 1399 size_t elts = elements (); 1400 1401 /* Resize only when table after removal of unused elements is either 1402 too full or too empty. */ 1403 unsigned int nindex; 1404 size_t nsize; 1405 if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) 1406 { 1407 nindex = hash_table_higher_prime_index (elts * 2); 1408 nsize = prime_tab[nindex].prime; 1409 } 1410 else 1411 { 1412 nindex = oindex; 1413 nsize = osize; 1414 } 1415 1416 value_type *nentries = alloc_entries (nsize); 1417 m_entries = nentries; 1418 m_size = nsize; 1419 m_size_prime_index = nindex; 1420 m_n_elements -= m_n_deleted; 1421 m_n_deleted = 0; 1422 1423 value_type *p = oentries; 1424 do 1425 { 1426 value_type &x = *p; 1427 1428 if (!is_empty (x) && !is_deleted (x)) 1429 { 1430 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x)); 1431 1432 *q = x; 1433 } 1434 1435 p++; 1436 } 1437 while (p < olimit); 1438 1439 if (!m_ggc) 1440 Allocator <value_type> ::data_free (oentries); 1441 else 1442 ggc_free (oentries); 1443} 1444 1445template<typename Descriptor, template<typename Type> class Allocator> 1446void 1447hash_table<Descriptor, Allocator, true>::empty () 1448{ 1449 size_t size = m_size; 1450 value_type *entries = m_entries; 1451 int i; 1452 1453 for (i = size - 1; i >= 0; i--) 1454 if (!is_empty (entries[i]) && !is_deleted (entries[i])) 1455 Descriptor::remove (entries[i]); 1456 1457 /* Instead of clearing megabyte, downsize the table. */ 1458 if (size > 1024*1024 / sizeof (PTR)) 1459 { 1460 int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR)); 1461 int nsize = prime_tab[nindex].prime; 1462 1463 if (!m_ggc) 1464 Allocator <value_type> ::data_free (m_entries); 1465 else 1466 ggc_free (m_entries); 1467 1468 m_entries = alloc_entries (nsize); 1469 m_size = nsize; 1470 m_size_prime_index = nindex; 1471 } 1472 else 1473 memset (entries, 0, size * sizeof (value_type)); 1474 m_n_deleted = 0; 1475 m_n_elements = 0; 1476} 1477 1478/* This function clears a specified SLOT in a hash table. It is 1479 useful when you've already done the lookup and don't want to do it 1480 again. */ 1481 1482template<typename Descriptor, template<typename Type> class Allocator> 1483void 1484hash_table<Descriptor, Allocator, true>::clear_slot (value_type *slot) 1485{ 1486 gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size () 1487 || is_empty (*slot) || is_deleted (*slot))); 1488 1489 Descriptor::remove (*slot); 1490 1491 mark_deleted (*slot); 1492 m_n_deleted++; 1493} 1494 1495/* This function searches for a hash table entry equal to the given 1496 COMPARABLE element starting with the given HASH value. It cannot 1497 be used to insert or delete an element. */ 1498 1499template<typename Descriptor, template<typename Type> class Allocator> 1500typename hash_table<Descriptor, Allocator, true>::value_type & 1501hash_table<Descriptor, Allocator, true> 1502::find_with_hash (const compare_type &comparable, hashval_t hash) 1503{ 1504 m_searches++; 1505 size_t size = m_size; 1506 hashval_t index = hash_table_mod1 (hash, m_size_prime_index); 1507 1508 value_type *entry = &m_entries[index]; 1509 if (is_empty (*entry) 1510 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable))) 1511 return *entry; 1512 1513 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); 1514 for (;;) 1515 { 1516 m_collisions++; 1517 index += hash2; 1518 if (index >= size) 1519 index -= size; 1520 1521 entry = &m_entries[index]; 1522 if (is_empty (*entry) 1523 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable))) 1524 return *entry; 1525 } 1526} 1527 1528/* This function searches for a hash table slot containing an entry 1529 equal to the given COMPARABLE element and starting with the given 1530 HASH. To delete an entry, call this with insert=NO_INSERT, then 1531 call clear_slot on the slot returned (possibly after doing some 1532 checks). To insert an entry, call this with insert=INSERT, then 1533 write the value you want into the returned slot. When inserting an 1534 entry, NULL may be returned if memory allocation fails. */ 1535 1536template<typename Descriptor, template<typename Type> class Allocator> 1537typename hash_table<Descriptor, Allocator, true>::value_type * 1538hash_table<Descriptor, Allocator, true> 1539::find_slot_with_hash (const compare_type &comparable, hashval_t hash, 1540 enum insert_option insert) 1541{ 1542 if (insert == INSERT && m_size * 3 <= m_n_elements * 4) 1543 expand (); 1544 1545 m_searches++; 1546 1547 value_type *first_deleted_slot = NULL; 1548 hashval_t index = hash_table_mod1 (hash, m_size_prime_index); 1549 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); 1550 value_type *entry = &m_entries[index]; 1551 size_t size = m_size; 1552 if (is_empty (*entry)) 1553 goto empty_entry; 1554 else if (is_deleted (*entry)) 1555 first_deleted_slot = &m_entries[index]; 1556 else if (Descriptor::equal (*entry, comparable)) 1557 return &m_entries[index]; 1558 1559 for (;;) 1560 { 1561 m_collisions++; 1562 index += hash2; 1563 if (index >= size) 1564 index -= size; 1565 1566 entry = &m_entries[index]; 1567 if (is_empty (*entry)) 1568 goto empty_entry; 1569 else if (is_deleted (*entry)) 1570 { 1571 if (!first_deleted_slot) 1572 first_deleted_slot = &m_entries[index]; 1573 } 1574 else if (Descriptor::equal (*entry, comparable)) 1575 return &m_entries[index]; 1576 } 1577 1578 empty_entry: 1579 if (insert == NO_INSERT) 1580 return NULL; 1581 1582 if (first_deleted_slot) 1583 { 1584 m_n_deleted--; 1585 mark_empty (*first_deleted_slot); 1586 return first_deleted_slot; 1587 } 1588 1589 m_n_elements++; 1590 return &m_entries[index]; 1591} 1592 1593/* This function deletes an element with the given COMPARABLE value 1594 from hash table starting with the given HASH. If there is no 1595 matching element in the hash table, this function does nothing. */ 1596 1597template<typename Descriptor, template<typename Type> class Allocator> 1598void 1599hash_table<Descriptor, Allocator, true> 1600::remove_elt_with_hash (const compare_type &comparable, hashval_t hash) 1601{ 1602 value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT); 1603 if (is_empty (*slot)) 1604 return; 1605 1606 Descriptor::remove (*slot); 1607 1608 mark_deleted (*slot); 1609 m_n_deleted++; 1610} 1611 1612/* This function scans over the entire hash table calling CALLBACK for 1613 each live entry. If CALLBACK returns false, the iteration stops. 1614 ARGUMENT is passed as CALLBACK's second argument. */ 1615 1616template<typename Descriptor, 1617 template<typename Type> class Allocator> 1618template<typename Argument, 1619 int (*Callback) (typename hash_table<Descriptor, Allocator, 1620 true>::value_type *slot, 1621 Argument argument)> 1622void 1623hash_table<Descriptor, Allocator, true>::traverse_noresize (Argument argument) 1624{ 1625 value_type *slot = m_entries; 1626 value_type *limit = slot + size (); 1627 1628 do 1629 { 1630 value_type &x = *slot; 1631 1632 if (!is_empty (x) && !is_deleted (x)) 1633 if (! Callback (slot, argument)) 1634 break; 1635 } 1636 while (++slot < limit); 1637} 1638 1639/* Like traverse_noresize, but does resize the table when it is too empty 1640 to improve effectivity of subsequent calls. */ 1641 1642template <typename Descriptor, 1643 template <typename Type> class Allocator> 1644template <typename Argument, 1645 int (*Callback) (typename hash_table<Descriptor, Allocator, 1646 true>::value_type *slot, 1647 Argument argument)> 1648void 1649hash_table<Descriptor, Allocator, true>::traverse (Argument argument) 1650{ 1651 size_t size = m_size; 1652 if (elements () * 8 < size && size > 32) 1653 expand (); 1654 1655 traverse_noresize <Argument, Callback> (argument); 1656} 1657 1658/* Slide down the iterator slots until an active entry is found. */ 1659 1660template<typename Descriptor, template<typename Type> class Allocator> 1661void 1662hash_table<Descriptor, Allocator, true>::iterator::slide () 1663{ 1664 for ( ; m_slot < m_limit; ++m_slot ) 1665 { 1666 value_type &x = *m_slot; 1667 if (!is_empty (x) && !is_deleted (x)) 1668 return; 1669 } 1670 m_slot = NULL; 1671 m_limit = NULL; 1672} 1673 1674/* Bump the iterator. */ 1675 1676template<typename Descriptor, template<typename Type> class Allocator> 1677inline typename hash_table<Descriptor, Allocator, true>::iterator & 1678hash_table<Descriptor, Allocator, true>::iterator::operator ++ () 1679{ 1680 ++m_slot; 1681 slide (); 1682 return *this; 1683} 1684 1685 1686/* Iterate through the elements of hash_table HTAB, 1687 using hash_table <....>::iterator ITER, 1688 storing each element in RESULT, which is of type TYPE. */ 1689 1690#define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \ 1691 for ((ITER) = (HTAB).begin (); \ 1692 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \ 1693 ++(ITER)) 1694 1695/* ggc walking routines. */ 1696 1697template<typename E> 1698static inline void 1699gt_ggc_mx (hash_table<E> *h) 1700{ 1701 typedef hash_table<E> table; 1702 1703 if (!ggc_test_and_set_mark (h->m_entries)) 1704 return; 1705 1706 for (size_t i = 0; i < h->m_size; i++) 1707 { 1708 if (table::is_empty (h->m_entries[i]) 1709 || table::is_deleted (h->m_entries[i])) 1710 continue; 1711 1712 E::ggc_mx (h->m_entries[i]); 1713 } 1714} 1715 1716template<typename D> 1717static inline void 1718hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op, 1719 void *cookie) 1720{ 1721 hash_table<D> *map = static_cast<hash_table<D> *> (h); 1722 gcc_checking_assert (map->m_entries == obj); 1723 for (size_t i = 0; i < map->m_size; i++) 1724 { 1725 typedef hash_table<D> table; 1726 if (table::is_empty (map->m_entries[i]) 1727 || table::is_deleted (map->m_entries[i])) 1728 continue; 1729 1730 D::pch_nx (map->m_entries[i], op, cookie); 1731 } 1732} 1733 1734template<typename D> 1735static void 1736gt_pch_nx (hash_table<D> *h) 1737{ 1738 bool success 1739 = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>); 1740 gcc_checking_assert (success); 1741 for (size_t i = 0; i < h->m_size; i++) 1742 { 1743 if (hash_table<D>::is_empty (h->m_entries[i]) 1744 || hash_table<D>::is_deleted (h->m_entries[i])) 1745 continue; 1746 1747 D::pch_nx (h->m_entries[i]); 1748 } 1749} 1750 1751template<typename D> 1752static inline void 1753gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie) 1754{ 1755 op (&h->m_entries, cookie); 1756} 1757 1758template<typename H> 1759inline void 1760gt_cleare_cache (hash_table<H> *h) 1761{ 1762 if (!h) 1763 return; 1764 1765 for (typename hash_table<H>::iterator iter = h->begin (); iter != h->end (); 1766 ++iter) 1767 H::handle_cache_entry (*iter); 1768} 1769 1770#endif /* TYPED_HASHTAB_H */ 1771