aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Framework
diff options
context:
space:
mode:
Diffstat (limited to 'OpenSim/Framework')
-rw-r--r--OpenSim/Framework/PriorityQueue.cs258
1 files changed, 258 insertions, 0 deletions
diff --git a/OpenSim/Framework/PriorityQueue.cs b/OpenSim/Framework/PriorityQueue.cs
new file mode 100644
index 0000000..eec2a92
--- /dev/null
+++ b/OpenSim/Framework/PriorityQueue.cs
@@ -0,0 +1,258 @@
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 // Heap[0] for self updates
46 // Heap[1..12] for entity updates
47
48 public const uint NumberOfQueues = 12;
49 public const uint ImmediateQueue = 0;
50
51 private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[NumberOfQueues];
52 private Dictionary<uint, LookupItem> m_lookupTable;
53 private uint m_nextQueue = 0;
54 private UInt64 m_nextRequest = 0;
55
56 private object m_syncRoot = new object();
57 public object SyncRoot {
58 get { return this.m_syncRoot; }
59 }
60
61 public PriorityQueue() : this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { }
62
63 public PriorityQueue(int capacity)
64 {
65 m_lookupTable = new Dictionary<uint, LookupItem>(capacity);
66
67 for (int i = 0; i < m_heaps.Length; ++i)
68 m_heaps[i] = new MinHeap<MinHeapItem>(capacity);
69 }
70
71 public int Count
72 {
73 get
74 {
75 int count = 0;
76 for (int i = 0; i < m_heaps.Length; ++i)
77 count += m_heaps[i].Count;
78 return count;
79 }
80 }
81
82 public bool Enqueue(uint pqueue, IEntityUpdate value)
83 {
84 LookupItem lookup;
85
86 uint localid = value.Entity.LocalId;
87 UInt64 entry = m_nextRequest++;
88 if (m_lookupTable.TryGetValue(localid, out lookup))
89 {
90 entry = lookup.Heap[lookup.Handle].EntryOrder;
91 value.Update(lookup.Heap[lookup.Handle].Value);
92 lookup.Heap.Remove(lookup.Handle);
93 }
94
95 pqueue = Util.Clamp<uint>(pqueue, 0, NumberOfQueues - 1);
96 lookup.Heap = m_heaps[pqueue];
97 lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle);
98 m_lookupTable[localid] = lookup;
99
100 return true;
101 }
102
103 public bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue)
104 {
105 // If there is anything in priority queue 0, return it first no
106 // matter what else. Breaks fairness. But very useful.
107 if (m_heaps[ImmediateQueue].Count > 0)
108 {
109 MinHeapItem item = m_heaps[ImmediateQueue].RemoveMin();
110 m_lookupTable.Remove(item.Value.Entity.LocalId);
111 timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime);
112 value = item.Value;
113
114 return true;
115 }
116
117 for (int i = 0; i < NumberOfQueues; ++i)
118 {
119 // To get the fair queing, we cycle through each of the
120 // queues when finding an element to dequeue, this code
121 // assumes that the distribution of updates in the queues
122 // is polynomial, probably quadractic (eg distance of PI * R^2)
123 uint h = (uint)((m_nextQueue + i) % NumberOfQueues);
124 if (m_heaps[h].Count > 0)
125 {
126 m_nextQueue = (uint)((h + 1) % NumberOfQueues);
127
128 MinHeapItem item = m_heaps[h].RemoveMin();
129 m_lookupTable.Remove(item.Value.Entity.LocalId);
130 timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime);
131 value = item.Value;
132
133 return true;
134 }
135 }
136
137 timeinqueue = 0;
138 value = default(IEntityUpdate);
139 return false;
140 }
141
142 public void Reprioritize(UpdatePriorityHandler handler)
143 {
144 MinHeapItem item;
145 foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values))
146 {
147 if (lookup.Heap.TryGetValue(lookup.Handle, out item))
148 {
149 uint pqueue = item.PriorityQueue;
150 uint localid = item.Value.Entity.LocalId;
151
152 if (handler(ref pqueue, item.Value.Entity))
153 {
154 // unless the priority queue has changed, there is no need to modify
155 // the entry
156 pqueue = Util.Clamp<uint>(pqueue, 0, NumberOfQueues - 1);
157 if (pqueue != item.PriorityQueue)
158 {
159 lookup.Heap.Remove(lookup.Handle);
160
161 LookupItem litem = lookup;
162 litem.Heap = m_heaps[pqueue];
163 litem.Heap.Add(new MinHeapItem(pqueue, item), ref litem.Handle);
164 m_lookupTable[localid] = litem;
165 }
166 }
167 else
168 {
169 // m_log.WarnFormat("[PQUEUE]: UpdatePriorityHandler returned false for {0}",item.Value.Entity.UUID);
170 lookup.Heap.Remove(lookup.Handle);
171 this.m_lookupTable.Remove(localid);
172 }
173 }
174 }
175 }
176
177 public override string ToString()
178 {
179 string s = "";
180 for (int i = 0; i < NumberOfQueues; i++)
181 {
182 if (s != "") s += ",";
183 s += m_heaps[i].Count.ToString();
184 }
185 return s;
186 }
187
188#region MinHeapItem
189 private struct MinHeapItem : IComparable<MinHeapItem>
190 {
191 private IEntityUpdate value;
192 internal IEntityUpdate Value {
193 get {
194 return this.value;
195 }
196 }
197
198 private uint pqueue;
199 internal uint PriorityQueue {
200 get {
201 return this.pqueue;
202 }
203 }
204
205 private Int32 entrytime;
206 internal Int32 EntryTime {
207 get {
208 return this.entrytime;
209 }
210 }
211
212 private UInt64 entryorder;
213 internal UInt64 EntryOrder
214 {
215 get {
216 return this.entryorder;
217 }
218 }
219
220 internal MinHeapItem(uint pqueue, MinHeapItem other)
221 {
222 this.entrytime = other.entrytime;
223 this.entryorder = other.entryorder;
224 this.value = other.value;
225 this.pqueue = pqueue;
226 }
227
228 internal MinHeapItem(uint pqueue, UInt64 entryorder, IEntityUpdate value)
229 {
230 this.entrytime = Util.EnvironmentTickCount();
231 this.entryorder = entryorder;
232 this.value = value;
233 this.pqueue = pqueue;
234 }
235
236 public override string ToString()
237 {
238 return String.Format("[{0},{1},{2}]",pqueue,entryorder,value.Entity.LocalId);
239 }
240
241 public int CompareTo(MinHeapItem other)
242 {
243 // I'm assuming that the root part of an SOG is added to the update queue
244 // before the component parts
245 return Comparer<UInt64>.Default.Compare(this.EntryOrder, other.EntryOrder);
246 }
247 }
248#endregion
249
250#region LookupItem
251 private struct LookupItem
252 {
253 internal MinHeap<MinHeapItem> Heap;
254 internal IHandle Handle;
255 }
256#endregion
257 }
258}