1 | /* A type-safe hash table template. |
---|---|

2 | Copyright (C) 2012-2017 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 | for ( ; size; ++entries, --size) |

808 | *entries = value_type (); |

809 | } |

810 | m_n_deleted = 0; |

811 | m_n_elements = 0; |

812 | } |

813 | |

814 | /* This function clears a specified SLOT in a hash table. It is |

815 | useful when you've already done the lookup and don't want to do it |

816 | again. */ |

817 | |

818 | template<typename Descriptor, template<typename Type> class Allocator> |

819 | void |

820 | hash_table<Descriptor, Allocator>::clear_slot (value_type *slot) |

821 | { |

822 | gcc_checking_assert (!(slot < m_entries || slot >= m_entries + size () |

823 | || is_empty (*slot) || is_deleted (*slot))); |

824 | |

825 | Descriptor::remove (*slot); |

826 | |

827 | mark_deleted (*slot); |

828 | m_n_deleted++; |

829 | } |

830 | |

831 | /* This function searches for a hash table entry equal to the given |

832 | COMPARABLE element starting with the given HASH value. It cannot |

833 | be used to insert or delete an element. */ |

834 | |

835 | template<typename Descriptor, template<typename Type> class Allocator> |

836 | typename hash_table<Descriptor, Allocator>::value_type & |

837 | hash_table<Descriptor, Allocator> |

838 | ::find_with_hash (const compare_type &comparable, hashval_t hash) |

839 | { |

840 | m_searches++; |

841 | size_t size = m_size; |

842 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); |

843 | |

844 | value_type *entry = &m_entries[index]; |

845 | if (is_empty (*entry) |

846 | || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable))) |

847 | return *entry; |

848 | |

849 | hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); |

850 | for (;;) |

851 | { |

852 | m_collisions++; |

853 | index += hash2; |

854 | if (index >= size) |

855 | index -= size; |

856 | |

857 | entry = &m_entries[index]; |

858 | if (is_empty (*entry) |

859 | || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable))) |

860 | return *entry; |

861 | } |

862 | } |

863 | |

864 | /* This function searches for a hash table slot containing an entry |

865 | equal to the given COMPARABLE element and starting with the given |

866 | HASH. To delete an entry, call this with insert=NO_INSERT, then |

867 | call clear_slot on the slot returned (possibly after doing some |

868 | checks). To insert an entry, call this with insert=INSERT, then |

869 | write the value you want into the returned slot. When inserting an |

870 | entry, NULL may be returned if memory allocation fails. */ |

871 | |

872 | template<typename Descriptor, template<typename Type> class Allocator> |

873 | typename hash_table<Descriptor, Allocator>::value_type * |

874 | hash_table<Descriptor, Allocator> |

875 | ::find_slot_with_hash (const compare_type &comparable, hashval_t hash, |

876 | enum insert_option insert) |

877 | { |

878 | if (insert == INSERT && m_size * 3 <= m_n_elements * 4) |

879 | expand (); |

880 | |

881 | m_searches++; |

882 | |

883 | value_type *first_deleted_slot = NULL; |

884 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); |

885 | hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); |

886 | value_type *entry = &m_entries[index]; |

887 | size_t size = m_size; |

888 | if (is_empty (*entry)) |

889 | goto empty_entry; |

890 | else if (is_deleted (*entry)) |

891 | first_deleted_slot = &m_entries[index]; |

892 | else if (Descriptor::equal (*entry, comparable)) |

893 | return &m_entries[index]; |

894 | |

895 | for (;;) |

896 | { |

897 | m_collisions++; |

898 | index += hash2; |

899 | if (index >= size) |

900 | index -= size; |

901 | |

902 | entry = &m_entries[index]; |

903 | if (is_empty (*entry)) |

904 | goto empty_entry; |

905 | else if (is_deleted (*entry)) |

906 | { |

907 | if (!first_deleted_slot) |

908 | first_deleted_slot = &m_entries[index]; |

909 | } |

910 | else if (Descriptor::equal (*entry, comparable)) |

911 | return &m_entries[index]; |

912 | } |

913 | |

914 | empty_entry: |

915 | if (insert == NO_INSERT) |

916 | return NULL; |

917 | |

918 | if (first_deleted_slot) |

919 | { |

920 | m_n_deleted--; |

921 | mark_empty (*first_deleted_slot); |

922 | return first_deleted_slot; |

923 | } |

924 | |

925 | m_n_elements++; |

926 | return &m_entries[index]; |

927 | } |

928 | |

929 | /* This function deletes an element with the given COMPARABLE value |

930 | from hash table starting with the given HASH. If there is no |

931 | matching element in the hash table, this function does nothing. */ |

932 | |

933 | template<typename Descriptor, template<typename Type> class Allocator> |

934 | void |

935 | hash_table<Descriptor, Allocator> |

936 | ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash) |

937 | { |

938 | value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT); |

939 | if (is_empty (*slot)) |

940 | return; |

941 | |

942 | Descriptor::remove (*slot); |

943 | |

944 | mark_deleted (*slot); |

945 | m_n_deleted++; |

946 | } |

947 | |

948 | /* This function scans over the entire hash table calling CALLBACK for |

949 | each live entry. If CALLBACK returns false, the iteration stops. |

950 | ARGUMENT is passed as CALLBACK's second argument. */ |

951 | |

952 | template<typename Descriptor, |

953 | template<typename Type> class Allocator> |

954 | template<typename Argument, |

955 | int (*Callback) |

956 | (typename hash_table<Descriptor, Allocator>::value_type *slot, |

957 | Argument argument)> |

958 | void |

