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