opensim – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | eva | 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 | |||
28 | using System; |
||
29 | using System.Collections; |
||
30 | using System.Collections.Generic; |
||
31 | using System.Reflection; |
||
32 | |||
33 | using OpenSim.Framework; |
||
34 | using OpenSim.Framework.Client; |
||
35 | using log4net; |
||
36 | |||
37 | namespace 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 | } |