nhlist.cc

在NS-2环境中实现了移动Ad Hoc的两种广播算法:Flood和Bcast。里面本来有个test目录

/*******************************************************************
 Copyright (C) 2004 Thomas Kunz, CRC Canada, BCAST for IPv4.
 DISTRIBUTED WITH NO WARRANTY, EXPRESS OR IMPLIED.
 See the GNU Library General Public License (file COPYING in the
 MANET_multicast directory) for conditions of use and redistribution.
*********************************************************************/

#include <assert.h>

#include "MANET_multicast/nhlist.h"

/* ======================================================================
   Next Hop List used by MAODV Mcast Table.
   ===================================================================== */
nh_entry::nh_entry()
{
	next_hop = -1;
	enabled_flag = NH_DISABLE;
	link_direction = DOWNSTREAM;
	next_ = 0;
}

nhlist::nhlist()
{
	head_ = tail_ = 0;
	len_ = 0;
}

nhlist::~nhlist()
{
	nh_entry *p = remove_head();
	while (p){
		delete p;
		p = remove_head();
	}
}

void 
nhlist::add(nh_entry *p)
{
	if(head_ == 0) {head_ = tail_ = p;}
	else {
		tail_->next_ = p;
		tail_ = p;
	}
	len_++;
#ifdef DEBUG
	verifyList();
#endif
}
                

nh_entry* nhlist::deque()
{
	nh_entry *p;

	p = remove_head();
#ifdef DEBUG
	verifyList();
#endif
	return p;
}
	

nh_entry* nhlist::deque(nsaddr_t dst)
{
	nh_entry *p, *prev;

	findNextHopWithDst(dst, p, prev);
	assert(p == 0 || (p == head_ && prev == 0) || (prev->next_ == p));

	if(p == 0) return 0;

	if (p == head_) {
		p = remove_head();
	}
	else if (p == tail_) {
		prev->next_ = 0;
		tail_ = prev;
		len_--;
	}
	else {
		prev->next_ = p->next_;
		len_--;
	}

#ifdef DEBUG
	verifyList();
#endif
	return p;
}

nh_entry* nhlist::find(nsaddr_t dst)
{
	nh_entry *p, *prev;  
	findNextHopWithDst(dst, p, prev);
	if (0 == p) return 0;
	else return p;
}

nh_entry* nhlist::top()
{
	return head_;
}

nh_entry* nhlist::next(nsaddr_t dst)
{
	nh_entry *p, *prev;
	findNextHopWithDst(dst, p, prev);

	if (p == 0) return 0;
	else if (p->next_ == 0) return 0;
	else return p->next_;
}

int nhlist::size(){
	int count = 0;
	nh_entry *p = head_;
	for(;p;p=p->next_){
		if (p->enabled_flag == NH_ENABLE) count++;
	}

	return count;
}

int nhlist::extrasize(){
	int count =0;
	nh_entry *p = head_;
	for (;p;p=p->next_){
		if (p->enabled_flag != NH_DISABLE) count++;
	}
	return count;
}

nh_entry * nhlist::hopexcept(nsaddr_t dst)
{
	nh_entry *p = head_;
	for (;p;p=p->next_){
		if (p->enabled_flag == NH_ENABLE && p->next_hop != dst) {
			break;
		}
	}
	return p;
}


void nhlist::disable(){
	nh_entry *p = head_;
	for(;p;p=p->next_){
		if (p->enabled_flag != NH_DISABLE) {p->enabled_flag = NH_DISABLE; p->link_direction = DOWNSTREAM;}
	}
}



nh_entry*  nhlist::findupstream(){
	nh_entry *p = head_;
	for(;p;p=p->next_){
		if (p->link_direction == UPSTREAM){ break;}
	}

	return p;
}

nh_entry* nhlist::findenabledupstream(){
	nh_entry *p = head_;
	for(;p;p=p->next_){
		if (p->link_direction == UPSTREAM && p->enabled_flag == NH_ENABLE) break;
	}
	
	return p;
}

nh_entry* nhlist::firsthop(){
	nh_entry *p = head_;
	for(;p;p=p->next_){
		if (p->enabled_flag == NH_ENABLE) { break;}
	}
	
	return p;
}
/* ======================================================================
   Private Routines
   ====================================================================== */
nh_entry* nhlist::remove_head()

{
	nh_entry *p = head_;
        
	if(head_ == tail_) head_ = tail_ = 0;
  else head_ = head_->next_;

	if(p) len_--;

	return p;
}


void nhlist::findNextHopWithDst(nsaddr_t dst, nh_entry*& p, nh_entry*& prev)
{
	p = prev = 0;

	for(p = head_; p; p = p->next_) {
		if(p->next_hop == dst) return;
		prev = p;
	}

	if(p == 0) prev = 0;	// not found
}


void nhlist::verifyList()
{
	nh_entry *p, *prev = 0;
	int cnt = 0;

	for(p = head_; p; p = p->next_) {
		cnt++;
		prev = p;
	}

	assert(cnt == len_);
	assert(prev == tail_);
}