|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r80632 - in branches/release: . boost boost/unordered boost/unordered/detail libs libs/unordered libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2012-09-22 13:28:56
Author: danieljames
Date: 2012-09-22 13:28:55 EDT (Sat, 22 Sep 2012)
New Revision: 80632
URL: http://svn.boost.org/trac/boost/changeset/80632
Log:
Unordered: Merge slightly simpler implementation.
Properties modified:
branches/release/ (props changed)
branches/release/boost/ (props changed)
branches/release/boost/unordered/ (props changed)
branches/release/libs/ (props changed)
branches/release/libs/unordered/ (props changed)
Text files modified:
branches/release/boost/unordered/detail/buckets.hpp | 12 ++++--
branches/release/boost/unordered/detail/equivalent.hpp | 7 +--
branches/release/boost/unordered/detail/table.hpp | 67 +++++++++++++++++----------------------
branches/release/boost/unordered/detail/unique.hpp | 29 ++--------------
branches/release/boost/unordered/unordered_map.hpp | 30 +++++++----------
branches/release/boost/unordered/unordered_set.hpp | 30 +++++++----------
branches/release/libs/unordered/test/unordered/insert_tests.cpp | 15 ++++++++
7 files changed, 82 insertions(+), 108 deletions(-)
Modified: branches/release/boost/unordered/detail/buckets.hpp
==============================================================================
--- branches/release/boost/unordered/detail/buckets.hpp (original)
+++ branches/release/boost/unordered/detail/buckets.hpp 2012-09-22 13:28:55 EDT (Sat, 22 Sep 2012)
@@ -444,10 +444,12 @@
base(b.node_alloc()),
nodes_()
{
- typename Table::previous_pointer prev = b.get_previous_start();
- nodes_ = static_cast<node_pointer>(prev->next_);
- prev->next_ = link_pointer();
- b.size_ = 0;
+ if (b.size_) {
+ typename Table::previous_pointer prev = b.get_previous_start();
+ nodes_ = static_cast<node_pointer>(prev->next_);
+ prev->next_ = link_pointer();
+ b.size_ = 0;
+ }
}
~node_holder();
@@ -508,7 +510,7 @@
}
}
- iterator get_start() const
+ iterator begin() const
{
return iterator(nodes_);
}
Modified: branches/release/boost/unordered/detail/equivalent.hpp
==============================================================================
--- branches/release/boost/unordered/detail/equivalent.hpp (original)
+++ branches/release/boost/unordered/detail/equivalent.hpp 2012-09-22 13:28:55 EDT (Sat, 22 Sep 2012)
@@ -234,11 +234,9 @@
Key const& k,
Pred const& eq) const
{
- if (!this->size_) return iterator();
-
std::size_t bucket_index =
policy::to_bucket(this->bucket_count_, key_hash);
- iterator n = this->get_start(bucket_index);
+ iterator n = this->begin(bucket_index);
for (;;)
{
@@ -293,9 +291,8 @@
bool equals(grouped_table_impl const& other) const
{
if(this->size_ != other.size_) return false;
- if(!this->size_) return true;
- for(iterator n1 = this->get_start(); n1.node_;)
+ for(iterator n1 = this->begin(); n1.node_;)
{
iterator n2 = other.find_matching_node(n1);
if (!n2.node_) return false;
Modified: branches/release/boost/unordered/detail/table.hpp
==============================================================================
--- branches/release/boost/unordered/detail/table.hpp (original)
+++ branches/release/boost/unordered/detail/table.hpp 2012-09-22 13:28:55 EDT (Sat, 22 Sep 2012)
@@ -187,7 +187,7 @@
std::size_t bucket_count_;
std::size_t size_;
float mlf_;
- std::size_t max_load_; // Only use if buckets_.
+ std::size_t max_load_;
bucket_pointer buckets_;
////////////////////////////////////////////////////////////////////////
@@ -222,6 +222,7 @@
bucket_pointer get_bucket(std::size_t bucket_index) const
{
+ BOOST_ASSERT(buckets_);
return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
}
@@ -235,14 +236,15 @@
return get_bucket(bucket_index)->next_;
}
- iterator get_start() const
+ iterator begin() const
{
- return iterator(static_cast<node_pointer>(
- get_previous_start()->next_));
+ return size_ ? iterator(static_cast<node_pointer>(
+ get_previous_start()->next_)) : iterator();
}
- iterator get_start(std::size_t bucket_index) const
+ iterator begin(std::size_t bucket_index) const
{
+ if (!size_) return iterator();
previous_pointer prev = get_previous_start(bucket_index);
return prev ? iterator(static_cast<node_pointer>(prev->next_)) :
iterator();
@@ -257,8 +259,7 @@
std::size_t bucket_size(std::size_t index) const
{
- if (!size_) return 0;
- iterator it = get_start(index);
+ iterator it = begin(index);
if (!it.node_) return 0;
std::size_t count = 0;
@@ -292,10 +293,10 @@
// From 6.3.1/13:
// Only resize when size >= mlf_ * count
- max_load_ = boost::unordered::detail::double_to_size(ceil(
+ max_load_ = buckets_ ? boost::unordered::detail::double_to_size(ceil(
static_cast<double>(mlf_) *
static_cast<double>(bucket_count_)
- ));
+ )) : 0;
}
@@ -303,7 +304,7 @@
{
BOOST_ASSERT(z > 0);
mlf_ = (std::max)(z, minimum_max_load_factor);
- if (buckets_) recalculate_max_load();
+ recalculate_max_load();
}
std::size_t min_buckets_for_size(std::size_t size) const
@@ -362,6 +363,7 @@
{
x.buckets_ = bucket_pointer();
x.size_ = 0;
+ x.max_load_ = 0;
}
table(table& x, node_allocator const& a,
@@ -383,7 +385,7 @@
if (x.size_) {
create_buckets(bucket_count_);
copy_nodes<node_allocator> copy(node_alloc());
- table_impl::fill_buckets(x.get_start(), *this, copy);
+ table_impl::fill_buckets(x.begin(), *this, copy);
}
}
@@ -398,7 +400,7 @@
move_nodes<node_allocator> move(node_alloc());
node_holder<node_allocator> nodes(x);
- table_impl::fill_buckets(nodes.get_start(), *this, move);
+ table_impl::fill_buckets(nodes.begin(), *this, move);
}
}
@@ -487,6 +489,7 @@
size_ = other.size_;
other.buckets_ = bucket_pointer();
other.size_ = 0;
+ other.max_load_ = 0;
}
////////////////////////////////////////////////////////////////////////
@@ -524,7 +527,7 @@
void delete_buckets()
{
if(buckets_) {
- delete_nodes(get_start(), iterator());
+ delete_nodes(begin(), iterator());
if (bucket::extra_node) {
node_pointer n = static_cast<node_pointer>(
@@ -536,6 +539,7 @@
destroy_buckets();
buckets_ = bucket_pointer();
+ max_load_ = 0;
}
BOOST_ASSERT(!size_);
@@ -545,7 +549,7 @@
{
if(!size_) return;
- delete_nodes(get_start(), iterator());
+ delete_nodes(begin(), iterator());
get_previous_start()->next_ = link_pointer();
clear_buckets();
@@ -649,13 +653,6 @@
}
////////////////////////////////////////////////////////////////////////
- // Iterators
-
- iterator begin() const {
- return !buckets_ ? iterator() : get_start();
- }
-
- ////////////////////////////////////////////////////////////////////////
// Assignment
void assign(table const& x)
@@ -680,7 +677,7 @@
if (!size_ && !x.size_) return;
- if (!buckets_ || x.size_ >= max_load_) {
+ if (x.size_ >= max_load_) {
create_buckets(min_buckets_for_size(x.size_));
}
else {
@@ -691,10 +688,7 @@
// assigning to them if possible, and deleting any that are
// left over.
assign_nodes<table> assign(*this);
-
- if (x.size_) {
- table_impl::fill_buckets(x.get_start(), *this, assign);
- }
+ table_impl::fill_buckets(x.begin(), *this, assign);
}
void assign(table const& x, true_type)
@@ -709,7 +703,7 @@
// Delete everything with current allocators before assigning
// the new ones.
- if (buckets_) delete_buckets();
+ delete_buckets();
allocators_.assign(x.allocators_);
// Copy over other data, all no throw.
@@ -722,7 +716,7 @@
if (x.size_) {
create_buckets(bucket_count_);
copy_nodes<node_allocator> copy(node_alloc());
- table_impl::fill_buckets(x.get_start(), *this, copy);
+ table_impl::fill_buckets(x.begin(), *this, copy);
}
}
}
@@ -740,7 +734,7 @@
void move_assign(table& x, true_type)
{
- if(buckets_) delete_buckets();
+ delete_buckets();
allocators_.move_assign(x.allocators_);
move_assign_no_alloc(x);
}
@@ -748,7 +742,7 @@
void move_assign(table& x, false_type)
{
if (node_alloc() == x.node_alloc()) {
- if(buckets_) delete_buckets();
+ delete_buckets();
move_assign_no_alloc(x);
}
else {
@@ -760,7 +754,7 @@
if (!size_ && !x.size_) return;
- if (!buckets_ || x.size_ >= max_load_) {
+ if (x.size_ >= max_load_) {
create_buckets(min_buckets_for_size(x.size_));
}
else {
@@ -771,11 +765,8 @@
// elements, assigning to them if possible, and deleting
// any that are left over.
move_assign_nodes<table> assign(*this);
-
- if (x.size_) {
- node_holder<node_allocator> nodes(x);
- table_impl::fill_buckets(nodes.get_start(), *this, assign);
- }
+ node_holder<node_allocator> nodes(x);
+ table_impl::fill_buckets(nodes.begin(), *this, assign);
}
}
@@ -784,9 +775,9 @@
boost::unordered::detail::set_hash_functions<hasher, key_equal>
new_func_this(*this, x);
// No throw from here.
- move_buckets_from(x);
mlf_ = x.mlf_;
max_load_ = x.max_load_;
+ move_buckets_from(x);
new_func_this.commit();
}
@@ -878,7 +869,7 @@
using namespace std;
if(!size_) {
- if(buckets_) delete_buckets();
+ delete_buckets();
bucket_count_ = policy::new_bucket_count(min_buckets);
}
else {
Modified: branches/release/boost/unordered/detail/unique.hpp
==============================================================================
--- branches/release/boost/unordered/detail/unique.hpp (original)
+++ branches/release/boost/unordered/detail/unique.hpp 2012-09-22 13:28:55 EDT (Sat, 22 Sep 2012)
@@ -231,11 +231,9 @@
Key const& k,
Pred const& eq) const
{
- if (!this->size_) return iterator();
-
std::size_t bucket_index =
policy::to_bucket(this->bucket_count_, key_hash);
- iterator n = this->get_start(bucket_index);
+ iterator n = this->begin(bucket_index);
for (;;)
{
@@ -288,9 +286,8 @@
bool equals(table_impl const& other) const
{
if(this->size_ != other.size_) return false;
- if(!this->size_) return true;
- for(iterator n1 = this->get_start(); n1.node_; ++n1)
+ for(iterator n1 = this->begin(); n1.node_; ++n1)
{
iterator n2 = other.find_matching_node(n1);
@@ -466,14 +463,9 @@
{
node_constructor a(this->node_alloc());
- // Special case for empty buckets so that we can use
- // max_load_ (which isn't valid when buckets_ is null).
- if (!this->buckets_) {
- insert_range_empty(a, k, i, j);
- if (++i == j) return;
- }
+ insert_range_impl2(a, k, i, j);
- do {
+ while(++i != j) {
// Note: can't use get_key as '*i' might not be value_type - it
// could be a pair with first_types as key_type without const or
// a different second_type.
@@ -483,18 +475,7 @@
// be less efficient if copying the full value_type is
// expensive.
insert_range_impl2(a, extractor::extract(*i), i, j);
- } while(++i != j);
- }
-
- template <class InputIt>
- void insert_range_empty(node_constructor& a, key_type const& k,
- InputIt i, InputIt j)
- {
- std::size_t key_hash = this->hash(k);
- a.construct_with_value2(*i);
- this->reserve_for_insert(this->size_ +
- boost::unordered::detail::insert_size(i, j));
- this->add_node(a, key_hash);
+ }
}
template <class InputIt>
Modified: branches/release/boost/unordered/unordered_map.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_map.hpp (original)
+++ branches/release/boost/unordered/unordered_map.hpp 2012-09-22 13:28:55 EDT (Sat, 22 Sep 2012)
@@ -469,16 +469,14 @@
local_iterator begin(size_type n)
{
- return table_.size_ ? local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- local_iterator();
+ return local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
const_local_iterator begin(size_type n) const
{
- return table_.size_ ? const_local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- const_local_iterator();
+ return const_local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
local_iterator end(size_type)
@@ -493,9 +491,8 @@
const_local_iterator cbegin(size_type n) const
{
- return table_.size_ ? const_local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- const_local_iterator();
+ return const_local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
const_local_iterator cend(size_type) const
@@ -951,16 +948,14 @@
local_iterator begin(size_type n)
{
- return table_.size_ ? local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- local_iterator();
+ return local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
const_local_iterator begin(size_type n) const
{
- return table_.size_ ? const_local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- const_local_iterator();
+ return const_local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
local_iterator end(size_type)
@@ -975,9 +970,8 @@
const_local_iterator cbegin(size_type n) const
{
- return table_.size_ ? const_local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- const_local_iterator();
+ return const_local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
const_local_iterator cend(size_type) const
Modified: branches/release/boost/unordered/unordered_set.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_set.hpp (original)
+++ branches/release/boost/unordered/unordered_set.hpp 2012-09-22 13:28:55 EDT (Sat, 22 Sep 2012)
@@ -454,16 +454,14 @@
local_iterator begin(size_type n)
{
- return table_.size_ ? local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- local_iterator();
+ return local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
const_local_iterator begin(size_type n) const
{
- return table_.size_ ? const_local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- const_local_iterator();
+ return const_local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
local_iterator end(size_type)
@@ -478,9 +476,8 @@
const_local_iterator cbegin(size_type n) const
{
- return table_.size_ ? const_local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- const_local_iterator();
+ return const_local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
const_local_iterator cend(size_type) const
@@ -926,16 +923,14 @@
local_iterator begin(size_type n)
{
- return table_.size_ ? local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- local_iterator();
+ return local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
const_local_iterator begin(size_type n) const
{
- return table_.size_ ? const_local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- const_local_iterator();
+ return const_local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
local_iterator end(size_type)
@@ -950,9 +945,8 @@
const_local_iterator cbegin(size_type n) const
{
- return table_.size_ ? const_local_iterator(
- table_.get_start(n), n, table_.bucket_count_) :
- const_local_iterator();
+ return const_local_iterator(
+ table_.begin(n), n, table_.bucket_count_);
}
const_local_iterator cend(size_type) const
Modified: branches/release/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/insert_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/insert_tests.cpp 2012-09-22 13:28:55 EDT (Sat, 22 Sep 2012)
@@ -276,6 +276,21 @@
test::check_equivalent_keys(x);
}
+
+ std::cerr<<"insert copy iterator range test 2.\n";
+
+ {
+ test::check_instances check_;
+
+ X x;
+
+ test::random_values<X> v1(500, generator);
+ test::random_values<X> v2(500, generator);
+ x.insert(test::copy_iterator(v1.begin()), test::copy_iterator(v1.end()));
+ x.insert(test::copy_iterator(v2.begin()), test::copy_iterator(v2.end()));
+
+ test::check_equivalent_keys(x);
+ }
}
#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
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