/*
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:
\p key_type and an argument of template type \p K must meet the following requirements:
- \p key_type should be constructible from value of type \p K;
- the hash functor should be able to calculate correct hash value from argument \p key of type \p K:
- <tt> hash( key_type(key) ) == hash( key ) </tt>
+ <tt> hash( key_type(key)) == hash( key ) </tt>
- values of type \p key_type and \p K should be comparable
There are the specializations:
typedef typename traits::allocator allocator; ///< Bucket table allocator
typedef typename ordered_list::key_comparator key_comparator; ///< key compare functor
+#ifdef CDS_DOXYGEN_INVOKED
typedef typename ordered_list::stat stat; ///< Internal statistics
+ /// Guarded pointer - a result of \p get() and \p extract() functions
+ typedef typename ordered_list::guarded_ptr guarded_ptr;
+#endif
/// Hash functor for \ref key_type and all its derivatives that you use
typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required
-#ifdef CDS_DOXYGEN_INVOKED
- /// Wrapped internal statistics for \p ordered_list
- typedef implementatin_specific bucket_stat;
-#else
+ //@cond
typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
-#endif
-#ifdef CDS_DOXYGEN_INVOKED
- /// Internal bucket type - rebind \p ordered_list with empty item counter and wrapped internal statistics
- typedef modified_ordered_list internal_bucket_type;
-#else
typedef typename ordered_list::template rebind_traits<
cds::opt::item_counter< cds::atomicity::empty_item_counter >
, cds::opt::stat< typename bucket_stat::wrapped_stat >
>::type internal_bucket_type;
-#endif
- /// Guarded pointer - a result of \p get() and \p extract() functions
typedef typename internal_bucket_type::guarded_ptr guarded_ptr;
-
- //@cond
- /// Bucket table allocator
typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
+ typedef typename bucket_stat::stat stat;
//@endcond
protected:
//@cond
const size_t m_nHashBitmask;
- internal_bucket_type * m_Buckets; ///< bucket table
+ internal_bucket_type* m_Buckets; ///< bucket table
item_counter m_ItemCounter; ///< Item counter
hash m_HashFunctor; ///< Hash functor
- typename bucket_stat::stat m_Stat; ///< Internal statistics
+ stat m_Stat; ///< Internal statistics
//@endcond
protected:
*/
iterator begin()
{
- return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end() );
+ return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end());
}
/// Returns an iterator that addresses the location succeeding the last element in a map
*/
iterator end()
{
- return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end() );
+ return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end());
}
/// Returns a forward const iterator addressing the first element in a map
size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
)
: m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
- , m_Buckets( bucket_table_allocator().allocate( bucket_count() ) )
+ , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
{
for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
construct_bucket<bucket_stat>( it );
for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
it->~internal_bucket_type();
- bucket_table_allocator().deallocate( m_Buckets, bucket_count() );
+ bucket_table_allocator().deallocate( m_Buckets, bucket_count());
}
/// Inserts new node with key and default value
(note that in this case the \ref key_type should be constructible from type \p K).
Otherwise, if \p key is found, the functor \p func is called with item found.
- The functor \p func signature depends of \p OrderedList:
+ The functor \p func signature depends on \p OrderedList:
<b>for \p MichaelKVList, \p LazyKVList</b>
\code
\p second is true if new item has been added or \p false if the item with \p key
already exists.
- @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList"
+ @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList"
as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
\ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
synchronization.
/**
The operation performs inserting or changing data with lock-free manner.
- If the item \p val is not found in the map, then \p val is inserted iff \p bAllowInsert is \p true.
+ If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
Otherwise, the current element is changed to \p val, the old element will be retired later.
Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
#ifdef CDS_DOXYGEN_INVOKED
std::pair<bool, bool>
#else
- typename std::enable_if<
+ typename std::enable_if<
std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
std::pair<bool, bool>
>::type
return bucket( key ).find( key, f );
}
+ /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
+ /**
+ If \p key is not found the function returns \p end().
+
+ @note This function is supported only for map based on \p IterableList
+ */
+ template <typename K>
+#ifdef CDS_DOXYGEN_INVOKED
+ iterator
+#else
+ typename std::enable_if< std::is_same<K,K>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+ find( K const& key )
+ {
+ auto& b = bucket( key );
+ auto it = b.find( key );
+ if ( it == b.end())
+ return end();
+ return iterator( it, &b, bucket_end());
+ }
+
+
/// Finds the key \p val using \p pred predicate for searching
/**
The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
return bucket( key ).find_with( key, pred, f );
}
+ /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
+ /**
+ The function is an analog of \p find(K&) but \p pred is used for key comparing.
+ \p Less functor has the interface like \p std::less.
+ \p pred must imply the same element order as the comparator used for building the set.
+
+ If \p key is not found the function returns \p end().
+
+ @note This function is supported only for map based on \p IterableList
+ */
+ template <typename K, typename Less>
+#ifdef CDS_DOXYGEN_INVOKED
+ iterator
+#else
+ typename std::enable_if< std::is_same<K, K>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+ find_with( K const& key, Less pred )
+ {
+ auto& b = bucket( key );
+ auto it = b.find_with( key, pred );
+ if ( it == b.end())
+ return end();
+ return iterator( it, &b, bucket_end());
+ }
+
/// Checks whether the map contains \p key
/**
The function searches the item with key equal to \p key
{
return bucket( key ).contains( key );
}
- //@cond
- template <typename K>
- CDS_DEPRECATED("deprecated, use contains()")
- bool find( K const& key )
- {
- return bucket( key ).contains( key );
- }
- //@endcond
/// Checks whether the map contains \p key using \p pred predicate for searching
/**
{
return bucket( key ).contains( key, pred );
}
- //@cond
- template <typename K, typename Less>
- CDS_DEPRECATED("deprecated, use contains()")
- bool find_with( K const& key, Less pred )
- {
- return bucket( key ).contains( key, pred );
- }
- //@endcond
/// Finds \p key and return the item found
/** \anchor cds_nonintrusive_MichaelHashMap_hp_get
const_iterator get_const_begin() const
{
- return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end() );
+ return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end());
}
const_iterator get_const_end() const
{
- return const_iterator( (bucket_end() - 1)->cend(), bucket_end() - 1, bucket_end() );
+ return const_iterator( (bucket_end() - 1)->cend(), bucket_end() - 1, bucket_end());
}
template <typename Stat>
projects / libcds.git / blobdiff