3 files changed, 92 insertions, 27 deletions

diff --git a/OpenSim/Framework/IClientAPI.cs b/OpenSim/Framework/IClientAPI.cs
index eea9107..f187468 100644
--- a/OpenSim/Framework/IClientAPI.cs
+++ b/OpenSim/Framework/IClientAPI.cs
@@ -576,34 +576,69 @@ namespace OpenSim.Framework
 
     public class IEntityUpdate
     {
-        public ISceneEntity Entity;
-        public uint Flags;
+        private ISceneEntity m_entity;
+        private uint m_flags;
+        private int m_updateTime;
+
+        public ISceneEntity Entity
+        {
+            get { return m_entity; }
+        }
+
+        public uint Flags
+        {
+            get { return m_flags; }
+        }
+
+        public int UpdateTime
+        {
+            get { return m_updateTime; }
+        }
 
         public virtual void Update(IEntityUpdate update)
         {
-            this.Flags |= update.Flags;
+            m_flags |= update.Flags;
+
+            // Use the older of the updates as the updateTime
+            if (Util.EnvironmentTickCountCompare(UpdateTime, update.UpdateTime) > 0)
+                m_updateTime = update.UpdateTime;
         }
 
         public IEntityUpdate(ISceneEntity entity, uint flags)
         {
-            Entity = entity;
-            Flags = flags;
+            m_entity = entity;
+            m_flags = flags;
+            m_updateTime = Util.EnvironmentTickCount();
+        }
+
+        public IEntityUpdate(ISceneEntity entity, uint flags, Int32 updateTime)
+        {
+            m_entity = entity;
+            m_flags = flags;
+            m_updateTime = updateTime;
         }
     }
-    
 
     public class EntityUpdate : IEntityUpdate
     {
-        // public ISceneEntity Entity;
-        // public PrimUpdateFlags Flags;
-        public float TimeDilation;
+        private float m_timeDilation;
+
+        public float TimeDilation
+        {
+            get { return m_timeDilation; }
+        }
 
         public EntityUpdate(ISceneEntity entity, PrimUpdateFlags flags, float timedilation)
-            : base(entity,(uint)flags)
+            : base(entity, (uint)flags)
         {
-            //Entity = entity;
             // Flags = flags;
-            TimeDilation = timedilation;
+            m_timeDilation = timedilation;
+        }
+
+        public EntityUpdate(ISceneEntity entity, PrimUpdateFlags flags, float timedilation, Int32 updateTime)
+            : base(entity,(uint)flags,updateTime)
+        {
+            m_timeDilation = timedilation;
         }
     }
 
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;
 using OpenSim.Framework.Client;
 using log4net;
 
-namespace OpenSim.Region.ClientStack.LindenUDP
+namespace OpenSim.Framework
 {
     public class PriorityQueue
     {
         private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType);
 
-        internal delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity);
+        public delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity);
 
         // Heap[0] for self updates
         // Heap[1..12] for entity updates
 
-        internal const uint m_numberOfQueues = 12;
+        public const uint NumberOfQueues = 12;
+        public const uint ImmediateQueue = 0;
 
-        private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[m_numberOfQueues];
+        private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[NumberOfQueues];
         private Dictionary<uint, LookupItem> m_lookupTable;
         private uint m_nextQueue = 0;
         private UInt64 m_nextRequest = 0;
@@ -57,9 +58,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP
             get { return this.m_syncRoot; }
         }
 
-        internal PriorityQueue() : this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { }
+        public PriorityQueue() : this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { }
 
-        internal PriorityQueue(int capacity)
+        public PriorityQueue(int capacity)
         {
             m_lookupTable = new Dictionary<uint, LookupItem>(capacity);
 
@@ -67,7 +68,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                 m_heaps[i] = new MinHeap<MinHeapItem>(capacity);
         }
 
