4 * Copyright (c) Microsoft Corporation. All rights reserved.
\r
7 * =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
\r
9 * internal_split_ordered_list.h
\r
11 * =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
\r
15 // Needed for forward iterators
\r
16 #include <forward_list>
\r
19 namespace Concurrency
\r
23 // Split-order list iterators, needed to skip dummy elements
\r
24 template<class _Mylist>
\r
25 class _Solist_const_iterator : public std::_Flist_const_iterator<_Mylist>
\r
28 typedef _Solist_const_iterator<_Mylist> _Myiter;
\r
29 typedef std::_Flist_const_iterator<_Mylist> _Mybase;
\r
30 typedef std::forward_iterator_tag iterator_category;
\r
32 typedef typename _Mylist::_Nodeptr _Nodeptr;
\r
33 typedef typename _Mylist::value_type value_type;
\r
34 typedef typename _Mylist::difference_type difference_type;
\r
35 typedef typename _Mylist::const_pointer pointer;
\r
36 typedef typename _Mylist::const_reference reference;
\r
38 _Solist_const_iterator()
\r
42 _Solist_const_iterator(_Nodeptr _Pnode, const _Mylist * _Plist) : _Mybase(_Pnode, _Plist)
\r
46 typedef _Solist_const_iterator<_Mylist> _Unchecked_type;
\r
48 _Myiter& _Rechecked(_Unchecked_type _Right)
\r
54 _Unchecked_type _Unchecked() const
\r
56 return (_Unchecked_type(_Ptr, (_Mylist *)_Getcont()));
\r
59 reference operator*() const
\r
61 return ((reference)**(_Mybase *)this);
\r
64 pointer operator->() const
\r
69 _Myiter& operator++()
\r
73 ++(*(_Mybase *)this);
\r
75 while (_Mynode() != NULL && _Mynode()->_Is_dummy());
\r
80 _Myiter operator++(int)
\r
82 _Myiter _Tmp = *this;
\r
87 while (_Mynode() != NULL && _Mynode()->_Is_dummy());
\r
93 template<class _Mylist> inline
\r
94 typename _Solist_const_iterator<_Mylist>::_Unchecked_type _Unchecked(_Solist_const_iterator<_Mylist> _Iterator)
\r
96 return (_Iterator._Unchecked());
\r
99 template<class _Mylist> inline
\r
100 _Solist_const_iterator<_Mylist>& _Rechecked(_Solist_const_iterator<_Mylist>& _Iterator,
\r
101 typename _Solist_const_iterator<_Mylist>::_Unchecked_type _Right)
\r
103 return (_Iterator._Rechecked(_Right));
\r
106 template<class _Mylist>
\r
107 class _Solist_iterator : public _Solist_const_iterator<_Mylist>
\r
110 typedef _Solist_iterator<_Mylist> _Myiter;
\r
111 typedef _Solist_const_iterator<_Mylist> _Mybase;
\r
112 typedef std::forward_iterator_tag iterator_category;
\r
114 typedef typename _Mylist::_Nodeptr _Nodeptr;
\r
115 typedef typename _Mylist::value_type value_type;
\r
116 typedef typename _Mylist::difference_type difference_type;
\r
117 typedef typename _Mylist::pointer pointer;
\r
118 typedef typename _Mylist::reference reference;
\r
124 _Solist_iterator(_Nodeptr _Pnode, const _Mylist *_Plist) : _Mybase(_Pnode, _Plist)
\r
128 typedef _Solist_iterator<_Mylist> _Unchecked_type;
\r
130 _Myiter& _Rechecked(_Unchecked_type _Right)
\r
132 _Ptr = _Right._Ptr;
\r
136 _Unchecked_type _Unchecked() const
\r
138 return (_Unchecked_type(_Ptr, (_Mylist *)_Getcont()));
\r
141 reference operator*() const
\r
143 return ((reference)**(_Mybase *)this);
\r
146 pointer operator->() const
\r
151 _Myiter& operator++()
\r
155 ++(*(_Mybase *)this);
\r
157 while (_Mynode() != NULL && _Mynode()->_Is_dummy());
\r
162 _Myiter operator++(int)
\r
164 _Myiter _Tmp = *this;
\r
169 while (_Mynode() != NULL && _Mynode()->_Is_dummy());
\r
175 template<class _Mylist> inline
\r
176 typename _Solist_iterator<_Mylist>::_Unchecked_type _Unchecked(_Solist_iterator<_Mylist> _Iterator)
\r
178 return (_Iterator._Unchecked());
\r
181 template<class _Mylist> inline
\r
182 _Solist_iterator<_Mylist>& _Rechecked(_Solist_iterator<_Mylist>& _Iterator,
\r
183 typename _Solist_iterator<_Mylist>::_Unchecked_type _Right)
\r
185 return (_Iterator._Rechecked(_Right));
\r
188 // Forward type and class definitions
\r
189 typedef size_t _Map_key;
\r
190 typedef _Map_key _Split_order_key;
\r
192 template<typename _Element_type, typename _Allocator_type>
\r
193 class _Split_order_list_node : public std::_Container_base
\r
196 typedef typename _Allocator_type::template rebind<_Element_type>::other _Allocator_type;
\r
197 typedef typename _Allocator_type::size_type size_type;
\r
198 typedef typename _Element_type value_type;
\r
201 typedef _Node * _Nodeptr;
\r
202 typedef _Nodeptr& _Nodepref;
\r
204 // Node that holds the element in a split-ordered list
\r
207 // Initialize the node with the given order key
\r
208 void _Init(_Split_order_key _Order_key)
\r
210 _M_order_key = _Order_key;
\r
214 // Return the order key (needed for hashing)
\r
215 _Split_order_key _Get_order_key() const
\r
217 return _M_order_key;
\r
220 // Inserts the new element in the list in an atomic fashion
\r
221 _Nodeptr _Atomic_set_next(_Nodeptr _New_node, _Nodeptr _Current_node)
\r
223 // Try to change the next pointer on the current element to a new element, only if it still points to the cached next
\r
224 _Nodeptr _Exchange_node = (_Nodeptr) _InterlockedCompareExchangePointer((void * volatile *) &_M_next, _New_node, _Current_node);
\r
226 if (_Exchange_node == _Current_node)
\r
228 // Operation succeeded, return the new node
\r
233 // Operation failed, return the "interfering" node
\r
234 return _Exchange_node;
\r
238 // Checks if this element in the list is a dummy, order enforcing node. Dummy nodes are used by buckets
\r
239 // in the hash table to quickly index into the right subsection of the split-ordered list.
\r
240 bool _Is_dummy() const
\r
242 return (_M_order_key & 0x1) == 0;
\r
245 _Nodeptr _M_next; // Next element in the list
\r
246 value_type _M_element; // Element storage
\r
247 _Split_order_key _M_order_key; // Order key for this element
\r
250 #if _ITERATOR_DEBUG_LEVEL == 0 /*IFSTRIP=IGN*/
\r
251 _Split_order_list_node(_Allocator_type _Allocator) : _M_node_allocator(_Allocator), _M_value_allocator(_Allocator)
\r
254 #else /* _ITERATOR_DEBUG_LEVEL == 0 */
\r
255 _Split_order_list_node(_Allocator_type _Allocator) : _M_node_allocator(_Allocator), _M_value_allocator(_Allocator)
\r
257 typename _Allocator_type::template rebind<std::_Container_proxy>::other _Alproxy(_M_node_allocator);
\r
258 _Myproxy = _Alproxy.allocate(1);
\r
259 _Cons_val(_Alproxy, _Myproxy, std::_Container_proxy());
\r
260 _Myproxy->_Mycont = this;
\r
263 ~_Split_order_list_node()
\r
265 typename _Allocator_type::template rebind<std::_Container_proxy>::other _Alproxy(_M_node_allocator);
\r
267 _Dest_val(_Alproxy, _Myproxy);
\r
268 _Alproxy.deallocate(_Myproxy, 1);
\r
271 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */
\r
273 _Nodeptr _Myhead; // pointer to head node
\r
274 typename _Allocator_type::template rebind<_Node>::other _M_node_allocator; // allocator object for nodes
\r
275 _Allocator_type _M_value_allocator; // allocator object for element values
\r
278 template<typename _Element_type, typename _Allocator_type>
\r
279 class _Split_order_list_value : public _Split_order_list_node<_Element_type, _Allocator_type>
\r
282 typedef _Split_order_list_node<_Element_type, _Allocator_type> _Mybase;
\r
283 typedef typename _Mybase::_Nodeptr _Nodeptr;
\r
284 typedef typename _Mybase::_Nodepref _Nodepref;
\r
285 typedef typename _Allocator_type::template rebind<_Element_type>::other _Allocator_type;
\r
287 typedef typename _Allocator_type::size_type size_type;
\r
288 typedef typename _Allocator_type::difference_type difference_type;
\r
289 typedef typename _Allocator_type::pointer pointer;
\r
290 typedef typename _Allocator_type::const_pointer const_pointer;
\r
291 typedef typename _Allocator_type::reference reference;
\r
292 typedef typename _Allocator_type::const_reference const_reference;
\r
293 typedef typename _Allocator_type::value_type value_type;
\r
295 _Split_order_list_value(_Allocator_type _Allocator = _Allocator_type()) : _Mybase(_Allocator)
\r
297 // Immediately allocate a dummy node with order key of 0. This node
\r
298 // will always be the head of the list.
\r
299 _Myhead = _Buynode(0);
\r
302 ~_Split_order_list_value()
\r
306 // Allocate a new node with the given order key and value
\r
307 template<typename _ValTy>
\r
308 _Nodeptr _Buynode(_Split_order_key _Order_key, _ValTy&& _Value)
\r
310 _Nodeptr _Pnode = _M_node_allocator.allocate(1);
\r
314 _M_value_allocator.construct(std::addressof(_Myval(_Pnode)), std::forward<_ValTy>(_Value));
\r
315 _Pnode->_Init(_Order_key);
\r
319 _M_node_allocator.deallocate(_Pnode, 1);
\r
326 // Allocate a new node with the given order key; used to allocate dummy nodes
\r
327 _Nodeptr _Buynode(_Split_order_key _Order_key)
\r
329 _Nodeptr _Pnode = _M_node_allocator.allocate(1);
\r
330 _Pnode->_Init(_Order_key);
\r
335 // Get the next node
\r
336 static _Nodepref _Nextnode(_Nodeptr _Pnode)
\r
338 return ((_Nodepref)(*_Pnode)._M_next);
\r
341 // Get the stored value
\r
342 static reference _Myval(_Nodeptr _Pnode)
\r
344 return ((reference)(*_Pnode)._M_element);
\r
348 // Forward list in which elements are sorted in a split-order
\r
349 template <typename _Element_type, typename _Element_allocator_type = std::allocator<_Element_type> >
\r
350 class _Split_ordered_list : _Split_order_list_value<_Element_type, _Element_allocator_type>
\r
353 typedef _Split_ordered_list<_Element_type, _Element_allocator_type> _Mytype;
\r
354 typedef _Split_order_list_value<_Element_type, _Element_allocator_type> _Mybase;
\r
355 typedef typename _Mybase::_Allocator_type _Allocator_type;
\r
356 typedef typename _Mybase::_Nodeptr _Nodeptr;
\r
358 typedef _Allocator_type allocator_type;
\r
359 typedef typename _Allocator_type::size_type size_type;
\r
360 typedef typename _Allocator_type::difference_type difference_type;
\r
361 typedef typename _Allocator_type::pointer pointer;
\r
362 typedef typename _Allocator_type::const_pointer const_pointer;
\r
363 typedef typename _Allocator_type::reference reference;
\r
364 typedef typename _Allocator_type::const_reference const_reference;
\r
365 typedef typename _Allocator_type::value_type value_type;
\r
367 typedef _Solist_const_iterator<_Mybase> const_iterator;
\r
368 typedef _Solist_iterator<_Mybase> iterator;
\r
369 typedef std::_Flist_const_iterator<_Mybase> _Full_const_iterator;
\r
370 typedef std::_Flist_iterator<_Mybase> _Full_iterator;
\r
371 typedef std::pair<iterator, bool> _Pairib;
\r
372 using _Split_order_list_value<_Element_type, _Element_allocator_type>::_Buynode;
\r
373 _Split_ordered_list(_Allocator_type _Allocator = allocator_type()) : _Mybase(_Allocator), _M_element_count(0)
\r
377 ~_Split_ordered_list()
\r
382 // Remove the head element which is not cleared by clear()
\r
383 _Nodeptr _Pnode = _Myhead;
\r
386 _ASSERT_EXPR(_Pnode != NULL && _Nextnode(_Pnode) == NULL, L"Invalid head list node");
\r
391 // Common forward list functions
\r
393 allocator_type get_allocator() const
\r
395 return (_M_value_allocator);
\r
400 #if _ITERATOR_DEBUG_LEVEL == 2 /*IFSTRIP=IGN*/
\r
401 _Orphan_ptr(*this, 0);
\r
402 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
\r
405 _Nodeptr _Pnode = _Myhead;
\r
407 _ASSERT_EXPR(_Myhead != NULL, L"Invalid head list node");
\r
408 _Pnext = _Nextnode(_Pnode);
\r
409 _Pnode->_M_next = NULL;
\r
412 while (_Pnode != NULL)
\r
414 _Pnext = _Nextnode(_Pnode);
\r
419 _M_element_count = 0;
\r
422 // Returns a first non-dummy element in the SOL
\r
425 _Full_iterator _Iterator = _Begin();
\r
426 return _Get_first_real_iterator(_Iterator);
\r
429 // Returns a first non-dummy element in the SOL
\r
430 const_iterator begin() const
\r
432 _Full_const_iterator _Iterator = _Begin();
\r
433 return _Get_first_real_iterator(_Iterator);
\r
438 return (iterator(0, this));
\r
441 const_iterator end() const
\r
443 return (const_iterator(0, this));
\r
446 const_iterator cbegin() const
\r
448 return (((const _Mytype *)this)->begin());
\r
451 const_iterator cend() const
\r
453 return (((const _Mytype *)this)->end());
\r
456 // Checks if the number of elements (non-dummy) is 0
\r
459 return (_M_element_count == 0);
\r
462 // Returns the number of non-dummy elements in the list
\r
463 size_type size() const
\r
465 return _M_element_count;
\r
468 // Returns the maximum size of the list, determined by the allocator
\r
469 size_type max_size() const
\r
471 return _M_value_allocator.max_size();
\r
474 // Swaps 'this' list with the passed in one
\r
475 void swap(_Mytype& _Right)
\r
477 if (this == &_Right)
\r
483 if (_M_value_allocator == _Right._M_value_allocator)
\r
486 std::swap(_Myhead, _Right._Myhead);
\r
487 std::swap(_M_element_count, _Right._M_element_count);
\r
491 _Mytype _Temp_list;
\r
492 _Temp_list._Move_all(_Right);
\r
493 _Right._Move_all(*this);
\r
494 _Move_all(_Temp_list);
\r
498 // Split-order list functions
\r
500 // Returns a first element in the SOL, which is always a dummy
\r
501 _Full_iterator _Begin()
\r
503 return _Full_iterator(_Myhead, this);
\r
506 // Returns a first element in the SOL, which is always a dummy
\r
507 _Full_const_iterator _Begin() const
\r
509 return _Full_const_iterator(_Myhead, this);
\r
512 _Full_iterator _End()
\r
514 return _Full_iterator(0, this);
\r
517 _Full_const_iterator _End() const
\r
519 return _Full_const_iterator(0, this);
\r
522 static _Split_order_key _Get_key(const _Full_const_iterator& _Iterator)
\r
524 return _Iterator._Mynode()->_Get_order_key();
\r
527 // Returns a public iterator version of the internal iterator. Public iterator must not
\r
528 // be a dummy private iterator.
\r
529 iterator _Get_iterator(_Full_iterator _Iterator)
\r
531 _ASSERT_EXPR(_Iterator._Mynode() != NULL && !_Iterator._Mynode()->_Is_dummy(), L"Invalid user node (dummy)");
\r
532 return iterator(_Iterator._Mynode(), this);
\r
535 // Returns a public iterator version of the internal iterator. Public iterator must not
\r
536 // be a dummy private iterator.
\r
537 const_iterator _Get_iterator(_Full_const_iterator _Iterator) const
\r
539 _ASSERT_EXPR(_Iterator._Mynode() != NULL && !_Iterator._Mynode()->_Is_dummy(), L"Invalid user node (dummy)");
\r
540 return const_iterator(_Iterator._Mynode(), this);
\r
543 // Returns a non-const version of the _Full_iterator
\r
544 _Full_iterator _Get_iterator(_Full_const_iterator _Iterator)
\r
546 return _Full_iterator(_Iterator._Mynode(), this);
\r
549 // Returns a non-const version of the iterator
\r
550 iterator _Get_iterator(const_iterator _Iterator)
\r
552 return iterator(_Iterator._Mynode(), this);
\r
555 // Returns a public iterator version of a first non-dummy internal iterator at or after
\r
556 // the passed in internal iterator.
\r
557 iterator _Get_first_real_iterator(_Full_iterator _Iterator)
\r
559 // Skip all dummy, internal only iterators
\r
560 while (_Iterator != _End() && _Iterator._Mynode()->_Is_dummy())
\r
565 return iterator(_Iterator._Mynode(), this);
\r
568 // Returns a public iterator version of a first non-dummy internal iterator at or after
\r
569 // the passed in internal iterator.
\r
570 const_iterator _Get_first_real_iterator(_Full_const_iterator _Iterator) const
\r
572 // Skip all dummy, internal only iterators
\r
573 while (_Iterator != _End() && _Iterator._Mynode()->_Is_dummy())
\r
578 return const_iterator(_Iterator._Mynode(), this);
\r
581 // Erase an element using the allocator
\r
582 void _Erase(_Nodeptr _Delete_node)
\r
584 if (!_Delete_node->_Is_dummy())
\r
586 // Dummy nodes have nothing constructed, thus should not be destroyed.
\r
587 _M_node_allocator.destroy(_Delete_node);
\r
589 _M_node_allocator.deallocate(_Delete_node, 1);
\r
592 // Try to insert a new element in the list. If insert fails, return the node that
\r
593 // was inserted instead.
\r
594 _Nodeptr _Insert(_Nodeptr _Previous, _Nodeptr _New_node, _Nodeptr _Current_node)
\r
596 _New_node->_M_next = _Current_node;
\r
597 return _Previous->_Atomic_set_next(_New_node, _Current_node);
\r
600 // Insert a new element between passed in iterators
\r
601 _Pairib _Insert(_Full_iterator _Iterator, _Full_iterator _Next, _Nodeptr _List_node, long * _New_count)
\r
603 _Nodeptr _Inserted_node = _Insert(_Iterator._Mynode(), _List_node, _Next._Mynode());
\r
605 if (_Inserted_node == _List_node)
\r
607 // If the insert succeeded, check that the order is correct and increment the element count
\r
609 *_New_count = _InterlockedIncrement(&_M_element_count);
\r
610 return _Pairib(iterator(_List_node, this), true);
\r
614 return _Pairib(end(), false);
\r
618 // Insert a new dummy element, starting search at a parent dummy element
\r
619 _Full_iterator _Insert_dummy(_Full_iterator _Iterator, _Split_order_key _Order_key)
\r
621 _Full_iterator _Last = _End();
\r
622 _Full_iterator _Where = _Iterator;
\r
624 _ASSERT_EXPR(_Where != _Last, L"Invalid head node");
\r
628 // Create a dummy element up front, even though it may be discarded (due to concurrent insertion)
\r
629 _Nodeptr _Dummy_node = _Buynode(_Order_key);
\r
633 _ASSERT_EXPR(_Iterator != _Last, L"Invalid head list node");
\r
635 // If the head iterator is at the end of the list, or past the point where this dummy
\r
636 // node needs to be inserted, then try to insert it.
\r
637 if (_Where == _Last || _Get_key(_Where) > _Order_key)
\r
639 _ASSERT_EXPR(_Get_key(_Iterator) < _Order_key, L"Invalid node order in the list");
\r
641 // Try to insert it in the right place
\r
642 _Nodeptr _Inserted_node = _Insert(_Iterator._Mynode(), _Dummy_node, _Where._Mynode());
\r
644 if (_Inserted_node == _Dummy_node)
\r
646 // Insertion succeeded, check the list for order violations
\r
648 return _Full_iterator(_Dummy_node, this);
\r
652 // Insertion failed: either dummy node was inserted by another thread, or
\r
653 // a real element was inserted at exactly the same place as dummy node.
\r
654 // Proceed with the search from the previous location where order key was
\r
655 // known to be larger (note: this is legal only because there is no safe
\r
656 // concurrent erase operation supported).
\r
657 _Where = _Iterator;
\r
662 else if (_Get_key(_Where) == _Order_key)
\r
664 // Another dummy node with the same value found, discard the new one.
\r
665 _Erase(_Dummy_node);
\r
669 // Move the iterator forward
\r
670 _Iterator = _Where;
\r
676 // This erase function can handle both real and dummy nodes
\r
677 void _Erase(_Full_iterator _Previous, _Full_const_iterator& _Where)
\r
679 #if _ITERATOR_DEBUG_LEVEL == 2 /*IFSTRIP=IGN*/
\r
680 if (_Where._Getcont() != this || _Where._Ptr == _Myhead)
\r
682 std::_DEBUG_ERROR("list erase iterator outside range");
\r
684 _Nodeptr _Pnode = (_Where++)._Mynode();
\r
685 _Orphan_ptr(*this, _Pnode);
\r
686 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
\r
687 _Nodeptr _Pnode = (_Where++)._Mynode();
\r
688 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
\r
690 _Nodeptr _Prevnode = _Previous._Mynode();
\r
691 _ASSERT_EXPR(_Prevnode->_M_next == _Pnode, L"Erase must take consecutive iterators");
\r
692 _Prevnode->_M_next = _Pnode->_M_next;
\r
697 // Erase the element (previous node needs to be passed because this is a forward only list)
\r
698 iterator _Erase(_Full_iterator _Previous, const_iterator _Where)
\r
700 _Full_const_iterator _Iterator = _Where;
\r
701 _Erase(_Previous, _Iterator);
\r
702 _M_element_count--;
\r
704 return _Get_iterator(_Get_first_real_iterator(_Iterator));
\r
707 // Move all elements from the passed in split-ordered list to this one
\r
708 void _Move_all(_Mytype& _Source_list)
\r
710 _Full_const_iterator _First = _Source_list._Begin();
\r
711 _Full_const_iterator _Last = _Source_list._End();
\r
713 if (_First == _Last)
\r
718 _Nodeptr _Previous_node = _Myhead;
\r
719 _Full_const_iterator _Begin_iterator = _First++;
\r
721 // Move all elements one by one, including dummy ones
\r
722 for (_Full_const_iterator _Iterator = _First; _Iterator != _Last;)
\r
724 _Nodeptr _Node = _Iterator._Mynode();
\r
726 _Nodeptr _Dummy_node = _Node->_Is_dummy() ? _Buynode(_Node->_Get_order_key()) : _Buynode(_Node->_Get_order_key(), _Myval(_Node));
\r
727 _Previous_node = _Insert(_Previous_node, _Dummy_node, NULL);
\r
728 _ASSERT_EXPR(_Previous_node != NULL, L"Insertion must succeed");
\r
729 _Full_const_iterator _Where = _Iterator++;
\r
730 _Source_list._Erase(_Get_iterator(_Begin_iterator), _Where);
\r
736 // Check the list for order violations
\r
737 void _Check_range()
\r
739 #if defined (_DEBUG)
\r
740 for (_Full_iterator _Iterator = _Begin(); _Iterator != _End(); _Iterator++)
\r
742 _Full_iterator _Next_iterator = _Iterator;
\r
745 _ASSERT_EXPR(_Next_iterator == end() || _Next_iterator._Mynode()->_Get_order_key() >= _Iterator._Mynode()->_Get_order_key(), L"!!! List order inconsistency !!!");
\r
750 #if _ITERATOR_DEBUG_LEVEL == 2 /*IFSTRIP=IGN*/
\r
751 void _Orphan_ptr(_Mytype& _Cont, _Nodeptr _Ptr) const
\r
753 std::_Lockit _Lock(_LOCK_DEBUG);
\r
754 const_iterator **_Pnext = (const_iterator **)_Cont._Getpfirst();
\r
757 while (*_Pnext != 0)
\r
759 if ((*_Pnext)->_Ptr == (_Nodeptr)&_Myhead || _Ptr != 0 && (*_Pnext)->_Ptr != _Ptr)
\r
761 _Pnext = (const_iterator **)(*_Pnext)->_Getpnext();
\r
765 (*_Pnext)->_Clrcont();
\r
766 *_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();
\r
771 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */
\r
773 volatile long _M_element_count; // Total item count, not counting dummy nodes
\r
776 } // namespace details;
\r
777 } // namespace Concurrency
\r