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 --------------------- 1 file changed, 205 deletions(-) (limited to 'OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs') 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); -- cgit v1.1