-        internal int Count
+        public int Count
         {
             get
             {
@@ -91,7 +92,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                 lookup.Heap.Remove(lookup.Handle);
             }
 
-            pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1);
+            pqueue = Util.Clamp<uint>(pqueue, 0, NumberOfQueues - 1);
             lookup.Heap = m_heaps[pqueue];
             lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle);
             m_lookupTable[localid] = lookup;
@@ -99,18 +100,30 @@ namespace OpenSim.Region.ClientStack.LindenUDP
             return true;
         }
 
-        internal bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue)
+        public bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue)
         {
-            for (int i = 0; i < m_numberOfQueues; ++i)
+            // If there is anything in priority queue 0, return it first no
+            // matter what else. Breaks fairness. But very useful.
+            if (m_heaps[ImmediateQueue].Count > 0)
+            {
+                MinHeapItem item = m_heaps[ImmediateQueue].RemoveMin();
+                m_lookupTable.Remove(item.Value.Entity.LocalId);
+                timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime);
+                value = item.Value;
+
+                return true;
+            }
+
+            for (int i = 0; i < NumberOfQueues; ++i)
             {
                 // To get the fair queing, we cycle through each of the
                 // queues when finding an element to dequeue, this code
                 // assumes that the distribution of updates in the queues
                 // is polynomial, probably quadractic (eg distance of PI * R^2)
-                uint h = (uint)((m_nextQueue + i) % m_numberOfQueues);
+                uint h = (uint)((m_nextQueue + i) % NumberOfQueues);
                 if (m_heaps[h].Count > 0)
                 {
-                    m_nextQueue = (uint)((h + 1) % m_numberOfQueues);
+                    m_nextQueue = (uint)((h + 1) % NumberOfQueues);
 
                     MinHeapItem item = m_heaps[h].RemoveMin();
                     m_lookupTable.Remove(item.Value.Entity.LocalId);
@@ -126,7 +139,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
             return false;
         }
 
-        internal void Reprioritize(UpdatePriorityHandler handler)
+        public void Reprioritize(UpdatePriorityHandler handler)
         {
             MinHeapItem item;
             foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values))
@@ -140,7 +153,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
                     {
                         // unless the priority queue has changed, there is no need to modify
                         // the entry
-                        pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1);
+                        pqueue = Util.Clamp<uint>(pqueue, 0, NumberOfQueues - 1);
                         if (pqueue != item.PriorityQueue)
                         {
                             lookup.Heap.Remove(lookup.Handle);
@@ -164,7 +177,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
         public override string ToString()
         {
             string s = "";
-            for (int i = 0; i < m_numberOfQueues; i++)
+            for (int i = 0; i < NumberOfQueues; i++)
             {
                 if (s != "") s += ",";
                 s += m_heaps[i].Count.ToString();
diff --git a/OpenSim/Framework/Util.cs b/OpenSim/Framework/Util.cs
index 3f676f9..366a38f 100644
--- a/OpenSim/Framework/Util.cs
+++ b/OpenSim/Framework/Util.cs
@@ -1549,6 +1549,23 @@ namespace OpenSim.Framework
             return (diff >= 0) ? diff : (diff + EnvironmentTickCountMask + 1);
         }
 
+        // Returns value of Tick Count A - TickCount B accounting for wrapping of TickCount
+        // Assumes both tcA and tcB came from previous calls to Util.EnvironmentTickCount().
+        // A positive return value indicates A occured later than B
+        public static Int32 EnvironmentTickCountCompare(Int32 tcA, Int32 tcB)
+        {
+            // A, B and TC are all between 0 and 0x3fffffff
+            int tc = EnvironmentTickCount();
+
+            if (tc - tcA >= 0)
+                tcA += EnvironmentTickCountMask + 1;
+
+            if (tc - tcB >= 0)
+                tcB += EnvironmentTickCountMask + 1;
+
+            return tcA - tcB;
+        }
+
         /// <summary>
         /// Prints the call stack at any given point. Useful for debugging.
         /// </summary>