diff options
author | Mic Bowman | 2011-04-06 09:26:38 -0700 |
---|---|---|
committer | Mic Bowman | 2011-04-10 16:57:02 -0700 |
commit | 19c6d1d569e081418e139d139c15ea66640288ba (patch) | |
tree | 8c0f16e3f67c3751e262c6e8320bc0ff5e85461a /OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs | |
parent | Fix a bug in the computation of the RTO. Basically... the RTO (the (diff) | |
download | opensim-SC_OLD-19c6d1d569e081418e139d139c15ea66640288ba.zip opensim-SC_OLD-19c6d1d569e081418e139d139c15ea66640288ba.tar.gz opensim-SC_OLD-19c6d1d569e081418e139d139c15ea66640288ba.tar.bz2 opensim-SC_OLD-19c6d1d569e081418e139d139c15ea66640288ba.tar.xz |
Split the priority queue class into a seperate file. LLClientView
is big enough.
Diffstat (limited to '')
-rw-r--r-- | OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs | 205 |
1 files changed, 0 insertions, 205 deletions
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 | |||
11805 | OutPacket(pack, ThrottleOutPacketType.Task); | 11805 | OutPacket(pack, ThrottleOutPacketType.Task); |
11806 | } | 11806 | } |
11807 | 11807 | ||
11808 | #region PriorityQueue | ||
11809 | public class PriorityQueue | ||
11810 | { | ||
11811 | internal delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity); | ||
11812 | |||
11813 | // Heap[0] for self updates | ||
11814 | // Heap[1..12] for entity updates | ||
11815 | |||
11816 | internal const uint m_numberOfQueues = 12; | ||
11817 | private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[m_numberOfQueues]; | ||
11818 | private Dictionary<uint, LookupItem> m_lookupTable; | ||
11819 | private object m_syncRoot = new object(); | ||
11820 | private uint m_nextQueue = 0; | ||
11821 | private UInt64 m_nextRequest = 0; | ||
11822 | |||
11823 | internal PriorityQueue() : | ||
11824 | this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { } | ||
11825 | internal PriorityQueue(int capacity) | ||
11826 | { | ||
11827 | m_lookupTable = new Dictionary<uint, LookupItem>(capacity); | ||
11828 | |||
11829 | for (int i = 0; i < m_heaps.Length; ++i) | ||
11830 | m_heaps[i] = new MinHeap<MinHeapItem>(capacity); | ||
11831 | } | ||
11832 | |||
11833 | public object SyncRoot { get { return this.m_syncRoot; } } | ||
11834 | |||
11835 | internal int Count | ||
11836 | { | ||
11837 | get | ||
11838 | { | ||
11839 | int count = 0; | ||
11840 | for (int i = 0; i < m_heaps.Length; ++i) | ||
11841 | count += m_heaps[i].Count; | ||
11842 | return count; | ||
11843 | } | ||
11844 | } | ||
11845 | |||
11846 | public bool Enqueue(uint pqueue, EntityUpdate value) | ||
11847 | { | ||
11848 | LookupItem lookup; | ||
11849 | |||
11850 | uint localid = value.Entity.LocalId; | ||
11851 | UInt64 entry = m_nextRequest++; | ||
11852 | if (m_lookupTable.TryGetValue(localid, out lookup)) | ||
11853 | { | ||
11854 | entry = lookup.Heap[lookup.Handle].EntryOrder; | ||
11855 | value.Flags |= lookup.Heap[lookup.Handle].Value.Flags; | ||
11856 | lookup.Heap.Remove(lookup.Handle); | ||
11857 | } | ||
11858 | |||
11859 | pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1); | ||
11860 | lookup.Heap = m_heaps[pqueue]; | ||
11861 | lookup.Heap.Add(new MinHeapItem(pqueue, entry, value), ref lookup.Handle); | ||
11862 | m_lookupTable[localid] = lookup; | ||
11863 | |||
11864 | return true; | ||
11865 | } | ||
11866 | |||
11867 | internal bool TryDequeue(out EntityUpdate value, out Int32 timeinqueue) | ||
11868 | { | ||
11869 | for (int i = 0; i < m_numberOfQueues; ++i) | ||
11870 | { | ||
11871 | // To get the fair queing, we cycle through each of the | ||
11872 | // queues when finding an element to dequeue, this code | ||
11873 | // assumes that the distribution of updates in the queues | ||
11874 | // is polynomial, probably quadractic (eg distance of PI * R^2) | ||
11875 | uint h = (uint)((m_nextQueue + i) % m_numberOfQueues); | ||
11876 | if (m_heaps[h].Count > 0) | ||
11877 | { | ||
11878 | m_nextQueue = (uint)((h + 1) % m_numberOfQueues); | ||
11879 | |||
11880 | MinHeapItem item = m_heaps[h].RemoveMin(); | ||
11881 | m_lookupTable.Remove(item.Value.Entity.LocalId); | ||
11882 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); | ||
11883 | value = item.Value; | ||
11884 | |||
11885 | return true; | ||
11886 | } | ||
11887 | } | ||
11888 | |||
11889 | timeinqueue = 0; | ||
11890 | value = default(EntityUpdate); | ||
11891 | return false; | ||
11892 | } | ||
11893 | |||
11894 | internal void Reprioritize(UpdatePriorityHandler handler) | ||
11895 | { | ||
11896 | MinHeapItem item; | ||
11897 | foreach (LookupItem lookup in new List<LookupItem>(this.m_lookupTable.Values)) | ||
11898 | { | ||
11899 | if (lookup.Heap.TryGetValue(lookup.Handle, out item)) | ||
11900 | { | ||
11901 | uint pqueue = item.PriorityQueue; | ||
11902 | uint localid = item.Value.Entity.LocalId; | ||
11903 | |||
11904 | if (handler(ref pqueue, item.Value.Entity)) | ||
11905 | { | ||
11906 | // unless the priority queue has changed, there is no need to modify | ||
11907 | // the entry | ||
11908 | pqueue = Util.Clamp<uint>(pqueue, 0, m_numberOfQueues - 1); | ||
11909 | if (pqueue != item.PriorityQueue) | ||
11910 | { | ||
11911 | lookup.Heap.Remove(lookup.Handle); | ||
11912 | |||
11913 | LookupItem litem = lookup; | ||
11914 | litem.Heap = m_heaps[pqueue]; | ||
11915 | litem.Heap.Add(new MinHeapItem(pqueue, item), ref litem.Handle); | ||
11916 | m_lookupTable[localid] = litem; | ||
11917 | } | ||
11918 | } | ||
11919 | else | ||
11920 | { | ||
11921 | m_log.WarnFormat("[LLCLIENTVIEW]: UpdatePriorityHandler returned false for {0}",item.Value.Entity.UUID); | ||
11922 | lookup.Heap.Remove(lookup.Handle); | ||
11923 | this.m_lookupTable.Remove(localid); | ||
11924 | } | ||
11925 | } | ||
11926 | } | ||
11927 | } | ||
11928 | |||
11929 | public override string ToString() | ||
11930 | { | ||
11931 | string s = ""; | ||
11932 | for (int i = 0; i < m_numberOfQueues; i++) | ||
11933 | { | ||
11934 | if (s != "") s += ","; | ||
11935 | s += m_heaps[i].Count.ToString(); | ||
11936 | } | ||
11937 | return s; | ||
11938 | } | ||
11939 | |||
11940 | #region MinHeapItem | ||
11941 | private struct MinHeapItem : IComparable<MinHeapItem> | ||
11942 | { | ||
11943 | private EntityUpdate value; | ||
11944 | internal EntityUpdate Value { | ||
11945 | get { | ||
11946 | return this.value; | ||
11947 | } | ||
11948 | } | ||
11949 | |||
11950 | private uint pqueue; | ||
11951 | internal uint PriorityQueue { | ||
11952 | get { | ||
11953 | return this.pqueue; | ||
11954 | } | ||
11955 | } | ||
11956 | |||
11957 | private Int32 entrytime; | ||
11958 | internal Int32 EntryTime { | ||
11959 | get { | ||
11960 | return this.entrytime; | ||
11961 | } | ||
11962 | } | ||
11963 | |||
11964 | private UInt64 entryorder; | ||
11965 | internal UInt64 EntryOrder | ||
11966 | { | ||
11967 | get { | ||
11968 | return this.entryorder; | ||
11969 | } | ||
11970 | } | ||
11971 | |||
11972 | internal MinHeapItem(uint pqueue, MinHeapItem other) | ||
11973 | { | ||
11974 | this.entrytime = other.entrytime; | ||
11975 | this.entryorder = other.entryorder; | ||
11976 | this.value = other.value; | ||
11977 | this.pqueue = pqueue; | ||
11978 | } | ||
11979 | |||
11980 | internal MinHeapItem(uint pqueue, UInt64 entryorder, EntityUpdate value) | ||
11981 | { | ||
11982 | this.entrytime = Util.EnvironmentTickCount(); | ||
11983 | this.entryorder = entryorder; | ||
11984 | this.value = value; | ||
11985 | this.pqueue = pqueue; | ||
11986 | } | ||
11987 | |||
11988 | public override string ToString() | ||
11989 | { | ||
11990 | return String.Format("[{0},{1},{2}]",pqueue,entryorder,value.Entity.LocalId); | ||
11991 | } | ||
11992 | |||
11993 | public int CompareTo(MinHeapItem other) | ||
11994 | { | ||
11995 | // I'm assuming that the root part of an SOG is added to the update queue | ||
11996 | // before the component parts | ||
11997 | return Comparer<UInt64>.Default.Compare(this.EntryOrder, other.EntryOrder); | ||
11998 | } | ||
11999 | } | ||
12000 | #endregion | ||
12001 | |||
12002 | #region LookupItem | ||
12003 | private struct LookupItem | ||
12004 | { | ||
12005 | internal MinHeap<MinHeapItem> Heap; | ||
12006 | internal IHandle Handle; | ||
12007 | } | ||
12008 | #endregion | ||
12009 | } | ||
12010 | |||
12011 | public struct PacketProcessor | 11808 | public struct PacketProcessor |
12012 | { | 11809 | { |
12013 | public PacketMethod method; | 11810 | public PacketMethod method; |
@@ -12028,8 +11825,6 @@ namespace OpenSim.Region.ClientStack.LindenUDP | |||
12028 | } | 11825 | } |
12029 | } | 11826 | } |
12030 | 11827 | ||
12031 | #endregion | ||
12032 | |||
12033 | public static OSD BuildEvent(string eventName, OSD eventBody) | 11828 | public static OSD BuildEvent(string eventName, OSD eventBody) |
12034 | { | 11829 | { |
12035 | OSDMap osdEvent = new OSDMap(2); | 11830 | OSDMap osdEvent = new OSDMap(2); |