959 | hash_table<Descriptor, Allocator>::traverse_noresize (Argument argument) |

960 | { |

961 | value_type *slot = m_entries; |

962 | value_type *limit = slot + size (); |

963 | |

964 | do |

965 | { |

966 | value_type &x = *slot; |

967 | |

968 | if (!is_empty (x) && !is_deleted (x)) |

969 | if (! Callback (slot, argument)) |

970 | break; |

971 | } |

972 | while (++slot < limit); |

973 | } |

974 | |

975 | /* Like traverse_noresize, but does resize the table when it is too empty |

976 | to improve effectivity of subsequent calls. */ |

977 | |

978 | template <typename Descriptor, |

979 | template <typename Type> class Allocator> |

980 | template <typename Argument, |

981 | int (*Callback) |

982 | (typename hash_table<Descriptor, Allocator>::value_type *slot, |

983 | Argument argument)> |

984 | void |

985 | hash_table<Descriptor, Allocator>::traverse (Argument argument) |

986 | { |

987 | if (too_empty_p (elements ())) |

988 | expand (); |

989 | |

990 | traverse_noresize <Argument, Callback> (argument); |

991 | } |

992 | |

993 | /* Slide down the iterator slots until an active entry is found. */ |

994 | |

995 | template<typename Descriptor, template<typename Type> class Allocator> |

996 | void |

997 | hash_table<Descriptor, Allocator>::iterator::slide () |

998 | { |

999 | for ( ; m_slot < m_limit; ++m_slot ) |

1000 | { |

1001 | value_type &x = *m_slot; |

1002 | if (!is_empty (x) && !is_deleted (x)) |

1003 | return; |

1004 | } |

1005 | m_slot = NULL; |

1006 | m_limit = NULL; |

1007 | } |

1008 | |

1009 | /* Bump the iterator. */ |

1010 | |

1011 | template<typename Descriptor, template<typename Type> class Allocator> |

1012 | inline typename hash_table<Descriptor, Allocator>::iterator & |

1013 | hash_table<Descriptor, Allocator>::iterator::operator ++ () |

1014 | { |

1015 | ++m_slot; |

1016 | slide (); |

1017 | return *this; |

1018 | } |

1019 | |

1020 | |

1021 | /* Iterate through the elements of hash_table HTAB, |

1022 | using hash_table <....>::iterator ITER, |

1023 | storing each element in RESULT, which is of type TYPE. */ |

1024 | |

1025 | #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \ |

1026 | for ((ITER) = (HTAB).begin (); \ |

1027 | (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \ |

1028 | ++(ITER)) |

1029 | |

1030 | /* ggc walking routines. */ |

1031 | |

1032 | template<typename E> |

1033 | static inline void |

1034 | gt_ggc_mx (hash_table<E> *h) |

1035 | { |

1036 | typedef hash_table<E> table; |

1037 | |

1038 | if (!ggc_test_and_set_mark (h->m_entries)) |

1039 | return; |

1040 | |

1041 | for (size_t i = 0; i < h->m_size; i++) |

1042 | { |

1043 | if (table::is_empty (h->m_entries[i]) |

1044 | || table::is_deleted (h->m_entries[i])) |

1045 | continue; |

1046 | |

1047 | /* Use ggc_maxbe_mx so we don't mark right away for cache tables; we'll |

1048 | mark in gt_cleare_cache if appropriate. */ |

1049 | E::ggc_maybe_mx (h->m_entries[i]); |

1050 | } |

1051 | } |

1052 | |

1053 | template<typename D> |

1054 | static inline void |

1055 | hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op, |

1056 | void *cookie) |

1057 | { |

1058 | hash_table<D> *map = static_cast<hash_table<D> *> (h); |

1059 | gcc_checking_assert (map->m_entries == obj); |

1060 | for (size_t i = 0; i < map->m_size; i++) |

1061 | { |

1062 | typedef hash_table<D> table; |

1063 | if (table::is_empty (map->m_entries[i]) |

1064 | || table::is_deleted (map->m_entries[i])) |

1065 | continue; |

1066 | |

1067 | D::pch_nx (map->m_entries[i], op, cookie); |

1068 | } |

1069 | } |

1070 | |

1071 | template<typename D> |

1072 | static void |

1073 | gt_pch_nx (hash_table<D> *h) |

1074 | { |

1075 | bool success |

1076 | = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>); |

1077 | gcc_checking_assert (success); |

1078 | for (size_t i = 0; i < h->m_size; i++) |

1079 | { |

1080 | if (hash_table<D>::is_empty (h->m_entries[i]) |

1081 | || hash_table<D>::is_deleted (h->m_entries[i])) |

1082 | continue; |

1083 | |

1084 | D::pch_nx (h->m_entries[i]); |

1085 | } |

1086 | } |

1087 | |

1088 | template<typename D> |

1089 | static inline void |

1090 | gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie) |

1091 | { |

1092 | op (&h->m_entries, cookie); |

1093 | } |

1094 | |

1095 | template<typename H> |

1096 | inline void |

1097 | gt_cleare_cache (hash_table<H> *h) |

1098 | { |

1099 | typedef hash_table<H> table; |

1100 | if (!h) |

1101 | return; |

1102 | |

1103 | for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter) |

1104 | if (!table::is_empty (*iter) && !table::is_deleted (*iter)) |

1105 | { |

1106 | int res = H::keep_cache_entry (*iter); |

1107 | if (res == 0) |

1108 | h->clear_slot (&*iter); |

1109 | else if (res != -1) |

1110 | H::ggc_mx (*iter); |

1111 | } |

1112 | } |

1113 | |

1114 | #endif /* TYPED_HASHTAB_H */ |

1115 |