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