wfq-list.h

区分服务的路由算法

/*
 * Copyright (c) 1999-2000 Paolo Losi
 * All rights reserved.
 *
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 */
#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) {printf("Error in List"); exit(1);} //debug 
					delete head;
					head=0;
					tail=0;
				}
				return 0;
			}
			return 1;
		};
				
};
		

#endif