gridkeeper.cc

Go to the documentation of this file.

/*
 * An optimizer for some wireless simulations
 *
 * Helps most when some nodes are mostly stationary.
 * We hope you can share your experience with the gridkeeper with us.
 *
 * Ported from Sun's mobility code
 */

#include "gridkeeper.h"

static double d2(double x1, double x2, double y1, double y2)
{
  return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

GridHandler::GridHandler()
{
}

void GridHandler::handle(Event *e)
{
  MoveEvent *me = (MoveEvent *)e;
  MobileNode **pptr;
  MobileNode * token_ = me->token_;

  if ((pptr = me->leave_)) {
    while (*pptr) {
      if ((*pptr)->address() == token_->address()) break;
      pptr = &((*pptr)->next());
    }
    if (!(*pptr)) abort();
    else {
      *pptr = token_->next();
      token_->next() = 0;
    }
    
  }
  if ((pptr = me->enter_)) {
    if (token_->next()) abort();  // can't be in more than one grid
    token_->next() = *pptr;
    *pptr = token_;
  }
  delete me;

  // dump info in the gridkeeper for debug only
  // dump();

}

GridKeeper* GridKeeper::instance_; 

static class GridKeeperClass : public TclClass {
public:
  GridKeeperClass() : TclClass("GridKeeper") {}
  TclObject* create(int, const char*const*) {
      return (new GridKeeper);
  }
} class_grid_keeper;

GridKeeper::GridKeeper() : size_(0),grid_(NULL), dim_x_(0), dim_y_(0)
{
  gh_ = new GridHandler();
}

GridKeeper::~GridKeeper()
{
  int i;
  for (i = 0; i <= dim_x_; i++) {
    delete [] grid_[i];
  }
  delete [] grid_;
}

int GridKeeper::command(int argc, const char*const* argv)
{
  int i, grid_x, grid_y;
  Tcl& tcl = Tcl::instance();
  MobileNode *mn;

  if (argc == 2) {
    if (strcmp(argv[1], "dump") == 0) {
      dump();
      return (TCL_OK);
    }
  }

  if (argc == 3) {
    if (strcmp(argv[1], "addnode") == 0) {
        mn = (MobileNode *)TclObject::lookup(argv[2]);
        grid_x = aligngrid((int)mn->X(), dim_x_);
        grid_y = aligngrid((int)mn->Y(), dim_y_);
        mn->next() = grid_[grid_x][grid_y];
        grid_[grid_x][grid_y] = mn;
        size_++;
        return (TCL_OK);
    }
  }
  if (argc == 4 && strcmp(argv[1], "dimension") == 0) {
    if (instance_ == 0) instance_ = this;

    dim_x_ = strtol(argv[2], (char**)0, 0);
    dim_y_ = strtol(argv[3], (char**)0, 0);

    if (dim_x_ <= 0 || dim_y_ <= 0) {
      tcl.result("illegal grid dimension");
      return (TCL_ERROR);
    }

    grid_ = new MobileNode **[dim_x_];
    for (i = 0; i < dim_x_; i++) {
      grid_[i] = new MobileNode *[dim_y_];
      bzero((void *)grid_[i], sizeof(MobileNode *)*dim_y_);
    }
    return (TCL_OK);
  }
  return (TclObject::command(argc, argv));
}

void GridKeeper::new_moves(MobileNode *mn)
{
  double x = mn->X(), y = mn->Y(); 
  double ss = mn->speed();
  double vx = (mn->dX())*ss, vy = (mn->dY())*ss;

  double endx, endy, pother, tm;
  int i, j, endi, gother, grid_x, grid_y;
  MoveEvent *me;

  Scheduler& s = Scheduler::instance();

  endx = mn->destX();
  endy = mn->destY();

  if (vx > 0) {
    endi = min(dim_x_-1, (int)endx);
    for (i = (int)x+1; i <= endi; i++) {
      tm = (i-x)/vx;
      pother = vy*tm + y;
      j = (int)pother;
      me = new MoveEvent;
      if (j == pother && j != 0 && j != dim_y_) {
        if (vy > 0) gother = j - 1;
        else if (vy < 0) gother = j + 1;
        else gother = j;
      }
      else {
        gother = j;
      }
      me->leave_ = &(grid_[aligngrid(i-1, dim_x_)][aligngrid(gother, dim_y_)]);

      me->grid_x_ = grid_x = aligngrid(i, dim_x_);
      me->grid_y_ = grid_y = aligngrid(j, dim_y_);
      me->enter_ = &(grid_[grid_x][grid_y]);
      me->token_ = mn;
      s.schedule(gh_, me, tm);
    }
  }
  else if (vx < 0) {
    endi = (int)endx;
    for (i = (int)x; i > endi; i--) {
      if (i == dim_x_) continue;
      tm = (i-x)/vx;
      pother = vy*tm + y;
      j = (int)pother;
      me = new MoveEvent;
      if (j == pother && j != 0 && j != dim_y_) {
        if (vy > 0) gother = j - 1;
        else if (vy < 0) gother = j + 1;
        else gother = j;
      }
      else {
        gother = j;
      }
      me->leave_ = &grid_[aligngrid(i, dim_x_)][aligngrid(gother, dim_y_)];

      me->grid_x_ = grid_x = aligngrid(i-1, dim_x_);
      me->grid_y_ = grid_y = aligngrid(j, dim_y_);
      me->enter_ = &grid_[grid_x][grid_y];
      me->token_ = mn;
      s.schedule(gh_, me, tm);
    }
  }
  if (vy > 0) {
    endi = min(dim_y_-1, (int)endy);
    for (j = (int)y+1; j <= endi; j++) {
      tm = (j-y)/vy;
      pother = vx*tm + x;
      i = (int)pother;
      me = new MoveEvent;
      if (i == pother && i != 0 && i != dim_x_ && vx != 0) continue;
      me->leave_ = &grid_[aligngrid(i, dim_x_)][aligngrid(j-1, dim_y_)];

      me->grid_x_ = grid_x = aligngrid(i, dim_x_);
      me->grid_y_ = grid_y = aligngrid(j, dim_y_);
      me->enter_ = &grid_[grid_x][grid_y];
      me->token_ = mn;

      s.schedule(gh_, me, tm);
    }
  }
  else if (vy < 0) {
    endi = (int)endy;
    for (j = (int)y; j > endi; j--) {
      if (j == dim_y_) continue;
      tm = (j-y)/vy;
      pother = vx*tm + x;
      i = (int)pother;
      me = new MoveEvent;
      if (i == pother && i != 0 && i != dim_x_ && vx != 0) continue;
      me->leave_ = &grid_[aligngrid(i, dim_x_)][aligngrid(j, dim_y_)];

      me->grid_x_ = grid_x = aligngrid(i, dim_x_);
      me->grid_y_ = grid_y = aligngrid(j-1, dim_y_);
      me->enter_ = &grid_[grid_x][grid_y];
      me->token_ = mn;
      s.schedule(gh_, me, tm);
    }
  }

}

int GridKeeper::get_neighbors(MobileNode* mn, MobileNode **output)
{
  int grid_x, grid_y, index = 0, i, j, ulx, uly, lly, adj;
  MobileNode *pgd;
  double mnx, mny, mnr, sqmnr;
  
  mn->update_position();
  mnx = mn->X();
  mny = mn->Y();

  grid_x = aligngrid((int)mn->X(), dim_x_);
  grid_y = aligngrid((int)mn->Y(), dim_y_);

  sqmnr = (mnr = mn->radius())*mnr;

  adj = (int)ceil(mnr);

  ulx = min(dim_x_-1, grid_x + adj);
  uly = min(dim_y_-1, grid_y + adj);
  lly = max(0, grid_y - adj);

  for (i = max(0, grid_x - adj); i <= ulx; i++) {
    for (j = lly; j <= uly; j++) {
      for (pgd = grid_[i][j]; pgd != 0; pgd = pgd->next()) {
        if (mn->address() == pgd->address()) 
                continue;
        pgd->update_position();
        if (d2(pgd->X(), mnx, pgd->Y(), mny) < sqmnr)
         output[index++] = pgd;
      }
    }
  }

  return index;
}

void GridKeeper::dump()
{
    int i,j;
    MobileNode *pgd;

    for (i = 0; i< dim_x_; i++) {
      for (j = 0; j < dim_y_; j++) {
        if (grid_[i][j] == 0) continue;
        printf("grid[%d][%d]: ",i,j);
        for (pgd = grid_[i][j]; pgd != 0; pgd = pgd->next()) {
          printf("%d ",pgd->address());
        }
        printf("\n");
      }
    }
    printf("-------------------------------\n");

}

---