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