routecache-squish.cc

在Linux下做的QuadTree的程序

RouteCache::squishAllCacheStrategy(const Path& route, Time,
				   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 = 0;			// 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
  
  if(verbose)
    trace("SRC %.5f %s adding %s owner %s",
	  Scheduler::instance().clock(), net_id.dump(),
	  nr.dump(), nr.owner().dump());

  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 { // for all cache lines

	if(j >= nr.length()) break;  // JOSH

	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(verbose)
	  trace("SRC %.5f %s match(i:%d,j:%d,index:%d) %s %s",
		Scheduler::instance().clock(), net_id.dump(),
		i,j,start, r ? r->dump() : "nothing to dump",
		r ? r->owner().dump(): "");

	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
		if(verbose)
		  trace("SRC %.5f %s blasted cache entry %d",
			Scheduler::instance().clock(), net_id.dump(),
			start);

	      }
	  }
	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 (?)
	    // this is the  case where the new route contains a longer
	    // path to a node than what's found in the route cache already.
	    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
		if(verbose)
		  trace("SRC %.5f %s entered unique rt %s owner %s",
			Scheduler::instance().clock(), net_id.dump(),
			cache[v].dump(), cache[v].owner().dump());

		unique = false;
	      }
	    squish(size,nr,j,*r,i);     // compress the bad prefix route in nr

#if 0
	    /* this is the old logic.  now that we can't squish out the owner
	       of a route from that route, we may have longer routes to nr[j]
	       in the cache, which we should try to compress if possible.
	       Therefore, we want to keep looping. -dam 4/17/98 */

	    // since all routes in cache to nr[j] are same length, we
	    // we can skip on...
	    j = i;
	    start = size;	    
#else
	    /* just keep going... */
#endif
	  }
	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
		if(verbose)
		  trace("SRC %.5f %s entered final unique rt (index %d) %s",
			Scheduler::instance().clock(), net_id.dump(),
			v, cache[v].dump());

    }
}

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

#ifdef DEBUG
  printf("SRC %.5f %s Adding route %s owner %s\n",
	 Scheduler::instance().clock(),net_id.dump(), route.dump(),
	 who_from.dump());
#endif
  if(verbose)
    trace("SRC %.5f %s adding rt %s owner %s",
	  Scheduler::instance().clock(), net_id.dump(),
	  route.dump(), who_from.dump());

  if (route[0] != net_id && route[0] != MAC_id) 
    {
      fprintf(stderr,"%.5f %s adding bad route to cache %s %s\n",
	      t, net_id.dump(), who_from.dump(), route.dump());
      return;
    }
	     
  Path& rt = (Path&) route;	// cast away const Path&
  rt.owner() = who_from;

  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)
  // 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

  if(verbose)
    trace("SRC %.5f %s dead link %s->%s",
	  Scheduler::instance().clock(), net_id.dump(),
	  from.dump(), to.dump());

  
  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(verbose)
		  trace("SRC %.5f %s truncating %s %s",
			Scheduler::instance().clock(), net_id.dump(),
			cache[p].dump(), cache[p].owner().dump());

	      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
	      if(verbose)
		trace("SRC %.5f %s to %s %s",
		      Scheduler::instance().clock(), net_id.dump(),
		      cache[p].dump(), cache[p].owner().dump());

	      break;
	    } // end if this is a dead link
	} // end for all nodes
    } // end for all paths
  return;
}

void
RouteCache::noticeDeadRoute(const Path& route, Time)
// 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...
      if (c == p.length() - 1) return; // path contains only us
      Path stub;
      CopyIntoPath(stub,p,c,p.length()-1);
      // add it in
      addRoute(stub,t, stub[1]);
      // overheard routes are owned by the next hop on the route
      // this should prevent them from ever being shortened -dam 4/17/98
    }
}

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 i, j;
  int min_len, min_index;

  min_len = MAX_SR_LEN + 1;
  min_index = -1;

  for (i = 0; i < size; i++)
    for (j = 0; j < cache[i].length(); j ++)
      if (cache[i][j] == dest && j <= min_len)
	{
	  /* if j == min_len, then randomize or round robin which we
	     return? XXX -dam 4/20/98 */
	  min_index = i;
	  min_len = j;
	}
  if (min_index == -1) return false;

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