1 /* A type-safe hash table template. 2 Copyright (C) 2012-2018 Free Software Foundation, Inc. 3 Contributed by Lawrence Crowl <crowl@google.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along 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 (or 'const value_type &') and returns a hashval_t value. 41 42 - A typedef named 'compare_type' that is used to test when a 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 and a compare_type, and returns a bool. Both arguments can be 49 const references. 50 51 - A static function named 'remove' that takes an value_type pointer 52 and frees the memory allocated by it. This function is used when 53 individual elements of the table need to be disposed of (e.g., 54 when deleting a hash table, removing elements from the table, etc). 55 56 - An optional static function named 'keep_cache_entry'. This 57 function is provided only for garbage-collected elements that 58 are not marked by the normal gc mark pass. It describes what 59 what should happen to the element at the end of the gc mark phase. 60 The return value should be: 61 - 0 if the element should be deleted 62 - 1 if the element should be kept and needs to be marked 63 - -1 if the element should be kept and is already marked. 64 Returning -1 rather than 1 is purely an optimization. 65 66 3. The type of the hash table itself. (More later.) 67 68 In very special circumstances, users may need to know about a fourth type. 69 70 4. The template type used to describe how hash table memory 71 is allocated. This type is called the allocator type. It is 72 parameterized on the value type. It provides two functions: 73 74 - A static member function named 'data_alloc'. This function 75 allocates the data elements in the table. 76 77 - A static member function named 'data_free'. This function 78 deallocates the data elements in the table. 79 80 Hash table are instantiated with two type arguments. 81 82 * The descriptor type, (2) above. 83 84 * The allocator type, (4) above. In general, you will not need to 85 provide your own allocator type. By default, hash tables will use 86 the class template xcallocator, which uses malloc/free for allocation. 87 88 89 DEFINING A DESCRIPTOR TYPE 90 91 The first task in using the hash table is to describe the element type. 92 We compose this into a few steps. 93 94 1. Decide on a removal policy for values stored in the table. 95 hash-traits.h provides class templates for the four most common 96 policies: 97 98 * typed_free_remove implements the static 'remove' member function 99 by calling free(). 100 101 * typed_noop_remove implements the static 'remove' member function 102 by doing nothing. 103 104 * ggc_remove implements the static 'remove' member by doing nothing, 105 but instead provides routines for gc marking and for PCH streaming. 106 Use this for garbage-collected data that needs to be preserved across 107 collections. 108 109 * ggc_cache_remove is like ggc_remove, except that it does not 110 mark the entries during the normal gc mark phase. Instead it 111 uses 'keep_cache_entry' (described above) to keep elements that 112 were not collected and delete those that were. Use this for 113 garbage-collected caches that should not in themselves stop 114 the data from being collected. 115 116 You can use these policies by simply deriving the descriptor type 117 from one of those class template, with the appropriate argument. 118 119 Otherwise, you need to write the static 'remove' member function 120 in the descriptor class. 121 122 2. Choose a hash function. Write the static 'hash' member function. 123 124 3. Decide whether the lookup function should take as input an object 125 of type value_type or something more restricted. Define compare_type 126 accordingly. 127 128 4. Choose an equality testing function 'equal' that compares a value_type 129 and a compare_type. 130 131 If your elements are pointers, it is usually easiest to start with one 132 of the generic pointer descriptors described below and override the bits 133 you need to change. 134 135 AN EXAMPLE DESCRIPTOR TYPE 136 137 Suppose you want to put some_type into the hash table. You could define 138 the descriptor type as follows. 139 140 struct some_type_hasher : nofree_ptr_hash <some_type> 141 // Deriving from nofree_ptr_hash means that we get a 'remove' that does 142 // nothing. This choice is good for raw values. 143 { 144 static inline hashval_t hash (const value_type *); 145 static inline bool equal (const value_type *, const compare_type *); 146 }; 147 148 inline hashval_t 149 some_type_hasher::hash (const value_type *e) 150 { ... compute and return a hash value for E ... } 151 152 inline bool 153 some_type_hasher::equal (const value_type *p1, const compare_type *p2) 154 { ... compare P1 vs P2. Return true if they are the 'same' ... } 155 156 157 AN EXAMPLE HASH_TABLE DECLARATION 158 159 To instantiate a hash table for some_type: 160 161 hash_table <some_type_hasher> some_type_hash_table; 162 163 There is no need to mention some_type directly, as the hash table will 164 obtain it using some_type_hasher::value_type. 165 166 You can then use any of the functions in hash_table's public interface. 167 See hash_table for details. The interface is very similar to libiberty's 168 htab_t. 169 170 171 EASY DESCRIPTORS FOR POINTERS 172 173 There are four descriptors for pointer elements, one for each of 174 the removal policies above: 175 176 * nofree_ptr_hash (based on typed_noop_remove) 177 * free_ptr_hash (based on typed_free_remove) 178 * ggc_ptr_hash (based on ggc_remove) 179 * ggc_cache_ptr_hash (based on ggc_cache_remove) 180 181 These descriptors hash and compare elements by their pointer value, 182 rather than what they point to. So, to instantiate a hash table over 183 pointers to whatever_type, without freeing the whatever_types, use: 184 185 hash_table <nofree_ptr_hash <whatever_type> > whatever_type_hash_table; 186 187 188 HASH TABLE ITERATORS 189 190 The hash table provides standard C++ iterators. For example, consider a 191 hash table of some_info. We wish to consume each element of the table: 192 193 extern void consume (some_info *); 194 195 We define a convenience typedef and the hash table: 196 197 typedef hash_table <some_info_hasher> info_table_type; 198 info_table_type info_table; 199 200 Then we write the loop in typical C++ style: 201 202 for (info_table_type::iterator iter = info_table.begin (); 203 iter != info_table.end (); 204 ++iter) 205 if ((*iter).status == INFO_READY) 206 consume (&*iter); 207 208 Or with common sub-expression elimination: 209 210 for (info_table_type::iterator iter = info_table.begin (); 211 iter != info_table.end (); 212 ++iter) 213 { 214 some_info &elem = *iter; 215 if (elem.status == INFO_READY) 216 consume (&elem); 217 } 218 219 One can also use a more typical GCC style: 220 221 typedef some_info *some_info_p; 222 some_info *elem_ptr; 223 info_table_type::iterator iter; 224 FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter) 225 if (elem_ptr->status == INFO_READY) 226 consume (elem_ptr); 227 228 */ 229 230 231 #ifndef TYPED_HASHTAB_H 232 #define TYPED_HASHTAB_H 233 234 #include "statistics.h" 235 #include "ggc.h" 236 #include "vec.h" 237 #include "hashtab.h" 238 #include "inchash.h" 239 #include "mem-stats-traits.h" 240 #include "hash-traits.h" 241 #include "hash-map-traits.h" 242 243 template<typename, typename, typename> class hash_map; 244 template<typename, typename> class hash_set; 245 246 /* The ordinary memory allocator. */ 247 /* FIXME (crowl): This allocator may be extracted for wider sharing later. */ 248 249 template <typename Type> 250 struct xcallocator 251 { 252 static Type *data_alloc (size_t count); 253 static void data_free (Type *memory); 254 }; 255 256 257 /* Allocate memory for COUNT data blocks. */ 258 259 template <typename Type> 260 inline Type * 261 xcallocator <Type>::data_alloc (size_t count) 262 { 263 return static_cast <Type *> (xcalloc (count, sizeof (Type))); 264 } 265 266 267 /* Free memory for data blocks. */ 268 269 template <typename Type> 270 inline void 271 xcallocator <Type>::data_free (Type *memory) 272 { 273 return ::free (memory); 274 } 275 276 277 /* Table of primes and their inversion information. */ 278 279 struct prime_ent 280 { 281 hashval_t prime; 282 hashval_t inv; 283 hashval_t inv_m2; /* inverse of prime-2 */ 284 hashval_t shift; 285 }; 286 287 extern struct prime_ent const prime_tab[]; 288 289 290 /* Functions for computing hash table indexes. */ 291 292 extern unsigned int hash_table_higher_prime_index (unsigned long n) 293 ATTRIBUTE_PURE; 294 295 /* Return X % Y using multiplicative inverse values INV and SHIFT. 296 297 The multiplicative inverses computed above are for 32-bit types, 298 and requires that we be able to compute a highpart multiply. 299 300 FIX: I am not at all convinced that 301 3 loads, 2 multiplications, 3 shifts, and 3 additions 302 will be faster than 303 1 load and 1 modulus 304 on modern systems running a compiler. */ 305 306 inline hashval_t 307 mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift) 308 { 309 hashval_t t1, t2, t3, t4, q, r; 310 311 t1 = ((uint64_t)x * inv) >> 32; 312 t2 = x - t1; 313 t3 = t2 >> 1; 314 t4 = t1 + t3; 315 q = t4 >> shift; 316 r = x - (q * y); 317 318 return r; 319 } 320 321 /* Compute the primary table index for HASH given current prime index. */ 322 323 inline hashval_t 324 hash_table_mod1 (hashval_t hash, unsigned int index) 325 { 326 const struct prime_ent *p = &prime_tab[index]; 327 gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32); 328 return mul_mod (hash, p->prime, p->inv, p->shift); 329 } 330 331 /* Compute the secondary table index for HASH given current prime index. */ 332 333 inline hashval_t 334 hash_table_mod2 (hashval_t hash, unsigned int index) 335 { 336 const struct prime_ent *p = &prime_tab[index]; 337 gcc_checking_assert (sizeof (hashval_t) * CHAR_BIT <= 32); 338 return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift); 339 } 340 341 class mem_usage; 342 343 /* User-facing hash table type. 344 345 The table stores elements of type Descriptor::value_type and uses 346 the static descriptor functions described at the top of the file 347 to hash, compare and remove elements. 348 349 Specify the template Allocator to allocate and free memory. 350 The default is xcallocator. 351 352 Storage is an implementation detail and should not be used outside the 353 hash table code. 354 355 */ 356 template <typename Descriptor, 357 template<typename Type> class Allocator = xcallocator> 358 class hash_table 359 { 360 typedef typename Descriptor::value_type value_type; 361 typedef typename Descriptor::compare_type compare_type; 362 363 public: 364 explicit hash_table (size_t, bool ggc = false, 365 bool gather_mem_stats = GATHER_STATISTICS, 366 mem_alloc_origin origin = HASH_TABLE_ORIGIN 367 CXX_MEM_STAT_INFO); 368 explicit hash_table (const hash_table &, bool ggc = false, 369 bool gather_mem_stats = GATHER_STATISTICS, 370 mem_alloc_origin origin = HASH_TABLE_ORIGIN 371 CXX_MEM_STAT_INFO); 372 ~hash_table (); 373 374 /* Create a hash_table in gc memory. */ 375 static hash_table * 376 create_ggc (size_t n CXX_MEM_STAT_INFO) 377 { 378 hash_table *table = ggc_alloc<hash_table> (); 379 new (table) hash_table (n, true, GATHER_STATISTICS, 380 HASH_TABLE_ORIGIN PASS_MEM_STAT); 381 return table; 382 } 383 384 /* Current size (in entries) of the hash table. */ 385 size_t size () const { return m_size; } 386 387 /* Return the current number of elements in this hash table. */ 388 size_t elements () const { return m_n_elements - m_n_deleted; } 389 390 /* Return the current number of elements in this hash table. */ 391 size_t elements_with_deleted () const { return m_n_elements; } 392 393 /* This function clears all entries in this hash table. */ 394 void empty () { if (elements ()) empty_slow (); } 395 396 /* This function clears a specified SLOT in a hash table. It is 397 useful when you've already done the lookup and don't want to do it 398 again. */ 399 void clear_slot (value_type *); 400 401 /* This function searches for a hash table entry equal to the given 402 COMPARABLE element starting with the given HASH value. It cannot 403 be used to insert or delete an element. */ 404 value_type &find_with_hash (const compare_type &, hashval_t); 405 406 /* Like find_slot_with_hash, but compute the hash value from the element. */ 407 value_type &find (const value_type &value) 408 { 409 return find_with_hash (value, Descriptor::hash (value)); 410 } 411 412 value_type *find_slot (const value_type &value, insert_option insert) 413 { 414 return find_slot_with_hash (value, Descriptor::hash (value), insert); 415 } 416 417 /* This function searches for a hash table slot containing an entry 418 equal to the given COMPARABLE element and starting with the given 419 HASH. To delete an entry, call this with insert=NO_INSERT, then 420 call clear_slot on the slot returned (possibly after doing some 421 checks). To insert an entry, call this with insert=INSERT, then 422 write the value you want into the returned slot. When inserting an 423 entry, NULL may be returned if memory allocation fails. */ 424 value_type *find_slot_with_hash (const compare_type &comparable, 425 hashval_t hash, enum insert_option insert); 426 427 /* This function deletes an element with the given COMPARABLE value 428 from hash table starting with the given HASH. If there is no 429 matching element in the hash table, this function does nothing. */ 430 void remove_elt_with_hash (const compare_type &, hashval_t); 431 432 /* Like remove_elt_with_hash, but compute the hash value from the 433 element. */ 434 void remove_elt (const value_type &value) 435 { 436 remove_elt_with_hash (value, Descriptor::hash (value)); 437 } 438 439 /* This function scans over the entire hash table calling CALLBACK for 440 each live entry. If CALLBACK returns false, the iteration stops. 441 ARGUMENT is passed as CALLBACK's second argument. */ 442 template <typename Argument, 443 int (*Callback) (value_type *slot, Argument argument)> 444 void traverse_noresize (Argument argument); 445 446 /* Like traverse_noresize, but does resize the table when it is too empty 447 to improve effectivity of subsequent calls. */ 448 template <typename Argument, 449 int (*Callback) (value_type *slot, Argument argument)> 450 void traverse (Argument argument); 451 452 class iterator 453 { 454 public: 455 iterator () : m_slot (NULL), m_limit (NULL) {} 456 457 iterator (value_type *slot, value_type *limit) : 458 m_slot (slot), m_limit (limit) {} 459 460 inline value_type &operator * () { return *m_slot; } 461 void slide (); 462 inline iterator &operator ++ (); 463 bool operator != (const iterator &other) const 464 { 465 return m_slot != other.m_slot || m_limit != other.m_limit; 466 } 467 468 private: 469 value_type *m_slot; 470 value_type *m_limit; 471 }; 472 473 iterator begin () const 474 { 475 iterator iter (m_entries, m_entries + m_size); 476 iter.slide (); 477 return iter; 478 } 479 480 iterator end () const { return iterator (); } 481 482 double collisions () const 483 { 484 return m_searches ? static_cast <double> (m_collisions) / m_searches : 0; 485 } 486 487 private: 488 template<typename T> friend void gt_ggc_mx (hash_table<T> *); 489 template<typename T> friend void gt_pch_nx (hash_table<T> *); 490 template<typename T> friend void 491 hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *); 492 template<typename T, typename U, typename V> friend void 493 gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *); 494 template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *, 495 gt_pointer_operator, 496 void *); 497 template<typename T> friend void gt_pch_nx (hash_table<T> *, 498 gt_pointer_operator, void *); 499 500 template<typename T> friend void gt_cleare_cache (hash_table<T> *); 501 502 void empty_slow (); 503 504 value_type *alloc_entries (size_t n CXX_MEM_STAT_INFO) const; 505 value_type *find_empty_slot_for_expand (hashval_t); 506 bool too_empty_p (unsigned int); 507 void expand (); 508 static bool is_deleted (value_type &v) 509 { 510 return Descriptor::is_deleted (v); 511 } 512 513 static bool is_empty (value_type &v) 514 { 515 return Descriptor::is_empty (v); 516 } 517 518 static void mark_deleted (value_type &v) 519 { 520 Descriptor::mark_deleted (v); 521 } 522 523 static void mark_empty (value_type &v) 524 { 525 Descriptor::mark_empty (v); 526 } 527 528 /* Table itself. */ 529 typename Descriptor::value_type *m_entries; 530 531 size_t m_size; 532 533 /* Current number of elements including also deleted elements. */ 534 size_t m_n_elements; 535 536 /* Current number of deleted elements in the table. */ 537 size_t m_n_deleted; 538 539 /* The following member is used for debugging. Its value is number 540 of all calls of `htab_find_slot' for the hash table. */ 541 unsigned int m_searches; 542 543 /* The following member is used for debugging. Its value is number 544 of collisions fixed for time of work with the hash table. */ 545 unsigned int m_collisions; 546 547 /* Current size (in entries) of the hash table, as an index into the 548 table of primes. */ 549 unsigned int m_size_prime_index; 550 551 /* if m_entries is stored in ggc memory. */ 552 bool m_ggc; 553 554 /* If we should gather memory statistics for the table. */ 555 bool m_gather_mem_stats; 556 }; 557 558 /* As mem-stats.h heavily utilizes hash maps (hash tables), we have to include 559 mem-stats.h after hash_table declaration. */ 560 561 #include "mem-stats.h" 562 #include "hash-map.h" 563 564 extern mem_alloc_description<mem_usage> hash_table_usage; 565 566 /* Support function for statistics. */ 567 extern void dump_hash_table_loc_statistics (void); 568 569 template<typename Descriptor, template<typename Type> class Allocator> 570 hash_table<Descriptor, Allocator>::hash_table (size_t size, bool ggc, bool 571 gather_mem_stats, 572 mem_alloc_origin origin 573 MEM_STAT_DECL) : 574 m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0), 575 m_ggc (ggc), m_gather_mem_stats (gather_mem_stats) 576 { 577 unsigned int size_prime_index; 578 579 size_prime_index = hash_table_higher_prime_index (size); 580 size = prime_tab[size_prime_index].prime; 581 582 if (m_gather_mem_stats) 583 hash_table_usage.register_descriptor (this, origin, ggc 584 FINAL_PASS_MEM_STAT); 585 586 m_entries = alloc_entries (size PASS_MEM_STAT); 587 m_size = size; 588 m_size_prime_index = size_prime_index; 589 } 590 591 template<typename Descriptor, template<typename Type> class Allocator> 592 hash_table<Descriptor, Allocator>::hash_table (const hash_table &h, bool ggc, 593 bool gather_mem_stats, 594 mem_alloc_origin origin 595 MEM_STAT_DECL) : 596 m_n_elements (h.m_n_elements), m_n_deleted (h.m_n_deleted), 597 m_searches (0), m_collisions (0), m_ggc (ggc), 598 m_gather_mem_stats (gather_mem_stats) 599 { 600 size_t size = h.m_size; 601 602 if (m_gather_mem_stats) 603 hash_table_usage.register_descriptor (this, origin, ggc 604 FINAL_PASS_MEM_STAT); 605 606 value_type *nentries = alloc_entries (size PASS_MEM_STAT); 607 for (size_t i = 0; i < size; ++i) 608 { 609 value_type &entry = h.m_entries[i]; 610 if (is_deleted (entry)) 611 mark_deleted (nentries[i]); 612 else if (!is_empty (entry)) 613 nentries[i] = entry; 614 } 615 m_entries = nentries; 616 m_size = size; 617 m_size_prime_index = h.m_size_prime_index; 618 } 619 620 template<typename Descriptor, template<typename Type> class Allocator> 621 hash_table<Descriptor, Allocator>::~hash_table () 622 { 623 for (size_t i = m_size - 1; i < m_size; i--) 624 if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i])) 625 Descriptor::remove (m_entries[i]); 626 627 if (!m_ggc) 628 Allocator <value_type> ::data_free (m_entries); 629 else 630 ggc_free (m_entries); 631 632 if (m_gather_mem_stats) 633 hash_table_usage.release_instance_overhead (this, 634 sizeof (value_type) * m_size, 635 true); 636 } 637 638 /* This function returns an array of empty hash table elements. */ 639 640 template<typename Descriptor, template<typename Type> class Allocator> 641 inline typename hash_table<Descriptor, Allocator>::value_type * 642 hash_table<Descriptor, Allocator>::alloc_entries (size_t n MEM_STAT_DECL) const 643 { 644 value_type *nentries; 645 646 if (m_gather_mem_stats) 647 hash_table_usage.register_instance_overhead (sizeof (value_type) * n, this); 648 649 if (!m_ggc) 650 nentries = Allocator <value_type> ::data_alloc (n); 651 else 652 nentries = ::ggc_cleared_vec_alloc<value_type> (n PASS_MEM_STAT); 653 654 gcc_assert (nentries != NULL); 655 for (size_t i = 0; i < n; i++) 656 mark_empty (nentries[i]); 657 658 return nentries; 659 } 660 661 /* Similar to find_slot, but without several unwanted side effects: 662 - Does not call equal when it finds an existing entry. 663 - Does not change the count of elements/searches/collisions in the 664 hash table. 665 This function also assumes there are no deleted entries in the table. 666 HASH is the hash value for the element to be inserted. */ 667 668 template<typename Descriptor, template<typename Type> class Allocator> 669 typename hash_table<Descriptor, Allocator>::value_type * 670 hash_table<Descriptor, Allocator>::find_empty_slot_for_expand (hashval_t hash) 671 { 672 hashval_t index = hash_table_mod1 (hash, m_size_prime_index); 673 size_t size = m_size; 674 value_type *slot = m_entries + index; 675 hashval_t hash2; 676 677 if (is_empty (*slot)) 678 return slot; 679 gcc_checking_assert (!is_deleted (*slot)); 680 681 hash2 = hash_table_mod2 (hash, m_size_prime_index); 682 for (;;) 683 { 684 index += hash2; 685 if (index >= size) 686 index -= size; 687 688 slot = m_entries + index; 689 if (is_empty (*slot)) 690 return slot; 691 gcc_checking_assert (!is_deleted (*slot)); 692 } 693 } 694 695 /* Return true if the current table is excessively big for ELTS elements. */ 696 697 template<typename Descriptor, template<typename Type> class Allocator> 698 inline bool 699 hash_table<Descriptor, Allocator>::too_empty_p (unsigned int elts) 700 { 701 return elts * 8 < m_size && m_size > 32; 702 } 703 704 /* The following function changes size of memory allocated for the 705 entries and repeatedly inserts the table elements. The occupancy 706 of the table after the call will be about 50%. Naturally the hash 707 table must already exist. Remember also that the place of the 708 table entries is changed. If memory allocation fails, this function 709 will abort. */ 710 711 template<typename Descriptor, template<typename Type> class Allocator> 712 void 713 hash_table<Descriptor, Allocator>::expand () 714 { 715 value_type *oentries = m_entries; 716 unsigned int oindex = m_size_prime_index; 717 size_t osize = size (); 718 value_type *olimit = oentries + osize; 719 size_t elts = elements (); 720 721 /* Resize only when table after removal of unused elements is either 722 too full or too empty. */ 723 unsigned int nindex; 724 size_t nsize; 725 if (elts * 2 > osize || too_empty_p (elts)) 726 { 727 nindex = hash_table_higher_prime_index (elts * 2); 728 nsize = prime_tab[nindex].prime; 729 } 730 else 731 { 732 nindex = oindex; 733 nsize = osize; 734 } 735 736 value_type *nentries = alloc_entries (nsize); 737 738 if (m_gather_mem_stats) 739 hash_table_usage.release_instance_overhead (this, sizeof (value_type) 740 * osize); 741 742 m_entries = nentries; 743 m_size = nsize; 744 m_size_prime_index = nindex; 745 m_n_elements -= m_n_deleted; 746 m_n_deleted = 0; 747 748 value_type *p = oentries; 749 do 750 { 751 value_type &x = *p; 752 753 if (!is_empty (x) && !is_deleted (x)) 754 { 755 value_type *q = find_empty_slot_for_expand (Descriptor::hash (x)); 756 757 *q = x; 758 } 759 760 p++; 761 } 762 while (p < olimit); 763 764 if (!m_ggc) 765 Allocator <value_type> ::data_free (oentries); 766 else 767 ggc_free (oentries); 768 } 769 770 /* Implements empty() in cases where it isn't a no-op. */ 771 772 template<typename Descriptor, template<typename Type> class Allocator> 773 void 774 hash_table<Descriptor, Allocator>::empty_slow () 775 { 776 size_t size = m_size; 777 size_t nsize = size; 778 value_type *entries = m_entries; 779 int i; 780 781 for (i = size - 1; i >= 0; i--) 782 if (!is_empty (entries[i]) && !is_deleted (entries[i])) 783 Descriptor::remove (entries[i]); 784 785 /* Instead of clearing megabyte, downsize the table. */ 786 if (size > 1024*1024 / sizeof (value_type)) 787 nsize = 1024 / sizeof (value_type); 788 else if (too_empty_p (m_n_elements)) 789 nsize = m_n_elements * 2; 790 791 if (nsize != size) 792 { 793 int nindex = hash_table_higher_prime_index (nsize); 794 int nsize = prime_tab[nindex].prime; 795 796 if (!m_ggc) 797 Allocator <value_type> ::data_free (m_entries); 798 else 799 ggc_free (m_entries); 800 801 m_entries = alloc_entries (nsize); 802 m_size = nsize; 803 m_size_prime_index = nindex; 804 } 805 else 806 { 807 #ifndef BROKEN_VALUE_INITIALIZATION 808 for ( ; size; ++entries, --size) 809 *entries = value_type (); 810 #else 811 memset (entries, 0, size * sizeof (value_type)); 812 #endif 813 } 814 m_n_deleted = 0; 815 m_n_elements = 0; 816 } 817 818 /* This function clears a specified SLOT in a hash table. It is 819 useful when you've already done the lookup and don't want to do it 820 again. */ 821 822 template<typename Descriptor, template<typename Type> class Allocator> 823 void 824 hash_table<Descriptor, Allocator>::clear_slot (value_type *slot) 825 { 826 gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size () 827 || is_empty (*slot) || is_deleted (*slot))); 828 829 Descriptor::remove (*slot); 830 831 mark_deleted (*slot); 832 m_n_deleted++; 833 } 834 835 /* This function searches for a hash table entry equal to the given 836 COMPARABLE element starting with the given HASH value. It cannot 837 be used to insert or delete an element. */ 838 839 template<typename Descriptor, template<typename Type> class Allocator> 840 typename hash_table<Descriptor, Allocator>::value_type & 841 hash_table<Descriptor, Allocator> 842 ::find_with_hash (const compare_type &comparable, hashval_t hash) 843 { 844 m_searches++; 845 size_t size = m_size; 846 hashval_t index = hash_table_mod1 (hash, m_size_prime_index); 847 848 value_type *entry = &m_entries[index]; 849 if (is_empty (*entry) 850 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable))) 851 return *entry; 852 853 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); 854 for (;;) 855 { 856 m_collisions++; 857 index += hash2; 858 if (index >= size) 859 index -= size; 860 861 entry = &m_entries[index]; 862 if (is_empty (*entry) 863 || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable))) 864 return *entry; 865 } 866 } 867 868 /* This function searches for a hash table slot containing an entry 869 equal to the given COMPARABLE element and starting with the given 870 HASH. To delete an entry, call this with insert=NO_INSERT, then 871 call clear_slot on the slot returned (possibly after doing some 872 checks). To insert an entry, call this with insert=INSERT, then 873 write the value you want into the returned slot. When inserting an 874 entry, NULL may be returned if memory allocation fails. */ 875 876 template<typename Descriptor, template<typename Type> class Allocator> 877 typename hash_table<Descriptor, Allocator>::value_type * 878 hash_table<Descriptor, Allocator> 879 ::find_slot_with_hash (const compare_type &comparable, hashval_t hash, 880 enum insert_option insert) 881 { 882 if (insert == INSERT && m_size * 3 <= m_n_elements * 4) 883 expand (); 884 885 m_searches++; 886 887 value_type *first_deleted_slot = NULL; 888 hashval_t index = hash_table_mod1 (hash, m_size_prime_index); 889 hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); 890 value_type *entry = &m_entries[index]; 891 size_t size = m_size; 892 if (is_empty (*entry)) 893 goto empty_entry; 894 else if (is_deleted (*entry)) 895 first_deleted_slot = &m_entries[index]; 896 else if (Descriptor::equal (*entry, comparable)) 897 return &m_entries[index]; 898 899 for (;;) 900 { 901 m_collisions++; 902 index += hash2; 903 if (index >= size) 904 index -= size; 905 906 entry = &m_entries[index]; 907 if (is_empty (*entry)) 908 goto empty_entry; 909 else if (is_deleted (*entry)) 910 { 911 if (!first_deleted_slot) 912 first_deleted_slot = &m_entries[index]; 913 } 914 else if (Descriptor::equal (*entry, comparable)) 915 return &m_entries[index]; 916 } 917 918 empty_entry: 919 if (insert == NO_INSERT) 920 return NULL; 921 922 if (first_deleted_slot) 923 { 924 m_n_deleted--; 925 mark_empty (*first_deleted_slot); 926 return first_deleted_slot; 927 } 928 929 m_n_elements++; 930 return &m_entries[index]; 931 } 932 933 /* This function deletes an element with the given COMPARABLE value 934 from hash table starting with the given HASH. If there is no 935 matching element in the hash table, this function does nothing. */ 936 937 template<typename Descriptor, template<typename Type> class Allocator> 938 void 939 hash_table<Descriptor, Allocator> 940 ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash) 941 { 942 value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT); 943 if (is_empty (*slot)) 944 return; 945 946 Descriptor::remove (*slot); 947 948 mark_deleted (*slot); 949 m_n_deleted++; 950 } 951 952 /* This function scans over the entire hash table calling CALLBACK for 953 each live entry. If CALLBACK returns false, the iteration stops. 954 ARGUMENT is passed as CALLBACK's second argument. */ 955 956 template<typename Descriptor, 957 template<typename Type> class Allocator> 958 template<typename Argument, 959 int (*Callback) 960 (typename hash_table<Descriptor, Allocator>::value_type *slot, 961 Argument argument)> 962 void 963 hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument) 964 { 965 value_type *slot = m_entries; 966 value_type *limit = slot + size (); 967 968 do 969 { 970 value_type &x = *slot; 971 972 if (!is_empty (x) && !is_deleted (x)) 973 if (! Callback (slot, argument)) 974 break; 975 } 976 while (++slot < limit); 977 } 978 979 /* Like traverse_noresize, but does resize the table when it is too empty 980 to improve effectivity of subsequent calls. */ 981 982 template <typename Descriptor, 983 template <typename Type> class Allocator> 984 template <typename Argument, 985 int (*Callback) 986 (typename hash_table<Descriptor, Allocator>::value_type *slot, 987 Argument argument)> 988 void 989 hash_table<Descriptor, Allocator>::traverse (Argument argument) 990 { 991 if (too_empty_p (elements ())) 992 expand (); 993 994 traverse_noresize <Argument, Callback> (argument); 995 } 996 997 /* Slide down the iterator slots until an active entry is found. */ 998 999 template<typename Descriptor, template<typename Type> class Allocator> 1000 void 1001 hash_table<Descriptor, Allocator>::iterator::slide () 1002 { 1003 for ( ; m_slot < m_limit; ++m_slot ) 1004 { 1005 value_type &x = *m_slot; 1006 if (!is_empty (x) && !is_deleted (x)) 1007 return; 1008 } 1009 m_slot = NULL; 1010 m_limit = NULL; 1011 } 1012 1013 /* Bump the iterator. */ 1014 1015 template<typename Descriptor, template<typename Type> class Allocator> 1016 inline typename hash_table<Descriptor, Allocator>::iterator & 1017 hash_table<Descriptor, Allocator>::iterator::operator ++ () 1018 { 1019 ++m_slot; 1020 slide (); 1021 return *this; 1022 } 1023 1024 1025 /* Iterate through the elements of hash_table HTAB, 1026 using hash_table <....>::iterator ITER, 1027 storing each element in RESULT, which is of type TYPE. */ 1028 1029 #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \ 1030 for ((ITER) = (HTAB).begin (); \ 1031 (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \ 1032 ++(ITER)) 1033 1034 /* ggc walking routines. */ 1035 1036 template<typename E> 1037 static inline void 1038 gt_ggc_mx (hash_table<E> *h) 1039 { 1040 typedef hash_table<E> table; 1041 1042 if (!ggc_test_and_set_mark (h->m_entries)) 1043 return; 1044 1045 for (size_t i = 0; i < h->m_size; i++) 1046 { 1047 if (table::is_empty (h->m_entries[i]) 1048 || table::is_deleted (h->m_entries[i])) 1049 continue; 1050 1051 /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll 1052 mark in gt_cleare_cache if appropriate. */ 1053 E::ggc_maybe_mx (h->m_entries[i]); 1054 } 1055 } 1056 1057 template<typename D> 1058 static inline void 1059 hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op, 1060 void *cookie) 1061 { 1062 hash_table<D> *map = static_cast<hash_table<D> *> (h); 1063 gcc_checking_assert (map->m_entries == obj); 1064 for (size_t i = 0; i < map->m_size; i++) 1065 { 1066 typedef hash_table<D> table; 1067 if (table::is_empty (map->m_entries[i]) 1068 || table::is_deleted (map->m_entries[i])) 1069 continue; 1070 1071 D::pch_nx (map->m_entries[i], op, cookie); 1072 } 1073 } 1074 1075 template<typename D> 1076 static void 1077 gt_pch_nx (hash_table<D> *h) 1078 { 1079 bool success 1080 = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>); 1081 gcc_checking_assert (success); 1082 for (size_t i = 0; i < h->m_size; i++) 1083 { 1084 if (hash_table<D>::is_empty (h->m_entries[i]) 1085 || hash_table<D>::is_deleted (h->m_entries[i])) 1086 continue; 1087 1088 D::pch_nx (h->m_entries[i]); 1089 } 1090 } 1091 1092 template<typename D> 1093 static inline void 1094 gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie) 1095 { 1096 op (&h->m_entries, cookie); 1097 } 1098 1099 template<typename H> 1100 inline void 1101 gt_cleare_cache (hash_table<H> *h) 1102 { 1103 typedef hash_table<H> table; 1104 if (!h) 1105 return; 1106 1107 for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter) 1108 if (!table::is_empty (*iter) && !table::is_deleted (*iter)) 1109 { 1110 int res = H::keep_cache_entry (*iter); 1111 if (res == 0) 1112 h->clear_slot (&*iter); 1113 else if (res != -1) 1114 H::ggc_mx (*iter); 1115 } 1116 } 1117 1118 #endif /* TYPED_HASHTAB_H */ 1119