3 #ifndef __CDS_CONTAINER_SPLIT_LIST_MAP_NOGC_H
4 #define __CDS_CONTAINER_SPLIT_LIST_MAP_NOGC_H
6 #include <cds/container/split_list_set_nogc.h>
7 #include <cds/details/binary_functor_wrapper.h>
9 namespace cds { namespace container {
11 /// Split-ordered list map (template specialization for gc::nogc)
12 /** @ingroup cds_nonintrusive_map
13 \anchor cds_nonintrusive_SplitListMap_nogc
15 This specialization is intended for so-called persistent usage when no item
16 reclamation may be performed. The class does not support deleting of list item.
18 See \ref cds_nonintrusive_SplitListMap_hp "SplitListMap" for description of template parameters.
20 The interface of the specialization is a slightly different.
25 #ifdef CDS_DOXYGEN_INVOKED
26 class Traits = split_list::type_traits
31 class SplitListMap<cds::gc::nogc, Key, Value, Traits>:
32 protected container::SplitListSet<
34 std::pair<Key const, Value>,
35 split_list::details::wrap_map_traits<Key, Value, Traits>
39 typedef container::SplitListSet<
41 std::pair<Key const, Value>,
42 split_list::details::wrap_map_traits<Key, Value, Traits>
46 typedef typename base_class::gc gc ; ///< Garbage collector
47 typedef Key key_type ; ///< key type
48 typedef Value mapped_type ; ///< type of value stored in the map
50 typedef std::pair<key_type const, mapped_type> value_type ; ///< Pair type
51 typedef typename base_class::ordered_list ordered_list; ///< Underlying ordered list class
52 typedef typename base_class::key_comparator key_comparator ; ///< key comparison functor
54 typedef typename base_class::hash hash ; ///< Hash functor for \ref key_type
55 typedef typename base_class::item_counter item_counter ; ///< Item counter type
59 typedef typename base_class::options::type_traits::key_accessor key_accessor;
63 /// Forward iterator (see SplitListSet::iterator)
65 Remember, the iterator <tt>operator -> </tt> and <tt>operator *</tt> returns \ref value_type pointer and reference.
66 To access item key and value use <tt>it->first</tt> and <tt>it->second</tt> respectively.
68 typedef typename base_class::iterator iterator;
70 /// Const forward iterator (see SplitListSet::const_iterator)
71 typedef typename base_class::const_iterator const_iterator;
73 /// Returns a forward iterator addressing the first element in a map
75 For empty set \code begin() == end() \endcode
79 return base_class::begin();
82 /// Returns an iterator that addresses the location succeeding the last element in a map
84 Do not use the value returned by <tt>end</tt> function to access any item.
85 The returned value can be used only to control reaching the end of the set.
86 For empty set \code begin() == end() \endcode
90 return base_class::end();
93 /// Returns a forward const iterator addressing the first element in a map
95 const_iterator begin() const
97 return base_class::begin();
99 const_iterator cbegin()
101 return base_class::cbegin();
105 /// Returns an const iterator that addresses the location succeeding the last element in a map
107 const_iterator end() const
109 return base_class::end();
111 const_iterator cend()
113 return base_class::cend();
118 /// Initialize split-ordered map of default capacity
120 The default capacity is defined in bucket table constructor.
121 See intrusive::split_list::expandable_bucket_table, intrusive::split_list::static_ducket_table
122 which selects by intrusive::split_list::dynamic_bucket_table option.
128 /// Initialize split-ordered map
130 size_t nItemCount ///< estimate average item count
131 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
133 : base_class( nItemCount, nLoadFactor )
137 /// Inserts new node with key and default value
139 The function creates a node with \p key and default value, and then inserts the node created into the map.
142 - The \ref key_type should be constructible from value of type \p K.
143 In trivial case, \p K is equal to \ref key_type.
144 - The \ref mapped_type should be default-constructible.
146 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
148 template <typename K>
149 iterator insert( K const& key )
151 //TODO: pass arguments by reference (make_pair makes copy)
152 return base_class::insert( std::make_pair( key, mapped_type() ) );
157 The function creates a node with copy of \p val value
158 and then inserts the node created into the map.
161 - The \ref key_type should be constructible from \p key of type \p K.
162 - The \ref mapped_type should be constructible from \p val of type \p V.
164 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
166 template <typename K, typename V>
167 iterator insert( K const& key, V const& val )
169 //TODO: pass arguments by reference (make_pair makes copy)
170 return base_class::insert( std::make_pair( key, val ) );
173 /// Inserts new node and initialize it by a functor
175 This function inserts new node with key \p key and if inserting is successful then it calls
176 \p func functor with signature
179 void operator()( value_type& item );
183 The argument \p item of user-defined functor \p func is the reference
184 to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
185 User-defined functor \p func should guarantee that during changing item's value no any other changes
186 could be made on this map's item by concurrent threads.
187 The user-defined functor can be passed by reference using \p std::ref
188 and it is called only if the inserting is successful.
190 The key_type should be constructible from value of type \p K.
192 The function allows to split creating of new item into two part:
193 - create item from \p key;
194 - insert new item into the map;
195 - if inserting is successful, initialize the value of item by calling \p f functor
197 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
198 it is preferable that the initialization should be completed only if inserting is successful.
200 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
202 template <typename K, typename Func>
203 iterator insert_key( const K& key, Func func )
205 iterator it = insert( key );
211 /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
213 \p key_type should be constructible from type \p K
215 Returns \p true if inserting successful, \p false otherwise.
217 template <typename K, typename... Args>
218 iterator emplace( K&& key, Args&&... args )
220 return base_class::emplace( std::forward<K>(key), std::move(mapped_type(std::forward<Args>(args)...)));
223 /// Ensures that the key \p key exists in the map
225 The operation inserts new item if the key \p key is not found in the map.
226 Otherwise, the function returns an iterator that points to item found.
228 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
229 item found or inserted, \p second is true if new item has been added or \p false if the item
230 already is in the list.
232 template <typename K>
233 std::pair<iterator, bool> ensure( K const& key )
235 //TODO: pass arguments by reference (make_pair makes copy)
236 return base_class::ensure( std::make_pair( key, mapped_type() ));
239 /// Find the key \p key
240 /** \anchor cds_nonintrusive_SplitListMap_nogc_find
242 The function searches the item with key equal to \p key
243 and returns an iterator pointed to item found if the key is found,
244 and \ref end() otherwise
246 template <typename K>
247 iterator find( K const& key )
249 return base_class::find( key );
252 /// Finds the key \p val using \p pred predicate for searching
254 The function is an analog of \ref cds_nonintrusive_SplitListMap_nogc_find "find(K const&)"
255 but \p pred is used for key comparing.
256 \p Less functor has the interface like \p std::less.
257 \p Less must imply the same element order as the comparator used for building the map.
259 template <typename K, typename Less>
260 iterator find_with( K const& key, Less pred )
262 return base_class::find_with( key, cds::details::predicate_wrapper<value_type, Less, key_accessor>() );
265 /// Checks if the map is empty
267 Emptiness is checked by item counting: if item count is zero then the map is empty.
268 Thus, the correct item counting feature is an important part of Michael's map implementation.
272 return base_class::empty();
275 /// Returns item count in the map
278 return base_class::size();
281 }} // namespace cds::container
284 #endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_MAP_NOGC_H