Subject: [Boost-commit] svn:boost r55990 - trunk/boost/unordered/detail
From: daniel_james_at_[hidden]
Date: 2009-09-03 03:36:22
Author: danieljames
Date: 2009-09-03 03:36:21 EDT (Thu, 03 Sep 2009)
New Revision: 55990
URL: http://svn.boost.org/trac/boost/changeset/55990
Log:
Combine hash_structure and hash_table_manager.
Removed:
trunk/boost/unordered/detail/structure.hpp
Text files modified:
trunk/boost/unordered/detail/fwd.hpp | 121 +++++++++----------------
trunk/boost/unordered/detail/insert.hpp | 16 ++-
trunk/boost/unordered/detail/manager.hpp | 190 +++++++++++++++++++++++++++++++++++----
trunk/boost/unordered/detail/node.hpp | 6
trunk/boost/unordered/detail/table.hpp | 19 ++-
5 files changed, 241 insertions(+), 111 deletions(-)
Modified: trunk/boost/unordered/detail/fwd.hpp
==============================================================================
--- trunk/boost/unordered/detail/fwd.hpp (original)
+++ trunk/boost/unordered/detail/fwd.hpp 2009-09-03 03:36:21 EDT (Thu, 03 Sep 2009)
@@ -152,74 +152,11 @@
template <class NodeBase, class ValueType>
class hash_node : public NodeBase, public value_base<ValueType>
{
+ public:
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
- {
- 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
-
- 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
@@ -256,22 +193,22 @@
// methods (other than getters and setters).
template <class A, class G>
- struct hash_table_manager :
- hash_structure<A, G>
+ struct hash_table_manager
{
// 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 BOOST_DEDUCED_TYPENAME A::value_type value_type;
+ typedef hash_bucket<A> bucket;
+ typedef BOOST_DEDUCED_TYPENAME G::BOOST_NESTED_TEMPLATE base<A>::type
+ node_base;
typedef hash_node<node_base, value_type> node;
+
+ typedef BOOST_DEDUCED_TYPENAME node::bucket_allocator bucket_allocator;
+ typedef BOOST_DEDUCED_TYPENAME node::bucket_ptr bucket_ptr;
+ typedef BOOST_DEDUCED_TYPENAME node::node_ptr node_ptr;
+
typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type node_allocator;
typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr;
@@ -279,6 +216,10 @@
// Members
+ bucket_ptr buckets_;
+ bucket_ptr cached_begin_bucket_;
+ std::size_t size_;
+ std::size_t bucket_count_;
boost::compressed_pair<bucket_allocator, node_allocator> allocators_;
// Data access
@@ -306,11 +247,21 @@
~hash_table_manager();
// no throw
+ void swap(hash_table_manager& other);
void move(hash_table_manager& other);
- // Methods
-
+ // Buckets
+
void create_buckets(std::size_t bucket_count);
+ 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;
+ bucket_ptr get_bucket(std::size_t n) const;
+ node_ptr bucket_begin(std::size_t n) const;
+ node_ptr bucket_end(std::size_t) const;
// Alloc/Dealloc
@@ -331,6 +282,24 @@
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
+ //
+ // 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;
};
template <class H, class P, class A, class G, class K>
Modified: trunk/boost/unordered/detail/insert.hpp
==============================================================================
--- trunk/boost/unordered/detail/insert.hpp (original)
+++ trunk/boost/unordered/detail/insert.hpp 2009-09-03 03:36:21 EDT (Thu, 03 Sep 2009)
@@ -70,7 +70,9 @@
inline node_ptr add_node(node_constructor& a, bucket_ptr bucket)
{
node_ptr n = a.release();
- this->link_node_in_bucket(n, bucket);
+ node::add_to_bucket(n, *bucket);
+ ++this->size_;
+ if(bucket < this->cached_begin_bucket_) this->cached_begin_bucket_ = bucket;
return n;
}
@@ -328,10 +330,14 @@
inline node_ptr add_node(node_constructor& a, bucket_ptr bucket, node_ptr pos)
{
node_ptr n = a.release();
- if(BOOST_UNORDERED_BORLAND_BOOL(pos))
- this->link_node(n, pos);
- else
- this->link_node_in_bucket(n, bucket);
+ if(BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ node::add_after_node(n, pos);
+ }
+ else {
+ node::add_to_bucket(n, *bucket);
+ if(bucket < this->cached_begin_bucket_) this->cached_begin_bucket_ = bucket;
+ }
+ ++this->size_;
return n;
}
Modified: trunk/boost/unordered/detail/manager.hpp
==============================================================================
--- trunk/boost/unordered/detail/manager.hpp (original)
+++ trunk/boost/unordered/detail/manager.hpp 2009-09-03 03:36:21 EDT (Thu, 03 Sep 2009)
@@ -9,7 +9,7 @@
#include <boost/config.hpp>
#include <boost/assert.hpp>
-#include <boost/unordered/detail/structure.hpp>
+#include <boost/unordered/detail/node.hpp>
namespace boost { namespace unordered_detail {
@@ -30,19 +30,19 @@
template <class A, class G>
hash_table_manager<A, G>::hash_table_manager()
- : structure(), allocators_() {}
+ : buckets_(), cached_begin_bucket_(), size_(), allocators_() {}
template <class A, class G>
hash_table_manager<A, G>::hash_table_manager(value_allocator const& a)
- : structure(), allocators_(a,a) {}
+ : buckets_(), cached_begin_bucket_(), size_(), allocators_(a,a) {}
template <class A, class G>
hash_table_manager<A, G>::hash_table_manager(hash_table_manager const& h)
- : structure(), allocators_(h.allocators_) {}
+ : buckets_(), cached_begin_bucket_(), size_(), allocators_(h.allocators_) {}
template <class A, class G>
hash_table_manager<A, G>::hash_table_manager(hash_table_manager& x, move_tag)
- : structure(), allocators_(x.allocators_)
+ : buckets_(), cached_begin_bucket_(), size_(), allocators_(x.allocators_)
{
this->buckets_ = x.buckets_;
this->cached_begin_bucket_ = x.cached_begin_bucket_;
@@ -56,7 +56,7 @@
template <class A, class G>
hash_table_manager<A, G>::hash_table_manager(hash_table_manager& x, value_allocator const& a, move_tag) :
- structure(), allocators_(a,a)
+ buckets_(), cached_begin_bucket_(), size_(), allocators_(a,a)
{
if(this->node_alloc() == x.node_alloc()) {
this->buckets_ = x.buckets_;
@@ -78,8 +78,9 @@
// no throw
template <class A, class G>
- void hash_table_manager<A, G>::move(hash_table_manager& other)
+ inline void hash_table_manager<A, G>::move(hash_table_manager& other)
{
+ BOOST_ASSERT(node_alloc() == other.node_alloc());
delete_buckets();
this->buckets_ = other.buckets_;
this->cached_begin_bucket_ = other.cached_begin_bucket_;
@@ -91,6 +92,131 @@
other.bucket_count_ = 0;
}
+ template <class A, class G>
+ inline void hash_table_manager<A, G>::swap(hash_table_manager<A, G>& other)
+ {
+ BOOST_ASSERT(node_alloc() == other.node_alloc());
+ std::swap(buckets_, other.buckets_);
+ std::swap(cached_begin_bucket_, other.cached_begin_bucket_);
+ std::swap(size_, other.size_);
+ std::swap(bucket_count_, other.bucket_count_);
+ }
+
+ // Buckets
+
+ template <class A, class G>
+ inline std::size_t hash_table_manager<A, G>::bucket_count() const
+ {
+ return bucket_count_;
+ }
+
+ template <class A, class G>
+ inline std::size_t hash_table_manager<A, G>::bucket_from_hash(std::size_t hashed) const
+ {
+ return hashed % bucket_count_;
+ }
+
+ template <class A, class G>
+ inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::bucket_ptr
+ hash_table_manager<A, G>::bucket_ptr_from_hash(std::size_t hashed) const
+ {
+ return buckets_ + static_cast<std::ptrdiff_t>(
+ bucket_from_hash(hashed));
+ }
+
+ template <class A, class G>
+ inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::bucket_ptr
+ hash_table_manager<A, G>::buckets_begin() const
+ {
+ return buckets_;
+ }
+
+ template <class A, class G>
+ inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::bucket_ptr
+ hash_table_manager<A, G>::buckets_end() const
+ {
+ return buckets_ + static_cast<std::ptrdiff_t>(bucket_count_);
+ }
+
+ template <class A, class G>
+ inline std::size_t hash_table_manager<A, G>::bucket_size(std::size_t index) const
+ {
+ bucket_ptr ptr = (buckets_ + static_cast<std::ptrdiff_t>(index))->next_;
+ std::size_t count = 0;
+ while(ptr) {
+ ++count;
+ ptr = next_node(ptr);
+ }
+ return count;
+ }
+
+ template <class A, class G>
+ inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::bucket_ptr
+ hash_table_manager<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_table_manager<A, G>::node_ptr
+ hash_table_manager<A, G>::bucket_begin(std::size_t n) const
+ {
+ return (buckets_ + static_cast<std::ptrdiff_t>(n))->next_;
+ }
+
+ template <class A, class G>
+ inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::node_ptr
+ hash_table_manager<A, G>::bucket_end(std::size_t) const
+ {
+ return node_ptr();
+ }
+
+ // recompute_begin_bucket
+ //
+ // After an erase cached_begin_bucket_ might be left pointing to
+ // an empty bucket, so this is called to update it
+ //
+ // no throw
+
+ template <class A, class G>
+ inline void hash_table_manager<A, G>::recompute_begin_bucket(bucket_ptr b)
+ {
+ BOOST_ASSERT(!(b < cached_begin_bucket_));
+
+ if(b == cached_begin_bucket_)
+ {
+ if (size_ != 0) {
+ while (!cached_begin_bucket_->next_)
+ ++cached_begin_bucket_;
+ } else {
+ cached_begin_bucket_ = buckets_end();
+ }
+ }
+ }
+
+ // This is called when a range has been erased
+ //
+ // no throw
+
+ template <class A, class G>
+ inline void hash_table_manager<A, G>::recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2)
+ {
+ BOOST_ASSERT(!(b1 < cached_begin_bucket_) && !(b2 < b1));
+ BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(b2->next_));
+
+ if(b1 == cached_begin_bucket_ && !b1->next_)
+ cached_begin_bucket_ = b2;
+ }
+
+ // no throw
+ template <class A, class G>
+ inline float hash_table_manager<A, G>::load_factor() const
+ {
+ BOOST_ASSERT(bucket_count_ != 0);
+ return static_cast<float>(size_)
+ / static_cast<float>(bucket_count_);
+ }
+
// Construct/destruct
template <class A, class G>
@@ -117,7 +243,7 @@
}
template <class A, class G>
- void hash_table_manager<A, G>::destruct_node(node_ptr b)
+ inline void hash_table_manager<A, G>::destruct_node(node_ptr b)
{
node* raw_ptr = static_cast<node*>(&*b);
BOOST_UNORDERED_DESTRUCT(&raw_ptr->value(), value_type);
@@ -129,13 +255,13 @@
// Delete and clear buckets
template <class A, class G>
- void hash_table_manager<A, G>::delete_group(node_ptr first_node)
+ inline void hash_table_manager<A, G>::delete_group(node_ptr first_node)
{
delete_nodes(first_node, node::next_group(first_node));
}
template <class A, class G>
- void hash_table_manager<A, G>::delete_nodes(node_ptr begin, node_ptr end)
+ inline void hash_table_manager<A, G>::delete_nodes(node_ptr begin, node_ptr end)
{
while(begin != end) {
node_ptr node = begin;
@@ -145,7 +271,7 @@
}
template <class A, class G>
- void hash_table_manager<A, G>::delete_to_bucket_end(node_ptr begin)
+ inline void hash_table_manager<A, G>::delete_to_bucket_end(node_ptr begin)
{
while(BOOST_UNORDERED_BORLAND_BOOL(begin)) {
node_ptr node = begin;
@@ -155,7 +281,7 @@
}
template <class A, class G>
- void hash_table_manager<A, G>::clear_bucket(bucket_ptr b)
+ inline void hash_table_manager<A, G>::clear_bucket(bucket_ptr b)
{
node_ptr node_it = b->next_;
b->next_ = node_ptr();
@@ -179,7 +305,7 @@
}
template <class A, class G>
- void hash_table_manager<A, G>::delete_buckets()
+ inline void hash_table_manager<A, G>::delete_buckets()
{
clear();
@@ -202,7 +328,8 @@
BOOST_ASSERT(!r.is_end());
iterator_base next = r;
next.increment();
- this->unlink_node(r.bucket_, r.node_);
+ --this->size_;
+ node::unlink_node(*r.bucket_, r.node_);
destruct_node(r.node_);
// r has been invalidated but its bucket is still valid
this->recompute_begin_bucket(r.bucket_, next.bucket_);
@@ -210,14 +337,14 @@
}
template <class A, class G>
- std::size_t hash_table_manager<A, G>::erase_group(node_ptr* it, bucket_ptr bucket)
+ inline std::size_t hash_table_manager<A, G>::erase_group(node_ptr* it, bucket_ptr bucket)
{
node_ptr pos = *it;
- std::size_t count = this->unlink_group(it);
+ std::size_t count = node::group_count(*it);
+ this->size_ -= count;
+ node::unlink_group(it);
delete_group(pos);
-
this->recompute_begin_bucket(bucket);
-
return count;
}
@@ -230,7 +357,8 @@
BOOST_ASSERT(!r1.is_end());
if (r1.bucket_ == r2.bucket_) {
- this->unlink_nodes(r1.bucket_, r1.node_, r2.node_);
+ this->size_ -= node_count(r1.node_, r2.node_);
+ node::unlink_nodes(*r1.bucket_, r1.node_, r2.node_);
delete_nodes(r1.node_, r2.node_);
// No need to call recompute_begin_bucket because
@@ -241,7 +369,8 @@
else {
BOOST_ASSERT(r1.bucket_ < r2.bucket_);
- this->unlink_nodes(r1.bucket_, r1.node_, node_ptr());
+ this->size_ -= node_count(r1.node_, node_ptr());
+ node::unlink_nodes(*r1.bucket_, r1.node_, node_ptr());
delete_to_bucket_end(r1.node_);
bucket_ptr i = r1.bucket_;
@@ -252,7 +381,8 @@
if(!r2.is_end()) {
node_ptr first = r2.bucket_->next_;
- this->unlink_nodes(r2.bucket_, r2.node_);
+ this->size_ -= node_count(r2.bucket_->next_, r2.node_);
+ node::unlink_nodes(*r2.bucket_, r2.node_);
delete_nodes(first, r2.node_);
}
@@ -265,6 +395,24 @@
return r2;
}
+ ////////////////////////////////////////////////////////////////////////////
+ // hash_iterator_base implementation
+
+ template <class BucketPtr>
+ inline void hash_iterator_base<BucketPtr>::increment(node_ptr node) {
+ while(!node) {
+ ++bucket_;
+ node = bucket_->next_;
+ }
+
+ node_ = node;
+ }
+
+ template <class BucketPtr>
+ inline void hash_iterator_base<BucketPtr>::increment()
+ {
+ increment(next_node(node_));
+ }
}}
#endif
Modified: trunk/boost/unordered/detail/node.hpp
==============================================================================
--- trunk/boost/unordered/detail/node.hpp (original)
+++ trunk/boost/unordered/detail/node.hpp 2009-09-03 03:36:21 EDT (Thu, 03 Sep 2009)
@@ -79,13 +79,13 @@
}
template <class A>
- void ungrouped_node_base<A>::unlink_node(bucket& b, node_ptr node)
+ inline 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);
@@ -93,7 +93,7 @@
}
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;
}
Deleted: trunk/boost/unordered/detail/structure.hpp
==============================================================================
--- trunk/boost/unordered/detail/structure.hpp 2009-09-03 03:36:21 EDT (Thu, 03 Sep 2009)
+++ (empty file)
@@ -1,220 +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)
-
-// This contains the basic data structure, apart from the actual values. There's
-// no construction or deconstruction here. So this only depends on the pointer
-// type.
-
-#ifndef BOOST_UNORDERED_DETAIL_STRUCTURE_HPP_INCLUDED
-#define BOOST_UNORDERED_DETAIL_STRUCTURE_HPP_INCLUDED
-
-#include <boost/unordered/detail/node.hpp>
-
-namespace boost { namespace unordered_detail {
-
- ////////////////////////////////////////////////////////////////////////////
- // hash_structure implementation
-
- template <class A, class G>
- void hash_structure<A, G>::swap(hash_structure<A, G>& other)
- {
- std::swap(buckets_, other.buckets_);
- std::swap(cached_begin_bucket_, other.cached_begin_bucket_);
- std::swap(size_, other.size_);
- std::swap(bucket_count_, other.bucket_count_);
- }
-
- template <class A, class G>
- std::size_t hash_structure<A, G>::bucket_count() const
- {
- return bucket_count_;
- }
-
- template <class A, class G>
- std::size_t hash_structure<A, G>::bucket_from_hash(std::size_t hashed) const
- {
- return hashed % bucket_count_;
- }
-
- template <class A, class G>
- BOOST_DEDUCED_TYPENAME hash_structure<A, G>::bucket_ptr
- hash_structure<A, G>::bucket_ptr_from_hash(std::size_t hashed) const
- {
- return buckets_ + static_cast<std::ptrdiff_t>(
- bucket_from_hash(hashed));
- }
-
- template <class A, class G>
- BOOST_DEDUCED_TYPENAME hash_structure<A, G>::bucket_ptr
- hash_structure<A, G>::buckets_begin() const
- {
- return buckets_;
- }
-
- template <class A, class G>
- BOOST_DEDUCED_TYPENAME hash_structure<A, G>::bucket_ptr
- hash_structure<A, G>::buckets_end() const
- {
- return buckets_ + static_cast<std::ptrdiff_t>(bucket_count_);
- }
-
- template <class A, class G>
- std::size_t hash_structure<A, G>::bucket_size(std::size_t index) const
- {
- bucket_ptr ptr = (buckets_ + static_cast<std::ptrdiff_t>(index))->next_;
- std::size_t count = 0;
- while(ptr) {
- ++count;
- ptr = next_node(ptr);
- }
- return count;
- }
-
- // Link a node
-
- template <class A, class G>
- void hash_structure<A, G>::link_node(node_ptr n, node_ptr position)
- {
- node_base::add_after_node(n, position);
- ++size_;
- }
-
- template <class A, class G>
- void hash_structure<A, G>::link_node_in_bucket(node_ptr n, bucket_ptr bucket)
- {
- node_base::add_to_bucket(n, *bucket);
- ++size_;
- if(bucket < cached_begin_bucket_) cached_begin_bucket_ = bucket;
- }
-
- template <class A, class G>
- void hash_structure<A, G>::unlink_node(bucket_ptr bucket, node_ptr pos)
- {
- --size_;
- node_base::unlink_node(*bucket, pos);
- }
-
- template <class A, class G>
- void hash_structure<A, G>::unlink_nodes(
- bucket_ptr bucket, node_ptr begin, node_ptr end)
- {
- size_ -= node_count(begin, end);
- node_base::unlink_nodes(*bucket, begin, end);
- }
-
- template <class A, class G>
- void hash_structure<A, G>::unlink_nodes(bucket_ptr bucket, node_ptr end)
- {
- size_ -= node_count(bucket->next_, end);
- node_base::unlink_nodes(*bucket, end);
- }
-
- template <class A, class G>
- std::size_t hash_structure<A, G>::unlink_group(node_ptr* pos)
- {
- std::size_t count = node_base::group_count(*pos);
- size_ -= count;
- node_base::unlink_group(pos);
- return count;
- }
-
- template <class A, class G>
- void hash_structure<A, G>::link_group(
- node_ptr n, bucket_ptr bucket, std::size_t count)
- {
- node_base::add_group_to_bucket(n, *bucket);
- size_ += count;
- if(bucket < cached_begin_bucket_) cached_begin_bucket_ = bucket;
- }
-
- template <class A, class G>
- BOOST_DEDUCED_TYPENAME hash_structure<A, G>::bucket_ptr
- hash_structure<A, G>::get_bucket(std::size_t n) const
- {
- return buckets_ + static_cast<std::ptrdiff_t>(n);
- }
-
- template <class A, class G>
- BOOST_DEDUCED_TYPENAME hash_structure<A, G>::node_ptr
- hash_structure<A, G>::bucket_begin(std::size_t n) const
- {
- return (buckets_ + static_cast<std::ptrdiff_t>(n))->next_;
- }
-
- template <class A, class G>
- BOOST_DEDUCED_TYPENAME hash_structure<A, G>::node_ptr
- hash_structure<A, G>::bucket_end(std::size_t) const
- {
- return node_ptr();
- }
-
- // recompute_begin_bucket
- //
- // After an erase cached_begin_bucket_ might be left pointing to
- // an empty bucket, so this is called to update it
- //
- // no throw
-
- template <class A, class G>
- void hash_structure<A, G>::recompute_begin_bucket(bucket_ptr b)
- {
- BOOST_ASSERT(!(b < cached_begin_bucket_));
-
- if(b == cached_begin_bucket_)
- {
- if (size_ != 0) {
- while (!cached_begin_bucket_->next_)
- ++cached_begin_bucket_;
- } else {
- cached_begin_bucket_ = buckets_end();
- }
- }
- }
-
- // This is called when a range has been erased
- //
- // no throw
-
- template <class A, class G>
- void hash_structure<A, G>::recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2)
- {
- BOOST_ASSERT(!(b1 < cached_begin_bucket_) && !(b2 < b1));
- BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(b2->next_));
-
- if(b1 == cached_begin_bucket_ && !b1->next_)
- cached_begin_bucket_ = b2;
- }
-
- // no throw
- template <class A, class G>
- inline float hash_structure<A, G>::load_factor() const
- {
- BOOST_ASSERT(bucket_count_ != 0);
- return static_cast<float>(size_)
- / static_cast<float>(bucket_count_);
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // hash_iterator_base implementation
-
- template <class BucketPtr>
- inline void hash_iterator_base<BucketPtr>::increment(node_ptr node) {
- while(!node) {
- ++bucket_;
- node = bucket_->next_;
- }
-
- node_ = node;
- }
-
- template <class BucketPtr>
- inline void hash_iterator_base<BucketPtr>::increment()
- {
- increment(next_node(node_));
- }
-}}
-
-#endif
Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp (original)
+++ trunk/boost/unordered/detail/table.hpp 2009-09-03 03:36:21 EDT (Thu, 03 Sep 2009)
@@ -327,7 +327,7 @@
// basic exception safety
template <class H, class P, class A, class G, class K>
- bool hash_table<H, P, A, G, K>
+ inline bool hash_table<H, P, A, G, K>
::reserve(std::size_t n)
{
bool need_to_reserve = n >= this->max_load_;
@@ -339,7 +339,7 @@
// basic exception safety
template <class H, class P, class A, class G, class K>
- bool hash_table<H, P, A, G, K>
+ inline bool hash_table<H, P, A, G, K>
::reserve_for_insert(std::size_t n)
{
bool need_to_reserve = n >= this->max_load_;
@@ -419,8 +419,12 @@
hf(extractor::extract(node::get_value(src_bucket->next_))));
node_ptr n = src_bucket->next_;
- std::size_t count = this->unlink_group(&src_bucket->next_);
- dst.link_group(n, dst_bucket, count);
+ std::size_t count = node::group_count(src_bucket->next_);
+ this->size_ -= count;
+ dst.size_ += count;
+ node::unlink_group(&src_bucket->next_);
+ node::add_group_to_bucket(n, *dst_bucket);
+ if(dst_bucket < dst.cached_begin_bucket_) dst.cached_begin_bucket_ = dst_bucket;
}
}
}
@@ -454,11 +458,14 @@
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);
+ ++dst.size_;
+ if(dst_bucket < dst.cached_begin_bucket_) dst.cached_begin_bucket_ = dst_bucket;
for(it = next_node(it); it != group_end; it = next_node(it)) {
a.construct(node::get_value(it));
- dst.link_node(a.release(), n);
+ node::add_after_node(a.release(), n);
+ ++dst.size_;
}
}
}