aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
-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}