]>
Commit | Line | Data |
---|---|---|
2b15d2ba | 1 | /* A type-safe hash table template. |
3aea1f79 | 2 | Copyright (C) 2012-2014 Free Software Foundation, Inc. |
2b15d2ba | 3 | Contributed by Lawrence Crowl <crowl@google.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it under | |
8 | the terms of the GNU General Public License as published by the Free | |
9 | Software Foundation; either version 3, or (at your option) any later | |
10 | version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING3. If not see | |
19 | <http://www.gnu.org/licenses/>. */ | |
20 | ||
21 | ||
22 | /* This file implements a typed hash table. | |
c580da87 | 23 | The implementation borrows from libiberty's htab_t in hashtab.h. |
24 | ||
25 | ||
26 | INTRODUCTION TO TYPES | |
27 | ||
28 | Users of the hash table generally need to be aware of three types. | |
29 | ||
30 | 1. The type being placed into the hash table. This type is called | |
31 | the value type. | |
32 | ||
33 | 2. The type used to describe how to handle the value type within | |
34 | the hash table. This descriptor type provides the hash table with | |
35 | several things. | |
36 | ||
37 | - A typedef named 'value_type' to the value type (from above). | |
38 | ||
39 | - A static member function named 'hash' that takes a value_type | |
40 | pointer and returns a hashval_t value. | |
41 | ||
42 | - A typedef named 'compare_type' that is used to test when an value | |
43 | is found. This type is the comparison type. Usually, it will be the | |
44 | same as value_type. If it is not the same type, you must generally | |
45 | explicitly compute hash values and pass them to the hash table. | |
46 | ||
47 | - A static member function named 'equal' that takes a value_type | |
48 | pointer and a compare_type pointer, and returns a bool. | |
49 | ||
50 | - A static function named 'remove' that takes an value_type pointer | |
51 | and frees the memory allocated by it. This function is used when | |
52 | individual elements of the table need to be disposed of (e.g., | |
53 | when deleting a hash table, removing elements from the table, etc). | |
54 | ||
55 | 3. The type of the hash table itself. (More later.) | |
56 | ||
57 | In very special circumstances, users may need to know about a fourth type. | |
58 | ||
59 | 4. The template type used to describe how hash table memory | |
60 | is allocated. This type is called the allocator type. It is | |
61 | parameterized on the value type. It provides four functions. | |
62 | ||
c580da87 | 63 | - A static member function named 'data_alloc'. This function |
64 | allocates the data elements in the table. | |
65 | ||
66 | - A static member function named 'data_free'. This function | |
67 | deallocates the data elements in the table. | |
68 | ||
69 | Hash table are instantiated with two type arguments. | |
70 | ||
71 | * The descriptor type, (2) above. | |
72 | ||
73 | * The allocator type, (4) above. In general, you will not need to | |
74 | provide your own allocator type. By default, hash tables will use | |
75 | the class template xcallocator, which uses malloc/free for allocation. | |
76 | ||
77 | ||
78 | DEFINING A DESCRIPTOR TYPE | |
79 | ||
80 | The first task in using the hash table is to describe the element type. | |
81 | We compose this into a few steps. | |
82 | ||
83 | 1. Decide on a removal policy for values stored in the table. | |
84 | This header provides class templates for the two most common | |
85 | policies. | |
86 | ||
87 | * typed_free_remove implements the static 'remove' member function | |
88 | by calling free(). | |
89 | ||
90 | * typed_noop_remove implements the static 'remove' member function | |
91 | by doing nothing. | |
92 | ||
93 | You can use these policies by simply deriving the descriptor type | |
94 | from one of those class template, with the appropriate argument. | |
95 | ||
96 | Otherwise, you need to write the static 'remove' member function | |
97 | in the descriptor class. | |
98 | ||
99 | 2. Choose a hash function. Write the static 'hash' member function. | |
100 | ||
101 | 3. Choose an equality testing function. In most cases, its two | |
102 | arguments will be value_type pointers. If not, the first argument must | |
103 | be a value_type pointer, and the second argument a compare_type pointer. | |
104 | ||
105 | ||
106 | AN EXAMPLE DESCRIPTOR TYPE | |
107 | ||
108 | Suppose you want to put some_type into the hash table. You could define | |
109 | the descriptor type as follows. | |
110 | ||
111 | struct some_type_hasher : typed_noop_remove <some_type> | |
112 | // Deriving from typed_noop_remove means that we get a 'remove' that does | |
113 | // nothing. This choice is good for raw values. | |
114 | { | |
115 | typedef some_type value_type; | |
116 | typedef some_type compare_type; | |
117 | static inline hashval_t hash (const value_type *); | |
118 | static inline bool equal (const value_type *, const compare_type *); | |
119 | }; | |
120 | ||
121 | inline hashval_t | |
122 | some_type_hasher::hash (const value_type *e) | |
123 | { ... compute and return a hash value for E ... } | |
124 | ||
125 | inline bool | |
126 | some_type_hasher::equal (const value_type *p1, const compare_type *p2) | |
127 | { ... compare P1 vs P2. Return true if they are the 'same' ... } | |
128 | ||
129 | ||
130 | AN EXAMPLE HASH_TABLE DECLARATION | |
131 | ||
132 | To instantiate a hash table for some_type: | |
133 | ||
134 | hash_table <some_type_hasher> some_type_hash_table; | |
135 | ||
136 | There is no need to mention some_type directly, as the hash table will | |
137 | obtain it using some_type_hasher::value_type. | |
138 | ||
139 | You can then used any of the functions in hash_table's public interface. | |
140 | See hash_table for details. The interface is very similar to libiberty's | |
141 | htab_t. | |
142 | ||
143 | ||
144 | EASY DESCRIPTORS FOR POINTERS | |
145 | ||
146 | The class template pointer_hash provides everything you need to hash | |
147 | pointers (as opposed to what they point to). So, to instantiate a hash | |
148 | table over pointers to whatever_type, | |
149 | ||
150 | hash_table <pointer_hash <whatever_type>> whatever_type_hash_table; | |
151 | ||
3e871d4d | 152 | |
153 | HASH TABLE ITERATORS | |
154 | ||
155 | The hash table provides standard C++ iterators. For example, consider a | |
156 | hash table of some_info. We wish to consume each element of the table: | |
157 | ||
158 | extern void consume (some_info *); | |
159 | ||
160 | We define a convenience typedef and the hash table: | |
161 | ||
162 | typedef hash_table <some_info_hasher> info_table_type; | |
163 | info_table_type info_table; | |
164 | ||
165 | Then we write the loop in typical C++ style: | |
166 | ||
167 | for (info_table_type::iterator iter = info_table.begin (); | |
168 | iter != info_table.end (); | |
169 | ++iter) | |
170 | if ((*iter).status == INFO_READY) | |
171 | consume (&*iter); | |
172 | ||
173 | Or with common sub-expression elimination: | |
174 | ||
175 | for (info_table_type::iterator iter = info_table.begin (); | |
176 | iter != info_table.end (); | |
177 | ++iter) | |
178 | { | |
179 | some_info &elem = *iter; | |
180 | if (elem.status == INFO_READY) | |
181 | consume (&elem); | |
182 | } | |
183 | ||
184 | One can also use a more typical GCC style: | |
185 | ||
186 | typedef some_info *some_info_p; | |
187 | some_info *elem_ptr; | |
188 | info_table_type::iterator iter; | |
189 | FOR_EACH_HASH_TABLE_ELEMENT (info_table, elem_ptr, some_info_p, iter) | |
190 | if (elem_ptr->status == INFO_READY) | |
191 | consume (elem_ptr); | |
192 | ||
c580da87 | 193 | */ |
2b15d2ba | 194 | |
195 | ||
196 | #ifndef TYPED_HASHTAB_H | |
197 | #define TYPED_HASHTAB_H | |
198 | ||
8f359205 | 199 | #include "ggc.h" |
2b15d2ba | 200 | #include "hashtab.h" |
2ef51f0e | 201 | #include <new> |
2b15d2ba | 202 | |
8f359205 | 203 | template<typename, typename, typename> class hash_map; |
204 | template<typename, typename> class hash_set; | |
2b15d2ba | 205 | |
206 | /* The ordinary memory allocator. */ | |
207 | /* FIXME (crowl): This allocator may be extracted for wider sharing later. */ | |
208 | ||
209 | template <typename Type> | |
210 | struct xcallocator | |
211 | { | |
2b15d2ba | 212 | static Type *data_alloc (size_t count); |
2b15d2ba | 213 | static void data_free (Type *memory); |
214 | }; | |
215 | ||
216 | ||
c580da87 | 217 | /* Allocate memory for COUNT data blocks. */ |
2b15d2ba | 218 | |
219 | template <typename Type> | |
220 | inline Type * | |
221 | xcallocator <Type>::data_alloc (size_t count) | |
222 | { | |
223 | return static_cast <Type *> (xcalloc (count, sizeof (Type))); | |
224 | } | |
225 | ||
226 | ||
2b15d2ba | 227 | /* Free memory for data blocks. */ |
228 | ||
229 | template <typename Type> | |
230 | inline void | |
231 | xcallocator <Type>::data_free (Type *memory) | |
232 | { | |
233 | return ::free (memory); | |
234 | } | |
235 | ||
236 | ||
c580da87 | 237 | /* Helpful type for removing with free. */ |
2b15d2ba | 238 | |
c580da87 | 239 | template <typename Type> |
494bbaae | 240 | struct typed_free_remove |
2b15d2ba | 241 | { |
c580da87 | 242 | static inline void remove (Type *p); |
494bbaae | 243 | }; |
2b15d2ba | 244 | |
2b15d2ba | 245 | |
c580da87 | 246 | /* Remove with free. */ |
247 | ||
248 | template <typename Type> | |
249 | inline void | |
250 | typed_free_remove <Type>::remove (Type *p) | |
251 | { | |
252 | free (p); | |
253 | } | |
254 | ||
255 | ||
256 | /* Helpful type for a no-op remove. */ | |
257 | ||
258 | template <typename Type> | |
494bbaae | 259 | struct typed_noop_remove |
2b15d2ba | 260 | { |
c580da87 | 261 | static inline void remove (Type *p); |
494bbaae | 262 | }; |
2b15d2ba | 263 | |
264 | ||
c580da87 | 265 | /* Remove doing nothing. */ |
266 | ||
267 | template <typename Type> | |
268 | inline void | |
269 | typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED) | |
270 | { | |
271 | } | |
272 | ||
273 | ||
494bbaae | 274 | /* Pointer hash with a no-op remove method. */ |
2b15d2ba | 275 | |
c580da87 | 276 | template <typename Type> |
277 | struct pointer_hash : typed_noop_remove <Type> | |
2b15d2ba | 278 | { |
2933f7af | 279 | typedef Type *value_type; |
280 | typedef Type *compare_type; | |
281 | typedef int store_values_directly; | |
2b15d2ba | 282 | |
2933f7af | 283 | static inline hashval_t hash (const value_type &); |
2b15d2ba | 284 | |
2933f7af | 285 | static inline bool equal (const value_type &existing, const compare_type &candidate); |
494bbaae | 286 | }; |
2b15d2ba | 287 | |
c580da87 | 288 | template <typename Type> |
494bbaae | 289 | inline hashval_t |
2933f7af | 290 | pointer_hash <Type>::hash (const value_type &candidate) |
494bbaae | 291 | { |
292 | /* This is a really poor hash function, but it is what the current code uses, | |
293 | so I am reusing it to avoid an additional axis in testing. */ | |
294 | return (hashval_t) ((intptr_t)candidate >> 3); | |
295 | } | |
296 | ||
c580da87 | 297 | template <typename Type> |
2933f7af | 298 | inline bool |
299 | pointer_hash <Type>::equal (const value_type &existing, | |
300 | const compare_type &candidate) | |
2b15d2ba | 301 | { |
494bbaae | 302 | return existing == candidate; |
2b15d2ba | 303 | } |
304 | ||
2ef51f0e | 305 | /* Hasher for entry in gc memory. */ |
306 | ||
307 | template<typename T> | |
308 | struct ggc_hasher | |
309 | { | |
310 | typedef T value_type; | |
311 | typedef T compare_type; | |
312 | typedef int store_values_directly; | |
313 | ||
314 | static void remove (T) {} | |
315 | ||
316 | static void | |
317 | ggc_mx (T p) | |
318 | { | |
319 | extern void gt_ggc_mx (T &); | |
320 | gt_ggc_mx (p); | |
321 | } | |
322 | ||
323 | static void | |
324 | pch_nx (T &p) | |
325 | { | |
326 | extern void gt_pch_nx (T &); | |
327 | gt_pch_nx (p); | |
328 | } | |
329 | ||
330 | static void | |
331 | pch_nx (T &p, gt_pointer_operator op, void *cookie) | |
332 | { | |
333 | op (&p, cookie); | |
334 | } | |
335 | }; | |
336 | ||
2b15d2ba | 337 | |
338 | /* Table of primes and their inversion information. */ | |
339 | ||
340 | struct prime_ent | |
341 | { | |
342 | hashval_t prime; | |
343 | hashval_t inv; | |
344 | hashval_t inv_m2; /* inverse of prime-2 */ | |
345 | hashval_t shift; | |
346 | }; | |
347 | ||
348 | extern struct prime_ent const prime_tab[]; | |
349 | ||
350 | ||
351 | /* Functions for computing hash table indexes. */ | |
352 | ||
353 | extern unsigned int hash_table_higher_prime_index (unsigned long n); | |
354 | extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index); | |
355 | extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index); | |
356 | ||
2933f7af | 357 | /* The below is some template meta programming to decide if we should use the |
358 | hash table partial specialization that directly stores value_type instead of | |
359 | pointers to value_type. If the Descriptor type defines the type | |
360 | Descriptor::store_values_directly then values are stored directly otherwise | |
361 | pointers to them are stored. */ | |
362 | template<typename T> struct notype { typedef void type; }; | |
363 | ||
364 | template<typename T, typename = void> | |
365 | struct storage_tester | |
366 | { | |
367 | static const bool value = false; | |
368 | }; | |
369 | ||
370 | template<typename T> | |
371 | struct storage_tester<T, typename notype<typename | |
372 | T::store_values_directly>::type> | |
373 | { | |
374 | static const bool value = true; | |
375 | }; | |
376 | ||
377 | template<typename Traits> | |
378 | struct has_is_deleted | |
379 | { | |
380 | template<typename U, bool (*)(U &)> struct helper {}; | |
381 | template<typename U> static char test (helper<U, U::is_deleted> *); | |
382 | template<typename U> static int test (...); | |
383 | static const bool value = sizeof (test<Traits> (0)) == sizeof (char); | |
384 | }; | |
385 | ||
386 | template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> | |
387 | struct is_deleted_helper | |
388 | { | |
389 | static inline bool | |
390 | call (Type &v) | |
391 | { | |
392 | return Traits::is_deleted (v); | |
393 | } | |
394 | }; | |
395 | ||
396 | template<typename Type, typename Traits> | |
397 | struct is_deleted_helper<Type *, Traits, false> | |
398 | { | |
399 | static inline bool | |
400 | call (Type *v) | |
401 | { | |
402 | return v == HTAB_DELETED_ENTRY; | |
403 | } | |
404 | }; | |
405 | ||
406 | template<typename Traits> | |
407 | struct has_is_empty | |
408 | { | |
409 | template<typename U, bool (*)(U &)> struct helper {}; | |
410 | template<typename U> static char test (helper<U, U::is_empty> *); | |
411 | template<typename U> static int test (...); | |
412 | static const bool value = sizeof (test<Traits> (0)) == sizeof (char); | |
413 | }; | |
414 | ||
415 | template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> | |
416 | struct is_empty_helper | |
417 | { | |
418 | static inline bool | |
419 | call (Type &v) | |
420 | { | |
421 | return Traits::is_empty (v); | |
422 | } | |
423 | }; | |
424 | ||
425 | template<typename Type, typename Traits> | |
426 | struct is_empty_helper<Type *, Traits, false> | |
427 | { | |
428 | static inline bool | |
429 | call (Type *v) | |
430 | { | |
431 | return v == HTAB_EMPTY_ENTRY; | |
432 | } | |
433 | }; | |
434 | ||
435 | template<typename Traits> | |
436 | struct has_mark_deleted | |
437 | { | |
438 | template<typename U, void (*)(U &)> struct helper {}; | |
439 | template<typename U> static char test (helper<U, U::mark_deleted> *); | |
440 | template<typename U> static int test (...); | |
441 | static const bool value = sizeof (test<Traits> (0)) == sizeof (char); | |
442 | }; | |
443 | ||
444 | template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> | |
445 | struct mark_deleted_helper | |
446 | { | |
447 | static inline void | |
448 | call (Type &v) | |
449 | { | |
450 | Traits::mark_deleted (v); | |
451 | } | |
452 | }; | |
453 | ||
454 | template<typename Type, typename Traits> | |
455 | struct mark_deleted_helper<Type *, Traits, false> | |
456 | { | |
457 | static inline void | |
458 | call (Type *&v) | |
459 | { | |
460 | v = static_cast<Type *> (HTAB_DELETED_ENTRY); | |
461 | } | |
462 | }; | |
463 | ||
464 | template<typename Traits> | |
465 | struct has_mark_empty | |
466 | { | |
467 | template<typename U, void (*)(U &)> struct helper {}; | |
468 | template<typename U> static char test (helper<U, U::mark_empty> *); | |
469 | template<typename U> static int test (...); | |
470 | static const bool value = sizeof (test<Traits> (0)) == sizeof (char); | |
471 | }; | |
472 | ||
473 | template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> | |
474 | struct mark_empty_helper | |
475 | { | |
476 | static inline void | |
477 | call (Type &v) | |
478 | { | |
479 | Traits::mark_empty (v); | |
480 | } | |
481 | }; | |
482 | ||
483 | template<typename Type, typename Traits> | |
484 | struct mark_empty_helper<Type *, Traits, false> | |
485 | { | |
486 | static inline void | |
487 | call (Type *&v) | |
488 | { | |
489 | v = static_cast<Type *> (HTAB_EMPTY_ENTRY); | |
490 | } | |
491 | }; | |
2b15d2ba | 492 | |
2b15d2ba | 493 | /* User-facing hash table type. |
494 | ||
2933f7af | 495 | The table stores elements of type Descriptor::value_type, or pointers to |
496 | objects of type value_type if the descriptor does not define the type | |
497 | store_values_directly. | |
2b15d2ba | 498 | |
c580da87 | 499 | It hashes values with the hash member function. |
2b15d2ba | 500 | The table currently works with relatively weak hash functions. |
c580da87 | 501 | Use typed_pointer_hash <Value> when hashing pointers instead of objects. |
2b15d2ba | 502 | |
c580da87 | 503 | It compares elements with the equal member function. |
2b15d2ba | 504 | Two elements with the same hash may not be equal. |
c580da87 | 505 | Use typed_pointer_equal <Value> when hashing pointers instead of objects. |
2b15d2ba | 506 | |
c580da87 | 507 | It removes elements with the remove member function. |
2b15d2ba | 508 | This feature is useful for freeing memory. |
c580da87 | 509 | Derive from typed_null_remove <Value> when not freeing objects. |
510 | Derive from typed_free_remove <Value> when doing a simple object free. | |
2b15d2ba | 511 | |
c580da87 | 512 | Specify the template Allocator to allocate and free memory. |
2b15d2ba | 513 | The default is xcallocator. |
514 | ||
2933f7af | 515 | Storage is an implementation detail and should not be used outside the |
516 | hash table code. | |
517 | ||
2b15d2ba | 518 | */ |
c580da87 | 519 | template <typename Descriptor, |
2933f7af | 520 | template<typename Type> class Allocator= xcallocator, |
521 | bool Storage = storage_tester<Descriptor>::value> | |
2b15d2ba | 522 | class hash_table |
2933f7af | 523 | { |
524 | }; | |
525 | ||
526 | template <typename Descriptor, | |
527 | template<typename Type> class Allocator> | |
528 | class hash_table<Descriptor, Allocator, false> | |
2b15d2ba | 529 | { |
c580da87 | 530 | typedef typename Descriptor::value_type value_type; |
531 | typedef typename Descriptor::compare_type compare_type; | |
2b15d2ba | 532 | |
2b15d2ba | 533 | public: |
c1f445d2 | 534 | hash_table (size_t); |
535 | ~hash_table (); | |
3e871d4d | 536 | |
c1f445d2 | 537 | /* Current size (in entries) of the hash table. */ |
538 | size_t size () const { return m_size; } | |
2b15d2ba | 539 | |
c1f445d2 | 540 | /* Return the current number of elements in this hash table. */ |
541 | size_t elements () const { return m_n_elements - m_n_deleted; } | |
2b15d2ba | 542 | |
c1f445d2 | 543 | /* Return the current number of elements in this hash table. */ |
544 | size_t elements_with_deleted () const { return m_n_elements; } | |
2b15d2ba | 545 | |
c1f445d2 | 546 | /* This function clears all entries in the given hash table. */ |
547 | void empty (); | |
2b15d2ba | 548 | |
c1f445d2 | 549 | /* This function clears a specified SLOT in a hash table. It is |
550 | useful when you've already done the lookup and don't want to do it | |
551 | again. */ | |
2b15d2ba | 552 | |
c1f445d2 | 553 | void clear_slot (value_type **); |
2b15d2ba | 554 | |
c1f445d2 | 555 | /* This function searches for a hash table entry equal to the given |
556 | COMPARABLE element starting with the given HASH value. It cannot | |
557 | be used to insert or delete an element. */ | |
558 | value_type *find_with_hash (const compare_type *, hashval_t); | |
2b15d2ba | 559 | |
c1f445d2 | 560 | /* Like find_slot_with_hash, but compute the hash value from the element. */ |
561 | value_type *find (const value_type *value) | |
562 | { | |
563 | return find_with_hash (value, Descriptor::hash (value)); | |
564 | } | |
2b15d2ba | 565 | |
c1f445d2 | 566 | value_type **find_slot (const value_type *value, insert_option insert) |
567 | { | |
568 | return find_slot_with_hash (value, Descriptor::hash (value), insert); | |
569 | } | |
2b15d2ba | 570 | |
c1f445d2 | 571 | /* This function searches for a hash table slot containing an entry |
572 | equal to the given COMPARABLE element and starting with the given | |
573 | HASH. To delete an entry, call this with insert=NO_INSERT, then | |
574 | call clear_slot on the slot returned (possibly after doing some | |
575 | checks). To insert an entry, call this with insert=INSERT, then | |
576 | write the value you want into the returned slot. When inserting an | |
577 | entry, NULL may be returned if memory allocation fails. */ | |
578 | value_type **find_slot_with_hash (const compare_type *comparable, | |
579 | hashval_t hash, enum insert_option insert); | |
2b15d2ba | 580 | |
c1f445d2 | 581 | /* This function deletes an element with the given COMPARABLE value |
582 | from hash table starting with the given HASH. If there is no | |
583 | matching element in the hash table, this function does nothing. */ | |
584 | void remove_elt_with_hash (const compare_type *, hashval_t); | |
2b15d2ba | 585 | |
c1f445d2 | 586 | /* Like remove_elt_with_hash, but compute the hash value from the element. */ |
587 | void remove_elt (const value_type *value) | |
588 | { | |
589 | remove_elt_with_hash (value, Descriptor::hash (value)); | |
590 | } | |
2b15d2ba | 591 | |
c1f445d2 | 592 | /* This function scans over the entire hash table calling CALLBACK for |
593 | each live entry. If CALLBACK returns false, the iteration stops. | |
594 | ARGUMENT is passed as CALLBACK's second argument. */ | |
595 | template <typename Argument, | |
596 | int (*Callback) (value_type **slot, Argument argument)> | |
597 | void traverse_noresize (Argument argument); | |
2b15d2ba | 598 | |
c1f445d2 | 599 | /* Like traverse_noresize, but does resize the table when it is too empty |
600 | to improve effectivity of subsequent calls. */ | |
601 | template <typename Argument, | |
602 | int (*Callback) (value_type **slot, Argument argument)> | |
603 | void traverse (Argument argument); | |
2b15d2ba | 604 | |
c1f445d2 | 605 | class iterator |
606 | { | |
607 | public: | |
608 | iterator () : m_slot (NULL), m_limit (NULL) {} | |
2b15d2ba | 609 | |
c1f445d2 | 610 | iterator (value_type **slot, value_type **limit) : |
611 | m_slot (slot), m_limit (limit) {} | |
2b15d2ba | 612 | |
2933f7af | 613 | inline value_type *operator * () { return *m_slot; } |
c1f445d2 | 614 | void slide (); |
615 | inline iterator &operator ++ (); | |
616 | bool operator != (const iterator &other) const | |
617 | { | |
618 | return m_slot != other.m_slot || m_limit != other.m_limit; | |
619 | } | |
2b15d2ba | 620 | |
c1f445d2 | 621 | private: |
622 | value_type **m_slot; | |
623 | value_type **m_limit; | |
624 | }; | |
2b15d2ba | 625 | |
c1f445d2 | 626 | iterator begin () const |
627 | { | |
628 | iterator iter (m_entries, m_entries + m_size); | |
629 | iter.slide (); | |
630 | return iter; | |
631 | } | |
2b15d2ba | 632 | |
c1f445d2 | 633 | iterator end () const { return iterator (); } |
2b15d2ba | 634 | |
c1f445d2 | 635 | double collisions () const |
636 | { | |
637 | return m_searches ? static_cast <double> (m_collisions) / m_searches : 0; | |
638 | } | |
2b15d2ba | 639 | |
c1f445d2 | 640 | private: |
2b15d2ba | 641 | |
c1f445d2 | 642 | value_type **find_empty_slot_for_expand (hashval_t); |
643 | void expand (); | |
3e871d4d | 644 | |
c1f445d2 | 645 | /* Table itself. */ |
646 | typename Descriptor::value_type **m_entries; | |
3e871d4d | 647 | |
c1f445d2 | 648 | size_t m_size; |
3e871d4d | 649 | |
c1f445d2 | 650 | /* Current number of elements including also deleted elements. */ |
651 | size_t m_n_elements; | |
2b15d2ba | 652 | |
c1f445d2 | 653 | /* Current number of deleted elements in the table. */ |
654 | size_t m_n_deleted; | |
2b15d2ba | 655 | |
c1f445d2 | 656 | /* The following member is used for debugging. Its value is number |
657 | of all calls of `htab_find_slot' for the hash table. */ | |
658 | unsigned int m_searches; | |
2b15d2ba | 659 | |
c1f445d2 | 660 | /* The following member is used for debugging. Its value is number |
661 | of collisions fixed for time of work with the hash table. */ | |
662 | unsigned int m_collisions; | |
2b15d2ba | 663 | |
c1f445d2 | 664 | /* Current size (in entries) of the hash table, as an index into the |
665 | table of primes. */ | |
666 | unsigned int m_size_prime_index; | |
667 | }; | |
2b15d2ba | 668 | |
c1f445d2 | 669 | template<typename Descriptor, template<typename Type> class Allocator> |
2933f7af | 670 | hash_table<Descriptor, Allocator, false>::hash_table (size_t size) : |
c1f445d2 | 671 | m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0) |
2b15d2ba | 672 | { |
673 | unsigned int size_prime_index; | |
674 | ||
675 | size_prime_index = hash_table_higher_prime_index (size); | |
676 | size = prime_tab[size_prime_index].prime; | |
677 | ||
c1f445d2 | 678 | m_entries = Allocator <value_type*> ::data_alloc (size); |
679 | gcc_assert (m_entries != NULL); | |
680 | m_size = size; | |
681 | m_size_prime_index = size_prime_index; | |
2b15d2ba | 682 | } |
683 | ||
c1f445d2 | 684 | template<typename Descriptor, template<typename Type> class Allocator> |
2933f7af | 685 | hash_table<Descriptor, Allocator, false>::~hash_table () |
2b15d2ba | 686 | { |
c1f445d2 | 687 | for (size_t i = m_size - 1; i < m_size; i--) |
688 | if (m_entries[i] != HTAB_EMPTY_ENTRY && m_entries[i] != HTAB_DELETED_ENTRY) | |
689 | Descriptor::remove (m_entries[i]); | |
2b15d2ba | 690 | |
c1f445d2 | 691 | Allocator <value_type *> ::data_free (m_entries); |
2b15d2ba | 692 | } |
693 | ||
2b15d2ba | 694 | /* Similar to find_slot, but without several unwanted side effects: |
494bbaae | 695 | - Does not call equal when it finds an existing entry. |
2b15d2ba | 696 | - Does not change the count of elements/searches/collisions in the |
697 | hash table. | |
698 | This function also assumes there are no deleted entries in the table. | |
699 | HASH is the hash value for the element to be inserted. */ | |
700 | ||
c1f445d2 | 701 | template<typename Descriptor, template<typename Type> class Allocator> |
0aa6cf04 | 702 | typename hash_table<Descriptor, Allocator, false>::value_type ** |
2933f7af | 703 | hash_table<Descriptor, Allocator, false> |
704 | ::find_empty_slot_for_expand (hashval_t hash) | |
2b15d2ba | 705 | { |
c1f445d2 | 706 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); |
707 | size_t size = m_size; | |
708 | value_type **slot = m_entries + index; | |
2b15d2ba | 709 | hashval_t hash2; |
710 | ||
711 | if (*slot == HTAB_EMPTY_ENTRY) | |
712 | return slot; | |
713 | else if (*slot == HTAB_DELETED_ENTRY) | |
714 | abort (); | |
715 | ||
c1f445d2 | 716 | hash2 = hash_table_mod2 (hash, m_size_prime_index); |
2b15d2ba | 717 | for (;;) |
718 | { | |
719 | index += hash2; | |
720 | if (index >= size) | |
721 | index -= size; | |
722 | ||
c1f445d2 | 723 | slot = m_entries + index; |
2b15d2ba | 724 | if (*slot == HTAB_EMPTY_ENTRY) |
725 | return slot; | |
726 | else if (*slot == HTAB_DELETED_ENTRY) | |
727 | abort (); | |
728 | } | |
729 | } | |
730 | ||
2b15d2ba | 731 | /* The following function changes size of memory allocated for the |
732 | entries and repeatedly inserts the table elements. The occupancy | |
733 | of the table after the call will be about 50%. Naturally the hash | |
734 | table must already exist. Remember also that the place of the | |
735 | table entries is changed. If memory allocation fails, this function | |
736 | will abort. */ | |
737 | ||
c1f445d2 | 738 | template<typename Descriptor, template<typename Type> class Allocator> |
2b15d2ba | 739 | void |
2933f7af | 740 | hash_table<Descriptor, Allocator, false>::expand () |
2b15d2ba | 741 | { |
c1f445d2 | 742 | value_type **oentries = m_entries; |
743 | unsigned int oindex = m_size_prime_index; | |
744 | size_t osize = size (); | |
745 | value_type **olimit = oentries + osize; | |
746 | size_t elts = elements (); | |
2b15d2ba | 747 | |
748 | /* Resize only when table after removal of unused elements is either | |
749 | too full or too empty. */ | |
c1f445d2 | 750 | unsigned int nindex; |
751 | size_t nsize; | |
2b15d2ba | 752 | if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) |
753 | { | |
754 | nindex = hash_table_higher_prime_index (elts * 2); | |
755 | nsize = prime_tab[nindex].prime; | |
756 | } | |
757 | else | |
758 | { | |
759 | nindex = oindex; | |
760 | nsize = osize; | |
761 | } | |
762 | ||
c1f445d2 | 763 | value_type **nentries = Allocator <value_type *> ::data_alloc (nsize); |
2b15d2ba | 764 | gcc_assert (nentries != NULL); |
c1f445d2 | 765 | m_entries = nentries; |
766 | m_size = nsize; | |
767 | m_size_prime_index = nindex; | |
768 | m_n_elements -= m_n_deleted; | |
769 | m_n_deleted = 0; | |
2b15d2ba | 770 | |
c1f445d2 | 771 | value_type **p = oentries; |
2b15d2ba | 772 | do |
773 | { | |
c580da87 | 774 | value_type *x = *p; |
2b15d2ba | 775 | |
776 | if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) | |
777 | { | |
c580da87 | 778 | value_type **q = find_empty_slot_for_expand (Descriptor::hash (x)); |
2b15d2ba | 779 | |
780 | *q = x; | |
781 | } | |
782 | ||
783 | p++; | |
784 | } | |
785 | while (p < olimit); | |
786 | ||
c580da87 | 787 | Allocator <value_type *> ::data_free (oentries); |
2b15d2ba | 788 | } |
789 | ||
c1f445d2 | 790 | template<typename Descriptor, template<typename Type> class Allocator> |
791 | void | |
2933f7af | 792 | hash_table<Descriptor, Allocator, false>::empty () |
c1f445d2 | 793 | { |
794 | size_t size = m_size; | |
795 | value_type **entries = m_entries; | |
796 | int i; | |
797 | ||
798 | for (i = size - 1; i >= 0; i--) | |
799 | if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY) | |
800 | Descriptor::remove (entries[i]); | |
801 | ||
802 | /* Instead of clearing megabyte, downsize the table. */ | |
803 | if (size > 1024*1024 / sizeof (PTR)) | |
804 | { | |
805 | int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR)); | |
806 | int nsize = prime_tab[nindex].prime; | |
807 | ||
808 | Allocator <value_type *> ::data_free (m_entries); | |
809 | m_entries = Allocator <value_type *> ::data_alloc (nsize); | |
810 | m_size = nsize; | |
811 | m_size_prime_index = nindex; | |
812 | } | |
813 | else | |
814 | memset (entries, 0, size * sizeof (value_type *)); | |
815 | m_n_deleted = 0; | |
816 | m_n_elements = 0; | |
817 | } | |
818 | ||
819 | /* This function clears a specified SLOT in a hash table. It is | |
820 | useful when you've already done the lookup and don't want to do it | |
821 | again. */ | |
822 | ||
823 | template<typename Descriptor, template<typename Type> class Allocator> | |
824 | void | |
2933f7af | 825 | hash_table<Descriptor, Allocator, false>::clear_slot (value_type **slot) |
c1f445d2 | 826 | { |
827 | if (slot < m_entries || slot >= m_entries + size () | |
828 | || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY) | |
829 | abort (); | |
830 | ||
831 | Descriptor::remove (*slot); | |
832 | ||
833 | *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); | |
834 | m_n_deleted++; | |
835 | } | |
2b15d2ba | 836 | |
837 | /* This function searches for a hash table entry equal to the given | |
838 | COMPARABLE element starting with the given HASH value. It cannot | |
839 | be used to insert or delete an element. */ | |
840 | ||
c1f445d2 | 841 | template<typename Descriptor, template<typename Type> class Allocator> |
0aa6cf04 | 842 | typename hash_table<Descriptor, Allocator, false>::value_type * |
2933f7af | 843 | hash_table<Descriptor, Allocator, false> |
c580da87 | 844 | ::find_with_hash (const compare_type *comparable, hashval_t hash) |
2b15d2ba | 845 | { |
c1f445d2 | 846 | m_searches++; |
847 | size_t size = m_size; | |
848 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); | |
2b15d2ba | 849 | |
c1f445d2 | 850 | value_type *entry = m_entries[index]; |
2b15d2ba | 851 | if (entry == HTAB_EMPTY_ENTRY |
c580da87 | 852 | || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable))) |
2b15d2ba | 853 | return entry; |
854 | ||
c1f445d2 | 855 | hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); |
2b15d2ba | 856 | for (;;) |
857 | { | |
c1f445d2 | 858 | m_collisions++; |
2b15d2ba | 859 | index += hash2; |
860 | if (index >= size) | |
861 | index -= size; | |
862 | ||
c1f445d2 | 863 | entry = m_entries[index]; |
2b15d2ba | 864 | if (entry == HTAB_EMPTY_ENTRY |
c580da87 | 865 | || (entry != HTAB_DELETED_ENTRY |
866 | && Descriptor::equal (entry, comparable))) | |
2b15d2ba | 867 | return entry; |
868 | } | |
869 | } | |
870 | ||
2b15d2ba | 871 | /* This function searches for a hash table slot containing an entry |
872 | equal to the given COMPARABLE element and starting with the given | |
873 | HASH. To delete an entry, call this with insert=NO_INSERT, then | |
874 | call clear_slot on the slot returned (possibly after doing some | |
875 | checks). To insert an entry, call this with insert=INSERT, then | |
876 | write the value you want into the returned slot. When inserting an | |
877 | entry, NULL may be returned if memory allocation fails. */ | |
878 | ||
c1f445d2 | 879 | template<typename Descriptor, template<typename Type> class Allocator> |
0aa6cf04 | 880 | typename hash_table<Descriptor, Allocator, false>::value_type ** |
2933f7af | 881 | hash_table<Descriptor, Allocator, false> |
c580da87 | 882 | ::find_slot_with_hash (const compare_type *comparable, hashval_t hash, |
2b15d2ba | 883 | enum insert_option insert) |
884 | { | |
c1f445d2 | 885 | if (insert == INSERT && m_size * 3 <= m_n_elements * 4) |
886 | expand (); | |
2b15d2ba | 887 | |
c1f445d2 | 888 | m_searches++; |
2b15d2ba | 889 | |
c1f445d2 | 890 | value_type **first_deleted_slot = NULL; |
891 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); | |
892 | hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); | |
893 | value_type *entry = m_entries[index]; | |
894 | size_t size = m_size; | |
2b15d2ba | 895 | if (entry == HTAB_EMPTY_ENTRY) |
896 | goto empty_entry; | |
897 | else if (entry == HTAB_DELETED_ENTRY) | |
c1f445d2 | 898 | first_deleted_slot = &m_entries[index]; |
c580da87 | 899 | else if (Descriptor::equal (entry, comparable)) |
c1f445d2 | 900 | return &m_entries[index]; |
c580da87 | 901 | |
2b15d2ba | 902 | for (;;) |
903 | { | |
c1f445d2 | 904 | m_collisions++; |
2b15d2ba | 905 | index += hash2; |
906 | if (index >= size) | |
907 | index -= size; | |
c580da87 | 908 | |
c1f445d2 | 909 | entry = m_entries[index]; |
2b15d2ba | 910 | if (entry == HTAB_EMPTY_ENTRY) |
911 | goto empty_entry; | |
912 | else if (entry == HTAB_DELETED_ENTRY) | |
913 | { | |
914 | if (!first_deleted_slot) | |
c1f445d2 | 915 | first_deleted_slot = &m_entries[index]; |
2b15d2ba | 916 | } |
c580da87 | 917 | else if (Descriptor::equal (entry, comparable)) |
c1f445d2 | 918 | return &m_entries[index]; |
2b15d2ba | 919 | } |
920 | ||
921 | empty_entry: | |
922 | if (insert == NO_INSERT) | |
923 | return NULL; | |
924 | ||
925 | if (first_deleted_slot) | |
926 | { | |
c1f445d2 | 927 | m_n_deleted--; |
c580da87 | 928 | *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY); |
2b15d2ba | 929 | return first_deleted_slot; |
930 | } | |
931 | ||
c1f445d2 | 932 | m_n_elements++; |
933 | return &m_entries[index]; | |
2b15d2ba | 934 | } |
935 | ||
2b15d2ba | 936 | /* This function deletes an element with the given COMPARABLE value |
937 | from hash table starting with the given HASH. If there is no | |
938 | matching element in the hash table, this function does nothing. */ | |
939 | ||
c1f445d2 | 940 | template<typename Descriptor, template<typename Type> class Allocator> |
2b15d2ba | 941 | void |
2933f7af | 942 | hash_table<Descriptor, Allocator, false> |
c580da87 | 943 | ::remove_elt_with_hash (const compare_type *comparable, hashval_t hash) |
2b15d2ba | 944 | { |
c1f445d2 | 945 | value_type **slot = find_slot_with_hash (comparable, hash, NO_INSERT); |
2b15d2ba | 946 | if (*slot == HTAB_EMPTY_ENTRY) |
947 | return; | |
948 | ||
c580da87 | 949 | Descriptor::remove (*slot); |
2b15d2ba | 950 | |
c580da87 | 951 | *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); |
c1f445d2 | 952 | m_n_deleted++; |
2b15d2ba | 953 | } |
954 | ||
2b15d2ba | 955 | /* This function scans over the entire hash table calling CALLBACK for |
956 | each live entry. If CALLBACK returns false, the iteration stops. | |
957 | ARGUMENT is passed as CALLBACK's second argument. */ | |
958 | ||
2933f7af | 959 | template<typename Descriptor, template<typename Type> class Allocator> |
c1f445d2 | 960 | template<typename Argument, |
0aa6cf04 | 961 | int (*Callback) (typename hash_table<Descriptor, Allocator, |
962 | false>::value_type **slot, | |
963 | Argument argument)> | |
2b15d2ba | 964 | void |
2933f7af | 965 | hash_table<Descriptor, Allocator, false>::traverse_noresize (Argument argument) |
2b15d2ba | 966 | { |
c1f445d2 | 967 | value_type **slot = m_entries; |
968 | value_type **limit = slot + size (); | |
2b15d2ba | 969 | |
970 | do | |
971 | { | |
c580da87 | 972 | value_type *x = *slot; |
2b15d2ba | 973 | |
974 | if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) | |
975 | if (! Callback (slot, argument)) | |
976 | break; | |
977 | } | |
978 | while (++slot < limit); | |
979 | } | |
980 | ||
2b15d2ba | 981 | /* Like traverse_noresize, but does resize the table when it is too empty |
982 | to improve effectivity of subsequent calls. */ | |
983 | ||
c580da87 | 984 | template <typename Descriptor, |
2b15d2ba | 985 | template <typename Type> class Allocator> |
986 | template <typename Argument, | |
0aa6cf04 | 987 | int (*Callback) (typename hash_table<Descriptor, Allocator, |
988 | false>::value_type **slot, | |
c580da87 | 989 | Argument argument)> |
2b15d2ba | 990 | void |
2933f7af | 991 | hash_table<Descriptor, Allocator, false>::traverse (Argument argument) |
2b15d2ba | 992 | { |
c1f445d2 | 993 | size_t size = m_size; |
2b15d2ba | 994 | if (elements () * 8 < size && size > 32) |
995 | expand (); | |
996 | ||
997 | traverse_noresize <Argument, Callback> (argument); | |
998 | } | |
999 | ||
3e871d4d | 1000 | /* Slide down the iterator slots until an active entry is found. */ |
1001 | ||
c1f445d2 | 1002 | template<typename Descriptor, template<typename Type> class Allocator> |
3e871d4d | 1003 | void |
2933f7af | 1004 | hash_table<Descriptor, Allocator, false>::iterator::slide () |
3e871d4d | 1005 | { |
ae84f584 | 1006 | for ( ; m_slot < m_limit; ++m_slot ) |
3e871d4d | 1007 | { |
ae84f584 | 1008 | value_type *x = *m_slot; |
3e871d4d | 1009 | if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) |
1010 | return; | |
1011 | } | |
ae84f584 | 1012 | m_slot = NULL; |
1013 | m_limit = NULL; | |
3e871d4d | 1014 | } |
1015 | ||
1016 | /* Bump the iterator. */ | |
1017 | ||
c1f445d2 | 1018 | template<typename Descriptor, template<typename Type> class Allocator> |
2933f7af | 1019 | inline typename hash_table<Descriptor, Allocator, false>::iterator & |
1020 | hash_table<Descriptor, Allocator, false>::iterator::operator ++ () | |
1021 | { | |
1022 | ++m_slot; | |
1023 | slide (); | |
1024 | return *this; | |
1025 | } | |
1026 | ||
1027 | /* A partial specialization used when values should be stored directly. */ | |
1028 | ||
1029 | template <typename Descriptor, | |
1030 | template<typename Type> class Allocator> | |
1031 | class hash_table<Descriptor, Allocator, true> | |
1032 | { | |
1033 | typedef typename Descriptor::value_type value_type; | |
1034 | typedef typename Descriptor::compare_type compare_type; | |
1035 | ||
1036 | public: | |
8f359205 | 1037 | explicit hash_table (size_t, bool ggc = false); |
2933f7af | 1038 | ~hash_table (); |
1039 | ||
2ef51f0e | 1040 | /* Create a hash_table in gc memory. */ |
1041 | ||
1042 | static hash_table * | |
1043 | create_ggc (size_t n) | |
1044 | { | |
1045 | hash_table *table = ggc_alloc<hash_table> (); | |
1046 | new (table) hash_table (n, true); | |
1047 | return table; | |
1048 | } | |
1049 | ||
2933f7af | 1050 | /* Current size (in entries) of the hash table. */ |
1051 | size_t size () const { return m_size; } | |
1052 | ||
1053 | /* Return the current number of elements in this hash table. */ | |
1054 | size_t elements () const { return m_n_elements - m_n_deleted; } | |
1055 | ||
1056 | /* Return the current number of elements in this hash table. */ | |
1057 | size_t elements_with_deleted () const { return m_n_elements; } | |
1058 | ||
1059 | /* This function clears all entries in the given hash table. */ | |
1060 | void empty (); | |
1061 | ||
1062 | /* This function clears a specified SLOT in a hash table. It is | |
1063 | useful when you've already done the lookup and don't want to do it | |
1064 | again. */ | |
1065 | ||
1066 | void clear_slot (value_type *); | |
1067 | ||
1068 | /* This function searches for a hash table entry equal to the given | |
1069 | COMPARABLE element starting with the given HASH value. It cannot | |
1070 | be used to insert or delete an element. */ | |
1071 | value_type &find_with_hash (const compare_type &, hashval_t); | |
1072 | ||
1073 | /* Like find_slot_with_hash, but compute the hash value from the element. */ | |
1074 | value_type &find (const value_type &value) | |
1075 | { | |
1076 | return find_with_hash (value, Descriptor::hash (value)); | |
1077 | } | |
1078 | ||
1079 | value_type *find_slot (const value_type &value, insert_option insert) | |
1080 | { | |
1081 | return find_slot_with_hash (value, Descriptor::hash (value), insert); | |
1082 | } | |
1083 | ||
1084 | /* This function searches for a hash table slot containing an entry | |
1085 | equal to the given COMPARABLE element and starting with the given | |
1086 | HASH. To delete an entry, call this with insert=NO_INSERT, then | |
1087 | call clear_slot on the slot returned (possibly after doing some | |
1088 | checks). To insert an entry, call this with insert=INSERT, then | |
1089 | write the value you want into the returned slot. When inserting an | |
1090 | entry, NULL may be returned if memory allocation fails. */ | |
1091 | value_type *find_slot_with_hash (const compare_type &comparable, | |
1092 | hashval_t hash, enum insert_option insert); | |
1093 | ||
1094 | /* This function deletes an element with the given COMPARABLE value | |
1095 | from hash table starting with the given HASH. If there is no | |
1096 | matching element in the hash table, this function does nothing. */ | |
1097 | void remove_elt_with_hash (const compare_type &, hashval_t); | |
1098 | ||
1099 | /* Like remove_elt_with_hash, but compute the hash value from the element. */ | |
1100 | void remove_elt (const value_type &value) | |
1101 | { | |
1102 | remove_elt_with_hash (value, Descriptor::hash (value)); | |
1103 | } | |
1104 | ||
1105 | /* This function scans over the entire hash table calling CALLBACK for | |
1106 | each live entry. If CALLBACK returns false, the iteration stops. | |
1107 | ARGUMENT is passed as CALLBACK's second argument. */ | |
1108 | template <typename Argument, | |
1109 | int (*Callback) (value_type *slot, Argument argument)> | |
1110 | void traverse_noresize (Argument argument); | |
1111 | ||
1112 | /* Like traverse_noresize, but does resize the table when it is too empty | |
1113 | to improve effectivity of subsequent calls. */ | |
1114 | template <typename Argument, | |
1115 | int (*Callback) (value_type *slot, Argument argument)> | |
1116 | void traverse (Argument argument); | |
1117 | ||
1118 | class iterator | |
1119 | { | |
1120 | public: | |
1121 | iterator () : m_slot (NULL), m_limit (NULL) {} | |
1122 | ||
1123 | iterator (value_type *slot, value_type *limit) : | |
1124 | m_slot (slot), m_limit (limit) {} | |
1125 | ||
1126 | inline value_type &operator * () { return *m_slot; } | |
1127 | void slide (); | |
1128 | inline iterator &operator ++ (); | |
1129 | bool operator != (const iterator &other) const | |
1130 | { | |
1131 | return m_slot != other.m_slot || m_limit != other.m_limit; | |
1132 | } | |
1133 | ||
1134 | private: | |
1135 | value_type *m_slot; | |
1136 | value_type *m_limit; | |
1137 | }; | |
1138 | ||
1139 | iterator begin () const | |
1140 | { | |
1141 | iterator iter (m_entries, m_entries + m_size); | |
1142 | iter.slide (); | |
1143 | return iter; | |
1144 | } | |
1145 | ||
1146 | iterator end () const { return iterator (); } | |
1147 | ||
1148 | double collisions () const | |
1149 | { | |
1150 | return m_searches ? static_cast <double> (m_collisions) / m_searches : 0; | |
1151 | } | |
1152 | ||
1153 | private: | |
8f359205 | 1154 | template<typename T> friend void gt_ggc_mx (hash_table<T> *); |
1155 | template<typename T> friend void gt_pch_nx (hash_table<T> *); | |
2ef51f0e | 1156 | template<typename T> friend void |
1157 | hashtab_entry_note_pointers (void *, void *, gt_pointer_operator, void *); | |
1158 | template<typename T, typename U, typename V> friend void | |
1159 | gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *); | |
1160 | template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *, | |
1161 | gt_pointer_operator, | |
1162 | void *); | |
1163 | template<typename T> friend void gt_pch_nx (hash_table<T> *, | |
1164 | gt_pointer_operator, void *); | |
2933f7af | 1165 | |
1166 | value_type *find_empty_slot_for_expand (hashval_t); | |
1167 | void expand (); | |
1168 | static bool is_deleted (value_type &v) | |
1169 | { | |
1170 | return is_deleted_helper<value_type, Descriptor>::call (v); | |
1171 | } | |
1172 | static bool is_empty (value_type &v) | |
1173 | { | |
1174 | return is_empty_helper<value_type, Descriptor>::call (v); | |
1175 | } | |
1176 | ||
1177 | static void mark_deleted (value_type &v) | |
1178 | { | |
1179 | return mark_deleted_helper<value_type, Descriptor>::call (v); | |
1180 | } | |
1181 | ||
1182 | static void mark_empty (value_type &v) | |
1183 | { | |
1184 | return mark_empty_helper<value_type, Descriptor>::call (v); | |
1185 | } | |
1186 | ||
1187 | /* Table itself. */ | |
1188 | typename Descriptor::value_type *m_entries; | |
1189 | ||
1190 | size_t m_size; | |
1191 | ||
1192 | /* Current number of elements including also deleted elements. */ | |
1193 | size_t m_n_elements; | |
1194 | ||
1195 | /* Current number of deleted elements in the table. */ | |
1196 | size_t m_n_deleted; | |
1197 | ||
1198 | /* The following member is used for debugging. Its value is number | |
1199 | of all calls of `htab_find_slot' for the hash table. */ | |
1200 | unsigned int m_searches; | |
1201 | ||
1202 | /* The following member is used for debugging. Its value is number | |
1203 | of collisions fixed for time of work with the hash table. */ | |
1204 | unsigned int m_collisions; | |
1205 | ||
1206 | /* Current size (in entries) of the hash table, as an index into the | |
1207 | table of primes. */ | |
1208 | unsigned int m_size_prime_index; | |
8f359205 | 1209 | |
1210 | /* if m_entries is stored in ggc memory. */ | |
1211 | bool m_ggc; | |
2933f7af | 1212 | }; |
1213 | ||
1214 | template<typename Descriptor, template<typename Type> class Allocator> | |
8f359205 | 1215 | hash_table<Descriptor, Allocator, true>::hash_table (size_t size, bool ggc) : |
1216 | m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0), | |
1217 | m_ggc (ggc) | |
2933f7af | 1218 | { |
1219 | unsigned int size_prime_index; | |
1220 | ||
1221 | size_prime_index = hash_table_higher_prime_index (size); | |
1222 | size = prime_tab[size_prime_index].prime; | |
1223 | ||
8f359205 | 1224 | if (!m_ggc) |
1225 | m_entries = Allocator <value_type> ::data_alloc (size); | |
1226 | else | |
1227 | m_entries = ggc_cleared_vec_alloc<value_type> (size); | |
1228 | ||
2933f7af | 1229 | gcc_assert (m_entries != NULL); |
1230 | m_size = size; | |
1231 | m_size_prime_index = size_prime_index; | |
1232 | } | |
1233 | ||
1234 | template<typename Descriptor, template<typename Type> class Allocator> | |
1235 | hash_table<Descriptor, Allocator, true>::~hash_table () | |
1236 | { | |
1237 | for (size_t i = m_size - 1; i < m_size; i--) | |
1238 | if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i])) | |
1239 | Descriptor::remove (m_entries[i]); | |
1240 | ||
8f359205 | 1241 | if (!m_ggc) |
1242 | Allocator <value_type> ::data_free (m_entries); | |
1243 | else | |
1244 | ggc_free (m_entries); | |
2933f7af | 1245 | } |
1246 | ||
1247 | /* Similar to find_slot, but without several unwanted side effects: | |
1248 | - Does not call equal when it finds an existing entry. | |
1249 | - Does not change the count of elements/searches/collisions in the | |
1250 | hash table. | |
1251 | This function also assumes there are no deleted entries in the table. | |
1252 | HASH is the hash value for the element to be inserted. */ | |
1253 | ||
1254 | template<typename Descriptor, template<typename Type> class Allocator> | |
0aa6cf04 | 1255 | typename hash_table<Descriptor, Allocator, true>::value_type * |
2933f7af | 1256 | hash_table<Descriptor, Allocator, true> |
1257 | ::find_empty_slot_for_expand (hashval_t hash) | |
1258 | { | |
1259 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); | |
1260 | size_t size = m_size; | |
1261 | value_type *slot = m_entries + index; | |
1262 | hashval_t hash2; | |
1263 | ||
1264 | if (is_empty (*slot)) | |
1265 | return slot; | |
1266 | else if (is_deleted (*slot)) | |
1267 | abort (); | |
1268 | ||
1269 | hash2 = hash_table_mod2 (hash, m_size_prime_index); | |
1270 | for (;;) | |
1271 | { | |
1272 | index += hash2; | |
1273 | if (index >= size) | |
1274 | index -= size; | |
1275 | ||
1276 | slot = m_entries + index; | |
1277 | if (is_empty (*slot)) | |
1278 | return slot; | |
1279 | else if (is_deleted (*slot)) | |
1280 | abort (); | |
1281 | } | |
1282 | } | |
1283 | ||
1284 | /* The following function changes size of memory allocated for the | |
1285 | entries and repeatedly inserts the table elements. The occupancy | |
1286 | of the table after the call will be about 50%. Naturally the hash | |
1287 | table must already exist. Remember also that the place of the | |
1288 | table entries is changed. If memory allocation fails, this function | |
1289 | will abort. */ | |
1290 | ||
1291 | template<typename Descriptor, template<typename Type> class Allocator> | |
1292 | void | |
1293 | hash_table<Descriptor, Allocator, true>::expand () | |
1294 | { | |
1295 | value_type *oentries = m_entries; | |
1296 | unsigned int oindex = m_size_prime_index; | |
1297 | size_t osize = size (); | |
1298 | value_type *olimit = oentries + osize; | |
1299 | size_t elts = elements (); | |
1300 | ||
1301 | /* Resize only when table after removal of unused elements is either | |
1302 | too full or too empty. */ | |
1303 | unsigned int nindex; | |
1304 | size_t nsize; | |
1305 | if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) | |
1306 | { | |
1307 | nindex = hash_table_higher_prime_index (elts * 2); | |
1308 | nsize = prime_tab[nindex].prime; | |
1309 | } | |
1310 | else | |
1311 | { | |
1312 | nindex = oindex; | |
1313 | nsize = osize; | |
1314 | } | |
1315 | ||
8f359205 | 1316 | value_type *nentries; |
1317 | if (!m_ggc) | |
1318 | nentries = Allocator <value_type> ::data_alloc (nsize); | |
1319 | else | |
1320 | nentries = ggc_cleared_vec_alloc<value_type> (nsize); | |
1321 | ||
2933f7af | 1322 | gcc_assert (nentries != NULL); |
1323 | m_entries = nentries; | |
1324 | m_size = nsize; | |
1325 | m_size_prime_index = nindex; | |
1326 | m_n_elements -= m_n_deleted; | |
1327 | m_n_deleted = 0; | |
1328 | ||
1329 | value_type *p = oentries; | |
1330 | do | |
1331 | { | |
1332 | value_type &x = *p; | |
1333 | ||
1334 | if (!is_empty (x) && !is_deleted (x)) | |
1335 | { | |
1336 | value_type *q = find_empty_slot_for_expand (Descriptor::hash (x)); | |
1337 | ||
1338 | *q = x; | |
1339 | } | |
1340 | ||
1341 | p++; | |
1342 | } | |
1343 | while (p < olimit); | |
1344 | ||
8f359205 | 1345 | if (!m_ggc) |
1346 | Allocator <value_type> ::data_free (oentries); | |
1347 | else | |
1348 | ggc_free (oentries); | |
2933f7af | 1349 | } |
1350 | ||
1351 | template<typename Descriptor, template<typename Type> class Allocator> | |
1352 | void | |
1353 | hash_table<Descriptor, Allocator, true>::empty () | |
1354 | { | |
1355 | size_t size = m_size; | |
1356 | value_type *entries = m_entries; | |
1357 | int i; | |
1358 | ||
1359 | for (i = size - 1; i >= 0; i--) | |
1360 | if (!is_empty (entries[i]) && !is_deleted (entries[i])) | |
1361 | Descriptor::remove (entries[i]); | |
1362 | ||
1363 | /* Instead of clearing megabyte, downsize the table. */ | |
1364 | if (size > 1024*1024 / sizeof (PTR)) | |
1365 | { | |
1366 | int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR)); | |
1367 | int nsize = prime_tab[nindex].prime; | |
1368 | ||
8f359205 | 1369 | if (!m_ggc) |
1370 | { | |
1371 | Allocator <value_type> ::data_free (m_entries); | |
1372 | m_entries = Allocator <value_type> ::data_alloc (nsize); | |
1373 | } | |
1374 | else | |
1375 | { | |
1376 | ggc_free (m_entries); | |
1377 | m_entries = ggc_cleared_vec_alloc<value_type> (nsize); | |
1378 | } | |
1379 | ||
2933f7af | 1380 | m_size = nsize; |
1381 | m_size_prime_index = nindex; | |
1382 | } | |
1383 | else | |
1384 | memset (entries, 0, size * sizeof (value_type)); | |
1385 | m_n_deleted = 0; | |
1386 | m_n_elements = 0; | |
1387 | } | |
1388 | ||
1389 | /* This function clears a specified SLOT in a hash table. It is | |
1390 | useful when you've already done the lookup and don't want to do it | |
1391 | again. */ | |
1392 | ||
1393 | template<typename Descriptor, template<typename Type> class Allocator> | |
1394 | void | |
1395 | hash_table<Descriptor, Allocator, true>::clear_slot (value_type *slot) | |
1396 | { | |
1397 | if (slot < m_entries || slot >= m_entries + size () | |
1398 | || is_empty (*slot) || is_deleted (*slot)) | |
1399 | abort (); | |
1400 | ||
1401 | Descriptor::remove (*slot); | |
1402 | ||
1403 | mark_deleted (*slot); | |
1404 | m_n_deleted++; | |
1405 | } | |
1406 | ||
1407 | /* This function searches for a hash table entry equal to the given | |
1408 | COMPARABLE element starting with the given HASH value. It cannot | |
1409 | be used to insert or delete an element. */ | |
1410 | ||
1411 | template<typename Descriptor, template<typename Type> class Allocator> | |
0aa6cf04 | 1412 | typename hash_table<Descriptor, Allocator, true>::value_type & |
2933f7af | 1413 | hash_table<Descriptor, Allocator, true> |
1414 | ::find_with_hash (const compare_type &comparable, hashval_t hash) | |
1415 | { | |
1416 | m_searches++; | |
1417 | size_t size = m_size; | |
1418 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); | |
1419 | ||
1420 | value_type *entry = &m_entries[index]; | |
1421 | if (is_empty (*entry) | |
1422 | || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable))) | |
1423 | return *entry; | |
1424 | ||
1425 | hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); | |
1426 | for (;;) | |
1427 | { | |
1428 | m_collisions++; | |
1429 | index += hash2; | |
1430 | if (index >= size) | |
1431 | index -= size; | |
1432 | ||
1433 | entry = &m_entries[index]; | |
1434 | if (is_empty (*entry) | |
1435 | || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable))) | |
1436 | return *entry; | |
1437 | } | |
1438 | } | |
1439 | ||
1440 | /* This function searches for a hash table slot containing an entry | |
1441 | equal to the given COMPARABLE element and starting with the given | |
1442 | HASH. To delete an entry, call this with insert=NO_INSERT, then | |
1443 | call clear_slot on the slot returned (possibly after doing some | |
1444 | checks). To insert an entry, call this with insert=INSERT, then | |
1445 | write the value you want into the returned slot. When inserting an | |
1446 | entry, NULL may be returned if memory allocation fails. */ | |
1447 | ||
1448 | template<typename Descriptor, template<typename Type> class Allocator> | |
0aa6cf04 | 1449 | typename hash_table<Descriptor, Allocator, true>::value_type * |
2933f7af | 1450 | hash_table<Descriptor, Allocator, true> |
1451 | ::find_slot_with_hash (const compare_type &comparable, hashval_t hash, | |
1452 | enum insert_option insert) | |
1453 | { | |
1454 | if (insert == INSERT && m_size * 3 <= m_n_elements * 4) | |
1455 | expand (); | |
1456 | ||
1457 | m_searches++; | |
1458 | ||
1459 | value_type *first_deleted_slot = NULL; | |
1460 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); | |
1461 | hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); | |
1462 | value_type *entry = &m_entries[index]; | |
1463 | size_t size = m_size; | |
1464 | if (is_empty (*entry)) | |
1465 | goto empty_entry; | |
1466 | else if (is_deleted (*entry)) | |
1467 | first_deleted_slot = &m_entries[index]; | |
1468 | else if (Descriptor::equal (*entry, comparable)) | |
1469 | return &m_entries[index]; | |
1470 | ||
1471 | for (;;) | |
1472 | { | |
1473 | m_collisions++; | |
1474 | index += hash2; | |
1475 | if (index >= size) | |
1476 | index -= size; | |
1477 | ||
1478 | entry = &m_entries[index]; | |
1479 | if (is_empty (*entry)) | |
1480 | goto empty_entry; | |
1481 | else if (is_deleted (*entry)) | |
1482 | { | |
1483 | if (!first_deleted_slot) | |
1484 | first_deleted_slot = &m_entries[index]; | |
1485 | } | |
1486 | else if (Descriptor::equal (*entry, comparable)) | |
1487 | return &m_entries[index]; | |
1488 | } | |
1489 | ||
1490 | empty_entry: | |
1491 | if (insert == NO_INSERT) | |
1492 | return NULL; | |
1493 | ||
1494 | if (first_deleted_slot) | |
1495 | { | |
1496 | m_n_deleted--; | |
1497 | mark_empty (*first_deleted_slot); | |
1498 | return first_deleted_slot; | |
1499 | } | |
1500 | ||
1501 | m_n_elements++; | |
1502 | return &m_entries[index]; | |
1503 | } | |
1504 | ||
1505 | /* This function deletes an element with the given COMPARABLE value | |
1506 | from hash table starting with the given HASH. If there is no | |
1507 | matching element in the hash table, this function does nothing. */ | |
1508 | ||
1509 | template<typename Descriptor, template<typename Type> class Allocator> | |
1510 | void | |
1511 | hash_table<Descriptor, Allocator, true> | |
1512 | ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash) | |
1513 | { | |
1514 | value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT); | |
1515 | if (is_empty (*slot)) | |
1516 | return; | |
1517 | ||
1518 | Descriptor::remove (*slot); | |
1519 | ||
1520 | mark_deleted (*slot); | |
1521 | m_n_deleted++; | |
1522 | } | |
1523 | ||
1524 | /* This function scans over the entire hash table calling CALLBACK for | |
1525 | each live entry. If CALLBACK returns false, the iteration stops. | |
1526 | ARGUMENT is passed as CALLBACK's second argument. */ | |
1527 | ||
1528 | template<typename Descriptor, | |
1529 | template<typename Type> class Allocator> | |
1530 | template<typename Argument, | |
0aa6cf04 | 1531 | int (*Callback) (typename hash_table<Descriptor, Allocator, |
1532 | true>::value_type *slot, | |
2933f7af | 1533 | Argument argument)> |
1534 | void | |
1535 | hash_table<Descriptor, Allocator, true>::traverse_noresize (Argument argument) | |
1536 | { | |
1537 | value_type *slot = m_entries; | |
1538 | value_type *limit = slot + size (); | |
1539 | ||
1540 | do | |
1541 | { | |
1542 | value_type &x = *slot; | |
1543 | ||
1544 | if (!is_empty (x) && !is_deleted (x)) | |
1545 | if (! Callback (slot, argument)) | |
1546 | break; | |
1547 | } | |
1548 | while (++slot < limit); | |
1549 | } | |
1550 | ||
1551 | /* Like traverse_noresize, but does resize the table when it is too empty | |
1552 | to improve effectivity of subsequent calls. */ | |
1553 | ||
1554 | template <typename Descriptor, | |
1555 | template <typename Type> class Allocator> | |
1556 | template <typename Argument, | |
0aa6cf04 | 1557 | int (*Callback) (typename hash_table<Descriptor, Allocator, |
1558 | true>::value_type *slot, | |
2933f7af | 1559 | Argument argument)> |
1560 | void | |
1561 | hash_table<Descriptor, Allocator, true>::traverse (Argument argument) | |
1562 | { | |
1563 | size_t size = m_size; | |
1564 | if (elements () * 8 < size && size > 32) | |
1565 | expand (); | |
1566 | ||
1567 | traverse_noresize <Argument, Callback> (argument); | |
1568 | } | |
1569 | ||
1570 | /* Slide down the iterator slots until an active entry is found. */ | |
1571 | ||
1572 | template<typename Descriptor, template<typename Type> class Allocator> | |
1573 | void | |
1574 | hash_table<Descriptor, Allocator, true>::iterator::slide () | |
1575 | { | |
1576 | for ( ; m_slot < m_limit; ++m_slot ) | |
1577 | { | |
1578 | value_type &x = *m_slot; | |
1579 | if (!is_empty (x) && !is_deleted (x)) | |
1580 | return; | |
1581 | } | |
1582 | m_slot = NULL; | |
1583 | m_limit = NULL; | |
1584 | } | |
1585 | ||
1586 | /* Bump the iterator. */ | |
1587 | ||
1588 | template<typename Descriptor, template<typename Type> class Allocator> | |
1589 | inline typename hash_table<Descriptor, Allocator, true>::iterator & | |
1590 | hash_table<Descriptor, Allocator, true>::iterator::operator ++ () | |
3e871d4d | 1591 | { |
ae84f584 | 1592 | ++m_slot; |
3e871d4d | 1593 | slide (); |
1594 | return *this; | |
1595 | } | |
1596 | ||
3e871d4d | 1597 | |
1598 | /* Iterate through the elements of hash_table HTAB, | |
1599 | using hash_table <....>::iterator ITER, | |
f6d8a42a | 1600 | storing each element in RESULT, which is of type TYPE. */ |
3e871d4d | 1601 | |
1602 | #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \ | |
1603 | for ((ITER) = (HTAB).begin (); \ | |
2933f7af | 1604 | (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \ |
3e871d4d | 1605 | ++(ITER)) |
1606 | ||
8f359205 | 1607 | /* ggc walking routines. */ |
1608 | ||
1609 | template<typename E> | |
1610 | static inline void | |
1611 | gt_ggc_mx (hash_table<E> *h) | |
1612 | { | |
1613 | typedef hash_table<E> table; | |
1614 | ||
1615 | if (!ggc_test_and_set_mark (h->m_entries)) | |
1616 | return; | |
1617 | ||
1618 | for (size_t i = 0; i < h->m_size; i++) | |
1619 | { | |
1620 | if (table::is_empty (h->m_entries[i]) | |
1621 | || table::is_deleted (h->m_entries[i])) | |
1622 | continue; | |
1623 | ||
1624 | E::ggc_mx (h->m_entries[i]); | |
1625 | } | |
1626 | } | |
1627 | ||
1628 | template<typename D> | |
1629 | static inline void | |
1630 | hashtab_entry_note_pointers (void *obj, void *h, gt_pointer_operator op, | |
1631 | void *cookie) | |
1632 | { | |
1633 | hash_table<D> *map = static_cast<hash_table<D> *> (h); | |
1634 | gcc_checking_assert (map->m_entries == obj); | |
1635 | for (size_t i = 0; i < map->m_size; i++) | |
1636 | { | |
1637 | typedef hash_table<D> table; | |
1638 | if (table::is_empty (map->m_entries[i]) | |
1639 | || table::is_deleted (map->m_entries[i])) | |
1640 | continue; | |
1641 | ||
1642 | D::pch_nx (map->m_entries[i], op, cookie); | |
1643 | } | |
1644 | } | |
1645 | ||
1646 | template<typename D> | |
1647 | static void | |
1648 | gt_pch_nx (hash_table<D> *h) | |
1649 | { | |
2ef51f0e | 1650 | bool success |
e7246521 | 1651 | = gt_pch_note_object (h->m_entries, h, hashtab_entry_note_pointers<D>); |
1652 | gcc_checking_assert (success); | |
8f359205 | 1653 | for (size_t i = 0; i < h->m_size; i++) |
1654 | { | |
1655 | if (hash_table<D>::is_empty (h->m_entries[i]) | |
1656 | || hash_table<D>::is_deleted (h->m_entries[i])) | |
1657 | continue; | |
1658 | ||
1659 | D::pch_nx (h->m_entries[i]); | |
1660 | } | |
1661 | } | |
1662 | ||
2ef51f0e | 1663 | template<typename D> |
1664 | static inline void | |
1665 | gt_pch_nx (hash_table<D> *h, gt_pointer_operator op, void *cookie) | |
1666 | { | |
1667 | op (&h->m_entries, cookie); | |
1668 | } | |
1669 | ||
2b15d2ba | 1670 | #endif /* TYPED_HASHTAB_H */ |