X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fimpl%2Fiterable_kvlist.h;h=4a5e44bf72a823ac953f330e8c14c81502d78e90;hb=71da1f106e0d9451556720b8315f7db0f24383b7;hp=d3b2de374282416e07250dbf4be7b49e22368697;hpb=ff0a61a3efd6bf63d5ed812c2dd5c0447b093bb4;p=libcds.git
diff --git a/cds/container/impl/iterable_kvlist.h b/cds/container/impl/iterable_kvlist.h
index d3b2de37..4a5e44bf 100644
--- a/cds/container/impl/iterable_kvlist.h
+++ b/cds/container/impl/iterable_kvlist.h
@@ -1,11 +1,11 @@
/*
This file is a part of libcds - Concurrent Data Structures library
- (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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:
@@ -47,8 +47,8 @@ namespace cds { namespace container {
Usually, ordered single-linked list is used as a building block for the hash table implementation.
Iterable list is suitable for almost append-only hash table because the list doesn't delete
its internal node when erasing a key but it is marked them as empty to be reused in the future.
- However, plenty of empty nodes degrades performance.
-
+ However, plenty of empty nodes degrades performance.
+
The complexity of searching is O(N).
Template arguments:
@@ -123,15 +123,15 @@ namespace cds { namespace container {
public:
#ifdef CDS_DOXYGEN_INVOKED
- typedef Key key_type ; ///< Key type
- typedef Value mapped_type ; ///< Type of value stored in the list
- typedef std::pair value_type ; ///< key/value pair stored in the list
+ typedef Key key_type; ///< Key type
+ typedef Value mapped_type; ///< Type of value stored in the list
+ typedef std::pair value_type; ///< key/value pair stored in the list
#else
typedef typename maker::key_type key_type;
typedef typename maker::mapped_type mapped_type;
typedef typename maker::value_type value_type;
#endif
-
+ typedef Traits traits; ///< List traits
typedef typename base_class::gc gc; ///< Garbage collector used
typedef typename base_class::back_off back_off; ///< Back-off strategy used
typedef typename maker::data_allocator_type allocator_type; ///< Allocator type used for allocate/deallocate data
@@ -145,6 +145,22 @@ namespace cds { namespace container {
/// Guarded pointer
typedef typename base_class::guarded_ptr guarded_ptr;
+ //@cond
+ // Rebind traits (split-list support)
+ template
+ struct rebind_traits {
+ typedef IterableKVList<
+ gc
+ , key_type, mapped_type
+ , typename cds::opt::make_options< traits, Options...>::type
+ > type;
+ };
+
+ // Stat selector
+ template
+ using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >;
+ //@endcond
+
protected:
//@cond
typedef typename base_class::head_type head_type;
@@ -201,7 +217,7 @@ namespace cds { namespace container {
this code
\code
if ( it1 == it2 )
- assert( &(*it1) == &(*it2) );
+ assert( &(*it1) == &(*it2));
\endcode
can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
@@ -249,9 +265,9 @@ namespace cds { namespace container {
@note The function is supported only if \ref mapped_type is default constructible
*/
template
- bool insert( K const& key )
+ bool insert( K&& key )
{
- return base_class::emplace( key, mapped_type());
+ return base_class::emplace( key_type( std::forward( key )), mapped_type());
}
/// Inserts new node with a key and a value
@@ -265,9 +281,9 @@ namespace cds { namespace container {
Returns \p true if inserting successful, \p false otherwise.
*/
template
- bool insert( K const& key, V const& val )
+ bool insert( K&& key, V&& val )
{
- return base_class::emplace( key, val );
+ return base_class::emplace( key_type( std::forward( key )), mapped_type( std::forward( val )));
}
/// Inserts new node and initialize it by a functor
@@ -301,9 +317,9 @@ namespace cds { namespace container {
@note The function is supported only if \ref mapped_type is default constructible
*/
template
- bool insert_with( K const& key, Func func )
+ bool insert_with( K&& key, Func func )
{
- return base_class::insert( value_type( key, mapped_type()), func );
+ return base_class::insert( value_type( key_type( std::forward( key )), mapped_type()), func );
}
/// Updates data by \p key
@@ -326,7 +342,7 @@ namespace cds { namespace container {
The functor may change non-key fields of \p val; however, \p func must guarantee
that during changing no any other modifications could be made on this item by concurrent threads.
- Returns std::pair where \p first is true if operation is successful,
+ @return std::pair where \p first is true if operation is successful,
\p second is true if new item has been added or \p false if the item with such \p key
already exists.
@@ -335,9 +351,9 @@ namespace cds { namespace container {
@note The function is supported only if \ref mapped_type is default constructible
*/
template
- std::pair update( K const& key, Func f, bool bAllowInsert = true )
+ std::pair update( K&& key, Func f, bool bAllowInsert = true )
{
- return base_class::update( value_type( key, mapped_type()), f, bAllowInsert );
+ return base_class::update( value_type( key_type( std::forward( key )), mapped_type()), f, bAllowInsert );
}
/// Insert or update
@@ -346,7 +362,7 @@ namespace cds { namespace container {
If the item \p key is not found in the list, then \p key is inserted
iff \p bInsert is \p true.
- Otherwise, the current element is changed to value_type( key, val ),
+ Otherwise, the current element is changed to value_type( key, val ),
the old element will be retired later.
Returns std::pair where \p first is \p true if operation is successful,
@@ -356,7 +372,7 @@ namespace cds { namespace container {
template
std::pair upsert( Q&& key, V&& val, bool bInsert = true )
{
- return base_class::upsert( value_type( std::forward( key ), std::forward( val )), bInsert );
+ return base_class::upsert( value_type( key_type( std::forward( key )), mapped_type( std::forward( val ))), bInsert );
}
/// Inserts a new node using move semantics
@@ -369,7 +385,7 @@ namespace cds { namespace container {
template
bool emplace( K&& key, Args&&... args )
{
- return base_class::emplace( std::forward( key ), std::forward( args )... );
+ return base_class::emplace( key_type( std::forward( key )), mapped_type( std::forward( args )... ));
}
/// Deletes \p key from the list
@@ -393,7 +409,7 @@ namespace cds { namespace container {
bool erase_with( K const& key, Less pred )
{
CDS_UNUSED( pred );
- return base_class::erase_with( key, less_wrapper() );
+ return base_class::erase_with( key, less_wrapper());
}
/// Deletes \p key from the list
@@ -475,7 +491,7 @@ namespace cds { namespace container {
guarded_ptr extract_with( K const& key, Less pred )
{
CDS_UNUSED( pred );
- return base_class::extract_with( key, less_wrapper() );
+ return base_class::extract_with( key, less_wrapper());
}
/// Checks whether the list contains \p key
@@ -499,7 +515,7 @@ namespace cds { namespace container {
bool contains( Q const& key, Less pred ) const
{
CDS_UNUSED( pred );
- return base_class::contains( key, less_wrapper() );
+ return base_class::contains( key, less_wrapper());
}
/// Finds the key \p key and performs an action with it
@@ -609,7 +625,7 @@ namespace cds { namespace container {
guarded_ptr get_with( K const& key, Less pred ) const
{
CDS_UNUSED( pred );
- return base_class::get_with( key, less_wrapper() );
+ return base_class::get_with( key, less_wrapper());
}
/// Checks if the list is empty
@@ -650,21 +666,21 @@ namespace cds { namespace container {
// Split-list support
template
- bool insert_at( head_type& refHead, const K& key )
+ bool insert_at( head_type& refHead, K&& key )
{
- return base_class::insert_at( refHead, value_type( key, mapped_type() ));
+ return base_class::insert_at( refHead, value_type( key_type( std::forward( key )), mapped_type()));
}
template
- bool insert_at( head_type& refHead, const K& key, const V& val )
+ bool insert_at( head_type& refHead, K&& key, V&& val )
{
- return base_class::insert_at( refHead, value_type( key, val ));
+ return base_class::insert_at( refHead, value_type( key_type( std::forward( key )), std::forward( val )));
}
template
- bool insert_with_at( head_type& refHead, const K& key, Func f )
+ bool insert_with_at( head_type& refHead, K&& key, Func f )
{
- return base_class::insert_at( refHead, value_type( key, mapped_type()), f );
+ return base_class::insert_at( refHead, value_type( key_type( std::forward( key )), mapped_type()), f );
}
template
@@ -674,9 +690,9 @@ namespace cds { namespace container {
}
template
- std::pair update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert )
+ std::pair update_at( head_type& refHead, K&& key, Func f, bool bAllowInsert )
{
- return base_class::update_at( refHead, value_type( key, mapped_type()), f, bAllowInsert );
+ return base_class::update_at( refHead, value_type( key_type( std::forward( key )), mapped_type()), f, bAllowInsert );
}
template
@@ -691,9 +707,9 @@ namespace cds { namespace container {
return base_class::erase_at( refHead, key, cmp, f );
}
template
- bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp )
+ guarded_ptr extract_at( head_type& refHead, K const& key, Compare cmp )
{
- return base_class::extract_at( refHead, guard, key, cmp );
+ return base_class::extract_at( refHead, key, cmp );
}
template
@@ -709,9 +725,9 @@ namespace cds { namespace container {
}
template
- bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp )
+ guarded_ptr get_at( head_type& refHead, K const& key, Compare cmp )
{
- return base_class::get_at( refHead, guard, key, cmp );
+ return base_class::get_at( refHead, key, cmp );
}
//@endcond