Google Git
Sign in
android / platform / external / boost / ac861f8c0f33538060790a8e50701464ca9982d3 / . / boost / unordered / detail / hash_table_impl.hpp
blob: 6bfe6580ee963ef65c10f6e5ae1069763375ed19 [file] [log] [blame]
// 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)
#if BOOST_UNORDERED_EQUIVALENT_KEYS
#define BOOST_UNORDERED_TABLE hash_table_equivalent_keys
#define BOOST_UNORDERED_TABLE_DATA hash_table_data_equivalent_keys
#define BOOST_UNORDERED_ITERATOR hash_iterator_equivalent_keys
#define BOOST_UNORDERED_CONST_ITERATOR hash_const_iterator_equivalent_keys
#define BOOST_UNORDERED_LOCAL_ITERATOR hash_local_iterator_equivalent_keys
#define BOOST_UNORDERED_CONST_LOCAL_ITERATOR hash_const_local_iterator_equivalent_keys
#else
#define BOOST_UNORDERED_TABLE hash_table_unique_keys
#define BOOST_UNORDERED_TABLE_DATA hash_table_data_unique_keys
#define BOOST_UNORDERED_ITERATOR hash_iterator_unique_keys
#define BOOST_UNORDERED_CONST_ITERATOR hash_const_iterator_unique_keys
#define BOOST_UNORDERED_LOCAL_ITERATOR hash_local_iterator_unique_keys
#define BOOST_UNORDERED_CONST_LOCAL_ITERATOR hash_const_local_iterator_unique_keys
#endif
namespace boost {
namespace unordered_detail {
//
// Hash Table Data
//
// Responsible for managing the hash buckets.
template <typename Alloc>
class BOOST_UNORDERED_TABLE_DATA
{
public:
typedef BOOST_UNORDERED_TABLE_DATA data;
struct node;
struct bucket;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef Alloc value_allocator;
typedef BOOST_DEDUCED_TYPENAME
boost::unordered_detail::rebind_wrap<Alloc, node>::type
node_allocator;
typedef BOOST_DEDUCED_TYPENAME
boost::unordered_detail::rebind_wrap<Alloc, bucket>::type
bucket_allocator;
typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
typedef BOOST_DEDUCED_TYPENAME allocator_pointer<node_allocator>::type node_ptr;
typedef BOOST_DEDUCED_TYPENAME allocator_pointer<bucket_allocator>::type bucket_ptr;
typedef BOOST_DEDUCED_TYPENAME allocator_reference<value_allocator>::type reference;
typedef BOOST_DEDUCED_TYPENAME allocator_reference<bucket_allocator>::type bucket_reference;
typedef bucket_ptr link_ptr;
// Hash Bucket
//
// all no throw
struct bucket
{
private:
bucket& operator=(bucket const&);
public:
link_ptr next_;
bucket() : next_()
{
BOOST_UNORDERED_MSVC_RESET_PTR(next_);
}
bucket(bucket const& x) : next_(x.next_)
{
// Only copy construct when allocating.
BOOST_ASSERT(!x.next_);
}
bool empty() const
{
return !this->next_;
}
};
// Value Base
struct value_base {
typename boost::aligned_storage<
sizeof(value_type),
::boost::alignment_of<value_type>::value>::type data_;
void* address() { return this; }
};
// Hash Node
//
// all no throw
struct node : value_base, bucket {
#if BOOST_UNORDERED_EQUIVALENT_KEYS
public:
node() : group_prev_()
{
BOOST_UNORDERED_MSVC_RESET_PTR(group_prev_);
}
link_ptr group_prev_;
#endif
value_type& value() {
return *static_cast<value_type*>(this->address());
}
};
// allocators
//
// Stores all the allocators that we're going to need.
struct allocators
{
node_allocator node_alloc_;
bucket_allocator bucket_alloc_;
allocators(value_allocator const& a)
: node_alloc_(a), bucket_alloc_(a)
{}
void destroy(link_ptr ptr)
{
node* raw_ptr = static_cast<node*>(&*ptr);
BOOST_UNORDERED_DESTRUCT(&raw_ptr->value(), value_type);
node_ptr n(node_alloc_.address(*raw_ptr));
node_alloc_.destroy(n);
node_alloc_.deallocate(n, 1);
}
void swap(allocators& x)
{
boost::swap(node_alloc_, x.node_alloc_);
boost::swap(bucket_alloc_, x.bucket_alloc_);
}
bool operator==(allocators const& x)
{
return node_alloc_ == x.node_alloc_;
}
};
// node_constructor
//
// Used to construct nodes in an exception safe manner.
class node_constructor
{
allocators& allocators_;
node_ptr node_;
bool node_constructed_;
bool value_constructed_;
public:
node_constructor(allocators& a)
: allocators_(a),
node_(), node_constructed_(false), value_constructed_(false)
{
}
~node_constructor()
{
if (node_) {
if (value_constructed_) {
BOOST_UNORDERED_DESTRUCT(&node_->value(), value_type);
}
if (node_constructed_)
allocators_.node_alloc_.destroy(node_);
allocators_.node_alloc_.deallocate(node_, 1);
}
}
void construct_preamble()
{
if(!node_) {
node_constructed_ = false;
value_constructed_ = false;
node_ = allocators_.node_alloc_.allocate(1);
allocators_.node_alloc_.construct(node_, node());
node_constructed_ = true;
}
else {
BOOST_ASSERT(node_constructed_ && value_constructed_);
BOOST_UNORDERED_DESTRUCT(&node_->value(), value_type);
value_constructed_ = false;
}
}
#if defined(BOOST_UNORDERED_STD_FORWARD)
template <typename... Args>
void construct(Args&&... args)
{
construct_preamble();
new(node_->address()) value_type(std::forward<Args>(args)...);
value_constructed_ = true;
}
#else
#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, n, _) \
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
void construct( \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
) \
{ \
construct_preamble(); \
construct_impl( \
(value_type*) 0, \
BOOST_UNORDERED_CALL_PARAMS(z, n) \
); \
value_constructed_ = true; \
} \
\
template < \
typename T, \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
void construct_impl( \
T*, \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
) \
{ \
new(node_->address()) value_type( \
BOOST_UNORDERED_CALL_PARAMS(z, n) \
); \
}
#define BOOST_UNORDERED_CONSTRUCT_IMPL2(z, n, _) \
template <typename First, typename Second, typename Key, \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
void construct_impl( \
std::pair<First, Second>*, \
Key const& k, \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
) \
{ \
new(node_->address()) value_type(k, \
Second( \
BOOST_UNORDERED_CALL_PARAMS(z, n) \
) \
); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_CONSTRUCT_IMPL, _)
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_CONSTRUCT_IMPL2, _)
template <typename First, typename Second, typename T1, typename T2>
void construct_impl(std::pair<First, Second>*,
std::pair<T1, T2> const& arg0)
{
new(node_->address()) value_type(arg0);
}
#undef BOOST_UNORDERED_CONSTRUCT_IMPL
#endif
template <typename K, typename M>
void construct_pair(K const& k, M*)
{
construct_preamble();
new(node_->address()) value_type(k, M());
value_constructed_ = true;
}
node_ptr get() const
{
BOOST_ASSERT(node_);
return node_;
}
// no throw
link_ptr release()
{
node_ptr p = node_;
unordered_detail::reset(node_);
return link_ptr(allocators_.bucket_alloc_.address(*p));
}
private:
node_constructor(node_constructor const&);
node_constructor& operator=(node_constructor const&);
};
// Methods for navigating groups of elements with equal keys.
#if BOOST_UNORDERED_EQUIVALENT_KEYS
static inline link_ptr& prev_in_group(link_ptr n) {
return static_cast<node*>(&*n)->group_prev_;
}
// pre: Must be pointing to the first node in a group.
static inline link_ptr& next_group(link_ptr n) {
BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
return prev_in_group(n)->next_;
}
#else
static inline link_ptr& next_group(link_ptr n) {
BOOST_ASSERT(n);
return n->next_;
}
#endif
// pre: Must be pointing to a node
static inline node& get_node(link_ptr p) {
BOOST_ASSERT(p);
return *static_cast<node*>(&*p);
}
// pre: Must be pointing to a node
static inline reference get_value(link_ptr p) {
return get_node(p).value();
}
class iterator_base
{
typedef BOOST_UNORDERED_TABLE_DATA<Alloc> data;
public:
bucket_ptr bucket_;
link_ptr node_;
iterator_base()
: bucket_(), node_()
{
BOOST_UNORDERED_MSVC_RESET_PTR(bucket_);
BOOST_UNORDERED_MSVC_RESET_PTR(node_);
}
explicit iterator_base(bucket_ptr b)
: bucket_(b), node_(b->next_) {}
iterator_base(bucket_ptr b, link_ptr n)
: bucket_(b), node_(n) {}
bool operator==(iterator_base const& x) const
{
return node_ == x.node_;
}
bool operator!=(iterator_base const& x) const
{
return node_ != x.node_;
}
reference operator*() const
{
return get_value(node_);
}
void increment()
{
BOOST_ASSERT(bucket_);
node_ = node_->next_;
while (!node_) {
++bucket_;
node_ = bucket_->next_;
}
}
void increment_group()
{
node_ = data::next_group(node_);
while (!node_) {
++bucket_;
node_ = bucket_->next_;
}
}
};
// Member Variables
allocators allocators_;
bucket_ptr buckets_;
bucket_manager bucket_manager_;
bucket_ptr cached_begin_bucket_;
size_type size_;
// Constructors/Deconstructor
BOOST_UNORDERED_TABLE_DATA(size_type n, value_allocator const& a)
: allocators_(a),
buckets_(), bucket_manager_(n),
cached_begin_bucket_(), size_(0)
{
BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
create_buckets();
}
BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const& x, size_type n)
: allocators_(x.allocators_),
buckets_(), bucket_manager_(n),
cached_begin_bucket_(), size_(0)
{
BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
create_buckets();
}
BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x, move_tag)
: allocators_(x.allocators_),
buckets_(x.buckets_), bucket_manager_(x.bucket_manager_),
cached_begin_bucket_(x.cached_begin_bucket_), size_(x.size_)
{
unordered_detail::reset(x.buckets_);
}
BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x,
value_allocator const& a, size_type n, move_tag)
: allocators_(a), buckets_(), bucket_manager_(),
cached_begin_bucket_(), size_(0)
{
if(allocators_ == x.allocators_) {
buckets_ = x.buckets_;
bucket_manager_ = x.bucket_manager_;
cached_begin_bucket_ = x.cached_begin_bucket_;
size_ = x.size_;
unordered_detail::reset(x.buckets_);
}
else {
BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
bucket_manager_ = bucket_manager(n);
create_buckets();
}
}
// no throw
~BOOST_UNORDERED_TABLE_DATA()
{
delete_buckets();
}
void create_buckets() {
size_type bucket_count = bucket_manager_.bucket_count();
// The array constructor will clean up in the event of an
// exception.
allocator_array_constructor<bucket_allocator>
constructor(allocators_.bucket_alloc_);
// Creates an extra bucket to act as a sentinel.
constructor.construct(bucket(), bucket_count + 1);
cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count);
// Set up the sentinel.
cached_begin_bucket_->next_ = link_ptr(cached_begin_bucket_);
// Only release the buckets once everything is successfully
// done.
buckets_ = constructor.release();
}
// no throw
void delete_buckets()
{
if(buckets_) {
bucket_ptr begin = cached_begin_bucket_;
bucket_ptr end = buckets_end();
while(begin != end) {
clear_bucket(begin);
++begin;
}
// Destroy an extra bucket for the sentinels.
++end;
for(begin = buckets_; begin != end; ++begin)
allocators_.bucket_alloc_.destroy(begin);
allocators_.bucket_alloc_.deallocate(buckets_,
bucket_manager_.bucket_count() + 1);
}
}
private:
BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const&);
BOOST_UNORDERED_TABLE_DATA& operator=(BOOST_UNORDERED_TABLE_DATA const&);
public:
// no throw
void swap(BOOST_UNORDERED_TABLE_DATA& other)
{
std::swap(buckets_, other.buckets_);
std::swap(bucket_manager_, other.bucket_manager_);
std::swap(cached_begin_bucket_, other.cached_begin_bucket_);
std::swap(size_, other.size_);
}
// no throw
void move(BOOST_UNORDERED_TABLE_DATA& other)
{
delete_buckets();
buckets_ = other.buckets_;
unordered_detail::reset(other.buckets_);
bucket_manager_ = other.bucket_manager_;
cached_begin_bucket_ = other.cached_begin_bucket_;
size_ = other.size_;
}
// Return the bucket number for a hashed value.
//
// no throw
size_type bucket_from_hash(size_type hashed) const
{
return bucket_manager_.bucket_from_hash(hashed);
}
// Return the bucket for a hashed value.
//
// no throw
bucket_ptr bucket_ptr_from_hash(size_type hashed) const
{
return buckets_ + static_cast<difference_type>(
bucket_manager_.bucket_from_hash(hashed));
}
// Begin & End
//
// no throw
bucket_ptr buckets_end() const
{
return buckets_ + static_cast<difference_type>(bucket_manager_.bucket_count());
}
iterator_base begin() const
{
return size_
? iterator_base(cached_begin_bucket_)
: end();
}
iterator_base end() const
{
return iterator_base(buckets_end());
}
link_ptr begin(size_type n) const
{
return (buckets_ + static_cast<difference_type>(n))->next_;
}
link_ptr end(size_type) const
{
return unordered_detail::null_ptr<link_ptr>();
}
link_ptr begin(bucket_ptr b) const
{
return b->next_;
}
// Bucket Size
// no throw
static inline size_type node_count(link_ptr it)
{
size_type count = 0;
while(BOOST_UNORDERED_BORLAND_BOOL(it)) {
++count;
it = it->next_;
}
return count;
}
static inline size_type node_count(link_ptr it1, link_ptr it2)
{
size_type count = 0;
while(it1 != it2) {
++count;
it1 = it1->next_;
}
return count;
}
size_type bucket_size(size_type n) const
{
return node_count(begin(n));
}
#if BOOST_UNORDERED_EQUIVALENT_KEYS
static inline size_type group_count(link_ptr it)
{
return node_count(it, next_group(it));
}
#else
static inline size_type group_count(link_ptr)
{
return 1;
}
#endif
// get_for_erase
//
// Find the pointer to a node, for use when erasing.
//
// no throw
#if BOOST_UNORDERED_EQUIVALENT_KEYS
static link_ptr* get_for_erase(iterator_base r)
{
link_ptr n = r.node_;
// If the element isn't the first in its group, then
// the link to it will be found in the previous element
// in the group.
link_ptr* it = &prev_in_group(n)->next_;
if(*it == n) return it;
// The element is the first in its group, so iterate
// throught the groups, checking against the first element.
it = &r.bucket_->next_;
while(*it != n) it = &BOOST_UNORDERED_TABLE_DATA::next_group(*it);
return it;
}
#else
static link_ptr* get_for_erase(iterator_base r)
{
link_ptr n = r.node_;
link_ptr* it = &r.bucket_->next_;
while(*it != n) it = &(*it)->next_;
return it;
}
#endif
// Link/Unlink/Move Node
//
// For adding nodes to buckets, removing them and moving them to a
// new bucket.
//
// no throw
#if BOOST_UNORDERED_EQUIVALENT_KEYS
// If n points to the first node in a group, this adds it to the
// end of that group.
link_ptr link_node(node_constructor& a, link_ptr pos)
{
link_ptr n = a.release();
node& node_ref = get_node(n);
node& pos_ref = get_node(pos);
node_ref.next_ = pos_ref.group_prev_->next_;
node_ref.group_prev_ = pos_ref.group_prev_;
pos_ref.group_prev_->next_ = n;
pos_ref.group_prev_ = n;
++size_;
return n;
}
link_ptr link_node_in_bucket(node_constructor& a, bucket_ptr base)
{
link_ptr n = a.release();
node& node_ref = get_node(n);
node_ref.next_ = base->next_;
node_ref.group_prev_ = n;
base->next_ = n;
++size_;
if(base < cached_begin_bucket_) cached_begin_bucket_ = base;
return n;
}
void link_group(link_ptr n, bucket_ptr base, size_type count)
{
node& node_ref = get_node(n);
node& last_ref = get_node(node_ref.group_prev_);
last_ref.next_ = base->next_;
base->next_ = n;
size_ += count;
if(base < cached_begin_bucket_) cached_begin_bucket_ = base;
}
#else
void link_node(link_ptr n, bucket_ptr base)
{
n->next_ = base->next_;
base->next_ = n;
++size_;
if(base < cached_begin_bucket_) cached_begin_bucket_ = base;
}
link_ptr link_node_in_bucket(node_constructor& a, bucket_ptr base)
{
link_ptr n = a.release();
link_node(n, base);
return n;
}
void link_group(link_ptr n, bucket_ptr base, size_type)
{
link_node(n, base);
}
#endif
#if BOOST_UNORDERED_EQUIVALENT_KEYS
void unlink_node(iterator_base it)
{
link_ptr* pos = get_for_erase(it);
node* n = &get_node(it.node_);
link_ptr next = n->next_;
if(n->group_prev_ == *pos) {
// The deleted node is the sole node in the group, so
// no need to unlink it from a group.
}
else if(BOOST_UNORDERED_BORLAND_BOOL(next) && prev_in_group(next) == *pos)
{
// The deleted node is not at the end of the group, so
// change the link from the next node.
prev_in_group(next) = n->group_prev_;
}
else {
// The deleted node is at the end of the group, so the
// first node in the group is pointing to it.
// Find that to change its pointer.
link_ptr it = n->group_prev_;
while(prev_in_group(it) != *pos) {
it = prev_in_group(it);
}
prev_in_group(it) = n->group_prev_;
}
*pos = next;
--size_;
}
size_type unlink_group(link_ptr* pos)
{
size_type count = group_count(*pos);
size_ -= count;
*pos = next_group(*pos);
return count;
}
#else
void unlink_node(iterator_base n)
{
link_ptr* pos = get_for_erase(n);
*pos = (*pos)->next_;
--size_;
}
size_type unlink_group(link_ptr* pos)
{
*pos = (*pos)->next_;
--size_;
return 1;
}
#endif
void unlink_nodes(iterator_base n)
{
link_ptr* it = get_for_erase(n);
split_group(*it);
unordered_detail::reset(*it);
size_ -= node_count(n.node_);
}
void unlink_nodes(iterator_base begin, iterator_base end)
{
BOOST_ASSERT(begin.bucket_ == end.bucket_);
size_ -= node_count(begin.node_, end.node_);
link_ptr* it = get_for_erase(begin);
split_group(*it, end.node_);
*it = end.node_;
}
void unlink_nodes(bucket_ptr base, iterator_base end)
{
BOOST_ASSERT(base == end.bucket_);
split_group(end.node_);
link_ptr ptr(base->next_);
base->next_ = end.node_;
size_ -= node_count(ptr, end.node_);
}
#if BOOST_UNORDERED_EQUIVALENT_KEYS
// Break a ciruclar list into two, with split as the beginning
// of the second group (if split is at the beginning then don't
// split).
static inline link_ptr split_group(link_ptr split)
{
// If split is at the beginning of the group then there's
// nothing to split.
if(prev_in_group(split)->next_ != split)
return unordered_detail::null_ptr<link_ptr>();
// Find the start of the group.
link_ptr start = split;
do {
start = prev_in_group(start);
} while(prev_in_group(start)->next_ == start);
link_ptr last = prev_in_group(start);
prev_in_group(start) = prev_in_group(split);
prev_in_group(split) = last;
return start;
}
static inline void split_group(link_ptr split1, link_ptr split2)
{
link_ptr begin1 = split_group(split1);
link_ptr begin2 = split_group(split2);
if(BOOST_UNORDERED_BORLAND_BOOL(begin1) && split1 == begin2) {
link_ptr end1 = prev_in_group(begin1);
prev_in_group(begin1) = prev_in_group(begin2);
prev_in_group(begin2) = end1;
}
}
#else
static inline void split_group(link_ptr)
{
}
static inline void split_group(link_ptr, link_ptr)
{
}
#endif
// copy_group
//
// Basic exception safety.
// If it throws, it only copies some of the nodes in the group.
#if BOOST_UNORDERED_EQUIVALENT_KEYS
void copy_group(link_ptr it, bucket_ptr dst)
{
node_constructor a(allocators_);
link_ptr end = next_group(it);
a.construct(get_value(it)); // throws
link_ptr n = link_node_in_bucket(a, dst);
for(it = it->next_; it != end; it = it->next_) {
a.construct(get_value(it)); // throws
link_node(a, n);
}
}
#else
void copy_group(link_ptr it, bucket_ptr dst)
{
node_constructor a(allocators_);
a.construct(get_value(it)); // throws
link_node_in_bucket(a, dst);
}
#endif
// Delete Node
//
// Remove a node, or a range of nodes, from a bucket, and destroy
// them.
//
// no throw
void delete_to_bucket_end(link_ptr begin)
{
while(begin) {
link_ptr node = begin;
begin = begin->next_;
allocators_.destroy(node);
}
}
void delete_nodes(link_ptr begin, link_ptr end)
{
while(begin != end) {
link_ptr node = begin;
begin = begin->next_;
allocators_.destroy(node);
}
}
#if BOOST_UNORDERED_EQUIVALENT_KEYS
void delete_group(link_ptr first_node)
{
delete_nodes(first_node, prev_in_group(first_node)->next_);
}
#else
void delete_group(link_ptr node)
{
allocators_.destroy(node);
}
#endif
// Clear
//
// Remove all the nodes.
//
// no throw
void clear_bucket(bucket_ptr b)
{
link_ptr first_node = b->next_;
unordered_detail::reset(b->next_);
delete_to_bucket_end(first_node);
}
void clear()
{
bucket_ptr begin = cached_begin_bucket_;
bucket_ptr end = buckets_end();
size_ = 0;
cached_begin_bucket_ = end;
while(begin != end) {
clear_bucket(begin);
++begin;
}
}
// Erase
//
// no throw
iterator_base erase(iterator_base r)
{
BOOST_ASSERT(r != end());
iterator_base next = r;
next.increment();
unlink_node(r);
allocators_.destroy(r.node_);
// r has been invalidated but its bucket is still valid
recompute_begin_bucket(r.bucket_, next.bucket_);
return next;
}
iterator_base erase_range(iterator_base r1, iterator_base r2)
{
if(r1 != r2)
{
BOOST_ASSERT(r1 != end());
if (r1.bucket_ == r2.bucket_) {
unlink_nodes(r1, r2);
delete_nodes(r1.node_, r2.node_);
// No need to call recompute_begin_bucket because
// the nodes are only deleted from one bucket, which
// still contains r2 after the erase.
BOOST_ASSERT(!r1.bucket_->empty());
}
else {
BOOST_ASSERT(r1.bucket_ < r2.bucket_);
unlink_nodes(r1);
delete_to_bucket_end(r1.node_);
bucket_ptr i = r1.bucket_;
for(++i; i != r2.bucket_; ++i) {
size_ -= node_count(i->next_);
clear_bucket(i);
}
if(r2 != end()) {
link_ptr first = r2.bucket_->next_;
unlink_nodes(r2.bucket_, r2);
delete_nodes(first, r2.node_);
}
// r1 has been invalidated but its bucket is still
// valid.
recompute_begin_bucket(r1.bucket_, r2.bucket_);
}
}
return r2;
}
// recompute_begin_bucket
//
// After an erase cached_begin_bucket_ might be left pointing to
// an empty bucket, so this is called to update it
//
// no throw
void recompute_begin_bucket(bucket_ptr b)
{
BOOST_ASSERT(!(b < cached_begin_bucket_));
if(b == cached_begin_bucket_)
{
if (size_ != 0) {
while (cached_begin_bucket_->empty())
++cached_begin_bucket_;
} else {
cached_begin_bucket_ = buckets_end();
}
}
}
// This is called when a range has been erased
//
// no throw
void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2)
{
BOOST_ASSERT(!(b1 < cached_begin_bucket_) && !(b2 < b1));
BOOST_ASSERT(b2 == buckets_end() || !b2->empty());
if(b1 == cached_begin_bucket_ && b1->empty())
cached_begin_bucket_ = b2;
}
size_type erase_group(link_ptr* it, bucket_ptr bucket)
{
link_ptr pos = *it;
size_type count = unlink_group(it);
delete_group(pos);
this->recompute_begin_bucket(bucket);
return count;
}
};
#if defined(BOOST_MPL_CFG_MSVC_ETI_BUG)
template <>
class BOOST_UNORDERED_TABLE_DATA<int>
{
public:
typedef int size_type;
typedef int iterator_base;
};
#endif
//
// Hash Table
//
template <typename ValueType, typename KeyType,
typename Hash, typename Pred,
typename Alloc>
class BOOST_UNORDERED_TABLE
{
typedef BOOST_UNORDERED_TABLE_DATA<Alloc> data;
typedef BOOST_DEDUCED_TYPENAME data::node_constructor node_constructor;
typedef BOOST_DEDUCED_TYPENAME data::bucket_ptr bucket_ptr;
typedef BOOST_DEDUCED_TYPENAME data::link_ptr link_ptr;
public:
typedef BOOST_DEDUCED_TYPENAME data::value_allocator value_allocator;
typedef BOOST_DEDUCED_TYPENAME data::node_allocator node_allocator;
// Type definitions
typedef KeyType key_type;
typedef Hash hasher;
typedef Pred key_equal;
typedef ValueType value_type;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
// iterators
typedef BOOST_DEDUCED_TYPENAME data::iterator_base iterator_base;
private:
typedef boost::unordered_detail::buffered_functions<Hash, Pred>
function_store;
typedef BOOST_DEDUCED_TYPENAME function_store::functions functions;
typedef BOOST_DEDUCED_TYPENAME function_store::functions_ptr
functions_ptr;
function_store functions_;
float mlf_;
size_type max_load_;
public:
data data_;
// Constructors
//
// In the constructors, if anything throws an exception,
// BOOST_UNORDERED_TABLE_DATA's destructor will clean up.
BOOST_UNORDERED_TABLE(size_type n,
hasher const& hf, key_equal const& eq,
value_allocator const& a)
: functions_(hf, eq), // throws, cleans itself up
mlf_(1.0f), // no throw
data_(n, a) // throws, cleans itself up
{
calculate_max_load(); // no throw
}
// Construct from iterators
// initial_size
//
// A helper function for the copy constructor to calculate how many
// nodes will be created if the iterator's support it. Might get it
// totally wrong for containers with unique keys.
//
// no throw
template <typename I>
size_type initial_size(I i, I j, size_type n,
boost::forward_traversal_tag)
{
// max load factor isn't set yet, but when it is, it'll be 1.0.
return (std::max)(static_cast<size_type>(unordered_detail::distance(i, j)) + 1, n);
}
template <typename I>
size_type initial_size(I, I, size_type n,
boost::incrementable_traversal_tag)
{
return n;
}
template <typename I>
size_type initial_size(I i, I j, size_type n)
{
BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
iterator_traversal_tag;
return initial_size(i, j, n, iterator_traversal_tag);
}
template <typename I>
BOOST_UNORDERED_TABLE(I i, I j, size_type n,
hasher const& hf, key_equal const& eq,
value_allocator const& a)
: functions_(hf, eq), // throws, cleans itself up
mlf_(1.0f), // no throw
data_(initial_size(i, j, n), a) // throws, cleans itself up
{
calculate_max_load(); // no throw
// This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean up.
insert_range(i, j);
}
// Copy Construct
BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE const& x)
: functions_(x.functions_), // throws
mlf_(x.mlf_), // no throw
data_(x.data_, x.min_buckets_for_size(x.size())) // throws
{
calculate_max_load(); // no throw
// This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean
// up.
x.copy_buckets_to(data_);
}
// Copy Construct with allocator
BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE const& x,
value_allocator const& a)
: functions_(x.functions_), // throws
mlf_(x.mlf_), // no throw
data_(x.min_buckets_for_size(x.size()), a)
{
calculate_max_load(); // no throw
// This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean
// up.
x.copy_buckets_to(data_);
}
// Move Construct
BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE& x, move_tag m)
: functions_(x.functions_), // throws
mlf_(x.mlf_), // no throw
data_(x.data_, m) // throws
{
calculate_max_load(); // no throw
}
BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE& x,
value_allocator const& a, move_tag m)
: functions_(x.functions_), // throws
mlf_(x.mlf_), // no throw
data_(x.data_, a,
x.min_buckets_for_size(x.size()), m) // throws
{
calculate_max_load(); // no throw
if(x.data_.buckets_) {
// This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean
// up.
x.copy_buckets_to(data_);
}
}
// Assign
//
// basic exception safety, if buffered_functions::buffer or reserver throws
// the container is left in a sane, empty state. If copy_buckets_to
// throws the container is left with whatever was successfully
// copied.
BOOST_UNORDERED_TABLE& operator=(BOOST_UNORDERED_TABLE const& x)
{
if(this != &x)
{
data_.clear(); // no throw
functions_.set(functions_.buffer(x.functions_));
// throws, strong
mlf_ = x.mlf_; // no throw
calculate_max_load(); // no throw
reserve(x.size()); // throws
x.copy_buckets_to(data_); // throws
}
return *this;
}
// Swap
//
// Swap's behaviour when allocators aren't equal is in dispute, for
// details see:
//
// http://unordered.nfshost.com/doc/html/unordered/rationale.html#swapping_containers_with_unequal_allocators
//
// ----------------------------------------------------------------
//
// Strong exception safety (might change unused function objects)
//
// Can throw if hash or predicate object's copy constructor throws
// or if allocators are unequal.
void swap(BOOST_UNORDERED_TABLE& x)
{
// The swap code can work when swapping a container with itself
// but it triggers an assertion in buffered_functions.
// At the moment, I'd rather leave that assertion in and add a
// check here, rather than remove the assertion. I might change
// this at a later date.
if(this == &x) return;
// These can throw, but they only affect the function objects
// that aren't in use so it is strongly exception safe, via.
// double buffering.
functions_ptr new_func_this = functions_.buffer(x.functions_);
functions_ptr new_func_that = x.functions_.buffer(functions_);
if(data_.allocators_ == x.data_.allocators_) {
data_.swap(x.data_); // no throw
}
else {
// Create new buckets in separate HASH_TABLE_DATA objects
// which will clean up if anything throws an exception.
// (all can throw, but with no effect as these are new objects).
data new_this(data_, x.min_buckets_for_size(x.data_.size_));
x.copy_buckets_to(new_this);
data new_that(x.data_, min_buckets_for_size(data_.size_));
copy_buckets_to(new_that);
// Start updating the data here, no throw from now on.
data_.swap(new_this);
x.data_.swap(new_that);
}
// We've made it, the rest is no throw.
std::swap(mlf_, x.mlf_);
functions_.set(new_func_this);
x.functions_.set(new_func_that);
calculate_max_load();
x.calculate_max_load();
}
// Move
//
// ----------------------------------------------------------------
//
// Strong exception safety (might change unused function objects)
//
// Can throw if hash or predicate object's copy constructor throws
// or if allocators are unequal.
void move(BOOST_UNORDERED_TABLE& x)
{
// This can throw, but it only affects the function objects
// that aren't in use so it is strongly exception safe, via.
// double buffering.
functions_ptr new_func_this = functions_.buffer(x.functions_);
if(data_.allocators_ == x.data_.allocators_) {
data_.move(x.data_); // no throw
}
else {
// Create new buckets in separate HASH_TABLE_DATA objects
// which will clean up if anything throws an exception.
// (all can throw, but with no effect as these are new objects).
data new_this(data_, x.min_buckets_for_size(x.data_.size_));
x.copy_buckets_to(new_this);
// Start updating the data here, no throw from now on.
data_.move(new_this);
}
// We've made it, the rest is no throw.
mlf_ = x.mlf_;
functions_.set(new_func_this);
calculate_max_load();
}
// accessors
// no throw
node_allocator get_allocator() const
{
return data_.allocators_.node_alloc_;
}
// no throw
hasher const& hash_function() const
{
return functions_.current().hash_function();
}
// no throw
key_equal const& key_eq() const
{
return functions_.current().key_eq();
}
// no throw
size_type size() const
{
return data_.size_;
}
// no throw
bool empty() const
{
return data_.size_ == 0;
}
// no throw
size_type max_size() const
{
using namespace std;
// size < mlf_ * count
return double_to_size_t(ceil(
(double) mlf_ * max_bucket_count())) - 1;
}
// strong safety
size_type bucket(key_type const& k) const
{
// hash_function can throw:
return data_.bucket_from_hash(hash_function()(k));
}
// strong safety
bucket_ptr get_bucket(key_type const& k) const
{
return data_.buckets_ + static_cast<difference_type>(bucket(k));
}
// no throw
size_type bucket_count() const
{
return data_.bucket_manager_.bucket_count();
}
// no throw
size_type max_bucket_count() const
{
// -1 to account for the end marker.
return prev_prime(data_.allocators_.bucket_alloc_.max_size() - 1);
}
private:
// no throw
size_type min_buckets_for_size(size_type n) const
{
BOOST_ASSERT(mlf_ != 0);
using namespace std;
// From 6.3.1/13:
// size < mlf_ * count
// => count > size / mlf_
//
// Or from rehash post-condition:
// count > size / mlf_
return double_to_size_t(floor(n / (double) mlf_)) + 1;
}
// no throw
void calculate_max_load()
{
using namespace std;
// From 6.3.1/13:
// Only resize when size >= mlf_ * count
max_load_ = double_to_size_t(ceil(
(double) mlf_ * data_.bucket_manager_.bucket_count()));
}
// basic exception safety
bool reserve(size_type n)
{
bool need_to_reserve = n >= max_load_;
// throws - basic:
if (need_to_reserve) rehash_impl(min_buckets_for_size(n));
BOOST_ASSERT(n < max_load_ || n > max_size());
return need_to_reserve;
}
// basic exception safety
bool reserve_for_insert(size_type n)
{
bool need_to_reserve = n >= max_load_;
// throws - basic:
if (need_to_reserve) {
size_type s = size();
s = s + (s >> 1);
s = s > n ? s : n;
rehash_impl(min_buckets_for_size(s));
}
BOOST_ASSERT(n < max_load_ || n > max_size());
return need_to_reserve;
}
public:
// no throw
float max_load_factor() const
{
return mlf_;
}
// no throw
void max_load_factor(float z)
{
BOOST_ASSERT(z > 0);
mlf_ = (std::max)(z, minimum_max_load_factor);
calculate_max_load();
}
// no throw
float load_factor() const
{
BOOST_ASSERT(data_.bucket_manager_.bucket_count() != 0);
return static_cast<float>(data_.size_)
/ static_cast<float>(data_.bucket_manager_.bucket_count());
}
// key extractors
//
// no throw
//
// 'extract_key' is called with the emplace parameters to return a
// key if available or 'no_key' is one isn't and will need to be
// constructed.
struct no_key {
no_key() {}
template <class T> no_key(T const&) {}
};
// If emplace is called with no arguments then there obviously
// isn't an available key.
static no_key extract_key()
{
return no_key();
}
// Emplace or insert was called with the value type.
static key_type const& extract_key(value_type const& v)
{
return extract(v, (type_wrapper<value_type>*)0);
}
static key_type const& extract(value_type const& v,
type_wrapper<key_type>*)
{
return v;
}
static key_type const& extract(value_type const& v,
void*)
{
return v.first;
}
// For maps, if emplace is called with just a key, then it's the value type
// with the second value default initialised.
template <typename Arg>
static BOOST_DEDUCED_TYPENAME
boost::mpl::if_<boost::is_same<Arg, key_type>, key_type const&, no_key>::type
extract_key(Arg const& k)
{
return k;
}
// For a map, the argument might be a pair with the key as the first
// part and a convertible value as the second part.
template <typename First, typename Second>
static BOOST_DEDUCED_TYPENAME
boost::mpl::if_<
boost::mpl::and_<
boost::mpl::not_<boost::is_same<key_type, value_type> >,
boost::is_same<key_type,
typename boost::remove_const<
typename boost::remove_reference<First>::type
>::type>
>,
key_type const&, no_key
>::type extract_key(std::pair<First, Second> const& v)
{
return v.first;
}
// For maps if there is more than one argument, the key can be the first argument.
#if defined(BOOST_UNORDERED_STD_FORWARD)
template <typename Arg, typename Arg1, typename... Args>
static BOOST_DEDUCED_TYPENAME
boost::mpl::if_<
boost::mpl::and_<
boost::mpl::not_<boost::is_same<value_type, key_type> >,
boost::is_same<Arg, key_type>
>,
key_type const&, no_key
>::type extract_key(Arg const& k, Arg1 const&, Args const&...)
{
return k;
}
#else
template <typename Arg, typename Arg1>
static BOOST_DEDUCED_TYPENAME
boost::mpl::if_<
boost::mpl::and_<
boost::mpl::not_<boost::is_same<value_type, key_type> >,
boost::is_same<Arg, key_type>
>,
key_type const&, no_key
>::type extract_key(Arg const& k, Arg1 const&)
{
return k;
}
#endif
public:
// if hash function throws, basic exception safety
// strong otherwise.
void rehash(size_type n)
{
using namespace std;
// no throw:
size_type min_size = min_buckets_for_size(size());
// basic/strong:
rehash_impl(min_size > n ? min_size : n);
BOOST_ASSERT((float) bucket_count() > (float) size() / max_load_factor()
&& bucket_count() >= n);
}
private:
// if hash function throws, basic exception safety
// strong otherwise
void rehash_impl(size_type n)
{
n = next_prime(n); // no throw
if (n == bucket_count()) // no throw
return;
data new_buckets(data_, n); // throws, seperate
move_buckets_to(new_buckets); // basic/no throw
new_buckets.swap(data_); // no throw
calculate_max_load(); // no throw
}
// move_buckets_to & copy_buckets_to
//
// if the hash function throws, basic excpetion safety
// no throw otherwise
void move_buckets_to(data& dst)
{
BOOST_ASSERT(dst.size_ == 0);
//BOOST_ASSERT(src.allocators_.node_alloc_ == dst.allocators_.node_alloc_);
data& src = this->data_;
hasher const& hf = this->hash_function();
bucket_ptr end = src.buckets_end();
for(; src.cached_begin_bucket_ != end;
++src.cached_begin_bucket_) {
bucket_ptr src_bucket = src.cached_begin_bucket_;
while(src_bucket->next_) {
// Move the first group of equivalent nodes in
// src_bucket to dst.
// This next line throws iff the hash function throws.
bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
hf(extract_key(data::get_value(src_bucket->next_))));
link_ptr n = src_bucket->next_;
size_type count = src.unlink_group(&src_bucket->next_);
dst.link_group(n, dst_bucket, count);
}
}
}
// basic excpetion safety. If an exception is thrown this will
// leave dst partially filled.
void copy_buckets_to(data& dst) const
{
BOOST_ASSERT(dst.size_ == 0);
// no throw:
data const& src = this->data_;
hasher const& hf = this->hash_function();
bucket_ptr end = src.buckets_end();
// no throw:
for(bucket_ptr i = src.cached_begin_bucket_; i != end; ++i) {
// no throw:
for(link_ptr it = src.begin(i);
BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it)) {
// hash function can throw.
bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
hf(extract_key(data::get_value(it))));
// throws, strong
dst.copy_group(it, dst_bucket);
}
}
}
public:
// Insert functions
//
// basic exception safety, if hash function throws
// strong otherwise.
#if BOOST_UNORDERED_EQUIVALENT_KEYS
#if defined(BOOST_UNORDERED_STD_FORWARD)
// Emplace (equivalent key containers)
// (I'm using an overloaded emplace for both 'insert' and 'emplace')
// if hash function throws, basic exception safety
// strong otherwise
template <class... Args>
iterator_base emplace(Args&&... args)
{
// Create the node before rehashing in case it throws an
// exception (need strong safety in such a case).
node_constructor a(data_.allocators_);
a.construct(std::forward<Args>(args)...);
return emplace_impl(a);
}
// Emplace (equivalent key containers)
// (I'm using an overloaded emplace for both 'insert' and 'emplace')
// if hash function throws, basic exception safety
// strong otherwise
template <class... Args>
iterator_base emplace_hint(iterator_base const& it, Args&&... args)
{
// Create the node before rehashing in case it throws an
// exception (need strong safety in such a case).
node_constructor a(data_.allocators_);
a.construct(std::forward<Args>(args)...);
return emplace_hint_impl(it, a);
}
#else
#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
iterator_base emplace( \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
) \
{ \
node_constructor a(data_.allocators_); \
a.construct( \
BOOST_UNORDERED_CALL_PARAMS(z, n) \
); \
return emplace_impl(a); \
} \
\
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
iterator_base emplace_hint(iterator_base const& it, \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
) \
{ \
node_constructor a(data_.allocators_); \
a.construct( \
BOOST_UNORDERED_CALL_PARAMS(z, n) \
); \
return emplace_hint_impl(it, a); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_INSERT_IMPL, _)
#undef BOOST_UNORDERED_INSERT_IMPL
#endif
iterator_base emplace_impl(node_constructor& a)
{
key_type const& k = extract_key(a.get()->value());
size_type hash_value = hash_function()(k);
bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
link_ptr position = find_iterator(bucket, k);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(reserve_for_insert(size() + 1))
bucket = data_.bucket_ptr_from_hash(hash_value);
// I'm relying on link_ptr not being invalidated by
// the rehash here.
return iterator_base(bucket,
(BOOST_UNORDERED_BORLAND_BOOL(position)) ?
data_.link_node(a, position) :
data_.link_node_in_bucket(a, bucket)
);
}
iterator_base emplace_hint_impl(iterator_base const& it, node_constructor& a)
{
// equal can throw, but with no effects
if (it == data_.end() || !equal(extract_key(a.get()->value()), *it)) {
// Use the standard emplace if the iterator doesn't point
// to a matching key.
return emplace_impl(a);
}
else {
// Find the first node in the group - so that the node
// will be added at the end of the group.
link_ptr start(it.node_);
while(data_.prev_in_group(start)->next_ == start)
start = data_.prev_in_group(start);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
bucket_ptr base = reserve_for_insert(size() + 1) ?
get_bucket(extract_key(a.get()->value())) : it.bucket_;
// Nothing after this point can throw
return iterator_base(base,
data_.link_node(a, start));
}
}
// Insert from iterator range (equivalent key containers)
private:
// if hash function throws, or inserting > 1 element, basic exception safety
// strong otherwise
template <typename I>
void insert_for_range(I i, I j, forward_traversal_tag)
{
size_type distance = unordered_detail::distance(i, j);
if(distance == 1) {
emplace(*i);
}
else {
// Only require basic exception safety here
reserve_for_insert(size() + distance);
node_constructor a(data_.allocators_);
for (; i != j; ++i) {
a.construct(*i);
key_type const& k = extract_key(a.get()->value());
bucket_ptr bucket = get_bucket(k);
link_ptr position = find_iterator(bucket, k);
if(BOOST_UNORDERED_BORLAND_BOOL(position))
data_.link_node(a, position);
else
data_.link_node_in_bucket(a, bucket);
}
}
}
// if hash function throws, or inserting > 1 element, basic exception safety
// strong otherwise
template <typename I>
void insert_for_range(I i, I j,
boost::incrementable_traversal_tag)
{
// If only inserting 1 element, get the required
// safety since insert is only called once.
for (; i != j; ++i) emplace(*i);
}
public:
// if hash function throws, or inserting > 1 element, basic exception safety
// strong otherwise
template <typename I>
void insert_range(I i, I j)
{
BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
iterator_traversal_tag;
insert_for_range(i, j, iterator_traversal_tag);
}
#else
// if hash function throws, basic exception safety
// strong otherwise
value_type& operator[](key_type const& k)
{
BOOST_STATIC_ASSERT((
!boost::is_same<value_type, key_type>::value));
typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
size_type hash_value = hash_function()(k);
bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, k);
if (BOOST_UNORDERED_BORLAND_BOOL(pos))
return data::get_value(pos);
else
{
// Side effects only in this block.
// Create the node before rehashing in case it throws an
// exception (need strong safety in such a case).
node_constructor a(data_.allocators_);
a.construct_pair(k, (mapped_type*) 0);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(reserve_for_insert(size() + 1))
bucket = data_.bucket_ptr_from_hash(hash_value);
// Nothing after this point can throw.
return data::get_value(data_.link_node_in_bucket(a, bucket));
}
}
#if defined(BOOST_UNORDERED_STD_FORWARD)
// Emplace (unique keys)
// (I'm using an overloaded emplace for both 'insert' and 'emplace')
// if hash function throws, basic exception safety
// strong otherwise
template<typename... Args>
std::pair<iterator_base, bool> emplace(Args&&... args)
{
return emplace_impl(
extract_key(std::forward<Args>(args)...),
std::forward<Args>(args)...);
}
// Insert (unique keys)
// (I'm using an overloaded emplace for both 'insert' and 'emplace')
// I'm just ignoring hints here for now.
// if hash function throws, basic exception safety
// strong otherwise
template<typename... Args>
iterator_base emplace_hint(iterator_base const&, Args&&... args)
{
return emplace_impl(
extract_key(std::forward<Args>(args)...),
std::forward<Args>(args)...).first;
}
template<typename... Args>
std::pair<iterator_base, bool> emplace_impl(key_type const& k, Args&&... args)
{
// No side effects in this initial code
size_type hash_value = hash_function()(k);
bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, k);
if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
// Found an existing key, return it (no throw).
return std::pair<iterator_base, bool>(
iterator_base(bucket, pos), false);
} else {
// Doesn't already exist, add to bucket.
// Side effects only in this block.
// Create the node before rehashing in case it throws an
// exception (need strong safety in such a case).
node_constructor a(data_.allocators_);
a.construct(std::forward<Args>(args)...);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(reserve_for_insert(size() + 1))
bucket = data_.bucket_ptr_from_hash(hash_value);
// Nothing after this point can throw.
return std::pair<iterator_base, bool>(iterator_base(bucket,
data_.link_node_in_bucket(a, bucket)), true);
}
}
template<typename... Args>
std::pair<iterator_base, bool> emplace_impl(no_key, Args&&... args)
{
// Construct the node regardless - in order to get the key.
// It will be discarded if it isn't used
node_constructor a(data_.allocators_);
a.construct(std::forward<Args>(args)...);
return emplace_impl_with_node(a);
}
#else
template <typename Arg0>
std::pair<iterator_base, bool> emplace(Arg0 const& arg0)
{
return emplace_impl(extract_key(arg0), arg0);
}
template <typename Arg0>
iterator_base emplace_hint(iterator_base const& it, Arg0 const& arg0)
{
return emplace_impl(extract_key(arg0), arg0).first;
}
#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
std::pair<iterator_base, bool> emplace( \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
) \
{ \
return emplace_impl( \
extract_key(arg0, arg1), \
BOOST_UNORDERED_CALL_PARAMS(z, n) \
); \
} \
\
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
iterator_base emplace_hint(iterator_base const& it, \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
) \
{ \
return emplace_impl( \
extract_key(arg0, arg1), \
BOOST_UNORDERED_CALL_PARAMS(z, n) \
).first; \
} \
BOOST_UNORDERED_INSERT_IMPL2(z, n, _)
#define BOOST_UNORDERED_INSERT_IMPL2(z, n, _) \
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
std::pair<iterator_base, bool> emplace_impl(key_type const& k, \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
) \
{ \
size_type hash_value = hash_function()(k); \
bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value); \
link_ptr pos = find_iterator(bucket, k); \
\
if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { \
return std::pair<iterator_base, bool>( \
iterator_base(bucket, pos), false); \
} else { \
node_constructor a(data_.allocators_); \
a.construct( \
BOOST_UNORDERED_CALL_PARAMS(z, n) \
); \
\
if(reserve_for_insert(size() + 1)) \
bucket = data_.bucket_ptr_from_hash(hash_value); \
\
return std::pair<iterator_base, bool>(iterator_base(bucket, \
data_.link_node_in_bucket(a, bucket)), true); \
} \
} \
\
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
std::pair<iterator_base, bool> emplace_impl(no_key, \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
) \
{ \
node_constructor a(data_.allocators_); \
a.construct( \
BOOST_UNORDERED_CALL_PARAMS(z, n) \
); \
return emplace_impl_with_node(a); \
}
BOOST_UNORDERED_INSERT_IMPL2(1, 1, _)
BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_INSERT_IMPL, _)
#undef BOOST_UNORDERED_INSERT_IMPL
#endif
std::pair<iterator_base, bool> emplace_impl_with_node(node_constructor& a)
{
// No side effects in this initial code
key_type const& k = extract_key(a.get()->value());
size_type hash_value = hash_function()(k);
bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, k);
if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
// Found an existing key, return it (no throw).
return std::pair<iterator_base, bool>(
iterator_base(bucket, pos), false);
} else {
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(reserve_for_insert(size() + 1))
bucket = data_.bucket_ptr_from_hash(hash_value);
// Nothing after this point can throw.
return std::pair<iterator_base, bool>(iterator_base(bucket,
data_.link_node_in_bucket(a, bucket)), true);
}
}
// Insert from iterators (unique keys)
template <typename I>
size_type insert_size(I i, I j, boost::forward_traversal_tag)
{
return unordered_detail::distance(i, j);
}
template <typename I>
size_type insert_size(I, I, boost::incrementable_traversal_tag)
{
return 1;
}
template <typename I>
size_type insert_size(I i, I j)
{
BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
iterator_traversal_tag;
return insert_size(i, j, iterator_traversal_tag);
}
// if hash function throws, or inserting > 1 element, basic exception safety
// strong otherwise
template <typename InputIterator>
void insert_range(InputIterator i, InputIterator j)
{
if(i != j)
return insert_range_impl(extract_key(*i), i, j);
}
template <typename InputIterator>
void insert_range_impl(key_type const&, InputIterator i, InputIterator j)
{
node_constructor a(data_.allocators_);
for (; i != j; ++i) {
// No side effects in this initial code
size_type hash_value = hash_function()(extract_key(*i));
bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, extract_key(*i));
if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
// Doesn't already exist, add to bucket.
// Side effects only in this block.
// Create the node before rehashing in case it throws an
// exception (need strong safety in such a case).
a.construct(*i);
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(size() + 1 >= max_load_) {
reserve_for_insert(size() + insert_size(i, j));
bucket = data_.bucket_ptr_from_hash(hash_value);
}
// Nothing after this point can throw.
data_.link_node_in_bucket(a, bucket);
}
}
}
template <typename InputIterator>
void insert_range_impl(no_key, InputIterator i, InputIterator j)
{
node_constructor a(data_.allocators_);
for (; i != j; ++i) {
// No side effects in this initial code
a.construct(*i);
key_type const& k = extract_key(a.get()->value());
size_type hash_value = hash_function()(extract_key(k));
bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, k);
if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
// Doesn't already exist, add to bucket.
// Side effects only in this block.
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(size() + 1 >= max_load_) {
reserve_for_insert(size() + insert_size(i, j));
bucket = data_.bucket_ptr_from_hash(hash_value);
}
// Nothing after this point can throw.
data_.link_node_in_bucket(a, bucket);
}
}
}
#endif
public:
// erase_key
// strong exception safety
size_type erase_key(key_type const& k)
{
// No side effects in initial section
bucket_ptr bucket = get_bucket(k);
link_ptr* it = find_for_erase(bucket, k);
// No throw.
return *it ? data_.erase_group(it, bucket) : 0;
}
// count
//
// strong exception safety, no side effects
size_type count(key_type const& k) const
{
link_ptr it = find_iterator(k); // throws, strong
return BOOST_UNORDERED_BORLAND_BOOL(it) ? data::group_count(it) : 0;
}
// find
//
// strong exception safety, no side effects
iterator_base find(key_type const& k) const
{
bucket_ptr bucket = get_bucket(k);
link_ptr it = find_iterator(bucket, k);
if (BOOST_UNORDERED_BORLAND_BOOL(it))
return iterator_base(bucket, it);
else
return data_.end();
}
value_type& at(key_type const& k) const
{
bucket_ptr bucket = get_bucket(k);
link_ptr it = find_iterator(bucket, k);
if (BOOST_UNORDERED_BORLAND_BOOL(it))
return data::get_value(it);
else
throw std::out_of_range("Unable to find key in unordered_map.");
}
// equal_range
//
// strong exception safety, no side effects
std::pair<iterator_base, iterator_base> equal_range(key_type const& k) const
{
bucket_ptr bucket = get_bucket(k);
link_ptr it = find_iterator(bucket, k);
if (BOOST_UNORDERED_BORLAND_BOOL(it)) {
iterator_base first(iterator_base(bucket, it));
iterator_base second(first);
second.increment_group();
return std::pair<iterator_base, iterator_base>(first, second);
}
else {
return std::pair<iterator_base, iterator_base>(
data_.end(), data_.end());
}
}
// strong exception safety, no side effects
bool equal(key_type const& k, value_type const& v) const
{
return key_eq()(k, extract_key(v));
}
// strong exception safety, no side effects
link_ptr find_iterator(key_type const& k) const
{
return find_iterator(get_bucket(k), k);
}
// strong exception safety, no side effects
link_ptr find_iterator(bucket_ptr bucket,
key_type const& k) const
{
link_ptr it = data_.begin(bucket);
while (BOOST_UNORDERED_BORLAND_BOOL(it) && !equal(k, data::get_value(it))) {
it = data::next_group(it);
}
return it;
}
// strong exception safety, no side effects
link_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const
{
link_ptr* it = &bucket->next_;
while(BOOST_UNORDERED_BORLAND_BOOL(*it) && !equal(k, data::get_value(*it)))
it = &data::next_group(*it);
return it;
}
};
//
// Equals - unordered container equality comparison.
//
#if BOOST_UNORDERED_EQUIVALENT_KEYS
template <typename A, typename KeyType>
inline bool group_equals(
BOOST_UNORDERED_TABLE_DATA<A>*,
typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
KeyType*,
type_wrapper<KeyType>*)
{
typedef BOOST_UNORDERED_TABLE_DATA<A> data;
return data::group_count(it1) == data::group_count(it2);
}
template <typename A, typename KeyType>
inline bool group_equals(
BOOST_UNORDERED_TABLE_DATA<A>*,
typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
KeyType*,
void*)
{
typedef BOOST_UNORDERED_TABLE_DATA<A> data;
typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr end1 = data::next_group(it1);
typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr end2 = data::next_group(it2);
do {
if(data::get_value(it1).second != data::get_value(it2).second) return false;
it1 = it1->next_;
it2 = it2->next_;
} while(it1 != end1 && it2 != end2);
return it1 == end1 && it2 == end2;
}
#else
template <typename A, typename KeyType>
inline bool group_equals(
BOOST_UNORDERED_TABLE_DATA<A>*,
typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr,
typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr,
KeyType*,
type_wrapper<KeyType>*)
{
return true;
}
template <typename A, typename KeyType>
inline bool group_equals(
BOOST_UNORDERED_TABLE_DATA<A>*,
typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
KeyType*,
void*)
{
typedef BOOST_UNORDERED_TABLE_DATA<A> data;
return data::get_value(it1).second == data::get_value(it2).second;
}
#endif
template <typename V, typename K, typename H, typename P, typename A>
bool equals(BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t1,
BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t2)
{
typedef BOOST_UNORDERED_TABLE_DATA<A> data;
typedef typename data::bucket_ptr bucket_ptr;
typedef typename data::link_ptr link_ptr;
if(t1.size() != t2.size()) return false;
for(bucket_ptr i = t1.data_.cached_begin_bucket_,
j = t1.data_.buckets_end(); i != j; ++i)
{
for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
{
link_ptr other_pos = t2.find_iterator(t2.extract_key(data::get_value(it)));
if(!BOOST_UNORDERED_BORLAND_BOOL(other_pos) ||
!group_equals((data*)0, it, other_pos, (K*)0, (type_wrapper<V>*)0))
return false;
}
}
return true;
}
// Iterators
template <typename Alloc> class BOOST_UNORDERED_ITERATOR;
template <typename Alloc> class BOOST_UNORDERED_CONST_ITERATOR;
template <typename Alloc> class BOOST_UNORDERED_LOCAL_ITERATOR;
template <typename Alloc> class BOOST_UNORDERED_CONST_LOCAL_ITERATOR;
class iterator_access;
// Local Iterators
//
// all no throw
template <typename Alloc>
class BOOST_UNORDERED_LOCAL_ITERATOR
: public boost::iterator <
std::forward_iterator_tag,
BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type,
std::ptrdiff_t,
BOOST_DEDUCED_TYPENAME allocator_pointer<Alloc>::type,
BOOST_DEDUCED_TYPENAME allocator_reference<Alloc>::type >
{
public:
typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
private:
typedef BOOST_UNORDERED_TABLE_DATA<Alloc> data;
typedef BOOST_DEDUCED_TYPENAME data::link_ptr ptr;
typedef BOOST_UNORDERED_CONST_LOCAL_ITERATOR<Alloc> const_local_iterator;
friend class BOOST_UNORDERED_CONST_LOCAL_ITERATOR<Alloc>;
ptr ptr_;
public:
BOOST_UNORDERED_LOCAL_ITERATOR() : ptr_() {
BOOST_UNORDERED_MSVC_RESET_PTR(ptr_);
}
explicit BOOST_UNORDERED_LOCAL_ITERATOR(ptr x) : ptr_(x) {}
BOOST_DEDUCED_TYPENAME allocator_reference<Alloc>::type operator*() const
{ return data::get_value(ptr_); }
value_type* operator->() const { return &data::get_value(ptr_); }
BOOST_UNORDERED_LOCAL_ITERATOR& operator++() { ptr_ = ptr_->next_; return *this; }
BOOST_UNORDERED_LOCAL_ITERATOR operator++(int) { BOOST_UNORDERED_LOCAL_ITERATOR tmp(ptr_); ptr_ = ptr_->next_; return tmp; }
bool operator==(BOOST_UNORDERED_LOCAL_ITERATOR x) const { return ptr_ == x.ptr_; }
bool operator==(const_local_iterator x) const { return ptr_ == x.ptr_; }
bool operator!=(BOOST_UNORDERED_LOCAL_ITERATOR x) const { return ptr_ != x.ptr_; }
bool operator!=(const_local_iterator x) const { return ptr_ != x.ptr_; }
};
template <typename Alloc>
class BOOST_UNORDERED_CONST_LOCAL_ITERATOR
: public boost::iterator <
std::forward_iterator_tag,
BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type,
std::ptrdiff_t,
BOOST_DEDUCED_TYPENAME allocator_const_pointer<Alloc>::type,
BOOST_DEDUCED_TYPENAME allocator_const_reference<Alloc>::type >
{
public:
typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
private:
typedef BOOST_UNORDERED_TABLE_DATA<Alloc> data;
typedef BOOST_DEDUCED_TYPENAME data::link_ptr ptr;
typedef BOOST_UNORDERED_LOCAL_ITERATOR<Alloc> local_iterator;
friend class BOOST_UNORDERED_LOCAL_ITERATOR<Alloc>;
ptr ptr_;
public:
BOOST_UNORDERED_CONST_LOCAL_ITERATOR() : ptr_() {
BOOST_UNORDERED_MSVC_RESET_PTR(ptr_);
}
explicit BOOST_UNORDERED_CONST_LOCAL_ITERATOR(ptr x) : ptr_(x) {}
BOOST_UNORDERED_CONST_LOCAL_ITERATOR(local_iterator x) : ptr_(x.ptr_) {}
BOOST_DEDUCED_TYPENAME allocator_const_reference<Alloc>::type
operator*() const { return data::get_value(ptr_); }
value_type const* operator->() const { return &data::get_value(ptr_); }
BOOST_UNORDERED_CONST_LOCAL_ITERATOR& operator++() { ptr_ = ptr_->next_; return *this; }
BOOST_UNORDERED_CONST_LOCAL_ITERATOR operator++(int) { BOOST_UNORDERED_CONST_LOCAL_ITERATOR tmp(ptr_); ptr_ = ptr_->next_; return tmp; }
bool operator==(local_iterator x) const { return ptr_ == x.ptr_; }
bool operator==(BOOST_UNORDERED_CONST_LOCAL_ITERATOR x) const { return ptr_ == x.ptr_; }
bool operator!=(local_iterator x) const { return ptr_ != x.ptr_; }
bool operator!=(BOOST_UNORDERED_CONST_LOCAL_ITERATOR x) const { return ptr_ != x.ptr_; }
};
// iterators
//
// all no throw
template <typename Alloc>
class BOOST_UNORDERED_ITERATOR
: public boost::iterator <
std::forward_iterator_tag,
BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type,
std::ptrdiff_t,
BOOST_DEDUCED_TYPENAME allocator_pointer<Alloc>::type,
BOOST_DEDUCED_TYPENAME allocator_reference<Alloc>::type >
{
public:
typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
private:
typedef BOOST_DEDUCED_TYPENAME BOOST_UNORDERED_TABLE_DATA<Alloc>::iterator_base base;
typedef BOOST_UNORDERED_CONST_ITERATOR<Alloc> const_iterator;
friend class BOOST_UNORDERED_CONST_ITERATOR<Alloc>;
base base_;
public:
BOOST_UNORDERED_ITERATOR() : base_() {}
explicit BOOST_UNORDERED_ITERATOR(base const& x) : base_(x) {}
BOOST_DEDUCED_TYPENAME allocator_reference<Alloc>::type
operator*() const { return *base_; }
value_type* operator->() const { return &*base_; }
BOOST_UNORDERED_ITERATOR& operator++() { base_.increment(); return *this; }
BOOST_UNORDERED_ITERATOR operator++(int) { BOOST_UNORDERED_ITERATOR tmp(base_); base_.increment(); return tmp; }
bool operator==(BOOST_UNORDERED_ITERATOR const& x) const { return base_ == x.base_; }
bool operator==(const_iterator const& x) const { return base_ == x.base_; }
bool operator!=(BOOST_UNORDERED_ITERATOR const& x) const { return base_ != x.base_; }
bool operator!=(const_iterator const& x) const { return base_ != x.base_; }
};
template <typename Alloc>
class BOOST_UNORDERED_CONST_ITERATOR
: public boost::iterator <
std::forward_iterator_tag,
BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type,
std::ptrdiff_t,
BOOST_DEDUCED_TYPENAME allocator_const_pointer<Alloc>::type,
BOOST_DEDUCED_TYPENAME allocator_const_reference<Alloc>::type >
{
public:
typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
private:
typedef BOOST_DEDUCED_TYPENAME BOOST_UNORDERED_TABLE_DATA<Alloc>::iterator_base base;
typedef BOOST_UNORDERED_ITERATOR<Alloc> iterator;
friend class BOOST_UNORDERED_ITERATOR<Alloc>;
friend class iterator_access;
base base_;
public:
BOOST_UNORDERED_CONST_ITERATOR() : base_() {}
explicit BOOST_UNORDERED_CONST_ITERATOR(base const& x) : base_(x) {}
BOOST_UNORDERED_CONST_ITERATOR(iterator const& x) : base_(x.base_) {}
BOOST_DEDUCED_TYPENAME allocator_const_reference<Alloc>::type
operator*() const { return *base_; }
value_type const* operator->() const { return &*base_; }
BOOST_UNORDERED_CONST_ITERATOR& operator++() { base_.increment(); return *this; }
BOOST_UNORDERED_CONST_ITERATOR operator++(int) { BOOST_UNORDERED_CONST_ITERATOR tmp(base_); base_.increment(); return tmp; }
bool operator==(iterator const& x) const { return base_ == x.base_; }
bool operator==(BOOST_UNORDERED_CONST_ITERATOR const& x) const { return base_ == x.base_; }
bool operator!=(iterator const& x) const { return base_ != x.base_; }
bool operator!=(BOOST_UNORDERED_CONST_ITERATOR const& x) const { return base_ != x.base_; }
};
}
}
#undef BOOST_UNORDERED_TABLE
#undef BOOST_UNORDERED_TABLE_DATA
#undef BOOST_UNORDERED_ITERATOR
#undef BOOST_UNORDERED_CONST_ITERATOR
#undef BOOST_UNORDERED_LOCAL_ITERATOR
#undef BOOST_UNORDERED_CONST_LOCAL_ITERATOR