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