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 internal statistics
  71         template <typename EventCounter = cds::atomicity::event_counter>
  72         struct stat {
  73             typedef EventCounter event_counter; ///< Event counter type
  74
  75             event_counter   m_nInsertSuccess;   ///< Number of success \p insert() operations
  76             event_counter   m_nInsertFailed;    ///< Number of failed \p insert() operations
  77             event_counter   m_nInsertRetry;     ///< Number of attempts to insert new item
  78             event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
  79             event_counter   m_nUpdateExisting;  ///< Number of existing item updates
  80             event_counter   m_nUpdateFailed;    ///< Number of failed \p update() call
  81             event_counter   m_nUpdateRetry;     ///< Number of attempts to update the item
  82             event_counter   m_nEraseSuccess;    ///< Number of successful \p erase(), \p unlink(), \p extract() operations
  83             event_counter   m_nEraseFailed;     ///< Number of failed \p erase(), \p unlink(), \p extract() operations
  84             event_counter   m_nEraseRetry;      ///< Number of attempts to \p erase() an item
  85             event_counter   m_nFindSuccess;     ///< Number of successful \p find() and \p get() operations
  86             event_counter   m_nFindFailed;      ///< Number of failed \p find() and \p get() operations
  87
  88             event_counter   m_nNodeCreated;     ///< Number of created internal nodes
  89             event_counter   m_nNodeRemoved;     ///< Number of removed internal nodes
  90
  91             //@cond
  92             void onInsertSuccess()      { ++m_nInsertSuccess;   }
  93             void onInsertFailed()       { ++m_nInsertFailed;    }
  94             void onInsertRetry()        { ++m_nInsertRetry;     }
  95             void onUpdateNew()          { ++m_nUpdateNew;       }
  96             void onUpdateExisting()     { ++m_nUpdateExisting;  }
  97             void onUpdateFailed()       { ++m_nUpdateFailed;    }
  98             void onUpdateRetry()        { ++m_nUpdateRetry;     }
  99             void onEraseSuccess()       { ++m_nEraseSuccess;    }
 100             void onEraseFailed()        { ++m_nEraseFailed;     }
 101             void onEraseRetry()         { ++m_nEraseRetry;      }
 102             void onFindSuccess()        { ++m_nFindSuccess;     }
 103             void onFindFailed()         { ++m_nFindFailed;      }
 104
 105             void onNodeCreated()        { ++m_nNodeCreated;     }
 106             void onNodeRemoved()        { ++m_nNodeRemoved;     }
 107             //@endcond
 108         };
 109
 110         /// \p IterableList empty internal statistics
 111         struct empty_stat {
 112             //@cond
 113             void onInsertSuccess()              const {}
 114             void onInsertFailed()               const {}
 115             void onInsertRetry()                const {}
 116             void onUpdateNew()                  const {}
 117             void onUpdateExisting()             const {}
 118             void onUpdateFailed()               const {}
 119             void onUpdateRetry()                const {}
 120             void onEraseSuccess()               const {}
 121             void onEraseFailed()                const {}
 122             void onEraseRetry()                 const {}
 123             void onFindSuccess()                const {}
 124             void onFindFailed()                 const {}
 125
 126             void onNodeCreated()                const {}
 127             void onNodeRemoved()                const {}
 128             //@endcond
 129         };
 130
 131         //@cond
 132         template <typename Stat = iterable_list::stat<>>
 133         struct wrapped_stat {
 134             typedef Stat stat_type;
 135
 136             wrapped_stat( stat_type& st )
 137                 : m_stat( st )
 138             {}
 139
 140             void onInsertSuccess()   { m_stat.onInsertSuccess(); }
 141             void onInsertFailed()    { m_stat.onInsertFailed();  }
 142             void onInsertRetry()     { m_stat.onInsertRetry();   }
 143             void onUpdateNew()       { m_stat.onUpdateNew();     }
 144             void onUpdateExisting()  { m_stat.onUpdateExisting();}
 145             void onUpdateFailed()    { m_stat.onUpdateFailed();  }
 146             void onUpdateRetry()     { m_stat.onUpdateRetry();   }
 147             void onEraseSuccess()    { m_stat.onEraseSuccess();  }
 148             void onEraseFailed()     { m_stat.onEraseFailed();   }
 149             void onEraseRetry()      { m_stat.onEraseRetry();    }
 150             void onFindSuccess()     { m_stat.onFindSuccess();   }
 151             void onFindFailed()      { m_stat.onFindFailed();    }
 152
 153             void onNodeCreated()     { m_stat.onNodeCreated();   }
 154             void onNodeRemoved()     { m_stat.onNodeRemoved();   }
 155
 156             stat_type& m_stat;
 157         };
 158         //@endcond
 159
 160
 161         /// \p IterableList traits
 162         struct traits
 163         {
 164             /// Key comparison functor
 165             /**
 166                 No default functor is provided. If the option is not specified, the \p less is used.
 167             */
 168             typedef opt::none                       compare;
 169
 170             /// Specifies binary predicate used for key compare.
 171             /**
 172                 Default is \p std::less<T>
 173             */
 174             typedef opt::none                       less;
 175
 176             /// Node allocator
 177             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 178
 179             /// Back-off strategy
 180             typedef cds::backoff::Default           back_off;
 181
 182             /// Disposer for removing items
 183             typedef opt::v::empty_disposer          disposer;
 184
 185             /// Internal statistics
 186             /**
 187                 By default, internal statistics is disabled (\p iterable_list::empty_stat).
 188                 Use \p iterable_list::stat to enable it.
 189             */
 190             typedef empty_stat                      stat;
 191
 192             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 193             typedef atomicity::empty_item_counter   item_counter;
 194
 195             /// C++ memory ordering model
 196             /**
 197                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 198                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 199             */
 200             typedef opt::v::relaxed_ordering        memory_model;
 201
 202             /// RCU deadlock checking policy (only for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList")
 203             /**
 204                 List of available policy see \p opt::rcu_check_deadlock
 205             */
 206             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 207         };
 208
 209         /// Metafunction converting option list to \p iterable_list::traits
 210         /**
 211             Supported \p Options are:
 212             - \p opt::compare - key comparison functor. No default functor is provided.
 213                 If the option is not specified, the \p opt::less is used.
 214             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 215             - \p opt::node_allocator - node allocator, default is \p std::allocator.
 216             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 217             - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
 218                 of GC schema the disposer may be called asynchronously.
 219             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
 220                  To enable item counting use \p atomicity::item_counter.
 221             - \p opt::stat - internal statistics. By default, it is disabled (\p iterable_list::empty_stat).
 222                 To enable it use \p iterable_list::stat
 223             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 224                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
 225             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
 226                 Default is \p opt::v::rcu_throw_deadlock
 227         */
 228         template <typename... Options>
 229         struct make_traits {
 230 #   ifdef CDS_DOXYGEN_INVOKED
 231             typedef implementation_defined type ;   ///< Metafunction result
 232 #   else
 233             typedef typename cds::opt::make_options<
 234                 typename cds::opt::find_type_traits< traits, Options... >::type
 235                 ,Options...
 236             >::type   type;
 237 #   endif
 238         };
 239
 240
 241         //@cond
 242         template <typename Stat>
 243         struct select_stat_wrapper
 244         {
 245             typedef Stat stat;
 246             typedef iterable_list::wrapped_stat<Stat> wrapped_stat;
 247             enum {
 248                 empty = false
 249             };
 250         };
 251
 252         template <>
 253         struct select_stat_wrapper< empty_stat >
 254         {
 255             typedef empty_stat stat;
 256             typedef empty_stat wrapped_stat;
 257             enum {
 258                 empty = true
 259             };
 260         };
 261
 262         template <typename Stat>
 263         struct select_stat_wrapper< iterable_list::wrapped_stat<Stat>>: public select_stat_wrapper<Stat>
 264         {};
 265         //@endcond
 266
 267     } // namespace iterable_list
 268
 269     //@cond
 270     // Forward declaration
 271     template < class GC, typename T, class Traits = iterable_list::traits >
 272     class IterableList;
 273     //@endcond
 274
 275     //@cond
 276     template <typename GC, typename T, typename Traits>
 277     struct is_iterable_list< IterableList< GC, T, Traits >> {
 278         enum {
 279             value = true
 280         };
 281     };
 282     //@endcond
 283
 284 }}   // namespace cds::intrusive
 285
 286 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H