diff options
Diffstat (limited to 'src/mem/gems_common/PrioHeap.hh')
-rw-r--r-- | src/mem/gems_common/PrioHeap.hh | 249 |
1 files changed, 249 insertions, 0 deletions
diff --git a/src/mem/gems_common/PrioHeap.hh b/src/mem/gems_common/PrioHeap.hh new file mode 100644 index 000000000..acdcc0eba --- /dev/null +++ b/src/mem/gems_common/PrioHeap.hh @@ -0,0 +1,249 @@ +/* + * Copyright (c) 1999-2005 Mark D. Hill and David A. Wood + * All rights reserved. + * + * 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 copyright holders 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 COPYRIGHT HOLDERS AND CONTRIBUTORS + * "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 COPYRIGHT + * OWNER OR 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. + */ + +#ifndef PRIOHEAP_H +#define PRIOHEAP_H + +#include "mem/gems_common/Vector.hh" + +typedef unsigned int HeapIndex; + +template <class TYPE> +class PrioHeap { +public: + // Constructors + PrioHeap() { init(); } + + // Destructor + //~PrioHeap(); + + // Public Methods + void init() { m_current_size = 0; } + int size() const { return m_current_size; } + void insert(const TYPE& key); + const TYPE& peekMin() const; + const TYPE& peekElement(int index) const; + TYPE extractMin(); + void print(ostream& out) const; +private: + // Private Methods + bool verifyHeap() const; + bool verifyHeap(HeapIndex index) const; + void heapify(); + + // Private copy constructor and assignment operator + PrioHeap(const PrioHeap& obj); + PrioHeap<TYPE>& operator=(const PrioHeap& obj); + + // Data Members (m_ prefix) + Vector<TYPE> m_heap; + HeapIndex m_current_size; +}; + +// Output operator declaration +template <class TYPE> +ostream& operator<<(ostream& out, const PrioHeap<TYPE>& obj); + +// ******************* Helper Functions ******************* +inline +HeapIndex get_parent(HeapIndex i) +{ + // return (i/2); + return (i>>1); +} + +inline +HeapIndex get_right(HeapIndex i) +{ + // return (2*i) + 1; + return (i<<1) | 1; +} + +inline +HeapIndex get_left(HeapIndex i) +{ + // return (2*i); + return (i<<1); +} + +template <class TYPE> +void prio_heap_swap(TYPE& n1, TYPE& n2) +{ + TYPE temp = n1; + n1 = n2; + n2 = temp; +} + +// ******************* Definitions ******************* + +template <class TYPE> +void PrioHeap<TYPE>::insert(const TYPE& key) +{ + int i; + // grow the vector size + m_current_size++; + m_heap.setSize(m_current_size+1); + + if(m_current_size == 1){ // HACK: need to initialize index 0 to avoid purify UMCs + m_heap[0] = key; + } + + i = m_current_size; + while ((i > 1) && (node_less_then_eq(key, m_heap[get_parent(i)]))) { + m_heap[i] = m_heap[get_parent(i)]; + i = get_parent(i); + } + m_heap[i] = key; + // assert(verifyHeap()); +} + +template <class TYPE> +const TYPE& PrioHeap<TYPE>::peekMin() const +{ + assert(size() > 0); + return m_heap[1]; // 1, not 0, is the first element +} + +template <class TYPE> +const TYPE& PrioHeap<TYPE>::peekElement(int index) const +{ + assert(size() > 0); + return m_heap[index]; +} + +template <class TYPE> +TYPE PrioHeap<TYPE>::extractMin() +{ + // TYPE temp; + assert(size() > 0); + TYPE temp = m_heap[1]; // 1, not 0, is the first element + m_heap[1] = m_heap[m_current_size]; + m_current_size--; + heapify(); + return temp; +} + +template <class TYPE> +bool PrioHeap<TYPE>::verifyHeap() const +{ + return verifyHeap(1); +} + +template <class TYPE> +bool PrioHeap<TYPE>::verifyHeap(HeapIndex index) const +{ + // Recursively verify that each node is <= its parent + if(index > m_current_size) { + return true; + } else if (index == 1) { + return + verifyHeap(get_right(index)) && + verifyHeap(get_left(index)); + } else if (node_less_then_eq(m_heap[get_parent(index)], m_heap[index])) { + return + verifyHeap(get_right(index)) && + verifyHeap(get_left(index)); + } else { + // Heap property violation + return false; + } +} + +template <class TYPE> +void PrioHeap<TYPE>::heapify() +{ + HeapIndex current_node = 1; + HeapIndex left, right, smallest; + // HeapIndex size = m_current_size; + + while(true) { + left = get_left(current_node); + right = get_right(current_node); + + // Find the smallest of the current node and children + if (left <= m_current_size && node_less_then_eq(m_heap[left], m_heap[current_node])) { + smallest = left; + } else { + smallest = current_node; + } + + if (right <= m_current_size && node_less_then_eq(m_heap[right], m_heap[smallest])) { + smallest = right; + } + + // Check to see if we are done + if (smallest == current_node) { + // We are done + break; + } else { + // Not done, heapify on the smallest child + prio_heap_swap(m_heap[current_node], m_heap[smallest]); + current_node = smallest; + } + } + // assert(verifyHeap()); +} + +template <class TYPE> +void PrioHeap<TYPE>::print(ostream& out) const +{ + Vector<TYPE> copyHeap(m_heap); + + // sort copyHeap (inefficient, but will not be done often) + + for(HeapIndex i=0;i<m_current_size; i++){ + for(HeapIndex j=0; j< m_current_size; j++){ + if(copyHeap[i].m_time < copyHeap[j].m_time){ + prio_heap_swap(copyHeap[i], copyHeap[j]); + } + } + } + + out << "[PrioHeap: "; + + for(HeapIndex i=1; i<= m_current_size; i++){ + out << copyHeap[i]; + + if(i != m_current_size-1){ + out << ","; + } + out << " "; + } + out << "]"; +} + +// Output operator definition +template <class TYPE> +ostream& operator<<(ostream& out, const PrioHeap<TYPE>& obj) +{ + obj.print(out); + out << flush; + return out; +} + +#endif //PRIOHEAP_H |