[Boost-commit] svn:boost r86717 - in trunk/boost/multi_index: . detail

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;
       }