annotate gcc/hash-table.h @ 16:04ced10e8804

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