annotate gcc/hash-table.h @ 145:1830386684a0

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