1 | |
---|
2 | // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. |
---|
3 | // Copyright (C) 2005-2009 Daniel James |
---|
4 | // Distributed under the Boost Software License, Version 1.0. (See accompanying |
---|
5 | // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
---|
6 | |
---|
7 | // This contains the basic data structure, apart from the actual values. There's |
---|
8 | // no construction or deconstruction here. So this only depends on the pointer |
---|
9 | // type. |
---|
10 | |
---|
11 | #ifndef BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED |
---|
12 | #define BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED |
---|
13 | |
---|
14 | #include <boost/config.hpp> |
---|
15 | #include <boost/iterator.hpp> |
---|
16 | #include <boost/compressed_pair.hpp> |
---|
17 | #include <boost/type_traits/aligned_storage.hpp> |
---|
18 | #include <boost/type_traits/alignment_of.hpp> |
---|
19 | #include <boost/unordered/detail/allocator_helpers.hpp> |
---|
20 | #include <algorithm> |
---|
21 | |
---|
22 | // This header defines most of the classes used to implement the unordered |
---|
23 | // containers. It doesn't include the insert methods as they require a lot |
---|
24 | // of preprocessor metaprogramming - they are in insert.hpp |
---|
25 | |
---|
26 | // Template parameters: |
---|
27 | // |
---|
28 | // H = Hash Function |
---|
29 | // P = Predicate |
---|
30 | // A = Value Allocator |
---|
31 | // G = Grouped/Ungrouped |
---|
32 | // E = Key Extractor |
---|
33 | |
---|
34 | #if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES) |
---|
35 | # if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION) |
---|
36 | // STLport doesn't have std::forward. |
---|
37 | # else |
---|
38 | # define BOOST_UNORDERED_STD_FORWARD |
---|
39 | # endif |
---|
40 | #endif |
---|
41 | |
---|
42 | #if !defined(BOOST_UNORDERED_EMPLACE_LIMIT) |
---|
43 | #define BOOST_UNORDERED_EMPLACE_LIMIT 10 |
---|
44 | #endif |
---|
45 | |
---|
46 | #if !defined(BOOST_UNORDERED_STD_FORWARD) |
---|
47 | |
---|
48 | #include <boost/preprocessor/repetition/enum_params.hpp> |
---|
49 | #include <boost/preprocessor/repetition/enum_binary_params.hpp> |
---|
50 | #include <boost/preprocessor/repetition/repeat_from_to.hpp> |
---|
51 | |
---|
52 | #define BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ |
---|
53 | BOOST_PP_ENUM_PARAMS_Z(z, num_params, class Arg) |
---|
54 | #define BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ |
---|
55 | BOOST_PP_ENUM_BINARY_PARAMS_Z(z, num_params, Arg, const& arg) |
---|
56 | #define BOOST_UNORDERED_CALL_PARAMS(z, num_params) \ |
---|
57 | BOOST_PP_ENUM_PARAMS_Z(z, num_params, arg) |
---|
58 | |
---|
59 | #endif |
---|
60 | |
---|
61 | namespace boost { namespace unordered_detail { |
---|
62 | |
---|
63 | static const float minimum_max_load_factor = 1e-3f; |
---|
64 | static const std::size_t default_bucket_count = 11; |
---|
65 | struct move_tag {}; |
---|
66 | |
---|
67 | template <class T> class hash_unique_table; |
---|
68 | template <class T> class hash_equivalent_table; |
---|
69 | template <class Alloc, class Grouped> |
---|
70 | class hash_node_constructor; |
---|
71 | template <class ValueType> |
---|
72 | struct set_extractor; |
---|
73 | template <class Key, class ValueType> |
---|
74 | struct map_extractor; |
---|
75 | struct no_key; |
---|
76 | |
---|
77 | // Explicitly call a destructor |
---|
78 | |
---|
79 | #if defined(BOOST_MSVC) |
---|
80 | #pragma warning(push) |
---|
81 | #pragma warning(disable:4100) // unreferenced formal parameter |
---|
82 | #endif |
---|
83 | |
---|
84 | template <class T> |
---|
85 | inline void destroy(T* x) { |
---|
86 | x->~T(); |
---|
87 | } |
---|
88 | |
---|
89 | #if defined(BOOST_MSVC) |
---|
90 | #pragma warning(pop) |
---|
91 | #endif |
---|
92 | |
---|
93 | // hash_bucket |
---|
94 | |
---|
95 | template <class A> |
---|
96 | class hash_bucket |
---|
97 | { |
---|
98 | hash_bucket& operator=(hash_bucket const&); |
---|
99 | public: |
---|
100 | typedef hash_bucket<A> bucket; |
---|
101 | typedef BOOST_DEDUCED_TYPENAME |
---|
102 | boost::unordered_detail::rebind_wrap<A, bucket>::type |
---|
103 | bucket_allocator; |
---|
104 | typedef BOOST_DEDUCED_TYPENAME bucket_allocator::pointer bucket_ptr; |
---|
105 | typedef bucket_ptr node_ptr; |
---|
106 | |
---|
107 | node_ptr next_; |
---|
108 | |
---|
109 | hash_bucket() : next_() {} |
---|
110 | }; |
---|
111 | |
---|
112 | template <class A> |
---|
113 | struct ungrouped_node_base : hash_bucket<A> { |
---|
114 | typedef hash_bucket<A> bucket; |
---|
115 | typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; |
---|
116 | typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; |
---|
117 | |
---|
118 | ungrouped_node_base() : bucket() {} |
---|
119 | static inline node_ptr& next_group(node_ptr ptr); |
---|
120 | static inline std::size_t group_count(node_ptr ptr); |
---|
121 | static inline void add_to_bucket(node_ptr n, bucket& b); |
---|
122 | static inline void add_after_node(node_ptr n, node_ptr position); |
---|
123 | static void unlink_node(bucket& b, node_ptr n); |
---|
124 | static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end); |
---|
125 | static void unlink_nodes(bucket& b, node_ptr end); |
---|
126 | }; |
---|
127 | |
---|
128 | template <class A> |
---|
129 | struct grouped_node_base : hash_bucket<A> |
---|
130 | { |
---|
131 | typedef hash_bucket<A> bucket; |
---|
132 | typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; |
---|
133 | typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; |
---|
134 | |
---|
135 | node_ptr group_prev_; |
---|
136 | |
---|
137 | grouped_node_base() : bucket(), group_prev_() {} |
---|
138 | static inline node_ptr& next_group(node_ptr ptr); |
---|
139 | static inline node_ptr first_in_group(node_ptr n); |
---|
140 | static inline std::size_t group_count(node_ptr ptr); |
---|
141 | static inline void add_to_bucket(node_ptr n, bucket& b); |
---|
142 | static inline void add_after_node(node_ptr n, node_ptr position); |
---|
143 | static void unlink_node(bucket& b, node_ptr n); |
---|
144 | static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end); |
---|
145 | static void unlink_nodes(bucket& b, node_ptr end); |
---|
146 | |
---|
147 | private: |
---|
148 | static inline node_ptr split_group(node_ptr split); |
---|
149 | static inline grouped_node_base& get(node_ptr ptr) { |
---|
150 | return static_cast<grouped_node_base&>(*ptr); |
---|
151 | } |
---|
152 | }; |
---|
153 | |
---|
154 | struct ungrouped |
---|
155 | { |
---|
156 | template <class A> |
---|
157 | struct base { |
---|
158 | typedef ungrouped_node_base<A> type; |
---|
159 | }; |
---|
160 | }; |
---|
161 | |
---|
162 | struct grouped |
---|
163 | { |
---|
164 | template <class A> |
---|
165 | struct base { |
---|
166 | typedef grouped_node_base<A> type; |
---|
167 | }; |
---|
168 | }; |
---|
169 | |
---|
170 | template <class ValueType> |
---|
171 | struct value_base |
---|
172 | { |
---|
173 | typedef ValueType value_type; |
---|
174 | BOOST_DEDUCED_TYPENAME boost::aligned_storage< |
---|
175 | sizeof(value_type), |
---|
176 | ::boost::alignment_of<value_type>::value>::type data_; |
---|
177 | |
---|
178 | void* address() { |
---|
179 | return this; |
---|
180 | } |
---|
181 | value_type& value() { |
---|
182 | return *(ValueType*) this; |
---|
183 | } |
---|
184 | private: |
---|
185 | value_base& operator=(value_base const&); |
---|
186 | }; |
---|
187 | |
---|
188 | // Node |
---|
189 | |
---|
190 | template <class A, class G> |
---|
191 | class hash_node : |
---|
192 | public G::BOOST_NESTED_TEMPLATE base<A>::type, |
---|
193 | public value_base<BOOST_DEDUCED_TYPENAME A::value_type> |
---|
194 | { |
---|
195 | public: |
---|
196 | typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; |
---|
197 | typedef BOOST_DEDUCED_TYPENAME hash_bucket<A>::node_ptr node_ptr; |
---|
198 | |
---|
199 | static value_type& get_value(node_ptr p) { |
---|
200 | return static_cast<hash_node&>(*p).value(); |
---|
201 | } |
---|
202 | private: |
---|
203 | hash_node& operator=(hash_node const&); |
---|
204 | }; |
---|
205 | |
---|
206 | // Iterator Base |
---|
207 | |
---|
208 | template <class A, class G> |
---|
209 | class hash_iterator_base |
---|
210 | { |
---|
211 | public: |
---|
212 | typedef A value_allocator; |
---|
213 | typedef hash_bucket<A> bucket; |
---|
214 | typedef hash_node<A, G> node; |
---|
215 | typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; |
---|
216 | typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; |
---|
217 | typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; |
---|
218 | |
---|
219 | bucket_ptr bucket_; |
---|
220 | node_ptr node_; |
---|
221 | |
---|
222 | hash_iterator_base() : bucket_(), node_() {} |
---|
223 | explicit hash_iterator_base(bucket_ptr b) |
---|
224 | : bucket_(b), |
---|
225 | node_(b ? b->next_ : node_ptr()) {} |
---|
226 | hash_iterator_base(bucket_ptr b, node_ptr n) |
---|
227 | : bucket_(b), |
---|
228 | node_(n) {} |
---|
229 | |
---|
230 | bool operator==(hash_iterator_base const& x) const { |
---|
231 | return node_ == x.node_; } |
---|
232 | bool operator!=(hash_iterator_base const& x) const { |
---|
233 | return node_ != x.node_; } |
---|
234 | value_type& operator*() const { |
---|
235 | return node::get_value(node_); |
---|
236 | } |
---|
237 | |
---|
238 | void increment_bucket(node_ptr n) { |
---|
239 | while(!n) { |
---|
240 | ++bucket_; |
---|
241 | n = bucket_->next_; |
---|
242 | } |
---|
243 | node_ = bucket_ == n ? node_ptr() : n; |
---|
244 | } |
---|
245 | |
---|
246 | void increment() { |
---|
247 | increment_bucket(node_->next_); |
---|
248 | } |
---|
249 | }; |
---|
250 | |
---|
251 | // hash_buckets |
---|
252 | // |
---|
253 | // This is responsible for allocating and deallocating buckets and nodes. |
---|
254 | // |
---|
255 | // Notes: |
---|
256 | // 1. For the sake exception safety the allocators themselves don't allocate |
---|
257 | // anything. |
---|
258 | // 2. It's the callers responsibility to allocate the buckets before calling |
---|
259 | // any of the methods (other than getters and setters). |
---|
260 | |
---|
261 | template <class A, class G> |
---|
262 | class hash_buckets |
---|
263 | { |
---|
264 | hash_buckets(hash_buckets const&); |
---|
265 | hash_buckets& operator=(hash_buckets const&); |
---|
266 | public: |
---|
267 | // Types |
---|
268 | |
---|
269 | typedef A value_allocator; |
---|
270 | typedef hash_bucket<A> bucket; |
---|
271 | typedef hash_iterator_base<A, G> iterator_base; |
---|
272 | typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; |
---|
273 | typedef BOOST_DEDUCED_TYPENAME iterator_base::node node; |
---|
274 | |
---|
275 | typedef BOOST_DEDUCED_TYPENAME bucket::bucket_allocator |
---|
276 | bucket_allocator; |
---|
277 | typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; |
---|
278 | typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; |
---|
279 | |
---|
280 | typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type |
---|
281 | node_allocator; |
---|
282 | typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr; |
---|
283 | |
---|
284 | // Members |
---|
285 | |
---|
286 | bucket_ptr buckets_; |
---|
287 | std::size_t bucket_count_; |
---|
288 | boost::compressed_pair<bucket_allocator, node_allocator> allocators_; |
---|
289 | |
---|
290 | // Data access |
---|
291 | |
---|
292 | bucket_allocator const& bucket_alloc() const { |
---|
293 | return allocators_.first(); } |
---|
294 | node_allocator const& node_alloc() const { |
---|
295 | return allocators_.second(); } |
---|
296 | bucket_allocator& bucket_alloc() { |
---|
297 | return allocators_.first(); } |
---|
298 | node_allocator& node_alloc() { |
---|
299 | return allocators_.second(); } |
---|
300 | std::size_t max_bucket_count() const; |
---|
301 | |
---|
302 | // Constructors |
---|
303 | |
---|
304 | hash_buckets(node_allocator const& a, std::size_t n); |
---|
305 | void create_buckets(); |
---|
306 | ~hash_buckets(); |
---|
307 | |
---|
308 | // no throw |
---|
309 | void swap(hash_buckets& other); |
---|
310 | void move(hash_buckets& other); |
---|
311 | |
---|
312 | // For the remaining functions, buckets_ must not be null. |
---|
313 | |
---|
314 | bucket_ptr get_bucket(std::size_t n) const; |
---|
315 | bucket_ptr bucket_ptr_from_hash(std::size_t hashed) const; |
---|
316 | std::size_t bucket_size(std::size_t index) const; |
---|
317 | node_ptr bucket_begin(std::size_t n) const; |
---|
318 | |
---|
319 | // Alloc/Dealloc |
---|
320 | |
---|
321 | void delete_node(node_ptr); |
---|
322 | |
---|
323 | // |
---|
324 | void delete_buckets(); |
---|
325 | void clear_bucket(bucket_ptr); |
---|
326 | std::size_t delete_nodes(node_ptr begin, node_ptr end); |
---|
327 | std::size_t delete_to_bucket_end(node_ptr begin); |
---|
328 | }; |
---|
329 | |
---|
330 | template <class H, class P> class set_hash_functions; |
---|
331 | |
---|
332 | template <class H, class P> |
---|
333 | class hash_buffered_functions |
---|
334 | { |
---|
335 | friend class set_hash_functions<H, P>; |
---|
336 | hash_buffered_functions& operator=(hash_buffered_functions const&); |
---|
337 | |
---|
338 | typedef boost::compressed_pair<H, P> function_pair; |
---|
339 | typedef BOOST_DEDUCED_TYPENAME boost::aligned_storage< |
---|
340 | sizeof(function_pair), |
---|
341 | ::boost::alignment_of<function_pair>::value>::type aligned_function; |
---|
342 | |
---|
343 | bool current_; // The currently active functions. |
---|
344 | aligned_function funcs_[2]; |
---|
345 | |
---|
346 | function_pair const& current() const { |
---|
347 | return *static_cast<function_pair const*>( |
---|
348 | static_cast<void const*>(&funcs_[current_])); |
---|
349 | } |
---|
350 | |
---|
351 | void construct(bool which, H const& hf, P const& eq) |
---|
352 | { |
---|
353 | new((void*) &funcs_[which]) function_pair(hf, eq); |
---|
354 | } |
---|
355 | |
---|
356 | void construct(bool which, function_pair const& f) |
---|
357 | { |
---|
358 | new((void*) &funcs_[which]) function_pair(f); |
---|
359 | } |
---|
360 | |
---|
361 | void destroy(bool which) |
---|
362 | { |
---|
363 | boost::unordered_detail::destroy((function_pair*)(&funcs_[which])); |
---|
364 | } |
---|
365 | |
---|
366 | public: |
---|
367 | |
---|
368 | hash_buffered_functions(H const& hf, P const& eq) |
---|
369 | : current_(false) |
---|
370 | { |
---|
371 | construct(current_, hf, eq); |
---|
372 | } |
---|
373 | |
---|
374 | hash_buffered_functions(hash_buffered_functions const& bf) |
---|
375 | : current_(false) |
---|
376 | { |
---|
377 | construct(current_, bf.current()); |
---|
378 | } |
---|
379 | |
---|
380 | ~hash_buffered_functions() { |
---|
381 | destroy(current_); |
---|
382 | } |
---|
383 | |
---|
384 | H const& hash_function() const { |
---|
385 | return current().first(); |
---|
386 | } |
---|
387 | |
---|
388 | P const& key_eq() const { |
---|
389 | return current().second(); |
---|
390 | } |
---|
391 | }; |
---|
392 | |
---|
393 | template <class H, class P> |
---|
394 | class set_hash_functions |
---|
395 | { |
---|
396 | set_hash_functions(set_hash_functions const&); |
---|
397 | set_hash_functions& operator=(set_hash_functions const&); |
---|
398 | |
---|
399 | typedef hash_buffered_functions<H, P> buffered_functions; |
---|
400 | buffered_functions& buffered_functions_; |
---|
401 | bool tmp_functions_; |
---|
402 | |
---|
403 | public: |
---|
404 | |
---|
405 | set_hash_functions(buffered_functions& f, H const& h, P const& p) |
---|
406 | : buffered_functions_(f), |
---|
407 | tmp_functions_(!f.current_) |
---|
408 | { |
---|
409 | f.construct(tmp_functions_, h, p); |
---|
410 | } |
---|
411 | |
---|
412 | set_hash_functions(buffered_functions& f, |
---|
413 | buffered_functions const& other) |
---|
414 | : buffered_functions_(f), |
---|
415 | tmp_functions_(!f.current_) |
---|
416 | { |
---|
417 | f.construct(tmp_functions_, other.current()); |
---|
418 | } |
---|
419 | |
---|
420 | ~set_hash_functions() |
---|
421 | { |
---|
422 | buffered_functions_.destroy(tmp_functions_); |
---|
423 | } |
---|
424 | |
---|
425 | void commit() |
---|
426 | { |
---|
427 | buffered_functions_.current_ = tmp_functions_; |
---|
428 | tmp_functions_ = !tmp_functions_; |
---|
429 | } |
---|
430 | }; |
---|
431 | |
---|
432 | template <class T> |
---|
433 | class hash_table : public T::buckets, public T::buffered_functions |
---|
434 | { |
---|
435 | hash_table(hash_table const&); |
---|
436 | public: |
---|
437 | typedef BOOST_DEDUCED_TYPENAME T::hasher hasher; |
---|
438 | typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal; |
---|
439 | typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator; |
---|
440 | typedef BOOST_DEDUCED_TYPENAME T::key_type key_type; |
---|
441 | typedef BOOST_DEDUCED_TYPENAME T::value_type value_type; |
---|
442 | typedef BOOST_DEDUCED_TYPENAME T::buffered_functions base; |
---|
443 | typedef BOOST_DEDUCED_TYPENAME T::buckets buckets; |
---|
444 | typedef BOOST_DEDUCED_TYPENAME T::extractor extractor; |
---|
445 | typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor; |
---|
446 | |
---|
447 | typedef BOOST_DEDUCED_TYPENAME T::node node; |
---|
448 | typedef BOOST_DEDUCED_TYPENAME T::bucket bucket; |
---|
449 | typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr; |
---|
450 | typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr; |
---|
451 | typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base; |
---|
452 | typedef BOOST_DEDUCED_TYPENAME T::node_allocator node_allocator; |
---|
453 | typedef BOOST_DEDUCED_TYPENAME T::iterator_pair iterator_pair; |
---|
454 | |
---|
455 | // Members |
---|
456 | |
---|
457 | std::size_t size_; |
---|
458 | float mlf_; |
---|
459 | // Cached data - invalid if !this->buckets_ |
---|
460 | bucket_ptr cached_begin_bucket_; |
---|
461 | std::size_t max_load_; |
---|
462 | |
---|
463 | // Helper methods |
---|
464 | |
---|
465 | key_type const& get_key(value_type const& v) const { |
---|
466 | return extractor::extract(v); |
---|
467 | } |
---|
468 | key_type const& get_key_from_ptr(node_ptr n) const { |
---|
469 | return extractor::extract(node::get_value(n)); |
---|
470 | } |
---|
471 | bool equal(key_type const& k, value_type const& v) const; |
---|
472 | template <class Key, class Pred> |
---|
473 | node_ptr find_iterator(bucket_ptr bucket, Key const& k, |
---|
474 | Pred const&) const; |
---|
475 | node_ptr find_iterator(bucket_ptr bucket, key_type const& k) const; |
---|
476 | node_ptr find_iterator(key_type const& k) const; |
---|
477 | node_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const; |
---|
478 | |
---|
479 | // Load methods |
---|
480 | |
---|
481 | std::size_t max_size() const; |
---|
482 | std::size_t bucket_index(key_type const& k) const; |
---|
483 | void max_load_factor(float z); |
---|
484 | std::size_t min_buckets_for_size(std::size_t n) const; |
---|
485 | std::size_t calculate_max_load(); |
---|
486 | |
---|
487 | // Constructors |
---|
488 | |
---|
489 | hash_table(std::size_t n, hasher const& hf, key_equal const& eq, |
---|
490 | node_allocator const& a); |
---|
491 | hash_table(hash_table const& x, node_allocator const& a); |
---|
492 | hash_table(hash_table& x, move_tag m); |
---|
493 | hash_table(hash_table& x, node_allocator const& a, move_tag m); |
---|
494 | ~hash_table() {} |
---|
495 | hash_table& operator=(hash_table const&); |
---|
496 | |
---|
497 | // Iterators |
---|
498 | |
---|
499 | iterator_base begin() const { |
---|
500 | return this->size_ ? |
---|
501 | iterator_base(this->cached_begin_bucket_) : |
---|
502 | iterator_base(); |
---|
503 | } |
---|
504 | iterator_base end() const { |
---|
505 | return iterator_base(); |
---|
506 | } |
---|
507 | |
---|
508 | // Swap & Move |
---|
509 | |
---|
510 | void swap(hash_table& x); |
---|
511 | void fast_swap(hash_table& other); |
---|
512 | void slow_swap(hash_table& other); |
---|
513 | void partial_swap(hash_table& other); |
---|
514 | void move(hash_table& x); |
---|
515 | |
---|
516 | // Reserve and rehash |
---|
517 | |
---|
518 | void create_for_insert(std::size_t n); |
---|
519 | bool reserve_for_insert(std::size_t n); |
---|
520 | void rehash(std::size_t n); |
---|
521 | void rehash_impl(std::size_t n); |
---|
522 | |
---|
523 | // Move/copy buckets |
---|
524 | |
---|
525 | void move_buckets_to(buckets& dst); |
---|
526 | void copy_buckets_to(buckets& dst) const; |
---|
527 | |
---|
528 | // Misc. key methods |
---|
529 | |
---|
530 | std::size_t count(key_type const& k) const; |
---|
531 | iterator_base find(key_type const& k) const; |
---|
532 | template <class Key, class Hash, class Pred> |
---|
533 | iterator_base find(Key const& k, Hash const& h, Pred const& eq) const; |
---|
534 | value_type& at(key_type const& k) const; |
---|
535 | iterator_pair equal_range(key_type const& k) const; |
---|
536 | |
---|
537 | // Erase |
---|
538 | // |
---|
539 | // no throw |
---|
540 | |
---|
541 | void clear(); |
---|
542 | std::size_t erase_key(key_type const& k); |
---|
543 | iterator_base erase_return_iterator(iterator_base r); |
---|
544 | void erase(iterator_base r); |
---|
545 | std::size_t erase_group(node_ptr* it, bucket_ptr bucket); |
---|
546 | iterator_base erase_range(iterator_base r1, iterator_base r2); |
---|
547 | |
---|
548 | // recompute_begin_bucket |
---|
549 | |
---|
550 | void init_buckets(); |
---|
551 | |
---|
552 | // After an erase cached_begin_bucket_ might be left pointing to |
---|
553 | // an empty bucket, so this is called to update it |
---|
554 | // |
---|
555 | // no throw |
---|
556 | |
---|
557 | void recompute_begin_bucket(bucket_ptr b); |
---|
558 | |
---|
559 | // This is called when a range has been erased |
---|
560 | // |
---|
561 | // no throw |
---|
562 | |
---|
563 | void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2); |
---|
564 | |
---|
565 | // no throw |
---|
566 | float load_factor() const; |
---|
567 | |
---|
568 | iterator_base emplace_empty_impl_with_node( |
---|
569 | node_constructor&, std::size_t); |
---|
570 | }; |
---|
571 | |
---|
572 | // Iterator Access |
---|
573 | |
---|
574 | #if !defined(__clang__) |
---|
575 | class iterator_access |
---|
576 | { |
---|
577 | public: |
---|
578 | template <class Iterator> |
---|
579 | static BOOST_DEDUCED_TYPENAME Iterator::base const& |
---|
580 | get(Iterator const& it) |
---|
581 | { |
---|
582 | return it.base_; |
---|
583 | } |
---|
584 | }; |
---|
585 | #else |
---|
586 | class iterator_access |
---|
587 | { |
---|
588 | public: |
---|
589 | // Note: we access Iterator::base here, rather than in the function |
---|
590 | // signature to work around a bug in the friend support of an |
---|
591 | // early version of clang. |
---|
592 | |
---|
593 | template <class Iterator> |
---|
594 | struct base |
---|
595 | { |
---|
596 | typedef BOOST_DEDUCED_TYPENAME Iterator::base type; |
---|
597 | }; |
---|
598 | |
---|
599 | template <class Iterator> |
---|
600 | static BOOST_DEDUCED_TYPENAME base<Iterator>::type const& |
---|
601 | get(Iterator const& it) |
---|
602 | { |
---|
603 | return it.base_; |
---|
604 | } |
---|
605 | }; |
---|
606 | #endif |
---|
607 | |
---|
608 | // Iterators |
---|
609 | |
---|
610 | template <class A, class G> class hash_iterator; |
---|
611 | template <class A, class G> class hash_const_iterator; |
---|
612 | template <class A, class G> class hash_local_iterator; |
---|
613 | template <class A, class G> class hash_const_local_iterator; |
---|
614 | |
---|
615 | // Local Iterators |
---|
616 | // |
---|
617 | // all no throw |
---|
618 | |
---|
619 | template <class A, class G> |
---|
620 | class hash_local_iterator |
---|
621 | : public boost::iterator < |
---|
622 | std::forward_iterator_tag, |
---|
623 | BOOST_DEDUCED_TYPENAME A::value_type, |
---|
624 | std::ptrdiff_t, |
---|
625 | BOOST_DEDUCED_TYPENAME A::pointer, |
---|
626 | BOOST_DEDUCED_TYPENAME A::reference> |
---|
627 | { |
---|
628 | public: |
---|
629 | typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; |
---|
630 | |
---|
631 | private: |
---|
632 | typedef hash_buckets<A, G> buckets; |
---|
633 | typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr; |
---|
634 | typedef BOOST_DEDUCED_TYPENAME buckets::node node; |
---|
635 | typedef hash_const_local_iterator<A, G> const_local_iterator; |
---|
636 | |
---|
637 | friend class hash_const_local_iterator<A, G>; |
---|
638 | node_ptr ptr_; |
---|
639 | |
---|
640 | public: |
---|
641 | hash_local_iterator() : ptr_() {} |
---|
642 | explicit hash_local_iterator(node_ptr x) : ptr_(x) {} |
---|
643 | BOOST_DEDUCED_TYPENAME A::reference operator*() const { |
---|
644 | return node::get_value(ptr_); |
---|
645 | } |
---|
646 | value_type* operator->() const { |
---|
647 | return &node::get_value(ptr_); |
---|
648 | } |
---|
649 | hash_local_iterator& operator++() { |
---|
650 | ptr_ = ptr_->next_; return *this; |
---|
651 | } |
---|
652 | hash_local_iterator operator++(int) { |
---|
653 | hash_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; } |
---|
654 | bool operator==(hash_local_iterator x) const { |
---|
655 | return ptr_ == x.ptr_; |
---|
656 | } |
---|
657 | bool operator==(const_local_iterator x) const { |
---|
658 | return ptr_ == x.ptr_; |
---|
659 | } |
---|
660 | bool operator!=(hash_local_iterator x) const { |
---|
661 | return ptr_ != x.ptr_; |
---|
662 | } |
---|
663 | bool operator!=(const_local_iterator x) const { |
---|
664 | return ptr_ != x.ptr_; |
---|
665 | } |
---|
666 | }; |
---|
667 | |
---|
668 | template <class A, class G> |
---|
669 | class hash_const_local_iterator |
---|
670 | : public boost::iterator < |
---|
671 | std::forward_iterator_tag, |
---|
672 | BOOST_DEDUCED_TYPENAME A::value_type, |
---|
673 | std::ptrdiff_t, |
---|
674 | BOOST_DEDUCED_TYPENAME A::const_pointer, |
---|
675 | BOOST_DEDUCED_TYPENAME A::const_reference > |
---|
676 | { |
---|
677 | public: |
---|
678 | typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; |
---|
679 | |
---|
680 | private: |
---|
681 | typedef hash_buckets<A, G> buckets; |
---|
682 | typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr; |
---|
683 | typedef BOOST_DEDUCED_TYPENAME buckets::node node; |
---|
684 | typedef hash_local_iterator<A, G> local_iterator; |
---|
685 | friend class hash_local_iterator<A, G>; |
---|
686 | ptr ptr_; |
---|
687 | |
---|
688 | public: |
---|
689 | hash_const_local_iterator() : ptr_() {} |
---|
690 | explicit hash_const_local_iterator(ptr x) : ptr_(x) {} |
---|
691 | hash_const_local_iterator(local_iterator x) : ptr_(x.ptr_) {} |
---|
692 | BOOST_DEDUCED_TYPENAME A::const_reference |
---|
693 | operator*() const { |
---|
694 | return node::get_value(ptr_); |
---|
695 | } |
---|
696 | value_type const* operator->() const { |
---|
697 | return &node::get_value(ptr_); |
---|
698 | } |
---|
699 | hash_const_local_iterator& operator++() { |
---|
700 | ptr_ = ptr_->next_; return *this; |
---|
701 | } |
---|
702 | hash_const_local_iterator operator++(int) { |
---|
703 | hash_const_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; |
---|
704 | } |
---|
705 | bool operator==(local_iterator x) const { |
---|
706 | return ptr_ == x.ptr_; |
---|
707 | } |
---|
708 | bool operator==(hash_const_local_iterator x) const { |
---|
709 | return ptr_ == x.ptr_; |
---|
710 | } |
---|
711 | bool operator!=(local_iterator x) const { |
---|
712 | return ptr_ != x.ptr_; |
---|
713 | } |
---|
714 | bool operator!=(hash_const_local_iterator x) const { |
---|
715 | return ptr_ != x.ptr_; |
---|
716 | } |
---|
717 | }; |
---|
718 | |
---|
719 | // iterators |
---|
720 | // |
---|
721 | // all no throw |
---|
722 | |
---|
723 | |
---|
724 | template <class A, class G> |
---|
725 | class hash_iterator |
---|
726 | : public boost::iterator < |
---|
727 | std::forward_iterator_tag, |
---|
728 | BOOST_DEDUCED_TYPENAME A::value_type, |
---|
729 | std::ptrdiff_t, |
---|
730 | BOOST_DEDUCED_TYPENAME A::pointer, |
---|
731 | BOOST_DEDUCED_TYPENAME A::reference > |
---|
732 | { |
---|
733 | public: |
---|
734 | typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; |
---|
735 | |
---|
736 | private: |
---|
737 | typedef hash_buckets<A, G> buckets; |
---|
738 | typedef BOOST_DEDUCED_TYPENAME buckets::node node; |
---|
739 | typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base; |
---|
740 | typedef hash_const_iterator<A, G> const_iterator; |
---|
741 | friend class hash_const_iterator<A, G>; |
---|
742 | base base_; |
---|
743 | |
---|
744 | public: |
---|
745 | |
---|
746 | hash_iterator() : base_() {} |
---|
747 | explicit hash_iterator(base const& x) : base_(x) {} |
---|
748 | BOOST_DEDUCED_TYPENAME A::reference operator*() const { |
---|
749 | return *base_; |
---|
750 | } |
---|
751 | value_type* operator->() const { |
---|
752 | return &*base_; |
---|
753 | } |
---|
754 | hash_iterator& operator++() { |
---|
755 | base_.increment(); return *this; |
---|
756 | } |
---|
757 | hash_iterator operator++(int) { |
---|
758 | hash_iterator tmp(base_); base_.increment(); return tmp; |
---|
759 | } |
---|
760 | bool operator==(hash_iterator const& x) const { |
---|
761 | return base_ == x.base_; |
---|
762 | } |
---|
763 | bool operator==(const_iterator const& x) const { |
---|
764 | return base_ == x.base_; |
---|
765 | } |
---|
766 | bool operator!=(hash_iterator const& x) const { |
---|
767 | return base_ != x.base_; |
---|
768 | } |
---|
769 | bool operator!=(const_iterator const& x) const { |
---|
770 | return base_ != x.base_; |
---|
771 | } |
---|
772 | }; |
---|
773 | |
---|
774 | template <class A, class G> |
---|
775 | class hash_const_iterator |
---|
776 | : public boost::iterator < |
---|
777 | std::forward_iterator_tag, |
---|
778 | BOOST_DEDUCED_TYPENAME A::value_type, |
---|
779 | std::ptrdiff_t, |
---|
780 | BOOST_DEDUCED_TYPENAME A::const_pointer, |
---|
781 | BOOST_DEDUCED_TYPENAME A::const_reference > |
---|
782 | { |
---|
783 | public: |
---|
784 | typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; |
---|
785 | |
---|
786 | private: |
---|
787 | typedef hash_buckets<A, G> buckets; |
---|
788 | typedef BOOST_DEDUCED_TYPENAME buckets::node node; |
---|
789 | typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base; |
---|
790 | typedef hash_iterator<A, G> iterator; |
---|
791 | friend class hash_iterator<A, G>; |
---|
792 | friend class iterator_access; |
---|
793 | base base_; |
---|
794 | |
---|
795 | public: |
---|
796 | |
---|
797 | hash_const_iterator() : base_() {} |
---|
798 | explicit hash_const_iterator(base const& x) : base_(x) {} |
---|
799 | hash_const_iterator(iterator const& x) : base_(x.base_) {} |
---|
800 | BOOST_DEDUCED_TYPENAME A::const_reference operator*() const { |
---|
801 | return *base_; |
---|
802 | } |
---|
803 | value_type const* operator->() const { |
---|
804 | return &*base_; |
---|
805 | } |
---|
806 | hash_const_iterator& operator++() { |
---|
807 | base_.increment(); return *this; |
---|
808 | } |
---|
809 | hash_const_iterator operator++(int) { |
---|
810 | hash_const_iterator tmp(base_); base_.increment(); return tmp; |
---|
811 | } |
---|
812 | bool operator==(iterator const& x) const { |
---|
813 | return base_ == x.base_; |
---|
814 | } |
---|
815 | bool operator==(hash_const_iterator const& x) const { |
---|
816 | return base_ == x.base_; |
---|
817 | } |
---|
818 | bool operator!=(iterator const& x) const { |
---|
819 | return base_ != x.base_; |
---|
820 | } |
---|
821 | bool operator!=(hash_const_iterator const& x) const { |
---|
822 | return base_ != x.base_; |
---|
823 | } |
---|
824 | }; |
---|
825 | |
---|
826 | // types |
---|
827 | |
---|
828 | template <class K, class V, class H, class P, class A, class E, class G> |
---|
829 | struct types |
---|
830 | { |
---|
831 | public: |
---|
832 | typedef K key_type; |
---|
833 | typedef V value_type; |
---|
834 | typedef H hasher; |
---|
835 | typedef P key_equal; |
---|
836 | typedef A value_allocator; |
---|
837 | typedef E extractor; |
---|
838 | typedef G group_type; |
---|
839 | |
---|
840 | typedef hash_node_constructor<value_allocator, group_type> |
---|
841 | node_constructor; |
---|
842 | typedef hash_buckets<value_allocator, group_type> buckets; |
---|
843 | typedef hash_buffered_functions<hasher, key_equal> buffered_functions; |
---|
844 | |
---|
845 | typedef BOOST_DEDUCED_TYPENAME buckets::node node; |
---|
846 | typedef BOOST_DEDUCED_TYPENAME buckets::bucket bucket; |
---|
847 | typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr; |
---|
848 | typedef BOOST_DEDUCED_TYPENAME buckets::bucket_ptr bucket_ptr; |
---|
849 | typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base iterator_base; |
---|
850 | typedef BOOST_DEDUCED_TYPENAME buckets::node_allocator node_allocator; |
---|
851 | |
---|
852 | typedef std::pair<iterator_base, iterator_base> iterator_pair; |
---|
853 | }; |
---|
854 | }} |
---|
855 | |
---|
856 | #endif |
---|