3 #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_NOGC_H
4 #define __CDS_CONTAINER_SKIP_LIST_MAP_NOGC_H
6 #include <cds/container/skip_list_set_nogc.h>
8 namespace cds { namespace container {
10 namespace skip_list { namespace details {
11 struct map_key_accessor
13 template <typename NodeType>
14 typename NodeType::stored_value_type::first_type const& operator()( NodeType const& node ) const
16 return node.m_Value.first;
19 }} // namespace skip_list::details
23 /// Lock-free skip-list map (template specialization for gc::nogc)
24 /** @ingroup cds_nonintrusive_map
25 \anchor cds_nonintrusive_SkipListMap_nogc
27 This specialization is intended for so-called persistent usage when no item
28 reclamation may be performed. The class does not support deleting of map item.
29 See \ref cds_nonintrusive_SkipListMap_hp "SkipListMap" for detailed description.
32 - \p K - type of a key to be stored in the list.
33 - \p T - type of a value to be stored in the list.
34 - \p Traits - type traits. See skip_list::type_traits for explanation.
36 It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
38 Template argument list \p Options of cds::container::skip_list::make_traits metafunction are:
39 - opt::compare - key compare functor. No default functor is provided.
40 If the option is not specified, the opt::less is used.
41 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<K>.
42 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
43 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
44 or opt::v::sequential_consistent (sequentially consisnent memory model).
45 - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
46 user-provided one. See skip_list::random_level_generator option description for explanation.
47 Default is \p %skip_list::turbo_pascal.
48 - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
49 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
50 - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
55 #ifdef CDS_DOXYGEN_INVOKED
56 typename Traits = skip_list::type_traits
61 class SkipListMap< cds::gc::nogc, Key, T, Traits >:
62 #ifdef CDS_DOXYGEN_INVOKED
63 protected SkipListSet< cds::gc::nogc, std::pair< Key const, T >, Traits >
65 protected SkipListSet<
67 ,std::pair< Key const, T >
68 ,typename cds::opt::replace_key_accessor< Traits, skip_list::details::map_key_accessor >::type
75 ,std::pair< Key const, T >
76 ,typename cds::opt::replace_key_accessor< Traits, skip_list::details::map_key_accessor >::type
81 typedef typename base_class::gc gc ; ///< Garbage collector used
82 typedef Key key_type ; ///< Key type
83 typedef T mapped_type ; ///< Mapped type
84 typedef std::pair< key_type const, mapped_type> value_type ; ///< Key-value pair stored in the map
85 typedef Traits options ; ///< Options specified
87 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
88 typedef typename base_class::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes
89 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
90 typedef typename base_class::key_comparator key_comparator ; ///< key compare functor
91 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
92 typedef typename base_class::stat stat ; ///< internal statistics type
93 typedef typename base_class::random_level_generator random_level_generator ; ///< random level generator
97 typedef typename base_class::node_type node_type;
98 typedef typename base_class::node_allocator node_allocator;
101 template <class Less>
102 struct less_wrapper {
103 typedef Less less_op;
105 bool operator()( value_type const& v1, value_type const& v2 ) const
107 return less_op()( v1.first, v2.first);
110 template <typename Q>
111 bool operator()( value_type const& v1, Q const& v2 ) const
113 return less_op()( v1.first, v2 );
116 template <typename Q>
117 bool operator()( Q const& v1, value_type const& v2 ) const
119 return less_op()( v1, v2.first );
126 /// Default constructor
131 /// Destructor clears the map
138 Remember, the iterator <tt>operator -> </tt> and <tt>operator *</tt> returns \ref value_type pointer and reference.
139 To access item key and value use <tt>it->first</tt> and <tt>it->second</tt> respectively.
141 typedef typename base_class::iterator iterator;
143 /// Const forward iterator
144 typedef typename base_class::const_iterator const_iterator;
146 /// Returns a forward iterator addressing the first element in a map
148 For empty set \code begin() == end() \endcode
152 return base_class::begin();
155 /// Returns an iterator that addresses the location succeeding the last element in a map
157 Do not use the value returned by <tt>end</tt> function to access any item.
158 The returned value can be used only to control reaching the end of the set.
159 For empty set \code begin() == end() \endcode
163 return base_class::end();
166 /// Returns a forward const iterator addressing the first element in a map
168 const_iterator begin() const
170 return base_class::begin();
172 const_iterator cbegin()
174 return base_class::cbegin();
178 /// Returns an const iterator that addresses the location succeeding the last element in a map
180 const_iterator end() const
182 return base_class::end();
184 const_iterator cend()
186 return base_class::cend();
191 /// Inserts new node with key and default value
193 The function creates a node with \p key and default value, and then inserts the node created into the map.
196 - The \ref key_type should be constructible from value of type \p K.
197 In trivial case, \p K is equal to \ref key_type.
198 - The \ref mapped_type should be default-constructible.
200 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
202 template <typename K>
203 iterator insert( K const& key )
205 //TODO: pass arguments by reference (make_pair makes copy)
206 return base_class::insert( std::make_pair( key, mapped_type() ) );
211 The function creates a node with copy of \p val value
212 and then inserts the node created into the map.
215 - The \ref key_type should be constructible from \p key of type \p K.
216 - The \ref mapped_type should be constructible from \p val of type \p V.
218 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
220 template <typename K, typename V>
221 iterator insert( K const& key, V const& val )
223 //TODO: pass arguments by reference (make_pair makes copy)
224 return base_class::insert( std::make_pair( key, val ) );
227 /// Inserts new node and initialize it by a functor
229 This function inserts new node with key \p key and if inserting is successful then it calls
230 \p func functor with signature
233 void operator()( value_type& item );
237 The argument \p item of user-defined functor \p func is the reference
238 to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
239 User-defined functor \p func should guarantee that during changing item's value no any other changes
240 could be made on this map's item by concurrent threads.
241 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
242 and it is called only if the inserting is successful.
244 The key_type should be constructible from value of type \p K.
246 The function allows to split creating of new item into two part:
247 - create item from \p key;
248 - insert new item into the map;
249 - if inserting is successful, initialize the value of item by calling \p f functor
251 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
252 it is preferable that the initialization should be completed only if inserting is successful.
254 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
256 template <typename K, typename Func>
257 iterator insert_key( K const& key, Func func )
259 iterator it = insert( key );
261 cds::unref( func )( (*it) );
265 # ifdef CDS_EMPLACE_SUPPORT
266 /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
268 \p key_type should be constructible from type \p K
270 Returns \p true if inserting successful, \p false otherwise.
272 This function is available only for compiler that supports
273 variadic template and move semantics
275 template <typename K, typename... Args>
276 iterator emplace( K&& key, Args&&... args )
278 return base_class::emplace( std::forward<K>(key), std::move(mapped_type(std::forward<Args>(args)...)));
282 /// Ensures that the key \p key exists in the map
284 The operation inserts new item if the key \p key is not found in the map.
285 Otherwise, the function returns an iterator that points to item found.
287 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
288 item found or inserted, \p second is true if new item has been added or \p false if the item
289 already is in the list.
291 template <typename K>
292 std::pair<iterator, bool> ensure( K const& key )
294 //TODO: pass arguments by reference (make_pair makes copy)
295 return base_class::ensure( std::make_pair( key, mapped_type() ));
298 /// Finds the key \p key
299 /** \anchor cds_nonintrusive_SkipListMap_nogc_find_val
301 The function searches the item with key equal to \p key
302 and returns an iterator pointed to item found if the key is found,
303 and \ref end() otherwise
305 template <typename K>
306 iterator find( K const& key )
308 return base_class::find( key );
311 /// Finds the key \p key with comparing functor \p cmp
313 The function is an analog of \ref cds_nonintrusive_SkipListMap_nogc_find_val "find(K const&)"
314 but \p pred is used for key comparing.
315 \p Less functor has the interface like \p std::less.
316 \p Less must imply the same element order as the comparator used for building the set.
318 template <typename K, typename Less>
319 iterator find_with( K const& key, Less pred ) const
321 return base_class::find_with( key, pred );
324 /// Gets minimum key from the map
326 If the map is empty the function returns \p NULL
328 value_type * get_min() const
330 return base_class::get_min();
333 /// Gets maximum key from the map
335 The function returns \p NULL if the map is empty
337 value_type * get_max() const
339 return base_class::get_max();
342 /// Clears the map (non-atomic)
344 The function is not atomic.
345 Finding and/or inserting is prohibited while clearing.
346 Otherwise an unpredictable result may be encountered.
347 Thus, \p clear() may be used only for debugging purposes.
354 /// Checks if the map is empty
356 Emptiness is checked by item counting: if item count is zero then the map is empty.
357 Thus, the correct item counting feature is an important part of Michael's map implementation.
361 return base_class::empty();
364 /// Returns item count in the map
367 return base_class::size();
370 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
371 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
373 return base_class::max_height();
376 /// Returns const reference to internal statistics
377 stat const& statistics() const
379 return base_class::statistics();
383 }} // namespace cds::container
386 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_NOGC_H