STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
concurrent_priority_queue.h
Go to the documentation of this file.
1 /***
2 * ==++==
3 *
4 * Copyright (c) Microsoft Corporation. All rights reserved.
5 * Microsoft would like to acknowledge that this concurrency data structure implementation
6 * is based on Intel's implementation in its Threading Building Blocks ("Intel Material").
7 *
8 * ==--==
9 * =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
10 *
11 * concurrent_priority_queue.h
12 *
13 * =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
14 ****/
15 
16 /*
17  Intel Material Copyright 2005-2011 Intel Corporation. All Rights Reserved.
18 */
19 
20 #pragma once
21 
22 #include <crtdefs.h>
23 #include <memory>
24 #include <iterator>
25 #include <limits>
26 #include <algorithm>
27 #include <cstring>
28 #include <vector>
29 #include <crtdbg.h>
30 #include <concrt.h>
31 
32 #if !(defined (_M_X64) || defined (_M_IX86) || defined (_M_ARM) || defined (_M_ARM64))
33  #error ERROR: Concurrency Runtime is supported only on X64, X86, ARM, and ARM64 architectures.
34 #endif /* !(defined (_M_X64) || defined (_M_IX86) || defined (_M_ARM) || defined (_M_ARM64)) */
35 
36 #if defined (_M_CEE)
37  #error ERROR: Concurrency Runtime is not supported when compiling /clr.
38 #endif /* defined (_M_CEE) */
39 
40 #pragma pack(push,_CRT_PACKING)
41 #pragma warning (push)
42 #pragma warning (disable: 4510 4512 4610) // disable warnings for compiler unable to generate constructor
43 
48 
49 namespace Concurrency
50 {
51 
52 namespace details
53 {
57  template <typename _Derived>
59  {
60  public:
61  volatile int _M_status;
62  _Derived * _M_pNext;
63 
65  _M_status(0),
66  _M_pNext(NULL)
67  {
68  }
69  };
70 
76  template < typename _Operation_type, typename _Handler_type >
78  {
79  public:
81  {
83  }
84 
86  {
87  }
88 
89  void _Initialize_handler(_Handler_type _Handler)
90  {
91  _M_handle_operations = _Handler;
92  }
93 
97  void _Execute(_Operation_type *_Op)
98  {
99  _Operation_type *_Res;
100 
101  // Insert the operation in the queue
102  do
103  {
104  _Op->_M_pNext = _Res = _M_pPending_operations;
105  } while (_InterlockedCompareExchangePointer(reinterpret_cast<void *volatile *>(&_M_pPending_operations), _Op, _Res) != _Res);
106 
107  if (_Res == NULL)
108  {
109  // This item was the first one in the list; this thread will handle the operations. Note that by the time the
110  // thread pops the list of operations to handle, there may be several operations queued up.
112  _CONCRT_ASSERT(_Op->_M_status != 0);
113  }
114  else
115  {
116  // This item was not the first one on the list; a different thread is going to handle this operation, wait for
117  // the result to be ready.
119  while (_Op->_M_status == 0)
120  {
121  _SpinWait._SpinOnce();
122  }
123  }
124  }
125 
126  private:
127  // An atomically updated list (also known as a mailbox) of pending operations
128  _Operation_type * volatile _M_pPending_operations;
129 
130  // Controls thread access to _M_handle_operations
131  volatile long _M_handler_busy;
132 
133  // The method that handles the operations
134  _Handler_type _M_handle_operations;
135 
136  // Trigger the handling of operations when the handler is free
138  {
139  _Operation_type * _POp_list;
140 
141  // Acquire the _M_handler_busy flag. Only one thread can possibly spin here at a time
143  while (_M_handler_busy == 1)
144  {
145  _SpinWait._SpinOnce();
146  }
147 
148  long _OldVal = _InterlockedExchange(&_M_handler_busy, 1);
149  _CONCRT_ASSERT(_OldVal == 0);
150 
151  // Get the list of pending operations
152  _POp_list = reinterpret_cast<_Operation_type *>(_InterlockedExchangePointer(reinterpret_cast<void * volatile *>(&_M_pPending_operations), NULL));
153 
154  // Handle all the operations
155  _M_handle_operations(_POp_list);
156 
157  // Release the handler
158  _OldVal = _InterlockedExchange(&_M_handler_busy, 0);
159  _CONCRT_ASSERT(_OldVal == 1);
160  }
161  };
162 
163 } // namespace details
164 
186 
187 template <typename _Ty, typename _Compare=std::less<_Ty>, typename _Ax = std::allocator<_Ty> >
189 {
190 public:
191 
195 
196  typedef _Ty value_type;
197 
201 
202  typedef _Ty& reference;
203 
207 
208  typedef const _Ty& const_reference;
209 
213 
214  typedef size_t size_type;
215 
219 
220  typedef _Ax allocator_type;
221 
238 
239  explicit concurrent_priority_queue(const allocator_type& _Al = allocator_type()) : _M_mark(0), _M_size(0), _M_data(_Al)
240  {
241  _M_my_aggregator._Initialize_handler(_My_functor_type(this));
242  }
243 
263 
264  explicit concurrent_priority_queue(size_type _Init_capacity, const allocator_type& _Al = allocator_type()) : _M_mark(0), _M_size(0), _M_data(_Al)
265  {
266  _M_data.reserve(_Init_capacity);
267  _M_my_aggregator._Initialize_handler(_My_functor_type(this));
268  }
269 
295 
296  template<typename _InputIterator>
297  concurrent_priority_queue(_InputIterator _Begin, _InputIterator _End, const allocator_type& _Al = allocator_type()) : _M_data(_Begin, _End, _Al)
298  {
299  // Set the mark to 0 to indicate that nothing is sorted.
300  _M_mark = 0;
301  _M_size = _M_data.size();
302  _M_my_aggregator._Initialize_handler(_My_functor_type(this));
303  _Heapify();
304  }
305 
322 
324  {
325  _M_my_aggregator._Initialize_handler(_My_functor_type(this));
326  _Heapify();
327  }
328 
348 
349  concurrent_priority_queue(const concurrent_priority_queue& _Src, const allocator_type& _Al) : _M_mark(_Src._M_mark), _M_data(_Src._M_data.begin(), _Src._M_data.end(), _Al)
350  {
351  _M_size = _M_data.size();
352  _M_my_aggregator._Initialize_handler(_My_functor_type(this));
353  _Heapify();
354  }
355 
372 
374  {
375  // Set _M_mark and _M_size for the argument to 0 because its data has been moved over to this priority queue.
376  _Src._M_mark = 0;
377  _Src._M_size = 0;
378  _M_my_aggregator._Initialize_handler(_My_functor_type(this));
379  _Heapify();
380  }
381 
401 
402  concurrent_priority_queue(concurrent_priority_queue&& _Src, const allocator_type& _Al) : _M_mark(_Src._M_mark), _M_size(_Src._M_size), _M_data(std::move(_Src._M_data), _Al)
403  {
404  // Set _M_mark and _M_size for the argument to 0 because its data has been moved over to this priority queue.
405  _Src._M_mark = 0;
406  _Src._M_size = 0;
407  _M_my_aggregator._Initialize_handler(_My_functor_type(this));
408  _Heapify();
409  }
410 
420 
422  {
423  if (this != &_Src)
424  {
425  std::vector<value_type, allocator_type>(_Src._M_data.begin(), _Src._M_data.end(), _Src._M_data.get_allocator()).swap(_M_data);
426  _M_mark = _Src._M_mark;
427  _M_size = _Src._M_size;
428  }
429  return *this;
430  }
431 
441 
443  {
444  if (this != &_Src)
445  {
446  _M_data = std::move(_Src._M_data);
447  _M_mark = _Src._M_mark;
448  _M_size = _Src._M_size;
449  // Set _M_mark and _M_size for the arguement to 0 because its data has been moved over to this priority queue.
450  _Src._M_mark = 0;
451  _Src._M_size = 0;
452  }
453  return *this;
454  }
455 
462 
463  bool empty() const
464  {
465  return (_M_size == 0);
466  }
467 
478 
479  size_type size() const
480  {
481  return _M_size;
482  }
483 
490  void push(const value_type& _Elem)
491  {
492  _Cpq_operation _Op_data(_Elem, _PUSH_OP_COPY);
493  _M_my_aggregator._Execute(&_Op_data);
494  if (_Op_data._M_status == _FAILED)
495  {
496  // Rethrow the saved exception.
498  }
499  }
500 
507  void push(value_type&& _Elem)
508  {
509  _Cpq_operation _Op_data(_Elem, _PUSH_OP_MOVE);
510  _M_my_aggregator._Execute(&_Op_data);
511  if (_Op_data._M_status == _FAILED)
512  {
513  // Rethrow the saved exception
515  }
516  }
517 
527 
528  bool try_pop(reference _Elem)
529  {
530  _Cpq_operation _Op_data(_POP_OP);
531  _Op_data._M_elem = &_Elem;
532  _M_my_aggregator._Execute(&_Op_data);
533  return (_Op_data._M_status == _SUCCEEDED);
534  }
535 
543 
544  void clear()
545  {
546  _M_data.clear();
547  _M_mark = 0;
548  _M_size = 0;
549  }
550 
557 
559  {
560  _M_data.swap(_Queue._M_data);
561  std::swap(_M_mark, _Queue._M_mark);
562  std::swap(_M_size, _Queue._M_size);
563  }
564 
571 
572  allocator_type get_allocator() const { return _M_data.get_allocator(); }
573 
574  private:
577 
579  {
580  public:
582  union
583  {
584  value_type * _M_elem;
585  size_type _M_size;
586  };
587  std::exception_ptr _M_exception_ptr;
588 
589  _Cpq_operation(const_reference _E, _Operation_type _T) :
590  _M_type(_T), _M_elem(const_cast<value_type*>(&_E)) {}
591  _Cpq_operation(value_type&& _E, _Operation_type _T) :
592  _M_type(_T), _M_elem(const_cast<value_type*>(&_E)) {}
593  _Cpq_operation(_Operation_type _T) : _M_type(_T) {}
594  };
595 
597  {
599  public:
602  void operator()(_Cpq_operation* _POp_list)
603  {
604  _M_PCpq->_M_handle_operations(_POp_list);
605  }
606  };
607 
609 
610  // Padding added to avoid false sharing
612 
613  // The point at which unsorted elements begin
614  size_type _M_mark;
615 
616  // Size of the concurrent priority queue. This is cached instead of using vector::size(), because that method is unsafe in the presence
617  // of concurrent pushes/pops.
618  volatile size_type _M_size;
619 
620  // The comparator function to determine relative priority between elements stored in the priority queue.
622 
623  // Padding added to avoid false sharing
624  char _M_padding2[64 /* CACHE_LINE_SIZE */ - sizeof(size_type) - sizeof(_Compare)];
625 
626  // Storage for the heap of elements in queue, plus unheapified elements. _M_data has the following structure:
627  //
628  // binary unheapified
629  // heap elements
630  // ____|_______|____
631  // | | |
632  // v v v
633  // [_|...|_|_|...|_| |...| ]
634  // 0 ^ ^ ^
635  // | | |__capacity
636  // | |__size
637  // |__mark
638  //
639  // Thus, _M_data stores the binary heap starting at position 0 through _M_mark-1 (it may be empty). Then there are 0 or more elements
640  // that have not yet been inserted into the heap, in positions _M_mark through size-1.
641  std::vector<value_type, allocator_type> _M_data;
642 
647  {
648  _Cpq_operation *_PTmp, *_PPop_list=NULL;
649 
650  _CONCRT_ASSERT(_M_mark == _M_data.size());
651 
652  // First pass processes all constant time operations: pushes, some pops.
653  while (_POp_list != NULL)
654  {
655  _CONCRT_ASSERT(_POp_list->_M_type != _INVALID_OP);
656  _PTmp = _POp_list;
657  _POp_list = _POp_list->_M_pNext;
658  if (_PTmp->_M_type == _PUSH_OP_COPY)
659  {
660  try
661  {
662  _M_data.push_back(*(_PTmp->_M_elem));
663  ++_M_size;
664  _InterlockedExchange((volatile long *) &_PTmp->_M_status, _SUCCEEDED);
665  }
666  catch (...)
667  {
669  _InterlockedExchange((volatile long *) &_PTmp->_M_status, _FAILED);
670  }
671  }
672  else if (_PTmp->_M_type == _PUSH_OP_MOVE)
673  {
674  try
675  {
676  _M_data.push_back(std::move(*(_PTmp->_M_elem)));
677  ++_M_size;
678  _InterlockedExchange((volatile long *) &_PTmp->_M_status, _SUCCEEDED);
679  }
680  catch (...)
681  {
683  _InterlockedExchange((volatile long *) &_PTmp->_M_status, _FAILED);
684  }
685  }
686  else
687  {
688  _CONCRT_ASSERT(_PTmp->_M_type == _POP_OP);
689  if (_M_mark < _M_size && _M_compare(_M_data[0], _M_data[_M_size - 1]))
690  {
691  // There are newly pushed elems and the last one is higher than top
692  // Because we're going to pop the last element, we can move the _M_data instead of copying it.
693  *(_PTmp->_M_elem) = std::move(_M_data[_M_size - 1]);
694  --_M_size;
695  _InterlockedExchange((volatile long *) &_PTmp->_M_status, _SUCCEEDED);
696  _M_data.pop_back();
697 
698  _CONCRT_ASSERT(_M_mark <= _M_size);
699  }
700  else
701  {
702  // No convenient item to pop; postpone
703  _PTmp->_M_pNext = _PPop_list;
704  _PPop_list = _PTmp;
705  }
706  }
707  }
708 
709  // Second pass processes pop operations.
710  while (_PPop_list != NULL)
711  {
712  _PTmp = _PPop_list;
713  _PPop_list = _PPop_list->_M_pNext;
714  _CONCRT_ASSERT(_PTmp->_M_type == _POP_OP);
715 
716  if (_M_size == 0)
717  {
718  _InterlockedExchange((volatile long *) &_PTmp->_M_status, _FAILED);
719  }
720  else
721  {
722  _CONCRT_ASSERT(_M_mark <= _M_size);
723 
724  if (_M_mark < _M_size && _M_compare(_M_data[0], _M_data[_M_size - 1]))
725  {
726  // There are newly pushed elems and the last one is higher than top.
727  // Because we're going to pop the last element, we can move the _M_data instead of copying it.
728  *(_PTmp->_M_elem) = std::move(_M_data[_M_size - 1]); // copy the _M_data
729  --_M_size;
730  _InterlockedExchange((volatile long *) &_PTmp->_M_status, _SUCCEEDED);
731  _M_data.pop_back();
732  }
733  else
734  {
735  // Extract top and push last element down heap.
736  *(_PTmp->_M_elem) = std::move(_M_data[0]); // copy the _M_data
737  --_M_size;
738  _InterlockedExchange((volatile long *) &_PTmp->_M_status, _SUCCEEDED);
739  _Reheap();
740  }
741  }
742  }
743  _CONCRT_ASSERT(_M_size == _M_data.size());
744  // _Heapify any leftover pushed elements before doing the next batch of operations.
745  if (_M_mark < _M_size)
746  {
747  _Heapify();
748  }
749  _CONCRT_ASSERT(_M_mark == _M_size);
750  }
751 
755  void _Heapify()
756  {
757  if (_M_mark == 0 && _M_size > 0)
758  {
759  _M_mark = 1;
760  }
761 
762  for (; _M_mark < _M_size; ++_M_mark)
763  {
764  // for each unheapified element under size
765  size_type _Cur_pos = _M_mark;
766  value_type _To_place = std::move(_M_data[_M_mark]);
767  do
768  { // push _To_place up the heap
769  size_type _Parent = (_Cur_pos - 1) >> 1;
770  if (!_M_compare(_M_data[_Parent], _To_place))
771  {
772  break;
773  }
774  _M_data[_Cur_pos] = std::move(_M_data[_Parent]);
775  _Cur_pos = _Parent;
776 
777  } while( _Cur_pos != 0 );
778 
779  _M_data[_Cur_pos] = std::move(_To_place);
780  }
781  }
782 
786  void _Reheap()
787  {
788  size_type _Cur_pos=0, _Child=1;
789  // Use _M_data.size() instead of _M_size throughout this function, because _M_size has already
790  // been decremented to account for the pop right before Reheap was invoked.
791  while (_Child < _M_mark)
792  {
793  size_type _Target = _Child;
794  if (_Child + 1 < _M_mark && _M_compare(_M_data[_Child], _M_data[_Child + 1]))
795  {
796  ++_Target;
797  }
798  // _Target now has the higher priority _Child.
799  if (_M_compare(_M_data[_Target], _M_data[_M_data.size() - 1]))
800  {
801  break;
802  }
803 
804  _M_data[_Cur_pos] = std::move(_M_data[_Target]);
805  _Cur_pos = _Target;
806  _Child = (_Cur_pos << 1) + 1;
807  }
808 
809  _M_data[_Cur_pos] = std::move(_M_data[_M_data.size() - 1]);
810  _M_data.pop_back();
811 
812  if (_M_mark > _M_data.size())
813  {
814  _M_mark = _M_data.size();
815  }
816  }
817 };
818 
819 } // namespace Concurrency
820 
821 namespace concurrency = ::Concurrency;
822 
823 #pragma warning (pop)
824 #pragma pack(pop)
directory_iterator end(const directory_iterator &) _NOEXCEPT
Definition: filesystem:1974
value_type * _M_elem
Definition: concurrent_priority_queue.h:584
Definition: concurrent_priority_queue.h:575
std::vector< value_type, allocator_type > _M_data
Definition: concurrent_priority_queue.h:641
allocator_type get_allocator() const
Returns a copy of the allocator used to construct the concurrent priority queue. This method is concu...
Definition: concurrent_priority_queue.h:572
#define NULL
Definition: vcruntime.h:236
An aggregator for collecting operations coming from multiple sources and executing them serially on a...
Definition: concurrent_priority_queue.h:77
~_Aggregator()
Definition: concurrent_priority_queue.h:85
_Ty & reference
A type that represents a reference to an element of the type stored in a concurrent priority queue...
Definition: concurrent_priority_queue.h:202
void swap(concurrent_priority_queue &_Queue)
Swaps the contents of two concurrent priority queues. This method is not concurrency-safe.
Definition: concurrent_priority_queue.h:558
_My_functor_type(concurrent_priority_queue< _Ty, _Compare, _Ax > *_PCpq)
Definition: concurrent_priority_queue.h:601
Definition: concurrent_priority_queue.h:578
Implements busy wait with no backoff
Definition: concrt.h:578
#define _CONCRT_ASSERT(x)
Definition: concrt.h:123
void operator()(_Cpq_operation *_POp_list)
Definition: concurrent_priority_queue.h:602
concurrent_priority_queue & operator=(const concurrent_priority_queue &_Src)
Assigns the contents of another concurrent_priority_queue object to this one. This method is not conc...
Definition: concurrent_priority_queue.h:421
void _Initialize_handler(_Handler_type _Handler)
Definition: concurrent_priority_queue.h:89
concurrent_priority_queue(concurrent_priority_queue &&_Src, const allocator_type &_Al)
Constructs a concurrent priority queue.
Definition: concurrent_priority_queue.h:402
The concurrent_priority_queue class is a container that allows multiple threads to concurrently push ...
Definition: concurrent_priority_queue.h:188
size_t size_type
A type that counts the number of elements in a concurrent priority queue.
Definition: concurrent_priority_queue.h:214
bool try_pop(reference _Elem)
Removes and returns the highest priority element from the queue if the queue is non-empty. This method is concurrency-safe.
Definition: concurrent_priority_queue.h:528
_Ty value_type
A type that represents the data type stored in a concurrent priority queue.
Definition: concurrent_priority_queue.h:196
STL namespace.
The Concurrency namespace provides classes and functions that provide access to the Concurrency Runti...
Definition: agents.h:43
Definition: concurrent_priority_queue.h:576
const _Ty & const_reference
A type that represents a const reference to an element of the type stored in a concurrent priority qu...
Definition: concurrent_priority_queue.h:208
void clear()
Erases all elements in the concurrent priority. This method is not concurrency-safe.
Definition: concurrent_priority_queue.h:544
_Cpq_operation(value_type &&_E, _Operation_type _T)
Definition: concurrent_priority_queue.h:591
Definition: concurrent_priority_queue.h:575
std::exception_ptr _M_exception_ptr
Definition: concurrent_priority_queue.h:587
bool _SpinOnce()
Spins for one time quantum,until a maximum spin is reached.
Definition: concrt.h:626
Definition: concurrent_priority_queue.h:576
const directory_iterator & begin(const directory_iterator &_Iter) _NOEXCEPT
Definition: filesystem:1968
_Cpq_operation(_Operation_type _T)
Definition: concurrent_priority_queue.h:593
_BidIt1 _Compare(_BidIt1 _Begin1, _BidIt1 _End1, _BidIt2 _Begin2, _BidIt2 _End2, const _RxTraits &_Traits, regex_constants::syntax_option_type _Sflags)
Definition: regex:4355
_Ax allocator_type
A type that represents the allocator class for the concurrent priority queue.
Definition: concurrent_priority_queue.h:220
char _M_padding1[64-sizeof(::Concurrency::details::_Aggregator< _Cpq_operation, _My_functor_type >)]
Definition: concurrent_priority_queue.h:611
concurrent_priority_queue & operator=(concurrent_priority_queue &&_Src)
Assigns the contents of another concurrent_priority_queue object to this one. This method is not conc...
Definition: concurrent_priority_queue.h:442
concurrent_priority_queue(concurrent_priority_queue &&_Src)
Constructs a concurrent priority queue.
Definition: concurrent_priority_queue.h:373
::Concurrency::details::_Aggregator< _Cpq_operation, _My_functor_type > _M_my_aggregator
Definition: concurrent_priority_queue.h:608
void _M_handle_operations(_Cpq_operation *_POp_list)
Handle a batch of operations pending on the concurrent priority queue. Only one thread can execute th...
Definition: concurrent_priority_queue.h:646
concurrent_priority_queue(const concurrent_priority_queue &_Src)
Constructs a concurrent priority queue.
Definition: concurrent_priority_queue.h:323
concurrent_priority_queue< _Ty, _Compare, _Ax > * _M_PCpq
Definition: concurrent_priority_queue.h:598
volatile long _M_handler_busy
Definition: concurrent_priority_queue.h:131
void _Execute(_Operation_type *_Op)
Place operation in list and either handle list or wait for operation to complete. ...
Definition: concurrent_priority_queue.h:97
size_type size() const
Returns the number of elements in the concurrent priority queue. This method is concurrency-safe.
Definition: concurrent_priority_queue.h:479
_Derived * _M_pNext
Definition: concurrent_priority_queue.h:62
void swap(array< _Ty, _Size > &_Left, array< _Ty, _Size > &_Right) _NOEXCEPT_OP(_NOEXCEPT_OP(_Left.swap(_Right)))
Definition: array:433
volatile size_type _M_size
Definition: concurrent_priority_queue.h:618
concurrent_priority_queue(const allocator_type &_Al=allocator_type())
Constructs a concurrent priority queue.
Definition: concurrent_priority_queue.h:239
_Operation_type _M_type
Definition: concurrent_priority_queue.h:581
const void * _Target(const _XSTD2 type_info &_Info) const _NOEXCEPT
Definition: functional:413
size_type _M_size
Definition: concurrent_priority_queue.h:585
_Aggregator()
Definition: concurrent_priority_queue.h:80
size_type _M_mark
Definition: concurrent_priority_queue.h:614
void * _InterlockedCompareExchangePointer(void *volatile *, void *, void *)
Definition: concurrent_priority_queue.h:575
void push(const value_type &_Elem)
Adds an element to the concurrent priority queue. This method is concurrency-safe.
Definition: concurrent_priority_queue.h:490
Definition: concurrent_priority_queue.h:576
void rethrow_exception(_In_ exception_ptr _Ptr)
Definition: exception:364
void _Heapify()
Merge unsorted elements into heap.
Definition: concurrent_priority_queue.h:755
_Cpq_operation(const_reference _E, _Operation_type _T)
Definition: concurrent_priority_queue.h:589
concurrent_priority_queue(size_type _Init_capacity, const allocator_type &_Al=allocator_type())
Constructs a concurrent priority queue.
Definition: concurrent_priority_queue.h:264
_Handler_type _M_handle_operations
Definition: concurrent_priority_queue.h:134
_Operation_type
Definition: concurrent_priority_queue.h:575
void push(value_type &&_Elem)
Adds an element to the concurrent priority queue. This method is concurrency-safe.
Definition: concurrent_priority_queue.h:507
char _M_padding2[64-sizeof(size_type)-sizeof(_Compare)]
Definition: concurrent_priority_queue.h:624
concurrent_priority_queue(_InputIterator _Begin, _InputIterator _End, const allocator_type &_Al=allocator_type())
Constructs a concurrent priority queue.
Definition: concurrent_priority_queue.h:297
_Aggregated_operation base class
Definition: concurrent_priority_queue.h:58
void _Reheap()
Re-_Heapify by pushing last element down the heap from the root.
Definition: concurrent_priority_queue.h:786
Definition: concurrent_priority_queue.h:575
_Operation_status
Definition: concurrent_priority_queue.h:576
void _Start_handle_operations()
Definition: concurrent_priority_queue.h:137
_Compare _M_compare
Definition: concurrent_priority_queue.h:621
concurrent_priority_queue(const concurrent_priority_queue &_Src, const allocator_type &_Al)
Constructs a concurrent priority queue.
Definition: concurrent_priority_queue.h:349
_My_functor_type()
Definition: concurrent_priority_queue.h:600
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1290
exception_ptr current_exception() _NOEXCEPT
Definition: exception:359
_Operation_type *volatile _M_pPending_operations
Definition: concurrent_priority_queue.h:128
volatile int _M_status
Definition: concurrent_priority_queue.h:61
_Aggregated_operation()
Definition: concurrent_priority_queue.h:64
bool empty() const
Tests if the concurrent priority queue is empty at the time this method is called. This method is concurrency-safe.
Definition: concurrent_priority_queue.h:463
Definition: concurrent_priority_queue.h:596