cds/container/details/lazy_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_LAZY_LIST_BASE_H
  32 #define CDSLIB_CONTAINER_DETAILS_LAZY_LIST_BASE_H
  33
  34 #include <cds/container/details/base.h>
  35 #include <cds/intrusive/details/lazy_list_base.h>
  36 #include <cds/urcu/options.h>
  37
  38 namespace cds { namespace container {
  39
  40     /// \p LazyList ordered list related definitions
  41     /** @ingroup cds_nonintrusive_helper
  42     */
  43     namespace lazy_list {
  44
  45         /// \p LazyList internal statistics, see \p cds::intrusive::lazy_list::stat
  46         template <typename EventCounter = cds::atomicity::event_counter>
  47         using stat = cds::intrusive::lazy_list::stat< EventCounter >;
  48
  49         /// \p LazyList empty internal statistics, see \p cds::intrusive::lazy_list::empty_stat
  50         typedef cds::intrusive::lazy_list::empty_stat empty_stat;
  51
  52         //@cond
  53         template <typename Stat = lazy_list::stat<>>
  54         using wrapped_stat = cds::intrusive::lazy_list::wrapped_stat< Stat >;
  55         //@endif
  56
  57         /// LazyList traits
  58         /**
  59             Either \p compare or \p less or both must be specified.
  60         */
  61         struct traits
  62         {
  63             /// allocator used to allocate new node
  64             typedef CDS_DEFAULT_ALLOCATOR   allocator;
  65
  66             /// Key comparing functor
  67             /**
  68                 No default functor is provided. If the option is not specified, the \p less is used.
  69             */
  70             typedef opt::none                       compare;
  71
  72             /// Specifies binary predicate used for key comparing
  73             /**
  74                 Default is \p std::less<T>.
  75             */
  76             typedef opt::none                       less;
  77
  78             /// Specifies binary functor used for comparing keys for equality
  79             /**
  80                 No default functor is provided. If \p equal_to option is not spcified, \p compare is used, if \p compare is not
  81                 specified, \p less is used.
  82             */
  83             typedef opt::none                       equal_to;
  84
  85             /// Specifies list ordering policy.
  86             /**
  87                 If \p sort is \p true, than list maintains items in sorted order, otherwise items are unordered. Default is \p true.
  88                 Note that if \p sort is \p false then lookup operations scan entire list.
  89             */
  90             static const bool sort = true;
  91
  92             /// Lock type used to lock modifying items
  93             /**
  94                 Default is cds::sync::spin
  95             */
  96             typedef cds::sync::spin                 lock_type;
  97
  98             /// back-off strategy used
  99             typedef cds::backoff::Default           back_off;
 100
 101             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 102             typedef atomicity::empty_item_counter     item_counter;
 103
 104             /// Internal statistics
 105             /**
 106                 By default, internal statistics is disabled (\p lazy_list::empty_stat).
 107                 Use \p lazy_list::stat to enable it.
 108             */
 109             typedef empty_stat                      stat;
 110
 111             /// C++ memory ordering model
 112             /**
 113                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 114                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
 115             */
 116             typedef opt::v::relaxed_ordering        memory_model;
 117
 118             /// RCU deadlock checking policy (only for \ref cds_intrusive_LazyList_rcu "RCU-based LazyList")
 119             /**
 120                 List of available options see \p opt::rcu_check_deadlock
 121             */
 122             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 123
 124             //@cond
 125             // LazyKVList: supporting for split-ordered list
 126             // key accessor (opt::none = internal key type is equal to user key type)
 127             typedef opt::none                       key_accessor;
 128
 129             //@endcond
 130         };
 131
 132         /// Metafunction converting option list to \p lazy_list::traits
 133         /**
 134             \p Options are:
 135             - \p opt::lock_type - lock type for node-level locking. Default \p is cds::sync::spin. Note that <b>each</b> node
 136                 of the list has member of type \p lock_type, therefore, heavy-weighted locking primitive is not
 137                 acceptable as candidate for \p lock_type.
 138             - \p opt::compare - key compare functor. No default functor is provided.
 139                 If the option is not specified, the \p opt::less is used.
 140             - \p opt::less - specifies binary predicate used for key compare. Default is \p std::less<T>.
 141             - \p opt::equal_to - specifies binary functor for comparing keys for equality. This option is applicable only for unordered list.
 142                 No default is provided. If \p equal_to is not specified, \p compare is used, if \p compare is not specified, \p less is used.
 143             - \p opt::sort - specifies ordering policy. Default value is \p true, i.e. the list is ordered.
 144                 Note: unordering feature is not fully supported yet.
 145             - \p opt::back_off - back-off strategy used. If the option is not specified, \p cds::backoff::Default is used.
 146             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
 147                 To enable item counting use \p atomicity::item_counter.
 148             - \p opt::stat - internal statistics. By default, it is disabled (\p lazy_list::empty_stat).
 149                 To enable it use \p lazy_list::stat
 150             - \p opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
 151             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 152                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 153         */
 154         template <typename... Options>
 155         struct make_traits {
 156 #   ifdef CDS_DOXYGEN_INVOKED
 157             typedef implementation_defined type ;   ///< Metafunction result
 158 #   else
 159             typedef typename cds::opt::make_options<
 160                 typename cds::opt::find_type_traits< traits, Options... >::type
 161                 ,Options...
 162             >::type   type;
 163 #endif
 164         };
 165
 166
 167     } // namespace lazy_list
 168
 169     // Forward declarations
 170     template <typename GC, typename T, typename Traits=lazy_list::traits>
 171     class LazyList;
 172
 173     template <typename GC, typename Key, typename Value, typename Traits=lazy_list::traits>
 174     class LazyKVList;
 175
 176     // Tag for selecting lazy list implementation
 177     /**
 178         This struct is empty and it is used only as a tag for selecting LazyList
 179         as ordered list implementation in declaration of some classes.
 180
 181         See \p split_list::traits::ordered_list as an example.
 182     */
 183     struct lazy_list_tag
 184     {};
 185
 186 }}  // namespace cds::container
 187
 188
 189 #endif  // #ifndef CDSLIB_CONTAINER_DETAILS_LAZY_LIST_BASE_H