-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_INTRUSIVE_DETAILS_BASE_H
-#define __CDS_INTRUSIVE_DETAILS_BASE_H
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
-#include <cds/intrusive/node_traits.h>
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_INTRUSIVE_DETAILS_BASE_H
+#define CDSLIB_INTRUSIVE_DETAILS_BASE_H
+
+#include <cds/intrusive/details/node_traits.h>
#include <cds/details/allocator.h>
#include <cds/algo/backoff_strategy.h>
/// Intrusive containers
/**
@ingroup cds_intrusive_containers
- The namespace cds::intrusive contains intrusive lock-free containers.
+ The namespace \p cds::intrusive contains intrusive lock-free containers.
The idea comes from \p boost::intrusive library, see http://boost.org/doc/ as a good introduction to intrusive approach.
- The intrusive containers of libcds library is developed as close to boost::intrusive
+ The intrusive containers of libcds library is developed as close to \p boost::intrusive
In terms of lock-free approach, the main advantage of intrusive containers is
- that no memory allocation is performed to maintain container items.
- However, additional requirements is imposed for types and values that can be stored in intrusive container.
+ that no memory allocation is performed to maintain container elements.
+ However, additional requirements are imposed for types and values that can be stored in intrusive container.
See the container documentation for details.
- Restriction for Gidenstam's garbage collector cds::gc::HRC:
- the Gidenstam's garbage collector makes additional requirements to type of item in intrusive container.
- Therefore, for this GC only \p base_hook is allowed as the value of opt::hook option.
+ \anchor cds_intrusive_hook_tag
+ \par Tags
+ Many hooks and nodes for intrusive containers contain template argument \p Tag.
+ This argument serves as a tag, so you can derive from more than one container's node and hence put an object in multiple intrusive containers
+ at the same time. An incomplete type can serve as a tag. If you specify two hooks, you must specify a different tag for each one.
+ Example:
+ \code
+ struct tag1;
+ cds::intrusive::treiber_stack::node< cds::gc::HP, tag<tag1> >
+ \endcode
+ If no tag is specified the default \p cds::opt::none will be used.
+
+ \anchor cds_intrusive_item_creating
+ \par Inserting items
+ Many intrusive and non-intrusive (standard-like) containers in the library have the member functions
+ that take a functor argument to initialize the inserted item after it has been successfully inserted,
+ for example:
+ \code
+ template <typename Q, typename Func>
+ bool insert( Q& key, Func f );
+
+ template <typename Q, typename Func>
+ std::pair<bool, bool> update( Q& key, Func f, bool bAllowInsert = true );
+ \endcode
+ The first member function calls \p f functor iif a new item has been inserted. The functor takes two parameter: a reference to inserted item and
+ \p key.
+
+ The second member function, \p update(), allows to insert a new item to the container if \p key is not found, or to find the item with \p key and
+ to perform some action with it. The \p f signature is:
+ \code
+ void f( bool bNew, item_type& item, Q& key );
+ \endcode
+ where \p bNew is a flag to indicate whether \p item is a new created node or not.
+
+ Such functions should be used with caution in multi-threaded environment
+ since they can cause races. The library does not synchronize access
+ to container's items, so many threads can access to one item simultaneously.
+ For example, for \p insert member function the following race is possible:
+ \code
+ // Suppose, Foo is a complex structure with int key field
+ SomeContainer<Foo> q;
+
+ Thread 1 Thread 2
+
+ q.insert( Foo(5), q.find( 5, []( Foo& item ) {
+ []( Foo& item ){ // access to item fields
+ // complex initialization ...
+ item.f1 = ...; });
+ ...
+ });
+ \endcode
+ Execute sequence:
+ \code
+ Find 5 in the container.
+ Key 5 is not found
+ Create a new item Find key 5
+ with calling Foo(5) ctor
+ Insert the new item
+ The key 5 is found -
+ call the functor (!)
+ Perform complex
+ initialization -
+ call the functor
+ \endcode
+ (!): Thread 2 found the key and call its functor on incomplete initialized item.
+ Simultaneous access to the item also is possible. In this case Thread 1 is
+ initializing the item, thread 2 is reading (or writing) the item's fields.
+ In any case, Thread 2 can read uninitialized or incomplete initialized fields.
+
+ \p update() member function race. Suppose, thread 1 and thread 2 perform
+ the
+ following code:
+ \code
+ q.update( 5, []( bool bNew, Foo& item, int arg )
+ {
+ // bNew: true if the new element has been created
+ // false otherwise
+ if ( bNew ) {
+ // initialize item
+ item.f1=...;
+ //...
+ }
+ else {
+ // do some work
+ if ( !item.f1 )
+ item.f1 = ...;
+ else {
+ //...
+ }
+ //...
+ }
+ }
+ );
+ \endcode
+ Execute sequence:
+ \code
+ Thread 1 Thread 2
+ key 5 not found
+ insert new item Foo(5) Find 5
+ Key 5 found
+ call the functor with
+ bNew = false (!)
+ call the functor with
+ bNew = true
+ \endcode
+ (!): Thread 2 executes its functor on incomplete initialized item.
+
+ To protect your code from such races you can use some item-level synchronization,
+ for example:
+ \code
+ struct Foo {
+ spinlock lock; // item-level lock
+ bool initialized = false; // initialization flag
+ // other fields
+ // ....
+ };
+
+ q.update( 5, []( bool bNew, Foo& item, int arg )
+ {
+ // Lock access to the item
+ std::unique_lock( item.lock );
+
+ if ( !item.initialized ) {
+ // initialize item
+ item.f1=...;
+ //...
+ item.initialized = true; // mark the item as initialized
+ }
+ else {
+ // do some work
+ if ( !item.f1 )
+ item.f1 = ...;
+ else {
+ //...
+ }
+ //...
+ }
+ }
+ );
+ \endcode
+ If the item-level synchronization is not suitable, you should not use any inserting member function
+ with post-insert functor argument.
\anchor cds_intrusive_item_destroying
\par Destroying items
If you develop your intrusive container based on <b>libcds</b> library framework, you should
take in the account the following.
The main idea of garbage collectors (GC) based on Hazard Pointer schema is protecting a shared pointer
- by publishing it as a "hazard" one i.e. as a pointer that is changing at the current time and cannot be
- deleted at this moment. In intrusive container paradigm, the pointer to the node of the container
- and the pointer to the item stored in the container are not equal in the general case.
- However, any pointer to the node should be castable to the appropriate pointer to the container's item.
- In general, any item can be placed to some different intrusive containers simultaneously,
- and each of those container holds a unique pointer to its node that refers to the same item.
+ by publishing it as a "hazard" i.e. as a pointer that is changing at the current time and cannot be
+ deleted at this moment. In intrusive container paradigm, the pointer to a node of the container
+ and the pointer to a item stored in the container are not equal in the general case.
+ However, any pointer to node should be castable to appropriate pointer to container's item.
+ In general, any item can be placed to two or more intrusive containers simultaneously,
+ and each of those container holds an unique pointer to its node that refers to the same item.
When we protect a pointer, we want to protect an <b>item</b> pointer that is the invariant
- for any container stored that item. In your intrusive container, instead of protecting by GC's guard a pointer to an node
- you should convert it to the pointer to the item and then protect resulting item pointer.
+ for any container stored that item. In your intrusive container, instead of protecting by GC's guard a pointer to node
+ you should cast it to the pointer to item and then protect that item pointer.
Otherwise an unpredictable result may occur.
-
*/
namespace intrusive {
/** @defgroup cds_intrusive_list List
@ingroup cds_intrusive_containers
*/
+ /** @defgroup cds_intrusive_freelist Free-list
+ @ingroup cds_intrusive_containers
+ */
+
+ //@cond
+ class iterable_list_tag
+ {};
+
+ template <typename List>
+ struct is_iterable_list: public std::is_base_of< iterable_list_tag, List>
+ {};
+ //@endcond
}} // namespace cds::intrusuve
-#endif // #ifndef __CDS_INTRUSIVE_DETAILS_BASE_H
+#endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_BASE_H
projects / libcds.git / blobdiff