calcdest.cc

在Linux下做的QuadTree的程序

extern "C" {
#include <assert.h>
#include <fcntl.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <unistd.h>
#include <err.h>
};

#include "setdest.h"

//#define		DEBUG
#define		SANITY_CHECKS
//#define		SHOW_SYMMETRIC_PAIRS


#define GOD_FORMAT	"$ns_ at %.12f \"$god_ set-dist %d %d %d\"\n"
#define GOD_FORMAT2	"$god_ set-dist %d %d %d\n"
#define NODE_FORMAT	"$ns_ at %.12f \"$node_(%d) setdest %.12f %.12f %.12f\"\n"
#define NODE_FORMAT2	"$node_(%d) setdest %.12f %.12f %.12f\n"
#define NODE_FORMAT3	"$node_(%d) set %c_ %.12f\n"

#define		INFINITY	0x00ffffff
#define		min(x,y)	((x) < (y) ? (x) : (y))
#define		max(x,y)	((x) > (y) ? (x) : (y))
#define		ROUND_ERROR	1e-9

static int count = 0;

/* ======================================================================
   Function Prototypes
   ====================================================================== */
void		usage(char**);
void		init(void);
double		uniform(void);

void		dumpall(void);
void		ComputeW(void);
void		floyd_warshall(void);

void		show_diffs(void);
void		show_routes(void);
void		show_counters(void);


/* ======================================================================
   Global Variables
   ====================================================================== */
double	        RANGE = 250.0;		// transmitter range in meters
double		TIME = 0.0;		// my clock;
double		MAXTIME = 0.0;		// duration of simulation

double		MAXX = 0.0;
double		MAXY = 0.0;
double		MAXSPEED = 0.0;
double		PAUSE = 0.0;
u_int32_t	NODES = 0;
u_int32_t	RouteChangeCount = 0;
u_int32_t       LinkChangeCount = 0;
u_int32_t	DestUnreachableCount = 0;

Node		*NodeList = 0;
u_int32_t	*D1 = 0;
u_int32_t	*D2 = 0;

FILE            *in_file;
FILE            *out_file;


/* ======================================================================
   Random Number Generation
   ====================================================================== */
#define M		2147483647L
#define INVERSE_M	((double)4.656612875e-10)

char random_state[32];

double
uniform()
{
  assert(0 && "shouldn't need random numbers here");
}


/* ======================================================================
   Misc Functions...
   ====================================================================== */
void
usage(char **argv)
{
	fprintf(stderr,
		"\nusage: %s\t[-n <nodes>] \n",
		argv[0]);
	fprintf(stderr,
		"\t\t[-t <simulation time>]\n");
	fprintf(stderr,
		"\t\t-i <input_file> -o <output file>\n");
	fprintf(stderr,
"\t\t #nodes, max time, and range read from scenario file if possible\n\n");
	
}

void
init()
{
	/*
	 * Allocate memory for globals
	 */
	NodeList = new Node[NODES];
	if(NodeList == 0) {
		perror("new");
		exit(1);
	}

	D1 = new u_int32_t[NODES * NODES];
	if(D1 == 0) {
		perror("new");
		exit(1);
	}
	memset(D1, '\xff', sizeof(u_int32_t) * NODES * NODES);

	D2 = new u_int32_t[NODES * NODES];
	if(D2 == 0) {
		perror("new");
		exit(1);
	}
	memset(D2, '\xff', sizeof(u_int32_t) * NODES * NODES);
}

void
OpenAndReadHeader(char *in_filename, char *out_filename)
  /* assumes all initialization comments are at top of file with no
     no lines that start with other than '#' */
{
  char buf[256];
  
  in_file = fopen(in_filename,"r");
  out_file = fopen(out_filename,"w");
  
  if (NULL == in_file) err(-1,"can't open inputfile '%s'",in_filename);
  if (NULL == out_file) err(-1,"can't open outputfile '%s'",out_filename);
  
  while (!feof(in_file)) {

    *buf = fgetc(in_file);
    ungetc(*buf,in_file);
    if (*buf != '#') break;

    fgets(buf, sizeof(buf), in_file);

    /* check to see if we need data from the line */
    sscanf(buf, "# nodes: %d, max time: %lf", &NODES, &MAXTIME);
    sscanf(buf, "# nominal range: %lf", &RANGE);
    
    fprintf(out_file, "%s", buf);
  }
  NODES += 1;			// correct for 1-based indexs
  fflush(out_file);
}

