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