git.sesse.net Git - casparcg/blob - concrt_extras/internal_split_ordered_list.h

   1 /***\r
   2 * ==++==\r
   3 *\r
   4 * Copyright (c) Microsoft Corporation.  All rights reserved.\r
   5 * \r
   6 * ==--==\r
   7 * =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+\r
   8 *\r
   9 * internal_split_ordered_list.h\r
  10 *\r
  11 * =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\r
  12 ****/\r
  13 #pragma once\r
  14 \r
  15 // Needed for forward iterators\r
  16 #include <forward_list>\r
  17 #include <concrt.h>\r
  18 \r
  19 namespace Concurrency\r
  20 {\r
  21 namespace details\r
  22 {\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
  26 {\r
  27 public:\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
  31 \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
  37 \r
  38     _Solist_const_iterator()\r
  39     {\r
  40     }\r
  41 \r
  42     _Solist_const_iterator(_Nodeptr _Pnode, const _Mylist * _Plist) : _Mybase(_Pnode, _Plist)\r
  43     {\r
  44     }\r
  45 \r
  46     typedef _Solist_const_iterator<_Mylist> _Unchecked_type;\r
  47 \r
  48     _Myiter& _Rechecked(_Unchecked_type _Right)\r
  49     {\r
  50         _Ptr = _Right._Ptr;\r
  51         return (*this);\r
  52     }\r
  53 \r
  54     _Unchecked_type _Unchecked() const\r
  55     {\r
  56         return (_Unchecked_type(_Ptr, (_Mylist *)_Getcont()));\r
  57     }\r
  58 \r
  59     reference operator*() const\r
  60     {\r
  61         return ((reference)**(_Mybase *)this);\r
  62     }\r
  63 \r
  64     pointer operator->() const\r
  65     {\r
  66         return (&**this);\r
  67     }\r
  68 \r
  69     _Myiter& operator++()\r
  70     {\r
  71         do\r
  72         {\r
  73             ++(*(_Mybase *)this);\r
  74         }\r
  75         while (_Mynode() != NULL && _Mynode()->_Is_dummy());\r
  76 \r
  77         return (*this);\r
  78     }\r
  79 \r
  80     _Myiter operator++(int)\r
  81     {\r
  82         _Myiter _Tmp = *this;\r
  83         do\r
  84         {\r
  85             ++*this;\r
  86         }\r
  87         while (_Mynode() != NULL && _Mynode()->_Is_dummy());\r
  88 \r
  89         return (_Tmp);\r
  90     }\r
  91 };\r
  92 \r
  93 template<class _Mylist> inline\r
  94 typename _Solist_const_iterator<_Mylist>::_Unchecked_type _Unchecked(_Solist_const_iterator<_Mylist> _Iterator)\r
  95 {\r
  96     return (_Iterator._Unchecked());\r
  97 }\r
  98 \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
 102 {\r
 103     return (_Iterator._Rechecked(_Right));\r
 104 }\r
 105 \r
 106 template<class _Mylist>\r
 107 class _Solist_iterator : public _Solist_const_iterator<_Mylist>\r
 108 {\r
 109 public:\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
 113 \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
 119 \r
 120     _Solist_iterator()\r
 121     {\r
 122     }\r
 123 \r
 124     _Solist_iterator(_Nodeptr _Pnode, const _Mylist *_Plist) : _Mybase(_Pnode, _Plist)\r
 125     {\r
 126     }\r
 127 \r
 128     typedef _Solist_iterator<_Mylist> _Unchecked_type;\r
 129 \r
 130     _Myiter& _Rechecked(_Unchecked_type _Right)\r
 131     {\r
 132         _Ptr = _Right._Ptr;\r
 133         return (*this);\r
 134     }\r
 135 \r
 136     _Unchecked_type _Unchecked() const\r
 137     {\r
 138         return (_Unchecked_type(_Ptr, (_Mylist *)_Getcont()));\r
 139     }\r
 140 \r
 141     reference operator*() const\r
 142     {\r
 143         return ((reference)**(_Mybase *)this);\r
 144     }\r
 145 \r
 146     pointer operator->() const\r
 147     {\r
 148         return (&**this);\r
 149     }\r
 150 \r
 151     _Myiter& operator++()\r
 152     {\r
 153         do\r
 154         {\r
 155             ++(*(_Mybase *)this);\r
 156         }\r
 157         while (_Mynode() != NULL && _Mynode()->_Is_dummy());\r
 158 \r
 159         return (*this);\r
 160     }\r
 161 \r
 162     _Myiter operator++(int)\r
 163     {\r
 164         _Myiter _Tmp = *this;\r
 165         do\r
 166         {\r
 167             ++*this;\r
 168         }\r
 169         while (_Mynode() != NULL && _Mynode()->_Is_dummy());\r
 170 \r
 171         return (_Tmp);\r
 172     }\r
 173 };\r
 174 \r
 175 template<class _Mylist> inline\r
 176 typename _Solist_iterator<_Mylist>::_Unchecked_type _Unchecked(_Solist_iterator<_Mylist> _Iterator)\r
 177 {\r
 178     return (_Iterator._Unchecked());\r
 179 }\r
 180 \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
 184 {\r
 185     return (_Iterator._Rechecked(_Right));\r
 186 }\r
 187 \r
 188 // Forward type and class definitions\r
 189 typedef size_t _Map_key;\r
 190 typedef _Map_key _Split_order_key;\r
 191 \r
 192 template<typename _Element_type, typename _Allocator_type>\r
 193 class _Split_order_list_node : public std::_Container_base\r
 194 {\r
 195 public:\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
 199 \r
 200     struct _Node;\r
 201     typedef _Node * _Nodeptr;\r
 202     typedef _Nodeptr& _Nodepref;\r
 203 \r
 204     // Node that holds the element in a split-ordered list\r
 205     struct _Node\r
 206     {\r
 207         // Initialize the node with the given order key\r
 208         void _Init(_Split_order_key _Order_key)\r
 209         {\r
 210             _M_order_key = _Order_key;\r
 211             _M_next = NULL;\r
 212         }\r
 213 \r
 214         // Return the order key (needed for hashing)\r
 215         _Split_order_key _Get_order_key() const\r
 216         {\r
 217             return _M_order_key;\r
 218         }\r
 219 \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
 222         {\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
 225 \r
 226             if (_Exchange_node == _Current_node)\r
 227             {\r
 228                 // Operation succeeded, return the new node\r
 229                 return _New_node;\r
 230             }\r
 231             else\r
 232             {\r
 233                 // Operation failed, return the "interfering" node\r
 234                 return _Exchange_node;\r
 235             }\r
 236         }\r
 237 \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
 241         {\r
 242             return (_M_order_key & 0x1) == 0;\r
 243         }\r
 244 \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
 248     };\r
 249 \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
 252     {\r
 253     }\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
 256     {\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
 261     }\r
 262 \r
 263     ~_Split_order_list_node()\r
 264     {\r
 265         typename _Allocator_type::template rebind<std::_Container_proxy>::other _Alproxy(_M_node_allocator);\r
 266         _Orphan_all();\r
 267         _Dest_val(_Alproxy, _Myproxy);\r
 268         _Alproxy.deallocate(_Myproxy, 1);\r
 269         _Myproxy = 0;\r
 270     }\r
 271 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */\r
 272 \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
 276 };\r
 277 \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
 280 {\r
 281 public:\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
 286 \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
 294 \r
 295     _Split_order_list_value(_Allocator_type _Allocator = _Allocator_type()) : _Mybase(_Allocator)\r
 296     {\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
 300     }\r
 301 \r
 302     ~_Split_order_list_value()\r
 303     {\r
 304     }\r
 305 \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
 309     {\r
 310         _Nodeptr _Pnode = _M_node_allocator.allocate(1);\r
 311 \r
 312         try\r
 313         {\r
 314             _M_value_allocator.construct(std::addressof(_Myval(_Pnode)), std::forward<_ValTy>(_Value));\r
 315             _Pnode->_Init(_Order_key);\r
 316         }\r
 317         catch(...)\r
 318         {\r
 319             _M_node_allocator.deallocate(_Pnode, 1);\r
 320             throw;\r
 321         }\r
 322 \r
 323         return (_Pnode);\r
 324     }\r
 325 \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
 328     {\r
 329         _Nodeptr _Pnode = _M_node_allocator.allocate(1);\r
 330         _Pnode->_Init(_Order_key);\r
 331 \r
 332         return (_Pnode);\r
 333     }\r
 334 \r
 335     // Get the next node\r
 336     static _Nodepref _Nextnode(_Nodeptr _Pnode)\r
 337     {\r
 338         return ((_Nodepref)(*_Pnode)._M_next);\r
 339     }\r
 340 \r
 341     // Get the stored value\r
 342     static reference _Myval(_Nodeptr _Pnode)\r
 343     {\r
 344         return ((reference)(*_Pnode)._M_element);\r
 345     }\r
 346 };\r
 347 \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
 351 {\r
 352 public:\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
 357 \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
 366 \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
 374     {\r
 375     }\r
 376 \r
 377     ~_Split_ordered_list()\r
 378     {\r
 379         // Clear the list\r
 380         clear();\r
 381 \r
 382         // Remove the head element which is not cleared by clear()\r
 383         _Nodeptr _Pnode = _Myhead;\r
 384         _Myhead = NULL;\r
 385 \r
 386         _ASSERT_EXPR(_Pnode != NULL && _Nextnode(_Pnode) == NULL, L"Invalid head list node");\r
 387 \r
 388         _Erase(_Pnode);\r
 389     }\r
 390 \r
 391     // Common forward list functions\r
 392 \r
 393     allocator_type get_allocator() const\r
 394     {\r
 395         return (_M_value_allocator);\r
 396     }\r
 397 \r
 398     void clear()\r
 399     {\r
 400 #if _ITERATOR_DEBUG_LEVEL == 2 /*IFSTRIP=IGN*/ \r
 401         _Orphan_ptr(*this, 0);\r
 402 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */\r
 403 \r
 404         _Nodeptr _Pnext;\r
 405         _Nodeptr _Pnode = _Myhead;\r
 406 \r
 407         _ASSERT_EXPR(_Myhead != NULL, L"Invalid head list node");\r
 408         _Pnext = _Nextnode(_Pnode);\r
 409         _Pnode->_M_next = NULL;\r
 410         _Pnode = _Pnext;\r
 411 \r
 412         while (_Pnode != NULL)\r
 413         {\r
 414             _Pnext = _Nextnode(_Pnode);\r
 415             _Erase(_Pnode);\r
 416             _Pnode = _Pnext;\r
 417         }\r
 418 \r
 419         _M_element_count = 0;\r
 420     }\r
 421 \r
 422     // Returns a first non-dummy element in the SOL\r
 423     iterator begin()\r
 424     {\r
 425         _Full_iterator _Iterator = _Begin();\r
 426         return _Get_first_real_iterator(_Iterator);\r
 427     }\r
 428 \r
 429     // Returns a first non-dummy element in the SOL\r
 430     const_iterator begin() const\r
 431     {\r
 432         _Full_const_iterator _Iterator = _Begin();\r
 433         return _Get_first_real_iterator(_Iterator);\r
 434     }\r
 435 \r
 436     iterator end()\r
 437     {\r
 438         return (iterator(0, this));\r
 439     }\r
 440 \r
 441     const_iterator end() const\r
 442     {\r
 443         return (const_iterator(0, this));\r
 444     }\r
 445 \r
 446     const_iterator cbegin() const\r
 447     {\r
 448         return (((const _Mytype *)this)->begin());\r
 449     }\r
 450 \r
 451     const_iterator cend() const\r
 452     {\r
 453         return (((const _Mytype *)this)->end());\r
 454     }\r
 455 \r
 456     // Checks if the number of elements (non-dummy) is 0\r
 457     bool empty() const\r
 458     {\r
 459         return (_M_element_count == 0);\r
 460     }\r
 461 \r
 462     // Returns the number of non-dummy elements in the list\r
 463     size_type size() const\r
 464     {\r
 465         return _M_element_count;\r
 466     }\r
 467 \r
 468     // Returns the maximum size of the list, determined by the allocator\r
 469     size_type max_size() const\r
 470     {\r
 471         return _M_value_allocator.max_size();\r
 472     }\r
 473 \r
 474     // Swaps 'this' list with the passed in one\r
 475     void swap(_Mytype& _Right)\r
 476     {\r
 477         if (this == &_Right)\r
 478         {\r
 479             // Nothing to do\r
 480             return;\r
 481         }\r
 482 \r
 483         if (_M_value_allocator == _Right._M_value_allocator)\r
 484         {\r
 485             _Swap_all(_Right);\r
 486             std::swap(_Myhead, _Right._Myhead);\r
 487             std::swap(_M_element_count, _Right._M_element_count);\r
 488         }\r
 489         else\r
 490         {\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
 495         }\r
 496     }\r
 497 \r
 498     // Split-order list functions\r
 499 \r
 500     // Returns a first element in the SOL, which is always a dummy\r
 501     _Full_iterator _Begin()\r
 502     {\r
 503         return _Full_iterator(_Myhead, this);\r
 504     }\r
 505 \r
 506     // Returns a first element in the SOL, which is always a dummy\r
 507     _Full_const_iterator _Begin() const\r
 508     {\r
 509         return _Full_const_iterator(_Myhead, this);\r
 510     }\r
 511 \r
 512     _Full_iterator _End()\r
 513     {\r
 514         return _Full_iterator(0, this);\r
 515     }\r
 516 \r
 517     _Full_const_iterator _End() const\r
 518     {\r
 519         return _Full_const_iterator(0, this);\r
 520     }\r
 521 \r
 522     static _Split_order_key _Get_key(const _Full_const_iterator& _Iterator)\r
 523     {\r
 524         return _Iterator._Mynode()->_Get_order_key();\r
 525     }\r
 526 \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
 530     {\r
 531         _ASSERT_EXPR(_Iterator._Mynode() != NULL && !_Iterator._Mynode()->_Is_dummy(), L"Invalid user node (dummy)");\r
 532         return iterator(_Iterator._Mynode(), this);\r
 533     }\r
 534 \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
 538     {\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
 541     }\r
 542 \r
 543     // Returns a non-const version of the _Full_iterator\r
 544     _Full_iterator _Get_iterator(_Full_const_iterator _Iterator)\r
 545     {\r
 546         return _Full_iterator(_Iterator._Mynode(), this);\r
 547     }\r
 548 \r
 549     // Returns a non-const version of the iterator\r
 550     iterator _Get_iterator(const_iterator _Iterator)\r
 551     {\r
 552         return iterator(_Iterator._Mynode(), this);\r
 553     }\r
 554 \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
 558     {\r
 559         // Skip all dummy, internal only iterators\r
 560         while (_Iterator != _End() && _Iterator._Mynode()->_Is_dummy())\r
 561         {\r
 562             _Iterator++;\r
 563         }\r
 564 \r
 565         return iterator(_Iterator._Mynode(), this);\r
 566     }\r
 567 \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
 571     {\r
 572         // Skip all dummy, internal only iterators\r
 573         while (_Iterator != _End() && _Iterator._Mynode()->_Is_dummy())\r
 574         {\r
 575             _Iterator++;\r
 576         }\r
 577 \r
 578         return const_iterator(_Iterator._Mynode(), this);\r
 579     }\r
 580 \r
 581     // Erase an element using the allocator\r
 582     void _Erase(_Nodeptr _Delete_node)\r
 583     {\r
 584         if (!_Delete_node->_Is_dummy())\r
 585         {\r
 586             // Dummy nodes have nothing constructed, thus should not be destroyed.\r
 587             _M_node_allocator.destroy(_Delete_node);\r
 588         }\r
 589         _M_node_allocator.deallocate(_Delete_node, 1);\r
 590     }\r
 591 \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
 595     {\r
 596         _New_node->_M_next = _Current_node;\r
 597         return _Previous->_Atomic_set_next(_New_node, _Current_node);\r
 598     }\r
 599     \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
 602     {\r
 603         _Nodeptr _Inserted_node = _Insert(_Iterator._Mynode(), _List_node, _Next._Mynode());\r
 604 \r
 605         if (_Inserted_node == _List_node)\r
 606         {\r
 607             // If the insert succeeded, check that the order is correct and increment the element count\r
 608             _Check_range();\r
 609             *_New_count = _InterlockedIncrement(&_M_element_count);\r
 610             return _Pairib(iterator(_List_node, this), true);\r
 611         }\r
 612         else\r
 613         {\r
 614             return _Pairib(end(), false);\r
 615         }\r
 616     }\r
 617 \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
 620     {\r
 621         _Full_iterator _Last = _End();\r
 622         _Full_iterator _Where = _Iterator;\r
 623 \r
 624         _ASSERT_EXPR(_Where != _Last, L"Invalid head node");\r
 625 \r
 626         _Where++;\r
 627 \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
 630 \r
 631         for (;;)\r
 632         {\r
 633             _ASSERT_EXPR(_Iterator != _Last, L"Invalid head list node");\r
 634 \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
 638             {\r
 639                 _ASSERT_EXPR(_Get_key(_Iterator) < _Order_key, L"Invalid node order in the list");\r
 640 \r
 641                 // Try to insert it in the right place\r
 642                 _Nodeptr _Inserted_node = _Insert(_Iterator._Mynode(), _Dummy_node, _Where._Mynode());\r
 643 \r
 644                 if (_Inserted_node == _Dummy_node)\r
 645                 {\r
 646                     // Insertion succeeded, check the list for order violations\r
 647                     _Check_range();\r
 648                     return _Full_iterator(_Dummy_node, this);\r
 649                 }\r
 650                 else\r
 651                 {\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
 658                     _Where++;\r
 659                     continue;\r
 660                 }\r
 661             }\r
 662             else if (_Get_key(_Where) == _Order_key)\r
 663             {\r
 664                 // Another dummy node with the same value found, discard the new one.\r
 665                 _Erase(_Dummy_node);\r
 666                 return _Where;\r
 667             }\r
 668 \r
 669             // Move the iterator forward\r
 670             _Iterator = _Where;\r
 671             _Where++;\r
 672         }\r
 673 \r
 674     }\r
 675 \r
 676     // This erase function can handle both real and dummy nodes\r
 677     void _Erase(_Full_iterator _Previous, _Full_const_iterator& _Where)\r
 678     {\r
 679 #if _ITERATOR_DEBUG_LEVEL == 2 /*IFSTRIP=IGN*/ \r
 680         if (_Where._Getcont() != this || _Where._Ptr == _Myhead)\r
 681         {\r
 682             std::_DEBUG_ERROR("list erase iterator outside range");\r
 683         }\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
 689 \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
 693 \r
 694         _Erase(_Pnode);\r
 695     }\r
 696 \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
 699     {\r
 700         _Full_const_iterator _Iterator = _Where;\r
 701         _Erase(_Previous, _Iterator);\r
 702         _M_element_count--;\r
 703 \r
 704         return _Get_iterator(_Get_first_real_iterator(_Iterator));\r
 705     }\r
 706 \r
 707     // Move all elements from the passed in split-ordered list to this one\r
 708     void _Move_all(_Mytype& _Source_list)\r
 709     {\r
 710         _Full_const_iterator _First = _Source_list._Begin();\r
 711         _Full_const_iterator _Last = _Source_list._End();\r
 712 \r
 713         if (_First == _Last)\r
 714         {\r
 715             return;\r
 716         }\r
 717 \r
 718         _Nodeptr _Previous_node = _Myhead;\r
 719         _Full_const_iterator _Begin_iterator = _First++;\r
 720 \r
 721         // Move all elements one by one, including dummy ones\r
 722         for (_Full_const_iterator _Iterator = _First; _Iterator != _Last;)\r
 723         {\r
 724             _Nodeptr _Node = _Iterator._Mynode();\r
 725 \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
 731         }\r
 732     }\r
 733 \r
 734 private:\r
 735 \r
 736     // Check the list for order violations\r
 737     void _Check_range()\r
 738     {\r
 739 #if defined (_DEBUG)\r
 740         for (_Full_iterator _Iterator = _Begin(); _Iterator != _End(); _Iterator++)\r
 741         {\r
 742             _Full_iterator _Next_iterator = _Iterator;\r
 743             _Next_iterator++;\r
 744 \r
 745             _ASSERT_EXPR(_Next_iterator == end() || _Next_iterator._Mynode()->_Get_order_key() >= _Iterator._Mynode()->_Get_order_key(), L"!!! List order inconsistency !!!");\r
 746         }\r
 747 #endif\r
 748     }\r
 749 \r
 750 #if _ITERATOR_DEBUG_LEVEL == 2 /*IFSTRIP=IGN*/ \r
 751     void _Orphan_ptr(_Mytype& _Cont, _Nodeptr _Ptr) const\r
 752     {\r
 753         std::_Lockit _Lock(_LOCK_DEBUG);\r
 754         const_iterator **_Pnext = (const_iterator **)_Cont._Getpfirst();\r
 755         if (_Pnext != 0)\r
 756         {\r
 757             while (*_Pnext != 0)\r
 758             {\r
 759                 if ((*_Pnext)->_Ptr == (_Nodeptr)&_Myhead || _Ptr != 0 && (*_Pnext)->_Ptr != _Ptr)\r
 760                 {\r
 761                     _Pnext = (const_iterator **)(*_Pnext)->_Getpnext();\r
 762                 }\r
 763                 else\r
 764                 {\r
 765                     (*_Pnext)->_Clrcont();\r
 766                     *_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();\r
 767                 }\r
 768             }\r
 769         }\r
 770     }\r
 771 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */\r
 772 \r
 773     volatile long _M_element_count; // Total item count, not counting dummy nodes\r
 774 };\r
 775 \r
 776 } // namespace details;\r
 777 } // namespace Concurrency\r