routecache-squish.cc

在Linux下做的QuadTree的程序

/* routecache.cc

   handles routes

*/

extern "C" {
#include <stdio.h>
#include <stdarg.h>
};

#undef DEBUG

#include "path.h"
#include "routecache.h"

/* invariants

   - no path contains an id more than once
   - all paths start with the id of our node (MAC_id or net_id)
*/

#define fout stdout

static const int verbose = 1;

/*===============================================================
  function selectors
----------------------------------------------------------------*/
bool cache_squish_all_on_add = true; // use the full cache optimization strat
bool cache_ignore_hints = false;     // ignore all hints?
bool cache_trust_senders = false;
// if the src of a route lists the route to them as longer than the route
// we have in our cache, should we update our cache to the longer entry?

/*===============================================================
  helper routines
----------------------------------------------------------------*/
static bool
SamePath(const Path& path1, const Path& path2)
{
  Path& p1 = (Path&) path1;
  Path& p2 = (Path&) path2;
  if (p1.length() != p2.length()) return false;
  for (int c = 0 ; c < p1.length() ; c ++)
    if (!(p1[c] == p2[c])) return false;
  return true;
}

/*===============================================================
  OTcl definition
----------------------------------------------------------------*/
static class RouteCacheClass : public TclClass {
public:
        RouteCacheClass() : TclClass("RouteCache") {}
        TclObject* create(int, const char*const*) {
                return (new RouteCache);
        }
} class_RouteCache;

/*===============================================================
  member functions
----------------------------------------------------------------*/
int
RouteCache::pickVictim(int exclude)
// returns the index of a suitable victim in the cache
// never return exclude as the victim, but rather spare their life
{
  for(int c = 0; c < size ; c++)
    if (cache[c].length() == 0) return c;
  
  int victim = ptr;
  while (victim == exclude)
    {
      ptr = (ptr+1 == size) ? 0 : ptr+1;
      victim = ptr;
    }
  ptr = (ptr+1 == size) ? 0 : ptr+1;
  return victim;
}

void
RouteCache::squish(int index, Path& r, int i, Path& nr, int j)
/* see paper notes:
   use NR[0->j] in place of R[0->i] but preserve any
   routes in R[0->i] not found elsewhere in the cache
   cache[index] should == r or == size if
   r isn't in the cache.  If index == size we don't verify
   r[0->i] before blasting it
   */
{
  int c;
  bool owner_on_nr, owner_on_r;	// is owner on part of route getting squished?
  owner_on_nr = owner_on_r = false;

  assert(i < MAX_SR_LEN && j < MAX_SR_LEN);

  for (c = 0; c < i; c++)
    if (r[c] == r.owner())
	{ 
	  owner_on_r = true;
	  break;
	}

  if (owner_on_r)
    for (c = 0; c < j; c++)
      if (nr[c] == r.owner())
	{ 
	  owner_on_nr = true;
	  break;
	}
    
  if (owner_on_r && ! owner_on_nr)
    { // we're not allowed to remove the owner of r from r
      if(verbose)
	{
	  trace("SRC %.5f %s not squishing %s owner %s",
		Scheduler::instance().clock(), net_id.dump(),
		r.dump(),r.owner().dump());
	  trace("SRC %.5f %s using %s owner %s",
		Scheduler::instance().clock(), net_id.dump(),
		nr.dump(), nr.owner().dump());
	}
      /* but yet, nr has a better route to nr[j], so save it */
      int v = pickVictim(index); // spare r from destruction
      if (verbose)
	{
	  trace("SRC %.5f %s evicting index(%d) %s",
		Scheduler::instance().clock(), net_id.dump(),
		v, cache[v].dump());
	  trace("SRC %.5f %s to hold shorter routes in %s",
		Scheduler::instance().clock(), net_id.dump(),
		nr.dump());
	}
      cache[v].reset();
      CopyIntoPath(cache[v],nr,0,nr.length()-1);
      return;
    }

  assert(r[i] == nr[j] && j < i);
  // first verify that there are no routes in  R[0->i] not found
  // elsewhere in the cache
  if (index != size)
    for(c = i-1; c > 0 ; c--)
      {
	if (searchRoute(r[c],index+1) == index)
	  { // we've got a unique route
	    int v = pickVictim(index); // spare r from destruction
	    cache[v].reset();
	    CopyIntoPath(cache[v],r,0,c);
#ifdef DEBUG
	    fprintf(fout,"      salvaged unique route: ");
	    cache[v].unparse(fout); fprintf(fout,"\n");
#endif
	    if(verbose)
	      trace("SRC %.5f %s salavged unique rt %s",
		    Scheduler::instance().clock(), net_id.dump(),
		    cache[v].dump());
	    break;
	  }
      }

#ifdef DEBUG
  fprintf(fout,"      squished "); r.unparse(fout);
#endif
  
  if(verbose)
    trace("SRC %.5f %s squishing %s owner %s",
	  Scheduler::instance().clock(), net_id.dump(),
	  r.dump(),r.owner().dump());

  // now compress
  // R[0->j] = NR[0->j]
  for(c = 0; c <= j ; c++)
    r[c] = nr[c];
  // R[j+1->~] = R[i+1->~]
  int to;
  for(to = j+1, c = i+1; c < r.length() ; c++,to++)
    r[to] = r[c];		// j < i so this is ok
  r.setLength(to);
  
#ifdef DEBUG
  fprintf(fout," to "); r.unparse(fout);
#endif

  int a;
  for (a = r.length() - 1; a >= 0; a--)
    {
      if (r[a] == r.owner()) break;
      if (r[a] == nr.owner()) 
	{
	  r.owner() = nr.owner();
	  break;
	}
    } 

#ifdef DEBUG
  fprintf(fout," owner "); r.owner().unparse(fout);fprintf(fout,"\n");
#endif
  if(verbose)
    trace("SRC %.5f %s to %s owner %s",
	  Scheduler::instance().clock(), net_id.dump(),
	  r.dump(), r.owner().dump());
}

