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-2017
   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_nNullPrevABA;     ///< Number of ABA-problem for \p nullptr prev node
  85             event_counter   m_nNewNodeCreated;  ///< Number of new node created when we try to insert new data
  86             event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
  87             event_counter   m_nUpdateExisting;  ///< Number of existing item updates
  88             event_counter   m_nUpdateFailed;    ///< Number of failed \p update() call
  89             event_counter   m_nUpdateRetry;     ///< Number of attempts to update the item
  90             event_counter   m_nEraseSuccess;    ///< Number of successful \p erase(), \p unlink(), \p extract() operations
  91             event_counter   m_nEraseFailed;     ///< Number of failed \p erase(), \p unlink(), \p extract() operations
  92             event_counter   m_nEraseRetry;      ///< Number of attempts to \p erase() an item
  93             event_counter   m_nFindSuccess;     ///< Number of successful \p find() and \p get() operations
  94             event_counter   m_nFindFailed;      ///< Number of failed \p find() and \p get() operations
  95
  96             event_counter   m_nNodeCreated;     ///< Number of created internal nodes
  97             event_counter   m_nNodeRemoved;     ///< Number of removed internal nodes
  98
  99             //@cond
 100             void onInsertSuccess()      { ++m_nInsertSuccess;   }
 101             void onInsertFailed()       { ++m_nInsertFailed;    }
 102             void onInsertRetry()        { ++m_nInsertRetry;     }
 103             void onReuseNode()          { ++m_nReuseNode;       }
 104             void onNodeMarkFailed()     { ++m_nNodeMarkFailed;  }
 105             void onNodeSeqBreak()       { ++m_nNodeSeqBreak;    }
 106             void onNullPrevABA()        { ++m_nNullPrevABA;     }
 107             void onNewNodeCreated()     { ++m_nNewNodeCreated;  }
 108             void onUpdateNew()          { ++m_nUpdateNew;       }
 109             void onUpdateExisting()     { ++m_nUpdateExisting;  }
 110             void onUpdateFailed()       { ++m_nUpdateFailed;    }
 111             void onUpdateRetry()        { ++m_nUpdateRetry;     }
 112             void onEraseSuccess()       { ++m_nEraseSuccess;    }
 113             void onEraseFailed()        { ++m_nEraseFailed;     }
 114             void onEraseRetry()         { ++m_nEraseRetry;      }
 115             void onFindSuccess()        { ++m_nFindSuccess;     }
 116             void onFindFailed()         { ++m_nFindFailed;      }
 117
 118             void onNodeCreated()        { ++m_nNodeCreated;     }
 119             void onNodeRemoved()        { ++m_nNodeRemoved;     }
 120             //@endcond
 121         };
 122
 123         /// \p IterableList empty internal statistics
 124         struct empty_stat {
 125             //@cond
 126             void onInsertSuccess()              const {}
 127             void onInsertFailed()               const {}
 128             void onInsertRetry()                const {}
 129             void onReuseNode()                  const {}
 130             void onNodeMarkFailed()             const {}
 131             void onNodeSeqBreak()               const {}
 132             void onNullPrevABA()                const {}
 133             void onNewNodeCreated()             const {}
 134             void onUpdateNew()                  const {}
 135             void onUpdateExisting()             const {}
 136             void onUpdateFailed()               const {}
 137             void onUpdateRetry()                const {}
 138             void onEraseSuccess()               const {}
 139             void onEraseFailed()                const {}
 140             void onEraseRetry()                 const {}
 141             void onFindSuccess()                const {}
 142             void onFindFailed()                 const {}
 143
 144             void onNodeCreated()                const {}
 145             void onNodeRemoved()                const {}
 146             //@endcond
 147         };
 148
 149         //@cond
 150         template <typename Stat = iterable_list::stat<>>
 151         struct wrapped_stat {
 152             typedef Stat stat_type;
 153
 154             wrapped_stat( stat_type& st )
 155                 : m_stat( st )
 156             {}
 157
 158             void onInsertSuccess()   { m_stat.onInsertSuccess(); }
 159             void onInsertFailed()    { m_stat.onInsertFailed();  }
 160             void onInsertRetry()     { m_stat.onInsertRetry();   }
 161             void onReuseNode()       { m_stat.onReuseNode();     }
 162             void onNodeMarkFailed()  { m_stat.onNodeMarkFailed();}
 163             void onNodeSeqBreak()    { m_stat.onNodeSeqBreak();  }
 164             void onNullPrevABA()     { m_stat.onNullPrevABA();   }
 165             void onNewNodeCreated()  { m_stat.onNewNodeCreated();}
 166             void onUpdateNew()       { m_stat.onUpdateNew();     }
 167             void onUpdateExisting()  { m_stat.onUpdateExisting();}
 168             void onUpdateFailed()    { m_stat.onUpdateFailed();  }
 169             void onUpdateRetry()     { m_stat.onUpdateRetry();   }
 170             void onEraseSuccess()    { m_stat.onEraseSuccess();  }
 171             void onEraseFailed()     { m_stat.onEraseFailed();   }
 172             void onEraseRetry()      { m_stat.onEraseRetry();    }
 173             void onFindSuccess()     { m_stat.onFindSuccess();   }
 174             void onFindFailed()      { m_stat.onFindFailed();    }
 175
 176             void onNodeCreated()     { m_stat.onNodeCreated();   }
 177             void onNodeRemoved()     { m_stat.onNodeRemoved();   }
 178
 179             stat_type& m_stat;
 180         };
 181         //@endcond
 182
 183
 184         /// \p IterableList traits
 185         struct traits
 186         {
 187             /// Key comparison functor
 188             /**
 189                 No default functor is provided. If the option is not specified, the \p less is used.
 190             */
 191             typedef opt::none                       compare;
 192
 193             /// Specifies binary predicate used for key compare.
 194             /**
 195                 Default is \p std::less<T>
 196             */
 197             typedef opt::none                       less;
 198
 199             /// Node allocator
 200             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
 201
 202             /// Back-off strategy
 203             typedef cds::backoff::Default           back_off;
 204
 205             /// Disposer for removing items
 206             typedef opt::v::empty_disposer          disposer;
 207
 208             /// Internal statistics
 209             /**
 210                 By default, internal statistics is disabled (\p iterable_list::empty_stat).
 211                 Use \p iterable_list::stat to enable it.
 212             */
 213             typedef empty_stat                      stat;
 214
 215             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter or \p atomicity::cache_friendly_item_counter to enable item counting
 216             typedef atomicity::empty_item_counter   item_counter;
 217
 218             /// C++ memory ordering model
 219             /**
 220                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 221                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 222             */
 223             typedef opt::v::relaxed_ordering        memory_model;
 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 or \p atomicity::cache_friendly_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         */
 243         template <typename... Options>
 244         struct make_traits {
 245 #   ifdef CDS_DOXYGEN_INVOKED
 246             typedef implementation_defined type ;   ///< Metafunction result
 247 #   else
 248             typedef typename cds::opt::make_options<
 249                 typename cds::opt::find_type_traits< traits, Options... >::type
 250                 ,Options...
 251             >::type   type;
 252 #   endif
 253         };
 254
 255
 256         //@cond
 257         template <typename Stat>
 258         struct select_stat_wrapper
 259         {
 260             typedef Stat stat;
 261             typedef iterable_list::wrapped_stat<Stat> wrapped_stat;
 262             enum {
 263                 empty = false
 264             };
 265         };
 266
 267         template <>
 268         struct select_stat_wrapper< empty_stat >
 269         {
 270             typedef empty_stat stat;
 271             typedef empty_stat wrapped_stat;
 272             enum {
 273                 empty = true
 274             };
 275         };
 276
 277         template <typename Stat>
 278         struct select_stat_wrapper< iterable_list::wrapped_stat<Stat>>: public select_stat_wrapper<Stat>
 279         {};
 280         //@endcond
 281
 282     } // namespace iterable_list
 283
 284     //@cond
 285     // Forward declaration
 286     template < class GC, typename T, class Traits = iterable_list::traits >
 287     class IterableList;
 288     //@endcond
 289
 290 }}   // namespace cds::intrusive
 291
 292 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_ITERABLE_LIST_BASE_H