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