Subject: [Boost-commit] svn:boost r86717 - in trunk/boost/multi_index: . detail
From: joaquin_at_[hidden]
Date: 2013-11-16 07:49:13
Author: joaquin
Date: 2013-11-16 07:49:13 EST (Sat, 16 Nov 2013)
New Revision: 86717
URL: http://svn.boost.org/trac/boost/changeset/86717
Log:
hashed index performance improvements
Text files modified:
trunk/boost/multi_index/detail/hash_index_node.hpp | 64 +++++++++++++--------------------------
trunk/boost/multi_index/hashed_index.hpp | 25 ++++++++------
2 files changed, 36 insertions(+), 53 deletions(-)
Modified: trunk/boost/multi_index/detail/hash_index_node.hpp
==============================================================================
--- trunk/boost/multi_index/detail/hash_index_node.hpp Sat Nov 16 04:23:13 2013 (r86716)
+++ trunk/boost/multi_index/detail/hash_index_node.hpp 2013-11-16 07:49:13 EST (Sat, 16 Nov 2013) (r86717)
@@ -234,11 +234,6 @@
return x->prior()->next()!=x;
}
- static bool is_last_of_bucket(pointer x)
- {
- return x->next()->prior()!=base_pointer_from(x);
- }
-
static pointer after(pointer x)
{
return x->next();
@@ -315,6 +310,11 @@
{
return Node::base_pointer_from(x);
}
+
+ static bool is_last_of_bucket(pointer x)
+ {
+ return x->next()->prior()!=base_pointer_from(x);
+ }
};
template<typename Node>
@@ -330,11 +330,6 @@
return x->prior()->next()->next()==x;
}
- static bool is_last_of_bucket(pointer x)
- {
- return x->next()->prior()->next()==x;
- }
-
static bool is_first_of_group(pointer x)
{
return
@@ -388,54 +383,34 @@
static void link(pointer x,pointer first,pointer last)
{
- x->next()=last->next();
- x->prior()=base_pointer_from(last);
- if(is_last_of_bucket(last)){
- x->next()->prior()->next()=x;
+ x->prior()=first->prior();
+ x->next()=first;
+ if(is_first_of_bucket(first)){
+ x->prior()->next()->next()=x;
}
else{
- x->next()->prior()=base_pointer_from(x);
+ x->prior()->next()=x;
}
if(first==last){
- last->next()=x;
+ last->prior()=base_pointer_from(x);
}
else if(first->next()==last){
- last->next()=first;
- last->prior()=base_pointer_from(x);
+ first->prior()=base_pointer_from(last);
+ first->next()=x;
}
else{
pointer second=first->next(),
lastbutone=pointer_from(last->prior());
- lastbutone->next()=last;
- last->next()=first;
- second->prior()=base_pointer_from(x);
+ second->prior()=base_pointer_from(first);
+ first->prior()=base_pointer_from(last);
+ lastbutone->next()=x;
}
}
- static void splice_range(
+ static void link_range(
pointer first,pointer last,base_pointer buc,pointer cend)
{
- if(is_first_of_bucket(first)){
- if(is_last_of_bucket(last)){
- first->prior()->next()->next()=last->next();
- last->next()->prior()->next()=first->prior()->next();
- first->prior()->next()=pointer(0);
- }
- else{
- first->prior()->next()->next()=last->next();
- last->next()->prior()=first->prior();
- }
- }
- else if(is_last_of_bucket(last)){
- first->prior()->next()=last->next();
- last->next()->prior()->next()=pointer_from(first->prior());
- }
- else{
- first->prior()->next()=last->next();
- last->next()->prior()=first->prior();
- }
-
if(buc->next()==pointer(0)){ /* empty bucket */
last->next()=cend->next();
last->next()->prior()->next()=last;
@@ -524,6 +499,11 @@
return Node::base_pointer_from(x);
}
+ static bool is_last_of_bucket(pointer x)
+ {
+ return x->next()->prior()->next()==x;
+ }
+
static bool is_last_but_one_of_group(pointer x)
{
return
Modified: trunk/boost/multi_index/hashed_index.hpp
==============================================================================
--- trunk/boost/multi_index/hashed_index.hpp Sat Nov 16 04:23:13 2013 (r86716)
+++ trunk/boost/multi_index/hashed_index.hpp 2013-11-16 07:49:13 EST (Sat, 16 Nov 2013) (r86717)
@@ -1177,15 +1177,18 @@
node_impl_pointer last_of_range(
node_impl_pointer x,hashed_non_unique_tag)const
{
- if(node_alg::is_last_of_bucket(x))return x;
- node_impl_pointer y=x->next();
- if(y->prior()!=node_impl_type::base_pointer_from(x)){
- return node_impl_type::pointer_from(y->prior());
+ node_impl_pointer y=x->next();
+ node_impl_base_pointer z=y->prior();
+ if(z->next()==x)return x; /* last of bucket */
+ else if(z!=node_impl_type::base_pointer_from(x)){
+ return node_impl_type::pointer_from(z); /* group of size>2 */
+ }
+ else{
+ return /* range of size 1 or 2 */
+ eq_(
+ key(node_type::from_impl(x)->value()),
+ key(node_type::from_impl(y)->value()))?y:x;
}
- else if(eq_(
- key(node_type::from_impl(x)->value()),
- key(node_type::from_impl(y)->value())))return y;
- else return x;
}
node_impl_pointer end_of_range(node_impl_pointer x)const
@@ -1292,10 +1295,10 @@
if(size()!=0){
auto_space<
- std::size_t,allocator_type> hashes(get_allocator(),size()+1);
+ std::size_t,allocator_type> hashes(get_allocator(),size());
auto_space<
node_impl_pointer,
- allocator_type> range_lasts(get_allocator(),size()+1);
+ allocator_type> range_lasts(get_allocator(),size());
std::size_t i=0;
node_impl_pointer x=begin_;
@@ -1312,7 +1315,7 @@
std::size_t h=hashes.data()[i];
node_impl_pointer last=range_lasts.data()[i++],
y=last->next();
- node_alg::splice_range(
+ node_alg::link_range(
x,last,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
x=y;
}