diff options
author | Mic Bowman | 2011-04-20 21:58:49 -0700 |
---|---|---|
committer | Mic Bowman | 2011-04-20 21:58:49 -0700 |
commit | 7759bda833c03f4c29500dce32b835a7aef8285b (patch) | |
tree | 603e524f040dca865e3b67e50a78b4279c12e019 /OpenSim/Region/ClientStack/LindenUDP | |
parent | Merge branch 'queuetest' of ssh://opensimulator.org/var/git/opensim into queu... (diff) | |
download | opensim-SC_OLD-7759bda833c03f4c29500dce32b835a7aef8285b.zip opensim-SC_OLD-7759bda833c03f4c29500dce32b835a7aef8285b.tar.gz opensim-SC_OLD-7759bda833c03f4c29500dce32b835a7aef8285b.tar.bz2 opensim-SC_OLD-7759bda833c03f4c29500dce32b835a7aef8285b.tar.xz |
Added an "immediate" queue to the priority queue. This is
per Melanie's very good suggestion. The immediate queue is
serviced completely before all others, making it a very good
place to put avatar updates & attachments.
Moved the priority queue out of the LLUDP directory and
into the framework. It is now a fairly general utility.
Diffstat (limited to '')
-rw-r--r-- | OpenSim/Framework/PriorityQueue.cs (renamed from OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs) | 43 |
1 files changed, 28 insertions, 15 deletions
diff --git a/OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs b/OpenSim/Framework/PriorityQueue.cs index b62ec07..eec2a92 100644 --- a/OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs +++ b/OpenSim/Framework/PriorityQueue.cs | |||
@@ -34,20 +34,21 @@ using OpenSim.Framework; | |||
34 | using OpenSim.Framework.Client; | 34 | using OpenSim.Framework.Client; |
35 | using log4net; | 35 | using log4net; |
36 | 36 | ||
37 | namespace OpenSim.Region.ClientStack.LindenUDP | 37 | namespace OpenSim.Framework |
38 | { | 38 | { |
39 | public class PriorityQueue | 39 | public class PriorityQueue |
40 | { | 40 | { |
41 | private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); | 41 | private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); |
42 | 42 | ||
43 | internal delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity); | 43 | public delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity); |
44 | 44 | ||
45 | // Heap[0] for self updates | 45 | // Heap[0] for self updates |
46 | // Heap[1..12] for entity updates | 46 | // Heap[1..12] for entity updates |
47 | 47 | ||
48 | internal const uint m_numberOfQueues = 12; | 48 | public const uint NumberOfQueues = 12; |
49 | public const uint ImmediateQueue = 0; | ||
49 | 50 | ||
50 | private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[m_numberOfQueues]; | 51 | private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[NumberOfQueues]; |
51 | private Dictionary<uint, LookupItem> m_lookupTable; | 52 | private Dictionary<uint, LookupItem> m_lookupTable; |
52 | private uint m_nextQueue = 0; | 53 | private uint m_nextQueue = 0; |
53 | private UInt64 m_nextRequest = 0; | 54 | private UInt64 m_nextRequest = 0; |
@@ -57,9 +58,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
57 | get { return this.m_syncRoot; } | 58 | get { return this.m_syncRoot; } |
58 | } | 59 | } |
59 | 60 | ||
60 | internal PriorityQueue() : this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { } | 61 | public PriorityQueue() : this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { } |
61 | 62 | ||
62 | internal PriorityQueue(int capacity) | 63 | public PriorityQueue(int capacity) |
63 | { | 64 | { |
64 | m_lookupTable = new Dictionary<uint, LookupItem>(capacity); | 65 | m_lookupTable = new Dictionary<uint, LookupItem>(capacity); |
65 | 66 | ||
@@ -67,7 +68,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
67 | m_heaps[i] = new MinHeap<MinHeapItem>(capacity); | 68 | m_heaps[i] = new MinHeap<MinHeapItem>(capacity); |
68 | } | 69 | } |
69 | 70 | ||
70 | internal int Count | 71 | public int Count |
71 | { | 72 | { |
72 | get | 73 | get |
73 | { | 74 | { |
@@ -91,7 +92,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
91 | lookup.Heap.Remove(lookup.Handle); | 92 | lookup.Heap.Remove(lookup.Handle); |
92 | } | 93 | } |
93 | 94 | ||
94 | pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1); | 95 | pqueue = Util.Clamp<uint>(pqueue, 0, NumberOfQueues - 1); |
95 | lookup.Heap = m_heaps[pqueue]; | 96 | lookup.Heap = m_heaps[pqueue]; |
96 | lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle); | 97 | lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle); |
97 | m_lookupTable[localid] = lookup; | 98 | m_lookupTable[localid] = lookup; |
@@ -99,18 +100,30 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
99 | return true; | 100 | return true; |
100 | } | 101 | } |
101 | 102 | ||
102 | internal bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue) | 103 | public bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue) |
103 | { | 104 | { |
104 | for (int i = 0; i < m_numberOfQueues; ++i) | 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) | ||
105 | { | 118 | { |
106 | // To get the fair queing, we cycle through each of the | 119 | // To get the fair queing, we cycle through each of the |
107 | // queues when finding an element to dequeue, this code | 120 | // queues when finding an element to dequeue, this code |
108 | // assumes that the distribution of updates in the queues | 121 | // assumes that the distribution of updates in the queues |
109 | // is polynomial, probably quadractic (eg distance of PI * R^2) | 122 | // is polynomial, probably quadractic (eg distance of PI * R^2) |
110 | uint h = (uint)((m_nextQueue + i) % m_numberOfQueues); | 123 | uint h = (uint)((m_nextQueue + i) % NumberOfQueues); |
111 | if (m_heaps[h].Count > 0) | 124 | if (m_heaps[h].Count > 0) |
112 | { | 125 | { |
113 | m_nextQueue = (uint)((h + 1) % m_numberOfQueues); | 126 | m_nextQueue = (uint)((h + 1) % NumberOfQueues); |
114 | 127 | ||
115 | MinHeapItem item = m_heaps[h].RemoveMin(); | 128 | MinHeapItem item = m_heaps[h].RemoveMin(); |
116 | m_lookupTable.Remove(item.Value.Entity.LocalId); | 129 | m_lookupTable.Remove(item.Value.Entity.LocalId); |
@@ -126,7 +139,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
126 | return false; | 139 | return false; |
127 | } | 140 | } |
128 | 141 | ||
129 | internal void Reprioritize(UpdatePriorityHandler handler) | 142 | public void Reprioritize(UpdatePriorityHandler handler) |
130 | { | 143 | { |
131 | MinHeapItem item; | 144 | MinHeapItem item; |
132 | foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values)) | 145 | foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values)) |
@@ -140,7 +153,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
140 | { | 153 | { |
141 | // unless the priority queue has changed, there is no need to modify | 154 | // unless the priority queue has changed, there is no need to modify |
142 | // the entry | 155 | // the entry |
143 | pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1); | 156 | pqueue = Util.Clamp<uint>(pqueue, 0, NumberOfQueues - 1); |
144 | if (pqueue != item.PriorityQueue) | 157 | if (pqueue != item.PriorityQueue) |
145 | { | 158 | { |
146 | lookup.Heap.Remove(lookup.Handle); | 159 | lookup.Heap.Remove(lookup.Handle); |
@@ -164,7 +177,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
164 | public override string ToString() | 177 | public override string ToString() |
165 | { | 178 | { |
166 | string s = ""; | 179 | string s = ""; |
167 | for (int i = 0; i < m_numberOfQueues; i++) | 180 | for (int i = 0; i < NumberOfQueues; i++) |
168 | { | 181 | { |
169 | if (s != "") s += ","; | 182 | if (s != "") s += ","; |
170 | s += m_heaps[i].Count.ToString(); | 183 | s += m_heaps[i].Count.ToString(); |