summaryrefslogtreecommitdiff
path: root/boost/unordered/detail/table.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/unordered/detail/table.hpp')
-rw-r--r--boost/unordered/detail/table.hpp794
1 files changed, 0 insertions, 794 deletions
diff --git a/boost/unordered/detail/table.hpp b/boost/unordered/detail/table.hpp
deleted file mode 100644
index 1092d31f9f..0000000000
--- a/boost/unordered/detail/table.hpp
+++ /dev/null
@@ -1,794 +0,0 @@
-
-// 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 <boost/config.hpp>
-#if defined(BOOST_HAS_PRAGMA_ONCE)
-#pragma once
-#endif
-
-#include <boost/unordered/detail/buckets.hpp>
-
-#if defined(BOOST_MSVC)
-#pragma warning(push)
-#pragma warning(disable:4127) // conditional expression is constant
-#endif
-
-namespace boost { 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 boost::aligned_storage<
- sizeof(value_type),
- boost::alignment_of<value_type>::value>::type data_;
-
- value_base() :
- 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 Types>
- struct table :
- boost::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 typename Types::iterator iterator;
- typedef typename Types::c_iterator c_iterator;
- typedef typename Types::l_iterator l_iterator;
- typedef typename Types::cl_iterator cl_iterator;
-
- typedef boost::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 boost::unordered::detail::
- rebind_wrap<allocator, node>::type node_allocator;
- typedef typename boost::unordered::detail::
- rebind_wrap<allocator, bucket>::type bucket_allocator;
- typedef boost::unordered::detail::allocator_traits<node_allocator>
- node_allocator_traits;
- typedef boost::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 boost::unordered::detail::node_constructor<node_allocator>
- node_constructor;
- typedef boost::unordered::detail::node_tmp<node_allocator>
- node_tmp;
-
- ////////////////////////////////////////////////////////////////////////
- // Members
-
- boost::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_;
-
- ////////////////////////////////////////////////////////////////////////
- // Node functions
-
- static inline node_pointer next_node(link_pointer n) {
- return static_cast<node_pointer>(n->next_);
- }
-
- ////////////////////////////////////////////////////////////////////////
- // 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_;
- }
-
- node_pointer begin() const
- {
- return size_ ? next_node(get_previous_start()) : node_pointer();
- }
-
- node_pointer begin(std::size_t bucket_index) const
- {
- if (!size_) return node_pointer();
- link_pointer prev = get_previous_start(bucket_index);
- return prev ? next_node(prev) : node_pointer();
- }
-
- std::size_t hash_to_bucket(std::size_t hash_value) const
- {
- return policy::to_bucket(bucket_count_, hash_value);
- }
-
- 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
- {
- node_pointer n = begin(index);
- if (!n) return 0;
-
- std::size_t count = 0;
- while(n && hash_to_bucket(n->hash_) == index)
- {
- ++count;
- n = next_node(n);
- }
-
- return count;
- }
-
- ////////////////////////////////////////////////////////////////////////
- // Load methods
-
- std::size_t max_size() const
- {
- using namespace std;
-
- // size < mlf_ * count
- return boost::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_ ? boost::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(
- boost::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, boost::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,
- boost::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_) {
- static_cast<table_impl*>(this)->copy_buckets(x);
- }
- }
-
- 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?
- static_cast<table_impl*>(this)->move_buckets(x);
- }
- }
-
- ////////////////////////////////////////////////////////////////////////
- // Create buckets
-
- void create_buckets(std::size_t new_count)
- {
- std::size_t length = new_count + 1;
- bucket_pointer new_buckets = bucket_allocator_traits::allocate(
- bucket_alloc(), length);
- bucket_pointer constructed = new_buckets;
-
- BOOST_TRY {
- bucket_pointer end = new_buckets
- + static_cast<std::ptrdiff_t>(length);
- for(; constructed != end; ++constructed) {
- new ((void*) boost::addressof(*constructed)) bucket();
- }
-
- if (buckets_)
- {
- // Copy the nodes to the new buckets, including the dummy
- // node if there is one.
- (new_buckets +
- 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.create_node();
-
- (new_buckets +
- static_cast<std::ptrdiff_t>(new_count))->next_ =
- a.release();
- }
- }
- BOOST_CATCH(...) {
- for(bucket_pointer p = new_buckets; p != constructed; ++p) {
- boost::unordered::detail::func::destroy(
- boost::addressof(*p));
- }
-
- bucket_allocator_traits::deallocate(bucket_alloc(),
- new_buckets, length);
-
- BOOST_RETHROW;
- }
- BOOST_CATCH_END
-
- bucket_count_ = new_count;
- buckets_ = new_buckets;
- recalculate_max_load();
- }
-
- ////////////////////////////////////////////////////////////////////////
- // Swap and Move
-
- void swap_allocators(table& other, false_type)
- {
- boost::unordered::detail::func::ignore_unused_variable_warning(other);
-
- // 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,
- boost::unordered::detail::integral_constant<bool,
- allocator_traits<node_allocator>::
- propagate_on_container_swap::value>());
-
- boost::swap(buckets_, x.buckets_);
- boost::swap(bucket_count_, x.bucket_count_);
- boost::swap(size_, x.size_);
- std::swap(mlf_, x.mlf_);
- std::swap(max_load_, x.max_load_);
- op1.commit();
- op2.commit();
- }
-
- // Only call with nodes allocated with the currect allocator, or
- // one that is equal to it. (Can't assert because other's
- // allocators might have already been moved).
- void move_buckets_from(table& other)
- {
- 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_;
-
- boost::unordered::detail::func::call_destroy(node_alloc(),
- n->value_ptr());
- boost::unordered::detail::func::destroy(boost::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_);
- boost::unordered::detail::func::destroy(
- boost::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)
- {
- boost::unordered::detail::func::destroy(
- boost::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 != boost::addressof(x))
- {
- assign(x,
- boost::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);
- mlf_ = x.mlf_;
- recalculate_max_load();
-
- if (!size_ && !x.size_) {
- new_func_this.commit();
- return;
- }
-
- if (x.size_ >= max_load_) {
- create_buckets(min_buckets_for_size(x.size_));
- }
- else {
- clear_buckets();
- }
-
- new_func_this.commit();
- static_cast<table_impl*>(this)->assign_buckets(x);
- }
-
- 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_) {
- static_cast<table_impl*>(this)->copy_buckets(x);
- }
- }
- }
-
- void move_assign(table& x)
- {
- if (this != boost::addressof(x))
- {
- move_assign(x,
- boost::unordered::detail::integral_constant<bool,
- allocator_traits<node_allocator>::
- propagate_on_container_move_assignment::value>());
- }
- }
-
- void move_assign(table& x, true_type)
- {
- delete_buckets();
- set_hash_functions new_func_this(*this, x);
- allocators_.move_assign(x.allocators_);
- // No throw from here.
- mlf_ = x.mlf_;
- max_load_ = x.max_load_;
- move_buckets_from(x);
- new_func_this.commit();
- }
-
- void move_assign(table& x, false_type)
- {
- if (node_alloc() == x.node_alloc()) {
- delete_buckets();
- 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();
- }
- else {
- set_hash_functions new_func_this(*this, x);
- mlf_ = x.mlf_;
- recalculate_max_load();
-
- if (!size_ && !x.size_) {
- new_func_this.commit();
- return;
- }
-
- if (x.size_ >= max_load_) {
- create_buckets(min_buckets_for_size(x.size_));
- }
- else {
- clear_buckets();
- }
-
- new_func_this.commit();
- static_cast<table_impl*>(this)->move_assign_buckets(x);
- }
- }
-
- // 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>
- node_pointer 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);
- }
-
- node_pointer 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());
- }
-
- node_pointer find_node(key_type const& k) const
- {
- return static_cast<table_impl const*>(this)->
- find_node_impl(hash(k), k, this->key_eq());
- }
-
- // 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,
- boost::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