cds/container/details/cuckoo_base.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H
  32 #define CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H
  33
  34 #include <cds/intrusive/cuckoo_set.h>
  35
  36 namespace cds { namespace container {
  37
  38     /// CuckooSet and CuckooMap related definitions
  39     /** @ingroup cds_nonintrusive_helper
  40     */
  41     namespace cuckoo {
  42 #ifdef CDS_DOXYGEN_INVOKED
  43         /// Lock striping concurrent access policy. This is typedef for intrusive::cuckoo::striping template
  44         class striping
  45         {};
  46 #else
  47         using intrusive::cuckoo::striping;
  48 #endif
  49
  50 #ifdef CDS_DOXYGEN_INVOKED
  51         /// Refinable concurrent access policy. This is typedef for intrusive::cuckoo::refinable template
  52         class refinable
  53         {};
  54 #else
  55         using intrusive::cuckoo::refinable;
  56 #endif
  57
  58 #ifdef CDS_DOXYGEN_INVOKED
  59         /// Striping internal statistics. This is typedef for intrusive::cuckoo::striping_stat
  60         class striping_stat
  61         {};
  62 #else
  63         using intrusive::cuckoo::striping_stat;
  64 #endif
  65
  66 #ifdef CDS_DOXYGEN_INVOKED
  67         /// Empty striping internal statistics. This is typedef for intrusive::cuckoo::empty_striping_stat
  68         class empty_striping_stat
  69         {};
  70 #else
  71         using intrusive::cuckoo::empty_striping_stat;
  72 #endif
  73
  74 #ifdef CDS_DOXYGEN_INVOKED
  75         /// Refinable internal statistics. This is typedef for intrusive::cuckoo::refinable_stat
  76         class refinable_stat
  77         {};
  78 #else
  79         using intrusive::cuckoo::refinable_stat;
  80 #endif
  81
  82 #ifdef CDS_DOXYGEN_INVOKED
  83         /// Empty refinable internal statistics. This is typedef for intrusive::cuckoo::empty_refinable_stat
  84         class empty_refinable_stat
  85         {};
  86 #else
  87         using intrusive::cuckoo::empty_refinable_stat;
  88 #endif
  89
  90 #ifdef CDS_DOXYGEN_INVOKED
  91         /// Cuckoo statistics. This is typedef for intrusive::cuckoo::stat
  92         class stat
  93         {};
  94 #else
  95         using intrusive::cuckoo::stat;
  96 #endif
  97
  98 #ifdef CDS_DOXYGEN_INVOKED
  99         /// Cuckoo empty statistics.This is typedef for intrusive::cuckoo::empty_stat
 100         class empty_stat
 101         {};
 102 #else
 103         using intrusive::cuckoo::empty_stat;
 104 #endif
 105
 106         /// Option specifying whether to store hash values in the node
 107         /**
 108              This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
 109              When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
 110              to recalculate the hash of the value. This option will improve the performance of unordered containers
 111              when rehashing is frequent or hashing the value is a slow operation
 112
 113              The \p Enable template parameter toggles the feature:
 114              - the value \p true enables storing the hash values
 115              - the value \p false disables storing the hash values
 116         */
 117         template <bool Enable>
 118         struct store_hash
 119         {
 120             //@cond
 121             template <typename Base>
 122             struct pack: public Base {
 123                 static bool const store_hash = Enable;
 124             };
 125             //@endcond
 126         };
 127
 128 #ifdef CDS_DOXYGEN_INVOKED
 129         /// Probe set type option
 130         /**
 131             @copydetails cds::intrusive::cuckoo::probeset_type
 132         */
 133         template <typename Type>
 134         struct probeset_type
 135         {};
 136 #else
 137         using intrusive::cuckoo::probeset_type;
 138 #endif
 139
 140         using intrusive::cuckoo::list;
 141         using intrusive::cuckoo::vector;
 142
 143         /// Type traits for CuckooSet and CuckooMap classes
 144         struct traits
 145         {
 146             /// Hash functors tuple
 147             /**
 148                 This is mandatory type and has no predefined one.
 149
 150                 At least, two hash functors should be provided. All hash functor
 151                 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
 152                 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
 153                 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
 154                 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
 155
 156                 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
 157                 \code
 158                 struct my_traits: public cds::container::cuckoo::traits {
 159                     typedef cds::opt::hash_tuple< hash1, hash2 > hash;
 160                 };
 161                 \endcode
 162             */
 163             typedef cds::opt::none      hash;
 164
 165             /// Concurrent access policy
 166             /**
 167                 Available opt::mutex_policy types:
 168                 - cuckoo::striping - simple, but the lock array is not resizable
 169                 - cuckoo::refinable - resizable lock array, but more complex access to set data.
 170
 171                 Default is cuckoo::striping.
 172             */
 173             typedef cuckoo::striping<>               mutex_policy;
 174
 175             /// Key equality functor
 176             /**
 177                 Default is <tt>std::equal_to<T></tt>
 178             */
 179             typedef opt::none                       equal_to;
 180
 181             /// Key comparison functor
 182             /**
 183                 No default functor is provided. If the option is not specified, the \p less is used.
 184             */
 185             typedef opt::none                       compare;
 186
 187             /// specifies binary predicate used for key comparison.
 188             /**
 189                 Default is \p std::less<T>.
 190             */
 191             typedef opt::none                       less;
 192
 193             /// Item counter
 194             /**
 195                 The type for item counting feature.
 196                 Default is cds::atomicity::item_counter
 197
 198                 Only atomic item counter type is allowed.
 199             */
 200             typedef cds::intrusive::cuckoo::traits::item_counter   item_counter;
 201
 202             /// Allocator type
 203             /**
 204                 The allocator type for allocating bucket tables.
 205                 Default is \p CDS_DEFAULT_ALLOCATOR that is \p std::allocator
 206             */
 207             typedef CDS_DEFAULT_ALLOCATOR       allocator;
 208
 209             /// Node allocator type
 210             /**
 211                 If this type is not set explicitly, the \ref allocator type is used.
 212             */
 213             typedef opt::none                   node_allocator;
 214
 215             /// Store hash value into items. See cuckoo::store_hash for explanation
 216             static bool const store_hash = false;
 217
 218             /// Probe-set type. See \ref probeset_type option for explanation
 219             typedef cuckoo::list                probeset_type;
 220
 221             /// Internal statistics
 222             typedef empty_stat                  stat;
 223         };
 224
 225         /// Metafunction converting option list to CuckooSet/CuckooMap traits
 226         /**
 227             Template argument list \p Options... are:
 228             - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
 229                 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
 230                 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
 231                 the number \p k - the count of hash tables in cuckoo hashing.
 232             - \p opt::mutex_policy - concurrent access policy.
 233                 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
 234                 Default is \p %cuckoo::striping.
 235             - \p opt::equal_to - key equality functor like \p std::equal_to.
 236                 If this functor is defined then the probe-set will be unordered.
 237                 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
 238                 and \p %opt::equal_to will be ignored.
 239             - \p opt::compare - key comparison functor. No default functor is provided.
 240                 If the option is not specified, the \p %opt::less is used.
 241                 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
 242             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 243                 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
 244             - \p opt::item_counter - the type of item counting feature. Default is \p opt::v::sequential_item_counter.
 245             - \p opt::allocator - the allocator type using for allocating bucket tables.
 246                 Default is \ref CDS_DEFAULT_ALLOCATOR
 247             - \p opt::node_allocator - the allocator type using for allocating set's items. If this option
 248                 is not specified then the type defined in \p %opt::allocator option is used.
 249             - \p cuckoo::store_hash - this option reserves additional space in the node to store the hash value
 250                 of the object once it's introduced in the container. When this option is used,
 251                 the unordered container will store the calculated hash value in the node and rehashing operations won't need
 252                 to recalculate the hash of the value. This option will improve the performance of unordered containers
 253                 when rehashing is frequent or hashing the value is a slow operation. Default value is \p false.
 254             - \ref intrusive::cuckoo::probeset_type "cuckoo::probeset_type" - type of probe set, may be \p cuckoo::list or <tt>cuckoo::vector<Capacity></tt>,
 255                 Default is \p cuckoo::list.
 256             - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
 257                 Default is \p %cuckoo::empty_stat
 258         */
 259         template <typename... Options>
 260         struct make_traits {
 261             typedef typename cds::opt::make_options<
 262                 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
 263                 ,Options...
 264             >::type   type ;    ///< Result of metafunction
 265         };
 266     }   // namespace cuckoo
 267 }} // namespace cds::container
 268
 269 #endif  // #ifndef CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H