2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_NOGC_H
32 #define CDSLIB_CONTAINER_SKIP_LIST_MAP_NOGC_H
34 #include <cds/container/skip_list_set_nogc.h>
36 namespace cds { namespace container {
38 namespace skip_list { namespace details {
39 struct map_key_accessor
41 template <typename NodeType>
42 typename NodeType::stored_value_type::first_type const& operator()( NodeType const& node ) const
44 return node.m_Value.first;
47 }} // namespace skip_list::details
50 /// Lock-free skip-list map (template specialization for gc::nogc)
51 /** @ingroup cds_nonintrusive_map
52 \anchor cds_nonintrusive_SkipListMap_nogc
54 This specialization is intended for so-called persistent usage when no item
55 reclamation may be performed. The class does not support deleting of map item.
56 See \ref cds_nonintrusive_SkipListMap_hp "SkipListMap" for detailed description.
59 - \p K - type of a key to be stored in the map.
60 - \p T - type of a value to be stored in the map.
61 - \p Traits - map traits, default is \p skip_list::traits
62 It is possible to declare option-based list with \p cds::container::skip_list::make_traits
63 metafunction istead of \p Traits template argument.
68 #ifdef CDS_DOXYGEN_INVOKED
69 typename Traits = skip_list::traits
74 class SkipListMap< cds::gc::nogc, Key, T, Traits >:
75 #ifdef CDS_DOXYGEN_INVOKED
76 protected SkipListSet< cds::gc::nogc, std::pair< Key const, T >, Traits >
78 protected SkipListSet<
80 ,std::pair< Key const, T >
81 ,typename cds::opt::replace_key_accessor< Traits, skip_list::details::map_key_accessor >::type
88 ,std::pair< Key const, T >
89 ,typename cds::opt::replace_key_accessor< Traits, skip_list::details::map_key_accessor >::type
94 typedef cds::gc::nogc gc; ///< Garbage collector
95 typedef Key key_type; ///< Key type
96 typedef T mapped_type; ///< Mapped type
97 typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair stored in the map
98 typedef Traits traits; ///< Options specified
100 typedef typename base_class::back_off back_off; ///< Back-off strategy
101 typedef typename base_class::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the skip-list nodes
102 typedef typename base_class::item_counter item_counter; ///< Item counting policy
103 typedef typename base_class::key_comparator key_comparator; ///< key compare functor
104 typedef typename base_class::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model option
105 typedef typename base_class::stat stat; ///< internal statistics type
106 typedef typename base_class::random_level_generator random_level_generator; ///< random level generator
110 typedef typename base_class::node_type node_type;
111 typedef typename base_class::node_allocator node_allocator;
115 /// Default constructor
120 /// Destructor clears the map
125 ///@name Forward ordered iterators
129 The forward iterator for a split-list has some features:
130 - it has no post-increment operator
131 - it depends on iterator of underlying \p OrderedList
133 typedef typename base_class::iterator iterator;
135 /// Const forward iterator
136 typedef typename base_class::const_iterator const_iterator;
138 /// Returns a forward iterator addressing the first element in a map
140 For empty set \code begin() == end() \endcode
144 return base_class::begin();
147 /// Returns an iterator that addresses the location succeeding the last element in a map
149 Do not use the value returned by <tt>end</tt> function to access any item.
150 The returned value can be used only to control reaching the end of the set.
151 For empty set \code begin() == end() \endcode
155 return base_class::end();
158 /// Returns a forward const iterator addressing the first element in a map
159 const_iterator begin() const
161 return base_class::begin();
164 /// Returns a forward const iterator addressing the first element in a map
165 const_iterator cbegin() const
167 return base_class::cbegin();
170 /// Returns an const iterator that addresses the location succeeding the last element in a map
171 const_iterator end() const
173 return base_class::end();
176 /// Returns an const iterator that addresses the location succeeding the last element in a map
177 const_iterator cend() const
179 return base_class::cend();
184 /// Inserts new node with key and default value
186 The function creates a node with \p key and default value, and then inserts the node created into the map.
189 - The \ref key_type should be constructible from value of type \p K.
190 In trivial case, \p K is equal to \ref key_type.
191 - The \ref mapped_type should be default-constructible.
193 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
195 template <typename K>
196 iterator insert( K const& key )
198 //TODO: pass arguments by reference (make_pair makes copy)
199 return base_class::insert( std::make_pair( key_type( key ), mapped_type() ) );
204 The function creates a node with copy of \p val value
205 and then inserts the node created into the map.
208 - The \ref key_type should be constructible from \p key of type \p K.
209 - The \ref mapped_type should be constructible from \p val of type \p V.
211 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
213 template <typename K, typename V>
214 iterator insert( K const& key, V const& val )
216 //TODO: pass arguments by reference (make_pair makes copy)
217 return base_class::insert( std::make_pair( key_type( key ), mapped_type( val )));
220 /// Inserts new node and initialize it by a functor
222 This function inserts new node with key \p key and if inserting is successful then it calls
223 \p func functor with signature
226 void operator()( value_type& item );
230 The argument \p item of user-defined functor \p func is the reference
231 to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
232 User-defined functor \p func should guarantee that during changing item's value no any other changes
233 could be made on this map's item by concurrent threads.
235 The key_type should be constructible from value of type \p K.
237 The function allows to split creating of new item into three part:
238 - create item from \p key;
239 - insert new item into the map;
240 - if inserting is successful, initialize the value of item by calling \p f functor
242 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
243 it is preferable that the initialization should be completed only if inserting is successful.
245 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
247 template <typename K, typename Func>
248 iterator insert_with( K const& key, Func func )
250 iterator it = insert( key );
256 /// For key \p key inserts data of type \p mapped_type created in-place from \p args
258 \p key_type should be constructible from type \p K
260 Returns \p true if inserting successful, \p false otherwise.
262 template <typename K, typename... Args>
263 iterator emplace( K&& key, Args&&... args )
265 return base_class::emplace( key_type( std::forward<K>( key )), mapped_type( std::forward<Args>(args)... ));
268 /// UPdates data by \p key
270 The operation inserts new item if \p key is not found in the map and \p bInsert is \p true.
271 Otherwise, if \p key is found, the function returns an iterator that points to item found.
273 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
274 item found or inserted or \p end() if \p key is not found and insertion is not allowed (\p bInsert is \p false),
275 \p second is \p true if new item has been added or \p false if the item already exists.
277 template <typename K>
278 std::pair<iterator, bool> update( K const& key, bool bInsert = true )
280 //TODO: pass arguments by reference (make_pair makes copy)
281 return base_class::update( std::make_pair( key_type( key ), mapped_type() ), bInsert );
284 template <typename K>
285 CDS_DEPRECATED("ensure() is deprecated, use update()")
286 std::pair<iterator, bool> ensure( K const& key )
288 return update( key, true );
292 /// Checks whether the map contains \p key
294 The function searches the item with key equal to \p key
295 and returns an iterator pointed to item found if the key is found,
296 and \ref end() otherwise
298 template <typename K>
299 iterator contains( K const& key )
301 return base_class::contains( key );
305 template <typename K>
306 CDS_DEPRECATED("deprecated, use contains()")
307 iterator find( K const& key )
309 return contains( key );
313 /// Checks whether the map contains \p key using \p pred predicate for searching
315 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
316 \p Less functor has the interface like \p std::less.
317 \p Less must imply the same element order as the comparator used for building the map.
319 template <typename K, typename Less>
320 iterator contains( K const& key, Less pred ) const
322 return base_class::contains( key, pred );
325 template <typename K, typename Less>
326 CDS_DEPRECATED("deprecated, use contains()")
327 iterator find_with( K const& key, Less pred ) const
329 return contains( key, pred );
333 /// Gets minimum key from the map
335 If the map is empty the function returns \p nullptr
337 value_type * get_min() const
339 return base_class::get_min();
342 /// Gets maximum key from the map
344 The function returns \p nullptr if the map is empty
346 value_type * get_max() const
348 return base_class::get_max();
351 /// Clears the map (not atomic)
353 Finding and/or inserting is prohibited while clearing.
354 Otherwise an unpredictable result may be encountered.
355 Thus, \p clear() may be used only for debugging purposes.
362 /// Checks if the map is empty
364 Emptiness is checked by item counting: if item count is zero then the map is empty.
365 Thus, the correct item counting feature is an important part of Michael's map implementation.
369 return base_class::empty();
372 /// Returns item count in the map
375 return base_class::size();
378 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
379 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
381 return base_class::max_height();
384 /// Returns const reference to internal statistics
385 stat const& statistics() const
387 return base_class::statistics();
391 }} // namespace cds::container
394 #endif // #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_NOGC_H