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/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