Mercurial > hg > CbC > CbC_gcc
comparison libvtv/vtv_set.h @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* Copyright (C) 2012-2017 Free Software Foundation, Inc. | |
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 */ |