wfq-list.h

c＋＋编写的ns环境下关于wfq算法的仿真源代码

/*
 * Copyright (c) 1999-2000 Paolo Losi ([e-mail])
 *
 * Copyright (c) 2001-2004 Paolo Losi ([e-mail])
 *                         Alexander Sayenko ([e-mail])
 *
 * All rights reserved
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 */


#ifndef LIST_H
#define LIST_H

// *** List class implements a double linked list ordered by key
//
// - get_key_min() and get_data_min() return the key and the data of the
//   smallest key element without extracting it from the list
//
// - extract()  extracts from the list the smallest key element
//
// - insert_order() interface uses flowid knowledge to allow to implement 
//   other data structures:  Calendar Queues, array of Lists (a list per flow) 

template <class X> struct elem {
	double key;
	X data;
	elem *next;
	elem *prev;

	elem(double k=0,X d=0,elem *n=0,elem *p=0) : key(k),data(d),next(n),prev(p) {};
};


template <class X> class List {
	protected:
		elem<X> *head,*tail; 
		
	public:
		List(): head(0), tail(0) {};
		
		void insert_order(X el,double k,int flowID) {
			elem<X> *tmp=new elem<X>(k,el);
			
			if(head==0 && tail==0) { //  list is empty 
				tail = head = tmp;
			} else if (k >= tail->key ) { // insert as first
					tmp->next=tail;
					tail->prev=tmp;
					tail = tmp;
			} else {
				elem<X> *p=tail; // other cases
				while((p->next)!=0) {
					if( (p->next)->key <= k ) break;
					p=p->next;
				}
				if(p->next != 0) {
					p->next->prev = tmp;
					tmp->next = p->next;
				} else 
					// it is the head element 
					head=tmp;
				p->next=tmp;
				tmp->prev=p;
			}
		};

		double get_key_min() {
			if(head !=0)
				return head->key;
			else 
				return -1; // keys cannot be negative  
		};

		X get_data_min() {
			if(head != 0)
				return head->data;
			else
				return 0;
		};
		
		int extract() {
			if(head != 0) {
				if(head->prev != 0) {
					elem<X> *new_head=head->prev;
					new_head->next=0;
					delete head;
					head=new_head;
				} else {
					// sanity check
					//if(head!=tail) exit(1); //debug 
					delete head;
					head=0;
					tail=0;
				}
				return 0;
			}
			return 1;
		};
				
};
		

#endif