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/PriorityQueue.cs | 245 +++++++++++++++++++++ 1 file changed, 245 insertions(+) create mode 100644 OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs (limited to 'OpenSim/Region/ClientStack/LindenUDP/PriorityQueue.cs') 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