aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Framework/PriorityQueue.cs
diff options
context:
space:
mode:
Diffstat (limited to 'OpenSim/Framework/PriorityQueue.cs')
-rw-r--r--OpenSim/Framework/PriorityQueue.cs323
1 files changed, 323 insertions, 0 deletions
diff --git a/OpenSim/Framework/PriorityQueue.cs b/OpenSim/Framework/PriorityQueue.cs
new file mode 100644
index 0000000..3e6fdaa
--- /dev/null
+++ b/OpenSim/Framework/PriorityQueue.cs
@@ -0,0 +1,323 @@
1/*
2 * Copyright (c) Contributors, http://opensimulator.org/
3 * See CONTRIBUTORS.TXT for a full list of copyright holders.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of the OpenSimulator Project nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28using System;
29using System.Collections;
30using System.Collections.Generic;
31using System.Reflection;
32
33using OpenSim.Framework;
34using OpenSim.Framework.Client;
35using log4net;
36
37namespace OpenSim.Framework
38{
39 public class PriorityQueue
40 {
41 private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
42
43 public delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity);
44
45 /// <summary>
46 /// Total number of queues (priorities) available
47 /// </summary>
48 public const uint NumberOfQueues = 12;
49
50 /// <summary>
51 /// Number of queuest (priorities) that are processed immediately
52 /// </summary.
53 public const uint NumberOfImmediateQueues = 2;
54
55 private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[NumberOfQueues];
56 private Dictionary<uint, LookupItem> m_lookupTable;
57
58 // internal state used to ensure the deqeues are spread across the priority
59 // queues "fairly". queuecounts is the amount to pull from each queue in
60 // each pass. weighted towards the higher priority queues
61 private uint m_nextQueue = 0;
62 private uint m_countFromQueue = 0;
63 private uint[] m_queueCounts = { 8, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1 };
64
65 // next request is a counter of the number of updates queued, it provides
66 // a total ordering on the updates coming through the queue and is more
67 // lightweight (and more discriminating) than tick count
68 private UInt64 m_nextRequest = 0;
69
70 /// <summary>
71 /// Lock for enqueue and dequeue operations on the priority queue
72 /// </summary>
73 private object m_syncRoot = new object();
74 public object SyncRoot {
75 get { return this.m_syncRoot; }
76 }
77
78#region constructor
79 public PriorityQueue() : this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { }
80
81 public PriorityQueue(int capacity)
82 {
83 m_lookupTable = new Dictionary<uint, LookupItem>(capacity);
84
85 for (int i = 0; i < m_heaps.Length; ++i)
86 m_heaps[i] = new MinHeap<MinHeapItem>(capacity);
87
88 m_nextQueue = NumberOfImmediateQueues;
89 m_countFromQueue = m_queueCounts[m_nextQueue];
90 }
91#endregion Constructor
92
93#region PublicMethods
94 /// <summary>
95 /// Return the number of items in the queues
96 /// </summary>
97 public int Count
98 {
99 get
100 {
101 int count = 0;
102 for (int i = 0; i < m_heaps.Length; ++i)
103 count += m_heaps[i].Count;
104
105 return count;
106 }
107 }
108
109 /// <summary>
110 /// Enqueue an item into the specified priority queue
111 /// </summary>
112 public bool Enqueue(uint pqueue, IEntityUpdate value)
113 {
114 LookupItem lookup;
115
116 uint localid = value.Entity.LocalId;
117 UInt64 entry = m_nextRequest++;
118 if (m_lookupTable.TryGetValue(localid, out lookup))
119 {
120 entry = lookup.Heap[lookup.Handle].EntryOrder;
121 value.Update(lookup.Heap[lookup.Handle].Value);
122 lookup.Heap.Remove(lookup.Handle);
123 }
124
125 pqueue = Util.Clamp<uint>(pqueue, 0, NumberOfQueues - 1);
126 lookup.Heap = m_heaps[pqueue];
127 lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle);
128 m_lookupTable[localid] = lookup;
129
130 return true;
131 }
132
133 /// <summary>
134 /// Remove an item from one of the queues. Specifically, it removes the
135 /// oldest item from the next queue in order to provide fair access to
136 /// all of the queues
137 /// </summary>
138 public bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue)
139 {
140 // If there is anything in priority queue 0, return it first no
141 // matter what else. Breaks fairness. But very useful.
142 for (int iq = 0; iq < NumberOfImmediateQueues; iq++)
143 {
144 if (m_heaps[iq].Count > 0)
145 {
146 MinHeapItem item = m_heaps[iq].RemoveMin();
147 m_lookupTable.Remove(item.Value.Entity.LocalId);
148 timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime);
149 value = item.Value;
150
151 return true;
152 }
153 }
154
155 // To get the fair queing, we cycle through each of the
156 // queues when finding an element to dequeue.
157 // We pull (NumberOfQueues - QueueIndex) items from each queue in order
158 // to give lower numbered queues a higher priority and higher percentage
159 // of the bandwidth.
160
161 // Check for more items to be pulled from the current queue
162 if (m_heaps[m_nextQueue].Count > 0 && m_countFromQueue > 0)
163 {
164 m_countFromQueue--;
165
166 MinHeapItem item = m_heaps[m_nextQueue].RemoveMin();
167 m_lookupTable.Remove(item.Value.Entity.LocalId);
168 timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime);
169 value = item.Value;
170
171 return true;
172 }
173
174 // Find the next non-immediate queue with updates in it
175 for (int i = 0; i < NumberOfQueues; ++i)
176 {
177 m_nextQueue = (uint)((m_nextQueue + 1) % NumberOfQueues);
178 m_countFromQueue = m_queueCounts[m_nextQueue];
179
180 // if this is one of the immediate queues, just skip it
181 if (m_nextQueue < NumberOfImmediateQueues)
182 continue;
183
184 if (m_heaps[m_nextQueue].Count > 0)
185 {
186 m_countFromQueue--;
187
188 MinHeapItem item = m_heaps[m_nextQueue].RemoveMin();
189 m_lookupTable.Remove(item.Value.Entity.LocalId);
190 timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime);
191 value = item.Value;
192
193 return true;
194 }
195 }
196
197 timeinqueue = 0;
198 value = default(IEntityUpdate);
199 return false;
200 }
201
202 /// <summary>
203 /// Reapply the prioritization function to each of the updates currently
204 /// stored in the priority queues.
205 /// </summary
206 public void Reprioritize(UpdatePriorityHandler handler)
207 {
208 MinHeapItem item;
209 foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values))
210 {
211 if (lookup.Heap.TryGetValue(lookup.Handle, out item))
212 {
213 uint pqueue = item.PriorityQueue;
214 uint localid = item.Value.Entity.LocalId;
215
216 if (handler(ref pqueue, item.Value.Entity))
217 {
218 // unless the priority queue has changed, there is no need to modify
219 // the entry
220 pqueue = Util.Clamp<uint>(pqueue, 0, NumberOfQueues - 1);
221 if (pqueue != item.PriorityQueue)
222 {
223 lookup.Heap.Remove(lookup.Handle);
224
225 LookupItem litem = lookup;
226 litem.Heap = m_heaps[pqueue];
227 litem.Heap.Add(new MinHeapItem(pqueue, item), ref litem.Handle);
228 m_lookupTable[localid] = litem;
229 }
230 }
231 else
232 {
233 // m_log.WarnFormat("[PQUEUE]: UpdatePriorityHandler returned false for {0}",item.Value.Entity.UUID);
234 lookup.Heap.Remove(lookup.Handle);
235 this.m_lookupTable.Remove(localid);
236 }
237 }
238 }
239 }
240
241 /// <summary>
242 /// </summary>
243 public override string ToString()
244 {
245 string s = "";
246 for (int i = 0; i < NumberOfQueues; i++)
247 s += String.Format("{0,7} ",m_heaps[i].Count);
248 return s;
249 }
250
251#endregion PublicMethods
252
253#region MinHeapItem
254 private struct MinHeapItem : IComparable<MinHeapItem>
255 {
256 private IEntityUpdate value;
257 internal IEntityUpdate Value {
258 get {
259 return this.value;
260 }
261 }
262
263 private uint pqueue;
264 internal uint PriorityQueue {
265 get {
266 return this.pqueue;
267 }
268 }
269
270 private Int32 entrytime;
271 internal Int32 EntryTime {
272 get {
273 return this.entrytime;
274 }
275 }
276
277 private UInt64 entryorder;
278 internal UInt64 EntryOrder
279 {
280 get {
281 return this.entryorder;
282 }
283 }
284
285 internal MinHeapItem(uint pqueue, MinHeapItem other)
286 {
287 this.entrytime = other.entrytime;
288 this.entryorder = other.entryorder;
289 this.value = other.value;
290 this.pqueue = pqueue;
291 }
292
293 internal MinHeapItem(uint pqueue, UInt64 entryorder, IEntityUpdate value)
294 {
295 this.entrytime = Util.EnvironmentTickCount();
296 this.entryorder = entryorder;
297 this.value = value;
298 this.pqueue = pqueue;
299 }
300
301 public override string ToString()
302 {
303 return String.Format("[{0},{1},{2}]",pqueue,entryorder,value.Entity.LocalId);
304 }
305
306 public int CompareTo(MinHeapItem other)
307 {
308 // I'm assuming that the root part of an SOG is added to the update queue
309 // before the component parts
310 return Comparer<UInt64>.Default.Compare(this.EntryOrder, other.EntryOrder);
311 }
312 }
313#endregion
314
315#region LookupItem
316 private struct LookupItem
317 {
318 internal MinHeap<MinHeapItem> Heap;
319 internal IHandle Handle;
320 }
321#endregion
322 }
323}