]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | |
2 | // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. | |
3 | // Copyright (C) 2005-2011 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 | #ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED | |
8 | #define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED | |
9 | ||
10 | #include <boost/config.hpp> | |
11 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
12 | #pragma once | |
13 | #endif | |
14 | ||
15 | #include <boost/unordered/detail/util.hpp> | |
16 | #include <boost/unordered/detail/allocate.hpp> | |
17 | ||
18 | namespace boost { namespace unordered { namespace detail { | |
19 | ||
20 | template <typename Types> struct table; | |
21 | template <typename NodePointer> struct bucket; | |
22 | struct ptr_bucket; | |
23 | template <typename Types> struct table_impl; | |
24 | template <typename Types> struct grouped_table_impl; | |
25 | ||
26 | }}} | |
27 | ||
28 | // The 'iterator_detail' namespace was a misguided attempt at avoiding ADL | |
29 | // in the detail namespace. It didn't work because the template parameters | |
30 | // were in detail. I'm not changing it at the moment to be safe. I might | |
31 | // do in the future if I change the iterator types. | |
32 | namespace boost { namespace unordered { namespace iterator_detail { | |
33 | ||
34 | //////////////////////////////////////////////////////////////////////////// | |
35 | // Iterators | |
36 | // | |
37 | // all no throw | |
38 | ||
39 | template <typename Node> struct iterator; | |
40 | template <typename Node> struct c_iterator; | |
41 | template <typename Node, typename Policy> struct l_iterator; | |
42 | template <typename Node, typename Policy> | |
43 | struct cl_iterator; | |
44 | ||
45 | // Local Iterators | |
46 | // | |
47 | // all no throw | |
48 | ||
49 | template <typename Node, typename Policy> | |
50 | struct l_iterator | |
51 | : public std::iterator< | |
52 | std::forward_iterator_tag, | |
53 | typename Node::value_type, | |
54 | std::ptrdiff_t, | |
55 | typename Node::value_type*, | |
56 | typename Node::value_type&> | |
57 | { | |
58 | #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) | |
59 | template <typename Node2, typename Policy2> | |
60 | friend struct boost::unordered::iterator_detail::cl_iterator; | |
61 | private: | |
62 | #endif | |
63 | typedef typename Node::node_pointer node_pointer; | |
64 | node_pointer ptr_; | |
65 | std::size_t bucket_; | |
66 | std::size_t bucket_count_; | |
67 | ||
68 | public: | |
69 | ||
70 | typedef typename Node::value_type value_type; | |
71 | ||
72 | l_iterator() BOOST_NOEXCEPT : ptr_() {} | |
73 | ||
74 | l_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT | |
75 | : ptr_(n), bucket_(b), bucket_count_(c) {} | |
76 | ||
77 | value_type& operator*() const { | |
78 | return ptr_->value(); | |
79 | } | |
80 | ||
81 | value_type* operator->() const { | |
82 | return ptr_->value_ptr(); | |
83 | } | |
84 | ||
85 | l_iterator& operator++() { | |
86 | ptr_ = static_cast<node_pointer>(ptr_->next_); | |
87 | if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_) | |
88 | != bucket_) | |
89 | ptr_ = node_pointer(); | |
90 | return *this; | |
91 | } | |
92 | ||
93 | l_iterator operator++(int) { | |
94 | l_iterator tmp(*this); | |
95 | ++(*this); | |
96 | return tmp; | |
97 | } | |
98 | ||
99 | bool operator==(l_iterator x) const BOOST_NOEXCEPT { | |
100 | return ptr_ == x.ptr_; | |
101 | } | |
102 | ||
103 | bool operator!=(l_iterator x) const BOOST_NOEXCEPT { | |
104 | return ptr_ != x.ptr_; | |
105 | } | |
106 | }; | |
107 | ||
108 | template <typename Node, typename Policy> | |
109 | struct cl_iterator | |
110 | : public std::iterator< | |
111 | std::forward_iterator_tag, | |
112 | typename Node::value_type, | |
113 | std::ptrdiff_t, | |
114 | typename Node::value_type const*, | |
115 | typename Node::value_type const&> | |
116 | { | |
117 | friend struct boost::unordered::iterator_detail::l_iterator | |
118 | <Node, Policy>; | |
119 | private: | |
120 | ||
121 | typedef typename Node::node_pointer node_pointer; | |
122 | node_pointer ptr_; | |
123 | std::size_t bucket_; | |
124 | std::size_t bucket_count_; | |
125 | ||
126 | public: | |
127 | ||
128 | typedef typename Node::value_type value_type; | |
129 | ||
130 | cl_iterator() BOOST_NOEXCEPT : ptr_() {} | |
131 | ||
132 | cl_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT : | |
133 | ptr_(n), bucket_(b), bucket_count_(c) {} | |
134 | ||
135 | cl_iterator(boost::unordered::iterator_detail::l_iterator< | |
136 | Node, Policy> const& x) BOOST_NOEXCEPT : | |
137 | ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_) | |
138 | {} | |
139 | ||
140 | value_type const& operator*() const { | |
141 | return ptr_->value(); | |
142 | } | |
143 | ||
144 | value_type const* operator->() const { | |
145 | return ptr_->value_ptr(); | |
146 | } | |
147 | ||
148 | cl_iterator& operator++() { | |
149 | ptr_ = static_cast<node_pointer>(ptr_->next_); | |
150 | if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_) | |
151 | != bucket_) | |
152 | ptr_ = node_pointer(); | |
153 | return *this; | |
154 | } | |
155 | ||
156 | cl_iterator operator++(int) { | |
157 | cl_iterator tmp(*this); | |
158 | ++(*this); | |
159 | return tmp; | |
160 | } | |
161 | ||
162 | friend bool operator==(cl_iterator const& x, cl_iterator const& y) | |
163 | BOOST_NOEXCEPT | |
164 | { | |
165 | return x.ptr_ == y.ptr_; | |
166 | } | |
167 | ||
168 | friend bool operator!=(cl_iterator const& x, cl_iterator const& y) | |
169 | BOOST_NOEXCEPT | |
170 | { | |
171 | return x.ptr_ != y.ptr_; | |
172 | } | |
173 | }; | |
174 | ||
175 | template <typename Node> | |
176 | struct iterator | |
177 | : public std::iterator< | |
178 | std::forward_iterator_tag, | |
179 | typename Node::value_type, | |
180 | std::ptrdiff_t, | |
181 | typename Node::value_type*, | |
182 | typename Node::value_type&> | |
183 | { | |
184 | #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) | |
185 | template <typename> | |
186 | friend struct boost::unordered::iterator_detail::c_iterator; | |
187 | template <typename> | |
188 | friend struct boost::unordered::detail::table; | |
189 | template <typename> | |
190 | friend struct boost::unordered::detail::table_impl; | |
191 | template <typename> | |
192 | friend struct boost::unordered::detail::grouped_table_impl; | |
193 | private: | |
194 | #endif | |
195 | typedef typename Node::node_pointer node_pointer; | |
196 | node_pointer node_; | |
197 | ||
198 | public: | |
199 | ||
200 | typedef typename Node::value_type value_type; | |
201 | ||
202 | iterator() BOOST_NOEXCEPT : node_() {} | |
203 | ||
204 | explicit iterator(typename Node::link_pointer x) BOOST_NOEXCEPT : | |
205 | node_(static_cast<node_pointer>(x)) {} | |
206 | ||
207 | value_type& operator*() const { | |
208 | return node_->value(); | |
209 | } | |
210 | ||
211 | value_type* operator->() const { | |
212 | return node_->value_ptr(); | |
213 | } | |
214 | ||
215 | iterator& operator++() { | |
216 | node_ = static_cast<node_pointer>(node_->next_); | |
217 | return *this; | |
218 | } | |
219 | ||
220 | iterator operator++(int) { | |
221 | iterator tmp(node_); | |
222 | node_ = static_cast<node_pointer>(node_->next_); | |
223 | return tmp; | |
224 | } | |
225 | ||
226 | bool operator==(iterator const& x) const BOOST_NOEXCEPT { | |
227 | return node_ == x.node_; | |
228 | } | |
229 | ||
230 | bool operator!=(iterator const& x) const BOOST_NOEXCEPT { | |
231 | return node_ != x.node_; | |
232 | } | |
233 | }; | |
234 | ||
235 | template <typename Node> | |
236 | struct c_iterator | |
237 | : public std::iterator< | |
238 | std::forward_iterator_tag, | |
239 | typename Node::value_type, | |
240 | std::ptrdiff_t, | |
241 | typename Node::value_type const*, | |
242 | typename Node::value_type const&> | |
243 | { | |
244 | friend struct boost::unordered::iterator_detail::iterator<Node>; | |
245 | ||
246 | #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) | |
247 | template <typename> | |
248 | friend struct boost::unordered::detail::table; | |
249 | template <typename> | |
250 | friend struct boost::unordered::detail::table_impl; | |
251 | template <typename> | |
252 | friend struct boost::unordered::detail::grouped_table_impl; | |
253 | ||
254 | private: | |
255 | #endif | |
256 | typedef typename Node::node_pointer node_pointer; | |
257 | typedef boost::unordered::iterator_detail::iterator<Node> n_iterator; | |
258 | node_pointer node_; | |
259 | ||
260 | public: | |
261 | ||
262 | typedef typename Node::value_type value_type; | |
263 | ||
264 | c_iterator() BOOST_NOEXCEPT : node_() {} | |
265 | ||
266 | explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT : | |
267 | node_(static_cast<node_pointer>(x)) {} | |
268 | ||
269 | c_iterator(n_iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {} | |
270 | ||
271 | value_type const& operator*() const { | |
272 | return node_->value(); | |
273 | } | |
274 | ||
275 | value_type const* operator->() const { | |
276 | return node_->value_ptr(); | |
277 | } | |
278 | ||
279 | c_iterator& operator++() { | |
280 | node_ = static_cast<node_pointer>(node_->next_); | |
281 | return *this; | |
282 | } | |
283 | ||
284 | c_iterator operator++(int) { | |
285 | c_iterator tmp(node_); | |
286 | node_ = static_cast<node_pointer>(node_->next_); | |
287 | return tmp; | |
288 | } | |
289 | ||
290 | friend bool operator==(c_iterator const& x, c_iterator const& y) | |
291 | BOOST_NOEXCEPT | |
292 | { | |
293 | return x.node_ == y.node_; | |
294 | } | |
295 | ||
296 | friend bool operator!=(c_iterator const& x, c_iterator const& y) | |
297 | BOOST_NOEXCEPT | |
298 | { | |
299 | return x.node_ != y.node_; | |
300 | } | |
301 | }; | |
302 | }}} | |
303 | ||
304 | namespace boost { namespace unordered { namespace detail { | |
305 | ||
306 | /////////////////////////////////////////////////////////////////// | |
307 | // | |
308 | // Node Holder | |
309 | // | |
310 | // Temporary store for nodes. Deletes any that aren't used. | |
311 | ||
312 | template <typename NodeAlloc> | |
313 | struct node_holder | |
314 | { | |
315 | private: | |
316 | typedef NodeAlloc node_allocator; | |
317 | typedef boost::unordered::detail::allocator_traits<NodeAlloc> | |
318 | node_allocator_traits; | |
319 | typedef typename node_allocator_traits::value_type node; | |
320 | typedef typename node_allocator_traits::pointer node_pointer; | |
321 | typedef typename node::value_type value_type; | |
322 | typedef typename node::link_pointer link_pointer; | |
323 | typedef boost::unordered::iterator_detail::iterator<node> iterator; | |
324 | ||
325 | node_constructor<NodeAlloc> constructor_; | |
326 | node_pointer nodes_; | |
327 | ||
328 | public: | |
329 | ||
330 | template <typename Table> | |
331 | explicit node_holder(Table& b) : | |
332 | constructor_(b.node_alloc()), | |
333 | nodes_() | |
334 | { | |
335 | if (b.size_) { | |
336 | typename Table::link_pointer prev = b.get_previous_start(); | |
337 | nodes_ = static_cast<node_pointer>(prev->next_); | |
338 | prev->next_ = link_pointer(); | |
339 | b.size_ = 0; | |
340 | } | |
341 | } | |
342 | ||
343 | ~node_holder(); | |
344 | ||
345 | node_pointer pop_node() | |
346 | { | |
347 | node_pointer n = nodes_; | |
348 | nodes_ = static_cast<node_pointer>(nodes_->next_); | |
349 | n->init(n); | |
350 | n->next_ = link_pointer(); | |
351 | return n; | |
352 | } | |
353 | ||
354 | template <typename T> | |
355 | inline node_pointer copy_of(T const& v) { | |
356 | if (nodes_) { | |
357 | constructor_.reclaim(pop_node()); | |
358 | } | |
359 | else { | |
360 | constructor_.create_node(); | |
361 | } | |
362 | boost::unordered::detail::func::call_construct( | |
363 | constructor_.alloc_, constructor_.node_->value_ptr(), v); | |
364 | return constructor_.release(); | |
365 | } | |
366 | ||
367 | template <typename T> | |
368 | inline node_pointer move_copy_of(T& v) { | |
369 | if (nodes_) { | |
370 | constructor_.reclaim(pop_node()); | |
371 | } | |
372 | else { | |
373 | constructor_.create_node(); | |
374 | } | |
375 | boost::unordered::detail::func::call_construct( | |
376 | constructor_.alloc_, constructor_.node_->value_ptr(), | |
377 | boost::move(v)); | |
378 | return constructor_.release(); | |
379 | } | |
380 | ||
381 | iterator begin() const | |
382 | { | |
383 | return iterator(nodes_); | |
384 | } | |
385 | }; | |
386 | ||
387 | template <typename Alloc> | |
388 | node_holder<Alloc>::~node_holder() | |
389 | { | |
390 | while (nodes_) { | |
391 | node_pointer p = nodes_; | |
392 | nodes_ = static_cast<node_pointer>(p->next_); | |
393 | ||
394 | boost::unordered::detail::func::call_destroy(constructor_.alloc_, | |
395 | p->value_ptr()); | |
396 | boost::unordered::detail::func::destroy(boost::addressof(*p)); | |
397 | node_allocator_traits::deallocate(constructor_.alloc_, p, 1); | |
398 | } | |
399 | } | |
400 | ||
401 | /////////////////////////////////////////////////////////////////// | |
402 | // | |
403 | // Bucket | |
404 | ||
405 | template <typename NodePointer> | |
406 | struct bucket | |
407 | { | |
408 | typedef NodePointer link_pointer; | |
409 | link_pointer next_; | |
410 | ||
411 | bucket() : next_() {} | |
412 | ||
413 | link_pointer first_from_start() | |
414 | { | |
415 | return next_; | |
416 | } | |
417 | ||
418 | enum { extra_node = true }; | |
419 | }; | |
420 | ||
421 | struct ptr_bucket | |
422 | { | |
423 | typedef ptr_bucket* link_pointer; | |
424 | link_pointer next_; | |
425 | ||
426 | ptr_bucket() : next_(0) {} | |
427 | ||
428 | link_pointer first_from_start() | |
429 | { | |
430 | return this; | |
431 | } | |
432 | ||
433 | enum { extra_node = false }; | |
434 | }; | |
435 | ||
436 | /////////////////////////////////////////////////////////////////// | |
437 | // | |
438 | // Hash Policy | |
439 | ||
440 | template <typename SizeT> | |
441 | struct prime_policy | |
442 | { | |
443 | template <typename Hash, typename T> | |
444 | static inline SizeT apply_hash(Hash const& hf, T const& x) { | |
445 | return hf(x); | |
446 | } | |
447 | ||
448 | static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) { | |
449 | return hash % bucket_count; | |
450 | } | |
451 | ||
452 | static inline SizeT new_bucket_count(SizeT min) { | |
453 | return boost::unordered::detail::next_prime(min); | |
454 | } | |
455 | ||
456 | static inline SizeT prev_bucket_count(SizeT max) { | |
457 | return boost::unordered::detail::prev_prime(max); | |
458 | } | |
459 | }; | |
460 | ||
461 | template <typename SizeT> | |
462 | struct mix64_policy | |
463 | { | |
464 | template <typename Hash, typename T> | |
465 | static inline SizeT apply_hash(Hash const& hf, T const& x) { | |
466 | SizeT key = hf(x); | |
467 | key = (~key) + (key << 21); // key = (key << 21) - key - 1; | |
468 | key = key ^ (key >> 24); | |
469 | key = (key + (key << 3)) + (key << 8); // key * 265 | |
470 | key = key ^ (key >> 14); | |
471 | key = (key + (key << 2)) + (key << 4); // key * 21 | |
472 | key = key ^ (key >> 28); | |
473 | key = key + (key << 31); | |
474 | return key; | |
475 | } | |
476 | ||
477 | static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) { | |
478 | return hash & (bucket_count - 1); | |
479 | } | |
480 | ||
481 | static inline SizeT new_bucket_count(SizeT min) { | |
482 | if (min <= 4) return 4; | |
483 | --min; | |
484 | min |= min >> 1; | |
485 | min |= min >> 2; | |
486 | min |= min >> 4; | |
487 | min |= min >> 8; | |
488 | min |= min >> 16; | |
489 | min |= min >> 32; | |
490 | return min + 1; | |
491 | } | |
492 | ||
493 | static inline SizeT prev_bucket_count(SizeT max) { | |
494 | max |= max >> 1; | |
495 | max |= max >> 2; | |
496 | max |= max >> 4; | |
497 | max |= max >> 8; | |
498 | max |= max >> 16; | |
499 | max |= max >> 32; | |
500 | return (max >> 1) + 1; | |
501 | } | |
502 | }; | |
503 | ||
504 | template <int digits, int radix> | |
505 | struct pick_policy_impl { | |
506 | typedef prime_policy<std::size_t> type; | |
507 | }; | |
508 | ||
509 | template <> | |
510 | struct pick_policy_impl<64, 2> { | |
511 | typedef mix64_policy<std::size_t> type; | |
512 | }; | |
513 | ||
514 | template <typename T> | |
515 | struct pick_policy : | |
516 | pick_policy_impl< | |
517 | std::numeric_limits<std::size_t>::digits, | |
518 | std::numeric_limits<std::size_t>::radix> {}; | |
519 | ||
520 | // While the mix policy is generally faster, the prime policy is a lot | |
521 | // faster when a large number consecutive integers are used, because | |
522 | // there are no collisions. Since that is probably quite common, use | |
523 | // prime policy for integeral types. But not the smaller ones, as they | |
524 | // don't have enough unique values for this to be an issue. | |
525 | ||
526 | template <> | |
527 | struct pick_policy<int> { | |
528 | typedef prime_policy<std::size_t> type; | |
529 | }; | |
530 | ||
531 | template <> | |
532 | struct pick_policy<unsigned int> { | |
533 | typedef prime_policy<std::size_t> type; | |
534 | }; | |
535 | ||
536 | template <> | |
537 | struct pick_policy<long> { | |
538 | typedef prime_policy<std::size_t> type; | |
539 | }; | |
540 | ||
541 | template <> | |
542 | struct pick_policy<unsigned long> { | |
543 | typedef prime_policy<std::size_t> type; | |
544 | }; | |
545 | ||
546 | // TODO: Maybe not if std::size_t is smaller than long long. | |
547 | #if !defined(BOOST_NO_LONG_LONG) | |
548 | template <> | |
549 | struct pick_policy<boost::long_long_type> { | |
550 | typedef prime_policy<std::size_t> type; | |
551 | }; | |
552 | ||
553 | template <> | |
554 | struct pick_policy<boost::ulong_long_type> { | |
555 | typedef prime_policy<std::size_t> type; | |
556 | }; | |
557 | #endif | |
558 | ||
559 | //////////////////////////////////////////////////////////////////////////// | |
560 | // Functions | |
561 | ||
562 | // Assigning and swapping the equality and hash function objects | |
563 | // needs strong exception safety. To implement that normally we'd | |
564 | // require one of them to be known to not throw and the other to | |
565 | // guarantee strong exception safety. Unfortunately they both only | |
566 | // have basic exception safety. So to acheive strong exception | |
567 | // safety we have storage space for two copies, and assign the new | |
568 | // copies to the unused space. Then switch to using that to use | |
569 | // them. This is implemented in 'set_hash_functions' which | |
570 | // atomically assigns the new function objects in a strongly | |
571 | // exception safe manner. | |
572 | ||
573 | template <class H, class P, bool NoThrowMoveAssign> | |
574 | class set_hash_functions; | |
575 | ||
576 | template <class H, class P> | |
577 | class functions | |
578 | { | |
579 | public: | |
580 | static const bool nothrow_move_assignable = | |
581 | boost::is_nothrow_move_assignable<H>::value && | |
582 | boost::is_nothrow_move_assignable<P>::value; | |
583 | static const bool nothrow_move_constructible = | |
584 | boost::is_nothrow_move_constructible<H>::value && | |
585 | boost::is_nothrow_move_constructible<P>::value; | |
586 | ||
587 | private: | |
588 | friend class boost::unordered::detail::set_hash_functions<H, P, | |
589 | nothrow_move_assignable>; | |
590 | functions& operator=(functions const&); | |
591 | ||
592 | typedef compressed<H, P> function_pair; | |
593 | ||
594 | typedef typename boost::aligned_storage< | |
595 | sizeof(function_pair), | |
596 | boost::alignment_of<function_pair>::value>::type aligned_function; | |
597 | ||
598 | bool current_; // The currently active functions. | |
599 | aligned_function funcs_[2]; | |
600 | ||
601 | function_pair const& current() const { | |
602 | return *static_cast<function_pair const*>( | |
603 | static_cast<void const*>(&funcs_[current_])); | |
604 | } | |
605 | ||
606 | function_pair& current() { | |
607 | return *static_cast<function_pair*>( | |
608 | static_cast<void*>(&funcs_[current_])); | |
609 | } | |
610 | ||
611 | void construct(bool which, H const& hf, P const& eq) | |
612 | { | |
613 | new((void*) &funcs_[which]) function_pair(hf, eq); | |
614 | } | |
615 | ||
616 | void construct(bool which, function_pair const& f, | |
617 | boost::unordered::detail::false_type = | |
618 | boost::unordered::detail::false_type()) | |
619 | { | |
620 | new((void*) &funcs_[which]) function_pair(f); | |
621 | } | |
622 | ||
623 | void construct(bool which, function_pair& f, | |
624 | boost::unordered::detail::true_type) | |
625 | { | |
626 | new((void*) &funcs_[which]) function_pair(f, | |
627 | boost::unordered::detail::move_tag()); | |
628 | } | |
629 | ||
630 | void destroy(bool which) | |
631 | { | |
632 | boost::unordered::detail::func::destroy((function_pair*)(&funcs_[which])); | |
633 | } | |
634 | ||
635 | public: | |
636 | ||
637 | typedef boost::unordered::detail::set_hash_functions<H, P, | |
638 | nothrow_move_assignable> set_hash_functions; | |
639 | ||
640 | functions(H const& hf, P const& eq) | |
641 | : current_(false) | |
642 | { | |
643 | construct(current_, hf, eq); | |
644 | } | |
645 | ||
646 | functions(functions const& bf) | |
647 | : current_(false) | |
648 | { | |
649 | construct(current_, bf.current()); | |
650 | } | |
651 | ||
652 | functions(functions& bf, boost::unordered::detail::move_tag) | |
653 | : current_(false) | |
654 | { | |
655 | construct(current_, bf.current(), | |
656 | boost::unordered::detail::integral_constant<bool, | |
657 | nothrow_move_constructible>()); | |
658 | } | |
659 | ||
660 | ~functions() { | |
661 | this->destroy(current_); | |
662 | } | |
663 | ||
664 | H const& hash_function() const { | |
665 | return current().first(); | |
666 | } | |
667 | ||
668 | P const& key_eq() const { | |
669 | return current().second(); | |
670 | } | |
671 | }; | |
672 | ||
673 | template <class H, class P> | |
674 | class set_hash_functions<H, P, false> | |
675 | { | |
676 | set_hash_functions(set_hash_functions const&); | |
677 | set_hash_functions& operator=(set_hash_functions const&); | |
678 | ||
679 | typedef functions<H, P> functions_type; | |
680 | ||
681 | functions_type& functions_; | |
682 | bool tmp_functions_; | |
683 | ||
684 | public: | |
685 | ||
686 | set_hash_functions(functions_type& f, H const& h, P const& p) | |
687 | : functions_(f), | |
688 | tmp_functions_(!f.current_) | |
689 | { | |
690 | f.construct(tmp_functions_, h, p); | |
691 | } | |
692 | ||
693 | set_hash_functions(functions_type& f, functions_type const& other) | |
694 | : functions_(f), | |
695 | tmp_functions_(!f.current_) | |
696 | { | |
697 | f.construct(tmp_functions_, other.current()); | |
698 | } | |
699 | ||
700 | ~set_hash_functions() | |
701 | { | |
702 | functions_.destroy(tmp_functions_); | |
703 | } | |
704 | ||
705 | void commit() | |
706 | { | |
707 | functions_.current_ = tmp_functions_; | |
708 | tmp_functions_ = !tmp_functions_; | |
709 | } | |
710 | }; | |
711 | ||
712 | template <class H, class P> | |
713 | class set_hash_functions<H, P, true> | |
714 | { | |
715 | set_hash_functions(set_hash_functions const&); | |
716 | set_hash_functions& operator=(set_hash_functions const&); | |
717 | ||
718 | typedef functions<H, P> functions_type; | |
719 | ||
720 | functions_type& functions_; | |
721 | H hash_; | |
722 | P pred_; | |
723 | ||
724 | public: | |
725 | ||
726 | set_hash_functions(functions_type& f, H const& h, P const& p) : | |
727 | functions_(f), | |
728 | hash_(h), | |
729 | pred_(p) {} | |
730 | ||
731 | set_hash_functions(functions_type& f, functions_type const& other) : | |
732 | functions_(f), | |
733 | hash_(other.hash_function()), | |
734 | pred_(other.key_eq()) {} | |
735 | ||
736 | void commit() | |
737 | { | |
738 | functions_.current().first() = boost::move(hash_); | |
739 | functions_.current().second() = boost::move(pred_); | |
740 | } | |
741 | }; | |
742 | ||
743 | //////////////////////////////////////////////////////////////////////////// | |
744 | // rvalue parameters when type can't be a BOOST_RV_REF(T) parameter | |
745 | // e.g. for int | |
746 | ||
747 | #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) | |
748 | # define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T) | |
749 | #else | |
750 | struct please_ignore_this_overload { | |
751 | typedef please_ignore_this_overload type; | |
752 | }; | |
753 | ||
754 | template <typename T> | |
755 | struct rv_ref_impl { | |
756 | typedef BOOST_RV_REF(T) type; | |
757 | }; | |
758 | ||
759 | template <typename T> | |
760 | struct rv_ref : | |
761 | boost::detail::if_true< | |
762 | boost::is_class<T>::value | |
763 | >::BOOST_NESTED_TEMPLATE then < | |
764 | boost::unordered::detail::rv_ref_impl<T>, | |
765 | please_ignore_this_overload | |
766 | >::type | |
767 | {}; | |
768 | ||
769 | # define BOOST_UNORDERED_RV_REF(T) \ | |
770 | typename boost::unordered::detail::rv_ref<T>::type | |
771 | #endif | |
772 | }}} | |
773 | ||
774 | #endif |