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