Major merge from 'dev'
[libcds.git] / cds / container / michael_kvlist_nogc.h
1 //$$CDS-header$$
2
3 #ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_NOGC_H
4 #define CDSLIB_CONTAINER_MICHAEL_KVLIST_NOGC_H
5
6 #include <memory>
7 #include <cds/container/details/michael_list_base.h>
8 #include <cds/intrusive/michael_list_nogc.h>
9 #include <cds/container/details/make_michael_kvlist.h>
10
11 namespace cds { namespace container {
12
13     //@cond
14     namespace details {
15
16         template <typename K, typename T, class Traits>
17         struct make_michael_kvlist_nogc: public make_michael_kvlist<gc::nogc, K, T, Traits>
18         {
19             typedef make_michael_kvlist<cds::gc::nogc, K, T, Traits>  base_maker;
20             typedef typename base_maker::node_type node_type;
21
22             struct intrusive_traits: public base_maker::intrusive_traits
23             {
24                 typedef typename base_maker::node_deallocator    disposer;
25             };
26
27             typedef intrusive::MichaelList<cds::gc::nogc, node_type, intrusive_traits>  type;
28         };
29
30     }   // namespace details
31     //@endcond
32
33     /// Michael's ordered list (key-value pair, template specialization for gc::nogc)
34     /** @ingroup cds_nonintrusive_list
35         @anchor cds_nonintrusive_MichaelKVList_nogc
36
37         This specialization is intended for so-called persistent usage when no item
38         reclamation may be performed. The class does not support deleting of list item.
39
40         Usually, ordered single-linked list is used as a building block for the hash table implementation.
41         The complexity of searching is <tt>O(N)</tt>.
42
43         See \ref cds_nonintrusive_MichaelList_gc "MichaelList" for description of template parameters.
44
45         The interface of the specialization is a little different.
46     */
47     template <
48         typename Key,
49         typename Value,
50 #ifdef CDS_DOXYGEN_INVOKED
51         typename Traits = michael_list::traits
52 #else
53         typename Traits
54 #endif
55     >
56     class MichaelKVList<gc::nogc, Key, Value, Traits>:
57 #ifdef CDS_DOXYGEN_INVOKED
58         protected intrusive::MichaelList< gc::nogc, implementation_defined, Traits >
59 #else
60         protected details::make_michael_kvlist_nogc< Key, Value, Traits >::type
61 #endif
62     {
63         //@cond
64         typedef details::make_michael_kvlist_nogc< Key, Value, Traits > maker;
65         typedef typename maker::type  base_class;
66         //@endcond
67
68     public:
69         typedef cds::gc::nogc gc;         ///< Garbage collector used
70         typedef Traits        traits;     ///< List traits
71
72 #ifdef CDS_DOXYGEN_INVOKED
73         typedef Key                                 key_type        ;   ///< Key type
74         typedef Value                               mapped_type     ;   ///< Type of value stored in the list
75         typedef std::pair<key_type const, mapped_type> value_type   ;   ///< key/value pair stored in the list
76 #else
77         typedef typename maker::key_type          key_type;
78         typedef typename maker::value_type        mapped_type;
79         typedef typename maker::pair_type         value_type;
80 #endif
81
82         typedef typename base_class::back_off     back_off;       ///< Back-off strategy used
83         typedef typename maker::allocator_type    allocator_type; ///< Allocator type used for allocate/deallocate the nodes
84         typedef typename base_class::item_counter item_counter;   ///< Item counting policy used
85         typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
86         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See cds::opt::memory_model option
87
88     protected:
89         //@cond
90         typedef typename base_class::value_type   node_type;
91         typedef typename maker::cxx_allocator     cxx_allocator;
92         typedef typename maker::node_deallocator  node_deallocator;
93         typedef typename maker::intrusive_traits::compare  intrusive_key_comparator;
94
95         typedef typename base_class::atomic_node_ptr head_type;
96         //@endcond
97
98     protected:
99         //@cond
100         template <typename K>
101         static node_type * alloc_node(const K& key)
102         {
103             return cxx_allocator().New( key );
104         }
105
106         template <typename K, typename V>
107         static node_type * alloc_node( const K& key, const V& val )
108         {
109             return cxx_allocator().New( key, val );
110         }
111
112         template <typename K, typename... Args>
113         static node_type * alloc_node( K&& key, Args&&... args )
114         {
115             return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)... );
116         }
117
118         static void free_node( node_type * pNode )
119         {
120             cxx_allocator().Delete( pNode );
121         }
122
123         struct node_disposer {
124             void operator()( node_type * pNode )
125             {
126                 free_node( pNode );
127             }
128         };
129         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
130
131         head_type& head()
132         {
133             return base_class::m_pHead;
134         }
135
136         head_type const& head() const
137         {
138             return base_class::m_pHead;
139         }
140         //@endcond
141
142     protected:
143         //@cond
144         template <bool IsConst>
145         class iterator_type: protected base_class::template iterator_type<IsConst>
146         {
147             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
148
149             iterator_type( head_type const& refNode )
150                 : iterator_base( refNode )
151             {}
152
153             explicit iterator_type( const iterator_base& it )
154                 : iterator_base( it )
155             {}
156
157             friend class MichaelKVList;
158
159         protected:
160             explicit iterator_type( node_type& pNode )
161                 : iterator_base( &pNode )
162             {}
163
164         public:
165             typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference  value_ref;
166             typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer    value_ptr;
167
168             typedef typename cds::details::make_const_type<value_type,  IsConst>::reference  pair_ref;
169             typedef typename cds::details::make_const_type<value_type,  IsConst>::pointer    pair_ptr;
170
171             iterator_type()
172                 : iterator_base()
173             {}
174
175             iterator_type( const iterator_type& src )
176                 : iterator_base( src )
177             {}
178
179             key_type const& key() const
180             {
181                 typename iterator_base::value_ptr p = iterator_base::operator ->();
182                 assert( p != nullptr );
183                 return p->m_Data.first;
184             }
185
186             value_ref val() const
187             {
188                 typename iterator_base::value_ptr p = iterator_base::operator ->();
189                 assert( p != nullptr );
190                 return p->m_Data.second;
191             }
192
193             pair_ptr operator ->() const
194             {
195                 typename iterator_base::value_ptr p = iterator_base::operator ->();
196                 return p ? &(p->m_Data) : nullptr;
197             }
198
199             pair_ref operator *() const
200             {
201                 typename iterator_base::value_ref p = iterator_base::operator *();
202                 return p.m_Data;
203             }
204
205             /// Pre-increment
206             iterator_type& operator ++()
207             {
208                 iterator_base::operator ++();
209                 return *this;
210             }
211
212             /// Post-increment
213             iterator_type operator ++(int)
214             {
215                 return iterator_base::operator ++(0);
216             }
217
218             template <bool C>
219             bool operator ==(iterator_type<C> const& i ) const
220             {
221                 return iterator_base::operator ==(i);
222             }
223             template <bool C>
224             bool operator !=(iterator_type<C> const& i ) const
225             {
226                 return iterator_base::operator !=(i);
227             }
228         };
229         //@endcond
230
231     public:
232         /// Forward iterator
233         /**
234             The forward iterator for Michael's list based on gc::nogc has pre- and post-increment operators.
235
236             The iterator interface to access item data:
237             - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator
238             - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \ref value_type for iterator
239             - <tt> const key_type& key() </tt> - returns a key reference for iterator
240             - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
241
242             For both functions the iterator should not be equal to <tt> end() </tt>
243         */
244         typedef iterator_type<false>    iterator;
245
246         /// Const forward iterator
247         /**
248             For iterator's features and requirements see \ref iterator
249         */
250         typedef iterator_type<true>     const_iterator;
251
252         /// Returns a forward iterator addressing the first element in a list
253         /**
254             For empty list \code begin() == end() \endcode
255         */
256         iterator begin()
257         {
258             return iterator( head() );
259         }
260
261         /// Returns an iterator that addresses the location succeeding the last element in a list
262         /**
263             Do not use the value returned by <tt>end</tt> function to access any item.
264             Internally, <tt>end</tt> returning value equals to \p nullptr.
265
266             The returned value can be used only to control reaching the end of the list.
267             For empty list \code begin() == end() \endcode
268         */
269         iterator end()
270         {
271             return iterator();
272         }
273
274         /// Returns a forward const iterator addressing the first element in a list
275         //@{
276         const_iterator begin() const
277         {
278             return const_iterator( head() );
279         }
280         const_iterator cbegin() const
281         {
282             return const_iterator( head() );
283         }
284         //@}
285
286         /// Returns an const iterator that addresses the location succeeding the last element in a list
287         //@{
288         const_iterator end() const
289         {
290             return const_iterator();
291         }
292         const_iterator cend() const
293         {
294             return const_iterator();
295         }
296         //@}
297
298     protected:
299         //@cond
300         iterator node_to_iterator( node_type * pNode )
301         {
302             if ( pNode )
303                 return iterator( *pNode );
304             return end();
305         }
306         //@endcond
307
308     public:
309         /// Default constructor
310         /**
311             Initialize empty list
312         */
313         MichaelKVList()
314         {}
315
316         /// List desctructor
317         /**
318             Clears the list
319         */
320         ~MichaelKVList()
321         {
322             clear();
323         }
324
325         /// Inserts new node with key and default value
326         /**
327             The function creates a node with \p key and default value, and then inserts the node created into the list.
328
329             Preconditions:
330             - The \ref key_type should be constructible from value of type \p K.
331                 In trivial case, \p K is equal to \ref key_type.
332             - The \ref mapped_type should be default-constructible.
333
334             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
335         */
336         template <typename K>
337         iterator insert( const K& key )
338         {
339             return node_to_iterator( insert_at( head(), key ));
340         }
341
342         /// Inserts new node with a key and a value
343         /**
344             The function creates a node with \p key and value \p val, and then inserts the node created into the list.
345
346             Preconditions:
347             - The \ref key_type should be constructible from \p key of type \p K.
348             - The \ref mapped_type should be constructible from \p val of type \p V.
349
350             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
351         */
352         template <typename K, typename V>
353         iterator insert( const K& key, const V& val )
354         {
355             // We cannot use insert with functor here
356             // because we cannot lock inserted node for updating
357             // Therefore, we use separate function
358             return node_to_iterator( insert_at( head(), key, val ));
359         }
360
361         /// Inserts new node and initialize it by a functor
362         /**
363             This function inserts new node with key \p key and if inserting is successful then it calls
364             \p func functor with signature
365             \code void func( value_type& item );
366                 struct functor {
367                     void operator()( value_type& item );
368                 };
369             \endcode
370
371             The argument \p item of user-defined functor \p func is the reference
372             to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
373             User-defined functor \p func should guarantee that during changing item's value no any other changes
374             could be made on this list's item by concurrent threads.
375
376             The key_type should be constructible from value of type \p K.
377
378             The function allows to split creating of new item into two part:
379             - create item from \p key;
380             - insert new item into the list;
381             - if inserting is successful, initialize the value of item by calling \p f functor
382
383             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
384             it is preferable that the initialization should be completed only if inserting is successful.
385
386             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
387         */
388         template <typename K, typename Func>
389         iterator insert_with( const K& key, Func func )
390         {
391             return node_to_iterator( insert_with_at( head(), key, func ));
392         }
393
394         /// Ensures that the key \p key exists in the list
395         /**
396             The operation inserts new item if the key \p key is not found in the list.
397             Otherwise, the function returns an iterator that points to item found.
398
399             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
400             item found or inserted, \p second is true if new item has been added or \p false if the item
401             already is in the list.
402         */
403         template <typename K>
404         std::pair<iterator, bool> ensure( const K& key )
405         {
406             std::pair< node_type *, bool > ret = ensure_at( head(), key );
407             return std::make_pair( node_to_iterator( ret.first ), ret.second );
408         }
409
410         /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
411         /**
412             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
413         */
414         template <typename K, typename... Args>
415         iterator emplace( K&& key, Args&&... args )
416         {
417             return node_to_iterator( emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... ));
418         }
419
420         /// Find the key \p key
421         /** \anchor cds_nonintrusive_MichaelKVList_nogc_find
422
423             The function searches the item with key equal to \p key
424             and returns an iterator pointed to item found if the key is found,
425             and \ref end() otherwise
426         */
427         template <typename Q>
428         iterator find( Q const& key )
429         {
430             return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) );
431         }
432
433         /// Finds the key \p key using \p pred predicate for searching
434         /**
435             The function is an analog of \ref cds_nonintrusive_MichaelKVList_nogc_find "find(Q const&)"
436             but \p pred is used for key comparing.
437             \p Less functor has the interface like \p std::less.
438             \p pred must imply the same element order as the comparator used for building the list.
439         */
440         template <typename Q, typename Less>
441         iterator find_with( Q const& key, Less pred )
442         {
443             CDS_UNUSED( pred );
444             return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
445         }
446
447         /// Check if the list is empty
448         bool empty() const
449         {
450             return base_class::empty();
451         }
452
453         /// Returns list's item count
454         /**
455             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
456             this function always returns 0.
457
458             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
459             is empty. To check list emptyness use \p empty() method.
460         */
461         size_t size() const
462         {
463             return base_class::size();
464         }
465
466         /// Clears the list
467         void clear()
468         {
469             base_class::clear();
470         }
471
472     protected:
473         //@cond
474         node_type * insert_node_at( head_type& refHead, node_type * pNode )
475         {
476             assert( pNode != nullptr );
477             scoped_node_ptr p( pNode );
478             if ( base_class::insert_at( refHead, *pNode ))
479                 return p.release();
480             return nullptr;
481         }
482
483         template <typename K>
484         node_type * insert_at( head_type& refHead, const K& key )
485         {
486             return insert_node_at( refHead, alloc_node( key ));
487         }
488
489         template <typename K, typename V>
490         node_type * insert_at( head_type& refHead, const K& key, const V& val )
491         {
492             return insert_node_at( refHead, alloc_node( key, val ));
493         }
494
495         template <typename K, typename Func>
496         node_type * insert_with_at( head_type& refHead, const K& key, Func f )
497         {
498             scoped_node_ptr pNode( alloc_node( key ));
499
500             if ( base_class::insert_at( refHead, *pNode )) {
501                 f( pNode->m_Data );
502                 return pNode.release();
503             }
504             return nullptr;
505         }
506
507         template <typename K>
508         std::pair< node_type *, bool > ensure_at( head_type& refHead, const K& key )
509         {
510             scoped_node_ptr pNode( alloc_node( key ));
511             node_type * pItemFound = nullptr;
512
513             std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; });
514             assert( pItemFound != nullptr );
515
516             if ( ret.first && ret.second )
517                 pNode.release();
518             return std::make_pair( pItemFound, ret.second );
519         }
520
521         template <typename K, typename... Args>
522         node_type * emplace_at( head_type& refHead, K&& key, Args&&... args )
523         {
524             return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
525         }
526
527         template <typename K, typename Compare>
528         node_type * find_at( head_type& refHead, K const& key, Compare cmp )
529         {
530             return base_class::find_at( refHead, key, cmp );
531         }
532         //@endcond
533     };
534
535 }} // namespace cds::container
536
537 #endif // #ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_NOGC_H