--- /dev/null
+//--------------------------------------------------------------------------\r
+// \r
+// Copyright (c) Microsoft Corporation. All rights reserved. \r
+// \r
+// File: agents_extras.h\r
+//\r
+// Implementation of various useful message blocks\r
+//\r
+//--------------------------------------------------------------------------\r
+\r
+#pragma once\r
+\r
+#include <agents.h>\r
+\r
+// bounded_buffer uses a map\r
+#include <map>\r
+#include <queue>\r
+\r
+namespace Concurrency\r
+{\r
+ /// <summary>\r
+ /// Simple queue class for storing messages.\r
+ /// </summary>\r
+ /// <typeparam name="_Type">\r
+ /// The payload type of messages stored in this queue.\r
+ /// </typeparam>\r
+ template <class _Type>\r
+ class MessageQueue\r
+ {\r
+ public:\r
+ typedef message<_Type> _Message;\r
+\r
+ /// <summary>\r
+ /// Constructs an initially empty queue.\r
+ /// </summary>\r
+ MessageQueue()\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Removes and deletes any messages remaining in the queue.\r
+ /// </summary>\r
+ ~MessageQueue() \r
+ {\r
+ _Message * _Msg = dequeue();\r
+ while (_Msg != NULL)\r
+ {\r
+ delete _Msg;\r
+ _Msg = dequeue();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Add an item to the queue.\r
+ /// </summary>\r
+ /// <param name="_Msg">\r
+ /// Message to add.\r
+ /// </param>\r
+ void enqueue(_Message *_Msg)\r
+ {\r
+ _M_queue.push(_Msg);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Dequeue an item from the head of queue.\r
+ /// </summary>\r
+ /// <returns>\r
+ /// Returns a pointer to the message found at the head of the queue.\r
+ /// </returns>\r
+ _Message * dequeue()\r
+ {\r
+ _Message * _Msg = NULL;\r
+\r
+ if (!_M_queue.empty())\r
+ {\r
+ _Msg = _M_queue.front();\r
+ _M_queue.pop();\r
+ }\r
+\r
+ return _Msg;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Return the item at the head of the queue, without dequeuing\r
+ /// </summary>\r
+ /// <returns>\r
+ /// Returns a pointer to the message found at the head of the queue.\r
+ /// </returns>\r
+ _Message * peek() const\r
+ {\r
+ _Message * _Msg = NULL;\r
+\r
+ if (!_M_queue.empty())\r
+ {\r
+ _Msg = _M_queue.front();\r
+ }\r
+\r
+ return _Msg;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the number of items currently in the queue.\r
+ /// </summary>\r
+ /// <returns>\r
+ /// Size of the queue.\r
+ /// </returns>\r
+ size_t count() const\r
+ {\r
+ return _M_queue.size();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Checks to see if specified msg id is at the head of the queue.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// Message id to check for.\r
+ /// </param>\r
+ /// <returns>\r
+ /// True if a message with specified id is at the head, false otherwise.\r
+ /// </returns>\r
+ bool is_head(const runtime_object_identity _MsgId) const\r
+ {\r
+ _Message * _Msg = peek();\r
+ if(_Msg != NULL)\r
+ {\r
+ return _Msg->msg_id() == _MsgId;\r
+ }\r
+ return false;\r
+ }\r
+\r
+ private:\r
+ \r
+ std::queue<_Message *> _M_queue;\r
+ };\r
+\r
+ /// <summary>\r
+ /// Simple queue implementation that takes into account priority\r
+ /// using the comparison operator <.\r
+ /// </summary>\r
+ /// <typeparam name="_Type">\r
+ /// The payload type of messages stored in this queue.\r
+ /// </typeparam>\r
+ template <class _Type>\r
+ class PriorityQueue\r
+ {\r
+ public:\r
+ /// <summary>\r
+ /// Constructs an initially empty queue.\r
+ /// </summary>\r
+ PriorityQueue() : _M_pHead(NULL), _M_count(0) {}\r
+\r
+ /// <summary>\r
+ /// Removes and deletes any messages remaining in the queue.\r
+ /// </summary>\r
+ ~PriorityQueue() \r
+ {\r
+ message<_Type> * _Msg = dequeue();\r
+ while (_Msg != NULL)\r
+ {\r
+ delete _Msg;\r
+ _Msg = dequeue();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Add an item to the queue, comparisons using the 'payload' field\r
+ /// will determine the location in the queue.\r
+ /// </summary>\r
+ /// <param name="_Msg">\r
+ /// Message to add.\r
+ /// </param>\r
+ /// <param name="fCanReplaceHead">\r
+ /// True if this new message can be inserted at the head.\r
+ /// </param>\r
+ void enqueue(message<_Type> *_Msg, const bool fInsertAtHead = true)\r
+ {\r
+ MessageNode *_Element = new MessageNode();\r
+ _Element->_M_pMsg = _Msg;\r
+\r
+ // Find location to insert.\r
+ MessageNode *pCurrent = _M_pHead;\r
+ MessageNode *pPrev = NULL;\r
+ if(!fInsertAtHead && pCurrent != NULL)\r
+ {\r
+ pPrev = pCurrent;\r
+ pCurrent = pCurrent->_M_pNext;\r
+ }\r
+ while(pCurrent != NULL)\r
+ {\r
+ if(_Element->_M_pMsg->payload < pCurrent->_M_pMsg->payload)\r
+ {\r
+ break;\r
+ }\r
+ pPrev = pCurrent;\r
+ pCurrent = pCurrent->_M_pNext;\r
+ }\r
+\r
+ // Insert at head.\r
+ if(pPrev == NULL)\r
+ {\r
+ _M_pHead = _Element;\r
+ }\r
+ else\r
+ {\r
+ pPrev->_M_pNext = _Element;\r
+ }\r
+\r
+ // Last item in queue.\r
+ if(pCurrent == NULL)\r
+ {\r
+ _Element->_M_pNext = NULL;\r
+ }\r
+ else\r
+ {\r
+ _Element->_M_pNext = pCurrent;\r
+ }\r
+\r
+ ++_M_count;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Dequeue an item from the head of queue.\r
+ /// </summary>\r
+ /// <returns>\r
+ /// Returns a pointer to the message found at the head of the queue.\r
+ /// </returns>\r
+ message<_Type> * dequeue()\r
+ {\r
+ if (_M_pHead == NULL) \r
+ {\r
+ return NULL;\r
+ }\r
+\r
+ MessageNode *_OldHead = _M_pHead;\r
+ message<_Type> * _Result = _OldHead->_M_pMsg;\r
+\r
+ _M_pHead = _OldHead->_M_pNext;\r
+\r
+ delete _OldHead;\r
+\r
+ if(--_M_count == 0)\r
+ {\r
+ _M_pHead = NULL;\r
+ }\r
+ return _Result;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Return the item at the head of the queue, without dequeuing\r
+ /// </summary>\r
+ /// <returns>\r
+ /// Returns a pointer to the message found at the head of the queue.\r
+ /// </returns>\r
+ message<_Type> * peek() const\r
+ {\r
+ if(_M_count != 0)\r
+ {\r
+ return _M_pHead->_M_pMsg;\r
+ }\r
+ return NULL;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the number of items currently in the queue.\r
+ /// </summary>\r
+ /// <returns>\r
+ /// Size of the queue.\r
+ /// </returns>\r
+ size_t count() const\r
+ {\r
+ return _M_count;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Checks to see if specified msg id is at the head of the queue.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// Message id to check for.\r
+ /// </param>\r
+ /// <returns>\r
+ /// True if a message with specified id is at the head, false otherwise.\r
+ /// </returns>\r
+ bool is_head(const runtime_object_identity _MsgId) const\r
+ {\r
+ if(_M_count != 0)\r
+ {\r
+ return _M_pHead->_M_pMsg->msg_id() == _MsgId;\r
+ }\r
+ return false;\r
+ }\r
+\r
+ private:\r
+ \r
+ // Used to store individual message nodes.\r
+ struct MessageNode\r
+ {\r
+ MessageNode() : _M_pMsg(NULL), _M_pNext(NULL) {}\r
+ message<_Type> * _M_pMsg;\r
+ MessageNode * _M_pNext;\r
+ };\r
+\r
+ // A pointer to the head of the queue.\r
+ MessageNode * _M_pHead;\r
+\r
+ // The number of elements presently stored in the queue.\r
+ size_t _M_count;\r
+ };\r
+ \r
+ /// <summary>\r
+ /// priority_buffer is a buffer that uses a comparison operator on the 'payload' of each message to determine\r
+ /// order when offering to targets. Besides this it acts exactly like an unbounded_buffer.\r
+ /// </summary>\r
+ /// <typeparam name="_Type">\r
+ /// The payload type of messages stored and propagated by the buffer.\r
+ /// </typeparam>\r
+ template<class _Type>\r
+ class priority_buffer : public propagator_block<multi_link_registry<ITarget<_Type>>, multi_link_registry<ISource<_Type>>>\r
+ {\r
+ public:\r
+\r
+ /// <summary>\r
+ /// Creates an priority_buffer within the default scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ priority_buffer() \r
+ {\r
+ initialize_source_and_target();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an priority_buffer within the default scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_Filter">\r
+ /// A reference to a filter function.\r
+ /// </param>\r
+ priority_buffer(filter_method const& _Filter)\r
+ {\r
+ initialize_source_and_target();\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an priority_buffer within the specified scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_PScheduler">\r
+ /// A reference to a scheduler instance.\r
+ /// </param>\r
+ priority_buffer(Scheduler& _PScheduler)\r
+ {\r
+ initialize_source_and_target(&_PScheduler);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an priority_buffer within the specified scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_PScheduler">\r
+ /// A reference to a scheduler instance.\r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A reference to a filter function.\r
+ /// </param>\r
+ priority_buffer(Scheduler& _PScheduler, filter_method const& _Filter) \r
+ {\r
+ initialize_source_and_target(&_PScheduler);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an priority_buffer within the specified schedule group. The scheduler is implied\r
+ /// by the schedule group.\r
+ /// </summary>\r
+ /// <param name="_PScheduleGroup">\r
+ /// A reference to a schedule group.\r
+ /// </param>\r
+ priority_buffer(ScheduleGroup& _PScheduleGroup)\r
+ {\r
+ initialize_source_and_target(NULL, &_PScheduleGroup);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an priority_buffer within the specified schedule group. The scheduler is implied\r
+ /// by the schedule group.\r
+ /// </summary>\r
+ /// <param name="_PScheduleGroup">\r
+ /// A reference to a schedule group.\r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A reference to a filter function.\r
+ /// </param>\r
+ priority_buffer(ScheduleGroup& _PScheduleGroup, filter_method const& _Filter)\r
+ {\r
+ initialize_source_and_target(NULL, &_PScheduleGroup);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Cleans up any resources that may have been created by the priority_buffer.\r
+ /// </summary>\r
+ ~priority_buffer()\r
+ {\r
+ // Remove all links\r
+ remove_network_links();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Add an item to the priority_buffer\r
+ /// </summary>\r
+ /// <param name="_Item">\r
+ /// A reference to the item to add.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A boolean indicating whether the data was accepted.\r
+ /// </returns>\r
+ bool enqueue(_Type const& _Item)\r
+ {\r
+ return Concurrency::send<_Type>(this, _Item);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove an item from the priority_buffer\r
+ /// </summary>\r
+ /// <returns>\r
+ /// The message payload.\r
+ /// </returns>\r
+ _Type dequeue()\r
+ {\r
+ return receive<_Type>(this);\r
+ }\r
+\r
+ protected:\r
+\r
+ /// <summary>\r
+ /// The main propagate() function for ITarget blocks. Called by a source\r
+ /// block, generally within an asynchronous task to send messages to its targets.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// A pointer to the message.\r
+ /// </param>\r
+ /// <param name="_PSource">\r
+ /// A pointer to the source block offering the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// An indication of what the target decided to do with the message.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// It is important that calls to propagate do *not* take the same lock on the\r
+ /// internal structure that is used by Consume and the LWT. Doing so could\r
+ /// result in a deadlock with the Consume call. (in the case of the priority_buffer,\r
+ /// this lock is the m_internalLock)\r
+ /// </remarks>\r
+ virtual message_status propagate_message(message<_Type> * _PMessage, ISource<_Type> * _PSource)\r
+ {\r
+ message_status _Result = accepted;\r
+ //\r
+ // Accept the message being propagated\r
+ // Note: depending on the source block propagating the message\r
+ // this may not necessarily be the same message (pMessage) first\r
+ // passed into the function.\r
+ //\r
+ _PMessage = _PSource->accept(_PMessage->msg_id(), this);\r
+\r
+ if (_PMessage != NULL)\r
+ {\r
+ async_send(_PMessage);\r
+ }\r
+ else\r
+ {\r
+ _Result = missed;\r
+ }\r
+\r
+ return _Result;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Synchronously sends a message to this block. When this function completes the message will\r
+ /// already have propagated into the block.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// A pointer to the message.\r
+ /// </param>\r
+ /// <param name="_PSource">\r
+ /// A pointer to the source block offering the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// An indication of what the target decided to do with the message.\r
+ /// </returns>\r
+ virtual message_status send_message(message<_Type> * _PMessage, ISource<_Type> * _PSource)\r
+ {\r
+ _PMessage = _PSource->accept(_PMessage->msg_id(), this);\r
+\r
+ if (_PMessage != NULL)\r
+ {\r
+ sync_send(_PMessage);\r
+ }\r
+ else\r
+ {\r
+ return missed;\r
+ }\r
+\r
+ return accepted;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Accepts an offered message by the source, transferring ownership to the caller.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A pointer to the message that the caller now has ownership of.\r
+ /// </returns>\r
+ virtual message<_Type> * accept_message(runtime_object_identity _MsgId)\r
+ {\r
+ //\r
+ // Peek at the head message in the message buffer. If the Ids match\r
+ // dequeue and transfer ownership\r
+ //\r
+ message<_Type> * _Msg = NULL;\r
+\r
+ if (_M_messageBuffer.is_head(_MsgId))\r
+ {\r
+ _Msg = _M_messageBuffer.dequeue();\r
+ }\r
+\r
+ return _Msg;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Reserves a message previously offered by the source.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A Boolean indicating whether the reservation worked or not.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After 'reserve' is called, either 'consume' or 'release' must be called.\r
+ /// </remarks>\r
+ virtual bool reserve_message(runtime_object_identity _MsgId)\r
+ {\r
+ // Allow reservation if this is the head message\r
+ return _M_messageBuffer.is_head(_MsgId);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Consumes a message that was reserved previously.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A pointer to the message that the caller now has ownership of.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// Similar to 'accept', but is always preceded by a call to 'reserve'.\r
+ /// </remarks>\r
+ virtual message<_Type> * consume_message(runtime_object_identity _MsgId)\r
+ {\r
+ // By default, accept the message\r
+ return accept_message(_MsgId);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Releases a previous message reservation.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ virtual void release_message(runtime_object_identity _MsgId)\r
+ {\r
+ // The head message is the one reserved.\r
+ if (!_M_messageBuffer.is_head(_MsgId))\r
+ {\r
+ throw message_not_found();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Resumes propagation after a reservation has been released\r
+ /// </summary>\r
+ virtual void resume_propagation()\r
+ {\r
+ // If there are any messages in the buffer, propagate them out\r
+ if (_M_messageBuffer.count() > 0)\r
+ {\r
+ async_send(NULL);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Notification that a target was linked to this source.\r
+ /// </summary>\r
+ /// <param name="_PTarget">\r
+ /// A pointer to the newly linked target.\r
+ /// </param>\r
+ virtual void link_target_notification(ITarget<_Type> * _PTarget)\r
+ {\r
+ // If the message queue is blocked due to reservation\r
+ // there is no need to do any message propagation\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+\r
+ message<_Type> * _Msg = _M_messageBuffer.peek();\r
+\r
+ if (_Msg != NULL)\r
+ {\r
+ // Propagate the head message to the new target\r
+ message_status _Status = _PTarget->propagate(_Msg, this);\r
+\r
+ if (_Status == accepted)\r
+ {\r
+ // The target accepted the message, restart propagation.\r
+ propagate_to_any_targets(NULL);\r
+ }\r
+\r
+ // If the status is anything other than accepted, then leave\r
+ // the message queue blocked.\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Takes the message and propagates it to all the targets of this priority_buffer.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// A pointer to a new message.\r
+ /// </param>\r
+ virtual void propagate_to_any_targets(message<_Type> * _PMessage)\r
+ {\r
+ // Enqueue pMessage to the internal unbounded buffer queue if it is non-NULL.\r
+ // _PMessage can be NULL if this LWT was the result of a Repropagate call\r
+ // out of a Consume or Release (where no new message is queued up, but\r
+ // everything remaining in the priority_buffer needs to be propagated out)\r
+ if (_PMessage != NULL)\r
+ {\r
+ message<_Type> *pPrevHead = _M_messageBuffer.peek();\r
+\r
+ // If a reservation is held make sure to not insert this new\r
+ // message before it.\r
+ if(_M_pReservedFor != NULL)\r
+ {\r
+ _M_messageBuffer.enqueue(_PMessage, false);\r
+ }\r
+ else\r
+ {\r
+ _M_messageBuffer.enqueue(_PMessage);\r
+ }\r
+\r
+ // If the head message didn't change, we can safely assume that\r
+ // the head message is blocked and waiting on Consume(), Release() or a new\r
+ // link_target()\r
+ if (pPrevHead != NULL && !_M_messageBuffer.is_head(pPrevHead->msg_id()))\r
+ {\r
+ return;\r
+ }\r
+ }\r
+\r
+ // Attempt to propagate messages to all the targets\r
+ _Propagate_priority_order();\r
+ }\r
+\r
+ private:\r
+\r
+ /// <summary>\r
+ /// Attempts to propagate out any messages currently in the block.\r
+ /// </summary>\r
+ void _Propagate_priority_order()\r
+ {\r
+ message<_Target_type> * _Msg = _M_messageBuffer.peek();\r
+\r
+ // If someone has reserved the _Head message, don't propagate anymore\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+\r
+ while (_Msg != NULL)\r
+ {\r
+ message_status _Status = declined;\r
+\r
+ // Always start from the first target that linked.\r
+ for (target_iterator _Iter = _M_connectedTargets.begin(); *_Iter != NULL; ++_Iter)\r
+ {\r
+ ITarget<_Target_type> * _PTarget = *_Iter;\r
+ _Status = _PTarget->propagate(_Msg, this);\r
+\r
+ // Ownership of message changed. Do not propagate this\r
+ // message to any other target.\r
+ if (_Status == accepted)\r
+ {\r
+ break;\r
+ }\r
+\r
+ // If the target just propagated to reserved this message, stop\r
+ // propagating it to others.\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ break;\r
+ }\r
+ }\r
+\r
+ // If status is anything other than accepted, then the head message\r
+ // was not propagated out. Thus, nothing after it in the queue can\r
+ // be propagated out. Cease propagation.\r
+ if (_Status != accepted)\r
+ {\r
+ break;\r
+ }\r
+\r
+ // Get the next message\r
+ _Msg = _M_messageBuffer.peek();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Priority Queue used to store messages.\r
+ /// </summary>\r
+ PriorityQueue<_Type> _M_messageBuffer;\r
+\r
+ //\r
+ // Hide assignment operator and copy constructor.\r
+ //\r
+ priority_buffer const &operator =(priority_buffer const&); // no assignment operator\r
+ priority_buffer(priority_buffer const &); // no copy constructor\r
+ };\r
+\r
+\r
+ /// <summary>\r
+ /// A bounded_buffer implementation. Once the capacity is reached it will save the offered message\r
+ /// id and postpone. Once below capacity again the bounded_buffer will try to reserve and consume\r
+ /// any of the postponed messages. Preference is given to previously offered messages before new ones.\r
+ ///\r
+ /// NOTE: this bounded_buffer implementation contains code that is very unique to this particular block. \r
+ /// Extreme caution should be taken if code is directly copy and pasted from this class. The bounded_buffer\r
+ /// implementation uses a critical_section, several interlocked operations, and additional calls to async_send.\r
+ /// These are needed to not abandon a previously saved message id. Most blocks never have to deal with this problem.\r
+ /// </summary>\r
+ /// <typeparam name="_Type">\r
+ /// The payload type of messages stored and propagated by the buffer.\r
+ /// </typeparam>\r
+ template<class _Type>\r
+ class bounded_buffer : public propagator_block<multi_link_registry<ITarget<_Type>>, multi_link_registry<ISource<_Type>>>\r
+ {\r
+ public:\r
+ /// <summary>\r
+ /// Creates an bounded_buffer within the default scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ bounded_buffer(const size_t capacity)\r
+ : _M_capacity(capacity), _M_currentSize(0)\r
+ {\r
+ initialize_source_and_target();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an bounded_buffer within the default scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_Filter">\r
+ /// A reference to a filter function.\r
+ /// </param>\r
+ bounded_buffer(const size_t capacity, filter_method const& _Filter)\r
+ : _M_capacity(capacity), _M_currentSize(0)\r
+ {\r
+ initialize_source_and_target();\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an bounded_buffer within the specified scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_PScheduler">\r
+ /// A reference to a scheduler instance.\r
+ /// </param>\r
+ bounded_buffer(const size_t capacity, Scheduler& _PScheduler)\r
+ : _M_capacity(capacity), _M_currentSize(0)\r
+ {\r
+ initialize_source_and_target(&_PScheduler);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an bounded_buffer within the specified scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_PScheduler">\r
+ /// A reference to a scheduler instance.\r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A reference to a filter function.\r
+ /// </param>\r
+ bounded_buffer(const size_t capacity, Scheduler& _PScheduler, filter_method const& _Filter) \r
+ : _M_capacity(capacity), _M_currentSize(0)\r
+ {\r
+ initialize_source_and_target(&_PScheduler);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an bounded_buffer within the specified schedule group. The scheduler is implied\r
+ /// by the schedule group.\r
+ /// </summary>\r
+ /// <param name="_PScheduleGroup">\r
+ /// A reference to a schedule group.\r
+ /// </param>\r
+ bounded_buffer(const size_t capacity, ScheduleGroup& _PScheduleGroup)\r
+ : _M_capacity(capacity), _M_currentSize(0)\r
+ {\r
+ initialize_source_and_target(NULL, &_PScheduleGroup);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an bounded_buffer within the specified schedule group. The scheduler is implied\r
+ /// by the schedule group.\r
+ /// </summary>\r
+ /// <param name="_PScheduleGroup">\r
+ /// A reference to a schedule group.\r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A reference to a filter function.\r
+ /// </param>\r
+ bounded_buffer(const size_t capacity, ScheduleGroup& _PScheduleGroup, filter_method const& _Filter)\r
+ : _M_capacity(capacity), _M_currentSize(0)\r
+ {\r
+ initialize_source_and_target(NULL, &_PScheduleGroup);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Cleans up any resources that may have been used by the bounded_buffer.\r
+ /// </summary>\r
+ ~bounded_buffer()\r
+ {\r
+ // Remove all links\r
+ remove_network_links();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Add an item to the bounded_buffer.\r
+ /// </summary>\r
+ /// <param name="_Item">\r
+ /// A reference to the item to add.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A boolean indicating whether the data was accepted.\r
+ /// </returns>\r
+ bool enqueue(_Type const& _Item)\r
+ {\r
+ return Concurrency::send<_Type>(this, _Item);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Remove an item from the bounded_buffer.\r
+ /// </summary>\r
+ /// <returns>\r
+ /// The message payload.\r
+ /// </returns>\r
+ _Type dequeue()\r
+ {\r
+ return receive<_Type>(this);\r
+ }\r
+\r
+ protected:\r
+\r
+ /// <summary>\r
+ /// The main propagate() function for ITarget blocks. Called by a source\r
+ /// block, generally within an asynchronous task to send messages to its targets.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// A pointer to the message.\r
+ /// </param>\r
+ /// <param name="_PSource">\r
+ /// A pointer to the source block offering the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// An indication of what the target decided to do with the message.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// It is important that calls to propagate do *not* take the same lock on the\r
+ /// internal structure that is used by Consume and the LWT. Doing so could\r
+ /// result in a deadlock with the Consume call. (in the case of the bounded_buffer,\r
+ /// this lock is the m_internalLock)\r
+ /// </remarks>\r
+ virtual message_status propagate_message(message<_Type> * _PMessage, ISource<_Type> * _PSource)\r
+ {\r
+ message_status _Result = accepted;\r
+ \r
+ // Check current capacity. \r
+ if((size_t)_InterlockedIncrement(&_M_currentSize) > _M_capacity)\r
+ {\r
+ // Postpone the message, buffer is full.\r
+ _InterlockedDecrement(&_M_currentSize);\r
+ _Result = postponed;\r
+\r
+ // Save off the message id from this source to later try\r
+ // and reserve/consume when more space is free.\r
+ {\r
+ critical_section::scoped_lock scopedLock(_M_savedIdsLock);\r
+ _M_savedSourceMsgIds[_PSource] = _PMessage->msg_id();\r
+ }\r
+\r
+ async_send(NULL);\r
+ }\r
+ else\r
+ {\r
+ //\r
+ // Accept the message being propagated\r
+ // Note: depending on the source block propagating the message\r
+ // this may not necessarily be the same message (pMessage) first\r
+ // passed into the function.\r
+ //\r
+ _PMessage = _PSource->accept(_PMessage->msg_id(), this);\r
+\r
+ if (_PMessage != NULL)\r
+ {\r
+ async_send(_PMessage);\r
+ }\r
+ else\r
+ {\r
+ // Didn't get a message so need to decrement.\r
+ _InterlockedDecrement(&_M_currentSize);\r
+ _Result = missed;\r
+ async_send(NULL);\r
+ }\r
+ }\r
+\r
+ return _Result;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Synchronously sends a message to this block. When this function completes the message will\r
+ /// already have propagated into the block.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// A pointer to the message.\r
+ /// </param>\r
+ /// <param name="_PSource">\r
+ /// A pointer to the source block offering the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// An indication of what the target decided to do with the message.\r
+ /// </returns>\r
+ virtual message_status send_message(message<_Type> * _PMessage, ISource<_Type> * _PSource)\r
+ {\r
+ message_status _Result = accepted;\r
+ \r
+ // Check current capacity. \r
+ if((size_t)_InterlockedIncrement(&_M_currentSize) > _M_capacity)\r
+ {\r
+ // Postpone the message, buffer is full.\r
+ _InterlockedDecrement(&_M_currentSize);\r
+ _Result = postponed;\r
+\r
+ // Save off the message id from this source to later try\r
+ // and reserve/consume when more space is free.\r
+ {\r
+ critical_section::scoped_lock scopedLock(_M_savedIdsLock);\r
+ _M_savedSourceMsgIds[_PSource] = _PMessage->msg_id();\r
+ }\r
+\r
+ async_send(NULL);\r
+ }\r
+ else\r
+ {\r
+ //\r
+ // Accept the message being propagated\r
+ // Note: depending on the source block propagating the message\r
+ // this may not necessarily be the same message (pMessage) first\r
+ // passed into the function.\r
+ //\r
+ _PMessage = _PSource->accept(_PMessage->msg_id(), this);\r
+\r
+ if (_PMessage != NULL)\r
+ {\r
+ async_send(_PMessage);\r
+ }\r
+ else\r
+ {\r
+ // Didn't get a message so need to decrement.\r
+ _InterlockedDecrement(&_M_currentSize);\r
+ _Result = missed;\r
+ async_send(NULL);\r
+ }\r
+ }\r
+\r
+ return _Result;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Accepts an offered message by the source, transferring ownership to the caller.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A pointer to the message that the caller now has ownership of.\r
+ /// </returns>\r
+ virtual message<_Type> * accept_message(runtime_object_identity _MsgId)\r
+ {\r
+ //\r
+ // Peek at the head message in the message buffer. If the Ids match\r
+ // dequeue and transfer ownership\r
+ //\r
+ message<_Type> * _Msg = NULL;\r
+\r
+ if (_M_messageBuffer.is_head(_MsgId))\r
+ {\r
+ _Msg = _M_messageBuffer.dequeue();\r
+\r
+ // Give preference to any previously postponed messages\r
+ // before decrementing current size.\r
+ if(!try_consume_msg())\r
+ {\r
+ _InterlockedDecrement(&_M_currentSize);\r
+ }\r
+ }\r
+\r
+ return _Msg;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Try to reserve and consume a message from list of saved message ids.\r
+ /// </summary>\r
+ /// <returns>\r
+ /// True if a message was sucessfully consumed, false otherwise.\r
+ /// </returns>\r
+ bool try_consume_msg()\r
+ {\r
+ runtime_object_identity _ReservedId = -1;\r
+ ISource<_Type> * _PSource = NULL;\r
+\r
+ // Walk through source links seeing if any saved ids exist.\r
+ bool _ConsumedMsg = true;\r
+ while(_ConsumedMsg)\r
+ {\r
+ source_iterator _Iter = _M_connectedSources.begin();\r
+ {\r
+ critical_section::scoped_lock scopedLock(_M_savedIdsLock);\r
+ for (; *_Iter != NULL; ++_Iter)\r
+ {\r
+ _PSource = *_Iter;\r
+ std::map<ISource<_Type> *, runtime_object_identity>::iterator _MapIter;\r
+ if((_MapIter = _M_savedSourceMsgIds.find(_PSource)) != _M_savedSourceMsgIds.end())\r
+ {\r
+ _ReservedId = _MapIter->second;\r
+ _M_savedSourceMsgIds.erase(_MapIter);\r
+ break;\r
+ }\r
+ }\r
+ }\r
+\r
+ // Can't call into source block holding _M_savedIdsLock, that would be a recipe for disaster.\r
+ if(_ReservedId != -1)\r
+ {\r
+ if(_PSource->reserve(_ReservedId, this))\r
+ {\r
+ message<_Type> * _ConsumedMsg = _PSource->consume(_ReservedId, this);\r
+ async_send(_ConsumedMsg);\r
+ return true;\r
+ }\r
+ // Reserve failed go or link was removed, \r
+ // go back and try and find a different msg id.\r
+ else\r
+ {\r
+ continue;\r
+ }\r
+ }\r
+\r
+ // If this point is reached the map of source ids was empty.\r
+ break;\r
+ }\r
+\r
+ return false;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Reserves a message previously offered by the source.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A Boolean indicating whether the reservation worked or not.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After 'reserve' is called, either 'consume' or 'release' must be called.\r
+ /// </remarks>\r
+ virtual bool reserve_message(runtime_object_identity _MsgId)\r
+ {\r
+ // Allow reservation if this is the head message\r
+ return _M_messageBuffer.is_head(_MsgId);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Consumes a message that was reserved previously.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A pointer to the message that the caller now has ownership of.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// Similar to 'accept', but is always preceded by a call to 'reserve'.\r
+ /// </remarks>\r
+ virtual message<_Type> * consume_message(runtime_object_identity _MsgId)\r
+ {\r
+ // By default, accept the message\r
+ return accept_message(_MsgId);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Releases a previous message reservation.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ virtual void release_message(runtime_object_identity _MsgId)\r
+ {\r
+ // The head message is the one reserved.\r
+ if (!_M_messageBuffer.is_head(_MsgId))\r
+ {\r
+ throw message_not_found();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Resumes propagation after a reservation has been released\r
+ /// </summary>\r
+ virtual void resume_propagation()\r
+ {\r
+ // If there are any messages in the buffer, propagate them out\r
+ if (_M_messageBuffer.count() > 0)\r
+ {\r
+ async_send(NULL);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Notification that a target was linked to this source.\r
+ /// </summary>\r
+ /// <param name="_PTarget">\r
+ /// A pointer to the newly linked target.\r
+ /// </param>\r
+ virtual void link_target_notification(ITarget<_Type> * _PTarget)\r
+ {\r
+ // If the message queue is blocked due to reservation\r
+ // there is no need to do any message propagation\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+\r
+ message<_Type> * _Msg = _M_messageBuffer.peek();\r
+\r
+ if (_Msg != NULL)\r
+ {\r
+ // Propagate the head message to the new target\r
+ message_status _Status = _PTarget->propagate(_Msg, this);\r
+\r
+ if (_Status == accepted)\r
+ {\r
+ // The target accepted the message, restart propagation.\r
+ propagate_to_any_targets(NULL);\r
+ }\r
+\r
+ // If the status is anything other than accepted, then leave\r
+ // the message queue blocked.\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Takes the message and propagates it to all the targets of this bounded_buffer.\r
+ /// This is called from async_send.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// A pointer to a new message.\r
+ /// </param>\r
+ virtual void propagate_to_any_targets(message<_Type> * _PMessage)\r
+ {\r
+ // Enqueue pMessage to the internal message buffer if it is non-NULL.\r
+ // pMessage can be NULL if this LWT was the result of a Repropagate call\r
+ // out of a Consume or Release (where no new message is queued up, but\r
+ // everything remaining in the bounded buffer needs to be propagated out)\r
+ if (_PMessage != NULL)\r
+ {\r
+ _M_messageBuffer.enqueue(_PMessage);\r
+\r
+ // If the incoming pMessage is not the head message, we can safely assume that\r
+ // the head message is blocked and waiting on Consume(), Release() or a new\r
+ // link_target() and cannot be propagated out.\r
+ if (_M_messageBuffer.is_head(_PMessage->msg_id()))\r
+ {\r
+ _Propagate_priority_order();\r
+ }\r
+ }\r
+ else\r
+ {\r
+ // While current size is less than capacity try to consume\r
+ // any previously offered ids.\r
+ bool _ConsumedMsg = true;\r
+ while(_ConsumedMsg)\r
+ {\r
+ // Assume a message will be found to successfully consume in the\r
+ // saved ids, if not this will be decremented afterwards.\r
+ if((size_t)_InterlockedIncrement(&_M_currentSize) > _M_capacity)\r
+ {\r
+ break;\r
+ }\r
+\r
+ _ConsumedMsg = try_consume_msg();\r
+ }\r
+\r
+ // Decrement the current size, we broke out of the previous loop\r
+ // because we reached capacity or there were no more messages to consume.\r
+ _InterlockedDecrement(&_M_currentSize);\r
+ }\r
+ }\r
+\r
+ private:\r
+\r
+ /// <summary>\r
+ /// Attempts to propagate out any messages currently in the block.\r
+ /// </summary>\r
+ void _Propagate_priority_order()\r
+ {\r
+ message<_Target_type> * _Msg = _M_messageBuffer.peek();\r
+\r
+ // If someone has reserved the _Head message, don't propagate anymore\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+\r
+ while (_Msg != NULL)\r
+ {\r
+ message_status _Status = declined;\r
+\r
+ // Always start from the first target that linked.\r
+ for (target_iterator _Iter = _M_connectedTargets.begin(); *_Iter != NULL; ++_Iter)\r
+ {\r
+ ITarget<_Target_type> * _PTarget = *_Iter;\r
+ _Status = _PTarget->propagate(_Msg, this);\r
+\r
+ // Ownership of message changed. Do not propagate this\r
+ // message to any other target.\r
+ if (_Status == accepted)\r
+ {\r
+ break;\r
+ }\r
+\r
+ // If the target just propagated to reserved this message, stop\r
+ // propagating it to others.\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ break;\r
+ }\r
+ }\r
+\r
+ // If status is anything other than accepted, then the head message\r
+ // was not propagated out. Thus, nothing after it in the queue can\r
+ // be propagated out. Cease propagation.\r
+ if (_Status != accepted)\r
+ {\r
+ break;\r
+ }\r
+\r
+ // Get the next message\r
+ _Msg = _M_messageBuffer.peek();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Message buffer used to store messages.\r
+ /// </summary>\r
+ MessageQueue<_Type> _M_messageBuffer;\r
+\r
+ /// <summary>\r
+ /// Maximum number of messages bounded_buffer can hold.\r
+ /// </summary>\r
+ const size_t _M_capacity;\r
+\r
+ /// <summary>\r
+ /// Current number of messages in bounded_buffer.\r
+ /// </summary>\r
+ volatile long _M_currentSize;\r
+\r
+ /// <summary>\r
+ /// Lock used to guard saved message ids map.\r
+ /// </summary>\r
+ critical_section _M_savedIdsLock;\r
+\r
+ /// <summary>\r
+ /// Map of source links to saved message ids.\r
+ /// </summary>\r
+ std::map<ISource<_Type> *, runtime_object_identity> _M_savedSourceMsgIds;\r
+\r
+ //\r
+ // Hide assignment operator and copy constructor\r
+ //\r
+ bounded_buffer const &operator =(bounded_buffer const&); // no assignment operator\r
+ bounded_buffer(bounded_buffer const &); // no copy constructor\r
+ };\r
+\r
+ /// <summary>\r
+ /// A simple alternator, offers messages in order to each target\r
+ /// one at a time. If a consume occurs a message won't be offered to that target again\r
+ /// until all others are given a chance. This causes messages to be distributed more\r
+ /// evenly among targets.\r
+ /// </summary>\r
+ /// <typeparam name="_Type">\r
+ /// The payload type of messages stored and propagated by the buffer.\r
+ /// </typeparam>\r
+ template<class _Type>\r
+ class alternator : public propagator_block<multi_link_registry<ITarget<_Type>>, multi_link_registry<ISource<_Type>>>\r
+ {\r
+ public:\r
+ /// <summary>\r
+ /// Create an alternator within the default scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ alternator()\r
+ : _M_indexNextTarget(0)\r
+ {\r
+ initialize_source_and_target();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an alternator within the default scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_Filter">\r
+ /// A reference to a filter function.\r
+ /// </param>\r
+ alternator(filter_method const& _Filter)\r
+ : _M_indexNextTarget(0)\r
+ {\r
+ initialize_source_and_target();\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an alternator within the specified scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_PScheduler">\r
+ /// A reference to a scheduler instance.\r
+ /// </param>\r
+ alternator(Scheduler& _PScheduler)\r
+ : _M_indexNextTarget(0)\r
+ {\r
+ initialize_source_and_target(&_PScheduler);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an alternator within the specified scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_PScheduler">\r
+ /// A reference to a scheduler instance.\r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A reference to a filter function.\r
+ /// </param>\r
+ alternator(Scheduler& _PScheduler, filter_method const& _Filter) \r
+ : _M_indexNextTarget(0)\r
+ {\r
+ initialize_source_and_target(&_PScheduler);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an alternator within the specified schedule group. The scheduler is implied\r
+ /// by the schedule group.\r
+ /// </summary>\r
+ /// <param name="_PScheduleGroup">\r
+ /// A reference to a schedule group.\r
+ /// </param>\r
+ alternator(ScheduleGroup& _PScheduleGroup)\r
+ : _M_indexNextTarget(0)\r
+ {\r
+ initialize_source_and_target(NULL, &_PScheduleGroup);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Creates an alternator within the specified schedule group. The scheduler is implied\r
+ /// by the schedule group.\r
+ /// </summary>\r
+ /// <param name="_PScheduleGroup">\r
+ /// A reference to a schedule group.\r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A reference to a filter function.\r
+ /// </param>\r
+ alternator(ScheduleGroup& _PScheduleGroup, filter_method const& _Filter)\r
+ : _M_indexNextTarget(0)\r
+ {\r
+ initialize_source_and_target(NULL, &_PScheduleGroup);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Cleans up any resources that may have been created by the alternator.\r
+ /// </summary>\r
+ ~alternator()\r
+ {\r
+ // Remove all links\r
+ remove_network_links();\r
+ }\r
+\r
+ protected:\r
+\r
+ /// <summary>\r
+ /// The main propagate() function for ITarget blocks. Called by a source\r
+ /// block, generally within an asynchronous task to send messages to its targets.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// A pointer to the message\r
+ /// </param>\r
+ /// <param name="_PSource">\r
+ /// A pointer to the source block offering the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// An indication of what the target decided to do with the message.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// It is important that calls to propagate do *not* take the same lock on the\r
+ /// internal structure that is used by Consume and the LWT. Doing so could\r
+ /// result in a deadlock with the Consume call. (in the case of the alternator,\r
+ /// this lock is the m_internalLock)\r
+ /// </remarks>\r
+ virtual message_status propagate_message(message<_Type> * _PMessage, ISource<_Type> * _PSource)\r
+ {\r
+ message_status _Result = accepted;\r
+ //\r
+ // Accept the message being propagated\r
+ // Note: depending on the source block propagating the message\r
+ // this may not necessarily be the same message (pMessage) first\r
+ // passed into the function.\r
+ //\r
+ _PMessage = _PSource->accept(_PMessage->msg_id(), this);\r
+\r
+ if (_PMessage != NULL)\r
+ {\r
+ async_send(_PMessage);\r
+ }\r
+ else\r
+ {\r
+ _Result = missed;\r
+ }\r
+\r
+ return _Result;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Synchronously sends a message to this block. When this function completes the message will\r
+ /// already have propagated into the block.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// A pointer to the message.\r
+ /// </param>\r
+ /// <param name="_PSource">\r
+ /// A pointer to the source block offering the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// An indication of what the target decided to do with the message.\r
+ /// </returns>\r
+ virtual message_status send_message(message<_Type> * _PMessage, ISource<_Type> * _PSource)\r
+ {\r
+ _PMessage = _PSource->accept(_PMessage->msg_id(), this);\r
+\r
+ if (_PMessage != NULL)\r
+ {\r
+ sync_send(_PMessage);\r
+ }\r
+ else\r
+ {\r
+ return missed;\r
+ }\r
+\r
+ return accepted;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Accepts an offered message by the source, transferring ownership to the caller.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A pointer to the message that the caller now has ownership of.\r
+ /// </returns>\r
+ virtual message<_Type> * accept_message(runtime_object_identity _MsgId)\r
+ {\r
+ //\r
+ // Peek at the head message in the message buffer. If the Ids match\r
+ // dequeue and transfer ownership\r
+ //\r
+ message<_Type> * _Msg = NULL;\r
+\r
+ if (_M_messageBuffer.is_head(_MsgId))\r
+ {\r
+ _Msg = _M_messageBuffer.dequeue();\r
+ }\r
+\r
+ return _Msg;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Reserves a message previously offered by the source.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A Boolean indicating whether the reservation worked or not.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After 'reserve' is called, either 'consume' or 'release' must be called.\r
+ /// </remarks>\r
+ virtual bool reserve_message(runtime_object_identity _MsgId)\r
+ {\r
+ // Allow reservation if this is the head message\r
+ return _M_messageBuffer.is_head(_MsgId);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Consumes a message that was reserved previously.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A pointer to the message that the caller now has ownership of.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// Similar to 'accept', but is always preceded by a call to 'reserve'.\r
+ /// </remarks>\r
+ virtual message<_Type> * consume_message(runtime_object_identity _MsgId)\r
+ {\r
+ // Update so we don't offer to this target again until\r
+ // all others have a chance.\r
+ target_iterator _CurrentIter = _M_connectedTargets.begin();\r
+ for(size_t i = 0;*_CurrentIter != NULL; ++_CurrentIter, ++i) \r
+ {\r
+ if(*_CurrentIter == _M_pReservedFor)\r
+ {\r
+ _M_indexNextTarget = i + 1;\r
+ break;\r
+ }\r
+ }\r
+\r
+ // By default, accept the message\r
+ return accept_message(_MsgId);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Releases a previous message reservation.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ virtual void release_message(runtime_object_identity _MsgId)\r
+ {\r
+ // The head message is the one reserved.\r
+ if (!_M_messageBuffer.is_head(_MsgId))\r
+ {\r
+ throw message_not_found();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Resumes propagation after a reservation has been released.\r
+ /// </summary>\r
+ virtual void resume_propagation()\r
+ {\r
+ // If there are any messages in the buffer, propagate them out\r
+ if (_M_messageBuffer.count() > 0)\r
+ {\r
+ async_send(NULL);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Notification that a target was linked to this source.\r
+ /// </summary>\r
+ /// <param name="_PTarget">\r
+ /// A pointer to the newly linked target.\r
+ /// </param>\r
+ virtual void link_target_notification(ITarget<_Type> * _PTarget)\r
+ {\r
+ // If the message queue is blocked due to reservation\r
+ // there is no need to do any message propagation\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+\r
+ message<_Type> * _Msg = _M_messageBuffer.peek();\r
+\r
+ if (_Msg != NULL)\r
+ {\r
+ // Propagate the head message to the new target\r
+ message_status _Status = _PTarget->propagate(_Msg, this);\r
+\r
+ if (_Status == accepted)\r
+ {\r
+ // The target accepted the message, restart propagation.\r
+ propagate_to_any_targets(NULL);\r
+ }\r
+\r
+ // If the status is anything other than accepted, then leave\r
+ // the message queue blocked.\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Takes the message and propagates it to all the targets of this alternator.\r
+ /// This is called from async_send.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// A pointer to a new message.\r
+ /// </param>\r
+ virtual void propagate_to_any_targets(message<_Type> * _PMessage)\r
+ {\r
+ // Enqueue pMessage to the internal buffer queue if it is non-NULL.\r
+ // pMessage can be NULL if this LWT was the result of a Repropagate call\r
+ // out of a Consume or Release (where no new message is queued up, but\r
+ // everything remaining in the unbounded buffer needs to be propagated out)\r
+ if (_PMessage != NULL)\r
+ {\r
+ _M_messageBuffer.enqueue(_PMessage);\r
+\r
+ // If the incoming pMessage is not the head message, we can safely assume that\r
+ // the head message is blocked and waiting on Consume(), Release() or a new\r
+ // link_target()\r
+ if (!_M_messageBuffer.is_head(_PMessage->msg_id()))\r
+ {\r
+ return;\r
+ }\r
+ }\r
+\r
+ // Attempt to propagate messages to targets in order last left off.\r
+ _Propagate_alternating_order();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Offers messages to targets in alternating order to help distribute messages\r
+ /// evenly among targets.\r
+ /// </summary>\r
+ void _Propagate_alternating_order()\r
+ {\r
+ message<_Target_type> * _Msg = _M_messageBuffer.peek();\r
+\r
+ // If someone has reserved the _Head message, don't propagate anymore\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+\r
+ //\r
+ // Try to start where left off before, if the link has been removed\r
+ // or this is the first time then start at the beginning.\r
+ //\r
+ target_iterator _CurrentIter = _M_connectedTargets.begin();\r
+ const target_iterator _FirstLinkIter(_CurrentIter);\r
+ for(size_t i = 0;*_CurrentIter != NULL && i < _M_indexNextTarget; ++_CurrentIter, ++i) {}\r
+\r
+ while (_Msg != NULL)\r
+ {\r
+ message_status _Status = declined;\r
+\r
+ // Loop offering message until end of links is reached.\r
+ target_iterator _StartedIter(_CurrentIter);\r
+ for(;*_CurrentIter != NULL; ++_CurrentIter)\r
+ {\r
+ _Status = (*_CurrentIter)->propagate(_Msg, this);\r
+ ++_M_indexNextTarget;\r
+\r
+ // Ownership of message changed. Do not propagate this\r
+ // message to any other target.\r
+ if (_Status == accepted)\r
+ {\r
+ ++_CurrentIter;\r
+ break;\r
+ }\r
+\r
+ // If the target just propagated to reserved this message, stop\r
+ // propagating it to others\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+ }\r
+\r
+ // Message ownership changed go to next messages.\r
+ if (_Status == accepted)\r
+ {\r
+ continue;\r
+ }\r
+\r
+ // Try starting from the beginning until the first link offering was started at.\r
+ _M_indexNextTarget = 0;\r
+ for(_CurrentIter = _FirstLinkIter;*_CurrentIter != NULL; ++_CurrentIter)\r
+ {\r
+ // I have offered the same message to all links now so stop.\r
+ if(*_CurrentIter == *_StartedIter)\r
+ {\r
+ break;\r
+ }\r
+\r
+ _Status = (*_CurrentIter)->propagate(_Msg, this);\r
+ ++_M_indexNextTarget;\r
+\r
+ // Ownership of message changed. Do not propagate this\r
+ // message to any other target.\r
+ if (_Status == accepted)\r
+ {\r
+ ++_CurrentIter;\r
+ break;\r
+ }\r
+\r
+ // If the target just propagated to reserved this message, stop\r
+ // propagating it to others\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+ }\r
+\r
+ // If status is anything other than accepted, then the head message\r
+ // was not propagated out. Thus, nothing after it in the queue can\r
+ // be propagated out. Cease propagation.\r
+ if (_Status != accepted)\r
+ {\r
+ break;\r
+ }\r
+\r
+ // Get the next message\r
+ _Msg = _M_messageBuffer.peek();\r
+ }\r
+ }\r
+\r
+ private:\r
+\r
+ /// <summary>\r
+ /// Message queue used to store messages.\r
+ /// </summary>\r
+ MessageQueue<_Type> _M_messageBuffer;\r
+\r
+ /// <summary>\r
+ /// Index of next target to call propagate on. Used to alternate and load\r
+ /// balance message offering.\r
+ /// </summary>\r
+ size_t _M_indexNextTarget;\r
+\r
+ //\r
+ // Hide assignment operator and copy constructor.\r
+ //\r
+ alternator const &operator =(alternator const&); // no assignment operator\r
+ alternator(alternator const &); // no copy constructor\r
+ };\r
+\r
+ #include <agents.h>\r
+ \r
+ //\r
+ // Sample block that combines join and transform.\r
+ //\r
+ template<class _Input, class _Output, join_type _Jtype = non_greedy>\r
+ class join_transform : public propagator_block<single_link_registry<ITarget<_Output>>, multi_link_registry<ISource<_Input>>>\r
+ {\r
+ public:\r
+\r
+ typedef std::tr1::function<_Output(std::vector<_Input> const&)> _Transform_method;\r
+\r
+ /// <summary>\r
+ /// Create an join block within the default scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs this join will be allowed\r
+ /// </param>\r
+ join_transform(size_t _NumInputs, _Transform_method const& _Func)\r
+ : _M_messageArray(_NumInputs, 0),\r
+ _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an join block within the default scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs this join will be allowed\r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A filter method placed on this join\r
+ /// </param>\r
+ join_transform(size_t _NumInputs, _Transform_method const& _Func, filter_method const& _Filter)\r
+ : _M_messageArray(_NumInputs, 0),\r
+ _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an join block within the specified scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_Scheduler">\r
+ /// The scheduler onto which the task's message propagation will be scheduled.\r
+ /// </param>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs this join will be allowed\r
+ /// </param>\r
+ join_transform(Scheduler& _PScheduler, size_t _NumInputs, _Transform_method const& _Func)\r
+ : _M_messageArray(_NumInputs, 0),\r
+ _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs, &_PScheduler);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an join block within the specified scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_Scheduler">\r
+ /// The scheduler onto which the task's message propagation will be scheduled.\r
+ /// </param>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs this join will be allowed\r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A filter method placed on this join\r
+ /// </param>\r
+ join_transform(Scheduler& _PScheduler, size_t _NumInputs, _Transform_method const& _Func, filter_method const& _Filter)\r
+ : _M_messageArray(_NumInputs, 0),\r
+ _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs, &_PScheduler);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an join block within the specified schedule group. The scheduler is implied\r
+ /// by the schedule group.\r
+ /// </summary>\r
+ /// <param name="_PScheduleGroup">\r
+ /// The ScheduleGroup onto which the task's message propagation will be scheduled.\r
+ /// </param>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs this join will be allowed\r
+ /// </param>\r
+ join_transform(ScheduleGroup& _PScheduleGroup, size_t _NumInputs, _Transform_method const& _Func)\r
+ : _M_messageArray(_NumInputs, 0),\r
+ _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs, NULL, &_PScheduleGroup);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an join block within the specified schedule group. The scheduler is implied\r
+ /// by the schedule group.\r
+ /// </summary>\r
+ /// <param name="_PScheduleGroup">\r
+ /// The ScheduleGroup onto which the task's message propagation will be scheduled.\r
+ /// </param>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs this join will be allowed\r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A filter method placed on this join\r
+ /// </param>\r
+ join_transform(ScheduleGroup& _PScheduleGroup, size_t _NumInputs, _Transform_method const& _Func, filter_method const& _Filter)\r
+ : _M_messageArray(_NumInputs, 0),\r
+ _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs, NULL, &_PScheduleGroup);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Destroys a join\r
+ /// </summary>\r
+ ~join_transform()\r
+ {\r
+ // Remove all links that are targets of this join\r
+ remove_network_links();\r
+\r
+ delete [] _M_savedIdBuffer;\r
+ }\r
+\r
+ protected:\r
+ //\r
+ // propagator_block protected function implementations\r
+ //\r
+\r
+ /// <summary>\r
+ /// The main propagate() function for ITarget blocks. Called by a source\r
+ /// block, generally within an asynchronous task to send messages to its targets.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// The message being propagated\r
+ /// </param>\r
+ /// <param name="_PSource">\r
+ /// The source doing the propagation\r
+ /// </param>\r
+ /// <returns>\r
+ /// An indication of what the target decided to do with the message.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// It is important that calls to propagate do *not* take the same lock on the\r
+ /// internal structure that is used by Consume and the LWT. Doing so could\r
+ /// result in a deadlock with the Consume call. \r
+ /// </remarks>\r
+ message_status propagate_message(message<_Input> * _PMessage, ISource<_Input> * _PSource) \r
+ {\r
+ message_status _Ret_val = accepted;\r
+\r
+ //\r
+ // Find the slot index of this source\r
+ //\r
+ size_t _Slot = 0;\r
+ bool _Found = false;\r
+ for (source_iterator _Iter = _M_connectedSources.begin(); *_Iter != NULL; ++_Iter)\r
+ {\r
+ if (*_Iter == _PSource)\r
+ {\r
+ _Found = true;\r
+ break;\r
+ }\r
+\r
+ _Slot++;\r
+ }\r
+\r
+ if (!_Found)\r
+ {\r
+ // If this source was not found in the array, this is not a connected source\r
+ // decline the message\r
+ return declined;\r
+ }\r
+\r
+ _ASSERTE(_Slot < _M_messageArray.size());\r
+\r
+ bool fIsGreedy = (_Jtype == greedy);\r
+\r
+ if (fIsGreedy)\r
+ {\r
+ //\r
+ // Greedy type joins immediately accept the message.\r
+ //\r
+ {\r
+ critical_section::scoped_lock lockHolder(_M_propagationLock);\r
+ if (_M_messageArray[_Slot] != NULL)\r
+ {\r
+ _M_savedMessageIdArray[_Slot] = _PMessage->msg_id();\r
+ _Ret_val = postponed;\r
+ }\r
+ }\r
+\r
+ if (_Ret_val != postponed)\r
+ {\r
+ _M_messageArray[_Slot] = _PSource->accept(_PMessage->msg_id(), this);\r
+\r
+ if (_M_messageArray[_Slot] != NULL)\r
+ {\r
+ if (_InterlockedDecrementSizeT(&_M_messagesRemaining) == 0)\r
+ {\r
+ // If messages have arrived on all links, start a propagation\r
+ // of the current message\r
+ async_send(NULL);\r
+ }\r
+ }\r
+ else\r
+ {\r
+ _Ret_val = missed;\r
+ }\r
+ }\r
+ }\r
+ else\r
+ {\r
+ //\r
+ // Non-greedy type joins save the message ids until they have all arrived\r
+ //\r
+\r
+ if (_InterlockedExchange((volatile long *) &_M_savedMessageIdArray[_Slot], _PMessage->msg_id()) == -1)\r
+ {\r
+ // Decrement the message remaining count if this thread is switching \r
+ // the saved id from -1 to a valid value.\r
+ if (_InterlockedDecrementSizeT(&_M_messagesRemaining) == 0)\r
+ {\r
+ async_send(NULL);\r
+ }\r
+ }\r
+\r
+ // Always return postponed. This message will be consumed\r
+ // in the LWT\r
+ _Ret_val = postponed;\r
+ }\r
+\r
+ return _Ret_val;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Accepts an offered message by the source, transferring ownership to the caller.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A pointer to the message that the caller now has ownership of.\r
+ /// </returns>\r
+ virtual message<_Output> * accept_message(runtime_object_identity _MsgId)\r
+ {\r
+ //\r
+ // Peek at the head message in the message buffer. If the Ids match\r
+ // dequeue and transfer ownership\r
+ //\r
+ message<_Output> * _Msg = NULL;\r
+\r
+ if (_M_messageBuffer.is_head(_MsgId))\r
+ {\r
+ _Msg = _M_messageBuffer.dequeue();\r
+ }\r
+\r
+ return _Msg;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Reserves a message previously offered by the source.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A bool indicating whether the reservation worked or not\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After 'reserve' is called, either 'consume' or 'release' must be called.\r
+ /// </remarks>\r
+ virtual bool reserve_message(runtime_object_identity _MsgId)\r
+ {\r
+ // Allow reservation if this is the head message\r
+ return _M_messageBuffer.is_head(_MsgId);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Consumes a message previously offered by the source and reserved by the target, \r
+ /// transferring ownership to the caller.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A pointer to the message that the caller now has ownership of.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// Similar to 'accept', but is always preceded by a call to 'reserve'\r
+ /// </remarks>\r
+ virtual message<_Output> * consume_message(runtime_object_identity _MsgId)\r
+ {\r
+ // By default, accept the message\r
+ return accept_message(_MsgId);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Releases a previous message reservation.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ virtual void release_message(runtime_object_identity _MsgId)\r
+ {\r
+ // The head message is the one reserved.\r
+ if (!_M_messageBuffer.is_head(_MsgId))\r
+ {\r
+ throw message_not_found();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Resumes propagation after a reservation has been released\r
+ /// </summary>\r
+ virtual void resume_propagation()\r
+ {\r
+ // If there are any messages in the buffer, propagate them out\r
+ if (_M_messageBuffer.count() > 0)\r
+ {\r
+ async_send(NULL);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Notification that a target was linked to this source.\r
+ /// </summary>\r
+ /// <param name="_PTarget">\r
+ /// A pointer to the newly linked target.\r
+ /// </param>\r
+ virtual void link_target_notification(ITarget<_Output> *)\r
+ {\r
+ // If the message queue is blocked due to reservation\r
+ // there is no need to do any message propagation\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+\r
+ _Propagate_priority_order(_M_messageBuffer);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Takes the message and propagates it to all the target of this join.\r
+ /// This is called from async_send.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// The message being propagated\r
+ /// </param>\r
+ void propagate_to_any_targets(message<_Output> *) \r
+ {\r
+ message<_Output> * _Msg = NULL;\r
+ // Create a new message from the input sources\r
+ // If messagesRemaining == 0, we have a new message to create. Otherwise, this is coming from\r
+ // a consume or release from the target. In that case we don't want to create a new message.\r
+ if (_M_messagesRemaining == 0)\r
+ {\r
+ // A greedy join can immediately create the message, a non-greedy\r
+ // join must try and consume all the messages it has postponed\r
+ _Msg = _Create_new_message();\r
+ }\r
+\r
+ if (_Msg == NULL)\r
+ {\r
+ // Create message failed. This happens in non_greedy joins when the\r
+ // reserve/consumption of a postponed message failed.\r
+ _Propagate_priority_order(_M_messageBuffer);\r
+ return;\r
+ }\r
+\r
+ bool fIsGreedy = (_Jtype == greedy);\r
+\r
+ // For a greedy join, reset the number of messages remaining\r
+ // Check to see if multiple messages have been passed in on any of the links,\r
+ // and postponed. If so, try and reserve/consume them now\r
+ if (fIsGreedy)\r
+ {\r
+ // Look at the saved ids and reserve/consume any that have passed in while\r
+ // this join was waiting to complete\r
+ _ASSERTE(_M_messageArray.size() == _M_savedMessageIdArray.size());\r
+\r
+ for (size_t i = 0; i < _M_messageArray.size(); i++)\r
+ {\r
+ for(;;)\r
+ {\r
+ runtime_object_identity _Saved_id;\r
+ // Grab the current saved id value. This value could be changing from based on any\r
+ // calls of source->propagate(this). If the message id is different than what is snapped\r
+ // here, that means, the reserve below must fail. This is because reserve is trying\r
+ // to get the same source lock the propagate(this) call must be holding.\r
+ {\r
+ critical_section::scoped_lock lockHolder(_M_propagationLock);\r
+\r
+ _ASSERTE(_M_messageArray[i] != NULL);\r
+\r
+ _Saved_id = _M_savedMessageIdArray[i];\r
+\r
+ if (_Saved_id == -1)\r
+ {\r
+ _M_messageArray[i] = NULL;\r
+ break;\r
+ }\r
+ else\r
+ {\r
+ _M_savedMessageIdArray[i] = -1;\r
+ }\r
+ }\r
+\r
+ if (_Saved_id != -1)\r
+ {\r
+ source_iterator _Iter = _M_connectedSources.begin();\r
+ \r
+ ISource<_Input> * _PSource = _Iter[i];\r
+ if ((_PSource != NULL) && _PSource->reserve(_Saved_id, this))\r
+ {\r
+ _M_messageArray[i] = _PSource->consume(_Saved_id, this);\r
+ _InterlockedDecrementSizeT(&_M_messagesRemaining);\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ // If messages have all been received, async_send again, this will start the\r
+ // LWT up to create a new message\r
+ if (_M_messagesRemaining == 0)\r
+ {\r
+ async_send(NULL);\r
+ }\r
+ }\r
+ \r
+ // Add the new message to the outbound queue\r
+ _M_messageBuffer.enqueue(_Msg);\r
+\r
+ if (!_M_messageBuffer.is_head(_Msg->msg_id()))\r
+ {\r
+ // another message is at the head of the outbound message queue and blocked\r
+ // simply return\r
+ return;\r
+ }\r
+\r
+ _Propagate_priority_order(_M_messageBuffer);\r
+ }\r
+\r
+ private:\r
+\r
+ //\r
+ // Private Methods\r
+ //\r
+\r
+ /// <summary>\r
+ /// Propagate messages in priority order\r
+ /// </summary>\r
+ /// <param name="_MessageBuffer">\r
+ /// Reference to a message queue with messages to be propagated\r
+ /// </param>\r
+ void _Propagate_priority_order(MessageQueue<_Output> & _MessageBuffer)\r
+ {\r
+ message<_Output> * _Msg = _MessageBuffer.peek();\r
+\r
+ // If someone has reserved the _Head message, don't propagate anymore\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+\r
+ while (_Msg != NULL)\r
+ {\r
+ message_status _Status = declined;\r
+\r
+ // Always start from the first target that linked\r
+ for (target_iterator _Iter = _M_connectedTargets.begin(); *_Iter != NULL; ++_Iter)\r
+ {\r
+ ITarget<_Output> * _PTarget = *_Iter;\r
+ _Status = _PTarget->propagate(_Msg, this);\r
+\r
+ // Ownership of message changed. Do not propagate this\r
+ // message to any other target.\r
+ if (_Status == accepted)\r
+ {\r
+ break;\r
+ }\r
+\r
+ // If the target just propagated to reserved this message, stop\r
+ // propagating it to others\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ break;\r
+ }\r
+ }\r
+\r
+ // If status is anything other than accepted, then the head message\r
+ // was not propagated out. Thus, nothing after it in the queue can\r
+ // be propagated out. Cease propagation.\r
+ if (_Status != accepted)\r
+ {\r
+ break;\r
+ }\r
+\r
+ // Get the next message\r
+ _Msg = _MessageBuffer.peek();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create a new message from the data output\r
+ /// </summary>\r
+ /// <returns>\r
+ /// The created message (NULL if creation failed)\r
+ /// </returns>\r
+ message<_Output> * __cdecl _Create_new_message()\r
+ {\r
+ bool fIsNonGreedy = (_Jtype == non_greedy);\r
+\r
+ // If this is a non-greedy join, check each source and try to consume their message\r
+ if (fIsNonGreedy)\r
+ {\r
+\r
+ // The iterator _Iter below will ensure that it is safe to touch\r
+ // non-NULL source pointers. Take a snapshot.\r
+ std::vector<ISource<_Input> *> _Sources;\r
+ source_iterator _Iter = _M_connectedSources.begin();\r
+\r
+ while (*_Iter != NULL)\r
+ {\r
+ ISource<_Input> * _PSource = *_Iter;\r
+\r
+ if (_PSource == NULL)\r
+ {\r
+ break;\r
+ }\r
+\r
+ _Sources.push_back(_PSource);\r
+ ++_Iter;\r
+ }\r
+\r
+ if (_Sources.size() != _M_messageArray.size())\r
+ {\r
+ // Some of the sources were unlinked. The join is broken\r
+ return NULL;\r
+ }\r
+\r
+ // First, try and reserve all the messages. If a reservation fails,\r
+ // then release any reservations that had been made.\r
+ for (size_t i = 0; i < _M_savedMessageIdArray.size(); i++)\r
+ {\r
+ // Snap the current saved id into a buffer. This value can be changing behind the scenes from\r
+ // other source->propagate(msg, this) calls, but if so, that just means the reserve below will\r
+ // fail.\r
+ _InterlockedIncrementSizeT(&_M_messagesRemaining);\r
+ _M_savedIdBuffer[i] = _InterlockedExchange((volatile long *) &_M_savedMessageIdArray[i], -1);\r
+\r
+ _ASSERTE(_M_savedIdBuffer[i] != -1);\r
+\r
+ if (!_Sources[i]->reserve(_M_savedIdBuffer[i], this))\r
+ {\r
+ // A reservation failed, release all reservations made up until\r
+ // this block, and wait for another message to arrive on this link\r
+ for (size_t j = 0; j < i; j++)\r
+ {\r
+ _Sources[j]->release(_M_savedIdBuffer[j], this);\r
+ if (_InterlockedCompareExchange((volatile long *) &_M_savedMessageIdArray[j], _M_savedIdBuffer[j], -1) == -1)\r
+ {\r
+ if (_InterlockedDecrementSizeT(&_M_messagesRemaining) == 0)\r
+ {\r
+ async_send(NULL);\r
+ }\r
+ }\r
+ }\r
+\r
+ // Return NULL to indicate that the create failed\r
+ return NULL;\r
+ } \r
+ }\r
+\r
+ // Since everything has been reserved, consume all the messages.\r
+ // This is guaranteed to return true.\r
+ for (size_t i = 0; i < _M_messageArray.size(); i++)\r
+ {\r
+ _M_messageArray[i] = _Sources[i]->consume(_M_savedIdBuffer[i], this);\r
+ _M_savedIdBuffer[i] = -1;\r
+ }\r
+ }\r
+\r
+ if (!fIsNonGreedy)\r
+ {\r
+ // Reinitialize how many messages are being waited for.\r
+ // This is safe because all messages have been received, thus no new async_sends for\r
+ // greedy joins can be called.\r
+ _M_messagesRemaining = _M_messageArray.size();\r
+ }\r
+\r
+ std::vector<_Input> _OutputVector;\r
+ for (size_t i = 0; i < _M_messageArray.size(); i++)\r
+ {\r
+ _ASSERTE(_M_messageArray[i] != NULL);\r
+ _OutputVector.push_back(_M_messageArray[i]->payload);\r
+\r
+ delete _M_messageArray[i];\r
+ if (fIsNonGreedy)\r
+ {\r
+ _M_messageArray[i] = NULL;\r
+ }\r
+ }\r
+\r
+ _Output _Out = _M_pFunc(_OutputVector);\r
+\r
+ return (new message<_Output>(_Out));\r
+ }\r
+\r
+ /// <summary>\r
+ /// Initialize the join block\r
+ /// </summary>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs\r
+ /// </param>\r
+ void _Initialize(size_t _NumInputs, Scheduler * _PScheduler = NULL, ScheduleGroup * _PScheduleGroup = NULL)\r
+ {\r
+ initialize_source_and_target(_PScheduler, _PScheduleGroup);\r
+\r
+ _M_connectedSources.set_bound(_NumInputs);\r
+ _M_messagesRemaining = _NumInputs;\r
+\r
+ bool fIsNonGreedy = (_Jtype == non_greedy);\r
+\r
+ if (fIsNonGreedy)\r
+ {\r
+ // Non greedy joins need a buffer to snap off saved message ids to.\r
+ _M_savedIdBuffer = new runtime_object_identity[_NumInputs];\r
+ memset(_M_savedIdBuffer, -1, sizeof(runtime_object_identity) * _NumInputs);\r
+ }\r
+ else\r
+ {\r
+ _M_savedIdBuffer = NULL;\r
+ }\r
+ }\r
+\r
+ // The current number of messages remaining\r
+ volatile size_t _M_messagesRemaining;\r
+\r
+ // An array containing the accepted messages of this join.\r
+ std::vector<message<_Input>*> _M_messageArray;\r
+\r
+ // An array containing the msg ids of messages propagated to the array\r
+ // For greedy joins, this contains a log of other messages passed to this\r
+ // join after the first has been accepted\r
+ // For non-greedy joins, this contains the message id of any message \r
+ // passed to it.\r
+ std::vector<runtime_object_identity> _M_savedMessageIdArray;\r
+\r
+ // The transformer method called by this block\r
+ _Transform_method _M_pFunc;\r
+\r
+ // Buffer for snapping saved ids in non-greedy joins\r
+ runtime_object_identity * _M_savedIdBuffer;\r
+\r
+ // A lock for modifying the buffer or the connected blocks\r
+ ::Concurrency::critical_section _M_propagationLock;\r
+\r
+ // Queue to hold output messages\r
+ MessageQueue<_Output> _M_messageBuffer;\r
+ };\r
+\r
+ //\r
+ // Message block that invokes a transform method when it receives message on any of the input links.\r
+ // A typical example is recal engine for a cell in an Excel spreadsheet.\r
+ // (Remember that a normal join block is triggered only when it receives messages on all its input links).\r
+ //\r
+ template<class _Input, class _Output>\r
+ class recalculate : public propagator_block<single_link_registry<ITarget<_Output>>, multi_link_registry<ISource<_Input>>>\r
+ {\r
+ public:\r
+ typedef std::tr1::function<_Output(std::vector<_Input> const&)> _Recalculate_method;\r
+\r
+ /// <summary>\r
+ /// Create an recalculate block within the default scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs \r
+ /// </param>\r
+ recalculate(size_t _NumInputs, _Recalculate_method const& _Func)\r
+ : _M_messageArray(_NumInputs, 0), _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an recalculate block within the default scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs \r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A filter method placed on this join\r
+ /// </param>\r
+ recalculate(size_t _NumInputs, _Recalculate_method const& _Func, filter_method const& _Filter)\r
+ : _M_messageArray(_NumInputs, 0), _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an recalculate block within the specified scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_Scheduler">\r
+ /// The scheduler onto which the task's message propagation will be scheduled.\r
+ /// </param>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs \r
+ /// </param>\r
+ recalculate(size_t _NumInputs, Scheduler& _PScheduler, _Recalculate_method const& _Func)\r
+ : _M_messageArray(_NumInputs, 0), _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs, &_PScheduler);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an recalculate block within the specified scheduler, and places it any schedule\r
+ /// group of the scheduler\92s choosing.\r
+ /// </summary>\r
+ /// <param name="_Scheduler">\r
+ /// The scheduler onto which the task's message propagation will be scheduled.\r
+ /// </param>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs \r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A filter method placed on this join\r
+ /// </param>\r
+ recalculate(size_t _NumInputs, Scheduler& _PScheduler, _Recalculate_method const& _Func, filter_method const& _Filter)\r
+ : _M_messageArray(_NumInputs, 0), _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs, &_PScheduler);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an recalculate block within the specified schedule group. The scheduler is implied\r
+ /// by the schedule group.\r
+ /// </summary>\r
+ /// <param name="_PScheduleGroup">\r
+ /// The ScheduleGroup onto which the task's message propagation will be scheduled.\r
+ /// </param>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs \r
+ /// </param>\r
+ recalculate(size_t _NumInputs, ScheduleGroup& _PScheduleGroup, _Recalculate_method const& _Func)\r
+ : _M_messageArray(_NumInputs, 0), _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs, NULL, &_PScheduleGroup);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create an recalculate block within the specified schedule group. The scheduler is implied\r
+ /// by the schedule group.\r
+ /// </summary>\r
+ /// <param name="_PScheduleGroup">\r
+ /// The ScheduleGroup onto which the task's message propagation will be scheduled.\r
+ /// </param>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs \r
+ /// </param>\r
+ /// <param name="_Filter">\r
+ /// A filter method placed on this join\r
+ /// </param>\r
+ recalculate(size_t _NumInputs, ScheduleGroup& _PScheduleGroup, _Recalculate_method const& _Func, filter_method const& _Filter)\r
+ : _M_messageArray(_NumInputs, 0), _M_savedMessageIdArray(_NumInputs, -1),\r
+ _M_pFunc(_Func)\r
+ {\r
+ _Initialize(_NumInputs, NULL, &_PScheduleGroup);\r
+ register_filter(_Filter);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Destroys a join\r
+ /// </summary>\r
+ ~recalculate()\r
+ {\r
+ // Remove all links that are targets of this join\r
+ remove_network_links();\r
+\r
+ delete [] _M_savedIdBuffer;\r
+ }\r
+\r
+ protected:\r
+ //\r
+ // propagator_block protected function implementations\r
+ //\r
+\r
+ /// <summary>\r
+ /// The main propagate() function for ITarget blocks. Called by a source\r
+ /// block, generally within an asynchronous task to send messages to its targets.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// The message being propagated\r
+ /// </param>\r
+ /// <param name="_PSource">\r
+ /// The source doing the propagation\r
+ /// </param>\r
+ /// <returns>\r
+ /// An indication of what the target decided to do with the message.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// It is important that calls to propagate do *not* take the same lock on the\r
+ /// internal structure that is used by Consume and the LWT. Doing so could\r
+ /// result in a deadlock with the Consume call. \r
+ /// </remarks>\r
+ message_status propagate_message(message<_Input> * _PMessage, ISource<_Input> * _PSource) \r
+ {\r
+ //\r
+ // Find the slot index of this source\r
+ //\r
+ size_t _Slot = 0;\r
+ bool _Found = false;\r
+ for (source_iterator _Iter = _M_connectedSources.begin(); *_Iter != NULL; ++_Iter)\r
+ {\r
+ if (*_Iter == _PSource)\r
+ {\r
+ _Found = true;\r
+ break;\r
+ }\r
+\r
+ _Slot++;\r
+ }\r
+\r
+ if (!_Found)\r
+ {\r
+ // If this source was not found in the array, this is not a connected source\r
+ // decline the message\r
+ return declined;\r
+ }\r
+\r
+ //\r
+ // Save the message id\r
+ //\r
+ if (_InterlockedExchange((volatile long *) &_M_savedMessageIdArray[_Slot], _PMessage->msg_id()) == -1)\r
+ {\r
+ // If it is not seen by Create_message attempt a recalculate\r
+ async_send(NULL);\r
+ }\r
+\r
+ // Always return postponed. This message will be consumed\r
+ // in the LWT\r
+ return postponed;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Accepts an offered message by the source, transferring ownership to the caller.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A pointer to the message that the caller now has ownership of.\r
+ /// </returns>\r
+ virtual message<_Output> * accept_message(runtime_object_identity _MsgId)\r
+ {\r
+ //\r
+ // Peek at the head message in the message buffer. If the Ids match\r
+ // dequeue and transfer ownership\r
+ //\r
+ message<_Output> * _Msg = NULL;\r
+\r
+ if (_M_messageBuffer.is_head(_MsgId))\r
+ {\r
+ _Msg = _M_messageBuffer.dequeue();\r
+ }\r
+\r
+ return _Msg;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Reserves a message previously offered by the source.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A bool indicating whether the reservation worked or not\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After 'reserve' is called, either 'consume' or 'release' must be called.\r
+ /// </remarks>\r
+ virtual bool reserve_message(runtime_object_identity _MsgId)\r
+ {\r
+ // Allow reservation if this is the head message\r
+ return _M_messageBuffer.is_head(_MsgId);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Consumes a message previously offered by the source and reserved by the target, \r
+ /// transferring ownership to the caller.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A pointer to the message that the caller now has ownership of.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// Similar to 'accept', but is always preceded by a call to 'reserve'\r
+ /// </remarks>\r
+ virtual message<_Output> * consume_message(runtime_object_identity _MsgId)\r
+ {\r
+ // By default, accept the message\r
+ return accept_message(_MsgId);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Releases a previous message reservation.\r
+ /// </summary>\r
+ /// <param name="_MsgId">\r
+ /// The runtime object identity of the message.\r
+ /// </param>\r
+ virtual void release_message(runtime_object_identity _MsgId)\r
+ {\r
+ // The head message is the one reserved.\r
+ if (!_M_messageBuffer.is_head(_MsgId))\r
+ {\r
+ throw message_not_found();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Resumes propagation after a reservation has been released\r
+ /// </summary>\r
+ virtual void resume_propagation()\r
+ {\r
+ // If there are any messages in the buffer, propagate them out\r
+ if (_M_messageBuffer.count() > 0)\r
+ {\r
+ async_send(NULL);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Notification that a target was linked to this source.\r
+ /// </summary>\r
+ /// <param name="_PTarget">\r
+ /// A pointer to the newly linked target.\r
+ /// </param>\r
+ virtual void link_target_notification(ITarget<_Output> *)\r
+ {\r
+ // If the message queue is blocked due to reservation\r
+ // there is no need to do any message propagation\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+\r
+ _Propagate_priority_order(_M_messageBuffer);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Takes the message and propagates it to all the target of this join.\r
+ /// This is called from async_send.\r
+ /// </summary>\r
+ /// <param name="_PMessage">\r
+ /// The message being propagated\r
+ /// </param>\r
+ void propagate_to_any_targets(message<_Output> *) \r
+ {\r
+ // Attempt to create a new message\r
+ message<_Output> * _Msg = _Create_new_message();\r
+\r
+ if (_Msg != NULL)\r
+ {\r
+ // Add the new message to the outbound queue\r
+ _M_messageBuffer.enqueue(_Msg);\r
+\r
+ if (!_M_messageBuffer.is_head(_Msg->msg_id()))\r
+ {\r
+ // another message is at the head of the outbound message queue and blocked\r
+ // simply return\r
+ return;\r
+ }\r
+ }\r
+\r
+ _Propagate_priority_order(_M_messageBuffer);\r
+ }\r
+\r
+ private:\r
+\r
+ //\r
+ // Private Methods\r
+ //\r
+\r
+ /// <summary>\r
+ /// Propagate messages in priority order\r
+ /// </summary>\r
+ /// <param name="_MessageBuffer">\r
+ /// Reference to a message queue with messages to be propagated\r
+ /// </param>\r
+ void _Propagate_priority_order(MessageQueue<_Output> & _MessageBuffer)\r
+ {\r
+ message<_Output> * _Msg = _MessageBuffer.peek();\r
+\r
+ // If someone has reserved the _Head message, don't propagate anymore\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ return;\r
+ }\r
+\r
+ while (_Msg != NULL)\r
+ {\r
+ message_status _Status = declined;\r
+\r
+ // Always start from the first target that linked\r
+ for (target_iterator _Iter = _M_connectedTargets.begin(); *_Iter != NULL; ++_Iter)\r
+ {\r
+ ITarget<_Output> * _PTarget = *_Iter;\r
+ _Status = _PTarget->propagate(_Msg, this);\r
+\r
+ // Ownership of message changed. Do not propagate this\r
+ // message to any other target.\r
+ if (_Status == accepted)\r
+ {\r
+ break;\r
+ }\r
+\r
+ // If the target just propagated to reserved this message, stop\r
+ // propagating it to others\r
+ if (_M_pReservedFor != NULL)\r
+ {\r
+ break;\r
+ }\r
+ }\r
+\r
+ // If status is anything other than accepted, then the head message\r
+ // was not propagated out. Thus, nothing after it in the queue can\r
+ // be propagated out. Cease propagation.\r
+ if (_Status != accepted)\r
+ {\r
+ break;\r
+ }\r
+\r
+ // Get the next message\r
+ _Msg = _MessageBuffer.peek();\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Create a new message from the data output\r
+ /// </summary>\r
+ /// <returns>\r
+ /// The created message (NULL if creation failed)\r
+ /// </returns>\r
+ message<_Output> * __cdecl _Create_new_message()\r
+ {\r
+ // If this is a non-greedy join, check each source and try to consume their message\r
+ size_t _NumInputs = _M_savedMessageIdArray.size();\r
+\r
+ // The iterator _Iter below will ensure that it is safe to touch\r
+ // non-NULL source pointers. Take a snapshot.\r
+ std::vector<ISource<_Input> *> _Sources;\r
+ source_iterator _Iter = _M_connectedSources.begin();\r
+\r
+ while (*_Iter != NULL)\r
+ {\r
+ ISource<_Input> * _PSource = *_Iter;\r
+\r
+ if (_PSource == NULL)\r
+ {\r
+ break;\r
+ }\r
+\r
+ _Sources.push_back(_PSource);\r
+ ++_Iter;\r
+ }\r
+\r
+ if (_Sources.size() != _NumInputs)\r
+ {\r
+ // Some of the sources were unlinked. The join is broken\r
+ return NULL;\r
+ }\r
+\r
+ // First, try and reserve all the messages. If a reservation fails,\r
+ // then release any reservations that had been made.\r
+ for (size_t i = 0; i < _M_savedMessageIdArray.size(); i++)\r
+ {\r
+ // Swap the id to -1 indicating that we have used that value for a recalculate\r
+ _M_savedIdBuffer[i] = _InterlockedExchange((volatile long *) &_M_savedMessageIdArray[i], -1);\r
+\r
+ // If the id is -1, either we have never received a message on that link or the previous message is stored\r
+ // in the message array. If it is the former we abort. \r
+ // If the id is not -1, we attempt to reserve the message. On failure we abort.\r
+ if (((_M_savedIdBuffer[i] == -1) && (_M_messageArray[i] == NULL))\r
+ || ((_M_savedIdBuffer[i] != -1) && !_Sources[i]->reserve(_M_savedIdBuffer[i], this)))\r
+ {\r
+ // Abort. Release all reservations made up until this block, \r
+ // and wait for another message to arrive.\r
+ for (size_t j = 0; j < i; j++)\r
+ {\r
+ if (_M_savedIdBuffer[j] != -1)\r
+ {\r
+ _Sources[j]->release(_M_savedIdBuffer[j], this);\r
+ _InterlockedCompareExchange((volatile long *) &_M_savedMessageIdArray[j], _M_savedIdBuffer[j], -1);\r
+ }\r
+ }\r
+\r
+ // Return NULL to indicate that the create failed\r
+ return NULL;\r
+ } \r
+ }\r
+\r
+ // Since everything has been reserved, consume all the messages.\r
+ // This is guaranteed to return true.\r
+ size_t _NewMessages = 0;\r
+ for (size_t i = 0; i < _NumInputs; i++)\r
+ {\r
+ if (_M_savedIdBuffer[i] != -1)\r
+ {\r
+ // Delete previous message since we have a new one\r
+ if (_M_messageArray[i] != NULL)\r
+ {\r
+ delete _M_messageArray[i];\r
+ }\r
+ _M_messageArray[i] = _Sources[i]->consume(_M_savedIdBuffer[i], this);\r
+ _M_savedIdBuffer[i] = -1;\r
+ _NewMessages++;\r
+ }\r
+ }\r
+\r
+ if (_NewMessages == 0)\r
+ {\r
+ // There is no need to recal if we did not consume a new message\r
+ return NULL;\r
+ }\r
+\r
+ std::vector<_Input> _OutputVector;\r
+ for (size_t i = 0; i < _NumInputs; i++)\r
+ {\r
+ _ASSERTE(_M_messageArray[i] != NULL);\r
+ _OutputVector.push_back(_M_messageArray[i]->payload);\r
+ }\r
+\r
+ _Output _Out = _M_pFunc(_OutputVector);\r
+ return (new message<_Output>(_Out));\r
+ }\r
+\r
+ /// <summary>\r
+ /// Initialize the recalculate block\r
+ /// </summary>\r
+ /// <param name="_NumInputs">\r
+ /// The number of inputs\r
+ /// </param>\r
+ void _Initialize(size_t _NumInputs, Scheduler * _PScheduler = NULL, ScheduleGroup * _PScheduleGroup = NULL)\r
+ {\r
+ initialize_source_and_target(_PScheduler, _PScheduleGroup);\r
+\r
+ _M_connectedSources.set_bound(_NumInputs);\r
+\r
+ // Non greedy joins need a buffer to snap off saved message ids to.\r
+ _M_savedIdBuffer = new runtime_object_identity[_NumInputs];\r
+ memset(_M_savedIdBuffer, -1, sizeof(runtime_object_identity) * _NumInputs);\r
+ }\r
+\r
+ // An array containing the accepted messages of this join.\r
+ std::vector<message<_Input>*> _M_messageArray;\r
+\r
+ // An array containing the msg ids of messages propagated to the array\r
+ // For non-greedy joins, this contains the message id of any message \r
+ // passed to it.\r
+ std::vector<runtime_object_identity> _M_savedMessageIdArray;\r
+\r
+ // Buffer for snapping saved ids in non-greedy joins\r
+ runtime_object_identity * _M_savedIdBuffer;\r
+\r
+ // The transformer method called by this block\r
+ _Recalculate_method _M_pFunc;\r
+\r
+ // Queue to hold output messages\r
+ MessageQueue<_Output> _M_messageBuffer;\r
+ };\r
+\r
+ //\r
+ // Container class to hold a join_transform block and keep unbounded buffers in front of each input.\r
+ //\r
+ template<class _Input, class _Output>\r
+ class buffered_join\r
+ {\r
+ typedef std::tr1::function<_Output(std::vector<_Input> const&)> _Transform_method;\r
+\r
+ public:\r
+ buffered_join(int _NumInputs, _Transform_method const& _Func): m_currentInput(0), m_numInputs(_NumInputs)\r
+ {\r
+ m_buffers = new unbounded_buffer<_Input>*[_NumInputs];\r
+ m_join = new join_transform<_Input,_Output,greedy>(_NumInputs, _Func);\r
+\r
+ for(int i = 0; i < _NumInputs; i++)\r
+ {\r
+ m_buffers[i] = new unbounded_buffer<_Input>;\r
+ m_buffers[i]->link_target(m_join);\r
+ }\r
+ }\r
+\r
+ ~buffered_join()\r
+ {\r
+ for(int i = 0; i < m_numInputs; i++)\r
+ delete m_buffers[i];\r
+ delete [] m_buffers;\r
+ delete m_join;\r
+ }\r
+\r
+ // Add input takes _PSource and connects it to the next input on this block\r
+ void add_input(ISource<_Input> * _PSource)\r
+ {\r
+ _PSource->link_target(m_buffers[m_currentInput]);\r
+ m_currentInput++;\r
+ }\r
+\r
+ // link_target links this container block to _PTarget\r
+ void link_target(ITarget<_Output> * _PTarget)\r
+ {\r
+ m_join->link_target(_PTarget);\r
+ }\r
+ private:\r
+\r
+ int m_currentInput;\r
+ int m_numInputs;\r
+ unbounded_buffer<_Input> ** m_buffers;\r
+ join_transform<_Input,_Output,greedy> * m_join;\r
+ };\r
+} // namespace Concurrency\r
--- /dev/null
+//--------------------------------------------------------------------------\r
+// \r
+// Copyright (c) Microsoft Corporation. All rights reserved. \r
+// \r
+// File: concrt_extras.h\r
+//\r
+// Implementation of ConcRT helpers\r
+//\r
+//--------------------------------------------------------------------------\r
+\r
+#pragma once\r
+\r
+#include <concrtrm.h>\r
+#include <concrt.h>\r
+\r
+namespace Concurrency\r
+{\r
+ /// <summary>\r
+ /// An RAII style wrapper around Concurrency::Context::Oversubscribe,\r
+ /// useful for annotating known blocking calls\r
+ /// </summary>\r
+ class scoped_oversubcription_token\r
+ {\r
+ public:\r
+ scoped_oversubcription_token()\r
+ {\r
+ Concurrency::Context::CurrentContext()->Oversubscribe(true);\r
+ }\r
+ ~scoped_oversubcription_token()\r
+ {\r
+ Concurrency::Context::CurrentContext()->Oversubscribe(false);\r
+ }\r
+ };\r
+}
\ No newline at end of file
--- /dev/null
+/***\r
+* ==++==\r
+*\r
+* Copyright (c) Microsoft Corporation. All rights reserved.\r
+* \r
+* ==--==\r
+* =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+\r
+*\r
+* concurrent_unordered_map.h\r
+*\r
+* =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\r
+****/\r
+#pragma once\r
+\r
+#include <utility>\r
+#include "internal_concurrent_hash.h"\r
+\r
+#if !(defined(_M_AMD64) || defined(_M_IX86))\r
+ #error ERROR: Concurrency Runtime is supported only on X64 and X86 architectures.\r
+#endif\r
+\r
+#if defined(_M_CEE)\r
+ #error ERROR: Concurrency Runtime is not supported when compiling /clr.\r
+#endif\r
+\r
+#pragma pack(push,_CRT_PACKING)\r
+\r
+namespace Concurrency\r
+{\r
+namespace details\r
+{\r
+// Template class for hash map traits\r
+template<typename _Key_type, typename _Element_type, typename _Key_comparator, typename _Allocator_type, bool _Allow_multimapping>\r
+class _Concurrent_unordered_map_traits : public std::_Container_base\r
+{\r
+public:\r
+ typedef std::pair<_Key_type, _Element_type> _Value_type;\r
+ typedef std::pair<const _Key_type, _Element_type> value_type;\r
+ typedef _Key_type key_type;\r
+ typedef _Key_comparator key_compare;\r
+\r
+ typedef typename _Allocator_type::template rebind<value_type>::other allocator_type;\r
+\r
+ enum\r
+ {\r
+ _M_allow_multimapping = _Allow_multimapping\r
+ };\r
+\r
+ _Concurrent_unordered_map_traits() : _M_comparator()\r
+ {\r
+ }\r
+\r
+ _Concurrent_unordered_map_traits(const key_compare& _Traits) : _M_comparator(_Traits)\r
+ {\r
+ }\r
+\r
+ class value_compare : public std::binary_function<value_type, value_type, bool>\r
+ {\r
+ friend class _Concurrent_unordered_map_traits<_Key_type, _Element_type, _Key_comparator, _Allocator_type, _Allow_multimapping>;\r
+\r
+ public:\r
+ bool operator()(const value_type& _Left, const value_type& _Right) const\r
+ {\r
+ return (_M_comparator(_Left.first, _Right.first));\r
+ }\r
+\r
+ value_compare(const key_compare& _Traits) : _M_comparator(_Traits)\r
+ {\r
+ }\r
+\r
+ protected:\r
+ key_compare _M_comparator; // the comparator predicate for keys\r
+ };\r
+\r
+ template<class _Type1, class _Type2>\r
+ static const _Type1& _Key_function(const std::pair<_Type1, _Type2>& _Value)\r
+ {\r
+ return (_Value.first);\r
+ }\r
+ key_compare _M_comparator; // the comparator predicate for keys\r
+};\r
+} // namespace details;\r
+\r
+/// <summary>\r
+/// The <c>concurrent_unordered_map</c> class is an concurrency-safe container that controls a varying-length sequence of \r
+/// elements of type std::pair<const _Key_type, _Element_type>. The sequence is represented in a way that enables \r
+/// concurrency-safe append, element access, iterator access and iterator traversal operations.\r
+/// </summary>\r
+/// <typeparam name="_Key_type">\r
+/// The key type.\r
+/// </typeparam>\r
+/// <typeparam name="_Element_type">\r
+/// The mapped type.\r
+/// </typeparam>\r
+/// <typeparam name="_Hasher">\r
+/// The hash function object type. This argument is optional and the default value is\r
+/// tr1::hash<</c><typeparamref name="_Key_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <typeparam name="_Key_equality">\r
+/// The equality comparison function object type. This argument is optional and the default value is\r
+/// <c>equal_to<</c><typeparamref name="_Key_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <typeparam name="_Allocator_type">\r
+/// The type that represents the stored allocator object that encapsulates details about the allocation and\r
+/// deallocation of memory for the concurrent vector. This argument is optional and the default value is\r
+/// <c>allocator<</c><typeparamref name="_Key_type"/>, <typeparamref name="_Element_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <remarks>\r
+/// For detailed information on the <c>concurrent_unordered_map</c> class, see <see cref="Parallel Containers and Objects"/>.\r
+/// </remarks>\r
+/// <seealso cref="Parallel Containers and Objects"/>\r
+/**/\r
+template <typename _Key_type, typename _Element_type, typename _Hasher = std::tr1::hash<_Key_type>, typename _Key_equality = std::equal_to<_Key_type>, typename _Allocator_type = std::allocator<std::pair<const _Key_type, _Element_type> > >\r
+class concurrent_unordered_map : public details::_Concurrent_hash< details::_Concurrent_unordered_map_traits<_Key_type, _Element_type, details::_Hash_compare<_Key_type, _Hasher, _Key_equality>, _Allocator_type, false> >\r
+{\r
+public:\r
+ // Base type definitions\r
+ typedef concurrent_unordered_map<_Key_type, _Element_type, _Hasher, _Key_equality, _Allocator_type> _Mytype;\r
+ typedef details::_Hash_compare<_Key_type, _Hasher, _Key_equality> _Mytraits;\r
+ typedef details::_Concurrent_hash< details::_Concurrent_unordered_map_traits<_Key_type, _Element_type, _Mytraits, _Allocator_type, false> > _Mybase;\r
+\r
+ // Type definitions\r
+ typedef _Key_type key_type;\r
+ typedef typename _Mybase::value_type value_type;\r
+ typedef _Element_type mapped_type;\r
+ typedef _Hasher hasher;\r
+ typedef _Key_equality key_equal;\r
+ typedef _Mytraits key_compare;\r
+\r
+ typedef typename _Mybase::allocator_type allocator_type;\r
+ typedef typename _Mybase::pointer pointer;\r
+ typedef typename _Mybase::const_pointer const_pointer;\r
+ typedef typename _Mybase::reference reference;\r
+ typedef typename _Mybase::const_reference const_reference;\r
+\r
+ typedef typename _Mybase::size_type size_type;\r
+ typedef typename _Mybase::difference_type difference_type;\r
+\r
+ typedef typename _Mybase::iterator iterator;\r
+ typedef typename _Mybase::const_iterator const_iterator;\r
+ typedef typename _Mybase::iterator local_iterator;\r
+ typedef typename _Mybase::const_iterator const_local_iterator;\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered map.\r
+ /// </summary>\r
+ /// <param name="_Number_of_buckets">\r
+ /// The initial number of buckets for this unordered map.\r
+ /// </param>\r
+ /// <param name="_Hasher">\r
+ /// The hash function for this unordered map.\r
+ /// </param>\r
+ /// <param name="_Key_equality">\r
+ /// The equality comparison function for this unordered map.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered map.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered map.\r
+ /// <para>The first constructor specifies an empty initial map and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered map.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ explicit concurrent_unordered_map(size_type _Number_of_buckets = 8, const hasher& _Hasher = hasher(), const key_equal& _Key_equality = key_equal(),\r
+ const allocator_type& _Allocator = allocator_type())\r
+ : _Mybase(_Number_of_buckets, key_compare(_Hasher, _Key_equality), _Allocator)\r
+ {\r
+ this->rehash(_Number_of_buckets);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered map.\r
+ /// </summary>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered map.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered map.\r
+ /// <para>The first constructor specifies an empty initial map and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered map.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_map(const allocator_type& _Allocator) : _Mybase(8, key_compare(), _Allocator)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered map.\r
+ /// </summary>\r
+ /// <typeparam name="_Iterator">\r
+ /// The type of the input iterator.\r
+ /// </typeparam>\r
+ /// <param name="_Begin">\r
+ /// Position of the first element in the range of elements to be copied.\r
+ /// </param>\r
+ /// <param name="_End">\r
+ /// Position of the first element beyond the range of elements to be copied.\r
+ /// </param>\r
+ /// <param name="_Number_of_buckets">\r
+ /// The initial number of buckets for this unordered map.\r
+ /// </param>\r
+ /// <param name="_Hasher">\r
+ /// The hash function for this unordered map.\r
+ /// </param>\r
+ /// <param name="_Key_equality">\r
+ /// The equality comparison function for this unordered map.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered map.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered map.\r
+ /// <para>The first constructor specifies an empty initial map and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered map.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ template <typename _Iterator>\r
+ concurrent_unordered_map(_Iterator _Begin, _Iterator _End, size_type _Number_of_buckets = 8, const hasher& _Hasher = hasher(),\r
+ const key_equal& _Key_equality = key_equal(), const allocator_type& _Allocator = allocator_type())\r
+ : _Mybase(_Number_of_buckets, key_compare(), allocator_type())\r
+ {\r
+ this->rehash(_Number_of_buckets);\r
+ for (; _Begin != _End; ++_Begin)\r
+ {\r
+ _Mybase::insert(*_Begin);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered map.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The source <c>concurrent_unordered_map</c> object to copy or move elements from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered map.\r
+ /// <para>The first constructor specifies an empty initial map and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered map.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_map(const concurrent_unordered_map& _Umap) : _Mybase(_Umap)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered map.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The source <c>concurrent_unordered_map</c> object to copy or move elements from.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered map.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered map.\r
+ /// <para>The first constructor specifies an empty initial map and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered map.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_map(const concurrent_unordered_map& _Umap, const allocator_type& _Allocator) : _Mybase(_Umap, _Allocator)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered map.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The source <c>concurrent_unordered_map</c> object to copy or move elements from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered map.\r
+ /// <para>The first constructor specifies an empty initial map and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered map.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered map <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_map(concurrent_unordered_map&& _Umap) : _Mybase(std::move(_Umap))\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Assigns the contents of another <c>concurrent_unordered_map</c> object to this one. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The source <c>concurrent_unordered_map</c> object.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A reference to this <c>concurrent_unordered_map</c> object.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After erasing any existing elements a concurrent vector, <c>operator=</c> either copies or moves the contents of <paramref name="_Umap"/> into\r
+ /// the concurrent vector.\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_map& operator=(const concurrent_unordered_map& _Umap)\r
+ {\r
+ _Mybase::operator=(_Umap);\r
+ return (*this);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Assigns the contents of another <c>concurrent_unordered_map</c> object to this one. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The source <c>concurrent_unordered_map</c> object.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A reference to this <c>concurrent_unordered_map</c> object.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After erasing any existing elements in a concurrent vector, <c>operator=</c> either copies or moves the contents of <paramref name="_Umap"/> into\r
+ /// the concurrent vector.\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_map& operator=(concurrent_unordered_map&& _Umap)\r
+ {\r
+ _Mybase::operator=(std::move(_Umap));\r
+ return (*this);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_map</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Where">\r
+ /// The iterator position to erase from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the map given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for this <c>concurrent_unordered_map</c> object.\r
+ /// </returns>\r
+ /**/\r
+ iterator unsafe_erase(const_iterator _Where)\r
+ {\r
+ return _Mybase::unsafe_erase(_Where);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_map</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key to erase.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the map given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The count of elements erased from this <c>concurrent_unordered_map</c> object.\r
+ /// </returns>\r
+ /**/\r
+ size_type unsafe_erase(const key_type& _Keyval)\r
+ {\r
+ return _Mybase::unsafe_erase(_Keyval);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_map</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Begin">\r
+ /// Position of the first element in the range of elements to be erased.\r
+ /// </param>\r
+ /// <param name="_End">\r
+ /// Position of the first element beyond the range of elements to be erased.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the map given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for this <c>concurrent_unordered_map</c> object.\r
+ /// </returns>\r
+ /**/\r
+ iterator unsafe_erase(const_iterator _Begin, const_iterator _End)\r
+ {\r
+ return _Mybase::unsafe_erase(_Begin, _End);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Swaps the contents of two <c>concurrent_unordered_map</c> objects. \r
+ /// This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The <c>concurrent_unordered_map</c> object to swap with.\r
+ /// </param>\r
+ /**/\r
+ void swap(concurrent_unordered_map& _Umap)\r
+ {\r
+ _Mybase::swap(_Umap);\r
+ }\r
+\r
+ // Observers\r
+ /// <summary>\r
+ /// The hash function object.\r
+ /// </summary>\r
+ /**/\r
+ hasher hash_function() const\r
+ {\r
+ return _M_comparator._M_hash_object;\r
+ }\r
+\r
+ /// <summary>\r
+ /// The equality comparison function object.\r
+ /// </summary>\r
+ /**/\r
+ key_equal key_eq() const\r
+ {\r
+ return _M_comparator._M_key_compare_object;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Provides access to the element at the given key in the concurrent unordered map. This method is concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key of the element to be retrieved.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A element mapped to by the key.\r
+ /// </returns>\r
+ /**/\r
+ mapped_type& operator[](const key_type& _Keyval)\r
+ {\r
+ iterator _Where = find(_Keyval);\r
+\r
+ if (_Where == end())\r
+ {\r
+ _Where = insert(std::pair<key_type, mapped_type>(std::move(_Keyval), mapped_type())).first;\r
+ }\r
+\r
+ return ((*_Where).second);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Provides access to the element at the given key in the concurrent unordered map. This method is concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key of the element to be retrieved.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A element mapped to by the key.\r
+ /// </returns>\r
+ /**/\r
+ mapped_type& at(const key_type& _Keyval)\r
+ {\r
+ iterator _Where = find(_Keyval);\r
+\r
+ if (_Where == end())\r
+ {\r
+ throw std::out_of_range("invalid concurrent_unordered_map<K, T> key");\r
+ }\r
+\r
+ return ((*_Where).second);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Provides read access to the element at the given key in the concurrent unordered map. This method is concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key of the element to be retrieved.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A element mapped to by the key.\r
+ /// </returns>\r
+ /**/\r
+ const mapped_type& at(const key_type& _Keyval) const\r
+ {\r
+ const_iterator _Where = find(_Keyval);\r
+\r
+ if (_Where == end())\r
+ {\r
+ throw std::out_of_range("invalid concurrent_unordered_map<K, T> key");\r
+ }\r
+\r
+ return ((*_Where).second);\r
+ }\r
+};\r
+\r
+/// <summary>\r
+/// The <c>concurrent_unordered_multimap</c> class is an concurrency-safe container that controls a varying-length sequence of \r
+/// elements of type std::pair<const _Key_type, _Element_type>. The sequence is represented in a way that enables \r
+/// concurrency-safe append, element access, iterator access and iterator traversal operations.\r
+/// </summary>\r
+/// <typeparam name="_Key_type">\r
+/// The key type.\r
+/// </typeparam>\r
+/// <typeparam name="_Element_type">\r
+/// The mapped type.\r
+/// </typeparam>\r
+/// <typeparam name="_Hasher">\r
+/// The hash function object type. This argument is optional and the default value is\r
+/// tr1::hash<</c><typeparamref name="_Key_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <typeparam name="_Key_equality">\r
+/// The equality comparison function object type. This argument is optional and the default value is\r
+/// <c>equal_to<</c><typeparamref name="_Key_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <typeparam name="_Allocator_type">\r
+/// The type that represents the stored allocator object that encapsulates details about the allocation and\r
+/// deallocation of memory for the concurrent vector. This argument is optional and the default value is\r
+/// <c>allocator<</c><typeparamref name="_Key_type"/>, <typeparamref name="_Element_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <remarks>\r
+/// For detailed information on the <c>concurrent_unordered_multimap</c> class, see <see cref="Parallel Containers and Objects"/>.\r
+/// </remarks>\r
+/// <seealso cref="Parallel Containers and Objects"/>\r
+/**/\r
+template <typename _Key_type, typename _Element_type, typename _Hasher = std::tr1::hash<_Key_type>, typename _Key_equality = std::equal_to<_Key_type>, typename _Allocator_type = std::allocator<std::pair<const _Key_type, _Element_type> > >\r
+class concurrent_unordered_multimap : public details::_Concurrent_hash< details::_Concurrent_unordered_map_traits<_Key_type, _Element_type, details::_Hash_compare<_Key_type, _Hasher, _Key_equality>, _Allocator_type, true> >\r
+{\r
+public:\r
+ // Base type definitions\r
+ typedef concurrent_unordered_multimap<_Key_type, _Element_type, _Hasher, _Key_equality, _Allocator_type> _Mytype;\r
+ typedef details::_Hash_compare<_Key_type, _Hasher, _Key_equality> _Mytraits;\r
+ typedef details::_Concurrent_hash< details::_Concurrent_unordered_map_traits<_Key_type, _Element_type, _Mytraits, _Allocator_type, true> > _Mybase;\r
+\r
+ // Type definitions\r
+ typedef _Key_type key_type;\r
+ typedef typename _Mybase::value_type value_type;\r
+ typedef _Element_type mapped_type;\r
+ typedef _Hasher hasher;\r
+ typedef _Key_equality key_equal;\r
+ typedef _Mytraits key_compare;\r
+\r
+ typedef typename _Mybase::allocator_type allocator_type;\r
+ typedef typename _Mybase::pointer pointer;\r
+ typedef typename _Mybase::const_pointer const_pointer;\r
+ typedef typename _Mybase::reference reference;\r
+ typedef typename _Mybase::const_reference const_reference;\r
+\r
+ typedef typename _Mybase::size_type size_type;\r
+ typedef typename _Mybase::difference_type difference_type;\r
+\r
+ typedef typename _Mybase::iterator iterator;\r
+ typedef typename _Mybase::const_iterator const_iterator;\r
+ typedef typename _Mybase::iterator local_iterator;\r
+ typedef typename _Mybase::const_iterator const_local_iterator;\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multimap.\r
+ /// </summary>\r
+ /// <param name="_Number_of_buckets">\r
+ /// The initial number of buckets for this unordered multimap.\r
+ /// </param>\r
+ /// <param name="_Hasher">\r
+ /// The hash function for this unordered multimap.\r
+ /// </param>\r
+ /// <param name="_Key_equality">\r
+ /// The equality comparison function for this unordered multimap.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered multimap.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multimap.\r
+ /// <para>The first constructor specifies an empty initial multimap and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multimap.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ explicit concurrent_unordered_multimap(size_type _Number_of_buckets = 8, const hasher& _Hasher = hasher(), const key_equal& _Key_equality = key_equal(),\r
+ const allocator_type& _Allocator = allocator_type())\r
+ : _Mybase(_Number_of_buckets, key_compare(_Hasher, _Key_equality), _Allocator)\r
+ {\r
+ this->rehash(_Number_of_buckets);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multimap.\r
+ /// </summary>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered multimap.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multimap.\r
+ /// <para>The first constructor specifies an empty initial multimap and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multimap.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multimap(const allocator_type& _Allocator) : _Mybase(8, key_compare(), _Allocator)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multimap.\r
+ /// </summary>\r
+ /// <typeparam name="_Iterator">\r
+ /// The type of the input iterator.\r
+ /// </typeparam>\r
+ /// <param name="_Begin">\r
+ /// Position of the first element in the range of elements to be copied.\r
+ /// </param>\r
+ /// <param name="_End">\r
+ /// Position of the first element beyond the range of elements to be copied.\r
+ /// </param>\r
+ /// <param name="_Number_of_buckets">\r
+ /// The initial number of buckets for this unordered multimap.\r
+ /// </param>\r
+ /// <param name="_Hasher">\r
+ /// The hash function for this unordered multimap.\r
+ /// </param>\r
+ /// <param name="_Key_equality">\r
+ /// The equality comparison function for this unordered multimap.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered multimap.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multimap.\r
+ /// <para>The first constructor specifies an empty initial multimap and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multimap.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ template <typename _Iterator>\r
+ concurrent_unordered_multimap(_Iterator _Begin, _Iterator _End, size_type _Number_of_buckets = 8, const hasher& _Hasher = hasher(),\r
+ const key_equal& _Key_equality = key_equal(), const allocator_type& _Allocator = allocator_type())\r
+ : _Mybase(_Number_of_buckets, key_compare(), allocator_type())\r
+ {\r
+ this->rehash(_Number_of_buckets);\r
+ for (; _Begin != _End; ++_Begin)\r
+ {\r
+ _Mybase::insert(*_Begin);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multimap.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The source <c>concurrent_unordered_multimap</c> object to copy elements from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multimap.\r
+ /// <para>The first constructor specifies an empty initial multimap and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multimap.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multimap(const concurrent_unordered_multimap& _Umap) : _Mybase(_Umap)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multimap.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The source <c>concurrent_unordered_multimap</c> object to copy elements from.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered multimap.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multimap.\r
+ /// <para>The first constructor specifies an empty initial multimap and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multimap.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multimap(const concurrent_unordered_multimap& _Umap, const allocator_type& _Allocator) : _Mybase(_Umap, _Allocator)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multimap.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The source <c>concurrent_unordered_multimap</c> object to copy elements from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multimap.\r
+ /// <para>The first constructor specifies an empty initial multimap and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multimap.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multimap <paramref name="_Umap"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multimap(concurrent_unordered_multimap&& _Umap) : _Mybase(std::move(_Umap))\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Assigns the contents of another <c>concurrent_unordered_multimap</c> object to this one. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The source <c>concurrent_unordered_multimap</c> object.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A reference to this <c>concurrent_unordered_multimap</c> object.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After erasing any existing elements in a concurrent unordered multimap, <c>operator=</c> either copies or moves the contents of\r
+ /// <paramref name="_Umap"/> into the concurrent unordered multimap.\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multimap& operator=(const concurrent_unordered_multimap& _Umap)\r
+ {\r
+ _Mybase::operator=(_Umap);\r
+ return (*this);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Assigns the contents of another <c>concurrent_unordered_multimap</c> object to this one. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The source <c>concurrent_unordered_multimap</c> object.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A reference to this <c>concurrent_unordered_multimap</c> object.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After erasing any existing elements in a concurrent unordered multimap, <c>operator=</c> either copies or moves the contents of\r
+ /// <paramref name="_Umap"/> into the concurrent unordered multimap.\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multimap& operator=(concurrent_unordered_multimap&& _Umap)\r
+ {\r
+ _Mybase::operator=(std::move(_Umap));\r
+ return (*this);\r
+ }\r
+\r
+ // Modifiers\r
+ /// <summary>\r
+ /// Inserts a value into the <c>concurrent_unordered_multimap</c> object. \r
+ /// </summary>\r
+ /// <param name="_Value">\r
+ /// The value to be inserted into the <c>concurrent_unordered_multimap</c> object.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function determines whether an element X exists in the sequence whose key has equivalent ordering to \r
+ /// that of _Value. If not, it creates such an element X and initializes it with _Value. The function then determines the \r
+ /// iterator where that designates X. If an insertion occurred, the function returns std::pair(where, true). Otherwise, \r
+ /// it returns std::pair(where, false).\r
+ /// <para>The second function uses the <c>const_iterator _Where</c> as a starting location to search for an insertion point</para>\r
+ /// <para>The third function inserts the sequence of element values, from the range [_First, _Last).</para>\r
+ /// <para>The last two functions behave the same as the first two, except that <paramref name="_Value"/> is used to construct the inserted value.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator pointing to the insertion location.\r
+ /// </returns>\r
+ /**/\r
+ iterator insert(const value_type& _Value)\r
+ {\r
+ return (_Mybase::insert(_Value)).first;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts a value into the <c>concurrent_unordered_multimap</c> object. \r
+ /// </summary>\r
+ /// <param name="_Where">\r
+ /// The starting location to search for an insertion point into the <c>concurrent_unordered_multimap</c> object.\r
+ /// </param>\r
+ /// <param name="_Value">\r
+ /// The value to be inserted into the <c>concurrent_unordered_multimap</c> object.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function determines whether an element X exists in the sequence whose key has equivalent ordering to \r
+ /// that of _Value. If not, it creates such an element X and initializes it with _Value. The function then determines the \r
+ /// iterator where that designates X. If an insertion occurred, the function returns std::pair(where, true). Otherwise, \r
+ /// it returns std::pair(where, false).\r
+ /// <para>The second function uses the <c>const_iterator _Where</c> as a starting location to search for an insertion point</para>\r
+ /// <para>The third function inserts the sequence of element values, from the range [_First, _Last).</para>\r
+ /// <para>The last two functions behave the same as the first two, except that <paramref name="_Value"/> is used to construct the inserted value.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for the <c>concurrent_unordered_multimap</c> object.\r
+ /// </returns>\r
+ iterator insert(const_iterator _Where, const value_type& _Value)\r
+ {\r
+ return _Mybase::insert(_Where, _Value);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts values into the <c>concurrent_unordered_multimap</c> object. \r
+ /// </summary>\r
+ /// <typeparam name="_Iterator">\r
+ /// The iterator type used for insertion.\r
+ /// </typeparm>\r
+ /// <param name="_First">\r
+ /// The starting location in an itertor of elements to insert into the <c>concurrent_unordered_multimap</c> object.\r
+ /// </param>\r
+ /// <param name="_Last">\r
+ /// The ending location in an itertor of elements to insert into the <c>concurrent_unordered_multimap</c> object.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function determines whether an element X exists in the sequence whose key has equivalent ordering to \r
+ /// that of _Value. If not, it creates such an element X and initializes it with _Value. The function then determines the \r
+ /// iterator where that designates X. If an insertion occurred, the function returns std::pair(where, true). Otherwise, \r
+ /// it returns std::pair(where, false).\r
+ /// <para>The second function uses the <c>const_iterator _Where</c> as a starting location to search for an insertion point</para>\r
+ /// <para>The third function inserts the sequence of element values, from the range [_First, _Last).</para>\r
+ /// <para>The last two functions behave the same as the first two, except that <paramref name="_Value"/> is used to construct the inserted value.</para>\r
+ /// </remarks>\r
+ template<class _Iterator>\r
+ void insert(_Iterator _First, _Iterator _Last)\r
+ {\r
+ _Mybase::insert(_First, _Last);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts a value into the <c>concurrent_unordered_multimap</c> object. \r
+ /// </summary>\r
+ /// <typeparam name="_Valty">\r
+ /// The type of the value inserted into the map.\r
+ /// </typeparm>\r
+ /// <param name="_Value">\r
+ /// The value to be inserted into the <c>concurrent_unordered_multimap</c> object.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function determines whether an element X exists in the sequence whose key has equivalent ordering to \r
+ /// that of _Value. If not, it creates such an element X and initializes it with _Value. The function then determines the \r
+ /// iterator where that designates X. If an insertion occurred, the function returns std::pair(where, true). Otherwise, \r
+ /// it returns std::pair(where, false).\r
+ /// <para>The second function uses the <c>const_iterator _Where</c> as a starting location to search for an insertion point</para>\r
+ /// <para>The third function inserts the sequence of element values, from the range [_First, _Last).</para>\r
+ /// <para>The last two functions behave the same as the first two, except that <paramref name="_Value"/> is used to construct the inserted value.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator pointing to the insertion location.\r
+ /// </returns>\r
+ /**/\r
+ template<class _Valty>\r
+ iterator insert(_Valty&& _Value)\r
+ {\r
+ return (_Mybase::insert(std::forward<_Valty>(_Value))).first;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts a value into the <c>concurrent_unordered_multimap</c> object. \r
+ /// </summary>\r
+ /// <typeparam name="_Valty">\r
+ /// The type of the value inserted into the map.\r
+ /// </typeparm>\r
+ /// <param name="_Where">\r
+ /// The starting location to search for an insertion point into the <c>concurrent_unordered_multimap</c> object.\r
+ /// </param>\r
+ /// <param name="_Value">\r
+ /// The value to be inserted into the <c>concurrent_unordered_multimap</c> object.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function determines whether an element X exists in the sequence whose key has equivalent ordering to \r
+ /// that of _Value. If not, it creates such an element X and initializes it with _Value. The function then determines the \r
+ /// iterator where that designates X. If an insertion occurred, the function returns std::pair(where, true). Otherwise, \r
+ /// it returns std::pair(where, false).\r
+ /// <para>The second function uses the <c>const_iterator _Where</c> as a starting location to search for an insertion point</para>\r
+ /// <para>The third function inserts the sequence of element values, from the range [_First, _Last).</para>\r
+ /// <para>The last two functions behave the same as the first two, except that <paramref name="_Value"/> is used to construct the inserted value.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for the <c>concurrent_unordered_multimap</c> object.\r
+ /// </returns>\r
+ template<class _Valty>\r
+ typename std::tr1::enable_if<!std::tr1::is_same<const_iterator, \r
+ typename std::tr1::remove_reference<_Valty>::type>::value, iterator>::type\r
+ insert(const_iterator _Where, _Valty&& _Value)\r
+ {\r
+ return _Mybase::insert(_Where, std::forward<_Valty>(_Value));\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_multimap</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Where">\r
+ /// The iterator position to erase from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the map given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for this <c>concurrent_unordered_multimap</c> object.\r
+ /// </returns>\r
+ /**/\r
+ iterator unsafe_erase(const_iterator _Where)\r
+ {\r
+ return _Mybase::unsafe_erase(_Where);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_multimap</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key to erase.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the map given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The count of elements erased from this <c>concurrent_unordered_multimap</c> object.\r
+ /// </returns>\r
+ /**/\r
+ size_type unsafe_erase(const key_type& _Keyval)\r
+ {\r
+ return _Mybase::unsafe_erase(_Keyval);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_multimap</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Begin">\r
+ /// Position of the first element in the range of elements to be erased.\r
+ /// </param>\r
+ /// <param name="_End">\r
+ /// Position of the first element beyond the range of elements to be erased.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the map given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for this <c>concurrent_unordered_multimap</c> object.\r
+ /// </returns>\r
+ /**/\r
+ iterator unsafe_erase(const_iterator _First, const_iterator _Last)\r
+ {\r
+ return _Mybase::unsafe_erase(_First, _Last);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Swaps the contents of two <c>concurrent_unordered_multimap</c> objects. \r
+ /// This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Umap">\r
+ /// The <c>concurrent_unordered_multimap</c> object to swap with.\r
+ /// </param>\r
+ /**/\r
+ void swap(concurrent_unordered_multimap& _Umap)\r
+ {\r
+ _Mybase::swap(_Umap);\r
+ }\r
+\r
+ // Observers\r
+ /// <summary>\r
+ /// The hash function object.\r
+ /// </summary>\r
+ /**/\r
+ hasher hash_function() const\r
+ {\r
+ return _M_comparator._M_hash_object;\r
+ }\r
+\r
+ /// <summary>\r
+ /// The equality comparison function object.\r
+ /// </summary>\r
+ /**/\r
+ key_equal key_eq() const\r
+ {\r
+ return _M_comparator._M_key_compare_object;\r
+ }\r
+};\r
+} // namespace Concurrency\r
+\r
+#pragma pack(pop)\r
--- /dev/null
+/***\r
+* ==++==\r
+*\r
+* Copyright (c) Microsoft Corporation. All rights reserved.\r
+* \r
+* ==--==\r
+* =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+\r
+*\r
+* concurrent_unordered_set.h\r
+*\r
+* =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\r
+****/\r
+#pragma once\r
+\r
+#include <utility>\r
+#include "internal_concurrent_hash.h"\r
+\r
+#if !(defined(_M_AMD64) || defined(_M_IX86))\r
+ #error ERROR: Concurrency Runtime is supported only on X64 and X86 architectures.\r
+#endif\r
+\r
+#if defined(_M_CEE)\r
+ #error ERROR: Concurrency Runtime is not supported when compiling /clr.\r
+#endif\r
+\r
+#pragma pack(push,_CRT_PACKING)\r
+\r
+namespace Concurrency\r
+{\r
+namespace samples\r
+{\r
+namespace details\r
+{\r
+// Template class for hash set traits\r
+template<typename _Key_type, typename _Key_comparator, typename _Allocator_type, bool _Allow_multimapping>\r
+class _Concurrent_unordered_set_traits : public std::_Container_base\r
+{\r
+public:\r
+ typedef _Key_type _Value_type;\r
+ typedef _Key_type value_type;\r
+ typedef _Key_type key_type;\r
+ typedef _Key_comparator key_compare;\r
+\r
+ typedef typename _Allocator_type::template rebind<value_type>::other allocator_type;\r
+\r
+ enum\r
+ {\r
+ _M_allow_multimapping = _Allow_multimapping\r
+ };\r
+\r
+ _Concurrent_unordered_set_traits() : _M_comparator()\r
+ {\r
+ }\r
+\r
+ _Concurrent_unordered_set_traits(const _Key_comparator& _Traits) : _M_comparator(_Traits)\r
+ {\r
+ }\r
+\r
+ typedef key_compare value_compare;\r
+\r
+ static const _Key_type& _Key_function(const value_type& _Value)\r
+ {\r
+ return _Value;\r
+ }\r
+\r
+ _Key_comparator _M_comparator; // the comparator predicate for keys\r
+};\r
+} // namespace details;\r
+\r
+/// <summary>\r
+/// The <c>concurrent_unordered_set</c> class is an concurrency-safe container that controls a varying-length sequence of \r
+/// elements of type _Key_type The sequence is represented in a way that enables concurrency-safe append, element access, \r
+/// iterator access and iterator traversal operations.\r
+/// </summary>\r
+/// <typeparam name="_Key_type">\r
+/// The key type.\r
+/// </typeparam>\r
+/// <typeparam name="_Hasher">\r
+/// The hash function object type. This argument is optional and the default value is\r
+/// tr1::hash<</c><typeparamref name="_Key_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <typeparam name="_Key_equality">\r
+/// The equality comparison function object type. This argument is optional and the default value is\r
+/// <c>equal_to<</c><typeparamref name="_Key_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <typeparam name="_Allocator_type">\r
+/// The type that represents the stored allocator object that encapsulates details about the allocation and\r
+/// deallocation of memory for the concurrent vector. This argument is optional and the default value is\r
+/// <c>allocator<</c><typeparamref name="_Key_type"/>, <typeparamref name="_Element_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <remarks>\r
+/// For detailed information on the <c>concurrent_unordered_set</c> class, see <see cref="Parallel Containers and Objects"/>.\r
+/// </remarks>\r
+/// <seealso cref="Parallel Containers and Objects"/>\r
+/**/\r
+template <typename _Key_type, typename _Hasher = std::tr1::hash<_Key_type>, typename _Key_equality = std::equal_to<_Key_type>, typename _Allocator_type = std::allocator<_Key_type> >\r
+class concurrent_unordered_set : public details::_Concurrent_hash< details::_Concurrent_unordered_set_traits<_Key_type, details::_Hash_compare<_Key_type, _Hasher, _Key_equality>, _Allocator_type, false> >\r
+{\r
+public:\r
+ // Base type definitions\r
+ typedef concurrent_unordered_set<_Key_type, _Hasher, _Key_equality, _Allocator_type> _Mytype;\r
+ typedef details::_Hash_compare<_Key_type, _Hasher, _Key_equality> _Mytraits;\r
+ typedef details::_Concurrent_hash< details::_Concurrent_unordered_set_traits<_Key_type, _Mytraits, _Allocator_type, false> > _Mybase;\r
+\r
+ // Type definitions\r
+ typedef _Key_type key_type;\r
+ typedef typename _Mybase::value_type value_type;\r
+ typedef _Key_type mapped_type;\r
+ typedef _Hasher hasher;\r
+ typedef _Key_equality key_equal;\r
+ typedef _Mytraits key_compare;\r
+\r
+ typedef typename _Mybase::allocator_type allocator_type;\r
+ typedef typename _Mybase::pointer pointer;\r
+ typedef typename _Mybase::const_pointer const_pointer;\r
+ typedef typename _Mybase::reference reference;\r
+ typedef typename _Mybase::const_reference const_reference;\r
+\r
+ typedef typename _Mybase::size_type size_type;\r
+ typedef typename _Mybase::difference_type difference_type;\r
+\r
+ typedef typename _Mybase::iterator iterator;\r
+ typedef typename _Mybase::const_iterator const_iterator;\r
+ typedef typename _Mybase::iterator local_iterator;\r
+ typedef typename _Mybase::const_iterator const_local_iterator;\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered set.\r
+ /// </summary>\r
+ /// <param name="_Number_of_buckets">\r
+ /// The initial number of buckets for this unordered set.\r
+ /// </param>\r
+ /// <param name="_Hasher">\r
+ /// The hash function for this unordered set.\r
+ /// </param>\r
+ /// <param name="_Key_equality">\r
+ /// The equality comparison function for this unordered set.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered set.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered set.\r
+ /// <para>The first constructor specifies an empty initial set and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered set.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ explicit concurrent_unordered_set(size_type _Number_of_buckets = 8, const hasher& _Hasher = hasher(), const key_equal& _Key_equality = key_equal(),\r
+ const allocator_type& _Allocator = allocator_type())\r
+ : _Mybase(_Number_of_buckets, key_compare(_Hasher, _Key_equality), _Allocator)\r
+ {\r
+ this->rehash(_Number_of_buckets);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered set.\r
+ /// </summary>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered set.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered set.\r
+ /// <para>The first constructor specifies an empty initial set and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered set.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_set(const allocator_type& _Allocator) : _Mybase(8, key_compare(), _Allocator)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered set.\r
+ /// </summary>\r
+ /// <typeparam name="_Iterator">\r
+ /// The type of the input iterator.\r
+ /// </typeparam>\r
+ /// <param name="_Begin">\r
+ /// Position of the first element in the range of elements to be copied.\r
+ /// </param>\r
+ /// <param name="_End">\r
+ /// Position of the first element beyond the range of elements to be copied.\r
+ /// </param>\r
+ /// <param name="_Number_of_buckets">\r
+ /// The initial number of buckets for this unordered set.\r
+ /// </param>\r
+ /// <param name="_Hasher">\r
+ /// The hash function for this unordered set.\r
+ /// </param>\r
+ /// <param name="_Key_equality">\r
+ /// The equality comparison function for this unordered set.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered set.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered set.\r
+ /// <para>The first constructor specifies an empty initial set and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered set.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ template <typename _Iterator>\r
+ concurrent_unordered_set(_Iterator _First, _Iterator _Last, size_type _Number_of_buckets = 8, const hasher& _Hasher = hasher(),\r
+ const key_equal& _Key_equality = key_equal(), const allocator_type& _Allocator = allocator_type())\r
+ : _Mybase(_Number_of_buckets, key_compare(), allocator_type())\r
+ {\r
+ this->rehash(_Number_of_buckets);\r
+ for (; _First != _Last; ++_First)\r
+ {\r
+ _Mybase::insert(*_First);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered set.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The source <c>concurrent_unordered_set</c> object to copy or move elements from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered set.\r
+ /// <para>The first constructor specifies an empty initial set and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered set.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_set(const concurrent_unordered_set& _Uset) : _Mybase(_Uset)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered set.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The source <c>concurrent_unordered_map</c> object to copy or move elements from.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered set.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered set.\r
+ /// <para>The first constructor specifies an empty initial set and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered set.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_set(const concurrent_unordered_set& _Uset, const allocator_type& _Allocator) : _Mybase(_Uset, _Allocator)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered set.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The source <c>concurrent_unordered_set</c> object to copy or move elements from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered set.\r
+ /// <para>The first constructor specifies an empty initial set and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered set.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered set <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_set(concurrent_unordered_set&& _Uset) : _Mybase(std::move(_Uset))\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Assigns the contents of another <c>concurrent_unordered_set</c> object to this one. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The source <c>concurrent_unordered_set</c> object.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A reference to this <c>concurrent_unordered_set</c> object.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After erasing any existing elements in a concurrent unordered set, <c>operator=</c> either copies or moves the contents of\r
+ /// <paramref name="_Uset"/> into the concurrent unordered set.\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_set& operator=(const concurrent_unordered_set& _Uset)\r
+ {\r
+ _Mybase::operator=(_Uset);\r
+ return (*this);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Assigns the contents of another <c>concurrent_unordered_set</c> object to this one. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The source <c>concurrent_unordered_set</c> object.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A reference to this <c>concurrent_unordered_set</c> object.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After erasing any existing elements in a concurrent unordered set, <c>operator=</c> either copies or moves the contents of\r
+ /// <paramref name="_Uset"/> into the concurrent unordered set.\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_set& operator=(concurrent_unordered_set&& _Uset)\r
+ {\r
+ _Mybase::operator=(std::move(_Uset));\r
+ return (*this);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_set</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Where">\r
+ /// The iterator position to erase from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the set given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for this <c>concurrent_unordered_set</c> object.\r
+ /// </returns>\r
+ /**/\r
+ iterator unsafe_erase(const_iterator _Where)\r
+ {\r
+ return _Mybase::unsafe_erase(_Where);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_set</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key to erase.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the set given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The count of elements erased from this <c>concurrent_unordered_set</c> object.\r
+ /// </returns>\r
+ /**/\r
+ size_type unsafe_erase(const key_type& _Keyval)\r
+ {\r
+ return _Mybase::unsafe_erase(_Keyval);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_set</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Begin">\r
+ /// Position of the first element in the range of elements to be erased.\r
+ /// </param>\r
+ /// <param name="_End">\r
+ /// Position of the first element beyond the range of elements to be erased.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the set given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for this <c>concurrent_unordered_set</c> object.\r
+ /// </returns>\r
+ /**/\r
+ iterator unsafe_erase(const_iterator _First, const_iterator _Last)\r
+ {\r
+ return _Mybase::unsafe_erase(_First, _Last);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Swaps the contents of two <c>concurrent_unordered_set</c> objects. \r
+ /// This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The <c>concurrent_unordered_set</c> object to swap with.\r
+ /// </param>\r
+ /**/\r
+ void swap(concurrent_unordered_set& _Uset)\r
+ {\r
+ _Mybase::swap(_Uset);\r
+ }\r
+\r
+ // Observers\r
+ /// <summary>\r
+ /// The hash function object.\r
+ /// </summary>\r
+ /**/\r
+ hasher hash_function() const\r
+ {\r
+ return _M_comparator._M_hash_object;\r
+ }\r
+\r
+ /// <summary>\r
+ /// The equality comparison function object.\r
+ /// </summary>\r
+ /**/\r
+ key_equal key_eq() const\r
+ {\r
+ return _M_comparator._M_key_compare_object;\r
+ }\r
+};\r
+\r
+/// <summary>\r
+/// The <c>concurrent_unordered_multiset</c> class is an concurrency-safe container that controls a varying-length sequence of \r
+/// elements of type _Key_type The sequence is represented in a way that enables concurrency-safe append, element access, \r
+/// iterator access and iterator traversal operations.\r
+/// </summary>\r
+/// <typeparam name="_Key_type">\r
+/// The key type.\r
+/// </typeparam>\r
+/// <typeparam name="_Hasher">\r
+/// The hash function object type. This argument is optional and the default value is\r
+/// tr1::hash<</c><typeparamref name="_Key_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <typeparam name="_Key_equality">\r
+/// The equality comparison function object type. This argument is optional and the default value is\r
+/// <c>equal_to<</c><typeparamref name="_Key_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <typeparam name="_Allocator_type">\r
+/// The type that represents the stored allocator object that encapsulates details about the allocation and\r
+/// deallocation of memory for the concurrent vector. This argument is optional and the default value is\r
+/// <c>allocator<</c><typeparamref name="_Key_type"/>, <typeparamref name="_Element_type"/><c>></c>.\r
+/// </typeparam>\r
+/// <remarks>\r
+/// For detailed information on the <c>concurrent_unordered_multiset</c> class, see <see cref="Parallel Containers and Objects"/>.\r
+/// </remarks>\r
+/// <seealso cref="Parallel Containers and Objects"/>\r
+/**/\r
+template <typename _Key_type, typename _Hasher = std::tr1::hash<_Key_type>, typename _Key_equality = std::equal_to<_Key_type>, typename _Allocator_type = std::allocator<_Key_type> >\r
+class concurrent_unordered_multiset : public details::_Concurrent_hash< details::_Concurrent_unordered_set_traits<_Key_type, details::_Hash_compare<_Key_type, _Hasher, _Key_equality>, _Allocator_type, true> >\r
+{\r
+public:\r
+ // Base type definitions\r
+ typedef concurrent_unordered_multiset<_Key_type, _Hasher, _Key_equality, _Allocator_type> _Mytype;\r
+ typedef details::_Hash_compare<_Key_type, _Hasher, _Key_equality> _Mytraits;\r
+ typedef details::_Concurrent_hash< details::_Concurrent_unordered_set_traits<_Key_type, _Mytraits, _Allocator_type, true> > _Mybase;\r
+\r
+ // Type definitions\r
+ typedef _Key_type key_type;\r
+ typedef typename _Mybase::value_type value_type;\r
+ typedef _Key_type mapped_type;\r
+ typedef _Hasher hasher;\r
+ typedef _Key_equality key_equal;\r
+ typedef _Mytraits key_compare;\r
+\r
+ typedef typename _Mybase::allocator_type allocator_type;\r
+ typedef typename _Mybase::pointer pointer;\r
+ typedef typename _Mybase::const_pointer const_pointer;\r
+ typedef typename _Mybase::reference reference;\r
+ typedef typename _Mybase::const_reference const_reference;\r
+\r
+ typedef typename _Mybase::size_type size_type;\r
+ typedef typename _Mybase::difference_type difference_type;\r
+\r
+ typedef typename _Mybase::iterator iterator;\r
+ typedef typename _Mybase::const_iterator const_iterator;\r
+ typedef typename _Mybase::iterator local_iterator;\r
+ typedef typename _Mybase::const_iterator const_local_iterator;\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multiset.\r
+ /// </summary>\r
+ /// <param name="_Number_of_buckets">\r
+ /// The initial number of buckets for this unordered multiset.\r
+ /// </param>\r
+ /// <param name="_Hasher">\r
+ /// The hash function for this unordered multiset.\r
+ /// </param>\r
+ /// <param name="_Key_equality">\r
+ /// The equality comparison function for this unordered multiset.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered multiset.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multiset.\r
+ /// <para>The first constructor specifies an empty initial multiset and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multiset.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ explicit concurrent_unordered_multiset(size_type _Number_of_buckets = 8, const hasher& _Hasher = hasher(), const key_equal& _Key_equality = key_equal(),\r
+ const allocator_type& _Allocator = allocator_type())\r
+ : _Mybase(_Number_of_buckets, key_compare(_Hasher, _Key_equality), _Allocator)\r
+ {\r
+ this->rehash(_Number_of_buckets);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multiset.\r
+ /// </summary>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered multiset.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multiset.\r
+ /// <para>The first constructor specifies an empty initial multiset and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multiset.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multiset(const allocator_type& _Allocator) : _Mybase(8, key_compare(), _Allocator)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multiset.\r
+ /// </summary>\r
+ /// <typeparam name="_Iterator">\r
+ /// The type of the input iterator.\r
+ /// </typeparam>\r
+ /// <param name="_Begin">\r
+ /// Position of the first element in the range of elements to be copied.\r
+ /// </param>\r
+ /// <param name="_End">\r
+ /// Position of the first element beyond the range of elements to be copied.\r
+ /// </param>\r
+ /// <param name="_Number_of_buckets">\r
+ /// The initial number of buckets for this unordered multiset.\r
+ /// </param>\r
+ /// <param name="_Hasher">\r
+ /// The hash function for this unordered multiset.\r
+ /// </param>\r
+ /// <param name="_Key_equality">\r
+ /// The equality comparison function for this unordered multiset.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered multiset.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multiset.\r
+ /// <para>The first constructor specifies an empty initial multiset and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multiset.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ template <typename _Iterator>\r
+ concurrent_unordered_multiset(_Iterator _First, _Iterator _Last, size_type _Number_of_buckets = 8, const hasher& _Hasher = hasher(),\r
+ const key_equal& _Key_equality = key_equal(), const allocator_type& _Allocator = allocator_type())\r
+ : _Mybase(_Number_of_buckets, key_compare(), allocator_type())\r
+ {\r
+ this->rehash(_Number_of_buckets);\r
+ for (; _First != _Last; ++_First)\r
+ {\r
+ _Mybase::insert(*_First);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multiset.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The source <c>concurrent_unordered_multiset</c> object to copy elements from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multiset.\r
+ /// <para>The first constructor specifies an empty initial multiset and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multiset.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multiset(const concurrent_unordered_multiset& _Uset) : _Mybase(_Uset)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multiset.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The source <c>concurrent_unordered_multiset</c> object to copy elements from.\r
+ /// </param>\r
+ /// <param name="_Allocator">\r
+ /// The allocator for this unordered multiset.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multiset.\r
+ /// <para>The first constructor specifies an empty initial multiset and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multiset.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multiset(const concurrent_unordered_multiset& _Uset, const allocator_type& _Allocator) : _Mybase(_Uset, _Allocator)\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Constructs a concurrent unordered multiset.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The source <c>concurrent_unordered_multiset</c> object to move elements from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// All constructors store an allocator object <paramref name="_Allocator"/> and initialize the unordered multiset.\r
+ /// <para>The first constructor specifies an empty initial multiset and explicitly specifies the number of buckets,\r
+ /// hash function, equality function and allocator type to be used.</para>\r
+ /// <para>The second constructor specifies an allocator for the unordered multiset.<para>\r
+ /// <para>The third constructor specifies values supplied by the iterator range [<paramref name="_Begin"/>, <paramref name="_End"/>).</para>\r
+ /// <para>The fourth and fifth constructors specify a copy of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// <para>The last constructor specifies a move of the concurrent unordered multiset <paramref name="_Uset"/>.</para>\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multiset(concurrent_unordered_multiset&& _Uset) : _Mybase(std::move(_Uset))\r
+ {\r
+ }\r
+\r
+ /// <summary>\r
+ /// Assigns the contents of another <c>concurrent_unordered_multiset</c> object to this one. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The source <c>concurrent_unordered_multiset</c> object.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A reference to this <c>concurrent_unordered_multiset</c> object.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After erasing any existing elements in a concurrent unordered multiset, <c>operator=</c> either copies or moves the contents of \r
+ /// <paramref name="_Uset"/> into the concurrent unordered multiset.\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multiset& operator=(const concurrent_unordered_multiset& _Uset)\r
+ {\r
+ _Mybase::operator=(_Uset);\r
+ return (*this);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Assigns the contents of another <c>concurrent_unordered_multiset</c> object to this one. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The source <c>concurrent_unordered_multiset</c> object.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A reference to this <c>concurrent_unordered_multiset</c> object.\r
+ /// </returns>\r
+ /// <remarks>\r
+ /// After erasing any existing elements in a concurrent unordered multiset, <c>operator=</c> either copies or moves the contents of \r
+ /// <paramref name="_Uset"/> into the concurrent unordered multiset.\r
+ /// </remarks>\r
+ /**/\r
+ concurrent_unordered_multiset& operator=(concurrent_unordered_multiset&& _Uset)\r
+ {\r
+ _Mybase::operator=(std::move(_Uset));\r
+ return (*this);\r
+ }\r
+\r
+ // Modifiers\r
+ /// <summary>\r
+ /// Inserts a value into the <c>concurrent_unordered_multiset</c> object. \r
+ /// </summary>\r
+ /// <param name="_Value">\r
+ /// The value to be inserted into the <c>concurrent_unordered_multiset</c> object.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function determines whether an element X exists in the sequence whose key has equivalent ordering to \r
+ /// that of _Value. If not, it creates such an element X and initializes it with _Value. The function then determines the \r
+ /// iterator where that designates X. If an insertion occurred, the function returns std::pair(where, true). Otherwise, \r
+ /// it returns std::pair(where, false).\r
+ /// <para>The second function uses the <c>const_iterator _Where</c> as a starting location to search for an insertion point</para>\r
+ /// <para>The third function inserts the sequence of element values, from the range [_First, _Last).</para>\r
+ /// <para>The last two functions behave the same as the first two, except that <paramref name="_Value"/> is used to construct the inserted value.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator pointing to the insertion location.\r
+ /// </returns>\r
+ /**/\r
+ iterator insert(const value_type& _Value)\r
+ {\r
+ return (_Mybase::insert(_Value)).first;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts a value into the <c>concurrent_unordered_multiset</c> object. \r
+ /// </summary>\r
+ /// <param name="_Where">\r
+ /// The starting location to search for an insertion point into the <c>concurrent_unordered_multiset</c> object.\r
+ /// </param>\r
+ /// <param name="_Value">\r
+ /// The value to be inserted into the <c>concurrent_unordered_multiset</c> object.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function determines whether an element X exists in the sequence whose key has equivalent ordering to \r
+ /// that of _Value. If not, it creates such an element X and initializes it with _Value. The function then determines the \r
+ /// iterator where that designates X. If an insertion occurred, the function returns std::pair(where, true). Otherwise, \r
+ /// it returns std::pair(where, false).\r
+ /// <para>The second function uses the <c>const_iterator _Where</c> as a starting location to search for an insertion point</para>\r
+ /// <para>The third function inserts the sequence of element values, from the range [_First, _Last).</para>\r
+ /// <para>The last two functions behave the same as the first two, except that <paramref name="_Value"/> is used to construct the inserted value.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for the <c>concurrent_unordered_multiset</c> object.\r
+ /// </returns>\r
+ iterator insert(const_iterator _Where, const value_type& _Value)\r
+ {\r
+ return _Mybase::insert(_Where, _Value);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts values into the <c>concurrent_unordered_multiset</c> object. \r
+ /// </summary>\r
+ /// <typeparam name="_Iterator">\r
+ /// The iterator type used for insertion.\r
+ /// </typeparm>\r
+ /// <param name="_First">\r
+ /// The starting location in an itertor of elements to insert into the <c>concurrent_unordered_multiset</c> object.\r
+ /// </param>\r
+ /// <param name="_Last">\r
+ /// The ending location in an itertor of elements to insert into the <c>concurrent_unordered_multiset</c> object.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function determines whether an element X exists in the sequence whose key has equivalent ordering to \r
+ /// that of _Value. If not, it creates such an element X and initializes it with _Value. The function then determines the \r
+ /// iterator where that designates X. If an insertion occurred, the function returns std::pair(where, true). Otherwise, \r
+ /// it returns std::pair(where, false).\r
+ /// <para>The second function uses the <c>const_iterator _Where</c> as a starting location to search for an insertion point</para>\r
+ /// <para>The third function inserts the sequence of element values, from the range [_First, _Last).</para>\r
+ /// <para>The last two functions behave the same as the first two, except that <paramref name="_Value"/> is used to construct the inserted value.\r
+ /// </remarks>\r
+ template<class _Iterator>\r
+ void insert(_Iterator _First, _Iterator _Last)\r
+ {\r
+ _Mybase::insert(_First, _Last);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts a value into the <c>concurrent_unordered_multiset</c> object. \r
+ /// </summary>\r
+ /// <typeparam name="_Valty">\r
+ /// The type of the value inserted into the map.\r
+ /// </typeparm>\r
+ /// <param name="_Value">\r
+ /// The value to be inserted into the <c>concurrent_unordered_multiset</c> object.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function determines whether an element X exists in the sequence whose key has equivalent ordering to \r
+ /// that of _Value. If not, it creates such an element X and initializes it with _Value. The function then determines the \r
+ /// iterator where that designates X. If an insertion occurred, the function returns std::pair(where, true). Otherwise, \r
+ /// it returns std::pair(where, false).\r
+ /// <para>The second function uses the <c>const_iterator _Where</c> as a starting location to search for an insertion point</para>\r
+ /// <para>The third function inserts the sequence of element values, from the range [_First, _Last).</para>\r
+ /// <para>The last two functions behave the same as the first two, except that <paramref name="_Value"/> is used to construct the inserted value.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator pointing to the insertion location.\r
+ /// </returns>\r
+ /**/\r
+ template<class _Valty>\r
+ iterator insert(_Valty&& _Value)\r
+ {\r
+ return (_Mybase::insert(std::forward<_Valty>(_Value))).first;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts a value into the <c>concurrent_unordered_multiset</c> object. \r
+ /// </summary>\r
+ /// <typeparam name="_Valty">\r
+ /// The type of the value inserted into the map.\r
+ /// </typeparm>\r
+ /// <param name="_Where">\r
+ /// The starting location to search for an insertion point into the <c>concurrent_unordered_multiset</c> object.\r
+ /// </param>\r
+ /// <param name="_Value">\r
+ /// The value to be inserted into the <c>concurrent_unordered_multiset</c> object.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function determines whether an element X exists in the sequence whose key has equivalent ordering to \r
+ /// that of _Value. If not, it creates such an element X and initializes it with _Value. The function then determines the \r
+ /// iterator where that designates X. If an insertion occurred, the function returns std::pair(where, true). Otherwise, \r
+ /// it returns std::pair(where, false).\r
+ /// <para>The second function uses the <c>const_iterator _Where</c> as a starting location to search for an insertion point</para>\r
+ /// <para>The third function inserts the sequence of element values, from the range [_First, _Last).</para>\r
+ /// <para>The last two functions behave the same as the first two, except that <paramref name="_Value"/> is used to construct the inserted value.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for the <c>concurrent_unordered_multiset</c> object.\r
+ /// </returns>\r
+ template<class _Valty>\r
+ typename std::tr1::enable_if<!std::tr1::is_same<const_iterator, \r
+ typename std::tr1::remove_reference<_Valty>::type>::value, iterator>::type\r
+ insert(const_iterator _Where, _Valty&& _Value)\r
+ {\r
+ return _Mybase::insert(_Where, std::forward<_Valty>(_Value));\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_multiset</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Where">\r
+ /// The iterator position to erase from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the multiset given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for this <c>concurrent_unordered_multiset</c> object.\r
+ /// </returns>\r
+ /**/\r
+ iterator unsafe_erase(const_iterator _Where)\r
+ {\r
+ return _Mybase::unsafe_erase(_Where);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_multiset</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key to erase.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the multiset given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The count of elements erased from this <c>concurrent_unordered_multiset</c> object.\r
+ /// </returns>\r
+ /**/\r
+ size_type unsafe_erase(const key_type& _Keyval)\r
+ {\r
+ return _Mybase::unsafe_erase(_Keyval);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases elements from the <c>concurrent_unordered_multiset</c>. This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Begin">\r
+ /// Position of the first element in the range of elements to be erased.\r
+ /// </param>\r
+ /// <param name="_End">\r
+ /// Position of the first element beyond the range of elements to be erased.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The first function erases an element from the multiset given an iterator position.\r
+ /// <para>The second function erases an element matching a key</para>\r
+ /// <para>The third function erases elements given an iterator begin and end position</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The iterator for this <c>concurrent_unordered_multiset</c> object.\r
+ /// </returns>\r
+ /**/\r
+ iterator unsafe_erase(const_iterator _First, const_iterator _Last)\r
+ {\r
+ return _Mybase::unsafe_erase(_First, _Last);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Swaps the contents of two <c>concurrent_unordered_multiset</c> objects. \r
+ /// This method is not concurrency-safe.\r
+ /// </summary>\r
+ /// <param name="_Uset">\r
+ /// The <c>concurrent_unordered_multiset</c> object to swap with.\r
+ /// </param>\r
+ /**/\r
+ void swap(concurrent_unordered_multiset& _Uset)\r
+ {\r
+ _Mybase::swap(_Uset);\r
+ }\r
+\r
+ // Observers\r
+ /// <summary>\r
+ /// The hash function object.\r
+ /// </summary>\r
+ /**/\r
+ hasher hash_function() const\r
+ {\r
+ return _M_comparator._M_hash_object;\r
+ }\r
+\r
+ /// <summary>\r
+ /// The equality comparison function object.\r
+ /// </summary>\r
+ /**/\r
+ key_equal key_eq() const\r
+ {\r
+ return _M_comparator._M_key_compare_object;\r
+ }\r
+};\r
+} // namespace samples\r
+} // namespace Concurrency\r
+\r
+#pragma pack(pop)\r
--- /dev/null
+//--------------------------------------------------------------------------\r
+// \r
+// Copyright (c) Microsoft Corporation. All rights reserved. \r
+// \r
+// File: connect.h\r
+//\r
+// connect / disconnect helper functions\r
+//\r
+//--------------------------------------------------------------------------\r
+#pragma once\r
+#include <type_traits>\r
+#include <agents.h>\r
+\r
+namespace Concurrency\r
+{\r
+ namespace details\r
+ { \r
+ //details for the connect type traits\r
+\r
+ //creates a has_member_foo class which can be used to check\r
+ //for a named member variable\r
+ #define DEFINE_HAS_MEMBER(NAME) \\r
+ template <typename T> class has_member_ ## NAME { \\r
+ private: \\r
+ template <typename U> static std::true_type helper(decltype(&U::NAME)); \\r
+ template <typename U> static std::false_type helper(...); \\r
+ typedef decltype(helper<T>(nullptr)) helper_t; \\r
+ public: \\r
+ static const bool value = helper_t::value; \\r
+ };\r
+\r
+ //define input_buffer & output_buffer classes\r
+ DEFINE_HAS_MEMBER(input_buffer)\r
+ DEFINE_HAS_MEMBER(output_buffer)\r
+\r
+ //there must be an existing type trait for this\r
+ template<const bool value_type>\r
+ struct _is_true : std::false_type\r
+ {\r
+ };\r
+\r
+ template<>\r
+ struct _is_true<true> : std::true_type\r
+ {\r
+ };\r
+\r
+ //_as_ref normalizes an instance of a class to a reference parameter.\r
+ //this works with pointers, references and values, but probably not with\r
+ //pointer to pointer and definitely not with shared pointers\r
+ template<typename T>\r
+ class _as_ref\r
+ {\r
+ _as_ref & operator=(const _as_ref & );\r
+\r
+ public:\r
+ typedef T type;\r
+ //_as_ref(T& t): ref(t){}\r
+ _as_ref(T& t): ref(t){}\r
+ _as_ref(T* t): ref(*t){}\r
+ typename std::add_const<typename std::add_reference<T>::type>::type& ref;\r
+ };\r
+\r
+ //_as_ref normalizes an instance of a class to a reference parameter.\r
+ template <typename T>\r
+ class as_ref : public _as_ref<typename std::remove_pointer<T>::type>\r
+ {\r
+ as_ref & operator=( const as_ref & );\r
+ public:\r
+ as_ref(T& t):_as_ref(t){}\r
+ };\r
+\r
+ }// end details namespace\r
+\r
+ using namespace details;\r
+ //type traits, determines if a class acts as a compound message target\r
+ template<typename target_type>\r
+ struct is_compound_target\r
+ : _is_true<has_member_input_buffer<typename std::remove_cv<target_type>::type>::value>\r
+ {\r
+ };\r
+\r
+ //type traits, determines if a class acts as a compound message source\r
+ template<typename source_type>\r
+ struct is_compound_source\r
+ : _is_true<has_member_output_buffer<typename std::remove_cv<source_type>::type>::value>\r
+ {\r
+ };\r
+\r
+ //connects two message blocks or compound message blocks forward declaration\r
+ template<typename source_type, typename target_type>\r
+ inline void connect(source_type& source, target_type& target);\r
+\r
+ //disconnects two message blocks or compound message blocks forward declaration\r
+ template<typename source_type, typename target_type>\r
+ inline void disconnect(source_type& source, target_type& target);\r
+\r
+ namespace details\r
+ {\r
+ //connects an ISource to an ITarget\r
+ template <typename source_block, typename target_block>\r
+ inline void connect_to_target_impl(source_block& source, target_block& target)\r
+ {\r
+ source.link_target(&target);\r
+ }\r
+ //connect a simple source to a simple target\r
+ template<typename source_type, typename target_type>\r
+ inline void connect_impl(source_type& source, std::false_type /*not_compound_source*/, \r
+ target_type& target, std::false_type /*not_compound_target*/)\r
+ {\r
+ connect_to_target_impl(source,target);\r
+ }\r
+\r
+ //connect a simple source to a compound target\r
+ template<typename source_type, typename target_type>\r
+ inline void connect_impl(source_type& source, std::false_type /*not_compound_source*/, \r
+ target_type& target, std::true_type /*is_compound_target*/)\r
+ {\r
+ samples::connect(source, target.input_buffer);\r
+ }\r
+\r
+ //connect a compound source to a simple target\r
+ template<typename source_type, typename target_type>\r
+ inline void connect_impl(source_type& source, std::true_type /*not_compound_source*/, \r
+ target_type& target, std::false_type /*is_compound_target*/)\r
+ {\r
+ samples::connect(source.output_buffer, target);\r
+ }\r
+\r
+ //connect a compound source to a compound target\r
+ template<typename source_type, typename target_type>\r
+ inline void connect_impl(source_type& source, std::true_type /*not_compound_source*/, \r
+ target_type& target, std::true_type /*is_compound_target*/)\r
+ {\r
+ samples::connect(source.output_buffer, target.input_buffer);\r
+ }\r
+\r
+ //connect_impl function that works with 'as_ref' types, this function\r
+ //relies on overloading and is_compound_source/target type traits to resolve\r
+ //to simple message blocks\r
+ template<typename source_type, typename target_type>\r
+ inline void connect_impl(const source_type& source, const target_type& target)\r
+ {\r
+ connect_impl(source.ref, is_compound_source<typename source_type::type>(),\r
+ target.ref, is_compound_target<typename target_type::type>());\r
+ }\r
+\r
+ template <typename source_block, typename target_block>\r
+ inline void disconnect_from_target_impl(source_block& source, target_block& target)\r
+ {\r
+ source.unlink_target(&target);\r
+ }\r
+ //disconnect a source from a target, neither of which is a compound source or target\r
+ template<typename source_type, typename target_type>\r
+ inline void disconnect_impl(source_type& source, std::false_type /*not_compound_source*/, \r
+ target_type& target, std::false_type /*not_compound_target*/)\r
+ {\r
+ disconnect_from_target_impl(source,target);\r
+ }\r
+ //disconnect a simple source to a compound target\r
+ template<typename source_type, typename target_type>\r
+ inline void disconnect_impl(source_type& source, std::false_type /*not_compound_source*/, \r
+ target_type& target, std::true_type /*is_compound_target*/)\r
+ {\r
+ samples::disconnect(source, target.input_buffer);\r
+ }\r
+ //disconnect a compound source from a simple target\r
+ template<typename source_type, typename target_type>\r
+ inline void disconnect_impl(source_type& source, std::true_type /*not_compound_source*/, \r
+ target_type& target, std::false_type /*is_compound_target*/)\r
+ {\r
+ samples::disconnect(source.output_buffer, target);\r
+ }\r
+\r
+ //disconnect a compound source from a compound target\r
+ template<typename source_type, typename target_type>\r
+ inline void disconnect_impl(source_type& source, std::true_type /*not_compound_source*/, \r
+ target_type& target, std::true_type /*is_compound_target*/)\r
+ {\r
+ samples::disconnect(source.output_buffer, target.input_buffer);\r
+ }\r
+\r
+ //disconnect impl has pointers removed already these are as_ref types\r
+ template<typename source_type, typename target_type>\r
+ inline void disconnect_impl(const source_type& source, const target_type& target)\r
+ {\r
+ //first pass remove pointers\r
+ disconnect_impl(source.ref, is_compound_source<typename source_type::type>(),\r
+ target.ref, is_compound_target<typename target_type::type>());\r
+ }\r
+ template<typename source_type>\r
+ inline void disconnect_all_impl(source_type& source, std::false_type/*not_compound_source*/)\r
+ {\r
+ source.unlink_targets();\r
+ }\r
+ template<typename source_type>\r
+ inline void disconnect_all_impl(source_type& source, std::true_type /*is_compound_source*/)\r
+ {\r
+ samples::disconnect(source.output_buffer);\r
+ }\r
+ template<typename source_type>\r
+ inline void disconnect_all_impl(source_type& source)\r
+ {\r
+ details::disconnect_all_impl(source.ref, is_compound_source<typename source_type::type>());\r
+ }\r
+\r
+ }// end details namespace\r
+\r
+ //connects two message blocks or compound message blocks\r
+ template<typename source_type, typename target_type>\r
+ inline void connect(source_type& source, target_type& target)\r
+ {\r
+ details::connect_impl(as_ref<source_type>(source), as_ref<target_type>(target));\r
+ }\r
+\r
+ //disconnects two message blocks or compound message blocks\r
+ template<typename source_type, typename target_type>\r
+ inline void disconnect(source_type& source, target_type& target)\r
+ {\r
+ details::disconnect_impl(as_ref<source_type>(source), as_ref<target_type>(target));\r
+ }\r
+\r
+ //connects two message blocks or compound message blocks, source is shared_ptr\r
+ template<typename source_type, typename target_type>\r
+ inline void connect(std::shared_ptr<source_type>& source_ptr, target_type& target)\r
+ {\r
+ details::connect_impl(as_ref<source_type>(*source_ptr.get()), as_ref<target_type>(target));\r
+ }\r
+\r
+ //connects two message blocks or compound message blocks both shared ptrs\r
+ template<typename source_type, typename target_type>\r
+ inline void connect(std::shared_ptr<source_type>& source_ptr, std::shared_ptr<target_type>& target_ptr)\r
+ {\r
+ details::connect_impl(as_ref<source_type>(*source_ptr.get()), as_ref<target_type>(*target_ptr.get()));\r
+ }\r
+\r
+ //connects two message blocks or compound message blocks target is shared_ptr\r
+ template<typename source_type, typename target_type>\r
+ inline void connect(source_type& source, std::shared_ptr<target_type>& target_ptr)\r
+ {\r
+ details::connect_impl(as_ref<source_type>(source), as_ref<target_type>(*target_ptr.get()));\r
+ }\r
+\r
+ //connects two message blocks or compound message blocks, source is shared_ptr\r
+ template<typename source_type, typename target_type>\r
+ inline void disconnect(std::shared_ptr<source_type>& source_ptr, target_type& target)\r
+ {\r
+ details::disconnect_impl(as_ref<source_type>(*source_ptr.get()), as_ref<target_type>(target));\r
+ }\r
+\r
+ //connects two message blocks or compound message blocks both shared ptrs\r
+ template<typename source_type, typename target_type>\r
+ inline void disconnect(std::shared_ptr<source_type>& source_ptr, std::shared_ptr<target_type>& target_ptr)\r
+ {\r
+ details::disconnect_impl(as_ref<source_type>(*source_ptr.get()), as_ref<target_type>(*target_ptr.get()));\r
+ }\r
+\r
+ //connects two message blocks or compound message blocks target is shared_ptr\r
+ template<typename source_type, typename target_type>\r
+ inline void disconnect(source_type& source, std::shared_ptr<target_type>& target_ptr)\r
+ {\r
+ details::disconnect_impl(as_ref<source_type>(source), as_ref<target_type>(*target_ptr.get()));\r
+ }\r
+\r
+ //disconnects all connected targets\r
+ template<typename source_type>\r
+ inline void disconnect(source_type& source)\r
+ {\r
+ details::disconnect_all_impl(as_ref<source_type>(source));\r
+ }\r
+\r
+ //disconnects a message block that is a shared_ptr\r
+ template<typename source_type>\r
+ inline void disconnect(std::shared_ptr<source_type>& source_ptr)\r
+ {\r
+ details::disconnect_all_impl(as_ref<source_type>(*source_ptr.get()));\r
+ }\r
+}
\ No newline at end of file
--- /dev/null
+/***\r
+* ==++==\r
+*\r
+* Copyright (c) Microsoft Corporation. All rights reserved.\r
+* \r
+* ==--==\r
+* =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+\r
+*\r
+* internal_concurrent_hash.h\r
+*\r
+* =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\r
+****/\r
+#pragma once\r
+\r
+#include <utility>\r
+#include "internal_split_ordered_list.h"\r
+#include <concrt.h>\r
+\r
+namespace Concurrency\r
+{\r
+namespace details\r
+{\r
+// Template class for hash compare\r
+template<typename _Key_type, typename _Hasher, typename _Key_equality>\r
+class _Hash_compare\r
+{\r
+public:\r
+ typedef _Hasher hasher;\r
+\r
+ _Hash_compare()\r
+ {\r
+ }\r
+\r
+ _Hash_compare(hasher _Hasharg) : _M_hash_object(_Hasharg)\r
+ {\r
+ }\r
+\r
+ _Hash_compare(hasher _Hasharg, _Key_equality _Keyeqarg) : _M_hash_object(_Hasharg), _M_key_compare_object(_Keyeqarg)\r
+ {\r
+ }\r
+\r
+ size_t operator()(const _Key_type& _Keyval) const\r
+ {\r
+ return ((size_t)_M_hash_object(_Keyval));\r
+ }\r
+\r
+ bool operator()(const _Key_type& _Keyval1, const _Key_type& _Keyval2) const\r
+ {\r
+ return (!_M_key_compare_object(_Keyval1, _Keyval2));\r
+ }\r
+\r
+ hasher _M_hash_object; // The hash object\r
+ _Key_equality _M_key_compare_object; // The equality comparator object\r
+};\r
+\r
+// An efficient implementation of the _Reverse function utilizes a 2^8 or 2^16 lookup table holding the\r
+// bit-reversed values of [0..2^8 - 1] or [0..2^16 - 1] respectively. Those values can also be computed\r
+// on the fly at a slightly higher cost.\r
+const unsigned char _Byte_reverse_table[] =\r
+{\r
+ 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,\r
+ 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,\r
+ 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,\r
+ 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,\r
+ 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,\r
+ 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,\r
+ 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,\r
+ 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,\r
+ 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,\r
+ 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,\r
+ 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,\r
+ 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,\r
+ 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,\r
+ 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,\r
+ 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,\r
+ 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF\r
+};\r
+\r
+// Given a byte, reverses it\r
+inline unsigned char _Reverse_byte(unsigned char _Original_byte)\r
+{\r
+ // return ((_Original_byte * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;\r
+ return _Byte_reverse_table[_Original_byte];\r
+}\r
+\r
+// Finds the most significant bit in a size_t\r
+inline unsigned char _Get_msb(size_t _Mask)\r
+{\r
+ unsigned long _Index = 0;\r
+\r
+#if defined(_M_IX86)\r
+ _BitScanReverse(&_Index, _Mask);\r
+#else\r
+ _BitScanReverse64(&_Index, _Mask);\r
+#endif\r
+\r
+ return (unsigned char) _Index;\r
+}\r
+\r
+#pragma warning(push)\r
+#pragma warning(disable: 4127) // warning 4127 -- while (true) has a constant expression in it\r
+\r
+template <typename _Traits>\r
+class _Concurrent_hash : public _Traits\r
+{\r
+public:\r
+ // Type definitions\r
+ typedef _Concurrent_hash<_Traits> _Mytype;\r
+ typedef typename _Traits::_Value_type _Value_type;\r
+ typedef typename _Traits::value_type value_type;\r
+ typedef typename _Traits::key_type key_type;\r
+ typedef typename _Traits::key_compare key_compare;\r
+ typedef typename _Traits::value_compare value_compare;\r
+\r
+ typedef typename _Traits::allocator_type allocator_type;\r
+ typedef typename allocator_type::pointer pointer;\r
+ typedef typename allocator_type::const_pointer const_pointer;\r
+ typedef typename allocator_type::reference reference;\r
+ typedef typename allocator_type::const_reference const_reference;\r
+\r
+ typedef typename allocator_type::size_type size_type;\r
+ typedef typename allocator_type::difference_type difference_type;\r
+\r
+ typedef typename _Split_ordered_list<typename _Traits::value_type, typename _Traits::allocator_type> _Mylist;\r
+ typedef typename _Mylist::_Nodeptr _Nodeptr;\r
+\r
+ typedef typename std::tr1::conditional<std::tr1::is_same<key_type, value_type>::value, typename _Mylist::const_iterator, typename _Mylist::iterator>::type iterator;\r
+ typedef typename _Mylist::const_iterator const_iterator;\r
+ typedef iterator local_iterator;\r
+ typedef const_iterator const_local_iterator;\r
+ typedef std::pair<iterator, bool> _Pairib;\r
+ typedef std::pair<iterator, iterator> _Pairii;\r
+ typedef std::pair<const_iterator, const_iterator> _Paircc;\r
+\r
+ // Iterators that walk the entire split-order list, including dummy nodes\r
+ typedef typename _Mylist::_Full_iterator _Full_iterator;\r
+ typedef typename _Mylist::_Full_const_iterator _Full_const_iterator;\r
+\r
+ static const size_type _Initial_bucket_number = 8; // Initial number of buckets\r
+ static const size_type _Initial_bucket_load = 4; // Initial maximum number of elements per bucket\r
+ static size_type const _Pointers_per_table = sizeof(size_type) * 8; // One bucket segment per bit\r
+\r
+ // Constructors/Destructors\r
+ _Concurrent_hash(size_type _Number_of_buckets = _Initial_bucket_number, const key_compare& _Parg = key_compare(), const allocator_type& _Allocator = allocator_type())\r
+ : _Traits(_Parg), _M_number_of_buckets(_Number_of_buckets), _M_split_ordered_list(_Allocator), _M_allocator(_Allocator), _M_maximum_bucket_size((float) _Initial_bucket_load)\r
+ {\r
+ _Init();\r
+ }\r
+\r
+ _Concurrent_hash(const _Concurrent_hash& _Right, const allocator_type& _Allocator) : _Traits(_Right._M_comparator), _M_split_ordered_list(_Allocator), _M_allocator(_Allocator)\r
+ {\r
+ _Copy(_Right);\r
+ }\r
+\r
+ _Concurrent_hash(const _Concurrent_hash& _Right) : _Traits(_Right._M_comparator), _M_split_ordered_list(_Right.get_allocator()), _M_allocator(_Right.get_allocator())\r
+ {\r
+ _Init();\r
+ _Copy(_Right);\r
+ }\r
+\r
+ _Concurrent_hash(_Concurrent_hash&& _Right) : _Traits(_Right._M_comparator), _M_split_ordered_list(_Right.get_allocator()), _M_allocator(_Right.get_allocator()),\r
+ _M_number_of_buckets(_Initial_bucket_number), _M_maximum_bucket_size((float) _Initial_bucket_load)\r
+ {\r
+ _Init();\r
+ swap(_Right);\r
+ }\r
+\r
+ _Concurrent_hash& operator=(const _Concurrent_hash& _Right)\r
+ {\r
+ if (this != &_Right)\r
+ {\r
+ _Copy(_Right);\r
+ }\r
+\r
+ return (*this);\r
+ }\r
+\r
+ _Concurrent_hash& operator=(_Concurrent_hash&& _Right)\r
+ {\r
+ if (this != &_Right)\r
+ {\r
+ clear();\r
+ swap(_Right);\r
+ }\r
+\r
+ return (*this);\r
+ }\r
+\r
+ ~_Concurrent_hash()\r
+ {\r
+ // Delete all node segments\r
+ for (size_type _Index = 0; _Index < _Pointers_per_table; _Index++)\r
+ {\r
+ if (_M_buckets[_Index] != NULL)\r
+ {\r
+ size_type _Seg_size = _Segment_size(_Index);\r
+ for (size_type _Index2 = 0; _Index2 < _Seg_size; _Index2++)\r
+ {\r
+ _M_allocator.destroy(&_M_buckets[_Index][_Index2]);\r
+ }\r
+ _M_allocator.deallocate(_M_buckets[_Index], _Seg_size);\r
+ }\r
+ }\r
+ }\r
+\r
+ static size_type __cdecl _Segment_index_of( size_type _Index )\r
+ {\r
+ return size_type( _Get_msb( _Index|1 ) );\r
+ }\r
+\r
+ static size_type _Segment_base( size_type _K )\r
+ {\r
+ return (size_type(1)<<_K & ~size_type(1));\r
+ }\r
+\r
+ static size_type _Segment_size( size_type _K )\r
+ {\r
+ return _K ? size_type(1)<<_K : 2;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the allocator used for this concurrent container. \r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The allocator used for this concurrent container.\r
+ /// </returns>\r
+ /**/\r
+ allocator_type get_allocator() const\r
+ {\r
+ return _M_split_ordered_list.get_allocator();\r
+ }\r
+\r
+ // Size and capacity function\r
+ /// <summary>\r
+ /// Checks whether the number of elements in this concurrent container is non-zero. \r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// <para>With concurrent inserts, whether or not the concurrent container is empty may change \r
+ /// immediately after calling this function, before the return value is even read.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// True, if this concurrent container object is empty, false, otherwise.\r
+ /// </returns>\r
+ /**/\r
+ bool empty() const\r
+ {\r
+ return _M_split_ordered_list.empty();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the number of elements in this concurrent container. \r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// <para>With concurrent inserts, the number of elements in the concurrent container may change \r
+ /// immediately after calling this function, before the return value is even read.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The number of items in the container.\r
+ /// </returns>\r
+ /**/\r
+ size_type size() const\r
+ {\r
+ return _M_split_ordered_list.size();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the maximum size of the concurrent container, determined by the allocator.\r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// <para>This upper bound value may actually be higher than what the container can actually hold.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The maximum number of elements that can be put into this concurrent container.\r
+ /// </returns>\r
+ /**/\r
+ size_type max_size() const\r
+ {\r
+ return _M_split_ordered_list.max_size();\r
+ }\r
+\r
+ // Iterators \r
+ /// <summary>\r
+ /// Returns an iterator pointing to the first element in the concurrent container.\r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator to the first element in the concurrent container.\r
+ /// </returns>\r
+ /**/\r
+ iterator begin()\r
+ {\r
+ return _M_split_ordered_list.begin();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns a const_iterator pointing to the first element in the concurrent container.\r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// A const_iterator to the first element in the concurrent container.\r
+ /// </returns>\r
+ /**/\r
+ const_iterator begin() const\r
+ {\r
+ return _M_split_ordered_list.begin();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns an iterator pointing to the location succeeding the last element in the concurrent container.\r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator to the location succeeding the last element in the concurrent container.\r
+ /// </returns>\r
+ /**/\r
+ iterator end()\r
+ {\r
+ return _M_split_ordered_list.end();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns a const_iterator pointing to the location succeeding the last element in the concurrent container.\r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// A const_iterator to the location succeeding the last element in the concurrent container.\r
+ /// </returns>\r
+ /**/\r
+ const_iterator end() const\r
+ {\r
+ return _M_split_ordered_list.end();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns a const_iterator pointing to the first element in the concurrent container.\r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// A const_iterator to the first element in the concurrent container.\r
+ /// </returns>\r
+ /**/\r
+ const_iterator cbegin() const\r
+ {\r
+ return _M_split_ordered_list.cbegin();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns a const_iterator pointing to the location succeeding the last element in the concurrent container.\r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// A const_iterator to the location succeeding the last element in the concurrent container.\r
+ /// </returns>\r
+ /**/\r
+ const_iterator cend() const\r
+ {\r
+ return _M_split_ordered_list.cend();\r
+ }\r
+\r
+ // Modifiers\r
+ /// <summary>\r
+ /// Inserts a value into the concurrent container.\r
+ /// </summary>\r
+ /// <param name="_Value">\r
+ /// The value to insert.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// A <see cref="pair Class">pair</see> where the first object is an iterator into the container at the insertion point and the \r
+ /// second object is a bool indicating whether the value was inserted (true) or not (false).\r
+ /// </returns>\r
+ /**/\r
+ _Pairib insert(const value_type& _Value)\r
+ {\r
+ return _Insert(_Value);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts a value into the concurrent container.\r
+ /// </summary>\r
+ /// <typeparam name="_Valty">\r
+ /// The type of the value inserted into the map.\r
+ /// </typeparm>\r
+ /// <param name="_Value">\r
+ /// The value to insert.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// A <see cref="pair Class">pair</see> where the first object is an iterator into the container at the insertion point and the \r
+ /// second object is a bool indicating whether the value was inserted (true) or not (false).\r
+ /// </returns>\r
+ /**/\r
+ template<class _Valty>\r
+ _Pairib insert(_Valty&& _Value)\r
+ {\r
+ return _Insert(std::forward<_Valty>(_Value));\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts a value into the concurrent container.\r
+ /// </summary>\r
+ /// <param name="_Value">\r
+ /// The value to insert.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// <para>The current implementation ignores the first <c>const_iterator</c> argument. It exists for\r
+ /// similarity with the <see cref="unordered_map Class">unordered_map</see>, and hints to a location to start the search\r
+ /// for an insertion point.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator pointing to the insertion point of the object. If the key already exists in the container\r
+ /// and the container does not support multiple keys, an iterator pointing to the duplicate key location in \r
+ /// the map is returned. \r
+ /// </returns>\r
+ /**/\r
+ iterator insert(const_iterator, const value_type& _Value)\r
+ {\r
+ // Ignore hint\r
+ return insert(_Value).first;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts a value into the concurrent container.\r
+ /// </summary>\r
+ /// <typeparam name="_Valty">\r
+ /// The type of the value inserted into the map.\r
+ /// </typeparm>\r
+ /// <param name="_Value">\r
+ /// The value to insert.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// <para>The current implementation ignores the first <c>const_iterator</c> argument. It exists for\r
+ /// similarity with the <see cref="unordered_map Class">unordered_map</see>, and hints to a location to start the search\r
+ /// for an insertion point.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator pointing to the insertion point of the object. If the key already exists in the container\r
+ /// and the container does not support multiple keys, an iterator pointing to the duplicate key location in \r
+ /// the map is returned.\r
+ /// </returns>\r
+ /**/\r
+ template<class _Valty>\r
+ typename std::tr1::enable_if<!std::tr1::is_same<const_iterator, \r
+ typename std::tr1::remove_reference<_Valty>::type>::value, iterator>::type\r
+ insert(const_iterator, _Valty&& _Value)\r
+ {\r
+ // Ignore hint\r
+ return insert(std::forward<_Valty>(_Value)).first;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Inserts a set of values into the concurrent container from an iterator.\r
+ /// </summary>\r
+ /// <typeparam name="_Iterator">\r
+ /// The iterator type used for insertion.\r
+ /// </typeparm>\r
+ /// <param name="_First">\r
+ /// The input iterator pointing to the beginning location.\r
+ /// </param>\r
+ /// <param name="_Last">\r
+ /// The input iterator pointing to the end location.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /**/\r
+ template<class _Iterator>\r
+ void insert(_Iterator _First, _Iterator _Last)\r
+ {\r
+ for (_Iterator _I = _First; _I != _Last; _I++)\r
+ {\r
+ insert(*_I);\r
+ }\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases an element from the concurrent container.\r
+ /// </summary>\r
+ /// <param name="_Where">\r
+ /// A <c>const_iterator</c> pointing to the element to erase.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is not concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator pointing to the location immediately following the deleted object in the container.\r
+ /// </returns>\r
+ /**/\r
+ iterator unsafe_erase(const_iterator _Where)\r
+ {\r
+ return _Erase(_Where);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases multiple elements from the concurrent container.\r
+ /// </summary>\r
+ /// <param name="_First">\r
+ /// A <c>const_iterator</c> pointing to the first element to erase.\r
+ /// </param>\r
+ /// <param name="_Last">\r
+ /// A <c>const_iterator</c> pointing to the location after the last element to erase,.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is not concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator pointing to the location immediately following the deleted object(s) in the container.\r
+ /// </returns>\r
+ /**/\r
+ iterator unsafe_erase(const_iterator _First, const_iterator _Last)\r
+ {\r
+ while (_First != _Last)\r
+ {\r
+ unsafe_erase(_First++);\r
+ }\r
+\r
+ return _M_split_ordered_list._Get_iterator(_First);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Erases an element from the concurrent container.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The value to erase from the concurrent container.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is not concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// A count of the number of keys removed from the concurrent_unordered_map. \r
+ /// </returns>\r
+ /**/\r
+ size_type unsafe_erase(const key_type& _Keyval)\r
+ {\r
+ _Pairii _Where = equal_range(_Keyval);\r
+ size_type _Count = _Distance(_Where.first, _Where.second);\r
+ unsafe_erase(_Where.first, _Where.second);\r
+ return _Count;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Swaps the contents of two concurrent containers.\r
+ /// </summary>\r
+ /// <param name="_Right">\r
+ /// The container to swap elements from.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is not concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// Throws an <see cref="invalid_argument Class">invalid_argument</see> exception if the swap is being\r
+ /// performed on unequal allocators.\r
+ /// </returns>\r
+ /**/\r
+ void swap(_Concurrent_hash& _Right)\r
+ {\r
+ if (this != &_Right)\r
+ {\r
+ std::_Swap_adl(_M_comparator, _Right._M_comparator);\r
+ _M_split_ordered_list.swap(_Right._M_split_ordered_list);\r
+ _Swap_buckets(_Right);\r
+ std::swap(_M_number_of_buckets, _Right._M_number_of_buckets);\r
+ std::swap(_M_maximum_bucket_size, _Right._M_maximum_bucket_size);\r
+ }\r
+ }\r
+\r
+ // Observers\r
+ /// <summary>\r
+ /// Clears all the objects in the concurrent container.\r
+ /// </summary>\r
+ /// <remarks>\r
+ /// This function is not concurrency safe.\r
+ /// </remarks>\r
+ /**/\r
+ void clear()\r
+ {\r
+ // Clear list\r
+ _M_split_ordered_list.clear();\r
+\r
+ // Clear buckets\r
+ for (size_type _Index = 0; _Index < _Pointers_per_table; _Index++)\r
+ {\r
+ if (_M_buckets[_Index] != NULL)\r
+ {\r
+ size_type _Seg_size = _Segment_size(_Index);\r
+ for (size_type _Index2 = 0; _Index2 < _Seg_size; _Index2++)\r
+ {\r
+ _M_allocator.destroy(&_M_buckets[_Index][_Index2]);\r
+ }\r
+ _M_allocator.deallocate(_M_buckets[_Index], _Seg_size);\r
+ }\r
+ }\r
+\r
+ // memset all the buckets to zero and initialize the dummy node 0\r
+ _Init();\r
+ }\r
+\r
+ // Lookup\r
+ /// <summary>\r
+ /// Searches the concurrent container for a specific key.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key to search for.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// An iterator pointing to the location of the searched for key, or points to end() if not found.\r
+ /// </returns>\r
+ /**/\r
+ iterator find(const key_type& _Keyval)\r
+ {\r
+ return _Find(_Keyval);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Searches the concurrent container for a specific key.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key to search for.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// A const_iterator pointing to the location of the searched for key.\r
+ /// </returns>\r
+ /**/\r
+ const_iterator find(const key_type& _Keyval) const\r
+ {\r
+ return _Find(_Keyval);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Counts the number of times a specific key appears in the container.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key to count.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is concurrency safe.\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// The number of times the key appears in the container.\r
+ /// </returns>\r
+ /**/\r
+ size_type count(const key_type& _Keyval) const\r
+ {\r
+ size_type _Count = 0;\r
+ const_iterator _It = _Find(_Keyval);\r
+ for (;_It != end() && !_M_comparator(_Key_function(*_It), _Keyval); _It++)\r
+ {\r
+ _Count++;\r
+ }\r
+ return _Count;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Finds the iterators pointing to the being and end locations a specific key appears in the container.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key to search for.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is concurrency safe. \r
+ /// <para>It is possible that concurrent inserts may cause the additional keys to be inserted after the \r
+ /// begin iterator and before the end iterator.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// A <see cref="pair Class">pair</see> where the first element is an iterator to the beginning and the second element\r
+ /// is an iterator to the end of the range..\r
+ /// </returns>\r
+ /**/\r
+ _Pairii equal_range(const key_type& _Keyval)\r
+ {\r
+ return _Equal_range(_Keyval);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Finds the const_iterators pointing to the being and end locations a specific key appears in the container.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The key to search for.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// This function is concurrency safe. \r
+ /// <para>It is possible that concurrent inserts may cause the additional keys to be inserted after the \r
+ /// begin iterator and before the end iterator.</para>\r
+ /// </remarks>\r
+ /// <returns>\r
+ /// A <see cref="pair Class">pair</see> where the first element is a const_iterator to the beginning and the second element\r
+ /// is a const_iterator to the end of the range.\r
+ /// </returns>\r
+ /**/\r
+ _Paircc equal_range(const key_type& _Keyval) const\r
+ {\r
+ return _Equal_range(_Keyval);\r
+ }\r
+\r
+ // Bucket interface - for debugging \r
+ /// <summary>\r
+ /// Returns the current number of buckets in this container.\r
+ /// </summary>\r
+ /// <returns>\r
+ /// The current number of buckets in this container.\r
+ /// </returns>\r
+ /**/\r
+ size_type unsafe_bucket_count() const\r
+ {\r
+ return _M_number_of_buckets;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the maximum number of buckets in this container.\r
+ /// </summary>\r
+ /// <returns>\r
+ /// The maximum number of buckets in this container.\r
+ /// </returns>\r
+ /**/\r
+ size_type unsafe_max_bucket_count() const\r
+ {\r
+ return _Segment_size(_Pointers_per_table-1);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the number of items in a specific bucket of this container.\r
+ /// </summary>\r
+ /// <param name="_Bucket">\r
+ /// The bucket to search for.\r
+ /// </param>\r
+ /// <returns>\r
+ /// The current number of buckets in this container.\r
+ /// </returns>\r
+ /**/\r
+ size_type unsafe_bucket_size(size_type _Bucket)\r
+ {\r
+ size_type _Count = 0;\r
+\r
+ if (!_Is_initialized(_Bucket))\r
+ {\r
+ return _Count;\r
+ }\r
+\r
+ _Full_iterator _Iterator = _Get_bucket(_Bucket);\r
+ _Iterator++;\r
+\r
+ for (; _Iterator != _M_split_ordered_list._End() && !_Iterator._Mynode()->_Is_dummy(); _Iterator++)\r
+ {\r
+ _Count++;\r
+ }\r
+\r
+ return _Count;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the bucket index that a specific key maps to in this container.\r
+ /// </summary>\r
+ /// <param name="_Keyval">\r
+ /// The element key being searched for.\r
+ /// </param>\r
+ /// <returns>\r
+ /// The bucket index for the key in this container.\r
+ /// </returns>\r
+ /**/\r
+ size_type unsafe_bucket(const key_type& _Keyval) const\r
+ {\r
+ _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
+ size_type _Bucket = _Order_key % _M_number_of_buckets;\r
+ return _Bucket;\r
+ }\r
+\r
+ // If the bucket is initialized, return a first non-dummy element in it\r
+\r
+ /// <summary>\r
+ /// Returns an iterator to the first element in this container for a specific bucket.\r
+ /// </summary>\r
+ /// <param name="_Bucket">\r
+ /// The bucket index.\r
+ /// </param>\r
+ /// <returns>\r
+ /// An iterator pointing to the beginning of the bucket.\r
+ /// </returns>\r
+ /**/\r
+ local_iterator unsafe_begin(size_type _Bucket)\r
+ {\r
+ // It is possible the bucket being searched for has not yet been initialized\r
+ if (!_Is_initialized(_Bucket))\r
+ {\r
+ _Initialize_bucket(_Bucket);\r
+ }\r
+\r
+ _Full_iterator _Iterator = _Get_bucket(_Bucket);\r
+ return _M_split_ordered_list._Get_first_real_iterator(_Iterator);\r
+ }\r
+\r
+ // If the bucket is initialized, return a first non-dummy element in it\r
+\r
+ /// <summary>\r
+ /// Returns a const_iterator to the first element in this container for a specific bucket.\r
+ /// </summary>\r
+ /// <param name="_Bucket">\r
+ /// The bucket index.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A const_iterator pointing to the beginning of the bucket.\r
+ /// </returns>\r
+ /**/\r
+ const_local_iterator unsafe_begin(size_type _Bucket) const\r
+ {\r
+ // It is possible the bucket being searched for has not yet been initialized\r
+ if (!_Is_initialized(_Bucket))\r
+ {\r
+ _Initialize_bucket(_Bucket);\r
+ }\r
+\r
+\r
+ _Full_const_iterator _Iterator = _Get_bucket(_Bucket);\r
+ return _M_split_ordered_list._Get_first_real_iterator(_Iterator);\r
+ }\r
+\r
+ // Returns the iterator after the last non-dummy element in the bucket\r
+\r
+ /// <summary>\r
+ /// Returns an iterator to the last element in this container for a specific bucket.\r
+ /// </summary>\r
+ /// <param name="_Bucket">\r
+ /// The bucket index.\r
+ /// </param>\r
+ /// <returns>\r
+ /// An iterator pointing to the end of the bucket.\r
+ /// </returns>\r
+ /**/\r
+ local_iterator unsafe_end(size_type _Bucket)\r
+ {\r
+ // If we've increased the number of buckets, there's a chance the intermediate dummy\r
+ // node marking the end of this bucket has not yet been lazily initialized.\r
+ // Inserting from from _M_number_of_buckets/2 to _M_number_of_buckets will recursively\r
+ // initialize all the dummy nodes in the map.\r
+ for(size_type _Bucket_index = _M_number_of_buckets >> 1; _Bucket_index < _M_number_of_buckets; _Bucket_index++)\r
+ {\r
+ if (!_Is_initialized(_Bucket_index))\r
+ {\r
+ _Initialize_bucket(_Bucket_index);\r
+ }\r
+ }\r
+\r
+ _Full_iterator _Iterator = _Get_bucket(_Bucket);\r
+ \r
+ // Find the end of the bucket, denoted by the dummy element\r
+ do\r
+ {\r
+ _Iterator++;\r
+ }\r
+ while(_Iterator != _M_split_ordered_list._End() && !_Iterator._Mynode()->_Is_dummy());\r
+\r
+ // Return the first real element past the end of the bucket\r
+ return _M_split_ordered_list._Get_first_real_iterator(_Iterator);\r
+ }\r
+\r
+ // Returns the iterator after the last non-dummy element in the bucket\r
+\r
+ /// <summary>\r
+ /// Returns a const_iterator to the last element in this container for a specific bucket.\r
+ /// </summary>\r
+ /// <param name="_Bucket">\r
+ /// The bucket index.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A const_iterator pointing to the end of the bucket.\r
+ /// </returns>\r
+ /**/\r
+ const_local_iterator unsafe_end(size_type _Bucket) const\r
+ {\r
+ // If we've increased the number of buckets, there's a chance the intermediate dummy\r
+ // node marking the end of this bucket has not yet been lazily initialized.\r
+ // Inserting from from _M_number_of_buckets/2 to _M_number_of_buckets will recursively\r
+ // initialize all the dummy nodes in the map.\r
+ for(size_type _Bucket_index = _M_number_of_buckets >> 1; _Bucket_index < _M_number_of_buckets; _Bucket_index++)\r
+ {\r
+ if (!_Is_initialized(_Bucket_index))\r
+ {\r
+ _Initialize_bucket(_Bucket_index);\r
+ }\r
+ }\r
+\r
+ _Full_const_iterator _Iterator = _Get_bucket(_Bucket);\r
+ \r
+ // Find the end of the bucket, denoted by the dummy element\r
+ do\r
+ {\r
+ _Iterator++;\r
+ }\r
+ while(_Iterator != _M_split_ordered_list._End() && !_Iterator._Mynode()->_Is_dummy());\r
+\r
+ // Return the first real element past the end of the bucket\r
+ return _M_split_ordered_list._Get_first_real_iterator(_Iterator);\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns a const_iterator to the first element in this container for a specific bucket.\r
+ /// </summary>\r
+ /// <param name="_Bucket">\r
+ /// The bucket index.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A const_iterator pointing to the beginning of the bucket.\r
+ /// </returns>\r
+ /**/\r
+ const_local_iterator unsafe_cbegin(size_type _Bucket) const\r
+ {\r
+ return ((const _Mytype *) this)->begin();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns a const_iterator to the last element in this container for a specific bucket.\r
+ /// </summary>\r
+ /// <param name="_Bucket">\r
+ /// The bucket index.\r
+ /// </param>\r
+ /// <returns>\r
+ /// A const_iterator pointing to the end of the bucket.\r
+ /// </returns>\r
+ /**/\r
+ const_local_iterator unsafe_cend(size_type _Bucket) const\r
+ {\r
+ return ((const _Mytype *) this)->end();\r
+ }\r
+\r
+ // Hash policy\r
+ /// <summary>\r
+ /// Computes and returns the current load factor of the container. \r
+ /// The load factor is the number of elements in the container divided by the number of buckets.\r
+ /// </summary>\r
+ /// <returns>\r
+ /// The load factor for the container\r
+ /// </returns>\r
+ /**/\r
+ float load_factor() const\r
+ {\r
+ return (float) size() / (float) unsafe_bucket_count();\r
+ }\r
+\r
+ /// <summary>\r
+ /// Returns the maximum load factor of the container. The maximum load factor is the \r
+ /// largest number of elements than can be in any bucket before the container grows its \r
+ /// internal table.\r
+ /// </summary>\r
+ /// <returns>\r
+ /// The maximum load factor for the container\r
+ /// </returns>\r
+ /**/\r
+ float max_load_factor() const\r
+ {\r
+ return _M_maximum_bucket_size;\r
+ }\r
+\r
+ /// <summary>\r
+ /// Sets the maximum load factor of the container to a specific value.\r
+ /// </summary>\r
+ /// <param name="_Newmax">\r
+ /// The desired load factor for this container.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// Throws an <see cref="out_of_range Class">out_of_range</see> exception if the load factor is invalid (NaN or negative)\r
+ /// </remarks>\r
+ /**/\r
+ void max_load_factor(float _Newmax)\r
+ {\r
+ // The _Newmax != _Newmax is a check for NaN, because NaN is != to itself\r
+ if (_Newmax != _Newmax || _Newmax < 0)\r
+ {\r
+ throw std::out_of_range("invalid hash load factor");\r
+ }\r
+\r
+ _M_maximum_bucket_size = _Newmax;\r
+ }\r
+\r
+ // This function is a noop, because the underlying split-ordered list\r
+ // is already sorted, so an increase in the bucket number will be\r
+ // reflected next time this bucket is touched.\r
+\r
+ /// <summary>\r
+ /// Sets the the number of buckets for the container to a specific value.\r
+ /// </summary>\r
+ /// <param name="_Buckets">\r
+ /// The desired number of buckets.\r
+ /// </param>\r
+ /// <remarks>\r
+ /// The number of buckets must be a power of 2. If not a power of 2, it will be rounded up to\r
+ /// the next largest power of 2.\r
+ /// <para>Throws an <see cref="out_of_range Class">out_of_range</see> exception if the number of buckets \r
+ /// is invalid (0 or greater than the maximum number of buckets)</para>\r
+ /// </remarks>\r
+ /**/\r
+ void rehash(size_type _Buckets)\r
+ {\r
+ size_type _Current_buckets = _M_number_of_buckets;\r
+\r
+ if (_Current_buckets > _Buckets)\r
+ {\r
+ return;\r
+ }\r
+ else if (_Buckets <= 0 || _Buckets > unsafe_max_bucket_count())\r
+ {\r
+ throw std::out_of_range("invalid number of buckets");\r
+ }\r
+ // Round up the number of buckets to the next largest power of 2\r
+ _M_number_of_buckets = ((size_type) 1) << _Get_msb(_Buckets*2-1);\r
+ }\r
+\r
+private:\r
+\r
+ // Initialize the hash and keep the first bucket open\r
+ void _Init()\r
+ {\r
+ // Allocate an array of segment pointers\r
+ memset(_M_buckets, 0, _Pointers_per_table * sizeof(void *));\r
+\r
+ // Insert the first element in the split-ordered list\r
+ _Full_iterator _Dummy_node = _M_split_ordered_list._Begin();\r
+ _Set_bucket(0, _Dummy_node);\r
+ }\r
+\r
+ void _Copy(const _Mytype& _Right)\r
+ {\r
+ clear();\r
+\r
+ _M_maximum_bucket_size = _Right._M_maximum_bucket_size;\r
+ _M_number_of_buckets = _Right._M_number_of_buckets;\r
+\r
+ try\r
+ {\r
+ insert(_Right.begin(), _Right.end());\r
+ _M_comparator = _Right._M_comparator;\r
+ }\r
+ catch(...)\r
+ {\r
+ _M_split_ordered_list.clear();\r
+ throw;\r
+ }\r
+ }\r
+\r
+ void _Swap_buckets(_Concurrent_hash& _Right)\r
+ {\r
+ if (_M_allocator == _Right._M_allocator)\r
+ {\r
+ // Swap all node segments\r
+ for (size_type _Index = 0; _Index < _Pointers_per_table; _Index++)\r
+ {\r
+ _Full_iterator * _Iterator_pointer = _M_buckets[_Index];\r
+ _M_buckets[_Index] = _Right._M_buckets[_Index];\r
+ _Right._M_buckets[_Index] = _Iterator_pointer;\r
+ }\r
+ }\r
+ else\r
+ {\r
+ throw std::invalid_argument("swap is invalid on non-equal allocators");\r
+ }\r
+ }\r
+\r
+ // Hash APIs\r
+ size_type _Distance(const_iterator _First, const_iterator _Last) const\r
+ {\r
+ size_type _Num = 0;\r
+\r
+ for (const_iterator _Iterator = _First; _Iterator != _Last; _Iterator++)\r
+ {\r
+ _Num++;\r
+ }\r
+\r
+ return _Num;\r
+ }\r
+\r
+ // Insert an element in the hash given its value\r
+ template<typename _ValTy>\r
+ _Pairib _Insert(_ValTy&& _Value)\r
+ {\r
+ _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Key_function(_Value));\r
+ size_type _Bucket = _Order_key % _M_number_of_buckets;\r
+\r
+ // If bucket is empty, initialize it first\r
+ if (!_Is_initialized(_Bucket))\r
+ {\r
+ _Initialize_bucket(_Bucket);\r
+ }\r
+\r
+ long _New_count;\r
+ _Order_key = _Split_order_regular_key(_Order_key);\r
+ _Full_iterator _Iterator = _Get_bucket(_Bucket);\r
+ _Full_iterator _Last = _M_split_ordered_list._End();\r
+ _Full_iterator _Where = _Iterator;\r
+ _Nodeptr _New_node = _M_split_ordered_list._Buynode(_Order_key, std::forward<_ValTy>(_Value));\r
+\r
+ _ASSERT_EXPR(_Where != _Last, L"Invalid head node");\r
+\r
+ // First node is a dummy node\r
+ _Where++;\r
+\r
+ for (;;)\r
+ {\r
+ if (_Where == _Last || _Mylist::_Get_key(_Where) > _Order_key)\r
+ {\r
+ // Try to insert it in the right place\r
+ _Pairib _Result = _M_split_ordered_list._Insert(_Iterator, _Where, _New_node, &_New_count);\r
+ \r
+ if (_Result.second)\r
+ {\r
+ // Insertion succeeded, adjust the table size, if needed\r
+ _Adjust_table_size(_New_count, _M_number_of_buckets);\r
+ return _Result;\r
+ }\r
+ else\r
+ {\r
+ // Insertion failed: either the same node was inserted by another thread, or\r
+ // another element was inserted at exactly the same place as this node.\r
+ // Proceed with the search from the previous location where order key was\r
+ // known to be larger (note: this is legal only because there is no safe\r
+ // concurrent erase operation supported).\r
+ _Where = _Iterator;\r
+ _Where++;\r
+ continue;\r
+ }\r
+ }\r
+ else if (!_M_allow_multimapping && _Mylist::_Get_key(_Where) == _Order_key && \r
+ _M_comparator(_Key_function(*_Where), _Key_function(_New_node->_M_element)) == 0)\r
+ {\r
+ // If the insert failed (element already there), then delete the new one\r
+ _M_split_ordered_list._Erase(_New_node);\r
+\r
+ // Element already in the list, return it\r
+ return _Pairib(_M_split_ordered_list._Get_iterator(_Where), false);\r
+ }\r
+\r
+ // Move the iterator forward\r
+ _Iterator = _Where;\r
+ _Where++;\r
+ }\r
+ }\r
+ // Find the element in the split-ordered list\r
+ iterator _Find(const key_type& _Keyval)\r
+ {\r
+ _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
+ size_type _Bucket = _Order_key % _M_number_of_buckets;\r
+\r
+ // If _Bucket is empty, initialize it first\r
+ if (!_Is_initialized(_Bucket))\r
+ {\r
+ _Initialize_bucket(_Bucket);\r
+ }\r
+\r
+ _Order_key = _Split_order_regular_key(_Order_key);\r
+ _Full_iterator _Last = _M_split_ordered_list._End();\r
+\r
+ for (_Full_iterator _Iterator = _Get_bucket(_Bucket); _Iterator != _Last; _Iterator++)\r
+ {\r
+ if (_Mylist::_Get_key(_Iterator) > _Order_key)\r
+ {\r
+ // If the order key is smaller than the current order key, the element\r
+ // is not in the hash.\r
+ return end();\r
+ }\r
+ else if (_Mylist::_Get_key(_Iterator) == _Order_key)\r
+ {\r
+ // The fact that order keys match does not mean that the element is found.\r
+ // Key function comparison has to be performed to check whether this is the\r
+ // right element. If not, keep searching while order key is the same.\r
+ if (!_M_comparator(_Key_function(*_Iterator), _Keyval))\r
+ {\r
+ return _M_split_ordered_list._Get_iterator(_Iterator);\r
+ }\r
+ }\r
+ }\r
+\r
+ return end();\r
+ }\r
+\r
+ // Find the element in the split-ordered list\r
+ const_iterator _Find(const key_type& _Keyval) const\r
+ {\r
+ _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
+ size_type _Bucket = _Order_key % _M_number_of_buckets;\r
+\r
+ // If _Bucket has not been initialized, keep searching up for a parent bucket\r
+ // that has been initialized. Worst case is the entire map will be read.\r
+ while (!_Is_initialized(_Bucket))\r
+ {\r
+ _Bucket = _Get_parent(_Bucket);\r
+ }\r
+\r
+ _Order_key = _Split_order_regular_key(_Order_key);\r
+ _Full_const_iterator _Last = _M_split_ordered_list._End();\r
+\r
+ for (_Full_const_iterator _Iterator = _Get_bucket(_Bucket); _Iterator != _Last; _Iterator++)\r
+ {\r
+ if (_Mylist::_Get_key(_Iterator) > _Order_key)\r
+ {\r
+ // If the order key is smaller than the current order key, the element\r
+ // is not in the hash.\r
+ return end();\r
+ }\r
+ else if (_Mylist::_Get_key(_Iterator) == _Order_key)\r
+ {\r
+ // The fact that order keys match does not mean that the element is found.\r
+ // Key function comparison has to be performed to check whether this is the\r
+ // right element. If not, keep searching while order key is the same.\r
+ if (!_M_comparator(_Key_function(*_Iterator), _Keyval))\r
+ {\r
+ return _M_split_ordered_list._Get_iterator(_Iterator);\r
+ }\r
+ }\r
+ }\r
+\r
+ return end();\r
+ }\r
+\r
+ // Erase an element from the list. This is not a concurrency safe function.\r
+ iterator _Erase(const_iterator _Iterator)\r
+ {\r
+ key_type _Keyval = _Key_function(*_Iterator);\r
+ _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
+ size_type _Bucket = _Order_key % _M_number_of_buckets;\r
+\r
+ // If bucket is empty, initialize it first\r
+ if (!_Is_initialized(_Bucket))\r
+ {\r
+ _Initialize_bucket(_Bucket);\r
+ }\r
+\r
+ _Order_key = _Split_order_regular_key(_Order_key);\r
+\r
+ _Full_iterator _Previous = _Get_bucket(_Bucket);\r
+ _Full_iterator _Last = _M_split_ordered_list._End();\r
+ _Full_iterator _Where = _Previous;\r
+\r
+ _ASSERT_EXPR(_Where != _Last, L"Invalid head node");\r
+\r
+ // First node is a dummy node\r
+ _Where++;\r
+\r
+ for (;;)\r
+ {\r
+ if (_Where == _Last)\r
+ {\r
+ return end();\r
+ }\r
+ else if (_M_split_ordered_list._Get_iterator(_Where) == _Iterator)\r
+ {\r
+ return _M_split_ordered_list._Erase(_Previous, _Iterator);\r
+ }\r
+\r
+ // Move the iterator forward\r
+ _Previous = _Where;\r
+ _Where++;\r
+ }\r
+ }\r
+\r
+ // Return the [begin, end) pair of iterators with the same key values.\r
+ // This operation makes sense only if mapping is many-to-one.\r
+ _Pairii _Equal_range(const key_type& _Keyval)\r
+ {\r
+ _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
+ size_type _Bucket = _Order_key % _M_number_of_buckets;\r
+\r
+ // If _Bucket is empty, initialize it first\r
+ if (!_Is_initialized(_Bucket))\r
+ {\r
+ _Initialize_bucket(_Bucket);\r
+ }\r
+\r
+ _Order_key = _Split_order_regular_key(_Order_key);\r
+ _Full_iterator _Last = _M_split_ordered_list._End();\r
+\r
+ for (_Full_iterator _Iterator = _Get_bucket(_Bucket); _Iterator != _Last; _Iterator++)\r
+ {\r
+ if (_Mylist::_Get_key(_Iterator) > _Order_key)\r
+ {\r
+ // There is no element with the given key\r
+ return _Pairii(end(), end());\r
+ }\r
+ else if (_Mylist::_Get_key(_Iterator) == _Order_key && !_M_comparator(_Key_function(*_Iterator), _Keyval))\r
+ {\r
+ iterator _Begin = _M_split_ordered_list._Get_iterator(_Iterator);\r
+ iterator _End= _Begin;\r
+\r
+ for (;_End != end() && !_M_comparator(_Key_function(*_End), _Keyval); _End++)\r
+ {\r
+ }\r
+\r
+ return _Pairii(_Begin, _End);\r
+ }\r
+ }\r
+\r
+ return _Pairii(end(), end());\r
+ }\r
+\r
+ // Return the [begin, end) pair of const iterators with the same key values.\r
+ // This operation makes sense only if mapping is many-to-one.\r
+ _Paircc _Equal_range(const key_type& _Keyval) const\r
+ {\r
+ _Split_order_key _Order_key = (_Split_order_key) _M_comparator(_Keyval);\r
+ size_type _Bucket = _Order_key % _M_number_of_buckets;\r
+\r
+ // If _Bucket has not been initialized, keep searching up for a parent bucket\r
+ // that has been initialized. Worst case is the entire map will be read.\r
+ while (!_Is_initialized(_Bucket))\r
+ {\r
+ _Bucket = _Get_parent(_Bucket);\r
+ }\r
+\r
+ _Order_key = _Split_order_regular_key(_Order_key);\r
+ _Full_const_iterator _Last = _M_split_ordered_list._End();\r
+\r
+ for (_Full_const_iterator _Iterator = _Get_bucket(_Bucket); _Iterator != _Last; _Iterator++)\r
+ {\r
+ if (_Mylist::_Get_key(_Iterator) > _Order_key)\r
+ {\r
+ // There is no element with the given key\r
+ return _Paircc(end(), end());\r
+ }\r
+ else if (_Mylist::_Get_key(_Iterator) == _Order_key && !_M_comparator(_Key_function(*_Iterator), _Keyval))\r
+ {\r
+ const_iterator _Begin = _M_split_ordered_list._Get_iterator(_Iterator);\r
+ const_iterator _End = _Begin;\r
+\r
+ for (; _End != end() && !_M_comparator(_Key_function(*_End), _Keyval); _End++)\r
+ {\r
+ }\r
+\r
+ return _Paircc(_Begin, _End);\r
+ }\r
+ }\r
+\r
+ return _Paircc(end(), end());\r
+ }\r
+\r
+ // Bucket APIs\r
+ void _Initialize_bucket(size_type _Bucket)\r
+ {\r
+ // Bucket 0 has no parent. Initialize it and return.\r
+ if (_Bucket == 0)\r
+ {\r
+ _Init();\r
+ return;\r
+ }\r
+\r
+ size_type _Parent_bucket = _Get_parent(_Bucket);\r
+\r
+ // All _Parent_bucket buckets have to be initialized before this bucket is\r
+ if (!_Is_initialized(_Parent_bucket))\r
+ {\r
+ _Initialize_bucket(_Parent_bucket);\r
+ }\r
+\r
+ _Full_iterator _Parent = _Get_bucket(_Parent_bucket);\r
+\r
+ // Create a dummy first node in this bucket\r
+ _Full_iterator _Dummy_node = _M_split_ordered_list._Insert_dummy(_Parent, _Split_order_dummy_key(_Bucket));\r
+ _Set_bucket(_Bucket, _Dummy_node);\r
+ }\r
+\r
+ void _Adjust_table_size(size_type _Total_elements, size_type _Current_size)\r
+ {\r
+ // Grow the table by a factor of 2 if possible and needed\r
+ if (((float) _Total_elements / (float) _Current_size) > _M_maximum_bucket_size)\r
+ {\r
+ // Double the size of the hash only if size has not changed inbetween loads\r
+ _InterlockedCompareExchangeSizeT(&_M_number_of_buckets, 2 * _Current_size, _Current_size);\r
+ }\r
+ }\r
+\r
+ size_type _Get_parent(size_type _Bucket) const\r
+ {\r
+ // Unsets bucket's most significant turned-on bit\r
+ unsigned char _Msb = _Get_msb(_Bucket);\r
+ return _Bucket & ~(1 << _Msb);\r
+ }\r
+\r
+\r
+ // Dynamic sized array (segments)\r
+\r
+ _Full_iterator _Get_bucket(size_type _Bucket) const\r
+ {\r
+ size_type _Segment = _Segment_index_of(_Bucket);\r
+ _Bucket -= _Segment_base(_Segment);\r
+ return _M_buckets[_Segment][_Bucket];\r
+ }\r
+\r
+ void _Set_bucket(size_type _Bucket, _Full_iterator _Dummy_head)\r
+ {\r
+ size_type _Segment = _Segment_index_of(_Bucket);\r
+ _Bucket -= _Segment_base(_Segment);\r
+\r
+ if (_M_buckets[_Segment] == NULL)\r
+ {\r
+ size_type _Seg_size = _Segment_size(_Segment);\r
+ _Full_iterator * _New_segment = _M_allocator.allocate(_Seg_size);\r
+ _Uninitialized_default_fill_n(_New_segment, _Seg_size, (_Full_iterator *) 0, _M_allocator);\r
+ if (_InterlockedCompareExchangePointer((void * volatile *) &_M_buckets[_Segment], _New_segment, NULL) != NULL)\r
+ {\r
+ _M_allocator.deallocate(_New_segment, _Seg_size);\r
+ }\r
+ }\r
+ _M_buckets[_Segment][_Bucket] = _Dummy_head;\r
+ }\r
+\r
+ bool _Is_initialized(size_type _Bucket) const\r
+ {\r
+ size_type _Segment = _Segment_index_of(_Bucket);\r
+ _Bucket -= _Segment_base(_Segment);\r
+\r
+ if (_M_buckets[_Segment] == NULL)\r
+ {\r
+ return false;\r
+ }\r
+\r
+ _Full_iterator _Iterator = _M_buckets[_Segment][_Bucket];\r
+ return (_Iterator._Mynode() != NULL);\r
+ }\r
+\r
+ // Utilities for keys\r
+\r
+ _Split_order_key _Reverse(_Map_key _Order_key) const\r
+ {\r
+ _Split_order_key _Reversed_order_key;\r
+\r
+ unsigned char * _Original = (unsigned char *) &_Order_key;\r
+ unsigned char * _Reversed = (unsigned char *) &_Reversed_order_key;\r
+\r
+ int _Size = sizeof(_Map_key);\r
+ for (int _Index = 0; _Index < _Size; _Index++)\r
+ {\r
+ _Reversed[_Size - _Index - 1] = _Reverse_byte(_Original[_Index]);\r
+ }\r
+\r
+ return _Reversed_order_key;\r
+ }\r
+\r
+ // A regular order key has its original hash value reversed and the last bit set\r
+ _Split_order_key _Split_order_regular_key(_Map_key _Order_key) const\r
+ {\r
+ return _Reverse(_Order_key) | 0x1;\r
+ }\r
+\r
+ // A dummy order key has its original hash value reversed and the last bit unset\r
+ _Split_order_key _Split_order_dummy_key(_Map_key _Order_key) const\r
+ {\r
+ return _Reverse(_Order_key) & ~(0x1);\r
+ }\r
+\r
+ // Shared variables\r
+ _Full_iterator * _M_buckets[_Pointers_per_table]; // The segment table\r
+ _Mylist _M_split_ordered_list; // List where all the elements are kept\r
+ typename allocator_type::template rebind<_Full_iterator>::other _M_allocator; // Allocator object for segments\r
+ size_type _M_number_of_buckets; // Current table size\r
+ float _M_maximum_bucket_size; // Maximum size of the bucket\r
+};\r
+\r
+#pragma warning(pop) // warning 4127 -- while (true) has a constant expression in it\r
+\r
+} // namespace details;\r
+} // namespace Concurrency\r
--- /dev/null
+/***\r
+* ==++==\r
+*\r
+* Copyright (c) Microsoft Corporation. All rights reserved.\r
+* \r
+* ==--==\r
+* =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+\r
+*\r
+* internal_split_ordered_list.h\r
+*\r
+* =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\r
+****/\r
+#pragma once\r
+\r
+// Needed for forward iterators\r
+#include <forward_list>\r
+#include <concrt.h>\r
+\r
+namespace Concurrency\r
+{\r
+namespace details\r
+{\r
+// Split-order list iterators, needed to skip dummy elements\r
+template<class _Mylist>\r
+class _Solist_const_iterator : public std::_Flist_const_iterator<_Mylist>\r
+{\r
+public:\r
+ typedef _Solist_const_iterator<_Mylist> _Myiter;\r
+ typedef std::_Flist_const_iterator<_Mylist> _Mybase;\r
+ typedef std::forward_iterator_tag iterator_category;\r
+\r
+ typedef typename _Mylist::_Nodeptr _Nodeptr;\r
+ typedef typename _Mylist::value_type value_type;\r
+ typedef typename _Mylist::difference_type difference_type;\r
+ typedef typename _Mylist::const_pointer pointer;\r
+ typedef typename _Mylist::const_reference reference;\r
+\r
+ _Solist_const_iterator()\r
+ {\r
+ }\r
+\r
+ _Solist_const_iterator(_Nodeptr _Pnode, const _Mylist * _Plist) : _Mybase(_Pnode, _Plist)\r
+ {\r
+ }\r
+\r
+ typedef _Solist_const_iterator<_Mylist> _Unchecked_type;\r
+\r
+ _Myiter& _Rechecked(_Unchecked_type _Right)\r
+ {\r
+ _Ptr = _Right._Ptr;\r
+ return (*this);\r
+ }\r
+\r
+ _Unchecked_type _Unchecked() const\r
+ {\r
+ return (_Unchecked_type(_Ptr, (_Mylist *)_Getcont()));\r
+ }\r
+\r
+ reference operator*() const\r
+ {\r
+ return ((reference)**(_Mybase *)this);\r
+ }\r
+\r
+ pointer operator->() const\r
+ {\r
+ return (&**this);\r
+ }\r
+\r
+ _Myiter& operator++()\r
+ {\r
+ do\r
+ {\r
+ ++(*(_Mybase *)this);\r
+ }\r
+ while (_Mynode() != NULL && _Mynode()->_Is_dummy());\r
+\r
+ return (*this);\r
+ }\r
+\r
+ _Myiter operator++(int)\r
+ {\r
+ _Myiter _Tmp = *this;\r
+ do\r
+ {\r
+ ++*this;\r
+ }\r
+ while (_Mynode() != NULL && _Mynode()->_Is_dummy());\r
+\r
+ return (_Tmp);\r
+ }\r
+};\r
+\r
+template<class _Mylist> inline\r
+typename _Solist_const_iterator<_Mylist>::_Unchecked_type _Unchecked(_Solist_const_iterator<_Mylist> _Iterator)\r
+{\r
+ return (_Iterator._Unchecked());\r
+}\r
+\r
+template<class _Mylist> inline\r
+_Solist_const_iterator<_Mylist>& _Rechecked(_Solist_const_iterator<_Mylist>& _Iterator,\r
+ typename _Solist_const_iterator<_Mylist>::_Unchecked_type _Right)\r
+{\r
+ return (_Iterator._Rechecked(_Right));\r
+}\r
+\r
+template<class _Mylist>\r
+class _Solist_iterator : public _Solist_const_iterator<_Mylist>\r
+{\r
+public:\r
+ typedef _Solist_iterator<_Mylist> _Myiter;\r
+ typedef _Solist_const_iterator<_Mylist> _Mybase;\r
+ typedef std::forward_iterator_tag iterator_category;\r
+\r
+ typedef typename _Mylist::_Nodeptr _Nodeptr;\r
+ typedef typename _Mylist::value_type value_type;\r
+ typedef typename _Mylist::difference_type difference_type;\r
+ typedef typename _Mylist::pointer pointer;\r
+ typedef typename _Mylist::reference reference;\r
+\r
+ _Solist_iterator()\r
+ {\r
+ }\r
+\r
+ _Solist_iterator(_Nodeptr _Pnode, const _Mylist *_Plist) : _Mybase(_Pnode, _Plist)\r
+ {\r
+ }\r
+\r
+ typedef _Solist_iterator<_Mylist> _Unchecked_type;\r
+\r
+ _Myiter& _Rechecked(_Unchecked_type _Right)\r
+ {\r
+ _Ptr = _Right._Ptr;\r
+ return (*this);\r
+ }\r
+\r
+ _Unchecked_type _Unchecked() const\r
+ {\r
+ return (_Unchecked_type(_Ptr, (_Mylist *)_Getcont()));\r
+ }\r
+\r
+ reference operator*() const\r
+ {\r
+ return ((reference)**(_Mybase *)this);\r
+ }\r
+\r
+ pointer operator->() const\r
+ {\r
+ return (&**this);\r
+ }\r
+\r
+ _Myiter& operator++()\r
+ {\r
+ do\r
+ {\r
+ ++(*(_Mybase *)this);\r
+ }\r
+ while (_Mynode() != NULL && _Mynode()->_Is_dummy());\r
+\r
+ return (*this);\r
+ }\r
+\r
+ _Myiter operator++(int)\r
+ {\r
+ _Myiter _Tmp = *this;\r
+ do\r
+ {\r
+ ++*this;\r
+ }\r
+ while (_Mynode() != NULL && _Mynode()->_Is_dummy());\r
+\r
+ return (_Tmp);\r
+ }\r
+};\r
+\r
+template<class _Mylist> inline\r
+typename _Solist_iterator<_Mylist>::_Unchecked_type _Unchecked(_Solist_iterator<_Mylist> _Iterator)\r
+{\r
+ return (_Iterator._Unchecked());\r
+}\r
+\r
+template<class _Mylist> inline\r
+_Solist_iterator<_Mylist>& _Rechecked(_Solist_iterator<_Mylist>& _Iterator,\r
+ typename _Solist_iterator<_Mylist>::_Unchecked_type _Right)\r
+{\r
+ return (_Iterator._Rechecked(_Right));\r
+}\r
+\r
+// Forward type and class definitions\r
+typedef size_t _Map_key;\r
+typedef _Map_key _Split_order_key;\r
+\r
+template<typename _Element_type, typename _Allocator_type>\r
+class _Split_order_list_node : public std::_Container_base\r
+{\r
+public:\r
+ typedef typename _Allocator_type::template rebind<_Element_type>::other _Allocator_type;\r
+ typedef typename _Allocator_type::size_type size_type;\r
+ typedef typename _Element_type value_type;\r
+\r
+ struct _Node;\r
+ typedef _Node * _Nodeptr;\r
+ typedef _Nodeptr& _Nodepref;\r
+\r
+ // Node that holds the element in a split-ordered list\r
+ struct _Node\r
+ {\r
+ // Initialize the node with the given order key\r
+ void _Init(_Split_order_key _Order_key)\r
+ {\r
+ _M_order_key = _Order_key;\r
+ _M_next = NULL;\r
+ }\r
+\r
+ // Return the order key (needed for hashing)\r
+ _Split_order_key _Get_order_key() const\r
+ {\r
+ return _M_order_key;\r
+ }\r
+\r
+ // Inserts the new element in the list in an atomic fashion\r
+ _Nodeptr _Atomic_set_next(_Nodeptr _New_node, _Nodeptr _Current_node)\r
+ {\r
+ // Try to change the next pointer on the current element to a new element, only if it still points to the cached next\r
+ _Nodeptr _Exchange_node = (_Nodeptr) _InterlockedCompareExchangePointer((void * volatile *) &_M_next, _New_node, _Current_node);\r
+\r
+ if (_Exchange_node == _Current_node)\r
+ {\r
+ // Operation succeeded, return the new node\r
+ return _New_node;\r
+ }\r
+ else\r
+ {\r
+ // Operation failed, return the "interfering" node\r
+ return _Exchange_node;\r
+ }\r
+ }\r
+\r
+ // Checks if this element in the list is a dummy, order enforcing node. Dummy nodes are used by buckets\r
+ // in the hash table to quickly index into the right subsection of the split-ordered list.\r
+ bool _Is_dummy() const\r
+ {\r
+ return (_M_order_key & 0x1) == 0;\r
+ }\r
+\r
+ _Nodeptr _M_next; // Next element in the list\r
+ value_type _M_element; // Element storage\r
+ _Split_order_key _M_order_key; // Order key for this element\r
+ };\r
+\r
+#if _ITERATOR_DEBUG_LEVEL == 0 /*IFSTRIP=IGN*/ \r
+ _Split_order_list_node(_Allocator_type _Allocator) : _M_node_allocator(_Allocator), _M_value_allocator(_Allocator)\r
+ {\r
+ }\r
+#else /* _ITERATOR_DEBUG_LEVEL == 0 */\r
+ _Split_order_list_node(_Allocator_type _Allocator) : _M_node_allocator(_Allocator), _M_value_allocator(_Allocator)\r
+ {\r
+ typename _Allocator_type::template rebind<std::_Container_proxy>::other _Alproxy(_M_node_allocator);\r
+ _Myproxy = _Alproxy.allocate(1);\r
+ _Cons_val(_Alproxy, _Myproxy, std::_Container_proxy());\r
+ _Myproxy->_Mycont = this;\r
+ }\r
+\r
+ ~_Split_order_list_node()\r
+ {\r
+ typename _Allocator_type::template rebind<std::_Container_proxy>::other _Alproxy(_M_node_allocator);\r
+ _Orphan_all();\r
+ _Dest_val(_Alproxy, _Myproxy);\r
+ _Alproxy.deallocate(_Myproxy, 1);\r
+ _Myproxy = 0;\r
+ }\r
+#endif /* _ITERATOR_DEBUG_LEVEL == 0 */\r
+\r
+ _Nodeptr _Myhead; // pointer to head node\r
+ typename _Allocator_type::template rebind<_Node>::other _M_node_allocator; // allocator object for nodes\r
+ _Allocator_type _M_value_allocator; // allocator object for element values\r
+};\r
+\r
+template<typename _Element_type, typename _Allocator_type>\r
+class _Split_order_list_value : public _Split_order_list_node<_Element_type, _Allocator_type>\r
+{\r
+public:\r
+ typedef _Split_order_list_node<_Element_type, _Allocator_type> _Mybase;\r
+ typedef typename _Mybase::_Nodeptr _Nodeptr;\r
+ typedef typename _Mybase::_Nodepref _Nodepref;\r
+ typedef typename _Allocator_type::template rebind<_Element_type>::other _Allocator_type;\r
+\r
+ typedef typename _Allocator_type::size_type size_type;\r
+ typedef typename _Allocator_type::difference_type difference_type;\r
+ typedef typename _Allocator_type::pointer pointer;\r
+ typedef typename _Allocator_type::const_pointer const_pointer;\r
+ typedef typename _Allocator_type::reference reference;\r
+ typedef typename _Allocator_type::const_reference const_reference;\r
+ typedef typename _Allocator_type::value_type value_type;\r
+\r
+ _Split_order_list_value(_Allocator_type _Allocator = _Allocator_type()) : _Mybase(_Allocator)\r
+ {\r
+ // Immediately allocate a dummy node with order key of 0. This node\r
+ // will always be the head of the list.\r
+ _Myhead = _Buynode(0);\r
+ }\r
+\r
+ ~_Split_order_list_value()\r
+ {\r
+ }\r
+\r
+ // Allocate a new node with the given order key and value\r
+ template<typename _ValTy>\r
+ _Nodeptr _Buynode(_Split_order_key _Order_key, _ValTy&& _Value)\r
+ {\r
+ _Nodeptr _Pnode = _M_node_allocator.allocate(1);\r
+\r
+ try\r
+ {\r
+ _M_value_allocator.construct(std::addressof(_Myval(_Pnode)), std::forward<_ValTy>(_Value));\r
+ _Pnode->_Init(_Order_key);\r
+ }\r
+ catch(...)\r
+ {\r
+ _M_node_allocator.deallocate(_Pnode, 1);\r
+ throw;\r
+ }\r
+\r
+ return (_Pnode);\r
+ }\r
+\r
+ // Allocate a new node with the given order key; used to allocate dummy nodes\r
+ _Nodeptr _Buynode(_Split_order_key _Order_key)\r
+ {\r
+ _Nodeptr _Pnode = _M_node_allocator.allocate(1);\r
+ _Pnode->_Init(_Order_key);\r
+\r
+ return (_Pnode);\r
+ }\r
+\r
+ // Get the next node\r
+ static _Nodepref _Nextnode(_Nodeptr _Pnode)\r
+ {\r
+ return ((_Nodepref)(*_Pnode)._M_next);\r
+ }\r
+\r
+ // Get the stored value\r
+ static reference _Myval(_Nodeptr _Pnode)\r
+ {\r
+ return ((reference)(*_Pnode)._M_element);\r
+ }\r
+};\r
+\r
+// Forward list in which elements are sorted in a split-order\r
+template <typename _Element_type, typename _Element_allocator_type = std::allocator<_Element_type> >\r
+class _Split_ordered_list : _Split_order_list_value<_Element_type, _Element_allocator_type>\r
+{\r
+public:\r
+ typedef _Split_ordered_list<_Element_type, _Element_allocator_type> _Mytype;\r
+ typedef _Split_order_list_value<_Element_type, _Element_allocator_type> _Mybase;\r
+ typedef typename _Mybase::_Allocator_type _Allocator_type;\r
+ typedef typename _Mybase::_Nodeptr _Nodeptr;\r
+\r
+ typedef _Allocator_type allocator_type;\r
+ typedef typename _Allocator_type::size_type size_type;\r
+ typedef typename _Allocator_type::difference_type difference_type;\r
+ typedef typename _Allocator_type::pointer pointer;\r
+ typedef typename _Allocator_type::const_pointer const_pointer;\r
+ typedef typename _Allocator_type::reference reference;\r
+ typedef typename _Allocator_type::const_reference const_reference;\r
+ typedef typename _Allocator_type::value_type value_type;\r
+\r
+ typedef _Solist_const_iterator<_Mybase> const_iterator;\r
+ typedef _Solist_iterator<_Mybase> iterator;\r
+ typedef std::_Flist_const_iterator<_Mybase> _Full_const_iterator;\r
+ typedef std::_Flist_iterator<_Mybase> _Full_iterator;\r
+ typedef std::pair<iterator, bool> _Pairib;\r
+ using _Split_order_list_value<_Element_type, _Element_allocator_type>::_Buynode;\r
+ _Split_ordered_list(_Allocator_type _Allocator = allocator_type()) : _Mybase(_Allocator), _M_element_count(0)\r
+ {\r
+ }\r
+\r
+ ~_Split_ordered_list()\r
+ {\r
+ // Clear the list\r
+ clear();\r
+\r
+ // Remove the head element which is not cleared by clear()\r
+ _Nodeptr _Pnode = _Myhead;\r
+ _Myhead = NULL;\r
+\r
+ _ASSERT_EXPR(_Pnode != NULL && _Nextnode(_Pnode) == NULL, L"Invalid head list node");\r
+\r
+ _Erase(_Pnode);\r
+ }\r
+\r
+ // Common forward list functions\r
+\r
+ allocator_type get_allocator() const\r
+ {\r
+ return (_M_value_allocator);\r
+ }\r
+\r
+ void clear()\r
+ {\r
+#if _ITERATOR_DEBUG_LEVEL == 2 /*IFSTRIP=IGN*/ \r
+ _Orphan_ptr(*this, 0);\r
+#endif /* _ITERATOR_DEBUG_LEVEL == 2 */\r
+\r
+ _Nodeptr _Pnext;\r
+ _Nodeptr _Pnode = _Myhead;\r
+\r
+ _ASSERT_EXPR(_Myhead != NULL, L"Invalid head list node");\r
+ _Pnext = _Nextnode(_Pnode);\r
+ _Pnode->_M_next = NULL;\r
+ _Pnode = _Pnext;\r
+\r
+ while (_Pnode != NULL)\r
+ {\r
+ _Pnext = _Nextnode(_Pnode);\r
+ _Erase(_Pnode);\r
+ _Pnode = _Pnext;\r
+ }\r
+\r
+ _M_element_count = 0;\r
+ }\r
+\r
+ // Returns a first non-dummy element in the SOL\r
+ iterator begin()\r
+ {\r
+ _Full_iterator _Iterator = _Begin();\r
+ return _Get_first_real_iterator(_Iterator);\r
+ }\r
+\r
+ // Returns a first non-dummy element in the SOL\r
+ const_iterator begin() const\r
+ {\r
+ _Full_const_iterator _Iterator = _Begin();\r
+ return _Get_first_real_iterator(_Iterator);\r
+ }\r
+\r
+ iterator end()\r
+ {\r
+ return (iterator(0, this));\r
+ }\r
+\r
+ const_iterator end() const\r
+ {\r
+ return (const_iterator(0, this));\r
+ }\r
+\r
+ const_iterator cbegin() const\r
+ {\r
+ return (((const _Mytype *)this)->begin());\r
+ }\r
+\r
+ const_iterator cend() const\r
+ {\r
+ return (((const _Mytype *)this)->end());\r
+ }\r
+\r
+ // Checks if the number of elements (non-dummy) is 0\r
+ bool empty() const\r
+ {\r
+ return (_M_element_count == 0);\r
+ }\r
+\r
+ // Returns the number of non-dummy elements in the list\r
+ size_type size() const\r
+ {\r
+ return _M_element_count;\r
+ }\r
+\r
+ // Returns the maximum size of the list, determined by the allocator\r
+ size_type max_size() const\r
+ {\r
+ return _M_value_allocator.max_size();\r
+ }\r
+\r
+ // Swaps 'this' list with the passed in one\r
+ void swap(_Mytype& _Right)\r
+ {\r
+ if (this == &_Right)\r
+ {\r
+ // Nothing to do\r
+ return;\r
+ }\r
+\r
+ if (_M_value_allocator == _Right._M_value_allocator)\r
+ {\r
+ _Swap_all(_Right);\r
+ std::swap(_Myhead, _Right._Myhead);\r
+ std::swap(_M_element_count, _Right._M_element_count);\r
+ }\r
+ else\r
+ {\r
+ _Mytype _Temp_list;\r
+ _Temp_list._Move_all(_Right);\r
+ _Right._Move_all(*this);\r
+ _Move_all(_Temp_list);\r
+ }\r
+ }\r
+\r
+ // Split-order list functions\r
+\r
+ // Returns a first element in the SOL, which is always a dummy\r
+ _Full_iterator _Begin()\r
+ {\r
+ return _Full_iterator(_Myhead, this);\r
+ }\r
+\r
+ // Returns a first element in the SOL, which is always a dummy\r
+ _Full_const_iterator _Begin() const\r
+ {\r
+ return _Full_const_iterator(_Myhead, this);\r
+ }\r
+\r
+ _Full_iterator _End()\r
+ {\r
+ return _Full_iterator(0, this);\r
+ }\r
+\r
+ _Full_const_iterator _End() const\r
+ {\r
+ return _Full_const_iterator(0, this);\r
+ }\r
+\r
+ static _Split_order_key _Get_key(const _Full_const_iterator& _Iterator)\r
+ {\r
+ return _Iterator._Mynode()->_Get_order_key();\r
+ }\r
+\r
+ // Returns a public iterator version of the internal iterator. Public iterator must not\r
+ // be a dummy private iterator.\r
+ iterator _Get_iterator(_Full_iterator _Iterator)\r
+ {\r
+ _ASSERT_EXPR(_Iterator._Mynode() != NULL && !_Iterator._Mynode()->_Is_dummy(), L"Invalid user node (dummy)");\r
+ return iterator(_Iterator._Mynode(), this);\r
+ }\r
+\r
+ // Returns a public iterator version of the internal iterator. Public iterator must not\r
+ // be a dummy private iterator.\r
+ const_iterator _Get_iterator(_Full_const_iterator _Iterator) const\r
+ {\r
+ _ASSERT_EXPR(_Iterator._Mynode() != NULL && !_Iterator._Mynode()->_Is_dummy(), L"Invalid user node (dummy)");\r
+ return const_iterator(_Iterator._Mynode(), this);\r
+ }\r
+\r
+ // Returns a non-const version of the _Full_iterator\r
+ _Full_iterator _Get_iterator(_Full_const_iterator _Iterator)\r
+ {\r
+ return _Full_iterator(_Iterator._Mynode(), this);\r
+ }\r
+\r
+ // Returns a non-const version of the iterator\r
+ iterator _Get_iterator(const_iterator _Iterator)\r
+ {\r
+ return iterator(_Iterator._Mynode(), this);\r
+ }\r
+\r
+ // Returns a public iterator version of a first non-dummy internal iterator at or after\r
+ // the passed in internal iterator.\r
+ iterator _Get_first_real_iterator(_Full_iterator _Iterator)\r
+ {\r
+ // Skip all dummy, internal only iterators\r
+ while (_Iterator != _End() && _Iterator._Mynode()->_Is_dummy())\r
+ {\r
+ _Iterator++;\r
+ }\r
+\r
+ return iterator(_Iterator._Mynode(), this);\r
+ }\r
+\r
+ // Returns a public iterator version of a first non-dummy internal iterator at or after\r
+ // the passed in internal iterator.\r
+ const_iterator _Get_first_real_iterator(_Full_const_iterator _Iterator) const\r
+ {\r
+ // Skip all dummy, internal only iterators\r
+ while (_Iterator != _End() && _Iterator._Mynode()->_Is_dummy())\r
+ {\r
+ _Iterator++;\r
+ }\r
+\r
+ return const_iterator(_Iterator._Mynode(), this);\r
+ }\r
+\r
+ // Erase an element using the allocator\r
+ void _Erase(_Nodeptr _Delete_node)\r
+ {\r
+ if (!_Delete_node->_Is_dummy())\r
+ {\r
+ // Dummy nodes have nothing constructed, thus should not be destroyed.\r
+ _M_node_allocator.destroy(_Delete_node);\r
+ }\r
+ _M_node_allocator.deallocate(_Delete_node, 1);\r
+ }\r
+\r
+ // Try to insert a new element in the list. If insert fails, return the node that\r
+ // was inserted instead.\r
+ _Nodeptr _Insert(_Nodeptr _Previous, _Nodeptr _New_node, _Nodeptr _Current_node)\r
+ {\r
+ _New_node->_M_next = _Current_node;\r
+ return _Previous->_Atomic_set_next(_New_node, _Current_node);\r
+ }\r
+ \r
+ // Insert a new element between passed in iterators\r
+ _Pairib _Insert(_Full_iterator _Iterator, _Full_iterator _Next, _Nodeptr _List_node, long * _New_count)\r
+ {\r
+ _Nodeptr _Inserted_node = _Insert(_Iterator._Mynode(), _List_node, _Next._Mynode());\r
+\r
+ if (_Inserted_node == _List_node)\r
+ {\r
+ // If the insert succeeded, check that the order is correct and increment the element count\r
+ _Check_range();\r
+ *_New_count = _InterlockedIncrement(&_M_element_count);\r
+ return _Pairib(iterator(_List_node, this), true);\r
+ }\r
+ else\r
+ {\r
+ return _Pairib(end(), false);\r
+ }\r
+ }\r
+\r
+ // Insert a new dummy element, starting search at a parent dummy element\r
+ _Full_iterator _Insert_dummy(_Full_iterator _Iterator, _Split_order_key _Order_key)\r
+ {\r
+ _Full_iterator _Last = _End();\r
+ _Full_iterator _Where = _Iterator;\r
+\r
+ _ASSERT_EXPR(_Where != _Last, L"Invalid head node");\r
+\r
+ _Where++;\r
+\r
+ // Create a dummy element up front, even though it may be discarded (due to concurrent insertion)\r
+ _Nodeptr _Dummy_node = _Buynode(_Order_key);\r
+\r
+ for (;;)\r
+ {\r
+ _ASSERT_EXPR(_Iterator != _Last, L"Invalid head list node");\r
+\r
+ // If the head iterator is at the end of the list, or past the point where this dummy\r
+ // node needs to be inserted, then try to insert it.\r
+ if (_Where == _Last || _Get_key(_Where) > _Order_key)\r
+ {\r
+ _ASSERT_EXPR(_Get_key(_Iterator) < _Order_key, L"Invalid node order in the list");\r
+\r
+ // Try to insert it in the right place\r
+ _Nodeptr _Inserted_node = _Insert(_Iterator._Mynode(), _Dummy_node, _Where._Mynode());\r
+\r
+ if (_Inserted_node == _Dummy_node)\r
+ {\r
+ // Insertion succeeded, check the list for order violations\r
+ _Check_range();\r
+ return _Full_iterator(_Dummy_node, this);\r
+ }\r
+ else\r
+ {\r
+ // Insertion failed: either dummy node was inserted by another thread, or\r
+ // a real element was inserted at exactly the same place as dummy node.\r
+ // Proceed with the search from the previous location where order key was\r
+ // known to be larger (note: this is legal only because there is no safe\r
+ // concurrent erase operation supported).\r
+ _Where = _Iterator;\r
+ _Where++;\r
+ continue;\r
+ }\r
+ }\r
+ else if (_Get_key(_Where) == _Order_key)\r
+ {\r
+ // Another dummy node with the same value found, discard the new one.\r
+ _Erase(_Dummy_node);\r
+ return _Where;\r
+ }\r
+\r
+ // Move the iterator forward\r
+ _Iterator = _Where;\r
+ _Where++;\r
+ }\r
+\r
+ }\r
+\r
+ // This erase function can handle both real and dummy nodes\r
+ void _Erase(_Full_iterator _Previous, _Full_const_iterator& _Where)\r
+ {\r
+#if _ITERATOR_DEBUG_LEVEL == 2 /*IFSTRIP=IGN*/ \r
+ if (_Where._Getcont() != this || _Where._Ptr == _Myhead)\r
+ {\r
+ std::_DEBUG_ERROR("list erase iterator outside range");\r
+ }\r
+ _Nodeptr _Pnode = (_Where++)._Mynode();\r
+ _Orphan_ptr(*this, _Pnode);\r
+#else /* _ITERATOR_DEBUG_LEVEL == 2 */\r
+ _Nodeptr _Pnode = (_Where++)._Mynode();\r
+#endif /* _ITERATOR_DEBUG_LEVEL == 2 */\r
+\r
+ _Nodeptr _Prevnode = _Previous._Mynode();\r
+ _ASSERT_EXPR(_Prevnode->_M_next == _Pnode, L"Erase must take consecutive iterators");\r
+ _Prevnode->_M_next = _Pnode->_M_next;\r
+\r
+ _Erase(_Pnode);\r
+ }\r
+\r
+ // Erase the element (previous node needs to be passed because this is a forward only list)\r
+ iterator _Erase(_Full_iterator _Previous, const_iterator _Where)\r
+ {\r
+ _Full_const_iterator _Iterator = _Where;\r
+ _Erase(_Previous, _Iterator);\r
+ _M_element_count--;\r
+\r
+ return _Get_iterator(_Get_first_real_iterator(_Iterator));\r
+ }\r
+\r
+ // Move all elements from the passed in split-ordered list to this one\r
+ void _Move_all(_Mytype& _Source_list)\r
+ {\r
+ _Full_const_iterator _First = _Source_list._Begin();\r
+ _Full_const_iterator _Last = _Source_list._End();\r
+\r
+ if (_First == _Last)\r
+ {\r
+ return;\r
+ }\r
+\r
+ _Nodeptr _Previous_node = _Myhead;\r
+ _Full_const_iterator _Begin_iterator = _First++;\r
+\r
+ // Move all elements one by one, including dummy ones\r
+ for (_Full_const_iterator _Iterator = _First; _Iterator != _Last;)\r
+ {\r
+ _Nodeptr _Node = _Iterator._Mynode();\r
+\r
+ _Nodeptr _Dummy_node = _Node->_Is_dummy() ? _Buynode(_Node->_Get_order_key()) : _Buynode(_Node->_Get_order_key(), _Myval(_Node));\r
+ _Previous_node = _Insert(_Previous_node, _Dummy_node, NULL);\r
+ _ASSERT_EXPR(_Previous_node != NULL, L"Insertion must succeed");\r
+ _Full_const_iterator _Where = _Iterator++;\r
+ _Source_list._Erase(_Get_iterator(_Begin_iterator), _Where);\r
+ }\r
+ }\r
+\r
+private:\r
+\r
+ // Check the list for order violations\r
+ void _Check_range()\r
+ {\r
+#if defined (_DEBUG)\r
+ for (_Full_iterator _Iterator = _Begin(); _Iterator != _End(); _Iterator++)\r
+ {\r
+ _Full_iterator _Next_iterator = _Iterator;\r
+ _Next_iterator++;\r
+\r
+ _ASSERT_EXPR(_Next_iterator == end() || _Next_iterator._Mynode()->_Get_order_key() >= _Iterator._Mynode()->_Get_order_key(), L"!!! List order inconsistency !!!");\r
+ }\r
+#endif\r
+ }\r
+\r
+#if _ITERATOR_DEBUG_LEVEL == 2 /*IFSTRIP=IGN*/ \r
+ void _Orphan_ptr(_Mytype& _Cont, _Nodeptr _Ptr) const\r
+ {\r
+ std::_Lockit _Lock(_LOCK_DEBUG);\r
+ const_iterator **_Pnext = (const_iterator **)_Cont._Getpfirst();\r
+ if (_Pnext != 0)\r
+ {\r
+ while (*_Pnext != 0)\r
+ {\r
+ if ((*_Pnext)->_Ptr == (_Nodeptr)&_Myhead || _Ptr != 0 && (*_Pnext)->_Ptr != _Ptr)\r
+ {\r
+ _Pnext = (const_iterator **)(*_Pnext)->_Getpnext();\r
+ }\r
+ else\r
+ {\r
+ (*_Pnext)->_Clrcont();\r
+ *_Pnext = *(const_iterator **)(*_Pnext)->_Getpnext();\r
+ }\r
+ }\r
+ }\r
+ }\r
+#endif /* _ITERATOR_DEBUG_LEVEL == 2 */\r
+\r
+ volatile long _M_element_count; // Total item count, not counting dummy nodes\r
+};\r
+\r
+} // namespace details;\r
+} // namespace Concurrency\r
--- /dev/null
+//--------------------------------------------------------------------------\r
+// \r
+// Copyright (c) Microsoft Corporation. All rights reserved. \r
+// \r
+// File: concrt_extras.h\r
+//\r
+// Implementation of ConcRT helpers\r
+//\r
+//--------------------------------------------------------------------------\r
+\r
+#pragma once\r
+\r
+#include <concrt.h>\r
+#include <concurrent_queue.h>\r
+\r
+namespace Concurrency\r
+{ \r
+ class semaphore\r
+ {\r
+ public:\r
+ explicit semaphore(LONG capacity)\r
+ : _semaphore_count(capacity)\r
+ {\r
+ }\r
+\r
+ // Acquires access to the semaphore.\r
+ void acquire()\r
+ {\r
+ // The capacity of the semaphore is exceeded when the semaphore count \r
+ // falls below zero. When this happens, add the current context to the \r
+ // back of the wait queue and block the current context.\r
+ if (InterlockedDecrement(&_semaphore_count) < 0)\r
+ {\r
+ _waiting_contexts.push(Concurrency::Context::CurrentContext());\r
+ Concurrency::Context::Block();\r
+ }\r
+ }\r
+\r
+ // Releases access to the semaphore.\r
+ void release()\r
+ {\r
+ // If the semaphore count is negative, unblock the first waiting context.\r
+ if (InterlockedIncrement(&_semaphore_count) <= 0)\r
+ {\r
+ // A call to acquire might have decremented the counter, but has not\r
+ // yet finished adding the context to the queue. \r
+ // Create a spin loop that waits for the context to become available.\r
+ Concurrency:: Context* waiting = NULL;\r
+ while(!_waiting_contexts.try_pop(waiting))\r
+ {\r
+ Concurrency::wait(0);\r
+ }\r
+\r
+ // Unblock the context.\r
+ waiting->Unblock();\r
+ }\r
+ }\r
+\r
+ private:\r
+ // The semaphore count.\r
+ LONG _semaphore_count;\r
+\r
+ // A concurrency-safe queue of contexts that must wait to \r
+ // acquire the semaphore.\r
+ Concurrency::concurrent_queue<Concurrency::Context*> _waiting_contexts;\r
+ \r
+ semaphore const &operator =(semaphore const&); // no assignment operator\r
+ semaphore(semaphore const &); // no copy constructor\r
+ };\r
+}
\ No newline at end of file
projects / casparcg / commitdiff