simple_rtcache.cc

在Linux下做的QuadTree的程序

/* simple_rtcache.cc

   handles routes
   $Id: simple_rtcache.cc,v 1.1.1.1 2000/08/28 18:40:10 jinyang Exp $

*/

extern "C" {
#include <stdio.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

/*===============================================================
  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;
    }
  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;
  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
	    break;
	  }
      }

#ifdef DEBUG
  fprintf(fout,"      squished "); r.unparse(fout);
#endif
  
  // 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);fprintf(fout,"\n");
#endif
}

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)
{
  Tcl& tcl = Tcl::instance();

  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], "tracetarget") == 0) {
	tracetarget = (Trace*) obj;
	return TCL_OK;
      }

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



#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;
	}
  return false;      
}

void
RouteCache::squishAllCacheStrategy(const Path& route, Time t,
				   const ID& info_src)
     // do the full check on all routes to all nodes in cache
     // when we add a new route
     // take new route nr (obtained from info_src) and add it at time t
{
  Path nr = route.copy();
  bool unique = false;		// does nr contain any unique routes
  Path *r;			// a route in the cache
  int i;			// index of nr[j] in r
  int start;			//
  
#ifdef DEBUG
  fprintf(fout,"   Node: "); net_id.unparse(fout);
  fprintf(fout," squishing rt ");nr.unparse(fout);fprintf(fout," into cache\n");
#endif
  
  assert(nr[0] == net_id || nr[0] == MAC_id && nr.length() > 1);
  for (int j = 1; j < nr.length(); j++)
    {
      start = -1;
      bool found = false;	// does cache contain nr[j] at all?
      do {
	start = start + 1;	// skip the cache line one we've done
	bool exists = findIndex(/*out*/r,i,nr[j],start);
	found = found || exists;

#ifdef DEBUG
	if (exists) {
	  fprintf(fout,"    match(i:%d,j:%d,index:%d) ",i,j,start);
	  r->unparse(fout);
	  fprintf(fout,"\n");
	}
#endif
	if (exists && j < i)
	  {
	    squish(start,*r,i,nr,j);
	  }
	else if (exists && j == i)
	  { // see if r is just a prefix of nr
	    // this keeps the caching from building up multiple routes
	    // of the form x,y ; x,y ; x,y ; etc...
	    if (i = 1 && r->length() == 2 )
	      { // r is completely contained in nr
		r->reset();
		unique = true;
#ifdef DEBUG
		fprintf(fout,"      blasted cache entry %d\n",start);
#endif
	      }
	  }
	else if (cache_trust_senders && exists && j > i && nr[j] == info_src)
	  { // someone is telling us that the route to them is
	    // longer than the route we have for them in the cache
	    // so extend the path in the cache
	    int orig_len = r->length()-1;
	    r->setLength(r->length()+j-i);
	    for (int c = orig_len; c > i; c--)
	      (*r)[c+j-i] = (*r)[c];
	    CopyIntoPath(*r,nr,0,j);
#ifdef DEBUG
		fprintf(fout,"      sender "); info_src.unparse(fout);
		fprintf(fout," sez expand route to: ");
		(*r).unparse(fout); fprintf(fout,"\n");
#endif
	  }
	else if (exists && j > i)
	  { // shouldn't happen very often (?)
	    if (unique)
	      { // save the unique routes in nr[0->j]
		int v = pickVictim(start); // don't clobber the current line
		cache[v].reset();
		CopyIntoPath(cache[v],nr,0,j-1);
#ifdef DEBUG
		fprintf(fout,"      entered unique route: ");
		cache[v].unparse(fout); fprintf(fout,"\n");
#endif
		unique = false;
	      }
	    squish(size,nr,j,*r,i);     // compress the bad prefix route in nr
	    // since all routes in cache to nr[j] are same length, we
	    // we can skip on...
	    j = i;
	    start = size;	    
	  }
	else
	  {;}
      } while (start != size);
      if (!found) unique = true;
    }
  if (unique)
    { // there are still unique routes in nr, so save 'em
      int v = pickVictim();
      cache[v].reset();
      CopyIntoPath(cache[v],nr,0,nr.length()-1);      
#ifdef DEBUG
		fprintf(fout,"    entered final unique route (index %d): ",
		       v);
		cache[v].unparse(fout); fprintf(fout,"\n");
#endif
    }
}

