dllist.cc

linux的例子,就是下载后到自己的机子上去运行

#include "dllist.h"
#include "system.h"
#include "thread.h"

/*extern "C"{
#include <assert.h>
#define ASSERT(expression) assert(expression)
}*/
#ifndef NULL
#define NULL 0
#endif
DLLElement::DLLElement(void *itemptr,int sortkey){
	next=prev=NULL;
	key=sortkey;
	item=itemptr;
}

DLList::DLList(){
	lock = new Lock("dllist lock");
	listEmpty = new Condition("list empty cond");
	first=last=NULL;
}

DLList::~DLList(){
	int tmp;
	while(!IsEmpty())
	  (void) Remove(&tmp);
}

void
DLList::Prepend(void *item){
	lock->Acquire();
	DLLElement *element= new DLLElement(item,0);
	DLLElement *temp;
	temp=first;
	if(IsEmpty()){
		first=element;
		last=element;
	}
	else{
		first=element;
		element->key=temp->key-1;
		element->next=temp;
		temp->prev = element;
	}
//	listEmpty->Signal(lock);
	lock->Release();
}

void
DLList::Append(void *item){
	lock->Acquire();
	DLLElement *element= new DLLElement(item,0);
	if(IsEmpty()){
		first=element;
		last=element;
	}
	else{
		element->key=last->key+1;
		element->prev=last;
		last->next=element;
		element->next=NULL;
		last=element;
	}
//	listEmpty->Signal(lock);
	lock->Release();
}

void *
DLList::Remove(int *keyptr){
	lock->Acquire();
	DLLElement *element=first;
	if(IsEmpty()) 
	{
		*keyptr=0;
		lock->Release();
		return NULL;
	}
	element=first;
	*keyptr=element->key;
	if(first==last){
		first=NULL;
		last=NULL;
	}
	else{
		first=element->next;
	//	currentThread->Yield();
		first->prev=NULL;
	}
	lock->Release();
	return element->item;
}

bool
DLList::IsEmpty(){
	return (first==NULL);
}

void
DLList::SortedInsert(void *item,int sortkey){
	lock->Acquire();
	DLLElement *element= new DLLElement(NULL,0);
	DLLElement *temp=new DLLElement(NULL,0);
	element->key=sortkey;
	element->item=item;
	if(first==NULL) {
		first=element;
		last=element;
		element->prev=NULL;
	//	currentThread->Yield();
		element->next=NULL;
		lock->Release();
		return;	
	}
	temp=first;
	while(temp!=last&&element->key>=temp->key){
		temp=temp->next;
	}
	currentThread->Yield();
	if(element->key<temp->key){
		if(temp!=first) temp->prev->next=element;
		else first=element;
		element->next=temp;
	//	currentThread->Yield();
		element->prev=temp->prev;
		temp->prev=element;
	}
	else{
		temp->next=element;
		last=element;
		element->next=NULL;
		element->prev=temp;
	}
//	listEmpty->Signal(lock);
	lock->Release();
}

void *
DLList::SortedRemove(int sortkey){
	lock->Acquire();
	DLLElement *element= new DLLElement(NULL,0);
	element=first;
	while(element!=NULL&&element->key!=sortkey){
		element=element->next;
	}
	if(element!=NULL){
		element->prev->next=element->next;
		element->next->prev=element->prev;
	} 
	lock->Release();
	return element;
}		

void 
DLList::Print()
{
	lock->Acquire();
	DLLElement *e;
	e=first;
	printf("DLList: ");
	while(e!=NULL)
	{
		printf("%d->",e->key);
		e=e->next;
	}
	printf("NULL\n");
	lock->Release();
}