cds/intrusive/details/michael_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_MICHAEL_LIST_BASE_H
  32 #define CDSLIB_INTRUSIVE_DETAILS_MICHAEL_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     /// MichaelList ordered list related definitions
  44     /** @ingroup cds_intrusive_helper
  45     */
  46     namespace michael_list {
  47         /// Michael's list node
  48         /**
  49             Template parameters:
  50             - \p GC - garbage collector
  51             - \p Tag - a \ref cds_intrusive_hook_tag "tag"
  52         */
  53         template <class GC, typename Tag = opt::none>
  54         struct node
  55         {
  56             typedef GC              gc  ;   ///< Garbage collector
  57             typedef Tag             tag ;   ///< tag
  58
  59             typedef cds::details::marked_ptr<node, 1>   marked_ptr;   ///< marked pointer
  60             typedef typename gc::template atomic_marked_ptr<marked_ptr> atomic_marked_ptr;   ///< atomic marked pointer specific for GC
  61
  62             atomic_marked_ptr m_pNext ; ///< pointer to the next node in the container
  63
  64             CDS_CONSTEXPR node() CDS_NOEXCEPT
  65                 : m_pNext( nullptr )
  66             {}
  67         };
  68
  69         //@cond
  70         template <typename GC, typename Node, typename MemoryModel>
  71         struct node_cleaner {
  72             void operator()( Node * p )
  73             {
  74                 typedef typename Node::marked_ptr marked_ptr;
  75                 p->m_pNext.store( marked_ptr(), MemoryModel::memory_order_release );
  76             }
  77         };
  78         //@endcond
  79
  80         //@cond
  81         struct undefined_gc;
  82         struct default_hook {
  83             typedef undefined_gc    gc;
  84             typedef opt::none       tag;
  85         };
  86         //@endcond
  87
  88         //@cond
  89         template < typename HookType, typename... Options>
  90         struct hook
  91         {
  92             typedef typename opt::make_options< default_hook, Options...>::type  options;
  93             typedef typename options::gc    gc;
  94             typedef typename options::tag   tag;
  95             typedef node<gc, tag>   node_type;
  96             typedef HookType        hook_type;
  97         };
  98         //@endcond
  99
 100         /// Base hook
 101         /**
 102             \p Options are:
 103             - opt::gc - garbage collector used.
 104             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 105         */
 106         template < typename... Options >
 107         struct base_hook: public hook< opt::base_hook_tag, Options... >
 108         {};
 109
 110         /// Member hook
 111         /**
 112             \p MemberOffset defines offset in bytes of \ref node member into your structure.
 113             Use \p offsetof macro to define \p MemberOffset
 114
 115             \p Options are:
 116             - opt::gc - garbage collector used.
 117             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 118         */
 119         template < size_t MemberOffset, typename... Options >
 120         struct member_hook: public hook< opt::member_hook_tag, Options... >
 121         {
 122             //@cond
 123             static const size_t c_nMemberOffset = MemberOffset;
 124             //@endcond
 125         };
 126
 127         /// Traits hook
 128         /**
 129             \p NodeTraits defines type traits for node.
 130             See \ref node_traits for \p NodeTraits interface description
 131
 132             \p Options are:
 133             - opt::gc - garbage collector used.
 134             - opt::tag - a \ref cds_intrusive_hook_tag "tag"
 135         */
 136         template <typename NodeTraits, typename... Options >
 137         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
 138         {
 139             //@cond
 140             typedef NodeTraits node_traits;
 141             //@endcond
 142         };
 143
 144         /// Checks link
 145         template <typename Node>
 146         struct link_checker
 147         {
 148             //@cond
 149             typedef Node node_type;
 150             //@endcond
 151
 152             /// Checks if the link field of node \p pNode is \p nullptr
 153             /**
 154                 An asserting is generated if \p pNode link field is not \p nullptr
 155             */
 156             static void is_empty( const node_type * pNode )
 157             {
 158                 assert( pNode->m_pNext.load( atomics::memory_order_relaxed ) == nullptr );
 159                 CDS_UNUSED( pNode );
 160             }
 161         };
 162
 163         //@cond
 164         template <class GC, typename Node, opt::link_check_type LinkType >
 165         struct link_checker_selector;
 166
 167         template <typename GC, typename Node>
 168         struct link_checker_selector< GC, Node, opt::never_check_link >
 169         {
 170             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 171         };
 172
 173         template <typename GC, typename Node>
 174         struct link_checker_selector< GC, Node, opt::debug_check_link >
 175         {
 176 #       ifdef _DEBUG
 177             typedef link_checker<Node>  type;
 178 #       else
 179             typedef intrusive::opt::v::empty_link_checker<Node>  type;
 180 #       endif
 181         };
 182
 183         template <typename GC, typename Node>
 184         struct link_checker_selector< GC, Node, opt::always_check_link >
 185         {
 186             typedef link_checker<Node>  type;
 187         };
 188         //@endcond
 189
 190         /// Metafunction for selecting appropriate link checking policy
 191         template < typename Node, opt::link_check_type LinkType >
 192         struct get_link_checker
 193         {
 194             //@cond
 195             typedef typename link_checker_selector< typename Node::gc, Node, LinkType>::type type;
 196             //@endcond
 197         };
 198
 199
 200         /// \p MichaelList internal statistics
 201         template <typename EventCounter = cds::atomicity::event_counter>
 202         struct stat {
 203             typedef EventCounter event_counter; ///< Event counter type
 204
 205             event_counter   m_nInsertSuccess;   ///< Number of success \p insert() operations
 206             event_counter   m_nInsertFailed;    ///< Number of failed \p insert() operations
 207             event_counter   m_nInsertRetry;     ///< Number of attempts to insert new item
 208             event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
 209             event_counter   m_nUpdateExisting;  ///< Number of existing item updates
 210             event_counter   m_nUpdateFailed;    ///< Number of failed \p update() call
 211             event_counter   m_nUpdateRetry;     ///< Number of attempts to \p update() the item
 212             event_counter   m_nUpdateMarked;    ///< Number of attempts to \p update() logically deleted (marked) items
 213             event_counter   m_nEraseSuccess;    ///< Number of successful \p erase(), \p unlink(), \p extract() operations
 214             event_counter   m_nEraseFailed;     ///< Number of failed \p erase(), \p unlink(), \p extract() operations
 215             event_counter   m_nEraseRetry;      ///< Number of attempts to \p erase() an item
 216             event_counter   m_nFindSuccess;     ///< Number of successful \p find() and \p get() operations
 217             event_counter   m_nFindFailed;      ///< Number of failed \p find() and \p get() operations
 218
 219             event_counter   m_nHelpingSuccess;  ///< Number of successful help attempts to remove marked item during searching
 220             event_counter   m_nHelpingFailed;   ///< Number if failed help attempts to remove marked item during searching
 221
 222             //@cond
 223             void onInsertSuccess()      { ++m_nInsertSuccess;   }
 224             void onInsertFailed()       { ++m_nInsertFailed;    }
 225             void onInsertRetry()        { ++m_nInsertRetry;     }
 226             void onUpdateNew()          { ++m_nUpdateNew;       }
 227             void onUpdateExisting()     { ++m_nUpdateExisting;  }
 228             void onUpdateFailed()       { ++m_nUpdateFailed;    }
 229             void onUpdateRetry()        { ++m_nUpdateRetry;     }
 230             void onUpdateMarked()       { ++m_nUpdateMarked;    }
 231             void onEraseSuccess()       { ++m_nEraseSuccess;    }
 232             void onEraseFailed()        { ++m_nEraseFailed;     }
 233             void onEraseRetry()         { ++m_nEraseRetry;      }
 234             void onFindSuccess()        { ++m_nFindSuccess;     }
 235             void onFindFailed()         { ++m_nFindFailed;      }
 236
 237             void onHelpingSuccess()     { ++m_nHelpingSuccess;  }
 238             void onHelpingFailed()      { ++m_nHelpingFailed;   }
 239             //@endcond
 240         };
 241
 242         /// \p MichaelList empty internal statistics
 243         struct empty_stat {
 244             //@cond
 245             void onInsertSuccess()              const {}
 246             void onInsertFailed()               const {}
 247             void onInsertRetry()                const {}
 248             void onUpdateNew()                  const {}
 249             void onUpdateExisting()             const {}
 250             void onUpdateFailed()               const {}
 251             void onUpdateRetry()                const {}
 252             void onUpdateMarked()               const {}
 253             void onEraseSuccess()               const {}
 254             void onEraseFailed()                const {}
 255             void onEraseRetry()                 const {}
 256             void onFindSuccess()                const {}
 257             void onFindFailed()                 const {}
 258
 259             void onHelpingSuccess()             const {}
 260             void onHelpingFailed()              const {}
 261             //@endcond
 262         };
 263
 264         //@cond
 265         template <typename Stat = michael_list::stat<>>
 266         struct wrapped_stat {
 267             typedef Stat stat_type;
 268
 269             wrapped_stat( stat_type& st )
 270                 : m_stat( st )
 271             {}
 272
 273             void onInsertSuccess()      { m_stat.onInsertSuccess();     }
 274             void onInsertFailed()       { m_stat.onInsertFailed();      }
 275             void onInsertRetry()        { m_stat.onInsertRetry();       }
 276             void onUpdateNew()          { m_stat.onUpdateNew();         }
 277             void onUpdateExisting()     { m_stat.onUpdateExisting();    }
 278             void onUpdateFailed()       { m_stat.onUpdateFailed();      }
 279             void onUpdateRetry()        { m_stat.onUpdateRetry();       }
 280             void onUpdateMarked()       { m_stat.onUpdateMarked();      }
 281             void onEraseSuccess()       { m_stat.onEraseSuccess();      }
 282             void onEraseFailed()        { m_stat.onEraseFailed();       }
 283             void onEraseRetry()         { m_stat.onEraseRetry();        }
 284             void onFindSuccess()        { m_stat.onFindSuccess();       }
 285             void onFindFailed()         { m_stat.onFindFailed();        }
 286
 287             void onHelpingSuccess()     { m_stat.onHelpingSuccess();    }
 288             void onHelpingFailed()      { m_stat.onHelpingFailed();     }
 289
 290             stat_type& m_stat;
 291         };
 292         //@endcond
 293
 294         /// MichaelList traits
 295         struct traits
 296         {
 297             /// Hook used
 298             /**
 299                 Possible values are: \p michael_list::base_hook, \p michael_list::member_hook, \p michael_list::traits_hook.
 300             */
 301             typedef base_hook<>       hook;
 302
 303             /// Key comparison functor
 304             /**
 305                 No default functor is provided. If the option is not specified, the \p less is used.
 306             */
 307             typedef opt::none                       compare;
 308
 309             /// Specifies binary predicate used for key compare.
 310             /**
 311                 Default is \p std::less<T>.
 312             */
 313             typedef opt::none                       less;
 314
 315             /// Back-off strategy
 316             typedef cds::backoff::Default           back_off;
 317
 318             /// Disposer for removing items
 319             typedef opt::v::empty_disposer          disposer;
 320
 321             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
 322             typedef atomicity::empty_item_counter   item_counter;
 323
 324             /// Internal statistics
 325             /**
 326                 By default, internal statistics is disabled (\p michael_list::empty_stat).
 327                 Use \p michael_list::stat to enable it.
 328             */
 329             typedef empty_stat                      stat;
 330
 331             /// Link fields checking feature
 332             /**
 333                 Default is \p opt::debug_check_link
 334             */
 335             static const opt::link_check_type link_checker = opt::debug_check_link;
 336
 337             /// C++ memory ordering model
 338             /**
 339                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 340                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 341             */
 342             typedef opt::v::relaxed_ordering        memory_model;
 343
 344             /// RCU deadlock checking policy (only for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList")
 345             /**
 346                 List of available policy see \p opt::rcu_check_deadlock
 347             */
 348             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 349         };
 350
 351         /// Metafunction converting option list to \p michael_list::traits
 352         /**
 353             Supported \p Options are:
 354             - \p opt::hook - hook used. Possible values are: \p michael_list::base_hook, \p michael_list::member_hook, \p michael_list::traits_hook.
 355                 If the option is not specified, \p %michael_list::base_hook<> and \p gc::HP is used.
 356             - \p opt::compare - key comparison functor. No default functor is provided.
 357                 If the option is not specified, the \p opt::less is used.
 358             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 359             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 360             - \p opt::disposer - the functor used for disposing removed items. Default is \p opt::v::empty_disposer. Due the nature
 361                 of GC schema the disposer may be called asynchronously.
 362             - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
 363             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
 364                  To enable item counting use \p atomicity::item_counter.
 365             - \p opt::stat - internal statistics. By default, it is disabled (\p michael_list::empty_stat).
 366                 To enable it use \p michael_list::stat
 367             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 368                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
 369             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
 370                 Default is \p opt::v::rcu_throw_deadlock
 371         */
 372         template <typename... Options>
 373         struct make_traits {
 374 #   ifdef CDS_DOXYGEN_INVOKED
 375             typedef implementation_defined type ;   ///< Metafunction result
 376 #   else
 377             typedef typename cds::opt::make_options<
 378                 typename cds::opt::find_type_traits< traits, Options... >::type
 379                 ,Options...
 380             >::type   type;
 381 #   endif
 382         };
 383
 384
 385         //@cond
 386         template <typename Stat>
 387         struct select_stat_wrapper
 388         {
 389             typedef Stat stat;
 390             typedef michael_list::wrapped_stat<Stat> wrapped_stat;
 391             enum {
 392                 empty = false
 393             };
 394         };
 395
 396         template <>
 397         struct select_stat_wrapper< empty_stat >
 398         {
 399             typedef empty_stat stat;
 400             typedef empty_stat wrapped_stat;
 401             enum {
 402                 empty = true
 403             };
 404         };
 405
 406         template <typename Stat>
 407         struct select_stat_wrapper< michael_list::wrapped_stat<Stat>>: public select_stat_wrapper< Stat >
 408         {};
 409
 410         //@endcond
 411
 412     } // namespace michael_list
 413
 414     //@cond
 415     // Forward declaration
 416     template < class GC, typename T, class Traits = michael_list::traits >
 417     class MichaelList;
 418     //@endcond
 419
 420
 421     //@cond
 422     template <typename List>
 423     struct is_michael_list {
 424         enum {
 425             value = false
 426         };
 427     };
 428
 429     template <typename GC, typename T, typename Traits>
 430     struct is_michael_list< MichaelList< GC, T, Traits >> {
 431         enum {
 432             value = true
 433         };
 434     };
 435     //@endcond
 436
 437 }}   // namespace cds::intrusive
 438
 439 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_LIST_BASE_H