diff options
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail/buckets.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/buckets.hpp | 183 |
1 files changed, 183 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp new file mode 100644 index 0000000..b1dee5c --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp @@ -0,0 +1,183 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2009 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 + +#include <boost/config.hpp> +#include <boost/assert.hpp> +#include <boost/unordered/detail/node.hpp> +#include <boost/unordered/detail/util.hpp> + +namespace boost { namespace unordered_detail { + + //////////////////////////////////////////////////////////////////////////// + // Buckets + + template <class A, class G> + inline std::size_t hash_buckets<A, G>::max_bucket_count() const { + // -1 to account for the sentinel. + return prev_prime(this->bucket_alloc().max_size() - 1); + } + + template <class A, class G> + inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr + hash_buckets<A, G>::get_bucket(std::size_t num) const + { + return buckets_ + static_cast<std::ptrdiff_t>(num); + } + + template <class A, class G> + inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr + hash_buckets<A, G>::bucket_ptr_from_hash(std::size_t hashed) const + { + return get_bucket(hashed % bucket_count_); + } + + template <class A, class G> + std::size_t hash_buckets<A, G>::bucket_size(std::size_t index) const + { + if(!buckets_) return 0; + bucket_ptr ptr = get_bucket(index)->next_; + std::size_t count = 0; + while(ptr) { + ++count; + ptr = ptr->next_; + } + return count; + } + + template <class A, class G> + inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::node_ptr + hash_buckets<A, G>::bucket_begin(std::size_t num) const + { + return buckets_ ? get_bucket(num)->next_ : node_ptr(); + } + + //////////////////////////////////////////////////////////////////////////// + // Delete + + template <class A, class G> + inline void hash_buckets<A, G>::delete_node(node_ptr b) + { + node* raw_ptr = static_cast<node*>(&*b); + boost::unordered_detail::destroy(&raw_ptr->value()); + real_node_ptr n(node_alloc().address(*raw_ptr)); + node_alloc().destroy(n); + node_alloc().deallocate(n, 1); + } + + template <class A, class G> + inline void hash_buckets<A, G>::clear_bucket(bucket_ptr b) + { + node_ptr node_it = b->next_; + b->next_ = node_ptr(); + + while(node_it) { + node_ptr node_to_delete = node_it; + node_it = node_it->next_; + delete_node(node_to_delete); + } + } + + template <class A, class G> + inline void hash_buckets<A, G>::delete_buckets() + { + bucket_ptr end = this->get_bucket(this->bucket_count_); + + for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { + clear_bucket(begin); + } + + // Destroy the buckets (including the sentinel bucket). + ++end; + for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { + bucket_alloc().destroy(begin); + } + + bucket_alloc().deallocate(this->buckets_, this->bucket_count_ + 1); + + this->buckets_ = bucket_ptr(); + } + + template <class A, class G> + inline std::size_t hash_buckets<A, G>::delete_nodes( + node_ptr begin, node_ptr end) + { + std::size_t count = 0; + while(begin != end) { + node_ptr n = begin; + begin = begin->next_; + delete_node(n); + ++count; + } + return count; + } + + //////////////////////////////////////////////////////////////////////////// + // Constructors and Destructors + + template <class A, class G> + inline hash_buckets<A, G>::hash_buckets( + node_allocator const& a, std::size_t bucket_count) + : buckets_(), + bucket_count_(bucket_count), + allocators_(a,a) + { + } + + template <class A, class G> + inline hash_buckets<A, G>::~hash_buckets() + { + if(this->buckets_) { this->delete_buckets(); } + } + + template <class A, class G> + inline void hash_buckets<A, G>::create_buckets() + { + // The array constructor will clean up in the event of an + // exception. + allocator_array_constructor<bucket_allocator> + constructor(bucket_alloc()); + + // Creates an extra bucket to act as a sentinel. + constructor.construct(bucket(), this->bucket_count_ + 1); + + // Set up the sentinel (node_ptr cast) + bucket_ptr sentinel = constructor.get() + + static_cast<std::ptrdiff_t>(this->bucket_count_); + sentinel->next_ = sentinel; + + // Only release the buckets once everything is successfully + // done. + this->buckets_ = constructor.release(); + } + + //////////////////////////////////////////////////////////////////////////// + // Constructors and Destructors + + // no throw + template <class A, class G> + inline void hash_buckets<A, G>::move(hash_buckets& other) + { + BOOST_ASSERT(node_alloc() == other.node_alloc()); + if(this->buckets_) { this->delete_buckets(); } + this->buckets_ = other.buckets_; + this->bucket_count_ = other.bucket_count_; + other.buckets_ = bucket_ptr(); + other.bucket_count_ = 0; + } + + template <class A, class G> + inline void hash_buckets<A, G>::swap(hash_buckets<A, G>& other) + { + BOOST_ASSERT(node_alloc() == other.node_alloc()); + std::swap(buckets_, other.buckets_); + std::swap(bucket_count_, other.bucket_count_); + } +}} + +#endif |