]>
Commit | Line | Data |
---|---|---|
fbd26352 | 1 | /* Copyright (C) 2012-2019 Free Software Foundation, Inc. |
b710ec85 | 2 | |
3 | This file is part of GCC. | |
4 | ||
5 | GCC is free software; you can redistribute it and/or modify it | |
6 | under the terms of the GNU General Public License as published by | |
7 | the Free Software Foundation; either version 3, or (at your option) | |
8 | any later version. | |
9 | ||
10 | GCC is distributed in the hope that it will be useful, but WITHOUT | |
11 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
12 | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
13 | License for more details. | |
14 | ||
15 | Under Section 7 of GPL version 3, you are granted additional | |
16 | permissions described in the GCC Runtime Library Exception, version | |
17 | 3.1, as published by the Free Software Foundation. | |
18 | ||
19 | You should have received a copy of the GNU General Public License | |
20 | and a copy of the GCC Runtime Library Exception along with this | |
21 | program; see the files COPYING3 and COPYING.RUNTIME respectively. | |
22 | If not, see <http://www.gnu.org/licenses/>. */ | |
23 | ||
24 | #ifndef _VTV_SET_H | |
25 | #define _VTV_SET_H 1 | |
26 | ||
27 | /* Code in this file manages a collection of insert-only sets. We | |
28 | have only tested the case where Key is uintptr_t, though it | |
29 | theoretically should work for some other cases. All odd keys are | |
30 | reserved, and must not be inserted into any of the sets. This code | |
31 | is intended primarily for sets of pointers, and the code is | |
32 | optimized for small sets (including size 0 and 1), but regardless | |
33 | of the set size, insert() and contains() have close to O(1) speed | |
34 | in practice. | |
35 | ||
36 | TODO(gpike): fix this comment. | |
37 | ||
38 | Recommended multithreaded use of a set: | |
39 | ||
40 | For speed, we want to use a lock-free test for set membership. The | |
41 | code handles simultaneous reads and inserts, as long as at most one | |
42 | insertion is in progress at a time. After an insert, other threads | |
43 | may not immediately "see" the inserted key if they perform a | |
44 | lock-free read, so we recommend retrying, as explained below. | |
45 | ||
46 | Also, to make data corruption less likely, we recommend using a | |
47 | "normal" RW page as well as one or pages that are typically RO | |
48 | but that can be switched to RW and back as needed. The latter | |
49 | pages should contain sets. The former should contain a lock, L, | |
50 | and an int or similar, num_writers. Then, to insert, something | |
51 | like this would be safe: | |
52 | o Acquire L. | |
53 | o Increment num_writers; if that made it 1, change pages to RW. | |
54 | o Release L. | |
55 | o while (there are insertions to do in some set, S) { | |
56 | acquire L; | |
57 | do some insertions in S; | |
58 | release L; | |
59 | } | |
60 | o Acquire L. | |
61 | o Decrement num_writers; if that made it 0, change pages to RO. | |
62 | o Release L. | |
63 | ||
64 | And to check if the set contains some key, one could use | |
65 | set.contains(key) || | |
66 | ({ Acquire L; bool b = set.contains(key); Release L; b; }) | |
67 | ||
68 | In this scheme, the number of threads with reads in progress isn't | |
69 | tracked, so old sets can never be deleted. In addition, on some | |
70 | architectures the intentionally racy reads might cause contains() | |
71 | to return true when it should have returned false. This should be | |
72 | no problem on x86, and most other machines, where reading or | |
73 | writing an aligned uintptr_t is atomic. E.g., on those machines, | |
74 | if *p is 0 and one thread does *p = x while another reads *p, the | |
75 | read will see either 0 or x. | |
76 | ||
77 | To make the above easier, the insert_only_hash_sets class provides | |
78 | an interface to manipulate any number of hash sets. One shouldn't | |
79 | create objects of that class, as it has no member data and its | |
80 | methods are static. | |
81 | ||
82 | So the recommended model is to have a single lock, a single | |
83 | num_writers variable, and some number of sets. If lock contention | |
84 | becomes a problem then the sets can be divided into k groups, each | |
85 | of which has a lock and a num_writers variable; or each set can be | |
86 | represented as a set of values that equal 0 mod m, a set of values | |
87 | that equal 1 mod m, ..., plus a set of values that equal m-1 mod m. | |
88 | ||
89 | However, we expect most or all uses of this code to call contains() | |
90 | much more frequently than anything else, so lock contention is | |
91 | likely to be low. */ | |
92 | ||
93 | #include <algorithm> | |
94 | ||
95 | #ifndef HASHTABLE_STATS | |
96 | #define HASHTABLE_STATS 0 | |
97 | #endif | |
98 | ||
99 | #ifndef HASHTABLE_STATS_ATOMIC | |
100 | #define HASHTABLE_STATS_ATOMIC 0 | |
101 | #endif | |
102 | ||
103 | #if HASHTABLE_STATS | |
104 | #if HASHTABLE_STATS_ATOMIC | |
105 | /* Stat counters, with atomics. */ | |
106 | #include <bits/atomic_word.h> | |
107 | ||
108 | typedef _Atomic_word _AtomicStatCounter; | |
109 | ||
110 | void | |
111 | inc_by (_AtomicStatCounter &stat, int amount) | |
112 | { | |
113 | __atomic_add_fetch (&stat, amount, __ATOMIC_ACQ_REL); | |
114 | } | |
115 | ||
116 | #else | |
117 | ||
118 | /* Stat counters, but without atomics. */ | |
119 | typedef int _AtomicStatCounter; | |
120 | ||
121 | void | |
122 | inc_by (_AtomicStatCounter& stat, int amount) | |
123 | { | |
124 | stat += amount; | |
125 | } | |
126 | ||
127 | #endif | |
128 | ||
129 | ||
130 | /* Number of calls to contains(), insert(), etc. */ | |
131 | extern _AtomicStatCounter stat_insert; | |
132 | extern _AtomicStatCounter stat_contains; | |
133 | extern _AtomicStatCounter stat_resize; | |
134 | extern _AtomicStatCounter stat_create; | |
135 | ||
136 | /* Sum of set size over all calls to contains(). */ | |
137 | extern _AtomicStatCounter stat_contains_sizes; | |
138 | ||
139 | /* contains() calls in a set whose capacity is more than 1. */ | |
140 | extern _AtomicStatCounter stat_contains_in_non_trivial_set; | |
141 | ||
142 | /* Probes in a set whose capacity is more than 1. Ideally, this will | |
143 | be pretty close to stat_contains_in_non_trivial_set. That will | |
144 | happen if our hash function is good and/or important keys were | |
145 | inserted before unimportant keys. */ | |
146 | extern _AtomicStatCounter stat_probes_in_non_trivial_set; | |
147 | ||
148 | /* number of calls to contains() with size=0, 1, etc. */ | |
149 | extern _AtomicStatCounter stat_contains_size0; | |
150 | extern _AtomicStatCounter stat_contains_size1; | |
151 | extern _AtomicStatCounter stat_contains_size2; | |
152 | extern _AtomicStatCounter stat_contains_size3; | |
153 | extern _AtomicStatCounter stat_contains_size4; | |
154 | extern _AtomicStatCounter stat_contains_size5; | |
155 | extern _AtomicStatCounter stat_contains_size6; | |
156 | extern _AtomicStatCounter stat_contains_size7; | |
157 | extern _AtomicStatCounter stat_contains_size8; | |
158 | extern _AtomicStatCounter stat_contains_size9; | |
159 | extern _AtomicStatCounter stat_contains_size10; | |
160 | extern _AtomicStatCounter stat_contains_size11; | |
161 | extern _AtomicStatCounter stat_contains_size12; | |
162 | extern _AtomicStatCounter stat_contains_size13_or_more; | |
163 | extern _AtomicStatCounter stat_grow_from_size0_to_1; | |
164 | extern _AtomicStatCounter stat_grow_from_size1_to_2; | |
165 | extern _AtomicStatCounter stat_double_the_number_of_buckets; | |
166 | extern _AtomicStatCounter stat_insert_key_that_was_already_present; | |
167 | ||
168 | /* Hash collisions detected during insert_no_resize(). Only counts | |
169 | hasher(k) == hasher(k'); hasher(k) % tablesize == hasher(k') % | |
170 | tablesize is not sufficient. Will count collisions that are | |
171 | detected during table resizes etc., so the same two keys may add to | |
172 | this stat multiple times. */ | |
173 | extern _AtomicStatCounter stat_insert_found_hash_collision; | |
174 | ||
175 | #include <string> | |
176 | ||
177 | struct insert_only_hash_sets_logger | |
178 | { | |
179 | static char * | |
180 | log (char c, char *buf) | |
181 | { | |
182 | *buf++ = c; | |
183 | return buf; | |
184 | } | |
185 | ||
186 | static char * | |
187 | log (const char *s, char *buf) | |
188 | { return strcpy (buf, s) + strlen (s); } | |
189 | ||
190 | static char * | |
191 | log (_AtomicStatCounter i, char *buf) | |
192 | { | |
193 | if (i < 10) | |
194 | return log ((char) ('0' + i), buf); | |
195 | else | |
196 | return log ((char) ('0' + i % 10), log (i / 10, buf)); | |
197 | } | |
198 | ||
199 | static char * | |
200 | log (const char *label, _AtomicStatCounter i, char *buf) | |
201 | { | |
202 | buf = log (label, buf); | |
203 | buf = log (": ", buf); | |
204 | buf = log (i, buf); | |
205 | return log ('\n', buf); | |
206 | } | |
207 | }; | |
208 | ||
209 | // Write stats to the given buffer, which should be at least 4000 bytes. | |
210 | static inline void | |
211 | insert_only_hash_tables_stats (char *buf) | |
212 | { | |
213 | buf = insert_only_hash_sets_logger::log ("insert", stat_insert, buf); | |
214 | buf = insert_only_hash_sets_logger::log ("contains", stat_contains, buf); | |
215 | buf = insert_only_hash_sets_logger::log ("resize", stat_resize, buf); | |
216 | buf = insert_only_hash_sets_logger::log ("create", stat_create, buf); | |
217 | buf = insert_only_hash_sets_logger::log ("insert_key_that_was_already_" | |
218 | "present", | |
219 | stat_insert_key_that_was_already_present, | |
220 | buf); | |
221 | buf = insert_only_hash_sets_logger::log ("contains_sizes", | |
222 | stat_contains_sizes, buf); | |
223 | buf = insert_only_hash_sets_logger::log ("contains_in_non_trivial_set", | |
224 | stat_contains_in_non_trivial_set, | |
225 | buf); | |
226 | buf = insert_only_hash_sets_logger::log ("probes_in_non_trivial_set", | |
227 | stat_probes_in_non_trivial_set, | |
228 | buf); | |
229 | buf = insert_only_hash_sets_logger::log ("contains_size0", | |
230 | stat_contains_size0, buf); | |
231 | buf = insert_only_hash_sets_logger::log ("contains_size1", | |
232 | stat_contains_size1, buf); | |
233 | buf = insert_only_hash_sets_logger::log ("contains_size2", | |
234 | stat_contains_size2, buf); | |
235 | buf = insert_only_hash_sets_logger::log ("contains_size3", | |
236 | stat_contains_size3, buf); | |
237 | buf = insert_only_hash_sets_logger::log ("contains_size4", | |
238 | stat_contains_size4, buf); | |
239 | buf = insert_only_hash_sets_logger::log ("contains_size5", | |
240 | stat_contains_size5, buf); | |
241 | buf = insert_only_hash_sets_logger::log ("contains_size6", | |
242 | stat_contains_size6, buf); | |
243 | buf = insert_only_hash_sets_logger::log ("contains_size7", | |
244 | stat_contains_size7, buf); | |
245 | buf = insert_only_hash_sets_logger::log ("contains_size8", | |
246 | stat_contains_size8, buf); | |
247 | buf = insert_only_hash_sets_logger::log ("contains_size9", | |
248 | stat_contains_size9, buf); | |
249 | buf = insert_only_hash_sets_logger::log ("contains_size10", | |
250 | stat_contains_size10, buf); | |
251 | buf = insert_only_hash_sets_logger::log ("contains_size11", | |
252 | stat_contains_size11, buf); | |
253 | buf = insert_only_hash_sets_logger::log ("contains_size12", | |
254 | stat_contains_size12, buf); | |
255 | buf = insert_only_hash_sets_logger::log ("contains_size13_or_more", | |
256 | stat_contains_size13_or_more, buf); | |
257 | buf = insert_only_hash_sets_logger::log ("grow_from_size0_to_1", | |
258 | stat_grow_from_size0_to_1, buf); | |
259 | buf = insert_only_hash_sets_logger::log ("grow_from_size1_to_2", | |
260 | stat_grow_from_size1_to_2, buf); | |
261 | buf = insert_only_hash_sets_logger::log ("insert_found_hash_collision", | |
262 | stat_insert_found_hash_collision, | |
263 | buf); | |
264 | buf = insert_only_hash_sets_logger::log ("double_the_number_of_buckets", | |
265 | stat_double_the_number_of_buckets, | |
266 | buf); | |
267 | *buf = '\0'; | |
268 | } | |
269 | ||
270 | #else | |
271 | ||
272 | /* No stats. */ | |
273 | #define inc_by(statname, amount) do { } while (false && (amount)) | |
274 | ||
275 | #endif | |
276 | ||
277 | #define inc(statname) inc_by (statname, 1) | |
278 | ||
279 | template <typename Key, class HashFcn, class Alloc> | |
280 | class insert_only_hash_sets | |
281 | { | |
282 | public: | |
283 | typedef Key key_type; | |
284 | typedef size_t size_type; | |
285 | typedef Alloc alloc_type; | |
286 | enum { illegal_key = 1 }; | |
287 | enum { min_capacity = 4 }; | |
288 | #if HASHTABLE_STATS | |
289 | enum { stats = true }; | |
290 | #else | |
291 | enum { stats = false }; | |
292 | #endif | |
293 | ||
294 | /* Do not directly use insert_only_hash_set. Instead, use the | |
295 | static methods below to create and manipulate objects of the | |
296 | following class. | |
297 | ||
298 | Implementation details: each set is represented by a pointer | |
299 | plus, perhaps, out-of-line data, which would be an object of type | |
300 | insert_only_hash_set. For a pointer, s, the interpretation is: s | |
301 | == NULL means empty set, lsb(s) == 1 means a set with one | |
302 | element, which is (uintptr_t)s - 1, and otherwise s is a pointer | |
303 | of type insert_only_hash_set*. So, to increase the size of a set | |
304 | we have to change s and/or *s. To check if a set contains some | |
305 | key we have to examine s and possibly *s. */ | |
306 | class insert_only_hash_set | |
307 | { | |
308 | public: | |
309 | /* Insert a key. The key must not be a reserved key. */ | |
310 | static inline insert_only_hash_set *insert (key_type key, | |
311 | insert_only_hash_set *s); | |
312 | ||
313 | ||
314 | /* Create an empty set. */ | |
315 | static inline insert_only_hash_set *create (size_type capacity); | |
316 | ||
317 | /* Return whether the given key is present. If key is illegal_key | |
318 | then either true or false may be returned, but for all other | |
319 | reserved keys false will be returned. */ | |
320 | static bool | |
321 | contains (key_type key, const insert_only_hash_set *s) | |
322 | { | |
323 | if (stats) | |
324 | { | |
325 | inc (stat_contains); | |
326 | switch (size (s)) | |
327 | { | |
328 | case 0: inc (stat_contains_size0); break; | |
329 | case 1: inc (stat_contains_size1); break; | |
330 | case 2: inc (stat_contains_size2); break; | |
331 | case 3: inc (stat_contains_size3); break; | |
332 | case 4: inc (stat_contains_size4); break; | |
333 | case 5: inc (stat_contains_size5); break; | |
334 | case 6: inc (stat_contains_size6); break; | |
335 | case 7: inc (stat_contains_size7); break; | |
336 | case 8: inc (stat_contains_size8); break; | |
337 | case 9: inc (stat_contains_size9); break; | |
338 | case 10: inc (stat_contains_size10); break; | |
339 | case 11: inc (stat_contains_size11); break; | |
340 | case 12: inc (stat_contains_size12); break; | |
341 | default: inc (stat_contains_size13_or_more); break; | |
342 | } | |
343 | inc_by (stat_contains_sizes, size (s)); | |
344 | } | |
345 | ||
346 | return (singleton (s) ? | |
347 | singleton_key (key) == s : | |
348 | ((s != NULL) && s->contains (key))); | |
349 | } | |
350 | ||
351 | /* Return a set's size. */ | |
352 | static size_type | |
353 | size (const insert_only_hash_set *s) | |
354 | { return (s == NULL) ? 0 : (singleton (s) ? 1 : s->num_entries); } | |
355 | ||
356 | static inline insert_only_hash_set *resize (size_type target_num_buckets, | |
357 | insert_only_hash_set *s); | |
358 | ||
359 | ||
360 | private: | |
361 | /* Return whether a set has size 1. */ | |
362 | static bool | |
363 | singleton (const insert_only_hash_set *s) | |
364 | { return (uintptr_t) s & 1; } | |
365 | ||
366 | /* Return the representation of a singleton set containing the | |
367 | given key. */ | |
368 | static insert_only_hash_set * | |
369 | singleton_key (key_type key) | |
370 | { return (insert_only_hash_set *) ((uintptr_t) key + 1); } | |
371 | ||
372 | /* Given a singleton set, what key does it contain? */ | |
373 | static key_type | |
374 | extract_singleton_key (const insert_only_hash_set *s) | |
375 | { | |
376 | VTV_DEBUG_ASSERT (singleton (s)); | |
377 | return (key_type) ((uintptr_t) s - 1); | |
378 | } | |
379 | ||
380 | volatile key_type & | |
381 | key_at_index (size_type index) | |
382 | { return buckets[index]; } | |
383 | ||
384 | key_type | |
385 | key_at_index (size_type index) const | |
386 | { return buckets[index]; } | |
387 | ||
388 | size_type | |
389 | next_index (size_type index, size_type indices_examined) const | |
390 | { return (index + indices_examined) & (num_buckets - 1); } | |
391 | ||
392 | inline void insert_no_resize (key_type key); | |
393 | ||
394 | inline bool contains (key_type key) const; | |
395 | ||
396 | inline insert_only_hash_set *resize_if_necessary (void); | |
397 | ||
398 | size_type num_buckets; /* Must be a power of 2 not less than | |
399 | min_capacity. */ | |
400 | volatile size_type num_entries; | |
401 | volatile key_type buckets[0]; /* Actual array size is num_buckets. */ | |
402 | }; | |
403 | ||
404 | /* Create an empty set with the given capacity. Requires that n be | |
405 | 0 or a power of 2. If 1 < n < min_capacity then treat n as | |
406 | min_capacity. Sets *handle. Returns true unless the allocator | |
407 | fails. Subsequent operations on this set should use the same | |
408 | handle. */ | |
409 | ||
410 | static inline bool create (size_type n, insert_only_hash_set **handle); | |
411 | ||
412 | /* Force the capacity of a set to be n, unless it was more than n | |
413 | already. Requires that n be 0 or a power of 2. Sets *handle | |
414 | unless the current capacity is n or more. Returns true unless | |
415 | the allocator fails. */ | |
416 | ||
417 | static inline bool resize (size_type n, insert_only_hash_set **handle); | |
418 | ||
419 | /* Insert a key. *handle is unmodified unless (1) a resize occurs, | |
420 | or (2) the set was initially empty. Returns true unless the | |
421 | allocator fails during a resize. If the allocator fails during a | |
422 | resize then the set is reset to be the empty set. The key must | |
423 | not be a reserved key. */ | |
424 | ||
425 | static inline bool insert (key_type key, insert_only_hash_set **handle); | |
426 | ||
427 | /* Check for the presence of a key. If key is illegal_key then | |
428 | either true or false may be returned, but for all other reserved | |
429 | keys false will be returned. */ | |
430 | ||
431 | static inline bool | |
432 | contains (key_type key, /* const */ insert_only_hash_set **handle) | |
433 | { return insert_only_hash_set::contains (key, *handle); } | |
434 | ||
435 | /* Return the size of the given set. */ | |
436 | static size_type | |
437 | size (const insert_only_hash_set **handle) | |
438 | { return insert_only_hash_set::size (*handle); } | |
439 | ||
440 | static bool | |
441 | is_reserved_key (key_type key) | |
442 | { return ((uintptr_t) key % 2) == 1; } | |
443 | }; | |
444 | ||
445 | template <typename Key, class HashFcn, class Alloc> | |
446 | typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set * | |
447 | insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::resize | |
448 | (size_type n, insert_only_hash_set *s) | |
449 | { | |
450 | if (s == NULL) | |
451 | return create (n); | |
452 | ||
453 | size_type capacity = singleton (s) ? 1 : s->num_buckets; | |
454 | ||
455 | if (n <= capacity) | |
456 | return s; | |
457 | ||
458 | insert_only_hash_set *result = | |
459 | create (std::max<size_type> (n, min_capacity)); | |
460 | if (result != NULL) | |
461 | { | |
462 | if (singleton (s)) | |
463 | { | |
464 | result->insert_no_resize (extract_singleton_key (s)); | |
465 | } | |
466 | else | |
467 | { | |
468 | for (size_type i = 0; i < s->num_buckets; i++) | |
469 | if (s->buckets[i] != (key_type) illegal_key) | |
470 | result->insert_no_resize (s->buckets[i]); | |
471 | } | |
472 | VTV_DEBUG_ASSERT (size (result) == size (s)); | |
473 | } | |
474 | return result; | |
475 | } | |
476 | ||
477 | template <typename Key, class HashFcn, class Alloc> | |
478 | typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set * | |
479 | insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::insert | |
480 | (key_type key, insert_only_hash_set *s) | |
481 | { | |
482 | VTV_DEBUG_ASSERT (!is_reserved_key (key)); | |
483 | ||
484 | inc_by (stat_grow_from_size0_to_1, s == NULL); | |
485 | ||
486 | if (s == NULL) | |
487 | return singleton_key (key); | |
488 | ||
489 | if (singleton (s)) | |
490 | { | |
491 | const key_type old_key = extract_singleton_key (s); | |
492 | if (old_key == key) | |
493 | return s; | |
494 | ||
495 | /* Grow from size 1 to size 2. */ | |
496 | inc (stat_grow_from_size1_to_2); | |
497 | s = create (2); | |
498 | if (s == NULL) | |
499 | return NULL; | |
500 | ||
501 | s->insert_no_resize (old_key); | |
502 | s->insert_no_resize (key); | |
503 | VTV_DEBUG_ASSERT (size (s) == 2); | |
504 | return s; | |
505 | } | |
506 | s = s->resize_if_necessary(); | |
507 | if (s != NULL) | |
508 | s->insert_no_resize (key); | |
509 | return s; | |
510 | } | |
511 | ||
512 | template <typename Key, class HashFcn, class Alloc> | |
513 | typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set * | |
514 | insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set::create | |
515 | (size_type capacity) | |
516 | { | |
517 | if (capacity <= 1) | |
518 | return NULL; | |
519 | ||
520 | VTV_DEBUG_ASSERT (capacity > 1 && (capacity & (capacity - 1)) == 0); | |
521 | VTV_DEBUG_ASSERT (sizeof (insert_only_hash_set) == 2 * sizeof (size_type)); | |
522 | capacity = std::max <size_type> (capacity, min_capacity); | |
523 | const size_t num_bytes = sizeof (insert_only_hash_set) + | |
524 | sizeof (key_type) * capacity; | |
525 | alloc_type alloc; | |
526 | insert_only_hash_set *result = (insert_only_hash_set *) alloc (num_bytes); | |
527 | result->num_buckets = capacity; | |
528 | result->num_entries = 0; | |
529 | for (size_type i = 0; i < capacity; i++) | |
530 | result->buckets[i] = (key_type) illegal_key; | |
531 | return result; | |
532 | } | |
533 | ||
534 | template <typename Key, class HashFcn, class Alloc> | |
535 | void | |
536 | insert_only_hash_sets<Key, HashFcn, | |
537 | Alloc>::insert_only_hash_set::insert_no_resize | |
538 | (key_type key) | |
539 | { | |
540 | HashFcn hasher; | |
541 | const size_type capacity = num_buckets; | |
542 | VTV_DEBUG_ASSERT (capacity >= min_capacity); | |
543 | VTV_DEBUG_ASSERT (!is_reserved_key (key)); | |
544 | size_type index = hasher (key) & (capacity - 1); | |
545 | key_type k = key_at_index (index); | |
546 | size_type indices_examined = 0; | |
547 | while (k != key) | |
548 | { | |
549 | ++indices_examined; | |
550 | if (k == (key_type) illegal_key) | |
551 | { | |
552 | key_at_index (index) = key; | |
553 | ++num_entries; | |
554 | return; | |
555 | } | |
556 | else | |
557 | { | |
558 | inc_by (stat_insert_found_hash_collision, | |
559 | hasher (k) == hasher (key)); | |
560 | } | |
561 | VTV_DEBUG_ASSERT (indices_examined < capacity); | |
562 | index = next_index (index, indices_examined); | |
563 | k = key_at_index (index); | |
564 | } | |
565 | } | |
566 | ||
567 | template<typename Key, class HashFcn, class Alloc> | |
568 | bool | |
569 | insert_only_hash_sets<Key, HashFcn, Alloc>::insert_only_hash_set::contains | |
570 | (key_type key) const | |
571 | { | |
572 | inc (stat_contains_in_non_trivial_set); | |
573 | HashFcn hasher; | |
574 | const size_type capacity = num_buckets; | |
575 | size_type index = hasher (key) & (capacity - 1); | |
576 | key_type k = key_at_index (index); | |
577 | size_type indices_examined = 0; | |
578 | inc (stat_probes_in_non_trivial_set); | |
579 | while (k != key) | |
580 | { | |
581 | ++indices_examined; | |
582 | if (/*UNLIKELY*/(k == (key_type) illegal_key | |
583 | || indices_examined == capacity)) | |
584 | return false; | |
585 | ||
586 | index = next_index (index, indices_examined); | |
587 | k = key_at_index (index); | |
588 | inc (stat_probes_in_non_trivial_set); | |
589 | } | |
590 | return true; | |
591 | } | |
592 | ||
593 | template <typename Key, class HashFcn, class Alloc> | |
594 | typename insert_only_hash_sets <Key, HashFcn, Alloc>::insert_only_hash_set * | |
595 | insert_only_hash_sets<Key, HashFcn, | |
596 | Alloc>::insert_only_hash_set::resize_if_necessary (void) | |
597 | { | |
598 | VTV_DEBUG_ASSERT (num_buckets >= min_capacity); | |
599 | size_type unused = num_buckets - num_entries; | |
600 | if (unused < (num_buckets >> 2)) | |
601 | { | |
602 | inc (stat_double_the_number_of_buckets); | |
603 | size_type new_num_buckets = num_buckets * 2; | |
604 | insert_only_hash_set *s = create (new_num_buckets); | |
605 | for (size_type i = 0; i < num_buckets; i++) | |
606 | if (buckets[i] != (key_type) illegal_key) | |
607 | s->insert_no_resize (buckets[i]); | |
608 | VTV_DEBUG_ASSERT (size (this) == size (s)); | |
609 | return s; | |
610 | } | |
611 | else | |
612 | return this; | |
613 | } | |
614 | ||
615 | template<typename Key, class HashFcn, class Alloc> | |
616 | bool | |
617 | insert_only_hash_sets<Key, HashFcn, Alloc>::create (size_type n, | |
618 | insert_only_hash_set **handle) | |
619 | ||
620 | { | |
621 | inc (stat_create); | |
622 | *handle = insert_only_hash_set::create (n); | |
623 | return (n <= 1) || (*handle != NULL); | |
624 | } | |
625 | ||
626 | template<typename Key, class HashFcn, class Alloc> | |
627 | bool | |
628 | insert_only_hash_sets<Key, HashFcn, Alloc>::resize (size_type n, | |
629 | insert_only_hash_set **handle) | |
630 | { | |
631 | inc (stat_resize); | |
632 | *handle = insert_only_hash_set::resize (n, *handle); | |
633 | return (n <= 1) || (*handle != NULL); | |
634 | } | |
635 | ||
636 | template<typename Key, class HashFcn, class Alloc> | |
637 | bool | |
638 | insert_only_hash_sets<Key, HashFcn, Alloc>::insert (key_type key, | |
639 | insert_only_hash_set **handle) | |
640 | { | |
641 | inc (stat_insert); | |
642 | const size_type old_size = insert_only_hash_set::size (*handle); | |
643 | *handle = insert_only_hash_set::insert (key, *handle); | |
644 | if (*handle != NULL) | |
645 | { | |
646 | const size_type delta = insert_only_hash_set::size (*handle) - old_size; | |
647 | inc_by (stat_insert_key_that_was_already_present, delta == 0); | |
648 | } | |
649 | return *handle != NULL; | |
650 | } | |
651 | ||
652 | #endif /* VTV_SET_H */ |