3 #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_NOGC_H
4 #define CDSLIB_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
22 /// Lock-free skip-list map (template specialization for gc::nogc)
23 /** @ingroup cds_nonintrusive_map
24 \anchor cds_nonintrusive_SkipListMap_nogc
26 This specialization is intended for so-called persistent usage when no item
27 reclamation may be performed. The class does not support deleting of map item.
28 See \ref cds_nonintrusive_SkipListMap_hp "SkipListMap" for detailed description.
31 - \p K - type of a key to be stored in the map.
32 - \p T - type of a value to be stored in the map.
33 - \p Traits - map traits, default is \p skip_list::traits
34 It is possible to declare option-based list with \p cds::container::skip_list::make_traits
35 metafunction istead of \p Traits template argument.
40 #ifdef CDS_DOXYGEN_INVOKED
41 typename Traits = skip_list::traits
46 class SkipListMap< cds::gc::nogc, Key, T, Traits >:
47 #ifdef CDS_DOXYGEN_INVOKED
48 protected SkipListSet< cds::gc::nogc, std::pair< Key const, T >, Traits >
50 protected SkipListSet<
52 ,std::pair< Key const, T >
53 ,typename cds::opt::replace_key_accessor< Traits, skip_list::details::map_key_accessor >::type
60 ,std::pair< Key const, T >
61 ,typename cds::opt::replace_key_accessor< Traits, skip_list::details::map_key_accessor >::type
66 typedef cds::gc::nogc gc; ///< Garbage collector
67 typedef Key key_type; ///< Key type
68 typedef T mapped_type; ///< Mapped type
69 typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair stored in the map
70 typedef Traits traits; ///< Options specified
72 typedef typename base_class::back_off back_off; ///< Back-off strategy
73 typedef typename base_class::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the skip-list nodes
74 typedef typename base_class::item_counter item_counter; ///< Item counting policy
75 typedef typename base_class::key_comparator key_comparator; ///< key compare functor
76 typedef typename base_class::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
77 typedef typename base_class::stat stat; ///< internal statistics type
78 typedef typename base_class::random_level_generator random_level_generator; ///< random level generator
81 typedef cds::container::skip_list::implementation_tag implementation_tag;
86 typedef typename base_class::node_type node_type;
87 typedef typename base_class::node_allocator node_allocator;
91 /// Default constructor
96 /// Destructor clears the map
103 Remember, the iterator <tt>operator -> </tt> and <tt>operator *</tt> returns \ref value_type pointer and reference.
104 To access item key and value use <tt>it->first</tt> and <tt>it->second</tt> respectively.
106 typedef typename base_class::iterator iterator;
108 /// Const forward iterator
109 typedef typename base_class::const_iterator const_iterator;
111 /// Returns a forward iterator addressing the first element in a map
113 For empty set \code begin() == end() \endcode
117 return base_class::begin();
120 /// Returns an iterator that addresses the location succeeding the last element in a map
122 Do not use the value returned by <tt>end</tt> function to access any item.
123 The returned value can be used only to control reaching the end of the set.
124 For empty set \code begin() == end() \endcode
128 return base_class::end();
131 /// Returns a forward const iterator addressing the first element in a map
132 const_iterator begin() const
134 return base_class::begin();
136 /// Returns a forward const iterator addressing the first element in a map
137 const_iterator cbegin() const
139 return base_class::cbegin();
142 /// Returns an const iterator that addresses the location succeeding the last element in a map
143 const_iterator end() const
145 return base_class::end();
147 /// Returns an const iterator that addresses the location succeeding the last element in a map
148 const_iterator cend() const
150 return base_class::cend();
154 /// Inserts new node with key and default value
156 The function creates a node with \p key and default value, and then inserts the node created into the map.
159 - The \ref key_type should be constructible from value of type \p K.
160 In trivial case, \p K is equal to \ref key_type.
161 - The \ref mapped_type should be default-constructible.
163 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
165 template <typename K>
166 iterator insert( K const& key )
168 //TODO: pass arguments by reference (make_pair makes copy)
169 return base_class::insert( std::make_pair( key, mapped_type() ) );
174 The function creates a node with copy of \p val value
175 and then inserts the node created into the map.
178 - The \ref key_type should be constructible from \p key of type \p K.
179 - The \ref mapped_type should be constructible from \p val of type \p V.
181 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
183 template <typename K, typename V>
184 iterator insert( K const& key, V const& val )
186 //TODO: pass arguments by reference (make_pair makes copy)
187 return base_class::insert( std::make_pair( key, val ) );
190 /// Inserts new node and initialize it by a functor
192 This function inserts new node with key \p key and if inserting is successful then it calls
193 \p func functor with signature
196 void operator()( value_type& item );
200 The argument \p item of user-defined functor \p func is the reference
201 to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
202 User-defined functor \p func should guarantee that during changing item's value no any other changes
203 could be made on this map's item by concurrent threads.
205 The key_type should be constructible from value of type \p K.
207 The function allows to split creating of new item into three part:
208 - create item from \p key;
209 - insert new item into the map;
210 - if inserting is successful, initialize the value of item by calling \p f functor
212 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
213 it is preferable that the initialization should be completed only if inserting is successful.
215 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
217 template <typename K, typename Func>
218 iterator insert_with( K const& key, Func func )
220 iterator it = insert( key );
226 /// For key \p key inserts data of type \p mapped_type created in-place from \p args
228 \p key_type should be constructible from type \p K
230 Returns \p true if inserting successful, \p false otherwise.
232 template <typename K, typename... Args>
233 iterator emplace( K&& key, Args&&... args )
235 return base_class::emplace( std::forward<K>(key), std::move(mapped_type(std::forward<Args>(args)...)));
238 /// UPdates data by \p key
240 The operation inserts new item if \p key is not found in the map and \p bInsert is \p true.
241 Otherwise, if \p key is found, the function returns an iterator that points to item found.
243 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
244 item found or inserted or \p end() if \p key is not found and insertion is not allowed (\p bInsert is \p false),
245 \p second is \p true if new item has been added or \p false if the item already exists.
247 template <typename K>
248 std::pair<iterator, bool> update( K const& key, bool bInsert = true )
250 //TODO: pass arguments by reference (make_pair makes copy)
251 return base_class::update( std::make_pair( key, mapped_type() ), bInsert );
254 // Deprecated, use update()
255 template <typename K>
256 std::pair<iterator, bool> ensure( K const& key )
258 return update( key, true );
262 /// Checks whether the map contains \p key
264 The function searches the item with key equal to \p key
265 and returns an iterator pointed to item found if the key is found,
266 and \ref end() otherwise
268 template <typename K>
269 iterator contains( K const& key )
271 return base_class::contains( key );
274 // Deprecated, use contains()
275 template <typename K>
276 iterator find( K const& key )
278 return contains( key );
282 /// Checks whether the map contains \p key using \p pred predicate for searching
284 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
285 \p Less functor has the interface like \p std::less.
286 \p Less must imply the same element order as the comparator used for building the map.
288 template <typename K, typename Less>
289 iterator contains( K const& key, Less pred ) const
291 return base_class::contains( key, pred );
294 // Deprecated, use contains()
295 template <typename K, typename Less>
296 iterator find_with( K const& key, Less pred ) const
298 return contains( key, pred );
302 /// Gets minimum key from the map
304 If the map is empty the function returns \p nullptr
306 value_type * get_min() const
308 return base_class::get_min();
311 /// Gets maximum key from the map
313 The function returns \p nullptr if the map is empty
315 value_type * get_max() const
317 return base_class::get_max();
320 /// Clears the map (not atomic)
322 Finding and/or inserting is prohibited while clearing.
323 Otherwise an unpredictable result may be encountered.
324 Thus, \p clear() may be used only for debugging purposes.
331 /// Checks if the map is empty
333 Emptiness is checked by item counting: if item count is zero then the map is empty.
334 Thus, the correct item counting feature is an important part of Michael's map implementation.
338 return base_class::empty();
341 /// Returns item count in the map
344 return base_class::size();
347 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
348 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
350 return base_class::max_height();
353 /// Returns const reference to internal statistics
354 stat const& statistics() const
356 return base_class::statistics();
360 }} // namespace cds::container
363 #endif // #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_NOGC_H