cds/container/details/cuckoo_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H
   4 #define CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H
   5
   6 #include <cds/intrusive/cuckoo_set.h>
   7
   8 namespace cds { namespace container {
   9
  10     /// CuckooSet and CuckooMap related definitions
  11     /** @ingroup cds_nonintrusive_helper
  12     */
  13     namespace cuckoo {
  14 #ifdef CDS_DOXYGEN_INVOKED
  15         /// Lock striping concurrent access policy. This is typedef for intrusive::cuckoo::striping template
  16         class striping
  17         {};
  18 #else
  19         using intrusive::cuckoo::striping;
  20 #endif
  21
  22 #ifdef CDS_DOXYGEN_INVOKED
  23         /// Refinable concurrent access policy. This is typedef for intrusive::cuckoo::refinable template
  24         class refinable
  25         {};
  26 #else
  27         using intrusive::cuckoo::refinable;
  28 #endif
  29
  30 #ifdef CDS_DOXYGEN_INVOKED
  31         /// Striping internal statistics. This is typedef for intrusive::cuckoo::striping_stat
  32         class striping_stat
  33         {};
  34 #else
  35         using intrusive::cuckoo::striping_stat;
  36 #endif
  37
  38 #ifdef CDS_DOXYGEN_INVOKED
  39         /// Empty striping internal statistics. This is typedef for intrusive::cuckoo::empty_striping_stat
  40         class empty_striping_stat
  41         {};
  42 #else
  43         using intrusive::cuckoo::empty_striping_stat;
  44 #endif
  45
  46 #ifdef CDS_DOXYGEN_INVOKED
  47         /// Refinable internal statistics. This is typedef for intrusive::cuckoo::refinable_stat
  48         class refinable_stat
  49         {};
  50 #else
  51         using intrusive::cuckoo::refinable_stat;
  52 #endif
  53
  54 #ifdef CDS_DOXYGEN_INVOKED
  55         /// Empty refinable internal statistics. This is typedef for intrusive::cuckoo::empty_refinable_stat
  56         class empty_refinable_stat
  57         {};
  58 #else
  59         using intrusive::cuckoo::empty_refinable_stat;
  60 #endif
  61
  62 #ifdef CDS_DOXYGEN_INVOKED
  63         /// Cuckoo statistics. This is typedef for intrusive::cuckoo::stat
  64         class stat
  65         {};
  66 #else
  67         using intrusive::cuckoo::stat;
  68 #endif
  69
  70 #ifdef CDS_DOXYGEN_INVOKED
  71         /// Cuckoo empty statistics.This is typedef for intrusive::cuckoo::empty_stat
  72         class empty_stat
  73         {};
  74 #else
  75         using intrusive::cuckoo::empty_stat;
  76 #endif
  77
  78         /// Option specifying whether to store hash values in the node
  79         /**
  80              This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
  81              When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
  82              to recalculate the hash of the value. This option will improve the performance of unordered containers
  83              when rehashing is frequent or hashing the value is a slow operation
  84
  85              The \p Enable template parameter toggles the feature:
  86              - the value \p true enables storing the hash values
  87              - the value \p false disables storing the hash values
  88         */
  89         template <bool Enable>
  90         struct store_hash
  91         {
  92             //@cond
  93             template <typename Base>
  94             struct pack: public Base {
  95                 static bool const store_hash = Enable;
  96             };
  97             //@endcond
  98         };
  99
 100 #ifdef CDS_DOXYGEN_INVOKED
 101         /// Probe set type option
 102         /**
 103             @copydetails cds::intrusive::cuckoo::probeset_type
 104         */
 105         template <typename Type>
 106         struct probeset_type
 107         {};
 108 #else
 109         using intrusive::cuckoo::probeset_type;
 110 #endif
 111
 112         using intrusive::cuckoo::list;
 113         using intrusive::cuckoo::vector;
 114
 115         /// Type traits for CuckooSet and CuckooMap classes
 116         struct traits
 117         {
 118             /// Hash functors tuple
 119             /**
 120                 This is mandatory type and has no predefined one.
 121
 122                 At least, two hash functors should be provided. All hash functor
 123                 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
 124                 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
 125                 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
 126                 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
 127
 128                 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
 129                 \code
 130                 struct my_traits: public cds::container::cuckoo::traits {
 131                     typedef cds::opt::hash_tuple< hash1, hash2 > hash;
 132                 };
 133                 \endcode
 134             */
 135             typedef cds::opt::none      hash;
 136
 137             /// Concurrent access policy
 138             /**
 139                 Available opt::mutex_policy types:
 140                 - cuckoo::striping - simple, but the lock array is not resizable
 141                 - cuckoo::refinable - resizable lock array, but more complex access to set data.
 142
 143                 Default is cuckoo::striping.
 144             */
 145             typedef cuckoo::striping<>               mutex_policy;
 146
 147             /// Key equality functor
 148             /**
 149                 Default is <tt>std::equal_to<T></tt>
 150             */
 151             typedef opt::none                       equal_to;
 152
 153             /// Key comparison functor
 154             /**
 155                 No default functor is provided. If the option is not specified, the \p less is used.
 156             */
 157             typedef opt::none                       compare;
 158
 159             /// specifies binary predicate used for key comparison.
 160             /**
 161                 Default is \p std::less<T>.
 162             */
 163             typedef opt::none                       less;
 164
 165             /// Item counter
 166             /**
 167                 The type for item counting feature.
 168                 Default is cds::atomicity::item_counter
 169
 170                 Only atomic item counter type is allowed.
 171             */
 172             typedef cds::intrusive::cuckoo::traits::item_counter   item_counter;
 173
 174             /// Allocator type
 175             /**
 176                 The allocator type for allocating bucket tables.
 177                 Default is \p CDS_DEFAULT_ALLOCATOR that is \p std::allocator
 178             */
 179             typedef CDS_DEFAULT_ALLOCATOR       allocator;
 180
 181             /// Node allocator type
 182             /**
 183                 If this type is not set explicitly, the \ref allocator type is used.
 184             */
 185             typedef opt::none                   node_allocator;
 186
 187             /// Store hash value into items. See cuckoo::store_hash for explanation
 188             static bool const store_hash = false;
 189
 190             /// Probe-set type. See \ref probeset_type option for explanation
 191             typedef cuckoo::list                probeset_type;
 192
 193             /// Internal statistics
 194             typedef empty_stat                  stat;
 195         };
 196
 197         /// Metafunction converting option list to CuckooSet/CuckooMap traits
 198         /**
 199             Template argument list \p Options... are:
 200             - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
 201                 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
 202                 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
 203                 the number \p k - the count of hash tables in cuckoo hashing.
 204             - \p opt::mutex_policy - concurrent access policy.
 205                 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
 206                 Default is \p %cuckoo::striping.
 207             - \p opt::equal_to - key equality functor like \p std::equal_to.
 208                 If this functor is defined then the probe-set will be unordered.
 209                 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
 210                 and \p %opt::equal_to will be ignored.
 211             - \p opt::compare - key comparison functor. No default functor is provided.
 212                 If the option is not specified, the \p %opt::less is used.
 213                 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
 214             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 215                 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
 216             - \p opt::item_counter - the type of item counting feature. Default is \p opt::v::sequential_item_counter.
 217             - \p opt::allocator - the allocator type using for allocating bucket tables.
 218                 Default is \ref CDS_DEFAULT_ALLOCATOR
 219             - \p opt::node_allocator - the allocator type using for allocating set's items. If this option
 220                 is not specified then the type defined in \p %opt::allocator option is used.
 221             - \p cuckoo::store_hash - this option reserves additional space in the node to store the hash value
 222                 of the object once it's introduced in the container. When this option is used,
 223                 the unordered container will store the calculated hash value in the node and rehashing operations won't need
 224                 to recalculate the hash of the value. This option will improve the performance of unordered containers
 225                 when rehashing is frequent or hashing the value is a slow operation. Default value is \p false.
 226             - \ref intrusive::cuckoo::probeset_type "cuckoo::probeset_type" - type of probe set, may be \p cuckoo::list or <tt>cuckoo::vector<Capacity></tt>,
 227                 Default is \p cuckoo::list.
 228             - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
 229                 Default is \p %cuckoo::empty_stat
 230         */
 231         template <typename... Options>
 232         struct make_traits {
 233             typedef typename cds::opt::make_options<
 234                 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
 235                 ,Options...
 236             >::type   type ;    ///< Result of metafunction
 237         };
 238     }   // namespace cuckoo
 239 }} // namespace cds::container
 240
 241 #endif  // #ifndef CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H