|
111
|
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 E::ggc_mx (h->m_entries[i]);
|
|
|
1048 }
|
|
|
1049 }
|
|
|
1050
|
|
|
1051 template<typename D>
|
|
|
1052 static inline void
|
|
|
1053 hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op,
|
|
|
1054 void *cookie)
|
|
|
1055 {
|
|
|
1056 hash_table<D> *map = static_cast<hash_table<D> *> (h);
|
|
|
1057 gcc_checking_assert (map->m_entries == obj);
|
|
|
1058 for (size_t i = 0; i < map->m_size; i++)
|
|
|
1059 {
|
|
|
1060 typedef hash_table<D> table;
|
|
|
1061 if (table::is_empty (map->m_entries[i])
|
|
|
1062 || table::is_deleted (map->m_entries[i]))
|
|
|
1063 continue;
|
|
|
1064
|
|
|
1065 D::pch_nx (map->m_entries[i], op, cookie);
|
|
|
1066 }
|
|
|
1067 }
|
|
|
1068
|
|
|
1069 template<typename D>
|
|
|
1070 static void
|
|
|
1071 gt_pch_nx (hash_table<D> *h)
|
|
|
1072 {
|
|
|
1073 bool success
|
|
|
1074 = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>);
|
|
|
1075 gcc_checking_assert (success);
|
|
|
1076 for (size_t i = 0; i < h->m_size; i++)
|
|
|
1077 {
|
|
|
1078 if (hash_table<D>::is_empty (h->m_entries[i])
|
|
|
1079 || hash_table<D>::is_deleted (h->m_entries[i]))
|
|
|
1080 continue;
|
|
|
1081
|
|
|
1082 D::pch_nx (h->m_entries[i]);
|
|
|
1083 }
|
|
|
1084 }
|
|
|
1085
|
|
|
1086 template<typename D>
|
|
|
1087 static inline void
|
|
|
1088 gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie)
|
|
|
1089 {
|
|
|
1090 op (&h->m_entries, cookie);
|
|
|
1091 }
|
|
|
1092
|
|
|
1093 template<typename H>
|
|
|
1094 inline void
|
|
|
1095 gt_cleare_cache (hash_table<H> *h)
|
|
|
1096 {
|
|
|
1097 extern void gt_ggc_mx (typename H::value_type &t);
|
|
|
1098 typedef hash_table<H> table;
|
|
|
1099 if (!h)
|
|
|
1100 return;
|
|
|
1101
|
|
|
1102 for (typename table::iterator iter = h->begin (); iter != h->end (); ++iter)
|
|
|
1103 if (!table::is_empty (*iter) && !table::is_deleted (*iter))
|
|
|
1104 {
|
|
|
1105 int res = H::keep_cache_entry (*iter);
|
|
|
1106 if (res == 0)
|
|
|
1107 h->clear_slot (&*iter);
|
|
|
1108 else if (res != -1)
|
|
|
1109 gt_ggc_mx (*iter);
|
|
|
1110 }
|
|
|
1111 }
|
|
|
1112
|
|
|
1113 #endif /* TYPED_HASHTAB_H */
|
