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