locserver.cc

在Linux下做的QuadTree的程序

	/* inflate the timeout value a bit*/
	timeout_int = timeout_int + 4;
#endif
	for (int i=0;i<4;i++) {
	    if ((i << (stop-2)) == (myloc.loc & (0x3 << (stop-2)))) {
	    /*
	    if (i == ((myloc.loc << (MAX_MASK-stop))>> (MAX_MASK-stop+2)) ) {
	    */
	    }else{
		x = myloc.loc & (0xffffffff << stop);
		y = i<<(stop-2);
		dst_loc.loc = x+y;
		dst_loc.mask = myloc.mask - stop +2;
		assert(!inSameGrid(dst_loc,myloc));
		pkt = parent->allocpkt();

		hgpsh =  (hdr_hgps*)pkt->access(parent->off_hgps_); 
		iph =  (hdr_ip*)pkt->access(parent->off_ip_); 
		cmnh =  (hdr_cmn*)pkt->access(parent->off_cmn_);

		iph->dport_ = RT_PORT;
		iph->dst() = 0; //i don't care about specific recipient
		iph->src() = parent->myaddr_;

		hgpsh->init();
		hgpsh->src_loc_ = myloc;
		hgpsh->dst_loc_ = dst_loc;

		hgpsh->update_loc_ = dst_loc; //the area that the update takes effect
#ifdef TRIGGER_UPDATE_ONLY
		hgpsh->timeout_inteval_ = timeout_int;
#else
		hgpsh->timeout_inteval_ = 1.5 * pow(2, stop/2) * ((double)parent->update_distance_/getSpeed()) ;
#endif

		hgpsh->type_ = LOC_UPDATE;

		cmnh->ptype() = PT_HGPS;
		cmnh->size() = hgpsh->size();

		router->sendOutPktWithLocation(pkt,2*(stop-2)+jitter(1,1),false);
	    }
	}
	stop += 2;
    }

}

void
LocServer::addUpdateLiveConn(nsaddr_t id, location loc)
{
    assert(loc.mask!=0);
    live_connections->addUpdateEntry(id,loc,LIVE_CONN_TIMEOUT);
}

void
LocServer::purgeLocCache(nsaddr_t id)
{
    loc_cache->deleteEntry(id);
}

void
LocServer::updateLocCache(nsaddr_t id,location loc, double timeout_int)
{
    loc_cache->addUpdateEntry(id,loc,timeout_int);
}

LocTable::LocTable(int s, bool c)
{
    size = s;
    chopoff = c;

    table = new loc_entry[size];
    for (int i=0;i<size;i++) {
	table[i].lastupdate_time = -99999.9;
	table[i].timeout = -99999.9;
	table[i].id = -1;
    }
    used_size = 0;
}

LocTable::~LocTable()
{
    delete[] table;
}

void 
LocTable::addUpdateEntry(nsaddr_t id, location loc, double timeout)
{
    double now = Scheduler::instance().clock();
    int victim = -1;
    int j;

    for (int i = 0; i<size; i++) {
	j = (id+i) % size; //a naive hash
	if (id == table[j].id) {
	    table[j].loc = loc;
	    table[j].lastupdate_time = now;
	    table[j].timeout = timeout+now;
	    return;
	}else if ((victim == -1) && (now > table[j].timeout)) {
	    victim = j;
	}
    }
    
    if (victim == -1) {

	if (!chopoff) {
	    printf("no victim in loctable(%.2f) add entry!\n",timeout);
	    abort();
	}

    }else{
	if ((victim+1) > used_size) {
	    used_size = victim+1;
	}

	table[victim].lastupdate_time = now;
	table[victim].id = id;
	table[victim].loc = loc;
	table[victim].timeout = now+timeout;
    }

}    

void
LocTable::deleteEntry(nsaddr_t id)
{
    int j;
    for (int i=0;i<size;i++) {
	j = (id+i) % size;
	if (table[j].id == id) {
	    table[j].id = -1;
	    table[j].lastupdate_time = -99999.0;
	    table[j].timeout = -99999.0;
	    return;
	}
    }
	    
}

/* clean up all the location table */
void
LocTable::cleanTable()
{
    for (int i=0;i<size;i++) {
	table[i].id = -1;
	table[i].lastupdate_time = -9999.0;
	table[i].timeout = -9999.0;
    }
    used_size = 0;
}

loc_entry *
LocTable::getEntry(nsaddr_t id, double now)
{
    int j;
    for (int i=0;i<size;i++) {
	j = (id +i)% size;
	if ((table[j].id == id) && (now < table[j].timeout)) {
	    return &table[j];
	}
    }
    return NULL;
}

