landmark.cc

柯老师网站上找到的

// Author: Satish Kumar, [e-mail]

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

#include "landmark.h"
#include <random.h>
#include <cmu-trace.h>
#include <address.h>

static int lm_index = 0;


void
LMNode::copy_tag_list(compr_taglist *taglist)
{
  compr_taglist *tags = NULL;
  compr_taglist *tag_ptr1, *tag_ptr2;

  // Delete the old tag list if it exists
  if(tag_list_) {
    tag_ptr1 = tag_list_;
    while(tag_ptr1) {
      tag_ptr2 = tag_ptr1;
      tag_ptr1 = tag_ptr1->next_;
      delete tag_ptr2;
    }
    tag_list_ = NULL;
  }

  // Copy the specified taglist
  tag_ptr1 = taglist;
  while(tag_ptr1) {
    if(!tag_list_) {
      tag_list_ = new compr_taglist;
      tag_ptr2 = tag_list_;
    }
    else {
      tag_ptr2->next_ = new compr_taglist;
      tag_ptr2 = tag_ptr2->next_;
    }
    tag_ptr2->obj_name_ = tag_ptr1->obj_name_;
    tag_ptr1 = tag_ptr1->next_;
  }
}





// Returns a random number between 0 and max
inline double 
LandmarkAgent::jitter(double max, int be_random_)
{
  return (be_random_ ? Random::uniform(max) : 0);
}



// Returns a random number between 0 and max
inline double 
LandmarkAgent::random_timer(double max, int be_random_)
{
  return (be_random_ ? rn_->uniform(max) : 0);
}



void
LandmarkAgent::stop()
{
  ParentChildrenList *pcl = parent_children_list_, *tmp_pcl;

  trace("Node %d: LM Agent going down at time %f",myaddr_,NOW);

  // Cancel any running timers and reset relevant variables
  if(promo_timer_running_) {
    promo_timer_running_ = 0;
    promo_timer_->cancel();
  }
  num_resched_ = 0;
  wait_state_ = 0;
  total_wait_time_ = 0;

  // Reset highest level of node
  highest_level_ = 0;

  // Delete ParentChildrenList objects for all levels
  while(pcl) {
    tmp_pcl = pcl;
    pcl = pcl->next_;
    delete tmp_pcl;
  }
  parent_children_list_ = NULL;

  // Indicate that node is dead so that packets will not be processed
  node_dead_ = 1;

  global_lm_id_ = NO_GLOBAL_LM;
  global_lm_level_ = -1;

  // Event id > 0 for scheduled event
  if(tag_advt_event_->uid_ > 0) {
    Scheduler &s = Scheduler::instance();
    s.cancel(tag_advt_event_);
  }
}





void LandmarkAgent::
trace (char *fmt,...)
{
  va_list ap; // Define a variable ap that will refer to each argument in turn

  if (!tracetarget_)
    return;

  // Initializes ap to first argument
  va_start (ap, fmt); 
  // Prints the elements in turn
  vsprintf (tracetarget_->buffer (), fmt, ap); 
  tracetarget_->dump ();
  // Does the necessary clean-up before returning
  va_end (ap); 
}



static class LandmarkClass:public TclClass
{
  public:
  LandmarkClass ():TclClass ("Agent/landmark")
  {
  }
  TclObject *create (int, const char *const *)
  {
    return (new LandmarkAgent ());
  }
} class_landmark;




