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