src/ck-ldb/CommLBHeap.C

   1 /**
   2  * \addtogroup CkLdb
   3 */
   4 /*@{*/
   5
   6 #include "charm++.h"
   7 #include "CommLBHeap.h"
   8
   9 ObjectHeap::ObjectHeap(int sz) {
  10   size = sz;
  11   h = new hRecord[sz];
  12   count = 0;
  13 }
  14
  15 int ObjectHeap::numElements() {
  16   return count;
  17 }
  18
  19 int ObjectHeap::insert(ObjectRecord *x) {
  20   h[count].info = x;
  21   h[count].deleted  = 0;
  22   int current = count;
  23   count++;
  24
  25   if (count >= size) {
  26     CkPrintf("Heap overflow. \n");
  27     return -1;}
  28
  29   int parent = (current - 1)/2;
  30   while (current != 0)
  31     {
  32       if (h[current].info->val > h[parent].info->val)
  33         {
  34           swap(current, parent);
  35           current = parent;
  36           parent = (current-1)/2;
  37         }
  38       else
  39         break;
  40     }
  41   return 0;
  42 }
  43
  44 ObjectRecord *ObjectHeap::deleteMax() {
  45   if (count == 0) return 0;
  46   ObjectRecord *tmp = h[0].info;
  47   int best;
  48
  49   h[0] = h[count-1];
  50   count--;
  51
  52   int current = 0;
  53   int c1 = 1;
  54   int c2 = 2;
  55   while (c1 < count)
  56     {
  57       if (c2 >= count)
  58         best = c1;
  59       else
  60         {
  61           if (h[c1].info->val > h[c2].info->val)
  62             best = c1;
  63           else
  64             best = c2;
  65         }
  66       if (h[best].info->val > h[current].info->val)
  67         {
  68           swap(best, current);
  69           current = best;
  70           c1 = 2*current + 1;
  71           c2 = c1 + 1;
  72         }
  73       else
  74         break;
  75     }
  76   return tmp;
  77 }
  78
  79 ObjectRecord *ObjectHeap::iterator(hIterator *iter) {
  80   iter->next = 1;
  81   if (count == 0)
  82     return 0;
  83   return h[0].info;
  84 }
  85
  86 ObjectRecord *ObjectHeap::next(hIterator *iter) {
  87   if (iter->next >= count)
  88     return 0;
  89   iter->next += 1;
  90   return h[iter->next - 1].info;
  91 }
  92
  93 /*@}*/