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