From 5a246026a076b01b60578d1499c9761f8bcf4793 Mon Sep 17 00:00:00 2001 From: UbitUmarov Date: Wed, 24 Jan 2018 04:48:10 +0000 Subject: let MinHeap self trim on empty; cleanup --- OpenSim/Framework/MinHeap.cs | 150 +++++++++++++++++++++++-------------------- 1 file changed, 80 insertions(+), 70 deletions(-) (limited to 'OpenSim') diff --git a/OpenSim/Framework/MinHeap.cs b/OpenSim/Framework/MinHeap.cs index 99ac25d..68f6668 100644 --- a/OpenSim/Framework/MinHeap.cs +++ b/OpenSim/Framework/MinHeap.cs @@ -45,8 +45,8 @@ namespace OpenSim.Framework internal void Clear() { - this.index = -1; - this.heap = null; + index = -1; + heap = null; } } @@ -55,23 +55,26 @@ namespace OpenSim.Framework internal T value; internal Handle handle; - internal HeapItem(T value, Handle handle) + internal HeapItem(T _value, Handle _handle) { - this.value = value; - this.handle = handle; + value = _value; + handle = _handle; } internal void Clear() { - if (this.handle != null) - this.handle.Clear(); - ClearRef(); + if (handle != null) + { + handle.Clear(); + handle = null; + } + value = default(T); } internal void ClearRef() { - this.value = default(T); - this.handle = null; + value = default(T); + handle = null; } } @@ -81,6 +84,7 @@ namespace OpenSim.Framework private int size; private object sync_root; private int version; + private int capacity; private Comparison comparison; @@ -90,14 +94,15 @@ namespace OpenSim.Framework public MinHeap(int capacity, IComparer comparer) : this(capacity, new Comparison(comparer.Compare)) { } public MinHeap(Comparison comparison) : this(DEFAULT_CAPACITY, comparison) { } - public MinHeap(int capacity, Comparison comparison) + public MinHeap(int _capacity, Comparison _comparison) { - this.items = new HeapItem[capacity]; - this.comparison = comparison; - this.size = this.version = 0; + capacity = _capacity; + items = new HeapItem[capacity]; + comparison = _comparison; + size = version = 0; } - public int Count { get { return this.size; } } + public int Count { get { return size; } } public bool IsReadOnly { get { return false; } } @@ -108,15 +113,16 @@ namespace OpenSim.Framework get { Handle handle = ValidateThisHandle(key); - return this.items[handle.index].value; + return items[handle.index].value; } set { Handle handle = ValidateThisHandle(key); - this.items[handle.index].value = value; - if (!BubbleUp(handle.index)) - BubbleDown(handle.index); + int indx = handle.index; + items[indx].value = value; + if (!BubbleUp(indx)) + BubbleDown(indx); } } @@ -124,9 +130,9 @@ namespace OpenSim.Framework { get { - if (this.sync_root == null) - Interlocked.CompareExchange(ref this.sync_root, new object(), null); - return this.sync_root; + if (sync_root == null) + Interlocked.CompareExchange(ref sync_root, new object(), null); + return sync_root; } } @@ -152,27 +158,27 @@ namespace OpenSim.Framework private void Set(HeapItem item, int index) { - this.items[index] = item; + items[index] = item; if (item.handle != null) item.handle.index = index; } private bool BubbleUp(int index) { - HeapItem item = this.items[index]; + HeapItem item = items[index]; int current, parent; for (current = index, parent = (current - 1) / 2; - (current > 0) && (this.comparison(this.items[parent].value, item.value)) > 0; + (current > 0) && (comparison(items[parent].value, item.value)) > 0; current = parent, parent = (current - 1) / 2) { - Set(this.items[parent], current); + Set(items[parent], current); } if (current != index) { Set(item, current); - ++this.version; + ++version; return true; } return false; @@ -180,24 +186,24 @@ namespace OpenSim.Framework private void BubbleDown(int index) { - HeapItem item = this.items[index]; + HeapItem item = items[index]; int current, child; for (current = index, child = (2 * current) + 1; - current < this.size / 2; + current < size / 2; current = child, child = (2 * current) + 1) { - if ((child < this.size - 1) && this.comparison(this.items[child].value, this.items[child + 1].value) > 0) + if ((child < size - 1) && comparison(items[child].value, items[child + 1].value) > 0) ++child; - if (this.comparison(this.items[child].value, item.value) >= 0) + if (comparison(items[child].value, item.value) >= 0) break; - Set(this.items[child], current); + Set(items[child], current); } if (current != index) { Set(item, current); - ++this.version; + ++version; } } @@ -206,7 +212,7 @@ namespace OpenSim.Framework Handle handle = ValidateHandle(key); if (handle.index > -1) { - value = this.items[handle.index].value; + value = items[handle.index].value; return true; } value = default(T); @@ -228,12 +234,12 @@ namespace OpenSim.Framework public void Add(T value, IHandle ihandle) { - if (this.size == this.items.Length) + if (size == items.Length) { - int capacity = (int)((this.items.Length * 200L) / 100L); - if (capacity < (this.items.Length + DEFAULT_CAPACITY)) - capacity = this.items.Length + DEFAULT_CAPACITY; - Array.Resize(ref this.items, capacity); + int capacity = (int)((items.Length * 200L) / 100L); + if (capacity < (items.Length + DEFAULT_CAPACITY)) + capacity = items.Length + DEFAULT_CAPACITY; + Array.Resize(ref items, capacity); } Handle handle = null; @@ -245,8 +251,8 @@ namespace OpenSim.Framework HeapItem item = new MinHeap.HeapItem(value, handle); - Set(item, this.size); - BubbleUp(this.size++); + Set(item, size); + BubbleUp(size++); } public void Add(T value) @@ -256,50 +262,54 @@ namespace OpenSim.Framework public T Min() { - if (this.size == 0) + if (size == 0) throw new InvalidOperationException("Heap is empty"); - return this.items[0].value; + return items[0].value; } public void Clear() { - for (int index = 0; index < this.size; ++index) - this.items[index].Clear(); - this.size = 0; - ++this.version; + for (int index = 0; index < size; ++index) + items[index].Clear(); + size = 0; + if(items.Length > capacity) + items = new HeapItem[capacity]; + ++version; } public void TrimExcess() { - int length = (int)(this.items.Length * 0.9); - if (this.size < length) - Array.Resize(ref this.items, Math.Min(this.size, DEFAULT_CAPACITY)); + int length = (int)(items.Length * 0.9); + if (size < length) + Array.Resize(ref items, Math.Min(size, capacity)); } private void RemoveAt(int index) { - if (this.size == 0) + if (size == 0) throw new InvalidOperationException("Heap is empty"); - if (index >= this.size) + if (index >= size) throw new ArgumentOutOfRangeException("index"); - this.items[index].Clear(); - if (--this.size > 0 && index != this.size) + items[index].Clear(); + if (--size > 0 && index != size) { - Set(this.items[this.size], index); - this.items[this.size].ClearRef(); + Set(items[size], index); + items[size].ClearRef(); if (!BubbleUp(index)) BubbleDown(index); } + if(size == 0 && items.Length > 4 * capacity) + items = new HeapItem[capacity]; } public T RemoveMin() { - if (this.size == 0) + if (size == 0) throw new InvalidOperationException("Heap is empty"); - HeapItem item = this.items[0]; + HeapItem item = items[0]; RemoveAt(0); return item.value; } @@ -307,7 +317,7 @@ namespace OpenSim.Framework public T Remove(IHandle ihandle) { Handle handle = ValidateThisHandle(ihandle); - HeapItem item = this.items[handle.index]; + HeapItem item = items[handle.index]; RemoveAt(handle.index); return item.value; } @@ -317,9 +327,9 @@ namespace OpenSim.Framework EqualityComparer comparer = EqualityComparer.Default; int index; - for (index = 0; index < this.size; ++index) + for (index = 0; index < size; ++index) { - if (comparer.Equals(this.items[index].value, value)) + if (comparer.Equals(items[index].value, value)) return index; } return -1; @@ -356,8 +366,8 @@ namespace OpenSim.Framework if ((length - index) < this.size) throw new ArgumentException("Not enough space available in array starting at index"); - for (int i = 0; i < this.size; ++i) - array[index + i] = this.items[i].value; + for (int i = 0; i < size; ++i) + array[index + i] = items[i].value; } public void CopyTo(Array array, int index) @@ -372,13 +382,13 @@ namespace OpenSim.Framework int length = array.Length; if ((index < 0) || (index > length)) throw new ArgumentOutOfRangeException("index"); - if ((length - index) < this.size) + if ((length - index) < size) throw new ArgumentException("Not enough space available in array starting at index"); try { - for (int i = 0; i < this.size; ++i) - array.SetValue(this.items[i].value, index + i); + for (int i = 0; i < size; ++i) + array.SetValue(items[i].value, index + i); } catch (ArrayTypeMismatchException) { @@ -388,13 +398,13 @@ namespace OpenSim.Framework public IEnumerator GetEnumerator() { - int version = this.version; + int cversion = version; - for (int index = 0; index < this.size; ++index) + for (int index = 0; index < size; ++index) { - if (version != this.version) + if (cversion != version) throw new InvalidOperationException("Heap was modified while enumerating"); - yield return this.items[index].value; + yield return items[index].value; } } -- cgit v1.1