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