|
145
|
1 /* Copyright (C) 2012-2020 Free Software Foundation, Inc.
|
|
111
|
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 */
|
