-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+ 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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
#ifndef CDSLIB_CONTAINER_MICHAEL_MAP_H
#define CDSLIB_CONTAINER_MICHAEL_MAP_H
- for \p cds::gc::nogc declared in <tt>cds/container/michael_map_nogc.h</tt>,
see \ref cds_nonintrusive_MichaelHashMap_nogc "MichaelHashMap<gc::nogc>".
- <b>Iterators</b>
-
- The class supports a forward iterator (\ref iterator and \ref const_iterator).
- The iteration is unordered.
- The iterator object is thread-safe: the element pointed by the iterator object is guarded,
- so, the element cannot be reclaimed while the iterator object is alive.
- However, passing an iterator object between threads is dangerous.
-
- @warning Due to concurrent nature of Michael's set it is not guarantee that you can iterate
- all elements in the set: any concurrent deletion can exclude the element
- pointed by the iterator from the set, and your iteration can be terminated
- before end of the set. Therefore, such iteration is more suitable for debugging purpose only
-
- Remember, each iterator object requires an additional hazard pointer, that may be
- a limited resource for \p GC like \p gc::HP (for \p gc::DHP the count of
- guards is unlimited).
-
- The iterator class supports the following minimalistic interface:
- \code
- struct iterator {
- // Default ctor
- iterator();
-
- // Copy ctor
- iterator( iterator const& s);
-
- value_type * operator ->() const;
- value_type& operator *() const;
-
- // Pre-increment
- iterator& operator ++();
-
- // Copy assignment
- iterator& operator = (const iterator& src);
-
- bool operator ==(iterator const& i ) const;
- bool operator !=(iterator const& i ) const;
- };
- \endcode
- Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
-
\anchor cds_nonintrusive_MichaelHashMap_how_touse
<b>How to use</b>
typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
typedef typename bucket_type::guarded_ptr guarded_ptr; ///< Guarded pointer
- //@cond
- typedef cds::container::michael_map::implementation_tag implementation_tag;
- //@endcond
+ static CDS_CONSTEXPR const size_t c_nHazardPtrCount = bucket_type::c_nHazardPtrCount; ///< Count of hazard pointer required
protected:
item_counter m_ItemCounter; ///< Item counter
//@endcond
public:
+ ///@name Forward iterators (only for debugging purpose)
+ //@{
/// Forward iterator
+ /**
+ The iteration is unordered.
+ The iterator object is thread-safe: the element pointed by the iterator object is guarded,
+ so, the element cannot be reclaimed while the iterator object is alive.
+ However, passing an iterator object between threads is dangerous.
+
+ @warning Due to concurrent nature of Michael's map it is not guarantee that you can iterate
+ all elements in the map: any concurrent deletion can exclude the element
+ pointed by the iterator from the map, and your iteration can be terminated
+ before end of the map. Therefore, such iteration is more suitable for debugging purpose only.
+
+ Remember, each iterator object requires an additional hazard pointer, that may be
+ a limited resource for \p GC like \p gc::HP (for \p gc::DHP the count of
+ guards is unlimited).
+
+ The iterator class supports the following minimalistic interface:
+ \code
+ struct iterator {
+ // Default ctor
+ iterator();
+
+ // Copy ctor
+ iterator( iterator const& s);
+
+ value_type * operator ->() const;
+ value_type& operator *() const;
+
+ // Pre-increment
+ iterator& operator ++();
+
+ // Copy assignment
+ iterator& operator = (iterator const& src);
+
+ bool operator ==(iterator const& i ) const;
+ bool operator !=(iterator const& i ) const;
+ };
+ \endcode
+
+ @note The iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
+ */
typedef iterator_type< false > iterator;
/// Const forward iterator
}
/// Returns a forward const iterator addressing the first element in a map
- //@{
const_iterator begin() const
{
return get_const_begin();
}
+ /// Returns a forward const iterator addressing the first element in a map
const_iterator cbegin() const
{
return get_const_begin();
}
- //@}
/// Returns an const iterator that addresses the location succeeding the last element in a map
- //@{
const_iterator end() const
{
return get_const_end();
}
+ /// Returns an const iterator that addresses the location succeeding the last element in a map
const_iterator cend() const
{
return get_const_end();
}
- //@}
+ //@}
private:
//@cond
The functor may change any fields of the \p item.second that is \p mapped_type.
- Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
+ Returns <tt> std::pair<bool, bool> </tt> 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 \p key
already exists.
return bRet;
}
//@cond
- // Deprecated
template <typename K, typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
std::pair<bool, bool> ensure( K const& key, Func func )
{
std::pair<bool, bool> bRet = bucket( key ).update( key, func, true );
/// Extracts the item with specified \p key
/** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
The function searches an item with key equal to \p key,
- unlinks it from the set, and returns it as \p guarded_ptr.
+ unlinks it from the map, and returns it as \p guarded_ptr.
If \p key is not found the function returns an empty guarded pointer.
Note the compare functor should accept a parameter of type \p K that may be not the same as \p key_type.
return bucket( key ).contains( key );
}
//@cond
- // Deprecated
template <typename K>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find( K const& key )
{
return bucket( key ).contains( key );
return bucket( key ).contains( key, pred );
}
//@cond
- // Deprecated
template <typename K, typename Less>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find_with( K const& key, Less pred )
{
return bucket( key ).contains( key, pred );
projects / libcds.git / blobdiff