Subject: [Boost-commit] svn:boost r56329 - in trunk: boost/unordered boost/unordered/detail libs/unordered/test/helpers libs/unordered/test/unordered
From: daniel_james_at_[hidden]
Date: 2009-09-20 17:55:18
Author: danieljames
Date: 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
New Revision: 56329
URL: http://svn.boost.org/trac/boost/changeset/56329
Log:
Since all the compilers support out of line template members use them
and lots of other things.
Added:
trunk/boost/unordered/detail/equivalent.hpp (contents, props changed)
trunk/boost/unordered/detail/unique.hpp (contents, props changed)
Removed:
trunk/boost/unordered/detail/insert.hpp
Text files modified:
trunk/boost/unordered/detail/allocator_helpers.hpp | 3
trunk/boost/unordered/detail/buckets.hpp | 263 ++++---------
trunk/boost/unordered/detail/extract_key.hpp | 25 +
trunk/boost/unordered/detail/fwd.hpp | 715 +++++++++++++++++++++++++++++++--------
trunk/boost/unordered/detail/move.hpp | 2
trunk/boost/unordered/detail/node.hpp | 151 +++-----
trunk/boost/unordered/detail/table.hpp | 648 ++++++++++++++++++-----------------
trunk/boost/unordered/detail/util.hpp | 108 ++---
trunk/boost/unordered/unordered_map.hpp | 320 ++++++++++-------
trunk/boost/unordered/unordered_set.hpp | 295 +++++++++-------
trunk/libs/unordered/test/helpers/list.hpp | 13
trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp | 2
trunk/libs/unordered/test/unordered/out_of_line.cpp | 2
13 files changed, 1462 insertions(+), 1085 deletions(-)
Modified: trunk/boost/unordered/detail/allocator_helpers.hpp
==============================================================================
--- trunk/boost/unordered/detail/allocator_helpers.hpp (original)
+++ trunk/boost/unordered/detail/allocator_helpers.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -99,7 +99,8 @@
}
private:
allocator_array_constructor(allocator_array_constructor const&);
- allocator_array_constructor& operator=(allocator_array_constructor const&);
+ allocator_array_constructor& operator=(
+ allocator_array_constructor const&);
};
}}
Modified: trunk/boost/unordered/detail/buckets.hpp
==============================================================================
--- trunk/boost/unordered/detail/buckets.hpp (original)
+++ trunk/boost/unordered/detail/buckets.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -14,199 +14,56 @@
namespace boost { namespace unordered_detail {
////////////////////////////////////////////////////////////////////////////
- // Explicitly call a destructor
-
-#if defined(BOOST_MSVC)
-# define BOOST_UNORDERED_DESTRUCT(x, type) (x)->~type();
-#else
-# define BOOST_UNORDERED_DESTRUCT(x, type) boost::unordered_detail::destroy(x)
- template <class T>
- void destroy(T* x) {
- x->~T();
- }
-#endif
-
- // Constructors
-
- template <class A, class G>
- hash_buckets<A, G>::hash_buckets(node_allocator const& a, std::size_t bucket_count)
- : buckets_(), allocators_(a,a)
- {
- // 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(), bucket_count + 1);
-
- // Set up the sentinel (node_ptr cast)
- bucket_ptr sentinel = constructor.get() + static_cast<ptrdiff_t>(bucket_count);
- sentinel->next_ = sentinel;
-
- // Only release the buckets once everything is successfully
- // done.
- this->buckets_ = constructor.release();
- this->bucket_count_ = bucket_count;
- }
-
- template <class A, class G>
- hash_buckets<A, G>::hash_buckets(hash_buckets& x, move_tag)
- : buckets_(), allocators_(x.allocators_)
- {
- this->buckets_ = x.buckets_;
- this->bucket_count_ = x.bucket_count_;
- x.buckets_ = bucket_ptr();
- x.bucket_count_ = 0;
- }
-
- template <class A, class G>
- hash_buckets<A, G>::hash_buckets(hash_buckets& x, value_allocator const& a, move_tag) :
- buckets_(), allocators_(a,a)
- {
- if(this->node_alloc() == x.node_alloc()) {
- this->buckets_ = x.buckets_;
- this->bucket_count_ = x.bucket_count_;
- x.buckets_ = bucket_ptr();
- x.bucket_count_ = 0;
- }
- }
-
- template <class A, class G>
- hash_buckets<A, G>::~hash_buckets()
- {
- if(this->buckets_) { delete_buckets(); }
- }
-
- // no throw
- template <class A, class G>
- inline void hash_buckets<A, G>::move(hash_buckets& other)
- {
- BOOST_ASSERT(node_alloc() == other.node_alloc());
- 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_);
- }
-
// Buckets
+ // TODO: Are these needed?
template <class A, class G>
- inline std::size_t hash_buckets<A, G>::bucket_count() const
- {
- return bucket_count_;
- }
-
- template <class A, class G>
- inline std::size_t hash_buckets<A, G>::bucket_from_hash(std::size_t hashed) const
+ inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
+ hash_buckets<A, G>::get_bucket(std::size_t n) const
{
- return hashed % bucket_count_;
+ return buckets_ + static_cast<std::ptrdiff_t>(n);
}
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 buckets_ + static_cast<std::ptrdiff_t>(
- bucket_from_hash(hashed));
+ return get_bucket(hashed % bucket_count_);
}
template <class A, class G>
- inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
- hash_buckets<A, G>::buckets_begin() const
- {
- return buckets_;
- }
-
- template <class A, class G>
- inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
- hash_buckets<A, G>::buckets_end() const
- {
- return buckets_ + static_cast<std::ptrdiff_t>(bucket_count_);
- }
-
- template <class A, class G>
inline std::size_t hash_buckets<A, G>::bucket_size(std::size_t index) const
{
- bucket_ptr ptr = (buckets_ + static_cast<std::ptrdiff_t>(index))->next_;
+ if(!buckets_) return 0;
+ bucket_ptr ptr = get_bucket(index)->next_;
std::size_t count = 0;
while(ptr) {
++count;
- ptr = next_node(ptr);
+ ptr = ptr->next_;
}
return count;
}
template <class A, class G>
- inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
- hash_buckets<A, G>::get_bucket(std::size_t n) const
- {
- return buckets_ + static_cast<std::ptrdiff_t>(n);
- }
-
- template <class A, class G>
inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::node_ptr
hash_buckets<A, G>::bucket_begin(std::size_t n) const
{
- return (buckets_ + static_cast<std::ptrdiff_t>(n))->next_;
+ return buckets_ ? get_bucket(n)->next_ : node_ptr();
}
- template <class A, class G>
- inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::node_ptr
- hash_buckets<A, G>::bucket_end(std::size_t) const
- {
- return node_ptr();
- }
+ ////////////////////////////////////////////////////////////////////////////
+ // Delete
- // Construct/destruct
-
template <class A, class G>
- inline void hash_buckets<A, G>::destruct_node(node_ptr b)
+ inline void hash_buckets<A, G>::delete_node(node_ptr b)
{
node* raw_ptr = static_cast<node*>(&*b);
- BOOST_UNORDERED_DESTRUCT(&raw_ptr->value(), value_type);
+ 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);
}
- // Delete and clear buckets
-
- template <class A, class G>
- inline void hash_buckets<A, G>::delete_group(node_ptr first_node)
- {
- delete_nodes(first_node, node::next_group(first_node));
- }
-
- template <class A, class G>
- inline void hash_buckets<A, G>::delete_nodes(node_ptr begin, node_ptr end)
- {
- while(begin != end) {
- node_ptr node = begin;
- begin = next_node(begin);
- destruct_node(node);
- }
- }
-
- template <class A, class G>
- inline void hash_buckets<A, G>::delete_to_bucket_end(node_ptr begin)
- {
- while(BOOST_UNORDERED_BORLAND_BOOL(begin)) {
- node_ptr node = begin;
- begin = next_node(begin);
- destruct_node(node);
- }
- }
-
template <class A, class G>
inline void hash_buckets<A, G>::clear_bucket(bucket_ptr b)
{
@@ -214,48 +71,106 @@
b->next_ = node_ptr();
while(node_it) {
- node_ptr node_to_destruct = node_it;
- node_it = next_node(node_it);
- destruct_node(node_to_destruct);
+ 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()
{
- for(bucket_ptr begin = this->buckets_begin(), end = this->buckets_end(); begin != end; ++begin) {
+ 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).
- bucket_ptr end = this->buckets_end();
++end;
- for(bucket_ptr begin = this->buckets_begin(); begin != end; ++begin) {
+ for(bucket_ptr begin = this->buckets_; begin != end; ++begin) {
bucket_alloc().destroy(begin);
}
- bucket_alloc().deallocate(this->buckets_begin(), this->bucket_count() + 1);
+ 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 node = begin;
+ begin = begin->next_;
+ delete_node(node);
+ ++count;
+ }
+ return count;
+ }
+
////////////////////////////////////////////////////////////////////////////
- // hash_iterator_base implementation
+ // 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 BucketPtr>
- inline void hash_iterator_base<BucketPtr>::increment(node_ptr node) {
- while(!node) {
- ++bucket_;
- node = bucket_->next_;
- }
+ 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<ptrdiff_t>(this->bucket_count_);
+ sentinel->next_ = sentinel;
+
+ // Only release the buckets once everything is successfully
+ // done.
+ this->buckets_ = constructor.release();
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Constructors and Destructors
- node_ = node;
+ // 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 BucketPtr>
- inline void hash_iterator_base<BucketPtr>::increment()
+ template <class A, class G>
+ inline void hash_buckets<A, G>::swap(hash_buckets<A, G>& other)
{
- increment(next_node(node_));
+ BOOST_ASSERT(node_alloc() == other.node_alloc());
+ std::swap(buckets_, other.buckets_);
+ std::swap(bucket_count_, other.bucket_count_);
}
}}
Added: trunk/boost/unordered/detail/equivalent.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/unordered/detail/equivalent.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -0,0 +1,271 @@
+
+// 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_EQUIVALENT_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED
+
+#include <boost/unordered/detail/table.hpp>
+#include <boost/unordered/detail/extract_key.hpp>
+
+namespace boost { namespace unordered_detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Equality
+
+ template <class H, class P, class A, class K>
+ bool hash_equivalent_table<H, P, A, K>
+ ::equals(hash_equivalent_table<H, P, A, K> const& other) const
+ {
+ if(this->size_ != other.size_) return false;
+ if(!this->size_) return true;
+
+ bucket_ptr end = this->get_bucket(this->bucket_count_);
+ for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i)
+ {
+ node_ptr it1 = i->next_;
+ while(BOOST_UNORDERED_BORLAND_BOOL(it1))
+ {
+ node_ptr it2 = other.find_iterator(get_key_from_ptr(it1));
+ if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false;
+
+ node_ptr end1 = node::next_group(it1);
+ node_ptr end2 = node::next_group(it2);
+
+ do {
+ if(!extractor::compare_mapped(
+ node::get_value(it1), node::get_value(it2)))
+ return false;
+ it1 = it1->next_;
+ it2 = it2->next_;
+ } while(it1 != end1 && it2 != end2);
+ if(it1 != end1 || it2 != end2) return false;
+ }
+ }
+
+ return true;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // A convenience method for adding nodes.
+
+ template <class H, class P, class A, class K>
+ inline BOOST_DEDUCED_TYPENAME hash_equivalent_table<H, P, A, K>::node_ptr
+ hash_equivalent_table<H, P, A, K>
+ ::add_node(node_constructor& a, bucket_ptr bucket, node_ptr pos)
+ {
+ node_ptr n = a.release();
+ if(BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ node::add_after_node(n, pos);
+ }
+ else {
+ node::add_to_bucket(n, *bucket);
+ if(bucket < this->cached_begin_bucket_)
+ this->cached_begin_bucket_ = bucket;
+ }
+ ++this->size_;
+ return n;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Insert methods
+
+ template <class H, class P, class A, class K>
+ inline BOOST_DEDUCED_TYPENAME
+ hash_equivalent_table<H, P, A, K>::iterator_base
+ hash_equivalent_table<H, P, A, K>::emplace_impl(node_constructor& a)
+ {
+ key_type const& k = get_key(a.value());
+ std::size_t hash_value = this->hash_function()(k);
+
+ if(!this->size_) {
+ return this->emplace_empty_impl_with_node(a, 1);
+ }
+ else {
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_ptr position = find_iterator(bucket, k);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->reserve_for_insert(this->size_ + 1))
+ bucket = this->bucket_ptr_from_hash(hash_value);
+
+ return iterator_base(bucket, add_node(a, bucket, position));
+ }
+ }
+
+ template <class H, class P, class A, class K>
+ inline BOOST_DEDUCED_TYPENAME
+ hash_equivalent_table<H, P, A, K>::iterator_base
+ hash_equivalent_table<H, P, A, K>
+ ::emplace_hint_impl(iterator_base const& it, node_constructor& a)
+ {
+ // equal can throw, but with no effects
+ if (!it.node_ || !equal(get_key(a.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.
+
+ node_ptr start = node::first_in_group(it.node_);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ bucket_ptr bucket = this->reserve_for_insert(this->size_ + 1) ?
+ get_bucket(this->bucket_index(get_key(a.value()))) :
+ it.bucket_;
+
+ // Nothing after this point can throw
+
+ return iterator_base(bucket, add_node(a, bucket, start));
+ }
+ }
+
+ template <class H, class P, class A, class K>
+ inline void hash_equivalent_table<H, P, A, K>
+ ::emplace_impl_no_rehash(node_constructor& a)
+ {
+ key_type const& k = get_key(a.value());
+ bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
+ add_node(a, bucket, find_iterator(bucket, k));
+ }
+
+#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 H, class P, class A, class K>
+ template <class... Args>
+ BOOST_DEDUCED_TYPENAME hash_equivalent_table<H, P, A, K>::iterator_base
+ hash_equivalent_table<H, P, A, K>
+ ::emplace(Args&&... args)
+ {
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(*this);
+ 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 H, class P, class A, class K>
+ template <class... Args>
+ BOOST_DEDUCED_TYPENAME hash_equivalent_table<H, P, A, K>::iterator_base
+ hash_equivalent_table<H, P, A, K>
+ ::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(*this);
+ a.construct(std::forward<Args>(args)...);
+
+ return emplace_hint_impl(it, a);
+ }
+
+#else
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
+ template <class H, class P, class A, class K> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ BOOST_DEDUCED_TYPENAME hash_equivalent_table<H, P, A, K>::iterator_base \
+ hash_equivalent_table<H, P, A, K> \
+ ::emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ return emplace_impl(a); \
+ } \
+ \
+ template <class H, class P, class A, class K> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ BOOST_DEDUCED_TYPENAME hash_equivalent_table<H, P, A, K>::iterator_base \
+ hash_equivalent_table<H, P, A, K> \
+ ::emplace_hint(iterator_base const& it, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ node_constructor a(*this); \
+ 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
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Insert range methods
+
+ // if hash function throws, or inserting > 1 element, basic exception safety
+ // strong otherwise
+ template <class H, class P, class A, class K>
+ template <class I>
+ inline void hash_equivalent_table<H, P, A, K>
+ ::insert_for_range(I i, I j, forward_traversal_tag)
+ {
+ if(i == j) return;
+ std::size_t distance = unordered_detail::distance(i, j);
+ if(distance == 1) {
+ emplace(*i);
+ }
+ else {
+ node_constructor a(*this);
+
+ // Only require basic exception safety here
+ if(this->size_) {
+ this->reserve_for_insert(this->size_ + distance);
+ }
+ else {
+ a.construct(*i++);
+ this->emplace_empty_impl_with_node(a, distance);
+ }
+
+ for (; i != j; ++i) {
+ a.construct(*i);
+ emplace_impl_no_rehash(a);
+ }
+ }
+ }
+
+ // if hash function throws, or inserting > 1 element, basic exception safety
+ // strong otherwise
+ template <class H, class P, class A, class K>
+ template <class I>
+ inline void hash_equivalent_table<H, P, A, K>
+ ::insert_for_range(I i, I j, boost::incrementable_traversal_tag)
+ {
+ node_constructor a(*this);
+ for (; i != j; ++i) {
+ a.construct(*i);
+ emplace_impl(a);
+ }
+ }
+
+ // if hash function throws, or inserting > 1 element, basic exception safety
+ // strong otherwise
+ // TODO: Should I special case an empty container?
+ template <class H, class P, class A, class K>
+ template <class I>
+ void hash_equivalent_table<H, P, A, K>::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);
+ }
+}}
+
+#endif
Modified: trunk/boost/unordered/detail/extract_key.hpp
==============================================================================
--- trunk/boost/unordered/detail/extract_key.hpp (original)
+++ trunk/boost/unordered/detail/extract_key.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -66,6 +66,11 @@
return no_key();
}
#endif
+
+ static bool compare_mapped(value_type const&, value_type const&)
+ {
+ return true;
+ }
};
};
@@ -75,7 +80,9 @@
struct apply
{
typedef ValueType value_type;
- typedef BOOST_DEDUCED_TYPENAME remove_const<BOOST_DEDUCED_TYPENAME ValueType::first_type>::type key_type;
+ typedef BOOST_DEDUCED_TYPENAME
+ remove_const<BOOST_DEDUCED_TYPENAME ValueType::first_type>::type
+ key_type;
static key_type const& extract(value_type const& v)
{
@@ -94,19 +101,22 @@
}
template <class Second>
- static key_type const& extract(std::pair<key_type const, Second> const& v)
+ static key_type const& extract(
+ std::pair<key_type const, Second> const& v)
{
return v.first;
}
/*
template <class Second>
- static key_type const& extract(std::pair<key_type&, Second> const& v)
+ static key_type const& extract(
+ std::pair<key_type&, Second> const& v)
{
return v.first;
}
template <class Second>
- static key_type const& extract(std::pair<key_type const&, Second> const& v)
+ static key_type const& extract(
+ std::pair<key_type const&, Second> const& v)
{
return v.first;
}
@@ -114,7 +124,8 @@
#if defined(BOOST_UNORDERED_STD_FORWARD)
template <class Arg1, class... Args>
- static key_type const& extract(key_type const& k, Arg1 const&, Args const&...)
+ static key_type const& extract(key_type const& k,
+ Arg1 const&, Args const&...)
{
return k;
}
@@ -149,6 +160,10 @@
}
#endif
+ static bool compare_mapped(value_type const& x, value_type const& y)
+ {
+ return x.second == y.second;
+ }
};
};
}}
Modified: trunk/boost/unordered/detail/fwd.hpp
==============================================================================
--- trunk/boost/unordered/detail/fwd.hpp (original)
+++ trunk/boost/unordered/detail/fwd.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -18,6 +18,7 @@
#include <boost/type_traits/aligned_storage.hpp>
#include <boost/type_traits/alignment_of.hpp>
#include <boost/unordered/detail/allocator_helpers.hpp>
+#include <algorithm>
// This header defines most of the classes used to implement the unordered
// containers. It doesn't include the insert methods as they require a lot
@@ -31,8 +32,6 @@
// G = Grouped/Ungrouped
// K = Key Extractor
-#include <boost/config.hpp>
-
#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
# if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION)
// STLport doesn't have std::forward.
@@ -45,12 +44,51 @@
#define BOOST_UNORDERED_EMPLACE_LIMIT 10
#endif
+#if !defined(BOOST_UNORDERED_STD_FORWARD)
+
+#include <boost/preprocessor/repetition/enum_params.hpp>
+#include <boost/preprocessor/repetition/enum_binary_params.hpp>
+#include <boost/preprocessor/repetition/repeat_from_to.hpp>
+
+#define BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, class Arg)
+#define BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, const& arg)
+#define BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, arg)
+
+#endif
+
namespace boost { namespace unordered_detail {
static const float minimum_max_load_factor = 1e-3f;
- static const std::size_t default_initial_bucket_count = 11;
+ static const std::size_t default_bucket_count = 11;
struct move_tag {};
+ template <class Alloc, class Grouped>
+ class hash_node_constructor;
+ struct set_extractor;
+ struct map_extractor;
+ struct no_key;
+
+ // Explicitly call a destructor
+
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#if BOOST_MSVC >= 1400
+#pragma warning(disable:4100) // unreferenced formal parameter
+#endif
+#endif
+
+ template <class T>
+ inline void destroy(T* x) {
+ x->~T();
+ }
+
+#if defined(BOOST_MSVC)
+#pragma warning(pop)
+#endif
+
// hash_bucket
template <class A>
@@ -70,8 +108,11 @@
hash_bucket() : next_() {}
// Only copy construct when allocating.
- hash_bucket(hash_bucket const& x) : next_()
- { BOOST_ASSERT(!x.next_); }
+ hash_bucket(hash_bucket const& x)
+ : next_()
+ {
+ BOOST_ASSERT(!x.next_);
+ }
};
template <class A>
@@ -84,12 +125,10 @@
static inline node_ptr& next_group(node_ptr ptr);
static inline std::size_t group_count(node_ptr ptr);
static inline void add_to_bucket(node_ptr n, bucket& b);
- static inline void add_group_to_bucket(node_ptr n, bucket& b);
static inline void add_after_node(node_ptr n, node_ptr position);
static void unlink_node(bucket& b, node_ptr node);
static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end);
static void unlink_nodes(bucket& b, node_ptr end);
- static inline void unlink_group(node_ptr* b);
};
template <class A>
@@ -102,21 +141,20 @@
node_ptr group_prev_;
grouped_node_base() : bucket(), group_prev_() {}
- static inline node_ptr& group_prev(node_ptr ptr);
static inline node_ptr& next_group(node_ptr ptr);
+ static inline node_ptr first_in_group(node_ptr n);
static inline std::size_t group_count(node_ptr ptr);
static inline void add_to_bucket(node_ptr n, bucket& b);
- static inline void add_group_to_bucket(node_ptr n, bucket& b);
static inline void add_after_node(node_ptr n, node_ptr position);
static void unlink_node(bucket& b, node_ptr node);
static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end);
static void unlink_nodes(bucket& b, node_ptr end);
- static inline void unlink_group(node_ptr* b);
private:
static inline node_ptr split_group(node_ptr split);
- static inline grouped_node_base& get(node_ptr ptr)
- { return static_cast<grouped_node_base&>(*ptr); }
+ static inline grouped_node_base& get(node_ptr ptr) {
+ return static_cast<grouped_node_base&>(*ptr);
+ }
};
struct ungrouped
@@ -143,44 +181,73 @@
sizeof(value_type),
::boost::alignment_of<value_type>::value>::type data_;
- void* address() { return this; }
- value_type& value() { return *(ValueType*) this; }
+ void* address() {
+ return this;
+ }
+ value_type& value() {
+ return *(ValueType*) this;
+ }
};
// Node
-
- template <class NodeBase, class ValueType>
- class hash_node : public NodeBase, public value_base<ValueType>
+
+ template <class A, class G>
+ class hash_node :
+ public G::BOOST_NESTED_TEMPLATE base<A>::type,
+ public value_base<BOOST_DEDUCED_TYPENAME A::value_type>
{
public:
- typedef ValueType value_type;
- typedef BOOST_DEDUCED_TYPENAME NodeBase::node_ptr node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
+ typedef BOOST_DEDUCED_TYPENAME hash_bucket<A>::node_ptr node_ptr;
- static value_type& get_value(node_ptr p) { return static_cast<hash_node&>(*p).value(); }
+ static value_type& get_value(node_ptr p) {
+ return static_cast<hash_node&>(*p).value();
+ }
};
// Iterator Base
- template <class BucketPtr>
+ template <class A, class G>
class hash_iterator_base
{
public:
- typedef BucketPtr bucket_ptr;
- typedef BucketPtr node_ptr;
+ typedef A value_allocator;
+ typedef hash_bucket<A> bucket;
+ typedef hash_node<A, G> node;
+ typedef BOOST_DEDUCED_TYPENAME node::value_type value_type;
+ typedef BOOST_DEDUCED_TYPENAME node::bucket_ptr bucket_ptr;
+ typedef BOOST_DEDUCED_TYPENAME node::node_ptr node_ptr;
bucket_ptr bucket_;
node_ptr node_;
hash_iterator_base() : bucket_(), node_() {}
- explicit hash_iterator_base(bucket_ptr b) : bucket_(b), node_(b->next_) {}
- hash_iterator_base(bucket_ptr b, node_ptr n) : bucket_(b), node_(n) {}
-
- bool operator==(hash_iterator_base const& x) const { return node_ == x.node_; }
- bool operator!=(hash_iterator_base const& x) const { return node_ != x.node_; }
- bool is_end() const { return node_ == bucket_; }
- node_ptr get() const { return node_; }
- void increment(node_ptr node);
- void increment();
+ explicit hash_iterator_base(bucket_ptr b)
+ : bucket_(b),
+ node_(b ? b->next_ : node_ptr()) {}
+ hash_iterator_base(bucket_ptr b, node_ptr n)
+ : bucket_(b),
+ node_(n) {}
+
+ bool operator==(hash_iterator_base const& x) const {
+ return node_ == x.node_; }
+ bool operator!=(hash_iterator_base const& x) const {
+ return node_ != x.node_; }
+ value_type& operator*() const {
+ return node::get_value(node_);
+ }
+
+ void increment_bucket(node_ptr node) {
+ while(!node) {
+ ++bucket_;
+ node = bucket_->next_;
+ }
+ node_ = bucket_ == node ? node_ptr() : node;
+ }
+
+ void increment() {
+ increment_bucket(node_->next_);
+ }
};
// hash_buckets
@@ -188,9 +255,10 @@
// This is responsible for allocating and deallocating buckets and nodes.
//
// Notes:
- // 1. For the sake exception safety the allocators themselves don't allocate anything.
- // 2. It's the callers responsibility to allocate the buckets before calling any of the
- // methods (other than getters and setters).
+ // 1. For the sake exception safety the allocators themselves don't allocate
+ // anything.
+ // 2. It's the callers responsibility to allocate the buckets before calling
+ // any of the methods (other than getters and setters).
template <class A, class G>
class hash_buckets
@@ -201,22 +269,19 @@
// Types
typedef A value_allocator;
- typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
-
typedef hash_bucket<A> bucket;
- typedef BOOST_DEDUCED_TYPENAME G::BOOST_NESTED_TEMPLATE base<A>::type
- node_base;
- typedef hash_node<node_base, value_type> node;
+ typedef hash_iterator_base<A, G> iterator_base;
+ typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
+ typedef BOOST_DEDUCED_TYPENAME iterator_base::node node;
typedef BOOST_DEDUCED_TYPENAME node::bucket_allocator bucket_allocator;
typedef BOOST_DEDUCED_TYPENAME node::bucket_ptr bucket_ptr;
typedef BOOST_DEDUCED_TYPENAME node::node_ptr node_ptr;
- typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type node_allocator;
+ typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type
+ node_allocator;
typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr;
- typedef hash_iterator_base<bucket_ptr> iterator_base;
-
// Members
bucket_ptr buckets_;
@@ -225,124 +290,194 @@
// 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(); }
+ 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 sentinel.
return prev_prime(this->bucket_alloc().max_size() - 1);
}
// Constructors
- //
- // The copy constructor doesn't copy the buckets.
hash_buckets(node_allocator const& a, std::size_t n);
- hash_buckets(hash_buckets& x, move_tag m);
- hash_buckets(hash_buckets& x, value_allocator const& a, move_tag m);
+ void create_buckets();
~hash_buckets();
// no throw
void swap(hash_buckets& other);
void move(hash_buckets& other);
- // Buckets
+ // For the remaining functions, buckets_ must not be null.
- std::size_t bucket_count() const;
- std::size_t bucket_from_hash(std::size_t hashed) const;
+ bucket_ptr get_bucket(std::size_t n) const;
bucket_ptr bucket_ptr_from_hash(std::size_t hashed) const;
- bucket_ptr buckets_begin() const;
- bucket_ptr buckets_end() const;
std::size_t bucket_size(std::size_t index) const;
- bucket_ptr get_bucket(std::size_t n) const;
node_ptr bucket_begin(std::size_t n) const;
- node_ptr bucket_end(std::size_t) const;
// Alloc/Dealloc
- void destruct_node(node_ptr);
+ void delete_node(node_ptr);
//
void delete_buckets();
void clear_bucket(bucket_ptr);
- void delete_group(node_ptr first_node);
- void delete_nodes(node_ptr begin, node_ptr end);
- void delete_to_bucket_end(node_ptr begin);
+ std::size_t delete_nodes(node_ptr begin, node_ptr end);
+ std::size_t delete_to_bucket_end(node_ptr begin);
+ };
+
+ template <class H, class P> class set_hash_functions;
+
+ template <class H, class P>
+ class hash_buffered_functions
+ {
+ friend class set_hash_functions<H, P>;
+ hash_buffered_functions& operator=(hash_buffered_functions const&);
+
+ typedef boost::compressed_pair<H, P> function_pair;
+ typedef BOOST_DEDUCED_TYPENAME boost::aligned_storage<
+ sizeof(function_pair),
+ ::boost::alignment_of<function_pair>::value>::type aligned_function;
+
+ bool current_; // The currently active functions.
+ aligned_function funcs_[2];
+
+ function_pair const& current() const {
+ return *static_cast<function_pair const*>(
+ static_cast<void const*>(&funcs_[current_]));
+ }
+
+ void construct(bool which, H const& hf, P const& eq)
+ {
+ new((void*) &funcs_[which]) function_pair(hf, eq);
+ }
+
+ void construct(bool which, function_pair const& f)
+ {
+ new((void*) &funcs_[which]) function_pair(f);
+ }
+
+ void destroy(bool which)
+ {
+ boost::unordered_detail::destroy((function_pair*)(&funcs_[which]));
+ }
+
+ public:
+
+ hash_buffered_functions(H const& hf, P const& eq)
+ : current_(false)
+ {
+ construct(current_, hf, eq);
+ }
+
+ hash_buffered_functions(hash_buffered_functions const& bf)
+ : current_(false)
+ {
+ construct(current_, bf.current());
+ }
+
+ ~hash_buffered_functions() {
+ destroy(current_);
+ }
+
+ H const& hash_function() const {
+ return current().first();
+ }
+
+ P const& key_eq() const {
+ return current().second();
+ }
+ };
+
+ template <class H, class P>
+ class set_hash_functions
+ {
+ set_hash_functions(set_hash_functions const&);
+ set_hash_functions& operator=(set_hash_functions const&);
+
+ typedef hash_buffered_functions<H, P> buffered_functions;
+ buffered_functions& buffered_functions_;
+ bool tmp_functions_;
+
+ public:
+
+ set_hash_functions(buffered_functions& f, H const& h, P const& p)
+ : buffered_functions_(f),
+ tmp_functions_(!f.current_)
+ {
+ f.construct(tmp_functions_, h, p);
+ }
+
+ set_hash_functions(buffered_functions& f,
+ buffered_functions const& other)
+ : buffered_functions_(f),
+ tmp_functions_(!f.current_)
+ {
+ f.construct(tmp_functions_, other.current());
+ }
+
+ ~set_hash_functions()
+ {
+ buffered_functions_.destroy(tmp_functions_);
+ }
+
+ void commit()
+ {
+ buffered_functions_.current_ = tmp_functions_;
+ tmp_functions_ = !tmp_functions_;
+ }
};
template <class H, class P, class A, class G, class K>
class hash_table :
- public hash_buckets<A, G>
-
+ public hash_buckets<A, G>,
+ public hash_buffered_functions<H, P>
{
+ hash_table(hash_table const&);
public:
typedef H hasher;
typedef P key_equal;
typedef A value_allocator;
typedef G grouped;
typedef K key_extractor;
+ typedef hash_buffered_functions<H, P> base;
typedef hash_buckets<A, G> buckets;
typedef BOOST_DEDUCED_TYPENAME value_allocator::value_type value_type;
- typedef BOOST_DEDUCED_TYPENAME key_extractor::BOOST_NESTED_TEMPLATE apply<value_type>
- extractor;
+ typedef BOOST_DEDUCED_TYPENAME key_extractor::BOOST_NESTED_TEMPLATE
+ apply<value_type> extractor;
typedef BOOST_DEDUCED_TYPENAME extractor::key_type key_type;
typedef BOOST_DEDUCED_TYPENAME buckets::node node;
typedef BOOST_DEDUCED_TYPENAME buckets::bucket bucket;
typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
typedef BOOST_DEDUCED_TYPENAME buckets::bucket_ptr bucket_ptr;
-
typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base iterator_base;
-
- // Types for storing functions
-
- typedef boost::compressed_pair<hasher, key_equal> functions;
- typedef bool functions_ptr;
-
- typedef BOOST_DEDUCED_TYPENAME boost::aligned_storage<
- sizeof(functions),
- ::boost::alignment_of<functions>::value>::type aligned_function;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node_allocator node_allocator;
+ typedef hash_node_constructor<A, G> node_constructor;
+ typedef std::pair<iterator_base, iterator_base> iterator_pair;
// Members
- bool func_; // The currently active functions.
- aligned_function funcs_[2];
- bucket_ptr cached_begin_bucket_;
std::size_t size_;
float mlf_;
+ // Cached data - invalid if !this->buckets_
+ bucket_ptr cached_begin_bucket_;
std::size_t max_load_;
-
- // Buffered Functions
-
- functions* get_functions(bool which) {
- return static_cast<functions*>(static_cast<void*>(&this->funcs_[which]));
- }
- functions const* get_functions(bool which) const {
- return static_cast<functions const*>(static_cast<void const*>(&this->funcs_[which]));
- }
- functions const& current() const {
- return *this->get_functions(this->func_);
- }
- hasher const& hash_function() const {
- return this->current().first();
- }
- key_equal const& key_eq() const {
- return this->current().second();
- }
- functions_ptr buffer_functions(hash_table const& x) {
- functions_ptr ptr = !func_;
- *this->get_functions(ptr) = x.current();
- return ptr;
- }
- void set_functions(functions_ptr ptr) {
- BOOST_ASSERT(ptr != func_);
- func_ = ptr;
- }
// Helper methods
+ key_type const& get_key(value_type const& v) const {
+ return extractor::extract(v);
+ }
+ key_type const& get_key_from_ptr(node_ptr n) const {
+ return extractor::extract(node::get_value(n));
+ }
bool equal(key_type const& k, value_type const& v) const;
node_ptr find_iterator(bucket_ptr bucket, key_type const& k) const;
node_ptr find_iterator(key_type const& k) const;
@@ -354,31 +489,40 @@
std::size_t bucket_index(key_type const& k) const;
void max_load_factor(float z);
std::size_t min_buckets_for_size(std::size_t n) const;
- void calculate_max_load();
+ std::size_t calculate_max_load();
// Constructors
- hash_table(std::size_t n, hasher const& hf, key_equal const& eq, value_allocator const& a);
- hash_table(hash_table const& x);
- hash_table(hash_table const& x, value_allocator const& a);
+ hash_table(std::size_t n, hasher const& hf, key_equal const& eq,
+ node_allocator const& a);
+ hash_table(hash_table const& x, node_allocator const& a);
hash_table(hash_table& x, move_tag m);
- hash_table(hash_table& x, value_allocator const& a, move_tag m);
- ~hash_table();
+ hash_table(hash_table& x, node_allocator const& a, move_tag m);
+ ~hash_table() {}
hash_table& operator=(hash_table const&);
// Iterators
- iterator_base begin() const { return iterator_base(this->cached_begin_bucket_); }
- iterator_base end() const { return iterator_base(this->buckets_end()); }
+ iterator_base begin() const {
+ return this->size_ ?
+ iterator_base(this->cached_begin_bucket_) :
+ iterator_base();
+ }
+ iterator_base end() const {
+ return iterator_base();
+ }
// Swap & Move
void swap(hash_table& x);
+ void fast_swap(hash_table& other);
+ void slow_swap(hash_table& other);
+ void partial_swap(hash_table& other);
void move(hash_table& x);
// Reserve and rehash
- bool reserve(std::size_t n);
+ void create_for_insert(std::size_t n);
bool reserve_for_insert(std::size_t n);
void rehash(std::size_t n);
void rehash_impl(std::size_t n);
@@ -393,7 +537,7 @@
std::size_t count(key_type const& k) const;
iterator_base find(key_type const& k) const;
value_type& at(key_type const& k) const;
- std::pair<iterator_base, iterator_base> equal_range(key_type const& k) const;
+ iterator_pair equal_range(key_type const& k) const;
// Erase
//
@@ -407,7 +551,7 @@
// recompute_begin_bucket
- void recompute_begin_bucket();
+ void init_buckets();
// After an erase cached_begin_bucket_ might be left pointing to
// an empty bucket, so this is called to update it
@@ -424,6 +568,203 @@
// no throw
float load_factor() const;
+
+ iterator_base emplace_empty_impl_with_node(
+ node_constructor&, std::size_t);
+ };
+
+ template <class H, class P, class A, class K>
+ class hash_unique_table :
+ public hash_table<H, P, A, boost::unordered_detail::ungrouped, K>
+
+ {
+ public:
+ typedef H hasher;
+ typedef P key_equal;
+ typedef A value_allocator;
+ typedef K key_extractor;
+
+ typedef hash_table<H, P, A, ungrouped, K> table;
+ typedef hash_node_constructor<A, ungrouped> node_constructor;
+
+ typedef BOOST_DEDUCED_TYPENAME table::key_type key_type;
+ typedef BOOST_DEDUCED_TYPENAME table::value_type value_type;
+ typedef BOOST_DEDUCED_TYPENAME table::node node;
+ typedef BOOST_DEDUCED_TYPENAME table::node_ptr node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME table::bucket_ptr bucket_ptr;
+ typedef BOOST_DEDUCED_TYPENAME table::iterator_base iterator_base;
+ typedef BOOST_DEDUCED_TYPENAME table::extractor extractor;
+
+ typedef std::pair<iterator_base, bool> emplace_return;
+
+ // Constructors
+
+ hash_unique_table(std::size_t n, hasher const& hf, key_equal const& eq,
+ value_allocator const& a)
+ : table(n, hf, eq, a) {}
+ hash_unique_table(hash_unique_table const& x)
+ : table(x, x.node_alloc()) {}
+ hash_unique_table(hash_unique_table const& x, value_allocator const& a)
+ : table(x, a) {}
+ hash_unique_table(hash_unique_table& x, move_tag m)
+ : table(x, m) {}
+ hash_unique_table(hash_unique_table& x, value_allocator const& a,
+ move_tag m)
+ : table(x, a, m) {}
+ ~hash_unique_table() {}
+
+ // Insert methods
+
+ emplace_return emplace_impl_with_node(node_constructor& a);
+ value_type& operator[](key_type const& k);
+
+ // equals
+
+ bool equals(hash_unique_table const&) const;
+
+ node_ptr add_node(node_constructor& a, bucket_ptr bucket);
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+ template<class... Args>
+ emplace_return emplace(Args&&... args);
+ template<class... Args>
+ iterator_base emplace_hint(iterator_base const&, Args&&... args);
+ template<class... Args>
+ emplace_return emplace_impl(key_type const& k, Args&&... args);
+ template<class... Args>
+ emplace_return emplace_impl(no_key, Args&&... args);
+ template<class... Args>
+ emplace_return emplace_empty_impl(Args&&... args);
+#else
+ template <class Arg0>
+ emplace_return emplace(Arg0 const& arg0);
+ template <class Arg0>
+ iterator_base emplace_hint(iterator_base const&, Arg0 const& arg0);
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ iterator_base emplace_hint(iterator_base const& it, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
+ BOOST_UNORDERED_INSERT_IMPL2(z, n, _)
+
+#define BOOST_UNORDERED_INSERT_IMPL2(z, n, _) \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace_impl(key_type const& k, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace_impl(no_key, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace_empty_impl( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n));
+
+ 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
+#undef BOOST_UNORDERED_INSERT_IMPL2
+
+#endif
+
+ // if hash function throws, or inserting > 1 element, basic exception
+ // safety strong otherwise
+ template <class InputIt>
+ void insert_range(InputIt i, InputIt j);
+ template <class InputIt>
+ void insert_range_impl(key_type const&, InputIt i, InputIt j);
+ template <class InputIt>
+ void insert_range_impl(no_key, InputIt i, InputIt j);
+ };
+
+ template <class H, class P, class A, class K>
+ class hash_equivalent_table :
+ public hash_table<H, P, A, boost::unordered_detail::grouped, K>
+
+ {
+ public:
+ typedef H hasher;
+ typedef P key_equal;
+ typedef A value_allocator;
+ typedef K key_extractor;
+
+ typedef hash_table<H, P, A, boost::unordered_detail::grouped, K> table;
+ typedef hash_node_constructor<A, boost::unordered_detail::grouped>
+ node_constructor;
+ typedef hash_iterator_base<A, grouped> iterator_base;
+
+ typedef BOOST_DEDUCED_TYPENAME table::key_type key_type;
+ typedef BOOST_DEDUCED_TYPENAME table::value_type value_type;
+ typedef BOOST_DEDUCED_TYPENAME table::node node;
+ typedef BOOST_DEDUCED_TYPENAME table::node_ptr node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME table::bucket_ptr bucket_ptr;
+ typedef BOOST_DEDUCED_TYPENAME table::extractor extractor;
+
+ // Constructors
+
+ hash_equivalent_table(std::size_t n,
+ hasher const& hf, key_equal const& eq, value_allocator const& a)
+ : table(n, hf, eq, a) {}
+ hash_equivalent_table(hash_equivalent_table const& x)
+ : table(x, x.node_alloc()) {}
+ hash_equivalent_table(hash_equivalent_table const& x,
+ value_allocator const& a)
+ : table(x, a) {}
+ hash_equivalent_table(hash_equivalent_table& x, move_tag m)
+ : table(x, m) {}
+ hash_equivalent_table(hash_equivalent_table& x,
+ value_allocator const& a, move_tag m)
+ : table(x, a, m) {}
+ ~hash_equivalent_table() {}
+
+ // Insert methods
+
+ iterator_base emplace_impl(node_constructor& a);
+ iterator_base emplace_hint_impl(iterator_base const& it,
+ node_constructor& a);
+ void emplace_impl_no_rehash(node_constructor& a);
+
+ // equals
+
+ bool equals(hash_equivalent_table const&) const;
+
+ inline node_ptr add_node(node_constructor& a,
+ bucket_ptr bucket, node_ptr pos);
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+ template <class... Args>
+ iterator_base emplace(Args&&... args);
+ template <class... Args>
+ iterator_base emplace_hint(iterator_base const& it, Args&&... args);
+
+#else
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ iterator_base emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
+ \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ iterator_base emplace_hint(iterator_base const& it, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n));
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT_IMPL, _)
+
+#undef BOOST_UNORDERED_INSERT_IMPL
+#endif
+
+ template <class I>
+ void insert_for_range(I i, I j, forward_traversal_tag);
+ template <class I>
+ void insert_for_range(I i, I j, boost::incrementable_traversal_tag);
+ template <class I>
+ void insert_range(I i, I j);
};
// Iterator Access
@@ -432,7 +773,9 @@
{
public:
template <class Iterator>
- static BOOST_DEDUCED_TYPENAME Iterator::base const& get(Iterator const& it) {
+ static BOOST_DEDUCED_TYPENAME Iterator::base const&
+ get(Iterator const& it)
+ {
return it.base_;
}
};
@@ -462,25 +805,39 @@
private:
typedef hash_buckets<A, G> buckets;
- typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
typedef BOOST_DEDUCED_TYPENAME buckets::node node;
typedef hash_const_local_iterator<A, G> const_local_iterator;
friend class hash_const_local_iterator<A, G>;
- ptr ptr_;
+ node_ptr ptr_;
public:
hash_local_iterator() : ptr_() {}
- explicit hash_local_iterator(ptr x) : ptr_(x) {}
- BOOST_DEDUCED_TYPENAME A::reference operator*() const
- { return node::get_value(ptr_); }
- value_type* operator->() const { return &node::get_value(ptr_); }
- hash_local_iterator& operator++() { ptr_ = next_node(ptr_); return *this; }
- hash_local_iterator operator++(int) { hash_local_iterator tmp(ptr_); ptr_ = next_node(ptr_); return tmp; }
- bool operator==(hash_local_iterator x) const { return ptr_ == x.ptr_; }
- bool operator==(const_local_iterator x) const { return ptr_ == x.ptr_; }
- bool operator!=(hash_local_iterator x) const { return ptr_ != x.ptr_; }
- bool operator!=(const_local_iterator x) const { return ptr_ != x.ptr_; }
+ explicit hash_local_iterator(node_ptr x) : ptr_(x) {}
+ BOOST_DEDUCED_TYPENAME A::reference operator*() const {
+ return node::get_value(ptr_);
+ }
+ value_type* operator->() const {
+ return &node::get_value(ptr_);
+ }
+ hash_local_iterator& operator++() {
+ ptr_ = ptr_->next_; return *this;
+ }
+ hash_local_iterator operator++(int) {
+ hash_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; }
+ bool operator==(hash_local_iterator x) const {
+ return ptr_ == x.ptr_;
+ }
+ bool operator==(const_local_iterator x) const {
+ return ptr_ == x.ptr_;
+ }
+ bool operator!=(hash_local_iterator x) const {
+ return ptr_ != x.ptr_;
+ }
+ bool operator!=(const_local_iterator x) const {
+ return ptr_ != x.ptr_;
+ }
};
template <class A, class G>
@@ -508,14 +865,30 @@
explicit hash_const_local_iterator(ptr x) : ptr_(x) {}
hash_const_local_iterator(local_iterator x) : ptr_(x.ptr_) {}
BOOST_DEDUCED_TYPENAME A::const_reference
- operator*() const { return node::get_value(ptr_); }
- value_type const* operator->() const { return &node::get_value(ptr_); }
- hash_const_local_iterator& operator++() { ptr_ = next_node(ptr_); return *this; }
- hash_const_local_iterator operator++(int) { hash_const_local_iterator tmp(ptr_); ptr_ = next_node(ptr_); return tmp; }
- bool operator==(local_iterator x) const { return ptr_ == x.ptr_; }
- bool operator==(hash_const_local_iterator x) const { return ptr_ == x.ptr_; }
- bool operator!=(local_iterator x) const { return ptr_ != x.ptr_; }
- bool operator!=(hash_const_local_iterator x) const { return ptr_ != x.ptr_; }
+ operator*() const {
+ return node::get_value(ptr_);
+ }
+ value_type const* operator->() const {
+ return &node::get_value(ptr_);
+ }
+ hash_const_local_iterator& operator++() {
+ ptr_ = ptr_->next_; return *this;
+ }
+ hash_const_local_iterator operator++(int) {
+ hash_const_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp;
+ }
+ bool operator==(local_iterator x) const {
+ return ptr_ == x.ptr_;
+ }
+ bool operator==(hash_const_local_iterator x) const {
+ return ptr_ == x.ptr_;
+ }
+ bool operator!=(local_iterator x) const {
+ return ptr_ != x.ptr_;
+ }
+ bool operator!=(hash_const_local_iterator x) const {
+ return ptr_ != x.ptr_;
+ }
};
// iterators
@@ -547,15 +920,30 @@
hash_iterator() : base_() {}
explicit hash_iterator(base const& x) : base_(x) {}
- BOOST_DEDUCED_TYPENAME A::reference
- operator*() const { return node::get_value(base_.get()); }
- value_type* operator->() const { return &node::get_value(base_.get()); }
- hash_iterator& operator++() { base_.increment(); return *this; }
- hash_iterator operator++(int) { hash_iterator tmp(base_); base_.increment(); return tmp; }
- bool operator==(hash_iterator const& x) const { return base_ == x.base_; }
- bool operator==(const_iterator const& x) const { return base_ == x.base_; }
- bool operator!=(hash_iterator const& x) const { return base_ != x.base_; }
- bool operator!=(const_iterator const& x) const { return base_ != x.base_; }
+ BOOST_DEDUCED_TYPENAME A::reference operator*() const {
+ return *base_;
+ }
+ value_type* operator->() const {
+ return &*base_;
+ }
+ hash_iterator& operator++() {
+ base_.increment(); return *this;
+ }
+ hash_iterator operator++(int) {
+ hash_iterator tmp(base_); base_.increment(); return tmp;
+ }
+ bool operator==(hash_iterator const& x) const {
+ return base_ == x.base_;
+ }
+ bool operator==(const_iterator const& x) const {
+ return base_ == x.base_;
+ }
+ bool operator!=(hash_iterator const& x) const {
+ return base_ != x.base_;
+ }
+ bool operator!=(const_iterator const& x) const {
+ return base_ != x.base_;
+ }
};
template <class A, class G>
@@ -584,15 +972,30 @@
hash_const_iterator() : base_() {}
explicit hash_const_iterator(base const& x) : base_(x) {}
hash_const_iterator(iterator const& x) : base_(x.base_) {}
- BOOST_DEDUCED_TYPENAME A::const_reference
- operator*() const { return node::get_value(base_.get()); }
- value_type const* operator->() const { return &node::get_value(base_.get()); }
- hash_const_iterator& operator++() { base_.increment(); return *this; }
- hash_const_iterator operator++(int) { hash_const_iterator tmp(base_); base_.increment(); return tmp; }
- bool operator==(iterator const& x) const { return base_ == x.base_; }
- bool operator==(hash_const_iterator const& x) const { return base_ == x.base_; }
- bool operator!=(iterator const& x) const { return base_ != x.base_; }
- bool operator!=(hash_const_iterator const& x) const { return base_ != x.base_; }
+ BOOST_DEDUCED_TYPENAME A::const_reference operator*() const {
+ return *base_;
+ }
+ value_type const* operator->() const {
+ return &*base_;
+ }
+ hash_const_iterator& operator++() {
+ base_.increment(); return *this;
+ }
+ hash_const_iterator operator++(int) {
+ hash_const_iterator tmp(base_); base_.increment(); return tmp;
+ }
+ bool operator==(iterator const& x) const {
+ return base_ == x.base_;
+ }
+ bool operator==(hash_const_iterator const& x) const {
+ return base_ == x.base_;
+ }
+ bool operator!=(iterator const& x) const {
+ return base_ != x.base_;
+ }
+ bool operator!=(hash_const_iterator const& x) const {
+ return base_ != x.base_;
+ }
};
}}
Deleted: trunk/boost/unordered/detail/insert.hpp
==============================================================================
--- trunk/boost/unordered/detail/insert.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
+++ (empty file)
@@ -1,678 +0,0 @@
-
-// 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_INSERT_HPP_INCLUDED
-#define BOOST_UNORDERED_DETAIL_INSERT_HPP_INCLUDED
-
-#include <boost/unordered/detail/table.hpp>
-#include <boost/unordered/detail/extract_key.hpp>
-
-namespace boost { namespace unordered_detail {
-
- ////////////////////////////////////////////////////////////////////////////
- // A couple of convenience methods for adding nodes.
-
- // H = Has Func
- // P = Predicate
- // A = Value Allocator
- // K = Key Extractor
-
- template <class H, class P, class A, class K>
- class hash_unique_table :
- public hash_table<H, P, A, boost::unordered_detail::ungrouped, K>
-
- {
- public:
- typedef H hasher;
- typedef P key_equal;
- typedef A value_allocator;
- typedef K key_extractor;
-
- typedef hash_table<H, P, A, boost::unordered_detail::ungrouped, K> table;
- typedef hash_node_constructor<A, boost::unordered_detail::ungrouped> node_constructor;
-
- typedef BOOST_DEDUCED_TYPENAME table::key_type key_type;
- typedef BOOST_DEDUCED_TYPENAME table::value_type value_type;
- typedef BOOST_DEDUCED_TYPENAME table::node node;
- typedef BOOST_DEDUCED_TYPENAME table::node_ptr node_ptr;
- typedef BOOST_DEDUCED_TYPENAME table::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME table::iterator_base iterator_base;
- typedef BOOST_DEDUCED_TYPENAME table::extractor extractor;
-
- // Constructors
-
- hash_unique_table(std::size_t n, hasher const& hf, key_equal const& eq, value_allocator const& a)
- : table(n, hf, eq, a) {}
- hash_unique_table(hash_unique_table const& x)
- : table(x) {}
- hash_unique_table(hash_unique_table const& x, value_allocator const& a)
- : table(x, a) {}
- hash_unique_table(hash_unique_table& x, move_tag m)
- : table(x, m) {}
- hash_unique_table(hash_unique_table& x, value_allocator const& a, move_tag m)
- : table(x, a, m) {}
- ~hash_unique_table() {}
-
- // Insert methods
-
- std::pair<iterator_base, bool> emplace_impl_with_node(node_constructor& a);
- value_type& operator[](key_type const& k);
-
- // equals
-
- bool equals(hash_unique_table const&) const;
- static bool group_equals(node_ptr it1, node_ptr it2, set_extractor*);
- static bool group_equals(node_ptr it1, node_ptr it2, map_extractor*);
-
- inline node_ptr add_node(node_constructor& a, bucket_ptr bucket)
- {
- node_ptr n = a.release();
- node::add_to_bucket(n, *bucket);
- ++this->size_;
- if(bucket < this->cached_begin_bucket_) this->cached_begin_bucket_ = bucket;
- return n;
- }
-
-#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<class... Args>
- std::pair<iterator_base, bool> emplace(Args&&... args)
- {
- return emplace_impl(
- extractor::extract(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<class... Args>
- iterator_base emplace_hint(iterator_base const&, Args&&... args)
- {
- return emplace_impl(
- extractor::extract(std::forward<Args>(args)...),
- std::forward<Args>(args)...).first;
- }
-
- template<class... Args>
- std::pair<iterator_base, bool> emplace_impl(key_type const& k, Args&&... args)
- {
- // No side effects in this initial code
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_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(*this);
- a.construct(std::forward<Args>(args)...);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
- // Nothing after this point can throw.
-
- return std::pair<iterator_base, bool>(iterator_base(bucket,
- add_node(a, bucket)), true);
- }
- }
-
- template<class... 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(*this);
- a.construct(std::forward<Args>(args)...);
- return emplace_impl_with_node(a);
- }
-#else
- template <class Arg0>
- std::pair<iterator_base, bool> emplace(Arg0 const& arg0)
- {
- return emplace_impl(extractor::extract(arg0), arg0);
- }
-
- template <class Arg0>
- iterator_base emplace_hint(iterator_base const&, Arg0 const& arg0)
- {
- return emplace_impl(extractor::extract(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(extractor::extract(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(extractor::extract(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) \
- ) \
- { \
- std::size_t hash_value = this->hash_function()(k); \
- bucket_ptr bucket \
- = this->bucket_ptr_from_hash(hash_value); \
- node_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(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, n)); \
- \
- if(reserve_for_insert(this->size_ + 1)) \
- bucket = this->bucket_ptr_from_hash(hash_value); \
- \
- return std::pair<iterator_base, bool>(iterator_base(bucket, \
- add_node(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(*this); \
- 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
-
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <class InputIterator>
- void insert_range(InputIterator i, InputIterator j)
- {
- if(i != j)
- return insert_range_impl(extractor::extract(*i), i, j);
- }
-
- template <class InputIterator>
- void insert_range_impl(key_type const&, InputIterator i, InputIterator j)
- {
- node_constructor a(*this);
-
- for (; i != j; ++i) {
- // No side effects in this initial code
- std::size_t hash_value = this->hash_function()(extractor::extract(*i));
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr pos = find_iterator(bucket, extractor::extract(*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(this->size_ + 1 >= this->max_load_) {
- reserve_for_insert(this->size_ + insert_size(i, j));
- bucket = this->bucket_ptr_from_hash(hash_value);
- }
-
- // Nothing after this point can throw.
- add_node(a, bucket);
- }
- }
- }
-
- template <class InputIterator>
- void insert_range_impl(no_key, InputIterator i, InputIterator j)
- {
- node_constructor a(*this);
-
- for (; i != j; ++i) {
- // No side effects in this initial code
- a.construct(*i);
- emplace_impl_with_node(a);
- }
- }
- };
-
- template <class H, class P, class A, class K>
- class hash_equivalent_table :
- public hash_table<H, P, A, boost::unordered_detail::grouped, K>
-
- {
- public:
- typedef H hasher;
- typedef P key_equal;
- typedef A value_allocator;
- typedef K key_extractor;
-
- typedef hash_table<H, P, A, boost::unordered_detail::grouped, K> table;
- typedef hash_node_constructor<A, boost::unordered_detail::grouped> node_constructor;
-
- typedef BOOST_DEDUCED_TYPENAME table::key_type key_type;
- typedef BOOST_DEDUCED_TYPENAME table::value_type value_type;
- typedef BOOST_DEDUCED_TYPENAME table::node node;
- typedef BOOST_DEDUCED_TYPENAME table::node_ptr node_ptr;
- typedef BOOST_DEDUCED_TYPENAME table::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME table::iterator_base iterator_base;
- typedef BOOST_DEDUCED_TYPENAME table::extractor extractor;
-
- // Constructors
-
- hash_equivalent_table(std::size_t n, hasher const& hf, key_equal const& eq, value_allocator const& a)
- : table(n, hf, eq, a) {}
- hash_equivalent_table(hash_equivalent_table const& x)
- : table(x) {}
- hash_equivalent_table(hash_equivalent_table const& x, value_allocator const& a)
- : table(x, a) {}
- hash_equivalent_table(hash_equivalent_table& x, move_tag m)
- : table(x, m) {}
- hash_equivalent_table(hash_equivalent_table& x, value_allocator const& a, move_tag m)
- : table(x, a, m) {}
- ~hash_equivalent_table() {}
-
- // Insert methods
-
- iterator_base emplace_impl(node_constructor& a);
- iterator_base emplace_hint_impl(iterator_base const& it, node_constructor& a);
- void emplace_impl_no_rehash(node_constructor& a);
-
- // equals
-
- bool equals(hash_equivalent_table const&) const;
- static bool group_equals(node_ptr it1, node_ptr it2, set_extractor*);
- static bool group_equals(node_ptr it1, node_ptr it2, map_extractor*);
-
- inline node_ptr add_node(node_constructor& a, bucket_ptr bucket, node_ptr pos)
- {
- node_ptr n = a.release();
- if(BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- node::add_after_node(n, pos);
- }
- else {
- node::add_to_bucket(n, *bucket);
- if(bucket < this->cached_begin_bucket_) this->cached_begin_bucket_ = bucket;
- }
- ++this->size_;
- return n;
- }
-
- public:
-
- // Insert functions
- //
- // basic exception safety, if hash function throws
- // strong otherwise.
-
-#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(*this);
- 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(*this);
- 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(*this); \
- 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(*this); \
- 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
-
- // Insert from iterator range (equivalent key containers)
-
- private:
-
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <class I>
- void insert_for_range(I i, I j, forward_traversal_tag)
- {
- std::size_t distance = unordered_detail::distance(i, j);
- if(distance == 1) {
- emplace(*i);
- }
- else {
- // Only require basic exception safety here
- reserve_for_insert(this->size_ + distance);
- node_constructor a(*this);
-
- for (; i != j; ++i) {
- a.construct(*i);
- emplace_impl_no_rehash(a);
- }
- }
- }
-
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <class I>
- void insert_for_range(I i, I j,
- boost::incrementable_traversal_tag)
- {
- node_constructor a(*this);
- for (; i != j; ++i) {
- a.construct(*i);
- emplace_impl(a);
- }
- }
-
- public:
-
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <class 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);
- }
- };
-
- ////////////////////////////////////////////////////////////////////////////
- // Unique insert methods
-
- template <class H, class P, class A, class K>
- std::pair<
- BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::iterator_base,
- bool>
- hash_unique_table<H, P, A, K>
- ::emplace_impl_with_node(node_constructor& a)
- {
- // No side effects in this initial code
- key_type const& k = extractor::extract(a.get()->value());
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_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(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
- // Nothing after this point can throw.
-
- return std::pair<iterator_base, bool>(iterator_base(bucket,
- add_node(a, bucket)), true);
- }
- }
-
- // if hash function throws, basic exception safety
- // strong otherwise
- template <class H, class P, class A, class K>
- BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::value_type&
- hash_unique_table<H, P, A, K>
- ::operator[](key_type const& k)
- {
- typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
-
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr pos = find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- return node::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(*this);
- a.construct_pair(k, (mapped_type*) 0);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
- // Nothing after this point can throw.
-
- return node::get_value(add_node(a, bucket));
- }
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // Insert methods
-
- template <class H, class P, class A, class K>
- BOOST_DEDUCED_TYPENAME hash_equivalent_table<H, P, A, K>::iterator_base
- hash_equivalent_table<H, P, A, K>
- ::emplace_impl(node_constructor& a)
- {
- key_type const& k = extractor::extract(a.get()->value());
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr position = find_iterator(bucket, k);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
- // I'm relying on node_ptr not being invalidated by
- // the rehash here.
- return iterator_base(bucket, add_node(a, bucket, position));
- }
-
- template <class H, class P, class A, class K>
- BOOST_DEDUCED_TYPENAME hash_equivalent_table<H, P, A, K>::iterator_base
- hash_equivalent_table<H, P, A, K>
- ::emplace_hint_impl(iterator_base const& it, node_constructor& a)
- {
- // equal can throw, but with no effects
- if (it.is_end() ||
- !equal(extractor::extract(a.get()->value()), node::get_value(it.get()))) {
- // 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.
-
- node_ptr start(it.node_);
- while(node::next_group(start) == start)
- start = node::group_prev(start);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- bucket_ptr bucket = reserve_for_insert(this->size_ + 1) ?
- get_bucket(this->bucket_index(
- extractor::extract(a.get()->value()))) : it.bucket_;
-
- // Nothing after this point can throw
-
- return iterator_base(bucket, add_node(a, bucket, start));
- }
- }
-
- template <class H, class P, class A, class K>
- void hash_equivalent_table<H, P, A, K>
- ::emplace_impl_no_rehash(node_constructor& a)
- {
- key_type const& k = extractor::extract(a.get()->value());
- bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
- add_node(a, bucket, find_iterator(bucket, k));
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // Equalilty check
-
- template <class H, class P, class A, class K>
- inline bool hash_equivalent_table<H, P, A, K>
- ::group_equals(node_ptr it1, node_ptr it2, set_extractor*)
- {
- return node::group_count(it1) == node::group_count(it2);
- }
-
- template <class H, class P, class A, class K>
- inline bool hash_equivalent_table<H, P, A, K>
- ::group_equals(node_ptr it1, node_ptr it2, map_extractor*)
- {
- node_ptr end1 = node::next_group(it1);
- node_ptr end2 = node::next_group(it2);
-
- do {
- if(node::get_value(it1).second != node::get_value(it2).second) return false;
- it1 = next_node(it1);
- it2 = next_node(it2);
- } while(it1 != end1 && it2 != end2);
- return it1 == end1 && it2 == end2;
- }
-
- template <class H, class P, class A, class K>
- bool hash_equivalent_table<H, P, A, K>
- ::equals(hash_equivalent_table<H, P, A, K> const& other) const
- {
- if(this->size_ != other.size_) return false;
-
- for(bucket_ptr i = this->cached_begin_bucket_, j = this->buckets_end(); i != j; ++i)
- {
- for(node_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = node::next_group(it))
- {
- node_ptr other_pos = other.find_iterator(extractor::extract(node::get_value(it)));
- if(!BOOST_UNORDERED_BORLAND_BOOL(other_pos) ||
- !group_equals(it, other_pos, (K*)0))
- return false;
- }
- }
-
- return true;
- }
-
- template <class H, class P, class A, class K>
- inline bool hash_unique_table<H, P, A, K>
- ::group_equals(node_ptr, node_ptr, set_extractor*)
- {
- return true;
- }
-
- template <class H, class P, class A, class K>
- inline bool hash_unique_table<H, P, A, K>
- ::group_equals(node_ptr it1, node_ptr it2, map_extractor*)
- {
- return node::get_value(it1).second == node::get_value(it2).second;
- }
-
- template <class H, class P, class A, class K>
- bool hash_unique_table<H, P, A, K>
- ::equals(hash_unique_table<H, P, A, K> const& other) const
- {
- if(this->size_ != other.size_) return false;
-
- for(bucket_ptr i = this->cached_begin_bucket_, j = this->buckets_end(); i != j; ++i)
- {
- for(node_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = node::next_group(it))
- {
- node_ptr other_pos = other.find_iterator(extractor::extract(node::get_value(it)));
- if(!BOOST_UNORDERED_BORLAND_BOOL(other_pos) ||
- !group_equals(it, other_pos, (K*)0))
- return false;
- }
- }
-
- return true;
- }
-
-}}
-
-#endif
Modified: trunk/boost/unordered/detail/move.hpp
==============================================================================
--- trunk/boost/unordered/detail/move.hpp (original)
+++ trunk/boost/unordered/detail/move.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -109,6 +109,8 @@
{
explicit move_from(T& x) : source(x) { }
T& source;
+private:
+ move_from& operator=(move_from const&);
};
/*************************************************************************************************/
Modified: trunk/boost/unordered/detail/node.hpp
==============================================================================
--- trunk/boost/unordered/detail/node.hpp (original)
+++ trunk/boost/unordered/detail/node.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -24,23 +24,6 @@
namespace boost { namespace unordered_detail {
- template <class BucketPtr>
- inline BucketPtr& next_node(BucketPtr ptr)
- {
- return ptr->next_;
- }
-
- template <class BucketPtr>
- inline std::size_t node_count(BucketPtr ptr, BucketPtr end)
- {
- std::size_t count = 0;
- while(ptr != end) {
- ++count;
- ptr = next_node(ptr);
- }
- return count;
- }
-
////////////////////////////////////////////////////////////////////////////
// ungrouped node implementation
@@ -48,7 +31,7 @@
inline BOOST_DEDUCED_TYPENAME ungrouped_node_base<A>::node_ptr&
ungrouped_node_base<A>::next_group(node_ptr ptr)
{
- return next_node(ptr);
+ return ptr->next_;
}
template <class A>
@@ -60,35 +43,24 @@
template <class A>
inline void ungrouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b)
{
- next_node(n) = b.next_;
+ n->next_ = b.next_;
b.next_ = n;
}
template <class A>
- inline void ungrouped_node_base<A>::add_group_to_bucket(node_ptr n, bucket& b)
+ inline void ungrouped_node_base<A>::add_after_node(node_ptr n,
+ node_ptr position)
{
- next_node(n) = b.next_;
- b.next_ = n;
- }
-
- template <class A>
- inline void ungrouped_node_base<A>::add_after_node(node_ptr n, node_ptr position)
- {
- next_node(n) = next_node(position);
- next_node(position) = position;
+ n->next_ = position->next_;
+ position->next_ = position;
}
template <class A>
- inline void ungrouped_node_base<A>::unlink_node(bucket& b, node_ptr node)
- {
- unlink_nodes(b, node, next_node(node));
- }
-
- template <class A>
- inline void ungrouped_node_base<A>::unlink_nodes(bucket& b, node_ptr begin, node_ptr end)
+ inline void ungrouped_node_base<A>::unlink_nodes(bucket& b,
+ node_ptr begin, node_ptr end)
{
node_ptr* pos = &b.next_;
- while(*pos != begin) pos = &next_node(*pos);
+ while(*pos != begin) pos = &(*pos)->next_;
*pos = end;
}
@@ -99,26 +71,30 @@
}
template <class A>
- inline void ungrouped_node_base<A>::unlink_group(node_ptr* b)
+ inline void ungrouped_node_base<A>::unlink_node(bucket& b, node_ptr node)
{
- *b = next_node(*b);
+ unlink_nodes(b, node, node->next_);
}
////////////////////////////////////////////////////////////////////////////
// grouped node implementation
+ // If ptr is the first element in a group, return pointer to next group.
+ // Otherwise returns a pointer to ptr.
template <class A>
inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr&
- grouped_node_base<A>::group_prev(node_ptr ptr)
+ grouped_node_base<A>::next_group(node_ptr ptr)
{
- return get(ptr).group_prev_;
+ return get(ptr).group_prev_->next_;
}
template <class A>
- inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr&
- grouped_node_base<A>::next_group(node_ptr ptr)
+ inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr
+ grouped_node_base<A>::first_in_group(node_ptr ptr)
{
- return next_node(group_prev(ptr));
+ while(next_group(ptr) == ptr)
+ ptr = get(ptr).group_prev_;
+ return ptr;
}
template <class A>
@@ -128,7 +104,7 @@
std::size_t size = 0;
do {
++size;
- ptr = group_prev(ptr);
+ ptr = get(ptr).group_prev_;
} while(ptr != start);
return size;
}
@@ -136,25 +112,18 @@
template <class A>
inline void grouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b)
{
- next_node(n) = b.next_;
- group_prev(n) = n;
+ n->next_ = b.next_;
+ get(n).group_prev_ = n;
b.next_ = n;
}
template <class A>
- inline void grouped_node_base<A>::add_group_to_bucket(node_ptr n, bucket& b)
+ inline void grouped_node_base<A>::add_after_node(node_ptr n, node_ptr pos)
{
- next_group(n) = b.next_;
- b.next_ = n;
- }
-
- template <class A>
- inline void grouped_node_base<A>::add_after_node(node_ptr n, node_ptr position)
- {
- next_node(n) = next_group(position);
- group_prev(n) = group_prev(position);
- next_group(position) = n;
- group_prev(position) = n;
+ n->next_ = next_group(pos);
+ get(n).group_prev_ = get(pos).group_prev_;
+ next_group(pos) = n;
+ get(pos).group_prev_ = n;
}
// Break a ciruclar list into two, with split as the beginning
@@ -164,29 +133,21 @@
inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr
grouped_node_base<A>::split_group(node_ptr split)
{
- // If split is at the beginning of the group then there's
- // nothing to split.
- if(next_node(group_prev(split)) != split)
- return split;
-
- // Find the start of the group.
- node_ptr start = split;
- do {
- start = group_prev(start);
- } while(next_node(group_prev(start)) == start);
+ node_ptr first = first_in_group(split);
+ if(first == split) return split;
- node_ptr last = group_prev(start);
- group_prev(start) = group_prev(split);
- group_prev(split) = last;
+ node_ptr last = get(first).group_prev_;
+ get(first).group_prev_ = get(split).group_prev_;
+ get(split).group_prev_ = last;
- return start;
+ return first;
}
template <class A>
void grouped_node_base<A>::unlink_node(bucket& b, node_ptr node)
{
- node_ptr next = next_node(node);
- node_ptr* pos = &next_node(group_prev(node));
+ node_ptr next = node->next_;
+ node_ptr* pos = &next_group(node);
if(*pos != node) {
// The node is at the beginning of a group.
@@ -196,31 +157,37 @@
while(*pos != node) pos = &next_group(*pos);
// Remove from group
- if(BOOST_UNORDERED_BORLAND_BOOL(next) && group_prev(next) == node)
- group_prev(next) = group_prev(node);
+ if(BOOST_UNORDERED_BORLAND_BOOL(next) &&
+ get(next).group_prev_ == node)
+ {
+ get(next).group_prev_ = get(node).group_prev_;
+ }
}
- else if(BOOST_UNORDERED_BORLAND_BOOL(next) && group_prev(next) == node) {
+ else if(BOOST_UNORDERED_BORLAND_BOOL(next) &&
+ get(next).group_prev_ == node)
+ {
// The deleted node is not at the end of the group, so
// change the link from the next node.
- group_prev(next) = group_prev(node);
+ get(next).group_prev_ = get(node).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.
- node_ptr x = group_prev(node);
- while(group_prev(x) != node) {
- x = group_prev(x);
+ node_ptr x = get(node).group_prev_;
+ while(get(x).group_prev_ != node) {
+ x = get(x).group_prev_;
}
- group_prev(x) = group_prev(node);
+ get(x).group_prev_ = get(node).group_prev_;
}
*pos = next;
}
template <class A>
- void grouped_node_base<A>::unlink_nodes(bucket& b, node_ptr begin, node_ptr end)
+ void grouped_node_base<A>::unlink_nodes(bucket& b,
+ node_ptr begin, node_ptr end)
{
- node_ptr* pos = &next_node(group_prev(begin));
+ node_ptr* pos = &next_group(begin);
if(*pos != begin) {
// The node is at the beginning of a group.
@@ -238,10 +205,10 @@
node_ptr group2 = split_group(end);
if(begin == group2) {
- node_ptr end1 = group_prev(group1);
- node_ptr end2 = group_prev(group2);
- group_prev(group1) = end2;
- group_prev(group2) = end1;
+ node_ptr end1 = get(group1).group_prev_;
+ node_ptr end2 = get(group2).group_prev_;
+ get(group1).group_prev_ = end2;
+ get(group2).group_prev_ = end1;
}
}
}
@@ -254,12 +221,6 @@
split_group(end);
b.next_ = end;
}
-
- template <class A>
- inline void grouped_node_base<A>::unlink_group(node_ptr* b)
- {
- *b = next_group(*b);
- }
}}
#endif
Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp (original)
+++ trunk/boost/unordered/detail/table.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -23,20 +23,22 @@
// strong exception safety, no side effects
template <class H, class P, class A, class G, class K>
- inline bool hash_table<H, P, A, G, K>
- ::equal(key_type const& k, value_type const& v) const
+ inline bool hash_table<H, P, A, G, K>::equal(
+ key_type const& k, value_type const& v) const
{
- return this->key_eq()(k, extractor::extract(v));
+ return this->key_eq()(k, get_key(v));
}
// strong exception safety, no side effects
template <class H, class P, class A, class G, class K>
inline BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::node_ptr
- hash_table<H, P, A, G, K>
- ::find_iterator(bucket_ptr bucket, key_type const& k) const
+ hash_table<H, P, A, G, K>::find_iterator(
+ bucket_ptr bucket, key_type const& k) const
{
node_ptr it = bucket->next_;
- while (BOOST_UNORDERED_BORLAND_BOOL(it) && !equal(k, node::get_value(it))) {
+ while (BOOST_UNORDERED_BORLAND_BOOL(it) &&
+ !equal(k, node::get_value(it)))
+ {
it = node::next_group(it);
}
@@ -44,23 +46,26 @@
}
// strong exception safety, no side effects
+ // pre: this->buckets_
template <class H, class P, class A, class G, class K>
inline BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::node_ptr
- hash_table<H, P, A, G, K>
- ::find_iterator(key_type const& k) const
+ hash_table<H, P, A, G, K>::find_iterator(key_type const& k) const
{
return find_iterator(this->get_bucket(this->bucket_index(k)), k);
}
// strong exception safety, no side effects
template <class H, class P, class A, class G, class K>
- BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::node_ptr*
- hash_table<H, P, A, G, K>
- ::find_for_erase(bucket_ptr bucket, key_type const& k) const
+ inline BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::node_ptr*
+ hash_table<H, P, A, G, K>::find_for_erase(
+ bucket_ptr bucket, key_type const& k) const
{
node_ptr* it = &bucket->next_;
- while(BOOST_UNORDERED_BORLAND_BOOL(*it) && !equal(k, node::get_value(*it)))
+ while(BOOST_UNORDERED_BORLAND_BOOL(*it) &&
+ !equal(k, node::get_value(*it)))
+ {
it = &node::next_group(*it);
+ }
return it;
}
@@ -70,8 +75,7 @@
// no throw
template <class H, class P, class A, class G, class K>
- std::size_t hash_table<H, P, A, G, K>
- ::max_size() const
+ std::size_t hash_table<H, P, A, G, K>::max_size() const
{
using namespace std;
@@ -82,27 +86,37 @@
// strong safety
template <class H, class P, class A, class G, class K>
- std::size_t hash_table<H, P, A, G, K>
- ::bucket_index(key_type const& k) const
+ inline std::size_t hash_table<H, P, A, G, K>::bucket_index(
+ key_type const& k) const
{
// hash_function can throw:
- return this->bucket_from_hash(this->hash_function()(k));
+ return this->hash_function()(k) % this->bucket_count_;
}
+ // no throw
template <class H, class P, class A, class G, class K>
- void hash_table<H, P, A, G, K>
- ::max_load_factor(float z)
+ inline std::size_t hash_table<H, P, A, G, K>::calculate_max_load()
+ {
+ using namespace std;
+
+ // From 6.3.1/13:
+ // Only resize when size >= mlf_ * count
+ return double_to_size_t(ceil((double) mlf_ * this->bucket_count_));
+ }
+
+ template <class H, class P, class A, class G, class K>
+ void hash_table<H, P, A, G, K>::max_load_factor(float z)
{
BOOST_ASSERT(z > 0);
mlf_ = (std::max)(z, minimum_max_load_factor);
- this->calculate_max_load();
+ this->max_load_ = this->calculate_max_load();
}
// no throw
template <class H, class P, class A, class G, class K>
- std::size_t hash_table<H, P, A, G, K>
- ::min_buckets_for_size(std::size_t n) const
+ inline std::size_t hash_table<H, P, A, G, K>::min_buckets_for_size(
+ std::size_t n) const
{
BOOST_ASSERT(this->mlf_ != 0);
@@ -114,130 +128,146 @@
//
// Or from rehash post-condition:
// count > size / mlf_
- return double_to_size_t(floor(n / (double) mlf_)) + 1;
+ return next_prime(double_to_size_t(floor(n / (double) mlf_)) + 1);
}
- // no throw
+ ////////////////////////////////////////////////////////////////////////////
+ // recompute_begin_bucket
+
+ // init_buckets
+
template <class H, class P, class A, class G, class K>
- void hash_table<H, P, A, G, K>
- ::calculate_max_load()
+ inline void hash_table<H, P, A, G, K>::init_buckets()
{
- using namespace std;
-
- // From 6.3.1/13:
- // Only resize when size >= mlf_ * count
- max_load_ = double_to_size_t(ceil((double) mlf_ * this->bucket_count()));
+ if (this->size_) {
+ this->cached_begin_bucket_ = this->buckets_;
+ while (!this->cached_begin_bucket_->next_)
+ ++this->cached_begin_bucket_;
+ } else {
+ this->cached_begin_bucket_ = this->get_bucket(this->bucket_count_);
+ }
+ this->max_load_ = calculate_max_load();
}
- ////////////////////////////////////////////////////////////////////////////
- // Constructors
+ // After an erase cached_begin_bucket_ might be left pointing to
+ // an empty bucket, so this is called to update it
+ //
+ // no throw
template <class H, class P, class A, class G, class K>
- hash_table<H, P, A, G, K>
- ::hash_table(std::size_t n, hasher const& hf, key_equal const& eq, value_allocator const& a) :
- buckets(a, next_prime(n)), func_(false), cached_begin_bucket_(), size_(), mlf_(1.0f), max_load_(0)
- {
- std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
- functions(hf, eq));
- this->cached_begin_bucket_ = this->buckets_end();
- this->calculate_max_load();
- }
+ inline void hash_table<H, P, A, G, K>::recompute_begin_bucket(bucket_ptr b)
+ {
+ BOOST_ASSERT(!(b < this->cached_begin_bucket_));
- template <class H, class P, class A, class G, class K>
- hash_table<H, P, A, G, K>
- ::hash_table(hash_table const& x) :
- buckets(x.node_alloc(), next_prime(x.min_buckets_for_size(x.size_))), func_(false), cached_begin_bucket_(), size_(), mlf_(x.mlf_), max_load_(0)
- {
- std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
- x.current());
- this->calculate_max_load();
- x.copy_buckets_to(*this);
- this->size_ = x.size_;
- this->recompute_begin_bucket();
+ if(b == this->cached_begin_bucket_)
+ {
+ if (this->size_ != 0) {
+ while (!this->cached_begin_bucket_->next_)
+ ++this->cached_begin_bucket_;
+ } else {
+ this->cached_begin_bucket_ =
+ this->get_bucket(this->bucket_count_);
+ }
+ }
}
- // Copy Construct with allocator
+ // This is called when a range has been erased
+ //
+ // no throw
template <class H, class P, class A, class G, class K>
- hash_table<H, P, A, G, K>
- ::hash_table(hash_table const& x, value_allocator const& a) :
- buckets(a, next_prime(x.min_buckets_for_size(x.size_))), func_(false), cached_begin_bucket_(), size_(), mlf_(x.mlf_), max_load_(0)
- {
- std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
- x.current());
- this->cached_begin_bucket_ = this->buckets_end();
- this->calculate_max_load();
- x.copy_buckets_to(*this);
- this->size_ = x.size_;
- this->recompute_begin_bucket();
- }
+ inline void hash_table<H, P, A, G, K>::recompute_begin_bucket(
+ bucket_ptr b1, bucket_ptr b2)
+ {
+ BOOST_ASSERT(!(b1 < this->cached_begin_bucket_) && !(b2 < b1));
+ BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(b2->next_));
- // Move Construct
+ if(b1 == this->cached_begin_bucket_ && !b1->next_)
+ this->cached_begin_bucket_ = b2;
+ }
+ // no throw
template <class H, class P, class A, class G, class K>
- hash_table<H, P, A, G, K>
- ::hash_table(hash_table& x, move_tag m) :
- buckets(x, m), func_(false), cached_begin_bucket_(), size_(), mlf_(x.mlf_), max_load_(0)
+ inline float hash_table<H, P, A, G, K>::load_factor() const
{
- this->cached_begin_bucket_ = x.cached_begin_bucket_;
- this->size_ = x.size_;
- x.cached_begin_bucket_ = bucket_ptr();
- x.size_ = 0;
+ BOOST_ASSERT(this->bucket_count_ != 0);
+ return static_cast<float>(this->size_)
+ / static_cast<float>(this->bucket_count_);
+ }
- // TODO: Shouldn't I move the functions if poss.
- std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
- x.current());
- }
+ ////////////////////////////////////////////////////////////////////////////
+ // Constructors
template <class H, class P, class A, class G, class K>
- hash_table<H, P, A, G, K>
- ::hash_table(hash_table& x, value_allocator const& a, move_tag m) :
- buckets(x, a, m), func_(false), cached_begin_bucket_(), size_(), mlf_(x.mlf_), max_load_(0)
+ hash_table<H, P, A, G, K>::hash_table(std::size_t n,
+ hasher const& hf, key_equal const& eq, node_allocator const& a)
+ : buckets(a, next_prime(n)),
+ base(hf, eq),
+ size_(),
+ mlf_(1.0f),
+ cached_begin_bucket_(),
+ max_load_(0)
{
- std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
- x.current());
+ }
- this->calculate_max_load(); // no throw
+ // Copy Construct with allocator
- if(!this->buckets_) {
- buckets new_buckets(this->node_alloc(), x.min_buckets_for_size(x.size_));
- x.copy_buckets_to(new_buckets);
- new_buckets.swap(*this);
- this->size_ = x.size_;
- this->recompute_begin_bucket();
- }
- else {
- this->cached_begin_bucket_ = x.cached_begin_bucket_;
- this->size_ = x.size_;
- x.cached_begin_bucket_ = bucket_ptr();
- x.size_ = 0;
+ template <class H, class P, class A, class G, class K>
+ hash_table<H, P, A, G, K>::hash_table(hash_table const& x,
+ node_allocator const& a)
+ : buckets(a, x.min_buckets_for_size(x.size_)),
+ base(x),
+ size_(x.size_),
+ mlf_(x.mlf_),
+ cached_begin_bucket_(),
+ max_load_(0)
+ {
+ if(x.size_) {
+ x.copy_buckets_to(*this);
+ this->init_buckets();
}
}
+ // Move Construct
+
template <class H, class P, class A, class G, class K>
- hash_table<H, P, A, G, K>::~hash_table()
- {
- BOOST_UNORDERED_DESTRUCT(this->get_functions(false), functions);
- BOOST_UNORDERED_DESTRUCT(this->get_functions(true), functions);
+ hash_table<H, P, A, G, K>::hash_table(hash_table& x, move_tag)
+ : buckets(x.node_alloc(), x.bucket_count_),
+ base(x),
+ size_(0),
+ mlf_(1.0f),
+ cached_begin_bucket_(),
+ max_load_(0)
+ {
+ this->partial_swap(x);
}
- // TODO: Reuse current nodes amd buckets?
template <class H, class P, class A, class G, class K>
- hash_table<H, P, A, G, K>& hash_table<H, P, A, G, K>::operator=(hash_table const& x)
+ hash_table<H, P, A, G, K>::hash_table(hash_table& x,
+ node_allocator const& a, move_tag)
+ : buckets(a, x.bucket_count_),
+ base(x),
+ size_(0),
+ mlf_(x.mlf_),
+ cached_begin_bucket_(),
+ max_load_(0)
{
- if(this != &x) {
- this->clear(); // no throw
- this->set_functions(
- this->buffer_functions(x)); // throws, strong
- this->mlf_ = x.mlf_; // no throw
- buckets new_buckets(this->node_alloc(), x.min_buckets_for_size(x.size_));
- x.copy_buckets_to(new_buckets);
- new_buckets.swap(*this);
- this->calculate_max_load(); // no throw
+ if(a == x.node_alloc()) {
+ this->partial_swap(x);
+ }
+ else if(x.size_) {
+ x.copy_buckets_to(*this);
this->size_ = x.size_;
- this->recompute_begin_bucket();
+ this->init_buckets();
}
+ }
+ template <class H, class P, class A, class G, class K>
+ hash_table<H, P, A, G, K>& hash_table<H, P, A, G, K>::operator=(
+ hash_table const& x)
+ {
+ hash_table tmp(x, this->node_alloc());
+ this->fast_swap(tmp);
return *this;
}
@@ -252,58 +282,81 @@
// or if allocators are unequal.
template <class H, class P, class A, class G, class K>
- void hash_table<H, P, A, G, K>
- ::swap(hash_table& x)
+ inline void hash_table<H, P, A, G, K>::partial_swap(hash_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;
+ this->buckets::swap(x); // No throw
+ std::swap(this->size_, x.size_);
+ std::swap(this->mlf_, x.mlf_);
+ std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_);
+ std::swap(this->max_load_, x.max_load_);
+ }
+ template <class H, class P, class A, class G, class K>
+ inline void hash_table<H, P, A, G, K>::fast_swap(hash_table& x)
+ {
// 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 = this->buffer_functions(x);
- functions_ptr new_func_that = x.buffer_functions(*this);
-
- if(this->node_alloc() == x.node_alloc()) {
- this->buckets::swap(x); // No throw
- std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_);
- std::swap(this->size_, x.size_);
+ {
+ set_hash_functions<H, P> op1(*this, x);
+ set_hash_functions<H, P> op2(x, *this);
+ op1.commit();
+ op2.commit();
}
- else {
+ this->buckets::swap(x); // No throw
+ std::swap(this->size_, x.size_);
+ std::swap(this->mlf_, x.mlf_);
+ std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_);
+ std::swap(this->max_load_, x.max_load_);
+ }
+
+ template <class H, class P, class A, class G, class K>
+ inline void hash_table<H, P, A, G, K>::slow_swap(hash_table& x)
+ {
+ 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.
+ set_hash_functions<H, P> op1(*this, x);
+ set_hash_functions<H, P> op2(x, *this);
+
// Create new buckets in separate hash_buckets objects
// which will clean up if anything throws an exception.
// (all can throw, but with no effect as these are new objects).
-
- buckets new_this(this->node_alloc(), x.min_buckets_for_size(x.size_));
- x.copy_buckets_to(new_this);
-
- buckets new_that(x.node_alloc(), this->min_buckets_for_size(this->size_));
- copy_buckets_to(new_that);
-
+
+ buckets b1(this->node_alloc(), x.min_buckets_for_size(x.size_));
+ if(x.size_) x.copy_buckets_to(b1);
+
+ buckets b2(x.node_alloc(), this->min_buckets_for_size(this->size_));
+ if(this->size_) copy_buckets_to(b2);
+
// Modifying the data, so no throw from now on.
-
- this->buckets::swap(new_this);
- x.buckets::swap(new_that);
- std::swap(this->size_, x.size_);
- this->recompute_begin_bucket();
- x.recompute_begin_bucket();
+
+ b1.swap(*this);
+ b2.swap(x);
+ op1.commit();
+ op2.commit();
}
+
+ std::swap(this->size_, x.size_);
- // The rest is no throw.
-
- std::swap(this->mlf_, x.mlf_);
-
- this->set_functions(new_func_this);
- x.set_functions(new_func_that);
+ if(this->buckets_) this->init_buckets();
+ if(x.buckets_) x.init_buckets();
+ }
- //TODO: Test that this works:
- this->calculate_max_load();
- x.calculate_max_load();
+ template <class H, class P, class A, class G, class K>
+ void hash_table<H, P, A, G, K>::swap(hash_table& x)
+ {
+ if(this->node_alloc() == x.node_alloc()) {
+ if(this != &x) this->fast_swap(x);
+ }
+ else {
+ this->slow_swap(x);
+ }
}
+
// Move
//
@@ -313,40 +366,37 @@
// or if allocators are unequal.
template <class H, class P, class A, class G, class K>
- void hash_table<H, P, A, G, K>
- ::move(hash_table& x)
+ void hash_table<H, P, A, G, K>::move(hash_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 = this->buffer_functions(x);
+ set_hash_functions<H, P> new_func_this(*this, x);
if(this->node_alloc() == x.node_alloc()) {
this->buckets::move(x); // no throw
this->size_ = x.size_;
this->cached_begin_bucket_ = x.cached_begin_bucket_;
+ this->max_load_ = x.max_load_;
x.size_ = 0;
- x.cached_begin_bucket_ = bucket_ptr();
}
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).
- buckets new_this(this->node_alloc(), next_prime(x.min_buckets_for_size(x.size_)));
- x.copy_buckets_to(new_this);
+ buckets b(this->node_alloc(), x.min_buckets_for_size(x.size_));
+ if(x.size_) x.copy_buckets_to(b);
// Start updating the data here, no throw from now on.
- this->buckets::move(new_this);
this->size_ = x.size_;
- this->recompute_begin_bucket();
+ b.swap(*this);
+ this->init_buckets();
}
// We've made it, the rest is no throw.
this->mlf_ = x.mlf_;
- this->set_functions(new_func_this);
-
- this->calculate_max_load();
+ new_func_this.commit();
}
////////////////////////////////////////////////////////////////////////////
@@ -354,96 +404,100 @@
// basic exception safety
template <class H, class P, class A, class G, class K>
- inline bool hash_table<H, P, A, G, K>
- ::reserve(std::size_t n)
+ inline void hash_table<H, P, A, G, K>::create_for_insert(std::size_t n)
{
- bool need_to_reserve = n >= this->max_load_;
- // throws - basic:
- if (need_to_reserve) rehash_impl(this->min_buckets_for_size(n));
- BOOST_ASSERT(n < this->max_load_ || n > max_size());
- return need_to_reserve;
+ if(n > this->bucket_count_)
+ this->bucket_count_ = this->min_buckets_for_size(n);
+ this->create_buckets();
+ this->init_buckets();
}
// basic exception safety
template <class H, class P, class A, class G, class K>
- inline bool hash_table<H, P, A, G, K>
- ::reserve_for_insert(std::size_t n)
+ inline bool hash_table<H, P, A, G, K>::reserve_for_insert(std::size_t n)
{
- bool need_to_reserve = n >= this->max_load_;
- // throws - basic:
- if (need_to_reserve) {
+ if(n >= max_load_) {
std::size_t s = this->size_;
s = s + (s >> 1);
- s = s > n ? s : n;
- rehash_impl(this->min_buckets_for_size(s));
+ n = this->min_buckets_for_size(s > n ? s : n);
+ if(n != this->bucket_count_) {
+ rehash_impl(n);
+ return true;
+ }
}
- BOOST_ASSERT(n < this->max_load_ || n > max_size());
- return need_to_reserve;
+
+ return false;
}
// if hash function throws, basic exception safety
// strong otherwise.
+ // TODO: Should this always create buckets?
template <class H, class P, class A, class G, class K>
- void hash_table<H, P, A, G, K>
+ inline void hash_table<H, P, A, G, K>
::rehash(std::size_t n)
{
using namespace std;
- // no throw:
- std::size_t min_size = this->min_buckets_for_size(this->size_);
- // basic/strong:
- rehash_impl(min_size > n ? min_size : n);
+ if(!this->buckets_) {
+ this->bucket_count_ = next_prime(n);
+ this->create_buckets();
+ this->init_buckets();
+ }
+ else if(n != this->bucket_count_) {
+ // no throw:
+ // TODO: Needlessly calling next_prime twice.
+ std::size_t min_size = this->min_buckets_for_size(this->size_);
+ n = next_prime(n);
+ n = min_size > n ? min_size : n;
- BOOST_ASSERT((float) this->bucket_count() > (float) this->size_ / this->mlf_
- && this->bucket_count() >= n);
+ rehash_impl(n);
+ }
}
// if hash function throws, basic exception safety
// strong otherwise
+ // TODO: Rewrite so that it doesn't need to keep updating size_.
+
template <class H, class P, class A, class G, class K>
void hash_table<H, P, A, G, K>
::rehash_impl(std::size_t n)
- {
- n = next_prime(n); // no throw
-
- if (n == this->bucket_count()) // no throw
- return;
-
- // Save the size to restore it if successful
+ {
+ hasher const& hf = this->hash_function();
std::size_t size = this->size_;
+ bucket_ptr end = this->get_bucket(this->bucket_count_);
- // Create another buckets to move the nodes into.
- buckets dst(this->node_alloc(), n);// throws, separate
+ buckets dst(this->node_alloc(), n);
+ dst.create_buckets();
- // Move the nodes to dst.
- hasher const& hf = this->hash_function();
- bucket_ptr end = this->buckets_end();
+ buckets src(this->node_alloc(), this->bucket_count_);
+ src.swap(*this);
+ this->size_ = 0;
- for(; this->cached_begin_bucket_ != end; ++this->cached_begin_bucket_) {
- bucket_ptr src_bucket = this->cached_begin_bucket_;
- while(src_bucket->next_) {
- // Move the first group of equivalent nodes in
- // src_bucket to dst.
+ for(bucket_ptr bucket = this->cached_begin_bucket_;
+ bucket != end; ++bucket)
+ {
+ node_ptr group = bucket->next_;
+ while(group) {
+ // Move the first group of equivalent nodes in bucket to dst.
// This next line throws iff the hash function throws.
bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
- hf(extractor::extract(node::get_value(src_bucket->next_))));
+ hf(get_key_from_ptr(group)));
-
- node_ptr n = src_bucket->next_;
- this->size_ -= node::group_count(n);
- node::unlink_group(&src_bucket->next_);
- node::add_group_to_bucket(n, *dst_bucket);
+ node_ptr& next_group = node::next_group(group);
+ bucket->next_ = next_group;
+ next_group = dst_bucket->next_;
+ dst_bucket->next_ = group;
+ group = bucket->next_;
}
}
// Swap the new nodes back into the container and setup the local
// variables.
- dst.swap(*this); // no throw
this->size_ = size;
- this->recompute_begin_bucket(); // no throw
- this->calculate_max_load(); // no throw
+ dst.swap(*this); // no throw
+ this->init_buckets();
}
////////////////////////////////////////////////////////////////////////////
@@ -458,12 +512,13 @@
void hash_table<H, P, A, G, K>
::copy_buckets_to(buckets& dst) const
{
- BOOST_ASSERT(this->buckets_ && dst.buckets_);
+ BOOST_ASSERT(this->buckets_ && !dst.buckets_);
hasher const& hf = this->hash_function();
- bucket_ptr end = this->buckets_end();
+ bucket_ptr end = this->get_bucket(this->bucket_count_);
hash_node_constructor<A, G> a(dst);
+ dst.create_buckets();
// no throw:
for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) {
@@ -471,7 +526,7 @@
for(node_ptr it = i->next_; it;) {
// hash function can throw.
bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
- hf(extractor::extract(node::get_value(it))));
+ hf(get_key_from_ptr(it)));
// throws, strong
node_ptr group_end = node::next_group(it);
@@ -480,7 +535,7 @@
node_ptr n = a.release();
node::add_to_bucket(n, *dst_bucket);
- for(it = next_node(it); it != group_end; it = next_node(it)) {
+ for(it = it->next_; it != group_end; it = it->next_) {
a.construct(node::get_value(it));
node::add_after_node(a.release(), n);
}
@@ -498,8 +553,7 @@
// strong exception safety, no side effects
template <class H, class P, class A, class G, class K>
- std::size_t hash_table<H, P, A, G, K>
- ::count(key_type const& k) const
+ std::size_t hash_table<H, P, A, G, K>::count(key_type const& k) const
{
if(!this->size_) return 0;
node_ptr it = find_iterator(k); // throws, strong
@@ -511,8 +565,7 @@
// strong exception safety, no side effects
template <class H, class P, class A, class G, class K>
BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_base
- hash_table<H, P, A, G, K>
- ::find(key_type const& k) const
+ hash_table<H, P, A, G, K>::find(key_type const& k) const
{
if(!this->size_) return this->end();
@@ -527,8 +580,7 @@
template <class H, class P, class A, class G, class K>
BOOST_DEDUCED_TYPENAME A::value_type&
- hash_table<H, P, A, G, K>
- ::at(key_type const& k) const
+ hash_table<H, P, A, G, K>::at(key_type const& k) const
{
if(!this->size_)
throw std::out_of_range("Unable to find key in unordered_map.");
@@ -546,26 +598,22 @@
//
// strong exception safety, no side effects
template <class H, class P, class A, class G, class K>
- std::pair<
- BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_base,
- BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_base
- >
- hash_table<H, P, A, G, K>
- ::equal_range(key_type const& k) const
+ BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_pair
+ hash_table<H, P, A, G, K>::equal_range(key_type const& k) const
{
if(!this->size_)
- return std::pair<iterator_base, iterator_base>(this->end(), this->end());
+ return iterator_pair(this->end(), this->end());
bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
node_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(node::next_group(second.node_));
- return std::pair<iterator_base, iterator_base>(first, second);
+ second.increment_bucket(node::next_group(second.node_));
+ return iterator_pair(first, second);
}
else {
- return std::pair<iterator_base, iterator_base>(this->end(), this->end());
+ return iterator_pair(this->end(), this->end());
}
}
@@ -575,18 +623,37 @@
template <class H, class P, class A, class G, class K>
void hash_table<H, P, A, G, K>::clear()
{
- for(bucket_ptr begin = this->buckets_begin(), end = this->buckets_end(); begin != end; ++begin) {
+ // TODO: Is this check needed when called internally?
+ if(!this->size_) return;
+
+ bucket_ptr end = this->get_bucket(this->bucket_count_);
+ for(bucket_ptr begin = this->buckets_; begin != end; ++begin) {
this->clear_bucket(begin);
}
- this->cached_begin_bucket_ = this->buckets_end();
this->size_ = 0;
+ this->cached_begin_bucket_ = end;
}
template <class H, class P, class A, class G, class K>
+ inline std::size_t hash_table<H, P, A, G, K>::erase_group(
+ node_ptr* it, bucket_ptr bucket)
+ {
+ node_ptr pos = *it;
+ node_ptr end = node::next_group(pos);
+ *it = end;
+ std::size_t count = this->delete_nodes(pos, end);
+ this->size_ -= count;
+ this->recompute_begin_bucket(bucket);
+ return count;
+ }
+
+ template <class H, class P, class A, class G, class K>
std::size_t hash_table<H, P, A, G, K>
::erase_key(key_type const& k)
{
+ if(!this->size_) return 0;
+
// No side effects in initial section
bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
node_ptr* it = this->find_for_erase(bucket, k);
@@ -600,135 +667,78 @@
BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_base
hash_table<H, P, A, G, K>::erase(iterator_base r)
{
- BOOST_ASSERT(!r.is_end());
+ BOOST_ASSERT(r.node_);
iterator_base next = r;
next.increment();
--this->size_;
node::unlink_node(*r.bucket_, r.node_);
- this->destruct_node(r.node_);
+ this->delete_node(r.node_);
// r has been invalidated but its bucket is still valid
this->recompute_begin_bucket(r.bucket_, next.bucket_);
return next;
}
template <class H, class P, class A, class G, class K>
- inline std::size_t hash_table<H, P, A, G, K>::erase_group(node_ptr* it, bucket_ptr bucket)
- {
- node_ptr pos = *it;
- std::size_t count = node::group_count(*it);
- this->size_ -= count;
- node::unlink_group(it);
- this->delete_group(pos);
- this->recompute_begin_bucket(bucket);
- return count;
- }
-
- template <class H, class P, class A, class G, class K>
BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_base
- hash_table<H, P, A, G, K>::erase_range(iterator_base r1, iterator_base r2)
+ hash_table<H, P, A, G, K>::erase_range(
+ iterator_base r1, iterator_base r2)
{
if(r1 != r2)
{
- BOOST_ASSERT(!r1.is_end());
-
+ BOOST_ASSERT(r1.node_);
if (r1.bucket_ == r2.bucket_) {
- this->size_ -= node_count(r1.node_, r2.node_);
node::unlink_nodes(*r1.bucket_, r1.node_, r2.node_);
- this->delete_nodes(r1.node_, r2.node_);
+ this->size_ -= this->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_->next_);
+ BOOST_ASSERT(r1.bucket_->next_);
}
else {
- BOOST_ASSERT(r1.bucket_ < r2.bucket_);
-
- this->size_ -= node_count(r1.node_, node_ptr());
+ bucket_ptr end_bucket = r2.node_ ?
+ r2.bucket_ : this->get_bucket(this->bucket_count_);
+ BOOST_ASSERT(r1.bucket_ < end_bucket);
node::unlink_nodes(*r1.bucket_, r1.node_, node_ptr());
- this->delete_to_bucket_end(r1.node_);
+ this->size_ -= this->delete_nodes(r1.node_, node_ptr());
bucket_ptr i = r1.bucket_;
- for(++i; i != r2.bucket_; ++i) {
- this->size_ -= node_count(i->next_, node_ptr());
- this->clear_bucket(i);
+ for(++i; i != end_bucket; ++i) {
+ this->size_ -= this->delete_nodes(i->next_, node_ptr());
+ i->next_ = node_ptr();
}
- if(!r2.is_end()) {
+ if(r2.node_) {
node_ptr first = r2.bucket_->next_;
- this->size_ -= node_count(r2.bucket_->next_, r2.node_);
node::unlink_nodes(*r2.bucket_, r2.node_);
- this->delete_nodes(first, r2.node_);
+ this->size_ -= this->delete_nodes(first, r2.node_);
}
// r1 has been invalidated but its bucket is still
// valid.
- this->recompute_begin_bucket(r1.bucket_, r2.bucket_);
+ this->recompute_begin_bucket(r1.bucket_, end_bucket);
}
}
return r2;
}
-
- template <class H, class P, class A, class G, class K>
- inline void hash_table<H, P, A, G, K>::recompute_begin_bucket()
- {
- if (this->size_ != 0) {
- this->cached_begin_bucket_ = this->buckets_begin();
- while (!this->cached_begin_bucket_->next_)
- ++this->cached_begin_bucket_;
- } else {
- this->cached_begin_bucket_ = this->buckets_end();
- }
- }
-
- // 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
-
- template <class H, class P, class A, class G, class K>
- inline void hash_table<H, P, A, G, K>::recompute_begin_bucket(bucket_ptr b)
- {
- BOOST_ASSERT(!(b < this->cached_begin_bucket_));
-
- if(b == this->cached_begin_bucket_)
- {
- if (this->size_ != 0) {
- while (!this->cached_begin_bucket_->next_)
- ++this->cached_begin_bucket_;
- } else {
- this->cached_begin_bucket_ = this->buckets_end();
- }
- }
- }
-
- // This is called when a range has been erased
- //
- // no throw
-
template <class H, class P, class A, class G, class K>
- inline void hash_table<H, P, A, G, K>::recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2)
+ BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_base
+ hash_table<H, P, A, G, K>::emplace_empty_impl_with_node(
+ node_constructor& a, std::size_t n)
{
- BOOST_ASSERT(!(b1 < this->cached_begin_bucket_) && !(b2 < b1));
- BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(b2->next_));
-
- if(b1 == this->cached_begin_bucket_ && !b1->next_)
- this->cached_begin_bucket_ = b2;
+ key_type const& k = get_key(a.value());
+ std::size_t hash_value = this->hash_function()(k);
+ if(this->buckets_) this->reserve_for_insert(n);
+ else this->create_for_insert(n);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_ptr node = a.release();
+ node::add_to_bucket(node, *bucket);
+ ++this->size_;
+ this->cached_begin_bucket_ = bucket;
+ return iterator_base(bucket, node);
}
-
- // no throw
- template <class H, class P, class A, class G, class K>
- inline float hash_table<H, P, A, G, K>::load_factor() const
- {
- BOOST_ASSERT(this->bucket_count_ != 0);
- return static_cast<float>(this->size_)
- / static_cast<float>(this->bucket_count_);
- }
-
}}
#endif
Added: trunk/boost/unordered/detail/unique.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/unordered/detail/unique.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -0,0 +1,431 @@
+
+// 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_UNIQUE_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED
+
+#include <boost/unordered/detail/table.hpp>
+#include <boost/unordered/detail/extract_key.hpp>
+
+namespace boost { namespace unordered_detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Equality
+
+ template <class H, class P, class A, class K>
+ bool hash_unique_table<H, P, A, K>
+ ::equals(hash_unique_table<H, P, A, K> const& other) const
+ {
+ if(this->size_ != other.size_) return false;
+ if(!this->size_) return true;
+
+ bucket_ptr end = this->get_bucket(this->bucket_count_);
+ for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i)
+ {
+ node_ptr it1 = i->next_;
+ while(BOOST_UNORDERED_BORLAND_BOOL(it1))
+ {
+ node_ptr it2 = other.find_iterator(get_key_from_ptr(it1));
+ if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false;
+ if(!extractor::compare_mapped(
+ node::get_value(it1), node::get_value(it2)))
+ return false;
+ it1 = it1->next_;
+ }
+ }
+
+ return true;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // A convenience method for adding nodes.
+
+ template <class H, class P, class A, class K>
+ inline BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::node_ptr
+ hash_unique_table<H, P, A, K>::add_node(node_constructor& a,
+ bucket_ptr bucket)
+ {
+ node_ptr n = a.release();
+ node::add_to_bucket(n, *bucket);
+ ++this->size_;
+ if(bucket < this->cached_begin_bucket_)
+ this->cached_begin_bucket_ = bucket;
+ return n;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Insert methods
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ template <class H, class P, class A, class K>
+ BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::value_type&
+ hash_unique_table<H, P, A, K>::operator[](key_type const& k)
+ {
+ typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
+
+ std::size_t hash_value = this->hash_function()(k);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+
+ if(!this->buckets_) {
+ node_constructor a(*this);
+ a.construct_pair(k, (mapped_type*) 0);
+ return *this->emplace_empty_impl_with_node(a, 1);
+ }
+
+ node_ptr pos = find_iterator(bucket, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ return node::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(*this);
+ a.construct_pair(k, (mapped_type*) 0);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->reserve_for_insert(this->size_ + 1))
+ bucket = this->bucket_ptr_from_hash(hash_value);
+
+ // Nothing after this point can throw.
+
+ return node::get_value(add_node(a, bucket));
+ }
+ }
+
+ template <class H, class P, class A, class K>
+ inline BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::emplace_return
+ hash_unique_table<H, P, A, K>
+ ::emplace_impl_with_node(node_constructor& a)
+ {
+ // No side effects in this initial code
+ key_type const& k = get_key(a.value());
+ std::size_t hash_value = this->hash_function()(k);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_ptr pos = find_iterator(bucket, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Found an existing key, return it (no throw).
+ return emplace_return(iterator_base(bucket, pos), false);
+ } else {
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->reserve_for_insert(this->size_ + 1))
+ bucket = this->bucket_ptr_from_hash(hash_value);
+
+ // Nothing after this point can throw.
+
+ return emplace_return(
+ iterator_base(bucket, add_node(a, bucket)),
+ true);
+ }
+ }
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+ template <class H, class P, class A, class K>
+ template<class... Args>
+ inline BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::emplace_return
+ hash_unique_table<H, P, A, K>::emplace_impl(key_type const& k,
+ Args&&... args)
+ {
+ // No side effects in this initial code
+ std::size_t hash_value = this->hash_function()(k);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_ptr pos = find_iterator(bucket, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Found an existing key, return it (no throw).
+ return emplace_return(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(*this);
+ a.construct(std::forward<Args>(args)...);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->reserve_for_insert(this->size_ + 1))
+ bucket = this->bucket_ptr_from_hash(hash_value);
+
+ // Nothing after this point can throw.
+
+ return emplace_return(
+ iterator_base(bucket, add_node(a, bucket)),
+ true);
+ }
+ }
+
+ template <class H, class P, class A, class K>
+ template<class... Args>
+ inline BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::emplace_return
+ hash_unique_table<H, P, A, K>::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(*this);
+ a.construct(std::forward<Args>(args)...);
+ return emplace_impl_with_node(a);
+ }
+
+ template <class H, class P, class A, class K>
+ template<class... Args>
+ inline BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::emplace_return
+ hash_unique_table<H, P, A, K>::emplace_empty_impl(Args&&... args)
+ {
+ node_constructor a(*this);
+ a.construct(std::forward<Args>(args)...);
+ return emplace_return(this->emplace_empty_impl_with_node(a, 1), true);
+ }
+
+#else
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
+ template <class H, class P, class A, class K> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ inline BOOST_DEDUCED_TYPENAME \
+ hash_unique_table<H, P, A, K>::emplace_return \
+ hash_unique_table<H, P, A, K>::emplace_impl( \
+ key_type const& k, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ std::size_t hash_value = this->hash_function()(k); \
+ bucket_ptr bucket \
+ = this->bucket_ptr_from_hash(hash_value); \
+ node_ptr pos = find_iterator(bucket, k); \
+ \
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { \
+ return emplace_return(iterator_base(bucket, pos), false); \
+ } else { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ \
+ if(this->reserve_for_insert(this->size_ + 1)) \
+ bucket = this->bucket_ptr_from_hash(hash_value); \
+ \
+ return emplace_return(iterator_base(bucket, \
+ add_node(a, bucket)), true); \
+ } \
+ } \
+ \
+ template <class H, class P, class A, class K> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ inline BOOST_DEDUCED_TYPENAME \
+ hash_unique_table<H, P, A, K>::emplace_return \
+ hash_unique_table<H, P, A, K>:: \
+ emplace_impl(no_key, BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ return emplace_impl_with_node(a); \
+ } \
+ \
+ template <class H, class P, class A, class K> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ inline BOOST_DEDUCED_TYPENAME \
+ hash_unique_table<H, P, A, K>::emplace_return \
+ hash_unique_table<H, P, A, K>:: \
+ emplace_empty_impl(BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ return emplace_return(this->emplace_empty_impl_with_node(a, 1), true); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT_IMPL, _)
+
+#undef BOOST_UNORDERED_INSERT_IMPL
+
+#endif
+
+#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 <class H, class P, class A, class K>
+ template<class... Args>
+ BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::emplace_return
+ hash_unique_table<H, P, A, K>::emplace(Args&&... args)
+ {
+ return this->size_ ?
+ emplace_impl(
+ extractor::extract(std::forward<Args>(args)...),
+ std::forward<Args>(args)...) :
+ emplace_empty_impl(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 <class H, class P, class A, class K>
+ template<class... Args>
+ BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::iterator_base
+ hash_unique_table<H, P, A, K>::emplace_hint(iterator_base const&,
+ Args&&... args)
+ {
+ return this->size_ ?
+ emplace_impl(
+ extractor::extract(std::forward<Args>(args)...),
+ std::forward<Args>(args)...).first :
+ emplace_empty_impl(std::forward<Args>(args)...).first;
+ }
+
+#else
+
+ template <class H, class P, class A, class K>
+ template <class Arg0>
+ BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::emplace_return
+ hash_unique_table<H, P, A, K>::emplace(Arg0 const& arg0)
+ {
+ return this->size_ ?
+ emplace_impl(extractor::extract(arg0), arg0) :
+ emplace_empty_impl(arg0);
+ }
+
+ template <class H, class P, class A, class K>
+ template <class Arg0>
+ BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::iterator_base
+ hash_unique_table<H, P, A, K>::emplace_hint(iterator_base const&,
+ Arg0 const& arg0)
+ {
+ return this->size_ ?
+ emplace_impl(extractor::extract(arg0), arg0).first :
+ emplace_empty_impl(arg0).first;
+ }
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
+ template <class H, class P, class A, class K> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::emplace_return \
+ hash_unique_table<H, P, A, K>::emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ return this->size_ ? \
+ emplace_impl(extractor::extract(arg0, arg1), \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)) : \
+ emplace_empty_impl( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ } \
+ \
+ template <class H, class P, class A, class K> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::iterator_base \
+ hash_unique_table<H, P, A, K>:: \
+ emplace_hint(iterator_base const& it, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ return this->size_ ? \
+ emplace_impl(extractor::extract(arg0, arg1), \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)) : \
+ emplace_empty_impl( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ } \
+
+ BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT_IMPL, _)
+
+#undef BOOST_UNORDERED_INSERT_IMPL
+
+#endif
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Insert range methods
+
+ template <class H, class P, class A, class K>
+ template <class InputIt>
+ inline void hash_unique_table<H, P, A, K>::insert_range_impl(
+ key_type const&, InputIt i, InputIt j)
+ {
+ node_constructor a(*this);
+
+ if(!this->size_) {
+ a.construct(*i);
+ this->emplace_empty_impl_with_node(a, 1);
+ ++i;
+ if(i == j) return;
+ }
+
+ do {
+ // No side effects in this initial code
+ // Note: can't use get_key as '*i' might not be value_type.
+ // TODO: Check if std::pair has an appropriate constructor. If not
+ // that might not be true.
+ // TODO: Test this line better.
+ key_type const& k = extractor::extract(*i);
+ std::size_t hash_value = this->hash_function()(k);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_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.
+
+ // 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(this->size_ + 1 >= this->max_load_) {
+ this->reserve_for_insert(this->size_ + insert_size(i, j));
+ bucket = this->bucket_ptr_from_hash(hash_value);
+ }
+
+ // Nothing after this point can throw.
+ add_node(a, bucket);
+ }
+ } while(++i != j);
+ }
+
+ template <class H, class P, class A, class K>
+ template <class InputIt>
+ inline void hash_unique_table<H, P, A, K>::insert_range_impl(
+ no_key, InputIt i, InputIt j)
+ {
+ node_constructor a(*this);
+
+ if(!this->size_) {
+ a.construct(*i);
+ this->emplace_empty_impl_with_node(a, 1);
+ ++i;
+ if(i == j) return;
+ }
+
+ do {
+ // No side effects in this initial code
+ a.construct(*i);
+ emplace_impl_with_node(a);
+ } while(++i != j);
+ }
+
+ // if hash function throws, or inserting > 1 element, basic exception safety
+ // strong otherwise
+ template <class H, class P, class A, class K>
+ template <class InputIt>
+ void hash_unique_table<H, P, A, K>::insert_range(InputIt i, InputIt j)
+ {
+ if(i != j)
+ return insert_range_impl(extractor::extract(*i), i, j);
+ }
+}}
+
+#endif
Modified: trunk/boost/unordered/detail/util.hpp
==============================================================================
--- trunk/boost/unordered/detail/util.hpp (original)
+++ trunk/boost/unordered/detail/util.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -14,22 +14,7 @@
#include <boost/iterator/iterator_categories.hpp>
#include <boost/preprocessor/seq/size.hpp>
#include <boost/preprocessor/seq/enum.hpp>
-#include <boost/unordered/detail/buckets.hpp>
-
-#if !defined(BOOST_UNORDERED_STD_FORWARD)
-
-#include <boost/preprocessor/repetition/enum_params.hpp>
-#include <boost/preprocessor/repetition/enum_binary_params.hpp>
-#include <boost/preprocessor/repetition/repeat_from_to.hpp>
-
-#define BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- BOOST_PP_ENUM_PARAMS_Z(z, n, class Arg)
-#define BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, const& arg)
-#define BOOST_UNORDERED_CALL_PARAMS(z, n) \
- BOOST_PP_ENUM_PARAMS_Z(z, n, arg)
-
-#endif
+#include <boost/unordered/detail/fwd.hpp>
namespace boost { namespace unordered_detail {
@@ -38,7 +23,8 @@
inline std::size_t double_to_size_t(double f)
{
- return f >= static_cast<double>((std::numeric_limits<std::size_t>::max)()) ?
+ 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);
}
@@ -143,7 +129,7 @@
template <class I>
inline std::size_t initial_size(I i, I j,
- std::size_t n = boost::unordered_detail::default_initial_bucket_count)
+ std::size_t n = boost::unordered_detail::default_bucket_count)
{
return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1, n);
}
@@ -172,29 +158,29 @@
#else
-#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, n, _) \
- template < \
- class T, \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- inline void construct_impl( \
- T*, void* address, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- new(address) T( \
- BOOST_UNORDERED_CALL_PARAMS(z, n)); \
- } \
- \
- template <class First, class Second, class Key, \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- inline void construct_impl( \
- std::pair<First, Second>*, void* address, \
- Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
- { \
- new(address) std::pair<First, Second>(k, \
- Second(BOOST_UNORDERED_CALL_PARAMS(z, n))); \
+#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, n, _) \
+ template < \
+ class T, \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ inline void construct_impl( \
+ T*, void* address, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ new(address) T( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ } \
+ \
+ template <class First, class Second, class Key, \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ inline void construct_impl( \
+ std::pair<First, Second>*, void* address, \
+ Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ new(address) std::pair<First, Second>(k, \
+ Second(BOOST_UNORDERED_CALL_PARAMS(z, n))); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -244,20 +230,20 @@
}
#else
-#define BOOST_UNORDERED_CONSTRUCT(z, n, _) \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- void construct( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- construct_preamble(); \
- construct_impl( \
- (value_type*) 0, node_->address(), \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- ); \
- value_constructed_ = true; \
+#define BOOST_UNORDERED_CONSTRUCT(z, n, _) \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ void construct( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ construct_preamble(); \
+ construct_impl( \
+ (value_type*) 0, node_->address(), \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ ); \
+ value_constructed_ = true; \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -274,10 +260,10 @@
value_constructed_ = true;
}
- real_node_ptr get() const
+ value_type& value() const
{
BOOST_ASSERT(node_);
- return node_;
+ return node_->value();
}
// no throw
@@ -297,11 +283,11 @@
// hash_node_constructor
template <class Alloc, class Grouped>
- hash_node_constructor<Alloc, Grouped>::~hash_node_constructor()
+ inline hash_node_constructor<Alloc, Grouped>::~hash_node_constructor()
{
if (node_) {
if (value_constructed_) {
- BOOST_UNORDERED_DESTRUCT(&node_->value(), value_type);
+ boost::unordered_detail::destroy(&node_->value());
}
if (node_constructed_)
@@ -312,7 +298,7 @@
}
template <class Alloc, class Grouped>
- void hash_node_constructor<Alloc, Grouped>::construct_preamble()
+ inline void hash_node_constructor<Alloc, Grouped>::construct_preamble()
{
if(!node_) {
node_constructed_ = false;
@@ -324,7 +310,7 @@
}
else {
BOOST_ASSERT(node_constructed_ && value_constructed_);
- BOOST_UNORDERED_DESTRUCT(&node_->value(), value_type);
+ boost::unordered_detail::destroy(&node_->value());
value_constructed_ = false;
}
}
Modified: trunk/boost/unordered/unordered_map.hpp
==============================================================================
--- trunk/boost/unordered/unordered_map.hpp (original)
+++ trunk/boost/unordered/unordered_map.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -16,7 +16,8 @@
#include <boost/unordered/unordered_map_fwd.hpp>
#include <boost/functional/hash.hpp>
#include <boost/unordered/detail/allocator_helpers.hpp>
-#include <boost/unordered/detail/insert.hpp>
+#include <boost/unordered/detail/equivalent.hpp>
+#include <boost/unordered/detail/unique.hpp>
#if !defined(BOOST_HAS_RVALUE_REFS)
#include <boost/unordered/detail/move.hpp>
@@ -53,32 +54,41 @@
#endif
typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<allocator_type, value_type>::type
+ boost::unordered_detail::rebind_wrap<
+ allocator_type, value_type>::type
value_allocator;
- typedef boost::unordered_detail::hash_unique_table<Hash, Pred, value_allocator,
- boost::unordered_detail::map_extractor> table;
+ typedef boost::unordered_detail::hash_unique_table<Hash, Pred,
+ value_allocator, boost::unordered_detail::map_extractor> table;
typedef BOOST_DEDUCED_TYPENAME table::iterator_base iterator_base;
public:
- typedef BOOST_DEDUCED_TYPENAME value_allocator::pointer pointer;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::const_pointer const_pointer;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::reference reference;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::const_reference const_reference;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::pointer pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_pointer const_pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::reference reference;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_reference const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef boost::unordered_detail::hash_const_local_iterator<
- value_allocator, boost::unordered_detail::ungrouped> const_local_iterator;
+ value_allocator, boost::unordered_detail::ungrouped>
+ const_local_iterator;
typedef boost::unordered_detail::hash_local_iterator<
- value_allocator, boost::unordered_detail::ungrouped> local_iterator;
+ value_allocator, boost::unordered_detail::ungrouped>
+ local_iterator;
typedef boost::unordered_detail::hash_const_iterator<
- value_allocator, boost::unordered_detail::ungrouped> const_iterator;
+ value_allocator, boost::unordered_detail::ungrouped>
+ const_iterator;
typedef boost::unordered_detail::hash_iterator<
- value_allocator, boost::unordered_detail::ungrouped> iterator;
+ value_allocator, boost::unordered_detail::ungrouped>
+ iterator;
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
private:
@@ -97,49 +107,51 @@
// construct/destroy/copy
explicit unordered_map(
- size_type n = boost::unordered_detail::default_initial_bucket_count,
+ size_type n = boost::unordered_detail::default_bucket_count,
const hasher &hf = hasher(),
const key_equal &eql = key_equal(),
const allocator_type &a = allocator_type())
- : table_(n, hf, eql, a)
+ : table_(n, hf, eql, a)
{
}
explicit unordered_map(allocator_type const& a)
- : table_(boost::unordered_detail::default_initial_bucket_count,
+ : table_(boost::unordered_detail::default_bucket_count,
hasher(), key_equal(), a)
{
}
unordered_map(unordered_map const& other, allocator_type const& a)
- : table_(other.table_, a)
+ : table_(other.table_, a)
{
}
- template <class InputIterator>
- unordered_map(InputIterator f, InputIterator l)
- : table_(boost::unordered_detail::initial_size(f, l), hasher(), key_equal(), allocator_type())
+ template <class InputIt>
+ unordered_map(InputIt f, InputIt l)
+ : table_(boost::unordered_detail::initial_size(f, l),
+ hasher(), key_equal(), allocator_type())
{
table_.insert_range(f, l);
}
- template <class InputIterator>
- unordered_map(InputIterator f, InputIterator l,
+ template <class InputIt>
+ unordered_map(InputIt f, InputIt l,
size_type n,
const hasher &hf = hasher(),
const key_equal &eql = key_equal())
- : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, allocator_type())
+ : table_(boost::unordered_detail::initial_size(f, l, n),
+ hf, eql, allocator_type())
{
table_.insert_range(f, l);
}
- template <class InputIterator>
- unordered_map(InputIterator f, InputIterator l,
+ template <class InputIt>
+ unordered_map(InputIt f, InputIt l,
size_type n,
const hasher &hf,
const key_equal &eql,
const allocator_type &a)
- : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a)
+ : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a)
{
table_.insert_range(f, l);
}
@@ -148,12 +160,12 @@
#if defined(BOOST_HAS_RVALUE_REFS)
unordered_map(unordered_map&& other)
- : table_(other.table_, boost::unordered_detail::move_tag())
+ : table_(other.table_, boost::unordered_detail::move_tag())
{
}
unordered_map(unordered_map&& other, allocator_type const& a)
- : table_(other.table_, a, boost::unordered_detail::move_tag())
+ : table_(other.table_, a, boost::unordered_detail::move_tag())
{
}
@@ -163,8 +175,10 @@
return *this;
}
#else
- unordered_map(boost::unordered_detail::move_from<unordered_map<Key, T, Hash, Pred, Alloc> > other)
- : table_(other.source.table_, boost::unordered_detail::move_tag())
+ unordered_map(boost::unordered_detail::move_from<
+ unordered_map<Key, T, Hash, Pred, Alloc>
+ > other)
+ : table_(other.source.table_, boost::unordered_detail::move_tag())
{
}
@@ -179,11 +193,13 @@
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
unordered_map(std::initializer_list<value_type> list,
- size_type n = boost::unordered_detail::default_initial_bucket_count,
+ size_type n = boost::unordered_detail::default_bucket_count,
const hasher &hf = hasher(),
const key_equal &eql = key_equal(),
const allocator_type &a = allocator_type())
- : table_(boost::unordered_detail::initial_size(list.begin(), list.end(), n), hf, eql, allocator_type())
+ : table_(boost::unordered_detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, allocator_type())
{
table_.insert_range(list.begin(), list.end());
}
@@ -263,7 +279,8 @@
template <class... Args>
iterator emplace_hint(const_iterator hint, Args&&... args)
{
- return iterator(table_.emplace_hint(get(hint), std::forward<Args>(args)...));
+ return iterator(
+ table_.emplace_hint(get(hint), std::forward<Args>(args)...));
}
#else
@@ -273,35 +290,36 @@
table_.emplace(v));
}
- iterator emplace_hint(const_iterator hint, value_type const& v = value_type())
+ iterator emplace_hint(const_iterator hint,
+ value_type const& v = value_type())
{
return iterator(table_.emplace_hint(get(hint), v));
}
-#define BOOST_UNORDERED_EMPLACE(z, n, _) \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- std::pair<iterator, bool> emplace( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return boost::unordered_detail::pair_cast<iterator, bool>( \
- table_.emplace( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
- } \
- \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- iterator emplace_hint(const_iterator hint, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator(table_.emplace_hint(get(hint), \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ std::pair<iterator, bool> emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return boost::unordered_detail::pair_cast<iterator, bool>( \
+ table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ )); \
+ } \
+ \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ iterator emplace_hint(const_iterator hint, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator(table_.emplace_hint(get(hint), \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ )); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -322,8 +340,8 @@
return iterator(table_.emplace_hint(get(hint), obj));
}
- template <class InputIterator>
- void insert(InputIterator first, InputIterator last)
+ template <class InputIt>
+ void insert(InputIt first, InputIt last)
{
table_.insert_range(first, last);
}
@@ -400,14 +418,16 @@
std::pair<iterator, iterator>
equal_range(const key_type& k)
{
- return boost::unordered_detail::pair_cast<iterator, iterator>(
+ return boost::unordered_detail::pair_cast<
+ iterator, iterator>(
table_.equal_range(k));
}
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const
{
- return boost::unordered_detail::pair_cast<const_iterator, const_iterator>(
+ return boost::unordered_detail::pair_cast<
+ const_iterator, const_iterator>(
table_.equal_range(k));
}
@@ -415,7 +435,7 @@
size_type bucket_count() const
{
- return table_.bucket_count();
+ return table_.bucket_count_;
}
size_type max_bucket_count() const
@@ -443,14 +463,14 @@
return const_local_iterator(table_.bucket_begin(n));
}
- local_iterator end(size_type n)
+ local_iterator end(size_type)
{
- return local_iterator(table_.bucket_end(n));
+ return local_iterator();
}
- const_local_iterator end(size_type n) const
+ const_local_iterator end(size_type) const
{
- return const_local_iterator(table_.bucket_end(n));
+ return const_local_iterator();
}
const_local_iterator cbegin(size_type n) const
@@ -458,9 +478,9 @@
return const_local_iterator(table_.bucket_begin(n));
}
- const_local_iterator cend(size_type n) const
+ const_local_iterator cend(size_type) const
{
- return const_local_iterator(table_.bucket_end(n));
+ return const_local_iterator();
}
// hash policy
@@ -486,8 +506,10 @@
}
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
- friend bool operator==<Key, T, Hash, Pred, Alloc>(unordered_map const&, unordered_map const&);
- friend bool operator!=<Key, T, Hash, Pred, Alloc>(unordered_map const&, unordered_map const&);
+ friend bool operator==<Key, T, Hash, Pred, Alloc>(
+ unordered_map const&, unordered_map const&);
+ friend bool operator!=<Key, T, Hash, Pred, Alloc>(
+ unordered_map const&, unordered_map const&);
#endif
}; // class template unordered_map
@@ -528,31 +550,40 @@
private:
#endif
typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<allocator_type, value_type>::type
+ boost::unordered_detail::rebind_wrap<
+ allocator_type, value_type>::type
value_allocator;
- typedef boost::unordered_detail::hash_equivalent_table<Hash, Pred, value_allocator,
- boost::unordered_detail::map_extractor> table;
+ typedef boost::unordered_detail::hash_equivalent_table<Hash, Pred,
+ value_allocator, boost::unordered_detail::map_extractor> table;
typedef BOOST_DEDUCED_TYPENAME table::iterator_base iterator_base;
public:
- typedef BOOST_DEDUCED_TYPENAME value_allocator::pointer pointer;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::const_pointer const_pointer;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::reference reference;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::const_reference const_reference;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::pointer pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_pointer const_pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::reference reference;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_reference const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef boost::unordered_detail::hash_const_local_iterator<
- value_allocator, boost::unordered_detail::grouped> const_local_iterator;
+ value_allocator, boost::unordered_detail::grouped>
+ const_local_iterator;
typedef boost::unordered_detail::hash_local_iterator<
- value_allocator, boost::unordered_detail::grouped> local_iterator;
+ value_allocator, boost::unordered_detail::grouped>
+ local_iterator;
typedef boost::unordered_detail::hash_const_iterator<
- value_allocator, boost::unordered_detail::grouped> const_iterator;
+ value_allocator, boost::unordered_detail::grouped>
+ const_iterator;
typedef boost::unordered_detail::hash_iterator<
- value_allocator, boost::unordered_detail::grouped> iterator;
+ value_allocator, boost::unordered_detail::grouped>
+ iterator;
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
private:
@@ -571,7 +602,7 @@
// construct/destroy/copy
explicit unordered_multimap(
- size_type n = boost::unordered_detail::default_initial_bucket_count,
+ size_type n = boost::unordered_detail::default_bucket_count,
const hasher &hf = hasher(),
const key_equal &eql = key_equal(),
const allocator_type &a = allocator_type())
@@ -580,35 +611,38 @@
}
explicit unordered_multimap(allocator_type const& a)
- : table_(boost::unordered_detail::default_initial_bucket_count,
+ : table_(boost::unordered_detail::default_bucket_count,
hasher(), key_equal(), a)
{
}
- unordered_multimap(unordered_multimap const& other, allocator_type const& a)
- : table_(other.table_, a)
+ unordered_multimap(unordered_multimap const& other,
+ allocator_type const& a)
+ : table_(other.table_, a)
{
}
- template <class InputIterator>
- unordered_multimap(InputIterator f, InputIterator l)
- : table_(boost::unordered_detail::initial_size(f, l), hasher(), key_equal(), allocator_type())
+ template <class InputIt>
+ unordered_multimap(InputIt f, InputIt l)
+ : table_(boost::unordered_detail::initial_size(f, l),
+ hasher(), key_equal(), allocator_type())
{
table_.insert_range(f, l);
}
- template <class InputIterator>
- unordered_multimap(InputIterator f, InputIterator l,
+ template <class InputIt>
+ unordered_multimap(InputIt f, InputIt l,
size_type n,
const hasher &hf = hasher(),
const key_equal &eql = key_equal())
- : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, allocator_type())
+ : table_(boost::unordered_detail::initial_size(f, l, n),
+ hf, eql, allocator_type())
{
table_.insert_range(f, l);
}
- template <class InputIterator>
- unordered_multimap(InputIterator f, InputIterator l,
+ template <class InputIt>
+ unordered_multimap(InputIt f, InputIt l,
size_type n,
const hasher &hf,
const key_equal &eql,
@@ -622,12 +656,12 @@
#if defined(BOOST_HAS_RVALUE_REFS)
unordered_multimap(unordered_multimap&& other)
- : table_(other.table_, boost::unordered_detail::move_tag())
+ : table_(other.table_, boost::unordered_detail::move_tag())
{
}
unordered_multimap(unordered_multimap&& other, allocator_type const& a)
- : table_(other.table_, a, boost::unordered_detail::move_tag())
+ : table_(other.table_, a, boost::unordered_detail::move_tag())
{
}
@@ -637,8 +671,10 @@
return *this;
}
#else
- unordered_multimap(boost::unordered_detail::move_from<unordered_multimap<Key, T, Hash, Pred, Alloc> > other)
- : table_(other.source.table_, boost::unordered_detail::move_tag())
+ unordered_multimap(boost::unordered_detail::move_from<
+ unordered_multimap<Key, T, Hash, Pred, Alloc>
+ > other)
+ : table_(other.source.table_, boost::unordered_detail::move_tag())
{
}
@@ -653,11 +689,13 @@
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
unordered_multimap(std::initializer_list<value_type> list,
- size_type n = boost::unordered_detail::default_initial_bucket_count,
+ size_type n = boost::unordered_detail::default_bucket_count,
const hasher &hf = hasher(),
const key_equal &eql = key_equal(),
const allocator_type &a = allocator_type())
- : table_(boost::unordered_detail::initial_size(list.begin(), list.end(), n), hf, eql, allocator_type())
+ : table_(boost::unordered_detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, allocator_type())
{
table_.insert_range(list.begin(), list.end());
}
@@ -736,7 +774,8 @@
template <class... Args>
iterator emplace_hint(const_iterator hint, Args&&... args)
{
- return iterator(table_.emplace_hint(get(hint), std::forward<Args>(args)...));
+ return iterator(table_.emplace_hint(get(hint),
+ std::forward<Args>(args)...));
}
#else
@@ -745,36 +784,37 @@
return iterator(table_.emplace(v));
}
- iterator emplace_hint(const_iterator hint, value_type const& v = value_type())
+ iterator emplace_hint(const_iterator hint,
+ value_type const& v = value_type())
{
return iterator(table_.emplace_hint(get(hint), v));
}
-#define BOOST_UNORDERED_EMPLACE(z, n, _) \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- iterator emplace( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator( \
- table_.emplace( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
- } \
- \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- iterator emplace_hint(const_iterator hint, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator(table_.emplace_hint(get(hint), \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ iterator emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator( \
+ table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ )); \
+ } \
+ \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ iterator emplace_hint(const_iterator hint, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator(table_.emplace_hint(get(hint), \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ )); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -794,8 +834,8 @@
return iterator(table_.emplace_hint(get(hint), obj));
}
- template <class InputIterator>
- void insert(InputIterator first, InputIterator last)
+ template <class InputIt>
+ void insert(InputIt first, InputIt last)
{
table_.insert_range(first, last);
}
@@ -857,14 +897,16 @@
std::pair<iterator, iterator>
equal_range(const key_type& k)
{
- return boost::unordered_detail::pair_cast<iterator, iterator>(
+ return boost::unordered_detail::pair_cast<
+ iterator, iterator>(
table_.equal_range(k));
}
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const
{
- return boost::unordered_detail::pair_cast<const_iterator, const_iterator>(
+ return boost::unordered_detail::pair_cast<
+ const_iterator, const_iterator>(
table_.equal_range(k));
}
@@ -872,7 +914,7 @@
size_type bucket_count() const
{
- return table_.bucket_count();
+ return table_.bucket_count_;
}
size_type max_bucket_count() const
@@ -900,14 +942,14 @@
return const_local_iterator(table_.bucket_begin(n));
}
- local_iterator end(size_type n)
+ local_iterator end(size_type)
{
- return local_iterator(table_.bucket_end(n));
+ return local_iterator();
}
- const_local_iterator end(size_type n) const
+ const_local_iterator end(size_type) const
{
- return const_local_iterator(table_.bucket_end(n));
+ return const_local_iterator();
}
const_local_iterator cbegin(size_type n) const
@@ -915,9 +957,9 @@
return const_local_iterator(table_.bucket_begin(n));
}
- const_local_iterator cend(size_type n) const
+ const_local_iterator cend(size_type) const
{
- return const_local_iterator(table_.bucket_end(n));
+ return const_local_iterator();
}
// hash policy
@@ -943,8 +985,10 @@
}
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
- friend bool operator==<Key, T, Hash, Pred, Alloc>(unordered_multimap const&, unordered_multimap const&);
- friend bool operator!=<Key, T, Hash, Pred, Alloc>(unordered_multimap const&, unordered_multimap const&);
+ friend bool operator==<Key, T, Hash, Pred, Alloc>(
+ unordered_multimap const&, unordered_multimap const&);
+ friend bool operator!=<Key, T, Hash, Pred, Alloc>(
+ unordered_multimap const&, unordered_multimap const&);
#endif
}; // class template unordered_multimap
Modified: trunk/boost/unordered/unordered_set.hpp
==============================================================================
--- trunk/boost/unordered/unordered_set.hpp (original)
+++ trunk/boost/unordered/unordered_set.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -16,7 +16,8 @@
#include <boost/unordered/unordered_set_fwd.hpp>
#include <boost/functional/hash.hpp>
#include <boost/unordered/detail/allocator_helpers.hpp>
-#include <boost/unordered/detail/insert.hpp>
+#include <boost/unordered/detail/equivalent.hpp>
+#include <boost/unordered/detail/unique.hpp>
#if !defined(BOOST_HAS_RVALUE_REFS)
#include <boost/unordered/detail/move.hpp>
@@ -53,27 +54,34 @@
#endif
typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<allocator_type, value_type>::type
+ boost::unordered_detail::rebind_wrap<
+ allocator_type, value_type>::type
value_allocator;
- typedef boost::unordered_detail::hash_unique_table<Hash, Pred, value_allocator,
- boost::unordered_detail::set_extractor> table;
+ typedef boost::unordered_detail::hash_unique_table<Hash, Pred,
+ value_allocator, boost::unordered_detail::set_extractor> table;
typedef BOOST_DEDUCED_TYPENAME table::iterator_base iterator_base;
public:
- typedef BOOST_DEDUCED_TYPENAME value_allocator::pointer pointer;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::const_pointer const_pointer;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::reference reference;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::const_reference const_reference;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::pointer pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_pointer const_pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::reference reference;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_reference const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef boost::unordered_detail::hash_const_local_iterator<
- value_allocator, boost::unordered_detail::ungrouped> const_local_iterator;
+ value_allocator, boost::unordered_detail::ungrouped>
+ const_local_iterator;
typedef boost::unordered_detail::hash_const_iterator<
- value_allocator, boost::unordered_detail::ungrouped> const_iterator;
+ value_allocator, boost::unordered_detail::ungrouped>
+ const_iterator;
typedef const_local_iterator local_iterator;
typedef const_iterator iterator;
@@ -94,47 +102,49 @@
// construct/destroy/copy
explicit unordered_set(
- size_type n = boost::unordered_detail::default_initial_bucket_count,
+ size_type n = boost::unordered_detail::default_bucket_count,
const hasher &hf = hasher(),
const key_equal &eql = key_equal(),
const allocator_type &a = allocator_type())
- : table_(n, hf, eql, a)
+ : table_(n, hf, eql, a)
{
}
explicit unordered_set(allocator_type const& a)
- : table_(boost::unordered_detail::default_initial_bucket_count,
+ : table_(boost::unordered_detail::default_bucket_count,
hasher(), key_equal(), a)
{
}
unordered_set(unordered_set const& other, allocator_type const& a)
- : table_(other.table_, a)
+ : table_(other.table_, a)
{
}
- template <class InputIterator>
- unordered_set(InputIterator f, InputIterator l)
- : table_(boost::unordered_detail::initial_size(f, l), hasher(), key_equal(), allocator_type())
+ template <class InputIt>
+ unordered_set(InputIt f, InputIt l)
+ : table_(boost::unordered_detail::initial_size(f, l),
+ hasher(), key_equal(), allocator_type())
{
table_.insert_range(f, l);
}
- template <class InputIterator>
- unordered_set(InputIterator f, InputIterator l, size_type n,
+ template <class InputIt>
+ unordered_set(InputIt f, InputIt l, size_type n,
const hasher &hf = hasher(),
const key_equal &eql = key_equal())
- : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, allocator_type())
+ : table_(boost::unordered_detail::initial_size(f, l, n),
+ hf, eql, allocator_type())
{
table_.insert_range(f, l);
}
- template <class InputIterator>
- unordered_set(InputIterator f, InputIterator l, size_type n,
+ template <class InputIt>
+ unordered_set(InputIt f, InputIt l, size_type n,
const hasher &hf,
const key_equal &eql,
const allocator_type &a)
- : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a)
+ : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a)
{
table_.insert_range(f, l);
}
@@ -143,12 +153,12 @@
#if defined(BOOST_HAS_RVALUE_REFS)
unordered_set(unordered_set&& other)
- : table_(other.table_, boost::unordered_detail::move_tag())
+ : table_(other.table_, boost::unordered_detail::move_tag())
{
}
unordered_set(unordered_set&& other, allocator_type const& a)
- : table_(other.table_, a, boost::unordered_detail::move_tag())
+ : table_(other.table_, a, boost::unordered_detail::move_tag())
{
}
@@ -158,8 +168,10 @@
return *this;
}
#else
- unordered_set(boost::unordered_detail::move_from<unordered_set<Value, Hash, Pred, Alloc> > other)
- : table_(other.source.table_, boost::unordered_detail::move_tag())
+ unordered_set(boost::unordered_detail::move_from<
+ unordered_set<Value, Hash, Pred, Alloc>
+ > other)
+ : table_(other.source.table_, boost::unordered_detail::move_tag())
{
}
@@ -174,11 +186,13 @@
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
unordered_set(std::initializer_list<value_type> list,
- size_type n = boost::unordered_detail::default_initial_bucket_count,
+ size_type n = boost::unordered_detail::default_bucket_count,
const hasher &hf = hasher(),
const key_equal &eql = key_equal(),
const allocator_type &a = allocator_type())
- : table_(boost::unordered_detail::initial_size(list.begin(), list.end(), n), hf, eql, allocator_type())
+ : table_(boost::unordered_detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, allocator_type())
{
table_.insert_range(list.begin(), list.end());
}
@@ -269,35 +283,36 @@
table_.emplace(v));
}
- iterator emplace_hint(const_iterator hint, value_type const& v = value_type())
+ iterator emplace_hint(const_iterator hint,
+ value_type const& v = value_type())
{
return iterator(table_.emplace_hint(get(hint), v));
}
-#define BOOST_UNORDERED_EMPLACE(z, n, _) \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- std::pair<iterator, bool> emplace( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return boost::unordered_detail::pair_cast<iterator, bool>( \
- table_.emplace( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
- } \
- \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- iterator emplace_hint(const_iterator hint, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator(table_.emplace_hint(get(hint), \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ std::pair<iterator, bool> emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return boost::unordered_detail::pair_cast<iterator, bool>( \
+ table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ )); \
+ } \
+ \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ iterator emplace_hint(const_iterator hint, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator(table_.emplace_hint(get(hint), \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ )); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -318,8 +333,8 @@
return iterator(table_.emplace_hint(get(hint), obj));
}
- template <class InputIterator>
- void insert(InputIterator first, InputIterator last)
+ template <class InputIt>
+ void insert(InputIt first, InputIt last)
{
table_.insert_range(first, last);
}
@@ -376,7 +391,8 @@
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const
{
- return boost::unordered_detail::pair_cast<const_iterator, const_iterator>(
+ return boost::unordered_detail::pair_cast<
+ const_iterator, const_iterator>(
table_.equal_range(k));
}
@@ -384,7 +400,7 @@
size_type bucket_count() const
{
- return table_.bucket_count();
+ return table_.bucket_count_;
}
size_type max_bucket_count() const
@@ -412,14 +428,14 @@
return const_local_iterator(table_.bucket_begin(n));
}
- local_iterator end(size_type n)
+ local_iterator end(size_type)
{
- return local_iterator(table_.bucket_end(n));
+ return local_iterator();
}
- const_local_iterator end(size_type n) const
+ const_local_iterator end(size_type) const
{
- return const_local_iterator(table_.bucket_end(n));
+ return const_local_iterator();
}
const_local_iterator cbegin(size_type n) const
@@ -427,9 +443,9 @@
return const_local_iterator(table_.bucket_begin(n));
}
- const_local_iterator cend(size_type n) const
+ const_local_iterator cend(size_type) const
{
- return const_local_iterator(table_.bucket_end(n));
+ return const_local_iterator();
}
// hash policy
@@ -455,8 +471,10 @@
}
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
- friend bool operator==<Value, Hash, Pred, Alloc>(unordered_set const&, unordered_set const&);
- friend bool operator!=<Value, Hash, Pred, Alloc>(unordered_set const&, unordered_set const&);
+ friend bool operator==<Value, Hash, Pred, Alloc>(
+ unordered_set const&, unordered_set const&);
+ friend bool operator!=<Value, Hash, Pred, Alloc>(
+ unordered_set const&, unordered_set const&);
#endif
}; // class template unordered_set
@@ -496,27 +514,34 @@
private:
#endif
typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<allocator_type, value_type>::type
+ boost::unordered_detail::rebind_wrap<
+ allocator_type, value_type>::type
value_allocator;
- typedef boost::unordered_detail::hash_equivalent_table<Hash, Pred, value_allocator,
- boost::unordered_detail::set_extractor> table;
+ typedef boost::unordered_detail::hash_equivalent_table<Hash, Pred,
+ value_allocator, boost::unordered_detail::set_extractor> table;
typedef BOOST_DEDUCED_TYPENAME table::iterator_base iterator_base;
public:
- typedef BOOST_DEDUCED_TYPENAME value_allocator::pointer pointer;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::const_pointer const_pointer;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::reference reference;
- typedef BOOST_DEDUCED_TYPENAME value_allocator::const_reference const_reference;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::pointer pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_pointer const_pointer;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::reference reference;
+ typedef BOOST_DEDUCED_TYPENAME
+ value_allocator::const_reference const_reference;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef boost::unordered_detail::hash_const_local_iterator<
- value_allocator, boost::unordered_detail::grouped> const_local_iterator;
+ value_allocator, boost::unordered_detail::grouped>
+ const_local_iterator;
typedef boost::unordered_detail::hash_const_iterator<
- value_allocator, boost::unordered_detail::grouped> const_iterator;
+ value_allocator, boost::unordered_detail::grouped>
+ const_iterator;
typedef const_local_iterator local_iterator;
typedef const_iterator iterator;
@@ -537,7 +562,7 @@
// construct/destroy/copy
explicit unordered_multiset(
- size_type n = boost::unordered_detail::default_initial_bucket_count,
+ size_type n = boost::unordered_detail::default_bucket_count,
const hasher &hf = hasher(),
const key_equal &eql = key_equal(),
const allocator_type &a = allocator_type())
@@ -546,34 +571,37 @@
}
explicit unordered_multiset(allocator_type const& a)
- : table_(boost::unordered_detail::default_initial_bucket_count,
+ : table_(boost::unordered_detail::default_bucket_count,
hasher(), key_equal(), a)
{
}
- unordered_multiset(unordered_multiset const& other, allocator_type const& a)
- : table_(other.table_, a)
+ unordered_multiset(unordered_multiset const& other,
+ allocator_type const& a)
+ : table_(other.table_, a)
{
}
- template <class InputIterator>
- unordered_multiset(InputIterator f, InputIterator l)
- : table_(boost::unordered_detail::initial_size(f, l), hasher(), key_equal(), allocator_type())
+ template <class InputIt>
+ unordered_multiset(InputIt f, InputIt l)
+ : table_(boost::unordered_detail::initial_size(f, l),
+ hasher(), key_equal(), allocator_type())
{
table_.insert_range(f, l);
}
- template <class InputIterator>
- unordered_multiset(InputIterator f, InputIterator l, size_type n,
+ template <class InputIt>
+ unordered_multiset(InputIt f, InputIt l, size_type n,
const hasher &hf = hasher(),
const key_equal &eql = key_equal())
- : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, allocator_type())
+ : table_(boost::unordered_detail::initial_size(f, l, n),
+ hf, eql, allocator_type())
{
table_.insert_range(f, l);
}
- template <class InputIterator>
- unordered_multiset(InputIterator f, InputIterator l, size_type n,
+ template <class InputIt>
+ unordered_multiset(InputIt f, InputIt l, size_type n,
const hasher &hf,
const key_equal &eql,
const allocator_type &a)
@@ -586,12 +614,12 @@
#if defined(BOOST_HAS_RVALUE_REFS)
unordered_multiset(unordered_multiset&& other)
- : table_(other.table_, boost::unordered_detail::move_tag())
+ : table_(other.table_, boost::unordered_detail::move_tag())
{
}
unordered_multiset(unordered_multiset&& other, allocator_type const& a)
- : table_(other.table_, a, boost::unordered_detail::move_tag())
+ : table_(other.table_, a, boost::unordered_detail::move_tag())
{
}
@@ -601,8 +629,10 @@
return *this;
}
#else
- unordered_multiset(boost::unordered_detail::move_from<unordered_multiset<Value, Hash, Pred, Alloc> > other)
- : table_(other.source.table_, boost::unordered_detail::move_tag())
+ unordered_multiset(boost::unordered_detail::move_from<
+ unordered_multiset<Value, Hash, Pred, Alloc>
+ > other)
+ : table_(other.source.table_, boost::unordered_detail::move_tag())
{
}
@@ -617,11 +647,13 @@
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
unordered_multiset(std::initializer_list<value_type> list,
- size_type n = boost::unordered_detail::default_initial_bucket_count,
+ size_type n = boost::unordered_detail::default_bucket_count,
const hasher &hf = hasher(),
const key_equal &eql = key_equal(),
const allocator_type &a = allocator_type())
- : table_(boost::unordered_detail::initial_size(list.begin(), list.end(), n), hf, eql, allocator_type())
+ : table_(boost::unordered_detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, allocator_type())
{
table_.insert_range(list.begin(), list.end());
}
@@ -700,7 +732,8 @@
template <class... Args>
iterator emplace_hint(const_iterator hint, Args&&... args)
{
- return iterator(table_.emplace_hint(get(hint), std::forward<Args>(args)...));
+ return iterator(table_.emplace_hint(get(hint),
+ std::forward<Args>(args)...));
}
#else
@@ -709,33 +742,34 @@
return iterator(table_.emplace(v));
}
- iterator emplace_hint(const_iterator hint, value_type const& v = value_type())
+ iterator emplace_hint(const_iterator hint,
+ value_type const& v = value_type())
{
return iterator(table_.emplace_hint(get(hint), v));
}
-#define BOOST_UNORDERED_EMPLACE(z, n, _) \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- iterator emplace( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator( \
- table_.emplace(BOOST_UNORDERED_CALL_PARAMS(z, n))); \
- } \
- \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- iterator emplace_hint(const_iterator hint, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator(table_.emplace_hint(get(hint), \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ iterator emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator( \
+ table_.emplace(BOOST_UNORDERED_CALL_PARAMS(z, n))); \
+ } \
+ \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ iterator emplace_hint(const_iterator hint, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator(table_.emplace_hint(get(hint), \
+ BOOST_UNORDERED_CALL_PARAMS(z, n) \
+ )); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -755,8 +789,8 @@
return iterator(table_.emplace_hint(get(hint), obj));
}
- template <class InputIterator>
- void insert(InputIterator first, InputIterator last)
+ template <class InputIt>
+ void insert(InputIt first, InputIt last)
{
table_.insert_range(first, last);
}
@@ -813,7 +847,8 @@
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const
{
- return boost::unordered_detail::pair_cast<const_iterator, const_iterator>(
+ return boost::unordered_detail::pair_cast<
+ const_iterator, const_iterator>(
table_.equal_range(k));
}
@@ -821,7 +856,7 @@
size_type bucket_count() const
{
- return table_.bucket_count();
+ return table_.bucket_count_;
}
size_type max_bucket_count() const
@@ -849,14 +884,14 @@
return const_local_iterator(table_.bucket_begin(n));
}
- local_iterator end(size_type n)
+ local_iterator end(size_type)
{
- return local_iterator(table_.bucket_end(n));
+ return local_iterator();
}
- const_local_iterator end(size_type n) const
+ const_local_iterator end(size_type) const
{
- return const_local_iterator(table_.bucket_end(n));
+ return const_local_iterator();
}
const_local_iterator cbegin(size_type n) const
@@ -864,9 +899,9 @@
return const_local_iterator(table_.bucket_begin(n));
}
- const_local_iterator cend(size_type n) const
+ const_local_iterator cend(size_type) const
{
- return const_local_iterator(table_.bucket_end(n));
+ return const_local_iterator();
}
// hash policy
@@ -892,8 +927,10 @@
}
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
- friend bool operator==<Value, Hash, Pred, Alloc>(unordered_multiset const&, unordered_multiset const&);
- friend bool operator!=<Value, Hash, Pred, Alloc>(unordered_multiset const&, unordered_multiset const&);
+ friend bool operator==<Value, Hash, Pred, Alloc>(
+ unordered_multiset const&, unordered_multiset const&);
+ friend bool operator!=<Value, Hash, Pred, Alloc>(
+ unordered_multiset const&, unordered_multiset const&);
#endif
}; // class template unordered_multiset
Modified: trunk/libs/unordered/test/helpers/list.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/list.hpp (original)
+++ trunk/libs/unordered/test/helpers/list.hpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -21,14 +21,17 @@
namespace test_detail
{
- template <typename T> struct list_node;
+ template <typename T> class list_node;
template <typename T> class list_data;
template <typename T> class list_iterator;
template <typename T> class list_const_iterator;
template <typename T>
- struct list_node
+ class list_node
{
+ list_node(list_node const&);
+ list_node& operator=(list_node const&);
+ public:
T value_;
list_node* next_;
@@ -243,8 +246,8 @@
node** merge_adjacent_ranges(node** first, node** second,
node** third, Less less)
{
- while(true) {
- while(true) {
+ for(;;) {
+ for(;;) {
if(first == second) return third;
if(less((*second)->value_, (*first)->value_)) break;
first = &(*first)->next_;
@@ -256,7 +259,7 @@
// Since the two ranges we just swapped, the order is now:
// first...third...second
- while(true) {
+ for(;;) {
if(first == third) return second;
if(!less((*first)->value_, (*third)->value_)) break;
first = &(*first)->next_;
Modified: trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -116,7 +116,7 @@
}
template <class Container>
-bool general_erase_range_test(Container& x, int start, int end)
+bool general_erase_range_test(Container& x, std::size_t start, std::size_t end)
{
collide_list l(x.begin(), x.end());
l.erase(boost::next(l.begin(), start), boost::next(l.begin(), end));
Modified: trunk/libs/unordered/test/unordered/out_of_line.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/out_of_line.cpp (original)
+++ trunk/libs/unordered/test/unordered/out_of_line.cpp 2009-09-20 17:55:15 EDT (Sun, 20 Sep 2009)
@@ -10,7 +10,7 @@
template <class T>
template <class U>
-bool foo<T>::bar(U x) { return x; }
+bool foo<T>::bar(U x) { return x ? true : false; }
int main() {
foo<int> x;