setws.cc

在Linux下做的QuadTree的程序

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <fcntl.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <unistd.h>
#include <string.h>
#include <err.h>

#define ROUND_ERROR 1e-9
#define		min(x,y)	((x) < (y) ? (x) : (y))

void
usage(char **argv)
{
   fprintf(stderr, "\nusage: %s\t-n <nodes> -w <wake time> -s <sleep time> -t <simulation time> -g <percentage of stable nodes>\n", 
	  argv[0]);
}

double TIME = 0.0;
double MAXTIME = 0.0;
double PERCENTAGE = 0.0;
double LIFETIME = 0.0;
double DEATHTIME = 0.0;
u_int32_t NODES = 0;
double *NodeList;

static int count = 0;

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

char random_state[32];

double
uniform()
{
   count++;
   return random() * INVERSE_M;
}


void
init()
{
   /*
    * Initialized the Random Number Generation
    */
   struct timeval tp;
   int fd, seed, bytes;
   
   if((fd = open("/dev/random", O_RDONLY)) < 0) {
   	perror("open /dev/random");
   	exit(1);
   }
   if((bytes = read(fd, random_state, sizeof(random_state))) < 0) {
   	perror("read");
   	exit(1);
   }
   close(fd);
   
   fprintf(stderr, "*** read %d bytes from /dev/random\n", bytes);
   
   if(bytes != sizeof(random_state)) {
     fprintf(stderr,"Not enough randomness. Reading `.rand_state'\n");
     if((fd = open(".rand_state", O_RDONLY)) < 0) {
       perror("open .rand_state");
       exit(1);
     }
     if((bytes = read(fd, random_state, sizeof(random_state))) < 0) {
       perror("reading .rand_state");
       exit(1);
     }
     close(fd);
   }
   
   if(gettimeofday(&tp, 0) < 0) {
   	perror("gettimeofday");
   	exit(1);
   }
   seed = (tp.tv_sec  >> 12 ) ^ tp.tv_usec;
   (void) initstate(seed, random_state, bytes & 0xf8);
   
   /*
    * Allocate memory for globals
    */
   NodeList = new double[NODES];
   if(NodeList == 0) {
   	perror("new");
   	exit(1);
  }

   for (int i=0;i<NODES;i++) {
       NodeList[i] = 0.0;
   }
  
} 
  

int main(int argc, char **argv)
{
    char ch;
    while ((ch = getopt(argc, argv, "n:w:s:t:g:")) != EOF) {       

	switch (ch) { 

	case 'n':
	    NODES = atoi(optarg)+1;
	    break;
	case 'w':
	    LIFETIME = atof(optarg);
	    break;
	case 's':
	    DEATHTIME = atof(optarg);
	    break;
	case 't':
	    MAXTIME = atof(optarg);
	    break;
	case 'g':
	    PERCENTAGE = atof(optarg);
	    break;
	default:
	    usage(argv);
	    exit(1);

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

    fprintf(stdout, "#\n# nodes: %d, wake time: %f, sleep time: %f\n", NODES-1, LIFETIME,DEATHTIME);
  
    init();

    int i;
    double nexttime;
    double waketime, sleeptime;
    double uni;
    int max_stable_nodes = floor(PERCENTAGE * (NODES-1));

    while (max_stable_nodes) {
      for (int i = 1; i< NODES; i++) {
	//i want roughly 60% of the nodes to be awake first
	uni = uniform();
	if ((NodeList[i]<MAXTIME) && (uni<PERCENTAGE)) {
	    max_stable_nodes--;
	    if (max_stable_nodes == 0) break;
	    //these are stable nodes
	    fprintf(stdout, "$ns_ at %.12f \"$node_(%d) wakeup %.12f\"\n",
			TIME, i, MAXTIME);
    	    fprintf(stdout, "$ns_ at %.12f \"$god_ wakeup %d %.12f\"\n",TIME,i,MAXTIME);
	    NodeList[i] = MAXTIME + 0.1;
	}
      }
    }

    for (int i=1;i<NODES;i++) {
	if (NodeList[i]<MAXTIME) {
	    uni = uniform();
	    //50% of the unstable nodes should be asleep first
	    if (uni > 0.5) {
		NodeList[i] = DEATHTIME/2 + uniform()*(DEATHTIME)/2;
	    }
	}  
    }

    while (TIME <= MAXTIME) {
	nexttime = 0.0;
	for (i = 1; i < NODES; i++) {
	    if (TIME >= NodeList[i]) {
		waketime = LIFETIME/2 + uniform() * (LIFETIME)/2;
		sleeptime = DEATHTIME/2 + uniform() * (DEATHTIME)/2;
		//update the waketime and sleep time of each node
		fprintf(stdout, "$ns_ at %.12f \"$node_(%d) wakeup %.12f\"\n",
			TIME, i, waketime);
		fprintf(stdout, "$ns_ at %.12f \"$god_ wakeup %d %.12f\"\n",TIME,i,waketime);
		NodeList[i] = TIME + waketime + sleeptime;
	    }
	}

	for (i = 1; i< NODES; i++) {
	    if (nexttime == 0.0) {
		nexttime = NodeList[i];
	    }else{
		nexttime = min(nexttime,NodeList[i]);
	    }
	}

	assert(nexttime > TIME + ROUND_ERROR);
	TIME = nexttime;
    }
}