bool
LocTable::findClosestinRT(nsaddr_t myid,location myloc, nsaddr_t dst, struct route_entry *nt, loc_entry &entry, bool in_same_grid)
{

    int closest_dist = myid - dst;
    int dist;
    double now = Scheduler::instance().clock();

    entry.id = 0;

    assert(myid!=dst);

    for (int i=0;i<MAX_RT_ENTRIES;i++) {
	if (((now - nt[i].lastupdate_time)<NEIGHBOR_TIMEOUT_INTEVAL) && ((!in_same_grid) ||(nt[i].loc.loc == myloc.loc))) { 
	    dist = nt[i].dst- dst;
	    if (dist == 0) {
		entry.id = dst;
		entry.loc = nt[i].loc;
		entry.lastupdate_time = nt[i].lastupdate_time;
		return true;
	    }

	    /*
	    if (((closest_dist<0) && (dist<0) && (dist>closest_dist))
		|| ((closest_dist>0) && (dist<0))
		|| ((closest_dist>0) && (dist>0) && (dist<closest_dist))){
		*/
	      if (((closest_dist>0) && (dist>0) && (dist<closest_dist))
		|| (closest_dist<0) && (dist>0)
		|| (closest_dist<0) && (dist<0) && (dist<closest_dist)) {
		closest_dist = dist;
		entry.id = nt[i].dst;
		entry.loc =nt[i].loc;
		entry.lastupdate_time = nt[i].lastupdate_time;
	    }
	}
    }
    if (entry.id == 0) {
	return false;
    }else{
	return true;
    }
}

/* find the closest node in location entry database 
   in ID space to dst. If such a node is found and is closer than me, return true,
   otherwise return false */
bool
LocTable::findClosest(nsaddr_t myid,location myloc,nsaddr_t dst,struct route_entry *nt,loc_entry &entry, double lastupdate_time)
{
    int closest_dist = myid - dst;
    int dist;

    double now = Scheduler::instance().clock();

    entry.id = 0;

    assert(myid != dst);

    for (int i=0;i<MAX_RT_ENTRIES;i++) {
	if (((now - nt[i].lastupdate_time)<NEIGHBOR_TIMEOUT_INTEVAL) && (nt[i].loc.loc == myloc.loc)) {
	    dist = nt[i].dst- dst;
	    if ((dist == 0) && (nt[i].lastupdate_time > lastupdate_time)) {
		entry.id = dst;
		entry.loc = nt[i].loc;
		entry.lastupdate_time = nt[i].lastupdate_time;
		return true;
	    }
	    /*
	    if (((closest_dist<0) && (dist<0) && (dist>closest_dist))
		|| ((closest_dist>0) && (dist<0))
		|| ((closest_dist>0) && (dist>0) && (dist<closest_dist))){
	    */
	    if (((closest_dist>0) && (dist>0) && (dist<closest_dist))
		|| (closest_dist<0) && (dist>0)
		|| (closest_dist<0) && (dist<0) && (dist<closest_dist)) {
		closest_dist = dist;
		entry.id = nt[i].dst;
		entry.loc =nt[i].loc;
		entry.lastupdate_time = nt[i].lastupdate_time;
	    }
	}
    }

    for (int i=0;i<used_size;i++) {
	if ((table[i].id == -1) || (now > table[i].timeout)) {
	}else{
	    dist = table[i].id - dst;

	    if ((dist == 0) && (table[i].lastupdate_time > lastupdate_time)) {
		entry = table[i];
		return true;
	    }
/*
	    if (((closest_dist<0) && (dist<0) && (dist>closest_dist))
		|| ((closest_dist>0) && (dist<0))
		|| ((closest_dist>0) && (dist>0) && (dist<closest_dist))){
*/
 	    if (((closest_dist>0) && (dist>0) && (dist<closest_dist))
		|| (closest_dist<0) && (dist>0)
		|| (closest_dist<0) && (dist<0) && (dist<closest_dist)) {

		closest_dist = dist;
		entry = table[i];
	    }
	}
    }

    if (entry.id == 0) {
	return false;
    }else{
	return true;
    }
}

/* find the closest node in the specified grid in location entry database 
   in ID space to dst. If such a node is found and is closer than me, return true,
   otherwise return false */
