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