LandmarkAgent::LandmarkAgent (): Agent(PT_MESSAGE), promo_start_time_(0), promo_timeout_(50), promo_timeout_decr_(1), promo_timer_running_(0), seqno_(0), highest_level_(0), parent_children_list_(NULL), ll_queue(0), be_random_(1), wait_state_(0), total_wait_time_(0), debug_(1) ,qry_debug_(0)
 {

  promo_timer_ = new PromotionTimer(this);

  //  bind_time ("promo_timeout_", "&promo_timeout_");
  num_resched_ = 0;
  tag_dbase_ = NULL;
  node_ = NULL;

  cache_ = 0; // default is to disable caching
  tag_cache_ = new TagCache[MAX_CACHE_ITEMS];
  num_cached_items_ = 0;

  recent_demotion_msgs_ = new RecentMsgRecord[MAX_DEMOTION_RECORDS];
  num_demotion_msgs_ = 0;

  // default value for the update period
  update_period_ = 400;
  update_timeout_ = update_period_ + 4 * LM_STARTUP_JITTER;

  adverts_type_ = FLOOD;  // default is to flood adverts
  global_lm_ = 0; // No global LMs by default
  global_lm_id_ = NO_GLOBAL_LM;
  global_lm_level_ = -1;

  // myaddr_ not defined at this point ... So use lm_index for init
  rn_ = new RNG(RNG::RAW_SEED_SOURCE,lm_index++);;
  // Throw away a bunch of initial values
  for(int i = 0; i < 128; ++i) {
    rn_->uniform(200);
  }

  node_dead_ = 0;

  bind ("be_random_", &be_random_);
  //  bind ("myaddr_", &myaddr_);
  bind ("debug_", &debug_);

  num_nbrs_ = 0;
  nbrs_ = NULL;

  tag_mobility_ = new TagMobilityHandler(this);
  tag_mobility_event_ = new Event;

  // myaddr_ not defined at this point ... So use lm_index for init
  tag_rng_ = new RNG(RNG::RAW_SEED_SOURCE,lm_index++);;
  // Throw away a bunch of initial values
  for(int i = 0; i < 128; ++i) {
    tag_rng_->uniform(200);
  }

  mobility_period_ = 60;
  mobile_tags_ = NULL;

  tag_advt_handler_ = new TagAdvtHandler(this);
  tag_advt_event_ = new Event;
}




int
LandmarkAgent::CheckDemotionMsg(nsaddr_t id, int level, int origin_time)
{
  int i = 0;

  // If object already exists in cache, update info if necessary
  for(i = 0; i < num_demotion_msgs_; ++i) {
    if(recent_demotion_msgs_[i].id_ == id && recent_demotion_msgs_[i].level_ == level) {
      if(recent_demotion_msgs_[i].origin_time_ >= origin_time) {
        return(OLD_MESSAGE);
      }
      else {
        recent_demotion_msgs_[i].origin_time_ = origin_time;
        return(NEW_ENTRY);
      }
    }
  }

  if(num_demotion_msgs_ < MAX_DEMOTION_RECORDS) {
    i = num_demotion_msgs_;
    ++num_demotion_msgs_;
    recent_demotion_msgs_[i].id_ = id;
    recent_demotion_msgs_[i].level_ = level;
    recent_demotion_msgs_[i].origin_time_ = origin_time;
  }
  else {
    // Use LRU cache replacement
    int replace_index = 0;
    int least_time = recent_demotion_msgs_[replace_index].origin_time_;
    for(i = 0; i < MAX_DEMOTION_RECORDS; ++i) {
      if(recent_demotion_msgs_[i].origin_time_ < least_time)
        replace_index = i;
    }
    recent_demotion_msgs_[replace_index].id_ = id;
    recent_demotion_msgs_[replace_index].level_ = level;
    recent_demotion_msgs_[replace_index].origin_time_ = origin_time;
  }
  return(NEW_ENTRY);
}




void
ParentChildrenList::UpdateChildLMAddr(nsaddr_t id, int num_lm_addrs, int64_t *lm_addrs)
{
  LMNode *potl_ch = NULL;

  potl_ch = pchildren_;
  while(potl_ch) {
    if(potl_ch->id_ == id)
      break;
    potl_ch = potl_ch->next_;
  }

  assert(potl_ch);
  (potl_ch->lmaddr_)->delete_lm_addrs();
  for(int i = 0; i < num_lm_addrs; ++i)
    (potl_ch->lmaddr_)->add_lm_addr(lm_addrs[i]);
}




