cds/container/details/michael_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_CONTAINER_DETAILS_MICHAEL_LIST_BASE_H
  32 #define CDSLIB_CONTAINER_DETAILS_MICHAEL_LIST_BASE_H
  33
  34 #include <cds/container/details/base.h>
  35 #include <cds/intrusive/details/michael_list_base.h>
  36 #include <cds/urcu/options.h>
  37
  38 namespace cds { namespace container {
  39
  40     /// MichaelList ordered list related definitions
  41     /** @ingroup cds_nonintrusive_helper
  42     */
  43     namespace michael_list {
  44
  45         /// \p MichaelList internal statistics, see \p cds::intrusive::michael_list::stat
  46         template <typename EventCounter = cds::atomicity::event_counter>
  47         using stat = cds::intrusive::michael_list::stat< EventCounter >;
  48
  49         /// \p MichaelList empty internal statistics, see \p cds::intrusive::michael_list::empty_stat
  50         typedef cds::intrusive::michael_list::empty_stat empty_stat;
  51
  52         //@cond
  53         template <typename Stat = michael_list::stat<>>
  54         using wrapped_stat = cds::intrusive::michael_list::wrapped_stat< Stat >;
  55         //@endif
  56
  57         /// MichaelList traits
  58         struct traits
  59         {
  60             typedef CDS_DEFAULT_ALLOCATOR   allocator;   ///< allocator used to allocate new node
  61
  62             /// Key comparison functor
  63             /**
  64                 No default functor is provided. If the option is not specified, the \p less is used.
  65             */
  66             typedef opt::none                       compare;
  67
  68             /// Specifies binary predicate used for key comparison.
  69             /**
  70                 Default is \p std::less<T>.
  71             */
  72             typedef opt::none                       less;
  73
  74             /// Back-off strategy
  75             typedef cds::backoff::empty             back_off;
  76
  77             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
  78             typedef atomicity::empty_item_counter     item_counter;
  79
  80             /// Internal statistics
  81             /**
  82                 By default, internal statistics is disabled (\p michael_list::empty_stat).
  83                 Use \p michael_list::stat to enable it.
  84             */
  85             typedef empty_stat                      stat;
  86
  87             /// C++ memory ordering model
  88             /**
  89                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
  90                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
  91             */
  92             typedef opt::v::relaxed_ordering        memory_model;
  93
  94             /// RCU deadlock checking policy (only for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList")
  95             /**
  96                 List of available options see opt::rcu_check_deadlock
  97             */
  98             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
  99
 100             //@cond
 101             // MichaelKVList: supporting for split-ordered list
 102             // key accessor (opt::none = internal key type is equal to user key type)
 103             typedef opt::none                       key_accessor;
 104             //@endcond
 105         };
 106
 107         /// Metafunction converting option list to \p michael_list::traits
 108         /**
 109             Supported \p Options are:
 110             - \p opt::compare - key comparison functor. No default functor is provided.
 111                 If the option is not specified, the \p opt::less is used.
 112             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 113             - \p opt::allocator - an allocator, default is \p CDS_DEFAULT_ALLOCATOR
 114             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 115             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
 116                  To enable item counting use \p atomicity::item_counter.
 117             - \p opt::stat - internal statistics. By default, it is disabled (\p michael_list::empty_stat).
 118                 To enable it use \p michael_list::stat
 119             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 120                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
 121             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
 122                 Default is \p opt::v::rcu_throw_deadlock
 123         */
 124         template <typename... Options>
 125         struct make_traits {
 126 #   ifdef CDS_DOXYGEN_INVOKED
 127             typedef implementation_defined type ;   ///< Metafunction result
 128 #   else
 129             typedef typename cds::opt::make_options<
 130                 typename cds::opt::find_type_traits< traits, Options... >::type
 131                 ,Options...
 132             >::type   type;
 133 #endif
 134         };
 135
 136
 137     } // namespace michael_list
 138
 139     // Forward declarations
 140     template <typename GC, typename T, typename Traits=michael_list::traits>
 141     class MichaelList;
 142
 143     template <typename GC, typename Key, typename Value, typename Traits=michael_list::traits>
 144     class MichaelKVList;
 145
 146     // Tag for selecting Michael's list implementation
 147     /**
 148         This struct is empty and it is used only as a tag for selecting MichaelList
 149         as ordered list implementation in declaration of some classes.
 150
 151         See split_list::traits::ordered_list as an example.
 152     */
 153     struct michael_list_tag
 154     {};
 155
 156 }}  // namespace cds::container
 157
 158
 159 #endif  // #ifndef CDSLIB_CONTAINER_DETAILS_MICHAEL_LIST_BASE_H