simplecache.cc

在Linux下做的QuadTree的程序

/* simplecache.cc
   $Id: simplecache.cc,v 1.1.1.1 2000/08/28 18:40:10 jinyang Exp $


*/

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

#undef DEBUG

#include <god.h>
#include "path.h"
#include "hdr_sr.h"
#include "routecache.h"

/*===============================================================
  function selectors
----------------------------------------------------------------*/
static const int verbose = 0;

#if DSRRC_USE_GOD_INFO
# warning Using God Info
#endif

#if defined(BIDIRECTIONAL) && defined(YIHCHUN_DSR)
# warning Using Bidirectional Links
#endif

#if defined(NEGATIVE_LINK_CACHE) && defined(YIHCHUN_DSR)
# warning Using Negative Link Cache
#endif

#ifdef NO_EXTRA_OPTIMIZATIONS
# warning Not salvaging packets
# warning Not replying from cache
#endif

#ifdef NO_CACHE_REPLIES
# warning Not replying from cache
#endif

#if DSRRC_USE_GOD_INFO
# include <scheduler.h>
# include <god.h>
#endif 


/*===============================================================
  Class declaration
----------------------------------------------------------------*/
class SimpleCache : public RouteCache {

public:
  MobiCache();
  ~MobiCache();
  void noticeDeadLink(const ID&from, const ID& to, Time t);
  // the link from->to isn't working anymore, purge routes containing
  // it from the cache
  void noticeRouteUsed(const Path& route, Time t,
		       const ID& who_from);
  // tell the cache about a route we saw being used
  void 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)
  bool findRoute(ID dest, Path& route, int for_use = 0);
  // if there is a cached path from us to dest returns true and fills in
  // the route accordingly. returns false otherwise
  // if for_use, then we assume that the node really wants to keep 
  // the returned route so it will be promoted to primary storage if not there
  // already
  int command(int argc, const char*const* argv);

  // cache logging stuff and statistics
  void checkCache();
  int checkRoute(Path &p, char *msg);
  void  checkRoute(Path &p, int&, int&, double&);
  int   add_route_count;
  int   notice_route_count;
  int   find_count;
  int   find_miss_count;
};

struct PathElt {
  Path      path;
  ID        dest;
  PathElt  *next;
  PathElt **prev;
};

PathElt *findnode(const ID &);
PathElt *cache;

RouteCache *
makeRouteCache()
{
  return new SimpleCache();
}
/*===============================================================

----------------------------------------------------------------*/

bool 
RouteCache::findRoute(ID dest, Path& route, int for_use) 
{
  PathElt *there = findnode(dest);

  if (there) {
    route = there->path;

    return true;
  } else {
    return false;
  }

}



RouteCache::RouteCache() {
  cache       = 0;
}

RouteCache::~RouteCache() 
{
  PathElt *tmp;
  while (cache) {
    tmp = cache->next;
    delete cache;
    cache = tmp;
  }
}

void 
RouteCache::noticeDeadLink(const ID&from, const ID& to, Time) {
  PathElt *walk = cache;
  PathElt *tmp;
  
  while (walk) {
    tmp = walk->next;

    for (int i=1;i<walk->path.length();i++) {
      if (from == walk->path[i-1] && to == walk->path[i]) {
	*walk->prev = walk->next;

	if (walk->next)
	  walk->next->prev = walk->prev;

	delete walk;
	break;
      }
    }

    walk = tmp;
  }
}

RouteCache::PathElt *
RouteCache::findnode(const ID &target) {
  PathElt *walk = cache;

  while (walk && walk->dest != target)
    walk = walk->next;

  return walk;
}

void 
RouteCache::noticeRouteUsed(const Path&, Time) {
  return;
}

void 
RouteCache::addRoute(const Path& route, Time, const ID&) {
  PathElt *there = findnode(route[route.length()-1]);
  if (there) {
    if (there->path.length() >= route.length())
      there->path = route;
  } else {
    there = new PathElt;
    there->path = route;
    there->dest = route[route.length()-1];
    there->next = cache;
    there->prev = &cache;

    if (there->next)
      there->next->prev = &(there->next);

    cache = there;
  }
}


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

  printf("Warning!!  Simple Route Cache %s used.  It is not known to work\n",
	 __FILE__);
  fprintf(stderr,
	  "Warning!!  Simple Route Cache %s used.  It is not known to work\n",
	  __FILE__);
  exit(-1);

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

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

void 
RouteCache::dump(FILE *out) {
  for (PathElt *walk = cache; walk; walk = walk->next)
    fprintf(out, "To %s: %s\n", walk->dest.dump(), walk->path.dump());
}