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
   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     /// MultiLevelHashSet related definitions
  19     /** @ingroup cds_intrusive_helper
  20     */
  21     namespace multilevel_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 MultiLevelHashSet 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
  61             //@cond
  62             void onInsertSuccess()              { ++m_nInsertSuccess;       }
  63             void onInsertFailed()               { ++m_nInsertFailed;        }
  64             void onInsertRetry()                { ++m_nInsertRetry;         }
  65             void onUpdateNew()                  { ++m_nUpdateNew;           }
  66             void onUpdateExisting()             { ++m_nUpdateExisting;      }
  67             void onUpdateFailed()               { ++m_nUpdateFailed;        }
  68             void onUpdateRetry()                { ++m_nUpdateRetry;         }
  69             void onEraseSuccess()               { ++m_nEraseSuccess;        }
  70             void onEraseFailed()                { ++m_nEraseFailed;         }
  71             void onEraseRetry()                 { ++m_nEraseRetry;          }
  72             void onFindSuccess()                { ++m_nFindSuccess;         }
  73             void onFindFailed()                 { ++m_nFindFailed;          }
  74
  75             void onExpandNodeSuccess()          { ++m_nExpandNodeSuccess;   }
  76             void onExpandNodeFailed()           { ++m_nExpandNodeFailed;    }
  77             void onSlotChanged()                { ++m_nSlotChanged;         }
  78             void onSlotConverting()             { ++m_nSlotConverting;      }
  79             void onArrayNodeCreated()           { ++m_nArrayNodeCount;      }
  80             //@endcond
  81         };
  82
  83         /// \p MultiLevelHashSet empty internal statistics
  84         struct empty_stat {
  85             //@cond
  86             void onInsertSuccess()              const {}
  87             void onInsertFailed()               const {}
  88             void onInsertRetry()                const {}
  89             void onUpdateNew()                  const {}
  90             void onUpdateExisting()             const {}
  91             void onUpdateFailed()               const {}
  92             void onUpdateRetry()                const {}
  93             void onEraseSuccess()               const {}
  94             void onEraseFailed()                const {}
  95             void onEraseRetry()                 const {}
  96             void onFindSuccess()                const {}
  97             void onFindFailed()                 const {}
  98
  99             void onExpandNodeSuccess()          const {}
 100             void onExpandNodeFailed()           const {}
 101             void onSlotChanged()                const {}
 102             void onSlotConverting()             const {}
 103             void onArrayNodeCreated()           const {}
 104             //@endcond
 105         };
 106
 107         /// \p MultiLevelHashSet traits
 108         struct traits
 109         {
 110             /// Mandatory functor to get hash value from data node
 111             /**
 112                 It is most-important feature of \p MultiLevelHashSet.
 113                 That functor must return a reference to fixed-sized hash value of data node.
 114                 The return value of that functor specifies the type of hash value.
 115
 116                 Example:
 117                 \code
 118                 typedef uint8_t hash_type[32]; // 256-bit hash type
 119                 struct foo {
 120                     hash_type  hash; // 256-bit hash value
 121                     // ... other fields
 122                 };
 123
 124                 // Hash accessor
 125                 struct foo_hash_accessor {
 126                     hash_type const& operator()( foo const& d ) const
 127                     {
 128                         return d.hash;
 129                     }
 130                 };
 131                 \endcode
 132             */
 133             typedef cds::opt::none hash_accessor;
 134
 135             /// Disposer for removing data nodes
 136             typedef cds::intrusive::opt::v::empty_disposer disposer;
 137
 138             /// Hash comparing functor
 139             /**
 140                 No default functor is provided.
 141                 If the option is not specified, the \p less option is used.
 142             */
 143             typedef cds::opt::none compare;
 144
 145             /// Specifies binary predicate used for hash compare.
 146             /**
 147                 If \p %less and \p %compare are not specified, \p memcmp() -like @ref bitwise_compare "bit-wise hash comparator" is used
 148                 because the hash value is treated as fixed-sized bit-string.
 149             */
 150             typedef cds::opt::none less;
 151
 152             /// Item counter
 153             /**
 154                 The item counting is an important part of \p MultiLevelHashSet algorithm:
 155                 the \p empty() member function depends on correct item counting.
 156                 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 157
 158                 Default is \p atomicity::item_counter.
 159             */
 160             typedef cds::atomicity::item_counter item_counter;
 161
 162             /// Array node allocator
 163             /**
 164                 Allocator for array nodes. That allocator is used for creating \p headNode and \p arrayNode when the set grows.
 165                 Default is \ref CDS_DEFAULT_ALLOCATOR
 166             */
 167             typedef CDS_DEFAULT_ALLOCATOR node_allocator;
 168
 169             /// C++ memory ordering model
 170             /**
 171                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 172                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 173             */
 174             typedef cds::opt::v::relaxed_ordering memory_model;
 175
 176             /// Back-off strategy
 177             typedef cds::backoff::Default back_off;
 178
 179             /// Internal statistics
 180             /**
 181                 By default, internal statistics is disabled (\p multilevel_hashset::empty_stat).
 182                 Use \p multilevel_hashset::stat to enable it.
 183             */
 184             typedef empty_stat stat;
 185
 186             /// RCU deadlock checking policy (only for \ref cds_intrusive_MultilevelHashSet_rcu "RCU-based MultilevelHashSet")
 187             /**
 188                 List of available policy see \p opt::rcu_check_deadlock
 189             */
 190             typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
 191         };
 192
 193         /// Metafunction converting option list to \p multilevel_hashset::traits
 194         /**
 195             Supported \p Options are:
 196             - \p multilevel_hashset::hash_accessor - mandatory option, hash accessor functor.
 197                 @copydetails traits::hash_accessor
 198             - \p opt::node_allocator - array node allocator.
 199                 @copydetails traits::node_allocator
 200             - \p opt::compare - hash comparison functor. No default functor is provided.
 201                 If the option is not specified, the \p opt::less is used.
 202             - \p opt::less - specifies binary predicate used for hash comparison.
 203                 If the option is not specified, \p memcmp() -like bit-wise hash comparator is used
 204                 because the hash value is treated as fixed-sized bit-string.
 205             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 206             - \p opt::disposer - the functor used for disposing removed data node. Default is \p opt::v::empty_disposer. Due the nature
 207                 of GC schema the disposer may be called asynchronously.
 208             - \p opt::item_counter - the type of item counting feature.
 209                  The item counting is an important part of \p MultiLevelHashSet algorithm:
 210                  the \p empty() member function depends on correct item counting.
 211                  Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 212                  Default is \p atomicity::item_counter.
 213             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 214                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 215             - \p opt::stat - internal statistics. By default, it is disabled (\p multilevel_hashset::empty_stat).
 216                 To enable it use \p multilevel_hashset::stat
 217             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MultilevelHashSet_rcu "RCU-based MultilevelHashSet"
 218                 Default is \p opt::v::rcu_throw_deadlock
 219         */
 220         template <typename... Options>
 221         struct make_traits
 222         {
 223 #   ifdef CDS_DOXYGEN_INVOKED
 224             typedef implementation_defined type ;   ///< Metafunction result
 225 #   else
 226             typedef typename cds::opt::make_options<
 227                 typename cds::opt::find_type_traits< traits, Options... >::type
 228                 ,Options...
 229             >::type   type;
 230 #   endif
 231         };
 232
 233         /// Bit-wise memcmp-based comparator for hash value \p T
 234         template <typename T>
 235         struct bitwise_compare
 236         {
 237             /// Compares \p lhs and \p rhs
 238             /**
 239                 Returns:
 240                 - <tt> < 0</tt> if <tt>lhs < rhs</tt>
 241                 - <tt>0</tt> if <tt>lhs == rhs</tt>
 242                 - <tt> > 0</tt> if <tt>lhs > rhs</tt>
 243             */
 244             int operator()( T const& lhs, T const& rhs ) const
 245             {
 246                 return memcmp( &lhs, &rhs, sizeof(T));
 247             }
 248         };
 249
 250         //@cond
 251         namespace details {
 252             template <typename HashType, typename UInt = size_t >
 253             using hash_splitter = cds::algo::split_bitstring< HashType, UInt >;
 254         } // namespace details
 255         //@endcond
 256
 257     } // namespace multilevel_hashset
 258
 259     //@cond
 260     // Forward declaration
 261     template < class GC, typename T, class Traits = multilevel_hashset::traits >
 262     class MultiLevelHashSet;
 263     //@endcond
 264
 265 }} // namespace cds::intrusive
 266
 267 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_MULTILEVEL_HASHSET_BASE_H