In common.h, define func_lib for function objects. In configure.ac, define HAVE_STD_FUNCTION and HAVE_BOOST_FUNCTION. Include function headers in ndnboost.
diff --git a/ndnboost/unordered/detail/allocate.hpp b/ndnboost/unordered/detail/allocate.hpp
new file mode 100644
index 0000000..4ad6724
--- /dev/null
+++ b/ndnboost/unordered/detail/allocate.hpp
@@ -0,0 +1,1120 @@
+
+// Copyright 2005-2011 Daniel James.
+// Copyright 2009 Pablo Halpern.
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/libs/unordered for documentation
+
+#ifndef BOOST_UNORDERED_ALLOCATE_HPP
+#define BOOST_UNORDERED_ALLOCATE_HPP
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1020)
+# pragma once
+#endif
+
+#include <ndnboost/unordered/detail/fwd.hpp>
+#include <ndnboost/move/move.hpp>
+#include <ndnboost/preprocessor/cat.hpp>
+#include <ndnboost/preprocessor/inc.hpp>
+#include <ndnboost/preprocessor/dec.hpp>
+#include <ndnboost/preprocessor/repetition/enum.hpp>
+#include <ndnboost/preprocessor/repetition/enum_params.hpp>
+#include <ndnboost/preprocessor/repetition/enum_binary_params.hpp>
+#include <ndnboost/preprocessor/repetition/repeat_from_to.hpp>
+#include <ndnboost/type_traits/is_class.hpp>
+#include <ndnboost/type_traits/add_lvalue_reference.hpp>
+#include <ndnboost/tuple/tuple.hpp>
+#include <ndnboost/utility/enable_if.hpp>
+#include <ndnboost/utility/addressof.hpp>
+#include <ndnboost/detail/select_type.hpp>
+#include <ndnboost/assert.hpp>
+#include <utility>
+
+#if !defined(BOOST_NO_CXX11_HDR_TUPLE)
+#include <tuple>
+#endif
+
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#pragma warning(disable:4512) // assignment operator could not be generated.
+#pragma warning(disable:4345) // behavior change: an object of POD type
+ // constructed with an initializer of the form ()
+ // will be default-initialized.
+#endif
+
+#define BOOST_UNORDERED_EMPLACE_LIMIT 10
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Bits and pieces for implementing traits
+
+ template <typename T> typename ndnboost::add_lvalue_reference<T>::type make();
+ struct choice9 { typedef char (&type)[9]; };
+ struct choice8 : choice9 { typedef char (&type)[8]; };
+ struct choice7 : choice8 { typedef char (&type)[7]; };
+ struct choice6 : choice7 { typedef char (&type)[6]; };
+ struct choice5 : choice6 { typedef char (&type)[5]; };
+ struct choice4 : choice5 { typedef char (&type)[4]; };
+ struct choice3 : choice4 { typedef char (&type)[3]; };
+ struct choice2 : choice3 { typedef char (&type)[2]; };
+ struct choice1 : choice2 { typedef char (&type)[1]; };
+ choice1 choose();
+
+ typedef choice1::type yes_type;
+ typedef choice2::type no_type;
+
+ struct private_type
+ {
+ private_type const &operator,(int) const;
+ };
+
+ template <typename T>
+ no_type is_private_type(T const&);
+ yes_type is_private_type(private_type const&);
+
+ struct convert_from_anything {
+ template <typename T>
+ convert_from_anything(T const&);
+ };
+
+ ////////////////////////////////////////////////////////////////////////////
+ // emplace_args
+ //
+ // Either forwarding variadic arguments, or storing the arguments in
+ // emplace_args##n
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args
+#define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args
+#define BOOST_UNORDERED_EMPLACE_FORWARD ndnboost::forward<Args>(args)...
+
+#define BOOST_UNORDERED_EMPLACE_ARGS1(a0) a0
+#define BOOST_UNORDERED_EMPLACE_ARGS2(a0, a1) a0, a1
+#define BOOST_UNORDERED_EMPLACE_ARGS3(a0, a1, a2) a0, a1, a2
+
+#else
+
+#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args
+#define BOOST_UNORDERED_EMPLACE_ARGS Args const& args
+#define BOOST_UNORDERED_EMPLACE_FORWARD args
+
+#define BOOST_UNORDERED_FWD_PARAM(z, n, a) \
+ BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(a, n)
+
+#define BOOST_UNORDERED_CALL_FORWARD(z, i, a) \
+ ndnboost::forward<BOOST_PP_CAT(A,i)>(BOOST_PP_CAT(a,i))
+
+#define BOOST_UNORDERED_EARGS(z, n, _) \
+ template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
+ struct BOOST_PP_CAT(emplace_args, n) \
+ { \
+ BOOST_PP_REPEAT_##z(n, BOOST_UNORDERED_EARGS_MEMBER, _) \
+ BOOST_PP_CAT(emplace_args, n) ( \
+ BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, b) \
+ ) : BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_EARGS_INIT, _) \
+ {} \
+ \
+ }; \
+ \
+ template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
+ inline BOOST_PP_CAT(emplace_args, n) < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, A) \
+ > create_emplace_args( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, b) \
+ ) \
+ { \
+ BOOST_PP_CAT(emplace_args, n) < \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, A) \
+ > e(BOOST_PP_ENUM_PARAMS_Z(z, n, b)); \
+ return e; \
+ }
+
+#define BOOST_UNORDERED_EMPLACE_ARGS1 create_emplace_args
+#define BOOST_UNORDERED_EMPLACE_ARGS2 create_emplace_args
+#define BOOST_UNORDERED_EMPLACE_ARGS3 create_emplace_args
+
+#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+
+#define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
+ typedef BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(Arg, n); \
+ BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
+
+#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \
+ BOOST_PP_CAT(a, n)( \
+ ndnboost::forward<BOOST_PP_CAT(A,n)>(BOOST_PP_CAT(b, n)))
+
+#else
+
+#define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
+ typedef typename ndnboost::add_lvalue_reference<BOOST_PP_CAT(A, n)>::type \
+ BOOST_PP_CAT(Arg, n); \
+ BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
+
+#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \
+ BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n))
+
+#endif
+
+BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, BOOST_UNORDERED_EARGS,
+ _)
+
+#undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS
+#undef BOOST_UNORDERED_EARGS_MEMBER
+#undef BOOST_UNORDERED_EARGS_INIT
+
+#endif
+
+}}}
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// Pick which version of allocator_traits to use
+//
+// 0 = Own partial implementation
+// 1 = std::allocator_traits
+// 2 = ndnboost::container::allocator_traits
+
+#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
+# if defined(__GXX_EXPERIMENTAL_CXX0X__) && \
+ (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7))
+# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0
+# elif defined(BOOST_MSVC)
+# if BOOST_MSVC < 1400
+ // Use container's allocator_traits for older versions of Visual
+ // C++ as I don't test with them.
+# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 2
+# endif
+# endif
+#endif
+
+#if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
+# define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0
+#endif
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// Some utilities for implementing allocator_traits, but useful elsewhere so
+// they're always defined.
+
+#if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
+# include <type_traits>
+#endif
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Integral_constrant, true_type, false_type
+ //
+ // Uses the standard versions if available.
+
+#if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
+
+ using std::integral_constant;
+ using std::true_type;
+ using std::false_type;
+
+#else
+
+ template <typename T, T Value>
+ struct integral_constant { enum { value = Value }; };
+
+ typedef ndnboost::unordered::detail::integral_constant<bool, true> true_type;
+ typedef ndnboost::unordered::detail::integral_constant<bool, false> false_type;
+
+#endif
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Explicitly call a destructor
+
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#pragma warning(disable:4100) // unreferenced formal parameter
+#endif
+
+ template <class T>
+ inline void destroy(T* x) {
+ x->~T();
+ }
+
+#if defined(BOOST_MSVC)
+#pragma warning(pop)
+#endif
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Expression test mechanism
+ //
+ // When SFINAE expressions are available, define
+ // BOOST_UNORDERED_HAS_FUNCTION which can check if a function call is
+ // supported by a class, otherwise define BOOST_UNORDERED_HAS_MEMBER which
+ // can detect if a class has the specified member, but not that it has the
+ // correct type, this is good enough for a passable impression of
+ // allocator_traits.
+
+#if !defined(BOOST_NO_SFINAE_EXPR)
+
+ template <typename T, unsigned int> struct expr_test;
+ template <typename T> struct expr_test<T, sizeof(char)> : T {};
+ template <typename U> static char for_expr_test(U const&);
+
+# define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \
+ template <typename U> \
+ static typename ndnboost::unordered::detail::expr_test< \
+ BOOST_PP_CAT(choice, result), \
+ sizeof(ndnboost::unordered::detail::for_expr_test(( \
+ (expression), \
+ 0)))>::type test( \
+ BOOST_PP_CAT(choice, count))
+
+# define BOOST_UNORDERED_DEFAULT_EXPRESSION(count, result) \
+ template <typename U> \
+ static BOOST_PP_CAT(choice, result)::type test( \
+ BOOST_PP_CAT(choice, count))
+
+# define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _) \
+ struct BOOST_PP_CAT(has_, name) \
+ { \
+ BOOST_UNORDERED_CHECK_EXPRESSION(1, 1, \
+ ndnboost::unordered::detail::make< thing >().name args); \
+ BOOST_UNORDERED_DEFAULT_EXPRESSION(2, 2); \
+ \
+ enum { value = sizeof(test<T>(choose())) == sizeof(choice1::type) };\
+ }
+
+#else
+
+ template <typename T> struct identity { typedef T type; };
+
+# define BOOST_UNORDERED_CHECK_MEMBER(count, result, name, member) \
+ \
+ typedef typename ndnboost::unordered::detail::identity<member>::type \
+ BOOST_PP_CAT(check, count); \
+ \
+ template <BOOST_PP_CAT(check, count) e> \
+ struct BOOST_PP_CAT(test, count) { \
+ typedef BOOST_PP_CAT(choice, result) type; \
+ }; \
+ \
+ template <class U> static typename \
+ BOOST_PP_CAT(test, count)<&U::name>::type \
+ test(BOOST_PP_CAT(choice, count))
+
+# define BOOST_UNORDERED_DEFAULT_MEMBER(count, result) \
+ template <class U> static BOOST_PP_CAT(choice, result)::type \
+ test(BOOST_PP_CAT(choice, count))
+
+# define BOOST_UNORDERED_HAS_MEMBER(name) \
+ struct BOOST_PP_CAT(has_, name) \
+ { \
+ struct impl { \
+ struct base_mixin { int name; }; \
+ struct base : public T, public base_mixin {}; \
+ \
+ BOOST_UNORDERED_CHECK_MEMBER(1, 1, name, int base_mixin::*); \
+ BOOST_UNORDERED_DEFAULT_MEMBER(2, 2); \
+ \
+ enum { value = sizeof(choice2::type) == \
+ sizeof(test<base>(choose())) \
+ }; \
+ }; \
+ \
+ enum { value = impl::value }; \
+ }
+
+#endif
+
+}}}
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// Allocator traits
+//
+// First our implementation, then later light wrappers around the alternatives
+
+#if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0
+
+# include <ndnboost/limits.hpp>
+# include <ndnboost/utility/enable_if.hpp>
+# include <ndnboost/pointer_to_other.hpp>
+# if defined(BOOST_NO_SFINAE_EXPR)
+# include <ndnboost/type_traits/is_same.hpp>
+# endif
+
+# if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && \
+ !defined(BOOST_NO_SFINAE_EXPR)
+# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1
+# else
+# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0
+# endif
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ // TODO: Does this match std::allocator_traits<Alloc>::rebind_alloc<T>?
+ template <typename Alloc, typename T>
+ struct rebind_wrap
+ {
+ typedef typename Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other type;
+ };
+
+# if defined(BOOST_MSVC) && BOOST_MSVC <= 1400
+
+# define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
+ template <typename Tp, typename Default> \
+ struct default_type_ ## tname { \
+ \
+ template <typename X> \
+ static choice1::type test(choice1, typename X::tname* = 0); \
+ \
+ template <typename X> \
+ static choice2::type test(choice2, void* = 0); \
+ \
+ struct DefaultWrap { typedef Default tname; }; \
+ \
+ enum { value = (1 == sizeof(test<Tp>(choose()))) }; \
+ \
+ typedef typename ndnboost::detail::if_true<value>:: \
+ BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap> \
+ ::type::tname type; \
+ }
+
+# else
+
+ template <typename T, typename T2>
+ struct sfinae : T2 {};
+
+# define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
+ template <typename Tp, typename Default> \
+ struct default_type_ ## tname { \
+ \
+ template <typename X> \
+ static typename ndnboost::unordered::detail::sfinae< \
+ typename X::tname, choice1>::type \
+ test(choice1); \
+ \
+ template <typename X> \
+ static choice2::type test(choice2); \
+ \
+ struct DefaultWrap { typedef Default tname; }; \
+ \
+ enum { value = (1 == sizeof(test<Tp>(choose()))) }; \
+ \
+ typedef typename ndnboost::detail::if_true<value>:: \
+ BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap> \
+ ::type::tname type; \
+ }
+
+# endif
+
+# define BOOST_UNORDERED_DEFAULT_TYPE(T,tname, arg) \
+ typename default_type_ ## tname<T, arg>::type
+
+ BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(pointer);
+ BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_pointer);
+ BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(void_pointer);
+ BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_void_pointer);
+ BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(difference_type);
+ BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(size_type);
+ BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_copy_assignment);
+ BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_move_assignment);
+ BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_swap);
+
+# if !defined(BOOST_NO_SFINAE_EXPR)
+
+ template <typename T>
+ BOOST_UNORDERED_HAS_FUNCTION(
+ select_on_container_copy_construction, U const, (), 0
+ );
+
+ template <typename T>
+ BOOST_UNORDERED_HAS_FUNCTION(
+ max_size, U const, (), 0
+ );
+
+# if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ template <typename T, typename ValueType, typename... Args>
+ BOOST_UNORDERED_HAS_FUNCTION(
+ construct, U, (
+ ndnboost::unordered::detail::make<ValueType*>(),
+ ndnboost::unordered::detail::make<Args const>()...), 2
+ );
+
+# else
+
+ template <typename T, typename ValueType>
+ BOOST_UNORDERED_HAS_FUNCTION(
+ construct, U, (
+ ndnboost::unordered::detail::make<ValueType*>(),
+ ndnboost::unordered::detail::make<ValueType const>()), 2
+ );
+
+# endif
+
+ template <typename T, typename ValueType>
+ BOOST_UNORDERED_HAS_FUNCTION(
+ destroy, U, (ndnboost::unordered::detail::make<ValueType*>()), 1
+ );
+
+# else
+
+ template <typename T>
+ BOOST_UNORDERED_HAS_MEMBER(select_on_container_copy_construction);
+
+ template <typename T>
+ BOOST_UNORDERED_HAS_MEMBER(max_size);
+
+ template <typename T, typename ValueType>
+ BOOST_UNORDERED_HAS_MEMBER(construct);
+
+ template <typename T, typename ValueType>
+ BOOST_UNORDERED_HAS_MEMBER(destroy);
+
+# endif
+
+ template <typename Alloc>
+ inline Alloc call_select_on_container_copy_construction(const Alloc& rhs,
+ typename ndnboost::enable_if_c<
+ ndnboost::unordered::detail::
+ has_select_on_container_copy_construction<Alloc>::value, void*
+ >::type = 0)
+ {
+ return rhs.select_on_container_copy_construction();
+ }
+
+ template <typename Alloc>
+ inline Alloc call_select_on_container_copy_construction(const Alloc& rhs,
+ typename ndnboost::disable_if_c<
+ ndnboost::unordered::detail::
+ has_select_on_container_copy_construction<Alloc>::value, void*
+ >::type = 0)
+ {
+ return rhs;
+ }
+
+ template <typename SizeType, typename Alloc>
+ inline SizeType call_max_size(const Alloc& a,
+ typename ndnboost::enable_if_c<
+ ndnboost::unordered::detail::has_max_size<Alloc>::value, void*
+ >::type = 0)
+ {
+ return a.max_size();
+ }
+
+ template <typename SizeType, typename Alloc>
+ inline SizeType call_max_size(const Alloc&, typename ndnboost::disable_if_c<
+ ndnboost::unordered::detail::has_max_size<Alloc>::value, void*
+ >::type = 0)
+ {
+ return (std::numeric_limits<SizeType>::max)();
+ }
+
+ template <typename Alloc>
+ struct allocator_traits
+ {
+ typedef Alloc allocator_type;
+ typedef typename Alloc::value_type value_type;
+
+ typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, pointer, value_type*)
+ pointer;
+
+ template <typename T>
+ struct pointer_to_other : ndnboost::pointer_to_other<pointer, T> {};
+
+ typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_pointer,
+ typename pointer_to_other<const value_type>::type)
+ const_pointer;
+
+ //typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, void_pointer,
+ // typename pointer_to_other<void>::type)
+ // void_pointer;
+ //
+ //typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_void_pointer,
+ // typename pointer_to_other<const void>::type)
+ // const_void_pointer;
+
+ typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, difference_type,
+ std::ptrdiff_t) difference_type;
+
+ typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, size_type, std::size_t)
+ size_type;
+
+ // TODO: rebind_alloc and rebind_traits
+
+ static pointer allocate(Alloc& a, size_type n)
+ { return a.allocate(n); }
+
+ // I never use this, so I'll just comment it out for now.
+ //
+ //static pointer allocate(Alloc& a, size_type n,
+ // const_void_pointer hint)
+ // { return DEFAULT_FUNC(allocate, pointer)(a, n, hint); }
+
+ static void deallocate(Alloc& a, pointer p, size_type n)
+ { a.deallocate(p, n); }
+
+ public:
+
+# if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
+
+ template <typename T, typename... Args>
+ static typename ndnboost::enable_if_c<
+ ndnboost::unordered::detail::has_construct<Alloc, T, Args...>
+ ::value>::type
+ construct(Alloc& a, T* p, BOOST_FWD_REF(Args)... x)
+ {
+ a.construct(p, ndnboost::forward<Args>(x)...);
+ }
+
+ template <typename T, typename... Args>
+ static typename ndnboost::disable_if_c<
+ ndnboost::unordered::detail::has_construct<Alloc, T, Args...>
+ ::value>::type
+ construct(Alloc&, T* p, BOOST_FWD_REF(Args)... x)
+ {
+ new ((void*) p) T(ndnboost::forward<Args>(x)...);
+ }
+
+ template <typename T>
+ static typename ndnboost::enable_if_c<
+ ndnboost::unordered::detail::has_destroy<Alloc, T>::value>::type
+ destroy(Alloc& a, T* p)
+ {
+ a.destroy(p);
+ }
+
+ template <typename T>
+ static typename ndnboost::disable_if_c<
+ ndnboost::unordered::detail::has_destroy<Alloc, T>::value>::type
+ destroy(Alloc&, T* p)
+ {
+ ndnboost::unordered::detail::destroy(p);
+ }
+
+# elif !defined(BOOST_NO_SFINAE_EXPR)
+
+ template <typename T>
+ static typename ndnboost::enable_if_c<
+ ndnboost::unordered::detail::has_construct<Alloc, T>::value>::type
+ construct(Alloc& a, T* p, T const& x)
+ {
+ a.construct(p, x);
+ }
+
+ template <typename T>
+ static typename ndnboost::disable_if_c<
+ ndnboost::unordered::detail::has_construct<Alloc, T>::value>::type
+ construct(Alloc&, T* p, T const& x)
+ {
+ new ((void*) p) T(x);
+ }
+
+ template <typename T>
+ static typename ndnboost::enable_if_c<
+ ndnboost::unordered::detail::has_destroy<Alloc, T>::value>::type
+ destroy(Alloc& a, T* p)
+ {
+ a.destroy(p);
+ }
+
+ template <typename T>
+ static typename ndnboost::disable_if_c<
+ ndnboost::unordered::detail::has_destroy<Alloc, T>::value>::type
+ destroy(Alloc&, T* p)
+ {
+ ndnboost::unordered::detail::destroy(p);
+ }
+
+# else
+
+ // If we don't have SFINAE expressions, only call construct for the
+ // copy constructor for the allocator's value_type - as that's
+ // the only construct method that old fashioned allocators support.
+
+ template <typename T>
+ static void construct(Alloc& a, T* p, T const& x,
+ typename ndnboost::enable_if_c<
+ ndnboost::unordered::detail::has_construct<Alloc, T>::value &&
+ ndnboost::is_same<T, value_type>::value,
+ void*>::type = 0)
+ {
+ a.construct(p, x);
+ }
+
+ template <typename T>
+ static void construct(Alloc&, T* p, T const& x,
+ typename ndnboost::disable_if_c<
+ ndnboost::unordered::detail::has_construct<Alloc, T>::value &&
+ ndnboost::is_same<T, value_type>::value,
+ void*>::type = 0)
+ {
+ new ((void*) p) T(x);
+ }
+
+ template <typename T>
+ static void destroy(Alloc& a, T* p,
+ typename ndnboost::enable_if_c<
+ ndnboost::unordered::detail::has_destroy<Alloc, T>::value &&
+ ndnboost::is_same<T, value_type>::value,
+ void*>::type = 0)
+ {
+ a.destroy(p);
+ }
+
+ template <typename T>
+ static void destroy(Alloc&, T* p,
+ typename ndnboost::disable_if_c<
+ ndnboost::unordered::detail::has_destroy<Alloc, T>::value &&
+ ndnboost::is_same<T, value_type>::value,
+ void*>::type = 0)
+ {
+ ndnboost::unordered::detail::destroy(p);
+ }
+
+# endif
+
+ static size_type max_size(const Alloc& a)
+ {
+ return ndnboost::unordered::detail::call_max_size<size_type>(a);
+ }
+
+ // Allocator propagation on construction
+
+ static Alloc select_on_container_copy_construction(Alloc const& rhs)
+ {
+ return ndnboost::unordered::detail::
+ call_select_on_container_copy_construction(rhs);
+ }
+
+ // Allocator propagation on assignment and swap.
+ // Return true if lhs is modified.
+ typedef BOOST_UNORDERED_DEFAULT_TYPE(
+ Alloc, propagate_on_container_copy_assignment, false_type)
+ propagate_on_container_copy_assignment;
+ typedef BOOST_UNORDERED_DEFAULT_TYPE(
+ Alloc,propagate_on_container_move_assignment, false_type)
+ propagate_on_container_move_assignment;
+ typedef BOOST_UNORDERED_DEFAULT_TYPE(
+ Alloc,propagate_on_container_swap,false_type)
+ propagate_on_container_swap;
+ };
+}}}
+
+# undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT
+# undef BOOST_UNORDERED_DEFAULT_TYPE
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// std::allocator_traits
+
+#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1
+
+# include <memory>
+
+# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ template <typename Alloc>
+ struct allocator_traits : std::allocator_traits<Alloc> {};
+
+ template <typename Alloc, typename T>
+ struct rebind_wrap
+ {
+ typedef typename std::allocator_traits<Alloc>::
+ template rebind_alloc<T> type;
+ };
+}}}
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// ndnboost::container::allocator_traits
+
+#elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2
+
+# include <ndnboost/container/allocator_traits.hpp>
+
+# define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ template <typename Alloc>
+ struct allocator_traits :
+ ndnboost::container::allocator_traits<Alloc> {};
+
+ template <typename Alloc, typename T>
+ struct rebind_wrap :
+ ndnboost::container::allocator_traits<Alloc>::
+ template portable_rebind_alloc<T>
+ {};
+
+}}}
+
+#else
+
+#error "Invalid BOOST_UNORDERED_USE_ALLOCATOR_TRAITS value."
+
+#endif
+
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ // call_construct
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+# if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
+
+ template <typename Alloc, typename T, typename... Args>
+ inline void call_construct(Alloc& alloc, T* address,
+ BOOST_FWD_REF(Args)... args)
+ {
+ ndnboost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
+ address, ndnboost::forward<Args>(args)...);
+ }
+
+ template <typename Alloc, typename T>
+ inline void destroy_value_impl(Alloc& alloc, T* x) {
+ ndnboost::unordered::detail::allocator_traits<Alloc>::destroy(alloc, x);
+ }
+
+
+# else
+
+ template <typename Alloc, typename T, typename... Args>
+ inline void call_construct(Alloc&, T* address,
+ BOOST_FWD_REF(Args)... args)
+ {
+ new((void*) address) T(ndnboost::forward<Args>(args)...);
+ }
+
+ template <typename Alloc, typename T>
+ inline void destroy_value_impl(Alloc&, T* x) {
+ ndnboost::unordered::detail::destroy(x);
+ }
+
+
+# endif
+
+#else
+
+ template <typename Alloc, typename T>
+ inline void destroy_value_impl(Alloc&, T* x) {
+ ndnboost::unordered::detail::destroy(x);
+ }
+
+#endif
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Construct from tuple
+ //
+ // Used for piecewise construction.
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \
+ template<typename Alloc, typename T> \
+ void construct_from_tuple(Alloc& alloc, T* ptr, namespace_ tuple<>) \
+ { \
+ ndnboost::unordered::detail::call_construct(alloc, ptr); \
+ } \
+ \
+ BOOST_PP_REPEAT_FROM_TO(1, n, \
+ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_)
+
+# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \
+ template<typename Alloc, typename T, \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
+ void construct_from_tuple(Alloc& alloc, T* ptr, \
+ namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
+ { \
+ ndnboost::unordered::detail::call_construct(alloc, ptr, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \
+ ); \
+ }
+
+# define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \
+ namespace_ get<n>(x)
+
+#elif !defined(__SUNPRO_CC)
+
+# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \
+ template<typename Alloc, typename T> \
+ void construct_from_tuple(Alloc&, T* ptr, namespace_ tuple<>) \
+ { \
+ new ((void*) ptr) T(); \
+ } \
+ \
+ BOOST_PP_REPEAT_FROM_TO(1, n, \
+ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_)
+
+# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \
+ template<typename Alloc, typename T, \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
+ void construct_from_tuple(Alloc&, T* ptr, \
+ namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
+ { \
+ new ((void*) ptr) T( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \
+ ); \
+ }
+
+# define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \
+ namespace_ get<n>(x)
+
+#else
+
+ template <int N> struct length {};
+
+# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_) \
+ template<typename Alloc, typename T> \
+ void construct_from_tuple_impl( \
+ ndnboost::unordered::detail::length<0>, Alloc&, T* ptr, \
+ namespace_ tuple<>) \
+ { \
+ new ((void*) ptr) T(); \
+ } \
+ \
+ BOOST_PP_REPEAT_FROM_TO(1, n, \
+ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_)
+
+# define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_) \
+ template<typename Alloc, typename T, \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
+ void construct_from_tuple_impl( \
+ ndnboost::unordered::detail::length<n>, Alloc&, T* ptr, \
+ namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
+ { \
+ new ((void*) ptr) T( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \
+ ); \
+ }
+
+# define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) \
+ namespace_ get<n>(x)
+
+#endif
+
+BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, ndnboost::)
+
+#if !defined(__SUNPRO_CC) && !defined(BOOST_NO_CXX11_HDR_TUPLE)
+ BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, std::)
+#endif
+
+#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE
+#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL
+#undef BOOST_UNORDERED_GET_TUPLE_ARG
+
+#if defined(__SUNPRO_CC)
+
+ template <typename Alloc, typename T, typename Tuple>
+ void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x)
+ {
+ construct_from_tuple_impl(
+ ndnboost::unordered::detail::length<
+ ndnboost::tuples::length<Tuple>::value>(),
+ alloc, ptr, x);
+ }
+
+#endif
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Trait to check for piecewise construction.
+
+ template <typename A0>
+ struct use_piecewise {
+ static choice1::type test(choice1,
+ ndnboost::unordered::piecewise_construct_t);
+
+ static choice2::type test(choice2, ...);
+
+ enum { value = sizeof(choice1::type) ==
+ sizeof(test(choose(), ndnboost::unordered::detail::make<A0>())) };
+ };
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Construct from variadic parameters
+
+ // For the standard pair constructor.
+
+ template <typename Alloc, typename T, typename... Args>
+ inline void construct_value_impl(Alloc& alloc, T* address,
+ BOOST_FWD_REF(Args)... args)
+ {
+ ndnboost::unordered::detail::call_construct(alloc,
+ address, ndnboost::forward<Args>(args)...);
+ }
+
+ // Special case for piece_construct
+ //
+ // TODO: When possible, it might be better to use std::pair's
+ // constructor for std::piece_construct with std::tuple.
+
+ template <typename Alloc, typename A, typename B,
+ typename A0, typename A1, typename A2>
+ inline typename enable_if<use_piecewise<A0>, void>::type
+ construct_value_impl(Alloc& alloc, std::pair<A, B>* address,
+ BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
+ {
+ ndnboost::unordered::detail::construct_from_tuple(alloc,
+ ndnboost::addressof(address->first), ndnboost::forward<A1>(a1));
+ ndnboost::unordered::detail::construct_from_tuple(alloc,
+ ndnboost::addressof(address->second), ndnboost::forward<A2>(a2));
+ }
+
+#else // BOOST_NO_CXX11_VARIADIC_TEMPLATES
+
+////////////////////////////////////////////////////////////////////////////////
+// Construct from emplace_args
+
+ // Explicitly write out first three overloads for the sake of sane
+ // error messages.
+
+ template <typename Alloc, typename T, typename A0>
+ inline void construct_value_impl(Alloc&, T* address,
+ emplace_args1<A0> const& args)
+ {
+ new((void*) address) T(ndnboost::forward<A0>(args.a0));
+ }
+
+ template <typename Alloc, typename T, typename A0, typename A1>
+ inline void construct_value_impl(Alloc&, T* address,
+ emplace_args2<A0, A1> const& args)
+ {
+ new((void*) address) T(
+ ndnboost::forward<A0>(args.a0),
+ ndnboost::forward<A1>(args.a1)
+ );
+ }
+
+ template <typename Alloc, typename T, typename A0, typename A1, typename A2>
+ inline void construct_value_impl(Alloc&, T* address,
+ emplace_args3<A0, A1, A2> const& args)
+ {
+ new((void*) address) T(
+ ndnboost::forward<A0>(args.a0),
+ ndnboost::forward<A1>(args.a1),
+ ndnboost::forward<A2>(args.a2)
+ );
+ }
+
+ // Use a macro for the rest.
+
+#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \
+ template < \
+ typename Alloc, typename T, \
+ BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A) \
+ > \
+ inline void construct_value_impl(Alloc&, T* address, \
+ ndnboost::unordered::detail::BOOST_PP_CAT(emplace_args,num_params) < \
+ BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) \
+ > const& args) \
+ { \
+ new((void*) address) T( \
+ BOOST_PP_ENUM_##z(num_params, BOOST_UNORDERED_CALL_FORWARD, \
+ args.a)); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_CONSTRUCT_IMPL, _)
+
+#undef BOOST_UNORDERED_CONSTRUCT_IMPL
+
+ // Construct with piece_construct
+
+ template <typename Alloc, typename A, typename B,
+ typename A0, typename A1, typename A2>
+ inline void construct_value_impl(Alloc& alloc, std::pair<A, B>* address,
+ ndnboost::unordered::detail::emplace_args3<A0, A1, A2> const& args,
+ typename enable_if<use_piecewise<A0>, void*>::type = 0)
+ {
+ ndnboost::unordered::detail::construct_from_tuple(alloc,
+ ndnboost::addressof(address->first), args.a1);
+ ndnboost::unordered::detail::construct_from_tuple(alloc,
+ ndnboost::addressof(address->second), args.a2);
+ }
+
+#endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES
+
+}}}
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// Some helper functions for allocating & constructing
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ //
+ // array_constructor
+ //
+ // Allocate and construct an array in an exception safe manner, and
+ // clean up if an exception is thrown before the container takes charge
+ // of it.
+
+ template <typename Allocator>
+ struct array_constructor
+ {
+ typedef ndnboost::unordered::detail::allocator_traits<Allocator> traits;
+ typedef typename traits::pointer pointer;
+
+ Allocator& alloc_;
+ pointer ptr_;
+ pointer constructed_;
+ std::size_t length_;
+
+ array_constructor(Allocator& a)
+ : alloc_(a), ptr_(), constructed_(), length_(0)
+ {
+ constructed_ = pointer();
+ ptr_ = pointer();
+ }
+
+ ~array_constructor() {
+ if (ptr_) {
+ for(pointer p = ptr_; p != constructed_; ++p)
+ traits::destroy(alloc_, ndnboost::addressof(*p));
+
+ traits::deallocate(alloc_, ptr_, length_);
+ }
+ }
+
+ template <typename V>
+ void construct(V const& v, std::size_t l)
+ {
+ BOOST_ASSERT(!ptr_);
+ length_ = l;
+ ptr_ = traits::allocate(alloc_, length_);
+ pointer end = ptr_ + static_cast<std::ptrdiff_t>(length_);
+ for(constructed_ = ptr_; constructed_ != end; ++constructed_)
+ traits::construct(alloc_, ndnboost::addressof(*constructed_), v);
+ }
+
+ pointer get() const
+ {
+ return ptr_;
+ }
+
+ pointer release()
+ {
+ pointer p(ptr_);
+ ptr_ = pointer();
+ return p;
+ }
+
+ private:
+
+ array_constructor(array_constructor const&);
+ array_constructor& operator=(array_constructor const&);
+ };
+}}}
+
+#if defined(BOOST_MSVC)
+#pragma warning(pop)
+#endif
+
+#endif
diff --git a/ndnboost/unordered/detail/buckets.hpp b/ndnboost/unordered/detail/buckets.hpp
new file mode 100644
index 0000000..df44e70
--- /dev/null
+++ b/ndnboost/unordered/detail/buckets.hpp
@@ -0,0 +1,876 @@
+
+// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
+// Copyright (C) 2005-2011 Daniel James
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1020)
+# pragma once
+#endif
+
+#include <ndnboost/unordered/detail/util.hpp>
+#include <ndnboost/unordered/detail/allocate.hpp>
+#include <ndnboost/type_traits/aligned_storage.hpp>
+#include <ndnboost/type_traits/alignment_of.hpp>
+#include <ndnboost/type_traits/is_nothrow_move_constructible.hpp>
+#include <ndnboost/type_traits/is_nothrow_move_assignable.hpp>
+#include <ndnboost/swap.hpp>
+#include <ndnboost/assert.hpp>
+#include <ndnboost/limits.hpp>
+#include <ndnboost/iterator.hpp>
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ template <typename Types> struct table;
+ template <typename NodePointer> struct bucket;
+ struct ptr_bucket;
+ template <typename Types> struct table_impl;
+ template <typename Types> struct grouped_table_impl;
+
+}}}
+
+namespace ndnboost { namespace unordered { namespace iterator_detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Iterators
+ //
+ // all no throw
+
+ template <typename Node> struct iterator;
+ template <typename Node, typename ConstNodePointer> struct c_iterator;
+ template <typename Node, typename Policy> struct l_iterator;
+ template <typename Node, typename ConstNodePointer, typename Policy>
+ struct cl_iterator;
+
+ // Local Iterators
+ //
+ // all no throw
+
+ template <typename Node, typename Policy>
+ struct l_iterator
+ : public ndnboost::iterator<
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ typename Node::node_pointer,
+ typename Node::value_type&>
+ {
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+ template <typename Node2, typename ConstNodePointer, typename Policy2>
+ friend struct ndnboost::unordered::iterator_detail::cl_iterator;
+ private:
+#endif
+ typedef typename Node::node_pointer node_pointer;
+ typedef ndnboost::unordered::iterator_detail::iterator<Node> iterator;
+ node_pointer ptr_;
+ std::size_t bucket_;
+ std::size_t bucket_count_;
+
+ public:
+
+ typedef typename Node::value_type value_type;
+
+ l_iterator() : ptr_() {}
+
+ l_iterator(iterator x, std::size_t b, std::size_t c)
+ : ptr_(x.node_), bucket_(b), bucket_count_(c) {}
+
+ value_type& operator*() const {
+ return ptr_->value();
+ }
+
+ value_type* operator->() const {
+ return ptr_->value_ptr();
+ }
+
+ l_iterator& operator++() {
+ ptr_ = static_cast<node_pointer>(ptr_->next_);
+ if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_)
+ != bucket_)
+ ptr_ = node_pointer();
+ return *this;
+ }
+
+ l_iterator operator++(int) {
+ l_iterator tmp(*this);
+ ++(*this);
+ return tmp;
+ }
+
+ bool operator==(l_iterator x) const {
+ return ptr_ == x.ptr_;
+ }
+
+ bool operator!=(l_iterator x) const {
+ return ptr_ != x.ptr_;
+ }
+ };
+
+ template <typename Node, typename ConstNodePointer, typename Policy>
+ struct cl_iterator
+ : public ndnboost::iterator<
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ ConstNodePointer,
+ typename Node::value_type const&>
+ {
+ friend struct ndnboost::unordered::iterator_detail::l_iterator
+ <Node, Policy>;
+ private:
+
+ typedef typename Node::node_pointer node_pointer;
+ typedef ndnboost::unordered::iterator_detail::iterator<Node> iterator;
+ node_pointer ptr_;
+ std::size_t bucket_;
+ std::size_t bucket_count_;
+
+ public:
+
+ typedef typename Node::value_type value_type;
+
+ cl_iterator() : ptr_() {}
+
+ cl_iterator(iterator x, std::size_t b, std::size_t c) :
+ ptr_(x.node_), bucket_(b), bucket_count_(c) {}
+
+ cl_iterator(ndnboost::unordered::iterator_detail::l_iterator<
+ Node, Policy> const& x) :
+ ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_)
+ {}
+
+ value_type const& operator*() const {
+ return ptr_->value();
+ }
+
+ value_type const* operator->() const {
+ return ptr_->value_ptr();
+ }
+
+ cl_iterator& operator++() {
+ ptr_ = static_cast<node_pointer>(ptr_->next_);
+ if (ptr_ && Policy::to_bucket(bucket_count_, ptr_->hash_)
+ != bucket_)
+ ptr_ = node_pointer();
+ return *this;
+ }
+
+ cl_iterator operator++(int) {
+ cl_iterator tmp(*this);
+ ++(*this);
+ return tmp;
+ }
+
+ friend bool operator==(cl_iterator const& x, cl_iterator const& y) {
+ return x.ptr_ == y.ptr_;
+ }
+
+ friend bool operator!=(cl_iterator const& x, cl_iterator const& y) {
+ return x.ptr_ != y.ptr_;
+ }
+ };
+
+ template <typename Node>
+ struct iterator
+ : public ndnboost::iterator<
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ typename Node::node_pointer,
+ typename Node::value_type&>
+ {
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+ template <typename, typename>
+ friend struct ndnboost::unordered::iterator_detail::c_iterator;
+ template <typename, typename>
+ friend struct ndnboost::unordered::iterator_detail::l_iterator;
+ template <typename, typename, typename>
+ friend struct ndnboost::unordered::iterator_detail::cl_iterator;
+ template <typename>
+ friend struct ndnboost::unordered::detail::table;
+ template <typename>
+ friend struct ndnboost::unordered::detail::table_impl;
+ template <typename>
+ friend struct ndnboost::unordered::detail::grouped_table_impl;
+ private:
+#endif
+ typedef typename Node::node_pointer node_pointer;
+ node_pointer node_;
+
+ public:
+
+ typedef typename Node::value_type value_type;
+
+ iterator() : node_() {}
+
+ explicit iterator(typename Node::link_pointer x) :
+ node_(static_cast<node_pointer>(x)) {}
+
+ value_type& operator*() const {
+ return node_->value();
+ }
+
+ value_type* operator->() const {
+ return &node_->value();
+ }
+
+ iterator& operator++() {
+ node_ = static_cast<node_pointer>(node_->next_);
+ return *this;
+ }
+
+ iterator operator++(int) {
+ iterator tmp(node_);
+ node_ = static_cast<node_pointer>(node_->next_);
+ return tmp;
+ }
+
+ bool operator==(iterator const& x) const {
+ return node_ == x.node_;
+ }
+
+ bool operator!=(iterator const& x) const {
+ return node_ != x.node_;
+ }
+ };
+
+ template <typename Node, typename ConstNodePointer>
+ struct c_iterator
+ : public ndnboost::iterator<
+ std::forward_iterator_tag,
+ typename Node::value_type,
+ std::ptrdiff_t,
+ ConstNodePointer,
+ typename Node::value_type const&>
+ {
+ friend struct ndnboost::unordered::iterator_detail::iterator<Node>;
+
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+ template <typename>
+ friend struct ndnboost::unordered::detail::table;
+ template <typename>
+ friend struct ndnboost::unordered::detail::table_impl;
+ template <typename>
+ friend struct ndnboost::unordered::detail::grouped_table_impl;
+
+ private:
+#endif
+ typedef typename Node::node_pointer node_pointer;
+ typedef ndnboost::unordered::iterator_detail::iterator<Node> iterator;
+ node_pointer node_;
+
+ public:
+
+ typedef typename Node::value_type value_type;
+
+ c_iterator() : node_() {}
+
+ explicit c_iterator(typename Node::link_pointer x) :
+ node_(static_cast<node_pointer>(x)) {}
+
+ c_iterator(iterator const& x) : node_(x.node_) {}
+
+ value_type const& operator*() const {
+ return node_->value();
+ }
+
+ value_type const* operator->() const {
+ return &node_->value();
+ }
+
+ c_iterator& operator++() {
+ node_ = static_cast<node_pointer>(node_->next_);
+ return *this;
+ }
+
+ c_iterator operator++(int) {
+ c_iterator tmp(node_);
+ node_ = static_cast<node_pointer>(node_->next_);
+ return tmp;
+ }
+
+ friend bool operator==(c_iterator const& x, c_iterator const& y) {
+ return x.node_ == y.node_;
+ }
+
+ friend bool operator!=(c_iterator const& x, c_iterator const& y) {
+ return x.node_ != y.node_;
+ }
+ };
+}}}
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Node construction
+
+ template <typename NodeAlloc>
+ struct node_constructor
+ {
+ private:
+
+ typedef NodeAlloc node_allocator;
+ typedef ndnboost::unordered::detail::allocator_traits<NodeAlloc>
+ node_allocator_traits;
+ typedef typename node_allocator_traits::value_type node;
+ typedef typename node_allocator_traits::pointer node_pointer;
+ typedef typename node::value_type value_type;
+
+ protected:
+
+ node_allocator& alloc_;
+ node_pointer node_;
+ bool node_constructed_;
+ bool value_constructed_;
+
+ public:
+
+ node_constructor(node_allocator& n) :
+ alloc_(n),
+ node_(),
+ node_constructed_(false),
+ value_constructed_(false)
+ {
+ }
+
+ ~node_constructor();
+
+ void construct();
+
+ template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ void construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS)
+ {
+ construct();
+ ndnboost::unordered::detail::construct_value_impl(
+ alloc_, node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
+ value_constructed_ = true;
+ }
+
+ template <typename A0>
+ void construct_with_value2(BOOST_FWD_REF(A0) a0)
+ {
+ construct();
+ ndnboost::unordered::detail::construct_value_impl(
+ alloc_, node_->value_ptr(),
+ BOOST_UNORDERED_EMPLACE_ARGS1(ndnboost::forward<A0>(a0)));
+ value_constructed_ = true;
+ }
+
+ value_type const& value() const {
+ BOOST_ASSERT(node_ && node_constructed_ && value_constructed_);
+ return node_->value();
+ }
+
+ // no throw
+ node_pointer release()
+ {
+ BOOST_ASSERT(node_ && node_constructed_);
+ node_pointer p = node_;
+ node_ = node_pointer();
+ return p;
+ }
+
+ private:
+ node_constructor(node_constructor const&);
+ node_constructor& operator=(node_constructor const&);
+ };
+
+ template <typename Alloc>
+ node_constructor<Alloc>::~node_constructor()
+ {
+ if (node_) {
+ if (value_constructed_) {
+ ndnboost::unordered::detail::destroy_value_impl(alloc_,
+ node_->value_ptr());
+ }
+
+ if (node_constructed_) {
+ node_allocator_traits::destroy(alloc_,
+ ndnboost::addressof(*node_));
+ }
+
+ node_allocator_traits::deallocate(alloc_, node_, 1);
+ }
+ }
+
+ template <typename Alloc>
+ void node_constructor<Alloc>::construct()
+ {
+ if(!node_) {
+ node_constructed_ = false;
+ value_constructed_ = false;
+
+ node_ = node_allocator_traits::allocate(alloc_, 1);
+
+ node_allocator_traits::construct(alloc_,
+ ndnboost::addressof(*node_), node());
+ node_->init(node_);
+ node_constructed_ = true;
+ }
+ else {
+ BOOST_ASSERT(node_constructed_);
+
+ if (value_constructed_)
+ {
+ ndnboost::unordered::detail::destroy_value_impl(alloc_,
+ node_->value_ptr());
+ value_constructed_ = false;
+ }
+ }
+ }
+
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Node Holder
+ //
+ // Temporary store for nodes. Deletes any that aren't used.
+
+ template <typename NodeAlloc>
+ struct node_holder : private node_constructor<NodeAlloc>
+ {
+ private:
+ typedef node_constructor<NodeAlloc> base;
+
+ typedef NodeAlloc node_allocator;
+ typedef ndnboost::unordered::detail::allocator_traits<NodeAlloc>
+ node_allocator_traits;
+ typedef typename node_allocator_traits::value_type node;
+ typedef typename node_allocator_traits::pointer node_pointer;
+ typedef typename node::value_type value_type;
+ typedef typename node::link_pointer link_pointer;
+ typedef ndnboost::unordered::iterator_detail::iterator<node> iterator;
+
+ node_pointer nodes_;
+
+ public:
+
+ template <typename Table>
+ explicit node_holder(Table& b) :
+ base(b.node_alloc()),
+ nodes_()
+ {
+ if (b.size_) {
+ typename Table::link_pointer prev = b.get_previous_start();
+ nodes_ = static_cast<node_pointer>(prev->next_);
+ prev->next_ = link_pointer();
+ b.size_ = 0;
+ }
+ }
+
+ ~node_holder();
+
+ void node_for_assignment()
+ {
+ if (!this->node_ && nodes_) {
+ this->node_ = nodes_;
+ nodes_ = static_cast<node_pointer>(nodes_->next_);
+ this->node_->init(this->node_);
+ this->node_->next_ = link_pointer();
+
+ this->node_constructed_ = true;
+ this->value_constructed_ = true;
+ }
+ }
+
+ template <typename T>
+ inline void assign_impl(T const& v) {
+ if (this->node_ && this->value_constructed_) {
+ this->node_->value() = v;
+ }
+ else {
+ this->construct_with_value2(v);
+ }
+ }
+
+ template <typename T1, typename T2>
+ inline void assign_impl(std::pair<T1 const, T2> const& v) {
+ this->construct_with_value2(v);
+ }
+
+ template <typename T>
+ inline void move_assign_impl(T& v) {
+ if (this->node_ && this->value_constructed_) {
+ this->node_->value() = ndnboost::move(v);
+ }
+ else {
+ this->construct_with_value2(ndnboost::move(v));
+ }
+ }
+
+ template <typename T1, typename T2>
+ inline void move_assign_impl(std::pair<T1 const, T2>& v) {
+ this->construct_with_value2(ndnboost::move(v));
+ }
+
+ node_pointer copy_of(value_type const& v)
+ {
+ node_for_assignment();
+ assign_impl(v);
+ return base::release();
+ }
+
+ node_pointer move_copy_of(value_type& v)
+ {
+ node_for_assignment();
+ move_assign_impl(v);
+ return base::release();
+ }
+
+ iterator begin() const
+ {
+ return iterator(nodes_);
+ }
+ };
+
+ template <typename Alloc>
+ node_holder<Alloc>::~node_holder()
+ {
+ while (nodes_) {
+ node_pointer p = nodes_;
+ nodes_ = static_cast<node_pointer>(p->next_);
+
+ ndnboost::unordered::detail::destroy_value_impl(this->alloc_,
+ p->value_ptr());
+ node_allocator_traits::destroy(this->alloc_, ndnboost::addressof(*p));
+ node_allocator_traits::deallocate(this->alloc_, p, 1);
+ }
+ }
+
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Bucket
+
+ template <typename NodePointer>
+ struct bucket
+ {
+ typedef NodePointer link_pointer;
+ link_pointer next_;
+
+ bucket() : next_() {}
+
+ link_pointer first_from_start()
+ {
+ return next_;
+ }
+
+ enum { extra_node = true };
+ };
+
+ struct ptr_bucket
+ {
+ typedef ptr_bucket* link_pointer;
+ link_pointer next_;
+
+ ptr_bucket() : next_(0) {}
+
+ link_pointer first_from_start()
+ {
+ return this;
+ }
+
+ enum { extra_node = false };
+ };
+
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Hash Policy
+
+ template <typename SizeT>
+ struct prime_policy
+ {
+ template <typename Hash, typename T>
+ static inline SizeT apply_hash(Hash const& hf, T const& x) {
+ return hf(x);
+ }
+
+ static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
+ return hash % bucket_count;
+ }
+
+ static inline SizeT new_bucket_count(SizeT min) {
+ return ndnboost::unordered::detail::next_prime(min);
+ }
+
+ static inline SizeT prev_bucket_count(SizeT max) {
+ return ndnboost::unordered::detail::prev_prime(max);
+ }
+ };
+
+ template <typename SizeT>
+ struct mix64_policy
+ {
+ template <typename Hash, typename T>
+ static inline SizeT apply_hash(Hash const& hf, T const& x) {
+ SizeT key = hf(x);
+ key = (~key) + (key << 21); // key = (key << 21) - key - 1;
+ key = key ^ (key >> 24);
+ key = (key + (key << 3)) + (key << 8); // key * 265
+ key = key ^ (key >> 14);
+ key = (key + (key << 2)) + (key << 4); // key * 21
+ key = key ^ (key >> 28);
+ key = key + (key << 31);
+ return key;
+ }
+
+ static inline SizeT to_bucket(SizeT bucket_count, SizeT hash) {
+ return hash & (bucket_count - 1);
+ }
+
+ static inline SizeT new_bucket_count(SizeT min) {
+ if (min <= 4) return 4;
+ --min;
+ min |= min >> 1;
+ min |= min >> 2;
+ min |= min >> 4;
+ min |= min >> 8;
+ min |= min >> 16;
+ min |= min >> 32;
+ return min + 1;
+ }
+
+ static inline SizeT prev_bucket_count(SizeT max) {
+ max |= max >> 1;
+ max |= max >> 2;
+ max |= max >> 4;
+ max |= max >> 8;
+ max |= max >> 16;
+ max |= max >> 32;
+ return (max >> 1) + 1;
+ }
+ };
+
+ template <int digits, int radix>
+ struct pick_policy_impl {
+ typedef prime_policy<std::size_t> type;
+ };
+
+ template <>
+ struct pick_policy_impl<64, 2> {
+ typedef mix64_policy<std::size_t> type;
+ };
+
+ struct pick_policy :
+ pick_policy_impl<
+ std::numeric_limits<std::size_t>::digits,
+ std::numeric_limits<std::size_t>::radix> {};
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Functions
+
+ // Assigning and swapping the equality and hash function objects
+ // needs strong exception safety. To implement that normally we'd
+ // require one of them to be known to not throw and the other to
+ // guarantee strong exception safety. Unfortunately they both only
+ // have basic exception safety. So to acheive strong exception
+ // safety we have storage space for two copies, and assign the new
+ // copies to the unused space. Then switch to using that to use
+ // them. This is implemented in 'set_hash_functions' which
+ // atomically assigns the new function objects in a strongly
+ // exception safe manner.
+
+ template <class H, class P, bool NoThrowMoveAssign>
+ class set_hash_functions;
+
+ template <class H, class P>
+ class functions
+ {
+ public:
+ static const bool nothrow_move_assignable =
+ ndnboost::is_nothrow_move_assignable<H>::value &&
+ ndnboost::is_nothrow_move_assignable<P>::value;
+ static const bool nothrow_move_constructible =
+ ndnboost::is_nothrow_move_constructible<H>::value &&
+ ndnboost::is_nothrow_move_constructible<P>::value;
+
+ private:
+ friend class ndnboost::unordered::detail::set_hash_functions<H, P,
+ nothrow_move_assignable>;
+ functions& operator=(functions const&);
+
+ typedef compressed<H, P> function_pair;
+
+ typedef typename ndnboost::aligned_storage<
+ sizeof(function_pair),
+ ndnboost::alignment_of<function_pair>::value>::type aligned_function;
+
+ bool current_; // The currently active functions.
+ aligned_function funcs_[2];
+
+ function_pair const& current() const {
+ return *static_cast<function_pair const*>(
+ static_cast<void const*>(&funcs_[current_]));
+ }
+
+ function_pair& current() {
+ return *static_cast<function_pair*>(
+ static_cast<void*>(&funcs_[current_]));
+ }
+
+ void construct(bool which, H const& hf, P const& eq)
+ {
+ new((void*) &funcs_[which]) function_pair(hf, eq);
+ }
+
+ void construct(bool which, function_pair const& f)
+ {
+ new((void*) &funcs_[which]) function_pair(f);
+ }
+
+ void construct(bool which, function_pair& f,
+ ndnboost::unordered::detail::move_tag m)
+ {
+ new((void*) &funcs_[which]) function_pair(f, m);
+ }
+
+ void destroy(bool which)
+ {
+ ndnboost::unordered::detail::destroy((function_pair*)(&funcs_[which]));
+ }
+
+ public:
+
+ typedef ndnboost::unordered::detail::set_hash_functions<H, P,
+ nothrow_move_assignable> set_hash_functions;
+
+ functions(H const& hf, P const& eq)
+ : current_(false)
+ {
+ construct(current_, hf, eq);
+ }
+
+ functions(functions const& bf)
+ : current_(false)
+ {
+ construct(current_, bf.current());
+ }
+
+ functions(functions& bf, ndnboost::unordered::detail::move_tag m)
+ : current_(false)
+ {
+ if (nothrow_move_constructible) {
+ construct(current_, bf.current(), m);
+ }
+ else {
+ construct(current_, bf.current());
+ }
+ }
+
+ ~functions() {
+ this->destroy(current_);
+ }
+
+ H const& hash_function() const {
+ return current().first();
+ }
+
+ P const& key_eq() const {
+ return current().second();
+ }
+ };
+
+ template <class H, class P>
+ class set_hash_functions<H, P, false>
+ {
+ set_hash_functions(set_hash_functions const&);
+ set_hash_functions& operator=(set_hash_functions const&);
+
+ typedef functions<H, P> functions_type;
+
+ functions_type& functions_;
+ bool tmp_functions_;
+
+ public:
+
+ set_hash_functions(functions_type& f, H const& h, P const& p)
+ : functions_(f),
+ tmp_functions_(!f.current_)
+ {
+ f.construct(tmp_functions_, h, p);
+ }
+
+ set_hash_functions(functions_type& f, functions_type const& other)
+ : functions_(f),
+ tmp_functions_(!f.current_)
+ {
+ f.construct(tmp_functions_, other.current());
+ }
+
+ ~set_hash_functions()
+ {
+ functions_.destroy(tmp_functions_);
+ }
+
+ void commit()
+ {
+ functions_.current_ = tmp_functions_;
+ tmp_functions_ = !tmp_functions_;
+ }
+ };
+
+ template <class H, class P>
+ class set_hash_functions<H, P, true>
+ {
+ set_hash_functions(set_hash_functions const&);
+ set_hash_functions& operator=(set_hash_functions const&);
+
+ typedef functions<H, P> functions_type;
+
+ functions_type& functions_;
+ H hash_;
+ P pred_;
+
+ public:
+
+ set_hash_functions(functions_type& f, H const& h, P const& p) :
+ functions_(f),
+ hash_(h),
+ pred_(p) {}
+
+ set_hash_functions(functions_type& f, functions_type const& other) :
+ functions_(f),
+ hash_(other.hash_function()),
+ pred_(other.key_eq()) {}
+
+ void commit()
+ {
+ functions_.current().first() = ndnboost::move(hash_);
+ functions_.current().second() = ndnboost::move(pred_);
+ }
+ };
+
+ ////////////////////////////////////////////////////////////////////////////
+ // rvalue parameters when type can't be a BOOST_RV_REF(T) parameter
+ // e.g. for int
+
+#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+# define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T)
+#else
+ struct please_ignore_this_overload {
+ typedef please_ignore_this_overload type;
+ };
+
+ template <typename T>
+ struct rv_ref_impl {
+ typedef BOOST_RV_REF(T) type;
+ };
+
+ template <typename T>
+ struct rv_ref :
+ ndnboost::detail::if_true<
+ ndnboost::is_class<T>::value
+ >::BOOST_NESTED_TEMPLATE then <
+ ndnboost::unordered::detail::rv_ref_impl<T>,
+ please_ignore_this_overload
+ >::type
+ {};
+
+# define BOOST_UNORDERED_RV_REF(T) \
+ typename ndnboost::unordered::detail::rv_ref<T>::type
+#endif
+}}}
+
+#endif
diff --git a/ndnboost/unordered/detail/equivalent.hpp b/ndnboost/unordered/detail/equivalent.hpp
new file mode 100644
index 0000000..511fa0c
--- /dev/null
+++ b/ndnboost/unordered/detail/equivalent.hpp
@@ -0,0 +1,680 @@
+
+// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
+// Copyright (C) 2005-2011 Daniel James
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1020)
+# pragma once
+#endif
+
+#include <ndnboost/unordered/detail/table.hpp>
+#include <ndnboost/unordered/detail/extract_key.hpp>
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ template <typename A, typename T> struct grouped_node;
+ template <typename T> struct grouped_ptr_node;
+ template <typename Types> struct grouped_table_impl;
+
+ template <typename A, typename T>
+ struct grouped_node :
+ ndnboost::unordered::detail::value_base<T>
+ {
+ typedef typename ::ndnboost::unordered::detail::rebind_wrap<
+ A, grouped_node<A, T> >::type allocator;
+ typedef typename ::ndnboost::unordered::detail::
+ allocator_traits<allocator>::pointer node_pointer;
+ typedef node_pointer link_pointer;
+
+ link_pointer next_;
+ node_pointer group_prev_;
+ std::size_t hash_;
+
+ grouped_node() :
+ next_(),
+ group_prev_(),
+ hash_(0)
+ {}
+
+ void init(node_pointer self)
+ {
+ group_prev_ = self;
+ }
+
+ private:
+ grouped_node& operator=(grouped_node const&);
+ };
+
+ template <typename T>
+ struct grouped_ptr_node :
+ ndnboost::unordered::detail::value_base<T>,
+ ndnboost::unordered::detail::ptr_bucket
+ {
+ typedef ndnboost::unordered::detail::ptr_bucket bucket_base;
+ typedef grouped_ptr_node<T>* node_pointer;
+ typedef ptr_bucket* link_pointer;
+
+ node_pointer group_prev_;
+ std::size_t hash_;
+
+ grouped_ptr_node() :
+ bucket_base(),
+ group_prev_(0),
+ hash_(0)
+ {}
+
+ void init(node_pointer self)
+ {
+ group_prev_ = self;
+ }
+
+ private:
+ grouped_ptr_node& operator=(grouped_ptr_node const&);
+ };
+
+ // If the allocator uses raw pointers use grouped_ptr_node
+ // Otherwise use grouped_node.
+
+ template <typename A, typename T, typename NodePtr, typename BucketPtr>
+ struct pick_grouped_node2
+ {
+ typedef ndnboost::unordered::detail::grouped_node<A, T> node;
+
+ typedef typename ndnboost::unordered::detail::allocator_traits<
+ typename ndnboost::unordered::detail::rebind_wrap<A, node>::type
+ >::pointer node_pointer;
+
+ typedef ndnboost::unordered::detail::bucket<node_pointer> bucket;
+ typedef node_pointer link_pointer;
+ };
+
+ template <typename A, typename T>
+ struct pick_grouped_node2<A, T,
+ ndnboost::unordered::detail::grouped_ptr_node<T>*,
+ ndnboost::unordered::detail::ptr_bucket*>
+ {
+ typedef ndnboost::unordered::detail::grouped_ptr_node<T> node;
+ typedef ndnboost::unordered::detail::ptr_bucket bucket;
+ typedef bucket* link_pointer;
+ };
+
+ template <typename A, typename T>
+ struct pick_grouped_node
+ {
+ typedef ndnboost::unordered::detail::allocator_traits<
+ typename ndnboost::unordered::detail::rebind_wrap<A,
+ ndnboost::unordered::detail::grouped_ptr_node<T> >::type
+ > tentative_node_traits;
+
+ typedef ndnboost::unordered::detail::allocator_traits<
+ typename ndnboost::unordered::detail::rebind_wrap<A,
+ ndnboost::unordered::detail::ptr_bucket >::type
+ > tentative_bucket_traits;
+
+ typedef pick_grouped_node2<A, T,
+ typename tentative_node_traits::pointer,
+ typename tentative_bucket_traits::pointer> pick;
+
+ typedef typename pick::node node;
+ typedef typename pick::bucket bucket;
+ typedef typename pick::link_pointer link_pointer;
+ };
+
+ template <typename A, typename T, typename H, typename P>
+ struct multiset
+ {
+ typedef ndnboost::unordered::detail::multiset<A, T, H, P> types;
+
+ typedef A allocator;
+ typedef T value_type;
+ typedef H hasher;
+ typedef P key_equal;
+ typedef T key_type;
+
+ typedef ndnboost::unordered::detail::allocator_traits<allocator> traits;
+ typedef ndnboost::unordered::detail::pick_grouped_node<allocator,
+ value_type> pick;
+ typedef typename pick::node node;
+ typedef typename pick::bucket bucket;
+ typedef typename pick::link_pointer link_pointer;
+
+ typedef ndnboost::unordered::detail::grouped_table_impl<types> table;
+ typedef ndnboost::unordered::detail::set_extractor<value_type> extractor;
+
+ typedef ndnboost::unordered::detail::pick_policy::type policy;
+ };
+
+ template <typename A, typename K, typename M, typename H, typename P>
+ struct multimap
+ {
+ typedef ndnboost::unordered::detail::multimap<A, K, M, H, P> types;
+
+ typedef A allocator;
+ typedef std::pair<K const, M> value_type;
+ typedef H hasher;
+ typedef P key_equal;
+ typedef K key_type;
+
+ typedef ndnboost::unordered::detail::allocator_traits<allocator> traits;
+ typedef ndnboost::unordered::detail::pick_grouped_node<allocator,
+ value_type> pick;
+ typedef typename pick::node node;
+ typedef typename pick::bucket bucket;
+ typedef typename pick::link_pointer link_pointer;
+
+ typedef ndnboost::unordered::detail::grouped_table_impl<types> table;
+ typedef ndnboost::unordered::detail::map_extractor<key_type, value_type>
+ extractor;
+
+ typedef ndnboost::unordered::detail::pick_policy::type policy;
+ };
+
+ template <typename Types>
+ struct grouped_table_impl : ndnboost::unordered::detail::table<Types>
+ {
+ typedef ndnboost::unordered::detail::table<Types> table;
+ typedef typename table::value_type value_type;
+ typedef typename table::bucket bucket;
+ typedef typename table::policy policy;
+ typedef typename table::node_pointer node_pointer;
+ typedef typename table::node_allocator node_allocator;
+ typedef typename table::node_allocator_traits node_allocator_traits;
+ typedef typename table::bucket_pointer bucket_pointer;
+ typedef typename table::link_pointer link_pointer;
+ typedef typename table::hasher hasher;
+ typedef typename table::key_equal key_equal;
+ typedef typename table::key_type key_type;
+ typedef typename table::node_constructor node_constructor;
+ typedef typename table::extractor extractor;
+ typedef typename table::iterator iterator;
+ typedef typename table::c_iterator c_iterator;
+
+ // Constructors
+
+ grouped_table_impl(std::size_t n,
+ hasher const& hf,
+ key_equal const& eq,
+ node_allocator const& a)
+ : table(n, hf, eq, a)
+ {}
+
+ grouped_table_impl(grouped_table_impl const& x)
+ : table(x, node_allocator_traits::
+ select_on_container_copy_construction(x.node_alloc()))
+ {
+ this->init(x);
+ }
+
+ grouped_table_impl(grouped_table_impl const& x,
+ node_allocator const& a)
+ : table(x, a)
+ {
+ this->init(x);
+ }
+
+ grouped_table_impl(grouped_table_impl& x,
+ ndnboost::unordered::detail::move_tag m)
+ : table(x, m)
+ {}
+
+ grouped_table_impl(grouped_table_impl& x,
+ node_allocator const& a,
+ ndnboost::unordered::detail::move_tag m)
+ : table(x, a, m)
+ {
+ this->move_init(x);
+ }
+
+ // Accessors
+
+ template <class Key, class Pred>
+ iterator find_node_impl(
+ std::size_t key_hash,
+ Key const& k,
+ Pred const& eq) const
+ {
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
+ iterator n = this->begin(bucket_index);
+
+ for (;;)
+ {
+ if (!n.node_) return n;
+
+ std::size_t node_hash = n.node_->hash_;
+ if (key_hash == node_hash)
+ {
+ if (eq(k, this->get_key(*n)))
+ return n;
+ }
+ else
+ {
+ if (this->hash_to_bucket(node_hash) != bucket_index)
+ return iterator();
+ }
+
+ n = iterator(n.node_->group_prev_->next_);
+ }
+ }
+
+ std::size_t count(key_type const& k) const
+ {
+ iterator n = this->find_node(k);
+ if (!n.node_) return 0;
+
+ std::size_t x = 0;
+ node_pointer it = n.node_;
+ do {
+ it = it->group_prev_;
+ ++x;
+ } while(it != n.node_);
+
+ return x;
+ }
+
+ std::pair<iterator, iterator>
+ equal_range(key_type const& k) const
+ {
+ iterator n = this->find_node(k);
+ return std::make_pair(
+ n, n.node_ ? iterator(n.node_->group_prev_->next_) : n);
+ }
+
+ // Equality
+
+ bool equals(grouped_table_impl const& other) const
+ {
+ if(this->size_ != other.size_) return false;
+
+ for(iterator n1 = this->begin(); n1.node_;)
+ {
+ iterator n2 = other.find_matching_node(n1);
+ if (!n2.node_) return false;
+ iterator end1(n1.node_->group_prev_->next_);
+ iterator end2(n2.node_->group_prev_->next_);
+ if (!group_equals(n1, end1, n2, end2)) return false;
+ n1 = end1;
+ }
+
+ return true;
+ }
+
+ static bool group_equals(iterator n1, iterator end1,
+ iterator n2, iterator end2)
+ {
+ for(;;)
+ {
+ if (*n1 != *n2) break;
+
+ ++n1;
+ ++n2;
+
+ if (n1 == end1) return n2 == end2;
+ if (n2 == end2) return false;
+ }
+
+ for(iterator n1a = n1, n2a = n2;;)
+ {
+ ++n1a;
+ ++n2a;
+
+ if (n1a == end1)
+ {
+ if (n2a == end2) break;
+ else return false;
+ }
+
+ if (n2a == end2) return false;
+ }
+
+ iterator start = n1;
+ for(;n1 != end1; ++n1)
+ {
+ value_type const& v = *n1;
+ if (find(start, n1, v)) continue;
+ std::size_t matches = count_equal(n2, end2, v);
+ if (!matches) return false;
+ iterator next = n1;
+ ++next;
+ if (matches != 1 + count_equal(next, end1, v)) return false;
+ }
+
+ return true;
+ }
+
+ static bool find(iterator n, iterator end, value_type const& v)
+ {
+ for(;n != end; ++n)
+ if (*n == v)
+ return true;
+ return false;
+ }
+
+ static std::size_t count_equal(iterator n, iterator end,
+ value_type const& v)
+ {
+ std::size_t count = 0;
+ for(;n != end; ++n)
+ if (*n == v) ++count;
+ return count;
+ }
+
+ // Emplace/Insert
+
+ static inline void add_after_node(
+ node_pointer n,
+ node_pointer pos)
+ {
+ n->next_ = pos->group_prev_->next_;
+ n->group_prev_ = pos->group_prev_;
+ pos->group_prev_->next_ = n;
+ pos->group_prev_ = n;
+ }
+
+ inline iterator add_node(
+ node_constructor& a,
+ std::size_t key_hash,
+ iterator pos)
+ {
+ node_pointer n = a.release();
+ n->hash_ = key_hash;
+ if (pos.node_) {
+ this->add_after_node(n, pos.node_);
+ if (n->next_) {
+ std::size_t next_bucket = this->hash_to_bucket(
+ static_cast<node_pointer>(n->next_)->hash_);
+ if (next_bucket != this->hash_to_bucket(key_hash)) {
+ this->get_bucket(next_bucket)->next_ = n;
+ }
+ }
+ }
+ else {
+ bucket_pointer b = this->get_bucket(
+ this->hash_to_bucket(key_hash));
+
+ if (!b->next_)
+ {
+ link_pointer start_node = this->get_previous_start();
+
+ if (start_node->next_) {
+ this->get_bucket(this->hash_to_bucket(
+ static_cast<node_pointer>(start_node->next_)->hash_
+ ))->next_ = n;
+ }
+
+ b->next_ = start_node;
+ n->next_ = start_node->next_;
+ start_node->next_ = n;
+ }
+ else
+ {
+ n->next_ = b->next_->next_;
+ b->next_->next_ = n;
+ }
+ }
+ ++this->size_;
+ return iterator(n);
+ }
+
+ iterator emplace_impl(node_constructor& a)
+ {
+ key_type const& k = this->get_key(a.value());
+ std::size_t key_hash = this->hash(k);
+ iterator position = this->find_node(key_hash, k);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ this->reserve_for_insert(this->size_ + 1);
+ return this->add_node(a, key_hash, position);
+ }
+
+ void emplace_impl_no_rehash(node_constructor& a)
+ {
+ key_type const& k = this->get_key(a.value());
+ std::size_t key_hash = this->hash(k);
+ this->add_node(a, key_hash, this->find_node(key_hash, k));
+ }
+
+#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+# if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+ iterator emplace(ndnboost::unordered::detail::emplace_args1<
+ ndnboost::unordered::detail::please_ignore_this_overload> const&)
+ {
+ BOOST_ASSERT(false);
+ return iterator();
+ }
+# else
+ iterator emplace(
+ ndnboost::unordered::detail::please_ignore_this_overload const&)
+ {
+ BOOST_ASSERT(false);
+ return iterator();
+ }
+# endif
+#endif
+
+ template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ iterator emplace(BOOST_UNORDERED_EMPLACE_ARGS)
+ {
+ node_constructor a(this->node_alloc());
+ a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD);
+
+ return iterator(emplace_impl(a));
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Insert range methods
+
+ // if hash function throws, or inserting > 1 element, basic exception
+ // safety. Strong otherwise
+ template <class I>
+ typename ndnboost::unordered::detail::enable_if_forward<I, void>::type
+ insert_range(I i, I j)
+ {
+ if(i == j) return;
+
+ std::size_t distance = ndnboost::unordered::detail::distance(i, j);
+ if(distance == 1) {
+ node_constructor a(this->node_alloc());
+ a.construct_with_value2(*i);
+ emplace_impl(a);
+ }
+ else {
+ // Only require basic exception safety here
+ this->reserve_for_insert(this->size_ + distance);
+
+ node_constructor a(this->node_alloc());
+ for (; i != j; ++i) {
+ a.construct_with_value2(*i);
+ emplace_impl_no_rehash(a);
+ }
+ }
+ }
+
+ template <class I>
+ typename ndnboost::unordered::detail::disable_if_forward<I, void>::type
+ insert_range(I i, I j)
+ {
+ node_constructor a(this->node_alloc());
+ for (; i != j; ++i) {
+ a.construct_with_value2(*i);
+ emplace_impl(a);
+ }
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Erase
+ //
+ // no throw
+
+ std::size_t erase_key(key_type const& k)
+ {
+ if(!this->size_) return 0;
+
+ std::size_t key_hash = this->hash(k);
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
+ link_pointer prev = this->get_previous_start(bucket_index);
+ if (!prev) return 0;
+
+ for (;;)
+ {
+ if (!prev->next_) return 0;
+ std::size_t node_hash =
+ static_cast<node_pointer>(prev->next_)->hash_;
+ if (this->hash_to_bucket(node_hash) != bucket_index)
+ return 0;
+ if (node_hash == key_hash &&
+ this->key_eq()(k, this->get_key(
+ static_cast<node_pointer>(prev->next_)->value())))
+ break;
+ prev = static_cast<node_pointer>(prev->next_)->group_prev_;
+ }
+
+ node_pointer first_node = static_cast<node_pointer>(prev->next_);
+ link_pointer end = first_node->group_prev_->next_;
+
+ std::size_t count = this->delete_nodes(prev, end);
+ this->fix_bucket(bucket_index, prev);
+ return count;
+ }
+
+ iterator erase(c_iterator r)
+ {
+ BOOST_ASSERT(r.node_);
+ iterator next(r.node_);
+ ++next;
+ erase_nodes(r.node_, next.node_);
+ return next;
+ }
+
+ iterator erase_range(c_iterator r1, c_iterator r2)
+ {
+ if (r1 == r2) return iterator(r2.node_);
+ erase_nodes(r1.node_, r2.node_);
+ return iterator(r2.node_);
+ }
+
+ link_pointer erase_nodes(node_pointer begin, node_pointer end)
+ {
+ std::size_t bucket_index = this->hash_to_bucket(begin->hash_);
+
+ // Split the groups containing 'begin' and 'end'.
+ // And get the pointer to the node before begin while
+ // we're at it.
+ link_pointer prev = split_groups(begin, end);
+
+ // If we don't have a 'prev' it means that begin is at the
+ // beginning of a block, so search through the blocks in the
+ // same bucket.
+ if (!prev) {
+ prev = this->get_previous_start(bucket_index);
+ while (prev->next_ != begin)
+ prev = static_cast<node_pointer>(prev->next_)->group_prev_;
+ }
+
+ // Delete the nodes.
+ do {
+ link_pointer group_end =
+ static_cast<node_pointer>(prev->next_)->group_prev_->next_;
+ this->delete_nodes(prev, group_end);
+ bucket_index = this->fix_bucket(bucket_index, prev);
+ } while(prev->next_ != end);
+
+ return prev;
+ }
+
+ static link_pointer split_groups(node_pointer begin, node_pointer end)
+ {
+ node_pointer prev = begin->group_prev_;
+ if (prev->next_ != begin) prev = node_pointer();
+
+ if (end) {
+ node_pointer first = end;
+ while (first != begin && first->group_prev_->next_ == first) {
+ first = first->group_prev_;
+ }
+
+ ndnboost::swap(first->group_prev_, end->group_prev_);
+ if (first == begin) return prev;
+ }
+
+ if (prev) {
+ node_pointer first = prev;
+ while (first->group_prev_->next_ == first) {
+ first = first->group_prev_;
+ }
+ ndnboost::swap(first->group_prev_, begin->group_prev_);
+ }
+
+ return prev;
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // fill_buckets
+
+ template <class NodeCreator>
+ static void fill_buckets(iterator n, table& dst,
+ NodeCreator& creator)
+ {
+ link_pointer prev = dst.get_previous_start();
+
+ while (n.node_) {
+ std::size_t key_hash = n.node_->hash_;
+ iterator group_end(n.node_->group_prev_->next_);
+
+ node_pointer first_node = creator.create(*n);
+ node_pointer end = first_node;
+ first_node->hash_ = key_hash;
+ prev->next_ = first_node;
+ ++dst.size_;
+
+ for (++n; n != group_end; ++n)
+ {
+ end = creator.create(*n);
+ end->hash_ = key_hash;
+ add_after_node(end, first_node);
+ ++dst.size_;
+ }
+
+ prev = place_in_bucket(dst, prev, end);
+ }
+ }
+
+ // strong otherwise exception safety
+ void rehash_impl(std::size_t num_buckets)
+ {
+ BOOST_ASSERT(this->buckets_);
+
+ this->create_buckets(num_buckets);
+ link_pointer prev = this->get_previous_start();
+ while (prev->next_)
+ prev = place_in_bucket(*this, prev,
+ static_cast<node_pointer>(prev->next_)->group_prev_);
+ }
+
+ // Iterate through the nodes placing them in the correct buckets.
+ // pre: prev->next_ is not null.
+ static link_pointer place_in_bucket(table& dst,
+ link_pointer prev, node_pointer end)
+ {
+ bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(end->hash_));
+
+ if (!b->next_) {
+ b->next_ = prev;
+ return end;
+ }
+ else {
+ link_pointer next = end->next_;
+ end->next_ = b->next_->next_;
+ b->next_->next_ = prev->next_;
+ prev->next_ = next;
+ return prev;
+ }
+ }
+ };
+}}}
+
+#endif
diff --git a/ndnboost/unordered/detail/extract_key.hpp b/ndnboost/unordered/detail/extract_key.hpp
new file mode 100644
index 0000000..74dfdab
--- /dev/null
+++ b/ndnboost/unordered/detail/extract_key.hpp
@@ -0,0 +1,183 @@
+
+// Copyright (C) 2005-2011 Daniel James
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED
+
+#include <ndnboost/unordered/detail/table.hpp>
+
+namespace ndnboost {
+namespace unordered {
+namespace detail {
+
+ // key extractors
+ //
+ // no throw
+ //
+ // 'extract_key' is called with the emplace parameters to return a
+ // key if available or 'no_key' is one isn't and will need to be
+ // constructed. This could be done by overloading the emplace implementation
+ // for the different cases, but that's a bit tricky on compilers without
+ // variadic templates.
+
+ struct no_key {
+ no_key() {}
+ template <class T> no_key(T const&) {}
+ };
+
+ template <typename Key, typename T>
+ struct is_key {
+ template <typename T2>
+ static choice1::type test(T2 const&);
+ static choice2::type test(Key const&);
+
+ enum { value = sizeof(test(ndnboost::unordered::detail::make<T>())) ==
+ sizeof(choice2::type) };
+
+ typedef typename ndnboost::detail::if_true<value>::
+ BOOST_NESTED_TEMPLATE then<Key const&, no_key>::type type;
+ };
+
+ template <class ValueType>
+ struct set_extractor
+ {
+ typedef ValueType value_type;
+ typedef ValueType key_type;
+
+ static key_type const& extract(key_type const& v)
+ {
+ return v;
+ }
+
+ static no_key extract()
+ {
+ return no_key();
+ }
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+ template <class... Args>
+ static no_key extract(Args const&...)
+ {
+ return no_key();
+ }
+#else
+ template <class Arg>
+ static no_key extract(Arg const&)
+ {
+ return no_key();
+ }
+
+ template <class Arg1, class Arg2>
+ static no_key extract(Arg1 const&, Arg2 const&)
+ {
+ return no_key();
+ }
+#endif
+ };
+
+ template <class Key, class ValueType>
+ struct map_extractor
+ {
+ typedef ValueType value_type;
+ typedef typename ndnboost::remove_const<Key>::type key_type;
+
+ static key_type const& extract(value_type const& v)
+ {
+ return v.first;
+ }
+
+ template <class Second>
+ static key_type const& extract(std::pair<key_type, Second> const& v)
+ {
+ return v.first;
+ }
+
+ template <class Second>
+ static key_type const& extract(
+ std::pair<key_type const, Second> const& v)
+ {
+ return v.first;
+ }
+
+ template <class Arg1>
+ static key_type const& extract(key_type const& k, Arg1 const&)
+ {
+ return k;
+ }
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+ template <class... Args>
+ static no_key extract(Args const&...)
+ {
+ return no_key();
+ }
+#else
+
+ static no_key extract()
+ {
+ return no_key();
+ }
+
+ template <class Arg>
+ static no_key extract(Arg const&)
+ {
+ return no_key();
+ }
+
+ template <class Arg, class Arg1>
+ static no_key extract(Arg const&, Arg1 const&)
+ {
+ return no_key();
+ }
+#endif
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
+ template <typename T2> \
+ static no_key extract(ndnboost::unordered::piecewise_construct_t, \
+ namespace_ tuple<> const&, T2 const&) \
+ { \
+ return no_key(); \
+ } \
+ \
+ template <typename T, typename T2> \
+ static typename is_key<key_type, T>::type \
+ extract(ndnboost::unordered::piecewise_construct_t, \
+ namespace_ tuple<T> const& k, T2 const&) \
+ { \
+ return typename is_key<key_type, T>::type( \
+ namespace_ get<0>(k)); \
+ }
+
+#else
+
+#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
+ static no_key extract(ndnboost::unordered::piecewise_construct_t, \
+ namespace_ tuple<> const&) \
+ { \
+ return no_key(); \
+ } \
+ \
+ template <typename T> \
+ static typename is_key<key_type, T>::type \
+ extract(ndnboost::unordered::piecewise_construct_t, \
+ namespace_ tuple<T> const& k) \
+ { \
+ return typename is_key<key_type, T>::type( \
+ namespace_ get<0>(k)); \
+ }
+
+#endif
+
+BOOST_UNORDERED_KEY_FROM_TUPLE(ndnboost::)
+
+#if !defined(BOOST_NO_CXX11_HDR_TUPLE)
+BOOST_UNORDERED_KEY_FROM_TUPLE(std::)
+#endif
+ };
+}}}
+
+#endif
diff --git a/ndnboost/unordered/detail/fwd.hpp b/ndnboost/unordered/detail/fwd.hpp
new file mode 100644
index 0000000..929466f
--- /dev/null
+++ b/ndnboost/unordered/detail/fwd.hpp
@@ -0,0 +1,23 @@
+
+// Copyright (C) 2008-2011 Daniel James.
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UNORDERED_FWD_HPP_INCLUDED
+#define BOOST_UNORDERED_FWD_HPP_INCLUDED
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1020)
+# pragma once
+#endif
+
+
+namespace ndnboost
+{
+namespace unordered
+{
+ struct piecewise_construct_t {};
+ const piecewise_construct_t piecewise_construct = piecewise_construct_t();
+}
+}
+
+#endif
diff --git a/ndnboost/unordered/detail/table.hpp b/ndnboost/unordered/detail/table.hpp
new file mode 100644
index 0000000..3d2cf86
--- /dev/null
+++ b/ndnboost/unordered/detail/table.hpp
@@ -0,0 +1,861 @@
+
+// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
+// Copyright (C) 2005-2011 Daniel James
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED
+
+#include <ndnboost/unordered/detail/buckets.hpp>
+#include <ndnboost/unordered/detail/util.hpp>
+#include <ndnboost/type_traits/aligned_storage.hpp>
+#include <ndnboost/type_traits/alignment_of.hpp>
+#include <cmath>
+
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#pragma warning(disable:4127) // conditional expression is constant
+#endif
+
+#if defined(BOOST_UNORDERED_DEPRECATED_EQUALITY)
+
+#if defined(__EDG__)
+#elif defined(_MSC_VER) || defined(__BORLANDC__) || defined(__DMC__)
+#pragma message("Warning: BOOST_UNORDERED_DEPRECATED_EQUALITY is no longer supported.")
+#elif defined(__GNUC__) || defined(__HP_aCC) || \
+ defined(__SUNPRO_CC) || defined(__IBMCPP__)
+#warning "BOOST_UNORDERED_DEPRECATED_EQUALITY is no longer supported."
+#endif
+
+#endif
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ // convert double to std::size_t
+
+ inline std::size_t double_to_size(double f)
+ {
+ return f >= static_cast<double>(
+ (std::numeric_limits<std::size_t>::max)()) ?
+ (std::numeric_limits<std::size_t>::max)() :
+ static_cast<std::size_t>(f);
+ }
+
+ // The space used to store values in a node.
+
+ template <typename ValueType>
+ struct value_base
+ {
+ typedef ValueType value_type;
+
+ typename ndnboost::aligned_storage<
+ sizeof(value_type),
+ ndnboost::alignment_of<value_type>::value>::type data_;
+
+ void* address() {
+ return this;
+ }
+
+ value_type& value() {
+ return *(ValueType*) this;
+ }
+
+ value_type* value_ptr() {
+ return (ValueType*) this;
+ }
+
+ private:
+
+ value_base& operator=(value_base const&);
+ };
+
+ template <typename NodeAlloc>
+ struct copy_nodes
+ {
+ typedef ndnboost::unordered::detail::allocator_traits<NodeAlloc>
+ node_allocator_traits;
+
+ node_constructor<NodeAlloc> constructor;
+
+ explicit copy_nodes(NodeAlloc& a) : constructor(a) {}
+
+ typename node_allocator_traits::pointer create(
+ typename node_allocator_traits::value_type::value_type const& v)
+ {
+ constructor.construct_with_value2(v);
+ return constructor.release();
+ }
+ };
+
+ template <typename NodeAlloc>
+ struct move_nodes
+ {
+ typedef ndnboost::unordered::detail::allocator_traits<NodeAlloc>
+ node_allocator_traits;
+
+ node_constructor<NodeAlloc> constructor;
+
+ explicit move_nodes(NodeAlloc& a) : constructor(a) {}
+
+ typename node_allocator_traits::pointer create(
+ typename node_allocator_traits::value_type::value_type& v)
+ {
+ constructor.construct_with_value2(ndnboost::move(v));
+ return constructor.release();
+ }
+ };
+
+ template <typename Buckets>
+ struct assign_nodes
+ {
+ node_holder<typename Buckets::node_allocator> holder;
+
+ explicit assign_nodes(Buckets& b) : holder(b) {}
+
+ typename Buckets::node_pointer create(
+ typename Buckets::value_type const& v)
+ {
+ return holder.copy_of(v);
+ }
+ };
+
+ template <typename Buckets>
+ struct move_assign_nodes
+ {
+ node_holder<typename Buckets::node_allocator> holder;
+
+ explicit move_assign_nodes(Buckets& b) : holder(b) {}
+
+ typename Buckets::node_pointer create(
+ typename Buckets::value_type& v)
+ {
+ return holder.move_copy_of(v);
+ }
+ };
+
+ template <typename Types>
+ struct table :
+ ndnboost::unordered::detail::functions<
+ typename Types::hasher,
+ typename Types::key_equal>
+ {
+ private:
+ table(table const&);
+ table& operator=(table const&);
+ public:
+ typedef typename Types::node node;
+ typedef typename Types::bucket bucket;
+ typedef typename Types::hasher hasher;
+ typedef typename Types::key_equal key_equal;
+ typedef typename Types::key_type key_type;
+ typedef typename Types::extractor extractor;
+ typedef typename Types::value_type value_type;
+ typedef typename Types::table table_impl;
+ typedef typename Types::link_pointer link_pointer;
+ typedef typename Types::policy policy;
+
+ typedef ndnboost::unordered::detail::functions<
+ typename Types::hasher,
+ typename Types::key_equal> functions;
+ typedef typename functions::set_hash_functions set_hash_functions;
+
+ typedef typename Types::allocator allocator;
+ typedef typename ndnboost::unordered::detail::
+ rebind_wrap<allocator, node>::type node_allocator;
+ typedef typename ndnboost::unordered::detail::
+ rebind_wrap<allocator, bucket>::type bucket_allocator;
+ typedef ndnboost::unordered::detail::allocator_traits<node_allocator>
+ node_allocator_traits;
+ typedef ndnboost::unordered::detail::allocator_traits<bucket_allocator>
+ bucket_allocator_traits;
+ typedef typename node_allocator_traits::pointer
+ node_pointer;
+ typedef typename node_allocator_traits::const_pointer
+ const_node_pointer;
+ typedef typename bucket_allocator_traits::pointer
+ bucket_pointer;
+ typedef ndnboost::unordered::detail::node_constructor<node_allocator>
+ node_constructor;
+
+ typedef ndnboost::unordered::iterator_detail::
+ iterator<node> iterator;
+ typedef ndnboost::unordered::iterator_detail::
+ c_iterator<node, const_node_pointer> c_iterator;
+ typedef ndnboost::unordered::iterator_detail::
+ l_iterator<node, policy> l_iterator;
+ typedef ndnboost::unordered::iterator_detail::
+ cl_iterator<node, const_node_pointer, policy> cl_iterator;
+
+ ////////////////////////////////////////////////////////////////////////
+ // Members
+
+ ndnboost::unordered::detail::compressed<bucket_allocator, node_allocator>
+ allocators_;
+ std::size_t bucket_count_;
+ std::size_t size_;
+ float mlf_;
+ std::size_t max_load_;
+ bucket_pointer buckets_;
+
+ ////////////////////////////////////////////////////////////////////////
+ // Data access
+
+ bucket_allocator const& bucket_alloc() const
+ {
+ return allocators_.first();
+ }
+
+ node_allocator const& node_alloc() const
+ {
+ return allocators_.second();
+ }
+
+ bucket_allocator& bucket_alloc()
+ {
+ return allocators_.first();
+ }
+
+ node_allocator& node_alloc()
+ {
+ return allocators_.second();
+ }
+
+ std::size_t max_bucket_count() const
+ {
+ // -1 to account for the start bucket.
+ return policy::prev_bucket_count(
+ bucket_allocator_traits::max_size(bucket_alloc()) - 1);
+ }
+
+ bucket_pointer get_bucket(std::size_t bucket_index) const
+ {
+ BOOST_ASSERT(buckets_);
+ return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
+ }
+
+ link_pointer get_previous_start() const
+ {
+ return get_bucket(bucket_count_)->first_from_start();
+ }
+
+ link_pointer get_previous_start(std::size_t bucket_index) const
+ {
+ return get_bucket(bucket_index)->next_;
+ }
+
+ iterator begin() const
+ {
+ return size_ ? iterator(get_previous_start()->next_) : iterator();
+ }
+
+ iterator begin(std::size_t bucket_index) const
+ {
+ if (!size_) return iterator();
+ link_pointer prev = get_previous_start(bucket_index);
+ return prev ? iterator(prev->next_) : iterator();
+ }
+
+ std::size_t hash_to_bucket(std::size_t hash) const
+ {
+ return policy::to_bucket(bucket_count_, hash);
+ }
+
+ float load_factor() const
+ {
+ BOOST_ASSERT(bucket_count_ != 0);
+ return static_cast<float>(size_)
+ / static_cast<float>(bucket_count_);
+ }
+
+ std::size_t bucket_size(std::size_t index) const
+ {
+ iterator it = begin(index);
+ if (!it.node_) return 0;
+
+ std::size_t count = 0;
+ while(it.node_ && hash_to_bucket(it.node_->hash_) == index)
+ {
+ ++count;
+ ++it;
+ }
+
+ return count;
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Load methods
+
+ std::size_t max_size() const
+ {
+ using namespace std;
+
+ // size < mlf_ * count
+ return ndnboost::unordered::detail::double_to_size(ceil(
+ static_cast<double>(mlf_) *
+ static_cast<double>(max_bucket_count())
+ )) - 1;
+ }
+
+ void recalculate_max_load()
+ {
+ using namespace std;
+
+ // From 6.3.1/13:
+ // Only resize when size >= mlf_ * count
+ max_load_ = buckets_ ? ndnboost::unordered::detail::double_to_size(ceil(
+ static_cast<double>(mlf_) *
+ static_cast<double>(bucket_count_)
+ )) : 0;
+
+ }
+
+ void max_load_factor(float z)
+ {
+ BOOST_ASSERT(z > 0);
+ mlf_ = (std::max)(z, minimum_max_load_factor);
+ recalculate_max_load();
+ }
+
+ std::size_t min_buckets_for_size(std::size_t size) const
+ {
+ BOOST_ASSERT(mlf_ >= minimum_max_load_factor);
+
+ using namespace std;
+
+ // From 6.3.1/13:
+ // size < mlf_ * count
+ // => count > size / mlf_
+ //
+ // Or from rehash post-condition:
+ // count > size / mlf_
+
+ return policy::new_bucket_count(
+ ndnboost::unordered::detail::double_to_size(floor(
+ static_cast<double>(size) /
+ static_cast<double>(mlf_))) + 1);
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Constructors
+
+ table(std::size_t num_buckets,
+ hasher const& hf,
+ key_equal const& eq,
+ node_allocator const& a) :
+ functions(hf, eq),
+ allocators_(a,a),
+ bucket_count_(policy::new_bucket_count(num_buckets)),
+ size_(0),
+ mlf_(1.0f),
+ max_load_(0),
+ buckets_()
+ {}
+
+ table(table const& x, node_allocator const& a) :
+ functions(x),
+ allocators_(a,a),
+ bucket_count_(x.min_buckets_for_size(x.size_)),
+ size_(0),
+ mlf_(x.mlf_),
+ max_load_(0),
+ buckets_()
+ {}
+
+ table(table& x, ndnboost::unordered::detail::move_tag m) :
+ functions(x, m),
+ allocators_(x.allocators_, m),
+ bucket_count_(x.bucket_count_),
+ size_(x.size_),
+ mlf_(x.mlf_),
+ max_load_(x.max_load_),
+ buckets_(x.buckets_)
+ {
+ x.buckets_ = bucket_pointer();
+ x.size_ = 0;
+ x.max_load_ = 0;
+ }
+
+ table(table& x, node_allocator const& a,
+ ndnboost::unordered::detail::move_tag m) :
+ functions(x, m),
+ allocators_(a, a),
+ bucket_count_(x.bucket_count_),
+ size_(0),
+ mlf_(x.mlf_),
+ max_load_(x.max_load_),
+ buckets_()
+ {}
+
+ ////////////////////////////////////////////////////////////////////////
+ // Initialisation.
+
+ void init(table const& x)
+ {
+ if (x.size_) {
+ create_buckets(bucket_count_);
+ copy_nodes<node_allocator> copy(node_alloc());
+ table_impl::fill_buckets(x.begin(), *this, copy);
+ }
+ }
+
+ void move_init(table& x)
+ {
+ if(node_alloc() == x.node_alloc()) {
+ move_buckets_from(x);
+ }
+ else if(x.size_) {
+ // TODO: Could pick new bucket size?
+ create_buckets(bucket_count_);
+
+ move_nodes<node_allocator> move(node_alloc());
+ node_holder<node_allocator> nodes(x);
+ table_impl::fill_buckets(nodes.begin(), *this, move);
+ }
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Create buckets
+
+ void create_buckets(std::size_t new_count)
+ {
+ ndnboost::unordered::detail::array_constructor<bucket_allocator>
+ constructor(bucket_alloc());
+
+ // Creates an extra bucket to act as the start node.
+ constructor.construct(bucket(), new_count + 1);
+
+ if (buckets_)
+ {
+ // Copy the nodes to the new buckets, including the dummy
+ // node if there is one.
+ (constructor.get() +
+ static_cast<std::ptrdiff_t>(new_count))->next_ =
+ (buckets_ + static_cast<std::ptrdiff_t>(
+ bucket_count_))->next_;
+ destroy_buckets();
+ }
+ else if (bucket::extra_node)
+ {
+ node_constructor a(node_alloc());
+ a.construct();
+
+ (constructor.get() +
+ static_cast<std::ptrdiff_t>(new_count))->next_ =
+ a.release();
+ }
+
+ bucket_count_ = new_count;
+ buckets_ = constructor.release();
+ recalculate_max_load();
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Swap and Move
+
+ void swap_allocators(table& other, false_type)
+ {
+ // According to 23.2.1.8, if propagate_on_container_swap is
+ // false the behaviour is undefined unless the allocators
+ // are equal.
+ BOOST_ASSERT(node_alloc() == other.node_alloc());
+ }
+
+ void swap_allocators(table& other, true_type)
+ {
+ allocators_.swap(other.allocators_);
+ }
+
+ // Only swaps the allocators if propagate_on_container_swap
+ void swap(table& x)
+ {
+ set_hash_functions op1(*this, x);
+ set_hash_functions op2(x, *this);
+
+ // I think swap can throw if Propagate::value,
+ // since the allocators' swap can throw. Not sure though.
+ swap_allocators(x,
+ ndnboost::unordered::detail::integral_constant<bool,
+ allocator_traits<node_allocator>::
+ propagate_on_container_swap::value>());
+
+ ndnboost::swap(buckets_, x.buckets_);
+ ndnboost::swap(bucket_count_, x.bucket_count_);
+ ndnboost::swap(size_, x.size_);
+ std::swap(mlf_, x.mlf_);
+ std::swap(max_load_, x.max_load_);
+ op1.commit();
+ op2.commit();
+ }
+
+ void move_buckets_from(table& other)
+ {
+ BOOST_ASSERT(node_alloc() == other.node_alloc());
+ BOOST_ASSERT(!buckets_);
+ buckets_ = other.buckets_;
+ bucket_count_ = other.bucket_count_;
+ size_ = other.size_;
+ other.buckets_ = bucket_pointer();
+ other.size_ = 0;
+ other.max_load_ = 0;
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Delete/destruct
+
+ ~table()
+ {
+ delete_buckets();
+ }
+
+ void delete_node(link_pointer prev)
+ {
+ node_pointer n = static_cast<node_pointer>(prev->next_);
+ prev->next_ = n->next_;
+
+ ndnboost::unordered::detail::destroy_value_impl(node_alloc(),
+ n->value_ptr());
+ node_allocator_traits::destroy(node_alloc(),
+ ndnboost::addressof(*n));
+ node_allocator_traits::deallocate(node_alloc(), n, 1);
+ --size_;
+ }
+
+ std::size_t delete_nodes(link_pointer prev, link_pointer end)
+ {
+ BOOST_ASSERT(prev->next_ != end);
+
+ std::size_t count = 0;
+
+ do {
+ delete_node(prev);
+ ++count;
+ } while (prev->next_ != end);
+
+ return count;
+ }
+
+ void delete_buckets()
+ {
+ if(buckets_) {
+ if (size_) delete_nodes(get_previous_start(), link_pointer());
+
+ if (bucket::extra_node) {
+ node_pointer n = static_cast<node_pointer>(
+ get_bucket(bucket_count_)->next_);
+ node_allocator_traits::destroy(node_alloc(),
+ ndnboost::addressof(*n));
+ node_allocator_traits::deallocate(node_alloc(), n, 1);
+ }
+
+ destroy_buckets();
+ buckets_ = bucket_pointer();
+ max_load_ = 0;
+ }
+
+ BOOST_ASSERT(!size_);
+ }
+
+ void clear()
+ {
+ if (!size_) return;
+
+ delete_nodes(get_previous_start(), link_pointer());
+ clear_buckets();
+
+ BOOST_ASSERT(!size_);
+ }
+
+ void clear_buckets()
+ {
+ bucket_pointer end = get_bucket(bucket_count_);
+ for(bucket_pointer it = buckets_; it != end; ++it)
+ {
+ it->next_ = node_pointer();
+ }
+ }
+
+ void destroy_buckets()
+ {
+ bucket_pointer end = get_bucket(bucket_count_ + 1);
+ for(bucket_pointer it = buckets_; it != end; ++it)
+ {
+ bucket_allocator_traits::destroy(bucket_alloc(),
+ ndnboost::addressof(*it));
+ }
+
+ bucket_allocator_traits::deallocate(bucket_alloc(),
+ buckets_, bucket_count_ + 1);
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Fix buckets after delete
+ //
+
+ std::size_t fix_bucket(std::size_t bucket_index, link_pointer prev)
+ {
+ link_pointer end = prev->next_;
+ std::size_t bucket_index2 = bucket_index;
+
+ if (end)
+ {
+ bucket_index2 = hash_to_bucket(
+ static_cast<node_pointer>(end)->hash_);
+
+ // If begin and end are in the same bucket, then
+ // there's nothing to do.
+ if (bucket_index == bucket_index2) return bucket_index2;
+
+ // Update the bucket containing end.
+ get_bucket(bucket_index2)->next_ = prev;
+ }
+
+ // Check if this bucket is now empty.
+ bucket_pointer this_bucket = get_bucket(bucket_index);
+ if (this_bucket->next_ == prev)
+ this_bucket->next_ = link_pointer();
+
+ return bucket_index2;
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Assignment
+
+ void assign(table const& x)
+ {
+ if (this != ndnboost::addressof(x))
+ {
+ assign(x,
+ ndnboost::unordered::detail::integral_constant<bool,
+ allocator_traits<node_allocator>::
+ propagate_on_container_copy_assignment::value>());
+ }
+ }
+
+ void assign(table const& x, false_type)
+ {
+ // Strong exception safety.
+ set_hash_functions new_func_this(*this, x);
+ new_func_this.commit();
+ mlf_ = x.mlf_;
+ recalculate_max_load();
+
+ if (!size_ && !x.size_) return;
+
+ if (x.size_ >= max_load_) {
+ create_buckets(min_buckets_for_size(x.size_));
+ }
+ else {
+ clear_buckets();
+ }
+
+ // assign_nodes takes ownership of the container's elements,
+ // assigning to them if possible, and deleting any that are
+ // left over.
+ assign_nodes<table> assign(*this);
+ table_impl::fill_buckets(x.begin(), *this, assign);
+ }
+
+ void assign(table const& x, true_type)
+ {
+ if (node_alloc() == x.node_alloc()) {
+ allocators_.assign(x.allocators_);
+ assign(x, false_type());
+ }
+ else {
+ set_hash_functions new_func_this(*this, x);
+
+ // Delete everything with current allocators before assigning
+ // the new ones.
+ delete_buckets();
+ allocators_.assign(x.allocators_);
+
+ // Copy over other data, all no throw.
+ new_func_this.commit();
+ mlf_ = x.mlf_;
+ bucket_count_ = min_buckets_for_size(x.size_);
+ max_load_ = 0;
+
+ // Finally copy the elements.
+ if (x.size_) {
+ create_buckets(bucket_count_);
+ copy_nodes<node_allocator> copy(node_alloc());
+ table_impl::fill_buckets(x.begin(), *this, copy);
+ }
+ }
+ }
+
+ void move_assign(table& x)
+ {
+ if (this != ndnboost::addressof(x))
+ {
+ move_assign(x,
+ ndnboost::unordered::detail::integral_constant<bool,
+ allocator_traits<node_allocator>::
+ propagate_on_container_move_assignment::value>());
+ }
+ }
+
+ void move_assign(table& x, true_type)
+ {
+ delete_buckets();
+ allocators_.move_assign(x.allocators_);
+ move_assign_no_alloc(x);
+ }
+
+ void move_assign(table& x, false_type)
+ {
+ if (node_alloc() == x.node_alloc()) {
+ delete_buckets();
+ move_assign_no_alloc(x);
+ }
+ else {
+ set_hash_functions new_func_this(*this, x);
+ new_func_this.commit();
+ mlf_ = x.mlf_;
+ recalculate_max_load();
+
+ if (!size_ && !x.size_) return;
+
+ if (x.size_ >= max_load_) {
+ create_buckets(min_buckets_for_size(x.size_));
+ }
+ else {
+ clear_buckets();
+ }
+
+ // move_assign_nodes takes ownership of the container's
+ // elements, assigning to them if possible, and deleting
+ // any that are left over.
+ move_assign_nodes<table> assign(*this);
+ node_holder<node_allocator> nodes(x);
+ table_impl::fill_buckets(nodes.begin(), *this, assign);
+ }
+ }
+
+ void move_assign_no_alloc(table& x)
+ {
+ set_hash_functions new_func_this(*this, x);
+ // No throw from here.
+ mlf_ = x.mlf_;
+ max_load_ = x.max_load_;
+ move_buckets_from(x);
+ new_func_this.commit();
+ }
+
+ // Accessors
+
+ key_type const& get_key(value_type const& x) const
+ {
+ return extractor::extract(x);
+ }
+
+ std::size_t hash(key_type const& k) const
+ {
+ return policy::apply_hash(this->hash_function(), k);
+ }
+
+ // Find Node
+
+ template <typename Key, typename Hash, typename Pred>
+ iterator generic_find_node(
+ Key const& k,
+ Hash const& hf,
+ Pred const& eq) const
+ {
+ return static_cast<table_impl const*>(this)->
+ find_node_impl(policy::apply_hash(hf, k), k, eq);
+ }
+
+ iterator find_node(
+ std::size_t key_hash,
+ key_type const& k) const
+ {
+ return static_cast<table_impl const*>(this)->
+ find_node_impl(key_hash, k, this->key_eq());
+ }
+
+ iterator find_node(key_type const& k) const
+ {
+ return static_cast<table_impl const*>(this)->
+ find_node_impl(hash(k), k, this->key_eq());
+ }
+
+ iterator find_matching_node(iterator n) const
+ {
+ // TODO: Does this apply to C++11?
+ //
+ // For some stupid reason, I decided to support equality comparison
+ // when different hash functions are used. So I can't use the hash
+ // value from the node here.
+
+ return find_node(get_key(*n));
+ }
+
+ // Reserve and rehash
+
+ void reserve_for_insert(std::size_t);
+ void rehash(std::size_t);
+ void reserve(std::size_t);
+ };
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Reserve & Rehash
+
+ // basic exception safety
+ template <typename Types>
+ inline void table<Types>::reserve_for_insert(std::size_t size)
+ {
+ if (!buckets_) {
+ create_buckets((std::max)(bucket_count_,
+ min_buckets_for_size(size)));
+ }
+ // According to the standard this should be 'size >= max_load_',
+ // but I think this is better, defect report filed.
+ else if(size > max_load_) {
+ std::size_t num_buckets
+ = min_buckets_for_size((std::max)(size,
+ size_ + (size_ >> 1)));
+
+ if (num_buckets != bucket_count_)
+ static_cast<table_impl*>(this)->rehash_impl(num_buckets);
+ }
+ }
+
+ // if hash function throws, basic exception safety
+ // strong otherwise.
+
+ template <typename Types>
+ inline void table<Types>::rehash(std::size_t min_buckets)
+ {
+ using namespace std;
+
+ if(!size_) {
+ delete_buckets();
+ bucket_count_ = policy::new_bucket_count(min_buckets);
+ }
+ else {
+ min_buckets = policy::new_bucket_count((std::max)(min_buckets,
+ ndnboost::unordered::detail::double_to_size(floor(
+ static_cast<double>(size_) /
+ static_cast<double>(mlf_))) + 1));
+
+ if(min_buckets != bucket_count_)
+ static_cast<table_impl*>(this)->rehash_impl(min_buckets);
+ }
+ }
+
+ template <typename Types>
+ inline void table<Types>::reserve(std::size_t num_elements)
+ {
+ rehash(static_cast<std::size_t>(
+ std::ceil(static_cast<double>(num_elements) / mlf_)));
+ }
+}}}
+
+#if defined(BOOST_MSVC)
+#pragma warning(pop)
+#endif
+
+#endif
diff --git a/ndnboost/unordered/detail/unique.hpp b/ndnboost/unordered/detail/unique.hpp
new file mode 100644
index 0000000..44fc04d
--- /dev/null
+++ b/ndnboost/unordered/detail/unique.hpp
@@ -0,0 +1,622 @@
+
+// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
+// Copyright (C) 2005-2011 Daniel James
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1020)
+# pragma once
+#endif
+
+#include <ndnboost/unordered/detail/table.hpp>
+#include <ndnboost/unordered/detail/extract_key.hpp>
+#include <ndnboost/throw_exception.hpp>
+#include <stdexcept>
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ template <typename A, typename T> struct unique_node;
+ template <typename T> struct ptr_node;
+ template <typename Types> struct table_impl;
+
+ template <typename A, typename T>
+ struct unique_node :
+ ndnboost::unordered::detail::value_base<T>
+ {
+ typedef typename ::ndnboost::unordered::detail::rebind_wrap<
+ A, unique_node<A, T> >::type::pointer node_pointer;
+ typedef node_pointer link_pointer;
+
+ link_pointer next_;
+ std::size_t hash_;
+
+ unique_node() :
+ next_(),
+ hash_(0)
+ {}
+
+ void init(node_pointer)
+ {
+ }
+
+ private:
+ unique_node& operator=(unique_node const&);
+ };
+
+ template <typename T>
+ struct ptr_node :
+ ndnboost::unordered::detail::value_base<T>,
+ ndnboost::unordered::detail::ptr_bucket
+ {
+ typedef ndnboost::unordered::detail::ptr_bucket bucket_base;
+ typedef ptr_node<T>* node_pointer;
+ typedef ptr_bucket* link_pointer;
+
+ std::size_t hash_;
+
+ ptr_node() :
+ bucket_base(),
+ hash_(0)
+ {}
+
+ void init(node_pointer)
+ {
+ }
+
+ private:
+ ptr_node& operator=(ptr_node const&);
+ };
+
+ // If the allocator uses raw pointers use ptr_node
+ // Otherwise use node.
+
+ template <typename A, typename T, typename NodePtr, typename BucketPtr>
+ struct pick_node2
+ {
+ typedef ndnboost::unordered::detail::unique_node<A, T> node;
+
+ typedef typename ndnboost::unordered::detail::allocator_traits<
+ typename ndnboost::unordered::detail::rebind_wrap<A, node>::type
+ >::pointer node_pointer;
+
+ typedef ndnboost::unordered::detail::bucket<node_pointer> bucket;
+ typedef node_pointer link_pointer;
+ };
+
+ template <typename A, typename T>
+ struct pick_node2<A, T,
+ ndnboost::unordered::detail::ptr_node<T>*,
+ ndnboost::unordered::detail::ptr_bucket*>
+ {
+ typedef ndnboost::unordered::detail::ptr_node<T> node;
+ typedef ndnboost::unordered::detail::ptr_bucket bucket;
+ typedef bucket* link_pointer;
+ };
+
+ template <typename A, typename T>
+ struct pick_node
+ {
+ typedef ndnboost::unordered::detail::allocator_traits<
+ typename ndnboost::unordered::detail::rebind_wrap<A,
+ ndnboost::unordered::detail::ptr_node<T> >::type
+ > tentative_node_traits;
+
+ typedef ndnboost::unordered::detail::allocator_traits<
+ typename ndnboost::unordered::detail::rebind_wrap<A,
+ ndnboost::unordered::detail::ptr_bucket >::type
+ > tentative_bucket_traits;
+
+ typedef pick_node2<A, T,
+ typename tentative_node_traits::pointer,
+ typename tentative_bucket_traits::pointer> pick;
+
+ typedef typename pick::node node;
+ typedef typename pick::bucket bucket;
+ typedef typename pick::link_pointer link_pointer;
+ };
+
+ template <typename A, typename T, typename H, typename P>
+ struct set
+ {
+ typedef ndnboost::unordered::detail::set<A, T, H, P> types;
+
+ typedef A allocator;
+ typedef T value_type;
+ typedef H hasher;
+ typedef P key_equal;
+ typedef T key_type;
+
+ typedef ndnboost::unordered::detail::allocator_traits<allocator> traits;
+ typedef ndnboost::unordered::detail::pick_node<allocator, value_type> pick;
+ typedef typename pick::node node;
+ typedef typename pick::bucket bucket;
+ typedef typename pick::link_pointer link_pointer;
+
+ typedef ndnboost::unordered::detail::table_impl<types> table;
+ typedef ndnboost::unordered::detail::set_extractor<value_type> extractor;
+
+ typedef ndnboost::unordered::detail::pick_policy::type policy;
+ };
+
+ template <typename A, typename K, typename M, typename H, typename P>
+ struct map
+ {
+ typedef ndnboost::unordered::detail::map<A, K, M, H, P> types;
+
+ typedef A allocator;
+ typedef std::pair<K const, M> value_type;
+ typedef H hasher;
+ typedef P key_equal;
+ typedef K key_type;
+
+ typedef ndnboost::unordered::detail::allocator_traits<allocator>
+ traits;
+ typedef ndnboost::unordered::detail::pick_node<allocator, value_type> pick;
+ typedef typename pick::node node;
+ typedef typename pick::bucket bucket;
+ typedef typename pick::link_pointer link_pointer;
+
+ typedef ndnboost::unordered::detail::table_impl<types> table;
+ typedef ndnboost::unordered::detail::map_extractor<key_type, value_type>
+ extractor;
+
+ typedef ndnboost::unordered::detail::pick_policy::type policy;
+ };
+
+ template <typename Types>
+ struct table_impl : ndnboost::unordered::detail::table<Types>
+ {
+ typedef ndnboost::unordered::detail::table<Types> table;
+ typedef typename table::value_type value_type;
+ typedef typename table::bucket bucket;
+ typedef typename table::policy policy;
+ typedef typename table::node_pointer node_pointer;
+ typedef typename table::node_allocator node_allocator;
+ typedef typename table::node_allocator_traits node_allocator_traits;
+ typedef typename table::bucket_pointer bucket_pointer;
+ typedef typename table::link_pointer link_pointer;
+ typedef typename table::hasher hasher;
+ typedef typename table::key_equal key_equal;
+ typedef typename table::key_type key_type;
+ typedef typename table::node_constructor node_constructor;
+ typedef typename table::extractor extractor;
+ typedef typename table::iterator iterator;
+ typedef typename table::c_iterator c_iterator;
+
+ typedef std::pair<iterator, bool> emplace_return;
+
+ // Constructors
+
+ table_impl(std::size_t n,
+ hasher const& hf,
+ key_equal const& eq,
+ node_allocator const& a)
+ : table(n, hf, eq, a)
+ {}
+
+ table_impl(table_impl const& x)
+ : table(x, node_allocator_traits::
+ select_on_container_copy_construction(x.node_alloc()))
+ {
+ this->init(x);
+ }
+
+ table_impl(table_impl const& x,
+ node_allocator const& a)
+ : table(x, a)
+ {
+ this->init(x);
+ }
+
+ table_impl(table_impl& x,
+ ndnboost::unordered::detail::move_tag m)
+ : table(x, m)
+ {}
+
+ table_impl(table_impl& x,
+ node_allocator const& a,
+ ndnboost::unordered::detail::move_tag m)
+ : table(x, a, m)
+ {
+ this->move_init(x);
+ }
+
+ // Accessors
+
+ template <class Key, class Pred>
+ iterator find_node_impl(
+ std::size_t key_hash,
+ Key const& k,
+ Pred const& eq) const
+ {
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
+ iterator n = this->begin(bucket_index);
+
+ for (;;)
+ {
+ if (!n.node_) return n;
+
+ std::size_t node_hash = n.node_->hash_;
+ if (key_hash == node_hash)
+ {
+ if (eq(k, this->get_key(*n)))
+ return n;
+ }
+ else
+ {
+ if (this->hash_to_bucket(node_hash) != bucket_index)
+ return iterator();
+ }
+
+ ++n;
+ }
+ }
+
+ std::size_t count(key_type const& k) const
+ {
+ return this->find_node(k).node_ ? 1 : 0;
+ }
+
+ value_type& at(key_type const& k) const
+ {
+ if (this->size_) {
+ iterator it = this->find_node(k);
+ if (it.node_) return *it;
+ }
+
+ ndnboost::throw_exception(
+ std::out_of_range("Unable to find key in unordered_map."));
+ }
+
+ std::pair<iterator, iterator>
+ equal_range(key_type const& k) const
+ {
+ iterator n = this->find_node(k);
+ iterator n2 = n;
+ if (n2.node_) ++n2;
+ return std::make_pair(n, n2);
+ }
+
+ // equals
+
+ bool equals(table_impl const& other) const
+ {
+ if(this->size_ != other.size_) return false;
+
+ for(iterator n1 = this->begin(); n1.node_; ++n1)
+ {
+ iterator n2 = other.find_matching_node(n1);
+
+ if (!n2.node_ || *n1 != *n2)
+ return false;
+ }
+
+ return true;
+ }
+
+ // Emplace/Insert
+
+ inline iterator add_node(
+ node_constructor& a,
+ std::size_t key_hash)
+ {
+ node_pointer n = a.release();
+ n->hash_ = key_hash;
+
+ bucket_pointer b = this->get_bucket(this->hash_to_bucket(key_hash));
+
+ if (!b->next_)
+ {
+ link_pointer start_node = this->get_previous_start();
+
+ if (start_node->next_) {
+ this->get_bucket(this->hash_to_bucket(
+ static_cast<node_pointer>(start_node->next_)->hash_)
+ )->next_ = n;
+ }
+
+ b->next_ = start_node;
+ n->next_ = start_node->next_;
+ start_node->next_ = n;
+ }
+ else
+ {
+ n->next_ = b->next_->next_;
+ b->next_->next_ = n;
+ }
+
+ ++this->size_;
+ return iterator(n);
+ }
+
+ value_type& operator[](key_type const& k)
+ {
+ typedef typename value_type::second_type mapped_type;
+
+ std::size_t key_hash = this->hash(k);
+ iterator pos = this->find_node(key_hash, k);
+
+ if (pos.node_) return *pos;
+
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(this->node_alloc());
+ a.construct_with_value(BOOST_UNORDERED_EMPLACE_ARGS3(
+ ndnboost::unordered::piecewise_construct,
+ ndnboost::make_tuple(k),
+ ndnboost::make_tuple()));
+
+ this->reserve_for_insert(this->size_ + 1);
+ return *add_node(a, key_hash);
+ }
+
+#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+# if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+ emplace_return emplace(ndnboost::unordered::detail::emplace_args1<
+ ndnboost::unordered::detail::please_ignore_this_overload> const&)
+ {
+ BOOST_ASSERT(false);
+ return emplace_return(this->begin(), false);
+ }
+# else
+ emplace_return emplace(
+ ndnboost::unordered::detail::please_ignore_this_overload const&)
+ {
+ BOOST_ASSERT(false);
+ return emplace_return(this->begin(), false);
+ }
+# endif
+#endif
+
+ template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ emplace_return emplace(BOOST_UNORDERED_EMPLACE_ARGS)
+ {
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+ return emplace_impl(
+ extractor::extract(BOOST_UNORDERED_EMPLACE_FORWARD),
+ BOOST_UNORDERED_EMPLACE_FORWARD);
+#else
+ return emplace_impl(
+ extractor::extract(args.a0, args.a1),
+ BOOST_UNORDERED_EMPLACE_FORWARD);
+#endif
+ }
+
+#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+ template <typename A0>
+ emplace_return emplace(
+ ndnboost::unordered::detail::emplace_args1<A0> const& args)
+ {
+ return emplace_impl(extractor::extract(args.a0), args);
+ }
+#endif
+
+ template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ emplace_return emplace_impl(key_type const& k,
+ BOOST_UNORDERED_EMPLACE_ARGS)
+ {
+ std::size_t key_hash = this->hash(k);
+ iterator pos = this->find_node(key_hash, k);
+
+ if (pos.node_) return emplace_return(pos, false);
+
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(this->node_alloc());
+ a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ this->reserve_for_insert(this->size_ + 1);
+ return emplace_return(this->add_node(a, key_hash), true);
+ }
+
+ emplace_return emplace_impl_with_node(node_constructor& a)
+ {
+ key_type const& k = this->get_key(a.value());
+ std::size_t key_hash = this->hash(k);
+ iterator pos = this->find_node(key_hash, k);
+
+ if (pos.node_) return emplace_return(pos, false);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ this->reserve_for_insert(this->size_ + 1);
+ return emplace_return(this->add_node(a, key_hash), true);
+ }
+
+ template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
+ emplace_return emplace_impl(no_key, BOOST_UNORDERED_EMPLACE_ARGS)
+ {
+ // Don't have a key, so construct the node first in order
+ // to be able to lookup the position.
+ node_constructor a(this->node_alloc());
+ a.construct_with_value(BOOST_UNORDERED_EMPLACE_FORWARD);
+ return emplace_impl_with_node(a);
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Insert range methods
+ //
+ // if hash function throws, or inserting > 1 element, basic exception
+ // safety strong otherwise
+
+ template <class InputIt>
+ void insert_range(InputIt i, InputIt j)
+ {
+ if(i != j)
+ return insert_range_impl(extractor::extract(*i), i, j);
+ }
+
+ template <class InputIt>
+ void insert_range_impl(key_type const& k, InputIt i, InputIt j)
+ {
+ node_constructor a(this->node_alloc());
+
+ insert_range_impl2(a, k, i, j);
+
+ while(++i != j) {
+ // Note: can't use get_key as '*i' might not be value_type - it
+ // could be a pair with first_types as key_type without const or
+ // a different second_type.
+ //
+ // TODO: Might be worth storing the value_type instead of the
+ // key here. Could be more efficient if '*i' is expensive. Could
+ // be less efficient if copying the full value_type is
+ // expensive.
+ insert_range_impl2(a, extractor::extract(*i), i, j);
+ }
+ }
+
+ template <class InputIt>
+ void insert_range_impl2(node_constructor& a, key_type const& k,
+ InputIt i, InputIt j)
+ {
+ // No side effects in this initial code
+ std::size_t key_hash = this->hash(k);
+ iterator pos = this->find_node(key_hash, k);
+
+ if (!pos.node_) {
+ a.construct_with_value2(*i);
+ if(this->size_ + 1 > this->max_load_)
+ this->reserve_for_insert(this->size_ +
+ ndnboost::unordered::detail::insert_size(i, j));
+
+ // Nothing after this point can throw.
+ this->add_node(a, key_hash);
+ }
+ }
+
+ template <class InputIt>
+ void insert_range_impl(no_key, InputIt i, InputIt j)
+ {
+ node_constructor a(this->node_alloc());
+
+ do {
+ a.construct_with_value2(*i);
+ emplace_impl_with_node(a);
+ } while(++i != j);
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Erase
+ //
+ // no throw
+
+ std::size_t erase_key(key_type const& k)
+ {
+ if(!this->size_) return 0;
+
+ std::size_t key_hash = this->hash(k);
+ std::size_t bucket_index = this->hash_to_bucket(key_hash);
+ link_pointer prev = this->get_previous_start(bucket_index);
+ if (!prev) return 0;
+
+ for (;;)
+ {
+ if (!prev->next_) return 0;
+ std::size_t node_hash =
+ static_cast<node_pointer>(prev->next_)->hash_;
+ if (this->hash_to_bucket(node_hash) != bucket_index)
+ return 0;
+ if (node_hash == key_hash &&
+ this->key_eq()(k, this->get_key(
+ static_cast<node_pointer>(prev->next_)->value())))
+ break;
+ prev = prev->next_;
+ }
+
+ link_pointer end = static_cast<node_pointer>(prev->next_)->next_;
+
+ std::size_t count = this->delete_nodes(prev, end);
+ this->fix_bucket(bucket_index, prev);
+ return count;
+ }
+
+ iterator erase(c_iterator r)
+ {
+ BOOST_ASSERT(r.node_);
+ iterator next(r.node_);
+ ++next;
+ erase_nodes(r.node_, next.node_);
+ return next;
+ }
+
+ iterator erase_range(c_iterator r1, c_iterator r2)
+ {
+ if (r1 == r2) return iterator(r2.node_);
+ erase_nodes(r1.node_, r2.node_);
+ return iterator(r2.node_);
+ }
+
+ void erase_nodes(node_pointer begin, node_pointer end)
+ {
+ std::size_t bucket_index = this->hash_to_bucket(begin->hash_);
+
+ // Find the node before begin.
+ link_pointer prev = this->get_previous_start(bucket_index);
+ while(prev->next_ != begin) prev = prev->next_;
+
+ // Delete the nodes.
+ do {
+ this->delete_node(prev);
+ bucket_index = this->fix_bucket(bucket_index, prev);
+ } while (prev->next_ != end);
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // fill_buckets
+
+ template <class NodeCreator>
+ static void fill_buckets(iterator n, table& dst,
+ NodeCreator& creator)
+ {
+ link_pointer prev = dst.get_previous_start();
+
+ while (n.node_) {
+ node_pointer node = creator.create(*n);
+ node->hash_ = n.node_->hash_;
+ prev->next_ = node;
+ ++dst.size_;
+ ++n;
+
+ prev = place_in_bucket(dst, prev);
+ }
+ }
+
+ // strong otherwise exception safety
+ void rehash_impl(std::size_t num_buckets)
+ {
+ BOOST_ASSERT(this->buckets_);
+
+ this->create_buckets(num_buckets);
+ link_pointer prev = this->get_previous_start();
+ while (prev->next_)
+ prev = place_in_bucket(*this, prev);
+ }
+
+ // Iterate through the nodes placing them in the correct buckets.
+ // pre: prev->next_ is not null.
+ static link_pointer place_in_bucket(table& dst, link_pointer prev)
+ {
+ node_pointer n = static_cast<node_pointer>(prev->next_);
+ bucket_pointer b = dst.get_bucket(dst.hash_to_bucket(n->hash_));
+
+ if (!b->next_) {
+ b->next_ = prev;
+ return n;
+ }
+ else {
+ prev->next_ = n->next_;
+ n->next_ = b->next_->next_;
+ b->next_->next_ = n;
+ return prev;
+ }
+ }
+ };
+}}}
+
+#endif
diff --git a/ndnboost/unordered/detail/util.hpp b/ndnboost/unordered/detail/util.hpp
new file mode 100644
index 0000000..41f8e42
--- /dev/null
+++ b/ndnboost/unordered/detail/util.hpp
@@ -0,0 +1,260 @@
+
+// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
+// Copyright (C) 2005-2011 Daniel James
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
+
+#if defined(_MSC_VER) && (_MSC_VER >= 1020)
+# pragma once
+#endif
+
+#include <ndnboost/type_traits/is_convertible.hpp>
+#include <ndnboost/type_traits/is_empty.hpp>
+#include <ndnboost/iterator/iterator_categories.hpp>
+#include <ndnboost/utility/enable_if.hpp>
+#include <ndnboost/detail/select_type.hpp>
+#include <ndnboost/move/move.hpp>
+#include <ndnboost/preprocessor/seq/size.hpp>
+#include <ndnboost/preprocessor/seq/enum.hpp>
+#include <ndnboost/swap.hpp>
+
+namespace ndnboost { namespace unordered { namespace detail {
+
+ static const float minimum_max_load_factor = 1e-3f;
+ static const std::size_t default_bucket_count = 11;
+ struct move_tag {};
+ struct empty_emplace {};
+
+ ////////////////////////////////////////////////////////////////////////////
+ // iterator SFINAE
+
+ template <typename I>
+ struct is_forward :
+ ndnboost::is_convertible<
+ typename ndnboost::iterator_traversal<I>::type,
+ ndnboost::forward_traversal_tag>
+ {};
+
+ template <typename I, typename ReturnType>
+ struct enable_if_forward :
+ ndnboost::enable_if_c<
+ ndnboost::unordered::detail::is_forward<I>::value,
+ ReturnType>
+ {};
+
+ template <typename I, typename ReturnType>
+ struct disable_if_forward :
+ ndnboost::disable_if_c<
+ ndnboost::unordered::detail::is_forward<I>::value,
+ ReturnType>
+ {};
+
+ ////////////////////////////////////////////////////////////////////////////
+ // primes
+
+#define BOOST_UNORDERED_PRIMES \
+ (17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \
+ (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \
+ (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \
+ (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \
+ (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \
+ (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \
+ (1610612741ul)(3221225473ul)(4294967291ul)
+
+ template<class T> struct prime_list_template
+ {
+ static std::size_t const value[];
+
+#if !defined(SUNPRO_CC)
+ static std::ptrdiff_t const length;
+#else
+ static std::ptrdiff_t const length
+ = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
+#endif
+ };
+
+ template<class T>
+ std::size_t const prime_list_template<T>::value[] = {
+ BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)
+ };
+
+#if !defined(SUNPRO_CC)
+ template<class T>
+ std::ptrdiff_t const prime_list_template<T>::length
+ = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
+#endif
+
+#undef BOOST_UNORDERED_PRIMES
+
+ typedef prime_list_template<std::size_t> prime_list;
+
+ // no throw
+ inline std::size_t next_prime(std::size_t num) {
+ std::size_t const* const prime_list_begin = prime_list::value;
+ std::size_t const* const prime_list_end = prime_list_begin +
+ prime_list::length;
+ std::size_t const* bound =
+ std::lower_bound(prime_list_begin, prime_list_end, num);
+ if(bound == prime_list_end)
+ bound--;
+ return *bound;
+ }
+
+ // no throw
+ inline std::size_t prev_prime(std::size_t num) {
+ std::size_t const* const prime_list_begin = prime_list::value;
+ std::size_t const* const prime_list_end = prime_list_begin +
+ prime_list::length;
+ std::size_t const* bound =
+ std::upper_bound(prime_list_begin,prime_list_end, num);
+ if(bound != prime_list_begin)
+ bound--;
+ return *bound;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // insert_size/initial_size
+
+#if !defined(BOOST_NO_STD_DISTANCE)
+
+ using ::std::distance;
+
+#else
+
+ template <class ForwardIterator>
+ inline std::size_t distance(ForwardIterator i, ForwardIterator j) {
+ std::size_t x;
+ std::distance(i, j, x);
+ return x;
+ }
+
+#endif
+
+ template <class I>
+ inline typename
+ ndnboost::unordered::detail::enable_if_forward<I, std::size_t>::type
+ insert_size(I i, I j)
+ {
+ return std::distance(i, j);
+ }
+
+ template <class I>
+ inline typename
+ ndnboost::unordered::detail::disable_if_forward<I, std::size_t>::type
+ insert_size(I, I)
+ {
+ return 1;
+ }
+
+ template <class I>
+ inline std::size_t initial_size(I i, I j,
+ std::size_t num_buckets =
+ ndnboost::unordered::detail::default_bucket_count)
+ {
+ // TODO: Why +1?
+ return (std::max)(
+ ndnboost::unordered::detail::insert_size(i, j) + 1,
+ num_buckets);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // compressed
+
+ template <typename T, int Index>
+ struct compressed_base : private T
+ {
+ compressed_base(T const& x) : T(x) {}
+ compressed_base(T& x, move_tag) : T(ndnboost::move(x)) {}
+
+ T& get() { return *this; }
+ T const& get() const { return *this; }
+ };
+
+ template <typename T, int Index>
+ struct uncompressed_base
+ {
+ uncompressed_base(T const& x) : value_(x) {}
+ uncompressed_base(T& x, move_tag) : value_(ndnboost::move(x)) {}
+
+ T& get() { return value_; }
+ T const& get() const { return value_; }
+ private:
+ T value_;
+ };
+
+ template <typename T, int Index>
+ struct generate_base
+ : ndnboost::detail::if_true<
+ ndnboost::is_empty<T>::value
+ >:: BOOST_NESTED_TEMPLATE then<
+ ndnboost::unordered::detail::compressed_base<T, Index>,
+ ndnboost::unordered::detail::uncompressed_base<T, Index>
+ >
+ {};
+
+ template <typename T1, typename T2>
+ struct compressed
+ : private ndnboost::unordered::detail::generate_base<T1, 1>::type,
+ private ndnboost::unordered::detail::generate_base<T2, 2>::type
+ {
+ typedef typename generate_base<T1, 1>::type base1;
+ typedef typename generate_base<T2, 2>::type base2;
+
+ typedef T1 first_type;
+ typedef T2 second_type;
+
+ first_type& first() {
+ return static_cast<base1*>(this)->get();
+ }
+
+ first_type const& first() const {
+ return static_cast<base1 const*>(this)->get();
+ }
+
+ second_type& second() {
+ return static_cast<base2*>(this)->get();
+ }
+
+ second_type const& second() const {
+ return static_cast<base2 const*>(this)->get();
+ }
+
+ template <typename First, typename Second>
+ compressed(First const& x1, Second const& x2)
+ : base1(x1), base2(x2) {}
+
+ compressed(compressed const& x)
+ : base1(x.first()), base2(x.second()) {}
+
+ compressed(compressed& x, move_tag m)
+ : base1(x.first(), m), base2(x.second(), m) {}
+
+ void assign(compressed const& x)
+ {
+ first() = x.first();
+ second() = x.second();
+ }
+
+ void move_assign(compressed& x)
+ {
+ first() = ndnboost::move(x.first());
+ second() = ndnboost::move(x.second());
+ }
+
+ void swap(compressed& x)
+ {
+ ndnboost::swap(first(), x.first());
+ ndnboost::swap(second(), x.second());
+ }
+
+ private:
+ // Prevent assignment just to make use of assign or
+ // move_assign explicit.
+ compressed& operator=(compressed const&);
+ };
+}}}
+
+#endif