void
RouteCache::addRoute(const Path& route, Time t, const ID& who_from)
// add this route to the cache (presumably we did a route request
// to find this route and don't want to lose it)
// who_from is the id of the routes provider
{
  assert(!(net_id == invalid_addr));
  
  if (route.length() < 2) return; // we laugh in your face
  Path& rt = (Path&) route;
  if (cache_squish_all_on_add)
    { // do the strategy in my paper notes
      squishAllCacheStrategy(rt, t, who_from);
    }
  else
    { // the simplest cache adding strategy
#ifdef DEBUG
  fprintf(fout,"   Node: "); net_id.unparse(fout);
  fprintf(fout," adding rt ");rt.unparse(fout);fprintf(fout," into cache\n");
#endif
      if (!(rt[0] == MAC_id || rt[0] == net_id)) return;
      cache[pickVictim()] = rt.copy();
    }
}

void
RouteCache::noticeDeadLink(const ID&from, const ID& to, Time t)
  // the link from->to isn't working anymore, purge routes containing
  // it from the cache
{
#ifdef DEBUG
  fprintf(fout,"        Node:");
  net_id.unparse(fout);
  fprintf(fout," cache saw dead link ");
  from.unparse(fout);
  fprintf(fout,"->");
  to.unparse(fout);
  fprintf(fout,"\n");
#endif
  
  for (int p = 0 ; p < size ; p++)
    { // for all paths in the cache
      for (int n = 0 ; n < (cache[p].length()-1) ; n ++)
	{ // for all nodes in the path
	  if (cache[p][n] == from && cache[p][n+1] == to)
	    {
#ifdef DEBUG
	      fprintf(fout,"  truncating path ");
	      cache[p].unparse(fout);
#endif
	      if (n == 0)
		cache[p].reset();        // kill the whole path
	      else
		cache[p].setLength(n+1); // truncate the path here
#ifdef DEBUG
	      fprintf(fout," to ");
	      cache[p].unparse(fout);
	      fprintf(fout,"\n");
#endif
	      break;
	    } // end if this is a dead link
	} // end for all nodes
    } // end for all paths
  return;
}

void
RouteCache::noticeDeadRoute(const Path& route, Time t)
// some link between us (which must be either path[0]
// or path[index-1]) and the end of the path is dead)
{
  // if (route[0] != MAC_id && route[0] != net_id) return;

  //  world_statistics.sawDeadRoute(net_id,t,route);

  for (int c = 0; c < size ; c++)
    {
      if (SamePath(route,cache[c]))
	cache[c].reset();
    }
}

void
RouteCache::noticeRouteUsed(const Path& route, Time t)
// tell the cache about a route we saw being used
{
  int c;
  if (route.length() < 2) return; // we laugh in your face
  if (cache_ignore_hints)
    {
      ;  // we take no hints...
    }
  else
    { // find the sub route starting with us
      Path& p = (Path&) route;
      for (c = 0; c < p.length() ; c++)
	if (p[c] == net_id || p[c] == MAC_id) break;
      if (c == p.length()) return; // we aren't in the path...
      Path stub;
      CopyIntoPath(stub,p,c,p.length()-1);
      // add it in
      addRoute(stub,t, (stub[0].type == ::MAC ? MAC_id : net_id));
    }
}

bool
RouteCache::findRoute(ID dest, Path& route)
// if there is a cached path from us to dest returns true and fills in
// the route accordingly. returns false otherwise
{
  assert(!(net_id == invalid_addr));

  int index = searchRoute(dest);
  if (index == size) return false;
  route.reset();
  for (int c = 0 ; c < cache[index].length(); c++)
    {
      route.appendToPath(cache[index][c]);
      if (cache[index][c] == dest) break;
    }
  return true;
}