|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r56375 - in branches/release: . boost/algorithm/string boost/archive boost/fusion boost/graph boost/program_options boost/python boost/regex boost/serialization boost/signals boost/signals2 boost/spirit boost/system boost/unordered boost/unordered/detail boost/wave libs/graph_parallel libs/mpl/doc/refmanual libs/mpl/doc/src/refmanual libs/program_options libs/python libs/regex libs/serialization libs/signals libs/signals2 libs/spirit libs/system libs/timer libs/unordered/doc libs/unordered/test libs/unordered/test/helpers libs/unordered/test/unordered libs/wave status tools/build/v2 tools/regression tools/wave
From: daniel_james_at_[hidden]
Date: 2009-09-24 17:12:49
Author: danieljames
Date: 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
New Revision: 56375
URL: http://svn.boost.org/trac/boost/changeset/56375
Log:
New version of Boost.Unordered
Merged revisions 55470,55877-55878,55901-55902,55921-55922,55990-55992,56009-56010,56329,56346-56349,56362-56363,56374 via svnmerge from
https://svn.boost.org/svn/boost/trunk
........
r55470 | danieljames | 2009-08-08 19:50:00 +0100 (Sat, 08 Aug 2009) | 1 line
Remove empty svn:mergeinfo properties. This should reduce the amount of differences between trunk and release.
........
r55877 | danieljames | 2009-08-30 17:33:42 +0100 (Sun, 30 Aug 2009) | 1 line
Remove allocator_constructor since it's never used.
........
r55878 | danieljames | 2009-08-30 17:42:28 +0100 (Sun, 30 Aug 2009) | 6 lines
Initial checkin of new version of Boost.Unordered.
- More template use, less preprocessor use.
- Removed some of the Visual C++ 6 workarounds.
- Reduced memory use of the main object.
- Split into smaller headers.
........
r55901 | danieljames | 2009-08-31 11:39:25 +0100 (Mon, 31 Aug 2009) | 1 line
Detab.
........
r55902 | danieljames | 2009-08-31 11:39:40 +0100 (Mon, 31 Aug 2009) | 1 line
Remove unnecessary BOOST_DEDUCED_TYPENAMEs
........
r55921 | danieljames | 2009-08-31 16:33:28 +0100 (Mon, 31 Aug 2009) | 1 line
Remove a few unused parameters.
........
r55922 | danieljames | 2009-08-31 16:33:49 +0100 (Mon, 31 Aug 2009) | 1 line
Remove 'static' from next_node and node_count. Will hopefully make vacpp happy.
........
r55990 | danieljames | 2009-09-03 08:36:21 +0100 (Thu, 03 Sep 2009) | 1 line
Combine hash_structure and hash_table_manager.
........
r55991 | danieljames | 2009-09-03 08:37:14 +0100 (Thu, 03 Sep 2009) | 1 line
Remove some old Visual C++ workarounds.
........
r55992 | danieljames | 2009-09-03 08:37:30 +0100 (Thu, 03 Sep 2009) | 1 line
Add a small test to see if the tested compilers support out of line template methods.
........
r56009 | danieljames | 2009-09-04 08:02:28 +0100 (Fri, 04 Sep 2009) | 1 line
Fix link to n2691.
........
r56010 | danieljames | 2009-09-04 08:03:04 +0100 (Fri, 04 Sep 2009) | 1 line
Move size_ and cached_begin_bucket_ into table, rename hash_table_manager hash_buckets.
........
r56329 | danieljames | 2009-09-20 22:55:15 +0100 (Sun, 20 Sep 2009) | 2 lines
Since all the compilers support out of line template members use them
and lots of other things.
........
r56346 | danieljames | 2009-09-21 22:17:19 +0100 (Mon, 21 Sep 2009) | 1 line
Slightly more consistent variable names. In detail 'n' is now always a node pointer.
........
r56347 | danieljames | 2009-09-21 22:17:40 +0100 (Mon, 21 Sep 2009) | 1 line
Fix bug where container was reducing the number of buckets.
........
r56348 | danieljames | 2009-09-21 22:18:01 +0100 (Mon, 21 Sep 2009) | 1 line
Fix a bug that was causing unnecessary rehahes.
........
r56349 | danieljames | 2009-09-21 22:18:21 +0100 (Mon, 21 Sep 2009) | 1 line
Use std::max.
........
r56362 | danieljames | 2009-09-22 23:39:00 +0100 (Tue, 22 Sep 2009) | 1 line
Another std::max.
........
r56363 | danieljames | 2009-09-22 23:39:17 +0100 (Tue, 22 Sep 2009) | 1 line
Remove the emplace_hint implementation for unique containers as it isn't really used and seems to be causing sun 5.7 problems.
........
r56374 | danieljames | 2009-09-24 21:42:19 +0100 (Thu, 24 Sep 2009) | 1 line
Remove temporary test.
........
Added:
branches/release/boost/unordered/detail/buckets.hpp
- copied, changed from r56010, /trunk/boost/unordered/detail/buckets.hpp
branches/release/boost/unordered/detail/equivalent.hpp
- copied, changed from r56329, /trunk/boost/unordered/detail/equivalent.hpp
branches/release/boost/unordered/detail/extract_key.hpp
- copied, changed from r55902, /trunk/boost/unordered/detail/extract_key.hpp
branches/release/boost/unordered/detail/fwd.hpp
- copied, changed from r55902, /trunk/boost/unordered/detail/fwd.hpp
branches/release/boost/unordered/detail/node.hpp
- copied, changed from r55902, /trunk/boost/unordered/detail/node.hpp
branches/release/boost/unordered/detail/table.hpp
- copied, changed from r55902, /trunk/boost/unordered/detail/table.hpp
branches/release/boost/unordered/detail/unique.hpp
- copied, changed from r56329, /trunk/boost/unordered/detail/unique.hpp
branches/release/boost/unordered/detail/util.hpp
- copied, changed from r55902, /trunk/boost/unordered/detail/util.hpp
Removed:
branches/release/boost/unordered/detail/config.hpp
branches/release/boost/unordered/detail/hash_table.hpp
branches/release/boost/unordered/detail/hash_table_impl.hpp
Properties modified:
branches/release/ (props changed)
branches/release/boost/algorithm/string/ (props changed)
branches/release/boost/archive/ (props changed)
branches/release/boost/fusion/ (props changed)
branches/release/boost/graph/ (props changed)
branches/release/boost/program_options/ (props changed)
branches/release/boost/python/ (props changed)
branches/release/boost/regex/ (props changed)
branches/release/boost/serialization/ (props changed)
branches/release/boost/signals/ (props changed)
branches/release/boost/signals2/ (props changed)
branches/release/boost/spirit/ (props changed)
branches/release/boost/system/ (props changed)
branches/release/boost/wave/ (props changed)
branches/release/libs/graph_parallel/ (props changed)
branches/release/libs/mpl/doc/refmanual/broken-compiler-workarounds.html (props changed)
branches/release/libs/mpl/doc/refmanual/categorized-index-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/cfg-no-preprocessed-headers.html (props changed)
branches/release/libs/mpl/doc/refmanual/composition-and-argument-binding.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-concepts.html (props changed)
branches/release/libs/mpl/doc/refmanual/data-types-miscellaneous.html (props changed)
branches/release/libs/mpl/doc/refmanual/extensible-associative-sequence.html (props changed)
branches/release/libs/mpl/doc/refmanual/inserter-class.html (props changed)
branches/release/libs/mpl/doc/refmanual/tag-dispatched-metafunction.html (props changed)
branches/release/libs/mpl/doc/refmanual/trivial-metafunctions-summary.html (props changed)
branches/release/libs/mpl/doc/src/refmanual/Iterators-Iterator.rst (props changed)
branches/release/libs/program_options/ (props changed)
branches/release/libs/python/ (props changed)
branches/release/libs/regex/ (props changed)
branches/release/libs/serialization/ (props changed)
branches/release/libs/signals/ (props changed)
branches/release/libs/signals2/ (props changed)
branches/release/libs/spirit/ (props changed)
branches/release/libs/system/ (props changed)
branches/release/libs/timer/ (props changed)
branches/release/libs/wave/ (props changed)
branches/release/status/ (props changed)
branches/release/tools/build/v2/ (props changed)
branches/release/tools/regression/ (props changed)
branches/release/tools/wave/ (props changed)
Text files modified:
branches/release/boost/unordered/detail/allocator_helpers.hpp | 282 +++---------
branches/release/boost/unordered/detail/buckets.hpp | 265 ++++--------
branches/release/boost/unordered/detail/equivalent.hpp | 14
branches/release/boost/unordered/detail/extract_key.hpp | 25
branches/release/boost/unordered/detail/fwd.hpp | 868 ++++++++++++++++++++++++++++-----------
branches/release/boost/unordered/detail/move.hpp | 19
branches/release/boost/unordered/detail/node.hpp | 159 ++----
branches/release/boost/unordered/detail/table.hpp | 665 +++++++++++++++++++-----------
branches/release/boost/unordered/detail/unique.hpp | 170 ++----
branches/release/boost/unordered/detail/util.hpp | 145 +++---
branches/release/boost/unordered/unordered_map.hpp | 636 ++++++++++++++++-------------
branches/release/boost/unordered/unordered_set.hpp | 607 +++++++++++++++------------
branches/release/libs/unordered/doc/ref.xml | 8
branches/release/libs/unordered/test/Jamfile.v2 | 2
branches/release/libs/unordered/test/helpers/list.hpp | 13
branches/release/libs/unordered/test/unordered/Jamfile.v2 | 1
branches/release/libs/unordered/test/unordered/constructor_tests.cpp | 13
branches/release/libs/unordered/test/unordered/copy_tests.cpp | 8
branches/release/libs/unordered/test/unordered/erase_equiv_tests.cpp | 2
branches/release/libs/unordered/test/unordered/move_tests.cpp | 4
branches/release/libs/unordered/test/unordered/simple_tests.cpp | 3
21 files changed, 2154 insertions(+), 1755 deletions(-)
Modified: branches/release/boost/unordered/detail/allocator_helpers.hpp
==============================================================================
--- branches/release/boost/unordered/detail/allocator_helpers.hpp (original)
+++ branches/release/boost/unordered/detail/allocator_helpers.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -3,6 +3,8 @@
// 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)
+// A couple of templates to make using allocators easier.
+
#ifndef BOOST_UNORDERED_DETAIL_ALLOCATOR_UTILITIES_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_ALLOCATOR_UTILITIES_HPP_INCLUDED
@@ -21,214 +23,86 @@
# include <boost/detail/allocator_utilities.hpp>
#endif
-#include <boost/mpl/aux_/config/eti.hpp>
+namespace boost { namespace unordered_detail {
-namespace boost {
- namespace unordered_detail {
+ // rebind_wrap
+ //
+ // Rebind allocators. For some problematic libraries, use rebind_to
+ // from <boost/detail/allocator_utilities.hpp>.
#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES)
- template <class Alloc, class T>
- struct rebind_wrap : ::boost::detail::allocator::rebind_to<Alloc, T> {};
+ template <class Alloc, class T>
+ struct rebind_wrap : ::boost::detail::allocator::rebind_to<Alloc, T> {};
#else
- template <class Alloc, class T>
- struct rebind_wrap
- {
- typedef BOOST_DEDUCED_TYPENAME
- Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other
- type;
- };
-#endif
-
-#if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
- template <class T>
- inline void reset(T& x) { x = T(); }
-
- template <class Ptr>
- inline Ptr null_ptr() { return Ptr(); }
-#else
- template <class T>
- inline void reset_impl(T& x, ...) { x = T(); }
- template <class T>
- inline void reset_impl(T*& x, int) { x = 0; }
- template <class T>
- inline void reset(T& x) { reset_impl(x); }
-
- template <class Ptr>
- inline Ptr null_ptr() { Ptr x; reset(x); return x; }
-#endif
-
- // Work around for Microsoft's ETI bug.
-
- template <class Allocator> struct allocator_value_type
- {
- typedef BOOST_DEDUCED_TYPENAME Allocator::value_type type;
- };
-
- template <class Allocator> struct allocator_pointer
- {
- typedef BOOST_DEDUCED_TYPENAME Allocator::pointer type;
- };
-
- template <class Allocator> struct allocator_const_pointer
- {
- typedef BOOST_DEDUCED_TYPENAME Allocator::const_pointer type;
- };
-
- template <class Allocator> struct allocator_reference
- {
- typedef BOOST_DEDUCED_TYPENAME Allocator::reference type;
- };
-
- template <class Allocator> struct allocator_const_reference
- {
- typedef BOOST_DEDUCED_TYPENAME Allocator::const_reference type;
- };
-
-#if defined(BOOST_MPL_CFG_MSVC_ETI_BUG)
-
- template <>
- struct allocator_value_type<int>
- {
- typedef int type;
- };
-
- template <>
- struct allocator_pointer<int>
- {
- typedef int type;
- };
-
- template <>
- struct allocator_const_pointer<int>
- {
- typedef int type;
- };
-
- template <>
- struct allocator_reference<int>
- {
- typedef int type;
- };
-
- template <>
- struct allocator_const_reference<int>
- {
- typedef int type;
- };
-
-#endif
-
- template <class Allocator>
- struct allocator_constructor
- {
- typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Allocator>::type value_type;
- typedef BOOST_DEDUCED_TYPENAME allocator_pointer<Allocator>::type pointer;
-
- Allocator& alloc_;
- pointer ptr_;
- bool constructed_;
-
- allocator_constructor(Allocator& a)
- : alloc_(a), ptr_(), constructed_(false)
- {
-#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
- unordered_detail::reset(ptr_);
-#endif
- }
-
- ~allocator_constructor() {
- if(ptr_) {
- if(constructed_) alloc_.destroy(ptr_);
- alloc_.deallocate(ptr_, 1);
- }
- }
-
- template <class V>
- void construct(V const& v) {
- BOOST_ASSERT(!ptr_ && !constructed_);
- ptr_ = alloc_.allocate(1);
- alloc_.construct(ptr_, value_type(v));
- constructed_ = true;
- }
-
- void construct(value_type const& v) {
- BOOST_ASSERT(!ptr_ && !constructed_);
- ptr_ = alloc_.allocate(1);
- alloc_.construct(ptr_, v);
- constructed_ = true;
- }
-
- pointer get() const
- {
- return ptr_;
- }
-
- // no throw
- pointer release()
- {
- pointer p = ptr_;
- constructed_ = false;
- unordered_detail::reset(ptr_);
- return p;
- }
- };
-
- template <class Allocator>
- struct allocator_array_constructor
- {
- typedef BOOST_DEDUCED_TYPENAME allocator_pointer<Allocator>::type pointer;
-
- Allocator& alloc_;
- pointer ptr_;
- pointer constructed_;
- std::size_t length_;
-
- allocator_array_constructor(Allocator& a)
- : alloc_(a), ptr_(), constructed_(), length_(0)
- {
-#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
- unordered_detail::reset(constructed_);
- unordered_detail::reset(ptr_);
-#endif
- }
-
- ~allocator_array_constructor() {
- if (ptr_) {
- for(pointer p = ptr_; p != constructed_; ++p)
- alloc_.destroy(p);
-
- alloc_.deallocate(ptr_, length_);
- }
- }
-
- template <class V>
- void construct(V const& v, std::size_t l)
- {
- BOOST_ASSERT(!ptr_);
- length_ = l;
- ptr_ = alloc_.allocate(length_);
- pointer end = ptr_ + static_cast<std::ptrdiff_t>(length_);
- for(constructed_ = ptr_; constructed_ != end; ++constructed_)
- alloc_.construct(constructed_, v);
- }
-
- pointer get() const
- {
- return ptr_;
- }
-
- pointer release()
- {
- pointer p(ptr_);
- unordered_detail::reset(ptr_);
- return p;
- }
- private:
- allocator_array_constructor(allocator_array_constructor const&);
- allocator_array_constructor& operator=(allocator_array_constructor const&);
- };
- }
-}
+ template <class Alloc, class T>
+ struct rebind_wrap
+ {
+ typedef BOOST_DEDUCED_TYPENAME
+ Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other
+ type;
+ };
+#endif
+
+ // allocator_array_constructor
+ //
+ // Allocate and construct an array in an exception safe manner, and
+ // clean up if an exception is thrown before the container takes charge
+ // of it.
+
+ template <class Allocator>
+ struct allocator_array_constructor
+ {
+ typedef BOOST_DEDUCED_TYPENAME Allocator::pointer pointer;
+
+ Allocator& alloc_;
+ pointer ptr_;
+ pointer constructed_;
+ std::size_t length_;
+
+ allocator_array_constructor(Allocator& a)
+ : alloc_(a), ptr_(), constructed_(), length_(0)
+ {
+ constructed_ = pointer();
+ ptr_ = pointer();
+ }
+
+ ~allocator_array_constructor() {
+ if (ptr_) {
+ for(pointer p = ptr_; p != constructed_; ++p)
+ alloc_.destroy(p);
+
+ alloc_.deallocate(ptr_, length_);
+ }
+ }
+
+ template <class V>
+ void construct(V const& v, std::size_t l)
+ {
+ BOOST_ASSERT(!ptr_);
+ length_ = l;
+ ptr_ = alloc_.allocate(length_);
+ pointer end = ptr_ + static_cast<std::ptrdiff_t>(length_);
+ for(constructed_ = ptr_; constructed_ != end; ++constructed_)
+ alloc_.construct(constructed_, v);
+ }
+
+ pointer get() const
+ {
+ return ptr_;
+ }
+
+ pointer release()
+ {
+ pointer p(ptr_);
+ ptr_ = pointer();
+ return p;
+ }
+ private:
+ allocator_array_constructor(allocator_array_constructor const&);
+ allocator_array_constructor& operator=(
+ allocator_array_constructor const&);
+ };
+}}
#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES)
# undef BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES
Copied: branches/release/boost/unordered/detail/buckets.hpp (from r56010, /trunk/boost/unordered/detail/buckets.hpp)
==============================================================================
--- /trunk/boost/unordered/detail/buckets.hpp (original)
+++ branches/release/boost/unordered/detail/buckets.hpp 2009-09-24 17:12:46 EDT (Thu, 24 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 num) const
{
- return hashed % bucket_count_;
+ return buckets_ + static_cast<std::ptrdiff_t>(num);
}
template <class A, class G>
inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
hash_buckets<A, G>::bucket_ptr_from_hash(std::size_t hashed) const
{
- return 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
+ hash_buckets<A, G>::bucket_begin(std::size_t num) const
{
- return (buckets_ + static_cast<std::ptrdiff_t>(n))->next_;
+ return buckets_ ? get_bucket(num)->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 n = begin;
+ begin = begin->next_;
+ delete_node(n);
+ ++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();
+ }
- node_ = node;
+ ////////////////////////////////////////////////////////////////////////////
+ // Constructors and Destructors
+
+ // no throw
+ template <class A, class G>
+ inline void hash_buckets<A, G>::move(hash_buckets& other)
+ {
+ BOOST_ASSERT(node_alloc() == other.node_alloc());
+ if(this->buckets_) { this->delete_buckets(); }
+ this->buckets_ = other.buckets_;
+ this->bucket_count_ = other.bucket_count_;
+ other.buckets_ = bucket_ptr();
+ other.bucket_count_ = 0;
}
- template <class 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_);
}
}}
Deleted: branches/release/boost/unordered/detail/config.hpp
==============================================================================
--- branches/release/boost/unordered/detail/config.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
+++ (empty file)
@@ -1,30 +0,0 @@
-
-// Copyright 2008-2009 Daniel James.
-// Distributed under the Boost Software License, Version 1.0. (See accompanying
-// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
-
-#if !defined(BOOST_UNORDERED_DETAIL_CONFIG_HEADER)
-#define BOOST_UNORDERED_DETAIL_CONFIG_HEADER
-
-#include <boost/config.hpp>
-
-#if defined(BOOST_NO_SFINAE)
-# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN
-#elif defined(__GNUC__) && \
- (__GNUC__ < 3 || __GNUC__ == 3 && __GNUC_MINOR__ <= 3)
-# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN
-#elif BOOST_WORKAROUND(BOOST_INTEL, < 900) || \
- BOOST_WORKAROUND(__EDG_VERSION__, < 304) || \
- BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x0593))
-# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN
-#endif
-
-#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.
-# else
-# define BOOST_UNORDERED_STD_FORWARD
-# endif
-#endif
-
-#endif
Copied: branches/release/boost/unordered/detail/equivalent.hpp (from r56329, /trunk/boost/unordered/detail/equivalent.hpp)
==============================================================================
--- /trunk/boost/unordered/detail/equivalent.hpp (original)
+++ branches/release/boost/unordered/detail/equivalent.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -177,27 +177,27 @@
#else
-#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
+#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
template <class H, class P, class A, class K> \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
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)) \
+ ::emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
{ \
node_constructor a(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
return emplace_impl(a); \
} \
\
template <class H, class P, class A, class K> \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
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)) \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
{ \
node_constructor a(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
return emplace_hint_impl(it, a); \
}
Copied: branches/release/boost/unordered/detail/extract_key.hpp (from r55902, /trunk/boost/unordered/detail/extract_key.hpp)
==============================================================================
--- /trunk/boost/unordered/detail/extract_key.hpp (original)
+++ branches/release/boost/unordered/detail/extract_key.hpp 2009-09-24 17:12:46 EDT (Thu, 24 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;
+ }
};
};
}}
Copied: branches/release/boost/unordered/detail/fwd.hpp (from r55902, /trunk/boost/unordered/detail/fwd.hpp)
==============================================================================
--- /trunk/boost/unordered/detail/fwd.hpp (original)
+++ branches/release/boost/unordered/detail/fwd.hpp 2009-09-24 17:12:46 EDT (Thu, 24 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, num_params) \
+ BOOST_PP_ENUM_PARAMS_Z(z, num_params, class Arg)
+#define BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
+ BOOST_PP_ENUM_BINARY_PARAMS_Z(z, num_params, Arg, const& arg)
+#define BOOST_UNORDERED_CALL_PARAMS(z, num_params) \
+ BOOST_PP_ENUM_PARAMS_Z(z, num_params, 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_node(bucket& b, node_ptr n);
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_node(bucket& b, node_ptr n);
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,266 +181,303 @@
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>
- {
- typedef ValueType value_type;
- typedef BOOST_DEDUCED_TYPENAME NodeBase::node_ptr node_ptr;
- public:
- static value_type& get_value(node_ptr p) { return static_cast<hash_node&>(*p).value(); }
- };
-
+
template <class A, class G>
- struct hash_structure
+ class hash_node :
+ public G::BOOST_NESTED_TEMPLATE base<A>::type,
+ public value_base<BOOST_DEDUCED_TYPENAME A::value_type>
{
- typedef BOOST_DEDUCED_TYPENAME
- G::BOOST_NESTED_TEMPLATE base<A>::type
- node_base;
- typedef BOOST_DEDUCED_TYPENAME node_base::bucket_allocator bucket_allocator;
- typedef BOOST_DEDUCED_TYPENAME node_base::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME node_base::node_ptr node_ptr;
-
- // The actual data structure
-
- bucket_ptr buckets_;
- bucket_ptr cached_begin_bucket_;
- std::size_t size_;
- std::size_t bucket_count_;
-
- // Constructor
-
- hash_structure() : buckets_(), cached_begin_bucket_(), size_() {}
-
- void swap(hash_structure& other);
-
- // Buckets
-
- std::size_t bucket_count() const;
- std::size_t bucket_from_hash(std::size_t hashed) 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;
-
- // Link a node
-
- void link_node(node_ptr n, node_ptr position);
- void link_node_in_bucket(node_ptr n, bucket_ptr bucket);
- void unlink_node(bucket_ptr bucket, node_ptr pos);
- void unlink_nodes(bucket_ptr bucket, node_ptr begin, node_ptr end);
- void unlink_nodes(bucket_ptr bucket, node_ptr end);
- std::size_t unlink_group(node_ptr* pos);
- void link_group(node_ptr n, bucket_ptr bucket, std::size_t count);
- 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;
-
- // recompute_begin_bucket
- //
- // After an erase cached_begin_bucket_ might be left pointing to
- // an empty bucket, so this is called to update it
- //
- // no throw
-
- void recompute_begin_bucket(bucket_ptr b);
-
- // This is called when a range has been erased
- //
- // no throw
+ public:
+ typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
+ typedef BOOST_DEDUCED_TYPENAME hash_bucket<A>::node_ptr node_ptr;
- void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2);
-
- // no throw
- float load_factor() const;
+ 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 n) {
+ while(!n) {
+ ++bucket_;
+ n = bucket_->next_;
+ }
+ node_ = bucket_ == n ? node_ptr() : n;
+ }
+
+ void increment() {
+ increment_bucket(node_->next_);
+ }
};
- // hash_table_manager
+ // hash_buckets
//
// 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>
- struct hash_table_manager :
- hash_structure<A, G>
+ class hash_buckets
{
+ hash_buckets(hash_buckets const&);
+ hash_buckets& operator=(hash_buckets const&);
+ public:
// Types
- typedef hash_bucket<A> bucket;
- typedef hash_structure<A, G> structure;
- typedef BOOST_DEDUCED_TYPENAME structure::bucket_allocator bucket_allocator;
- typedef BOOST_DEDUCED_TYPENAME structure::node_base node_base;
- typedef BOOST_DEDUCED_TYPENAME structure::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME structure::node_ptr node_ptr;
-
typedef A value_allocator;
+ typedef hash_bucket<A> bucket;
+ 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 hash_node<node_base, value_type> node;
- typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type node_allocator;
- typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr;
+ 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 hash_iterator_base<bucket_ptr> iterator_base;
+ typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type
+ node_allocator;
+ typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr;
// Members
+ bucket_ptr buckets_;
+ std::size_t bucket_count_;
boost::compressed_pair<bucket_allocator, node_allocator> allocators_;
// 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(); }
- iterator_base begin() const { return iterator_base(this->cached_begin_bucket_); }
- iterator_base end() const { return iterator_base(this->buckets_end()); }
+ 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_table_manager();
- explicit hash_table_manager(value_allocator const& a);
- explicit hash_table_manager(hash_table_manager const& h);
- hash_table_manager(hash_table_manager& x, move_tag m);
- hash_table_manager(hash_table_manager& x, value_allocator const& a, move_tag m);
- ~hash_table_manager();
+ hash_buckets(node_allocator const& a, std::size_t n);
+ void create_buckets();
+ ~hash_buckets();
// no throw
- void move(hash_table_manager& other);
+ void swap(hash_buckets& other);
+ void move(hash_buckets& other);
- // Methods
-
- void create_buckets(std::size_t bucket_count);
+ // For the remaining functions, buckets_ must not be null.
+
+ bucket_ptr get_bucket(std::size_t n) const;
+ bucket_ptr bucket_ptr_from_hash(std::size_t hashed) const;
+ std::size_t bucket_size(std::size_t index) const;
+ node_ptr bucket_begin(std::size_t n) const;
// Alloc/Dealloc
- void destruct_node(node_ptr);
+ void delete_node(node_ptr);
//
void delete_buckets();
- void clear();
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);
+ };
- // Erase
- //
- // no throw
+ template <class H, class P> class set_hash_functions;
- iterator_base erase(iterator_base r);
- std::size_t erase_group(node_ptr* it, bucket_ptr bucket);
- iterator_base erase_range(iterator_base r1, iterator_base r2);
+ 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_table_manager<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_table_manager<A, G> manager;
+ 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 manager::node node;
- typedef BOOST_DEDUCED_TYPENAME manager::bucket bucket;
- typedef BOOST_DEDUCED_TYPENAME manager::node_ptr node_ptr;
- typedef BOOST_DEDUCED_TYPENAME manager::bucket_ptr bucket_ptr;
-
- typedef BOOST_DEDUCED_TYPENAME manager::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 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;
+ 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];
+ 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;
@@ -414,42 +489,267 @@
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 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);
// Move/copy buckets
- void move_buckets_to(manager& dst);
- void copy_buckets_to(manager& dst) const;
+ void move_buckets_to(buckets& dst);
+ void copy_buckets_to(buckets& dst) const;
// Misc. key methods
- std::size_t erase_key(key_type const& k);
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
+ //
+ // no throw
+
+ void clear();
+ std::size_t erase_key(key_type const& k);
+ iterator_base erase(iterator_base r);
+ std::size_t erase_group(node_ptr* it, bucket_ptr bucket);
+ iterator_base erase_range(iterator_base r1, iterator_base r2);
+
+ // 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
+ //
+ // no throw
+
+ void recompute_begin_bucket(bucket_ptr b);
+
+ // This is called when a range has been erased
+ //
+ // no throw
+
+ void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2);
+
+ // 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>
+ 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
+
+#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)> \
+ 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_PP_REPEAT_FROM_TO(1, 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 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
@@ -458,7 +758,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_;
}
};
@@ -487,26 +789,40 @@
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
private:
- typedef hash_table_manager<A, G> manager;
- typedef BOOST_DEDUCED_TYPENAME manager::node_ptr ptr;
- typedef BOOST_DEDUCED_TYPENAME manager::node node;
+ typedef hash_buckets<A, G> buckets;
+ 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>
@@ -522,9 +838,9 @@
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
private:
- typedef hash_table_manager<A, G> manager;
- typedef BOOST_DEDUCED_TYPENAME manager::node_ptr ptr;
- typedef BOOST_DEDUCED_TYPENAME manager::node node;
+ typedef hash_buckets<A, G> buckets;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
typedef hash_local_iterator<A, G> local_iterator;
friend class hash_local_iterator<A, G>;
ptr ptr_;
@@ -534,14 +850,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
@@ -562,9 +894,9 @@
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
private:
- typedef hash_table_manager<A, G> manager;
- typedef BOOST_DEDUCED_TYPENAME manager::node node;
- typedef BOOST_DEDUCED_TYPENAME manager::iterator_base base;
+ typedef hash_buckets<A, G> buckets;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+ typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base;
typedef hash_const_iterator<A, G> const_iterator;
friend class hash_const_iterator<A, G>;
base base_;
@@ -573,15 +905,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>
@@ -597,9 +944,9 @@
typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
private:
- typedef hash_table_manager<A, G> manager;
- typedef BOOST_DEDUCED_TYPENAME manager::node node;
- typedef BOOST_DEDUCED_TYPENAME manager::iterator_base base;
+ typedef hash_buckets<A, G> buckets;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+ typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base;
typedef hash_iterator<A, G> iterator;
friend class hash_iterator<A, G>;
friend class iterator_access;
@@ -610,15 +957,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: branches/release/boost/unordered/detail/hash_table.hpp
==============================================================================
--- branches/release/boost/unordered/detail/hash_table.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
+++ (empty file)
@@ -1,347 +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_HASH_TABLE_HPP_INCLUDED
-#define BOOST_UNORDERED_DETAIL_HASH_TABLE_HPP_INCLUDED
-
-#if defined(_MSC_VER) && (_MSC_VER >= 1020)
-# pragma once
-#endif
-
-#include <boost/config.hpp>
-#include <boost/unordered/detail/config.hpp>
-
-#if !defined(BOOST_UNORDERED_EMPLACE_LIMIT)
-#define BOOST_UNORDERED_EMPLACE_LIMIT 10
-#endif
-
-#include <cstddef>
-#include <boost/config/no_tr1/cmath.hpp>
-#include <algorithm>
-#include <utility>
-#include <stdexcept>
-
-#include <boost/iterator.hpp>
-#include <boost/iterator/iterator_categories.hpp>
-#include <boost/limits.hpp>
-#include <boost/assert.hpp>
-#include <boost/static_assert.hpp>
-#include <boost/unordered/detail/allocator_helpers.hpp>
-#include <boost/type_traits/is_same.hpp>
-#include <boost/type_traits/aligned_storage.hpp>
-#include <boost/type_traits/alignment_of.hpp>
-#include <boost/type_traits/remove_reference.hpp>
-#include <boost/type_traits/remove_const.hpp>
-#include <boost/mpl/if.hpp>
-#include <boost/mpl/and.hpp>
-#include <boost/mpl/or.hpp>
-#include <boost/mpl/not.hpp>
-#include <boost/detail/workaround.hpp>
-#include <boost/utility/swap.hpp>
-#include <boost/preprocessor/seq/size.hpp>
-#include <boost/preprocessor/seq/enum.hpp>
-
-#include <boost/mpl/aux_/config/eti.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, typename 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
-
-#if defined(BOOST_MSVC)
-#pragma warning(push)
-#if BOOST_MSVC >= 1400
-#pragma warning(disable:4267) // conversion from 'size_t' to 'unsigned int',
- // possible loss of data.
-#endif
-#endif
-
-#if BOOST_WORKAROUND(__BORLANDC__, <= 0x0582)
-#define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x)
-#else
-#define BOOST_UNORDERED_BORLAND_BOOL(x) x
-#endif
-
-#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
-#define BOOST_UNORDERED_MSVC_RESET_PTR(x) unordered_detail::reset(x)
-#else
-#define BOOST_UNORDERED_MSVC_RESET_PTR(x)
-#endif
-
-namespace boost {
- namespace unordered_detail {
- template <class T> struct type_wrapper {};
-
- static const std::size_t default_initial_bucket_count = 11;
- static const float minimum_max_load_factor = 1e-3f;
-
- inline std::size_t double_to_size_t(double f)
- {
- 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);
- }
-
- // prime number list, accessor
-
- template<typename T> struct prime_list_template
- {
- static std::size_t const value[];
- static std::ptrdiff_t const length;
- };
-
-#define BOOST_UNORDERED_PRIMES \
- (5ul)(11ul)(17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \
- (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \
- (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \
- (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \
- (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \
- (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \
- (1610612741ul)(3221225473ul)(4294967291ul)
-
- template<typename T>
- std::size_t const prime_list_template<T>::value[] = {
- BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)
- };
-
- template<typename T>
- std::ptrdiff_t const prime_list_template<T>::length
- = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
-
-#undef BOOST_UNORDERED_PRIMES
-
- typedef prime_list_template<std::size_t> prime_list;
-
- // no throw
- inline std::size_t next_prime(std::size_t n) {
- std::size_t const* const prime_list_begin = prime_list::value;
- std::size_t const* const prime_list_end = prime_list_begin +
- prime_list::length;
- std::size_t const* bound =
- std::lower_bound(prime_list_begin, prime_list_end, n);
- if(bound == prime_list_end)
- bound--;
- return *bound;
- }
-
- // no throw
- inline std::size_t prev_prime(std::size_t n) {
- std::size_t const* const prime_list_begin = prime_list::value;
- std::size_t const* const prime_list_end = prime_list_begin +
- prime_list::length;
- std::size_t const* bound =
- std::upper_bound(prime_list_begin,prime_list_end, n);
- if(bound != prime_list_begin)
- bound--;
- return *bound;
- }
-
- // Controls how many buckets are allocated and which buckets hash
- // values map to. Does not contain the buckets themselves, or ever
- // deal with them directly.
-
- struct bucket_manager {
- std::size_t bucket_count_;
-
- bucket_manager()
- : bucket_count_(0) {}
-
- explicit bucket_manager(std::size_t n)
- : bucket_count_(next_prime(n)) {}
-
- std::size_t bucket_count() const {
- return bucket_count_;
- }
-
- std::size_t bucket_from_hash(std::size_t hashed) const {
- return hashed % bucket_count_;
- }
-
- std::size_t max_bucket_count(std::size_t max_size) const {
- return prev_prime(max_size);
- }
- };
-
- // pair_cast - used to convert between pair types.
-
- template <class Dst1, class Dst2, class Src1, class Src2>
- inline std::pair<Dst1, Dst2> pair_cast(std::pair<Src1, Src2> const& x)
- {
- return std::pair<Dst1, Dst2>(Dst1(x.first), Dst2(x.second));
- }
-
-#if !defined(BOOST_NO_STD_DISTANCE)
- using ::std::distance;
-#else
- template <class ForwardIterator>
- inline std::size_t distance(ForwardIterator i, ForwardIterator j) {
- std::size_t x;
- std::distance(i, j, x);
- return x;
- }
-#endif
-
- struct move_tag {};
-
- // Both hasher and key_equal's copy/assign can throw so double
- // buffering is used to copy them.
-
- template <typename Hash, typename Pred>
- struct buffered_functions
- {
- typedef Hash hasher;
- typedef Pred key_equal;
-
- class functions
- {
- std::pair<hasher, key_equal> functions_;
-
- public:
-
- functions(hasher const& h, key_equal const& k)
- : functions_(h, k) {}
-
- hasher const& hash_function() const
- {
- return functions_.first;
- }
-
- key_equal const& key_eq() const
- {
- return functions_.second;
- }
- };
-
- typedef functions buffered_functions::*functions_ptr;
-
- buffered_functions(hasher const& h, key_equal const& k)
- : func1_(h, k), func2_(h, k), func_(&buffered_functions::func1_) {}
-
- // This copies the given function objects into the currently unused
- // function objects and returns a pointer, that func_ can later be
- // set to, to commit the change.
- //
- // Strong exception safety (since only usued function objects are
- // changed).
- functions_ptr buffer(buffered_functions const& x) {
- functions_ptr ptr = func_ == &buffered_functions::func1_
- ? &buffered_functions::func2_ : &buffered_functions::func1_;
- this->*ptr = x.current();
- return ptr;
- }
-
- void set(functions_ptr ptr) {
- BOOST_ASSERT(ptr != func_);
- func_ = ptr;
- }
-
- functions const& current() const {
- return this->*func_;
- }
-
- private:
- functions func1_;
- functions func2_;
- functions_ptr func_; // The currently active functions.
- };
-
-#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 <typename T>
- void destroy(T* x) {
- x->~T();
- }
-#endif
- }
-}
-
-#define BOOST_UNORDERED_EQUIVALENT_KEYS 1
-#include <boost/unordered/detail/hash_table_impl.hpp>
-#undef BOOST_UNORDERED_EQUIVALENT_KEYS
-
-#define BOOST_UNORDERED_EQUIVALENT_KEYS 0
-#include <boost/unordered/detail/hash_table_impl.hpp>
-#undef BOOST_UNORDERED_EQUIVALENT_KEYS
-
-namespace boost {
- namespace unordered_detail {
- class iterator_access
- {
- public:
- template <class Iterator>
- static BOOST_DEDUCED_TYPENAME Iterator::base const& get(Iterator const& it) {
- return it.base_;
- }
- };
-
- template <class ValueType, class KeyType,
- class Hash, class Pred, class Alloc>
- class hash_types_unique_keys
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<Alloc, ValueType>::type
- value_allocator;
-
- typedef hash_table_unique_keys<ValueType, KeyType, Hash, Pred,
- value_allocator> hash_table;
- typedef hash_table_data_unique_keys<value_allocator> data;
- typedef BOOST_DEDUCED_TYPENAME data::iterator_base iterator_base;
-
- typedef hash_const_local_iterator_unique_keys<value_allocator> const_local_iterator;
- typedef hash_local_iterator_unique_keys<value_allocator> local_iterator;
- typedef hash_const_iterator_unique_keys<value_allocator> const_iterator;
- typedef hash_iterator_unique_keys<value_allocator> iterator;
-
- typedef BOOST_DEDUCED_TYPENAME data::size_type size_type;
- typedef std::ptrdiff_t difference_type;
- };
-
- template <class ValueType, class KeyType,
- class Hash, class Pred, class Alloc>
- class hash_types_equivalent_keys
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<Alloc, ValueType>::type
- value_allocator;
-
- typedef hash_table_equivalent_keys<ValueType, KeyType, Hash, Pred,
- value_allocator> hash_table;
- typedef hash_table_data_equivalent_keys<value_allocator> data;
- typedef BOOST_DEDUCED_TYPENAME data::iterator_base iterator_base;
-
- typedef hash_const_local_iterator_equivalent_keys<value_allocator> const_local_iterator;
- typedef hash_local_iterator_equivalent_keys<value_allocator> local_iterator;
- typedef hash_const_iterator_equivalent_keys<value_allocator> const_iterator;
- typedef hash_iterator_equivalent_keys<value_allocator> iterator;
-
- typedef BOOST_DEDUCED_TYPENAME data::size_type size_type;
- typedef std::ptrdiff_t difference_type;
- };
- } // namespace boost::unordered_detail
-} // namespace boost
-
-#undef BOOST_UNORDERED_BORLAND_BOOL
-#undef BOOST_UNORDERED_MSVC_RESET_PTR
-
-#if defined(BOOST_MSVC)
-#pragma warning(pop)
-#endif
-
-#endif // BOOST_UNORDERED_DETAIL_HASH_TABLE_HPP_INCLUDED
Deleted: branches/release/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- branches/release/boost/unordered/detail/hash_table_impl.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
+++ (empty file)
@@ -1,2527 +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)
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
-#define BOOST_UNORDERED_TABLE hash_table_equivalent_keys
-#define BOOST_UNORDERED_TABLE_DATA hash_table_data_equivalent_keys
-#define BOOST_UNORDERED_ITERATOR hash_iterator_equivalent_keys
-#define BOOST_UNORDERED_CONST_ITERATOR hash_const_iterator_equivalent_keys
-#define BOOST_UNORDERED_LOCAL_ITERATOR hash_local_iterator_equivalent_keys
-#define BOOST_UNORDERED_CONST_LOCAL_ITERATOR hash_const_local_iterator_equivalent_keys
-#else
-#define BOOST_UNORDERED_TABLE hash_table_unique_keys
-#define BOOST_UNORDERED_TABLE_DATA hash_table_data_unique_keys
-#define BOOST_UNORDERED_ITERATOR hash_iterator_unique_keys
-#define BOOST_UNORDERED_CONST_ITERATOR hash_const_iterator_unique_keys
-#define BOOST_UNORDERED_LOCAL_ITERATOR hash_local_iterator_unique_keys
-#define BOOST_UNORDERED_CONST_LOCAL_ITERATOR hash_const_local_iterator_unique_keys
-#endif
-
-namespace boost {
- namespace unordered_detail {
-
- //
- // Hash Table Data
- //
- // Responsible for managing the hash buckets.
-
- template <typename Alloc>
- class BOOST_UNORDERED_TABLE_DATA
- {
- public:
- typedef BOOST_UNORDERED_TABLE_DATA data;
-
- struct node;
- struct bucket;
- typedef std::size_t size_type;
- typedef std::ptrdiff_t difference_type;
-
- typedef Alloc value_allocator;
-
- typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<Alloc, node>::type
- node_allocator;
- typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<Alloc, bucket>::type
- bucket_allocator;
-
- typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
- typedef BOOST_DEDUCED_TYPENAME allocator_pointer<node_allocator>::type node_ptr;
- typedef BOOST_DEDUCED_TYPENAME allocator_pointer<bucket_allocator>::type bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME allocator_reference<value_allocator>::type reference;
- typedef BOOST_DEDUCED_TYPENAME allocator_reference<bucket_allocator>::type bucket_reference;
-
- typedef bucket_ptr link_ptr;
-
- // Hash Bucket
- //
- // all no throw
-
- struct bucket
- {
- private:
- bucket& operator=(bucket const&);
- public:
- link_ptr next_;
-
- bucket() : next_()
- {
- BOOST_UNORDERED_MSVC_RESET_PTR(next_);
- }
-
- bucket(bucket const& x) : next_(x.next_)
- {
- // Only copy construct when allocating.
- BOOST_ASSERT(!x.next_);
- }
-
- bool empty() const
- {
- return !this->next_;
- }
- };
-
- // Value Base
-
- struct value_base {
- typename boost::aligned_storage<
- sizeof(value_type),
- ::boost::alignment_of<value_type>::value>::type data_;
-
- void* address() { return this; }
- };
-
- // Hash Node
- //
- // all no throw
-
- struct node : value_base, bucket {
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- public:
- node() : group_prev_()
- {
- BOOST_UNORDERED_MSVC_RESET_PTR(group_prev_);
- }
-
- link_ptr group_prev_;
-#endif
-
- value_type& value() {
- return *static_cast<value_type*>(this->address());
- }
- };
-
- // allocators
- //
- // Stores all the allocators that we're going to need.
-
- struct allocators
- {
- node_allocator node_alloc_;
- bucket_allocator bucket_alloc_;
-
- allocators(value_allocator const& a)
- : node_alloc_(a), bucket_alloc_(a)
- {}
-
- void destroy(link_ptr ptr)
- {
- node* raw_ptr = static_cast<node*>(&*ptr);
- BOOST_UNORDERED_DESTRUCT(&raw_ptr->value(), value_type);
- node_ptr n(node_alloc_.address(*raw_ptr));
- node_alloc_.destroy(n);
- node_alloc_.deallocate(n, 1);
- }
-
- void swap(allocators& x)
- {
- boost::swap(node_alloc_, x.node_alloc_);
- boost::swap(bucket_alloc_, x.bucket_alloc_);
- }
-
- bool operator==(allocators const& x)
- {
- return node_alloc_ == x.node_alloc_;
- }
- };
-
- // node_constructor
- //
- // Used to construct nodes in an exception safe manner.
-
- class node_constructor
- {
- allocators& allocators_;
-
- node_ptr node_;
- bool node_constructed_;
- bool value_constructed_;
-
- public:
-
- node_constructor(allocators& a)
- : allocators_(a),
- node_(), node_constructed_(false), value_constructed_(false)
- {
- }
-
- ~node_constructor()
- {
- if (node_) {
- if (value_constructed_) {
- BOOST_UNORDERED_DESTRUCT(&node_->value(), value_type);
- }
-
- if (node_constructed_)
- allocators_.node_alloc_.destroy(node_);
- allocators_.node_alloc_.deallocate(node_, 1);
- }
- }
-
- void construct_preamble()
- {
- if(!node_) {
- node_constructed_ = false;
- value_constructed_ = false;
-
- node_ = allocators_.node_alloc_.allocate(1);
- allocators_.node_alloc_.construct(node_, node());
- node_constructed_ = true;
- }
- else {
- BOOST_ASSERT(node_constructed_ && value_constructed_);
- BOOST_UNORDERED_DESTRUCT(&node_->value(), value_type);
- value_constructed_ = false;
- }
- }
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
- template <typename... Args>
- void construct(Args&&... args)
- {
- construct_preamble();
- new(node_->address()) value_type(std::forward<Args>(args)...);
- value_constructed_ = true;
- }
-#else
-
-#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, n, _) \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- void construct( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- construct_preamble(); \
- construct_impl( \
- (value_type*) 0, \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- ); \
- value_constructed_ = true; \
- } \
- \
- template < \
- typename T, \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- void construct_impl( \
- T*, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- new(node_->address()) value_type( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- ); \
- }
-
-#define BOOST_UNORDERED_CONSTRUCT_IMPL2(z, n, _) \
- template <typename First, typename Second, typename Key, \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- void construct_impl( \
- std::pair<First, Second>*, \
- Key const& k, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- new(node_->address()) value_type(k, \
- Second( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- ) \
- ); \
- }
-
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_CONSTRUCT_IMPL, _)
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_CONSTRUCT_IMPL2, _)
-
- template <typename First, typename Second, typename T1, typename T2>
- void construct_impl(std::pair<First, Second>*,
- std::pair<T1, T2> const& arg0)
- {
- new(node_->address()) value_type(arg0);
- }
-
-#undef BOOST_UNORDERED_CONSTRUCT_IMPL
-
-#endif
- template <typename K, typename M>
- void construct_pair(K const& k, M*)
- {
- construct_preamble();
- new(node_->address()) value_type(k, M());
- value_constructed_ = true;
- }
-
- node_ptr get() const
- {
- BOOST_ASSERT(node_);
- return node_;
- }
-
- // no throw
- link_ptr release()
- {
- node_ptr p = node_;
- unordered_detail::reset(node_);
- return link_ptr(allocators_.bucket_alloc_.address(*p));
- }
-
- private:
- node_constructor(node_constructor const&);
- node_constructor& operator=(node_constructor const&);
- };
-
- // Methods for navigating groups of elements with equal keys.
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- static inline link_ptr& prev_in_group(link_ptr n) {
- return static_cast<node*>(&*n)->group_prev_;
- }
-
- // pre: Must be pointing to the first node in a group.
- static inline link_ptr& next_group(link_ptr n) {
- BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
- return prev_in_group(n)->next_;
- }
-#else
- static inline link_ptr& next_group(link_ptr n) {
- BOOST_ASSERT(n);
- return n->next_;
- }
-#endif
-
- // pre: Must be pointing to a node
- static inline node& get_node(link_ptr p) {
- BOOST_ASSERT(p);
- return *static_cast<node*>(&*p);
- }
-
- // pre: Must be pointing to a node
- static inline reference get_value(link_ptr p) {
- return get_node(p).value();
- }
-
- class iterator_base
- {
- typedef BOOST_UNORDERED_TABLE_DATA<Alloc> data;
- public:
- bucket_ptr bucket_;
- link_ptr node_;
-
- iterator_base()
- : bucket_(), node_()
- {
- BOOST_UNORDERED_MSVC_RESET_PTR(bucket_);
- BOOST_UNORDERED_MSVC_RESET_PTR(node_);
- }
-
- explicit iterator_base(bucket_ptr b)
- : bucket_(b), node_(b->next_) {}
-
- iterator_base(bucket_ptr b, link_ptr n)
- : bucket_(b), node_(n) {}
-
- bool operator==(iterator_base const& x) const
- {
- return node_ == x.node_;
- }
-
- bool operator!=(iterator_base const& x) const
- {
- return node_ != x.node_;
- }
-
- reference operator*() const
- {
- return get_value(node_);
- }
-
- void increment()
- {
- BOOST_ASSERT(bucket_);
- node_ = node_->next_;
-
- while (!node_) {
- ++bucket_;
- node_ = bucket_->next_;
- }
- }
-
- void increment_group()
- {
- node_ = data::next_group(node_);
-
- while (!node_) {
- ++bucket_;
- node_ = bucket_->next_;
- }
- }
- };
-
- // Member Variables
-
- allocators allocators_;
- bucket_ptr buckets_;
- bucket_manager bucket_manager_;
- bucket_ptr cached_begin_bucket_;
- size_type size_;
-
- // Constructors/Deconstructor
-
- BOOST_UNORDERED_TABLE_DATA(size_type n, value_allocator const& a)
- : allocators_(a),
- buckets_(), bucket_manager_(n),
- cached_begin_bucket_(), size_(0)
- {
- BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
- create_buckets();
- }
-
- BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const& x, size_type n)
- : allocators_(x.allocators_),
- buckets_(), bucket_manager_(n),
- cached_begin_bucket_(), size_(0)
- {
- BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
- create_buckets();
- }
-
- BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x, move_tag)
- : allocators_(x.allocators_),
- buckets_(x.buckets_), bucket_manager_(x.bucket_manager_),
- cached_begin_bucket_(x.cached_begin_bucket_), size_(x.size_)
- {
- unordered_detail::reset(x.buckets_);
- }
-
- BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x,
- value_allocator const& a, size_type n, move_tag)
- : allocators_(a), buckets_(), bucket_manager_(),
- cached_begin_bucket_(), size_(0)
- {
- if(allocators_ == x.allocators_) {
- buckets_ = x.buckets_;
- bucket_manager_ = x.bucket_manager_;
- cached_begin_bucket_ = x.cached_begin_bucket_;
- size_ = x.size_;
- unordered_detail::reset(x.buckets_);
- }
- else {
- BOOST_UNORDERED_MSVC_RESET_PTR(buckets_);
- bucket_manager_ = bucket_manager(n);
- create_buckets();
- }
- }
-
- // no throw
- ~BOOST_UNORDERED_TABLE_DATA()
- {
- delete_buckets();
- }
-
- void create_buckets() {
- size_type bucket_count = bucket_manager_.bucket_count();
-
- // The array constructor will clean up in the event of an
- // exception.
- allocator_array_constructor<bucket_allocator>
- constructor(allocators_.bucket_alloc_);
-
- // Creates an extra bucket to act as a sentinel.
- constructor.construct(bucket(), bucket_count + 1);
-
- cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count);
-
- // Set up the sentinel.
- cached_begin_bucket_->next_ = link_ptr(cached_begin_bucket_);
-
- // Only release the buckets once everything is successfully
- // done.
- buckets_ = constructor.release();
- }
-
- // no throw
- void delete_buckets()
- {
- if(buckets_) {
- bucket_ptr begin = cached_begin_bucket_;
- bucket_ptr end = buckets_end();
- while(begin != end) {
- clear_bucket(begin);
- ++begin;
- }
-
- // Destroy an extra bucket for the sentinels.
- ++end;
- for(begin = buckets_; begin != end; ++begin)
- allocators_.bucket_alloc_.destroy(begin);
-
- allocators_.bucket_alloc_.deallocate(buckets_,
- bucket_manager_.bucket_count() + 1);
- }
- }
-
- private:
-
- BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const&);
- BOOST_UNORDERED_TABLE_DATA& operator=(BOOST_UNORDERED_TABLE_DATA const&);
-
- public:
-
- // no throw
- void swap(BOOST_UNORDERED_TABLE_DATA& other)
- {
- std::swap(buckets_, other.buckets_);
- std::swap(bucket_manager_, other.bucket_manager_);
- std::swap(cached_begin_bucket_, other.cached_begin_bucket_);
- std::swap(size_, other.size_);
- }
-
- // no throw
- void move(BOOST_UNORDERED_TABLE_DATA& other)
- {
- delete_buckets();
- buckets_ = other.buckets_;
- unordered_detail::reset(other.buckets_);
- bucket_manager_ = other.bucket_manager_;
- cached_begin_bucket_ = other.cached_begin_bucket_;
- size_ = other.size_;
- }
-
- // Return the bucket number for a hashed value.
- //
- // no throw
- size_type bucket_from_hash(size_type hashed) const
- {
- return bucket_manager_.bucket_from_hash(hashed);
- }
-
- // Return the bucket for a hashed value.
- //
- // no throw
- bucket_ptr bucket_ptr_from_hash(size_type hashed) const
- {
- return buckets_ + static_cast<difference_type>(
- bucket_manager_.bucket_from_hash(hashed));
- }
-
- // Begin & End
- //
- // no throw
-
- bucket_ptr buckets_end() const
- {
- return buckets_ + static_cast<difference_type>(bucket_manager_.bucket_count());
- }
-
- iterator_base begin() const
- {
- return size_
- ? iterator_base(cached_begin_bucket_)
- : end();
- }
-
- iterator_base end() const
- {
- return iterator_base(buckets_end());
- }
-
- link_ptr begin(size_type n) const
- {
- return (buckets_ + static_cast<difference_type>(n))->next_;
- }
-
- link_ptr end(size_type) const
- {
- return unordered_detail::null_ptr<link_ptr>();
- }
-
- link_ptr begin(bucket_ptr b) const
- {
- return b->next_;
- }
-
- // Bucket Size
-
- // no throw
- static inline size_type node_count(link_ptr it)
- {
- size_type count = 0;
- while(BOOST_UNORDERED_BORLAND_BOOL(it)) {
- ++count;
- it = it->next_;
- }
- return count;
- }
-
- static inline size_type node_count(link_ptr it1, link_ptr it2)
- {
- size_type count = 0;
- while(it1 != it2) {
- ++count;
- it1 = it1->next_;
- }
- return count;
- }
-
- size_type bucket_size(size_type n) const
- {
- return node_count(begin(n));
- }
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- static inline size_type group_count(link_ptr it)
- {
- return node_count(it, next_group(it));
- }
-#else
- static inline size_type group_count(link_ptr)
- {
- return 1;
- }
-#endif
-
- // get_for_erase
- //
- // Find the pointer to a node, for use when erasing.
- //
- // no throw
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- static link_ptr* get_for_erase(iterator_base r)
- {
- link_ptr n = r.node_;
-
- // If the element isn't the first in its group, then
- // the link to it will be found in the previous element
- // in the group.
- link_ptr* it = &prev_in_group(n)->next_;
- if(*it == n) return it;
-
- // The element is the first in its group, so iterate
- // throught the groups, checking against the first element.
- it = &r.bucket_->next_;
- while(*it != n) it = &BOOST_UNORDERED_TABLE_DATA::next_group(*it);
- return it;
- }
-#else
- static link_ptr* get_for_erase(iterator_base r)
- {
- link_ptr n = r.node_;
- link_ptr* it = &r.bucket_->next_;
- while(*it != n) it = &(*it)->next_;
- return it;
- }
-#endif
-
- // Link/Unlink/Move Node
- //
- // For adding nodes to buckets, removing them and moving them to a
- // new bucket.
- //
- // no throw
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- // If n points to the first node in a group, this adds it to the
- // end of that group.
- link_ptr link_node(node_constructor& a, link_ptr pos)
- {
- link_ptr n = a.release();
- node& node_ref = get_node(n);
- node& pos_ref = get_node(pos);
- node_ref.next_ = pos_ref.group_prev_->next_;
- node_ref.group_prev_ = pos_ref.group_prev_;
- pos_ref.group_prev_->next_ = n;
- pos_ref.group_prev_ = n;
- ++size_;
- return n;
- }
-
- link_ptr link_node_in_bucket(node_constructor& a, bucket_ptr base)
- {
- link_ptr n = a.release();
- node& node_ref = get_node(n);
- node_ref.next_ = base->next_;
- node_ref.group_prev_ = n;
- base->next_ = n;
- ++size_;
- if(base < cached_begin_bucket_) cached_begin_bucket_ = base;
- return n;
- }
-
- void link_group(link_ptr n, bucket_ptr base, size_type count)
- {
- node& node_ref = get_node(n);
- node& last_ref = get_node(node_ref.group_prev_);
- last_ref.next_ = base->next_;
- base->next_ = n;
- size_ += count;
- if(base < cached_begin_bucket_) cached_begin_bucket_ = base;
- }
-#else
- void link_node(link_ptr n, bucket_ptr base)
- {
- n->next_ = base->next_;
- base->next_ = n;
- ++size_;
- if(base < cached_begin_bucket_) cached_begin_bucket_ = base;
- }
-
- link_ptr link_node_in_bucket(node_constructor& a, bucket_ptr base)
- {
- link_ptr n = a.release();
- link_node(n, base);
- return n;
- }
-
- void link_group(link_ptr n, bucket_ptr base, size_type)
- {
- link_node(n, base);
- }
-#endif
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- void unlink_node(iterator_base it)
- {
- link_ptr* pos = get_for_erase(it);
- node* n = &get_node(it.node_);
- link_ptr next = n->next_;
-
- if(n->group_prev_ == *pos) {
- // The deleted node is the sole node in the group, so
- // no need to unlink it from a group.
- }
- else if(BOOST_UNORDERED_BORLAND_BOOL(next) && prev_in_group(next) == *pos)
- {
- // The deleted node is not at the end of the group, so
- // change the link from the next node.
- prev_in_group(next) = n->group_prev_;
- }
- else {
- // The deleted node is at the end of the group, so the
- // first node in the group is pointing to it.
- // Find that to change its pointer.
- link_ptr it = n->group_prev_;
- while(prev_in_group(it) != *pos) {
- it = prev_in_group(it);
- }
- prev_in_group(it) = n->group_prev_;
- }
- *pos = next;
- --size_;
- }
-
- size_type unlink_group(link_ptr* pos)
- {
- size_type count = group_count(*pos);
- size_ -= count;
- *pos = next_group(*pos);
- return count;
- }
-#else
- void unlink_node(iterator_base n)
- {
- link_ptr* pos = get_for_erase(n);
- *pos = (*pos)->next_;
- --size_;
- }
-
- size_type unlink_group(link_ptr* pos)
- {
- *pos = (*pos)->next_;
- --size_;
- return 1;
- }
-#endif
-
- void unlink_nodes(iterator_base n)
- {
- link_ptr* it = get_for_erase(n);
- split_group(*it);
- unordered_detail::reset(*it);
- size_ -= node_count(n.node_);
- }
-
- void unlink_nodes(iterator_base begin, iterator_base end)
- {
- BOOST_ASSERT(begin.bucket_ == end.bucket_);
- size_ -= node_count(begin.node_, end.node_);
- link_ptr* it = get_for_erase(begin);
- split_group(*it, end.node_);
- *it = end.node_;
- }
-
- void unlink_nodes(bucket_ptr base, iterator_base end)
- {
- BOOST_ASSERT(base == end.bucket_);
-
- split_group(end.node_);
-
- link_ptr ptr(base->next_);
- base->next_ = end.node_;
-
- size_ -= node_count(ptr, end.node_);
- }
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- // Break a ciruclar list into two, with split as the beginning
- // of the second group (if split is at the beginning then don't
- // split).
- static inline link_ptr split_group(link_ptr split)
- {
- // If split is at the beginning of the group then there's
- // nothing to split.
- if(prev_in_group(split)->next_ != split)
- return unordered_detail::null_ptr<link_ptr>();
-
- // Find the start of the group.
- link_ptr start = split;
- do {
- start = prev_in_group(start);
- } while(prev_in_group(start)->next_ == start);
-
- link_ptr last = prev_in_group(start);
- prev_in_group(start) = prev_in_group(split);
- prev_in_group(split) = last;
-
- return start;
- }
-
- static inline void split_group(link_ptr split1, link_ptr split2)
- {
- link_ptr begin1 = split_group(split1);
- link_ptr begin2 = split_group(split2);
-
- if(BOOST_UNORDERED_BORLAND_BOOL(begin1) && split1 == begin2) {
- link_ptr end1 = prev_in_group(begin1);
- prev_in_group(begin1) = prev_in_group(begin2);
- prev_in_group(begin2) = end1;
- }
- }
-#else
- static inline void split_group(link_ptr)
- {
- }
-
- static inline void split_group(link_ptr, link_ptr)
- {
- }
-#endif
-
- // copy_group
- //
- // Basic exception safety.
- // If it throws, it only copies some of the nodes in the group.
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- void copy_group(link_ptr it, bucket_ptr dst)
- {
- node_constructor a(allocators_);
-
- link_ptr end = next_group(it);
-
- a.construct(get_value(it)); // throws
- link_ptr n = link_node_in_bucket(a, dst);
-
- for(it = it->next_; it != end; it = it->next_) {
- a.construct(get_value(it)); // throws
- link_node(a, n);
- }
- }
-#else
- void copy_group(link_ptr it, bucket_ptr dst)
- {
- node_constructor a(allocators_);
-
- a.construct(get_value(it)); // throws
- link_node_in_bucket(a, dst);
- }
-#endif
-
- // Delete Node
- //
- // Remove a node, or a range of nodes, from a bucket, and destroy
- // them.
- //
- // no throw
-
- void delete_to_bucket_end(link_ptr begin)
- {
- while(begin) {
- link_ptr node = begin;
- begin = begin->next_;
- allocators_.destroy(node);
- }
- }
-
- void delete_nodes(link_ptr begin, link_ptr end)
- {
- while(begin != end) {
- link_ptr node = begin;
- begin = begin->next_;
- allocators_.destroy(node);
- }
- }
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- void delete_group(link_ptr first_node)
- {
- delete_nodes(first_node, prev_in_group(first_node)->next_);
- }
-#else
- void delete_group(link_ptr node)
- {
- allocators_.destroy(node);
- }
-#endif
-
- // Clear
- //
- // Remove all the nodes.
- //
- // no throw
-
- void clear_bucket(bucket_ptr b)
- {
- link_ptr first_node = b->next_;
- unordered_detail::reset(b->next_);
- delete_to_bucket_end(first_node);
- }
-
- void clear()
- {
- bucket_ptr begin = cached_begin_bucket_;
- bucket_ptr end = buckets_end();
-
- size_ = 0;
- cached_begin_bucket_ = end;
-
- while(begin != end) {
- clear_bucket(begin);
- ++begin;
- }
- }
-
- // Erase
- //
- // no throw
-
- iterator_base erase(iterator_base r)
- {
- BOOST_ASSERT(r != end());
- iterator_base next = r;
- next.increment();
- unlink_node(r);
- allocators_.destroy(r.node_);
- // r has been invalidated but its bucket is still valid
- recompute_begin_bucket(r.bucket_, next.bucket_);
- return next;
- }
-
- iterator_base erase_range(iterator_base r1, iterator_base r2)
- {
- if(r1 != r2)
- {
- BOOST_ASSERT(r1 != end());
-
- if (r1.bucket_ == r2.bucket_) {
- unlink_nodes(r1, r2);
- delete_nodes(r1.node_, r2.node_);
-
- // No need to call recompute_begin_bucket because
- // the nodes are only deleted from one bucket, which
- // still contains r2 after the erase.
- BOOST_ASSERT(!r1.bucket_->empty());
- }
- else {
- BOOST_ASSERT(r1.bucket_ < r2.bucket_);
-
- unlink_nodes(r1);
- delete_to_bucket_end(r1.node_);
-
- bucket_ptr i = r1.bucket_;
- for(++i; i != r2.bucket_; ++i) {
- size_ -= node_count(i->next_);
- clear_bucket(i);
- }
-
- if(r2 != end()) {
- link_ptr first = r2.bucket_->next_;
- unlink_nodes(r2.bucket_, r2);
- delete_nodes(first, r2.node_);
- }
-
- // r1 has been invalidated but its bucket is still
- // valid.
- recompute_begin_bucket(r1.bucket_, r2.bucket_);
- }
- }
-
- return r2;
- }
-
- // recompute_begin_bucket
- //
- // After an erase cached_begin_bucket_ might be left pointing to
- // an empty bucket, so this is called to update it
- //
- // no throw
-
- void recompute_begin_bucket(bucket_ptr b)
- {
- BOOST_ASSERT(!(b < cached_begin_bucket_));
-
- if(b == cached_begin_bucket_)
- {
- if (size_ != 0) {
- while (cached_begin_bucket_->empty())
- ++cached_begin_bucket_;
- } else {
- cached_begin_bucket_ = buckets_end();
- }
- }
- }
-
- // This is called when a range has been erased
- //
- // no throw
-
- void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2)
- {
- BOOST_ASSERT(!(b1 < cached_begin_bucket_) && !(b2 < b1));
- BOOST_ASSERT(b2 == buckets_end() || !b2->empty());
-
- if(b1 == cached_begin_bucket_ && b1->empty())
- cached_begin_bucket_ = b2;
- }
-
- size_type erase_group(link_ptr* it, bucket_ptr bucket)
- {
- link_ptr pos = *it;
- size_type count = unlink_group(it);
- delete_group(pos);
-
- this->recompute_begin_bucket(bucket);
-
- return count;
- }
- };
-
-#if defined(BOOST_MPL_CFG_MSVC_ETI_BUG)
- template <>
- class BOOST_UNORDERED_TABLE_DATA<int>
- {
- public:
- typedef int size_type;
- typedef int iterator_base;
- };
-#endif
-
- //
- // Hash Table
- //
-
- template <typename ValueType, typename KeyType,
- typename Hash, typename Pred,
- typename Alloc>
- class BOOST_UNORDERED_TABLE
- {
- typedef BOOST_UNORDERED_TABLE_DATA<Alloc> data;
-
- typedef BOOST_DEDUCED_TYPENAME data::node_constructor node_constructor;
- typedef BOOST_DEDUCED_TYPENAME data::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME data::link_ptr link_ptr;
-
- public:
-
- typedef BOOST_DEDUCED_TYPENAME data::value_allocator value_allocator;
- typedef BOOST_DEDUCED_TYPENAME data::node_allocator node_allocator;
-
- // Type definitions
-
- typedef KeyType key_type;
- typedef Hash hasher;
- typedef Pred key_equal;
- typedef ValueType value_type;
- typedef std::size_t size_type;
- typedef std::ptrdiff_t difference_type;
-
- // iterators
-
- typedef BOOST_DEDUCED_TYPENAME data::iterator_base iterator_base;
-
- private:
-
-
- typedef boost::unordered_detail::buffered_functions<Hash, Pred>
- function_store;
- typedef BOOST_DEDUCED_TYPENAME function_store::functions functions;
- typedef BOOST_DEDUCED_TYPENAME function_store::functions_ptr
- functions_ptr;
-
- function_store functions_;
- float mlf_;
- size_type max_load_;
-
- public:
-
- data data_;
-
- // Constructors
- //
- // In the constructors, if anything throws an exception,
- // BOOST_UNORDERED_TABLE_DATA's destructor will clean up.
-
- BOOST_UNORDERED_TABLE(size_type n,
- hasher const& hf, key_equal const& eq,
- value_allocator const& a)
- : functions_(hf, eq), // throws, cleans itself up
- mlf_(1.0f), // no throw
- data_(n, a) // throws, cleans itself up
- {
- calculate_max_load(); // no throw
- }
-
- // Construct from iterators
-
- // initial_size
- //
- // A helper function for the copy constructor to calculate how many
- // nodes will be created if the iterator's support it. Might get it
- // totally wrong for containers with unique keys.
- //
- // no throw
-
- template <typename I>
- size_type initial_size(I i, I j, size_type n,
- boost::forward_traversal_tag)
- {
- // max load factor isn't set yet, but when it is, it'll be 1.0.
- return (std::max)(static_cast<size_type>(unordered_detail::distance(i, j)) + 1, n);
- }
-
- template <typename I>
- size_type initial_size(I, I, size_type n,
- boost::incrementable_traversal_tag)
- {
- return n;
- }
-
- template <typename I>
- size_type initial_size(I i, I j, size_type n)
- {
- BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
- iterator_traversal_tag;
- return initial_size(i, j, n, iterator_traversal_tag);
- }
-
- template <typename I>
- BOOST_UNORDERED_TABLE(I i, I j, size_type n,
- hasher const& hf, key_equal const& eq,
- value_allocator const& a)
- : functions_(hf, eq), // throws, cleans itself up
- mlf_(1.0f), // no throw
- data_(initial_size(i, j, n), a) // throws, cleans itself up
- {
- calculate_max_load(); // no throw
-
- // This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean up.
- insert_range(i, j);
- }
-
- // Copy Construct
-
- BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE const& x)
- : functions_(x.functions_), // throws
- mlf_(x.mlf_), // no throw
- data_(x.data_, x.min_buckets_for_size(x.size())) // throws
- {
- calculate_max_load(); // no throw
-
- // This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean
- // up.
- x.copy_buckets_to(data_);
- }
-
- // Copy Construct with allocator
-
- BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE const& x,
- value_allocator const& a)
- : functions_(x.functions_), // throws
- mlf_(x.mlf_), // no throw
- data_(x.min_buckets_for_size(x.size()), a)
- {
- calculate_max_load(); // no throw
-
- // This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean
- // up.
- x.copy_buckets_to(data_);
- }
-
- // Move Construct
-
- BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE& x, move_tag m)
- : functions_(x.functions_), // throws
- mlf_(x.mlf_), // no throw
- data_(x.data_, m) // throws
- {
- calculate_max_load(); // no throw
- }
-
- BOOST_UNORDERED_TABLE(BOOST_UNORDERED_TABLE& x,
- value_allocator const& a, move_tag m)
- : functions_(x.functions_), // throws
- mlf_(x.mlf_), // no throw
- data_(x.data_, a,
- x.min_buckets_for_size(x.size()), m) // throws
- {
- calculate_max_load(); // no throw
-
- if(x.data_.buckets_) {
- // This can throw, but BOOST_UNORDERED_TABLE_DATA's destructor will clean
- // up.
- x.copy_buckets_to(data_);
- }
- }
-
- // Assign
- //
- // basic exception safety, if buffered_functions::buffer or reserver throws
- // the container is left in a sane, empty state. If copy_buckets_to
- // throws the container is left with whatever was successfully
- // copied.
-
- BOOST_UNORDERED_TABLE& operator=(BOOST_UNORDERED_TABLE const& x)
- {
- if(this != &x)
- {
- data_.clear(); // no throw
- functions_.set(functions_.buffer(x.functions_));
- // throws, strong
- mlf_ = x.mlf_; // no throw
- calculate_max_load(); // no throw
- reserve(x.size()); // throws
- x.copy_buckets_to(data_); // throws
- }
-
- return *this;
- }
-
- // Swap
- //
- // Swap's behaviour when allocators aren't equal is in dispute, for
- // details see:
- //
- // http://unordered.nfshost.com/doc/html/unordered/rationale.html#swapping_containers_with_unequal_allocators
- //
- // ----------------------------------------------------------------
- //
- // Strong exception safety (might change unused function objects)
- //
- // Can throw if hash or predicate object's copy constructor throws
- // or if allocators are unequal.
-
- void swap(BOOST_UNORDERED_TABLE& x)
- {
- // The swap code can work when swapping a container with itself
- // but it triggers an assertion in buffered_functions.
- // At the moment, I'd rather leave that assertion in and add a
- // check here, rather than remove the assertion. I might change
- // this at a later date.
- if(this == &x) return;
-
- // These can throw, but they only affect the function objects
- // that aren't in use so it is strongly exception safe, via.
- // double buffering.
- functions_ptr new_func_this = functions_.buffer(x.functions_);
- functions_ptr new_func_that = x.functions_.buffer(functions_);
-
- if(data_.allocators_ == x.data_.allocators_) {
- data_.swap(x.data_); // no throw
- }
- else {
- // Create new buckets in separate HASH_TABLE_DATA objects
- // which will clean up if anything throws an exception.
- // (all can throw, but with no effect as these are new objects).
- data new_this(data_, x.min_buckets_for_size(x.data_.size_));
- x.copy_buckets_to(new_this);
-
- data new_that(x.data_, min_buckets_for_size(data_.size_));
- copy_buckets_to(new_that);
-
- // Start updating the data here, no throw from now on.
- data_.swap(new_this);
- x.data_.swap(new_that);
- }
-
- // We've made it, the rest is no throw.
- std::swap(mlf_, x.mlf_);
-
- functions_.set(new_func_this);
- x.functions_.set(new_func_that);
-
- calculate_max_load();
- x.calculate_max_load();
- }
-
- // Move
- //
- // ----------------------------------------------------------------
- //
- // Strong exception safety (might change unused function objects)
- //
- // Can throw if hash or predicate object's copy constructor throws
- // or if allocators are unequal.
-
- void move(BOOST_UNORDERED_TABLE& x)
- {
- // This can throw, but it only affects the function objects
- // that aren't in use so it is strongly exception safe, via.
- // double buffering.
- functions_ptr new_func_this = functions_.buffer(x.functions_);
-
- if(data_.allocators_ == x.data_.allocators_) {
- data_.move(x.data_); // no throw
- }
- else {
- // Create new buckets in separate HASH_TABLE_DATA objects
- // which will clean up if anything throws an exception.
- // (all can throw, but with no effect as these are new objects).
- data new_this(data_, x.min_buckets_for_size(x.data_.size_));
- x.copy_buckets_to(new_this);
-
- // Start updating the data here, no throw from now on.
- data_.move(new_this);
- }
-
- // We've made it, the rest is no throw.
- mlf_ = x.mlf_;
- functions_.set(new_func_this);
- calculate_max_load();
- }
-
- // accessors
-
- // no throw
- node_allocator get_allocator() const
- {
- return data_.allocators_.node_alloc_;
- }
-
- // no throw
- hasher const& hash_function() const
- {
- return functions_.current().hash_function();
- }
-
- // no throw
- key_equal const& key_eq() const
- {
- return functions_.current().key_eq();
- }
-
- // no throw
- size_type size() const
- {
- return data_.size_;
- }
-
- // no throw
- bool empty() const
- {
- return data_.size_ == 0;
- }
-
- // no throw
- size_type max_size() const
- {
- using namespace std;
-
- // size < mlf_ * count
- return double_to_size_t(ceil(
- (double) mlf_ * max_bucket_count())) - 1;
- }
-
- // strong safety
- size_type bucket(key_type const& k) const
- {
- // hash_function can throw:
- return data_.bucket_from_hash(hash_function()(k));
- }
-
-
- // strong safety
- bucket_ptr get_bucket(key_type const& k) const
- {
- return data_.buckets_ + static_cast<difference_type>(bucket(k));
- }
-
- // no throw
- size_type bucket_count() const
- {
- return data_.bucket_manager_.bucket_count();
- }
-
- // no throw
- size_type max_bucket_count() const
- {
- // -1 to account for the end marker.
- return prev_prime(data_.allocators_.bucket_alloc_.max_size() - 1);
- }
-
- private:
-
- // no throw
- size_type min_buckets_for_size(size_type n) const
- {
- BOOST_ASSERT(mlf_ != 0);
-
- using namespace std;
-
- // From 6.3.1/13:
- // size < mlf_ * count
- // => count > size / mlf_
- //
- // Or from rehash post-condition:
- // count > size / mlf_
- return double_to_size_t(floor(n / (double) mlf_)) + 1;
- }
-
- // no throw
- void calculate_max_load()
- {
- using namespace std;
-
- // From 6.3.1/13:
- // Only resize when size >= mlf_ * count
- max_load_ = double_to_size_t(ceil(
- (double) mlf_ * data_.bucket_manager_.bucket_count()));
- }
-
- // basic exception safety
- bool reserve(size_type n)
- {
- bool need_to_reserve = n >= max_load_;
- // throws - basic:
- if (need_to_reserve) rehash_impl(min_buckets_for_size(n));
- BOOST_ASSERT(n < max_load_ || n > max_size());
- return need_to_reserve;
- }
-
- // basic exception safety
- bool reserve_for_insert(size_type n)
- {
- bool need_to_reserve = n >= max_load_;
- // throws - basic:
- if (need_to_reserve) {
- size_type s = size();
- s = s + (s >> 1);
- s = s > n ? s : n;
- rehash_impl(min_buckets_for_size(s));
- }
- BOOST_ASSERT(n < max_load_ || n > max_size());
- return need_to_reserve;
- }
-
- public:
-
- // no throw
- float max_load_factor() const
- {
- return mlf_;
- }
-
- // no throw
- void max_load_factor(float z)
- {
- BOOST_ASSERT(z > 0);
- mlf_ = (std::max)(z, minimum_max_load_factor);
- calculate_max_load();
- }
-
- // no throw
- float load_factor() const
- {
- BOOST_ASSERT(data_.bucket_manager_.bucket_count() != 0);
- return static_cast<float>(data_.size_)
- / static_cast<float>(data_.bucket_manager_.bucket_count());
- }
-
- // key extractors
- //
- // no throw
- //
- // 'extract_key' is called with the emplace parameters to return a
- // key if available or 'no_key' is one isn't and will need to be
- // constructed.
-
- struct no_key {
- no_key() {}
- template <class T> no_key(T const&) {}
- };
-
-
- // If emplace is called with no arguments then there obviously
- // isn't an available key.
-
- static no_key extract_key()
- {
- return no_key();
- }
-
- // Emplace or insert was called with the value type.
-
- static key_type const& extract_key(value_type const& v)
- {
- return extract(v, (type_wrapper<value_type>*)0);
- }
-
- static key_type const& extract(value_type const& v,
- type_wrapper<key_type>*)
- {
- return v;
- }
-
- static key_type const& extract(value_type const& v,
- void*)
- {
- return v.first;
- }
-
- // For maps, if emplace is called with just a key, then it's the value type
- // with the second value default initialised.
-
- template <typename Arg>
- static BOOST_DEDUCED_TYPENAME
- boost::mpl::if_<boost::is_same<Arg, key_type>, key_type const&, no_key>::type
- extract_key(Arg const& k)
- {
- return k;
- }
-
- // For a map, the argument might be a pair with the key as the first
- // part and a convertible value as the second part.
-
- template <typename First, typename Second>
- static BOOST_DEDUCED_TYPENAME
- boost::mpl::if_<
- boost::mpl::and_<
- boost::mpl::not_<boost::is_same<key_type, value_type> >,
- boost::is_same<key_type,
- typename boost::remove_const<
- typename boost::remove_reference<First>::type
- >::type>
- >,
- key_type const&, no_key
- >::type extract_key(std::pair<First, Second> const& v)
- {
- return v.first;
- }
-
- // For maps if there is more than one argument, the key can be the first argument.
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
- template <typename Arg, typename Arg1, typename... Args>
- static BOOST_DEDUCED_TYPENAME
- boost::mpl::if_<
- boost::mpl::and_<
- boost::mpl::not_<boost::is_same<value_type, key_type> >,
- boost::is_same<Arg, key_type>
- >,
- key_type const&, no_key
- >::type extract_key(Arg const& k, Arg1 const&, Args const&...)
- {
- return k;
- }
-
-#else
- template <typename Arg, typename Arg1>
- static BOOST_DEDUCED_TYPENAME
- boost::mpl::if_<
- boost::mpl::and_<
- boost::mpl::not_<boost::is_same<value_type, key_type> >,
- boost::is_same<Arg, key_type>
- >,
- key_type const&, no_key
- >::type extract_key(Arg const& k, Arg1 const&)
- {
- return k;
- }
-
-#endif
-
- public:
-
- // if hash function throws, basic exception safety
- // strong otherwise.
- void rehash(size_type n)
- {
- using namespace std;
-
- // no throw:
- size_type min_size = min_buckets_for_size(size());
- // basic/strong:
- rehash_impl(min_size > n ? min_size : n);
-
- BOOST_ASSERT((float) bucket_count() > (float) size() / max_load_factor()
- && bucket_count() >= n);
- }
-
- private:
-
- // if hash function throws, basic exception safety
- // strong otherwise
- void rehash_impl(size_type n)
- {
- n = next_prime(n); // no throw
-
- if (n == bucket_count()) // no throw
- return;
-
- data new_buckets(data_, n); // throws, seperate
- move_buckets_to(new_buckets); // basic/no throw
- new_buckets.swap(data_); // no throw
- calculate_max_load(); // no throw
- }
-
- // move_buckets_to & copy_buckets_to
- //
- // if the hash function throws, basic excpetion safety
- // no throw otherwise
-
- void move_buckets_to(data& dst)
- {
- BOOST_ASSERT(dst.size_ == 0);
- //BOOST_ASSERT(src.allocators_.node_alloc_ == dst.allocators_.node_alloc_);
-
- data& src = this->data_;
- hasher const& hf = this->hash_function();
- bucket_ptr end = src.buckets_end();
-
- for(; src.cached_begin_bucket_ != end;
- ++src.cached_begin_bucket_) {
- bucket_ptr src_bucket = src.cached_begin_bucket_;
- while(src_bucket->next_) {
- // Move the first group of equivalent nodes in
- // src_bucket to dst.
-
- // This next line throws iff the hash function throws.
- bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
- hf(extract_key(data::get_value(src_bucket->next_))));
-
- link_ptr n = src_bucket->next_;
- size_type count = src.unlink_group(&src_bucket->next_);
- dst.link_group(n, dst_bucket, count);
- }
- }
- }
-
- // basic excpetion safety. If an exception is thrown this will
- // leave dst partially filled.
-
- void copy_buckets_to(data& dst) const
- {
- BOOST_ASSERT(dst.size_ == 0);
-
- // no throw:
- data const& src = this->data_;
- hasher const& hf = this->hash_function();
- bucket_ptr end = src.buckets_end();
-
- // no throw:
- for(bucket_ptr i = src.cached_begin_bucket_; i != end; ++i) {
- // no throw:
- for(link_ptr it = src.begin(i);
- BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it)) {
- // hash function can throw.
- bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
- hf(extract_key(data::get_value(it))));
- // throws, strong
- dst.copy_group(it, dst_bucket);
- }
- }
- }
-
- public:
-
- // Insert functions
- //
- // basic exception safety, if hash function throws
- // strong otherwise.
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
-
- // Emplace (equivalent key containers)
- // (I'm using an overloaded emplace for both 'insert' and 'emplace')
-
- // if hash function throws, basic exception safety
- // strong otherwise
- template <class... Args>
- iterator_base emplace(Args&&... args)
- {
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- node_constructor a(data_.allocators_);
- a.construct(std::forward<Args>(args)...);
-
- return emplace_impl(a);
- }
-
- // Emplace (equivalent key containers)
- // (I'm using an overloaded emplace for both 'insert' and 'emplace')
-
- // if hash function throws, basic exception safety
- // strong otherwise
- template <class... Args>
- iterator_base emplace_hint(iterator_base const& it, Args&&... args)
- {
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- node_constructor a(data_.allocators_);
- a.construct(std::forward<Args>(args)...);
-
- return emplace_hint_impl(it, a);
- }
-
-#else
-
-#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- iterator_base emplace( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- node_constructor a(data_.allocators_); \
- a.construct( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- ); \
- return emplace_impl(a); \
- } \
- \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- iterator_base emplace_hint(iterator_base const& it, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- node_constructor a(data_.allocators_); \
- a.construct( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- ); \
- return emplace_hint_impl(it, a); \
- }
-
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_INSERT_IMPL, _)
-
-#undef BOOST_UNORDERED_INSERT_IMPL
-#endif
-
- iterator_base emplace_impl(node_constructor& a)
- {
- key_type const& k = extract_key(a.get()->value());
- size_type hash_value = hash_function()(k);
- bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
- link_ptr position = find_iterator(bucket, k);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(reserve_for_insert(size() + 1))
- bucket = data_.bucket_ptr_from_hash(hash_value);
-
- // I'm relying on link_ptr not being invalidated by
- // the rehash here.
- return iterator_base(bucket,
- (BOOST_UNORDERED_BORLAND_BOOL(position)) ?
- data_.link_node(a, position) :
- data_.link_node_in_bucket(a, bucket)
- );
- }
-
- iterator_base emplace_hint_impl(iterator_base const& it, node_constructor& a)
- {
- // equal can throw, but with no effects
- if (it == data_.end() || !equal(extract_key(a.get()->value()), *it)) {
- // Use the standard emplace if the iterator doesn't point
- // to a matching key.
- return emplace_impl(a);
- }
- else {
- // Find the first node in the group - so that the node
- // will be added at the end of the group.
-
- link_ptr start(it.node_);
- while(data_.prev_in_group(start)->next_ == start)
- start = data_.prev_in_group(start);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- bucket_ptr base = reserve_for_insert(size() + 1) ?
- get_bucket(extract_key(a.get()->value())) : it.bucket_;
-
- // Nothing after this point can throw
-
- return iterator_base(base,
- data_.link_node(a, start));
- }
- }
-
- // Insert from iterator range (equivalent key containers)
-
- private:
-
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <typename I>
- void insert_for_range(I i, I j, forward_traversal_tag)
- {
- size_type distance = unordered_detail::distance(i, j);
- if(distance == 1) {
- emplace(*i);
- }
- else {
- // Only require basic exception safety here
- reserve_for_insert(size() + distance);
- node_constructor a(data_.allocators_);
-
- for (; i != j; ++i) {
- a.construct(*i);
-
- key_type const& k = extract_key(a.get()->value());
- bucket_ptr bucket = get_bucket(k);
- link_ptr position = find_iterator(bucket, k);
-
- if(BOOST_UNORDERED_BORLAND_BOOL(position))
- data_.link_node(a, position);
- else
- data_.link_node_in_bucket(a, bucket);
- }
- }
- }
-
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <typename I>
- void insert_for_range(I i, I j,
- boost::incrementable_traversal_tag)
- {
- // If only inserting 1 element, get the required
- // safety since insert is only called once.
- for (; i != j; ++i) emplace(*i);
- }
-
- public:
-
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <typename I>
- void insert_range(I i, I j)
- {
- BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
- iterator_traversal_tag;
- insert_for_range(i, j, iterator_traversal_tag);
- }
-#else
- // if hash function throws, basic exception safety
- // strong otherwise
- value_type& operator[](key_type const& k)
- {
- BOOST_STATIC_ASSERT((
- !boost::is_same<value_type, key_type>::value));
- typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
-
- size_type hash_value = hash_function()(k);
- bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
- link_ptr pos = find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(pos))
- return data::get_value(pos);
- else
- {
- // Side effects only in this block.
-
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- node_constructor a(data_.allocators_);
- a.construct_pair(k, (mapped_type*) 0);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(reserve_for_insert(size() + 1))
- bucket = data_.bucket_ptr_from_hash(hash_value);
-
- // Nothing after this point can throw.
-
- return data::get_value(data_.link_node_in_bucket(a, bucket));
- }
- }
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
-
- // Emplace (unique keys)
- // (I'm using an overloaded emplace for both 'insert' and 'emplace')
-
- // if hash function throws, basic exception safety
- // strong otherwise
- template<typename... Args>
- std::pair<iterator_base, bool> emplace(Args&&... args)
- {
- return emplace_impl(
- extract_key(std::forward<Args>(args)...),
- std::forward<Args>(args)...);
- }
-
- // Insert (unique keys)
- // (I'm using an overloaded emplace for both 'insert' and 'emplace')
- // I'm just ignoring hints here for now.
-
- // if hash function throws, basic exception safety
- // strong otherwise
- template<typename... Args>
- iterator_base emplace_hint(iterator_base const&, Args&&... args)
- {
- return emplace_impl(
- extract_key(std::forward<Args>(args)...),
- std::forward<Args>(args)...).first;
- }
-
- template<typename... Args>
- std::pair<iterator_base, bool> emplace_impl(key_type const& k, Args&&... args)
- {
- // No side effects in this initial code
- size_type hash_value = hash_function()(k);
- bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
- link_ptr pos = find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Found an existing key, return it (no throw).
- return std::pair<iterator_base, bool>(
- iterator_base(bucket, pos), false);
-
- } else {
- // Doesn't already exist, add to bucket.
- // Side effects only in this block.
-
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- node_constructor a(data_.allocators_);
- a.construct(std::forward<Args>(args)...);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(reserve_for_insert(size() + 1))
- bucket = data_.bucket_ptr_from_hash(hash_value);
-
- // Nothing after this point can throw.
-
- return std::pair<iterator_base, bool>(iterator_base(bucket,
- data_.link_node_in_bucket(a, bucket)), true);
- }
- }
-
- template<typename... Args>
- std::pair<iterator_base, bool> emplace_impl(no_key, Args&&... args)
- {
- // Construct the node regardless - in order to get the key.
- // It will be discarded if it isn't used
- node_constructor a(data_.allocators_);
- a.construct(std::forward<Args>(args)...);
- return emplace_impl_with_node(a);
- }
-#else
- template <typename Arg0>
- std::pair<iterator_base, bool> emplace(Arg0 const& arg0)
- {
- return emplace_impl(extract_key(arg0), arg0);
- }
-
- template <typename Arg0>
- iterator_base emplace_hint(iterator_base const& it, Arg0 const& arg0)
- {
- return emplace_impl(extract_key(arg0), arg0).first;
- }
-
-
-#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- std::pair<iterator_base, bool> emplace( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return emplace_impl( \
- extract_key(arg0, arg1), \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- ); \
- } \
- \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- iterator_base emplace_hint(iterator_base const& it, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return emplace_impl( \
- extract_key(arg0, arg1), \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- ).first; \
- } \
- BOOST_UNORDERED_INSERT_IMPL2(z, n, _)
-
-#define BOOST_UNORDERED_INSERT_IMPL2(z, n, _) \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- std::pair<iterator_base, bool> emplace_impl(key_type const& k, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- size_type hash_value = hash_function()(k); \
- bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value); \
- link_ptr pos = find_iterator(bucket, k); \
- \
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { \
- return std::pair<iterator_base, bool>( \
- iterator_base(bucket, pos), false); \
- } else { \
- node_constructor a(data_.allocators_); \
- a.construct( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- ); \
- \
- if(reserve_for_insert(size() + 1)) \
- bucket = data_.bucket_ptr_from_hash(hash_value); \
- \
- return std::pair<iterator_base, bool>(iterator_base(bucket, \
- data_.link_node_in_bucket(a, bucket)), true); \
- } \
- } \
- \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
- > \
- std::pair<iterator_base, bool> emplace_impl(no_key, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- node_constructor a(data_.allocators_); \
- a.construct( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- ); \
- return emplace_impl_with_node(a); \
- }
-
- BOOST_UNORDERED_INSERT_IMPL2(1, 1, _)
-
- BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_INSERT_IMPL, _)
-
-#undef BOOST_UNORDERED_INSERT_IMPL
-
-#endif
-
- std::pair<iterator_base, bool> emplace_impl_with_node(node_constructor& a)
- {
- // No side effects in this initial code
- key_type const& k = extract_key(a.get()->value());
- size_type hash_value = hash_function()(k);
- bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
- link_ptr pos = find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Found an existing key, return it (no throw).
- return std::pair<iterator_base, bool>(
- iterator_base(bucket, pos), false);
- } else {
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(reserve_for_insert(size() + 1))
- bucket = data_.bucket_ptr_from_hash(hash_value);
-
- // Nothing after this point can throw.
-
- return std::pair<iterator_base, bool>(iterator_base(bucket,
- data_.link_node_in_bucket(a, bucket)), true);
- }
- }
-
- // Insert from iterators (unique keys)
-
- template <typename I>
- size_type insert_size(I i, I j, boost::forward_traversal_tag)
- {
- return unordered_detail::distance(i, j);
- }
-
- template <typename I>
- size_type insert_size(I, I, boost::incrementable_traversal_tag)
- {
- return 1;
- }
-
- template <typename I>
- size_type insert_size(I i, I j)
- {
- BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
- iterator_traversal_tag;
- return insert_size(i, j, iterator_traversal_tag);
- }
-
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <typename InputIterator>
- void insert_range(InputIterator i, InputIterator j)
- {
- if(i != j)
- return insert_range_impl(extract_key(*i), i, j);
- }
-
- template <typename InputIterator>
- void insert_range_impl(key_type const&, InputIterator i, InputIterator j)
- {
- node_constructor a(data_.allocators_);
-
- for (; i != j; ++i) {
- // No side effects in this initial code
- size_type hash_value = hash_function()(extract_key(*i));
- bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
- link_ptr pos = find_iterator(bucket, extract_key(*i));
-
- if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Doesn't already exist, add to bucket.
- // Side effects only in this block.
-
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- a.construct(*i);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(size() + 1 >= max_load_) {
- reserve_for_insert(size() + insert_size(i, j));
- bucket = data_.bucket_ptr_from_hash(hash_value);
- }
-
- // Nothing after this point can throw.
- data_.link_node_in_bucket(a, bucket);
- }
- }
- }
-
- template <typename InputIterator>
- void insert_range_impl(no_key, InputIterator i, InputIterator j)
- {
- node_constructor a(data_.allocators_);
-
- for (; i != j; ++i) {
- // No side effects in this initial code
- a.construct(*i);
- key_type const& k = extract_key(a.get()->value());
- size_type hash_value = hash_function()(extract_key(k));
- bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
- link_ptr pos = find_iterator(bucket, k);
-
- if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Doesn't already exist, add to bucket.
- // Side effects only in this block.
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(size() + 1 >= max_load_) {
- reserve_for_insert(size() + insert_size(i, j));
- bucket = data_.bucket_ptr_from_hash(hash_value);
- }
-
- // Nothing after this point can throw.
- data_.link_node_in_bucket(a, bucket);
- }
- }
- }
-#endif
- public:
-
- // erase_key
-
- // strong exception safety
- size_type erase_key(key_type const& k)
- {
- // No side effects in initial section
- bucket_ptr bucket = get_bucket(k);
- link_ptr* it = find_for_erase(bucket, k);
-
- // No throw.
- return *it ? data_.erase_group(it, bucket) : 0;
- }
-
- // count
- //
- // strong exception safety, no side effects
- size_type count(key_type const& k) const
- {
- link_ptr it = find_iterator(k); // throws, strong
- return BOOST_UNORDERED_BORLAND_BOOL(it) ? data::group_count(it) : 0;
- }
-
- // find
- //
- // strong exception safety, no side effects
- iterator_base find(key_type const& k) const
- {
- bucket_ptr bucket = get_bucket(k);
- link_ptr it = find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(it))
- return iterator_base(bucket, it);
- else
- return data_.end();
- }
-
- value_type& at(key_type const& k) const
- {
- bucket_ptr bucket = get_bucket(k);
- link_ptr it = find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(it))
- return data::get_value(it);
- else
- throw std::out_of_range("Unable to find key in unordered_map.");
- }
-
- // equal_range
- //
- // strong exception safety, no side effects
- std::pair<iterator_base, iterator_base> equal_range(key_type const& k) const
- {
- bucket_ptr bucket = get_bucket(k);
- link_ptr it = find_iterator(bucket, k);
- if (BOOST_UNORDERED_BORLAND_BOOL(it)) {
- iterator_base first(iterator_base(bucket, it));
- iterator_base second(first);
- second.increment_group();
- return std::pair<iterator_base, iterator_base>(first, second);
- }
- else {
- return std::pair<iterator_base, iterator_base>(
- data_.end(), data_.end());
- }
- }
-
- // strong exception safety, no side effects
- bool equal(key_type const& k, value_type const& v) const
- {
- return key_eq()(k, extract_key(v));
- }
-
- // strong exception safety, no side effects
- link_ptr find_iterator(key_type const& k) const
- {
- return find_iterator(get_bucket(k), k);
- }
-
- // strong exception safety, no side effects
- link_ptr find_iterator(bucket_ptr bucket,
- key_type const& k) const
- {
- link_ptr it = data_.begin(bucket);
- while (BOOST_UNORDERED_BORLAND_BOOL(it) && !equal(k, data::get_value(it))) {
- it = data::next_group(it);
- }
-
- return it;
- }
-
- // strong exception safety, no side effects
- link_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const
- {
- link_ptr* it = &bucket->next_;
- while(BOOST_UNORDERED_BORLAND_BOOL(*it) && !equal(k, data::get_value(*it)))
- it = &data::next_group(*it);
-
- return it;
- }
- };
-
- //
- // Equals - unordered container equality comparison.
- //
-
-#if BOOST_UNORDERED_EQUIVALENT_KEYS
- template <typename A, typename KeyType>
- inline bool group_equals(
- BOOST_UNORDERED_TABLE_DATA<A>*,
- typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
- typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
- KeyType*,
- type_wrapper<KeyType>*)
- {
- typedef BOOST_UNORDERED_TABLE_DATA<A> data;
- return data::group_count(it1) == data::group_count(it2);
- }
-
- template <typename A, typename KeyType>
- inline bool group_equals(
- BOOST_UNORDERED_TABLE_DATA<A>*,
- typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
- typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
- KeyType*,
- void*)
- {
- typedef BOOST_UNORDERED_TABLE_DATA<A> data;
- typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr end1 = data::next_group(it1);
- typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr end2 = data::next_group(it2);
-
- do {
- if(data::get_value(it1).second != data::get_value(it2).second) return false;
- it1 = it1->next_;
- it2 = it2->next_;
- } while(it1 != end1 && it2 != end2);
- return it1 == end1 && it2 == end2;
- }
-#else
- template <typename A, typename KeyType>
- inline bool group_equals(
- BOOST_UNORDERED_TABLE_DATA<A>*,
- typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr,
- typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr,
- KeyType*,
- type_wrapper<KeyType>*)
- {
- return true;
- }
-
- template <typename A, typename KeyType>
- inline bool group_equals(
- BOOST_UNORDERED_TABLE_DATA<A>*,
- typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it1,
- typename BOOST_UNORDERED_TABLE_DATA<A>::link_ptr it2,
- KeyType*,
- void*)
- {
- typedef BOOST_UNORDERED_TABLE_DATA<A> data;
- return data::get_value(it1).second == data::get_value(it2).second;
- }
-#endif
-
- template <typename V, typename K, typename H, typename P, typename A>
- bool equals(BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t1,
- BOOST_UNORDERED_TABLE<V, K, H, P, A> const& t2)
- {
- typedef BOOST_UNORDERED_TABLE_DATA<A> data;
- typedef typename data::bucket_ptr bucket_ptr;
- typedef typename data::link_ptr link_ptr;
-
- if(t1.size() != t2.size()) return false;
-
- for(bucket_ptr i = t1.data_.cached_begin_bucket_,
- j = t1.data_.buckets_end(); i != j; ++i)
- {
- for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
- {
- link_ptr other_pos = t2.find_iterator(t2.extract_key(data::get_value(it)));
- if(!BOOST_UNORDERED_BORLAND_BOOL(other_pos) ||
- !group_equals((data*)0, it, other_pos, (K*)0, (type_wrapper<V>*)0))
- return false;
- }
- }
-
- return true;
- }
-
- // Iterators
-
- template <typename Alloc> class BOOST_UNORDERED_ITERATOR;
- template <typename Alloc> class BOOST_UNORDERED_CONST_ITERATOR;
- template <typename Alloc> class BOOST_UNORDERED_LOCAL_ITERATOR;
- template <typename Alloc> class BOOST_UNORDERED_CONST_LOCAL_ITERATOR;
- class iterator_access;
-
- // Local Iterators
- //
- // all no throw
-
- template <typename Alloc>
- class BOOST_UNORDERED_LOCAL_ITERATOR
- : public boost::iterator <
- std::forward_iterator_tag,
- BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type,
- std::ptrdiff_t,
- BOOST_DEDUCED_TYPENAME allocator_pointer<Alloc>::type,
- BOOST_DEDUCED_TYPENAME allocator_reference<Alloc>::type >
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
-
- private:
- typedef BOOST_UNORDERED_TABLE_DATA<Alloc> data;
- typedef BOOST_DEDUCED_TYPENAME data::link_ptr ptr;
- typedef BOOST_UNORDERED_CONST_LOCAL_ITERATOR<Alloc> const_local_iterator;
-
- friend class BOOST_UNORDERED_CONST_LOCAL_ITERATOR<Alloc>;
- ptr ptr_;
-
- public:
- BOOST_UNORDERED_LOCAL_ITERATOR() : ptr_() {
- BOOST_UNORDERED_MSVC_RESET_PTR(ptr_);
- }
- explicit BOOST_UNORDERED_LOCAL_ITERATOR(ptr x) : ptr_(x) {}
- BOOST_DEDUCED_TYPENAME allocator_reference<Alloc>::type operator*() const
- { return data::get_value(ptr_); }
- value_type* operator->() const { return &data::get_value(ptr_); }
- BOOST_UNORDERED_LOCAL_ITERATOR& operator++() { ptr_ = ptr_->next_; return *this; }
- BOOST_UNORDERED_LOCAL_ITERATOR operator++(int) { BOOST_UNORDERED_LOCAL_ITERATOR tmp(ptr_); ptr_ = ptr_->next_; return tmp; }
- bool operator==(BOOST_UNORDERED_LOCAL_ITERATOR x) const { return ptr_ == x.ptr_; }
- bool operator==(const_local_iterator x) const { return ptr_ == x.ptr_; }
- bool operator!=(BOOST_UNORDERED_LOCAL_ITERATOR x) const { return ptr_ != x.ptr_; }
- bool operator!=(const_local_iterator x) const { return ptr_ != x.ptr_; }
- };
-
- template <typename Alloc>
- class BOOST_UNORDERED_CONST_LOCAL_ITERATOR
- : public boost::iterator <
- std::forward_iterator_tag,
- BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type,
- std::ptrdiff_t,
- BOOST_DEDUCED_TYPENAME allocator_const_pointer<Alloc>::type,
- BOOST_DEDUCED_TYPENAME allocator_const_reference<Alloc>::type >
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
-
- private:
- typedef BOOST_UNORDERED_TABLE_DATA<Alloc> data;
- typedef BOOST_DEDUCED_TYPENAME data::link_ptr ptr;
- typedef BOOST_UNORDERED_LOCAL_ITERATOR<Alloc> local_iterator;
- friend class BOOST_UNORDERED_LOCAL_ITERATOR<Alloc>;
- ptr ptr_;
-
- public:
- BOOST_UNORDERED_CONST_LOCAL_ITERATOR() : ptr_() {
- BOOST_UNORDERED_MSVC_RESET_PTR(ptr_);
- }
- explicit BOOST_UNORDERED_CONST_LOCAL_ITERATOR(ptr x) : ptr_(x) {}
- BOOST_UNORDERED_CONST_LOCAL_ITERATOR(local_iterator x) : ptr_(x.ptr_) {}
- BOOST_DEDUCED_TYPENAME allocator_const_reference<Alloc>::type
- operator*() const { return data::get_value(ptr_); }
- value_type const* operator->() const { return &data::get_value(ptr_); }
- BOOST_UNORDERED_CONST_LOCAL_ITERATOR& operator++() { ptr_ = ptr_->next_; return *this; }
- BOOST_UNORDERED_CONST_LOCAL_ITERATOR operator++(int) { BOOST_UNORDERED_CONST_LOCAL_ITERATOR tmp(ptr_); ptr_ = ptr_->next_; return tmp; }
- bool operator==(local_iterator x) const { return ptr_ == x.ptr_; }
- bool operator==(BOOST_UNORDERED_CONST_LOCAL_ITERATOR x) const { return ptr_ == x.ptr_; }
- bool operator!=(local_iterator x) const { return ptr_ != x.ptr_; }
- bool operator!=(BOOST_UNORDERED_CONST_LOCAL_ITERATOR x) const { return ptr_ != x.ptr_; }
- };
-
- // iterators
- //
- // all no throw
-
-
- template <typename Alloc>
- class BOOST_UNORDERED_ITERATOR
- : public boost::iterator <
- std::forward_iterator_tag,
- BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type,
- std::ptrdiff_t,
- BOOST_DEDUCED_TYPENAME allocator_pointer<Alloc>::type,
- BOOST_DEDUCED_TYPENAME allocator_reference<Alloc>::type >
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
-
- private:
- typedef BOOST_DEDUCED_TYPENAME BOOST_UNORDERED_TABLE_DATA<Alloc>::iterator_base base;
- typedef BOOST_UNORDERED_CONST_ITERATOR<Alloc> const_iterator;
- friend class BOOST_UNORDERED_CONST_ITERATOR<Alloc>;
- base base_;
-
- public:
-
- BOOST_UNORDERED_ITERATOR() : base_() {}
- explicit BOOST_UNORDERED_ITERATOR(base const& x) : base_(x) {}
- BOOST_DEDUCED_TYPENAME allocator_reference<Alloc>::type
- operator*() const { return *base_; }
- value_type* operator->() const { return &*base_; }
- BOOST_UNORDERED_ITERATOR& operator++() { base_.increment(); return *this; }
- BOOST_UNORDERED_ITERATOR operator++(int) { BOOST_UNORDERED_ITERATOR tmp(base_); base_.increment(); return tmp; }
- bool operator==(BOOST_UNORDERED_ITERATOR const& x) const { return base_ == x.base_; }
- bool operator==(const_iterator const& x) const { return base_ == x.base_; }
- bool operator!=(BOOST_UNORDERED_ITERATOR const& x) const { return base_ != x.base_; }
- bool operator!=(const_iterator const& x) const { return base_ != x.base_; }
- };
-
- template <typename Alloc>
- class BOOST_UNORDERED_CONST_ITERATOR
- : public boost::iterator <
- std::forward_iterator_tag,
- BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type,
- std::ptrdiff_t,
- BOOST_DEDUCED_TYPENAME allocator_const_pointer<Alloc>::type,
- BOOST_DEDUCED_TYPENAME allocator_const_reference<Alloc>::type >
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME allocator_value_type<Alloc>::type value_type;
-
- private:
- typedef BOOST_DEDUCED_TYPENAME BOOST_UNORDERED_TABLE_DATA<Alloc>::iterator_base base;
- typedef BOOST_UNORDERED_ITERATOR<Alloc> iterator;
- friend class BOOST_UNORDERED_ITERATOR<Alloc>;
- friend class iterator_access;
- base base_;
-
- public:
-
- BOOST_UNORDERED_CONST_ITERATOR() : base_() {}
- explicit BOOST_UNORDERED_CONST_ITERATOR(base const& x) : base_(x) {}
- BOOST_UNORDERED_CONST_ITERATOR(iterator const& x) : base_(x.base_) {}
- BOOST_DEDUCED_TYPENAME allocator_const_reference<Alloc>::type
- operator*() const { return *base_; }
- value_type const* operator->() const { return &*base_; }
- BOOST_UNORDERED_CONST_ITERATOR& operator++() { base_.increment(); return *this; }
- BOOST_UNORDERED_CONST_ITERATOR operator++(int) { BOOST_UNORDERED_CONST_ITERATOR tmp(base_); base_.increment(); return tmp; }
- bool operator==(iterator const& x) const { return base_ == x.base_; }
- bool operator==(BOOST_UNORDERED_CONST_ITERATOR const& x) const { return base_ == x.base_; }
- bool operator!=(iterator const& x) const { return base_ != x.base_; }
- bool operator!=(BOOST_UNORDERED_CONST_ITERATOR const& x) const { return base_ != x.base_; }
- };
- }
-}
-
-#undef BOOST_UNORDERED_TABLE
-#undef BOOST_UNORDERED_TABLE_DATA
-#undef BOOST_UNORDERED_ITERATOR
-#undef BOOST_UNORDERED_CONST_ITERATOR
-#undef BOOST_UNORDERED_LOCAL_ITERATOR
-#undef BOOST_UNORDERED_CONST_LOCAL_ITERATOR
Modified: branches/release/boost/unordered/detail/move.hpp
==============================================================================
--- branches/release/boost/unordered/detail/move.hpp (original)
+++ branches/release/boost/unordered/detail/move.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -11,7 +11,7 @@
#ifndef BOOST_UNORDERED_DETAIL_MOVE_HEADER
#define BOOST_UNORDERED_DETAIL_MOVE_HEADER
-
+#include <boost/config.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/or.hpp>
@@ -20,7 +20,20 @@
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/is_class.hpp>
#include <boost/utility/enable_if.hpp>
-#include <boost/unordered/detail/config.hpp>
+#include <boost/detail/workaround.hpp>
+
+/*************************************************************************************************/
+
+#if defined(BOOST_NO_SFINAE)
+# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN
+#elif defined(__GNUC__) && \
+ (__GNUC__ < 3 || __GNUC__ == 3 && __GNUC_MINOR__ <= 3)
+# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN
+#elif BOOST_WORKAROUND(BOOST_INTEL, < 900) || \
+ BOOST_WORKAROUND(__EDG_VERSION__, < 304) || \
+ BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x0593))
+# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN
+#endif
/*************************************************************************************************/
@@ -96,6 +109,8 @@
{
explicit move_from(T& x) : source(x) { }
T& source;
+private:
+ move_from& operator=(move_from const&);
};
/*************************************************************************************************/
Copied: branches/release/boost/unordered/detail/node.hpp (from r55902, /trunk/boost/unordered/detail/node.hpp)
==============================================================================
--- /trunk/boost/unordered/detail/node.hpp (original)
+++ branches/release/boost/unordered/detail/node.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -24,23 +24,6 @@
namespace boost { namespace unordered_detail {
- template <class BucketPtr>
- static inline BucketPtr& next_node(BucketPtr ptr)
- {
- return ptr->next_;
- }
-
- template <class BucketPtr>
- static 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,65 +43,58 @@
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>
- void ungrouped_node_base<A>::unlink_node(bucket& b, node_ptr node)
- {
- unlink_nodes(b, node, next_node(node));
- }
-
- template <class A>
- 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;
}
template <class A>
- void ungrouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end)
+ inline void ungrouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end)
{
b.next_ = end;
}
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 n)
{
- *b = next_node(*b);
+ unlink_nodes(b, n, n->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;
- b.next_ = n;
- }
-
- template <class A>
- inline void grouped_node_base<A>::add_group_to_bucket(node_ptr n, bucket& b)
- {
- next_group(n) = b.next_;
+ n->next_ = b.next_;
+ get(n).group_prev_ = n;
b.next_ = n;
}
template <class A>
- inline void grouped_node_base<A>::add_after_node(node_ptr n, node_ptr position)
+ inline void grouped_node_base<A>::add_after_node(node_ptr n, node_ptr pos)
{
- 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,63 +133,61 @@
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)
+ void grouped_node_base<A>::unlink_node(bucket& b, node_ptr n)
{
- node_ptr next = next_node(node);
- node_ptr* pos = &next_node(group_prev(node));
+ node_ptr next = n->next_;
+ node_ptr* pos = &next_group(n);
- if(*pos != node) {
+ if(*pos != n) {
// The node is at the beginning of a group.
// Find the previous node pointer:
pos = &b.next_;
- while(*pos != node) pos = &next_group(*pos);
+ while(*pos != n) 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_ == n)
+ {
+ get(next).group_prev_ = get(n).group_prev_;
+ }
}
- else if(BOOST_UNORDERED_BORLAND_BOOL(next) && group_prev(next) == node) {
+ else if(BOOST_UNORDERED_BORLAND_BOOL(next) &&
+ get(next).group_prev_ == n)
+ {
// 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(n).group_prev_;
}
else {
// The deleted node is at the end of the group, so the
// first node in the group is pointing to it.
// Find that to change its pointer.
- node_ptr x = group_prev(node);
- while(group_prev(x) != node) {
- x = group_prev(x);
+ node_ptr x = get(n).group_prev_;
+ while(get(x).group_prev_ != n) {
+ x = get(x).group_prev_;
}
- group_prev(x) = group_prev(node);
+ get(x).group_prev_ = get(n).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
Copied: branches/release/boost/unordered/detail/table.hpp (from r55902, /trunk/boost/unordered/detail/table.hpp)
==============================================================================
--- /trunk/boost/unordered/detail/table.hpp (original)
+++ branches/release/boost/unordered/detail/table.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -13,7 +13,7 @@
#include <boost/config/no_tr1/cmath.hpp>
#include <boost/iterator/iterator_categories.hpp>
-#include <boost/unordered/detail/manager.hpp>
+#include <boost/unordered/detail/buckets.hpp>
#include <boost/unordered/detail/util.hpp>
namespace boost { namespace unordered_detail {
@@ -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 size) const
{
BOOST_ASSERT(this->mlf_ != 0);
@@ -114,111 +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(size / (double) mlf_)) + 1);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // recompute_begin_bucket
+
+ // init_buckets
+
+ template <class H, class P, class A, class G, class K>
+ inline void hash_table<H, P, A, G, K>::init_buckets()
+ {
+ 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();
}
+ // 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>
- void hash_table<H, P, A, G, K>
- ::calculate_max_load()
+ inline void hash_table<H, P, A, G, K>::recompute_begin_bucket(bucket_ptr b)
{
- using namespace std;
+ BOOST_ASSERT(!(b < this->cached_begin_bucket_));
- // From 6.3.1/13:
- // Only resize when size >= mlf_ * count
- max_load_ = double_to_size_t(ceil((double) mlf_ * this->bucket_count()));
+ 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_);
+ }
+ }
}
- ////////////////////////////////////////////////////////////////////////////
- // Constructors
+ // 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(std::size_t n, hasher const& hf, key_equal const& eq, value_allocator const& a) :
- manager(a), func_(false), mlf_(1.0f), max_load_(0)
- {
- std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
- functions(hf, eq));
- this->create_buckets(next_prime(n));
- this->calculate_max_load();
+ 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_));
+
+ 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 const& x) :
- manager(x), func_(false), mlf_(x.mlf_), max_load_(0)
- {
- std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
- x.current());
- this->create_buckets(next_prime(x.min_buckets_for_size(x.size_)));
- this->calculate_max_load();
- x.copy_buckets_to(*this);
+ 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_);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Constructors
+
+ template <class H, class P, class A, class G, class K>
+ hash_table<H, P, A, G, K>::hash_table(std::size_t num_buckets,
+ hasher const& hf, key_equal const& eq, node_allocator const& a)
+ : buckets(a, next_prime(num_buckets)),
+ base(hf, eq),
+ size_(),
+ mlf_(1.0f),
+ cached_begin_bucket_(),
+ max_load_(0)
+ {
}
// Copy Construct with allocator
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) :
- manager(a), func_(false), mlf_(x.mlf_), max_load_(0)
- {
- std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
- x.current());
- this->create_buckets(next_prime(x.min_buckets_for_size(x.size_)));
- this->calculate_max_load();
- x.copy_buckets_to(*this);
+ 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(hash_table& x, move_tag m) :
- manager(x, m), func_(false), mlf_(x.mlf_), max_load_(0)
- {
- // TODO: Shouldn't I move the functions if poss.
- std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
- x.current());
+ 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);
}
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) :
- manager(x, a, m), func_(false), mlf_(x.mlf_), max_load_(0)
+ 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)
{
- std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
- x.current());
-
- this->calculate_max_load(); // no throw
-
- if(!this->buckets_) {
- this->create_buckets(next_prime(x.min_buckets_for_size(x.size_)));
- // This can throw, but hash_table_manager's destructor will clean
- // up.
+ if(a == x.node_alloc()) {
+ this->partial_swap(x);
+ }
+ else if(x.size_) {
x.copy_buckets_to(*this);
+ this->size_ = x.size_;
+ this->init_buckets();
}
}
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);
- }
-
- 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<H, P, A, G, K>::operator=(
+ hash_table const& x)
{
- if(this != &x) {
- this->clear(); // no throw
- this->set_functions(
- this->buffer_functions(x)); // throws, strong
- this->mlf_ = x.mlf_; // no throw
- this->calculate_max_load(); // no throw
- this->reserve(x.size_); // throws
- x.copy_buckets_to(*this); // throws
- }
-
+ hash_table tmp(x, this->node_alloc());
+ this->fast_swap(tmp);
return *this;
}
@@ -233,55 +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->manager::swap(x); // No throw
+ {
+ set_hash_functions<H, P> op1(*this, x);
+ set_hash_functions<H, P> op2(x, *this);
+ op1.commit();
+ op2.commit();
}
- else {
- // Create new buckets in separate hash_table_manager objects
- // which will clean up if anything throws an exception.
- // (all can throw, but with no effect as these are new objects).
+ 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_);
+ }
- manager new_this(*this);
- new_this.create_buckets(x.min_buckets_for_size(x.size_));
- x.copy_buckets_to(new_this);
-
- manager new_that(x);
- new_that.create_buckets(this->min_buckets_for_size(this->size_));
- copy_buckets_to(new_that);
+ 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 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->manager::swap(new_this);
- x.manager::swap(new_that);
+
+ 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
//
@@ -291,35 +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->manager::move(x); // no throw
+ 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;
}
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).
- manager new_this(*this);
- new_this.create_buckets(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->manager::move(new_this);
+ this->size_ = x.size_;
+ 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();
}
////////////////////////////////////////////////////////////////////////////
@@ -327,48 +404,52 @@
// basic exception safety
template <class H, class P, class A, class G, class K>
- 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 size)
{
- 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;
+ this->bucket_count_ = (std::max)(this->bucket_count_,
+ this->min_buckets_for_size(size));
+ this->create_buckets();
+ this->init_buckets();
}
// basic exception safety
template <class H, class P, class A, class G, class K>
- 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 size)
{
- bool need_to_reserve = n >= this->max_load_;
- // throws - basic:
- if (need_to_reserve) {
- std::size_t s = this->size_;
- s = s + (s >> 1);
- s = s > n ? s : n;
- rehash_impl(this->min_buckets_for_size(s));
+ if(size >= max_load_) {
+ std::size_t num_buckets
+ = this->min_buckets_for_size((std::max)(size,
+ this->size_ + (this->size_ >> 1)));
+ if(num_buckets != this->bucket_count_) {
+ rehash_impl(num_buckets);
+ 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>
- ::rehash(std::size_t n)
+ inline void hash_table<H, P, A, G, K>::rehash(std::size_t min_buckets)
{
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);
-
- BOOST_ASSERT((float) this->bucket_count() > (float) this->size_ / this->mlf_
- && this->bucket_count() >= n);
+ if(!this->buckets_) {
+ this->bucket_count_ = next_prime(min_buckets);
+ this->create_buckets();
+ this->init_buckets();
+ }
+ else {
+ // no throw:
+ // TODO: Needlessly calling next_prime twice.
+ min_buckets = (std::max)(
+ next_prime(min_buckets),
+ this->min_buckets_for_size(this->size_));
+ if(min_buckets != this->bucket_count_) rehash_impl(min_buckets);
+ }
}
// if hash function throws, basic exception safety
@@ -376,55 +457,48 @@
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;
-
- manager new_buckets(*this); // throws, seperate
- new_buckets.create_buckets(n); // throws, seperate
- move_buckets_to(new_buckets); // basic/no throw
- new_buckets.swap(*this); // no throw
- this->calculate_max_load(); // no throw
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // move_buckets_to & copy_buckets_to
-
- // move_buckets_to
- //
- // if the hash function throws, basic excpetion safety
- // no throw otherwise
-
- template <class H, class P, class A, class G, class K>
- void hash_table<H, P, A, G, K>
- ::move_buckets_to(manager& dst)
- {
- BOOST_ASSERT(this->node_alloc() == dst.node_alloc());
- BOOST_ASSERT(this->buckets_ && dst.buckets_);
-
+ ::rehash_impl(std::size_t num_buckets)
+ {
hasher const& hf = this->hash_function();
- bucket_ptr end = this->buckets_end();
+ std::size_t size = this->size_;
+ bucket_ptr end = this->get_bucket(this->bucket_count_);
+
+ buckets dst(this->node_alloc(), num_buckets);
+ dst.create_buckets();
- 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.
+ buckets src(this->node_alloc(), this->bucket_count_);
+ src.swap(*this);
+ this->size_ = 0;
+
+ 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_;
- std::size_t count = this->unlink_group(&src_bucket->next_);
- dst.link_group(n, dst_bucket, count);
+ 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.
+ this->size_ = size;
+ dst.swap(*this); // no throw
+ this->init_buckets();
}
+ ////////////////////////////////////////////////////////////////////////////
+ // copy_buckets_to
+
// copy_buckets_to
//
// basic excpetion safety. If an exception is thrown this will
@@ -432,14 +506,15 @@
template <class H, class P, class A, class G, class K>
void hash_table<H, P, A, G, K>
- ::copy_buckets_to(manager& dst) const
+ ::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) {
@@ -447,18 +522,18 @@
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);
a.construct(node::get_value(it));
node_ptr n = a.release();
- dst.link_node_in_bucket(n, dst_bucket);
+ 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));
- dst.link_node(a.release(), n);
+ node::add_after_node(a.release(), n);
}
}
}
@@ -469,25 +544,12 @@
// strong exception safety
- 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)
- {
- // No side effects in initial section
- bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
- node_ptr* it = find_for_erase(bucket, k);
-
- // No throw.
- return *it ? this->erase_group(it, bucket) : 0;
- }
-
// count
//
// 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
@@ -499,8 +561,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();
@@ -515,8 +576,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.");
@@ -534,27 +594,146 @@
//
// 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());
+ }
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Erase methods
+
+ template <class H, class P, class A, class G, class K>
+ void hash_table<H, P, A, G, K>::clear()
+ {
+ // 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->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);
+
+ // No throw.
+ return *it ? this->erase_group(it, bucket) : 0;
+ }
+
+
+ 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(iterator_base r)
+ {
+ BOOST_ASSERT(r.node_);
+ iterator_base next = r;
+ next.increment();
+ --this->size_;
+ node::unlink_node(*r.bucket_, 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>
+ 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)
+ {
+ if(r1 != r2)
+ {
+ BOOST_ASSERT(r1.node_);
+ if (r1.bucket_ == r2.bucket_) {
+ node::unlink_nodes(*r1.bucket_, 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_);
+ }
+ else {
+ 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->size_ -= this->delete_nodes(r1.node_, node_ptr());
+
+ bucket_ptr i = r1.bucket_;
+ for(++i; i != end_bucket; ++i) {
+ this->size_ -= this->delete_nodes(i->next_, node_ptr());
+ i->next_ = node_ptr();
+ }
+
+ if(r2.node_) {
+ node_ptr first = r2.bucket_->next_;
+ node::unlink_nodes(*r2.bucket_, 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_, end_bucket);
+ }
}
+
+ return r2;
+ }
+
+ 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>::emplace_empty_impl_with_node(
+ node_constructor& a, std::size_t size)
+ {
+ key_type const& k = get_key(a.value());
+ std::size_t hash_value = this->hash_function()(k);
+ if(this->buckets_) this->reserve_for_insert(size);
+ else this->create_for_insert(size);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_ptr n = a.release();
+ node::add_to_bucket(n, *bucket);
+ ++this->size_;
+ this->cached_begin_bucket_ = bucket;
+ return iterator_base(bucket, n);
}
}}
Copied: branches/release/boost/unordered/detail/unique.hpp (from r56329, /trunk/boost/unordered/detail/unique.hpp)
==============================================================================
--- /trunk/boost/unordered/detail/unique.hpp (original)
+++ branches/release/boost/unordered/detail/unique.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -191,56 +191,58 @@
#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); \
+#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
+ template <class H, class P, class A, class K> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
+ 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, num_params)) \
+ { \
+ 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, num_params)); \
+ \
+ 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, num_params)> \
+ 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, num_params)) \
+ { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ return emplace_impl_with_node(a); \
+ } \
+ \
+ template <class H, class P, class A, class K> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
+ 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, num_params)) \
+ { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ return emplace_return(this->emplace_empty_impl_with_node(a, 1), true); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -270,25 +272,6 @@
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>
@@ -301,45 +284,20 @@
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, num_params, _) \
+ template <class H, class P, class A, class K> \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
+ 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, num_params)) \
+ { \
+ return this->size_ ? \
+ emplace_impl(extractor::extract(arg0, arg1), \
+ BOOST_UNORDERED_CALL_PARAMS(z, num_params)) : \
+ emplace_empty_impl( \
+ BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
}
-#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, _)
Copied: branches/release/boost/unordered/detail/util.hpp (from r55902, /trunk/boost/unordered/detail/util.hpp)
==============================================================================
--- /trunk/boost/unordered/detail/util.hpp (original)
+++ branches/release/boost/unordered/detail/util.hpp 2009-09-24 17:12:46 EDT (Thu, 24 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/manager.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);
}
@@ -75,24 +61,24 @@
typedef prime_list_template<std::size_t> prime_list;
// no throw
- inline std::size_t next_prime(std::size_t n) {
+ inline std::size_t next_prime(std::size_t num) {
std::size_t const* const prime_list_begin = prime_list::value;
std::size_t const* const prime_list_end = prime_list_begin +
prime_list::length;
std::size_t const* bound =
- std::lower_bound(prime_list_begin, prime_list_end, n);
+ std::lower_bound(prime_list_begin, prime_list_end, num);
if(bound == prime_list_end)
bound--;
return *bound;
}
// no throw
- inline std::size_t prev_prime(std::size_t n) {
+ inline std::size_t prev_prime(std::size_t num) {
std::size_t const* const prime_list_begin = prime_list::value;
std::size_t const* const prime_list_end = prime_list_begin +
prime_list::length;
std::size_t const* bound =
- std::upper_bound(prime_list_begin,prime_list_end, n);
+ std::upper_bound(prime_list_begin,prime_list_end, num);
if(bound != prime_list_begin)
bound--;
return *bound;
@@ -143,9 +129,10 @@
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 num_buckets = boost::unordered_detail::default_bucket_count)
{
- return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1, n);
+ return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1,
+ num_buckets);
}
////////////////////////////////////////////////////////////////////////////
@@ -172,29 +159,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, num_params, _) \
+ template < \
+ class T, \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
+ > \
+ inline void construct_impl( \
+ T*, void* address, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
+ ) \
+ { \
+ new(address) T( \
+ BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ } \
+ \
+ template <class First, class Second, class Key, \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
+ > \
+ inline void construct_impl( \
+ std::pair<First, Second>*, void* address, \
+ Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
+ { \
+ new(address) std::pair<First, Second>(k, \
+ Second(BOOST_UNORDERED_CALL_PARAMS(z, num_params))); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -210,20 +197,20 @@
template <class Alloc, class Grouped>
class hash_node_constructor
{
- typedef hash_table_manager<Alloc, Grouped> manager;
- typedef BOOST_DEDUCED_TYPENAME manager::node node;
- typedef BOOST_DEDUCED_TYPENAME manager::real_node_ptr real_node_ptr;
- typedef BOOST_DEDUCED_TYPENAME manager::value_type value_type;
+ typedef hash_buckets<Alloc, Grouped> buckets;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+ typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type;
- manager& manager_;
+ buckets& buckets_;
real_node_ptr node_;
bool node_constructed_;
bool value_constructed_;
public:
- hash_node_constructor(manager& m) :
- manager_(m),
+ hash_node_constructor(buckets& m) :
+ buckets_(m),
node_(),
node_constructed_(false),
value_constructed_(false)
@@ -244,20 +231,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, num_params, _) \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
+ > \
+ void construct( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
+ ) \
+ { \
+ construct_preamble(); \
+ construct_impl( \
+ (value_type*) 0, node_->address(), \
+ BOOST_UNORDERED_CALL_PARAMS(z, num_params) \
+ ); \
+ value_constructed_ = true; \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -274,19 +261,19 @@
value_constructed_ = true;
}
- real_node_ptr get() const
+ value_type& value() const
{
BOOST_ASSERT(node_);
- return node_;
+ return node_->value();
}
// no throw
- BOOST_DEDUCED_TYPENAME manager::node_ptr release()
+ BOOST_DEDUCED_TYPENAME buckets::node_ptr release()
{
real_node_ptr p = node_;
node_ = real_node_ptr();
// node_ptr cast
- return manager_.bucket_alloc().address(*p);
+ return buckets_.bucket_alloc().address(*p);
}
private:
@@ -297,34 +284,34 @@
// 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_)
- manager_.node_alloc().destroy(node_);
+ buckets_.node_alloc().destroy(node_);
- manager_.node_alloc().deallocate(node_, 1);
+ buckets_.node_alloc().deallocate(node_, 1);
}
}
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;
value_constructed_ = false;
- node_ = manager_.node_alloc().allocate(1);
- manager_.node_alloc().construct(node_, node());
+ node_ = buckets_.node_alloc().allocate(1);
+ buckets_.node_alloc().construct(node_, node());
node_constructed_ = true;
}
else {
BOOST_ASSERT(node_constructed_ && value_constructed_);
- BOOST_UNORDERED_DESTRUCT(&node_->value(), value_type);
+ boost::unordered_detail::destroy(&node_->value());
value_constructed_ = false;
}
}
Modified: branches/release/boost/unordered/unordered_map.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_map.hpp (original)
+++ branches/release/boost/unordered/unordered_map.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -15,7 +15,9 @@
#include <boost/unordered/unordered_map_fwd.hpp>
#include <boost/functional/hash.hpp>
-#include <boost/unordered/detail/hash_table.hpp>
+#include <boost/unordered/detail/allocator_helpers.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>
@@ -39,115 +41,151 @@
template <class Key, class T, class Hash, class Pred, class Alloc>
class unordered_map
{
-#if BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
public:
+ typedef Key key_type;
+ typedef std::pair<const Key, T> value_type;
+ typedef T mapped_type;
+ typedef Hash hasher;
+ typedef Pred key_equal;
+ typedef Alloc allocator_type;
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
#endif
- typedef boost::unordered_detail::hash_types_unique_keys<
- std::pair<const Key, T>, Key, Hash, Pred, Alloc
- > implementation;
- BOOST_DEDUCED_TYPENAME implementation::hash_table base;
+ typedef BOOST_DEDUCED_TYPENAME
+ 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_DEDUCED_TYPENAME table::iterator_base iterator_base;
public:
- // types
+ 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;
+ typedef boost::unordered_detail::hash_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;
+ typedef boost::unordered_detail::hash_iterator<
+ value_allocator, boost::unordered_detail::ungrouped>
+ iterator;
- typedef Key key_type;
- typedef std::pair<const Key, T> value_type;
- typedef T mapped_type;
- typedef Hash hasher;
- typedef Pred key_equal;
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
+#endif
- typedef Alloc allocator_type;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::pointer pointer;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::const_pointer const_pointer;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::reference reference;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::const_reference const_reference;
-
- typedef BOOST_DEDUCED_TYPENAME implementation::size_type size_type;
- typedef BOOST_DEDUCED_TYPENAME implementation::difference_type difference_type;
-
- typedef BOOST_DEDUCED_TYPENAME implementation::iterator iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::const_iterator const_iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::local_iterator local_iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::const_local_iterator const_local_iterator;
+ table table_;
+
+ BOOST_DEDUCED_TYPENAME table::iterator_base const&
+ get(const_iterator const& it)
+ {
+ return boost::unordered_detail::iterator_access::get(it);
+ }
+
+ public:
// 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())
- : base(n, hf, eql, a)
+ : table_(n, hf, eql, a)
{
}
explicit unordered_map(allocator_type const& a)
- : base(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)
- : base(other.base, a)
+ : table_(other.table_, a)
{
}
- template <class InputIterator>
- unordered_map(InputIterator f, InputIterator l)
- : base(f, l, boost::unordered_detail::default_initial_bucket_count,
+ 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())
- : base(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)
- : base(f, l, n, hf, eql, a)
+ : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a)
{
+ table_.insert_range(f, l);
}
~unordered_map() {}
#if defined(BOOST_HAS_RVALUE_REFS)
unordered_map(unordered_map&& other)
- : base(other.base, boost::unordered_detail::move_tag())
+ : table_(other.table_, boost::unordered_detail::move_tag())
{
}
unordered_map(unordered_map&& other, allocator_type const& a)
- : base(other.base, a, boost::unordered_detail::move_tag())
+ : table_(other.table_, a, boost::unordered_detail::move_tag())
{
}
unordered_map& operator=(unordered_map&& x)
{
- base.move(x.base);
+ table_.move(x.table_);
return *this;
}
#else
- unordered_map(boost::unordered_detail::move_from<unordered_map<Key, T, Hash, Pred, Alloc> > other)
- : base(other.source.base, 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())
{
}
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
unordered_map& operator=(unordered_map x)
{
- base.move(x.base);
+ table_.move(x.table_);
return *this;
}
#endif
@@ -155,84 +193,77 @@
#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())
- : base(list.begin(), list.end(), n, hf, eql, a)
+ : table_(boost::unordered_detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, allocator_type())
{
+ table_.insert_range(list.begin(), list.end());
}
unordered_map& operator=(std::initializer_list<value_type> list)
{
- base.data_.clear();
- base.insert_range(list.begin(), list.end());
+ table_.clear();
+ table_.insert_range(list.begin(), list.end());
return *this;
}
#endif
- private:
-
- BOOST_DEDUCED_TYPENAME implementation::iterator_base const&
- get(const_iterator const& it)
- {
- return boost::unordered_detail::iterator_access::get(it);
- }
-
- public:
-
allocator_type get_allocator() const
{
- return base.get_allocator();
+ return table_.node_alloc();
}
// size and capacity
bool empty() const
{
- return base.empty();
+ return table_.size_ == 0;
}
size_type size() const
{
- return base.size();
+ return table_.size_;
}
size_type max_size() const
{
- return base.max_size();
+ return table_.max_size();
}
// iterators
iterator begin()
{
- return iterator(base.data_.begin());
+ return iterator(table_.begin());
}
const_iterator begin() const
{
- return const_iterator(base.data_.begin());
+ return const_iterator(table_.begin());
}
iterator end()
{
- return iterator(base.data_.end());
+ return iterator(table_.end());
}
const_iterator end() const
{
- return const_iterator(base.data_.end());
+ return const_iterator(table_.end());
}
const_iterator cbegin() const
{
- return const_iterator(base.data_.begin());
+ return const_iterator(table_.begin());
}
const_iterator cend() const
{
- return const_iterator(base.data_.end());
+ return const_iterator(table_.end());
}
// modifiers
@@ -242,51 +273,50 @@
std::pair<iterator, bool> emplace(Args&&... args)
{
return boost::unordered_detail::pair_cast<iterator, bool>(
- base.emplace(std::forward<Args>(args)...));
+ table_.emplace(std::forward<Args>(args)...));
}
template <class... Args>
- iterator emplace_hint(const_iterator hint, Args&&... args)
+ iterator emplace_hint(const_iterator, Args&&... args)
{
- return iterator(base.emplace_hint(get(hint), std::forward<Args>(args)...));
+ return iterator(table_.emplace(std::forward<Args>(args)...).first);
}
#else
std::pair<iterator, bool> emplace(value_type const& v = value_type())
{
return boost::unordered_detail::pair_cast<iterator, bool>(
- base.emplace(v));
+ table_.emplace(v));
}
- iterator emplace_hint(const_iterator hint, value_type const& v = value_type())
+ iterator emplace_hint(const_iterator, value_type const& v = value_type())
{
- return iterator(base.emplace_hint(get(hint), v));
+ return iterator(table_.emplace(v).first);
}
-#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>( \
- base.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(base.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( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)).first); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -299,183 +329,184 @@
std::pair<iterator, bool> insert(const value_type& obj)
{
return boost::unordered_detail::pair_cast<iterator, bool>(
- base.emplace(obj));
+ table_.emplace(obj));
}
iterator insert(const_iterator hint, const value_type& obj)
{
- return iterator(base.emplace_hint(get(hint), obj));
+ return iterator(table_.emplace(obj).first);
}
- template <class InputIterator>
- void insert(InputIterator first, InputIterator last)
+ template <class InputIt>
+ void insert(InputIt first, InputIt last)
{
- base.insert_range(first, last);
+ table_.insert_range(first, last);
}
iterator erase(const_iterator position)
{
- return iterator(base.data_.erase(get(position)));
+ return iterator(table_.erase(get(position)));
}
size_type erase(const key_type& k)
{
- return base.erase_key(k);
+ return table_.erase_key(k);
}
iterator erase(const_iterator first, const_iterator last)
{
- return iterator(base.data_.erase_range(get(first), get(last)));
+ return iterator(table_.erase_range(get(first), get(last)));
}
void clear()
{
- base.data_.clear();
+ table_.clear();
}
void swap(unordered_map& other)
{
- base.swap(other.base);
+ table_.swap(other.table_);
}
// observers
hasher hash_function() const
{
- return base.hash_function();
+ return table_.hash_function();
}
key_equal key_eq() const
{
- return base.key_eq();
+ return table_.key_eq();
}
mapped_type& operator[](const key_type &k)
{
- return base[k].second;
+ return table_[k].second;
}
mapped_type& at(const key_type& k)
{
- return base.at(k).second;
+ return table_.at(k).second;
}
mapped_type const& at(const key_type& k) const
{
- return base.at(k).second;
+ return table_.at(k).second;
}
// lookup
iterator find(const key_type& k)
{
- return iterator(base.find(k));
+ return iterator(table_.find(k));
}
const_iterator find(const key_type& k) const
{
- return const_iterator(base.find(k));
+ return const_iterator(table_.find(k));
}
size_type count(const key_type& k) const
{
- return base.count(k);
+ return table_.count(k);
}
std::pair<iterator, iterator>
equal_range(const key_type& k)
{
- return boost::unordered_detail::pair_cast<iterator, iterator>(
- base.equal_range(k));
+ 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>(
- base.equal_range(k));
+ return boost::unordered_detail::pair_cast<
+ const_iterator, const_iterator>(
+ table_.equal_range(k));
}
// bucket interface
size_type bucket_count() const
{
- return base.bucket_count();
+ return table_.bucket_count_;
}
size_type max_bucket_count() const
{
- return base.max_bucket_count();
+ return table_.max_bucket_count();
}
size_type bucket_size(size_type n) const
{
- return base.data_.bucket_size(n);
+ return table_.bucket_size(n);
}
size_type bucket(const key_type& k) const
{
- return base.bucket(k);
+ return table_.bucket_index(k);
}
local_iterator begin(size_type n)
{
- return local_iterator(base.data_.begin(n));
+ return local_iterator(table_.bucket_begin(n));
}
const_local_iterator begin(size_type n) const
{
- return const_local_iterator(base.data_.begin(n));
+ return const_local_iterator(table_.bucket_begin(n));
}
- local_iterator end(size_type n)
+ local_iterator end(size_type)
{
- return local_iterator(base.data_.end(n));
+ return local_iterator();
}
- const_local_iterator end(size_type n) const
+ const_local_iterator end(size_type) const
{
- return const_local_iterator(base.data_.end(n));
+ return const_local_iterator();
}
const_local_iterator cbegin(size_type n) const
{
- return const_local_iterator(base.data_.begin(n));
+ 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(base.data_.end(n));
+ return const_local_iterator();
}
// hash policy
float load_factor() const
{
- return base.load_factor();
+ return table_.load_factor();
}
float max_load_factor() const
{
- return base.max_load_factor();
+ return table_.mlf_;
}
void max_load_factor(float m)
{
- base.max_load_factor(m);
+ table_.max_load_factor(m);
}
void rehash(size_type n)
{
- base.rehash(n);
+ table_.rehash(n);
}
-#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
- friend bool operator==(unordered_map const&, unordered_map const&);
- friend bool operator!=(unordered_map const&, unordered_map const&);
-#elif !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&);
+#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&);
#endif
}; // class template unordered_map
@@ -483,14 +514,14 @@
inline bool operator==(unordered_map<K, T, H, P, A> const& m1,
unordered_map<K, T, H, P, A> const& m2)
{
- return boost::unordered_detail::equals(m1.base, m2.base);
+ return m1.table_.equals(m2.table_);
}
template <class K, class T, class H, class P, class A>
inline bool operator!=(unordered_map<K, T, H, P, A> const& m1,
unordered_map<K, T, H, P, A> const& m2)
{
- return !boost::unordered_detail::equals(m1.base, m2.base);
+ return !m1.table_.equals(m2.table_);
}
template <class K, class T, class H, class P, class A>
@@ -503,115 +534,151 @@
template <class Key, class T, class Hash, class Pred, class Alloc>
class unordered_multimap
{
-#if BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
public:
-#endif
- typedef boost::unordered_detail::hash_types_equivalent_keys<
- std::pair<const Key, T>, Key, Hash, Pred, Alloc
- > implementation;
-
- BOOST_DEDUCED_TYPENAME implementation::hash_table base;
-
- public:
-
- // types
typedef Key key_type;
typedef std::pair<const Key, T> value_type;
typedef T mapped_type;
typedef Hash hasher;
typedef Pred key_equal;
-
typedef Alloc allocator_type;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::pointer pointer;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::const_pointer const_pointer;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::reference reference;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::const_reference const_reference;
-
- typedef BOOST_DEDUCED_TYPENAME implementation::size_type size_type;
- typedef BOOST_DEDUCED_TYPENAME implementation::difference_type difference_type;
-
- typedef BOOST_DEDUCED_TYPENAME implementation::iterator iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::const_iterator const_iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::local_iterator local_iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::const_local_iterator const_local_iterator;
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
+#endif
+ typedef BOOST_DEDUCED_TYPENAME
+ 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_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 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;
+ typedef boost::unordered_detail::hash_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;
+ typedef boost::unordered_detail::hash_iterator<
+ value_allocator, boost::unordered_detail::grouped>
+ iterator;
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
+#endif
+
+ table table_;
+
+ BOOST_DEDUCED_TYPENAME table::iterator_base const&
+ get(const_iterator const& it)
+ {
+ return boost::unordered_detail::iterator_access::get(it);
+ }
+
+ public:
// 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())
- : base(n, hf, eql, a)
+ : table_(n, hf, eql, a)
{
}
explicit unordered_multimap(allocator_type const& a)
- : base(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)
- : base(other.base, a)
+ unordered_multimap(unordered_multimap const& other,
+ allocator_type const& a)
+ : table_(other.table_, a)
{
}
- template <class InputIterator>
- unordered_multimap(InputIterator f, InputIterator l)
- : base(f, l, boost::unordered_detail::default_initial_bucket_count,
+ 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())
- : base(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,
const allocator_type &a)
- : base(f, l, n, hf, eql, a)
+ : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a)
{
+ table_.insert_range(f, l);
}
~unordered_multimap() {}
#if defined(BOOST_HAS_RVALUE_REFS)
unordered_multimap(unordered_multimap&& other)
- : base(other.base, boost::unordered_detail::move_tag())
+ : table_(other.table_, boost::unordered_detail::move_tag())
{
}
unordered_multimap(unordered_multimap&& other, allocator_type const& a)
- : base(other.base, a, boost::unordered_detail::move_tag())
+ : table_(other.table_, a, boost::unordered_detail::move_tag())
{
}
unordered_multimap& operator=(unordered_multimap&& x)
{
- base.move(x.base);
+ table_.move(x.table_);
return *this;
}
#else
- unordered_multimap(boost::unordered_detail::move_from<unordered_multimap<Key, T, Hash, Pred, Alloc> > other)
- : base(other.source.base, 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())
{
}
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
unordered_multimap& operator=(unordered_multimap x)
{
- base.move(x.base);
+ table_.move(x.table_);
return *this;
}
#endif
@@ -619,85 +686,77 @@
#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())
- : base(list.begin(), list.end(), n, hf, eql, a)
+ : table_(boost::unordered_detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, allocator_type())
{
+ table_.insert_range(list.begin(), list.end());
}
unordered_multimap& operator=(std::initializer_list<value_type> list)
{
- base.data_.clear();
- base.insert_range(list.begin(), list.end());
+ table_.clear();
+ table_.insert_range(list.begin(), list.end());
return *this;
}
#endif
-
- private:
-
- BOOST_DEDUCED_TYPENAME implementation::iterator_base const&
- get(const_iterator const& it)
- {
- return boost::unordered_detail::iterator_access::get(it);
- }
-
- public:
-
allocator_type get_allocator() const
{
- return base.get_allocator();
+ return table_.node_alloc();
}
// size and capacity
bool empty() const
{
- return base.empty();
+ return table_.size_ == 0;
}
size_type size() const
{
- return base.size();
+ return table_.size_;
}
size_type max_size() const
{
- return base.max_size();
+ return table_.max_size();
}
// iterators
iterator begin()
{
- return iterator(base.data_.begin());
+ return iterator(table_.begin());
}
const_iterator begin() const
{
- return const_iterator(base.data_.begin());
+ return const_iterator(table_.begin());
}
iterator end()
{
- return iterator(base.data_.end());
+ return iterator(table_.end());
}
const_iterator end() const
{
- return const_iterator(base.data_.end());
+ return const_iterator(table_.end());
}
const_iterator cbegin() const
{
- return const_iterator(base.data_.begin());
+ return const_iterator(table_.begin());
}
const_iterator cend() const
{
- return const_iterator(base.data_.end());
+ return const_iterator(table_.end());
}
// modifiers
@@ -706,51 +765,53 @@
template <class... Args>
iterator emplace(Args&&... args)
{
- return iterator(base.emplace(std::forward<Args>(args)...));
+ return iterator(table_.emplace(std::forward<Args>(args)...));
}
template <class... Args>
iterator emplace_hint(const_iterator hint, Args&&... args)
{
- return iterator(base.emplace_hint(get(hint), std::forward<Args>(args)...));
+ return iterator(table_.emplace_hint(get(hint),
+ std::forward<Args>(args)...));
}
#else
iterator emplace(value_type const& v = value_type())
{
- return iterator(base.emplace(v));
+ 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(base.emplace_hint(get(hint), v));
+ 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( \
- base.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(base.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,
@@ -762,168 +823,169 @@
iterator insert(const value_type& obj)
{
- return iterator(base.emplace(obj));
+ return iterator(table_.emplace(obj));
}
iterator insert(const_iterator hint, const value_type& obj)
{
- return iterator(base.emplace_hint(get(hint), obj));
+ 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)
{
- base.insert_range(first, last);
+ table_.insert_range(first, last);
}
iterator erase(const_iterator position)
{
- return iterator(base.data_.erase(get(position)));
+ return iterator(table_.erase(get(position)));
}
size_type erase(const key_type& k)
{
- return base.erase_key(k);
+ return table_.erase_key(k);
}
iterator erase(const_iterator first, const_iterator last)
{
- return iterator(base.data_.erase_range(get(first), get(last)));
+ return iterator(table_.erase_range(get(first), get(last)));
}
void clear()
{
- base.data_.clear();
+ table_.clear();
}
void swap(unordered_multimap& other)
{
- base.swap(other.base);
+ table_.swap(other.table_);
}
// observers
hasher hash_function() const
{
- return base.hash_function();
+ return table_.hash_function();
}
key_equal key_eq() const
{
- return base.key_eq();
+ return table_.key_eq();
}
// lookup
iterator find(const key_type& k)
{
- return iterator(base.find(k));
+ return iterator(table_.find(k));
}
const_iterator find(const key_type& k) const
{
- return const_iterator(base.find(k));
+ return const_iterator(table_.find(k));
}
size_type count(const key_type& k) const
{
- return base.count(k);
+ return table_.count(k);
}
std::pair<iterator, iterator>
equal_range(const key_type& k)
{
- return boost::unordered_detail::pair_cast<iterator, iterator>(
- base.equal_range(k));
+ 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>(
- base.equal_range(k));
+ return boost::unordered_detail::pair_cast<
+ const_iterator, const_iterator>(
+ table_.equal_range(k));
}
// bucket interface
size_type bucket_count() const
{
- return base.bucket_count();
+ return table_.bucket_count_;
}
size_type max_bucket_count() const
{
- return base.max_bucket_count();
+ return table_.max_bucket_count();
}
size_type bucket_size(size_type n) const
{
- return base.data_.bucket_size(n);
+ return table_.bucket_size(n);
}
size_type bucket(const key_type& k) const
{
- return base.bucket(k);
+ return table_.bucket_index(k);
}
local_iterator begin(size_type n)
{
- return local_iterator(base.data_.begin(n));
+ return local_iterator(table_.bucket_begin(n));
}
const_local_iterator begin(size_type n) const
{
- return const_local_iterator(base.data_.begin(n));
+ return const_local_iterator(table_.bucket_begin(n));
}
- local_iterator end(size_type n)
+ local_iterator end(size_type)
{
- return local_iterator(base.data_.end(n));
+ return local_iterator();
}
- const_local_iterator end(size_type n) const
+ const_local_iterator end(size_type) const
{
- return const_local_iterator(base.data_.end(n));
+ return const_local_iterator();
}
const_local_iterator cbegin(size_type n) const
{
- return const_local_iterator(base.data_.begin(n));
+ 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(base.data_.end(n));
+ return const_local_iterator();
}
// hash policy
float load_factor() const
{
- return base.load_factor();
+ return table_.load_factor();
}
float max_load_factor() const
{
- return base.max_load_factor();
+ return table_.mlf_;
}
void max_load_factor(float m)
{
- base.max_load_factor(m);
+ table_.max_load_factor(m);
}
void rehash(size_type n)
{
- base.rehash(n);
+ table_.rehash(n);
}
-#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
- friend bool operator==(unordered_multimap const&, unordered_multimap const&);
- friend bool operator!=(unordered_multimap const&, unordered_multimap const&);
-#elif !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&);
+#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&);
#endif
}; // class template unordered_multimap
@@ -931,14 +993,14 @@
inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1,
unordered_multimap<K, T, H, P, A> const& m2)
{
- return boost::unordered_detail::equals(m1.base, m2.base);
+ return m1.table_.equals(m2.table_);
}
template <class K, class T, class H, class P, class A>
inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1,
unordered_multimap<K, T, H, P, A> const& m2)
{
- return !boost::unordered_detail::equals(m1.base, m2.base);
+ return !m1.table_.equals(m2.table_);
}
template <class K, class T, class H, class P, class A>
Modified: branches/release/boost/unordered/unordered_set.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_set.hpp (original)
+++ branches/release/boost/unordered/unordered_set.hpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -15,7 +15,9 @@
#include <boost/unordered/unordered_set_fwd.hpp>
#include <boost/functional/hash.hpp>
-#include <boost/unordered/detail/hash_table.hpp>
+#include <boost/unordered/detail/allocator_helpers.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>
@@ -39,112 +41,144 @@
template <class Value, class Hash, class Pred, class Alloc>
class unordered_set
{
-#if BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
public:
+
+ typedef Value key_type;
+ typedef Value value_type;
+ typedef Hash hasher;
+ typedef Pred key_equal;
+ typedef Alloc allocator_type;
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
#endif
- typedef boost::unordered_detail::hash_types_unique_keys<
- Value, Value, Hash, Pred, Alloc
- > implementation;
- BOOST_DEDUCED_TYPENAME implementation::hash_table base;
+ typedef BOOST_DEDUCED_TYPENAME
+ 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_DEDUCED_TYPENAME table::iterator_base iterator_base;
public:
- // types
+ 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;
+ typedef boost::unordered_detail::hash_const_iterator<
+ value_allocator, boost::unordered_detail::ungrouped>
+ const_iterator;
+ typedef const_local_iterator local_iterator;
+ typedef const_iterator iterator;
- typedef Value key_type;
- typedef Value value_type;
- typedef Hash hasher;
- typedef Pred key_equal;
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
+#endif
- typedef Alloc allocator_type;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::pointer pointer;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::const_pointer const_pointer;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::reference reference;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::const_reference const_reference;
-
- typedef BOOST_DEDUCED_TYPENAME implementation::size_type size_type;
- typedef BOOST_DEDUCED_TYPENAME implementation::difference_type difference_type;
-
- typedef BOOST_DEDUCED_TYPENAME implementation::const_iterator iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::const_iterator const_iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::const_local_iterator local_iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::const_local_iterator const_local_iterator;
+ table table_;
+
+ BOOST_DEDUCED_TYPENAME table::iterator_base const&
+ get(const_iterator const& it)
+ {
+ return boost::unordered_detail::iterator_access::get(it);
+ }
+
+ public:
// 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())
- : base(n, hf, eql, a)
+ : table_(n, hf, eql, a)
{
}
explicit unordered_set(allocator_type const& a)
- : base(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)
- : base(other.base, a)
+ : table_(other.table_, a)
{
}
- template <class InputIterator>
- unordered_set(InputIterator f, InputIterator l)
- : base(f, l, boost::unordered_detail::default_initial_bucket_count,
- 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())
- : base(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)
- : base(f, l, n, hf, eql, a)
+ : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a)
{
+ table_.insert_range(f, l);
}
~unordered_set() {}
#if defined(BOOST_HAS_RVALUE_REFS)
unordered_set(unordered_set&& other)
- : base(other.base, boost::unordered_detail::move_tag())
+ : table_(other.table_, boost::unordered_detail::move_tag())
{
}
unordered_set(unordered_set&& other, allocator_type const& a)
- : base(other.base, a, boost::unordered_detail::move_tag())
+ : table_(other.table_, a, boost::unordered_detail::move_tag())
{
}
unordered_set& operator=(unordered_set&& x)
{
- base.move(x.base);
+ table_.move(x.table_);
return *this;
}
#else
- unordered_set(boost::unordered_detail::move_from<unordered_set<Value, Hash, Pred, Alloc> > other)
- : base(other.source.base, 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())
{
}
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
unordered_set& operator=(unordered_set x)
{
- base.move(x.base);
+ table_.move(x.table_);
return *this;
}
#endif
@@ -152,84 +186,77 @@
#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())
- : base(list.begin(), list.end(), n, hf, eql, a)
+ : table_(boost::unordered_detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, allocator_type())
{
+ table_.insert_range(list.begin(), list.end());
}
unordered_set& operator=(std::initializer_list<value_type> list)
{
- base.data_.clear();
- base.insert_range(list.begin(), list.end());
+ table_.clear();
+ table_.insert_range(list.begin(), list.end());
return *this;
}
#endif
- private:
-
- BOOST_DEDUCED_TYPENAME implementation::iterator_base const&
- get(const_iterator const& it)
- {
- return boost::unordered_detail::iterator_access::get(it);
- }
-
- public:
-
allocator_type get_allocator() const
{
- return base.get_allocator();
+ return table_.node_alloc();
}
// size and capacity
bool empty() const
{
- return base.empty();
+ return table_.size_ == 0;
}
size_type size() const
{
- return base.size();
+ return table_.size_;
}
size_type max_size() const
{
- return base.max_size();
+ return table_.max_size();
}
// iterators
iterator begin()
{
- return iterator(base.data_.begin());
+ return iterator(table_.begin());
}
const_iterator begin() const
{
- return const_iterator(base.data_.begin());
+ return const_iterator(table_.begin());
}
iterator end()
{
- return iterator(base.data_.end());
+ return iterator(table_.end());
}
const_iterator end() const
{
- return const_iterator(base.data_.end());
+ return const_iterator(table_.end());
}
const_iterator cbegin() const
{
- return const_iterator(base.data_.begin());
+ return const_iterator(table_.begin());
}
const_iterator cend() const
{
- return const_iterator(base.data_.end());
+ return const_iterator(table_.end());
}
// modifiers
@@ -239,52 +266,51 @@
std::pair<iterator, bool> emplace(Args&&... args)
{
return boost::unordered_detail::pair_cast<iterator, bool>(
- base.emplace(std::forward<Args>(args)...));
+ table_.emplace(std::forward<Args>(args)...));
}
template <class... Args>
- iterator emplace_hint(const_iterator hint, Args&&... args)
+ iterator emplace_hint(const_iterator, Args&&... args)
{
- return iterator(
- base.emplace_hint(get(hint), std::forward<Args>(args)...));
+ return iterator(table_.emplace(std::forward<Args>(args)...).first);
}
#else
std::pair<iterator, bool> emplace(value_type const& v = value_type())
{
return boost::unordered_detail::pair_cast<iterator, bool>(
- base.emplace(v));
+ table_.emplace(v));
}
- iterator emplace_hint(const_iterator hint, value_type const& v = value_type())
+ iterator emplace_hint(const_iterator,
+ value_type const& v = value_type())
{
- return iterator(base.emplace_hint(get(hint), v));
+ return iterator(table_.emplace(v).first);
}
-#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>( \
- base.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(base.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, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator(table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)).first); \
}
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
@@ -297,156 +323,156 @@
std::pair<iterator, bool> insert(const value_type& obj)
{
return boost::unordered_detail::pair_cast<iterator, bool>(
- base.emplace(obj));
+ table_.emplace(obj));
}
iterator insert(const_iterator hint, const value_type& obj)
{
- return iterator(base.emplace_hint(get(hint), obj));
+ return iterator(table_.emplace(obj).first);
}
- template <class InputIterator>
- void insert(InputIterator first, InputIterator last)
+ template <class InputIt>
+ void insert(InputIt first, InputIt last)
{
- base.insert_range(first, last);
+ table_.insert_range(first, last);
}
iterator erase(const_iterator position)
{
- return iterator(base.data_.erase(get(position)));
+ return iterator(table_.erase(get(position)));
}
size_type erase(const key_type& k)
{
- return base.erase_key(k);
+ return table_.erase_key(k);
}
iterator erase(const_iterator first, const_iterator last)
{
- return iterator(base.data_.erase_range(get(first), get(last)));
+ return iterator(table_.erase_range(get(first), get(last)));
}
void clear()
{
- base.data_.clear();
+ table_.clear();
}
void swap(unordered_set& other)
{
- base.swap(other.base);
+ table_.swap(other.table_);
}
// observers
hasher hash_function() const
{
- return base.hash_function();
+ return table_.hash_function();
}
key_equal key_eq() const
{
- return base.key_eq();
+ return table_.key_eq();
}
// lookup
const_iterator find(const key_type& k) const
{
- return const_iterator(base.find(k));
+ return const_iterator(table_.find(k));
}
size_type count(const key_type& k) const
{
- return base.count(k);
+ return table_.count(k);
}
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const
{
- return boost::unordered_detail::pair_cast<const_iterator, const_iterator>(
- base.equal_range(k));
+ return boost::unordered_detail::pair_cast<
+ const_iterator, const_iterator>(
+ table_.equal_range(k));
}
// bucket interface
size_type bucket_count() const
{
- return base.bucket_count();
+ return table_.bucket_count_;
}
size_type max_bucket_count() const
{
- return base.max_bucket_count();
+ return table_.max_bucket_count();
}
size_type bucket_size(size_type n) const
{
- return base.data_.bucket_size(n);
+ return table_.bucket_size(n);
}
size_type bucket(const key_type& k) const
{
- return base.bucket(k);
+ return table_.bucket_index(k);
}
local_iterator begin(size_type n)
{
- return local_iterator(base.data_.begin(n));
+ return local_iterator(table_.bucket_begin(n));
}
const_local_iterator begin(size_type n) const
{
- return const_local_iterator(base.data_.begin(n));
+ return const_local_iterator(table_.bucket_begin(n));
}
- local_iterator end(size_type n)
+ local_iterator end(size_type)
{
- return local_iterator(base.data_.end(n));
+ return local_iterator();
}
- const_local_iterator end(size_type n) const
+ const_local_iterator end(size_type) const
{
- return const_local_iterator(base.data_.end(n));
+ return const_local_iterator();
}
const_local_iterator cbegin(size_type n) const
{
- return const_local_iterator(base.data_.begin(n));
+ 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(base.data_.end(n));
+ return const_local_iterator();
}
// hash policy
float load_factor() const
{
- return base.load_factor();
+ return table_.load_factor();
}
float max_load_factor() const
{
- return base.max_load_factor();
+ return table_.mlf_;
}
void max_load_factor(float m)
{
- base.max_load_factor(m);
+ table_.max_load_factor(m);
}
void rehash(size_type n)
{
- base.rehash(n);
+ table_.rehash(n);
}
-#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
- friend bool operator==(unordered_set const&, unordered_set const&);
- friend bool operator!=(unordered_set const&, unordered_set const&);
-#elif !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&);
+#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&);
#endif
}; // class template unordered_set
@@ -454,14 +480,14 @@
inline bool operator==(unordered_set<T, H, P, A> const& m1,
unordered_set<T, H, P, A> const& m2)
{
- return boost::unordered_detail::equals(m1.base, m2.base);
+ return m1.table_.equals(m2.table_);
}
template <class T, class H, class P, class A>
inline bool operator!=(unordered_set<T, H, P, A> const& m1,
unordered_set<T, H, P, A> const& m2)
{
- return !boost::unordered_detail::equals(m1.base, m2.base);
+ return !m1.table_.equals(m2.table_);
}
template <class T, class H, class P, class A>
@@ -474,112 +500,144 @@
template <class Value, class Hash, class Pred, class Alloc>
class unordered_multiset
{
-#if BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
- public:
-#endif
- typedef boost::unordered_detail::hash_types_equivalent_keys<
- Value, Value, Hash, Pred, Alloc
- > implementation;
-
- BOOST_DEDUCED_TYPENAME implementation::hash_table base;
-
public:
- //types
-
typedef Value key_type;
typedef Value value_type;
typedef Hash hasher;
typedef Pred key_equal;
-
typedef Alloc allocator_type;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::pointer pointer;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::const_pointer const_pointer;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::reference reference;
- typedef BOOST_DEDUCED_TYPENAME allocator_type::const_reference const_reference;
-
- typedef BOOST_DEDUCED_TYPENAME implementation::size_type size_type;
- typedef BOOST_DEDUCED_TYPENAME implementation::difference_type difference_type;
-
- typedef BOOST_DEDUCED_TYPENAME implementation::const_iterator iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::const_iterator const_iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::const_local_iterator local_iterator;
- typedef BOOST_DEDUCED_TYPENAME implementation::const_local_iterator const_local_iterator;
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
+#endif
+ typedef BOOST_DEDUCED_TYPENAME
+ 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_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 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;
+ typedef boost::unordered_detail::hash_const_iterator<
+ value_allocator, boost::unordered_detail::grouped>
+ const_iterator;
+ typedef const_local_iterator local_iterator;
+ typedef const_iterator iterator;
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
+ private:
+#endif
+
+ table table_;
+
+ BOOST_DEDUCED_TYPENAME table::iterator_base const&
+ get(const_iterator const& it)
+ {
+ return boost::unordered_detail::iterator_access::get(it);
+ }
+
+ public:
// 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())
- : base(n, hf, eql, a)
+ : table_(n, hf, eql, a)
{
}
explicit unordered_multiset(allocator_type const& a)
- : base(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)
- : base(other.base, a)
+ unordered_multiset(unordered_multiset const& other,
+ allocator_type const& a)
+ : table_(other.table_, a)
{
}
- template <class InputIterator>
- unordered_multiset(InputIterator f, InputIterator l)
- : base(f, l, boost::unordered_detail::default_initial_bucket_count,
+ 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())
- : base(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)
- : base(f, l, n, hf, eql, a)
+ : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a)
{
+ table_.insert_range(f, l);
}
~unordered_multiset() {}
#if defined(BOOST_HAS_RVALUE_REFS)
unordered_multiset(unordered_multiset&& other)
- : base(other.base, boost::unordered_detail::move_tag())
+ : table_(other.table_, boost::unordered_detail::move_tag())
{
}
unordered_multiset(unordered_multiset&& other, allocator_type const& a)
- : base(other.base, a, boost::unordered_detail::move_tag())
+ : table_(other.table_, a, boost::unordered_detail::move_tag())
{
}
unordered_multiset& operator=(unordered_multiset&& x)
{
- base.move(x.base);
+ table_.move(x.table_);
return *this;
}
#else
- unordered_multiset(boost::unordered_detail::move_from<unordered_multiset<Value, Hash, Pred, Alloc> > other)
- : base(other.source.base, 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())
{
}
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
unordered_multiset& operator=(unordered_multiset x)
{
- base.move(x.base);
+ table_.move(x.table_);
return *this;
}
#endif
@@ -587,84 +645,77 @@
#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())
- : base(list.begin(), list.end(), n, hf, eql, a)
+ : table_(boost::unordered_detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, allocator_type())
{
+ table_.insert_range(list.begin(), list.end());
}
unordered_multiset& operator=(std::initializer_list<value_type> list)
{
- base.data_.clear();
- base.insert_range(list.begin(), list.end());
+ table_.clear();
+ table_.insert_range(list.begin(), list.end());
return *this;
}
#endif
- private:
-
- BOOST_DEDUCED_TYPENAME implementation::iterator_base const&
- get(const_iterator const& it)
- {
- return boost::unordered_detail::iterator_access::get(it);
- }
-
- public:
-
allocator_type get_allocator() const
{
- return base.get_allocator();
+ return table_.node_alloc();
}
// size and capacity
bool empty() const
{
- return base.empty();
+ return table_.size_ == 0;
}
size_type size() const
{
- return base.size();
+ return table_.size_;
}
size_type max_size() const
{
- return base.max_size();
+ return table_.max_size();
}
// iterators
iterator begin()
{
- return iterator(base.data_.begin());
+ return iterator(table_.begin());
}
const_iterator begin() const
{
- return const_iterator(base.data_.begin());
+ return const_iterator(table_.begin());
}
iterator end()
{
- return iterator(base.data_.end());
+ return iterator(table_.end());
}
const_iterator end() const
{
- return const_iterator(base.data_.end());
+ return const_iterator(table_.end());
}
const_iterator cbegin() const
{
- return const_iterator(base.data_.begin());
+ return const_iterator(table_.begin());
}
const_iterator cend() const
{
- return const_iterator(base.data_.end());
+ return const_iterator(table_.end());
}
// modifiers
@@ -673,50 +724,50 @@
template <class... Args>
iterator emplace(Args&&... args)
{
- return iterator(base.emplace(std::forward<Args>(args)...));
+ return iterator(table_.emplace(std::forward<Args>(args)...));
}
template <class... Args>
iterator emplace_hint(const_iterator hint, Args&&... args)
{
- return iterator(base.emplace_hint(get(hint), std::forward<Args>(args)...));
+ return iterator(table_.emplace_hint(get(hint),
+ std::forward<Args>(args)...));
}
#else
iterator emplace(value_type const& v = value_type())
{
- return iterator(base.emplace(v));
+ 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(base.emplace_hint(get(hint), v));
+ 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( \
- base.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(base.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,
@@ -728,156 +779,156 @@
iterator insert(const value_type& obj)
{
- return iterator(base.emplace(obj));
+ return iterator(table_.emplace(obj));
}
iterator insert(const_iterator hint, const value_type& obj)
{
- return iterator(base.emplace_hint(get(hint), obj));
+ 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)
{
- base.insert_range(first, last);
+ table_.insert_range(first, last);
}
iterator erase(const_iterator position)
{
- return iterator(base.data_.erase(get(position)));
+ return iterator(table_.erase(get(position)));
}
size_type erase(const key_type& k)
{
- return base.erase_key(k);
+ return table_.erase_key(k);
}
iterator erase(const_iterator first, const_iterator last)
{
- return iterator(base.data_.erase_range(get(first), get(last)));
+ return iterator(table_.erase_range(get(first), get(last)));
}
void clear()
{
- base.data_.clear();
+ table_.clear();
}
void swap(unordered_multiset& other)
{
- base.swap(other.base);
+ table_.swap(other.table_);
}
// observers
hasher hash_function() const
{
- return base.hash_function();
+ return table_.hash_function();
}
key_equal key_eq() const
{
- return base.key_eq();
+ return table_.key_eq();
}
// lookup
const_iterator find(const key_type& k) const
{
- return const_iterator(base.find(k));
+ return const_iterator(table_.find(k));
}
size_type count(const key_type& k) const
{
- return base.count(k);
+ return table_.count(k);
}
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const
{
- return boost::unordered_detail::pair_cast<const_iterator, const_iterator>(
- base.equal_range(k));
+ return boost::unordered_detail::pair_cast<
+ const_iterator, const_iterator>(
+ table_.equal_range(k));
}
// bucket interface
size_type bucket_count() const
{
- return base.bucket_count();
+ return table_.bucket_count_;
}
size_type max_bucket_count() const
{
- return base.max_bucket_count();
+ return table_.max_bucket_count();
}
size_type bucket_size(size_type n) const
{
- return base.data_.bucket_size(n);
+ return table_.bucket_size(n);
}
size_type bucket(const key_type& k) const
{
- return base.bucket(k);
+ return table_.bucket_index(k);
}
local_iterator begin(size_type n)
{
- return local_iterator(base.data_.begin(n));
+ return local_iterator(table_.bucket_begin(n));
}
const_local_iterator begin(size_type n) const
{
- return const_local_iterator(base.data_.begin(n));
+ return const_local_iterator(table_.bucket_begin(n));
}
- local_iterator end(size_type n)
+ local_iterator end(size_type)
{
- return local_iterator(base.data_.end(n));
+ return local_iterator();
}
- const_local_iterator end(size_type n) const
+ const_local_iterator end(size_type) const
{
- return const_local_iterator(base.data_.end(n));
+ return const_local_iterator();
}
const_local_iterator cbegin(size_type n) const
{
- return const_local_iterator(base.data_.begin(n));
+ 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(base.data_.end(n));
+ return const_local_iterator();
}
// hash policy
float load_factor() const
{
- return base.load_factor();
+ return table_.load_factor();
}
float max_load_factor() const
{
- return base.max_load_factor();
+ return table_.mlf_;
}
void max_load_factor(float m)
{
- base.max_load_factor(m);
+ table_.max_load_factor(m);
}
void rehash(size_type n)
{
- base.rehash(n);
+ table_.rehash(n);
}
-#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
- friend bool operator==(unordered_multiset const&, unordered_multiset const&);
- friend bool operator!=(unordered_multiset const&, unordered_multiset const&);
-#elif !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&);
+#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&);
#endif
}; // class template unordered_multiset
@@ -885,14 +936,14 @@
inline bool operator==(unordered_multiset<T, H, P, A> const& m1,
unordered_multiset<T, H, P, A> const& m2)
{
- return boost::unordered_detail::equals(m1.base, m2.base);
+ return m1.table_.equals(m2.table_);
}
template <class T, class H, class P, class A>
inline bool operator!=(unordered_multiset<T, H, P, A> const& m1,
unordered_multiset<T, H, P, A> const& m2)
{
- return !boost::unordered_detail::equals(m1.base, m2.base);
+ return !m1.table_.equals(m2.table_);
}
template <class T, class H, class P, class A>
Modified: branches/release/libs/unordered/doc/ref.xml
==============================================================================
--- branches/release/libs/unordered/doc/ref.xml (original)
+++ branches/release/libs/unordered/doc/ref.xml 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -24,7 +24,7 @@
</simpara></purpose>
<description>
<para>For the normative reference see chapter 23 of
- <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008-2009/n2691.pdf">the working draft of the C++ standard [n2691].</ulink></para>
+ <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2691.pdf">the working draft of the C++ standard [n2691].</ulink></para>
<para><emphasis role="bold">Template Parameters</emphasis>
<informaltable>
<tgroup cols="2">
@@ -762,7 +762,7 @@
</simpara></purpose>
<description>
<para>For the normative reference see chapter 23 of
- <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008-2009/n2691.pdf">the working draft of the C++ standard [n2691].</ulink></para>
+ <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2691.pdf">the working draft of the C++ standard [n2691].</ulink></para>
<para><emphasis role="bold">Template Parameters</emphasis>
<informaltable>
<tgroup cols="2">
@@ -1504,7 +1504,7 @@
</simpara></purpose>
<description>
<para>For the normative reference see chapter 23 of
- <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008-2009/n2691.pdf">the working draft of the C++ standard [n2691].</ulink></para>
+ <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2691.pdf">the working draft of the C++ standard [n2691].</ulink></para>
<para><emphasis role="bold">Template Parameters</emphasis>
<informaltable>
<tgroup cols="2">
@@ -2291,7 +2291,7 @@
</simpara></purpose>
<description>
<para>For the normative reference see chapter 23 of
- <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008-2009/n2691.pdf">the working draft of the C++ standard [n2691].</ulink></para>
+ <ulink url="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2691.pdf">the working draft of the C++ standard [n2691].</ulink></para>
<para><emphasis role="bold">Template Parameters</emphasis>
<informaltable>
<tgroup cols="2">
Modified: branches/release/libs/unordered/test/Jamfile.v2
==============================================================================
--- branches/release/libs/unordered/test/Jamfile.v2 (original)
+++ branches/release/libs/unordered/test/Jamfile.v2 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -3,5 +3,7 @@
# 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)
+import testing ;
+
build-project unordered ;
build-project exception ;
Modified: branches/release/libs/unordered/test/helpers/list.hpp
==============================================================================
--- branches/release/libs/unordered/test/helpers/list.hpp (original)
+++ branches/release/libs/unordered/test/helpers/list.hpp 2009-09-24 17:12:46 EDT (Thu, 24 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: branches/release/libs/unordered/test/unordered/Jamfile.v2
==============================================================================
--- branches/release/libs/unordered/test/unordered/Jamfile.v2 (original)
+++ branches/release/libs/unordered/test/unordered/Jamfile.v2 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -10,6 +10,7 @@
<toolset>intel-linux:"<cxxflags>-strict_ansi -cxxlib-icc"
<toolset>gcc:<cxxflags>"-Wsign-promo -Wunused-parameter"
#<toolset>msvc:<cxxflags>/W4
+ <warnings>all
;
test-suite unordered
Modified: branches/release/libs/unordered/test/unordered/constructor_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/constructor_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/constructor_tests.cpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -250,6 +250,19 @@
test::check_equivalent_keys(x);
test::check_equivalent_keys(y);
}
+
+ std::cerr<<"Construct 9\n";
+ {
+ test::random_values<T> v(100, generator);
+ T x(50);
+ BOOST_TEST(x.bucket_count() >= 50);
+ x.max_load_factor(10);
+ BOOST_TEST(x.bucket_count() >= 50);
+ x.insert(v.begin(), v.end());
+ BOOST_TEST(x.bucket_count() >= 50);
+ test::check_container(x, v);
+ test::check_equivalent_keys(x);
+ }
}
template <class T>
Modified: branches/release/libs/unordered/test/unordered/copy_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/copy_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/copy_tests.cpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -41,7 +41,7 @@
T x(v.begin(), v.end());
T y(x);
test::unordered_equivalence_tester<T> equivalent(x);
- equivalent(y);
+ BOOST_TEST(equivalent(y));
test::check_equivalent_keys(y);
}
@@ -55,7 +55,7 @@
x.max_load_factor(x.load_factor() / 4);
T y(x);
test::unordered_equivalence_tester<T> equivalent(x);
- equivalent(y);
+ BOOST_TEST(equivalent(y));
// This isn't guaranteed:
BOOST_TEST(y.load_factor() < y.max_load_factor());
test::check_equivalent_keys(y);
@@ -100,7 +100,7 @@
T x(v.begin(), v.end(), 0, hf, eq, al);
T y(x);
test::unordered_equivalence_tester<T> equivalent(x);
- equivalent(y);
+ BOOST_TEST(equivalent(y));
test::check_equivalent_keys(y);
BOOST_TEST(test::equivalent(y.get_allocator(), al));
}
@@ -111,7 +111,7 @@
T x(v.begin(), v.end(), 0, hf, eq, al);
T y(x, al2);
test::unordered_equivalence_tester<T> equivalent(x);
- equivalent(y);
+ BOOST_TEST(equivalent(y));
test::check_equivalent_keys(y);
BOOST_TEST(test::equivalent(y.get_allocator(), al2));
}
Modified: branches/release/libs/unordered/test/unordered/erase_equiv_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/erase_equiv_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/erase_equiv_tests.cpp 2009-09-24 17:12:46 EDT (Thu, 24 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: branches/release/libs/unordered/test/unordered/move_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/move_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/move_tests.cpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -119,7 +119,7 @@
BOOST_TEST(y.max_load_factor() == 2.0); // Not necessarily required.
test::check_equivalent_keys(y);
}
-
+/*
{
test::random_values<T> v(25, generator);
T y(create(v, count, hf, eq, al, 1.0), al);
@@ -137,7 +137,7 @@
BOOST_TEST(y.max_load_factor() == 1.0); // Not necessarily required.
test::check_equivalent_keys(y);
}
- }
+*/ }
boost::unordered_set<test::object, test::hash, test::equal_to, test::allocator<test::object> >* test_set;
boost::unordered_multiset<test::object, test::hash, test::equal_to, test::allocator<test::object> >* test_multiset;
Modified: branches/release/libs/unordered/test/unordered/simple_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/simple_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/simple_tests.cpp 2009-09-24 17:12:46 EDT (Thu, 24 Sep 2009)
@@ -60,6 +60,7 @@
X u;
X& r = u;
BOOST_TEST(&(r = r) == &r);
+
BOOST_TEST(r.empty());
BOOST_TEST(&(r = a) == &r);
BOOST_TEST(equivalent(r));
@@ -91,7 +92,7 @@
std::cout<<"Test unordered_set.\n";
boost::unordered_set<int> set;
simple_test(set);
-
+
set.insert(1); set.insert(2); set.insert(1456);
simple_test(set);
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk