cds/intrusive/details/feldman_hashset_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
   4 #define CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
   5
   6 #include <memory.h> // memcmp, memcpy
   7 #include <type_traits>
   8
   9 #include <cds/intrusive/details/base.h>
  10 #include <cds/opt/compare.h>
  11 #include <cds/algo/atomic.h>
  12 #include <cds/algo/split_bitstring.h>
  13 #include <cds/details/marked_ptr.h>
  14 #include <cds/urcu/options.h>
  15
  16 namespace cds { namespace intrusive {
  17
  18     /// FeldmanHashSet related definitions
  19     /** @ingroup cds_intrusive_helper
  20     */
  21     namespace feldman_hashset {
  22         /// Hash accessor option
  23         /**
  24             @copydetails traits::hash_accessor
  25         */
  26         template <typename Accessor>
  27         struct hash_accessor {
  28             //@cond
  29             template <typename Base> struct pack: public Base
  30             {
  31                 typedef Accessor hash_accessor;
  32             };
  33             //@endcond
  34         };
  35
  36         /// \p FeldmanHashSet internal statistics
  37         template <typename EventCounter = cds::atomicity::event_counter>
  38         struct stat {
  39             typedef EventCounter event_counter ; ///< Event counter type
  40
  41             event_counter   m_nInsertSuccess;   ///< Number of success \p insert() operations
  42             event_counter   m_nInsertFailed;    ///< Number of failed \p insert() operations
  43             event_counter   m_nInsertRetry;     ///< Number of attempts to insert new item
  44             event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
  45             event_counter   m_nUpdateExisting;  ///< Number of existing item updates
  46             event_counter   m_nUpdateFailed;    ///< Number of failed \p update() call
  47             event_counter   m_nUpdateRetry;     ///< Number of attempts to update the item
  48             event_counter   m_nEraseSuccess;    ///< Number of successful \p erase(), \p unlink(), \p extract() operations
  49             event_counter   m_nEraseFailed;     ///< Number of failed \p erase(), \p unlink(), \p extract() operations
  50             event_counter   m_nEraseRetry;      ///< Number of attempts to \p erase() an item
  51             event_counter   m_nFindSuccess;     ///< Number of successful \p find() and \p get() operations
  52             event_counter   m_nFindFailed;      ///< Number of failed \p find() and \p get() operations
  53
  54             event_counter   m_nExpandNodeSuccess; ///< Number of succeeded attempts converting data node to array node
  55             event_counter   m_nExpandNodeFailed;  ///< Number of failed attempts converting data node to array node
  56             event_counter   m_nSlotChanged;     ///< Number of array node slot changing by other thread during an operation
  57             event_counter   m_nSlotConverting;  ///< Number of events when we encounter a slot while it is converting to array node
  58
  59             event_counter   m_nArrayNodeCount;  ///< Number of array nodes
  60             event_counter   m_nHeight;          ///< Current height of the tree
  61
  62             //@cond
  63             void onInsertSuccess()              { ++m_nInsertSuccess;       }
  64             void onInsertFailed()               { ++m_nInsertFailed;        }
  65             void onInsertRetry()                { ++m_nInsertRetry;         }
  66             void onUpdateNew()                  { ++m_nUpdateNew;           }
  67             void onUpdateExisting()             { ++m_nUpdateExisting;      }
  68             void onUpdateFailed()               { ++m_nUpdateFailed;        }
  69             void onUpdateRetry()                { ++m_nUpdateRetry;         }
  70             void onEraseSuccess()               { ++m_nEraseSuccess;        }
  71             void onEraseFailed()                { ++m_nEraseFailed;         }
  72             void onEraseRetry()                 { ++m_nEraseRetry;          }
  73             void onFindSuccess()                { ++m_nFindSuccess;         }
  74             void onFindFailed()                 { ++m_nFindFailed;          }
  75
  76             void onExpandNodeSuccess()          { ++m_nExpandNodeSuccess;   }
  77             void onExpandNodeFailed()           { ++m_nExpandNodeFailed;    }
  78             void onSlotChanged()                { ++m_nSlotChanged;         }
  79             void onSlotConverting()             { ++m_nSlotConverting;      }
  80             void onArrayNodeCreated()           { ++m_nArrayNodeCount;      }
  81             void height( size_t h )             { if (m_nHeight < h ) m_nHeight = h; }
  82             //@endcond
  83         };
  84
  85         /// \p FeldmanHashSet empty internal statistics
  86         struct empty_stat {
  87             //@cond
  88             void onInsertSuccess()              const {}
  89             void onInsertFailed()               const {}
  90             void onInsertRetry()                const {}
  91             void onUpdateNew()                  const {}
  92             void onUpdateExisting()             const {}
  93             void onUpdateFailed()               const {}
  94             void onUpdateRetry()                const {}
  95             void onEraseSuccess()               const {}
  96             void onEraseFailed()                const {}
  97             void onEraseRetry()                 const {}
  98             void onFindSuccess()                const {}
  99             void onFindFailed()                 const {}
 100
 101             void onExpandNodeSuccess()          const {}
 102             void onExpandNodeFailed()           const {}
 103             void onSlotChanged()                const {}
 104             void onSlotConverting()             const {}
 105             void onArrayNodeCreated()           const {}
 106             void height(size_t)                 const {}
 107             //@endcond
 108         };
 109
 110         /// \p FeldmanHashSet traits
 111         struct traits
 112         {
 113             /// Mandatory functor to get hash value from data node
 114             /**
 115                 It is most-important feature of \p FeldmanHashSet.
 116                 That functor must return a reference to fixed-sized hash value of data node.
 117                 The return value of that functor specifies the type of hash value.
 118
 119                 Example:
 120                 \code
 121                 typedef uint8_t hash_type[32]; // 256-bit hash type
 122                 struct foo {
 123                     hash_type  hash; // 256-bit hash value
 124                     // ... other fields
 125                 };
 126
 127                 // Hash accessor
 128                 struct foo_hash_accessor {
 129                     hash_type const& operator()( foo const& d ) const
 130                     {
 131                         return d.hash;
 132                     }
 133                 };
 134                 \endcode
 135             */
 136             typedef cds::opt::none hash_accessor;
 137
 138             /// Disposer for removing data nodes
 139             typedef cds::intrusive::opt::v::empty_disposer disposer;
 140
 141             /// Hash comparing functor
 142             /**
 143                 No default functor is provided.
 144                 If the option is not specified, the \p less option is used.
 145             */
 146             typedef cds::opt::none compare;
 147
 148             /// Specifies binary predicate used for hash compare.
 149             /**
 150                 If \p %less and \p %compare are not specified, \p memcmp() -like @ref bitwise_compare "bit-wise hash comparator" is used
 151                 because the hash value is treated as fixed-sized bit-string.
 152             */
 153             typedef cds::opt::none less;
 154
 155             /// Item counter
 156             /**
 157                 The item counting is an important part of \p FeldmanHashSet algorithm:
 158                 the \p empty() member function depends on correct item counting.
 159                 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 160
 161                 Default is \p atomicity::item_counter.
 162             */
 163             typedef cds::atomicity::item_counter item_counter;
 164
 165             /// Array node allocator
 166             /**
 167                 Allocator for array nodes. That allocator is used for creating \p headNode and \p arrayNode when the set grows.
 168                 Default is \ref CDS_DEFAULT_ALLOCATOR
 169             */
 170             typedef CDS_DEFAULT_ALLOCATOR node_allocator;
 171
 172             /// C++ memory ordering model
 173             /**
 174                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 175                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 176             */
 177             typedef cds::opt::v::relaxed_ordering memory_model;
 178
 179             /// Back-off strategy
 180             typedef cds::backoff::Default back_off;
 181
 182             /// Internal statistics
 183             /**
 184                 By default, internal statistics is disabled (\p feldman_hashset::empty_stat).
 185                 Use \p feldman_hashset::stat to enable it.
 186             */
 187             typedef empty_stat stat;
 188
 189             /// RCU deadlock checking policy (only for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet")
 190             /**
 191                 List of available policy see \p opt::rcu_check_deadlock
 192             */
 193             typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
 194         };
 195
 196         /// Metafunction converting option list to \p feldman_hashset::traits
 197         /**
 198             Supported \p Options are:
 199             - \p feldman_hashset::hash_accessor - mandatory option, hash accessor functor.
 200                 @copydetails traits::hash_accessor
 201             - \p opt::node_allocator - array node allocator.
 202                 @copydetails traits::node_allocator
 203             - \p opt::compare - hash comparison functor. No default functor is provided.
 204                 If the option is not specified, the \p opt::less is used.
 205             - \p opt::less - specifies binary predicate used for hash comparison.
 206                 If the option is not specified, \p memcmp() -like bit-wise hash comparator is used
 207                 because the hash value is treated as fixed-sized bit-string.
 208             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 209             - \p opt::disposer - the functor used for disposing removed data node. Default is \p opt::v::empty_disposer. Due the nature
 210                 of GC schema the disposer may be called asynchronously.
 211             - \p opt::item_counter - the type of item counting feature.
 212                  The item counting is an important part of \p FeldmanHashSet algorithm:
 213                  the \p empty() member function depends on correct item counting.
 214                  Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 215                  Default is \p atomicity::item_counter.
 216             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 217                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 218             - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashset::empty_stat).
 219                 To enable it use \p feldman_hashset::stat
 220             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
 221                 Default is \p opt::v::rcu_throw_deadlock
 222         */
 223         template <typename... Options>
 224         struct make_traits
 225         {
 226 #   ifdef CDS_DOXYGEN_INVOKED
 227             typedef implementation_defined type ;   ///< Metafunction result
 228 #   else
 229             typedef typename cds::opt::make_options<
 230                 typename cds::opt::find_type_traits< traits, Options... >::type
 231                 ,Options...
 232             >::type   type;
 233 #   endif
 234         };
 235
 236         /// Bit-wise memcmp-based comparator for hash value \p T
 237         template <typename T>
 238         struct bitwise_compare
 239         {
 240             /// Compares \p lhs and \p rhs
 241             /**
 242                 Returns:
 243                 - <tt> < 0</tt> if <tt>lhs < rhs</tt>
 244                 - <tt>0</tt> if <tt>lhs == rhs</tt>
 245                 - <tt> > 0</tt> if <tt>lhs > rhs</tt>
 246             */
 247             int operator()( T const& lhs, T const& rhs ) const
 248             {
 249                 return memcmp( &lhs, &rhs, sizeof(T));
 250             }
 251         };
 252
 253         //@cond
 254         namespace details {
 255             template <typename HashType, typename UInt = size_t >
 256             using hash_splitter = cds::algo::split_bitstring< HashType, UInt >;
 257
 258             struct metrics {
 259                 size_t  head_node_size;     // power-of-two
 260                 size_t  head_node_size_log; // log2( head_node_size )
 261                 size_t  array_node_size;    // power-of-two
 262                 size_t  array_node_size_log;// log2( array_node_size )
 263
 264                 static metrics make(size_t head_bits, size_t array_bits, size_t hash_size )
 265                 {
 266                     size_t const hash_bits = hash_size * 8;
 267
 268                     if (array_bits < 2)
 269                         array_bits = 2;
 270                     if (head_bits < 4)
 271                         head_bits = 4;
 272                     if (head_bits > hash_bits)
 273                         head_bits = hash_bits;
 274                     if ((hash_bits - head_bits) % array_bits != 0)
 275                         head_bits += (hash_bits - head_bits) % array_bits;
 276
 277                     assert((hash_bits - head_bits) % array_bits == 0);
 278
 279                     metrics m;
 280                     m.head_node_size_log = head_bits;
 281                     m.head_node_size = size_t(1) << head_bits;
 282                     m.array_node_size_log = array_bits;
 283                     m.array_node_size = size_t(1) << array_bits;
 284                     return m;
 285                 }
 286             };
 287
 288         } // namespace details
 289         //@endcond
 290     } // namespace feldman_hashset
 291
 292     //@cond
 293     // Forward declaration
 294     template < class GC, typename T, class Traits = feldman_hashset::traits >
 295     class FeldmanHashSet;
 296     //@endcond
 297
 298 }} // namespace cds::intrusive
 299
 300 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H