|
|
Boost-Commit : |
From: daniel_james_at_[hidden]
Date: 2008-01-01 15:21:05
Author: danieljames
Date: 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
New Revision: 42403
URL: http://svn.boost.org/trac/boost/changeset/42403
Log:
Merged revisions 41808-41821,41823-41927,41934-41942,41944-41950,41952-41993,41998-42091,42094-42095,42104-42105,42107,42109,42111-42152,42154,42160-42171,42173-42180,42183-42196,42198-42402 via svnmerge from
https://svn.boost.org/svn/boost/branches/unordered/dev
........
r41993 | danieljames | 2007-12-13 00:23:27 +0000 (Thu, 13 Dec 2007) | 3 lines
Add the hash documentation to the unordered library so that it'll be easier to
link between the libraries.
........
r42104 | danieljames | 2007-12-16 13:36:50 +0000 (Sun, 16 Dec 2007) | 1 line
Don't include any hash source in tarballs (although I'm including the documentation).
........
r42198 | danieljames | 2007-12-20 10:49:10 +0000 (Thu, 20 Dec 2007) | 1 line
Restore the extra warnings in the unit tests.
........
r42199 | danieljames | 2007-12-20 11:25:38 +0000 (Thu, 20 Dec 2007) | 1 line
Make a cast explicit in order to avoid a warning.
........
r42203 | danieljames | 2007-12-20 15:54:31 +0000 (Thu, 20 Dec 2007) | 1 line
Use 'BOOST_UNORDERED' prefix for macros.
........
r42209 | danieljames | 2007-12-20 19:41:17 +0000 (Thu, 20 Dec 2007) | 1 line
Initialise this branch (hopefully..)
........
r42210 | danieljames | 2007-12-20 19:51:21 +0000 (Thu, 20 Dec 2007) | 1 line
Merge in changes.
........
r42215 | danieljames | 2007-12-20 21:15:42 +0000 (Thu, 20 Dec 2007) | 1 line
Don't add size_type to pointers, cast to difference_type.
........
r42216 | danieljames | 2007-12-20 21:17:38 +0000 (Thu, 20 Dec 2007) | 1 line
I messed up the last commit, this fixes it.
........
r42218 | danieljames | 2007-12-20 21:22:20 +0000 (Thu, 20 Dec 2007) | 1 line
Get rid of last_in_group.
........
r42219 | danieljames | 2007-12-20 21:27:46 +0000 (Thu, 20 Dec 2007) | 1 line
Use node_count to implement group_count.
........
r42231 | danieljames | 2007-12-21 12:04:52 +0000 (Fri, 21 Dec 2007) | 1 line
Some minor changes for Visual C++.
........
r42233 | danieljames | 2007-12-21 19:41:27 +0000 (Fri, 21 Dec 2007) | 1 line
Inline some more methods.
........
r42335 | danieljames | 2007-12-29 13:14:45 +0000 (Sat, 29 Dec 2007) | 3 lines
Some of the changes to the introduction mention in the review. Hopefully this
will make it a little clearer.
........
r42336 | danieljames | 2007-12-29 13:16:55 +0000 (Sat, 29 Dec 2007) | 3 lines
Try to make the buckets explanation a little easier to read. Most of the
changes were based on Jamie Allsop (same for the last commit).
........
r42339 | danieljames | 2007-12-29 16:00:32 +0000 (Sat, 29 Dec 2007) | 1 line
Specify the namespace for 'std::out_of_range' in the reference documentation.
........
r42345 | danieljames | 2007-12-29 20:41:10 +0000 (Sat, 29 Dec 2007) | 8 lines
Rewrite much of the 'controlling the number of buckets' section.
I'm trying to make it clearer. It's a bit tricky as the standard doesn't guarantee much.
Instead of diving straight into the details I have tried to give the reader a rough
idea of what 'rehash' does and what the load factor is. This is hopefully enough to
understand the more detailled discussion of how you can control the number of buckets.
Then finally I discuss iterator invalidation.
........
r42346 | danieljames | 2007-12-29 20:52:22 +0000 (Sat, 29 Dec 2007) | 1 line
Move the table summarizing methods for controlling bucket size next to the discussion of these methods. The paragraphs about insert and invalidating iterator moves on to something else.
........
r42348 | danieljames | 2007-12-29 20:55:30 +0000 (Sat, 29 Dec 2007) | 1 line
Fix the badly marked up bullet points.
........
r42349 | danieljames | 2007-12-29 20:57:53 +0000 (Sat, 29 Dec 2007) | 2 lines
We now have cbegin and cend for local iterators.
........
Added:
branches/unordered/trunk/libs/functional/
- copied from r41993, /sandbox/unordered/libs/functional/
branches/unordered/trunk/libs/functional/hash/
- copied from r41993, /sandbox/unordered/libs/functional/hash/
branches/unordered/trunk/libs/functional/hash/doc/
- copied from r41993, /sandbox/unordered/libs/functional/hash/doc/
branches/unordered/trunk/libs/functional/hash/doc/Jamfile.v2
- copied unchanged from r41993, /sandbox/unordered/libs/functional/hash/doc/Jamfile.v2
branches/unordered/trunk/libs/functional/hash/doc/changes.qbk
- copied unchanged from r41993, /sandbox/unordered/libs/functional/hash/doc/changes.qbk
branches/unordered/trunk/libs/functional/hash/doc/disable.qbk
- copied unchanged from r41993, /sandbox/unordered/libs/functional/hash/doc/disable.qbk
branches/unordered/trunk/libs/functional/hash/doc/hash.qbk
- copied unchanged from r41993, /sandbox/unordered/libs/functional/hash/doc/hash.qbk
branches/unordered/trunk/libs/functional/hash/doc/intro.qbk
- copied unchanged from r41993, /sandbox/unordered/libs/functional/hash/doc/intro.qbk
branches/unordered/trunk/libs/functional/hash/doc/links.qbk
- copied unchanged from r41993, /sandbox/unordered/libs/functional/hash/doc/links.qbk
branches/unordered/trunk/libs/functional/hash/doc/portability.qbk
- copied unchanged from r41993, /sandbox/unordered/libs/functional/hash/doc/portability.qbk
branches/unordered/trunk/libs/functional/hash/doc/ref.xml
- copied unchanged from r41993, /sandbox/unordered/libs/functional/hash/doc/ref.xml
branches/unordered/trunk/libs/functional/hash/doc/thanks.qbk
- copied unchanged from r41993, /sandbox/unordered/libs/functional/hash/doc/thanks.qbk
branches/unordered/trunk/libs/functional/hash/doc/tutorial.qbk
- copied unchanged from r41993, /sandbox/unordered/libs/functional/hash/doc/tutorial.qbk
Properties modified:
branches/unordered/trunk/ (props changed)
Text files modified:
branches/unordered/trunk/boost/unordered/detail/hash_table.hpp | 20 ++--
branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp | 199 ++++++++++++++++++++-------------------
branches/unordered/trunk/doc/Jamfile.v2 | 4
branches/unordered/trunk/doc/src/boost.xml | 2
branches/unordered/trunk/libs/unordered/doc/buckets.qbk | 100 +++++++++++---------
branches/unordered/trunk/libs/unordered/doc/intro.qbk | 10 +
branches/unordered/trunk/libs/unordered/doc/ref.xml | 2
branches/unordered/trunk/libs/unordered/test/container/Jamfile.v2 | 2
branches/unordered/trunk/libs/unordered/test/exception/Jamfile.v2 | 1
branches/unordered/trunk/libs/unordered/test/helpers/generators.hpp | 2
branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2 | 2
branches/unordered/trunk/libs/unordered/test/unordered/compile_tests.cpp | 2
branches/unordered/trunk/release.sh | 1
13 files changed, 184 insertions(+), 163 deletions(-)
Modified: branches/unordered/trunk/boost/unordered/detail/hash_table.hpp
==============================================================================
--- branches/unordered/trunk/boost/unordered/detail/hash_table.hpp (original)
+++ branches/unordered/trunk/boost/unordered/detail/hash_table.hpp 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -33,15 +33,15 @@
#include <boost/mpl/aux_/config/eti.hpp>
#if BOOST_WORKAROUND(__BORLANDC__, <= 0x0551)
-#define BOOST_HASH_BORLAND_BOOL(x) (bool)(x)
+#define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x)
#else
-#define BOOST_HASH_BORLAND_BOOL(x) x
+#define BOOST_UNORDERED_BORLAND_BOOL(x) x
#endif
#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
-#define BOOST_HASH_MSVC_RESET_PTR(x) unordered_detail::reset(x)
+#define BOOST_UNORDERED_MSVC_RESET_PTR(x) unordered_detail::reset(x)
#else
-#define BOOST_HASH_MSVC_RESET_PTR(x)
+#define BOOST_UNORDERED_MSVC_RESET_PTR(x)
#endif
namespace boost {
@@ -112,13 +112,13 @@
}
}
-#define BOOST_UNORDERED_HASH_EQUIVALENT 1
+#define BOOST_UNORDERED_EQUIVALENT_KEYS 1
#include <boost/unordered/detail/hash_table_impl.hpp>
-#undef BOOST_UNORDERED_HASH_EQUIVALENT
+#undef BOOST_UNORDERED_EQUIVALENT_KEYS
-#define BOOST_UNORDERED_HASH_EQUIVALENT 0
+#define BOOST_UNORDERED_EQUIVALENT_KEYS 0
#include <boost/unordered/detail/hash_table_impl.hpp>
-#undef BOOST_UNORDERED_HASH_EQUIVALENT
+#undef BOOST_UNORDERED_EQUIVALENT_KEYS
namespace boost {
namespace unordered_detail {
@@ -179,7 +179,7 @@
} // namespace boost::unordered_detail
} // namespace boost
-#undef BOOST_HASH_BORLAND_BOOL
-#undef BOOST_HASH_MSVC_RESET_PTR
+#undef BOOST_UNORDERED_BORLAND_BOOL
+#undef BOOST_UNORDERED_MSVC_RESET_PTR
#endif // BOOST_UNORDERED_DETAIL_HASH_TABLE_HPP_INCLUDED
Modified: branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp (original)
+++ branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -4,7 +4,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)
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#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
@@ -32,10 +32,13 @@
class BOOST_UNORDERED_TABLE_DATA
{
public:
+ typedef BOOST_UNORDERED_TABLE_DATA data;
+
struct node_base;
struct node;
struct bucket;
typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
typedef Alloc value_allocator;
@@ -64,7 +67,7 @@
// It's a sort of strict typedef.
struct link_ptr {
- link_ptr() : ptr_() { BOOST_HASH_MSVC_RESET_PTR(ptr_); }
+ link_ptr() : ptr_() { BOOST_UNORDERED_MSVC_RESET_PTR(ptr_); }
explicit link_ptr(bucket_ptr p) : ptr_(p) {}
bucket_reference operator*() const { return *ptr_; }
bucket* operator->() const { return &*ptr_; }
@@ -88,7 +91,7 @@
bucket() : next_()
{
- BOOST_HASH_MSVC_RESET_PTR(next_);
+ BOOST_UNORDERED_MSVC_RESET_PTR(next_);
}
bucket(bucket const& x) : next_(x.next_)
@@ -109,11 +112,11 @@
struct node_base : bucket
{
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
public:
node_base() : group_prev_()
{
- BOOST_HASH_MSVC_RESET_PTR(group_prev_);
+ BOOST_UNORDERED_MSVC_RESET_PTR(group_prev_);
}
link_ptr group_prev_;
@@ -180,7 +183,7 @@
: allocators_(a),
node_(), value_constructed_(false), node_base_constructed_(false)
{
- BOOST_HASH_MSVC_RESET_PTR(node_);
+ BOOST_UNORDERED_MSVC_RESET_PTR(node_);
}
~node_constructor()
@@ -237,27 +240,17 @@
// Methods for navigating groups of elements with equal keys.
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#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 last_in_group(link_ptr n) {
- BOOST_ASSERT(BOOST_HASH_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
- return prev_in_group(n);
- }
-
- // pre: Must be pointing to the first node in a group.
static inline link_ptr& next_group(link_ptr n) {
- BOOST_ASSERT(BOOST_HASH_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
+ BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
return prev_in_group(n)->next_;
}
#else
- static inline link_ptr last_in_group(link_ptr n) {
- return n;
- }
-
static inline link_ptr& next_group(link_ptr n) {
BOOST_ASSERT(n);
return n->next_;
@@ -285,8 +278,8 @@
iterator_base()
: bucket_(), node_()
{
- BOOST_HASH_MSVC_RESET_PTR(bucket_);
- BOOST_HASH_MSVC_RESET_PTR(node_);
+ BOOST_UNORDERED_MSVC_RESET_PTR(bucket_);
+ BOOST_UNORDERED_MSVC_RESET_PTR(node_);
}
explicit iterator_base(bucket_ptr b)
@@ -320,6 +313,16 @@
node_ = bucket_->next_;
}
}
+
+ void incrementGroup()
+ {
+ node_ = data::next_group(node_);
+
+ while (!node_) {
+ ++bucket_;
+ node_ = bucket_->next_;
+ }
+ }
};
// Member Variables
@@ -345,7 +348,7 @@
// Creates an extra bucket to act as a sentinel.
constructor.construct(bucket(), bucket_count_ + 1);
- cached_begin_bucket_ = constructor.get() + bucket_count_;
+ cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count_);
// Set up the sentinel.
cached_begin_bucket_->next_ = link_ptr(cached_begin_bucket_);
@@ -368,7 +371,7 @@
// Creates an extra bucket to act as a sentinel.
constructor.construct(bucket(), bucket_count_ + 1);
- cached_begin_bucket_ = constructor.get() + bucket_count_;
+ cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count_);
// Set up the sentinel
cached_begin_bucket_->next_ = link_ptr(cached_begin_bucket_);
@@ -383,15 +386,16 @@
{
if(buckets_) {
bucket_ptr begin = cached_begin_bucket_;
- bucket_ptr end = buckets_ + bucket_count_;
+ bucket_ptr end = buckets_end();
while(begin != end) {
clear_bucket(begin);
++begin;
}
// Destroy an extra bucket for the sentinels.
- for(size_type i2 = 0; i2 < bucket_count_ + 1; ++i2)
- allocators_.bucket_alloc_.destroy(buckets_ + i2);
+ ++end;
+ for(begin = buckets_; begin != end; ++begin)
+ allocators_.bucket_alloc_.destroy(begin);
allocators_.bucket_alloc_.deallocate(buckets_, bucket_count_ + 1);
}
@@ -413,18 +417,24 @@
std::swap(size_, other.size_);
}
- // Return the bucket index for a hashed value.
+ // Return the bucket for a hashed value.
//
// no throw
- size_type index_from_hash(size_type hashed) const
+ bucket_ptr bucket_from_hash(size_type hashed) const
{
- return hashed % bucket_count_;
+ return buckets_ + static_cast<difference_type>(hashed % bucket_count_);
}
// Begin & End
//
// no throw
+ bucket_ptr buckets_end() const
+ {
+ return buckets_ + static_cast<difference_type>(bucket_count_);
+ }
+
+
iterator_base begin() const
{
return size_
@@ -434,7 +444,7 @@
iterator_base end() const
{
- return iterator_base(buckets_ + bucket_count_);
+ return iterator_base(buckets_end());
}
link_ptr begin(size_type n) const
@@ -455,17 +465,17 @@
// Bucket Size
// no throw
- size_type node_count(link_ptr it) const
+ static inline size_type node_count(link_ptr it)
{
size_type count = 0;
- while(BOOST_HASH_BORLAND_BOOL(it)) {
+ while(BOOST_UNORDERED_BORLAND_BOOL(it)) {
++count;
it = it->next_;
}
return count;
}
- size_type node_count(link_ptr it1, link_ptr it2) const
+ static inline size_type node_count(link_ptr it1, link_ptr it2)
{
size_type count = 0;
while(it1 != it2) {
@@ -480,19 +490,13 @@
return node_count(begin(n));
}
-#if BOOST_UNORDERED_HASH_EQUIVALENT
- static size_type group_count(link_ptr it)
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
+ static inline size_type group_count(link_ptr it)
{
- size_type count = 0;
- link_ptr first = it;
- do {
- ++count;
- it = prev_in_group(it);
- } while (it != first); // throws, strong
- return count;
+ return node_count(it, next_group(it));
}
#else
- static size_type group_count(link_ptr)
+ static inline size_type group_count(link_ptr)
{
return 1;
}
@@ -504,7 +508,7 @@
//
// no throw
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
static link_ptr* get_for_erase(iterator_base r)
{
link_ptr n = r.node_;
@@ -538,7 +542,7 @@
//
// no throw
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
void link_node(link_ptr n, link_ptr pos)
{
node& node_ref = get_node(n);
@@ -584,7 +588,7 @@
}
#endif
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
void unlink_node(iterator_base it)
{
link_ptr* pos = get_for_erase(it);
@@ -595,7 +599,7 @@
// The deleted node is the sole node in the group, so
// no need to unlink it from a group.
}
- else if(BOOST_HASH_BORLAND_BOOL(next) && prev_in_group(next) == *pos)
+ 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.
@@ -619,8 +623,7 @@
{
size_type count = group_count(*pos);
size_ -= count;
- link_ptr last = last_in_group(*pos);
- *pos = last->next_;
+ *pos = next_group(*pos);
return count;
}
#else
@@ -668,11 +671,11 @@
size_ -= node_count(ptr, end.node_);
}
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#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).
- link_ptr split_group(link_ptr 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.
@@ -692,23 +695,23 @@
return start;
}
- void split_group(link_ptr split1, link_ptr split2)
+ 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_HASH_BORLAND_BOOL(begin1) && split1 == begin2) {
+ 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
- void split_group(link_ptr)
+ static inline void split_group(link_ptr)
{
}
- void split_group(link_ptr, link_ptr)
+ static inline void split_group(link_ptr, link_ptr)
{
}
#endif
@@ -737,7 +740,7 @@
return iterator_base(base, n);
}
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
iterator_base create_node(value_type const& v, iterator_base position)
{
// throws, strong exception-safety:
@@ -755,7 +758,7 @@
link_ptr n = construct_node(v);
// Rest is no throw
- if(BOOST_HASH_BORLAND_BOOL(position))
+ if(BOOST_UNORDERED_BORLAND_BOOL(position))
link_node(n, position);
else
link_node_in_bucket(n, base);
@@ -764,7 +767,7 @@
}
#endif
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
void copy_group(link_ptr it, bucket_ptr dst)
{
link_ptr end = next_group(it);
@@ -804,7 +807,7 @@
}
}
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
void delete_group(link_ptr first_node)
{
delete_nodes(first_node, prev_in_group(first_node)->next_);
@@ -832,7 +835,7 @@
void clear()
{
bucket_ptr begin = cached_begin_bucket_;
- bucket_ptr end = buckets_ + bucket_count_;
+ bucket_ptr end = buckets_end();
size_ = 0;
cached_begin_bucket_ = end;
@@ -880,7 +883,8 @@
unlink_nodes(r1);
delete_to_bucket_end(r1.node_);
- for(bucket_ptr i = r1.bucket_ + 1; i != r2.bucket_; ++i) {
+ bucket_ptr i = r1.bucket_;
+ for(++i; i != r2.bucket_; ++i) {
size_ -= node_count(i->next_);
clear_bucket(i);
}
@@ -917,7 +921,7 @@
while (cached_begin_bucket_->empty())
++cached_begin_bucket_;
} else {
- cached_begin_bucket_ = buckets_ + bucket_count_;
+ cached_begin_bucket_ = buckets_end();
}
}
}
@@ -929,7 +933,7 @@
void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2)
{
BOOST_ASSERT(!(b1 < cached_begin_bucket_) && !(b2 < b1));
- BOOST_ASSERT(b2 == buckets_ + bucket_count_ || !b2->empty());
+ BOOST_ASSERT(b2 == buckets_end() || !b2->empty());
if(b1 == cached_begin_bucket_ && b1->empty())
cached_begin_bucket_ = b2;
@@ -985,6 +989,7 @@
typedef Pred key_equal;
typedef ValueType value_type;
typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
// iterators
@@ -1248,13 +1253,14 @@
size_type bucket(key_type const& k) const
{
// hash_function can throw:
- return this->index_from_hash(hash_function()(k));
+ return hash_function()(k) % this->bucket_count_;
}
+
// strong safety
bucket_ptr get_bucket(key_type const& k) const
{
- return this->buckets_ + bucket(k);
+ return this->buckets_ + static_cast<difference_type>(bucket(k));
}
// no throw
@@ -1416,7 +1422,7 @@
BOOST_ASSERT(dst.size_ == 0);
//BOOST_ASSERT(src.allocators_.node_alloc_ == dst.allocators_.node_alloc_);
- bucket_ptr end = src.buckets_ + src.bucket_count_;
+ bucket_ptr end = src.buckets_end();
for(; src.cached_begin_bucket_ != end;
++src.cached_begin_bucket_) {
@@ -1426,8 +1432,7 @@
// src_bucket to dst.
// This next line throws iff the hash function throws.
- bucket_ptr dst_bucket = dst.buckets_ +
- dst.index_from_hash(
+ bucket_ptr dst_bucket = dst.bucket_from_hash(
hf(extract_key(data::get_value(src_bucket->next_))));
link_ptr n = src_bucket->next_;
@@ -1444,17 +1449,17 @@
{
BOOST_ASSERT(dst.size_ == 0);
// no throw:
- bucket_ptr end = src.buckets_ + src.bucket_count_;
+ bucket_ptr end = src.buckets_end();
hasher const& hf = f.hash_function();
// no throw:
for(bucket_ptr i = src.cached_begin_bucket_; i != end; ++i) {
// no throw:
for(link_ptr it = src.begin(i);
- BOOST_HASH_BORLAND_BOOL(it); it = data::next_group(it)) {
+ BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it)) {
// hash function can throw.
- bucket_ptr dst_bucket = dst.buckets_ +
- dst.index_from_hash(hf(extract_key(data::get_value(it))));
+ bucket_ptr dst_bucket = dst.bucket_from_hash(
+ hf(extract_key(data::get_value(it))));
// throws, strong
dst.copy_group(it, dst_bucket);
}
@@ -1468,7 +1473,7 @@
// basic exception safety, if hash function throws
// strong otherwise.
-#if BOOST_UNORDERED_HASH_EQUIVALENT
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
// Insert (equivalent key containers)
@@ -1478,8 +1483,7 @@
{
key_type const& k = extract_key(v);
size_type hash_value = hash_function()(k);
- bucket_ptr bucket = this->buckets_
- + this->index_from_hash(hash_value);
+ bucket_ptr bucket = this->bucket_from_hash(hash_value);
link_ptr position = find_iterator(bucket, k);
// Create the node before rehashing in case it throws an
@@ -1490,7 +1494,7 @@
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(reserve(size() + 1))
- bucket = this->buckets_ + this->index_from_hash(hash_value);
+ bucket = this->bucket_from_hash(hash_value);
// Nothing after the point can throw.
@@ -1498,7 +1502,7 @@
// I'm relying on link_ptr not being invalidated by
// the rehash here.
- if(BOOST_HASH_BORLAND_BOOL(position))
+ if(BOOST_UNORDERED_BORLAND_BOOL(position))
this->link_node(n, position);
else
this->link_node_in_bucket(n, bucket);
@@ -1570,7 +1574,7 @@
bucket_ptr bucket = get_bucket(k);
link_ptr position = find_iterator(bucket, k);
- if(BOOST_HASH_BORLAND_BOOL(position))
+ if(BOOST_UNORDERED_BORLAND_BOOL(position))
this->link_node(a.release(), position);
else
this->link_node_in_bucket(a.release(), bucket);
@@ -1610,10 +1614,10 @@
typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
size_type hash_value = hash_function()(k);
- bucket_ptr bucket = this->buckets_ + this->index_from_hash(hash_value);
+ bucket_ptr bucket = this->bucket_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, k);
- if (BOOST_HASH_BORLAND_BOOL(pos))
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos))
return data::get_value(pos);
else
{
@@ -1626,8 +1630,8 @@
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
- if (reserve(size() + 1))
- bucket = this->buckets_ + this->index_from_hash(hash_value);
+ if(reserve(size() + 1))
+ bucket = this->bucket_from_hash(hash_value);
// Nothing after this point can throw.
@@ -1647,10 +1651,10 @@
// No side effects in this initial code
key_type const& k = extract_key(v);
size_type hash_value = hash_function()(k);
- bucket_ptr bucket = this->buckets_ + this->index_from_hash(hash_value);
+ bucket_ptr bucket = this->bucket_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, k);
- if (BOOST_HASH_BORLAND_BOOL(pos)) {
+ 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);
@@ -1667,7 +1671,7 @@
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(reserve(size() + 1))
- bucket = this->buckets_ + this->index_from_hash(hash_value);
+ bucket = this->bucket_from_hash(hash_value);
// Nothing after this point can throw.
@@ -1723,11 +1727,10 @@
for (; i != j; ++i) {
// No side effects in this initial code
size_type hash_value = hash_function()(extract_key(*i));
- bucket_ptr bucket = this->buckets_
- + this->index_from_hash(hash_value);
+ bucket_ptr bucket = this->bucket_from_hash(hash_value);
link_ptr pos = find_iterator(bucket, extract_key(*i));
- if (!BOOST_HASH_BORLAND_BOOL(pos)) {
+ if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
// Doesn't already exist, add to bucket.
// Side effects only in this block.
@@ -1740,7 +1743,7 @@
// throws, strong otherwise.
if(size() + 1 >= max_load_) {
reserve(size() + insert_size(i, j));
- bucket = this->buckets_ + this->index_from_hash(hash_value);
+ bucket = this->bucket_from_hash(hash_value);
}
// Nothing after this point can throw.
@@ -1782,7 +1785,7 @@
size_type count(key_type const& k) const
{
link_ptr it = find_iterator(k); // throws, strong
- return BOOST_HASH_BORLAND_BOOL(it) ? data::group_count(it) : 0;
+ return BOOST_UNORDERED_BORLAND_BOOL(it) ? data::group_count(it) : 0;
}
// find
@@ -1793,7 +1796,7 @@
bucket_ptr bucket = get_bucket(k);
link_ptr it = find_iterator(bucket, k);
- if (BOOST_HASH_BORLAND_BOOL(it))
+ if (BOOST_UNORDERED_BORLAND_BOOL(it))
return iterator_base(bucket, it);
else
return this->end();
@@ -1804,7 +1807,7 @@
bucket_ptr bucket = get_bucket(k);
link_ptr it = find_iterator(bucket, k);
- if (BOOST_HASH_BORLAND_BOOL(it))
+ if (BOOST_UNORDERED_BORLAND_BOOL(it))
return data::get_value(it);
else
throw std::out_of_range("Unable to find key in unordered_map.");
@@ -1817,10 +1820,10 @@
{
bucket_ptr bucket = get_bucket(k);
link_ptr it = find_iterator(bucket, k);
- if (BOOST_HASH_BORLAND_BOOL(it)) {
+ if (BOOST_UNORDERED_BORLAND_BOOL(it)) {
iterator_base first(iterator_base(bucket, it));
- iterator_base second(iterator_base(bucket, this->last_in_group(it)));
- second.increment();
+ iterator_base second(first);
+ second.incrementGroup();
return std::pair<iterator_base, iterator_base>(first, second);
}
else {
@@ -1848,7 +1851,7 @@
key_type const& k) const
{
link_ptr it = this->begin(bucket);
- while (BOOST_HASH_BORLAND_BOOL(it) && !equal(k, data::get_value(it)))
+ while (BOOST_UNORDERED_BORLAND_BOOL(it) && !equal(k, data::get_value(it)))
it = data::next_group(it);
return it;
@@ -1858,7 +1861,7 @@
link_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const
{
link_ptr* it = &bucket->next_;
- while(BOOST_HASH_BORLAND_BOOL(*it) && !equal(k, data::get_value(*it)))
+ while(BOOST_UNORDERED_BORLAND_BOOL(*it) && !equal(k, data::get_value(*it)))
it = &data::next_group(*it);
return it;
@@ -1899,7 +1902,7 @@
public:
BOOST_UNORDERED_LOCAL_ITERATOR() : ptr_() {
- BOOST_HASH_MSVC_RESET_PTR(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
@@ -1934,7 +1937,7 @@
public:
BOOST_UNORDERED_CONST_LOCAL_ITERATOR() : ptr_() {
- BOOST_HASH_MSVC_RESET_PTR(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_) {}
Modified: branches/unordered/trunk/doc/Jamfile.v2
==============================================================================
--- branches/unordered/trunk/doc/Jamfile.v2 (original)
+++ branches/unordered/trunk/doc/Jamfile.v2 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -8,8 +8,8 @@
<dependency>../libs/unordered/doc//unordered
<implicit-dependency>../libs/unordered/doc//unordered
- #<dependency>../libs/functional/hash/doc//hash
- #<implicit-dependency>../libs/functional/hash/doc//hash
+ <dependency>../libs/functional/hash/doc//hash
+ <implicit-dependency>../libs/functional/hash/doc//hash
<xsl:param>boost.libraries=../../libs/libraries.htm
;
Modified: branches/unordered/trunk/doc/src/boost.xml
==============================================================================
--- branches/unordered/trunk/doc/src/boost.xml (original)
+++ branches/unordered/trunk/doc/src/boost.xml 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -5,5 +5,5 @@
<title>The Boost C++ Unordered Containers Library Documentation</title>
<xi:include href="unordered.xml"/>
- <!-- <xi:include href="hash.xml"/> -->
+ <xi:include href="hash.xml"/>
</boostbook>
Modified: branches/unordered/trunk/libs/unordered/doc/buckets.qbk
==============================================================================
--- branches/unordered/trunk/libs/unordered/doc/buckets.qbk (original)
+++ branches/unordered/trunk/libs/unordered/doc/buckets.qbk 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -20,17 +20,16 @@
then the number of buckets, so that container applies another transformation to
that value to choose a bucket to place the element in.
-If at a later date the container wants to find an element in the container it
-just has to apply the same process to the element's key to discover which
-bucket it is in. If the hash function has worked well the elements will be
-evenly distributed amongst the buckets so it will only have to examine a small
-number of elements.
+Retreiving the elements for a given key is simple. The same process is applied
+to the key to find the correct bucket. Then the key is compared with the
+elements in the bucket to find any elements that match. If the hash
+function has worked well the elements will be evenly distributed amongst the
+buckets so only a small number of elements will need to be examined.
You can see in the diagram that `A` & `D` have been placed in the same bucket.
-This means that when looking for these elements, of another element that would
-be placed in the same bucket, up to 2 comparison have to be made, making
-searching slower. This is known as a collision. To keep things fast we try to
-keep these to a minimum.
+When looking for elements in this bucket up to 2 comparisons are made, making
+the search slower. This is known as a collision. To keep things fast we try to
+keep collisions to a minimum.
[table Methods for Accessing Buckets
[[Method] [Description]]
@@ -57,6 +56,8 @@
local_iterator end(size_type n);
const_local_iterator begin(size_type n) const;
const_local_iterator end(size_type n) const;
+ const_local_iterator cbegin(size_type n) const;
+ const_local_iterator cend(size_type n) const;
``]
[Return begin and end iterators for bucket `n`.]
]
@@ -65,42 +66,31 @@
[h2 Controlling the number of buckets]
As more elements are added to an unordered associative container, the number
-of elements in the buckets will increase causing performance to get worse. To
-combat this the containers increase the bucket count as elements are inserted.
-
-The standard gives you two methods to influence the bucket count. First you can
-specify the minimum number of buckets in the constructor, and later, by calling
-`rehash`.
-
-The other method is the `max_load_factor` member function. The 'load factor'
-is the average number of elements per bucket, `max_load_factor` can be used
-to give a /hint/ of a value that the load factor should be kept below. The
-draft standard doesn't actually require the container to pay much attention
-to this value. The only time the load factor is /required/ to be less than the
-maximum is following a call to `rehash`. But most implementations will probably
-try to keep the number of elements below the max load factor, and set the
-maximum load factor something the same or near to your hint - unless your hint
-is unreasonably small.
-
-It is not specified anywhere how member functions other than `rehash` affect
-the bucket count, although `insert` is only allowed to invalidate iterators
-when the insertion causes the load factor to reach the maximum. Which will
-typically mean that insert will only change the number of buckets when an
-insert causes this.
-
-In a similar manner to using `reserve` for `vector`s, it can be a good idea
-to call `rehash` before inserting a large number of elements. This will get
-the expensive rehashing out of the way and let you store iterators, safe in
-the knowledge that they won't be invalidated. If you are inserting `n`
-elements into container `x`, you could first call:
-
- x.rehash((x.size() + n) / x.max_load_factor() + 1);
-
-[blurb Note: `rehash`'s argument is the number of buckets, not the number of
-elements, which is why the new size is divided by the maximum load factor. The
-+ 1 guarantees there is no invalidation; without it, reallocation could occur
-if the number of bucket exactly divides the target size, since the container is
-allowed to rehash when the load factor is equal to the maximum load factor.]
+of elements in the buckets will increase causing performance to degrade.
+To combat this the containers increase the bucket count as elements are inserted.
+You can also tell the container to change the bucket count (if required) by
+calling `rehash`.
+
+The standard leaves a lot of freedom to the implementor to decide how the
+number of buckets are chosen, but it does make some requirements based on the
+container's 'load factor', the average number of elements per bucket.
+Containers also have a 'maximum load factor' which they should try to keep the
+load factor below.
+
+You can't control the bucket count directly but there are two ways to
+influence it:
+
+* Specify the minimum number of buckets when constructing a container or
+ when calling `rehash`.
+* Suggest a maximum load factor by calling `max_load_factor`.
+
+`max_load_factor` doesn't let you set the maximum load factor yourself, it just
+lets you give a /hint/. And even then, the draft standard doesn't actually
+require the container to pay much attention to this value. The only time the
+load factor is /required/ to be less than the maximum is following a call to
+`rehash`. But most implementations will try to keep the number of elements
+below the max load factor, and set the maximum load factor to be the same as
+or close to the hint - unless your hint is unreasonably small or large.
[table Methods for Controlling Bucket Size
[[Method] [Description]]
@@ -125,4 +115,24 @@
]
+It is not specified how member functions other than `rehash` affect
+the bucket count, although `insert` is only allowed to invalidate iterators
+when the insertion causes the load factor to be greater than or equal to the
+maximum load factor. For most implementations this means that insert will only
+change the number of buckets when this happens.
+
+In a similar manner to using `reserve` for `vector`s, it can be a good idea
+to call `rehash` before inserting a large number of elements. This will get
+the expensive rehashing out of the way and let you store iterators, safe in
+the knowledge that they won't be invalidated. If you are inserting `n`
+elements into container `x`, you could first call:
+
+ x.rehash((x.size() + n) / x.max_load_factor() + 1);
+
+[blurb Note: `rehash`'s argument is the minimum number of buckets, not the
+number of elements, which is why the new size is divided by the maximum load factor. The
+`+ 1` guarantees there is no invalidation; without it, reallocation could occur
+if the number of bucket exactly divides the target size, since the container is
+allowed to rehash when the load factor is equal to the maximum load factor.]
+
[endsect]
Modified: branches/unordered/trunk/libs/unordered/doc/intro.qbk
==============================================================================
--- branches/unordered/trunk/libs/unordered/doc/intro.qbk (original)
+++ branches/unordered/trunk/libs/unordered/doc/intro.qbk 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -28,11 +28,12 @@
Also, the existing containers require a 'less than' comparison object
to order their elements. For some data types this is impossible to implement
-or isn't practical. For a hash table you need an equality function
+or isn't practical. In contrast, a hash table only needs an equality function
and a hash function for the key.
-So the __tr1__ introduced the unordered associative containers, which are
-implemented using hash tables, and they have now been added to the __draft__.
+With this in mind, the __tr1__ introduced the unordered associative containers,
+which are implemented using hash tables, and they have now been added to the
+__draft__.
This library supplies an almost complete implementation of the specification in
the __draft__, (it doesn't support `emplace` yet, see the [link
@@ -110,6 +111,7 @@
three,3
missing,0
-There are other differences, which will be detailed later.
+There are other differences, which are listed in the
+[link unordered.comparison Comparison with Associative Containers] section.
[endsect]
Modified: branches/unordered/trunk/libs/unordered/doc/ref.xml
==============================================================================
--- branches/unordered/trunk/libs/unordered/doc/ref.xml (original)
+++ branches/unordered/trunk/libs/unordered/doc/ref.xml 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -1718,7 +1718,7 @@
<para>A reference to <code>x.second</code> where <code>x</code> is the (unique) element whose key is equivalent to <code>k</code>.</para>
</returns>
<throws>
- <para>An exception object of type <code>out_of_range</code> if no such element is present.</para>
+ <para>An exception object of type <code>std::out_of_range</code> if no such element is present.</para>
</throws>
<notes>
<para>This is not specified in the draft standard, but that is probably an oversight. The issue has been raised in
Modified: branches/unordered/trunk/libs/unordered/test/container/Jamfile.v2
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/container/Jamfile.v2 (original)
+++ branches/unordered/trunk/libs/unordered/test/container/Jamfile.v2 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -8,6 +8,8 @@
project unordered-test/container
: requirements
<toolset>intel-linux:"<cxxflags>-strict_ansi -cxxlib-icc"
+ <toolset>gcc:<cxxflags>-Wsign-promo
+ <toolset>msvc:<cxxflags>/W4
;
test-suite container-tests
Modified: branches/unordered/trunk/libs/unordered/test/exception/Jamfile.v2
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/exception/Jamfile.v2 (original)
+++ branches/unordered/trunk/libs/unordered/test/exception/Jamfile.v2 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -10,6 +10,7 @@
project unordered-test/exception-tests
: requirements
<toolset>intel-linux:"<cxxflags>-strict_ansi -cxxlib-icc"
+ <toolset>gcc:<cxxflags>-Wsign-promo
;
test-suite unordered-tests
Modified: branches/unordered/trunk/libs/unordered/test/helpers/generators.hpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/helpers/generators.hpp (original)
+++ branches/unordered/trunk/libs/unordered/test/helpers/generators.hpp 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -58,7 +58,7 @@
inline char generate(char const*)
{
using namespace std;
- return (rand() >> 1) % (128-32) + 32;
+ return static_cast<char>((rand() >> 1) % (128-32) + 32);
}
inline signed char generate(signed char const*)
Modified: branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2 (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -8,6 +8,8 @@
project unordered-test/unordered
: requirements
<toolset>intel-linux:"<cxxflags>-strict_ansi -cxxlib-icc"
+ <toolset>gcc:<cxxflags>-Wsign-promo
+ <toolset>msvc:<cxxflags>/W4
;
test-suite unordered-tests
Modified: branches/unordered/trunk/libs/unordered/test/unordered/compile_tests.cpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/compile_tests.cpp (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/compile_tests.cpp 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -59,7 +59,7 @@
}
template <class X, class Key, class T>
-void unordered_map_functions(X&, Key const& k, T const& t)
+void unordered_map_functions(X&, Key const& k, T const&)
{
typedef typename X::mapped_type mapped_type;
Modified: branches/unordered/trunk/release.sh
==============================================================================
--- branches/unordered/trunk/release.sh (original)
+++ branches/unordered/trunk/release.sh 2008-01-01 15:21:04 EST (Tue, 01 Jan 2008)
@@ -16,6 +16,7 @@
cp $BOOST_ROOT/doc/html/*.css $UNORDERED_DST/doc/html/
cp $BOOST_ROOT/doc/html/images/*.png $UNORDERED_DST/doc/html/images/
+rm -r $UNORDERED_DST/libs/functional
rm -r $UNORDERED_DST/bin.v2
rm $UNORDERED_DST/release.sh
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