cds/intrusive/details/multilevel_hashset_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_DETAILS_MULTILEVEL_HASHSET_BASE_H
   4 #define CDSLIB_INTRUSIVE_DETAILS_MULTILEVEL_HASHSET_BASE_H
   5
   6 #include <memory.h> // memcmp, memcpy
   7 #include <type_traits>
   8 #include <cds/intrusive/details/base.h>
   9 #include <cds/opt/compare.h>
  10 #include <cds/algo/atomic.h>
  11 #include <cds/details/marked_ptr.h>
  12 #include <cds/urcu/options.h>
  13
  14 namespace cds { namespace intrusive {
  15
  16     /// MultiLevelHashSet ordered list related definitions
  17     /** @ingroup cds_intrusive_helper
  18     */
  19     namespace multilevel_hashset {
  20
  21         /// Hash accessor option
  22         /**
  23             @copydetails traits::hash_accessor
  24         */
  25         template <typename Accessor>
  26         struct hash_accessor {
  27             //@cond
  28             template <typename Base> struct pack: public Base
  29             {
  30                 typedef Accessor hash_accessor;
  31             };
  32             //@endcond
  33         };
  34
  35         /// Head node allocator option
  36         /**
  37             @copydetails traits::head_node_allocator
  38         */
  39         template <typename Accessor>
  40         struct head_node_allocator {
  41             //@cond
  42             template <typename Base> struct pack: public Base
  43             {
  44                 typedef Accessor head_node_allocator;
  45             };
  46             //@endcond
  47         };
  48
  49         /// Array node allocator option
  50         /**
  51             @copydetails traits::array_node_allocator
  52         */
  53         template <typename Accessor>
  54         struct array_node_allocator {
  55             //@cond
  56             template <typename Base> struct pack: public Base
  57             {
  58                 typedef Accessor array_node_allocator;
  59             };
  60             //@endcond
  61         };
  62
  63         /// \p MultiLevelHashSet internal statistics
  64         template <typename EventCounter = cds::atomicity::event_counter>
  65         struct stat {
  66             typedef EventCounter event_counter ; ///< Event counter type
  67
  68             event_counter   m_nInsertSuccess;   ///< Number of success \p insert() operations
  69             event_counter   m_nInsertFailed;    ///< Number of failed \p insert() operations
  70             event_counter   m_nInsertRetry;     ///< Number of attempts to insert new item
  71             event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
  72             event_counter   m_nUpdateExisting;  ///< Number of existing item updates
  73             event_counter   m_nUpdateFailed;    ///< Number of failed \p update() call
  74             event_counter   m_nUpdateRetry;     ///< Number of attempts to update the item
  75             event_counter   m_nEraseSuccess;    ///< Number of successful \p erase(), \p unlink(), \p extract() operations
  76             event_counter   m_nEraseFailed;     ///< Number of failed \p erase(), \p unlink(), \p extract() operations
  77             event_counter   m_nEraseRetry;      ///< Number of attempts to \p erase() an item
  78             event_counter   m_nFindSuccess;     ///< Number of successful \p find() and \p get() operations
  79             event_counter   m_nFindFailed;      ///< Number of failed \p find() and \p get() operations
  80
  81             event_counter   m_nExpandNodeSuccess; ///< Number of succeeded attempts converting data node to array node
  82             event_counter   m_nExpandNodeFailed;  ///< Number of failed attempts converting data node to array node
  83             event_counter   m_nSlotChanged;     ///< Number of array node slot changing by other thread during an operation
  84             event_counter   m_nSlotConverting;  ///< Number of events when we encounter a slot while it is converting to array node
  85
  86             void onInsertSuccess()              { ++m_nInsertSuccess;       }
  87             void onInserFailed()                { ++m_nInsertFailed;        }
  88             void onInsertRetry()                { ++m_nInsertRetry;         }
  89             void onUpdateNew()                  { ++m_nUpdateNew;           }
  90             void onUpdateExisting()             { ++m_nUpdateExisting;      }
  91             void onUpdateFailed()               { ++m_nUpdateFailed;        }
  92             void onUpdateRetry()                { ++m_nUpdateRetry;         }
  93             void onEraseSuccess()               { ++m_nEraseSuccess;        }
  94             void onEraseFailed()                { ++m_nEraseFailed;         }
  95             void onEraseRetry()                 { ++m_nEraseRetry;          }
  96             void onFindSuccess()                { ++m_nFinSuccess;          }
  97             void onFindFailed()                 { ++m_nFindFailed;          }
  98
  99             void onExpandNodeSuccess()          { ++m_nExpandNodeSuccess;   }
 100             void onExpandNodeFailed()           { ++m_nExpandNodeFailed;    }
 101             void onSlotChanged()                { ++m_nSlotChanged;         }
 102             void onSlotConverting()             { ++m_nSlotConverting;      }
 103         };
 104
 105         /// \p MultiLevelHashSet empty internal statistics
 106         struct empty_stat {
 107             //@cond
 108             void onInsertSuccess()              const {}
 109             void onInsertFailed()               const {}
 110             void onInsertRetry()                const {}
 111             void onUpdateNew()                  const {}
 112             void onUpdateExisting()             const {}
 113             void onUpdateFailed()               const {}
 114             void onUpdateRetry()                const {}
 115             void onEraseSuccess()               const {}
 116             void onEraseFailed()                const {}
 117             void onEraseRetry()                 const {}
 118             void onFindSuccess()                const {}
 119             void onFindFailed()                 const {}
 120
 121             void onExpandNodeSuccess()          const {}
 122             void onExpandNodeFailed()           const {}
 123             void onSlotChanged()                const {}
 124             void onSlotConverting()             const {}
 125             //@endcond
 126         };
 127
 128         /// MultiLevelHashSet traits
 129         struct traits
 130         {
 131             /// Mandatory functor to get hash value from data node
 132             /**
 133                 It is most-important feature of \p MultiLevelHashSet.
 134                 That functor must return a reference to fixed-sized hash value of data node.
 135                 The return value of that functor specifies the type of hash value.
 136
 137                 Example:
 138                 \code
 139                 typedef uint8_t hash_type[32]; // 256-bit hash type
 140                 struct foo {
 141                     hash_type  hash; // 256-bit hash value
 142                     // ... other fields
 143                 };
 144
 145                 // Hash accessor
 146                 struct foo_hash_accessor {
 147                     hash_type const& operator()( foo const& d ) const
 148                     {
 149                         return d.hash;
 150                     }
 151                 };
 152                 \endcode
 153             */
 154             typedef opt::none hash_accessor;
 155
 156             /// Disposer for removing data nodes
 157             typedef opt::v::empty_disposer disposer;
 158
 159             /// Hash comparing functor
 160             /**
 161                 No default functor is provided.
 162                 If the option is not specified, the \p less option is used.
 163             */
 164             typedef opt::none compare;
 165
 166             /// Specifies binary predicate used for hash compare.
 167             /**
 168                 If the option is not specified, \p memcmp() -like bit-wise hash comparator is used
 169                 because the hash value is treated as fixed-sized bit-string.
 170             */
 171             typedef opt::none less;
 172
 173             /// Item counter
 174             /**
 175                 The item counting is an important part of \p MultiLevelHashSet algorithm:
 176                 the \p empty() member function depends on correct item counting.
 177                 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 178
 179                 Default is \p atomicity::item_counter.
 180             */
 181             typedef cds::atomicity::item_counter item_counter;
 182
 183             /// Head node allocator
 184             /**
 185                 Allocator for head node. That allocator uses only in the set's constructor for allocating
 186                 main head array and in the destructor for destroying the head array.
 187                 Default is \ref CDS_DEFAULT_ALLOCATOR
 188             */
 189             typedef CDS_DEFAULT_ALLOCATOR head_node_allocator;
 190
 191             /// Array node allocator
 192             /**
 193                 Allocator for array nodes. That allocator is used for creating \p arrayNode when the set grows.
 194                 The size of each array node is fixed.
 195                 Default is \ref CDS_DEFAULT_ALLOCATOR
 196             */
 197             typedef CDS_DEFAULT_ALLOCATOR array_node_allocator;
 198
 199             /// C++ memory ordering model
 200             /**
 201                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 202                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 203             */
 204             typedef opt::v::relaxed_ordering memory_model;
 205
 206             /// Back-off strategy
 207             typedef cds::backoff::Default back_off;
 208
 209             /// Internal statistics
 210             /**
 211                 By default, internal statistics is disabled (\p multilevel_hashset::empty_stat).
 212                 Use \p multilevel_hashset::stat to enable it.
 213             */
 214             typedef empty_stat stat;
 215
 216             /// RCU deadlock checking policy (only for \ref cds_intrusive_MultilevelHashSet_rcu "RCU-based MultilevelHashSet")
 217             /**
 218                 List of available policy see \p opt::rcu_check_deadlock
 219             */
 220             typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
 221         };
 222
 223         /// Metafunction converting option list to \p multilevel_hashset::traits
 224         /**
 225             Supported \p Options are:
 226             - \p multilevel_hashset::hash_accessor - mandatory option, hash accessor functor.
 227                 @copydetails traits::hash_accessor
 228             - \p multilevel_hashset::head_node_allocator - head node allocator.
 229                 @copydetails traits::head_node_allocator
 230             - \p multilevel_hashset::array_node_allocator - array node allocator.
 231                 @copydetails traits::array_node_allocator
 232             - \p opt::compare - hash comparison functor. No default functor is provided.
 233                 If the option is not specified, the \p opt::less is used.
 234             - \p opt::less - specifies binary predicate used for hash comparison.
 235                 If the option is not specified, \p memcmp() -like bit-wise hash comparator is used
 236                 because the hash value is treated as fixed-sized bit-string.
 237             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 238             - \p opt::disposer - the functor used for disposing removed data node. Default is \p opt::v::empty_disposer. Due the nature
 239                 of GC schema the disposer may be called asynchronously.
 240             - \p opt::item_counter - the type of item counting feature.
 241                  The item counting is an important part of \p MultiLevelHashSet algorithm:
 242                  the \p empty() member function depends on correct item counting.
 243                  Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 244                  Default is \p atomicity::item_counter.
 245             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 246                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 247             - \p opt::stat - internal statistics. By default, it is disabled (\p multilevel_hashset::empty_stat).
 248                 To enable it use \p multilevel_hashset::stat
 249             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MultilevelHashSet_rcu "RCU-based MultilevelHashSet"
 250                 Default is \p opt::v::rcu_throw_deadlock
 251         */
 252         template <typename... Options>
 253         struct make_traits
 254         {
 255 #   ifdef CDS_DOXYGEN_INVOKED
 256             typedef implementation_defined type ;   ///< Metafunction result
 257 #   else
 258             typedef typename cds::opt::make_options<
 259                 typename cds::opt::find_type_traits< traits, Options... >::type
 260                 ,Options...
 261             >::type   type;
 262 #   endif
 263         };
 264
 265         /// Bit-wise memcmp-based comparator for hash value \p T
 266         template <typename T>
 267         struct bitwise_compare
 268         {
 269             int operator()( T const& lhs, T const& rhs ) const
 270             {
 271                 return memcmp( &lhs, &rhs, sizeof(T));
 272             }
 273         };
 274
 275         //@cond
 276         namespace details {
 277             template <typename HashType, typename UInt = size_t >
 278             class hash_splitter
 279             {
 280             public:
 281                 typedef HashType hash_type;
 282                 typedef UInt     uint_type;
 283
 284                 static CDS_CONSTEXPR size_t const c_nHashSize   = (sizeof(hash_type) + sizeof(uint_type) - 1) / sizeof(uint_type);
 285                 static CDS_CONSTEXPR size_t const c_nBitPerByte = 8;
 286                 static CDS_CONSTEXPR size_t const c_nBitPerHash = sizeof(hash_type) * c_nBitPerByte;
 287                 static CDS_CONSTEXPR size_t const c_nBitPerInt  = sizeof(uint_type) * c_nBitPerByte;
 288
 289             public:
 290                 explicit hash_splitter( hash_type const& h )
 291                     : m_ptr(reinterpret_cast<uint_type const*>( &h ))
 292                     , m_pos(0)
 293                     , m_first( m_ptr )
 294 #           ifdef _DEBUG
 295                     , m_last( m_ptr + c_nHashSize )
 296 #           endif
 297                 {}
 298
 299                 explicit operator bool() const
 300                 {
 301                     return !eos();
 302                 }
 303
 304                 // end-of-bitstring
 305                 bool eos() const
 306                 {
 307                     return m_pos >= c_nBitPerHash;
 308                 }
 309
 310                 uint_type cut( size_t nBits )
 311                 {
 312                     assert( !eos() );
 313                     assert( nBits <= c_nBitPerInt );
 314                     assert( m_pos + nBits <= c_nBitPerHash );
 315 #           ifdef _DEBUG
 316                     assert( m_ptr < m_last );
 317 #           endif
 318                     uint_type result;
 319
 320                     size_t const nRest = c_nBitPerInt - m_pos % c_nBitPerInt;
 321                     m_pos += nBits;
 322                     if ( nBits < nRest ) {
 323                         result = *m_ptr << ( nRest - nBits );
 324                         result = result >> ( c_nBitPerInt - nBits );
 325                     }
 326                     else if ( nBits == nRest ) {
 327                         result = *m_ptr >> ( c_nBitPerInt - nRest );
 328                         ++m_ptr;
 329                     }
 330                     else {
 331                         size_t const lsb = *m_ptr >> ( c_nBitPerInt - nRest );
 332                         nBits -= nRest;
 333                         ++m_ptr;
 334
 335                         result = *m_ptr << ( c_nBitPerInt - nBits );
 336                         result = result >> ( c_nBitPerInt - nBits );
 337                         result = (result << nRest) + lsb;
 338                     }
 339
 340                     assert( m_pos <= c_nBitPerHash );
 341 #           ifdef _DEBUG
 342                     assert( m_ptr < m_last );
 343 #           endif
 344                     return result;
 345                 }
 346
 347                 uint_type safe_cut( size_t nBits )
 348                 {
 349                     assert( !eos() );
 350                     assert( nBits <= sizeof(uint_type) * c_nBitPerByte );
 351
 352                     if ( m_pos + nBits > c_nBitPerHash )
 353                         nBits = c_nBitPerHash - m_pos;
 354                     return nBits ? cut( nBits ) : 0;
 355                 }
 356
 357                 void reset()
 358                 {
 359                     m_ptr = m_first;
 360                     m_pos = 0;
 361                 }
 362
 363             private:
 364                 uint_type const* m_ptr;  ///< current position in the hash
 365                 size_t           m_pos;  ///< current position in bits
 366                 uint_type const* m_first; ///< first position
 367 #           ifdef _DEBUG
 368                 uint_type const* m_last;  ///< last position
 369 #           endif
 370             };
 371         } // namespace details
 372         //@endcond
 373
 374     } // namespace multilevel_hashset
 375
 376     //@cond
 377     // Forward declaration
 378     template < class GC, typename T, class Traits = multilevel_hashset::traits >
 379     class MultiLevelHashSet;
 380     //@endcond
 381
 382 }} // namespace cds::intrusive
 383
 384 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_MULTILEVEL_HASHSET_BASE_H