aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/ThirdParty/SmartThreadPool/PriorityQueue.cs
diff options
context:
space:
mode:
authorJustin Clark-Casey (justincc)2013-05-01 19:01:43 +0100
committerJustin Clark-Casey (justincc)2013-05-01 19:01:43 +0100
commit206fb306a7820cf593570e35ddfa8e7c5a10e449 (patch)
tree0ef0fdf42ddc0b63224af52b62b0bad42f62e352 /ThirdParty/SmartThreadPool/PriorityQueue.cs
parentFix CAPS to work like they should - do not send caps to the viewer if they're... (diff)
downloadopensim-SC-206fb306a7820cf593570e35ddfa8e7c5a10e449.zip
opensim-SC-206fb306a7820cf593570e35ddfa8e7c5a10e449.tar.gz
opensim-SC-206fb306a7820cf593570e35ddfa8e7c5a10e449.tar.bz2
opensim-SC-206fb306a7820cf593570e35ddfa8e7c5a10e449.tar.xz
Update SmartThreadPool to latest version 2.2.3 with a major and minor change.
SmartThreadPool code comes from http://www.codeproject.com/Articles/7933/Smart-Thread-Pool This version implements thread abort (via WorkItem.Cancel(true)), threadpool naming, max thread stack, etc. so we no longer need to manually patch those. However, two changes have been made to stock 2.2.3. Major change: WorkItem.Cancel(bool abortExecution) in our version does not succeed if the work item was in progress and thread abort was not specified. This is to match previous behaviour where we handle co-operative termination via another mechanism rather than checking WorkItem.IsCanceled. Minor change: Did not add STP's StopWatch implementation as this is only used WinCE and Silverlight and causes a build clash with System.Diagnostics.StopWatch The reason for updating is to see if this improves http://opensimulator.org/mantis/view.php?id=6557 and http://opensimulator.org/mantis/view.php?id=6586
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 2025-04-25 17:27:56 +0000