From 134f86e8d5c414409631b25b8c6f0ee45fbd8631 Mon Sep 17 00:00:00 2001 From: David Walter Seikel Date: Thu, 3 Nov 2016 21:44:39 +1000 Subject: Initial update to OpenSim 0.8.2.1 source code. --- ThirdParty/SmartThreadPool/PriorityQueue.cs | 465 ++++++++++++++-------------- 1 file changed, 232 insertions(+), 233 deletions(-) (limited to 'ThirdParty/SmartThreadPool/PriorityQueue.cs') diff --git a/ThirdParty/SmartThreadPool/PriorityQueue.cs b/ThirdParty/SmartThreadPool/PriorityQueue.cs index 63d5e84..409c879 100644 --- a/ThirdParty/SmartThreadPool/PriorityQueue.cs +++ b/ThirdParty/SmartThreadPool/PriorityQueue.cs @@ -1,240 +1,239 @@ -// Ami Bar -// amibar@gmail.com - using System; using System.Collections; +using System.Collections.Generic; using System.Diagnostics; namespace Amib.Threading.Internal { - #region PriorityQueue class - - /// - /// PriorityQueue class - /// This class is not thread safe because we use external lock - /// - public sealed class PriorityQueue : IEnumerable - { - #region Private members - - /// - /// The number of queues, there is one for each type of priority - /// - private const int _queuesCount = WorkItemPriority.Highest-WorkItemPriority.Lowest+1; - - /// - /// Work items queues. There is one for each type of priority - /// - private Queue [] _queues = new Queue[_queuesCount]; - - /// - /// The total number of work items within the queues - /// - private int _workItemsCount = 0; - - /// - /// Use with IEnumerable interface - /// - private int _version = 0; - - #endregion - - #region Contructor - - public PriorityQueue() - { - for(int i = 0; i < _queues.Length; ++i) - { - _queues[i] = new Queue(); - } - } - - #endregion - - #region Methods - - /// - /// Enqueue a work item. - /// - /// A work item - public void Enqueue(IHasWorkItemPriority workItem) - { - Debug.Assert(null != workItem); - - int queueIndex = _queuesCount-(int)workItem.WorkItemPriority-1; - Debug.Assert(queueIndex >= 0); - Debug.Assert(queueIndex < _queuesCount); - - _queues[queueIndex].Enqueue(workItem); - ++_workItemsCount; - ++_version; - } - - /// - /// Dequeque a work item. - /// - /// Returns the next work item - public IHasWorkItemPriority Dequeue() - { - IHasWorkItemPriority workItem = null; - - if(_workItemsCount > 0) - { - int queueIndex = GetNextNonEmptyQueue(-1); - Debug.Assert(queueIndex >= 0); - workItem = _queues[queueIndex].Dequeue() as IHasWorkItemPriority; - Debug.Assert(null != workItem); - --_workItemsCount; - ++_version; - } - - return workItem; - } - - /// - /// Find the next non empty queue starting at queue queueIndex+1 - /// - /// The index-1 to start from - /// - /// The index of the next non empty queue or -1 if all the queues are empty - /// - private int GetNextNonEmptyQueue(int queueIndex) - { - for(int i = queueIndex+1; i < _queuesCount; ++i) - { - if(_queues[i].Count > 0) - { - return i; - } - } - return -1; - } - - /// - /// The number of work items - /// - public int Count - { - get - { - return _workItemsCount; - } - } - - /// - /// Clear all the work items - /// - public void Clear() - { - if (_workItemsCount > 0) - { - foreach(Queue queue in _queues) - { - queue.Clear(); - } - _workItemsCount = 0; - ++_version; - } - } - - #endregion - - #region IEnumerable Members - - /// - /// Returns an enumerator to iterate over the work items - /// - /// Returns an enumerator - public IEnumerator GetEnumerator() - { - return new PriorityQueueEnumerator(this); - } - - #endregion - - #region PriorityQueueEnumerator - - /// - /// The class the implements the enumerator - /// - private class PriorityQueueEnumerator : IEnumerator - { - private PriorityQueue _priorityQueue; - private int _version; - private int _queueIndex; - private IEnumerator _enumerator; - - public PriorityQueueEnumerator(PriorityQueue priorityQueue) - { - _priorityQueue = priorityQueue; - _version = _priorityQueue._version; - _queueIndex = _priorityQueue.GetNextNonEmptyQueue(-1); - if (_queueIndex >= 0) - { - _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator(); - } - else - { - _enumerator = null; - } - } - - #region IEnumerator Members - - public void Reset() - { - _version = _priorityQueue._version; - _queueIndex = _priorityQueue.GetNextNonEmptyQueue(-1); - if (_queueIndex >= 0) - { - _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator(); - } - else - { - _enumerator = null; - } - } - - public object Current - { - get - { - Debug.Assert(null != _enumerator); - return _enumerator.Current; - } - } - - public bool MoveNext() - { - if (null == _enumerator) - { - return false; - } - - if(_version != _priorityQueue._version) - { - throw new InvalidOperationException("The collection has been modified"); - - } - if (!_enumerator.MoveNext()) - { - _queueIndex = _priorityQueue.GetNextNonEmptyQueue(_queueIndex); - if(-1 == _queueIndex) - { - return false; - } - _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator(); - _enumerator.MoveNext(); - return true; - } - return true; - } - - #endregion - } - - #endregion - } - - #endregion + #region PriorityQueue class + + /// + /// PriorityQueue class + /// This class is not thread safe because we use external lock + /// + public sealed class PriorityQueue : IEnumerable + { + #region Private members + + /// + /// The number of queues, there is one for each type of priority + /// + private const int _queuesCount = WorkItemPriority.Highest-WorkItemPriority.Lowest+1; + + /// + /// Work items queues. There is one for each type of priority + /// + private readonly LinkedList[] _queues = new LinkedList[_queuesCount]; + + /// + /// The total number of work items within the queues + /// + private int _workItemsCount; + + /// + /// Use with IEnumerable interface + /// + private int _version; + + #endregion + + #region Contructor + + public PriorityQueue() + { + for(int i = 0; i < _queues.Length; ++i) + { + _queues[i] = new LinkedList(); + } + } + + #endregion + + #region Methods + + /// + /// Enqueue a work item. + /// + /// A work item + public void Enqueue(IHasWorkItemPriority workItem) + { + Debug.Assert(null != workItem); + + int queueIndex = _queuesCount-(int)workItem.WorkItemPriority-1; + Debug.Assert(queueIndex >= 0); + Debug.Assert(queueIndex < _queuesCount); + + _queues[queueIndex].AddLast(workItem); + ++_workItemsCount; + ++_version; + } + + /// + /// Dequeque a work item. + /// + /// Returns the next work item + public IHasWorkItemPriority Dequeue() + { + IHasWorkItemPriority workItem = null; + + if(_workItemsCount > 0) + { + int queueIndex = GetNextNonEmptyQueue(-1); + Debug.Assert(queueIndex >= 0); + workItem = _queues[queueIndex].First.Value; + _queues[queueIndex].RemoveFirst(); + Debug.Assert(null != workItem); + --_workItemsCount; + ++_version; + } + + return workItem; + } + + /// + /// Find the next non empty queue starting at queue queueIndex+1 + /// + /// The index-1 to start from + /// + /// The index of the next non empty queue or -1 if all the queues are empty + /// + private int GetNextNonEmptyQueue(int queueIndex) + { + for(int i = queueIndex+1; i < _queuesCount; ++i) + { + if(_queues[i].Count > 0) + { + return i; + } + } + return -1; + } + + /// + /// The number of work items + /// + public int Count + { + get + { + return _workItemsCount; + } + } + + /// + /// Clear all the work items + /// + public void Clear() + { + if (_workItemsCount > 0) + { + foreach(LinkedList queue in _queues) + { + queue.Clear(); + } + _workItemsCount = 0; + ++_version; + } + } + + #endregion + + #region IEnumerable Members + + /// + /// Returns an enumerator to iterate over the work items + /// + /// Returns an enumerator + public IEnumerator GetEnumerator() + { + return new PriorityQueueEnumerator(this); + } + + #endregion + + #region PriorityQueueEnumerator + + /// + /// The class the implements the enumerator + /// + private class PriorityQueueEnumerator : IEnumerator + { + private readonly PriorityQueue _priorityQueue; + private int _version; + private int _queueIndex; + private IEnumerator _enumerator; + + public PriorityQueueEnumerator(PriorityQueue priorityQueue) + { + _priorityQueue = priorityQueue; + _version = _priorityQueue._version; + _queueIndex = _priorityQueue.GetNextNonEmptyQueue(-1); + if (_queueIndex >= 0) + { + _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator(); + } + else + { + _enumerator = null; + } + } + + #region IEnumerator Members + + public void Reset() + { + _version = _priorityQueue._version; + _queueIndex = _priorityQueue.GetNextNonEmptyQueue(-1); + if (_queueIndex >= 0) + { + _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator(); + } + else + { + _enumerator = null; + } + } + + public object Current + { + get + { + Debug.Assert(null != _enumerator); + return _enumerator.Current; + } + } + + public bool MoveNext() + { + if (null == _enumerator) + { + return false; + } + + if(_version != _priorityQueue._version) + { + throw new InvalidOperationException("The collection has been modified"); + + } + if (!_enumerator.MoveNext()) + { + _queueIndex = _priorityQueue.GetNextNonEmptyQueue(_queueIndex); + if(-1 == _queueIndex) + { + return false; + } + _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator(); + _enumerator.MoveNext(); + return true; + } + return true; + } + + #endregion + } + + #endregion + } + + #endregion } -- cgit v1.1