bool
LocTable::findClosestInGrid(nsaddr_t myid,location myloc,nsaddr_t dst, location dst_loc,struct route_entry *nt,loc_entry &entry, double lastupdate_time)
{
    int closest_dist = myid - dst;
    int dist;

    double now = Scheduler::instance().clock();

    entry.id = 0;

    assert(myid != dst);

    for (int i=0;i<MAX_RT_ENTRIES;i++) {
	if (((now - nt[i].lastupdate_time)<NEIGHBOR_TIMEOUT_INTEVAL) && (nt[i].loc.loc == myloc.loc) && inSameGrid(nt[i].loc,dst_loc)) {
	    dist = nt[i].dst- dst;
	    if ((dist == 0) && (nt[i].lastupdate_time > lastupdate_time)) {
		entry.id = dst;
		entry.loc = nt[i].loc;
		entry.lastupdate_time = nt[i].lastupdate_time;
		return true;
	    }
	    /*
	    if (((closest_dist<0) && (dist<0) && (dist>closest_dist))
		|| ((closest_dist>0) && (dist<0))
		|| ((closest_dist>0) && (dist>0) && (dist<closest_dist))){
	    */
	    if (((closest_dist>0) && (dist>0) && (dist<closest_dist))
		|| (closest_dist<0) && (dist>0)
		|| (closest_dist<0) && (dist<0) && (dist<closest_dist)) {
		closest_dist = dist;
		entry.id = nt[i].dst;
		entry.loc =nt[i].loc;
		entry.lastupdate_time = nt[i].lastupdate_time;
	    }
	}
    }

    for (int i=0;i<used_size;i++) {
	if ((table[i].id == -1) || (now > table[i].timeout) || (!inSameGrid(table[i].loc,dst_loc))) {
	}else{
	    dist = table[i].id - dst;

	    if ((dist == 0) && (table[i].lastupdate_time > lastupdate_time)) {
		entry = table[i];
		return true;
	    }
/*
	    if (((closest_dist<0) && (dist<0) && (dist>closest_dist))
		|| ((closest_dist>0) && (dist<0))
		|| ((closest_dist>0) && (dist>0) && (dist<closest_dist))){
*/
 	    if (((closest_dist>0) && (dist>0) && (dist<closest_dist))
		|| (closest_dist<0) && (dist>0)
		|| (closest_dist<0) && (dist<0) && (dist<closest_dist)) {

		closest_dist = dist;
		entry = table[i];
	    }
	}
    }

    if (entry.id == 0) {
	return false;
    }else{
	return true;
    }
}


/* find the closest node in ID space to dst but not dst node
   this is for the node handling location update to check if itself is
   indeed the node to be updated, despite the fact that there might 
   already be location table entry for the dst node*/
void
LocTable::findClosestExceptDst(nsaddr_t myid, location myloc,nsaddr_t dst,struct route_entry *nt,location update_loc,loc_entry &entry)
{
    int closest_dist; 
    int dist;

    double now = Scheduler::instance().clock();


    if (myid == dst) {
	return;
    }

    /* if the closest entry has been initialized to some node ID, compare it with
       myid and take a closer one as the starting ID */
    if (entry.id!=0) {
	closest_dist = entry.id - dst;
	dist = myid - dst;
	/*
	if (((closest_dist<0) && (dist<0) && (dist>closest_dist))
		|| ((closest_dist>0) && (dist<0))
		|| ((closest_dist>0) && (dist>0) && (dist<closest_dist))){
	*/
	if (((closest_dist>0) && (dist>0) && (dist<closest_dist))
		|| (closest_dist<0) && (dist>0)
		|| (closest_dist<0) && (dist<0) && (dist<closest_dist)) {
		closest_dist = dist;
		entry.id = myid; 
       }

    }else {
	closest_dist = myid - dst;
	entry.id = myid;
    }

    assert(closest_dist != 0);
    /* part of the location table database is in one's neighbor table,
       so check neighbor table first*/
    for (int i=0;i<MAX_RT_ENTRIES;i++) {

	if (((now - nt[i].lastupdate_time)<NEIGHBOR_TIMEOUT_INTEVAL) && (inSameGrid(nt[i].loc,update_loc))) {
	 
	    dist = nt[i].dst- dst;

	    if (dist == 0) {  //ignore direct dst location entry
		continue;
	    }
	    /*
	    if (((closest_dist<0) && (dist<0) && (dist>closest_dist))
		|| ((closest_dist>0) && (dist<0))
		|| ((closest_dist>0) && (dist>0) && (dist<closest_dist))){
	    */
	    if (((closest_dist>0) && (dist>0) && (dist<closest_dist))
		|| (closest_dist<0) && (dist>0)
		|| (closest_dist<0) && (dist<0) && (dist<closest_dist)){
		closest_dist = dist;
		entry.id = nt[i].dst;
		entry.loc = nt[i].loc;
	    }
	}
    }

    /* check location table */
    for (int i=0;i<used_size;i++) {
	if ((table[i].id == -1) || (now > table[i].timeout)) {
	}else{
	    if (!inSameGrid(table[i].loc,update_loc)) {
		continue;
	    }

	    dist = table[i].id - dst;

	    if (dist == 0) { //ignore direct dst location entry
		continue;
	    }
	    /*
	    if (((closest_dist<0) && (dist<0) && (dist>closest_dist))
		|| ((closest_dist>0) && (dist<0))
		|| ((closest_dist>0) && (dist>0) && (dist<closest_dist))){
	    */
	    if (((closest_dist>0) && (dist>0) && (dist<closest_dist))
		|| (closest_dist<0) && (dist>0)
		|| (closest_dist<0) && (dist<0) && (dist<closest_dist)){
		closest_dist = dist;
		entry = table[i];
	    }
	}
    }

    assert(entry.id != 0 );
    return;
}

int
LocTable::printTableNum()
{
    double now = Scheduler::instance().clock();
    int counter = 0;
    for (int i=0;i<size;i++) {
	if ((table[i].id == -1) || (now > table[i].timeout)) {
	}else{
	    counter++;
	}
    }
    return counter;
}