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