From 2f30950143cc70bc42a3c8a4111d7cf8198ec881 Mon Sep 17 00:00:00 2001 From: Nathan Binkert Date: Mon, 11 May 2009 10:38:43 -0700 Subject: ruby: Import ruby and slicc from GEMS We eventually plan to replace the m5 cache hierarchy with the GEMS hierarchy, but for now we will make both live alongside eachother. --- src/mem/gems_common/PrioHeap.hh | 249 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 249 insertions(+) create mode 100644 src/mem/gems_common/PrioHeap.hh (limited to 'src/mem/gems_common/PrioHeap.hh') diff --git a/src/mem/gems_common/PrioHeap.hh b/src/mem/gems_common/PrioHeap.hh new file mode 100644 index 000000000..d549f0944 --- /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 "Vector.hh" + +typedef unsigned int HeapIndex; + +template +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& operator=(const PrioHeap& obj); + + // Data Members (m_ prefix) + Vector m_heap; + HeapIndex m_current_size; +}; + +// Output operator declaration +template +ostream& operator<<(ostream& out, const PrioHeap& 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 +void prio_heap_swap(TYPE& n1, TYPE& n2) +{ + TYPE temp = n1; + n1 = n2; + n2 = temp; +} + +// ******************* Definitions ******************* + +template +void PrioHeap::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 +const TYPE& PrioHeap::peekMin() const +{ + assert(size() > 0); + return m_heap[1]; // 1, not 0, is the first element +} + +template +const TYPE& PrioHeap::peekElement(int index) const +{ + assert(size() > 0); + return m_heap[index]; +} + +template +TYPE PrioHeap::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 +bool PrioHeap::verifyHeap() const +{ + return verifyHeap(1); +} + +template +bool PrioHeap::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 +void PrioHeap::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 +void PrioHeap::print(ostream& out) const +{ + Vector copyHeap(m_heap); + + // sort copyHeap (inefficient, but will not be done often) + + for(HeapIndex i=0;i +ostream& operator<<(ostream& out, const PrioHeap& obj) +{ + obj.print(out); + out << flush; + return out; +} + +#endif //PRIOHEAP_H -- cgit v1.2.3