#ifndef __CDS_CONTAINER_LAZY_KVLIST_NOGC_H
#define __CDS_CONTAINER_LAZY_KVLIST_NOGC_H
-#include <cds/container/lazy_list_base.h>
+#include <memory>
+#include <cds/container/details/lazy_list_base.h>
#include <cds/intrusive/lazy_list_nogc.h>
#include <cds/container/details/make_lazy_kvlist.h>
-#include <cds/details/functor_wrapper.h>
-#include <cds/details/std/memory.h>
namespace cds { namespace container {
- //@cond
- namespace details {
-
- template <typename K, typename T, class Traits>
- struct make_lazy_kvlist_nogc: public make_lazy_kvlist<gc::nogc, K, T, Traits>
- {
- typedef make_lazy_kvlist<cds::gc::nogc, K, T, Traits> base_maker;
- typedef typename base_maker::node_type node_type;
-
- struct type_traits: public base_maker::type_traits
- {
- typedef typename base_maker::node_deallocator disposer;
- };
-
- typedef intrusive::LazyList<cds::gc::nogc, node_type, type_traits> type;
- };
-
- } // namespace details
- //@endcond
-
/// Lazy ordered list (key-value pair, template specialization for gc::nogc)
/** @ingroup cds_nonintrusive_list
+ @anchor cds_nonintrusive_LazyKVList_nogc
- This specialization is intended for so-called persistent usage when no item
+ This specialization is append-only list when no item
reclamation may be performed. The class does not support deleting of list item.
- Usually, ordered single-linked list is used as a building block for the hash table implementation.
- The complexity of searching is <tt>O(N)</tt>.
-
- See \ref cds_nonintrusive_LazyList_gc "LazyList" for description of template parameters.
-
- The interface of the specialization is a little different.
+ @copydetails cds_nonintrusive_LazyList_gc
*/
template <
typename Key,
typename Value,
#ifdef CDS_DOXYGEN_INVOKED
- typename Traits = lazy_list::type_traits
+ typename Traits = lazy_list::traits
#else
typename Traits
#endif
#ifdef CDS_DOXYGEN_INVOKED
protected intrusive::LazyList< gc::nogc, implementation_defined, Traits >
#else
- protected details::make_lazy_kvlist_nogc< Key, Value, Traits >::type
+ protected details::make_lazy_kvlist< cds::gc::nogc, Key, Value, Traits >::type
#endif
{
//@cond
- typedef details::make_lazy_kvlist_nogc< Key, Value, Traits > options;
- typedef typename options::type base_class;
+ typedef details::make_lazy_kvlist< cds::gc::nogc, Key, Value, Traits > maker;
+ typedef typename maker::type base_class;
//@endcond
public:
+ typedef cds::gc::nogc gc; ///< Garbage collector
#ifdef CDS_DOXYGEN_INVOKED
typedef Key key_type ; ///< Key type
typedef Value mapped_type ; ///< Type of value stored in the list
typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
#else
- typedef typename options::key_type key_type;
- typedef typename options::value_type mapped_type;
- typedef typename options::pair_type value_type;
+ typedef typename maker::key_type key_type;
+ typedef typename maker::mapped_type mapped_type;
+ typedef typename maker::value_type value_type;
#endif
- typedef typename base_class::gc gc ; ///< Garbage collector used
- typedef typename base_class::back_off back_off ; ///< Back-off strategy used
- typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
- typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
- typedef typename options::key_comparator key_comparator ; ///< key comparison functor
- typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
+ typedef typename base_class::back_off back_off; ///< Back-off strategy used
+ typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
+ typedef typename base_class::item_counter item_counter; ///< Item counting policy used
+ typedef typename maker::key_comparator key_comparator; ///< key comparison functor
+ typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
protected:
//@cond
- typedef typename base_class::value_type node_type;
- typedef typename options::cxx_allocator cxx_allocator;
- typedef typename options::node_deallocator node_deallocator;
- typedef typename options::type_traits::compare intrusive_key_comparator;
-
- typedef typename base_class::node_type head_type;
- //@endcond
-
- private:
- //@cond
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- struct ensure_functor
- {
- node_type * m_pItemFound;
-
- ensure_functor()
- : m_pItemFound( null_ptr<node_type *>() )
- {}
-
- void operator ()(bool, node_type& item, node_type& )
- {
- m_pItemFound = &item;
- }
- };
-
- template <typename Func>
- class find_functor: protected cds::details::functor_wrapper<Func>
- {
- typedef cds::details::functor_wrapper<Func> base_class;
- public:
- find_functor( Func f )
- : base_class(f)
- {}
-
- template <typename Q>
- void operator ()( node_type& node, Q& )
- {
- base_class::get()( node.m_Data );
- }
- };
-# endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
+ typedef typename base_class::value_type node_type;
+ typedef typename maker::cxx_allocator cxx_allocator;
+ typedef typename maker::node_deallocator node_deallocator;
+ typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
+ typedef typename base_class::node_type head_type;
//@endcond
protected:
return cxx_allocator().New( key, val );
}
-#ifdef CDS_EMPLACE_SUPPORT
template <typename... Args>
static node_type * alloc_node( Args&&... args )
{
return cxx_allocator().MoveNew( std::forward<Args>(args)... );
}
-#endif
static void free_node( node_type * pNode )
{
key_type const& key() const
{
typename iterator_base::value_ptr p = iterator_base::operator ->();
- assert( p != null_ptr<typename iterator_base::value_ptr>() );
+ assert( p != nullptr );
return p->m_Data.first;
}
value_ref val() const
{
typename iterator_base::value_ptr p = iterator_base::operator ->();
- assert( p != null_ptr<typename iterator_base::value_ptr>() );
+ assert( p != nullptr );
return p->m_Data.second;
}
pair_ptr operator ->() const
{
typename iterator_base::value_ptr p = iterator_base::operator ->();
- return p ? &(p->m_Data) : null_ptr<pair_ptr>();
+ return p ? &(p->m_Data) : nullptr;
}
pair_ref operator *() const
/// Returns an iterator that addresses the location succeeding the last element in a list
/**
Do not use the value returned by <tt>end</tt> function to access any item.
- Internally, <tt>end</tt> returning value equals to <tt>NULL</tt>.
+ Internally, <tt>end</tt> returning value equals to nullptr.
The returned value can be used only to control reaching the end of the list.
For empty list \code begin() == end() \endcode
++it ; // skip dummy head
return it;
}
- const_iterator cbegin()
+ const_iterator cbegin() const
{
const_iterator it( head() );
++it ; // skip dummy head
{
return const_iterator( tail());
}
- const_iterator cend()
+ const_iterator cend() const
{
return const_iterator( tail());
}
public:
/// Default constructor
- /**
- Initialize empty list
- */
LazyKVList()
{}
- /// List desctructor
- /**
- Clears the list
- */
+ /// Desctructor clears the list
~LazyKVList()
{
clear();
The argument \p item of user-defined functor \p func is the reference
to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
- User-defined functor \p func should guarantee that during changing item's value no any other changes
- could be made on this list's item by concurrent threads.
- The user-defined functor can be passed by reference using <tt>boost::ref</tt>
- and it is called only if the inserting is successful.
+ The user-defined functor is called only if the inserting is successful.
The key_type should be constructible from value of type \p K.
return std::make_pair( node_to_iterator( ret.first ), ret.second );
}
-# ifdef CDS_EMPLACE_SUPPORT
/// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
/**
Returns an iterator pointed to inserted value, or \p end() if inserting is failed
-
- This function is available only for compiler that supports
- variadic template and move semantics
*/
template <typename... Args>
iterator emplace( Args&&... args )
{
return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
}
-# endif
/// Find the key \p key
/** \anchor cds_nonintrusive_LazyKVList_nogc_find
template <typename Q, typename Less>
iterator find_with( Q const& key, Less pred )
{
- return node_to_iterator( find_at( head(), key, typename options::template less_wrapper<Less>::type() ) );
+ return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
}
/// Check if the list is empty
The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
this function always returns 0.
- <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
+ @note Even if you use real item counter and it returns 0, this fact is not mean that the list
is empty. To check list emptyness use \ref empty() method.
*/
size_t size() const
//@cond
node_type * insert_node_at( head_type& refHead, node_type * pNode )
{
- assert( pNode != null_ptr<node_type *>() );
+ assert( pNode != nullptr );
scoped_node_ptr p( pNode );
if ( base_class::insert_at( &refHead, *p ))
return p.release();
- return null_ptr<node_type *>();
+ return nullptr;
}
template <typename K>
scoped_node_ptr pNode( alloc_node( key ));
if ( base_class::insert_at( &refHead, *pNode )) {
- cds::unref(f)( pNode->m_Data );
+ f( pNode->m_Data );
return pNode.release();
}
- return null_ptr<node_type *>();
+ return nullptr;
}
std::pair< node_type *, bool > ensure_at( head_type& refHead, const K& key )
{
scoped_node_ptr pNode( alloc_node( key ));
- node_type * pItemFound = null_ptr<node_type *>();
+ node_type * pItemFound = nullptr;
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; } );
-# else
- ensure_functor func;
- std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode, boost::ref(func) );
- pItemFound = func.m_pItemFound;
-# endif
if ( ret.first && ret.second )
pNode.release();
- assert( pItemFound != null_ptr<node_type *>() );
+ assert( pItemFound != nullptr );
return std::make_pair( pItemFound, ret.second );
}
-# ifdef CDS_EMPLACE_SUPPORT
template <typename... Args>
node_type * emplace_at( head_type& refHead, Args&&... args )
{
return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
}
-#endif
template <typename K, typename Compare>
node_type * find_at( head_type& refHead, const K& key, Compare cmp )
template <typename K, typenam Compare, typename Func>
bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
{
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K const& ){ cds::unref(f)( node.m_Data ); });
-# else
- find_functor<Func> wrapper( f );
- return base_class::find_at( &refHead, key, cmp, cds::ref(wrapper) );
-# endif
+ return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K const& ){ f( node.m_Data ); });
}
*/
//@endcond