// 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_ptr()); 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