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