cds/container/details/make_split_list_set.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_MAKE_SPLIT_LIST_SET_H
  32 #define CDSLIB_CONTAINER_DETAILS_MAKE_SPLIT_LIST_SET_H
  33
  34 #include <cds/container/details/split_list_base.h>
  35 #include <cds/details/allocator.h>
  36 #include <cds/details/binary_functor_wrapper.h>
  37
  38 //@cond
  39 namespace cds { namespace container {
  40
  41     // Forward declaration
  42     struct michael_list_tag;
  43     struct lazy_list_tag;
  44
  45     namespace details {
  46
  47 #ifdef CDSLIB_CONTAINER_DETAILS_MICHAEL_LIST_BASE_H
  48         // if michael_list included
  49
  50         template <typename GC, typename T, typename Traits>
  51         struct make_split_list_set< GC, T, michael_list_tag, Traits >
  52         {
  53             typedef GC      gc;
  54             typedef T       value_type;
  55             typedef Traits  original_traits;
  56
  57             typedef typename cds::opt::select_default<
  58                 typename original_traits::ordered_list_traits,
  59                 cds::container::michael_list::traits
  60             >::type         original_ordered_list_traits;
  61
  62             typedef cds::intrusive::split_list::node< cds::intrusive::michael_list::node<gc> > primary_node_type;
  63             struct node_type: public primary_node_type
  64             {
  65                 value_type  m_Value;
  66
  67                 template <typename Q>
  68                 explicit node_type( Q const& v )
  69                     : m_Value(v)
  70                 {}
  71                 template <typename Q, typename... Args>
  72                 explicit node_type( Q&& q, Args&&... args )
  73                     : m_Value( std::forward<Q>(q), std::forward<Args>(args)... )
  74                 {}
  75
  76                 node_type() = delete;
  77             };
  78
  79             typedef typename cds::opt::select_default<
  80                 typename original_traits::ordered_list_traits,
  81                 typename original_traits::allocator,
  82                 typename cds::opt::select_default<
  83                     typename original_traits::ordered_list_traits::allocator,
  84                     typename original_traits::allocator
  85                 >::type
  86             >::type node_allocator_;
  87
  88             typedef typename node_allocator_::template rebind<node_type>::other node_allocator_type;
  89
  90             typedef cds::details::Allocator< node_type, node_allocator_type >   cxx_node_allocator;
  91             struct node_deallocator
  92             {
  93                 void operator ()( node_type * pNode )
  94                 {
  95                     cxx_node_allocator().Delete( pNode );
  96                 }
  97             };
  98
  99             typedef typename opt::details::make_comparator< value_type, original_ordered_list_traits >::type key_comparator;
 100
 101             typedef typename original_traits::key_accessor key_accessor;
 102
 103             struct value_accessor
 104             {
 105                 typename key_accessor::key_type const& operator()( node_type const& node ) const
 106                 {
 107                     return key_accessor()(node.m_Value);
 108                 }
 109             };
 110
 111             template <typename Predicate>
 112             struct predicate_wrapper {
 113                 typedef cds::details::predicate_wrapper< node_type, Predicate, value_accessor > type;
 114             };
 115
 116             struct ordered_list_traits: public original_ordered_list_traits
 117             {
 118                 typedef cds::intrusive::michael_list::base_hook<
 119                     opt::gc<gc>
 120                 >   hook;
 121                 typedef cds::atomicity::empty_item_counter item_counter;
 122                 typedef node_deallocator  disposer;
 123                 typedef cds::details::compare_wrapper< node_type, key_comparator, value_accessor > compare;
 124                 static CDS_CONSTEXPR const opt::link_check_type link_checker = cds::intrusive::michael_list::traits::link_checker;
 125             };
 126
 127             struct traits: public original_traits
 128             {
 129                 struct hash: public original_traits::hash
 130                 {
 131                     typedef typename original_traits::hash  base_class;
 132
 133                     size_t operator()(node_type const& v ) const
 134                     {
 135                         return base_class::operator()( key_accessor()( v.m_Value ) );
 136                     }
 137                     template <typename Q>
 138                     size_t operator()( Q const& k ) const
 139                     {
 140                         return base_class::operator()( k );
 141                     }
 142                 };
 143             };
 144
 145             class ordered_list: public cds::intrusive::MichaelList< gc, node_type, ordered_list_traits >
 146             {};
 147             //typedef cds::intrusive::MichaelList< gc, node_type, ordered_list_traits > ordered_list;
 148             typedef cds::intrusive::SplitListSet< gc, ordered_list, traits > type;
 149         };
 150 #endif  // ifdef CDSLIB_CONTAINER_DETAILS_MICHAEL_LIST_BASE_H
 151
 152 #ifdef CDSLIB_CONTAINER_DETAILS_LAZY_LIST_BASE_H
 153         // if lazy_list included
 154         template <typename GC, typename T, typename Traits>
 155         struct make_split_list_set< GC, T, lazy_list_tag, Traits >
 156         {
 157             typedef GC      gc;
 158             typedef T       value_type;
 159             typedef Traits  original_traits;
 160
 161             typedef typename cds::opt::select_default<
 162                 typename original_traits::ordered_list_traits,
 163                 cds::container::lazy_list::traits
 164             >::type         original_ordered_list_traits;
 165
 166             typedef typename cds::opt::select_default<
 167                 typename original_ordered_list_traits::lock_type,
 168                 typename cds::container::lazy_list::traits::lock_type
 169             >::type   lock_type;
 170
 171             typedef cds::intrusive::split_list::node< cds::intrusive::lazy_list::node<gc, lock_type > > primary_node_type;
 172             struct node_type: public primary_node_type
 173             {
 174                 value_type  m_Value;
 175
 176                 template <typename Q>
 177                 explicit node_type( const Q& v )
 178                     : m_Value(v)
 179                 {}
 180
 181                 template <typename Q, typename... Args>
 182                 explicit node_type( Q&& q, Args&&... args )
 183                     : m_Value( std::forward<Q>(q), std::forward<Args>(args)... )
 184                 {}
 185
 186                 node_type() = delete;
 187             };
 188
 189             typedef typename cds::opt::select_default<
 190                 typename original_traits::ordered_list_traits,
 191                 typename original_traits::allocator,
 192                 typename cds::opt::select_default<
 193                     typename original_traits::ordered_list_traits::allocator,
 194                     typename original_traits::allocator
 195                 >::type
 196             >::type node_allocator_;
 197
 198             typedef typename node_allocator_::template rebind<node_type>::other node_allocator_type;
 199
 200             typedef cds::details::Allocator< node_type, node_allocator_type >   cxx_node_allocator;
 201             struct node_deallocator
 202             {
 203                 void operator ()( node_type * pNode )
 204                 {
 205                     cxx_node_allocator().Delete( pNode );
 206                 }
 207             };
 208
 209             typedef typename opt::details::make_comparator< value_type, original_ordered_list_traits >::type key_comparator;
 210
 211             typedef typename original_traits::key_accessor key_accessor;
 212
 213             struct value_accessor
 214             {
 215                 typename key_accessor::key_type const & operator()( node_type const & node ) const
 216                 {
 217                     return key_accessor()(node.m_Value);
 218                 }
 219             };
 220
 221             template <typename Predicate>
 222             struct predicate_wrapper {
 223                 typedef cds::details::predicate_wrapper< node_type, Predicate, value_accessor > type;
 224             };
 225
 226             struct ordered_list_traits: public original_ordered_list_traits
 227             {
 228                 typedef cds::intrusive::lazy_list::base_hook<
 229                     opt::gc<gc>
 230                     ,opt::lock_type< lock_type >
 231                 >  hook;
 232                 typedef cds::atomicity::empty_item_counter item_counter;
 233                 typedef node_deallocator                disposer;
 234                 typedef cds::details::compare_wrapper< node_type, key_comparator, value_accessor > compare;
 235                 static CDS_CONSTEXPR const opt::link_check_type link_checker = cds::intrusive::lazy_list::traits::link_checker;
 236             };
 237
 238             struct traits: public original_traits
 239             {
 240                 struct hash: public original_traits::hash
 241                 {
 242                     typedef typename original_traits::hash  base_class;
 243
 244                     size_t operator()(node_type const& v ) const
 245                     {
 246                         return base_class::operator()( key_accessor()( v.m_Value ));
 247                     }
 248                     template <typename Q>
 249                     size_t operator()( Q const& k ) const
 250                     {
 251                         return base_class::operator()( k );
 252                     }
 253                 };
 254             };
 255
 256             class ordered_list: public cds::intrusive::LazyList< gc, node_type, ordered_list_traits >
 257             {};
 258             //typedef cds::intrusive::LazyList< gc, node_type, ordered_list_traits >  ordered_list;
 259             typedef cds::intrusive::SplitListSet< gc, ordered_list, traits >   type;
 260         };
 261 #endif  // ifdef CDSLIB_CONTAINER_DETAILS_LAZY_LIST_BASE_H
 262
 263     }   // namespace details
 264 }}  // namespace cds::container
 265 //@endcond
 266
 267 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_MAKE_SPLIT_LIST_SET_H