]>
Commit | Line | Data |
---|---|---|
0823efed | 1 | /* A type-safe hash table template. |
23a5b65a | 2 | Copyright (C) 2012-2014 Free Software Foundation, Inc. |
0823efed DN |
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. | |
5831a5f0 LC |
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 | ||
5831a5f0 LC |
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 | ||
bf190e8d LC |
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 | ||
5831a5f0 | 193 | */ |
0823efed DN |
194 | |
195 | ||
196 | #ifndef TYPED_HASHTAB_H | |
197 | #define TYPED_HASHTAB_H | |
198 | ||
199 | #include "hashtab.h" | |
200 | ||
201 | ||
202 | /* The ordinary memory allocator. */ | |
203 | /* FIXME (crowl): This allocator may be extracted for wider sharing later. */ | |
204 | ||
205 | template <typename Type> | |
206 | struct xcallocator | |
207 | { | |
0823efed | 208 | static Type *data_alloc (size_t count); |
0823efed DN |
209 | static void data_free (Type *memory); |
210 | }; | |
211 | ||
212 | ||
5831a5f0 | 213 | /* Allocate memory for COUNT data blocks. */ |
0823efed DN |
214 | |
215 | template <typename Type> | |
216 | inline Type * | |
217 | xcallocator <Type>::data_alloc (size_t count) | |
218 | { | |
219 | return static_cast <Type *> (xcalloc (count, sizeof (Type))); | |
220 | } | |
221 | ||
222 | ||
0823efed DN |
223 | /* Free memory for data blocks. */ |
224 | ||
225 | template <typename Type> | |
226 | inline void | |
227 | xcallocator <Type>::data_free (Type *memory) | |
228 | { | |
229 | return ::free (memory); | |
230 | } | |
231 | ||
232 | ||
5831a5f0 | 233 | /* Helpful type for removing with free. */ |
0823efed | 234 | |
5831a5f0 | 235 | template <typename Type> |
5deac340 | 236 | struct typed_free_remove |
0823efed | 237 | { |
5831a5f0 | 238 | static inline void remove (Type *p); |
5deac340 | 239 | }; |
0823efed | 240 | |
0823efed | 241 | |
5831a5f0 LC |
242 | /* Remove with free. */ |
243 | ||
244 | template <typename Type> | |
245 | inline void | |
246 | typed_free_remove <Type>::remove (Type *p) | |
247 | { | |
248 | free (p); | |
249 | } | |
250 | ||
251 | ||
252 | /* Helpful type for a no-op remove. */ | |
253 | ||
254 | template <typename Type> | |
5deac340 | 255 | struct typed_noop_remove |
0823efed | 256 | { |
5831a5f0 | 257 | static inline void remove (Type *p); |
5deac340 | 258 | }; |
0823efed DN |
259 | |
260 | ||
5831a5f0 LC |
261 | /* Remove doing nothing. */ |
262 | ||
263 | template <typename Type> | |
264 | inline void | |
265 | typed_noop_remove <Type>::remove (Type *p ATTRIBUTE_UNUSED) | |
266 | { | |
267 | } | |
268 | ||
269 | ||
5deac340 | 270 | /* Pointer hash with a no-op remove method. */ |
0823efed | 271 | |
5831a5f0 LC |
272 | template <typename Type> |
273 | struct pointer_hash : typed_noop_remove <Type> | |
0823efed | 274 | { |
84baa4b9 TS |
275 | typedef Type *value_type; |
276 | typedef Type *compare_type; | |
277 | typedef int store_values_directly; | |
0823efed | 278 | |
84baa4b9 | 279 | static inline hashval_t hash (const value_type &); |
0823efed | 280 | |
84baa4b9 | 281 | static inline bool equal (const value_type &existing, const compare_type &candidate); |
5deac340 | 282 | }; |
0823efed | 283 | |
5831a5f0 | 284 | template <typename Type> |
5deac340 | 285 | inline hashval_t |
84baa4b9 | 286 | pointer_hash <Type>::hash (const value_type &candidate) |
5deac340 RG |
287 | { |
288 | /* This is a really poor hash function, but it is what the current code uses, | |
289 | so I am reusing it to avoid an additional axis in testing. */ | |
290 | return (hashval_t) ((intptr_t)candidate >> 3); | |
291 | } | |
292 | ||
5831a5f0 | 293 | template <typename Type> |
84baa4b9 TS |
294 | inline bool |
295 | pointer_hash <Type>::equal (const value_type &existing, | |
296 | const compare_type &candidate) | |
0823efed | 297 | { |
5deac340 | 298 | return existing == candidate; |
0823efed DN |
299 | } |
300 | ||
301 | ||
302 | /* Table of primes and their inversion information. */ | |
303 | ||
304 | struct prime_ent | |
305 | { | |
306 | hashval_t prime; | |
307 | hashval_t inv; | |
308 | hashval_t inv_m2; /* inverse of prime-2 */ | |
309 | hashval_t shift; | |
310 | }; | |
311 | ||
312 | extern struct prime_ent const prime_tab[]; | |
313 | ||
314 | ||
315 | /* Functions for computing hash table indexes. */ | |
316 | ||
317 | extern unsigned int hash_table_higher_prime_index (unsigned long n); | |
318 | extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index); | |
319 | extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index); | |
320 | ||
84baa4b9 TS |
321 | /* The below is some template meta programming to decide if we should use the |
322 | hash table partial specialization that directly stores value_type instead of | |
323 | pointers to value_type. If the Descriptor type defines the type | |
324 | Descriptor::store_values_directly then values are stored directly otherwise | |
325 | pointers to them are stored. */ | |
326 | template<typename T> struct notype { typedef void type; }; | |
327 | ||
328 | template<typename T, typename = void> | |
329 | struct storage_tester | |
330 | { | |
331 | static const bool value = false; | |
332 | }; | |
333 | ||
334 | template<typename T> | |
335 | struct storage_tester<T, typename notype<typename | |
336 | T::store_values_directly>::type> | |
337 | { | |
338 | static const bool value = true; | |
339 | }; | |
340 | ||
341 | template<typename Traits> | |
342 | struct has_is_deleted | |
343 | { | |
344 | template<typename U, bool (*)(U &)> struct helper {}; | |
345 | template<typename U> static char test (helper<U, U::is_deleted> *); | |
346 | template<typename U> static int test (...); | |
347 | static const bool value = sizeof (test<Traits> (0)) == sizeof (char); | |
348 | }; | |
349 | ||
350 | template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> | |
351 | struct is_deleted_helper | |
352 | { | |
353 | static inline bool | |
354 | call (Type &v) | |
355 | { | |
356 | return Traits::is_deleted (v); | |
357 | } | |
358 | }; | |
359 | ||
360 | template<typename Type, typename Traits> | |
361 | struct is_deleted_helper<Type *, Traits, false> | |
362 | { | |
363 | static inline bool | |
364 | call (Type *v) | |
365 | { | |
366 | return v == HTAB_DELETED_ENTRY; | |
367 | } | |
368 | }; | |
369 | ||
370 | template<typename Traits> | |
371 | struct has_is_empty | |
372 | { | |
373 | template<typename U, bool (*)(U &)> struct helper {}; | |
374 | template<typename U> static char test (helper<U, U::is_empty> *); | |
375 | template<typename U> static int test (...); | |
376 | static const bool value = sizeof (test<Traits> (0)) == sizeof (char); | |
377 | }; | |
378 | ||
379 | template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> | |
380 | struct is_empty_helper | |
381 | { | |
382 | static inline bool | |
383 | call (Type &v) | |
384 | { | |
385 | return Traits::is_empty (v); | |
386 | } | |
387 | }; | |
388 | ||
389 | template<typename Type, typename Traits> | |
390 | struct is_empty_helper<Type *, Traits, false> | |
391 | { | |
392 | static inline bool | |
393 | call (Type *v) | |
394 | { | |
395 | return v == HTAB_EMPTY_ENTRY; | |
396 | } | |
397 | }; | |
398 | ||
399 | template<typename Traits> | |
400 | struct has_mark_deleted | |
401 | { | |
402 | template<typename U, void (*)(U &)> struct helper {}; | |
403 | template<typename U> static char test (helper<U, U::mark_deleted> *); | |
404 | template<typename U> static int test (...); | |
405 | static const bool value = sizeof (test<Traits> (0)) == sizeof (char); | |
406 | }; | |
407 | ||
408 | template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> | |
409 | struct mark_deleted_helper | |
410 | { | |
411 | static inline void | |
412 | call (Type &v) | |
413 | { | |
414 | Traits::mark_deleted (v); | |
415 | } | |
416 | }; | |
417 | ||
418 | template<typename Type, typename Traits> | |
419 | struct mark_deleted_helper<Type *, Traits, false> | |
420 | { | |
421 | static inline void | |
422 | call (Type *&v) | |
423 | { | |
424 | v = static_cast<Type *> (HTAB_DELETED_ENTRY); | |
425 | } | |
426 | }; | |
427 | ||
428 | template<typename Traits> | |
429 | struct has_mark_empty | |
430 | { | |
431 | template<typename U, void (*)(U &)> struct helper {}; | |
432 | template<typename U> static char test (helper<U, U::mark_empty> *); | |
433 | template<typename U> static int test (...); | |
434 | static const bool value = sizeof (test<Traits> (0)) == sizeof (char); | |
435 | }; | |
436 | ||
437 | template<typename Type, typename Traits, bool = has_is_deleted<Traits>::value> | |
438 | struct mark_empty_helper | |
439 | { | |
440 | static inline void | |
441 | call (Type &v) | |
442 | { | |
443 | Traits::mark_empty (v); | |
444 | } | |
445 | }; | |
446 | ||
447 | template<typename Type, typename Traits> | |
448 | struct mark_empty_helper<Type *, Traits, false> | |
449 | { | |
450 | static inline void | |
451 | call (Type *&v) | |
452 | { | |
453 | v = static_cast<Type *> (HTAB_EMPTY_ENTRY); | |
454 | } | |
455 | }; | |
0823efed | 456 | |
0823efed DN |
457 | /* User-facing hash table type. |
458 | ||
84baa4b9 TS |
459 | The table stores elements of type Descriptor::value_type, or pointers to |
460 | objects of type value_type if the descriptor does not define the type | |
461 | store_values_directly. | |
0823efed | 462 | |
5831a5f0 | 463 | It hashes values with the hash member function. |
0823efed | 464 | The table currently works with relatively weak hash functions. |
5831a5f0 | 465 | Use typed_pointer_hash <Value> when hashing pointers instead of objects. |
0823efed | 466 | |
5831a5f0 | 467 | It compares elements with the equal member function. |
0823efed | 468 | Two elements with the same hash may not be equal. |
5831a5f0 | 469 | Use typed_pointer_equal <Value> when hashing pointers instead of objects. |
0823efed | 470 | |
5831a5f0 | 471 | It removes elements with the remove member function. |
0823efed | 472 | This feature is useful for freeing memory. |
5831a5f0 LC |
473 | Derive from typed_null_remove <Value> when not freeing objects. |
474 | Derive from typed_free_remove <Value> when doing a simple object free. | |
0823efed | 475 | |
5831a5f0 | 476 | Specify the template Allocator to allocate and free memory. |
0823efed DN |
477 | The default is xcallocator. |
478 | ||
84baa4b9 TS |
479 | Storage is an implementation detail and should not be used outside the |
480 | hash table code. | |
481 | ||
0823efed | 482 | */ |
5831a5f0 | 483 | template <typename Descriptor, |
84baa4b9 TS |
484 | template<typename Type> class Allocator= xcallocator, |
485 | bool Storage = storage_tester<Descriptor>::value> | |
0823efed | 486 | class hash_table |
84baa4b9 TS |
487 | { |
488 | }; | |
489 | ||
490 | template <typename Descriptor, | |
491 | template<typename Type> class Allocator> | |
492 | class hash_table<Descriptor, Allocator, false> | |
0823efed | 493 | { |
5831a5f0 LC |
494 | typedef typename Descriptor::value_type value_type; |
495 | typedef typename Descriptor::compare_type compare_type; | |
0823efed | 496 | |
0823efed | 497 | public: |
c203e8a7 TS |
498 | hash_table (size_t); |
499 | ~hash_table (); | |
bf190e8d | 500 | |
c203e8a7 TS |
501 | /* Current size (in entries) of the hash table. */ |
502 | size_t size () const { return m_size; } | |
0823efed | 503 | |
c203e8a7 TS |
504 | /* Return the current number of elements in this hash table. */ |
505 | size_t elements () const { return m_n_elements - m_n_deleted; } | |
0823efed | 506 | |
c203e8a7 TS |
507 | /* Return the current number of elements in this hash table. */ |
508 | size_t elements_with_deleted () const { return m_n_elements; } | |
0823efed | 509 | |
c203e8a7 TS |
510 | /* This function clears all entries in the given hash table. */ |
511 | void empty (); | |
0823efed | 512 | |
c203e8a7 TS |
513 | /* This function clears a specified SLOT in a hash table. It is |
514 | useful when you've already done the lookup and don't want to do it | |
515 | again. */ | |
0823efed | 516 | |
c203e8a7 | 517 | void clear_slot (value_type **); |
0823efed | 518 | |
c203e8a7 TS |
519 | /* This function searches for a hash table entry equal to the given |
520 | COMPARABLE element starting with the given HASH value. It cannot | |
521 | be used to insert or delete an element. */ | |
522 | value_type *find_with_hash (const compare_type *, hashval_t); | |
0823efed | 523 | |
c203e8a7 TS |
524 | /* Like find_slot_with_hash, but compute the hash value from the element. */ |
525 | value_type *find (const value_type *value) | |
526 | { | |
527 | return find_with_hash (value, Descriptor::hash (value)); | |
528 | } | |
0823efed | 529 | |
c203e8a7 TS |
530 | value_type **find_slot (const value_type *value, insert_option insert) |
531 | { | |
532 | return find_slot_with_hash (value, Descriptor::hash (value), insert); | |
533 | } | |
0823efed | 534 | |
c203e8a7 TS |
535 | /* This function searches for a hash table slot containing an entry |
536 | equal to the given COMPARABLE element and starting with the given | |
537 | HASH. To delete an entry, call this with insert=NO_INSERT, then | |
538 | call clear_slot on the slot returned (possibly after doing some | |
539 | checks). To insert an entry, call this with insert=INSERT, then | |
540 | write the value you want into the returned slot. When inserting an | |
541 | entry, NULL may be returned if memory allocation fails. */ | |
542 | value_type **find_slot_with_hash (const compare_type *comparable, | |
543 | hashval_t hash, enum insert_option insert); | |
0823efed | 544 | |
c203e8a7 TS |
545 | /* This function deletes an element with the given COMPARABLE value |
546 | from hash table starting with the given HASH. If there is no | |
547 | matching element in the hash table, this function does nothing. */ | |
548 | void remove_elt_with_hash (const compare_type *, hashval_t); | |
0823efed | 549 | |
c203e8a7 TS |
550 | /* Like remove_elt_with_hash, but compute the hash value from the element. */ |
551 | void remove_elt (const value_type *value) | |
552 | { | |
553 | remove_elt_with_hash (value, Descriptor::hash (value)); | |
554 | } | |
0823efed | 555 | |
c203e8a7 TS |
556 | /* This function scans over the entire hash table calling CALLBACK for |
557 | each live entry. If CALLBACK returns false, the iteration stops. | |
558 | ARGUMENT is passed as CALLBACK's second argument. */ | |
559 | template <typename Argument, | |
560 | int (*Callback) (value_type **slot, Argument argument)> | |
561 | void traverse_noresize (Argument argument); | |
0823efed | 562 | |
c203e8a7 TS |
563 | /* Like traverse_noresize, but does resize the table when it is too empty |
564 | to improve effectivity of subsequent calls. */ | |
565 | template <typename Argument, | |
566 | int (*Callback) (value_type **slot, Argument argument)> | |
567 | void traverse (Argument argument); | |
0823efed | 568 | |
c203e8a7 TS |
569 | class iterator |
570 | { | |
571 | public: | |
572 | iterator () : m_slot (NULL), m_limit (NULL) {} | |
0823efed | 573 | |
c203e8a7 TS |
574 | iterator (value_type **slot, value_type **limit) : |
575 | m_slot (slot), m_limit (limit) {} | |
0823efed | 576 | |
84baa4b9 | 577 | inline value_type *operator * () { return *m_slot; } |
c203e8a7 TS |
578 | void slide (); |
579 | inline iterator &operator ++ (); | |
580 | bool operator != (const iterator &other) const | |
581 | { | |
582 | return m_slot != other.m_slot || m_limit != other.m_limit; | |
583 | } | |
0823efed | 584 | |
c203e8a7 TS |
585 | private: |
586 | value_type **m_slot; | |
587 | value_type **m_limit; | |
588 | }; | |
0823efed | 589 | |
c203e8a7 TS |
590 | iterator begin () const |
591 | { | |
592 | iterator iter (m_entries, m_entries + m_size); | |
593 | iter.slide (); | |
594 | return iter; | |
595 | } | |
0823efed | 596 | |
c203e8a7 | 597 | iterator end () const { return iterator (); } |
0823efed | 598 | |
c203e8a7 TS |
599 | double collisions () const |
600 | { | |
601 | return m_searches ? static_cast <double> (m_collisions) / m_searches : 0; | |
602 | } | |
0823efed | 603 | |
c203e8a7 | 604 | private: |
0823efed | 605 | |
c203e8a7 TS |
606 | value_type **find_empty_slot_for_expand (hashval_t); |
607 | void expand (); | |
bf190e8d | 608 | |
c203e8a7 TS |
609 | /* Table itself. */ |
610 | typename Descriptor::value_type **m_entries; | |
bf190e8d | 611 | |
c203e8a7 | 612 | size_t m_size; |
bf190e8d | 613 | |
c203e8a7 TS |
614 | /* Current number of elements including also deleted elements. */ |
615 | size_t m_n_elements; | |
0823efed | 616 | |
c203e8a7 TS |
617 | /* Current number of deleted elements in the table. */ |
618 | size_t m_n_deleted; | |
0823efed | 619 | |
c203e8a7 TS |
620 | /* The following member is used for debugging. Its value is number |
621 | of all calls of `htab_find_slot' for the hash table. */ | |
622 | unsigned int m_searches; | |
0823efed | 623 | |
c203e8a7 TS |
624 | /* The following member is used for debugging. Its value is number |
625 | of collisions fixed for time of work with the hash table. */ | |
626 | unsigned int m_collisions; | |
0823efed | 627 | |
c203e8a7 TS |
628 | /* Current size (in entries) of the hash table, as an index into the |
629 | table of primes. */ | |
630 | unsigned int m_size_prime_index; | |
631 | }; | |
0823efed | 632 | |
c203e8a7 | 633 | template<typename Descriptor, template<typename Type> class Allocator> |
84baa4b9 | 634 | hash_table<Descriptor, Allocator, false>::hash_table (size_t size) : |
c203e8a7 | 635 | m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0) |
0823efed DN |
636 | { |
637 | unsigned int size_prime_index; | |
638 | ||
639 | size_prime_index = hash_table_higher_prime_index (size); | |
640 | size = prime_tab[size_prime_index].prime; | |
641 | ||
c203e8a7 TS |
642 | m_entries = Allocator <value_type*> ::data_alloc (size); |
643 | gcc_assert (m_entries != NULL); | |
644 | m_size = size; | |
645 | m_size_prime_index = size_prime_index; | |
0823efed DN |
646 | } |
647 | ||
c203e8a7 | 648 | template<typename Descriptor, template<typename Type> class Allocator> |
84baa4b9 | 649 | hash_table<Descriptor, Allocator, false>::~hash_table () |
0823efed | 650 | { |
c203e8a7 TS |
651 | for (size_t i = m_size - 1; i < m_size; i--) |
652 | if (m_entries[i] != HTAB_EMPTY_ENTRY && m_entries[i] != HTAB_DELETED_ENTRY) | |
653 | Descriptor::remove (m_entries[i]); | |
0823efed | 654 | |
c203e8a7 | 655 | Allocator <value_type *> ::data_free (m_entries); |
0823efed DN |
656 | } |
657 | ||
0823efed | 658 | /* Similar to find_slot, but without several unwanted side effects: |
5deac340 | 659 | - Does not call equal when it finds an existing entry. |
0823efed DN |
660 | - Does not change the count of elements/searches/collisions in the |
661 | hash table. | |
662 | This function also assumes there are no deleted entries in the table. | |
663 | HASH is the hash value for the element to be inserted. */ | |
664 | ||
c203e8a7 | 665 | template<typename Descriptor, template<typename Type> class Allocator> |
e4e01495 | 666 | typename hash_table<Descriptor, Allocator, false>::value_type ** |
84baa4b9 TS |
667 | hash_table<Descriptor, Allocator, false> |
668 | ::find_empty_slot_for_expand (hashval_t hash) | |
0823efed | 669 | { |
c203e8a7 TS |
670 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); |
671 | size_t size = m_size; | |
672 | value_type **slot = m_entries + index; | |
0823efed DN |
673 | hashval_t hash2; |
674 | ||
675 | if (*slot == HTAB_EMPTY_ENTRY) | |
676 | return slot; | |
677 | else if (*slot == HTAB_DELETED_ENTRY) | |
678 | abort (); | |
679 | ||
c203e8a7 | 680 | hash2 = hash_table_mod2 (hash, m_size_prime_index); |
0823efed DN |
681 | for (;;) |
682 | { | |
683 | index += hash2; | |
684 | if (index >= size) | |
685 | index -= size; | |
686 | ||
c203e8a7 | 687 | slot = m_entries + index; |
0823efed DN |
688 | if (*slot == HTAB_EMPTY_ENTRY) |
689 | return slot; | |
690 | else if (*slot == HTAB_DELETED_ENTRY) | |
691 | abort (); | |
692 | } | |
693 | } | |
694 | ||
0823efed DN |
695 | /* The following function changes size of memory allocated for the |
696 | entries and repeatedly inserts the table elements. The occupancy | |
697 | of the table after the call will be about 50%. Naturally the hash | |
698 | table must already exist. Remember also that the place of the | |
699 | table entries is changed. If memory allocation fails, this function | |
700 | will abort. */ | |
701 | ||
c203e8a7 | 702 | template<typename Descriptor, template<typename Type> class Allocator> |
0823efed | 703 | void |
84baa4b9 | 704 | hash_table<Descriptor, Allocator, false>::expand () |
0823efed | 705 | { |
c203e8a7 TS |
706 | value_type **oentries = m_entries; |
707 | unsigned int oindex = m_size_prime_index; | |
708 | size_t osize = size (); | |
709 | value_type **olimit = oentries + osize; | |
710 | size_t elts = elements (); | |
0823efed DN |
711 | |
712 | /* Resize only when table after removal of unused elements is either | |
713 | too full or too empty. */ | |
c203e8a7 TS |
714 | unsigned int nindex; |
715 | size_t nsize; | |
0823efed DN |
716 | if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) |
717 | { | |
718 | nindex = hash_table_higher_prime_index (elts * 2); | |
719 | nsize = prime_tab[nindex].prime; | |
720 | } | |
721 | else | |
722 | { | |
723 | nindex = oindex; | |
724 | nsize = osize; | |
725 | } | |
726 | ||
c203e8a7 | 727 | value_type **nentries = Allocator <value_type *> ::data_alloc (nsize); |
0823efed | 728 | gcc_assert (nentries != NULL); |
c203e8a7 TS |
729 | m_entries = nentries; |
730 | m_size = nsize; | |
731 | m_size_prime_index = nindex; | |
732 | m_n_elements -= m_n_deleted; | |
733 | m_n_deleted = 0; | |
0823efed | 734 | |
c203e8a7 | 735 | value_type **p = oentries; |
0823efed DN |
736 | do |
737 | { | |
5831a5f0 | 738 | value_type *x = *p; |
0823efed DN |
739 | |
740 | if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) | |
741 | { | |
5831a5f0 | 742 | value_type **q = find_empty_slot_for_expand (Descriptor::hash (x)); |
0823efed DN |
743 | |
744 | *q = x; | |
745 | } | |
746 | ||
747 | p++; | |
748 | } | |
749 | while (p < olimit); | |
750 | ||
5831a5f0 | 751 | Allocator <value_type *> ::data_free (oentries); |
0823efed DN |
752 | } |
753 | ||
c203e8a7 TS |
754 | template<typename Descriptor, template<typename Type> class Allocator> |
755 | void | |
84baa4b9 | 756 | hash_table<Descriptor, Allocator, false>::empty () |
c203e8a7 TS |
757 | { |
758 | size_t size = m_size; | |
759 | value_type **entries = m_entries; | |
760 | int i; | |
761 | ||
762 | for (i = size - 1; i >= 0; i--) | |
763 | if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY) | |
764 | Descriptor::remove (entries[i]); | |
765 | ||
766 | /* Instead of clearing megabyte, downsize the table. */ | |
767 | if (size > 1024*1024 / sizeof (PTR)) | |
768 | { | |
769 | int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR)); | |
770 | int nsize = prime_tab[nindex].prime; | |
771 | ||
772 | Allocator <value_type *> ::data_free (m_entries); | |
773 | m_entries = Allocator <value_type *> ::data_alloc (nsize); | |
774 | m_size = nsize; | |
775 | m_size_prime_index = nindex; | |
776 | } | |
777 | else | |
778 | memset (entries, 0, size * sizeof (value_type *)); | |
779 | m_n_deleted = 0; | |
780 | m_n_elements = 0; | |
781 | } | |
782 | ||
783 | /* This function clears a specified SLOT in a hash table. It is | |
784 | useful when you've already done the lookup and don't want to do it | |
785 | again. */ | |
786 | ||
787 | template<typename Descriptor, template<typename Type> class Allocator> | |
788 | void | |
84baa4b9 | 789 | hash_table<Descriptor, Allocator, false>::clear_slot (value_type **slot) |
c203e8a7 TS |
790 | { |
791 | if (slot < m_entries || slot >= m_entries + size () | |
792 | || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY) | |
793 | abort (); | |
794 | ||
795 | Descriptor::remove (*slot); | |
796 | ||
797 | *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); | |
798 | m_n_deleted++; | |
799 | } | |
0823efed DN |
800 | |
801 | /* This function searches for a hash table entry equal to the given | |
802 | COMPARABLE element starting with the given HASH value. It cannot | |
803 | be used to insert or delete an element. */ | |
804 | ||
c203e8a7 | 805 | template<typename Descriptor, template<typename Type> class Allocator> |
e4e01495 | 806 | typename hash_table<Descriptor, Allocator, false>::value_type * |
84baa4b9 | 807 | hash_table<Descriptor, Allocator, false> |
5831a5f0 | 808 | ::find_with_hash (const compare_type *comparable, hashval_t hash) |
0823efed | 809 | { |
c203e8a7 TS |
810 | m_searches++; |
811 | size_t size = m_size; | |
812 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); | |
0823efed | 813 | |
c203e8a7 | 814 | value_type *entry = m_entries[index]; |
0823efed | 815 | if (entry == HTAB_EMPTY_ENTRY |
5831a5f0 | 816 | || (entry != HTAB_DELETED_ENTRY && Descriptor::equal (entry, comparable))) |
0823efed DN |
817 | return entry; |
818 | ||
c203e8a7 | 819 | hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); |
0823efed DN |
820 | for (;;) |
821 | { | |
c203e8a7 | 822 | m_collisions++; |
0823efed DN |
823 | index += hash2; |
824 | if (index >= size) | |
825 | index -= size; | |
826 | ||
c203e8a7 | 827 | entry = m_entries[index]; |
0823efed | 828 | if (entry == HTAB_EMPTY_ENTRY |
5831a5f0 LC |
829 | || (entry != HTAB_DELETED_ENTRY |
830 | && Descriptor::equal (entry, comparable))) | |
0823efed DN |
831 | return entry; |
832 | } | |
833 | } | |
834 | ||
0823efed DN |
835 | /* This function searches for a hash table slot containing an entry |
836 | equal to the given COMPARABLE element and starting with the given | |
837 | HASH. To delete an entry, call this with insert=NO_INSERT, then | |
838 | call clear_slot on the slot returned (possibly after doing some | |
839 | checks). To insert an entry, call this with insert=INSERT, then | |
840 | write the value you want into the returned slot. When inserting an | |
841 | entry, NULL may be returned if memory allocation fails. */ | |
842 | ||
c203e8a7 | 843 | template<typename Descriptor, template<typename Type> class Allocator> |
e4e01495 | 844 | typename hash_table<Descriptor, Allocator, false>::value_type ** |
84baa4b9 | 845 | hash_table<Descriptor, Allocator, false> |
5831a5f0 | 846 | ::find_slot_with_hash (const compare_type *comparable, hashval_t hash, |
0823efed DN |
847 | enum insert_option insert) |
848 | { | |
c203e8a7 TS |
849 | if (insert == INSERT && m_size * 3 <= m_n_elements * 4) |
850 | expand (); | |
0823efed | 851 | |
c203e8a7 | 852 | m_searches++; |
0823efed | 853 | |
c203e8a7 TS |
854 | value_type **first_deleted_slot = NULL; |
855 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); | |
856 | hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); | |
857 | value_type *entry = m_entries[index]; | |
858 | size_t size = m_size; | |
0823efed DN |
859 | if (entry == HTAB_EMPTY_ENTRY) |
860 | goto empty_entry; | |
861 | else if (entry == HTAB_DELETED_ENTRY) | |
c203e8a7 | 862 | first_deleted_slot = &m_entries[index]; |
5831a5f0 | 863 | else if (Descriptor::equal (entry, comparable)) |
c203e8a7 | 864 | return &m_entries[index]; |
5831a5f0 | 865 | |
0823efed DN |
866 | for (;;) |
867 | { | |
c203e8a7 | 868 | m_collisions++; |
0823efed DN |
869 | index += hash2; |
870 | if (index >= size) | |
871 | index -= size; | |
5831a5f0 | 872 | |
c203e8a7 | 873 | entry = m_entries[index]; |
0823efed DN |
874 | if (entry == HTAB_EMPTY_ENTRY) |
875 | goto empty_entry; | |
876 | else if (entry == HTAB_DELETED_ENTRY) | |
877 | { | |
878 | if (!first_deleted_slot) | |
c203e8a7 | 879 | first_deleted_slot = &m_entries[index]; |
0823efed | 880 | } |
5831a5f0 | 881 | else if (Descriptor::equal (entry, comparable)) |
c203e8a7 | 882 | return &m_entries[index]; |
0823efed DN |
883 | } |
884 | ||
885 | empty_entry: | |
886 | if (insert == NO_INSERT) | |
887 | return NULL; | |
888 | ||
889 | if (first_deleted_slot) | |
890 | { | |
c203e8a7 | 891 | m_n_deleted--; |
5831a5f0 | 892 | *first_deleted_slot = static_cast <value_type *> (HTAB_EMPTY_ENTRY); |
0823efed DN |
893 | return first_deleted_slot; |
894 | } | |
895 | ||
c203e8a7 TS |
896 | m_n_elements++; |
897 | return &m_entries[index]; | |
0823efed DN |
898 | } |
899 | ||
0823efed DN |
900 | /* This function deletes an element with the given COMPARABLE value |
901 | from hash table starting with the given HASH. If there is no | |
902 | matching element in the hash table, this function does nothing. */ | |
903 | ||
c203e8a7 | 904 | template<typename Descriptor, template<typename Type> class Allocator> |
0823efed | 905 | void |
84baa4b9 | 906 | hash_table<Descriptor, Allocator, false> |
5831a5f0 | 907 | ::remove_elt_with_hash (const compare_type *comparable, hashval_t hash) |
0823efed | 908 | { |
c203e8a7 | 909 | value_type **slot = find_slot_with_hash (comparable, hash, NO_INSERT); |
0823efed DN |
910 | if (*slot == HTAB_EMPTY_ENTRY) |
911 | return; | |
912 | ||
5831a5f0 | 913 | Descriptor::remove (*slot); |
0823efed | 914 | |
5831a5f0 | 915 | *slot = static_cast <value_type *> (HTAB_DELETED_ENTRY); |
c203e8a7 | 916 | m_n_deleted++; |
0823efed DN |
917 | } |
918 | ||
0823efed DN |
919 | /* This function scans over the entire hash table calling CALLBACK for |
920 | each live entry. If CALLBACK returns false, the iteration stops. | |
921 | ARGUMENT is passed as CALLBACK's second argument. */ | |
922 | ||
84baa4b9 | 923 | template<typename Descriptor, template<typename Type> class Allocator> |
c203e8a7 | 924 | template<typename Argument, |
e4e01495 TS |
925 | int (*Callback) (typename hash_table<Descriptor, Allocator, |
926 | false>::value_type **slot, | |
927 | Argument argument)> | |
0823efed | 928 | void |
84baa4b9 | 929 | hash_table<Descriptor, Allocator, false>::traverse_noresize (Argument argument) |
0823efed | 930 | { |
c203e8a7 TS |
931 | value_type **slot = m_entries; |
932 | value_type **limit = slot + size (); | |
0823efed DN |
933 | |
934 | do | |
935 | { | |
5831a5f0 | 936 | value_type *x = *slot; |
0823efed DN |
937 | |
938 | if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) | |
939 | if (! Callback (slot, argument)) | |
940 | break; | |
941 | } | |
942 | while (++slot < limit); | |
943 | } | |
944 | ||
0823efed DN |
945 | /* Like traverse_noresize, but does resize the table when it is too empty |
946 | to improve effectivity of subsequent calls. */ | |
947 | ||
5831a5f0 | 948 | template <typename Descriptor, |
0823efed DN |
949 | template <typename Type> class Allocator> |
950 | template <typename Argument, | |
e4e01495 TS |
951 | int (*Callback) (typename hash_table<Descriptor, Allocator, |
952 | false>::value_type **slot, | |
5831a5f0 | 953 | Argument argument)> |
0823efed | 954 | void |
84baa4b9 | 955 | hash_table<Descriptor, Allocator, false>::traverse (Argument argument) |
0823efed | 956 | { |
c203e8a7 | 957 | size_t size = m_size; |
0823efed DN |
958 | if (elements () * 8 < size && size > 32) |
959 | expand (); | |
960 | ||
961 | traverse_noresize <Argument, Callback> (argument); | |
962 | } | |
963 | ||
bf190e8d LC |
964 | /* Slide down the iterator slots until an active entry is found. */ |
965 | ||
c203e8a7 | 966 | template<typename Descriptor, template<typename Type> class Allocator> |
bf190e8d | 967 | void |
84baa4b9 | 968 | hash_table<Descriptor, Allocator, false>::iterator::slide () |
bf190e8d | 969 | { |
65d3284b | 970 | for ( ; m_slot < m_limit; ++m_slot ) |
bf190e8d | 971 | { |
65d3284b | 972 | value_type *x = *m_slot; |
bf190e8d LC |
973 | if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY) |
974 | return; | |
975 | } | |
65d3284b RS |
976 | m_slot = NULL; |
977 | m_limit = NULL; | |
bf190e8d LC |
978 | } |
979 | ||
980 | /* Bump the iterator. */ | |
981 | ||
c203e8a7 | 982 | template<typename Descriptor, template<typename Type> class Allocator> |
84baa4b9 TS |
983 | inline typename hash_table<Descriptor, Allocator, false>::iterator & |
984 | hash_table<Descriptor, Allocator, false>::iterator::operator ++ () | |
985 | { | |
986 | ++m_slot; | |
987 | slide (); | |
988 | return *this; | |
989 | } | |
990 | ||
991 | /* A partial specialization used when values should be stored directly. */ | |
992 | ||
993 | template <typename Descriptor, | |
994 | template<typename Type> class Allocator> | |
995 | class hash_table<Descriptor, Allocator, true> | |
996 | { | |
997 | typedef typename Descriptor::value_type value_type; | |
998 | typedef typename Descriptor::compare_type compare_type; | |
999 | ||
1000 | public: | |
1001 | hash_table (size_t); | |
1002 | ~hash_table (); | |
1003 | ||
1004 | /* Current size (in entries) of the hash table. */ | |
1005 | size_t size () const { return m_size; } | |
1006 | ||
1007 | /* Return the current number of elements in this hash table. */ | |
1008 | size_t elements () const { return m_n_elements - m_n_deleted; } | |
1009 | ||
1010 | /* Return the current number of elements in this hash table. */ | |
1011 | size_t elements_with_deleted () const { return m_n_elements; } | |
1012 | ||
1013 | /* This function clears all entries in the given hash table. */ | |
1014 | void empty (); | |
1015 | ||
1016 | /* This function clears a specified SLOT in a hash table. It is | |
1017 | useful when you've already done the lookup and don't want to do it | |
1018 | again. */ | |
1019 | ||
1020 | void clear_slot (value_type *); | |
1021 | ||
1022 | /* This function searches for a hash table entry equal to the given | |
1023 | COMPARABLE element starting with the given HASH value. It cannot | |
1024 | be used to insert or delete an element. */ | |
1025 | value_type &find_with_hash (const compare_type &, hashval_t); | |
1026 | ||
1027 | /* Like find_slot_with_hash, but compute the hash value from the element. */ | |
1028 | value_type &find (const value_type &value) | |
1029 | { | |
1030 | return find_with_hash (value, Descriptor::hash (value)); | |
1031 | } | |
1032 | ||
1033 | value_type *find_slot (const value_type &value, insert_option insert) | |
1034 | { | |
1035 | return find_slot_with_hash (value, Descriptor::hash (value), insert); | |
1036 | } | |
1037 | ||
1038 | /* This function searches for a hash table slot containing an entry | |
1039 | equal to the given COMPARABLE element and starting with the given | |
1040 | HASH. To delete an entry, call this with insert=NO_INSERT, then | |
1041 | call clear_slot on the slot returned (possibly after doing some | |
1042 | checks). To insert an entry, call this with insert=INSERT, then | |
1043 | write the value you want into the returned slot. When inserting an | |
1044 | entry, NULL may be returned if memory allocation fails. */ | |
1045 | value_type *find_slot_with_hash (const compare_type &comparable, | |
1046 | hashval_t hash, enum insert_option insert); | |
1047 | ||
1048 | /* This function deletes an element with the given COMPARABLE value | |
1049 | from hash table starting with the given HASH. If there is no | |
1050 | matching element in the hash table, this function does nothing. */ | |
1051 | void remove_elt_with_hash (const compare_type &, hashval_t); | |
1052 | ||
1053 | /* Like remove_elt_with_hash, but compute the hash value from the element. */ | |
1054 | void remove_elt (const value_type &value) | |
1055 | { | |
1056 | remove_elt_with_hash (value, Descriptor::hash (value)); | |
1057 | } | |
1058 | ||
1059 | /* This function scans over the entire hash table calling CALLBACK for | |
1060 | each live entry. If CALLBACK returns false, the iteration stops. | |
1061 | ARGUMENT is passed as CALLBACK's second argument. */ | |
1062 | template <typename Argument, | |
1063 | int (*Callback) (value_type *slot, Argument argument)> | |
1064 | void traverse_noresize (Argument argument); | |
1065 | ||
1066 | /* Like traverse_noresize, but does resize the table when it is too empty | |
1067 | to improve effectivity of subsequent calls. */ | |
1068 | template <typename Argument, | |
1069 | int (*Callback) (value_type *slot, Argument argument)> | |
1070 | void traverse (Argument argument); | |
1071 | ||
1072 | class iterator | |
1073 | { | |
1074 | public: | |
1075 | iterator () : m_slot (NULL), m_limit (NULL) {} | |
1076 | ||
1077 | iterator (value_type *slot, value_type *limit) : | |
1078 | m_slot (slot), m_limit (limit) {} | |
1079 | ||
1080 | inline value_type &operator * () { return *m_slot; } | |
1081 | void slide (); | |
1082 | inline iterator &operator ++ (); | |
1083 | bool operator != (const iterator &other) const | |
1084 | { | |
1085 | return m_slot != other.m_slot || m_limit != other.m_limit; | |
1086 | } | |
1087 | ||
1088 | private: | |
1089 | value_type *m_slot; | |
1090 | value_type *m_limit; | |
1091 | }; | |
1092 | ||
1093 | iterator begin () const | |
1094 | { | |
1095 | iterator iter (m_entries, m_entries + m_size); | |
1096 | iter.slide (); | |
1097 | return iter; | |
1098 | } | |
1099 | ||
1100 | iterator end () const { return iterator (); } | |
1101 | ||
1102 | double collisions () const | |
1103 | { | |
1104 | return m_searches ? static_cast <double> (m_collisions) / m_searches : 0; | |
1105 | } | |
1106 | ||
1107 | private: | |
1108 | ||
1109 | value_type *find_empty_slot_for_expand (hashval_t); | |
1110 | void expand (); | |
1111 | static bool is_deleted (value_type &v) | |
1112 | { | |
1113 | return is_deleted_helper<value_type, Descriptor>::call (v); | |
1114 | } | |
1115 | static bool is_empty (value_type &v) | |
1116 | { | |
1117 | return is_empty_helper<value_type, Descriptor>::call (v); | |
1118 | } | |
1119 | ||
1120 | static void mark_deleted (value_type &v) | |
1121 | { | |
1122 | return mark_deleted_helper<value_type, Descriptor>::call (v); | |
1123 | } | |
1124 | ||
1125 | static void mark_empty (value_type &v) | |
1126 | { | |
1127 | return mark_empty_helper<value_type, Descriptor>::call (v); | |
1128 | } | |
1129 | ||
1130 | /* Table itself. */ | |
1131 | typename Descriptor::value_type *m_entries; | |
1132 | ||
1133 | size_t m_size; | |
1134 | ||
1135 | /* Current number of elements including also deleted elements. */ | |
1136 | size_t m_n_elements; | |
1137 | ||
1138 | /* Current number of deleted elements in the table. */ | |
1139 | size_t m_n_deleted; | |
1140 | ||
1141 | /* The following member is used for debugging. Its value is number | |
1142 | of all calls of `htab_find_slot' for the hash table. */ | |
1143 | unsigned int m_searches; | |
1144 | ||
1145 | /* The following member is used for debugging. Its value is number | |
1146 | of collisions fixed for time of work with the hash table. */ | |
1147 | unsigned int m_collisions; | |
1148 | ||
1149 | /* Current size (in entries) of the hash table, as an index into the | |
1150 | table of primes. */ | |
1151 | unsigned int m_size_prime_index; | |
1152 | }; | |
1153 | ||
1154 | template<typename Descriptor, template<typename Type> class Allocator> | |
1155 | hash_table<Descriptor, Allocator, true>::hash_table (size_t size) : | |
1156 | m_n_elements (0), m_n_deleted (0), m_searches (0), m_collisions (0) | |
1157 | { | |
1158 | unsigned int size_prime_index; | |
1159 | ||
1160 | size_prime_index = hash_table_higher_prime_index (size); | |
1161 | size = prime_tab[size_prime_index].prime; | |
1162 | ||
1163 | m_entries = Allocator <value_type> ::data_alloc (size); | |
1164 | gcc_assert (m_entries != NULL); | |
1165 | m_size = size; | |
1166 | m_size_prime_index = size_prime_index; | |
1167 | } | |
1168 | ||
1169 | template<typename Descriptor, template<typename Type> class Allocator> | |
1170 | hash_table<Descriptor, Allocator, true>::~hash_table () | |
1171 | { | |
1172 | for (size_t i = m_size - 1; i < m_size; i--) | |
1173 | if (!is_empty (m_entries[i]) && !is_deleted (m_entries[i])) | |
1174 | Descriptor::remove (m_entries[i]); | |
1175 | ||
1176 | Allocator <value_type> ::data_free (m_entries); | |
1177 | } | |
1178 | ||
1179 | /* Similar to find_slot, but without several unwanted side effects: | |
1180 | - Does not call equal when it finds an existing entry. | |
1181 | - Does not change the count of elements/searches/collisions in the | |
1182 | hash table. | |
1183 | This function also assumes there are no deleted entries in the table. | |
1184 | HASH is the hash value for the element to be inserted. */ | |
1185 | ||
1186 | template<typename Descriptor, template<typename Type> class Allocator> | |
e4e01495 | 1187 | typename hash_table<Descriptor, Allocator, true>::value_type * |
84baa4b9 TS |
1188 | hash_table<Descriptor, Allocator, true> |
1189 | ::find_empty_slot_for_expand (hashval_t hash) | |
1190 | { | |
1191 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); | |
1192 | size_t size = m_size; | |
1193 | value_type *slot = m_entries + index; | |
1194 | hashval_t hash2; | |
1195 | ||
1196 | if (is_empty (*slot)) | |
1197 | return slot; | |
1198 | else if (is_deleted (*slot)) | |
1199 | abort (); | |
1200 | ||
1201 | hash2 = hash_table_mod2 (hash, m_size_prime_index); | |
1202 | for (;;) | |
1203 | { | |
1204 | index += hash2; | |
1205 | if (index >= size) | |
1206 | index -= size; | |
1207 | ||
1208 | slot = m_entries + index; | |
1209 | if (is_empty (*slot)) | |
1210 | return slot; | |
1211 | else if (is_deleted (*slot)) | |
1212 | abort (); | |
1213 | } | |
1214 | } | |
1215 | ||
1216 | /* The following function changes size of memory allocated for the | |
1217 | entries and repeatedly inserts the table elements. The occupancy | |
1218 | of the table after the call will be about 50%. Naturally the hash | |
1219 | table must already exist. Remember also that the place of the | |
1220 | table entries is changed. If memory allocation fails, this function | |
1221 | will abort. */ | |
1222 | ||
1223 | template<typename Descriptor, template<typename Type> class Allocator> | |
1224 | void | |
1225 | hash_table<Descriptor, Allocator, true>::expand () | |
1226 | { | |
1227 | value_type *oentries = m_entries; | |
1228 | unsigned int oindex = m_size_prime_index; | |
1229 | size_t osize = size (); | |
1230 | value_type *olimit = oentries + osize; | |
1231 | size_t elts = elements (); | |
1232 | ||
1233 | /* Resize only when table after removal of unused elements is either | |
1234 | too full or too empty. */ | |
1235 | unsigned int nindex; | |
1236 | size_t nsize; | |
1237 | if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) | |
1238 | { | |
1239 | nindex = hash_table_higher_prime_index (elts * 2); | |
1240 | nsize = prime_tab[nindex].prime; | |
1241 | } | |
1242 | else | |
1243 | { | |
1244 | nindex = oindex; | |
1245 | nsize = osize; | |
1246 | } | |
1247 | ||
1248 | value_type *nentries = Allocator <value_type> ::data_alloc (nsize); | |
1249 | gcc_assert (nentries != NULL); | |
1250 | m_entries = nentries; | |
1251 | m_size = nsize; | |
1252 | m_size_prime_index = nindex; | |
1253 | m_n_elements -= m_n_deleted; | |
1254 | m_n_deleted = 0; | |
1255 | ||
1256 | value_type *p = oentries; | |
1257 | do | |
1258 | { | |
1259 | value_type &x = *p; | |
1260 | ||
1261 | if (!is_empty (x) && !is_deleted (x)) | |
1262 | { | |
1263 | value_type *q = find_empty_slot_for_expand (Descriptor::hash (x)); | |
1264 | ||
1265 | *q = x; | |
1266 | } | |
1267 | ||
1268 | p++; | |
1269 | } | |
1270 | while (p < olimit); | |
1271 | ||
1272 | Allocator <value_type> ::data_free (oentries); | |
1273 | } | |
1274 | ||
1275 | template<typename Descriptor, template<typename Type> class Allocator> | |
1276 | void | |
1277 | hash_table<Descriptor, Allocator, true>::empty () | |
1278 | { | |
1279 | size_t size = m_size; | |
1280 | value_type *entries = m_entries; | |
1281 | int i; | |
1282 | ||
1283 | for (i = size - 1; i >= 0; i--) | |
1284 | if (!is_empty (entries[i]) && !is_deleted (entries[i])) | |
1285 | Descriptor::remove (entries[i]); | |
1286 | ||
1287 | /* Instead of clearing megabyte, downsize the table. */ | |
1288 | if (size > 1024*1024 / sizeof (PTR)) | |
1289 | { | |
1290 | int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR)); | |
1291 | int nsize = prime_tab[nindex].prime; | |
1292 | ||
1293 | Allocator <value_type> ::data_free (m_entries); | |
1294 | m_entries = Allocator <value_type> ::data_alloc (nsize); | |
1295 | m_size = nsize; | |
1296 | m_size_prime_index = nindex; | |
1297 | } | |
1298 | else | |
1299 | memset (entries, 0, size * sizeof (value_type)); | |
1300 | m_n_deleted = 0; | |
1301 | m_n_elements = 0; | |
1302 | } | |
1303 | ||
1304 | /* This function clears a specified SLOT in a hash table. It is | |
1305 | useful when you've already done the lookup and don't want to do it | |
1306 | again. */ | |
1307 | ||
1308 | template<typename Descriptor, template<typename Type> class Allocator> | |
1309 | void | |
1310 | hash_table<Descriptor, Allocator, true>::clear_slot (value_type *slot) | |
1311 | { | |
1312 | if (slot < m_entries || slot >= m_entries + size () | |
1313 | || is_empty (*slot) || is_deleted (*slot)) | |
1314 | abort (); | |
1315 | ||
1316 | Descriptor::remove (*slot); | |
1317 | ||
1318 | mark_deleted (*slot); | |
1319 | m_n_deleted++; | |
1320 | } | |
1321 | ||
1322 | /* This function searches for a hash table entry equal to the given | |
1323 | COMPARABLE element starting with the given HASH value. It cannot | |
1324 | be used to insert or delete an element. */ | |
1325 | ||
1326 | template<typename Descriptor, template<typename Type> class Allocator> | |
e4e01495 | 1327 | typename hash_table<Descriptor, Allocator, true>::value_type & |
84baa4b9 TS |
1328 | hash_table<Descriptor, Allocator, true> |
1329 | ::find_with_hash (const compare_type &comparable, hashval_t hash) | |
1330 | { | |
1331 | m_searches++; | |
1332 | size_t size = m_size; | |
1333 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); | |
1334 | ||
1335 | value_type *entry = &m_entries[index]; | |
1336 | if (is_empty (*entry) | |
1337 | || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable))) | |
1338 | return *entry; | |
1339 | ||
1340 | hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); | |
1341 | for (;;) | |
1342 | { | |
1343 | m_collisions++; | |
1344 | index += hash2; | |
1345 | if (index >= size) | |
1346 | index -= size; | |
1347 | ||
1348 | entry = &m_entries[index]; | |
1349 | if (is_empty (*entry) | |
1350 | || (!is_deleted (*entry) && Descriptor::equal (*entry, comparable))) | |
1351 | return *entry; | |
1352 | } | |
1353 | } | |
1354 | ||
1355 | /* This function searches for a hash table slot containing an entry | |
1356 | equal to the given COMPARABLE element and starting with the given | |
1357 | HASH. To delete an entry, call this with insert=NO_INSERT, then | |
1358 | call clear_slot on the slot returned (possibly after doing some | |
1359 | checks). To insert an entry, call this with insert=INSERT, then | |
1360 | write the value you want into the returned slot. When inserting an | |
1361 | entry, NULL may be returned if memory allocation fails. */ | |
1362 | ||
1363 | template<typename Descriptor, template<typename Type> class Allocator> | |
e4e01495 | 1364 | typename hash_table<Descriptor, Allocator, true>::value_type * |
84baa4b9 TS |
1365 | hash_table<Descriptor, Allocator, true> |
1366 | ::find_slot_with_hash (const compare_type &comparable, hashval_t hash, | |
1367 | enum insert_option insert) | |
1368 | { | |
1369 | if (insert == INSERT && m_size * 3 <= m_n_elements * 4) | |
1370 | expand (); | |
1371 | ||
1372 | m_searches++; | |
1373 | ||
1374 | value_type *first_deleted_slot = NULL; | |
1375 | hashval_t index = hash_table_mod1 (hash, m_size_prime_index); | |
1376 | hashval_t hash2 = hash_table_mod2 (hash, m_size_prime_index); | |
1377 | value_type *entry = &m_entries[index]; | |
1378 | size_t size = m_size; | |
1379 | if (is_empty (*entry)) | |
1380 | goto empty_entry; | |
1381 | else if (is_deleted (*entry)) | |
1382 | first_deleted_slot = &m_entries[index]; | |
1383 | else if (Descriptor::equal (*entry, comparable)) | |
1384 | return &m_entries[index]; | |
1385 | ||
1386 | for (;;) | |
1387 | { | |
1388 | m_collisions++; | |
1389 | index += hash2; | |
1390 | if (index >= size) | |
1391 | index -= size; | |
1392 | ||
1393 | entry = &m_entries[index]; | |
1394 | if (is_empty (*entry)) | |
1395 | goto empty_entry; | |
1396 | else if (is_deleted (*entry)) | |
1397 | { | |
1398 | if (!first_deleted_slot) | |
1399 | first_deleted_slot = &m_entries[index]; | |
1400 | } | |
1401 | else if (Descriptor::equal (*entry, comparable)) | |
1402 | return &m_entries[index]; | |
1403 | } | |
1404 | ||
1405 | empty_entry: | |
1406 | if (insert == NO_INSERT) | |
1407 | return NULL; | |
1408 | ||
1409 | if (first_deleted_slot) | |
1410 | { | |
1411 | m_n_deleted--; | |
1412 | mark_empty (*first_deleted_slot); | |
1413 | return first_deleted_slot; | |
1414 | } | |
1415 | ||
1416 | m_n_elements++; | |
1417 | return &m_entries[index]; | |
1418 | } | |
1419 | ||
1420 | /* This function deletes an element with the given COMPARABLE value | |
1421 | from hash table starting with the given HASH. If there is no | |
1422 | matching element in the hash table, this function does nothing. */ | |
1423 | ||
1424 | template<typename Descriptor, template<typename Type> class Allocator> | |
1425 | void | |
1426 | hash_table<Descriptor, Allocator, true> | |
1427 | ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash) | |
1428 | { | |
1429 | value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT); | |
1430 | if (is_empty (*slot)) | |
1431 | return; | |
1432 | ||
1433 | Descriptor::remove (*slot); | |
1434 | ||
1435 | mark_deleted (*slot); | |
1436 | m_n_deleted++; | |
1437 | } | |
1438 | ||
1439 | /* This function scans over the entire hash table calling CALLBACK for | |
1440 | each live entry. If CALLBACK returns false, the iteration stops. | |
1441 | ARGUMENT is passed as CALLBACK's second argument. */ | |
1442 | ||
1443 | template<typename Descriptor, | |
1444 | template<typename Type> class Allocator> | |
1445 | template<typename Argument, | |
e4e01495 TS |
1446 | int (*Callback) (typename hash_table<Descriptor, Allocator, |
1447 | true>::value_type *slot, | |
84baa4b9 TS |
1448 | Argument argument)> |
1449 | void | |
1450 | hash_table<Descriptor, Allocator, true>::traverse_noresize (Argument argument) | |
1451 | { | |
1452 | value_type *slot = m_entries; | |
1453 | value_type *limit = slot + size (); | |
1454 | ||
1455 | do | |
1456 | { | |
1457 | value_type &x = *slot; | |
1458 | ||
1459 | if (!is_empty (x) && !is_deleted (x)) | |
1460 | if (! Callback (slot, argument)) | |
1461 | break; | |
1462 | } | |
1463 | while (++slot < limit); | |
1464 | } | |
1465 | ||
1466 | /* Like traverse_noresize, but does resize the table when it is too empty | |
1467 | to improve effectivity of subsequent calls. */ | |
1468 | ||
1469 | template <typename Descriptor, | |
1470 | template <typename Type> class Allocator> | |
1471 | template <typename Argument, | |
e4e01495 TS |
1472 | int (*Callback) (typename hash_table<Descriptor, Allocator, |
1473 | true>::value_type *slot, | |
84baa4b9 TS |
1474 | Argument argument)> |
1475 | void | |
1476 | hash_table<Descriptor, Allocator, true>::traverse (Argument argument) | |
1477 | { | |
1478 | size_t size = m_size; | |
1479 | if (elements () * 8 < size && size > 32) | |
1480 | expand (); | |
1481 | ||
1482 | traverse_noresize <Argument, Callback> (argument); | |
1483 | } | |
1484 | ||
1485 | /* Slide down the iterator slots until an active entry is found. */ | |
1486 | ||
1487 | template<typename Descriptor, template<typename Type> class Allocator> | |
1488 | void | |
1489 | hash_table<Descriptor, Allocator, true>::iterator::slide () | |
1490 | { | |
1491 | for ( ; m_slot < m_limit; ++m_slot ) | |
1492 | { | |
1493 | value_type &x = *m_slot; | |
1494 | if (!is_empty (x) && !is_deleted (x)) | |
1495 | return; | |
1496 | } | |
1497 | m_slot = NULL; | |
1498 | m_limit = NULL; | |
1499 | } | |
1500 | ||
1501 | /* Bump the iterator. */ | |
1502 | ||
1503 | template<typename Descriptor, template<typename Type> class Allocator> | |
1504 | inline typename hash_table<Descriptor, Allocator, true>::iterator & | |
1505 | hash_table<Descriptor, Allocator, true>::iterator::operator ++ () | |
bf190e8d | 1506 | { |
65d3284b | 1507 | ++m_slot; |
bf190e8d LC |
1508 | slide (); |
1509 | return *this; | |
1510 | } | |
1511 | ||
bf190e8d LC |
1512 | |
1513 | /* Iterate through the elements of hash_table HTAB, | |
1514 | using hash_table <....>::iterator ITER, | |
3fadf78a | 1515 | storing each element in RESULT, which is of type TYPE. */ |
bf190e8d LC |
1516 | |
1517 | #define FOR_EACH_HASH_TABLE_ELEMENT(HTAB, RESULT, TYPE, ITER) \ | |
1518 | for ((ITER) = (HTAB).begin (); \ | |
84baa4b9 | 1519 | (ITER) != (HTAB).end () ? (RESULT = *(ITER) , true) : false; \ |
bf190e8d LC |
1520 | ++(ITER)) |
1521 | ||
0823efed | 1522 | #endif /* TYPED_HASHTAB_H */ |