opensim – Blame information for rev 1

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