Added several bit reversal algo

[libcds.git] / cds / intrusive / split_list_rcu.h

diff --git a/cds/intrusive/split_list_rcu.h b/cds/intrusive/split_list_rcu.h
index c8902d111c111df563004497fcef8ab46d82bb1c..117e49fc42401c6a07fc38094aa191bb6886176a 100644 (file)
--- a/cds/intrusive/split_list_rcu.h
+++ b/cds/intrusive/split_list_rcu.h
@@ -119,6 +119,7 @@ namespace cds { namespace intrusive {
         /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
         static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
 
+        typedef typename traits::bit_reversal bit_reversal; ///< Bit reversal algorithm, see \p split_list::traits::bit_reversal
         typedef typename traits::item_counter item_counter; ///< Item counter type
         typedef typename traits::back_off     back_off;     ///< back-off strategy for spinning
         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
@@ -323,7 +324,7 @@ namespace cds { namespace intrusive {
             aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
-            node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
+            node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
 
             if ( m_List.insert_at( pHead, val )) {
                 inc_item_count();
@@ -362,7 +363,7 @@ namespace cds { namespace intrusive {
             aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
-            node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
+            node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
 
             if ( m_List.insert_at( pHead, val, f )) {
                 inc_item_count();
@@ -410,7 +411,7 @@ namespace cds { namespace intrusive {
             aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
-            node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
+            node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
 
             std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
             if ( bRet.first && bRet.second ) {
@@ -929,7 +930,7 @@ namespace cds { namespace intrusive {
                 if ( pBucket )
                     return pBucket;
 
-                pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ));
+                pBucket = alloc_aux_node( split_list::dummy_hash<bit_reversal>( nBucket ));
                 if ( pBucket ) {
                     if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
                         m_Buckets.bucket( nBucket, pBucket );
@@ -974,7 +975,7 @@ namespace cds { namespace intrusive {
         void init()
         {
             // Initialize bucket 0
-            aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
+            aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash<bit_reversal>(0)*/ );
 
             // insert_aux_node cannot return false for empty list
             CDS_VERIFY( m_List.insert_aux_node( pNode ));
@@ -1013,7 +1014,7 @@ namespace cds { namespace intrusive {
         bool find_( Q& val, Compare cmp, Func f )
         {
             size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
+            split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
             aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
@@ -1025,7 +1026,7 @@ namespace cds { namespace intrusive {
         bool find_value( Q const& val, Compare cmp )
         {
             size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
+            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
             aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
@@ -1036,7 +1037,7 @@ namespace cds { namespace intrusive {
         raw_ptr get_( Q const& val, Compare cmp )
         {
             size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
+            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
             aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
@@ -1049,7 +1050,7 @@ namespace cds { namespace intrusive {
         value_type * extract_( Q const& val, Compare cmp )
         {
             size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
+            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
             aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
@@ -1074,7 +1075,7 @@ namespace cds { namespace intrusive {
         bool erase_( const Q& val, Compare cmp )
         {
             size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
+            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
             aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
@@ -1091,7 +1092,7 @@ namespace cds { namespace intrusive {
         bool erase_( Q const& val, Compare cmp, Func f )
         {
             size_t nHash = hash_value( val );
-            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
+            split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash<bit_reversal>( nHash ));
             aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );