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