diff options
Diffstat (limited to '')
-rw-r--r-- | OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs | 245 |
1 files changed, 245 insertions, 0 deletions
diff --git a/OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs b/OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs new file mode 100644 index 0000000..b62ec07 --- /dev/null +++ b/OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs | |||
@@ -0,0 +1,245 @@ | |||
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.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 | } | ||