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_MICHAEL_KVLIST_NOGC_H
32 #define CDSLIB_CONTAINER_MICHAEL_KVLIST_NOGC_H
35 #include <cds/container/details/michael_list_base.h>
36 #include <cds/intrusive/michael_list_nogc.h>
37 #include <cds/container/details/make_michael_kvlist.h>
39 namespace cds { namespace container {
44 template <typename K, typename T, class Traits>
45 struct make_michael_kvlist_nogc: public make_michael_kvlist<gc::nogc, K, T, Traits>
47 typedef make_michael_kvlist<cds::gc::nogc, K, T, Traits> base_maker;
48 typedef typename base_maker::node_type node_type;
50 struct intrusive_traits: public base_maker::intrusive_traits
52 typedef typename base_maker::node_deallocator disposer;
55 typedef intrusive::MichaelList<cds::gc::nogc, node_type, intrusive_traits> type;
58 } // namespace details
61 /// Michael's ordered list (key-value pair, template specialization for gc::nogc)
62 /** @ingroup cds_nonintrusive_list
63 @anchor cds_nonintrusive_MichaelKVList_nogc
65 This specialization is intended for so-called persistent usage when no item
66 reclamation may be performed. The class does not support deleting of list item.
68 Usually, ordered single-linked list is used as a building block for the hash table implementation.
69 The complexity of searching is <tt>O(N)</tt>.
71 See \ref cds_nonintrusive_MichaelList_gc "MichaelList" for description of template parameters.
73 The interface of the specialization is a little different.
78 #ifdef CDS_DOXYGEN_INVOKED
79 typename Traits = michael_list::traits
84 class MichaelKVList<gc::nogc, Key, Value, Traits>:
85 #ifdef CDS_DOXYGEN_INVOKED
86 protected intrusive::MichaelList< gc::nogc, implementation_defined, Traits >
88 protected details::make_michael_kvlist_nogc< Key, Value, Traits >::type
92 typedef details::make_michael_kvlist_nogc< Key, Value, Traits > maker;
93 typedef typename maker::type base_class;
97 typedef cds::gc::nogc gc; ///< Garbage collector used
98 typedef Traits traits; ///< List traits
100 #ifdef CDS_DOXYGEN_INVOKED
101 typedef Key key_type ; ///< Key type
102 typedef Value mapped_type ; ///< Type of value stored in the list
103 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
105 typedef typename maker::key_type key_type;
106 typedef typename maker::value_type mapped_type;
107 typedef typename maker::pair_type value_type;
110 typedef typename base_class::back_off back_off; ///< Back-off strategy used
111 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
112 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
113 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
114 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
115 typedef typename base_class::stat stat; ///< Internal statistics
119 typedef typename base_class::value_type node_type;
120 typedef typename maker::cxx_allocator cxx_allocator;
121 typedef typename maker::node_deallocator node_deallocator;
122 typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
124 typedef typename base_class::atomic_node_ptr head_type;
129 template <typename K>
130 static node_type * alloc_node(const K& key)
132 return cxx_allocator().New( key );
135 template <typename K, typename V>
136 static node_type * alloc_node( const K& key, const V& val )
138 return cxx_allocator().New( key, val );
141 template <typename K, typename... Args>
142 static node_type * alloc_node( K&& key, Args&&... args )
144 return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)... );
147 static void free_node( node_type * pNode )
149 cxx_allocator().Delete( pNode );
152 struct node_disposer {
153 void operator()( node_type * pNode )
158 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
162 return base_class::m_pHead;
165 head_type const& head() const
167 return base_class::m_pHead;
173 template <bool IsConst>
174 class iterator_type: protected base_class::template iterator_type<IsConst>
176 typedef typename base_class::template iterator_type<IsConst> iterator_base;
178 iterator_type( head_type const& refNode )
179 : iterator_base( refNode )
182 explicit iterator_type( const iterator_base& it )
183 : iterator_base( it )
186 friend class MichaelKVList;
189 explicit iterator_type( node_type& pNode )
190 : iterator_base( &pNode )
194 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
195 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
197 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
198 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
204 iterator_type( const iterator_type& src )
205 : iterator_base( src )
208 key_type const& key() const
210 typename iterator_base::value_ptr p = iterator_base::operator ->();
211 assert( p != nullptr );
212 return p->m_Data.first;
215 value_ref val() const
217 typename iterator_base::value_ptr p = iterator_base::operator ->();
218 assert( p != nullptr );
219 return p->m_Data.second;
222 pair_ptr operator ->() const
224 typename iterator_base::value_ptr p = iterator_base::operator ->();
225 return p ? &(p->m_Data) : nullptr;
228 pair_ref operator *() const
230 typename iterator_base::value_ref p = iterator_base::operator *();
235 iterator_type& operator ++()
237 iterator_base::operator ++();
242 iterator_type operator ++(int)
244 return iterator_base::operator ++(0);
248 bool operator ==(iterator_type<C> const& i ) const
250 return iterator_base::operator ==(i);
253 bool operator !=(iterator_type<C> const& i ) const
255 return iterator_base::operator !=(i);
261 ///@name Forward iterators
265 The forward iterator is safe: you may use it in multi-threaded enviromnent without any synchronization.
267 The forward iterator for Michael's list based on \p gc::nogc has pre- and post-increment operators.
269 The iterator interface to access item data:
270 - <tt> operator -> </tt> - returns a pointer to \p value_type
271 - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \p value_type
272 - <tt> const key_type& key() </tt> - returns a key reference for iterator
273 - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
275 For both functions the iterator should not be equal to \p end().
277 @note \p end() iterator is not dereferenceable
279 typedef iterator_type<false> iterator;
281 /// Const forward iterator
283 For iterator's features and requirements see \ref iterator
285 typedef iterator_type<true> const_iterator;
287 /// Returns a forward iterator addressing the first element in a list
289 For empty list \code begin() == end() \endcode
293 return iterator( head() );
296 /// Returns an iterator that addresses the location succeeding the last element in a list
298 Do not use the value returned by <tt>end</tt> function to access any item.
299 Internally, <tt>end</tt> returning value equals to \p nullptr.
301 The returned value can be used only to control reaching the end of the list.
302 For empty list \code begin() == end() \endcode
309 /// Returns a forward const iterator addressing the first element in a list
310 const_iterator begin() const
312 return const_iterator( head() );
314 /// Returns a forward const iterator addressing the first element in a list
315 const_iterator cbegin() const
317 return const_iterator( head() );
320 /// Returns an const iterator that addresses the location succeeding the last element in a list
321 const_iterator end() const
323 return const_iterator();
325 /// Returns an const iterator that addresses the location succeeding the last element in a list
326 const_iterator cend() const
328 return const_iterator();
334 iterator node_to_iterator( node_type * pNode )
337 return iterator( *pNode );
343 /// Default constructor
345 Initialize empty list
351 template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
352 explicit MichaelKVList( Stat& st )
366 /// Inserts new node with key and default value
368 The function creates a node with \p key and default value, and then inserts the node created into the list.
371 - The \ref key_type should be constructible from value of type \p K.
372 In trivial case, \p K is equal to \ref key_type.
373 - The \ref mapped_type should be default-constructible.
375 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
377 template <typename K>
378 iterator insert( const K& key )
380 return node_to_iterator( insert_at( head(), key ));
383 /// Inserts new node with a key and a value
385 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
388 - The \ref key_type should be constructible from \p key of type \p K.
389 - The \ref mapped_type should be constructible from \p val of type \p V.
391 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
393 template <typename K, typename V>
394 iterator insert( const K& key, const V& val )
396 // We cannot use insert with functor here
397 // because we cannot lock inserted node for updating
398 // Therefore, we use separate function
399 return node_to_iterator( insert_at( head(), key, val ));
402 /// Inserts new node and initialize it by a functor
404 This function inserts new node with key \p key and if inserting is successful then it calls
405 \p func functor with signature
406 \code void func( value_type& item );
408 void operator()( value_type& item );
412 The argument \p item of user-defined functor \p func is the reference
413 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
414 User-defined functor \p func should guarantee that during changing item's value no any other changes
415 could be made on this list's item by concurrent threads.
417 The key_type should be constructible from value of type \p K.
419 The function allows to split creating of new item into two part:
420 - create item from \p key;
421 - insert new item into the list;
422 - if inserting is successful, initialize the value of item by calling \p f functor
424 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
425 it is preferable that the initialization should be completed only if inserting is successful.
427 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
429 template <typename K, typename Func>
430 iterator insert_with( const K& key, Func func )
432 return node_to_iterator( insert_with_at( head(), key, func ));
437 If \p key is not in the list and \p bAllowInsert is \p true,
439 the function inserts a new item.
440 Otherwise, the function returns an iterator pointing to the item found.
442 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
443 item found or inserted, \p second is true if new item has been added or \p false if the item
444 already is in the list.
446 template <typename K>
447 std::pair<iterator, bool> update( K const& key, bool bAllowInsert = true )
449 std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert );
450 return std::make_pair( node_to_iterator( ret.first ), ret.second );
453 template <typename K>
454 CDS_DEPRECATED("ensure() is deprecated, use update()")
455 std::pair<iterator, bool> ensure( K const& key )
457 return update( key );
461 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
463 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
465 template <typename K, typename... Args>
466 iterator emplace( K&& key, Args&&... args )
468 return node_to_iterator( emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... ));
471 /// Checks whether the list contains \p key
473 The function searches the item with key equal to \p key
474 and returns an iterator pointed to item found and \ref end() otherwise
476 template <typename Q>
477 iterator contains( Q const& key )
479 return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) );
482 template <typename Q>
483 CDS_DEPRECATED("deprecated, use contains()")
484 iterator find( Q const& key )
486 return contains( key );
490 /// Checks whether the list contains \p key using \p pred predicate for searching
492 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
493 \p Less functor has the interface like \p std::less.
494 \p pred must imply the same element order as the comparator used for building the list.
496 template <typename Q, typename Less>
497 iterator contains( Q const& key, Less pred )
500 return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
503 template <typename Q, typename Less>
504 CDS_DEPRECATED("deprecated, use contains()")
505 iterator find_with( Q const& key, Less pred )
507 return contains( key, pred );
511 /// Check if the list is empty
514 return base_class::empty();
517 /// Returns list's item count
519 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
520 this function always returns 0.
522 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
523 is empty. To check list emptyness use \p empty() method.
527 return base_class::size();
530 /// Returns const reference to internal statistics
531 stat const& statistics() const
533 return base_class::statistics();
544 node_type * insert_node_at( head_type& refHead, node_type * pNode )
546 assert( pNode != nullptr );
547 scoped_node_ptr p( pNode );
548 if ( base_class::insert_at( refHead, *pNode ))
553 template <typename K>
554 node_type * insert_at( head_type& refHead, const K& key )
556 return insert_node_at( refHead, alloc_node( key ));
559 template <typename K, typename V>
560 node_type * insert_at( head_type& refHead, const K& key, const V& val )
562 return insert_node_at( refHead, alloc_node( key, val ));
565 template <typename K, typename Func>
566 node_type * insert_with_at( head_type& refHead, const K& key, Func f )
568 scoped_node_ptr pNode( alloc_node( key ));
570 if ( base_class::insert_at( refHead, *pNode )) {
572 return pNode.release();
577 template <typename K>
578 std::pair< node_type *, bool > update_at( head_type& refHead, const K& key, bool bAllowInsert )
580 scoped_node_ptr pNode( alloc_node( key ));
581 node_type * pItemFound = nullptr;
583 std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
585 [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; },
590 return std::make_pair( pItemFound, ret.second );
593 template <typename K, typename... Args>
594 node_type * emplace_at( head_type& refHead, K&& key, Args&&... args )
596 return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
599 template <typename K, typename Compare>
600 node_type * find_at( head_type& refHead, K const& key, Compare cmp )
602 return base_class::find_at( refHead, key, cmp );
607 }} // namespace cds::container
609 #endif // #ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_NOGC_H