cds/intrusive/details/iterable_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-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_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H
  32 #define CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H
  33
  34 #include <type_traits>
  35 #include <cds/intrusive/details/base.h>
  36 #include <cds/opt/compare.h>
  37 #include <cds/algo/atomic.h>
  38 #include <cds/details/marked_ptr.h>
  39 #include <cds/urcu/options.h>
  40
  41 namespace cds { namespace intrusive {
  42
  43     /// \p IterableList ordered list related definitions
  44     /** @ingroup cds_intrusive_helper
  45     */
  46     namespace iterable_list {
  47
  48         /// Node type
  49         template <typename T>
  50         struct node
  51         {
  52             typedef T value_type; ///< Value type
  53
  54             atomics::atomic< node* >  next;       ///< pointer to next node in the list
  55             atomics::atomic< value_type* > data; ///< pointer to user data, \p nullptr if the node is free
  56
  57             //@cond
  58             node()
  59                 : next( nullptr )
  60                 , data( nullptr )
  61             {}
  62
  63             node( value_type * pVal )
  64                 : next( nullptr )
  65                 , data( pVal )
  66             {}
  67             //@endcond
  68         };
  69
  70         /// \p IterableList traits
  71         struct traits
  72         {
  73             /// Key comparison functor
  74             /**
  75                 No default functor is provided. If the option is not specified, the \p less is used.
  76             */
  77             typedef opt::none                       compare;
  78
  79             /// Specifies binary predicate used for key compare.
  80             /**
  81                 Default is \p std::less<T>
  82             */
  83             typedef opt::none                       less;
  84
  85             /// Node allocator
  86             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
  87
  88             /// Back-off strategy
  89             typedef cds::backoff::Default           back_off;
  90
  91             /// Disposer for removing items
  92             typedef opt::v::empty_disposer          disposer;
  93
  94             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
  95             typedef atomicity::empty_item_counter     item_counter;
  96
  97             /// C++ memory ordering model
  98             /**
  99                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 100                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 101             */
 102             typedef opt::v::relaxed_ordering        memory_model;
 103
 104             /// RCU deadlock checking policy (only for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList")
 105             /**
 106                 List of available policy see \p opt::rcu_check_deadlock
 107             */
 108             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 109         };
 110
 111         /// Metafunction converting option list to \p iterable_list::traits
 112         /**
 113             Supported \p Options are:
 114             - \p opt::compare - key comparison functor. No default functor is provided.
 115                 If the option is not specified, the \p opt::less is used.
 116             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 117             - \p opt::node_allocator - node allocator, default is \p std::allocator.
 118             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 119             - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
 120                 of GC schema the disposer may be called asynchronously.
 121             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
 122                  To enable item counting use \p atomicity::item_counter.
 123             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 124                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
 125             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
 126                 Default is \p opt::v::rcu_throw_deadlock
 127         */
 128         template <typename... Options>
 129         struct make_traits {
 130 #   ifdef CDS_DOXYGEN_INVOKED
 131             typedef implementation_defined type ;   ///< Metafunction result
 132 #   else
 133             typedef typename cds::opt::make_options<
 134                 typename cds::opt::find_type_traits< traits, Options... >::type
 135                 ,Options...
 136             >::type   type;
 137 #   endif
 138         };
 139
 140     } // namespace iterable_list
 141
 142     //@cond
 143     // Forward declaration
 144     template < class GC, typename T, class Traits = iterable_list::traits >
 145     class IterableList;
 146     //@endcond
 147
 148
 149 }}   // namespace cds::intrusive
 150
 151 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H