diff options
Diffstat (limited to '')
-rw-r--r-- | ThirdParty/SmartThreadPool/PriorityQueue.cs | 239 |
1 files changed, 239 insertions, 0 deletions
diff --git a/ThirdParty/SmartThreadPool/PriorityQueue.cs b/ThirdParty/SmartThreadPool/PriorityQueue.cs new file mode 100644 index 0000000..3ea6084 --- /dev/null +++ b/ThirdParty/SmartThreadPool/PriorityQueue.cs | |||
@@ -0,0 +1,239 @@ | |||
1 | using System; | ||
2 | using System.Collections; | ||
3 | using System.Collections.Generic; | ||
4 | using System.Diagnostics; | ||
5 | |||
6 | namespace Amib.Threading.Internal | ||
7 | { | ||
8 | #region PriorityQueue class | ||
9 | |||
10 | /// <summary> | ||
11 | /// PriorityQueue class | ||
12 | /// This class is not thread safe because we use external lock | ||
13 | /// </summary> | ||
14 | public sealed class PriorityQueue : IEnumerable | ||
15 | { | ||
16 | #region Private members | ||
17 | |||
18 | /// <summary> | ||
19 | /// The number of queues, there is one for each type of priority | ||
20 | /// </summary> | ||
21 | private const int _queuesCount = WorkItemPriority.Highest-WorkItemPriority.Lowest+1; | ||
22 | |||
23 | /// <summary> | ||
24 | /// Work items queues. There is one for each type of priority | ||
25 | /// </summary> | ||
26 | private readonly LinkedList<IHasWorkItemPriority>[] _queues = new LinkedList<IHasWorkItemPriority>[_queuesCount]; | ||
27 | |||
28 | /// <summary> | ||
29 | /// The total number of work items within the queues | ||
30 | /// </summary> | ||
31 | private int _workItemsCount; | ||
32 | |||
33 | /// <summary> | ||
34 | /// Use with IEnumerable interface | ||
35 | /// </summary> | ||
36 | private int _version; | ||
37 | |||
38 | #endregion | ||
39 | |||
40 | #region Contructor | ||
41 | |||
42 | public PriorityQueue() | ||
43 | { | ||
44 | for(int i = 0; i < _queues.Length; ++i) | ||
45 | { | ||
46 | _queues[i] = new LinkedList<IHasWorkItemPriority>(); | ||
47 | } | ||
48 | } | ||
49 | |||
50 | #endregion | ||
51 | |||
52 | #region Methods | ||
53 | |||
54 | /// <summary> | ||
55 | /// Enqueue a work item. | ||
56 | /// </summary> | ||
57 | /// <param name="workItem">A work item</param> | ||
58 | public void Enqueue(IHasWorkItemPriority workItem) | ||
59 | { | ||
60 | Debug.Assert(null != workItem); | ||
61 | |||
62 | int queueIndex = _queuesCount-(int)workItem.WorkItemPriority-1; | ||
63 | Debug.Assert(queueIndex >= 0); | ||
64 | Debug.Assert(queueIndex < _queuesCount); | ||
65 | |||
66 | _queues[queueIndex].AddLast(workItem); | ||
67 | ++_workItemsCount; | ||
68 | ++_version; | ||
69 | } | ||
70 | |||
71 | /// <summary> | ||
72 | /// Dequeque a work item. | ||
73 | /// </summary> | ||
74 | /// <returns>Returns the next work item</returns> | ||
75 | public IHasWorkItemPriority Dequeue() | ||
76 | { | ||
77 | IHasWorkItemPriority workItem = null; | ||
78 | |||
79 | if(_workItemsCount > 0) | ||
80 | { | ||
81 | int queueIndex = GetNextNonEmptyQueue(-1); | ||
82 | Debug.Assert(queueIndex >= 0); | ||
83 | workItem = _queues[queueIndex].First.Value; | ||
84 | _queues[queueIndex].RemoveFirst(); | ||
85 | Debug.Assert(null != workItem); | ||
86 | --_workItemsCount; | ||
87 | ++_version; | ||
88 | } | ||
89 | |||
90 | return workItem; | ||
91 | } | ||
92 | |||
93 | /// <summary> | ||
94 | /// Find the next non empty queue starting at queue queueIndex+1 | ||
95 | /// </summary> | ||
96 | /// <param name="queueIndex">The index-1 to start from</param> | ||
97 | /// <returns> | ||
98 | /// The index of the next non empty queue or -1 if all the queues are empty | ||
99 | /// </returns> | ||
100 | private int GetNextNonEmptyQueue(int queueIndex) | ||
101 | { | ||
102 | for(int i = queueIndex+1; i < _queuesCount; ++i) | ||
103 | { | ||
104 | if(_queues[i].Count > 0) | ||
105 | { | ||
106 | return i; | ||
107 | } | ||
108 | } | ||
109 | return -1; | ||
110 | } | ||
111 | |||
112 | /// <summary> | ||
113 | /// The number of work items | ||
114 | /// </summary> | ||
115 | public int Count | ||
116 | { | ||
117 | get | ||
118 | { | ||
119 | return _workItemsCount; | ||
120 | } | ||
121 | } | ||
122 | |||
123 | /// <summary> | ||
124 | /// Clear all the work items | ||
125 | /// </summary> | ||
126 | public void Clear() | ||
127 | { | ||
128 | if (_workItemsCount > 0) | ||
129 | { | ||
130 | foreach(LinkedList<IHasWorkItemPriority> queue in _queues) | ||
131 | { | ||
132 | queue.Clear(); | ||
133 | } | ||
134 | _workItemsCount = 0; | ||
135 | ++_version; | ||
136 | } | ||
137 | } | ||
138 | |||
139 | #endregion | ||
140 | |||
141 | #region IEnumerable Members | ||
142 | |||
143 | /// <summary> | ||
144 | /// Returns an enumerator to iterate over the work items | ||
145 | /// </summary> | ||
146 | /// <returns>Returns an enumerator</returns> | ||
147 | public IEnumerator GetEnumerator() | ||
148 | { | ||
149 | return new PriorityQueueEnumerator(this); | ||
150 | } | ||
151 | |||
152 | #endregion | ||
153 | |||
154 | #region PriorityQueueEnumerator | ||
155 | |||
156 | /// <summary> | ||
157 | /// The class the implements the enumerator | ||
158 | /// </summary> | ||
159 | private class PriorityQueueEnumerator : IEnumerator | ||
160 | { | ||
161 | private readonly PriorityQueue _priorityQueue; | ||
162 | private int _version; | ||
163 | private int _queueIndex; | ||
164 | private IEnumerator _enumerator; | ||
165 | |||
166 | public PriorityQueueEnumerator(PriorityQueue priorityQueue) | ||
167 | { | ||
168 | _priorityQueue = priorityQueue; | ||
169 | _version = _priorityQueue._version; | ||
170 | _queueIndex = _priorityQueue.GetNextNonEmptyQueue(-1); | ||
171 | if (_queueIndex >= 0) | ||
172 | { | ||
173 | _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator(); | ||
174 | } | ||
175 | else | ||
176 | { | ||
177 | _enumerator = null; | ||
178 | } | ||
179 | } | ||
180 | |||
181 | #region IEnumerator Members | ||
182 | |||
183 | public void Reset() | ||
184 | { | ||
185 | _version = _priorityQueue._version; | ||
186 | _queueIndex = _priorityQueue.GetNextNonEmptyQueue(-1); | ||
187 | if (_queueIndex >= 0) | ||
188 | { | ||
189 | _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator(); | ||
190 | } | ||
191 | else | ||
192 | { | ||
193 | _enumerator = null; | ||
194 | } | ||
195 | } | ||
196 | |||
197 | public object Current | ||
198 | { | ||
199 | get | ||
200 | { | ||
201 | Debug.Assert(null != _enumerator); | ||
202 | return _enumerator.Current; | ||
203 | } | ||
204 | } | ||
205 | |||
206 | public bool MoveNext() | ||
207 | { | ||
208 | if (null == _enumerator) | ||
209 | { | ||
210 | return false; | ||
211 | } | ||
212 | |||
213 | if(_version != _priorityQueue._version) | ||
214 | { | ||
215 | throw new InvalidOperationException("The collection has been modified"); | ||
216 | |||
217 | } | ||
218 | if (!_enumerator.MoveNext()) | ||
219 | { | ||
220 | _queueIndex = _priorityQueue.GetNextNonEmptyQueue(_queueIndex); | ||
221 | if(-1 == _queueIndex) | ||
222 | { | ||
223 | return false; | ||
224 | } | ||
225 | _enumerator = _priorityQueue._queues[_queueIndex].GetEnumerator(); | ||
226 | _enumerator.MoveNext(); | ||
227 | return true; | ||
228 | } | ||
229 | return true; | ||
230 | } | ||
231 | |||
232 | #endregion | ||
233 | } | ||
234 | |||
235 | #endregion | ||
236 | } | ||
237 | |||
238 | #endregion | ||
239 | } | ||