summaryrefslogtreecommitdiff
path: root/boost/unordered/detail/buckets.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/unordered/detail/buckets.hpp')
-rw-r--r--boost/unordered/detail/buckets.hpp519
1 files changed, 451 insertions, 68 deletions
diff --git a/boost/unordered/detail/buckets.hpp b/boost/unordered/detail/buckets.hpp
index 7492220b16..85681a685c 100644
--- a/boost/unordered/detail/buckets.hpp
+++ b/boost/unordered/detail/buckets.hpp
@@ -12,12 +12,13 @@
#endif
#include <boost/unordered/detail/util.hpp>
-#include <boost/unordered/detail/allocator_helpers.hpp>
-#include <boost/unordered/detail/emplace_args.hpp>
+#include <boost/unordered/detail/allocate.hpp>
#include <boost/type_traits/aligned_storage.hpp>
#include <boost/type_traits/alignment_of.hpp>
#include <boost/swap.hpp>
#include <boost/assert.hpp>
+#include <boost/limits.hpp>
+#include <boost/iterator.hpp>
#if defined(BOOST_MSVC)
#pragma warning(push)
@@ -29,7 +30,10 @@ namespace boost { namespace unordered { namespace detail {
template <typename Types> struct table;
template <typename NodePointer> struct bucket;
struct ptr_bucket;
- template <typename A, typename Bucket, typename Node> struct buckets;
+ template <typename A, typename Bucket, typename Node, typename Policy>
+ struct buckets;
+ template <typename Types> struct table_impl;
+ template <typename Types> struct grouped_table_impl;
///////////////////////////////////////////////////////////////////
//
@@ -49,16 +53,14 @@ namespace boost { namespace unordered { namespace detail {
node_allocator& alloc_;
node_pointer node_;
- bool node_constructed_;
- bool value_constructed_;
+ bool constructed_;
public:
node_constructor(node_allocator& n) :
alloc_(n),
node_(),
- node_constructed_(false),
- value_constructed_(false)
+ constructed_(false)
{
}
@@ -69,26 +71,36 @@ namespace boost { namespace unordered { namespace detail {
template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
void construct_value(BOOST_UNORDERED_EMPLACE_ARGS)
{
- BOOST_ASSERT(node_ && node_constructed_ && !value_constructed_);
- boost::unordered::detail::construct_impl(
- node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
- value_constructed_ = true;
+ BOOST_ASSERT(node_ && !constructed_);
+ boost::unordered::detail::construct_node(alloc_,
+ boost::addressof(*node_), BOOST_UNORDERED_EMPLACE_FORWARD);
+ node_->init(static_cast<typename node::link_pointer>(node_));
+ constructed_ = true;
}
template <typename A0>
void construct_value2(BOOST_FWD_REF(A0) a0)
{
- BOOST_ASSERT(node_ && node_constructed_ && !value_constructed_);
- boost::unordered::detail::construct_impl2(
- node_->value_ptr(), boost::forward<A0>(a0));
- value_constructed_ = true;
+ BOOST_ASSERT(node_ && !constructed_);
+
+ boost::unordered::detail::construct_node(alloc_,
+ boost::addressof(*node_),
+ BOOST_UNORDERED_EMPLACE_ARGS1(boost::forward<A0>(a0)));
+
+ constructed_ = true;
+ node_->init(static_cast<typename node::link_pointer>(node_));
}
value_type const& value() const {
- BOOST_ASSERT(node_ && node_constructed_ && value_constructed_);
+ BOOST_ASSERT(node_ && constructed_);
return node_->value();
}
+ node_pointer get()
+ {
+ return node_;
+ }
+
// no throw
node_pointer release()
{
@@ -106,12 +118,8 @@ namespace boost { namespace unordered { namespace detail {
node_constructor<Alloc>::~node_constructor()
{
if (node_) {
- if (value_constructed_) {
- boost::unordered::detail::destroy(node_->value_ptr());
- }
-
- if (node_constructed_) {
- node_allocator_traits::destroy(alloc_,
+ if (constructed_) {
+ boost::unordered::detail::destroy_node(alloc_,
boost::addressof(*node_));
}
@@ -123,24 +131,13 @@ namespace boost { namespace unordered { namespace detail {
void node_constructor<Alloc>::construct_node()
{
if(!node_) {
- node_constructed_ = false;
- value_constructed_ = false;
-
+ constructed_ = false;
node_ = node_allocator_traits::allocate(alloc_, 1);
-
- node_allocator_traits::construct(alloc_,
- boost::addressof(*node_), node());
- node_->init(static_cast<typename node::link_pointer>(node_));
- node_constructed_ = true;
}
- else {
- BOOST_ASSERT(node_constructed_);
-
- if (value_constructed_)
- {
- boost::unordered::detail::destroy(node_->value_ptr());
- value_constructed_ = false;
- }
+ else if (constructed_) {
+ boost::unordered::detail::destroy_node(alloc_,
+ boost::addressof(*node_));
+ constructed_ = false;
}
}
@@ -179,12 +176,373 @@ namespace boost { namespace unordered { namespace detail {
enum { extra_node = false };
};
+ template <typename LinkPointer>
+ struct node_base
+ {
+ typedef LinkPointer link_pointer;
+ link_pointer next_;
+
+ node_base() : next_() {}
+ };
+
+}}}
+
+namespace boost { namespace unordered { namespace iterator_detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Iterators
+ //
+ // all no throw
+
+ template <typename NodePointer, typename Value> struct iterator;
+ template <typename ConstNodePointer, typename NodePointer,
+ typename Value> struct c_iterator;
+ template <typename NodePointer, typename Value, typename Policy>
+ struct l_iterator;
+ template <typename ConstNodePointer, typename NodePointer,
+ typename Value, typename Policy> struct cl_iterator;
+
+ // Local Iterators
+ //
+ // all no throw
+
+ template <typename NodePointer, typename Value, typename Policy>
+ struct l_iterator
+ : public boost::iterator<
+ std::forward_iterator_tag, Value, std::ptrdiff_t,
+ NodePointer, Value&>
+ {
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+ template <typename ConstNodePointer, typename NodePointer2,
+ typename Value2, typename Policy2>
+ friend struct boost::unordered::iterator_detail::cl_iterator;
+ private:
+#endif
+ typedef NodePointer node_pointer;
+ typedef boost::unordered::iterator_detail::iterator<NodePointer, Value>
+ iterator;
+ node_pointer ptr_;
+ std::size_t bucket_;
+ std::size_t bucket_count_;
+
+ public:
+
+ l_iterator() : ptr_() {}
+
+ l_iterator(iterator x, std::size_t b, std::size_t c)
+ : ptr_(x.node_), bucket_(b), bucket_count_(c) {}
+
+ Value& operator*() const {
+ return ptr_->value();
+ }
+
+ Value* 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 ConstNodePointer, typename NodePointer, typename Value,
+ typename Policy>
+ struct cl_iterator
+ : public boost::iterator<
+ std::forward_iterator_tag, Value, std::ptrdiff_t,
+ ConstNodePointer, Value const&>
+ {
+ friend struct boost::unordered::iterator_detail::l_iterator
+ <NodePointer, Value, Policy>;
+ private:
+
+ typedef NodePointer node_pointer;
+ typedef boost::unordered::iterator_detail::iterator<NodePointer, Value>
+ iterator;
+ node_pointer ptr_;
+ std::size_t bucket_;
+ std::size_t bucket_count_;
+
+ public:
+
+ 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(boost::unordered::iterator_detail::l_iterator<
+ NodePointer, Value, Policy> const& x) :
+ ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_)
+ {}
+
+ Value const&
+ operator*() const {
+ return ptr_->value();
+ }
+
+ Value 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 NodePointer, typename Value>
+ struct iterator
+ : public boost::iterator<
+ std::forward_iterator_tag, Value, std::ptrdiff_t,
+ NodePointer, Value&>
+ {
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+ template <typename, typename, typename>
+ friend struct boost::unordered::iterator_detail::c_iterator;
+ template <typename, typename, typename>
+ friend struct boost::unordered::iterator_detail::l_iterator;
+ template <typename, typename, typename, typename>
+ friend struct boost::unordered::iterator_detail::cl_iterator;
+ template <typename>
+ friend struct boost::unordered::detail::table;
+ template <typename, typename, typename, typename>
+ friend struct boost::unordered::detail::buckets;
+ template <typename>
+ friend struct boost::unordered::detail::table_impl;
+ template <typename>
+ friend struct boost::unordered::detail::grouped_table_impl;
+ private:
+#endif
+ typedef NodePointer node_pointer;
+ node_pointer node_;
+
+ public:
+
+ iterator() : node_() {}
+
+ explicit iterator(node_pointer const& x) : node_(x) {}
+
+ Value& operator*() const {
+ return node_->value();
+ }
+
+ Value* 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 ConstNodePointer, typename NodePointer, typename Value>
+ struct c_iterator
+ : public boost::iterator<
+ std::forward_iterator_tag, Value, std::ptrdiff_t,
+ ConstNodePointer, Value const&>
+ {
+ friend struct boost::unordered::iterator_detail::iterator<
+ NodePointer, Value>;
+
+#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
+ template <typename>
+ friend struct boost::unordered::detail::table;
+ template <typename, typename, typename, typename>
+ friend struct boost::unordered::detail::buckets;
+ template <typename>
+ friend struct boost::unordered::detail::table_impl;
+ template <typename>
+ friend struct boost::unordered::detail::grouped_table_impl;
+
+ private:
+#endif
+
+ typedef NodePointer node_pointer;
+ typedef boost::unordered::iterator_detail::iterator<NodePointer, Value>
+ iterator;
+ node_pointer node_;
+
+ public:
+
+ c_iterator() : node_() {}
+
+ explicit c_iterator(node_pointer const& x) : node_(x) {}
+
+ c_iterator(boost::unordered::iterator_detail::iterator<
+ NodePointer, Value> const& x) : node_(x.node_) {}
+
+ Value const& operator*() const {
+ return node_->value();
+ }
+
+ Value 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 boost { namespace unordered { namespace detail {
+
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Hash Policy
+ //
+ // Don't really want buckets to derive from this, but will for now.
+
+ 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 boost::unordered::detail::next_prime(min);
+ }
+
+ static inline SizeT prev_bucket_count(SizeT max) {
+ return boost::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> {};
+
///////////////////////////////////////////////////////////////////
//
// Buckets
- template <typename A, typename Bucket, typename Node>
- struct buckets
+ template <typename A, typename Bucket, typename Node, typename Policy>
+ struct buckets : Policy
{
private:
buckets(buckets const&);
@@ -193,6 +551,7 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::allocator_traits<A> traits;
typedef typename traits::value_type value_type;
+ typedef Policy policy;
typedef Node node;
typedef Bucket bucket;
typedef typename boost::unordered::detail::rebind_wrap<A, node>::type
@@ -214,6 +573,16 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::node_constructor<node_allocator>
node_constructor;
+ typedef boost::unordered::iterator_detail::
+ iterator<node_pointer, value_type> iterator;
+ typedef boost::unordered::iterator_detail::
+ c_iterator<const_node_pointer, node_pointer, value_type> c_iterator;
+ typedef boost::unordered::iterator_detail::
+ l_iterator<node_pointer, value_type, policy> l_iterator;
+ typedef boost::unordered::iterator_detail::
+ cl_iterator<const_node_pointer, node_pointer, value_type, policy>
+ cl_iterator;
+
// Members
bucket_pointer buckets_;
@@ -247,7 +616,7 @@ namespace boost { namespace unordered { namespace detail {
std::size_t max_bucket_count() const
{
// -1 to account for the start bucket.
- return boost::unordered::detail::prev_prime(
+ return policy::prev_bucket_count(
bucket_allocator_traits::max_size(bucket_alloc()) - 1);
}
@@ -266,16 +635,17 @@ namespace boost { namespace unordered { namespace detail {
return this->get_bucket(bucket_index)->next_;
}
- node_pointer get_start() const
+ iterator get_start() const
{
- return static_cast<node_pointer>(this->get_previous_start()->next_);
+ return iterator(static_cast<node_pointer>(
+ this->get_previous_start()->next_));
}
- node_pointer get_start(std::size_t bucket_index) const
+ iterator get_start(std::size_t bucket_index) const
{
previous_pointer prev = this->get_previous_start(bucket_index);
- return prev ? static_cast<node_pointer>(prev->next_) :
- node_pointer();
+ return prev ? iterator(static_cast<node_pointer>(prev->next_)) :
+ iterator();
}
float load_factor() const
@@ -288,14 +658,15 @@ namespace boost { namespace unordered { namespace detail {
std::size_t bucket_size(std::size_t index) const
{
if (!this->size_) return 0;
- node_pointer ptr = this->get_start(index);
- if (!ptr) return 0;
+ iterator it = this->get_start(index);
+ if (!it.node_) return 0;
std::size_t count = 0;
- while(ptr && ptr->hash_ % this->bucket_count_ == index)
+ while(it.node_ && policy::to_bucket(
+ this->bucket_count_, it.node_->hash_) == index)
{
++count;
- ptr = static_cast<node_pointer>(ptr->next_);
+ ++it;
}
return count;
@@ -349,6 +720,14 @@ namespace boost { namespace unordered { namespace detail {
node_constructor a(this->node_alloc());
a.construct_node();
+ // Since this node is just to mark the beginning it doesn't
+ // contain a value, so just construct node::node_base
+ // which containers the pointer to the next element.
+ node_allocator_traits::construct(node_alloc(),
+ static_cast<typename node::node_base*>(
+ boost::addressof(*a.get())),
+ typename node::node_base());
+
(constructor.get() +
static_cast<std::ptrdiff_t>(this->bucket_count_))->next_ =
a.release();
@@ -391,21 +770,21 @@ namespace boost { namespace unordered { namespace detail {
////////////////////////////////////////////////////////////////////////
// Delete/destruct
- inline void delete_node(node_pointer n)
+ inline void delete_node(c_iterator n)
{
- boost::unordered::detail::destroy(n->value_ptr());
- node_allocator_traits::destroy(node_alloc(), boost::addressof(*n));
- node_allocator_traits::deallocate(node_alloc(), n, 1);
+ boost::unordered::detail::destroy_node(
+ node_alloc(), boost::addressof(*n.node_));
+ node_allocator_traits::deallocate(node_alloc(), n.node_, 1);
--size_;
}
- std::size_t delete_nodes(node_pointer begin, node_pointer end)
+ std::size_t delete_nodes(c_iterator begin, c_iterator end)
{
std::size_t count = 0;
while(begin != end) {
- node_pointer n = begin;
- begin = static_cast<node_pointer>(begin->next_);
+ c_iterator n = begin;
+ ++begin;
delete_node(n);
++count;
}
@@ -416,7 +795,8 @@ namespace boost { namespace unordered { namespace detail {
inline void delete_extra_node(bucket_pointer) {}
inline void delete_extra_node(node_pointer n) {
- node_allocator_traits::destroy(node_alloc(), boost::addressof(*n));
+ node_allocator_traits::destroy(node_alloc(),
+ static_cast<typename node::node_base*>(boost::addressof(*n)));
node_allocator_traits::deallocate(node_alloc(), n, 1);
}
@@ -433,7 +813,7 @@ namespace boost { namespace unordered { namespace detail {
while(prev->next_) {
node_pointer n = static_cast<node_pointer>(prev->next_);
prev->next_ = n->next_;
- delete_node(n);
+ delete_node(iterator(n));
}
delete_extra_node(prev);
@@ -463,7 +843,7 @@ namespace boost { namespace unordered { namespace detail {
while(prev->next_) {
node_pointer n = static_cast<node_pointer>(prev->next_);
prev->next_ = n->next_;
- delete_node(n);
+ delete_node(iterator(n));
}
bucket_pointer end = this->get_bucket(this->bucket_count_);
@@ -477,22 +857,24 @@ namespace boost { namespace unordered { namespace detail {
// This is called after erasing a node or group of nodes to fix up
// the bucket pointers.
- void fix_buckets(bucket_pointer bucket,
+ void fix_buckets(bucket_pointer this_bucket,
previous_pointer prev, node_pointer next)
{
if (!next)
{
- if (bucket->next_ == prev) bucket->next_ = node_pointer();
+ if (this_bucket->next_ == prev)
+ this_bucket->next_ = node_pointer();
}
else
{
bucket_pointer next_bucket = this->get_bucket(
- next->hash_ % this->bucket_count_);
+ policy::to_bucket(this->bucket_count_, next->hash_));
- if (next_bucket != bucket)
+ if (next_bucket != this_bucket)
{
next_bucket->next_ = prev;
- if (bucket->next_ == prev) bucket->next_ = node_pointer();
+ if (this_bucket->next_ == prev)
+ this_bucket->next_ = node_pointer();
}
}
}
@@ -513,7 +895,7 @@ namespace boost { namespace unordered { namespace detail {
if (n == end) return;
std::size_t new_bucket_index =
- n->hash_ % this->bucket_count_;
+ policy::to_bucket(this->bucket_count_, n->hash_);
if (bucket_index != new_bucket_index) {
bucket_index = new_bucket_index;
break;
@@ -529,7 +911,7 @@ namespace boost { namespace unordered { namespace detail {
if (n == end) break;
std::size_t new_bucket_index =
- n->hash_ % this->bucket_count_;
+ policy::to_bucket(this->bucket_count_, n->hash_);
if (bucket_index != new_bucket_index) {
bucket_index = new_bucket_index;
this->get_bucket(bucket_index)->next_ = previous_pointer();
@@ -538,7 +920,8 @@ namespace boost { namespace unordered { namespace detail {
// Finally fix the bucket containing the trailing node.
if (n) {
- this->get_bucket(n->hash_ % this->bucket_count_)->next_
+ this->get_bucket(
+ policy::to_bucket(this->bucket_count_, n->hash_))->next_
= prev;
}
}