cds/container/details/split_list_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-2017
   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_SPLIT_LIST_BASE_H
  32 #define CDSLIB_CONTAINER_DETAILS_SPLIT_LIST_BASE_H
  33
  34 #include <cds/intrusive/details/split_list_base.h>
  35
  36 namespace cds { namespace container {
  37
  38     // forward declaration
  39     struct michael_list_tag;
  40
  41     /// SplitListSet related definitions
  42     /** @ingroup cds_nonintrusive_helper
  43     */
  44     namespace split_list {
  45         /// Internal statistics, see \p cds::intrusive::split_list::stat
  46         template <typename Counter = cds::intrusive::split_list::stat<>::counter_type >
  47         using stat = cds::intrusive::split_list::stat<Counter>;
  48
  49         /// Disabled internal statistics, see \p cds::intrusive::split_list::empty_stat
  50         typedef cds::intrusive::split_list::empty_stat empty_stat;
  51
  52         /// Selector of bucket table implementation = typedef for \p intrusive::split_list::dynamic_bucket_table
  53         template <bool Value>
  54         using dynamic_bucket_table = cds::intrusive::split_list::dynamic_bucket_table<Value>;
  55
  56         /// @copydoc cds::intrusive::split_list::bit_reversal
  57         template <typename Type>
  58         using bit_reversal = cds::intrusive::split_list::bit_reversal<Type>;
  59
  60         using cds::intrusive::split_list::static_bucket_table;
  61         using cds::intrusive::split_list::expandable_bucket_table;
  62
  63         //@cond
  64         namespace details {
  65
  66             template <typename Key, typename Value, typename Traits, typename Opt>
  67             struct wrap_map_traits_helper {
  68                 typedef Opt key_accessor;
  69             };
  70
  71             template <typename Key, typename Value, typename Traits >
  72             struct wrap_map_traits_helper<Key, Value, Traits, opt::none>
  73             {
  74                 struct key_accessor
  75                 {
  76                     typedef Key     key_type;
  77                     key_type const & operator()( std::pair<Key const, Value> const & val ) const
  78                     {
  79                         return val.first;
  80                     }
  81                 };
  82             };
  83
  84             template <typename Key, typename Value, typename Traits>
  85             struct wrap_map_traits: public Traits
  86             {
  87                 typedef typename wrap_map_traits_helper<Key, Value, Traits, typename Traits::key_accessor>::key_accessor    key_accessor;
  88             };
  89
  90             template <typename Value, typename Traits, typename Opt>
  91             struct wrap_set_traits_helper {
  92                 typedef Opt key_accessor;
  93             };
  94
  95             template <typename Value, typename Traits >
  96             struct wrap_set_traits_helper<Value, Traits, opt::none>
  97             {
  98                 struct key_accessor
  99                 {
 100                     typedef Value     key_type;
 101                     key_type const& operator()( Value const& val ) const
 102                     {
 103                         return val;
 104                     }
 105                 };
 106             };
 107
 108             template <typename Value, typename Traits>
 109             struct wrap_set_traits: public Traits
 110             {
 111                 typedef typename wrap_set_traits_helper<Value, Traits, typename Traits::key_accessor>::key_accessor key_accessor;
 112             };
 113         }  // namespace details
 114         //@endcond
 115
 116
 117         /// \p SplitListSet traits
 118         struct traits: public intrusive::split_list::traits
 119         {
 120             // Ordered list implementation
 121             /**
 122                 Selects appropriate ordered-list implementation for split-list.
 123                 Supported types are:
 124                 - \p michael_list_tag - for \p MichaelList
 125                 - \p lazy_list_tag - for \p LazyList
 126                 - \p iterable_list_tag - for \p IterableList
 127             */
 128             typedef michael_list_tag    ordered_list;
 129
 130             // Ordered list traits
 131             /**
 132                 Specifyes traits for selected ordered list type, default type:
 133                 - for \p michael_list_tag: \p container::michael_list::traits.
 134                 - for \p lazy_list_tag: \p container::lazy_list::traits.
 135                 - for \p iterable_list_tag: \p container::iterable_list::traits.
 136
 137                 If this type is \p opt::none, the ordered list traits is combined with default
 138                 ordered list traits and split-list traits.
 139             */
 140             typedef opt::none           ordered_list_traits;
 141
 142             //@cond
 143             typedef opt::none           key_accessor;
 144             //@endcond
 145         };
 146
 147         /// Option to select ordered list class for split-list
 148         /**
 149             This option selects appropriate ordered list class for containers based on split-list.
 150             Template parameter \p Type may be \p michael_list_tag or \p lazy_list_tag.
 151         */
 152         template <class Type>
 153         struct ordered_list
 154         {
 155             //@cond
 156             template<class Base> struct pack: public Base
 157             {
 158                 typedef Type ordered_list;
 159             };
 160             //@endcond
 161         };
 162
 163         /// Option to specify ordered list type traits
 164         /**
 165             The \p Type template parameter specifies ordered list type traits.
 166             It depends on type of ordered list selected.
 167         */
 168         template <class Type>
 169         struct ordered_list_traits
 170         {
 171             //@cond
 172             template<class Base> struct pack: public Base
 173             {
 174                 typedef Type ordered_list_traits;
 175             };
 176             //@endcond
 177         };
 178
 179         /// Metafunction converting option list to traits struct
 180         /**
 181             Available \p Options:
 182             - \p split_list::ordered_list - a tag for ordered list implementation.
 183             - \p split_list::ordered_list_traits - type traits for ordered list implementation.
 184                 For \p MichaelList use \p container::michael_list::traits or derivatives,
 185                 for \p LazyList use \p container::lazy_list::traits or derivatives.
 186             - plus any option from \p intrusive::split_list::make_traits
 187         */
 188         template <typename... Options>
 189         struct make_traits {
 190             typedef typename cds::opt::make_options< traits, Options...>::type type  ;   ///< Result of metafunction
 191         };
 192     }   // namespace split_list
 193
 194     //@cond
 195     // Forward declarations
 196     template <class GC, class T, class Traits = split_list::traits>
 197     class SplitListSet;
 198
 199     template <class GC, typename Key, typename Value, class Traits = split_list::traits>
 200     class SplitListMap;
 201     //@endcond
 202
 203     //@cond
 204     // Forward declaration
 205     namespace details {
 206         template <typename GC, typename T, typename OrderedListTag, typename Traits>
 207         struct make_split_list_set;
 208
 209         template <typename GC, typename Key, typename Value, typename OrderedListTag, typename Traits>
 210         struct make_split_list_map;
 211     }
 212     //@endcond
 213
 214 }}  // namespace cds::container
 215
 216
 217 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_SPLIT_LIST_BASE_H