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