diff options
Diffstat (limited to 'OpenSim/Framework/PriorityQueue.cs')
-rw-r--r-- | OpenSim/Framework/PriorityQueue.cs | 88 |
1 files changed, 63 insertions, 25 deletions
diff --git a/OpenSim/Framework/PriorityQueue.cs b/OpenSim/Framework/PriorityQueue.cs index e7a7f7f..22ffcdc 100644 --- a/OpenSim/Framework/PriorityQueue.cs +++ b/OpenSim/Framework/PriorityQueue.cs | |||
@@ -45,7 +45,8 @@ namespace OpenSim.Framework | |||
45 | /// <summary> | 45 | /// <summary> |
46 | /// Total number of queues (priorities) available | 46 | /// Total number of queues (priorities) available |
47 | /// </summary> | 47 | /// </summary> |
48 | public const uint NumberOfQueues = 12; | 48 | |
49 | public const uint NumberOfQueues = 12; // includes immediate queues, m_queueCounts need to be set acording | ||
49 | 50 | ||
50 | /// <summary> | 51 | /// <summary> |
51 | /// Number of queuest (priorities) that are processed immediately | 52 | /// Number of queuest (priorities) that are processed immediately |
@@ -56,11 +57,14 @@ namespace OpenSim.Framework | |||
56 | private Dictionary<uint, LookupItem> m_lookupTable; | 57 | private Dictionary<uint, LookupItem> m_lookupTable; |
57 | 58 | ||
58 | // internal state used to ensure the deqeues are spread across the priority | 59 | // 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 | // queues "fairly". queuecounts is the amount to pull from each queue in |
60 | // each pass. weighted towards the higher priority queues | 61 | // each pass. weighted towards the higher priority queues |
61 | private uint m_nextQueue = 0; | 62 | private uint m_nextQueue = 0; |
62 | private uint m_countFromQueue = 0; | 63 | private uint m_countFromQueue = 0; |
63 | private uint[] m_queueCounts = { 8, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1 }; | 64 | // first queues are imediate, so no counts |
65 | // private uint[] m_queueCounts = { 0, 0, 8, 4, 4, 2, 2, 2, 2, 1, 1, 1 }; | ||
66 | private uint[] m_queueCounts = {0, 0, 8, 8, 5, 4, 3, 2, 1, 1, 1, 1}; | ||
67 | // this is ava, ava, attach, <10m, 20,40,80,160m,320,640,1280, + | ||
64 | 68 | ||
65 | // next request is a counter of the number of updates queued, it provides | 69 | // 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 | 70 | // a total ordering on the updates coming through the queue and is more |
@@ -101,7 +105,7 @@ namespace OpenSim.Framework | |||
101 | int count = 0; | 105 | int count = 0; |
102 | for (int i = 0; i < m_heaps.Length; ++i) | 106 | for (int i = 0; i < m_heaps.Length; ++i) |
103 | count += m_heaps[i].Count; | 107 | count += m_heaps[i].Count; |
104 | 108 | ||
105 | return count; | 109 | return count; |
106 | } | 110 | } |
107 | } | 111 | } |
@@ -109,7 +113,7 @@ namespace OpenSim.Framework | |||
109 | /// <summary> | 113 | /// <summary> |
110 | /// Enqueue an item into the specified priority queue | 114 | /// Enqueue an item into the specified priority queue |
111 | /// </summary> | 115 | /// </summary> |
112 | public bool Enqueue(uint pqueue, IEntityUpdate value) | 116 | public bool Enqueue(uint pqueue, EntityUpdate value) |
113 | { | 117 | { |
114 | LookupItem lookup; | 118 | LookupItem lookup; |
115 | 119 | ||
@@ -130,14 +134,29 @@ namespace OpenSim.Framework | |||
130 | return true; | 134 | return true; |
131 | } | 135 | } |
132 | 136 | ||
137 | |||
138 | public void Remove(List<uint> ids) | ||
139 | { | ||
140 | LookupItem lookup; | ||
141 | |||
142 | foreach (uint localid in ids) | ||
143 | { | ||
144 | if (m_lookupTable.TryGetValue(localid, out lookup)) | ||
145 | { | ||
146 | lookup.Heap.Remove(lookup.Handle); | ||
147 | m_lookupTable.Remove(localid); | ||
148 | } | ||
149 | } | ||
150 | } | ||
151 | |||
133 | /// <summary> | 152 | /// <summary> |
134 | /// Remove an item from one of the queues. Specifically, it removes the | 153 | /// 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 | 154 | /// oldest item from the next queue in order to provide fair access to |
136 | /// all of the queues | 155 | /// all of the queues |
137 | /// </summary> | 156 | /// </summary> |
138 | public bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue) | 157 | public bool TryDequeue(out EntityUpdate value, out Int32 timeinqueue) |
139 | { | 158 | { |
140 | // If there is anything in priority queue 0, return it first no | 159 | // If there is anything in imediate queues, return it first no |
141 | // matter what else. Breaks fairness. But very useful. | 160 | // matter what else. Breaks fairness. But very useful. |
142 | for (int iq = 0; iq < NumberOfImmediateQueues; iq++) | 161 | for (int iq = 0; iq < NumberOfImmediateQueues; iq++) |
143 | { | 162 | { |
@@ -151,36 +170,35 @@ namespace OpenSim.Framework | |||
151 | return true; | 170 | return true; |
152 | } | 171 | } |
153 | } | 172 | } |
154 | 173 | ||
155 | // To get the fair queing, we cycle through each of the | 174 | // To get the fair queing, we cycle through each of the |
156 | // queues when finding an element to dequeue. | 175 | // queues when finding an element to dequeue. |
157 | // We pull (NumberOfQueues - QueueIndex) items from each queue in order | 176 | // We pull (NumberOfQueues - QueueIndex) items from each queue in order |
158 | // to give lower numbered queues a higher priority and higher percentage | 177 | // to give lower numbered queues a higher priority and higher percentage |
159 | // of the bandwidth. | 178 | // of the bandwidth. |
160 | 179 | ||
161 | // Check for more items to be pulled from the current queue | 180 | // Check for more items to be pulled from the current queue |
162 | if (m_heaps[m_nextQueue].Count > 0 && m_countFromQueue > 0) | 181 | if (m_heaps[m_nextQueue].Count > 0 && m_countFromQueue > 0) |
163 | { | 182 | { |
164 | m_countFromQueue--; | 183 | m_countFromQueue--; |
165 | 184 | ||
166 | MinHeapItem item = m_heaps[m_nextQueue].RemoveMin(); | 185 | MinHeapItem item = m_heaps[m_nextQueue].RemoveMin(); |
167 | m_lookupTable.Remove(item.Value.Entity.LocalId); | 186 | m_lookupTable.Remove(item.Value.Entity.LocalId); |
168 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); | 187 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); |
169 | value = item.Value; | 188 | value = item.Value; |
170 | 189 | ||
171 | return true; | 190 | return true; |
172 | } | 191 | } |
173 | 192 | ||
174 | // Find the next non-immediate queue with updates in it | 193 | // Find the next non-immediate queue with updates in it |
175 | for (int i = 0; i < NumberOfQueues; ++i) | 194 | for (uint i = NumberOfImmediateQueues; i < NumberOfQueues; ++i) |
176 | { | 195 | { |
177 | m_nextQueue = (uint)((m_nextQueue + 1) % NumberOfQueues); | 196 | m_nextQueue++; |
197 | if(m_nextQueue >= NumberOfQueues) | ||
198 | m_nextQueue = NumberOfImmediateQueues; | ||
199 | |||
178 | m_countFromQueue = m_queueCounts[m_nextQueue]; | 200 | m_countFromQueue = m_queueCounts[m_nextQueue]; |
179 | 201 | ||
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) | 202 | if (m_heaps[m_nextQueue].Count > 0) |
185 | { | 203 | { |
186 | m_countFromQueue--; | 204 | m_countFromQueue--; |
@@ -189,19 +207,39 @@ namespace OpenSim.Framework | |||
189 | m_lookupTable.Remove(item.Value.Entity.LocalId); | 207 | m_lookupTable.Remove(item.Value.Entity.LocalId); |
190 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); | 208 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); |
191 | value = item.Value; | 209 | value = item.Value; |
210 | return true; | ||
211 | } | ||
212 | } | ||
192 | 213 | ||
214 | timeinqueue = 0; | ||
215 | value = default(EntityUpdate); | ||
216 | return false; | ||
217 | } | ||
218 | |||
219 | public bool TryOrderedDequeue(out EntityUpdate value, out Int32 timeinqueue) | ||
220 | { | ||
221 | // If there is anything in imediate queues, return it first no | ||
222 | // matter what else. Breaks fairness. But very useful. | ||
223 | for (int iq = 0; iq < NumberOfQueues; iq++) | ||
224 | { | ||
225 | if (m_heaps[iq].Count > 0) | ||
226 | { | ||
227 | MinHeapItem item = m_heaps[iq].RemoveMin(); | ||
228 | m_lookupTable.Remove(item.Value.Entity.LocalId); | ||
229 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); | ||
230 | value = item.Value; | ||
193 | return true; | 231 | return true; |
194 | } | 232 | } |
195 | } | 233 | } |
196 | 234 | ||
197 | timeinqueue = 0; | 235 | timeinqueue = 0; |
198 | value = default(IEntityUpdate); | 236 | value = default(EntityUpdate); |
199 | return false; | 237 | return false; |
200 | } | 238 | } |
201 | 239 | ||
202 | /// <summary> | 240 | /// <summary> |
203 | /// Reapply the prioritization function to each of the updates currently | 241 | /// Reapply the prioritization function to each of the updates currently |
204 | /// stored in the priority queues. | 242 | /// stored in the priority queues. |
205 | /// </summary | 243 | /// </summary |
206 | public void Reprioritize(UpdatePriorityHandler handler) | 244 | public void Reprioritize(UpdatePriorityHandler handler) |
207 | { | 245 | { |
@@ -253,8 +291,8 @@ namespace OpenSim.Framework | |||
253 | #region MinHeapItem | 291 | #region MinHeapItem |
254 | private struct MinHeapItem : IComparable<MinHeapItem> | 292 | private struct MinHeapItem : IComparable<MinHeapItem> |
255 | { | 293 | { |
256 | private IEntityUpdate value; | 294 | private EntityUpdate value; |
257 | internal IEntityUpdate Value { | 295 | internal EntityUpdate Value { |
258 | get { | 296 | get { |
259 | return this.value; | 297 | return this.value; |
260 | } | 298 | } |
@@ -290,7 +328,7 @@ namespace OpenSim.Framework | |||
290 | this.pqueue = pqueue; | 328 | this.pqueue = pqueue; |
291 | } | 329 | } |
292 | 330 | ||
293 | internal MinHeapItem(uint pqueue, UInt64 entryorder, IEntityUpdate value) | 331 | internal MinHeapItem(uint pqueue, UInt64 entryorder, EntityUpdate value) |
294 | { | 332 | { |
295 | this.entrytime = Util.EnvironmentTickCount(); | 333 | this.entrytime = Util.EnvironmentTickCount(); |
296 | this.entryorder = entryorder; | 334 | this.entryorder = entryorder; |