typedef typename bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node
/// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
static CDS_CONSTEXPR const bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
+ /// Type of \p get() member function return value
+ typedef typename bucket_type::raw_ptr raw_ptr;
+
+ //@cond
+ typedef cds::container::michael_map::implementation_tag implementation_tag;
+ //@endcond
protected:
item_counter m_ItemCounter; ///< Item counter
public:
/// Initializes the map
- /** @copydetails cds_nonintrusive_MichaelHashMap_hp_ctor
+ /**
+ The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
+ when you create an object.
+ \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
+ Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
+ Note, that many popular STL hash map implementation uses load factor 1.
+
+ The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
*/
MichaelHashMap(
size_t nMaxItemCount, ///< estimation of max item count in the hash map
unlinks it from the map, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
If the item is not found the function return an empty \p exempt_ptr.
- @note The function does NOT call RCU read-side lock or synchronization,
- and does NOT dispose the item found. It just excludes the item from the map
- and returns a pointer to item found.
- You should lock RCU before calling of the function, and you should synchronize RCU
- outside the RCU lock to free extracted item
+ The function just excludes the key from the map and returns a pointer to item found.
+ Depends on \p bucket_type you should or should not lock RCU before calling of this function:
+ - for the set based on \ref cds_nonintrusive_MichaelList_rcu "MichaelList" RCU should not be locked
+ - for the set based on \ref cds_nonintrusive_LazyList_rcu "LazyList" RCU should be locked
+ See ordered list implementation for details.
\code
#include <cds/urcu/general_buffered.h>
// ...
rcu_michael_map::exempt_ptr p;
- {
- // first, we should lock RCU
- rcu_michael_map::rcu_lock lock;
-
- // Now, you can apply extract function
- // Note that you must not delete the item found inside the RCU lock
- p = theMap.extract( 10 );
- if ( p ) {
- // do something with p
- ...
- }
+
+ // For MichaelList we should not lock RCU
+
+ // Note that you must not delete the item found inside the RCU lock
+ p = theMap.extract( 10 );
+ if ( p ) {
+ // do something with p
+ ...
}
// We may safely release p here
The function returns \p true if \p key is found, \p false otherwise.
*/
template <typename K, typename Func>
- bool find( K const& key, Func f ) const
+ bool find( K const& key, Func f )
{
return bucket( key ).find( key, f );
}
\p Less must imply the same element order as the comparator used for building the map.
*/
template <typename K, typename Less, typename Func>
- bool find_with( K const& key, Less pred, Func f ) const
+ bool find_with( K const& key, Less pred, Func f )
{
return bucket( key ).find_with( key, pred, f );
}
The function applies RCU lock internally.
*/
template <typename K>
- bool find( K const& key ) const
+ bool find( K const& key )
{
return bucket( key ).find( key );
}
\p Less must imply the same element order as the comparator used for building the map.
*/
template <typename K, typename Less>
- bool find_with( K const& key, Less pred ) const
+ bool find_with( K const& key, Less pred )
{
return bucket( key ).find_with( key, pred );
}
/** \anchor cds_nonintrusive_MichaelHashMap_rcu_get
The function searches the item with key equal to \p key and returns the pointer to item found.
If \p key is not found it returns \p nullptr.
+ Note the type of returned value depends on underlying \p bucket_type.
+ For details, see documentation of ordered list you use.
Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
typedef cds::container::MichaelHashMap< your_template_parameters > hash_map;
hash_map theMap;
// ...
+ typename hash_map::raw_ptr gp;
{
// Lock RCU
hash_map::rcu_lock lock;
- hash_map::value_type * = theMap.get( 5 );
- if ( pVal ) {
- // Deal with pVal
+ gp = theMap.get( 5 );
+ if ( gp ) {
+ // Deal with gp
//...
}
// Unlock RCU by rcu_lock destructor
- // pVal can be freed at any time after RCU has been unlocked
+ // gp can be reclaimed at any time after RCU has been unlocked
}
\endcode
*/
template <typename K>
- value_type * get( K const& key ) const
+ raw_ptr get( K const& key )
{
return bucket( key ).get( key );
}
\p pred must imply the same element order as the comparator used for building the map.
*/
template <typename K, typename Less>
- value_type * get_with( K const& key, Less pred ) const
+ raw_ptr get_with( K const& key, Less pred )
{
return bucket( key ).get_with( key, pred );
}
projects / libcds.git / blobdiff