pending_heap.h

/**********************************************************************
 * Additional Contributions and Acknowledgements
 *   Kalyan Perumalla - Ga Tech
 *
 *   This implementation is an adaption of the implementation done
 *   by Kalyan for Ga Tech Time Warp
 **********************************************************************/

#ifndef _PENDING_HEAP_
#define _PENDING_HEAP_

#include "pending_queue.h"

#include "event.h"
#include "typedefs.h"
#include "util.h"

#include <float.h>

#define HEAP_INCREMENT 128

#define LEFT(i)   (2*i+1)
#define RIGHT(i)  (2*i+2)
#define PARENT(i) (((i-1)/2))

#define SWAP(x,y,t) { \
  t = elems[x]; \
  elems[x] = elems[y]; \
  elems[y] = t; \
  elems[x]->index = x; \
  elems[y]->index = y; \
}

class PendingHeap : public PendingQueue {
  private:
    CustomEventComparator comparator;
    size_t  nelems;
    size_t  curr_max;
    Event** elems;

    void sift_down(int i) {
      if (nelems <= 1) return;

      size_t parent, left, right, temp_idx = i;
      Event* temp;

      /* Stops when neither child is "strictly less than" parent */
      do {
        parent = temp_idx;
        left = LEFT(parent);
        right = RIGHT(parent);
        if (left  < nelems && comparator(elems[left], elems[temp_idx])) temp_idx = left;
        if (right < nelems && comparator(elems[right], elems[temp_idx])) temp_idx = right;
        if (parent != temp_idx) SWAP(parent, temp_idx, temp);
      } while (parent != temp_idx);
    }

    void percolate_up( int i ) {
      if (nelems <= 1) return;

      int child, parent, temp_idx = i;
      Event* temp;

      /* Stops when parent is "less than or equal to" child */
      do {
        child = temp_idx;
        parent = PARENT(child);
        if (parent >= 0 && comparator(elems[temp_idx], elems[parent])) temp_idx = parent;
        if (child != temp_idx) SWAP(child, temp_idx, temp);
      } while (child != temp_idx);
    }

  public:
    PendingHeap() {
      int init_size = HEAP_INCREMENT;
      nelems = 0;
      curr_max = (2*init_size);
      int err = posix_memalign((void**)&elems, 64, sizeof(Event*)*curr_max);
      memset(elems, 0, sizeof(Event*) * curr_max);
    }

    PendingHeap(int init_size) {
      nelems = 0;
      curr_max = (2*init_size);
      int err = posix_memalign((void**)&elems, 64, sizeof(Event*)*curr_max);
      memset(elems, 0, sizeof(Event**) * curr_max);
    }

    ~PendingHeap() {
      for (int i = 0; i < nelems; i++) {
        tw_event_free(elems[i],false);
      }
      delete[] elems;
    }

    virtual void pup(PUP::er& p) {
      p | nelems;
      p | curr_max;
      if (p.isUnpacking()) {
        int err = posix_memalign((void**)&elems, 64, sizeof(Event*)*curr_max);
        memset(elems, 0, sizeof(Event**) * curr_max);
      }
      for (int i = 0; i < nelems; i++) {
        if (p.isUnpacking()) {
          elems[i] = event_alloc();
        }
        elems[i]->pup(p);
      }
    }

    Event** get_temp_event_buffer() {
      return elems;
    }

    void delete_temp_event_buffer() {
    }

    Time min() const {
      return (nelems <= 0) ? TIME_MAX : elems[0]->ts;
    }

    size_t size() const {
      return nelems;
    }

    void push(Event* e) {
      if (nelems >= curr_max) {
        size_t old_max = curr_max;
        curr_max += HEAP_INCREMENT;
        Event** old = elems;
        int err = posix_memalign((void**)&elems, 64, sizeof(Event**)*curr_max);
        memcpy(elems, old, sizeof(Event**) * old_max);
        memset(&elems[old_max], 0, sizeof(Event**) * HEAP_INCREMENT);
        free(old);
      }

      e->state.owner = TW_chare_q;
      e->index = nelems;

      elems[nelems++] = e;
      percolate_up(nelems-1);
    }

    Event* pop() {
      if (nelems <= 0) {
        return NULL;
      } else {
        Event* e = elems[0];
        e->state.owner = 0;

        nelems--;
        elems[0] = elems[nelems];
        elems[0]->index = 0;
        elems[nelems] = NULL;
        sift_down(0);

        return e;
      }
    }

    void erase(Event* victim) {
      TW_ASSERT(nelems > 0, "Can't erase from an empty heap\n");
      TW_ASSERT(victim->index >= 0 && victim->index < nelems,
          "Invalid heap index in erase\n");
      TW_ASSERT(elems[victim->index]->index == victim->index,
          "Mismatch in heap indices during erase\n");

      int i = victim->index;
      nelems--;

      if (i == nelems) {
        elems[nelems] = NULL;
        return;
      } else if (nelems > 0) {
        elems[i] = elems[nelems];
        elems[i]->index = i;
        elems[nelems] = NULL;

        if (elems[i]->ts <= victim->ts) {
          percolate_up(i);
        } else {
          sift_down(i);
        }
      }
    }
};
#endif