aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
authorjjgreens2009-10-14 23:15:03 -0700
committerJohn Hurliman2009-10-15 15:52:53 -0700
commitdf2d5a460f060129e5c09148b9fa4df2f241d8b1 (patch)
treebdec08feae7b1494818830e30120df2bab437cef
parent* Removed some of the redundant broadcast functions in Scene and SceneGraph s... (diff)
downloadopensim-SC_OLD-df2d5a460f060129e5c09148b9fa4df2f241d8b1.zip
opensim-SC_OLD-df2d5a460f060129e5c09148b9fa4df2f241d8b1.tar.gz
opensim-SC_OLD-df2d5a460f060129e5c09148b9fa4df2f241d8b1.tar.bz2
opensim-SC_OLD-df2d5a460f060129e5c09148b9fa4df2f241d8b1.tar.xz
Replaced the update lists with a priority queue implementation in LLClientView
Replaced the update lists with a priority queue implementation in LLClientView. The priority queues are based on the MinHeap implementation also included in this commit within the OpneSim.Framework namespace. Initially setup to exactly mimic the behavior beofre the change which was a first come first serve queue.
-rwxr-xr-xOpenSim/Framework/MinHeap.cs375
-rw-r--r--OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs224
2 files changed, 554 insertions, 45 deletions
diff --git a/OpenSim/Framework/MinHeap.cs b/OpenSim/Framework/MinHeap.cs
new file mode 100755
index 0000000..ad39bbc
--- /dev/null
+++ b/OpenSim/Framework/MinHeap.cs
@@ -0,0 +1,375 @@
1using System;
2using System.Threading;
3using System.Collections;
4using System.Collections.Generic;
5using System.Runtime.InteropServices;
6
7namespace OpenSim.Framework
8{
9 public interface IHandle { }
10
11 [Serializable, ComVisible(false)]
12 public class MinHeap<T> : ICollection<T>, ICollection
13 {
14 private class Handle : IHandle
15 {
16 internal int index = -1;
17 internal MinHeap<T> heap = null;
18
19 internal void Clear()
20 {
21 this.index = -1;
22 this.heap = null;
23 }
24 }
25
26 private struct HeapItem
27 {
28 internal T value;
29 internal Handle handle;
30
31 internal HeapItem(T value, Handle handle)
32 {
33 this.value = value;
34 this.handle = handle;
35 }
36
37 internal void Clear()
38 {
39 this.value = default(T);
40 if (this.handle != null)
41 {
42 this.handle.Clear();
43 this.handle = null;
44 }
45 }
46 }
47
48 public const int DEFAULT_CAPACITY = 4;
49
50 private HeapItem[] items;
51 private int size;
52 private object sync_root;
53 private int version;
54
55 private Comparison<T> comparison;
56
57 public MinHeap() : this(DEFAULT_CAPACITY, Comparer<T>.Default) { }
58 public MinHeap(int capacity) : this(capacity, Comparer<T>.Default) { }
59 public MinHeap(IComparer<T> comparer) : this(DEFAULT_CAPACITY, comparer) { }
60 public MinHeap(int capacity, IComparer<T> comparer) :
61 this(capacity, new Comparison<T>(comparer.Compare)) { }
62 public MinHeap(Comparison<T> comparison) : this(DEFAULT_CAPACITY, comparison) { }
63 public MinHeap(int capacity, Comparison<T> comparison)
64 {
65 this.items = new HeapItem[capacity];
66 this.comparison = comparison;
67 this.size = this.version = 0;
68 }
69
70 public int Count { get { return this.size; } }
71
72 public bool IsReadOnly { get { return false; } }
73
74 public bool IsSynchronized { get { return false; } }
75
76 public T this[IHandle key]
77 {
78 get
79 {
80 Handle handle = ValidateThisHandle(key);
81 return this.items[handle.index].value;
82 }
83
84 set
85 {
86 Handle handle = ValidateThisHandle(key);
87 this.items[handle.index].value = value;
88 if (!BubbleUp(handle.index))
89 BubbleDown(handle.index);
90 }
91 }
92
93 public object SyncRoot
94 {
95 get
96 {
97 if (this.sync_root == null)
98 Interlocked.CompareExchange<object>(ref this.sync_root, new object(), null);
99 return this.sync_root;
100 }
101 }
102
103 private Handle ValidateHandle(IHandle ihandle)
104 {
105 if (ihandle == null)
106 throw new ArgumentNullException("handle");
107 Handle handle = ihandle as Handle;
108 if (handle == null)
109 throw new InvalidOperationException("handle is not valid");
110 return handle;
111 }
112
113 private Handle ValidateThisHandle(IHandle ihandle)
114 {
115 Handle handle = ValidateHandle(ihandle);
116 if (!object.ReferenceEquals(handle.heap, this))
117 throw new InvalidOperationException("handle is not valid for this heap");
118 if (handle.index < 0)
119 throw new InvalidOperationException("handle is not associated to a value");
120 return handle;
121 }
122
123 private void Set(HeapItem item, int index)
124 {
125 this.items[index] = item;
126 if (item.handle != null)
127 item.handle.index = index;
128 }
129
130 private bool BubbleUp(int index)
131 {
132 HeapItem item = this.items[index];
133 int current, parent;
134
135 for (current = index, parent = (current - 1) / 2;
136 (current > 0) && (this.comparison(this.items[parent].value, item.value)) > 0;
137 current = parent, parent = (current - 1) / 2)
138 {
139 Set(this.items[parent], current);
140 }
141
142 if (current != index)
143 {
144 Set(item, current);
145 ++this.version;
146 return true;
147 }
148 return false;
149 }
150
151 private void BubbleDown(int index)
152 {
153 HeapItem item = this.items[index];
154 int current, child;
155
156 for (current = index, child = (2 * current) + 1;
157 current < this.size / 2;
158 current = child, child = (2 * current) + 1)
159 {
160 if ((child < this.size - 1) && this.comparison(this.items[child].value, this.items[child + 1].value) > 0)
161 ++child;
162 if (this.comparison(this.items[child].value, item.value) >= 0)
163 break;
164 Set(this.items[child], current);
165 }
166
167 if (current != index)
168 {
169 Set(item, current);
170 ++this.version;
171 }
172 }
173
174 public bool TryGetValue(IHandle key, out T value)
175 {
176 Handle handle = ValidateHandle(key);
177 if (handle.index > -1)
178 {
179 value = this.items[handle.index].value;
180 return true;
181 }
182 value = default(T);
183 return false;
184 }
185
186 public bool ContainsHandle(IHandle ihandle)
187 {
188 Handle handle = ValidateHandle(ihandle);
189 return object.ReferenceEquals(handle.heap, this) && handle.index > -1;
190 }
191
192 public void Add(T value, ref IHandle handle)
193 {
194 if (handle == null)
195 handle = new Handle();
196 Add(value, handle);
197 }
198
199 public void Add(T value, IHandle ihandle)
200 {
201 if (this.size == this.items.Length)
202 {
203 int capacity = (int)((this.items.Length * 200L) / 100L);
204 if (capacity < (this.items.Length + DEFAULT_CAPACITY))
205 capacity = this.items.Length + DEFAULT_CAPACITY;
206 Array.Resize<HeapItem>(ref this.items, capacity);
207 }
208
209 Handle handle = null;
210 if (ihandle != null)
211 {
212 handle = ValidateHandle(ihandle);
213 handle.heap = this;
214 }
215
216 HeapItem item = new MinHeap<T>.HeapItem(value, handle);
217
218 Set(item, this.size);
219 BubbleUp(this.size++);
220 }
221
222 public void Add(T value)
223 {
224 Add(value, null);
225 }
226
227 public T Min()
228 {
229 if (this.size == 0)
230 throw new InvalidOperationException("Heap is empty");
231
232 return this.items[0].value;
233 }
234
235 public void Clear()
236 {
237 for (int index = 0; index < this.size; ++index)
238 this.items[index].Clear();
239 this.size = 0;
240 ++this.version;
241 }
242
243 public void TrimExcess()
244 {
245 int length = (int)(this.items.Length * 0.9);
246 if (this.size < length)
247 Array.Resize<HeapItem>(ref this.items, Math.Min(this.size, DEFAULT_CAPACITY));
248 }
249
250 private void RemoveAt(int index)
251 {
252 if (this.size == 0)
253 throw new InvalidOperationException("Heap is empty");
254 if (index >= this.size)
255 throw new ArgumentOutOfRangeException("index");
256
257 this.items[index].Clear();
258 if (--this.size > 0 && index != this.size)
259 {
260 Set(this.items[this.size], index);
261 if (!BubbleUp(index))
262 BubbleDown(index);
263 }
264 }
265
266 public T RemoveMin()
267 {
268 if (this.size == 0)
269 throw new InvalidOperationException("Heap is empty");
270
271 HeapItem item = this.items[0];
272 RemoveAt(0);
273 return item.value;
274 }
275
276 public T Remove(IHandle ihandle)
277 {
278 Handle handle = ValidateThisHandle(ihandle);
279 HeapItem item = this.items[handle.index];
280 RemoveAt(handle.index);
281 return item.value;
282 }
283
284 private int GetIndex(T value)
285 {
286 EqualityComparer<T> comparer = EqualityComparer<T>.Default;
287 int index;
288
289 for (index = 0; index < this.size; ++index)
290 {
291 if (comparer.Equals(this.items[index].value, value))
292 return index;
293 }
294 return -1;
295 }
296
297 public bool Contains(T value)
298 {
299 return GetIndex(value) != -1;
300 }
301
302 public bool Remove(T value)
303 {
304 int index = GetIndex(value);
305 if (index != -1)
306 {
307 RemoveAt(index);
308 return true;
309 }
310 return false;
311 }
312
313 public void CopyTo(T[] array, int index)
314 {
315 if (array == null)
316 throw new ArgumentNullException("array");
317 if (array.Rank != 1)
318 throw new ArgumentException("Multidimensional array not supported");
319 if (array.GetLowerBound(0) != 0)
320 throw new ArgumentException("Non-zero lower bound array not supported");
321
322 int length = array.Length;
323 if ((index < 0) || (index > length))
324 throw new ArgumentOutOfRangeException("index");
325 if ((length - index) < this.size)
326 throw new ArgumentException("Not enough space available in array starting at index");
327
328 for (int i = 0; i < this.size; ++i)
329 array[index + i] = this.items[i].value;
330 }
331
332 public void CopyTo(Array array, int index)
333 {
334 if (array == null)
335 throw new ArgumentNullException("array");
336 if (array.Rank != 1)
337 throw new ArgumentException("Multidimensional array not supported");
338 if (array.GetLowerBound(0) != 0)
339 throw new ArgumentException("Non-zero lower bound array not supported");
340
341 int length = array.Length;
342 if ((index < 0) || (index > length))
343 throw new ArgumentOutOfRangeException("index");
344 if ((length - index) < this.size)
345 throw new ArgumentException("Not enough space available in array starting at index");
346
347 try
348 {
349 for (int i = 0; i < this.size; ++i)
350 array.SetValue(this.items[i].value, index + i);
351 }
352 catch (ArrayTypeMismatchException)
353 {
354 throw new ArgumentException("Invalid array type");
355 }
356 }
357
358 public IEnumerator<T> GetEnumerator()
359 {
360 int version = this.version;
361
362 for (int index = 0; index < this.size; ++index)
363 {
364 if (version != this.version)
365 throw new InvalidOperationException("Heap was modified while enumerating");
366 yield return this.items[index].value;
367 }
368 }
369
370 IEnumerator IEnumerable.GetEnumerator()
371 {
372 return GetEnumerator();
373 }
374 }
375}
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
index 82a2cdd..93fdeef 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
@@ -321,11 +321,14 @@ namespace OpenSim.Region.ClientStack.LindenUDP
321 321
322 private int m_cachedTextureSerial; 322 private int m_cachedTextureSerial;
323 private Timer m_avatarTerseUpdateTimer; 323 private Timer m_avatarTerseUpdateTimer;
324 private List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock> m_avatarTerseUpdates = new List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>(); 324 private PriorityQueue<double, ImprovedTerseObjectUpdatePacket.ObjectDataBlock> m_avatarTerseUpdates_ =
325 new PriorityQueue<double, ImprovedTerseObjectUpdatePacket.ObjectDataBlock>();
325 private Timer m_primTerseUpdateTimer; 326 private Timer m_primTerseUpdateTimer;
326 private List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock> m_primTerseUpdates = new List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>(); 327 private PriorityQueue<double, ImprovedTerseObjectUpdatePacket.ObjectDataBlock> m_primTerseUpdates_ =
328 new PriorityQueue<double, ImprovedTerseObjectUpdatePacket.ObjectDataBlock>();
327 private Timer m_primFullUpdateTimer; 329 private Timer m_primFullUpdateTimer;
328 private List<ObjectUpdatePacket.ObjectDataBlock> m_primFullUpdates = new List<ObjectUpdatePacket.ObjectDataBlock>(); 330 private PriorityQueue<double, ObjectUpdatePacket.ObjectDataBlock> m_primFullUpdates_ =
331 new PriorityQueue<double, ObjectUpdatePacket.ObjectDataBlock>();
329 private int m_moneyBalance; 332 private int m_moneyBalance;
330 private int m_animationSequenceNumber = 1; 333 private int m_animationSequenceNumber = 1;
331 private bool m_SendLogoutPacketWhenClosing = true; 334 private bool m_SendLogoutPacketWhenClosing = true;
@@ -3435,16 +3438,16 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3435 ImprovedTerseObjectUpdatePacket.ObjectDataBlock terseBlock = 3438 ImprovedTerseObjectUpdatePacket.ObjectDataBlock terseBlock =
3436 CreateAvatarImprovedBlock(localID, position, velocity,rotation); 3439 CreateAvatarImprovedBlock(localID, position, velocity,rotation);
3437 3440
3438 lock (m_avatarTerseUpdates) 3441 lock (m_avatarTerseUpdates_.SyncRoot)
3439 { 3442 {
3440 m_avatarTerseUpdates.Add(terseBlock); 3443 m_avatarTerseUpdates_.Enqueue(DateTime.Now.ToOADate(), terseBlock, localID);
3441 3444
3442 // If packet is full or own movement packet, send it. 3445 // If packet is full or own movement packet, send it.
3443 if (m_avatarTerseUpdates.Count >= m_avatarTerseUpdatesPerPacket) 3446 if (m_avatarTerseUpdates_.Count >= m_avatarTerseUpdatesPerPacket)
3444 { 3447 {
3445 ProcessAvatarTerseUpdates(this, null); 3448 ProcessAvatarTerseUpdates(this, null);
3446 } 3449 }
3447 else if (m_avatarTerseUpdates.Count == 1) 3450 else if (m_avatarTerseUpdates_.Count == 1)
3448 { 3451 {
3449 lock (m_avatarTerseUpdateTimer) 3452 lock (m_avatarTerseUpdateTimer)
3450 m_avatarTerseUpdateTimer.Start(); 3453 m_avatarTerseUpdateTimer.Start();
@@ -3454,7 +3457,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3454 3457
3455 private void ProcessAvatarTerseUpdates(object sender, ElapsedEventArgs e) 3458 private void ProcessAvatarTerseUpdates(object sender, ElapsedEventArgs e)
3456 { 3459 {
3457 lock (m_avatarTerseUpdates) 3460 lock (m_avatarTerseUpdates_.SyncRoot)
3458 { 3461 {
3459 ImprovedTerseObjectUpdatePacket terse = (ImprovedTerseObjectUpdatePacket)PacketPool.Instance.GetPacket(PacketType.ImprovedTerseObjectUpdate); 3462 ImprovedTerseObjectUpdatePacket terse = (ImprovedTerseObjectUpdatePacket)PacketPool.Instance.GetPacket(PacketType.ImprovedTerseObjectUpdate);
3460 3463
@@ -3465,8 +3468,8 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3465 (ushort)(Scene.TimeDilation * ushort.MaxValue); 3468 (ushort)(Scene.TimeDilation * ushort.MaxValue);
3466 3469
3467 int max = m_avatarTerseUpdatesPerPacket; 3470 int max = m_avatarTerseUpdatesPerPacket;
3468 if (max > m_avatarTerseUpdates.Count) 3471 if (max > m_avatarTerseUpdates_.Count)
3469 max = m_avatarTerseUpdates.Count; 3472 max = m_avatarTerseUpdates_.Count;
3470 3473
3471 int count = 0; 3474 int count = 0;
3472 int size = 0; 3475 int size = 0;
@@ -3474,30 +3477,30 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3474 byte[] zerobuffer = new byte[1024]; 3477 byte[] zerobuffer = new byte[1024];
3475 byte[] blockbuffer = new byte[1024]; 3478 byte[] blockbuffer = new byte[1024];
3476 3479
3480 Queue<ImprovedTerseObjectUpdatePacket.ObjectDataBlock> updates = new Queue<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>();
3481
3477 for (count = 0 ; count < max ; count++) 3482 for (count = 0 ; count < max ; count++)
3478 { 3483 {
3479 int length = 0; 3484 int length = 0;
3480 m_avatarTerseUpdates[count].ToBytes(blockbuffer, ref length); 3485 m_avatarTerseUpdates_.Peek().ToBytes(blockbuffer, ref length);
3481 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer); 3486 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer);
3482 if (size + length > Packet.MTU) 3487 if (size + length > Packet.MTU)
3483 break; 3488 break;
3484 size += length; 3489 size += length;
3490 updates.Enqueue(m_avatarTerseUpdates_.Dequeue());
3485 } 3491 }
3486 3492
3487 terse.ObjectData = new ImprovedTerseObjectUpdatePacket.ObjectDataBlock[count]; 3493 terse.ObjectData = new ImprovedTerseObjectUpdatePacket.ObjectDataBlock[count];
3488 3494
3489 for (int i = 0 ; i < count ; i++) 3495 for (int i = 0 ; i < count ; i++)
3490 { 3496 terse.ObjectData[i] = updates.Dequeue();
3491 terse.ObjectData[i] = m_avatarTerseUpdates[0];
3492 m_avatarTerseUpdates.RemoveAt(0);
3493 }
3494 3497
3495 terse.Header.Reliable = false; 3498 terse.Header.Reliable = false;
3496 terse.Header.Zerocoded = true; 3499 terse.Header.Zerocoded = true;
3497 // FIXME: Move this to ThrottleOutPacketType.State when the real prioritization code is committed 3500 // FIXME: Move this to ThrottleOutPacketType.State when the real prioritization code is committed
3498 OutPacket(terse, ThrottleOutPacketType.Task); 3501 OutPacket(terse, ThrottleOutPacketType.Task);
3499 3502
3500 if (m_avatarTerseUpdates.Count == 0) 3503 if (m_avatarTerseUpdates_.Count == 0)
3501 { 3504 {
3502 lock (m_avatarTerseUpdateTimer) 3505 lock (m_avatarTerseUpdateTimer)
3503 m_avatarTerseUpdateTimer.Stop(); 3506 m_avatarTerseUpdateTimer.Stop();
@@ -3660,14 +3663,14 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3660 objectData.TextureAnim = textureanim; 3663 objectData.TextureAnim = textureanim;
3661 } 3664 }
3662 3665
3663 lock (m_primFullUpdates) 3666 lock (m_primFullUpdates_.SyncRoot)
3664 { 3667 {
3665 if (m_primFullUpdates.Count == 0) 3668 if (m_primFullUpdates_.Count == 0)
3666 m_primFullUpdateTimer.Start(); 3669 m_primFullUpdateTimer.Start();
3667 3670
3668 m_primFullUpdates.Add(objectData); 3671 m_primFullUpdates_.Enqueue(DateTime.Now.ToOADate(), objectData, localID);
3669 3672
3670 if (m_primFullUpdates.Count >= m_primFullUpdatesPerPacket) 3673 if (m_primFullUpdates_.Count >= m_primFullUpdatesPerPacket)
3671 ProcessPrimFullUpdates(this, null); 3674 ProcessPrimFullUpdates(this, null);
3672 } 3675 }
3673 } 3676 }
@@ -3690,9 +3693,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3690 3693
3691 void ProcessPrimFullUpdates(object sender, ElapsedEventArgs e) 3694 void ProcessPrimFullUpdates(object sender, ElapsedEventArgs e)
3692 { 3695 {
3693 lock (m_primFullUpdates) 3696 lock (m_primFullUpdates_.SyncRoot)
3694 { 3697 {
3695 if (m_primFullUpdates.Count == 0 && m_primFullUpdateTimer.Enabled) 3698 if (m_primFullUpdates_.Count == 0 && m_primFullUpdateTimer.Enabled)
3696 { 3699 {
3697 lock (m_primFullUpdateTimer) 3700 lock (m_primFullUpdateTimer)
3698 m_primFullUpdateTimer.Stop(); 3701 m_primFullUpdateTimer.Stop();
@@ -3709,7 +3712,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3709 outPacket.RegionData.TimeDilation = 3712 outPacket.RegionData.TimeDilation =
3710 (ushort)(Scene.TimeDilation * ushort.MaxValue); 3713 (ushort)(Scene.TimeDilation * ushort.MaxValue);
3711 3714
3712 int max = m_primFullUpdates.Count; 3715 int max = m_primFullUpdates_.Count;
3713 if (max > m_primFullUpdatesPerPacket) 3716 if (max > m_primFullUpdatesPerPacket)
3714 max = m_primFullUpdatesPerPacket; 3717 max = m_primFullUpdatesPerPacket;
3715 3718
@@ -3719,29 +3722,29 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3719 byte[] zerobuffer = new byte[1024]; 3722 byte[] zerobuffer = new byte[1024];
3720 byte[] blockbuffer = new byte[1024]; 3723 byte[] blockbuffer = new byte[1024];
3721 3724
3725 Queue<ObjectUpdatePacket.ObjectDataBlock> updates = new Queue<ObjectUpdatePacket.ObjectDataBlock>();
3726
3722 for (count = 0 ; count < max ; count++) 3727 for (count = 0 ; count < max ; count++)
3723 { 3728 {
3724 int length = 0; 3729 int length = 0;
3725 m_primFullUpdates[count].ToBytes(blockbuffer, ref length); 3730 m_primFullUpdates_.Peek().ToBytes(blockbuffer, ref length);
3726 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer); 3731 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer);
3727 if (size + length > Packet.MTU) 3732 if (size + length > Packet.MTU)
3728 break; 3733 break;
3729 size += length; 3734 size += length;
3735 updates.Enqueue(m_primFullUpdates_.Dequeue());
3730 } 3736 }
3731 3737
3732 outPacket.ObjectData = 3738 outPacket.ObjectData =
3733 new ObjectUpdatePacket.ObjectDataBlock[count]; 3739 new ObjectUpdatePacket.ObjectDataBlock[count];
3734 3740
3735 for (int index = 0 ; index < count ; index++) 3741 for (int index = 0 ; index < count ; index++)
3736 { 3742 outPacket.ObjectData[index] = updates.Dequeue();
3737 outPacket.ObjectData[index] = m_primFullUpdates[0];
3738 m_primFullUpdates.RemoveAt(0);
3739 }
3740 3743
3741 outPacket.Header.Zerocoded = true; 3744 outPacket.Header.Zerocoded = true;
3742 OutPacket(outPacket, ThrottleOutPacketType.State); 3745 OutPacket(outPacket, ThrottleOutPacketType.State);
3743 3746
3744 if (m_primFullUpdates.Count == 0 && m_primFullUpdateTimer.Enabled) 3747 if (m_primFullUpdates_.Count == 0 && m_primFullUpdateTimer.Enabled)
3745 lock (m_primFullUpdateTimer) 3748 lock (m_primFullUpdateTimer)
3746 m_primFullUpdateTimer.Stop(); 3749 m_primFullUpdateTimer.Stop();
3747 } 3750 }
@@ -3763,23 +3766,23 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3763 CreatePrimImprovedBlock(localID, position, rotation, 3766 CreatePrimImprovedBlock(localID, position, rotation,
3764 velocity, rotationalvelocity, state); 3767 velocity, rotationalvelocity, state);
3765 3768
3766 lock (m_primTerseUpdates) 3769 lock (m_primTerseUpdates_.SyncRoot)
3767 { 3770 {
3768 if (m_primTerseUpdates.Count == 0) 3771 if (m_primTerseUpdates_.Count == 0)
3769 m_primTerseUpdateTimer.Start(); 3772 m_primTerseUpdateTimer.Start();
3770 3773
3771 m_primTerseUpdates.Add(objectData); 3774 m_primTerseUpdates_.Enqueue(DateTime.Now.ToOADate(), objectData, localID);
3772 3775
3773 if (m_primTerseUpdates.Count >= m_primTerseUpdatesPerPacket) 3776 if (m_primTerseUpdates_.Count >= m_primTerseUpdatesPerPacket)
3774 ProcessPrimTerseUpdates(this, null); 3777 ProcessPrimTerseUpdates(this, null);
3775 } 3778 }
3776 } 3779 }
3777 3780
3778 void ProcessPrimTerseUpdates(object sender, ElapsedEventArgs e) 3781 void ProcessPrimTerseUpdates(object sender, ElapsedEventArgs e)
3779 { 3782 {
3780 lock (m_primTerseUpdates) 3783 lock (m_primTerseUpdates_.SyncRoot)
3781 { 3784 {
3782 if (m_primTerseUpdates.Count == 0) 3785 if (m_primTerseUpdates_.Count == 0)
3783 { 3786 {
3784 lock (m_primTerseUpdateTimer) 3787 lock (m_primTerseUpdateTimer)
3785 m_primTerseUpdateTimer.Stop(); 3788 m_primTerseUpdateTimer.Stop();
@@ -3797,7 +3800,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3797 outPacket.RegionData.TimeDilation = 3800 outPacket.RegionData.TimeDilation =
3798 (ushort)(Scene.TimeDilation * ushort.MaxValue); 3801 (ushort)(Scene.TimeDilation * ushort.MaxValue);
3799 3802
3800 int max = m_primTerseUpdates.Count; 3803 int max = m_primTerseUpdates_.Count;
3801 if (max > m_primTerseUpdatesPerPacket) 3804 if (max > m_primTerseUpdatesPerPacket)
3802 max = m_primTerseUpdatesPerPacket; 3805 max = m_primTerseUpdatesPerPacket;
3803 3806
@@ -3807,14 +3810,17 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3807 byte[] zerobuffer = new byte[1024]; 3810 byte[] zerobuffer = new byte[1024];
3808 byte[] blockbuffer = new byte[1024]; 3811 byte[] blockbuffer = new byte[1024];
3809 3812
3813 Queue<ImprovedTerseObjectUpdatePacket.ObjectDataBlock> updates = new Queue<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>();
3814
3810 for (count = 0 ; count < max ; count++) 3815 for (count = 0 ; count < max ; count++)
3811 { 3816 {
3812 int length = 0; 3817 int length = 0;
3813 m_primTerseUpdates[count].ToBytes(blockbuffer, ref length); 3818 m_primTerseUpdates_.Peek().ToBytes(blockbuffer, ref length);
3814 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer); 3819 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer);
3815 if (size + length > Packet.MTU) 3820 if (size + length > Packet.MTU)
3816 break; 3821 break;
3817 size += length; 3822 size += length;
3823 updates.Enqueue(m_primTerseUpdates_.Dequeue());
3818 } 3824 }
3819 3825
3820 outPacket.ObjectData = 3826 outPacket.ObjectData =
@@ -3822,16 +3828,13 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3822 ObjectDataBlock[count]; 3828 ObjectDataBlock[count];
3823 3829
3824 for (int index = 0 ; index < count ; index++) 3830 for (int index = 0 ; index < count ; index++)
3825 { 3831 outPacket.ObjectData[index] = updates.Dequeue();
3826 outPacket.ObjectData[index] = m_primTerseUpdates[0];
3827 m_primTerseUpdates.RemoveAt(0);
3828 }
3829 3832
3830 outPacket.Header.Reliable = false; 3833 outPacket.Header.Reliable = false;
3831 outPacket.Header.Zerocoded = true; 3834 outPacket.Header.Zerocoded = true;
3832 OutPacket(outPacket, ThrottleOutPacketType.State); 3835 OutPacket(outPacket, ThrottleOutPacketType.State);
3833 3836
3834 if (m_primTerseUpdates.Count == 0) 3837 if (m_primTerseUpdates_.Count == 0)
3835 lock (m_primTerseUpdateTimer) 3838 lock (m_primTerseUpdateTimer)
3836 m_primTerseUpdateTimer.Stop(); 3839 m_primTerseUpdateTimer.Stop();
3837 } 3840 }
@@ -3839,15 +3842,15 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3839 3842
3840 public void FlushPrimUpdates() 3843 public void FlushPrimUpdates()
3841 { 3844 {
3842 while (m_primFullUpdates.Count > 0) 3845 while (m_primFullUpdates_.Count > 0)
3843 { 3846 {
3844 ProcessPrimFullUpdates(this, null); 3847 ProcessPrimFullUpdates(this, null);
3845 } 3848 }
3846 while (m_primTerseUpdates.Count > 0) 3849 while (m_primTerseUpdates_.Count > 0)
3847 { 3850 {
3848 ProcessPrimTerseUpdates(this, null); 3851 ProcessPrimTerseUpdates(this, null);
3849 } 3852 }
3850 while (m_avatarTerseUpdates.Count > 0) 3853 while (m_avatarTerseUpdates_.Count > 0)
3851 { 3854 {
3852 ProcessAvatarTerseUpdates(this, null); 3855 ProcessAvatarTerseUpdates(this, null);
3853 } 3856 }
@@ -10578,5 +10581,136 @@ namespace OpenSim.Region.ClientStack.LindenUDP
10578 pack.TextureData.TextureID = textureID; 10581 pack.TextureData.TextureID = textureID;
10579 OutPacket(pack, ThrottleOutPacketType.Task); 10582 OutPacket(pack, ThrottleOutPacketType.Task);
10580 } 10583 }
10584
10585 #region PriorityQueue
10586 private class PriorityQueue<TPriority, TValue>
10587 {
10588 private MinHeap<MinHeapItem>[] heaps = new MinHeap<MinHeapItem>[1];
10589 private Dictionary<uint, LookupItem> lookup_table = new Dictionary<uint, LookupItem>();
10590 private Comparison<TPriority> comparison;
10591 private object sync_root = new object();
10592
10593 internal PriorityQueue() :
10594 this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY, Comparer<TPriority>.Default) { }
10595 internal PriorityQueue(int capacity) :
10596 this(capacity, Comparer<TPriority>.Default) { }
10597 internal PriorityQueue(IComparer<TPriority> comparer) :
10598 this(new Comparison<TPriority>(comparer.Compare)) { }
10599 internal PriorityQueue(Comparison<TPriority> comparison) :
10600 this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY, comparison) { }
10601 internal PriorityQueue(int capacity, IComparer<TPriority> comparer) :
10602 this(capacity, new Comparison<TPriority>(comparer.Compare)) { }
10603 internal PriorityQueue(int capacity, Comparison<TPriority> comparison)
10604 {
10605 for (int i = 0; i < heaps.Length; ++i)
10606 heaps[i] = new MinHeap<MinHeapItem>(capacity);
10607 this.comparison = comparison;
10608 }
10609
10610 internal object SyncRoot { get { return this.sync_root; } }
10611 internal int Count
10612 {
10613 get
10614 {
10615 int count = 0;
10616 for (int i = 0; i < heaps.Length; ++i)
10617 count = heaps[i].Count;
10618 return count;
10619 }
10620 }
10621
10622 internal bool Enqueue(TPriority priority, TValue value, uint local_id)
10623 {
10624 LookupItem item;
10625
10626 if (lookup_table.TryGetValue(local_id, out item))
10627 {
10628 item.Heap[item.Handle] = new MinHeapItem(priority, value, local_id, this.comparison);
10629 return false;
10630 }
10631 else
10632 {
10633 item.Heap = heaps[0];
10634 item.Heap.Add(new MinHeapItem(priority, value, local_id, this.comparison), ref item.Handle);
10635 lookup_table.Add(local_id, item);
10636 return true;
10637 }
10638 }
10639
10640 internal TValue Peek()
10641 {
10642 for (int i = 0; i < heaps.Length; ++i)
10643 if (heaps[i].Count > 0)
10644 return heaps[i].Min().Value;
10645 throw new InvalidOperationException(string.Format("The {0} is empty", this.GetType().ToString()));
10646 }
10647
10648 internal TValue Dequeue()
10649 {
10650 for (int i = 0; i < heaps.Length; ++i)
10651 {
10652 if (heaps[i].Count > 0)
10653 {
10654 MinHeapItem item = heaps[i].RemoveMin();
10655 lookup_table.Remove(item.LocalID);
10656 return item.Value;
10657 }
10658 }
10659 throw new InvalidOperationException(string.Format("The {0} is empty", this.GetType().ToString()));
10660 }
10661
10662 #region MinHeapItem
10663 private struct MinHeapItem : IComparable<MinHeapItem>
10664 {
10665 private TPriority priority;
10666 private TValue value;
10667 private uint local_id;
10668 private Comparison<TPriority> comparison;
10669
10670 internal MinHeapItem(TPriority priority, TValue value, uint local_id) :
10671 this(priority, value, local_id, Comparer<TPriority>.Default) { }
10672 internal MinHeapItem(TPriority priority, TValue value, uint local_id, IComparer<TPriority> comparer) :
10673 this(priority, value, local_id, new Comparison<TPriority>(comparer.Compare)) { }
10674 internal MinHeapItem(TPriority priority, TValue value, uint local_id, Comparison<TPriority> comparison)
10675 {
10676 this.priority = priority;
10677 this.value = value;
10678 this.local_id = local_id;
10679 this.comparison = comparison;
10680 }
10681
10682 internal TPriority Priority { get { return this.priority; } }
10683 internal TValue Value { get { return this.value; } }
10684 internal uint LocalID { get { return this.local_id; } }
10685
10686 public override string ToString()
10687 {
10688 StringBuilder sb = new StringBuilder();
10689 sb.Append("[");
10690 if (this.priority != null)
10691 sb.Append(this.priority.ToString());
10692 sb.Append(",");
10693 if (this.value != null)
10694 sb.Append(this.value.ToString());
10695 sb.Append("]");
10696 return sb.ToString();
10697 }
10698
10699 public int CompareTo(MinHeapItem other)
10700 {
10701 return this.comparison(this.priority, other.priority);
10702 }
10703 }
10704 #endregion
10705
10706 #region LookupItem
10707 private struct LookupItem {
10708 internal MinHeap<MinHeapItem> Heap;
10709 internal IHandle Handle;
10710 }
10711 #endregion
10712 }
10713 #endregion
10714
10581 } 10715 }
10582} 10716}