void
ReadInMovementPattern()
{
  char buf[256];
  u_int n;
  double x,y,z,t,s;
  struct setdest *setdest;

  while (!feof(in_file)) {

    fgets(buf, sizeof(buf), in_file);
    fprintf(out_file, "%s", buf);
    if (*buf == '#') continue;
    if (*buf == '\n') continue;

    /* check to see if we need data from the line */
    if (2 == sscanf(buf,"$node_(%d) set Z_ %lf", &n, &z)) 
      {
	assert(n < NODES);
	NodeList[n].position.Z = z;
      }
    else if (2 == sscanf(buf,"$node_(%d) set X_ %lf", &n, &x)) 
      {
	assert(n < NODES);
	NodeList[n].position.X = x;
      }
    else if (2 == sscanf(buf,"$node_(%d) set Y_ %lf", &n, &y)) 
      {
	assert(n < NODES);
	NodeList[n].position.Y = y;
      }
    else if (5 == sscanf(buf,"$ns_ at %lf \"$node_(%d) setdest %lf %lf %lf\"", 
			&t, &n, &x, &y, &s)) 
      {
	assert(n < NODES);
	assert(t <= MAXTIME);
	setdest = (struct setdest *)malloc(sizeof(*setdest));
	assert(setdest);
	setdest->X = x; setdest->Y = y; setdest->Z = 0;
	setdest->time = t;
	setdest->speed = s;
	if (NodeList[n].traj.lh_first 
	    && t > NodeList[n].traj.lh_first->time)
	  {
	    printf("setdest's must be in anti-chronological order in input file!\n");
	    printf("failed on node %d\n",n);
	    exit(-1);
	  }
	LIST_INSERT_HEAD(&NodeList[n].traj,setdest,traj);
#if 1
	NodeList[n].time_arrival = t;	/* fix ??? */
#endif
      }
    else 
      {
	printf("unparsable line: '%s'", buf);
	continue;
      }
  }  
  fflush(out_file);  
}

int
main(int argc, char **argv)
{
	char ch;
	char *in_filename = NULL;
	char *out_filename = NULL;

	while ((ch = getopt(argc, argv, "n:t:i:o:")) != EOF) {       

		switch (ch) { 

		case 'n':
			NODES = atoi(optarg) + 1;
			break;

		case 't':
			MAXTIME = atof(optarg);
			break;
	
		case 'i':
			in_filename = optarg;
			break;

		case 'o':
			out_filename = optarg;
			break;

		default:
			usage(argv);
			exit(1);
		}
	}

	if (NULL == in_filename || NULL == out_filename) {
	        usage(argv);
		exit(1);
	}

	OpenAndReadHeader(in_filename, out_filename);

	if(NODES == 0 || MAXTIME == 0.0) {
		usage(argv);
		exit(1);
	}

	init();

	ReadInMovementPattern();

	while(TIME <= MAXTIME) {
		double nexttime = 0.0;
		u_int32_t i;

		for(i = 1; i < NODES; i++) {
			NodeList[i].Update();
		}

		for(i = 1; i < NODES; i++) {
			NodeList[i].UpdateNeighbors();
		}

		for(i = 1; i < NODES; i++) {
			Node *n = &NodeList[i];
	
			if(n->time_transition > 0.0) {
				if(nexttime == 0.0)
					nexttime = n->time_transition;
				else
					nexttime = min(nexttime, n->time_transition);
			}

			if(n->time_arrival > 0.0) {
				if(nexttime == 0.0)
					nexttime = n->time_arrival;
				else
					nexttime = min(nexttime, n->time_arrival);
			}
		}

		floyd_warshall();

#ifdef DEBUG
		show_routes();
#endif

	 	show_diffs();

#ifdef DEBUG
		dumpall();
#endif

		if (nexttime <= TIME + ROUND_ERROR) 
		  TIME = MAXTIME + 1;   /* we're done */
		else 
		  TIME = nexttime;
#ifdef OLD
		assert(nexttime > TIME + ROUND_ERROR);
		TIME = nexttime;
#endif

	}

	show_counters();
}


/* ======================================================================
   Node Class Functions
   ====================================================================== */
u_int32_t Node::NodeIndex = 0;

Node::Node()
{
	u_int32_t i;

	index = NodeIndex++;

	if(index == 0)
		return;

	route_changes = 0;
        link_changes = 0;

        /*
         * For the first PAUSE seconds of the simulation, all nodes
         * are stationary.
         */
	time_arrival = TIME;
	time_update = TIME;
	time_transition = 0.0;

	position.X = position.Y = position.Z = 0.0;
	destination.X = destination.Y = destination.Z = 0.0;
	direction.X = direction.Y = direction.Z = 0.0;
	speed = 0.0;

	neighbor = new Neighbor[NODES];
	if(neighbor == 0) {
		perror("new");
		exit(1);
	}

	LIST_INIT(&traj);

	for(i = 1; i < NODES; i++) {
		neighbor[i].index = i;
		neighbor[i].reachable = (index == i) ? 1 : 0;
		neighbor[i].time_transition = 0.0;
	}
}



void
Node::RandomPosition()
{
	position.X = uniform() * MAXX;
	position.Y = uniform() * MAXY;