projects
/
libcds.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
issue#11: cds: changed __CDS_ guard prefix to CDSLIB_ for all .h files
[libcds.git]
/
cds
/
container
/
impl
/
michael_list.h
diff --git
a/cds/container/impl/michael_list.h
b/cds/container/impl/michael_list.h
index 17224e31d5d5a1488af0c568b4fc17d1844325d5..aa3a7c8dc53d8745149df98293f657e744dd0c51 100644
(file)
--- a/
cds/container/impl/michael_list.h
+++ b/
cds/container/impl/michael_list.h
@@
-1,7
+1,7
@@
//$$CDS-header$$
//$$CDS-header$$
-#ifndef
__CDS
_CONTAINER_IMPL_MICHAEL_LIST_H
-#define
__CDS
_CONTAINER_IMPL_MICHAEL_LIST_H
+#ifndef
CDSLIB
_CONTAINER_IMPL_MICHAEL_LIST_H
+#define
CDSLIB
_CONTAINER_IMPL_MICHAEL_LIST_H
#include <memory>
#include <cds/container/details/guarded_ptr_cast.h>
#include <memory>
#include <cds/container/details/guarded_ptr_cast.h>
@@
-13,7
+13,7
@@
namespace cds { namespace container {
\anchor cds_nonintrusive_MichaelList_gc
Usually, ordered single-linked list is used as a building block for the hash table implementation.
\anchor cds_nonintrusive_MichaelList_gc
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>, where \p N is the item count in the list, not in the
+ The complexity of searching is <tt>O(N)</tt>, where \p N is the item count in the list, not in the
hash table.
Source:
hash table.
Source:
@@
-121,7
+121,7
@@
namespace cds { namespace container {
public:
/// Guarded pointer
public:
/// Guarded pointer
- typedef
cds::gc::guarded_ptr< gc,
node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
+ typedef
typename gc::template guarded_ptr<
node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
private:
//@cond
private:
//@cond
@@
-234,7
+234,7
@@
namespace cds { namespace container {
The forward iterator for Michael's list has some features:
- it has no post-increment operator
- to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
The forward iterator for Michael's list has some features:
- it has no post-increment operator
- to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
- For some GC (
gc::HP, gc::HRC
), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
+ For some GC (
\p gc::HP
), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
may be thrown if a limit of guard count per thread is exceeded.
- The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
- Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
may be thrown if a limit of guard count per thread is exceeded.
- The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
- Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
@@
-279,7
+279,7
@@
namespace cds { namespace container {
{
return const_iterator( head() );
}
{
return const_iterator( head() );
}
- const_iterator cbegin()
+ const_iterator cbegin()
const
{
return const_iterator( head() );
}
{
return const_iterator( head() );
}
@@
-291,7
+291,7
@@
namespace cds { namespace container {
{
return const_iterator();
}
{
return const_iterator();
}
- const_iterator cend()
+ const_iterator cend()
const
{
return const_iterator();
}
{
return const_iterator();
}
@@
-433,6
+433,7
@@
namespace cds { namespace container {
template <typename Q, typename Less>
bool erase_with( Q const& key, Less pred )
{
template <typename Q, typename Less>
bool erase_with( Q const& key, Less pred )
{
+ CDS_UNUSED( pred );
return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), [](value_type const&){} );
}
return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), [](value_type const&){} );
}
@@
-447,7
+448,6
@@
namespace cds { namespace container {
void operator()(const value_type& val) { ... }
};
\endcode
void operator()(const value_type& val) { ... }
};
\endcode
- The functor may be passed by reference with <tt>boost:ref</tt>
Since the key of MichaelList's item type \p value_type is not explicitly specified,
template parameter \p Q should contain the complete key to search in the list.
Since the key of MichaelList's item type \p value_type is not explicitly specified,
template parameter \p Q should contain the complete key to search in the list.
@@
-472,14
+472,15
@@
namespace cds { namespace container {
template <typename Q, typename Less, typename Func>
bool erase_with( Q const& key, Less pred, Func f )
{
template <typename Q, typename Less, typename Func>
bool erase_with( Q const& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
}
/// Extracts the item from the list with specified \p key
/** \anchor cds_nonintrusive_MichaelList_hp_extract
The function searches an item with key equal to \p key,
return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
}
/// Extracts the item from the list with specified \p key
/** \anchor cds_nonintrusive_MichaelList_hp_extract
The function searches an item with key equal to \p key,
- unlinks it from the list, and returns it
in \p dest paramete
r.
- If
the item with key equal to \p key is not found the function returns \p false
.
+ unlinks it from the list, and returns it
as \p guarded_pt
r.
+ If
\p key is not found the function returns an empty guarded pointer
.
Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
@@
-491,24
+492,26
@@
namespace cds { namespace container {
ord_list theList;
// ...
{
ord_list theList;
// ...
{
- ord_list::guarded_ptr gp;
- theList.extract( gp, 5 );
- // Deal with gp
- // ...
-
+ ord_list::guarded_ptr gp
(theList.extract( 5 ))
;
+ if ( gp ) {
+
// Deal with gp
+
// ...
+ }
// Destructor of gp releases internal HP guard and frees the item
}
\endcode
*/
template <typename Q>
// Destructor of gp releases internal HP guard and frees the item
}
\endcode
*/
template <typename Q>
-
bool extract( guarded_ptr& dest,
Q const& key )
+
guarded_ptr extract(
Q const& key )
{
{
- return extract_at( head(), dest.guard(), key, intrusive_key_comparator() );
+ guarded_ptr gp;
+ extract_at( head(), gp.guard(), key, intrusive_key_comparator() );
+ return gp;
}
/// Extracts the item from the list with comparing functor \p pred
/**
}
/// Extracts the item from the list with comparing functor \p pred
/**
- The function is an analog of \ref cds_nonintrusive_MichaelList_hp_extract "extract(
guarded_ptr&,
Q const&)"
+ The function is an analog of \ref cds_nonintrusive_MichaelList_hp_extract "extract(Q const&)"
but \p pred predicate is used for key comparing.
\p Less functor has the semantics like \p std::less but it should accept arguments of type \p value_type and \p Q
but \p pred predicate is used for key comparing.
\p Less functor has the semantics like \p std::less but it should accept arguments of type \p value_type and \p Q
@@
-516,9
+519,12
@@
namespace cds { namespace container {
\p pred must imply the same element order as the comparator used for building the list.
*/
template <typename Q, typename Less>
\p pred must imply the same element order as the comparator used for building the list.
*/
template <typename Q, typename Less>
-
bool extract_with( guarded_ptr& dest,
Q const& key, Less pred )
+
guarded_ptr extract_with(
Q const& key, Less pred )
{
{
- return extract_at( head(), dest.guard(), key, typename maker::template less_wrapper<Less>::type() );
+ CDS_UNUSED( pred );
+ guarded_ptr gp;
+ extract_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
+ return gp;
}
/// Finds \p key
}
/// Finds \p key
@@
-542,6
+548,7
@@
namespace cds { namespace container {
template <typename Q, typename Less>
bool find_with( Q const& key, Less pred )
{
template <typename Q, typename Less>
bool find_with( Q const& key, Less pred )
{
+ CDS_UNUSED( pred );
return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
}
return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
}
@@
-568,6
+575,13
@@
namespace cds { namespace container {
{
return find_at( head(), key, intrusive_key_comparator(), f );
}
{
return find_at( head(), key, intrusive_key_comparator(), f );
}
+ //@cond
+ template <typename Q, typename Func>
+ bool find( Q const& key, Func f )
+ {
+ return find_at( head(), key, intrusive_key_comparator(), f );
+ }
+ //@endcond
/// Finds \p key using \p pred predicate for searching
/**
/// Finds \p key using \p pred predicate for searching
/**
@@
-579,15
+593,23
@@
namespace cds { namespace container {
template <typename Q, typename Less, typename Func>
bool find_with( Q& key, Less pred, Func f )
{
template <typename Q, typename Less, typename Func>
bool find_with( Q& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
}
return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
}
+ //@cond
+ template <typename Q, typename Less, typename Func>
+ bool find_with( Q const& key, Less pred, Func f )
+ {
+ CDS_UNUSED( pred );
+ return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
+ }
+ //@endcond
/// Finds \p key and return the item found
/** \anchor cds_nonintrusive_MichaelList_hp_get
The function searches the item with key equal to \p key
/// Finds \p key and return the item found
/** \anchor cds_nonintrusive_MichaelList_hp_get
The function searches the item with key equal to \p key
- and assigns the item found to guarded pointer \p ptr.
- The function returns \p true if \p key is found, and \p false otherwise.
- If \p key is not found the \p ptr parameter is not changed.
+ and returns it as \p guarded_ptr.
+ If \p key is not found the function returns an empty guarded pointer.
@note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
@note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
@@
-597,8
+619,8
@@
namespace cds { namespace container {
ord_list theList;
// ...
{
ord_list theList;
// ...
{
- ord_list::guarded_ptr gp;
- if (
theList.get( gp, 5 )
) {
+ ord_list::guarded_ptr gp
(theList.get( 5 ))
;
+ if (
gp
) {
// Deal with gp
//...
}
// Deal with gp
//...
}
@@
-610,14
+632,16
@@
namespace cds { namespace container {
should accept a parameter of type \p Q that can be not the same as \p value_type.
*/
template <typename Q>
should accept a parameter of type \p Q that can be not the same as \p value_type.
*/
template <typename Q>
-
bool get( guarded_ptr& ptr,
Q const& key )
+
guarded_ptr get(
Q const& key )
{
{
- return get_at( head(), ptr.guard(), key, intrusive_key_comparator() );
+ guarded_ptr gp;
+ get_at( head(), gp.guard(), key, intrusive_key_comparator() );
+ return gp;
}
/// Finds \p key and return the item found
/**
}
/// Finds \p key and return the item found
/**
- The function is an analog of \ref cds_nonintrusive_MichaelList_hp_get "get(
guarded_ptr& ptr,
Q const&)"
+ The function is an analog of \ref cds_nonintrusive_MichaelList_hp_get "get( Q const&)"
but \p pred is used for comparing the keys.
\p Less functor has the semantics like \p std::less but should accept arguments of type \p value_type and \p Q
but \p pred is used for comparing the keys.
\p Less functor has the semantics like \p std::less but should accept arguments of type \p value_type and \p Q
@@
-625,9
+649,12
@@
namespace cds { namespace container {
\p pred must imply the same element order as the comparator used for building the list.
*/
template <typename Q, typename Less>
\p pred must imply the same element order as the comparator used for building the list.
*/
template <typename Q, typename Less>
-
bool get_with( guarded_ptr& ptr,
Q const& key, Less pred )
+
guarded_ptr get_with(
Q const& key, Less pred )
{
{
- return get_at( head(), ptr.guard(), key, typename maker::template less_wrapper<Less>::type() );
+ CDS_UNUSED( pred );
+ guarded_ptr gp;
+ get_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
+ return gp;
}
/// Check if the list is empty
}
/// Check if the list is empty
@@
-700,9
+727,9
@@
namespace cds { namespace container {
}
template <typename Q, typename Compare>
}
template <typename Q, typename Compare>
- bool extract_at( head_type& refHead, typename g
c::Guard& dest
, Q const& key, Compare cmp )
+ bool extract_at( head_type& refHead, typename g
uarded_ptr::native_guard& guard
, Q const& key, Compare cmp )
{
{
- return base_class::extract_at( refHead,
dest
, key, cmp );
+ return base_class::extract_at( refHead,
guard
, key, cmp );
}
template <typename Q, typename Func>
}
template <typename Q, typename Func>
@@
-731,7
+758,7
@@
namespace cds { namespace container {
}
template <typename Q, typename Compare>
}
template <typename Q, typename Compare>
- bool get_at( head_type& refHead, typename g
c::G
uard& guard, Q const& key, Compare cmp )
+ bool get_at( head_type& refHead, typename g
uarded_ptr::native_g
uard& guard, Q const& key, Compare cmp )
{
return base_class::get_at( refHead, guard, key, cmp );
}
{
return base_class::get_at( refHead, guard, key, cmp );
}
@@
-741,4
+768,4
@@
namespace cds { namespace container {
}} // namespace cds::container
}} // namespace cds::container
-#endif // #ifndef
__CDS
_CONTAINER_IMPL_MICHAEL_LIST_H
+#endif // #ifndef
CDSLIB
_CONTAINER_IMPL_MICHAEL_LIST_H