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