3 #ifndef __CDS_CONTAINER_LAZY_KVLIST_NOGC_H
4 #define __CDS_CONTAINER_LAZY_KVLIST_NOGC_H
7 #include <cds/container/details/lazy_list_base.h>
8 #include <cds/intrusive/lazy_list_nogc.h>
9 #include <cds/container/details/make_lazy_kvlist.h>
11 namespace cds { namespace container {
13 /// Lazy ordered list (key-value pair, template specialization for gc::nogc)
14 /** @ingroup cds_nonintrusive_list
15 @anchor cds_nonintrusive_LazyKVList_nogc
17 This specialization is append-only list when no item
18 reclamation may be performed. The class does not support deleting of list item.
20 @copydetails cds_nonintrusive_LazyList_gc
25 #ifdef CDS_DOXYGEN_INVOKED
26 typename Traits = lazy_list::traits
31 class LazyKVList<gc::nogc, Key, Value, Traits>:
32 #ifdef CDS_DOXYGEN_INVOKED
33 protected intrusive::LazyList< gc::nogc, implementation_defined, Traits >
35 protected details::make_lazy_kvlist< cds::gc::nogc, Key, Value, Traits >::type
39 typedef details::make_lazy_kvlist< cds::gc::nogc, Key, Value, Traits > maker;
40 typedef typename maker::type base_class;
44 typedef cds::gc::nogc gc; ///< Garbage collector
45 #ifdef CDS_DOXYGEN_INVOKED
46 typedef Key key_type ; ///< Key type
47 typedef Value mapped_type ; ///< Type of value stored in the list
48 typedef std::pair<key_type const, mapped_type> value_type ; ///< key/value pair stored in the list
50 typedef typename maker::key_type key_type;
51 typedef typename maker::mapped_type mapped_type;
52 typedef typename maker::value_type value_type;
54 typedef typename base_class::back_off back_off; ///< Back-off strategy used
55 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
56 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
57 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
58 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
62 typedef typename base_class::value_type node_type;
63 typedef typename maker::cxx_allocator cxx_allocator;
64 typedef typename maker::node_deallocator node_deallocator;
65 typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
66 typedef typename base_class::node_type head_type;
72 static node_type * alloc_node(const K& key)
74 return cxx_allocator().New( key );
77 template <typename K, typename V>
78 static node_type * alloc_node( const K& key, const V& val )
80 return cxx_allocator().New( key, val );
83 template <typename... Args>
84 static node_type * alloc_node( Args&&... args )
86 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
89 static void free_node( node_type * pNode )
91 cxx_allocator().Delete( pNode );
94 struct node_disposer {
95 void operator()( node_type * pNode )
100 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
104 return base_class::m_Head;
107 head_type const& head() const
109 return base_class::m_Head;
114 return base_class::m_Tail;
117 head_type const& tail() const
119 return base_class::m_Tail;
125 template <bool IsConst>
126 class iterator_type: protected base_class::template iterator_type<IsConst>
128 typedef typename base_class::template iterator_type<IsConst> iterator_base;
130 iterator_type( head_type const& refNode )
131 : iterator_base( const_cast<head_type *>( &refNode ))
134 explicit iterator_type( const iterator_base& it )
135 : iterator_base( it )
138 friend class LazyKVList;
141 explicit iterator_type( node_type& pNode )
142 : iterator_base( &pNode )
146 typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference value_ref;
147 typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer value_ptr;
149 typedef typename cds::details::make_const_type<value_type, IsConst>::reference pair_ref;
150 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer pair_ptr;
156 iterator_type( const iterator_type& src )
157 : iterator_base( src )
160 key_type const& key() const
162 typename iterator_base::value_ptr p = iterator_base::operator ->();
163 assert( p != nullptr );
164 return p->m_Data.first;
167 value_ref val() const
169 typename iterator_base::value_ptr p = iterator_base::operator ->();
170 assert( p != nullptr );
171 return p->m_Data.second;
174 pair_ptr operator ->() const
176 typename iterator_base::value_ptr p = iterator_base::operator ->();
177 return p ? &(p->m_Data) : nullptr;
180 pair_ref operator *() const
182 typename iterator_base::value_ref p = iterator_base::operator *();
187 iterator_type& operator ++()
189 iterator_base::operator ++();
194 iterator_type operator ++(int)
196 return iterator_base::operator ++(0);
200 bool operator ==(iterator_type<C> const& i ) const
202 return iterator_base::operator ==(i);
205 bool operator !=(iterator_type<C> const& i ) const
207 return iterator_base::operator !=(i);
215 The forward iterator for lazy list based on gc::nogc has pre- and post-increment operators.
217 The iterator interface to access item data:
218 - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator
219 - <tt> operator *</tt> - returns a reference (a const reference for \p const_iterator) to \ref value_type for iterator
220 - <tt> const key_type& key() </tt> - returns a key reference for iterator
221 - <tt> mapped_type& val() </tt> - retuns a value reference for iterator (const reference for \p const_iterator)
223 For both functions the iterator should not be equal to <tt> end() </tt>
225 typedef iterator_type<false> iterator;
227 /// Const forward iterator
229 For iterator's features and requirements see \ref iterator
231 typedef iterator_type<true> const_iterator;
233 /// Returns a forward iterator addressing the first element in a list
235 For empty list \code begin() == end() \endcode
239 iterator it( head() );
240 ++it ; // skip dummy head
244 /// Returns an iterator that addresses the location succeeding the last element in a list
246 Do not use the value returned by <tt>end</tt> function to access any item.
247 Internally, <tt>end</tt> returning value equals to nullptr.
249 The returned value can be used only to control reaching the end of the list.
250 For empty list \code begin() == end() \endcode
254 return iterator( tail());
257 /// Returns a forward const iterator addressing the first element in a list
259 const_iterator begin() const
261 const_iterator it( head() );
262 ++it ; // skip dummy head
265 const_iterator cbegin() const
267 const_iterator it( head() );
268 ++it ; // skip dummy head
273 /// Returns an const iterator that addresses the location succeeding the last element in a list
275 const_iterator end() const
277 return const_iterator( tail());
279 const_iterator cend() const
281 return const_iterator( tail());
287 iterator node_to_iterator( node_type * pNode )
290 return iterator( *pNode );
296 /// Default constructor
300 /// Desctructor clears the list
306 /// Inserts new node with key and default value
308 The function creates a node with \p key and default value, and then inserts the node created into the list.
311 - The \ref key_type should be constructible from value of type \p K.
312 In trivial case, \p K is equal to \ref key_type.
313 - The \ref mapped_type should be default-constructible.
315 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
317 template <typename K>
318 iterator insert( const K& key )
320 return node_to_iterator( insert_at( head(), key ));
323 /// Inserts new node with a key and a value
325 The function creates a node with \p key and value \p val, and then inserts the node created into the list.
328 - The \ref key_type should be constructible from \p key of type \p K.
329 - The \ref mapped_type should be constructible from \p val of type \p V.
331 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
333 template <typename K, typename V>
334 iterator insert( const K& key, const V& val )
336 // We cannot use insert with functor here
337 // because we cannot lock inserted node for updating
338 // Therefore, we use separate function
339 return node_to_iterator( insert_at( head(), key, val ));
342 /// Inserts new node and initialize it by a functor
344 This function inserts new node with key \p key and if inserting is successful then it calls
345 \p func functor with signature
346 \code void func( value_type& item ) ; endcode
350 void operator()( value_type& item );
354 The argument \p item of user-defined functor \p func is the reference
355 to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
356 The user-defined functor is called only if the inserting is successful.
358 The key_type should be constructible from value of type \p K.
360 The function allows to split creating of new item into two part:
361 - create item from \p key;
362 - insert new item into the list;
363 - if inserting is successful, initialize the value of item by calling \p f functor
365 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
366 it is preferable that the initialization should be completed only if inserting is successful.
368 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
370 template <typename K, typename Func>
371 iterator insert_key( const K& key, Func func )
373 return node_to_iterator( insert_key_at( head(), key, func ));
376 /// Ensures that the key \p key exists in the list
378 The operation inserts new item if the key \p key is not found in the list.
379 Otherwise, the function returns an iterator that points to item found.
381 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
382 item found or inserted, \p second is true if new item has been added or \p false if the item
383 already is in the list.
385 template <typename K>
386 std::pair<iterator, bool> ensure( const K& key )
388 std::pair< node_type *, bool > ret = ensure_at( head(), key );
389 return std::make_pair( node_to_iterator( ret.first ), ret.second );
392 /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
394 Returns an iterator pointed to inserted value, or \p end() if inserting is failed
396 template <typename... Args>
397 iterator emplace( Args&&... args )
399 return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
402 /// Find the key \p key
403 /** \anchor cds_nonintrusive_LazyKVList_nogc_find
404 The function searches the item with key equal to \p key
405 and returns an iterator pointed to item found if the key is found,
406 and \ref end() otherwise
408 template <typename Q>
409 iterator find( Q const& key )
411 return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ) );
414 /// Finds the key \p val using \p pred predicate for searching
416 The function is an analog of \ref cds_nonintrusive_LazyKVList_nogc_find "find(Q const&)"
417 but \p pred is used for key comparing.
418 \p Less functor has the interface like \p std::less.
419 \p pred must imply the same element order as the comparator used for building the list.
421 template <typename Q, typename Less>
422 iterator find_with( Q const& key, Less pred )
425 return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
428 /// Check if the list is empty
431 return base_class::empty();
434 /// Returns list's item count
436 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
437 this function always returns 0.
439 @note Even if you use real item counter and it returns 0, this fact is not mean that the list
440 is empty. To check list emptyness use \ref empty() method.
444 return base_class::size();
449 Post-condition: the list is empty
458 node_type * insert_node_at( head_type& refHead, node_type * pNode )
460 assert( pNode != nullptr );
461 scoped_node_ptr p( pNode );
462 if ( base_class::insert_at( &refHead, *p ))
468 template <typename K>
469 node_type * insert_at( head_type& refHead, const K& key )
471 return insert_node_at( refHead, alloc_node( key ));
474 template <typename K, typename V>
475 node_type * insert_at( head_type& refHead, const K& key, const V& val )
477 return insert_node_at( refHead, alloc_node( key, val ));
480 template <typename K, typename Func>
481 node_type * insert_key_at( head_type& refHead, const K& key, Func f )
483 scoped_node_ptr pNode( alloc_node( key ));
485 if ( base_class::insert_at( &refHead, *pNode )) {
487 return pNode.release();
494 template <typename K>
495 std::pair< node_type *, bool > ensure_at( head_type& refHead, const K& key )
497 scoped_node_ptr pNode( alloc_node( key ));
498 node_type * pItemFound = nullptr;
500 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; } );
501 if ( ret.first && ret.second )
504 assert( pItemFound != nullptr );
505 return std::make_pair( pItemFound, ret.second );
508 template <typename... Args>
509 node_type * emplace_at( head_type& refHead, Args&&... args )
511 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
514 template <typename K, typename Compare>
515 node_type * find_at( head_type& refHead, const K& key, Compare cmp )
517 return base_class::find_at( &refHead, key, cmp );
521 template <typename K, typenam Compare, typename Func>
522 bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
524 return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K const& ){ f( node.m_Data ); });
530 }} // namespace cds::container
532 #endif // #ifndef __CDS_CONTAINER_LAZY_KVLIST_NOGC_H