int
RouteCache::searchRoute(const ID& dest, int start = 0)
// see if the cache contains a route to dest beginning the search
// at index start
// rtns index of path if one is found, size otherwise
{
  int index = (start == size ? 0 : start);
  do {
    if (cache[index].member(dest)) return index;
    index = (index+1 == size ? 0 : index+1);
  } while (index != start);
  return size;
}


RouteCache::RouteCache() : MAC_id(invalid_addr), net_id(invalid_addr)
{
  this->size = 64;
  assert(size > 2);
  cache = new Path[size];
  ptr = 0;
}

RouteCache::RouteCache(const ID& macid, const ID& netid, int size)
: MAC_id(macid), net_id(netid)
{
  assert(size > 2);
  this->size = size;
  cache = new Path[size];
  ptr = 0;
}

RouteCache::~RouteCache()
{
  delete[] cache;
}


int
RouteCache::command(int argc, const char*const* argv)
{

  if(argc == 2) {  
    return TCL_ERROR;
  }
  else if(argc == 3) 
    {    
      if (strcasecmp(argv[1], "ip-addr") == 0) {
	net_id = ID(atoi(argv[2]), ::IP);
	return TCL_OK;
      }
      else if(strcasecmp(argv[1], "mac-addr") == 0) {
	MAC_id = ID(atoi(argv[2]), ::MAC);
      return TCL_OK;
      }
      
      /* must be a looker up */
      TclObject *obj = (TclObject*) TclObject::lookup(argv[2]);
      if(obj == 0)
	return TCL_ERROR;
      
      if(strcasecmp(argv[1], "log-target") == 0) {
	logtarget = (Trace*) obj;
	return TCL_OK;
      }

      return TCL_ERROR;
    }
  
  return TclObject::command(argc, argv);
}

void
RouteCache::trace(char* fmt, ...)
{
  va_list ap;
  
  if (!logtarget) return;

  va_start(ap, fmt);
  vsprintf(logtarget->buffer(), fmt, ap);
  logtarget->dump();
  va_end(ap);
}



#if 0
/* removed 1/23/98 since we're not using it -dam */
void
RouteCache::clock(Time time_floor) 
// tell the route cache what the current time is so that it can
// update or remove routes as appropriate
// note: we rely here on the invariant that nodes always get a clock
// signal with a new timefloor before they are given a frame to
// proccess at that time
{
  // nothing to do
}
#endif

bool
RouteCache::findIndex(Path*& r, int& i, const ID& id, int& start)
     // starting a cache row start, see if there is a route
     // containing id, and if so set r to that route, i
     // to the index of id in r (r[i] == id), and return true,
     // else return false with start == size
{
  for ( ; start < size ; start++)
    for (i = 0; i < cache[start].length(); i++)
      if (cache[start][i] == id)
	{
	  r = &(cache[start]);
	  return true;
	}
  r = 0;
  return false;      
}

void