src/mem/gems_common/PrioHeap.hh

   1 /*
   2  * Copyright (c) 1999-2005 Mark D. Hill and David A. Wood
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #ifndef PRIOHEAP_H
  30 #define PRIOHEAP_H
  31
  32 #include "mem/gems_common/Vector.hh"
  33
  34 typedef unsigned int HeapIndex;
  35
  36 template <class TYPE>
  37 class PrioHeap {
  38 public:
  39   // Constructors
  40   PrioHeap() { init(); }
  41
  42   // Destructor
  43   //~PrioHeap();
  44
  45   // Public Methods
  46   void init() { m_current_size = 0; }
  47   int size() const { return m_current_size; }
  48   void insert(const TYPE& key);
  49   const TYPE& peekMin() const;
  50   const TYPE& peekElement(int index) const;
  51   TYPE extractMin();
  52   void print(ostream& out) const;
  53 private:
  54   // Private Methods
  55   bool verifyHeap() const;
  56   bool verifyHeap(HeapIndex index) const;
  57   void heapify();
  58
  59   // Private copy constructor and assignment operator
  60   PrioHeap(const PrioHeap& obj);
  61   PrioHeap<TYPE>& operator=(const PrioHeap& obj);
  62
  63   // Data Members (m_ prefix)
  64   Vector<TYPE> m_heap;
  65   HeapIndex m_current_size;
  66 };
  67
  68 // Output operator declaration
  69 template <class TYPE>
  70 ostream& operator<<(ostream& out, const PrioHeap<TYPE>& obj);
  71
  72 // ******************* Helper Functions *******************
  73 inline
  74 HeapIndex get_parent(HeapIndex i)
  75 {
  76   //  return (i/2);
  77   return (i>>1);
  78 }
  79
  80 inline
  81 HeapIndex get_right(HeapIndex i)
  82 {
  83   //  return (2*i) + 1;
  84   return (i<<1) | 1;
  85 }
  86
  87 inline
  88 HeapIndex get_left(HeapIndex i)
  89 {
  90   //  return (2*i);
  91   return (i<<1);
  92 }
  93
  94 template <class TYPE>
  95 void prio_heap_swap(TYPE& n1, TYPE& n2)
  96 {
  97   TYPE temp = n1;
  98   n1 = n2;
  99   n2 = temp;
 100 }
 101
 102 // ******************* Definitions *******************
 103
 104 template <class TYPE>
 105 void PrioHeap<TYPE>::insert(const TYPE& key)
 106 {
 107   int i;
 108   // grow the vector size
 109   m_current_size++;
 110   m_heap.setSize(m_current_size+1);
 111
 112   if(m_current_size == 1){      // HACK: need to initialize index 0 to avoid purify UMCs
 113     m_heap[0] = key;
 114   }
 115
 116   i = m_current_size;
 117   while ((i > 1) && (node_less_then_eq(key, m_heap[get_parent(i)]))) {
 118     m_heap[i] = m_heap[get_parent(i)];
 119     i = get_parent(i);
 120   }
 121   m_heap[i] = key;
 122   //  assert(verifyHeap());
 123 }
 124
 125 template <class TYPE>
 126 const TYPE& PrioHeap<TYPE>::peekMin() const
 127 {
 128   assert(size() > 0);
 129   return m_heap[1]; // 1, not 0, is the first element
 130 }
 131
 132 template <class TYPE>
 133 const TYPE& PrioHeap<TYPE>::peekElement(int index) const
 134 {
 135   assert(size() > 0);
 136   return m_heap[index];
 137 }
 138
 139 template <class TYPE>
 140 TYPE PrioHeap<TYPE>::extractMin()
 141 {
 142   //  TYPE temp;
 143   assert(size() > 0);
 144   TYPE temp = m_heap[1]; // 1, not 0, is the first element
 145   m_heap[1] = m_heap[m_current_size];
 146   m_current_size--;
 147   heapify();
 148   return temp;
 149 }
 150
 151 template <class TYPE>
 152 bool PrioHeap<TYPE>::verifyHeap() const
 153 {
 154   return verifyHeap(1);
 155 }
 156
 157 template <class TYPE>
 158 bool PrioHeap<TYPE>::verifyHeap(HeapIndex index) const
 159 {
 160   // Recursively verify that each node is <= its parent
 161   if(index > m_current_size) {
 162     return true;
 163   } else if (index == 1) {
 164     return
 165       verifyHeap(get_right(index)) &&
 166       verifyHeap(get_left(index));
 167   } else if (node_less_then_eq(m_heap[get_parent(index)], m_heap[index])) {
 168     return
 169       verifyHeap(get_right(index)) &&
 170       verifyHeap(get_left(index));
 171   } else {
 172     // Heap property violation
 173     return false;
 174   }
 175 }
 176
 177 template <class TYPE>
 178 void PrioHeap<TYPE>::heapify()
 179 {
 180   HeapIndex current_node = 1;
 181   HeapIndex left, right, smallest;
 182   //  HeapIndex size = m_current_size;
 183
 184   while(true) {
 185     left = get_left(current_node);
 186     right = get_right(current_node);
 187
 188     // Find the smallest of the current node and children
 189     if (left <= m_current_size && node_less_then_eq(m_heap[left], m_heap[current_node])) {
 190       smallest = left;
 191     } else {
 192       smallest = current_node;
 193     }
 194
 195     if (right <= m_current_size && node_less_then_eq(m_heap[right], m_heap[smallest])) {
 196       smallest = right;
 197     }
 198
 199     // Check to see if we are done
 200     if (smallest == current_node) {
 201       // We are done
 202       break;
 203     } else {
 204       // Not done, heapify on the smallest child
 205       prio_heap_swap(m_heap[current_node], m_heap[smallest]);
 206       current_node = smallest;
 207     }
 208   }
 209   //  assert(verifyHeap());
 210 }
 211
 212 template <class TYPE>
 213 void PrioHeap<TYPE>::print(ostream& out) const
 214 {
 215   Vector<TYPE> copyHeap(m_heap);
 216
 217   // sort copyHeap (inefficient, but will not be done often)
 218
 219   for(HeapIndex i=0;i<m_current_size; i++){
 220     for(HeapIndex j=0; j< m_current_size; j++){
 221       if(copyHeap[i].m_time < copyHeap[j].m_time){
 222         prio_heap_swap(copyHeap[i], copyHeap[j]);
 223       }
 224     }
 225   }
 226
 227   out << "[PrioHeap: ";
 228
 229   for(HeapIndex i=1; i<= m_current_size; i++){
 230     out << copyHeap[i];
 231
 232     if(i != m_current_size-1){
 233       out << ",";
 234     }
 235     out << " ";
 236   }
 237   out << "]";
 238 }
 239
 240 // Output operator definition
 241 template <class TYPE>
 242 ostream& operator<<(ostream& out, const PrioHeap<TYPE>& obj)
 243 {
 244   obj.print(out);
 245   out << flush;
 246   return out;
 247 }
 248
 249 #endif //PRIOHEAP_H