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

Subject: [Boost-commit] svn:boost r86370 - in trunk/boost/multi_index: . detail
From: joaquin_at_[hidden]
Date: 2013-10-20 12:19:16

Author: joaquin
Date: 2013-10-20 12:19:16 EDT (Sun, 20 Oct 2013)
New Revision: 86370
URL: http://svn.boost.org/trac/boost/changeset/86370

Log:
hashed index performance improvement

Text files modified: 
   trunk/boost/multi_index/detail/hash_index_node.hpp |    18 ++++++++++++++++                        
   trunk/boost/multi_index/hashed_index.hpp           |    43 +++++++++++++++++++-------------------- 
   2 files changed, 39 insertions(+), 22 deletions(-)

Modified: trunk/boost/multi_index/detail/hash_index_node.hpp
==============================================================================
--- trunk/boost/multi_index/detail/hash_index_node.hpp	Sun Oct 20 11:52:44 2013	(r86369)
+++ trunk/boost/multi_index/detail/hash_index_node.hpp	2013-10-20 12:19:16 EDT (Sun, 20 Oct 2013)	(r86370)
@@ -249,6 +249,13 @@
     return is_last_of_bucket(x)?pointer(0):after(x);
   }
 
+  static pointer next_to_inspect(pointer x)
+  {
+    pointer y=x->next();
+    if(y->prior()==base_pointer_from(x))return y;
+    else return pointer(0); /* x last of bucket, bucket finished */
+  }
+
   static void link(pointer x,base_pointer buc,pointer end)
   {
     if(buc->next()==pointer(0)){ /* empty bucket */
@@ -351,6 +358,17 @@
     return is_last_of_bucket(x)?pointer(0):after(x);
   }
 
+  static pointer next_to_inspect(pointer x)
+  {
+    pointer y=x->next();
+    if(y->prior()==base_pointer_from(x))return y;
+    pointer z=y->prior()->next();
+    if(z==x||                      /* x last of bucket */
+       z->prior()->next()!=z)      /* group(x) last of bucket */
+      return pointer(0);           /* bucket finished */
+    else return z;
+  }
+
   static void link(pointer x,base_pointer buc,pointer end)
   {
     if(buc->next()==pointer(0)){ /* empty bucket */

Modified: trunk/boost/multi_index/hashed_index.hpp
==============================================================================
--- trunk/boost/multi_index/hashed_index.hpp	Sun Oct 20 11:52:44 2013	(r86369)
+++ trunk/boost/multi_index/hashed_index.hpp	2013-10-20 12:19:16 EDT (Sun, 20 Oct 2013)	(r86370)
@@ -314,14 +314,14 @@
   {
     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 
-    size_type         s=0;
     std::size_t       buc=buckets.position(hash_(k));
     node_impl_pointer x=buckets.at(buc)->next();
     if(x!=node_impl_pointer(0)){
       x=x->next();
       do{
-        node_impl_pointer y=end_of_range(x);
         if(eq_(k,key(node_type::from_impl(x)->value()))){
+          node_impl_pointer y=end_of_range(x);
+          size_type         s=0;
           do{
             node_impl_pointer z=node_alg::after(x);
             this->final_erase_(
@@ -329,12 +329,12 @@
             x=z;
             ++s;
           }while(x!=y);
-          break;
+          return s;
         }
-        x=y;
-      }while(!node_alg::is_first_of_bucket(x));
+        x=node_alg::next_to_inspect(x);
+      }while(x!=node_impl_pointer(0));
     }
-    return s;
+    return 0;
   }
 
   iterator erase(iterator first,iterator last)
@@ -483,8 +483,8 @@
         if(eq(k,key(node_type::from_impl(x)->value()))){
           return make_iterator(node_type::from_impl(x));
         }
-        x=end_of_range(x);
-      }while(!node_alg::is_first_of_bucket(x));
+        x=node_alg::next_to_inspect(x);
+      }while(x!=node_impl_pointer(0));
     }
     return end();
   }
@@ -502,24 +502,24 @@
     const CompatibleKey& k,
     const CompatibleHash& hash,const CompatiblePred& eq)const
   {
-    size_type         res=0;
     std::size_t       buc=buckets.position(hash(k));
     node_impl_pointer x=buckets.at(buc)->next();
     if(x!=node_impl_pointer(0)){
       x=x->next();
       do{
-        node_impl_pointer y=end_of_range(x);
         if(eq(k,key(node_type::from_impl(x)->value()))){
+          size_type         res=0;
+          node_impl_pointer y=end_of_range(x);
           do{
             ++res;
             x=node_alg::after(x);
           }while(x!=y);
-          break;
+          return res;
         }
-        x=y;
-      }while(!node_alg::is_first_of_bucket(x));
+        x=node_alg::next_to_inspect(x);
+      }while(x!=node_impl_pointer(0));
     }
-    return res;
+    return 0;
   }
 
   template<typename CompatibleKey>
@@ -540,14 +540,13 @@
     if(x!=node_impl_pointer(0)){
       x=x->next();
       do{
-        node_impl_pointer y=end_of_range(x);
         if(eq(k,key(node_type::from_impl(x)->value()))){
           return std::pair<iterator,iterator>(
             make_iterator(node_type::from_impl(x)),
-            make_iterator(node_type::from_impl(y)));
+            make_iterator(node_type::from_impl(end_of_range(x))));
         }
-        x=y;
-      }while(!node_alg::is_first_of_bucket(x));
+        x=node_alg::next_to_inspect(x);
+      }while(x!=node_impl_pointer(0));
     }
     return std::pair<iterator,iterator>(end(),end());
   }
@@ -1142,8 +1141,8 @@
           pos=node_impl_type::base_pointer_from(x);
           return false;
         }
-        x=x->next();
-      }while(!node_alg::is_first_of_bucket(x));
+        x=node_alg::next_to_inspect(x);
+      }while(x!=node_impl_pointer(0));
     }
     return true;
   }
@@ -1159,8 +1158,8 @@
           pos.last=node_impl_type::base_pointer_from(last_of_range(x));
           return true;
         }
-        x=end_of_range(x);
-      }while(!node_alg::is_first_of_bucket(x));
+        x=node_alg::next_to_inspect(x);
+      }while(x!=node_impl_pointer(0));
     }
     return true;
   }