int
ParentChildrenList::UpdatePotlParent(nsaddr_t id, nsaddr_t next_hop, int num_hops, int level, int num_children, int energy, int origin_time, int delete_flag)
{
  LMNode *potl_parent, *list_ptr;
  double now = Scheduler::instance().clock();
  // Extract seqnum and origin time
  int seqnum = origin_time & 0xFFFF;
  origin_time = origin_time >> 16;
  
  assert(num_pparent_ >= 0);

  // cannot delete from an empty list!
  if(delete_flag && !pparent_)
    return(ENTRY_NOT_FOUND);

  //  if((a_->debug_) && (a_->myaddr_ == 24)) {
  //    a_->trace("Node %d: Updating Potl Parent level %d, id %d, delete_flag %d, time %f",a_->myaddr_,level_,id,delete_flag,now);
  //  }

  if(pparent_ == NULL) {
    pparent_ = new LMNode(id, next_hop, num_hops, level, num_children, energy, origin_time, now);
    pparent_->last_upd_seqnum_ = seqnum;
    parent_ = pparent_;
    ++num_pparent_;
    return(NEW_ENTRY);
  }
  
  list_ptr = pparent_;
  potl_parent = list_ptr;
  while(list_ptr != NULL) {
    if(list_ptr->id_ == id) {
      // Check if this is a old message floating around in the network
      if(list_ptr->last_upd_origin_time_ > origin_time || (list_ptr->last_upd_origin_time_ == origin_time && list_ptr->last_upd_seqnum_ >= seqnum)) {
	// Check if we got the old update on a shorter path
	if(list_ptr->num_hops_ > num_hops) {
	  list_ptr->next_hop_ = next_hop;
	  list_ptr->num_hops_ = num_hops;
	  return(OLD_ENTRY);
	}
	return(OLD_MESSAGE); 
      }
      if(!delete_flag) {
	// Make this node as parent if it's closer than current parent
	if(parent_->num_hops_ > num_hops + 10 || num_hops == 0) {
	  parent_ = list_ptr;
	}
	list_ptr->next_hop_ = next_hop;
	list_ptr->num_hops_ = num_hops;
	list_ptr->level_ = level;
	list_ptr->num_children_ = num_children;
	list_ptr->energy_ = energy;
	list_ptr->last_upd_origin_time_ = origin_time;
	list_ptr->last_upd_seqnum_ = seqnum;
	list_ptr->last_update_rcvd_ = Scheduler::instance().clock();
      }
      else { // delete the entry
	if(num_pparent_)
	  --(num_pparent_);

	if(pparent_ == list_ptr)
	  pparent_ = list_ptr->next_;
	else
	  potl_parent->next_ = list_ptr->next_;

	if(parent_->id_ == list_ptr->id_)
	  assert(parent_ == list_ptr);

	// No parent if potl parent list is empty
	if(pparent_ == NULL) {
	  parent_ = NULL;
	}
	else if(parent_ == list_ptr) {
	// Select new parent if current parent is deleted and
	// potl parent is not empty; closest potl parent is new parent
	  LMNode *tmp = pparent_;
	  int best_num_hops = pparent_->num_hops_;
	  LMNode *best_parent = pparent_;
	  while(tmp != NULL) {
	    if(tmp->num_hops_ < best_num_hops) {
	      best_num_hops = tmp->num_hops_;
	      best_parent = tmp;
	    }
	    tmp = tmp->next_;
	  }
	  parent_ = best_parent;
	}
	delete list_ptr;
      }
      return(OLD_ENTRY);
    }
    potl_parent = list_ptr;
    list_ptr = list_ptr->next_;
  }

  if(delete_flag)
    return(ENTRY_NOT_FOUND);

  potl_parent->next_ = new LMNode(id, next_hop, num_hops, level, num_children, energy, origin_time, now);
  (potl_parent->next_)->last_upd_seqnum_ = seqnum;
  ++num_pparent_;
  // Make this node as parent if it's closer than current parent
  if(parent_->num_hops_ > num_hops) {
    parent_ = potl_parent->next_;
  }
  return(NEW_ENTRY);
}




int
ParentChildrenList::UpdatePotlChild(nsaddr_t id, nsaddr_t next_hop, int num_hops, int level, int num_children, int energy, int origin_time, int child_flag, int delete_flag, compr_taglist *taglist)
{
  LMNode *potl_child, *list_ptr;
  double now = Scheduler::instance().clock();
  int new_child = 0;
  int tags_changed = 0;
  int seqnum = origin_time & 0xFFFF;
  origin_time = origin_time >> 16;

  //  if(a_->debug_) printf("Node %d: Number of potl children %d",a_->myaddr_,num_potl_children_);

  // cannot delete from an empty list!
  if(delete_flag && !pchildren_) {
    return(ENTRY_NOT_FOUND);
  }

  assert(num_potl_children_ >= 0);
  assert(num_children_ >= 0);

  if(pchildren_ == NULL) {
    pchildren_ = new LMNode(id, next_hop, num_hops, level, num_children, energy, origin_time, now);
    pchildren_->child_flag_ = child_flag;