From 19c6d1d569e081418e139d139c15ea66640288ba Mon Sep 17 00:00:00 2001 From: Mic Bowman Date: Wed, 6 Apr 2011 09:26:38 -0700 Subject: Split the priority queue class into a seperate file. LLClientView is big enough. --- .../Region/ClientStack/LindenUDP/LLClientView.cs | 205 ----------------- .../Region/ClientStack/LindenUDP/PriorityQueue.cs | 245 +++++++++++++++++++++ 2 files changed, 245 insertions(+), 205 deletions(-) create mode 100644 OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs (limited to 'OpenSim/Region/ClientStack/LindenUDP') diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs index a3f2c15..a724099 100644 --- a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs +++ b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs @@ -11805,209 +11805,6 @@ namespace OpenSim.Region.ClientStack.LindenUDP OutPacket(pack, ThrottleOutPacketType.Task); } - #region PriorityQueue - public class PriorityQueue - { - internal 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; - private MinHeap[] m_heaps = new MinHeap[m_numberOfQueues]; - private Dictionary m_lookupTable; - private object m_syncRoot = new object(); - private uint m_nextQueue = 0; - private UInt64 m_nextRequest = 0; - - internal PriorityQueue() : - this(MinHeap.DEFAULT_CAPACITY) { } - internal PriorityQueue(int capacity) - { - m_lookupTable = new Dictionary(capacity); - - for (int i = 0; i < m_heaps.Length; ++i) - m_heaps[i] = new MinHeap(capacity); - } - - public object SyncRoot { get { return this.m_syncRoot; } } - - internal int Count - { - get - { - int count = 0; - for (int i = 0; i < m_heaps.Length; ++i) - count += m_heaps[i].Count; - return count; - } - } - - public bool Enqueue(uint pqueue, EntityUpdate value) - { - LookupItem lookup; - - uint localid = value.Entity.LocalId; - UInt64 entry = m_nextRequest++; - if (m_lookupTable.TryGetValue(localid, out lookup)) - { - entry = lookup.Heap[lookup.Handle].EntryOrder; - value.Flags |= lookup.Heap[lookup.Handle].Value.Flags; - lookup.Heap.Remove(lookup.Handle); - } - - pqueue = Util.Clamp(pqueue, 0, m_numberOfQueues - 1); - lookup.Heap = m_heaps[pqueue]; - lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle); - m_lookupTable[localid] = lookup; - - return true; - } - - internal bool TryDequeue(out EntityUpdate value, out Int32 timeinqueue) - { - for (int i = 0; i < m_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); - if (m_heaps[h].Count > 0) - { - m_nextQueue = (uint)((h + 1) % m_numberOfQueues); - - MinHeapItem item = m_heaps[h].RemoveMin(); - m_lookupTable.Remove(item.Value.Entity.LocalId); - timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); - value = item.Value; - - return true; - } - } - - timeinqueue = 0; - value = default(EntityUpdate); - return false; - } - - internal void Reprioritize(UpdatePriorityHandler handler) - { - MinHeapItem item; - foreach (LookupItem lookup in new List(this.m_lookupTable.Values)) - { - if (lookup.Heap.TryGetValue(lookup.Handle, out item)) - { - uint pqueue = item.PriorityQueue; - uint localid = item.Value.Entity.LocalId; - - if (handler(ref pqueue, item.Value.Entity)) - { - // unless the priority queue has changed, there is no need to modify - // the entry - pqueue = Util.Clamp(pqueue, 0, m_numberOfQueues - 1); - if (pqueue != item.PriorityQueue) - { - lookup.Heap.Remove(lookup.Handle); - - LookupItem litem = lookup; - litem.Heap = m_heaps[pqueue]; - litem.Heap.Add(new MinHeapItem(pqueue, item), ref litem.Handle); - m_lookupTable[localid] = litem; - } - } - else - { - m_log.WarnFormat("[LLCLIENTVIEW]: UpdatePriorityHandler returned false for {0}",item.Value.Entity.UUID); - lookup.Heap.Remove(lookup.Handle); - this.m_lookupTable.Remove(localid); - } - } - } - } - - public override string ToString() - { - string s = ""; - for (int i = 0; i < m_numberOfQueues; i++) - { - if (s != "") s += ","; - s += m_heaps[i].Count.ToString(); - } - return s; - } - - #region MinHeapItem - private struct MinHeapItem : IComparable - { - private EntityUpdate value; - internal EntityUpdate Value { - get { - return this.value; - } - } - - private uint pqueue; - internal uint PriorityQueue { - get { - return this.pqueue; - } - } - - private Int32 entrytime; - internal Int32 EntryTime { - get { - return this.entrytime; - } - } - - private UInt64 entryorder; - internal UInt64 EntryOrder - { - get { - return this.entryorder; - } - } - - internal MinHeapItem(uint pqueue, MinHeapItem other) - { - this.entrytime = other.entrytime; - this.entryorder = other.entryorder; - this.value = other.value; - this.pqueue = pqueue; - } - - internal MinHeapItem(uint pqueue, UInt64 entryorder, EntityUpdate value) - { - this.entrytime = Util.EnvironmentTickCount(); - this.entryorder = entryorder; - this.value = value; - this.pqueue = pqueue; - } - - public override string ToString() - { - return String.Format("[{0},{1},{2}]",pqueue,entryorder,value.Entity.LocalId); - } - - public int CompareTo(MinHeapItem other) - { - // I'm assuming that the root part of an SOG is added to the update queue - // before the component parts - return Comparer.Default.Compare(this.EntryOrder, other.EntryOrder); - } - } - #endregion - - #region LookupItem - private struct LookupItem - { - internal MinHeap Heap; - internal IHandle Handle; - } - #endregion - } - public struct PacketProcessor { public PacketMethod method; @@ -12028,8 +11825,6 @@ namespace OpenSim.Region.ClientStack.LindenUDP } } - #endregion - public static OSD BuildEvent(string eventName, OSD eventBody) { OSDMap osdEvent = new OSDMap(2); diff --git a/OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs b/OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs new file mode 100644 index 0000000..364ce4b --- /dev/null +++ b/OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs @@ -0,0 +1,245 @@ +/* + * Copyright (c) Contributors, http://opensimulator.org/ + * See CONTRIBUTORS.TXT for a full list of copyright holders. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of the OpenSimulator Project nor the + * names of its contributors may be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +using System; +using System.Collections; +using System.Collections.Generic; +using System.Reflection; + +using OpenSim.Framework; +using OpenSim.Framework.Client; +using log4net; + +namespace OpenSim.Region.ClientStack.LindenUDP +{ + public class PriorityQueue + { + private static readonly ILog m_log = LogManager.GetLogger(MethodBase.GetCurrentMethod().DeclaringType); + + internal 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; + + private MinHeap[] m_heaps = new MinHeap[m_numberOfQueues]; + private Dictionary m_lookupTable; + private uint m_nextQueue = 0; + private UInt64 m_nextRequest = 0; + + private object m_syncRoot = new object(); + public object SyncRoot { + get { return this.m_syncRoot; } + } + + internal PriorityQueue() : this(MinHeap.DEFAULT_CAPACITY) { } + + internal PriorityQueue(int capacity) + { + m_lookupTable = new Dictionary(capacity); + + for (int i = 0; i < m_heaps.Length; ++i) + m_heaps[i] = new MinHeap(capacity); + } + + internal int Count + { + get + { + int count = 0; + for (int i = 0; i < m_heaps.Length; ++i) + count += m_heaps[i].Count; + return count; + } + } + + public bool Enqueue(uint pqueue, EntityUpdate value) + { + LookupItem lookup; + + uint localid = value.Entity.LocalId; + UInt64 entry = m_nextRequest++; + if (m_lookupTable.TryGetValue(localid, out lookup)) + { + entry = lookup.Heap[lookup.Handle].EntryOrder; + value.Flags |= lookup.Heap[lookup.Handle].Value.Flags; + lookup.Heap.Remove(lookup.Handle); + } + + pqueue = Util.Clamp(pqueue, 0, m_numberOfQueues - 1); + lookup.Heap = m_heaps[pqueue]; + lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle); + m_lookupTable[localid] = lookup; + + return true; + } + + internal bool TryDequeue(out EntityUpdate value, out Int32 timeinqueue) + { + for (int i = 0; i < m_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); + if (m_heaps[h].Count > 0) + { + m_nextQueue = (uint)((h + 1) % m_numberOfQueues); + + MinHeapItem item = m_heaps[h].RemoveMin(); + m_lookupTable.Remove(item.Value.Entity.LocalId); + timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); + value = item.Value; + + return true; + } + } + + timeinqueue = 0; + value = default(EntityUpdate); + return false; + } + + internal void Reprioritize(UpdatePriorityHandler handler) + { + MinHeapItem item; + foreach (LookupItem lookup in new List(this.m_lookupTable.Values)) + { + if (lookup.Heap.TryGetValue(lookup.Handle, out item)) + { + uint pqueue = item.PriorityQueue; + uint localid = item.Value.Entity.LocalId; + + if (handler(ref pqueue, item.Value.Entity)) + { + // unless the priority queue has changed, there is no need to modify + // the entry + pqueue = Util.Clamp(pqueue, 0, m_numberOfQueues - 1); + if (pqueue != item.PriorityQueue) + { + lookup.Heap.Remove(lookup.Handle); + + LookupItem litem = lookup; + litem.Heap = m_heaps[pqueue]; + litem.Heap.Add(new MinHeapItem(pqueue, item), ref litem.Handle); + m_lookupTable[localid] = litem; + } + } + else + { + // m_log.WarnFormat("[PQUEUE]: UpdatePriorityHandler returned false for {0}",item.Value.Entity.UUID); + lookup.Heap.Remove(lookup.Handle); + this.m_lookupTable.Remove(localid); + } + } + } + } + + public override string ToString() + { + string s = ""; + for (int i = 0; i < m_numberOfQueues; i++) + { + if (s != "") s += ","; + s += m_heaps[i].Count.ToString(); + } + return s; + } + +#region MinHeapItem + private struct MinHeapItem : IComparable + { + private EntityUpdate value; + internal EntityUpdate Value { + get { + return this.value; + } + } + + private uint pqueue; + internal uint PriorityQueue { + get { + return this.pqueue; + } + } + + private Int32 entrytime; + internal Int32 EntryTime { + get { + return this.entrytime; + } + } + + private UInt64 entryorder; + internal UInt64 EntryOrder + { + get { + return this.entryorder; + } + } + + internal MinHeapItem(uint pqueue, MinHeapItem other) + { + this.entrytime = other.entrytime; + this.entryorder = other.entryorder; + this.value = other.value; + this.pqueue = pqueue; + } + + internal MinHeapItem(uint pqueue, UInt64 entryorder, EntityUpdate value) + { + this.entrytime = Util.EnvironmentTickCount(); + this.entryorder = entryorder; + this.value = value; + this.pqueue = pqueue; + } + + public override string ToString() + { + return String.Format("[{0},{1},{2}]",pqueue,entryorder,value.Entity.LocalId); + } + + public int CompareTo(MinHeapItem other) + { + // I'm assuming that the root part of an SOG is added to the update queue + // before the component parts + return Comparer.Default.Compare(this.EntryOrder, other.EntryOrder); + } + } +#endregion + +#region LookupItem + private struct LookupItem + { + internal MinHeap Heap; + internal IHandle Handle; + } +#endregion + } +} -- cgit v1.1