1// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
2// Copyright (C) 2005-2016 Daniel James
3//
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_IMPLEMENTATION_HPP
8#define BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP
9
10#include <boost/config.hpp>
11#if defined(BOOST_HAS_PRAGMA_ONCE)
12#pragma once
13#endif
14
15#include <boost/assert.hpp>
16#include <boost/core/no_exceptions_support.hpp>
17#include <boost/core/pointer_traits.hpp>
18#include <boost/detail/select_type.hpp>
19#include <boost/limits.hpp>
20#include <boost/move/move.hpp>
21#include <boost/preprocessor/arithmetic/inc.hpp>
22#include <boost/preprocessor/cat.hpp>
23#include <boost/preprocessor/repetition/enum.hpp>
24#include <boost/preprocessor/repetition/enum_binary_params.hpp>
25#include <boost/preprocessor/repetition/enum_params.hpp>
26#include <boost/preprocessor/repetition/repeat_from_to.hpp>
27#include <boost/preprocessor/seq/enum.hpp>
28#include <boost/preprocessor/seq/size.hpp>
29#include <boost/swap.hpp>
30#include <boost/throw_exception.hpp>
31#include <boost/tuple/tuple.hpp>
32#include <boost/type_traits/add_lvalue_reference.hpp>
33#include <boost/type_traits/aligned_storage.hpp>
34#include <boost/type_traits/alignment_of.hpp>
35#include <boost/type_traits/integral_constant.hpp>
36#include <boost/type_traits/is_base_of.hpp>
37#include <boost/type_traits/is_class.hpp>
38#include <boost/type_traits/is_empty.hpp>
39#include <boost/type_traits/is_nothrow_move_assignable.hpp>
40#include <boost/type_traits/is_nothrow_move_constructible.hpp>
41#include <boost/type_traits/is_nothrow_swappable.hpp>
42#include <boost/type_traits/is_same.hpp>
43#include <boost/type_traits/remove_const.hpp>
44#include <boost/unordered/detail/fwd.hpp>
45#include <boost/utility/addressof.hpp>
46#include <boost/utility/enable_if.hpp>
47#include <cmath>
48#include <iterator>
49#include <stdexcept>
50#include <utility>
51
52#if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
53#include <type_traits>
54#endif
55
56////////////////////////////////////////////////////////////////////////////////
57// Configuration
58//
59// Unless documented elsewhere these configuration macros should be considered
60// an implementation detail, I'll try not to break them, but you never know.
61
62// Use Sun C++ workarounds
63// I'm not sure which versions of the compiler require these workarounds, so
64// I'm just using them of everything older than the current test compilers
65// (as of May 2017).
66
67#if !defined(BOOST_UNORDERED_SUN_WORKAROUNDS1)
68#if BOOST_COMP_SUNPRO && BOOST_COMP_SUNPRO < BOOST_VERSION_NUMBER(5, 20, 0)
69#define BOOST_UNORDERED_SUN_WORKAROUNDS1 1
70#else
71#define BOOST_UNORDERED_SUN_WORKAROUNDS1 0
72#endif
73#endif
74
75// BOOST_UNORDERED_EMPLACE_LIMIT = The maximum number of parameters in
76// emplace (not including things like hints). Don't set it to a lower value, as
77// that might break something.
78
79#if !defined BOOST_UNORDERED_EMPLACE_LIMIT
80#define BOOST_UNORDERED_EMPLACE_LIMIT 10
81#endif
82
83// BOOST_UNORDERED_USE_ALLOCATOR_TRAITS - Pick which version of
84// allocator_traits to use.
85//
86// 0 = Own partial implementation
87// 1 = std::allocator_traits
88// 2 = boost::container::allocator_traits
89
90#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
91#if !defined(BOOST_NO_CXX11_ALLOCATOR)
92#define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 1
93#elif defined(BOOST_MSVC)
94#if BOOST_MSVC < 1400
95// Use container's allocator_traits for older versions of Visual
96// C++ as I don't test with them.
97#define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 2
98#endif
99#endif
100#endif
101
102#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
103#define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0
104#endif
105
106// BOOST_UNORDERED_TUPLE_ARGS
107//
108// Maximum number of std::tuple members to support, or 0 if std::tuple
109// isn't avaiable. More are supported when full C++11 is used.
110
111// Already defined, so do nothing
112#if defined(BOOST_UNORDERED_TUPLE_ARGS)
113
114// Assume if we have C++11 tuple it's properly variadic,
115// and just use a max number of 10 arguments.
116#elif !defined(BOOST_NO_CXX11_HDR_TUPLE)
117#define BOOST_UNORDERED_TUPLE_ARGS 10
118
119// Visual C++ has a decent enough tuple for piecewise construction,
120// so use that if available, using _VARIADIC_MAX for the maximum
121// number of parameters. Note that this comes after the check
122// for a full C++11 tuple.
123#elif defined(BOOST_MSVC)
124#if !BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT
125#define BOOST_UNORDERED_TUPLE_ARGS 0
126#elif defined(_VARIADIC_MAX)
127#define BOOST_UNORDERED_TUPLE_ARGS _VARIADIC_MAX
128#else
129#define BOOST_UNORDERED_TUPLE_ARGS 5
130#endif
131
132// Assume that we don't have std::tuple
133#else
134#define BOOST_UNORDERED_TUPLE_ARGS 0
135#endif
136
137#if BOOST_UNORDERED_TUPLE_ARGS
138#include <tuple>
139#endif
140
141// BOOST_UNORDERED_CXX11_CONSTRUCTION
142//
143// Use C++11 construction, requires variadic arguments, good construct support
144// in allocator_traits and piecewise construction of std::pair
145// Otherwise allocators aren't used for construction/destruction
146
147#if BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT && \
148 !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && BOOST_UNORDERED_TUPLE_ARGS
149#if BOOST_COMP_SUNPRO && BOOST_LIB_STD_GNU
150// Sun C++ std::pair piecewise construction doesn't seem to be exception safe.
151// (At least for Sun C++ 12.5 using libstdc++).
152#define BOOST_UNORDERED_CXX11_CONSTRUCTION 0
153#elif BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 7, 0)
154// Piecewise construction in GCC 4.6 doesn't work for uncopyable types.
155#define BOOST_UNORDERED_CXX11_CONSTRUCTION 0
156#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0 && \
157 !defined(BOOST_NO_SFINAE_EXPR)
158#define BOOST_UNORDERED_CXX11_CONSTRUCTION 1
159#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1
160#define BOOST_UNORDERED_CXX11_CONSTRUCTION 1
161#endif
162#endif
163
164#if !defined(BOOST_UNORDERED_CXX11_CONSTRUCTION)
165#define BOOST_UNORDERED_CXX11_CONSTRUCTION 0
166#endif
167
168// BOOST_UNORDERED_SUPPRESS_DEPRECATED
169//
170// Define to stop deprecation attributes
171
172#if defined(BOOST_UNORDERED_SUPPRESS_DEPRECATED)
173#define BOOST_UNORDERED_DEPRECATED(msg)
174#endif
175
176// BOOST_UNORDERED_DEPRECATED
177//
178// Wrapper around various depreaction attributes.
179
180#if defined(__has_cpp_attribute) && \
181 (!defined(__cplusplus) || __cplusplus >= 201402)
182#if __has_cpp_attribute(deprecated) && !defined(BOOST_UNORDERED_DEPRECATED)
183#define BOOST_UNORDERED_DEPRECATED(msg) [[deprecated(msg)]]
184#endif
185#endif
186
187#if !defined(BOOST_UNORDERED_DEPRECATED)
188#if defined(__GNUC__) && __GNUC__ >= 4
189#define BOOST_UNORDERED_DEPRECATED(msg) __attribute__((deprecated))
190#elif defined(_MSC_VER) && _MSC_VER >= 1400
191#define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated(msg))
192#elif defined(_MSC_VER) && _MSC_VER >= 1310
193#define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated)
194#else
195#define BOOST_UNORDERED_DEPRECATED(msg)
196#endif
197#endif
198
199// BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
200
201#if !defined(BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES)
202#if BOOST_COMP_CLANG && __cplusplus >= 201703
203#define BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 1
204#endif
205#endif
206
207#if !defined(BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES)
208#define BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 0
209#endif
210
211namespace boost {
212 namespace unordered {
213 namespace iterator_detail {
214 template <typename Node> struct iterator;
215 template <typename Node> struct c_iterator;
216 template <typename Node> struct l_iterator;
217 template <typename Node> struct cl_iterator;
218 }
219 }
220}
221
222namespace boost {
223 namespace unordered {
224 namespace detail {
225
226 template <typename Types> struct table;
227 template <typename NodePointer> struct bucket;
228 struct ptr_bucket;
229
230 template <typename A, typename T> struct node;
231 template <typename T> struct ptr_node;
232
233 static const float minimum_max_load_factor = 1e-3f;
234 static const std::size_t default_bucket_count = 11;
235
236 struct move_tag
237 {
238 };
239
240 struct empty_emplace
241 {
242 };
243
244 struct no_key
245 {
246 no_key() {}
247 template <class T> no_key(T const&) {}
248 };
249
250 namespace func {
251 template <class T> inline void ignore_unused_variable_warning(T const&)
252 {
253 }
254 }
255
256 //////////////////////////////////////////////////////////////////////////
257 // iterator SFINAE
258
259 template <typename I>
260 struct is_forward : boost::is_base_of<std::forward_iterator_tag,
261 typename std::iterator_traits<I>::iterator_category>
262 {
263 };
264
265 template <typename I, typename ReturnType>
266 struct enable_if_forward
267 : boost::enable_if_c<boost::unordered::detail::is_forward<I>::value,
268 ReturnType>
269 {
270 };
271
272 template <typename I, typename ReturnType>
273 struct disable_if_forward
274 : boost::disable_if_c<boost::unordered::detail::is_forward<I>::value,
275 ReturnType>
276 {
277 };
278 }
279 }
280}
281
282////////////////////////////////////////////////////////////////////////////////
283// primes
284
285// clang-format off
286#define BOOST_UNORDERED_PRIMES \
287 (17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \
288 (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \
289 (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \
290 (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \
291 (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \
292 (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \
293 (1610612741ul)(3221225473ul)(4294967291ul)
294// clang-format on
295
296namespace boost {
297 namespace unordered {
298 namespace detail {
299 template <class T> struct prime_list_template
300 {
301 static std::size_t const value[];
302
303#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
304 static std::ptrdiff_t const length;
305#else
306 static std::ptrdiff_t const length =
307 BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
308#endif
309 };
310
311 template <class T>
312 std::size_t const prime_list_template<T>::value[] = {
313 BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)};
314
315#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
316 template <class T>
317 std::ptrdiff_t const prime_list_template<T>::length = BOOST_PP_SEQ_SIZE(
318 BOOST_UNORDERED_PRIMES);
319#endif
320
321#undef BOOST_UNORDERED_PRIMES
322
323 typedef prime_list_template<std::size_t> prime_list;
324
325 // no throw
326 inline std::size_t next_prime(std::size_t num)
327 {
328 std::size_t const* const prime_list_begin = prime_list::value;
329 std::size_t const* const prime_list_end =
330 prime_list_begin + prime_list::length;
331 std::size_t const* bound =
332 std::lower_bound(first: prime_list_begin, last: prime_list_end, val: num);
333 if (bound == prime_list_end)
334 bound--;
335 return *bound;
336 }
337
338 // no throw
339 inline std::size_t prev_prime(std::size_t num)
340 {
341 std::size_t const* const prime_list_begin = prime_list::value;
342 std::size_t const* const prime_list_end =
343 prime_list_begin + prime_list::length;
344 std::size_t const* bound =
345 std::upper_bound(first: prime_list_begin, last: prime_list_end, val: num);
346 if (bound != prime_list_begin)
347 bound--;
348 return *bound;
349 }
350
351 //////////////////////////////////////////////////////////////////////////
352 // insert_size/initial_size
353
354 template <class I>
355 inline std::size_t insert_size(I i, I j,
356 typename boost::unordered::detail::enable_if_forward<I, void*>::type =
357 0)
358 {
359 return static_cast<std::size_t>(std::distance(i, j));
360 }
361
362 template <class I>
363 inline std::size_t insert_size(I, I,
364 typename boost::unordered::detail::disable_if_forward<I, void*>::type =
365 0)
366 {
367 return 1;
368 }
369
370 template <class I>
371 inline std::size_t initial_size(I i, I j,
372 std::size_t num_buckets =
373 boost::unordered::detail::default_bucket_count)
374 {
375 return (std::max)(
376 boost::unordered::detail::insert_size(i, j), num_buckets);
377 }
378
379 //////////////////////////////////////////////////////////////////////////
380 // compressed
381
382 template <typename T, int Index> struct compressed_base : private T
383 {
384 compressed_base(T const& x) : T(x) {}
385 compressed_base(T& x, move_tag) : T(boost::move(x)) {}
386
387 T& get() { return *this; }
388 T const& get() const { return *this; }
389 };
390
391 template <typename T, int Index> struct uncompressed_base
392 {
393 uncompressed_base(T const& x) : value_(x) {}
394 uncompressed_base(T& x, move_tag) : value_(boost::move(x)) {}
395
396 T& get() { return value_; }
397 T const& get() const { return value_; }
398
399 private:
400 T value_;
401 };
402
403 template <typename T, int Index>
404 struct generate_base
405 : boost::detail::if_true<
406 boost::is_empty<T>::value>::BOOST_NESTED_TEMPLATE
407 then<boost::unordered::detail::compressed_base<T, Index>,
408 boost::unordered::detail::uncompressed_base<T, Index> >
409 {
410 };
411
412 template <typename T1, typename T2>
413 struct compressed
414 : private boost::unordered::detail::generate_base<T1, 1>::type,
415 private boost::unordered::detail::generate_base<T2, 2>::type
416 {
417 typedef typename generate_base<T1, 1>::type base1;
418 typedef typename generate_base<T2, 2>::type base2;
419
420 typedef T1 first_type;
421 typedef T2 second_type;
422
423 first_type& first() { return static_cast<base1*>(this)->get(); }
424
425 first_type const& first() const
426 {
427 return static_cast<base1 const*>(this)->get();
428 }
429
430 second_type& second() { return static_cast<base2*>(this)->get(); }
431
432 second_type const& second() const
433 {
434 return static_cast<base2 const*>(this)->get();
435 }
436
437 template <typename First, typename Second>
438 compressed(First const& x1, Second const& x2) : base1(x1), base2(x2)
439 {
440 }
441
442 compressed(compressed const& x) : base1(x.first()), base2(x.second()) {}
443
444 compressed(compressed& x, move_tag m)
445 : base1(x.first(), m), base2(x.second(), m)
446 {
447 }
448
449 void assign(compressed const& x)
450 {
451 first() = x.first();
452 second() = x.second();
453 }
454
455 void move_assign(compressed& x)
456 {
457 first() = boost::move(x.first());
458 second() = boost::move(x.second());
459 }
460
461 void swap(compressed& x)
462 {
463 boost::swap(first(), x.first());
464 boost::swap(second(), x.second());
465 }
466
467 private:
468 // Prevent assignment just to make use of assign or
469 // move_assign explicit.
470 compressed& operator=(compressed const&);
471 };
472
473 //////////////////////////////////////////////////////////////////////////
474 // pair_traits
475 //
476 // Used to get the types from a pair without instantiating it.
477
478 template <typename Pair> struct pair_traits
479 {
480 typedef typename Pair::first_type first_type;
481 typedef typename Pair::second_type second_type;
482 };
483
484 template <typename T1, typename T2> struct pair_traits<std::pair<T1, T2> >
485 {
486 typedef T1 first_type;
487 typedef T2 second_type;
488 };
489
490#if defined(BOOST_MSVC)
491#pragma warning(push)
492#pragma warning(disable : 4512) // assignment operator could not be generated.
493#pragma warning(disable : 4345) // behavior change: an object of POD type
494// constructed with an initializer of the form ()
495// will be default-initialized.
496#endif
497
498 //////////////////////////////////////////////////////////////////////////
499 // Bits and pieces for implementing traits
500
501 template <typename T>
502 typename boost::add_lvalue_reference<T>::type make();
503 struct choice9
504 {
505 typedef char (&type)[9];
506 };
507 struct choice8 : choice9
508 {
509 typedef char (&type)[8];
510 };
511 struct choice7 : choice8
512 {
513 typedef char (&type)[7];
514 };
515 struct choice6 : choice7
516 {
517 typedef char (&type)[6];
518 };
519 struct choice5 : choice6
520 {
521 typedef char (&type)[5];
522 };
523 struct choice4 : choice5
524 {
525 typedef char (&type)[4];
526 };
527 struct choice3 : choice4
528 {
529 typedef char (&type)[3];
530 };
531 struct choice2 : choice3
532 {
533 typedef char (&type)[2];
534 };
535 struct choice1 : choice2
536 {
537 typedef char (&type)[1];
538 };
539 choice1 choose();
540
541 typedef choice1::type yes_type;
542 typedef choice2::type no_type;
543
544 struct private_type
545 {
546 private_type const& operator,(int) const;
547 };
548
549 template <typename T> no_type is_private_type(T const&);
550 yes_type is_private_type(private_type const&);
551
552 struct convert_from_anything
553 {
554 template <typename T> convert_from_anything(T const&);
555 };
556 }
557 }
558}
559
560////////////////////////////////////////////////////////////////////////////
561// emplace_args
562//
563// Either forwarding variadic arguments, or storing the arguments in
564// emplace_args##n
565
566#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
567
568#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args
569#define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args
570#define BOOST_UNORDERED_EMPLACE_FORWARD boost::forward<Args>(args)...
571
572#else
573
574#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args
575#define BOOST_UNORDERED_EMPLACE_ARGS Args const& args
576#define BOOST_UNORDERED_EMPLACE_FORWARD args
577
578#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
579
580#define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
581 typedef BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(Arg, n); \
582 BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
583
584#else
585
586#define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
587 typedef typename boost::add_lvalue_reference<BOOST_PP_CAT(A, n)>::type \
588 BOOST_PP_CAT(Arg, n); \
589 BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
590
591#endif
592
593#define BOOST_UNORDERED_FWD_PARAM(z, n, a) \
594 BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(a, n)
595
596#define BOOST_UNORDERED_CALL_FORWARD(z, i, a) \
597 boost::forward<BOOST_PP_CAT(A, i)>(BOOST_PP_CAT(a, i))
598
599#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \
600 BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n))
601
602#define BOOST_UNORDERED_EARGS(z, n, _) \
603 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
604 struct BOOST_PP_CAT(emplace_args, n) \
605 { \
606 BOOST_PP_REPEAT_##z(n, BOOST_UNORDERED_EARGS_MEMBER, _) BOOST_PP_CAT( \
607 emplace_args, n)(BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, b)) \
608 : BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_EARGS_INIT, _) \
609 { \
610 } \
611 }; \
612 \
613 template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
614 inline BOOST_PP_CAT(emplace_args, n)<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> \
615 create_emplace_args(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, b)) \
616 { \
617 BOOST_PP_CAT(emplace_args, n)<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> e( \
618 BOOST_PP_ENUM_PARAMS_Z(z, n, b)); \
619 return e; \
620 }
621
622namespace boost {
623 namespace unordered {
624 namespace detail {
625 template <typename A0> struct emplace_args1
626 {
627 BOOST_UNORDERED_EARGS_MEMBER(1, 0, _)
628
629 explicit emplace_args1(Arg0 b0) : a0(b0) {}
630 };
631
632 template <typename A0>
633 inline emplace_args1<A0> create_emplace_args(BOOST_FWD_REF(A0) b0)
634 {
635 emplace_args1<A0> e(b0);
636 return e;
637 }
638
639 template <typename A0, typename A1> struct emplace_args2
640 {
641 BOOST_UNORDERED_EARGS_MEMBER(1, 0, _)
642 BOOST_UNORDERED_EARGS_MEMBER(1, 1, _)
643
644 emplace_args2(Arg0 b0, Arg1 b1) : a0(b0), a1(b1) {}
645 };
646
647 template <typename A0, typename A1>
648 inline emplace_args2<A0, A1> create_emplace_args(
649 BOOST_FWD_REF(A0) b0, BOOST_FWD_REF(A1) b1)
650 {
651 emplace_args2<A0, A1> e(b0, b1);
652 return e;
653 }
654
655 template <typename A0, typename A1, typename A2> struct emplace_args3
656 {
657 BOOST_UNORDERED_EARGS_MEMBER(1, 0, _)
658 BOOST_UNORDERED_EARGS_MEMBER(1, 1, _)
659 BOOST_UNORDERED_EARGS_MEMBER(1, 2, _)
660
661 emplace_args3(Arg0 b0, Arg1 b1, Arg2 b2) : a0(b0), a1(b1), a2(b2) {}
662 };
663
664 template <typename A0, typename A1, typename A2>
665 inline emplace_args3<A0, A1, A2> create_emplace_args(
666 BOOST_FWD_REF(A0) b0, BOOST_FWD_REF(A1) b1, BOOST_FWD_REF(A2) b2)
667 {
668 emplace_args3<A0, A1, A2> e(b0, b1, b2);
669 return e;
670 }
671
672 BOOST_UNORDERED_EARGS(1, 4, _)
673 BOOST_UNORDERED_EARGS(1, 5, _)
674 BOOST_UNORDERED_EARGS(1, 6, _)
675 BOOST_UNORDERED_EARGS(1, 7, _)
676 BOOST_UNORDERED_EARGS(1, 8, _)
677 BOOST_UNORDERED_EARGS(1, 9, _)
678 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
679 BOOST_UNORDERED_EARGS, _)
680 }
681 }
682}
683
684#undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS
685#undef BOOST_UNORDERED_EARGS_MEMBER
686#undef BOOST_UNORDERED_EARGS_INIT
687
688#endif
689
690////////////////////////////////////////////////////////////////////////////////
691//
692// Some utilities for implementing allocator_traits, but useful elsewhere so
693// they're always defined.
694
695namespace boost {
696 namespace unordered {
697 namespace detail {
698
699////////////////////////////////////////////////////////////////////////////
700// Integral_constrant, true_type, false_type
701//
702// Uses the standard versions if available.
703
704#if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
705
706 using std::integral_constant;
707 using std::true_type;
708 using std::false_type;
709
710#else
711
712 template <typename T, T Value> struct integral_constant
713 {
714 enum
715 {
716 value = Value
717 };
718 };
719
720 typedef boost::unordered::detail::integral_constant<bool, true> true_type;
721 typedef boost::unordered::detail::integral_constant<bool, false>
722 false_type;
723
724#endif
725
726////////////////////////////////////////////////////////////////////////////
727// Explicitly call a destructor
728
729#if defined(BOOST_MSVC)
730#pragma warning(push)
731#pragma warning(disable : 4100) // unreferenced formal parameter
732#endif
733
734 namespace func {
735 template <class T> inline void destroy(T* x) { x->~T(); }
736 }
737
738#if defined(BOOST_MSVC)
739#pragma warning(pop)
740#endif
741
742 //////////////////////////////////////////////////////////////////////////
743 // value_base
744 //
745 // Space used to store values.
746
747 template <typename ValueType> struct value_base
748 {
749 typedef ValueType value_type;
750
751 typename boost::aligned_storage<sizeof(value_type),
752 boost::alignment_of<value_type>::value>::type data_;
753
754 value_base() : data_() {}
755
756 void* address() { return this; }
757
758 value_type& value() { return *(ValueType*)this; }
759
760 value_type const& value() const { return *(ValueType const*)this; }
761
762 value_type* value_ptr() { return (ValueType*)this; }
763
764 value_type const* value_ptr() const { return (ValueType const*)this; }
765
766 private:
767 value_base& operator=(value_base const&);
768 };
769
770 //////////////////////////////////////////////////////////////////////////
771 // optional
772 // TODO: Use std::optional when available.
773
774 template <typename T> class optional
775 {
776 BOOST_MOVABLE_BUT_NOT_COPYABLE(optional)
777
778 boost::unordered::detail::value_base<T> value_;
779 bool has_value_;
780
781 void destroy()
782 {
783 if (has_value_) {
784 boost::unordered::detail::func::destroy(value_.value_ptr());
785 has_value_ = false;
786 }
787 }
788
789 void move(optional<T>& x)
790 {
791 BOOST_ASSERT(!has_value_ && x.has_value_);
792 new (value_.value_ptr()) T(boost::move(x.value_.value()));
793 boost::unordered::detail::func::destroy(x.value_.value_ptr());
794 has_value_ = true;
795 x.has_value_ = false;
796 }
797
798 public:
799 optional() BOOST_NOEXCEPT : has_value_(false) {}
800
801 optional(BOOST_RV_REF(optional<T>) x) : has_value_(false)
802 {
803 if (x.has_value_) {
804 move(x);
805 }
806 }
807
808 explicit optional(T const& x) : has_value_(true)
809 {
810 new (value_.value_ptr()) T(x);
811 }
812
813 optional& operator=(BOOST_RV_REF(optional<T>) x)
814 {
815 destroy();
816 if (x.has_value_) {
817 move(x);
818 }
819 return *this;
820 }
821
822 ~optional() { destroy(); }
823
824 bool has_value() const { return has_value_; }
825 T& operator*() { return value_.value(); }
826 T const& operator*() const { return value_.value(); }
827 T* operator->() { return value_.value_ptr(); }
828 T const* operator->() const { return value_.value_ptr(); }
829
830 bool operator==(optional<T> const& x)
831 {
832 return has_value_ ? x.has_value_ && value_.value() == x.value_.value()
833 : !x.has_value_;
834 }
835
836 bool operator!=(optional<T> const& x) { return !((*this) == x); }
837
838 void swap(optional<T>& x)
839 {
840 if (has_value_ != x.has_value_) {
841 if (has_value_) {
842 x.move(*this);
843 } else {
844 move(x);
845 }
846 } else if (has_value_) {
847 boost::swap(value_.value(), x.value_.value());
848 }
849 }
850
851 friend void swap(optional<T>& x, optional<T>& y) { x.swap(y); }
852 };
853 }
854 }
855}
856
857////////////////////////////////////////////////////////////////////////////
858// Expression test mechanism
859//
860// When SFINAE expressions are available, define
861// BOOST_UNORDERED_HAS_FUNCTION which can check if a function call is
862// supported by a class, otherwise define BOOST_UNORDERED_HAS_MEMBER which
863// can detect if a class has the specified member, but not that it has the
864// correct type, this is good enough for a passable impression of
865// allocator_traits.
866
867#if !defined(BOOST_NO_SFINAE_EXPR)
868
869namespace boost {
870 namespace unordered {
871 namespace detail {
872 template <typename T, long unsigned int> struct expr_test;
873 template <typename T> struct expr_test<T, sizeof(char)> : T
874 {
875 };
876 }
877 }
878}
879
880#define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \
881 template <typename U> \
882 static \
883 typename boost::unordered::detail::expr_test<BOOST_PP_CAT(choice, result), \
884 sizeof(for_expr_test(((expression), 0)))>::type \
885 test(BOOST_PP_CAT(choice, count))
886
887#define BOOST_UNORDERED_DEFAULT_EXPRESSION(count, result) \
888 template <typename U> \
889 static BOOST_PP_CAT(choice, result)::type test(BOOST_PP_CAT(choice, count))
890
891#define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _) \
892 struct BOOST_PP_CAT(has_, name) \
893 { \
894 template <typename U> static char for_expr_test(U const&); \
895 BOOST_UNORDERED_CHECK_EXPRESSION( \
896 1, 1, boost::unordered::detail::make<thing>().name args); \
897 BOOST_UNORDERED_DEFAULT_EXPRESSION(2, 2); \
898 \
899 enum \
900 { \
901 value = sizeof(test<T>(choose())) == sizeof(choice1::type) \
902 }; \
903 }
904
905#else
906
907namespace boost {
908 namespace unordered {
909 namespace detail {
910 template <typename T> struct identity
911 {
912 typedef T type;
913 };
914 }
915 }
916}
917
918#define BOOST_UNORDERED_CHECK_MEMBER(count, result, name, member) \
919 \
920 typedef \
921 typename boost::unordered::detail::identity<member>::type BOOST_PP_CAT( \
922 check, count); \
923 \
924 template <BOOST_PP_CAT(check, count) e> struct BOOST_PP_CAT(test, count) \
925 { \
926 typedef BOOST_PP_CAT(choice, result) type; \
927 }; \
928 \
929 template <class U> \
930 static typename BOOST_PP_CAT(test, count)<&U::name>::type test( \
931 BOOST_PP_CAT(choice, count))
932
933#define BOOST_UNORDERED_DEFAULT_MEMBER(count, result) \
934 template <class U> \
935 static BOOST_PP_CAT(choice, result)::type test(BOOST_PP_CAT(choice, count))
936
937#define BOOST_UNORDERED_HAS_MEMBER(name) \
938 struct BOOST_PP_CAT(has_, name) \
939 { \
940 struct impl \
941 { \
942 struct base_mixin \
943 { \
944 int name; \
945 }; \
946 struct base : public T, public base_mixin \
947 { \
948 }; \
949 \
950 BOOST_UNORDERED_CHECK_MEMBER(1, 1, name, int base_mixin::*); \
951 BOOST_UNORDERED_DEFAULT_MEMBER(2, 2); \
952 \
953 enum \
954 { \
955 value = sizeof(choice2::type) == sizeof(test<base>(choose())) \
956 }; \
957 }; \
958 \
959 enum \
960 { \
961 value = impl::value \
962 }; \
963 }
964
965#endif
966
967////////////////////////////////////////////////////////////////////////////
968// TRAITS TYPE DETECTION MECHANISM
969//
970// Used to implement traits that use a type if present, or a
971// default otherwise.
972
973#if defined(BOOST_MSVC) && BOOST_MSVC <= 1400
974
975#define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
976 template <typename Tp, typename Default> struct default_type_##tname \
977 { \
978 \
979 template <typename X> \
980 static choice1::type test(choice1, typename X::tname* = 0); \
981 \
982 template <typename X> static choice2::type test(choice2, void* = 0); \
983 \
984 struct DefaultWrap \
985 { \
986 typedef Default tname; \
987 }; \
988 \
989 enum \
990 { \
991 value = (1 == sizeof(test<Tp>(choose()))) \
992 }; \
993 \
994 typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE \
995 then<Tp, DefaultWrap>::type::tname type; \
996 }
997
998#else
999
1000namespace boost {
1001 namespace unordered {
1002 namespace detail {
1003 template <typename T, typename T2> struct sfinae : T2
1004 {
1005 };
1006 }
1007 }
1008}
1009
1010#define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
1011 template <typename Tp, typename Default> struct default_type_##tname \
1012 { \
1013 \
1014 template <typename X> \
1015 static typename boost::unordered::detail::sfinae<typename X::tname, \
1016 choice1>::type test(choice1); \
1017 \
1018 template <typename X> static choice2::type test(choice2); \
1019 \
1020 struct DefaultWrap \
1021 { \
1022 typedef Default tname; \
1023 }; \
1024 \
1025 enum \
1026 { \
1027 value = (1 == sizeof(test<Tp>(choose()))) \
1028 }; \
1029 \
1030 typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE \
1031 then<Tp, DefaultWrap>::type::tname type; \
1032 }
1033
1034#endif
1035
1036#define BOOST_UNORDERED_DEFAULT_TYPE(T, tname, arg) \
1037 typename default_type_##tname<T, arg>::type
1038
1039////////////////////////////////////////////////////////////////////////////////
1040//
1041// Allocator traits
1042//
1043// First our implementation, then later light wrappers around the alternatives
1044
1045#if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0
1046
1047#include <boost/limits.hpp>
1048#include <boost/pointer_to_other.hpp>
1049#include <boost/utility/enable_if.hpp>
1050
1051namespace boost {
1052 namespace unordered {
1053 namespace detail {
1054
1055 template <typename Alloc, typename T> struct rebind_alloc;
1056
1057#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1058
1059 template <template <typename, typename...> class Alloc, typename U,
1060 typename T, typename... Args>
1061 struct rebind_alloc<Alloc<U, Args...>, T>
1062 {
1063 typedef Alloc<T, Args...> type;
1064 };
1065
1066#else
1067
1068 template <template <typename> class Alloc, typename U, typename T>
1069 struct rebind_alloc<Alloc<U>, T>
1070 {
1071 typedef Alloc<T> type;
1072 };
1073
1074 template <template <typename, typename> class Alloc, typename U,
1075 typename T, typename A0>
1076 struct rebind_alloc<Alloc<U, A0>, T>
1077 {
1078 typedef Alloc<T, A0> type;
1079 };
1080
1081 template <template <typename, typename, typename> class Alloc, typename U,
1082 typename T, typename A0, typename A1>
1083 struct rebind_alloc<Alloc<U, A0, A1>, T>
1084 {
1085 typedef Alloc<T, A0, A1> type;
1086 };
1087
1088#endif
1089
1090 template <typename Alloc, typename T> struct rebind_wrap
1091 {
1092 template <typename X>
1093 static choice1::type test(
1094 choice1, typename X::BOOST_NESTED_TEMPLATE rebind<T>::other* = 0);
1095 template <typename X> static choice2::type test(choice2, void* = 0);
1096
1097 enum
1098 {
1099 value = (1 == sizeof(test<Alloc>(choose())))
1100 };
1101
1102 struct fallback
1103 {
1104 template <typename U> struct rebind
1105 {
1106 typedef typename rebind_alloc<Alloc, T>::type other;
1107 };
1108 };
1109
1110 typedef
1111 typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE then<
1112 Alloc, fallback>::type::BOOST_NESTED_TEMPLATE rebind<T>::other type;
1113 };
1114 }
1115 }
1116}
1117
1118namespace boost {
1119 namespace unordered {
1120 namespace detail {
1121 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(pointer);
1122 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_pointer);
1123 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(void_pointer);
1124 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_void_pointer);
1125 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(difference_type);
1126 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(size_type);
1127 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(
1128 propagate_on_container_copy_assignment);
1129 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(
1130 propagate_on_container_move_assignment);
1131 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_swap);
1132 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(is_always_equal);
1133
1134#if !defined(BOOST_NO_SFINAE_EXPR)
1135
1136 template <typename T>
1137 BOOST_UNORDERED_HAS_FUNCTION(
1138 select_on_container_copy_construction, U const, (), 0);
1139
1140 template <typename T>
1141 BOOST_UNORDERED_HAS_FUNCTION(max_size, U const, (), 0);
1142
1143#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1144
1145 template <typename T, typename ValueType, typename... Args>
1146 BOOST_UNORDERED_HAS_FUNCTION(construct, U,
1147 (boost::unordered::detail::make<ValueType*>(),
1148 boost::unordered::detail::make<Args const>()...),
1149 2);
1150
1151#else
1152
1153 template <typename T, typename ValueType>
1154 BOOST_UNORDERED_HAS_FUNCTION(construct, U,
1155 (boost::unordered::detail::make<ValueType*>(),
1156 boost::unordered::detail::make<ValueType const>()),
1157 2);
1158
1159#endif
1160
1161 template <typename T, typename ValueType>
1162 BOOST_UNORDERED_HAS_FUNCTION(
1163 destroy, U, (boost::unordered::detail::make<ValueType*>()), 1);
1164
1165#else
1166
1167 template <typename T>
1168 BOOST_UNORDERED_HAS_MEMBER(select_on_container_copy_construction);
1169
1170 template <typename T> BOOST_UNORDERED_HAS_MEMBER(max_size);
1171
1172 template <typename T, typename ValueType>
1173 BOOST_UNORDERED_HAS_MEMBER(construct);
1174
1175 template <typename T, typename ValueType>
1176 BOOST_UNORDERED_HAS_MEMBER(destroy);
1177
1178#endif
1179 }
1180 }
1181}
1182
1183namespace boost {
1184 namespace unordered {
1185 namespace detail {
1186 namespace func {
1187
1188 template <typename Alloc>
1189 inline Alloc call_select_on_container_copy_construction(
1190 const Alloc& rhs,
1191 typename boost::enable_if_c<
1192 boost::unordered::detail::has_select_on_container_copy_construction<
1193 Alloc>::value,
1194 void*>::type = 0)
1195 {
1196 return rhs.select_on_container_copy_construction();
1197 }
1198
1199 template <typename Alloc>
1200 inline Alloc call_select_on_container_copy_construction(
1201 const Alloc& rhs,
1202 typename boost::disable_if_c<
1203 boost::unordered::detail::has_select_on_container_copy_construction<
1204 Alloc>::value,
1205 void*>::type = 0)
1206 {
1207 return rhs;
1208 }
1209
1210 template <typename SizeType, typename Alloc>
1211 inline SizeType call_max_size(const Alloc& a,
1212 typename boost::enable_if_c<
1213 boost::unordered::detail::has_max_size<Alloc>::value, void*>::type =
1214 0)
1215 {
1216 return a.max_size();
1217 }
1218
1219 template <typename SizeType, typename Alloc>
1220 inline SizeType call_max_size(const Alloc&,
1221 typename boost::disable_if_c<
1222 boost::unordered::detail::has_max_size<Alloc>::value, void*>::type =
1223 0)
1224 {
1225 return (std::numeric_limits<SizeType>::max)();
1226 }
1227 } // namespace func.
1228 }
1229 }
1230}
1231
1232namespace boost {
1233 namespace unordered {
1234 namespace detail {
1235 template <typename Alloc> struct allocator_traits
1236 {
1237 typedef Alloc allocator_type;
1238 typedef typename Alloc::value_type value_type;
1239
1240 typedef BOOST_UNORDERED_DEFAULT_TYPE(
1241 Alloc, pointer, value_type*) pointer;
1242
1243 template <typename T>
1244 struct pointer_to_other : boost::pointer_to_other<pointer, T>
1245 {
1246 };
1247
1248 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_pointer,
1249 typename pointer_to_other<const value_type>::type) const_pointer;
1250
1251 // typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, void_pointer,
1252 // typename pointer_to_other<void>::type)
1253 // void_pointer;
1254 //
1255 // typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_void_pointer,
1256 // typename pointer_to_other<const void>::type)
1257 // const_void_pointer;
1258
1259 typedef BOOST_UNORDERED_DEFAULT_TYPE(
1260 Alloc, difference_type, std::ptrdiff_t) difference_type;
1261
1262 typedef BOOST_UNORDERED_DEFAULT_TYPE(
1263 Alloc, size_type, std::size_t) size_type;
1264
1265#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES)
1266 template <typename T>
1267 using rebind_alloc = typename rebind_wrap<Alloc, T>::type;
1268
1269 template <typename T>
1270 using rebind_traits =
1271 boost::unordered::detail::allocator_traits<rebind_alloc<T> >;
1272#endif
1273
1274 static pointer allocate(Alloc& a, size_type n) { return a.allocate(n); }
1275
1276 // I never use this, so I'll just comment it out for now.
1277 //
1278 // static pointer allocate(Alloc& a, size_type n,
1279 // const_void_pointer hint)
1280 // { return DEFAULT_FUNC(allocate, pointer)(a, n, hint); }
1281
1282 static void deallocate(Alloc& a, pointer p, size_type n)
1283 {
1284 a.deallocate(p, n);
1285 }
1286
1287 public:
1288#if BOOST_UNORDERED_CXX11_CONSTRUCTION
1289
1290 template <typename T, typename... Args>
1291 static
1292 typename boost::enable_if_c<boost::unordered::detail::has_construct<
1293 Alloc, T, Args...>::value>::type
1294 construct(Alloc& a, T* p, BOOST_FWD_REF(Args)... x)
1295 {
1296 a.construct(p, boost::forward<Args>(x)...);
1297 }
1298
1299 template <typename T, typename... Args>
1300 static
1301 typename boost::disable_if_c<boost::unordered::detail::has_construct<
1302 Alloc, T, Args...>::value>::type
1303 construct(Alloc&, T* p, BOOST_FWD_REF(Args)... x)
1304 {
1305 new (static_cast<void*>(p)) T(boost::forward<Args>(x)...);
1306 }
1307
1308 template <typename T>
1309 static typename boost::enable_if_c<
1310 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
1311 destroy(Alloc& a, T* p)
1312 {
1313 a.destroy(p);
1314 }
1315
1316 template <typename T>
1317 static typename boost::disable_if_c<
1318 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
1319 destroy(Alloc&, T* p)
1320 {
1321 boost::unordered::detail::func::destroy(p);
1322 }
1323
1324#elif !defined(BOOST_NO_SFINAE_EXPR)
1325
1326 template <typename T>
1327 static typename boost::enable_if_c<
1328 boost::unordered::detail::has_construct<Alloc, T>::value>::type
1329 construct(Alloc& a, T* p, T const& x)
1330 {
1331 a.construct(p, x);
1332 }
1333
1334 template <typename T>
1335 static typename boost::disable_if_c<
1336 boost::unordered::detail::has_construct<Alloc, T>::value>::type
1337 construct(Alloc&, T* p, T const& x)
1338 {
1339 new (static_cast<void*>(p)) T(x);
1340 }
1341
1342 template <typename T>
1343 static typename boost::enable_if_c<
1344 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
1345 destroy(Alloc& a, T* p)
1346 {
1347 a.destroy(p);
1348 }
1349
1350 template <typename T>
1351 static typename boost::disable_if_c<
1352 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
1353 destroy(Alloc&, T* p)
1354 {
1355 boost::unordered::detail::func::destroy(p);
1356 }
1357
1358#else
1359
1360 // If we don't have SFINAE expressions, only call construct for the
1361 // copy constructor for the allocator's value_type - as that's
1362 // the only construct method that old fashioned allocators support.
1363
1364 template <typename T>
1365 static void construct(Alloc& a, T* p, T const& x,
1366 typename boost::enable_if_c<
1367 boost::unordered::detail::has_construct<Alloc, T>::value &&
1368 boost::is_same<T, value_type>::value,
1369 void*>::type = 0)
1370 {
1371 a.construct(p, x);
1372 }
1373
1374 template <typename T>
1375 static void construct(Alloc&, T* p, T const& x,
1376 typename boost::disable_if_c<
1377 boost::unordered::detail::has_construct<Alloc, T>::value &&
1378 boost::is_same<T, value_type>::value,
1379 void*>::type = 0)
1380 {
1381 new (static_cast<void*>(p)) T(x);
1382 }
1383
1384 template <typename T>
1385 static void destroy(Alloc& a, T* p,
1386 typename boost::enable_if_c<
1387 boost::unordered::detail::has_destroy<Alloc, T>::value &&
1388 boost::is_same<T, value_type>::value,
1389 void*>::type = 0)
1390 {
1391 a.destroy(p);
1392 }
1393
1394 template <typename T>
1395 static void destroy(Alloc&, T* p,
1396 typename boost::disable_if_c<
1397 boost::unordered::detail::has_destroy<Alloc, T>::value &&
1398 boost::is_same<T, value_type>::value,
1399 void*>::type = 0)
1400 {
1401 boost::unordered::detail::func::destroy(p);
1402 }
1403
1404#endif
1405
1406 static size_type max_size(const Alloc& a)
1407 {
1408 return boost::unordered::detail::func::call_max_size<size_type>(a);
1409 }
1410
1411 // Allocator propagation on construction
1412
1413 static Alloc select_on_container_copy_construction(Alloc const& rhs)
1414 {
1415 return boost::unordered::detail::func::
1416 call_select_on_container_copy_construction(rhs);
1417 }
1418
1419 // Allocator propagation on assignment and swap.
1420 // Return true if lhs is modified.
1421 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc,
1422 propagate_on_container_copy_assignment,
1423 false_type) propagate_on_container_copy_assignment;
1424 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc,
1425 propagate_on_container_move_assignment,
1426 false_type) propagate_on_container_move_assignment;
1427 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, propagate_on_container_swap,
1428 false_type) propagate_on_container_swap;
1429
1430 typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, is_always_equal,
1431 typename boost::is_empty<Alloc>::type) is_always_equal;
1432 };
1433 }
1434 }
1435}
1436
1437#undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT
1438#undef BOOST_UNORDERED_DEFAULT_TYPE
1439
1440////////////////////////////////////////////////////////////////////////////////
1441//
1442// std::allocator_traits
1443
1444#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1
1445
1446#include <memory>
1447
1448namespace boost {
1449 namespace unordered {
1450 namespace detail {
1451
1452 BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(is_always_equal);
1453
1454 template <typename Alloc>
1455 struct allocator_traits : std::allocator_traits<Alloc>
1456 {
1457 // As is_always_equal was introduced in C++17, std::allocator_traits
1458 // doesn't always have it. So use it when available, implement it
1459 // ourselves when not. Would be simpler not to bother with
1460 // std::allocator_traits, but I feel like I should try to use
1461 // it where possible.
1462 typedef BOOST_UNORDERED_DEFAULT_TYPE(std::allocator_traits<Alloc>,
1463 is_always_equal,
1464 BOOST_UNORDERED_DEFAULT_TYPE(Alloc, is_always_equal,
1465 typename boost::is_empty<Alloc>::type)) is_always_equal;
1466 };
1467
1468 template <typename Alloc, typename T> struct rebind_wrap
1469 {
1470 typedef typename std::allocator_traits<Alloc>::template rebind_alloc<T>
1471 type;
1472 };
1473 }
1474 }
1475}
1476
1477////////////////////////////////////////////////////////////////////////////////
1478//
1479// boost::container::allocator_traits
1480
1481#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2
1482
1483#include <boost/container/allocator_traits.hpp>
1484
1485namespace boost {
1486 namespace unordered {
1487 namespace detail {
1488
1489 template <typename Alloc>
1490 struct allocator_traits : boost::container::allocator_traits<Alloc>
1491 {
1492 };
1493
1494 template <typename Alloc, typename T>
1495 struct rebind_wrap : boost::container::allocator_traits<
1496 Alloc>::template portable_rebind_alloc<T>
1497 {
1498 };
1499 }
1500 }
1501}
1502
1503#else
1504
1505#error "Invalid BOOST_UNORDERED_USE_ALLOCATOR_TRAITS value."
1506
1507#endif
1508
1509////////////////////////////////////////////////////////////////////////////
1510// Functions used to construct nodes. Emulates variadic construction,
1511// piecewise construction etc.
1512
1513////////////////////////////////////////////////////////////////////////////
1514// construct_value
1515//
1516// Only use allocator_traits::construct, allocator_traits::destroy when full
1517// C++11 support is available.
1518
1519#if BOOST_UNORDERED_CXX11_CONSTRUCTION
1520
1521#define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \
1522 Traits::construct(alloc, address, a0)
1523#define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) Traits::destroy(alloc, x)
1524
1525#elif !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1526
1527namespace boost {
1528 namespace unordered {
1529 namespace detail {
1530 namespace func {
1531 template <typename T, typename... Args>
1532 inline void construct_value(T* address, BOOST_FWD_REF(Args)... args)
1533 {
1534 new ((void*)address) T(boost::forward<Args>(args)...);
1535 }
1536 }
1537 }
1538 }
1539}
1540
1541#define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \
1542 boost::unordered::detail::func::construct_value(address, a0)
1543#define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) \
1544 boost::unordered::detail::func::destroy(x)
1545
1546#else
1547
1548namespace boost {
1549 namespace unordered {
1550 namespace detail {
1551 namespace func {
1552 template <typename T> inline void construct_value(T* address)
1553 {
1554 new ((void*)address) T();
1555 }
1556
1557 template <typename T, typename A0>
1558 inline void construct_value(T* address, BOOST_FWD_REF(A0) a0)
1559 {
1560 new ((void*)address) T(boost::forward<A0>(a0));
1561 }
1562 }
1563 }
1564 }
1565}
1566
1567#define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \
1568 boost::unordered::detail::func::construct_value(address, a0)
1569#define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) \
1570 boost::unordered::detail::func::destroy(x)
1571
1572#endif
1573
1574////////////////////////////////////////////////////////////////////////////
1575// Construct from tuple
1576//
1577// Used to emulate piecewise construction.
1578
1579#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(z, n, namespace_) \
1580 template <typename Alloc, typename T, \
1581 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
1582 void construct_from_tuple(Alloc&, T* ptr, \
1583 namespace_::tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
1584 { \
1585 new ((void*)ptr) \
1586 T(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \
1587 }
1588
1589#define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_::get<n>(x)
1590
1591// construct_from_tuple for boost::tuple
1592// The workaround for old Sun compilers comes later in the file.
1593
1594#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
1595
1596namespace boost {
1597 namespace unordered {
1598 namespace detail {
1599 namespace func {
1600 template <typename Alloc, typename T>
1601 void construct_from_tuple(Alloc&, T* ptr, boost::tuple<>)
1602 {
1603 new ((void*)ptr) T();
1604 }
1605
1606 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, boost)
1607 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, boost)
1608 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, boost)
1609 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, boost)
1610 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, boost)
1611 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 6, boost)
1612 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 7, boost)
1613 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 8, boost)
1614 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 9, boost)
1615 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 10, boost)
1616 }
1617 }
1618 }
1619}
1620
1621#endif
1622
1623// construct_from_tuple for std::tuple
1624
1625#if !BOOST_UNORDERED_CXX11_CONSTRUCTION && BOOST_UNORDERED_TUPLE_ARGS
1626
1627namespace boost {
1628 namespace unordered {
1629 namespace detail {
1630 namespace func {
1631 template <typename Alloc, typename T>
1632 void construct_from_tuple(Alloc&, T* ptr, std::tuple<>)
1633 {
1634 new ((void*)ptr) T();
1635 }
1636
1637 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, std)
1638 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, std)
1639 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, std)
1640 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, std)
1641 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, std)
1642
1643#if BOOST_UNORDERED_TUPLE_ARGS >= 6
1644 BOOST_PP_REPEAT_FROM_TO(6, BOOST_PP_INC(BOOST_UNORDERED_TUPLE_ARGS),
1645 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE, std)
1646#endif
1647 }
1648 }
1649 }
1650}
1651
1652#endif
1653
1654#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE
1655#undef BOOST_UNORDERED_GET_TUPLE_ARG
1656
1657// construct_from_tuple for boost::tuple on old versions of sunpro.
1658//
1659// Old versions of Sun C++ had problems with template overloads of
1660// boost::tuple, so to fix it I added a distinct type for each length to
1661// the overloads. That means there's no possible ambiguity between the
1662// different overloads, so that the compiler doesn't get confused
1663
1664#if BOOST_UNORDERED_SUN_WORKAROUNDS1
1665
1666#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(z, n, namespace_) \
1667 template <typename Alloc, typename T, \
1668 BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
1669 void construct_from_tuple_impl(boost::unordered::detail::func::length<n>, \
1670 Alloc&, T* ptr, \
1671 namespace_::tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
1672 { \
1673 new ((void*)ptr) \
1674 T(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \
1675 }
1676
1677#define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_::get<n>(x)
1678
1679namespace boost {
1680 namespace unordered {
1681 namespace detail {
1682 namespace func {
1683 template <int N> struct length
1684 {
1685 };
1686
1687 template <typename Alloc, typename T>
1688 void construct_from_tuple_impl(
1689 boost::unordered::detail::func::length<0>, Alloc&, T* ptr,
1690 boost::tuple<>)
1691 {
1692 new ((void*)ptr) T();
1693 }
1694
1695 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, boost)
1696 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, boost)
1697 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, boost)
1698 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, boost)
1699 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, boost)
1700 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 6, boost)
1701 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 7, boost)
1702 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 8, boost)
1703 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 9, boost)
1704 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 10, boost)
1705
1706 template <typename Alloc, typename T, typename Tuple>
1707 void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x)
1708 {
1709 construct_from_tuple_impl(boost::unordered::detail::func::length<
1710 boost::tuples::length<Tuple>::value>(),
1711 alloc, ptr, x);
1712 }
1713 }
1714 }
1715 }
1716}
1717
1718#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE
1719#undef BOOST_UNORDERED_GET_TUPLE_ARG
1720
1721#endif
1722
1723namespace boost {
1724 namespace unordered {
1725 namespace detail {
1726 namespace func {
1727 ////////////////////////////////////////////////////////////////////////
1728 // Trait to check for piecewise construction.
1729
1730 template <typename A0> struct use_piecewise
1731 {
1732 static choice1::type test(
1733 choice1, boost::unordered::piecewise_construct_t);
1734
1735 static choice2::type test(choice2, ...);
1736
1737 enum
1738 {
1739 value = sizeof(choice1::type) ==
1740 sizeof(test(choose(), boost::unordered::detail::make<A0>()))
1741 };
1742 };
1743
1744#if BOOST_UNORDERED_CXX11_CONSTRUCTION
1745
1746 ////////////////////////////////////////////////////////////////////////
1747 // Construct from variadic parameters
1748
1749 template <typename Alloc, typename T, typename... Args>
1750 inline void construct_from_args(
1751 Alloc& alloc, T* address, BOOST_FWD_REF(Args)... args)
1752 {
1753 boost::unordered::detail::allocator_traits<Alloc>::construct(
1754 alloc, address, boost::forward<Args>(args)...);
1755 }
1756
1757 // For backwards compatibility, implement a special case for
1758 // piecewise_construct with boost::tuple
1759
1760 template <typename A0> struct detect_boost_tuple
1761 {
1762 template <typename T0, typename T1, typename T2, typename T3,
1763 typename T4, typename T5, typename T6, typename T7, typename T8,
1764 typename T9>
1765 static choice1::type test(choice1,
1766 boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> const&);
1767
1768 static choice2::type test(choice2, ...);
1769
1770 enum
1771 {
1772 value = sizeof(choice1::type) ==
1773 sizeof(test(choose(), boost::unordered::detail::make<A0>()))
1774 };
1775 };
1776
1777 // Special case for piecewise_construct
1778
1779 template <typename Alloc, typename A, typename B, typename A0,
1780 typename A1, typename A2>
1781 inline typename boost::enable_if_c<use_piecewise<A0>::value &&
1782 detect_boost_tuple<A1>::value &&
1783 detect_boost_tuple<A2>::value,
1784 void>::type
1785 construct_from_args(Alloc& alloc, std::pair<A, B>* address,
1786 BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
1787 {
1788 boost::unordered::detail::func::construct_from_tuple(
1789 alloc, boost::addressof(address->first), boost::forward<A1>(a1));
1790 BOOST_TRY
1791 {
1792 boost::unordered::detail::func::construct_from_tuple(
1793 alloc, boost::addressof(address->second), boost::forward<A2>(a2));
1794 }
1795 BOOST_CATCH(...)
1796 {
1797 boost::unordered::detail::func::destroy(
1798 boost::addressof(address->first));
1799 BOOST_RETHROW
1800 }
1801 BOOST_CATCH_END
1802 }
1803
1804#elif !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1805
1806 ////////////////////////////////////////////////////////////////////////
1807 // Construct from variadic parameters
1808
1809 template <typename Alloc, typename T, typename... Args>
1810 inline void construct_from_args(
1811 Alloc&, T* address, BOOST_FWD_REF(Args)... args)
1812 {
1813 new ((void*)address) T(boost::forward<Args>(args)...);
1814 }
1815
1816 // Special case for piecewise_construct
1817
1818 template <typename Alloc, typename A, typename B, typename A0,
1819 typename A1, typename A2>
1820 inline typename enable_if<use_piecewise<A0>, void>::type
1821 construct_from_args(Alloc& alloc, std::pair<A, B>* address,
1822 BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
1823 {
1824 boost::unordered::detail::func::construct_from_tuple(
1825 alloc, boost::addressof(address->first), boost::forward<A1>(a1));
1826 BOOST_TRY
1827 {
1828 boost::unordered::detail::func::construct_from_tuple(
1829 alloc, boost::addressof(address->second), boost::forward<A2>(a2));
1830 }
1831 BOOST_CATCH(...)
1832 {
1833 boost::unordered::detail::func::destroy(
1834 boost::addressof(address->first));
1835 BOOST_RETHROW
1836 }
1837 BOOST_CATCH_END
1838 }
1839
1840#else // BOOST_NO_CXX11_VARIADIC_TEMPLATES
1841
1842 ////////////////////////////////////////////////////////////////////////
1843 // Construct from emplace_args
1844
1845 // Explicitly write out first three overloads for the sake of sane
1846 // error messages.
1847
1848 template <typename Alloc, typename T, typename A0>
1849 inline void construct_from_args(
1850 Alloc&, T* address, emplace_args1<A0> const& args)
1851 {
1852 new ((void*)address) T(boost::forward<A0>(args.a0));
1853 }
1854
1855 template <typename Alloc, typename T, typename A0, typename A1>
1856 inline void construct_from_args(
1857 Alloc&, T* address, emplace_args2<A0, A1> const& args)
1858 {
1859 new ((void*)address)
1860 T(boost::forward<A0>(args.a0), boost::forward<A1>(args.a1));
1861 }
1862
1863 template <typename Alloc, typename T, typename A0, typename A1,
1864 typename A2>
1865 inline void construct_from_args(
1866 Alloc&, T* address, emplace_args3<A0, A1, A2> const& args)
1867 {
1868 new ((void*)address) T(boost::forward<A0>(args.a0),
1869 boost::forward<A1>(args.a1), boost::forward<A2>(args.a2));
1870 }
1871
1872// Use a macro for the rest.
1873
1874#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \
1875 template <typename Alloc, typename T, \
1876 BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A)> \
1877 inline void construct_from_args(Alloc&, T* address, \
1878 boost::unordered::detail::BOOST_PP_CAT(emplace_args, num_params) < \
1879 BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) > const& args) \
1880 { \
1881 new ((void*)address) \
1882 T(BOOST_PP_ENUM_##z(num_params, BOOST_UNORDERED_CALL_FORWARD, args.a)); \
1883 }
1884
1885 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 4, _)
1886 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 5, _)
1887 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 6, _)
1888 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 7, _)
1889 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 8, _)
1890 BOOST_UNORDERED_CONSTRUCT_IMPL(1, 9, _)
1891 BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
1892 BOOST_UNORDERED_CONSTRUCT_IMPL, _)
1893
1894#undef BOOST_UNORDERED_CONSTRUCT_IMPL
1895
1896 // Construct with piecewise_construct
1897
1898 template <typename Alloc, typename A, typename B, typename A0,
1899 typename A1, typename A2>
1900 inline void construct_from_args(Alloc& alloc, std::pair<A, B>* address,
1901 boost::unordered::detail::emplace_args3<A0, A1, A2> const& args,
1902 typename enable_if<use_piecewise<A0>, void*>::type = 0)
1903 {
1904 boost::unordered::detail::func::construct_from_tuple(
1905 alloc, boost::addressof(address->first), args.a1);
1906 BOOST_TRY
1907 {
1908 boost::unordered::detail::func::construct_from_tuple(
1909 alloc, boost::addressof(address->second), args.a2);
1910 }
1911 BOOST_CATCH(...)
1912 {
1913 boost::unordered::detail::func::destroy(
1914 boost::addressof(address->first));
1915 BOOST_RETHROW
1916 }
1917 BOOST_CATCH_END
1918 }
1919
1920#endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES
1921 }
1922 }
1923 }
1924}
1925
1926namespace boost {
1927 namespace unordered {
1928 namespace detail {
1929
1930 ///////////////////////////////////////////////////////////////////
1931 //
1932 // Node construction
1933
1934 template <typename NodeAlloc> struct node_constructor
1935 {
1936 typedef NodeAlloc node_allocator;
1937 typedef boost::unordered::detail::allocator_traits<NodeAlloc>
1938 node_allocator_traits;
1939 typedef typename node_allocator_traits::value_type node;
1940 typedef typename node_allocator_traits::pointer node_pointer;
1941 typedef typename node::value_type value_type;
1942
1943 node_allocator& alloc_;
1944 node_pointer node_;
1945
1946 node_constructor(node_allocator& n) : alloc_(n), node_() {}
1947
1948 ~node_constructor();
1949
1950 void create_node();
1951
1952 // no throw
1953 node_pointer release()
1954 {
1955 BOOST_ASSERT(node_);
1956 node_pointer p = node_;
1957 node_ = node_pointer();
1958 return p;
1959 }
1960
1961 void reclaim(node_pointer p)
1962 {
1963 BOOST_ASSERT(!node_);
1964 node_ = p;
1965 BOOST_UNORDERED_CALL_DESTROY(
1966 node_allocator_traits, alloc_, node_->value_ptr());
1967 }
1968
1969 private:
1970 node_constructor(node_constructor const&);
1971 node_constructor& operator=(node_constructor const&);
1972 };
1973
1974 template <typename Alloc> node_constructor<Alloc>::~node_constructor()
1975 {
1976 if (node_) {
1977 boost::unordered::detail::func::destroy(boost::to_address(node_));
1978 node_allocator_traits::deallocate(alloc_, node_, 1);
1979 }
1980 }
1981
1982 template <typename Alloc> void node_constructor<Alloc>::create_node()
1983 {
1984 BOOST_ASSERT(!node_);
1985 node_ = node_allocator_traits::allocate(alloc_, 1);
1986 new ((void*)boost::to_address(node_)) node();
1987 }
1988
1989 template <typename NodeAlloc> struct node_tmp
1990 {
1991 typedef boost::unordered::detail::allocator_traits<NodeAlloc>
1992 node_allocator_traits;
1993 typedef typename node_allocator_traits::pointer node_pointer;
1994 typedef typename node_allocator_traits::value_type node;
1995
1996 NodeAlloc& alloc_;
1997 node_pointer node_;
1998
1999 explicit node_tmp(node_pointer n, NodeAlloc& a) : alloc_(a), node_(n) {}
2000
2001 ~node_tmp();
2002
2003 // no throw
2004 node_pointer release()
2005 {
2006 node_pointer p = node_;
2007 node_ = node_pointer();
2008 return p;
2009 }
2010 };
2011
2012 template <typename Alloc> node_tmp<Alloc>::~node_tmp()
2013 {
2014 if (node_) {
2015 BOOST_UNORDERED_CALL_DESTROY(
2016 node_allocator_traits, alloc_, node_->value_ptr());
2017 boost::unordered::detail::func::destroy(boost::to_address(node_));
2018 node_allocator_traits::deallocate(alloc_, node_, 1);
2019 }
2020 }
2021 }
2022 }
2023}
2024
2025namespace boost {
2026 namespace unordered {
2027 namespace detail {
2028 namespace func {
2029
2030 // Some nicer construct_node functions, might try to
2031 // improve implementation later.
2032
2033 template <typename Alloc, BOOST_UNORDERED_EMPLACE_TEMPLATE>
2034 inline
2035 typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2036 construct_node_from_args(Alloc& alloc, BOOST_UNORDERED_EMPLACE_ARGS)
2037 {
2038 node_constructor<Alloc> a(alloc);
2039 a.create_node();
2040 construct_from_args(
2041 alloc, a.node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
2042 return a.release();
2043 }
2044
2045 template <typename Alloc, typename U>
2046 inline
2047 typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2048 construct_node(Alloc& alloc, BOOST_FWD_REF(U) x)
2049 {
2050 node_constructor<Alloc> a(alloc);
2051 a.create_node();
2052 BOOST_UNORDERED_CALL_CONSTRUCT1(
2053 boost::unordered::detail::allocator_traits<Alloc>, alloc,
2054 a.node_->value_ptr(), boost::forward<U>(x));
2055 return a.release();
2056 }
2057
2058#if BOOST_UNORDERED_CXX11_CONSTRUCTION
2059
2060 template <typename Alloc, typename Key>
2061 inline
2062 typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2063 construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k)
2064 {
2065 node_constructor<Alloc> a(alloc);
2066 a.create_node();
2067 boost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
2068 a.node_->value_ptr(), std::piecewise_construct,
2069 std::forward_as_tuple(boost::forward<Key>(k)),
2070 std::forward_as_tuple());
2071 return a.release();
2072 }
2073
2074 template <typename Alloc, typename Key, typename Mapped>
2075 inline
2076 typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2077 construct_node_pair(
2078 Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m)
2079 {
2080 node_constructor<Alloc> a(alloc);
2081 a.create_node();
2082 boost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
2083 a.node_->value_ptr(), std::piecewise_construct,
2084 std::forward_as_tuple(boost::forward<Key>(k)),
2085 std::forward_as_tuple(boost::forward<Mapped>(m)));
2086 return a.release();
2087 }
2088
2089 template <typename Alloc, typename Key, typename... Args>
2090 inline
2091 typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2092 construct_node_pair_from_args(
2093 Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Args)... args)
2094 {
2095 node_constructor<Alloc> a(alloc);
2096 a.create_node();
2097#if !(BOOST_COMP_CLANG && BOOST_COMP_CLANG < BOOST_VERSION_NUMBER(3, 8, 0) && \
2098 defined(BOOST_LIBSTDCXX11))
2099 boost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
2100 a.node_->value_ptr(), std::piecewise_construct,
2101 std::forward_as_tuple(boost::forward<Key>(k)),
2102 std::forward_as_tuple(boost::forward<Args>(args)...));
2103#else
2104 // It doesn't seem to be possible to construct a tuple with 3 variadic
2105 // rvalue reference members when using older versions of clang with
2106 // libstdc++, so just use std::make_tuple instead of
2107 // std::forward_as_tuple.
2108 boost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
2109 a.node_->value_ptr(), std::piecewise_construct,
2110 std::forward_as_tuple(boost::forward<Key>(k)),
2111 std::make_tuple(boost::forward<Args>(args)...));
2112#endif
2113 return a.release();
2114 }
2115
2116#else
2117
2118 template <typename Alloc, typename Key>
2119 inline
2120 typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2121 construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k)
2122 {
2123 node_constructor<Alloc> a(alloc);
2124 a.create_node();
2125 boost::unordered::detail::func::construct_value(
2126 boost::addressof(a.node_->value_ptr()->first),
2127 boost::forward<Key>(k));
2128 BOOST_TRY
2129 {
2130 boost::unordered::detail::func::construct_value(
2131 boost::addressof(a.node_->value_ptr()->second));
2132 }
2133 BOOST_CATCH(...)
2134 {
2135 boost::unordered::detail::func::destroy(
2136 boost::addressof(a.node_->value_ptr()->first));
2137 BOOST_RETHROW
2138 }
2139 BOOST_CATCH_END
2140 return a.release();
2141 }
2142
2143 template <typename Alloc, typename Key, typename Mapped>
2144 inline
2145 typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2146 construct_node_pair(
2147 Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m)
2148 {
2149 node_constructor<Alloc> a(alloc);
2150 a.create_node();
2151 boost::unordered::detail::func::construct_value(
2152 boost::addressof(a.node_->value_ptr()->first),
2153 boost::forward<Key>(k));
2154 BOOST_TRY
2155 {
2156 boost::unordered::detail::func::construct_value(
2157 boost::addressof(a.node_->value_ptr()->second),
2158 boost::forward<Mapped>(m));
2159 }
2160 BOOST_CATCH(...)
2161 {
2162 boost::unordered::detail::func::destroy(
2163 boost::addressof(a.node_->value_ptr()->first));
2164 BOOST_RETHROW
2165 }
2166 BOOST_CATCH_END
2167 return a.release();
2168 }
2169
2170 template <typename Alloc, typename Key,
2171 BOOST_UNORDERED_EMPLACE_TEMPLATE>
2172 inline
2173 typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2174 construct_node_pair_from_args(
2175 Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS)
2176 {
2177 node_constructor<Alloc> a(alloc);
2178 a.create_node();
2179 boost::unordered::detail::func::construct_value(
2180 boost::addressof(a.node_->value_ptr()->first),
2181 boost::forward<Key>(k));
2182 BOOST_TRY
2183 {
2184 boost::unordered::detail::func::construct_from_args(alloc,
2185 boost::addressof(a.node_->value_ptr()->second),
2186 BOOST_UNORDERED_EMPLACE_FORWARD);
2187 }
2188 BOOST_CATCH(...)
2189 {
2190 boost::unordered::detail::func::destroy(
2191 boost::addressof(a.node_->value_ptr()->first));
2192 BOOST_RETHROW
2193 }
2194 BOOST_CATCH_END
2195 return a.release();
2196 }
2197
2198#endif
2199 }
2200 }
2201 }
2202}
2203
2204#if defined(BOOST_MSVC)
2205#pragma warning(pop)
2206#endif
2207
2208// The 'iterator_detail' namespace was a misguided attempt at avoiding ADL
2209// in the detail namespace. It didn't work because the template parameters
2210// were in detail. I'm not changing it at the moment to be safe. I might
2211// do in the future if I change the iterator types.
2212namespace boost {
2213 namespace unordered {
2214 namespace iterator_detail {
2215
2216 //////////////////////////////////////////////////////////////////////////
2217 // Iterators
2218 //
2219 // all no throw
2220
2221 template <typename Node> struct l_iterator
2222 {
2223#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
2224 template <typename Node2>
2225 friend struct boost::unordered::iterator_detail::cl_iterator;
2226
2227 private:
2228#endif
2229 typedef typename Node::node_pointer node_pointer;
2230 node_pointer ptr_;
2231 std::size_t bucket_;
2232 std::size_t bucket_count_;
2233
2234 public:
2235 typedef typename Node::value_type element_type;
2236 typedef typename Node::value_type value_type;
2237 typedef value_type* pointer;
2238 typedef value_type& reference;
2239 typedef std::ptrdiff_t difference_type;
2240 typedef std::forward_iterator_tag iterator_category;
2241
2242 l_iterator() BOOST_NOEXCEPT : ptr_() {}
2243
2244 l_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT
2245 : ptr_(n),
2246 bucket_(b),
2247 bucket_count_(c)
2248 {
2249 }
2250
2251 value_type& operator*() const { return ptr_->value(); }
2252
2253 value_type* operator->() const { return ptr_->value_ptr(); }
2254
2255 l_iterator& operator++()
2256 {
2257 ptr_ = static_cast<node_pointer>(ptr_->next_);
2258 if (ptr_ && ptr_->get_bucket() != bucket_)
2259 ptr_ = node_pointer();
2260 return *this;
2261 }
2262
2263 l_iterator operator++(int)
2264 {
2265 l_iterator tmp(*this);
2266 ++(*this);
2267 return tmp;
2268 }
2269
2270 bool operator==(l_iterator x) const BOOST_NOEXCEPT
2271 {
2272 return ptr_ == x.ptr_;
2273 }
2274
2275 bool operator!=(l_iterator x) const BOOST_NOEXCEPT
2276 {
2277 return ptr_ != x.ptr_;
2278 }
2279 };
2280
2281 template <typename Node> struct cl_iterator
2282 {
2283 friend struct boost::unordered::iterator_detail::l_iterator<Node>;
2284
2285 private:
2286 typedef typename Node::node_pointer node_pointer;
2287 node_pointer ptr_;
2288 std::size_t bucket_;
2289 std::size_t bucket_count_;
2290
2291 public:
2292 typedef typename Node::value_type const element_type;
2293 typedef typename Node::value_type value_type;
2294 typedef value_type const* pointer;
2295 typedef value_type const& reference;
2296 typedef std::ptrdiff_t difference_type;
2297 typedef std::forward_iterator_tag iterator_category;
2298
2299 cl_iterator() BOOST_NOEXCEPT : ptr_() {}
2300
2301 cl_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT
2302 : ptr_(n),
2303 bucket_(b),
2304 bucket_count_(c)
2305 {
2306 }
2307
2308 cl_iterator(
2309 boost::unordered::iterator_detail::l_iterator<Node> const& x)
2310 BOOST_NOEXCEPT : ptr_(x.ptr_),
2311 bucket_(x.bucket_),
2312 bucket_count_(x.bucket_count_)
2313 {
2314 }
2315
2316 value_type const& operator*() const { return ptr_->value(); }
2317
2318 value_type const* operator->() const { return ptr_->value_ptr(); }
2319
2320 cl_iterator& operator++()
2321 {
2322 ptr_ = static_cast<node_pointer>(ptr_->next_);
2323 if (ptr_ && ptr_->get_bucket() != bucket_)
2324 ptr_ = node_pointer();
2325 return *this;
2326 }
2327
2328 cl_iterator operator++(int)
2329 {
2330 cl_iterator tmp(*this);
2331 ++(*this);
2332 return tmp;
2333 }
2334
2335 friend bool operator==(
2336 cl_iterator const& x, cl_iterator const& y) BOOST_NOEXCEPT
2337 {
2338 return x.ptr_ == y.ptr_;
2339 }
2340
2341 friend bool operator!=(
2342 cl_iterator const& x, cl_iterator const& y) BOOST_NOEXCEPT
2343 {
2344 return x.ptr_ != y.ptr_;
2345 }
2346 };
2347
2348 template <typename Node> struct iterator
2349 {
2350#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
2351 template <typename>
2352 friend struct boost::unordered::iterator_detail::c_iterator;
2353 template <typename> friend struct boost::unordered::detail::table;
2354
2355 private:
2356#endif
2357 typedef typename Node::node_pointer node_pointer;
2358 node_pointer node_;
2359
2360 public:
2361 typedef typename Node::value_type element_type;
2362 typedef typename Node::value_type value_type;
2363 typedef value_type* pointer;
2364 typedef value_type& reference;
2365 typedef std::ptrdiff_t difference_type;
2366 typedef std::forward_iterator_tag iterator_category;
2367
2368 iterator() BOOST_NOEXCEPT : node_() {}
2369
2370 explicit iterator(typename Node::link_pointer x) BOOST_NOEXCEPT
2371 : node_(static_cast<node_pointer>(x))
2372 {
2373 }
2374
2375 value_type& operator*() const { return node_->value(); }
2376
2377 value_type* operator->() const { return node_->value_ptr(); }
2378
2379 iterator& operator++()
2380 {
2381 node_ = static_cast<node_pointer>(node_->next_);
2382 return *this;
2383 }
2384
2385 iterator operator++(int)
2386 {
2387 iterator tmp(node_);
2388 node_ = static_cast<node_pointer>(node_->next_);
2389 return tmp;
2390 }
2391
2392 bool operator==(iterator const& x) const BOOST_NOEXCEPT
2393 {
2394 return node_ == x.node_;
2395 }
2396
2397 bool operator!=(iterator const& x) const BOOST_NOEXCEPT
2398 {
2399 return node_ != x.node_;
2400 }
2401 };
2402
2403 template <typename Node> struct c_iterator
2404 {
2405 friend struct boost::unordered::iterator_detail::iterator<Node>;
2406
2407#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
2408 template <typename> friend struct boost::unordered::detail::table;
2409
2410 private:
2411#endif
2412 typedef typename Node::node_pointer node_pointer;
2413 typedef boost::unordered::iterator_detail::iterator<Node> n_iterator;
2414 node_pointer node_;
2415
2416 public:
2417 typedef typename Node::value_type const element_type;
2418 typedef typename Node::value_type value_type;
2419 typedef value_type const* pointer;
2420 typedef value_type const& reference;
2421 typedef std::ptrdiff_t difference_type;
2422 typedef std::forward_iterator_tag iterator_category;
2423
2424 c_iterator() BOOST_NOEXCEPT : node_() {}
2425
2426 explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT
2427 : node_(static_cast<node_pointer>(x))
2428 {
2429 }
2430
2431 c_iterator(n_iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {}
2432
2433 value_type const& operator*() const { return node_->value(); }
2434
2435 value_type const* operator->() const { return node_->value_ptr(); }
2436
2437 c_iterator& operator++()
2438 {
2439 node_ = static_cast<node_pointer>(node_->next_);
2440 return *this;
2441 }
2442
2443 c_iterator operator++(int)
2444 {
2445 c_iterator tmp(node_);
2446 node_ = static_cast<node_pointer>(node_->next_);
2447 return tmp;
2448 }
2449
2450 friend bool operator==(
2451 c_iterator const& x, c_iterator const& y) BOOST_NOEXCEPT
2452 {
2453 return x.node_ == y.node_;
2454 }
2455
2456 friend bool operator!=(
2457 c_iterator const& x, c_iterator const& y) BOOST_NOEXCEPT
2458 {
2459 return x.node_ != y.node_;
2460 }
2461 };
2462 }
2463 }
2464}
2465
2466namespace boost {
2467 namespace unordered {
2468 namespace detail {
2469
2470 ///////////////////////////////////////////////////////////////////
2471 //
2472 // Node Holder
2473 //
2474 // Temporary store for nodes. Deletes any that aren't used.
2475
2476 template <typename NodeAlloc> struct node_holder
2477 {
2478 private:
2479 typedef NodeAlloc node_allocator;
2480 typedef boost::unordered::detail::allocator_traits<NodeAlloc>
2481 node_allocator_traits;
2482 typedef typename node_allocator_traits::value_type node;
2483 typedef typename node_allocator_traits::pointer node_pointer;
2484 typedef typename node::value_type value_type;
2485 typedef typename node::link_pointer link_pointer;
2486 typedef boost::unordered::iterator_detail::iterator<node> iterator;
2487
2488 node_constructor<NodeAlloc> constructor_;
2489 node_pointer nodes_;
2490
2491 public:
2492 template <typename Table>
2493 explicit node_holder(Table& b) : constructor_(b.node_alloc()), nodes_()
2494 {
2495 if (b.size_) {
2496 typename Table::link_pointer prev = b.get_previous_start();
2497 nodes_ = static_cast<node_pointer>(prev->next_);
2498 prev->next_ = link_pointer();
2499 b.size_ = 0;
2500 }
2501 }
2502
2503 ~node_holder();
2504
2505 node_pointer pop_node()
2506 {
2507 node_pointer n = nodes_;
2508 nodes_ = static_cast<node_pointer>(nodes_->next_);
2509 n->next_ = link_pointer();
2510 return n;
2511 }
2512
2513 template <typename T> inline node_pointer copy_of(T const& v)
2514 {
2515 if (nodes_) {
2516 constructor_.reclaim(pop_node());
2517 } else {
2518 constructor_.create_node();
2519 }
2520 BOOST_UNORDERED_CALL_CONSTRUCT1(node_allocator_traits,
2521 constructor_.alloc_, constructor_.node_->value_ptr(), v);
2522 return constructor_.release();
2523 }
2524
2525 template <typename T> inline node_pointer move_copy_of(T& v)
2526 {
2527 if (nodes_) {
2528 constructor_.reclaim(pop_node());
2529 } else {
2530 constructor_.create_node();
2531 }
2532 BOOST_UNORDERED_CALL_CONSTRUCT1(node_allocator_traits,
2533 constructor_.alloc_, constructor_.node_->value_ptr(),
2534 boost::move(v));
2535 return constructor_.release();
2536 }
2537
2538 iterator begin() const { return iterator(nodes_); }
2539 };
2540
2541 template <typename Alloc> node_holder<Alloc>::~node_holder()
2542 {
2543 while (nodes_) {
2544 node_pointer p = nodes_;
2545 nodes_ = static_cast<node_pointer>(p->next_);
2546
2547 BOOST_UNORDERED_CALL_DESTROY(
2548 node_allocator_traits, constructor_.alloc_, p->value_ptr());
2549 boost::unordered::detail::func::destroy(boost::to_address(p));
2550 node_allocator_traits::deallocate(constructor_.alloc_, p, 1);
2551 }
2552 }
2553
2554 ///////////////////////////////////////////////////////////////////
2555 //
2556 // Bucket
2557
2558 template <typename NodePointer> struct bucket
2559 {
2560 typedef NodePointer link_pointer;
2561 link_pointer next_;
2562
2563 bucket() : next_() {}
2564 bucket(link_pointer n) : next_(n) {}
2565
2566 link_pointer first_from_start() { return next_; }
2567
2568 enum
2569 {
2570 extra_node = true
2571 };
2572 };
2573
2574 struct ptr_bucket
2575 {
2576 typedef ptr_bucket* link_pointer;
2577 link_pointer next_;
2578
2579 ptr_bucket() : next_(0) {}
2580 ptr_bucket(link_pointer n) : next_(n) {}
2581
2582 link_pointer first_from_start() { return this; }
2583
2584 enum
2585 {
2586 extra_node = false
2587 };
2588 };
2589
2590 ///////////////////////////////////////////////////////////////////
2591 //
2592 // Hash Policy
2593
2594 template <typename SizeT> struct prime_policy
2595 {
2596 template <typename Hash, typename T>
2597 static inline SizeT apply_hash(Hash const& hf, T const& x)
2598 {
2599 return hf(x);
2600 }
2601
2602 static inline SizeT to_bucket(SizeT bucket_count, SizeT hash)
2603 {
2604 return hash % bucket_count;
2605 }
2606
2607 static inline SizeT new_bucket_count(SizeT min)
2608 {
2609 return boost::unordered::detail::next_prime(num: min);
2610 }
2611
2612 static inline SizeT prev_bucket_count(SizeT max)
2613 {
2614 return boost::unordered::detail::prev_prime(num: max);
2615 }
2616 };
2617
2618 template <typename SizeT> struct mix64_policy
2619 {
2620 template <typename Hash, typename T>
2621 static inline SizeT apply_hash(Hash const& hf, T const& x)
2622 {
2623 SizeT key = hf(x);
2624 key = (~key) + (key << 21); // key = (key << 21) - key - 1;
2625 key = key ^ (key >> 24);
2626 key = (key + (key << 3)) + (key << 8); // key * 265
2627 key = key ^ (key >> 14);
2628 key = (key + (key << 2)) + (key << 4); // key * 21
2629 key = key ^ (key >> 28);
2630 key = key + (key << 31);
2631 return key;
2632 }
2633
2634 static inline SizeT to_bucket(SizeT bucket_count, SizeT hash)
2635 {
2636 return hash & (bucket_count - 1);
2637 }
2638
2639 static inline SizeT new_bucket_count(SizeT min)
2640 {
2641 if (min <= 4)
2642 return 4;
2643 --min;
2644 min |= min >> 1;
2645 min |= min >> 2;
2646 min |= min >> 4;
2647 min |= min >> 8;
2648 min |= min >> 16;
2649 min |= min >> 32;
2650 return min + 1;
2651 }
2652
2653 static inline SizeT prev_bucket_count(SizeT max)
2654 {
2655 max |= max >> 1;
2656 max |= max >> 2;
2657 max |= max >> 4;
2658 max |= max >> 8;
2659 max |= max >> 16;
2660 max |= max >> 32;
2661 return (max >> 1) + 1;
2662 }
2663 };
2664
2665 template <int digits, int radix> struct pick_policy_impl
2666 {
2667 typedef prime_policy<std::size_t> type;
2668 };
2669
2670 template <> struct pick_policy_impl<64, 2>
2671 {
2672 typedef mix64_policy<std::size_t> type;
2673 };
2674
2675 template <typename T>
2676 struct pick_policy2
2677 : pick_policy_impl<std::numeric_limits<std::size_t>::digits,
2678 std::numeric_limits<std::size_t>::radix>
2679 {
2680 };
2681
2682 // While the mix policy is generally faster, the prime policy is a lot
2683 // faster when a large number consecutive integers are used, because
2684 // there are no collisions. Since that is probably quite common, use
2685 // prime policy for integeral types. But not the smaller ones, as they
2686 // don't have enough unique values for this to be an issue.
2687
2688 template <> struct pick_policy2<int>
2689 {
2690 typedef prime_policy<std::size_t> type;
2691 };
2692
2693 template <> struct pick_policy2<unsigned int>
2694 {
2695 typedef prime_policy<std::size_t> type;
2696 };
2697
2698 template <> struct pick_policy2<long>
2699 {
2700 typedef prime_policy<std::size_t> type;
2701 };
2702
2703 template <> struct pick_policy2<unsigned long>
2704 {
2705 typedef prime_policy<std::size_t> type;
2706 };
2707
2708#if !defined(BOOST_NO_LONG_LONG)
2709 template <> struct pick_policy2<boost::long_long_type>
2710 {
2711 typedef prime_policy<std::size_t> type;
2712 };
2713
2714 template <> struct pick_policy2<boost::ulong_long_type>
2715 {
2716 typedef prime_policy<std::size_t> type;
2717 };
2718#endif
2719
2720 template <typename T>
2721 struct pick_policy : pick_policy2<typename boost::remove_cv<T>::type>
2722 {
2723 };
2724
2725 //////////////////////////////////////////////////////////////////////////
2726 // Functions
2727 //
2728 // This double buffers the storage for the hash function and key equality
2729 // predicate in order to have exception safe copy/swap. To do so,
2730 // use 'construct_spare' to construct in the spare space, and then when
2731 // ready to use 'switch_functions' to switch to the new functions.
2732 // If an exception is thrown between these two calls, use
2733 // 'cleanup_spare_functions' to destroy the unused constructed functions.
2734
2735 template <class H, class P> class functions
2736 {
2737 public:
2738 static const bool nothrow_move_assignable =
2739 boost::is_nothrow_move_assignable<H>::value &&
2740 boost::is_nothrow_move_assignable<P>::value;
2741 static const bool nothrow_move_constructible =
2742 boost::is_nothrow_move_constructible<H>::value &&
2743 boost::is_nothrow_move_constructible<P>::value;
2744 static const bool nothrow_swappable =
2745 boost::is_nothrow_swappable<H>::value &&
2746 boost::is_nothrow_swappable<P>::value;
2747
2748 private:
2749 functions& operator=(functions const&);
2750
2751 typedef compressed<H, P> function_pair;
2752
2753 typedef typename boost::aligned_storage<sizeof(function_pair),
2754 boost::alignment_of<function_pair>::value>::type aligned_function;
2755
2756 unsigned char current_; // 0/1 - Currently active functions
2757 // +2 - Both constructed
2758 aligned_function funcs_[2];
2759
2760 public:
2761 functions(H const& hf, P const& eq) : current_(0)
2762 {
2763 construct_functions(current_, hf, eq);
2764 }
2765
2766 functions(functions const& bf) : current_(0)
2767 {
2768 construct_functions(current_, bf.current_functions());
2769 }
2770
2771 functions(functions& bf, boost::unordered::detail::move_tag)
2772 : current_(0)
2773 {
2774 construct_functions(current_, bf.current_functions(),
2775 boost::unordered::detail::integral_constant<bool,
2776 nothrow_move_constructible>());
2777 }
2778
2779 ~functions()
2780 {
2781 BOOST_ASSERT(!(current_ & 2));
2782 destroy_functions(which: current_);
2783 }
2784
2785 H const& hash_function() const { return current_functions().first(); }
2786
2787 P const& key_eq() const { return current_functions().second(); }
2788
2789 function_pair const& current_functions() const
2790 {
2791 return *static_cast<function_pair const*>(
2792 static_cast<void const*>(funcs_[current_ & 1].address()));
2793 }
2794
2795 function_pair& current_functions()
2796 {
2797 return *static_cast<function_pair*>(
2798 static_cast<void*>(funcs_[current_ & 1].address()));
2799 }
2800
2801 void construct_spare_functions(function_pair const& f)
2802 {
2803 BOOST_ASSERT(!(current_ & 2));
2804 construct_functions(current_ ^ 1, f);
2805 current_ |= 2;
2806 }
2807
2808 void cleanup_spare_functions()
2809 {
2810 if (current_ & 2) {
2811 current_ = static_cast<unsigned char>(current_ & 1);
2812 destroy_functions(which: current_ ^ 1);
2813 }
2814 }
2815
2816 void switch_functions()
2817 {
2818 BOOST_ASSERT(current_ & 2);
2819 destroy_functions(which: static_cast<unsigned char>(current_ & 1));
2820 current_ ^= 3;
2821 }
2822
2823 private:
2824 void construct_functions(unsigned char which, H const& hf, P const& eq)
2825 {
2826 BOOST_ASSERT(!(which & 2));
2827 new ((void*)&funcs_[which]) function_pair(hf, eq);
2828 }
2829
2830 void construct_functions(unsigned char which, function_pair const& f,
2831 boost::unordered::detail::false_type =
2832 boost::unordered::detail::false_type())
2833 {
2834 BOOST_ASSERT(!(which & 2));
2835 new ((void*)&funcs_[which]) function_pair(f);
2836 }
2837
2838 void construct_functions(unsigned char which, function_pair& f,
2839 boost::unordered::detail::true_type)
2840 {
2841 BOOST_ASSERT(!(which & 2));
2842 new ((void*)&funcs_[which])
2843 function_pair(f, boost::unordered::detail::move_tag());
2844 }
2845
2846 void destroy_functions(unsigned char which)
2847 {
2848 BOOST_ASSERT(!(which & 2));
2849 boost::unordered::detail::func::destroy(
2850 (function_pair*)(&funcs_[which]));
2851 }
2852 };
2853
2854////////////////////////////////////////////////////////////////////////////
2855// rvalue parameters when type can't be a BOOST_RV_REF(T) parameter
2856// e.g. for int
2857
2858#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
2859#define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T)
2860#else
2861 struct please_ignore_this_overload
2862 {
2863 typedef please_ignore_this_overload type;
2864 };
2865
2866 template <typename T> struct rv_ref_impl
2867 {
2868 typedef BOOST_RV_REF(T) type;
2869 };
2870
2871 template <typename T>
2872 struct rv_ref
2873 : boost::detail::if_true<boost::is_class<T>::value>::
2874 BOOST_NESTED_TEMPLATE then<boost::unordered::detail::rv_ref_impl<T>,
2875 please_ignore_this_overload>::type
2876 {
2877 };
2878
2879#define BOOST_UNORDERED_RV_REF(T) \
2880 typename boost::unordered::detail::rv_ref<T>::type
2881#endif
2882
2883#if defined(BOOST_MSVC)
2884#pragma warning(push)
2885#pragma warning(disable : 4127) // conditional expression is constant
2886#endif
2887
2888 //////////////////////////////////////////////////////////////////////////
2889 // convert double to std::size_t
2890
2891 inline std::size_t double_to_size(double f)
2892 {
2893 return f >= static_cast<double>(
2894 (std::numeric_limits<std::size_t>::max)())
2895 ? (std::numeric_limits<std::size_t>::max)()
2896 : static_cast<std::size_t>(f);
2897 }
2898
2899 template <typename Types>
2900 struct table : boost::unordered::detail::functions<typename Types::hasher,
2901 typename Types::key_equal>
2902 {
2903 private:
2904 table(table const&);
2905 table& operator=(table const&);
2906
2907 public:
2908 typedef typename Types::node node;
2909 typedef typename Types::bucket bucket;
2910 typedef typename Types::hasher hasher;
2911 typedef typename Types::key_equal key_equal;
2912 typedef typename Types::const_key_type const_key_type;
2913 typedef typename Types::extractor extractor;
2914 typedef typename Types::value_type value_type;
2915 typedef typename Types::table table_impl;
2916 typedef typename Types::link_pointer link_pointer;
2917 typedef typename Types::policy policy;
2918 typedef typename Types::iterator iterator;
2919 typedef typename Types::c_iterator c_iterator;
2920 typedef typename Types::l_iterator l_iterator;
2921 typedef typename Types::cl_iterator cl_iterator;
2922
2923 typedef boost::unordered::detail::functions<typename Types::hasher,
2924 typename Types::key_equal>
2925 functions;
2926
2927 typedef typename Types::value_allocator value_allocator;
2928 typedef typename boost::unordered::detail::rebind_wrap<value_allocator,
2929 node>::type node_allocator;
2930 typedef typename boost::unordered::detail::rebind_wrap<value_allocator,
2931 bucket>::type bucket_allocator;
2932 typedef boost::unordered::detail::allocator_traits<node_allocator>
2933 node_allocator_traits;
2934 typedef boost::unordered::detail::allocator_traits<bucket_allocator>
2935 bucket_allocator_traits;
2936 typedef typename node_allocator_traits::pointer node_pointer;
2937 typedef
2938 typename node_allocator_traits::const_pointer const_node_pointer;
2939 typedef typename bucket_allocator_traits::pointer bucket_pointer;
2940 typedef boost::unordered::detail::node_constructor<node_allocator>
2941 node_constructor;
2942 typedef boost::unordered::detail::node_tmp<node_allocator> node_tmp;
2943
2944 typedef std::pair<iterator, bool> emplace_return;
2945
2946 ////////////////////////////////////////////////////////////////////////
2947 // Members
2948
2949 boost::unordered::detail::compressed<bucket_allocator, node_allocator>
2950 allocators_;
2951 std::size_t bucket_count_;
2952 std::size_t size_;
2953 float mlf_;
2954 std::size_t max_load_;
2955 bucket_pointer buckets_;
2956
2957 ////////////////////////////////////////////////////////////////////////
2958 // Data access
2959
2960 static node_pointer get_node(c_iterator it) { return it.node_; }
2961
2962 static node_pointer next_node(link_pointer n)
2963 {
2964 return static_cast<node_pointer>(n->next_);
2965 }
2966
2967 static node_pointer next_for_find(link_pointer n)
2968 {
2969 node_pointer n2 = static_cast<node_pointer>(n);
2970 do {
2971 n2 = next_node(n: n2);
2972 } while (n2 && !n2->is_first_in_group());
2973 return n2;
2974 }
2975
2976 node_pointer next_group(node_pointer n) const
2977 {
2978 node_pointer n1 = n;
2979 do {
2980 n1 = next_node(n: n1);
2981 } while (n1 && !n1->is_first_in_group());
2982 return n1;
2983 }
2984
2985 std::size_t group_count(node_pointer n) const
2986 {
2987 std::size_t x = 0;
2988 node_pointer it = n;
2989 do {
2990 ++x;
2991 it = next_node(n: it);
2992 } while (it && !it->is_first_in_group());
2993
2994 return x;
2995 }
2996
2997 std::size_t node_bucket(node_pointer n) const
2998 {
2999 return n->get_bucket();
3000 }
3001
3002 bucket_allocator const& bucket_alloc() const
3003 {
3004 return allocators_.first();
3005 }
3006
3007 node_allocator const& node_alloc() const
3008 {
3009 return allocators_.second();
3010 }
3011
3012 bucket_allocator& bucket_alloc() { return allocators_.first(); }
3013
3014 node_allocator& node_alloc() { return allocators_.second(); }
3015
3016 std::size_t max_bucket_count() const
3017 {
3018 // -1 to account for the start bucket.
3019 return policy::prev_bucket_count(
3020 bucket_allocator_traits::max_size(bucket_alloc()) - 1);
3021 }
3022
3023 bucket_pointer get_bucket_pointer(std::size_t bucket_index) const
3024 {
3025 BOOST_ASSERT(buckets_);
3026 return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
3027 }
3028
3029 link_pointer get_previous_start() const
3030 {
3031 return get_bucket_pointer(bucket_index: bucket_count_)->first_from_start();
3032 }
3033
3034 link_pointer get_previous_start(std::size_t bucket_index) const
3035 {
3036 return get_bucket_pointer(bucket_index)->next_;
3037 }
3038
3039 node_pointer begin() const
3040 {
3041 return size_ ? next_node(n: get_previous_start()) : node_pointer();
3042 }
3043
3044 node_pointer begin(std::size_t bucket_index) const
3045 {
3046 if (!size_)
3047 return node_pointer();
3048 link_pointer prev = get_previous_start(bucket_index);
3049 return prev ? next_node(n: prev) : node_pointer();
3050 }
3051
3052 std::size_t hash_to_bucket(std::size_t hash_value) const
3053 {
3054 return policy::to_bucket(bucket_count_, hash_value);
3055 }
3056
3057 std::size_t bucket_size(std::size_t index) const
3058 {
3059 node_pointer n = begin(index);
3060 if (!n)
3061 return 0;
3062
3063 std::size_t count = 0;
3064 while (n && node_bucket(n) == index) {
3065 ++count;
3066 n = next_node(n);
3067 }
3068
3069 return count;
3070 }
3071
3072 ////////////////////////////////////////////////////////////////////////
3073 // Load methods
3074
3075 void recalculate_max_load()
3076 {
3077 using namespace std;
3078
3079 // From 6.3.1/13:
3080 // Only resize when size >= mlf_ * count
3081 max_load_ = buckets_ ? boost::unordered::detail::double_to_size(
3082 f: ceil(x: static_cast<double>(mlf_) *
3083 static_cast<double>(bucket_count_)))
3084 : 0;
3085 }
3086
3087 void max_load_factor(float z)
3088 {
3089 BOOST_ASSERT(z > 0);
3090 mlf_ = (std::max)(a: z, b: minimum_max_load_factor);
3091 recalculate_max_load();
3092 }
3093
3094 std::size_t min_buckets_for_size(std::size_t size) const
3095 {
3096 BOOST_ASSERT(mlf_ >= minimum_max_load_factor);
3097
3098 using namespace std;
3099
3100 // From insert/emplace requirements:
3101 //
3102 // size <= mlf_ * count
3103 // => count >= size / mlf_
3104 //
3105 // Or from rehash post-condition:
3106 //
3107 // count >= size / mlf_
3108
3109 return policy::new_bucket_count(
3110 boost::unordered::detail::double_to_size(
3111 f: floor(x: static_cast<double>(size) / static_cast<double>(mlf_)) +
3112 1));
3113 }
3114
3115 ////////////////////////////////////////////////////////////////////////
3116 // Constructors
3117
3118 table(std::size_t num_buckets, hasher const& hf, key_equal const& eq,
3119 node_allocator const& a)
3120 : functions(hf, eq), allocators_(a, a),
3121 bucket_count_(policy::new_bucket_count(num_buckets)), size_(0),
3122 mlf_(1.0f), max_load_(0), buckets_()
3123 {
3124 }
3125
3126 table(table const& x, node_allocator const& a)
3127 : functions(x), allocators_(a, a),
3128 bucket_count_(x.min_buckets_for_size(x.size_)), size_(0),
3129 mlf_(x.mlf_), max_load_(0), buckets_()
3130 {
3131 }
3132
3133 table(table& x, boost::unordered::detail::move_tag m)
3134 : functions(x, m), allocators_(x.allocators_, m),
3135 bucket_count_(x.bucket_count_), size_(x.size_), mlf_(x.mlf_),
3136 max_load_(x.max_load_), buckets_(x.buckets_)
3137 {
3138 x.buckets_ = bucket_pointer();
3139 x.size_ = 0;
3140 x.max_load_ = 0;
3141 }
3142
3143 table(table& x, node_allocator const& a,
3144 boost::unordered::detail::move_tag m)
3145 : functions(x, m), allocators_(a, a),
3146 bucket_count_(x.bucket_count_), size_(0), mlf_(x.mlf_),
3147 max_load_(0), buckets_()
3148 {
3149 }
3150
3151 ////////////////////////////////////////////////////////////////////////
3152 // Clear buckets and Create buckets
3153 //
3154 // IMPORTANT: If the container already contains any elements, the
3155 // buckets will not contain any links to them. This will
3156 // need to be dealt with, for example by:
3157 // - deleting them
3158 // - putting them in a 'node_holder' for future use
3159 // (as in assignment)
3160 // - placing them in buckets (see rehash_impl)
3161
3162 // Clear the bucket pointers.
3163 void clear_buckets()
3164 {
3165 bucket_pointer end = get_bucket_pointer(bucket_index: bucket_count_);
3166 for (bucket_pointer it = buckets_; it != end; ++it) {
3167 it->next_ = node_pointer();
3168 }
3169 }
3170
3171 // Create container buckets. If the container already contains any
3172 // buckets
3173 // the linked list will be transferred to the new buckets, but none
3174 // of the bucket pointers will be set. See above note.
3175 //
3176 // Strong exception safety.
3177 void create_buckets(std::size_t new_count)
3178 {
3179 link_pointer dummy_node;
3180
3181 // Construct the new buckets and dummy node, and destroy the old
3182 // buckets
3183 if (buckets_) {
3184 dummy_node =
3185 (buckets_ + static_cast<std::ptrdiff_t>(bucket_count_))->next_;
3186 bucket_pointer new_buckets =
3187 bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1);
3188 destroy_buckets();
3189 buckets_ = new_buckets;
3190 } else if (bucket::extra_node) {
3191 node_constructor a(node_alloc());
3192 a.create_node();
3193 buckets_ =
3194 bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1);
3195 dummy_node = a.release();
3196 } else {
3197 dummy_node = link_pointer();
3198 buckets_ =
3199 bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1);
3200 }
3201
3202 // nothrow from here...
3203 bucket_count_ = new_count;
3204 recalculate_max_load();
3205
3206 bucket_pointer end =
3207 buckets_ + static_cast<std::ptrdiff_t>(new_count);
3208 for (bucket_pointer i = buckets_; i != end; ++i) {
3209 new ((void*)boost::to_address(i)) bucket();
3210 }
3211 new ((void*)boost::to_address(end)) bucket(dummy_node);
3212 }
3213
3214 ////////////////////////////////////////////////////////////////////////
3215 // Swap and Move
3216
3217 void swap_allocators(table& other, false_type)
3218 {
3219 boost::unordered::detail::func::ignore_unused_variable_warning(other);
3220
3221 // According to 23.2.1.8, if propagate_on_container_swap is
3222 // false the behaviour is undefined unless the allocators
3223 // are equal.
3224 BOOST_ASSERT(node_alloc() == other.node_alloc());
3225 }
3226
3227 void swap_allocators(table& other, true_type)
3228 {
3229 allocators_.swap(other.allocators_);
3230 }
3231
3232 // Not nothrow swappable
3233 void swap(table& x, false_type)
3234 {
3235 if (this == &x) {
3236 return;
3237 }
3238
3239 this->construct_spare_functions(x.current_functions());
3240 BOOST_TRY { x.construct_spare_functions(this->current_functions()); }
3241 BOOST_CATCH(...)
3242 {
3243 this->cleanup_spare_functions();
3244 BOOST_RETHROW
3245 }
3246 BOOST_CATCH_END
3247 this->switch_functions();
3248 x.switch_functions();
3249
3250 swap_allocators(
3251 x, boost::unordered::detail::integral_constant<bool,
3252 allocator_traits<
3253 node_allocator>::propagate_on_container_swap::value>());
3254
3255 boost::swap(buckets_, x.buckets_);
3256 boost::swap(bucket_count_, x.bucket_count_);
3257 boost::swap(size_, x.size_);
3258 std::swap(mlf_, x.mlf_);
3259 std::swap(max_load_, x.max_load_);
3260 }
3261
3262 // Nothrow swappable
3263 void swap(table& x, true_type)
3264 {
3265 swap_allocators(
3266 x, boost::unordered::detail::integral_constant<bool,
3267 allocator_traits<
3268 node_allocator>::propagate_on_container_swap::value>());
3269
3270 boost::swap(buckets_, x.buckets_);
3271 boost::swap(bucket_count_, x.bucket_count_);
3272 boost::swap(size_, x.size_);
3273 std::swap(mlf_, x.mlf_);
3274 std::swap(max_load_, x.max_load_);
3275 this->current_functions().swap(x.current_functions());
3276 }
3277
3278 // Only swaps the allocators if propagate_on_container_swap.
3279 // If not propagate_on_container_swap and allocators aren't
3280 // equal, behaviour is undefined.
3281 void swap(table& x)
3282 {
3283 BOOST_ASSERT(allocator_traits<
3284 node_allocator>::propagate_on_container_swap::value ||
3285 node_alloc() == x.node_alloc());
3286 swap(x, boost::unordered::detail::integral_constant<bool,
3287 functions::nothrow_swappable>());
3288 }
3289
3290 // Only call with nodes allocated with the currect allocator, or
3291 // one that is equal to it. (Can't assert because other's
3292 // allocators might have already been moved).
3293 void move_buckets_from(table& other)
3294 {
3295 BOOST_ASSERT(!buckets_);
3296 buckets_ = other.buckets_;
3297 bucket_count_ = other.bucket_count_;
3298 size_ = other.size_;
3299 max_load_ = other.max_load_;
3300 other.buckets_ = bucket_pointer();
3301 other.size_ = 0;
3302 other.max_load_ = 0;
3303 }
3304
3305 // For use in the constructor when allocators might be different.
3306 void move_construct_buckets(table& src)
3307 {
3308 if (this->node_alloc() == src.node_alloc()) {
3309 move_buckets_from(other&: src);
3310 } else {
3311 this->create_buckets(this->bucket_count_);
3312 link_pointer prev = this->get_previous_start();
3313 std::size_t last_bucket = this->bucket_count_;
3314 for (node_pointer n = src.begin(); n; n = next_node(n)) {
3315 std::size_t n_bucket = n->get_bucket();
3316 if (n_bucket != last_bucket) {
3317 this->get_bucket_pointer(n_bucket)->next_ = prev;
3318 }
3319 node_pointer n2 = boost::unordered::detail::func::construct_node(
3320 this->node_alloc(), boost::move(n->value()));
3321 n2->bucket_info_ = n->bucket_info_;
3322 prev->next_ = n2;
3323 ++size_;
3324 prev = n2;
3325 last_bucket = n_bucket;
3326 }
3327 }
3328 }
3329
3330 ////////////////////////////////////////////////////////////////////////
3331 // Delete/destruct
3332
3333 ~table() { delete_buckets(); }
3334
3335 void destroy_node(node_pointer n)
3336 {
3337 BOOST_UNORDERED_CALL_DESTROY(
3338 node_allocator_traits, node_alloc(), n->value_ptr());
3339 boost::unordered::detail::func::destroy(boost::to_address(n));
3340 node_allocator_traits::deallocate(node_alloc(), n, 1);
3341 }
3342
3343 void delete_buckets()
3344 {
3345 if (buckets_) {
3346 node_pointer n = static_cast<node_pointer>(
3347 get_bucket_pointer(bucket_index: bucket_count_)->next_);
3348
3349 if (bucket::extra_node) {
3350 node_pointer next = next_node(n);
3351 boost::unordered::detail::func::destroy(boost::to_address(n));
3352 node_allocator_traits::deallocate(node_alloc(), n, 1);
3353 n = next;
3354 }
3355
3356 while (n) {
3357 node_pointer next = next_node(n);
3358 destroy_node(n);
3359 n = next;
3360 }
3361
3362 destroy_buckets();
3363 buckets_ = bucket_pointer();
3364 max_load_ = 0;
3365 size_ = 0;
3366 }
3367 }
3368
3369 void destroy_buckets()
3370 {
3371 bucket_pointer end = get_bucket_pointer(bucket_index: bucket_count_ + 1);
3372 for (bucket_pointer it = buckets_; it != end; ++it) {
3373 boost::unordered::detail::func::destroy(boost::to_address(it));
3374 }
3375
3376 bucket_allocator_traits::deallocate(
3377 bucket_alloc(), buckets_, bucket_count_ + 1);
3378 }
3379
3380 ////////////////////////////////////////////////////////////////////////
3381 // Fix buckets after delete/extract
3382 //
3383 // (prev,next) should mark an open range of nodes in a single bucket
3384 // which
3385 // have either been unlinked, or are about to be.
3386
3387 std::size_t fix_bucket(
3388 std::size_t bucket_index, link_pointer prev, node_pointer next)
3389 {
3390 std::size_t bucket_index2 = bucket_index;
3391
3392 if (next) {
3393 bucket_index2 = node_bucket(n: next);
3394
3395 // If next is in the same bucket, then there's nothing to do.
3396 if (bucket_index == bucket_index2) {
3397 return bucket_index2;
3398 }
3399
3400 // Update the bucket containing next.
3401 get_bucket_pointer(bucket_index: bucket_index2)->next_ = prev;
3402 }
3403
3404 // Check if this bucket is now empty.
3405 bucket_pointer this_bucket = get_bucket_pointer(bucket_index);
3406 if (this_bucket->next_ == prev) {
3407 this_bucket->next_ = link_pointer();
3408 }
3409
3410 return bucket_index2;
3411 }
3412
3413 ////////////////////////////////////////////////////////////////////////
3414 // Clear
3415
3416 void clear_impl();
3417
3418 ////////////////////////////////////////////////////////////////////////
3419 // Assignment
3420
3421 template <typename UniqueType>
3422 void assign(table const& x, UniqueType is_unique)
3423 {
3424 if (this != &x) {
3425 assign(x, is_unique,
3426 boost::unordered::detail::integral_constant<bool,
3427 allocator_traits<node_allocator>::
3428 propagate_on_container_copy_assignment::value>());
3429 }
3430 }
3431
3432 template <typename UniqueType>
3433 void assign(table const& x, UniqueType is_unique, false_type)
3434 {
3435 // Strong exception safety.
3436 this->construct_spare_functions(x.current_functions());
3437 BOOST_TRY
3438 {
3439 mlf_ = x.mlf_;
3440 recalculate_max_load();
3441
3442 if (x.size_ > max_load_) {
3443 create_buckets(new_count: min_buckets_for_size(size: x.size_));
3444 } else if (size_) {
3445 clear_buckets();
3446 }
3447 }
3448 BOOST_CATCH(...)
3449 {
3450 this->cleanup_spare_functions();
3451 BOOST_RETHROW
3452 }
3453 BOOST_CATCH_END
3454 this->switch_functions();
3455 assign_buckets(x, is_unique);
3456 }
3457
3458 template <typename UniqueType>
3459 void assign(table const& x, UniqueType is_unique, true_type)
3460 {
3461 if (node_alloc() == x.node_alloc()) {
3462 allocators_.assign(x.allocators_);
3463 assign(x, is_unique, false_type());
3464 } else {
3465 this->construct_spare_functions(x.current_functions());
3466 this->switch_functions();
3467
3468 // Delete everything with current allocators before assigning
3469 // the new ones.
3470 delete_buckets();
3471 allocators_.assign(x.allocators_);
3472
3473 // Copy over other data, all no throw.
3474 mlf_ = x.mlf_;
3475 bucket_count_ = min_buckets_for_size(size: x.size_);
3476
3477 // Finally copy the elements.
3478 if (x.size_) {
3479 copy_buckets(x, is_unique);
3480 }
3481 }
3482 }
3483
3484 template <typename UniqueType>
3485 void move_assign(table& x, UniqueType is_unique)
3486 {
3487 if (this != &x) {
3488 move_assign(x, is_unique,
3489 boost::unordered::detail::integral_constant<bool,
3490 allocator_traits<node_allocator>::
3491 propagate_on_container_move_assignment::value>());
3492 }
3493 }
3494
3495 // Propagate allocator
3496 template <typename UniqueType>
3497 void move_assign(table& x, UniqueType, true_type)
3498 {
3499 if (!functions::nothrow_move_assignable) {
3500 this->construct_spare_functions(x.current_functions());
3501 this->switch_functions();
3502 } else {
3503 this->current_functions().move_assign(x.current_functions());
3504 }
3505 delete_buckets();
3506 allocators_.move_assign(x.allocators_);
3507 mlf_ = x.mlf_;
3508 move_buckets_from(other&: x);
3509 }
3510
3511 // Don't propagate allocator
3512 template <typename UniqueType>
3513 void move_assign(table& x, UniqueType is_unique, false_type)
3514 {
3515 if (node_alloc() == x.node_alloc()) {
3516 move_assign_equal_alloc(x);
3517 } else {
3518 move_assign_realloc(x, is_unique);
3519 }
3520 }
3521
3522 void move_assign_equal_alloc(table& x)
3523 {
3524 if (!functions::nothrow_move_assignable) {
3525 this->construct_spare_functions(x.current_functions());
3526 this->switch_functions();
3527 } else {
3528 this->current_functions().move_assign(x.current_functions());
3529 }
3530 delete_buckets();
3531 mlf_ = x.mlf_;
3532 move_buckets_from(other&: x);
3533 }
3534
3535 template <typename UniqueType>
3536 void move_assign_realloc(table& x, UniqueType is_unique)
3537 {
3538 this->construct_spare_functions(x.current_functions());
3539 BOOST_TRY
3540 {
3541 mlf_ = x.mlf_;
3542 recalculate_max_load();
3543
3544 if (x.size_ > max_load_) {
3545 create_buckets(new_count: min_buckets_for_size(size: x.size_));
3546 } else if (size_) {
3547 clear_buckets();
3548 }
3549 }
3550 BOOST_CATCH(...)
3551 {
3552 this->cleanup_spare_functions();
3553 BOOST_RETHROW
3554 }
3555 BOOST_CATCH_END
3556 this->switch_functions();
3557 move_assign_buckets(x, is_unique);
3558 }
3559
3560 // Accessors
3561
3562 const_key_type& get_key(node_pointer n) const
3563 {
3564 return extractor::extract(n->value());
3565 }
3566
3567 std::size_t hash(const_key_type& k) const
3568 {
3569 return policy::apply_hash(this->hash_function(), k);
3570 }
3571
3572 // Find Node
3573
3574 node_pointer find_node(std::size_t key_hash, const_key_type& k) const
3575 {
3576 return this->find_node_impl(key_hash, k, this->key_eq());
3577 }
3578
3579 node_pointer find_node(const_key_type& k) const
3580 {
3581 return this->find_node_impl(hash(k), k, this->key_eq());
3582 }
3583
3584 template <class Key, class Pred>
3585 node_pointer find_node_impl(
3586 std::size_t key_hash, Key const& k, Pred const& eq) const
3587 {
3588 std::size_t bucket_index = this->hash_to_bucket(key_hash);
3589 node_pointer n = this->begin(bucket_index);
3590
3591 for (;;) {
3592 if (!n)
3593 return n;
3594
3595 if (eq(k, this->get_key(n))) {
3596 return n;
3597 } else if (this->node_bucket(n) != bucket_index) {
3598 return node_pointer();
3599 }
3600
3601 n = next_for_find(n);
3602 }
3603 }
3604
3605 // Find the node before the key, so that it can be erased.
3606 link_pointer find_previous_node(
3607 const_key_type& k, std::size_t bucket_index)
3608 {
3609 link_pointer prev = this->get_previous_start(bucket_index);
3610 if (!prev) {
3611 return prev;
3612 }
3613
3614 for (;;) {
3615 node_pointer n = next_node(n: prev);
3616 if (!n) {
3617 return link_pointer();
3618 } else if (n->is_first_in_group()) {
3619 if (node_bucket(n) != bucket_index) {
3620 return link_pointer();
3621 } else if (this->key_eq()(k, this->get_key(n))) {
3622 return prev;
3623 }
3624 }
3625 prev = n;
3626 }
3627 }
3628
3629 // Extract and erase
3630
3631 inline node_pointer extract_by_key(const_key_type& k)
3632 {
3633 if (!this->size_) {
3634 return node_pointer();
3635 }
3636 std::size_t key_hash = this->hash(k);
3637 std::size_t bucket_index = this->hash_to_bucket(key_hash);
3638 link_pointer prev = this->find_previous_node(k, bucket_index);
3639 if (!prev) {
3640 return node_pointer();
3641 }
3642 node_pointer n = next_node(n: prev);
3643 node_pointer n2 = next_node(n);
3644 if (n2) {
3645 n2->set_first_in_group();
3646 }
3647 prev->next_ = n2;
3648 --this->size_;
3649 this->fix_bucket(bucket_index, prev, n2);
3650 n->next_ = link_pointer();
3651
3652 return n;
3653 }
3654
3655 // Reserve and rehash
3656
3657 void reserve_for_insert(std::size_t);
3658 void rehash(std::size_t);
3659 void reserve(std::size_t);
3660 void rehash_impl(std::size_t);
3661
3662 ////////////////////////////////////////////////////////////////////////
3663 // Unique keys
3664
3665 // equals
3666
3667 bool equals_unique(table const& other) const
3668 {
3669 if (this->size_ != other.size_)
3670 return false;
3671
3672 for (node_pointer n1 = this->begin(); n1; n1 = next_node(n: n1)) {
3673 node_pointer n2 = other.find_node(other.get_key(n1));
3674
3675 if (!n2 || n1->value() != n2->value())
3676 return false;
3677 }
3678
3679 return true;
3680 }
3681
3682 // Emplace/Insert
3683
3684 inline node_pointer add_node_unique(
3685 node_pointer n, std::size_t key_hash)
3686 {
3687 std::size_t bucket_index = this->hash_to_bucket(key_hash);
3688 bucket_pointer b = this->get_bucket_pointer(bucket_index);
3689
3690 n->bucket_info_ = bucket_index;
3691 n->set_first_in_group();
3692
3693 if (!b->next_) {
3694 link_pointer start_node = this->get_previous_start();
3695
3696 if (start_node->next_) {
3697 this->get_bucket_pointer(node_bucket(n: next_node(n: start_node)))
3698 ->next_ = n;
3699 }
3700
3701 b->next_ = start_node;
3702 n->next_ = start_node->next_;
3703 start_node->next_ = n;
3704 } else {
3705 n->next_ = b->next_->next_;
3706 b->next_->next_ = n;
3707 }
3708
3709 ++this->size_;
3710 return n;
3711 }
3712
3713 inline node_pointer resize_and_add_node_unique(
3714 node_pointer n, std::size_t key_hash)
3715 {
3716 node_tmp b(n, this->node_alloc());
3717 this->reserve_for_insert(this->size_ + 1);
3718 return this->add_node_unique(b.release(), key_hash);
3719 }
3720
3721 template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
3722 iterator emplace_hint_unique(
3723 c_iterator hint, const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS)
3724 {
3725 if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) {
3726 return iterator(hint.node_);
3727 } else {
3728 return emplace_unique(k, BOOST_UNORDERED_EMPLACE_FORWARD).first;
3729 }
3730 }
3731
3732 template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
3733 emplace_return emplace_unique(
3734 const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS)
3735 {
3736 std::size_t key_hash = this->hash(k);
3737 node_pointer pos = this->find_node(key_hash, k);
3738 if (pos) {
3739 return emplace_return(iterator(pos), false);
3740 } else {
3741 return emplace_return(
3742 iterator(this->resize_and_add_node_unique(
3743 boost::unordered::detail::func::construct_node_from_args(
3744 this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
3745 key_hash)),
3746 true);
3747 }
3748 }
3749
3750 template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
3751 iterator emplace_hint_unique(
3752 c_iterator hint, no_key, BOOST_UNORDERED_EMPLACE_ARGS)
3753 {
3754 node_tmp b(boost::unordered::detail::func::construct_node_from_args(
3755 this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
3756 this->node_alloc());
3757 const_key_type& k = this->get_key(b.node_);
3758 if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) {
3759 return iterator(hint.node_);
3760 }
3761 std::size_t key_hash = this->hash(k);
3762 node_pointer pos = this->find_node(key_hash, k);
3763 if (pos) {
3764 return iterator(pos);
3765 } else {
3766 return iterator(
3767 this->resize_and_add_node_unique(b.release(), key_hash));
3768 }
3769 }
3770
3771 template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
3772 emplace_return emplace_unique(no_key, BOOST_UNORDERED_EMPLACE_ARGS)
3773 {
3774 node_tmp b(boost::unordered::detail::func::construct_node_from_args(
3775 this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
3776 this->node_alloc());
3777 const_key_type& k = this->get_key(b.node_);
3778 std::size_t key_hash = this->hash(k);
3779 node_pointer pos = this->find_node(key_hash, k);
3780 if (pos) {
3781 return emplace_return(iterator(pos), false);
3782 } else {
3783 return emplace_return(
3784 iterator(this->resize_and_add_node_unique(b.release(), key_hash)),
3785 true);
3786 }
3787 }
3788
3789 template <typename Key>
3790 emplace_return try_emplace_unique(BOOST_FWD_REF(Key) k)
3791 {
3792 std::size_t key_hash = this->hash(k);
3793 node_pointer pos = this->find_node(key_hash, k);
3794 if (pos) {
3795 return emplace_return(iterator(pos), false);
3796 } else {
3797 return emplace_return(
3798 iterator(this->resize_and_add_node_unique(
3799 boost::unordered::detail::func::construct_node_pair(
3800 this->node_alloc(), boost::forward<Key>(k)),
3801 key_hash)),
3802 true);
3803 }
3804 }
3805
3806 template <typename Key>
3807 iterator try_emplace_hint_unique(c_iterator hint, BOOST_FWD_REF(Key) k)
3808 {
3809 if (hint.node_ && this->key_eq()(hint->first, k)) {
3810 return iterator(hint.node_);
3811 } else {
3812 return try_emplace_unique(k).first;
3813 }
3814 }
3815
3816 template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE>
3817 emplace_return try_emplace_unique(
3818 BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS)
3819 {
3820 std::size_t key_hash = this->hash(k);
3821 node_pointer pos = this->find_node(key_hash, k);
3822 if (pos) {
3823 return emplace_return(iterator(pos), false);
3824 } else {
3825 return emplace_return(
3826 iterator(this->resize_and_add_node_unique(
3827 boost::unordered::detail::func::construct_node_pair_from_args(
3828 this->node_alloc(), boost::forward<Key>(k),
3829 BOOST_UNORDERED_EMPLACE_FORWARD),
3830 key_hash)),
3831 true);
3832 }
3833 }
3834
3835 template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE>
3836 iterator try_emplace_hint_unique(
3837 c_iterator hint, BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS)
3838 {
3839 if (hint.node_ && this->key_eq()(hint->first, k)) {
3840 return iterator(hint.node_);
3841 } else {
3842 return try_emplace_unique(k, BOOST_UNORDERED_EMPLACE_FORWARD).first;
3843 }
3844 }
3845
3846 template <typename Key, typename M>
3847 emplace_return insert_or_assign_unique(
3848 BOOST_FWD_REF(Key) k, BOOST_FWD_REF(M) obj)
3849 {
3850 std::size_t key_hash = this->hash(k);
3851 node_pointer pos = this->find_node(key_hash, k);
3852
3853 if (pos) {
3854 pos->value().second = boost::forward<M>(obj);
3855 return emplace_return(iterator(pos), false);
3856 } else {
3857 return emplace_return(
3858 iterator(this->resize_and_add_node_unique(
3859 boost::unordered::detail::func::construct_node_pair(
3860 this->node_alloc(), boost::forward<Key>(k),
3861 boost::forward<M>(obj)),
3862 key_hash)),
3863 true);
3864 }
3865 }
3866
3867 template <typename NodeType, typename InsertReturnType>
3868 void move_insert_node_type_unique(
3869 NodeType& np, InsertReturnType& result)
3870 {
3871 if (np) {
3872 const_key_type& k = this->get_key(np.ptr_);
3873 std::size_t key_hash = this->hash(k);
3874 node_pointer pos = this->find_node(key_hash, k);
3875
3876 if (pos) {
3877 result.node = boost::move(np);
3878 result.position = iterator(pos);
3879 } else {
3880 this->reserve_for_insert(this->size_ + 1);
3881 result.position =
3882 iterator(this->add_node_unique(np.ptr_, key_hash));
3883 result.inserted = true;
3884 np.ptr_ = node_pointer();
3885 }
3886 }
3887 }
3888
3889 template <typename NodeType>
3890 iterator move_insert_node_type_with_hint_unique(
3891 c_iterator hint, NodeType& np)
3892 {
3893 if (!np) {
3894 return iterator();
3895 }
3896 const_key_type& k = this->get_key(np.ptr_);
3897 if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) {
3898 return iterator(hint.node_);
3899 }
3900 std::size_t key_hash = this->hash(k);
3901 node_pointer pos = this->find_node(key_hash, k);
3902 if (!pos) {
3903 this->reserve_for_insert(this->size_ + 1);
3904 pos = this->add_node_unique(np.ptr_, key_hash);
3905 np.ptr_ = node_pointer();
3906 }
3907 return iterator(pos);
3908 }
3909
3910 template <typename Types2>
3911 void merge_unique(boost::unordered::detail::table<Types2>& other)
3912 {
3913 typedef boost::unordered::detail::table<Types2> other_table;
3914 BOOST_STATIC_ASSERT(
3915 (boost::is_same<node, typename other_table::node>::value));
3916 BOOST_ASSERT(this->node_alloc() == other.node_alloc());
3917
3918 if (other.size_) {
3919 link_pointer prev = other.get_previous_start();
3920
3921 while (prev->next_) {
3922 node_pointer n = other_table::next_node(prev);
3923 const_key_type& k = this->get_key(n);
3924 std::size_t key_hash = this->hash(k);
3925 node_pointer pos = this->find_node(key_hash, k);
3926
3927 if (pos) {
3928 prev = n;
3929 } else {
3930 this->reserve_for_insert(this->size_ + 1);
3931 node_pointer n2 = next_node(n);
3932 prev->next_ = n2;
3933 if (n2 && n->is_first_in_group()) {
3934 n2->set_first_in_group();
3935 }
3936 --other.size_;
3937 other.fix_bucket(other.node_bucket(n), prev, n2);
3938 this->add_node_unique(n, key_hash);
3939 }
3940 }
3941 }
3942 }
3943
3944 ////////////////////////////////////////////////////////////////////////
3945 // Insert range methods
3946 //
3947 // if hash function throws, or inserting > 1 element, basic exception
3948 // safety strong otherwise
3949
3950 template <class InputIt>
3951 void insert_range_unique(const_key_type& k, InputIt i, InputIt j)
3952 {
3953 insert_range_unique2(k, i, j);
3954
3955 while (++i != j) {
3956 // Note: can't use get_key as '*i' might not be value_type - it
3957 // could be a pair with first_types as key_type without const or
3958 // a different second_type.
3959 insert_range_unique2(extractor::extract(*i), i, j);
3960 }
3961 }
3962
3963 template <class InputIt>
3964 void insert_range_unique2(const_key_type& k, InputIt i, InputIt j)
3965 {
3966 // No side effects in this initial code
3967 std::size_t key_hash = this->hash(k);
3968 node_pointer pos = this->find_node(key_hash, k);
3969
3970 if (!pos) {
3971 node_tmp b(boost::unordered::detail::func::construct_node(
3972 this->node_alloc(), *i),
3973 this->node_alloc());
3974 if (this->size_ + 1 > this->max_load_)
3975 this->reserve_for_insert(
3976 this->size_ + boost::unordered::detail::insert_size(i, j));
3977 this->add_node_unique(b.release(), key_hash);
3978 }
3979 }
3980
3981 template <class InputIt>
3982 void insert_range_unique(no_key, InputIt i, InputIt j)
3983 {
3984 node_constructor a(this->node_alloc());
3985
3986 do {
3987 if (!a.node_) {
3988 a.create_node();
3989 }
3990 BOOST_UNORDERED_CALL_CONSTRUCT1(
3991 node_allocator_traits, a.alloc_, a.node_->value_ptr(), *i);
3992 node_tmp b(a.release(), a.alloc_);
3993
3994 const_key_type& k = this->get_key(b.node_);
3995 std::size_t key_hash = this->hash(k);
3996 node_pointer pos = this->find_node(key_hash, k);
3997
3998 if (pos) {
3999 a.reclaim(b.release());
4000 } else {
4001 // reserve has basic exception safety if the hash function
4002 // throws, strong otherwise.
4003 this->reserve_for_insert(this->size_ + 1);
4004 this->add_node_unique(b.release(), key_hash);
4005 }
4006 } while (++i != j);
4007 }
4008
4009 ////////////////////////////////////////////////////////////////////////
4010 // Extract
4011
4012 inline node_pointer extract_by_iterator_unique(c_iterator i)
4013 {
4014 node_pointer n = i.node_;
4015 BOOST_ASSERT(n);
4016 std::size_t bucket_index = this->node_bucket(n);
4017 link_pointer prev = this->get_previous_start(bucket_index);
4018 while (prev->next_ != n) {
4019 prev = prev->next_;
4020 }
4021 node_pointer n2 = next_node(n);
4022 prev->next_ = n2;
4023 --this->size_;
4024 this->fix_bucket(bucket_index, prev, n2);
4025 n->next_ = link_pointer();
4026 return n;
4027 }
4028
4029 ////////////////////////////////////////////////////////////////////////
4030 // Erase
4031 //
4032 // no throw
4033
4034 std::size_t erase_key_unique(const_key_type& k)
4035 {
4036 if (!this->size_)
4037 return 0;
4038 std::size_t key_hash = this->hash(k);
4039 std::size_t bucket_index = this->hash_to_bucket(key_hash);
4040 link_pointer prev = this->find_previous_node(k, bucket_index);
4041 if (!prev)
4042 return 0;
4043 node_pointer n = next_node(n: prev);
4044 node_pointer n2 = next_node(n);
4045 prev->next_ = n2;
4046 --size_;
4047 this->fix_bucket(bucket_index, prev, n2);
4048 this->destroy_node(n);
4049 return 1;
4050 }
4051
4052 void erase_nodes_unique(node_pointer i, node_pointer j)
4053 {
4054 std::size_t bucket_index = this->node_bucket(i);
4055
4056 // Find the node before i.
4057 link_pointer prev = this->get_previous_start(bucket_index);
4058 while (prev->next_ != i)
4059 prev = prev->next_;
4060
4061 // Delete the nodes.
4062 prev->next_ = j;
4063 do {
4064 node_pointer next = next_node(n: i);
4065 destroy_node(n: i);
4066 --size_;
4067 bucket_index = this->fix_bucket(bucket_index, prev, next);
4068 i = next;
4069 } while (i != j);
4070 }
4071
4072 ////////////////////////////////////////////////////////////////////////
4073 // fill_buckets_unique
4074
4075 void copy_buckets(table const& src, true_type)
4076 {
4077 this->create_buckets(this->bucket_count_);
4078
4079 for (node_pointer n = src.begin(); n; n = next_node(n)) {
4080 std::size_t key_hash = this->hash(this->get_key(n));
4081 this->add_node_unique(
4082 boost::unordered::detail::func::construct_node(
4083 this->node_alloc(), n->value()),
4084 key_hash);
4085 }
4086 }
4087
4088 void assign_buckets(table const& src, true_type)
4089 {
4090 node_holder<node_allocator> holder(*this);
4091 for (node_pointer n = src.begin(); n; n = next_node(n)) {
4092 std::size_t key_hash = this->hash(this->get_key(n));
4093 this->add_node_unique(holder.copy_of(n->value()), key_hash);
4094 }
4095 }
4096
4097 void move_assign_buckets(table& src, true_type)
4098 {
4099 node_holder<node_allocator> holder(*this);
4100 for (node_pointer n = src.begin(); n; n = next_node(n)) {
4101 std::size_t key_hash = this->hash(this->get_key(n));
4102 this->add_node_unique(holder.move_copy_of(n->value()), key_hash);
4103 }
4104 }
4105
4106 ////////////////////////////////////////////////////////////////////////
4107 // Equivalent keys
4108
4109 // Equality
4110
4111 bool equals_equiv(table const& other) const
4112 {
4113 if (this->size_ != other.size_)
4114 return false;
4115
4116 for (node_pointer n1 = this->begin(); n1;) {
4117 node_pointer n2 = other.find_node(other.get_key(n1));
4118 if (!n2)
4119 return false;
4120 node_pointer end1 = next_group(n: n1);
4121 node_pointer end2 = next_group(n: n2);
4122 if (!group_equals_equiv(n1, end1, n2, end2))
4123 return false;
4124 n1 = end1;
4125 }
4126
4127 return true;
4128 }
4129
4130 static bool group_equals_equiv(node_pointer n1, node_pointer end1,
4131 node_pointer n2, node_pointer end2)
4132 {
4133 for (;;) {
4134 if (n1->value() != n2->value())
4135 break;
4136
4137 n1 = next_node(n: n1);
4138 n2 = next_node(n: n2);
4139
4140 if (n1 == end1)
4141 return n2 == end2;
4142 if (n2 == end2)
4143 return false;
4144 }
4145
4146 for (node_pointer n1a = n1, n2a = n2;;) {
4147 n1a = next_node(n: n1a);
4148 n2a = next_node(n: n2a);
4149
4150 if (n1a == end1) {
4151 if (n2a == end2)
4152 break;
4153 else
4154 return false;
4155 }
4156
4157 if (n2a == end2)
4158 return false;
4159 }
4160
4161 node_pointer start = n1;
4162 for (; n1 != end1; n1 = next_node(n: n1)) {
4163 value_type const& v = n1->value();
4164 if (!find_equiv(n: start, end: n1, v)) {
4165 std::size_t matches = count_equal_equiv(n: n2, end: end2, v);
4166 if (!matches)
4167 return false;
4168 if (matches != 1 + count_equal_equiv(n: next_node(n: n1), end: end1, v))
4169 return false;
4170 }
4171 }
4172
4173 return true;
4174 }
4175
4176 static bool find_equiv(
4177 node_pointer n, node_pointer end, value_type const& v)
4178 {
4179 for (; n != end; n = next_node(n))
4180 if (n->value() == v)
4181 return true;
4182 return false;
4183 }
4184
4185 static std::size_t count_equal_equiv(
4186 node_pointer n, node_pointer end, value_type const& v)
4187 {
4188 std::size_t count = 0;
4189 for (; n != end; n = next_node(n))
4190 if (n->value() == v)
4191 ++count;
4192 return count;
4193 }
4194
4195 // Emplace/Insert
4196
4197 inline node_pointer add_node_equiv(
4198 node_pointer n, std::size_t key_hash, node_pointer pos)
4199 {
4200 std::size_t bucket_index = this->hash_to_bucket(key_hash);
4201 n->bucket_info_ = bucket_index;
4202
4203 if (pos) {
4204 n->reset_first_in_group();
4205 n->next_ = pos->next_;
4206 pos->next_ = n;
4207 if (n->next_) {
4208 std::size_t next_bucket = this->node_bucket(next_node(n));
4209 if (next_bucket != bucket_index) {
4210 this->get_bucket_pointer(next_bucket)->next_ = n;
4211 }
4212 }
4213 } else {
4214 n->set_first_in_group();
4215 bucket_pointer b = this->get_bucket_pointer(bucket_index);
4216
4217 if (!b->next_) {
4218 link_pointer start_node = this->get_previous_start();
4219
4220 if (start_node->next_) {
4221 this
4222 ->get_bucket_pointer(this->node_bucket(next_node(n: start_node)))
4223 ->next_ = n;
4224 }
4225
4226 b->next_ = start_node;
4227 n->next_ = start_node->next_;
4228 start_node->next_ = n;
4229 } else {
4230 n->next_ = b->next_->next_;
4231 b->next_->next_ = n;
4232 }
4233 }
4234 ++this->size_;
4235 return n;
4236 }
4237
4238 inline node_pointer add_using_hint_equiv(
4239 node_pointer n, node_pointer hint)
4240 {
4241 n->bucket_info_ = hint->bucket_info_;
4242 n->reset_first_in_group();
4243 n->next_ = hint->next_;
4244 hint->next_ = n;
4245 if (n->next_) {
4246 std::size_t next_bucket = this->node_bucket(next_node(n));
4247 if (next_bucket != this->node_bucket(n)) {
4248 this->get_bucket_pointer(next_bucket)->next_ = n;
4249 }
4250 }
4251 ++this->size_;
4252 return n;
4253 }
4254
4255 iterator emplace_equiv(node_pointer n)
4256 {
4257 node_tmp a(n, this->node_alloc());
4258 const_key_type& k = this->get_key(a.node_);
4259 std::size_t key_hash = this->hash(k);
4260 node_pointer position = this->find_node(key_hash, k);
4261 this->reserve_for_insert(this->size_ + 1);
4262 return iterator(
4263 this->add_node_equiv(a.release(), key_hash, position));
4264 }
4265
4266 iterator emplace_hint_equiv(c_iterator hint, node_pointer n)
4267 {
4268 node_tmp a(n, this->node_alloc());
4269 const_key_type& k = this->get_key(a.node_);
4270 if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) {
4271 this->reserve_for_insert(this->size_ + 1);
4272 return iterator(
4273 this->add_using_hint_equiv(a.release(), hint.node_));
4274 } else {
4275 std::size_t key_hash = this->hash(k);
4276 node_pointer position = this->find_node(key_hash, k);
4277 this->reserve_for_insert(this->size_ + 1);
4278 return iterator(
4279 this->add_node_equiv(a.release(), key_hash, position));
4280 }
4281 }
4282
4283 void emplace_no_rehash_equiv(node_pointer n)
4284 {
4285 node_tmp a(n, this->node_alloc());
4286 const_key_type& k = this->get_key(a.node_);
4287 std::size_t key_hash = this->hash(k);
4288 node_pointer position = this->find_node(key_hash, k);
4289 this->add_node_equiv(a.release(), key_hash, position);
4290 }
4291
4292 template <typename NodeType>
4293 iterator move_insert_node_type_equiv(NodeType& np)
4294 {
4295 iterator result;
4296
4297 if (np) {
4298 const_key_type& k = this->get_key(np.ptr_);
4299 std::size_t key_hash = this->hash(k);
4300 node_pointer pos = this->find_node(key_hash, k);
4301 this->reserve_for_insert(this->size_ + 1);
4302 result = iterator(this->add_node_equiv(np.ptr_, key_hash, pos));
4303 np.ptr_ = node_pointer();
4304 }
4305
4306 return result;
4307 }
4308
4309 template <typename NodeType>
4310 iterator move_insert_node_type_with_hint_equiv(
4311 c_iterator hint, NodeType& np)
4312 {
4313 iterator result;
4314
4315 if (np) {
4316 const_key_type& k = this->get_key(np.ptr_);
4317
4318 if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) {
4319 this->reserve_for_insert(this->size_ + 1);
4320 result =
4321 iterator(this->add_using_hint_equiv(np.ptr_, hint.node_));
4322 } else {
4323 std::size_t key_hash = this->hash(k);
4324 node_pointer pos = this->find_node(key_hash, k);
4325 this->reserve_for_insert(this->size_ + 1);
4326 result = iterator(this->add_node_equiv(np.ptr_, key_hash, pos));
4327 }
4328 np.ptr_ = node_pointer();
4329 }
4330
4331 return result;
4332 }
4333
4334 ////////////////////////////////////////////////////////////////////////
4335 // Insert range methods
4336
4337 // if hash function throws, or inserting > 1 element, basic exception
4338 // safety. Strong otherwise
4339 template <class I>
4340 void insert_range_equiv(I i, I j,
4341 typename boost::unordered::detail::enable_if_forward<I, void*>::type =
4342 0)
4343 {
4344 if (i == j)
4345 return;
4346
4347 std::size_t distance = static_cast<std::size_t>(std::distance(i, j));
4348 if (distance == 1) {
4349 emplace_equiv(n: boost::unordered::detail::func::construct_node(
4350 this->node_alloc(), *i));
4351 } else {
4352 // Only require basic exception safety here
4353 this->reserve_for_insert(this->size_ + distance);
4354
4355 for (; i != j; ++i) {
4356 emplace_no_rehash_equiv(
4357 n: boost::unordered::detail::func::construct_node(
4358 this->node_alloc(), *i));
4359 }
4360 }
4361 }
4362
4363 template <class I>
4364 void insert_range_equiv(I i, I j,
4365 typename boost::unordered::detail::disable_if_forward<I,
4366 void*>::type = 0)
4367 {
4368 for (; i != j; ++i) {
4369 emplace_equiv(n: boost::unordered::detail::func::construct_node(
4370 this->node_alloc(), *i));
4371 }
4372 }
4373
4374 ////////////////////////////////////////////////////////////////////////
4375 // Extract
4376
4377 inline node_pointer extract_by_iterator_equiv(c_iterator n)
4378 {
4379 node_pointer i = n.node_;
4380 BOOST_ASSERT(i);
4381 node_pointer j(next_node(n: i));
4382 std::size_t bucket_index = this->node_bucket(i);
4383
4384 link_pointer prev = this->get_previous_start(bucket_index);
4385 while (prev->next_ != i) {
4386 prev = next_node(n: prev);
4387 }
4388
4389 prev->next_ = j;
4390 if (j && i->is_first_in_group()) {
4391 j->set_first_in_group();
4392 }
4393 --this->size_;
4394 this->fix_bucket(bucket_index, prev, j);
4395 i->next_ = link_pointer();
4396
4397 return i;
4398 }
4399
4400 ////////////////////////////////////////////////////////////////////////
4401 // Erase
4402 //
4403 // no throw
4404
4405 std::size_t erase_key_equiv(const_key_type& k)
4406 {
4407 if (!this->size_)
4408 return 0;
4409
4410 std::size_t key_hash = this->hash(k);
4411 std::size_t bucket_index = this->hash_to_bucket(key_hash);
4412 link_pointer prev = this->find_previous_node(k, bucket_index);
4413 if (!prev)
4414 return 0;
4415
4416 std::size_t deleted_count = 0;
4417 node_pointer n = next_node(n: prev);
4418 do {
4419 node_pointer n2 = next_node(n);
4420 destroy_node(n);
4421 ++deleted_count;
4422 n = n2;
4423 } while (n && !n->is_first_in_group());
4424 size_ -= deleted_count;
4425 prev->next_ = n;
4426 this->fix_bucket(bucket_index, prev, n);
4427 return deleted_count;
4428 }
4429
4430 link_pointer erase_nodes_equiv(node_pointer i, node_pointer j)
4431 {
4432 std::size_t bucket_index = this->node_bucket(i);
4433
4434 link_pointer prev = this->get_previous_start(bucket_index);
4435 while (prev->next_ != i) {
4436 prev = next_node(n: prev);
4437 }
4438
4439 // Delete the nodes.
4440 // Is it inefficient to call fix_bucket for every node?
4441 bool includes_first = false;
4442 prev->next_ = j;
4443 do {
4444 includes_first = includes_first || i->is_first_in_group();
4445 node_pointer next = next_node(n: i);
4446 destroy_node(n: i);
4447 --size_;
4448 bucket_index = this->fix_bucket(bucket_index, prev, next);
4449 i = next;
4450 } while (i != j);
4451 if (j && includes_first) {
4452 j->set_first_in_group();
4453 }
4454
4455 return prev;
4456 }
4457
4458 ////////////////////////////////////////////////////////////////////////
4459 // fill_buckets
4460
4461 void copy_buckets(table const& src, false_type)
4462 {
4463 this->create_buckets(this->bucket_count_);
4464
4465 for (node_pointer n = src.begin(); n;) {
4466 std::size_t key_hash = this->hash(this->get_key(n));
4467 node_pointer group_end(next_group(n));
4468 node_pointer pos = this->add_node_equiv(
4469 boost::unordered::detail::func::construct_node(
4470 this->node_alloc(), n->value()),
4471 key_hash, node_pointer());
4472 for (n = next_node(n); n != group_end; n = next_node(n)) {
4473 this->add_node_equiv(
4474 boost::unordered::detail::func::construct_node(
4475 this->node_alloc(), n->value()),
4476 key_hash, pos);
4477 }
4478 }
4479 }
4480
4481 void assign_buckets(table const& src, false_type)
4482 {
4483 node_holder<node_allocator> holder(*this);
4484 for (node_pointer n = src.begin(); n;) {
4485 std::size_t key_hash = this->hash(this->get_key(n));
4486 node_pointer group_end(next_group(n));
4487 node_pointer pos = this->add_node_equiv(
4488 holder.copy_of(n->value()), key_hash, node_pointer());
4489 for (n = next_node(n); n != group_end; n = next_node(n)) {
4490 this->add_node_equiv(holder.copy_of(n->value()), key_hash, pos);
4491 }
4492 }
4493 }
4494
4495 void move_assign_buckets(table& src, false_type)
4496 {
4497 node_holder<node_allocator> holder(*this);
4498 for (node_pointer n = src.begin(); n;) {
4499 std::size_t key_hash = this->hash(this->get_key(n));
4500 node_pointer group_end(next_group(n));
4501 node_pointer pos = this->add_node_equiv(
4502 holder.move_copy_of(n->value()), key_hash, node_pointer());
4503 for (n = next_node(n); n != group_end; n = next_node(n)) {
4504 this->add_node_equiv(
4505 holder.move_copy_of(n->value()), key_hash, pos);
4506 }
4507 }
4508 }
4509 };
4510
4511 //////////////////////////////////////////////////////////////////////////
4512 // Clear
4513
4514 template <typename Types> inline void table<Types>::clear_impl()
4515 {
4516 if (size_) {
4517 bucket_pointer end = get_bucket_pointer(bucket_index: bucket_count_);
4518 for (bucket_pointer it = buckets_; it != end; ++it) {
4519 it->next_ = node_pointer();
4520 }
4521
4522 link_pointer prev = end->first_from_start();
4523 node_pointer n = next_node(n: prev);
4524 prev->next_ = node_pointer();
4525 size_ = 0;
4526
4527 while (n) {
4528 node_pointer next = next_node(n);
4529 destroy_node(n);
4530 n = next;
4531 }
4532 }
4533 }
4534
4535 //////////////////////////////////////////////////////////////////////////
4536 // Reserve & Rehash
4537
4538 // basic exception safety
4539 template <typename Types>
4540 inline void table<Types>::reserve_for_insert(std::size_t size)
4541 {
4542 if (!buckets_) {
4543 create_buckets(new_count: (std::max)(bucket_count_, min_buckets_for_size(size)));
4544 } else if (size > max_load_) {
4545 std::size_t num_buckets =
4546 min_buckets_for_size(size: (std::max)(a: size, b: size_ + (size_ >> 1)));
4547
4548 if (num_buckets != bucket_count_)
4549 this->rehash_impl(num_buckets);
4550 }
4551 }
4552
4553 // if hash function throws, basic exception safety
4554 // strong otherwise.
4555
4556 template <typename Types>
4557 inline void table<Types>::rehash(std::size_t min_buckets)
4558 {
4559 using namespace std;
4560
4561 if (!size_) {
4562 delete_buckets();
4563 bucket_count_ = policy::new_bucket_count(min_buckets);
4564 } else {
4565 min_buckets = policy::new_bucket_count((std::max)(a: min_buckets,
4566 b: boost::unordered::detail::double_to_size(
4567 f: floor(x: static_cast<double>(size_) / static_cast<double>(mlf_))) +
4568 1));
4569
4570 if (min_buckets != bucket_count_)
4571 this->rehash_impl(min_buckets);
4572 }
4573 }
4574
4575 template <typename Types>
4576 inline void table<Types>::rehash_impl(std::size_t num_buckets)
4577 {
4578 BOOST_ASSERT(this->buckets_);
4579
4580 this->create_buckets(num_buckets);
4581 link_pointer prev = this->get_previous_start();
4582 BOOST_TRY
4583 {
4584 while (prev->next_) {
4585 node_pointer n = next_node(n: prev);
4586 std::size_t key_hash = this->hash(this->get_key(n));
4587 std::size_t bucket_index = this->hash_to_bucket(key_hash);
4588
4589 n->bucket_info_ = bucket_index;
4590 n->set_first_in_group();
4591
4592 // Iterator through the rest of the group of equal nodes,
4593 // setting the bucket.
4594 for (;;) {
4595 node_pointer next = next_node(n);
4596 if (!next || next->is_first_in_group()) {
4597 break;
4598 }
4599 n = next;
4600 n->bucket_info_ = bucket_index;
4601 n->reset_first_in_group();
4602 }
4603
4604 // n is now the last node in the group
4605 bucket_pointer b = this->get_bucket_pointer(bucket_index);
4606 if (!b->next_) {
4607 b->next_ = prev;
4608 prev = n;
4609 } else {
4610 link_pointer next = n->next_;
4611 n->next_ = b->next_->next_;
4612 b->next_->next_ = prev->next_;
4613 prev->next_ = next;
4614 }
4615 }
4616 }
4617 BOOST_CATCH(...)
4618 {
4619 node_pointer n = next_node(n: prev);
4620 prev->next_ = node_pointer();
4621 while (n) {
4622 node_pointer next = next_node(n);
4623 destroy_node(n);
4624 --size_;
4625 n = next;
4626 }
4627 BOOST_RETHROW
4628 }
4629 BOOST_CATCH_END
4630 }
4631
4632#if defined(BOOST_MSVC)
4633#pragma warning(pop)
4634#endif
4635
4636 ////////////////////////////////////////////////////////////////////////
4637 // key extractors
4638 //
4639 // no throw
4640 //
4641 // 'extract_key' is called with the emplace parameters to return a
4642 // key if available or 'no_key' is one isn't and will need to be
4643 // constructed. This could be done by overloading the emplace
4644 // implementation
4645 // for the different cases, but that's a bit tricky on compilers without
4646 // variadic templates.
4647
4648 template <typename Key, typename T> struct is_key
4649 {
4650 template <typename T2> static choice1::type test(T2 const&);
4651 static choice2::type test(Key const&);
4652
4653 enum
4654 {
4655 value = sizeof(test(boost::unordered::detail::make<T>())) ==
4656 sizeof(choice2::type)
4657 };
4658
4659 typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE
4660 then<Key const&, no_key>::type type;
4661 };
4662
4663 template <class ValueType> struct set_extractor
4664 {
4665 typedef ValueType value_type;
4666 typedef ValueType key_type;
4667
4668 static key_type const& extract(value_type const& v) { return v; }
4669
4670 static key_type const& extract(BOOST_UNORDERED_RV_REF(value_type) v)
4671 {
4672 return v;
4673 }
4674
4675 static no_key extract() { return no_key(); }
4676
4677 template <class Arg> static no_key extract(Arg const&)
4678 {
4679 return no_key();
4680 }
4681
4682#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
4683 template <class Arg1, class Arg2, class... Args>
4684 static no_key extract(Arg1 const&, Arg2 const&, Args const&...)
4685 {
4686 return no_key();
4687 }
4688#else
4689 template <class Arg1, class Arg2>
4690 static no_key extract(Arg1 const&, Arg2 const&)
4691 {
4692 return no_key();
4693 }
4694#endif
4695 };
4696
4697 template <class ValueType> struct map_extractor
4698 {
4699 typedef ValueType value_type;
4700 typedef typename boost::remove_const<typename boost::unordered::detail::
4701 pair_traits<ValueType>::first_type>::type key_type;
4702
4703 static key_type const& extract(value_type const& v) { return v.first; }
4704
4705 template <class Second>
4706 static key_type const& extract(std::pair<key_type, Second> const& v)
4707 {
4708 return v.first;
4709 }
4710
4711 template <class Second>
4712 static key_type const& extract(
4713 std::pair<key_type const, Second> const& v)
4714 {
4715 return v.first;
4716 }
4717
4718#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
4719 template <class Second>
4720 static key_type const& extract(
4721 boost::rv<std::pair<key_type, Second> > const& v)
4722 {
4723 return v.first;
4724 }
4725
4726 template <class Second>
4727 static key_type const& extract(
4728 boost::rv<std::pair<key_type const, Second> > const& v)
4729 {
4730 return v.first;
4731 }
4732#endif
4733
4734 template <class Arg1>
4735 static key_type const& extract(key_type const& k, Arg1 const&)
4736 {
4737 return k;
4738 }
4739
4740 static no_key extract() { return no_key(); }
4741
4742 template <class Arg> static no_key extract(Arg const&)
4743 {
4744 return no_key();
4745 }
4746
4747 template <class Arg1, class Arg2>
4748 static no_key extract(Arg1 const&, Arg2 const&)
4749 {
4750 return no_key();
4751 }
4752
4753#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
4754 template <class Arg1, class Arg2, class Arg3, class... Args>
4755 static no_key extract(
4756 Arg1 const&, Arg2 const&, Arg3 const&, Args const&...)
4757 {
4758 return no_key();
4759 }
4760#endif
4761
4762#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
4763
4764#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
4765 template <typename T2> \
4766 static no_key extract(boost::unordered::piecewise_construct_t, \
4767 namespace_ tuple<> const&, T2 const&) \
4768 { \
4769 return no_key(); \
4770 } \
4771 \
4772 template <typename T, typename T2> \
4773 static typename is_key<key_type, T>::type extract( \
4774 boost::unordered::piecewise_construct_t, namespace_ tuple<T> const& k, \
4775 T2 const&) \
4776 { \
4777 return typename is_key<key_type, T>::type(namespace_ get<0>(k)); \
4778 }
4779
4780#else
4781
4782#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
4783 static no_key extract( \
4784 boost::unordered::piecewise_construct_t, namespace_ tuple<> const&) \
4785 { \
4786 return no_key(); \
4787 } \
4788 \
4789 template <typename T> \
4790 static typename is_key<key_type, T>::type extract( \
4791 boost::unordered::piecewise_construct_t, namespace_ tuple<T> const& k) \
4792 { \
4793 return typename is_key<key_type, T>::type(namespace_ get<0>(k)); \
4794 }
4795
4796#endif
4797
4798 BOOST_UNORDERED_KEY_FROM_TUPLE(boost::)
4799
4800#if BOOST_UNORDERED_TUPLE_ARGS
4801 BOOST_UNORDERED_KEY_FROM_TUPLE(std::)
4802#endif
4803
4804#undef BOOST_UNORDERED_KEY_FROM_TUPLE
4805 };
4806
4807 ////////////////////////////////////////////////////////////////////////
4808 // Unique nodes
4809
4810 template <typename A, typename T>
4811 struct node : boost::unordered::detail::value_base<T>
4812 {
4813 typedef
4814 typename ::boost::unordered::detail::rebind_wrap<A, node<A, T> >::type
4815 allocator;
4816 typedef typename ::boost::unordered::detail::allocator_traits<
4817 allocator>::pointer node_pointer;
4818 typedef node_pointer link_pointer;
4819 typedef typename ::boost::unordered::detail::rebind_wrap<A,
4820 bucket<node_pointer> >::type bucket_allocator;
4821 typedef typename ::boost::unordered::detail::allocator_traits<
4822 bucket_allocator>::pointer bucket_pointer;
4823
4824 link_pointer next_;
4825 std::size_t bucket_info_;
4826
4827 node() : next_(), bucket_info_(0) {}
4828
4829 std::size_t get_bucket() const
4830 {
4831 return bucket_info_ & ((std::size_t)-1 >> 1);
4832 }
4833
4834 std::size_t is_first_in_group() const
4835 {
4836 return !(bucket_info_ & ~((std::size_t)-1 >> 1));
4837 }
4838
4839 void set_first_in_group()
4840 {
4841 bucket_info_ = bucket_info_ & ((std::size_t)-1 >> 1);
4842 }
4843
4844 void reset_first_in_group()
4845 {
4846 bucket_info_ = bucket_info_ | ~((std::size_t)-1 >> 1);
4847 }
4848
4849 private:
4850 node& operator=(node const&);
4851 };
4852
4853 template <typename T>
4854 struct ptr_node : boost::unordered::detail::ptr_bucket
4855 {
4856 typedef T value_type;
4857 typedef boost::unordered::detail::ptr_bucket bucket_base;
4858 typedef ptr_node<T>* node_pointer;
4859 typedef ptr_bucket* link_pointer;
4860 typedef ptr_bucket* bucket_pointer;
4861
4862 std::size_t bucket_info_;
4863 boost::unordered::detail::value_base<T> value_base_;
4864
4865 ptr_node() : bucket_base(), bucket_info_(0) {}
4866
4867 void* address() { return value_base_.address(); }
4868 value_type& value() { return value_base_.value(); }
4869 value_type* value_ptr() { return value_base_.value_ptr(); }
4870
4871 std::size_t get_bucket() const
4872 {
4873 return bucket_info_ & ((std::size_t)-1 >> 1);
4874 }
4875
4876 std::size_t is_first_in_group() const
4877 {
4878 return !(bucket_info_ & ~((std::size_t)-1 >> 1));
4879 }
4880
4881 void set_first_in_group()
4882 {
4883 bucket_info_ = bucket_info_ & ((std::size_t)-1 >> 1);
4884 }
4885
4886 void reset_first_in_group()
4887 {
4888 bucket_info_ = bucket_info_ | ~((std::size_t)-1 >> 1);
4889 }
4890
4891 private:
4892 ptr_node& operator=(ptr_node const&);
4893 };
4894
4895 // If the allocator uses raw pointers use ptr_node
4896 // Otherwise use node.
4897
4898 template <typename A, typename T, typename NodePtr, typename BucketPtr>
4899 struct pick_node2
4900 {
4901 typedef boost::unordered::detail::node<A, T> node;
4902
4903 typedef typename boost::unordered::detail::allocator_traits<
4904 typename boost::unordered::detail::rebind_wrap<A,
4905 node>::type>::pointer node_pointer;
4906
4907 typedef boost::unordered::detail::bucket<node_pointer> bucket;
4908 typedef node_pointer link_pointer;
4909 };
4910
4911 template <typename A, typename T>
4912 struct pick_node2<A, T, boost::unordered::detail::ptr_node<T>*,
4913 boost::unordered::detail::ptr_bucket*>
4914 {
4915 typedef boost::unordered::detail::ptr_node<T> node;
4916 typedef boost::unordered::detail::ptr_bucket bucket;
4917 typedef bucket* link_pointer;
4918 };
4919
4920 template <typename A, typename T> struct pick_node
4921 {
4922 typedef typename boost::remove_const<T>::type nonconst;
4923
4924 typedef boost::unordered::detail::allocator_traits<
4925 typename boost::unordered::detail::rebind_wrap<A,
4926 boost::unordered::detail::ptr_node<nonconst> >::type>
4927 tentative_node_traits;
4928
4929 typedef boost::unordered::detail::allocator_traits<
4930 typename boost::unordered::detail::rebind_wrap<A,
4931 boost::unordered::detail::ptr_bucket>::type>
4932 tentative_bucket_traits;
4933
4934 typedef pick_node2<A, nonconst, typename tentative_node_traits::pointer,
4935 typename tentative_bucket_traits::pointer>
4936 pick;
4937
4938 typedef typename pick::node node;
4939 typedef typename pick::bucket bucket;
4940 typedef typename pick::link_pointer link_pointer;
4941 };
4942 }
4943 }
4944}
4945
4946#undef BOOST_UNORDERED_EMPLACE_TEMPLATE
4947#undef BOOST_UNORDERED_EMPLACE_ARGS
4948#undef BOOST_UNORDERED_EMPLACE_FORWARD
4949#undef BOOST_UNORDERED_CALL_CONSTRUCT1
4950#undef BOOST_UNORDERED_CALL_DESTROY
4951
4952#endif
4953

source code of include/boost/unordered/detail/implementation.hpp