aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
authorMic Bowman2011-04-06 09:26:38 -0700
committerMic Bowman2011-04-10 16:57:02 -0700
commit19c6d1d569e081418e139d139c15ea66640288ba (patch)
tree8c0f16e3f67c3751e262c6e8320bc0ff5e85461a
parentFix a bug in the computation of the RTO. Basically... the RTO (the (diff)
downloadopensim-SC_OLD-19c6d1d569e081418e139d139c15ea66640288ba.zip
opensim-SC_OLD-19c6d1d569e081418e139d139c15ea66640288ba.tar.gz
opensim-SC_OLD-19c6d1d569e081418e139d139c15ea66640288ba.tar.bz2
opensim-SC_OLD-19c6d1d569e081418e139d139c15ea66640288ba.tar.xz
Split the priority queue class into a seperate file. LLClientView
is big enough.
-rw-r--r--OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs205
-rw-r--r--OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs245
2 files changed, 245 insertions, 205 deletions
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
index a3f2c15..a724099 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
@@ -11805,209 +11805,6 @@ namespace OpenSim.Region.ClientStack.LindenUDP
11805 OutPacket(pack, ThrottleOutPacketType.Task); 11805 OutPacket(pack, ThrottleOutPacketType.Task);
11806 } 11806 }
11807 11807
11808 #region PriorityQueue
11809 public class PriorityQueue
11810 {
11811 internal delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity);
11812
11813 // Heap[0] for self updates
11814 // Heap[1..12] for entity updates
11815
11816 internal const uint m_numberOfQueues = 12;
11817 private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[m_numberOfQueues];
11818 private Dictionary<uint, LookupItem> m_lookupTable;
11819 private object m_syncRoot = new object();
11820 private uint m_nextQueue = 0;
11821 private UInt64 m_nextRequest = 0;
11822
11823 internal PriorityQueue() :
11824 this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { }
11825 internal PriorityQueue(int capacity)
11826 {
11827 m_lookupTable = new Dictionary<uint, LookupItem>(capacity);
11828
11829 for (int i = 0; i < m_heaps.Length; ++i)
11830 m_heaps[i] = new MinHeap<MinHeapItem>(capacity);
11831 }
11832
11833 public object SyncRoot { get { return this.m_syncRoot; } }
11834
11835 internal int Count
11836 {
11837 get
11838 {
11839 int count = 0;
11840 for (int i = 0; i < m_heaps.Length; ++i)
11841 count += m_heaps[i].Count;
11842 return count;
11843 }
11844 }
11845
11846 public bool Enqueue(uint pqueue, EntityUpdate value)
11847 {
11848 LookupItem lookup;
11849
11850 uint localid = value.Entity.LocalId;
11851 UInt64 entry = m_nextRequest++;
11852 if (m_lookupTable.TryGetValue(localid, out lookup))
11853 {
11854 entry = lookup.Heap[lookup.Handle].EntryOrder;
11855 value.Flags |= lookup.Heap[lookup.Handle].Value.Flags;
11856 lookup.Heap.Remove(lookup.Handle);
11857 }
11858
11859 pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1);
11860 lookup.Heap = m_heaps[pqueue];
11861 lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle);
11862 m_lookupTable[localid] = lookup;
11863
11864 return true;
11865 }
11866
11867 internal bool TryDequeue(out EntityUpdate value, out Int32 timeinqueue)
11868 {
11869 for (int i = 0; i < m_numberOfQueues; ++i)
11870 {
11871 // To get the fair queing, we cycle through each of the
11872 // queues when finding an element to dequeue, this code
11873 // assumes that the distribution of updates in the queues
11874 // is polynomial, probably quadractic (eg distance of PI * R^2)
11875 uint h = (uint)((m_nextQueue + i) % m_numberOfQueues);
11876 if (m_heaps[h].Count > 0)
11877 {
11878 m_nextQueue = (uint)((h + 1) % m_numberOfQueues);
11879
11880 MinHeapItem item = m_heaps[h].RemoveMin();
11881 m_lookupTable.Remove(item.Value.Entity.LocalId);
11882 timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime);
11883 value = item.Value;
11884
11885 return true;
11886 }
11887 }
11888
11889 timeinqueue = 0;
11890 value = default(EntityUpdate);
11891 return false;
11892 }
11893
11894 internal void Reprioritize(UpdatePriorityHandler handler)
11895 {
11896 MinHeapItem item;
11897 foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values))
11898 {
11899 if (lookup.Heap.TryGetValue(lookup.Handle, out item))
11900 {
11901 uint pqueue = item.PriorityQueue;
11902 uint localid = item.Value.Entity.LocalId;
11903
11904 if (handler(ref pqueue, item.Value.Entity))
11905 {
11906 // unless the priority queue has changed, there is no need to modify
11907 // the entry
11908 pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1);
11909 if (pqueue != item.PriorityQueue)
11910 {
11911 lookup.Heap.Remove(lookup.Handle);
11912
11913 LookupItem litem = lookup;
11914 litem.Heap = m_heaps[pqueue];
11915 litem.Heap.Add(new MinHeapItem(pqueue, item), ref litem.Handle);
11916 m_lookupTable[localid] = litem;
11917 }
11918 }
11919 else
11920 {
11921 m_log.WarnFormat("[LLCLIENTVIEW]: UpdatePriorityHandler returned false for {0}",item.Value.Entity.UUID);
11922 lookup.Heap.Remove(lookup.Handle);
11923 this.m_lookupTable.Remove(localid);
11924 }
11925 }
11926 }
11927 }
11928
11929 public override string ToString()
11930 {
11931 string s = "";
11932 for (int i = 0; i < m_numberOfQueues; i++)
11933 {
11934 if (s != "") s += ",";
11935 s += m_heaps[i].Count.ToString();
11936 }
11937 return s;
11938 }
11939
11940 #region MinHeapItem
11941 private struct MinHeapItem : IComparable<MinHeapItem>
11942 {
11943 private EntityUpdate value;
11944 internal EntityUpdate Value {
11945 get {
11946 return this.value;
11947 }
11948 }
11949
11950 private uint pqueue;
11951 internal uint PriorityQueue {
11952 get {
11953 return this.pqueue;
11954 }
11955 }
11956
11957 private Int32 entrytime;
11958 internal Int32 EntryTime {
11959 get {
11960 return this.entrytime;
11961 }
11962 }
11963
11964 private UInt64 entryorder;
11965 internal UInt64 EntryOrder
11966 {
11967 get {
11968 return this.entryorder;
11969 }
11970 }
11971
11972 internal MinHeapItem(uint pqueue, MinHeapItem other)
11973 {
11974 this.entrytime = other.entrytime;
11975 this.entryorder = other.entryorder;
11976 this.value = other.value;
11977 this.pqueue = pqueue;
11978 }
11979
11980 internal MinHeapItem(uint pqueue, UInt64 entryorder, EntityUpdate value)
11981 {
11982 this.entrytime = Util.EnvironmentTickCount();
11983 this.entryorder = entryorder;
11984 this.value = value;
11985 this.pqueue = pqueue;
11986 }
11987
11988 public override string ToString()
11989 {
11990 return String.Format("[{0},{1},{2}]",pqueue,entryorder,value.Entity.LocalId);
11991 }
11992
11993 public int CompareTo(MinHeapItem other)
11994 {
11995 // I'm assuming that the root part of an SOG is added to the update queue
11996 // before the component parts
11997 return Comparer<UInt64>.Default.Compare(this.EntryOrder, other.EntryOrder);
11998 }
11999 }
12000 #endregion
12001
12002 #region LookupItem
12003 private struct LookupItem
12004 {
12005 internal MinHeap<MinHeapItem> Heap;
12006 internal IHandle Handle;
12007 }
12008 #endregion
12009 }
12010
12011 public struct PacketProcessor 11808 public struct PacketProcessor
12012 { 11809 {
12013 public PacketMethod method; 11810 public PacketMethod method;
@@ -12028,8 +11825,6 @@ namespace OpenSim.Region.ClientStack.LindenUDP
12028 } 11825 }
12029 } 11826 }
12030 11827
12031 #endregion
12032
12033 public static OSD BuildEvent(string eventName, OSD eventBody) 11828 public static OSD BuildEvent(string eventName, OSD eventBody)
12034 { 11829 {
12035 OSDMap osdEvent = new OSDMap(2); 11830 OSDMap osdEvent = new OSDMap(2);
diff --git a/OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs b/OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs
new file mode 100644
index 0000000..364ce4b
--- /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
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, EntityUpdate 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.Flags |= lookup.Heap[lookup.Handle].Value.Flags;
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 EntityUpdate 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(EntityUpdate);
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 EntityUpdate value;
179 internal EntityUpdate 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, EntityUpdate 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}