dllist.cc

nachos系统作业 实现线程系统 实现一个电梯模拟 附实验报告

#include "dllist.h"
#include "system.h"
#include "synch-sleep.h"
#include "synch-sem.h"
LockSem *lock = new LockSem("dllist lock");
ConditionSem *listEmpty = new ConditionSem("list empty cond");
//Lock *lock = new Lock("dllist lock");
//Condition *listEmpty = new Condition("list empty cond");

int min_key=10;
int max_key=10;
//------------------------------------------
DLLElement::DLLElement(void *itemPtr, int sortKey)
{
     item = itemPtr;
     key = sortKey;
     next = NULL;
	 prev = NULL;// assume we'll put it at the end of the list 
}


//---------------------------------------------------------
DLList::DLList()//	Initialize a list, empty to start with.
{ 
    first = last = NULL; 
}

//---------------------------------------------------------
DLList::~DLList()
{ 
    while (Remove(NULL) != NULL)
	;	 // delete all the list elements
}


//-----------------------------------------------------------

void
DLList::Prepend(void *item)
{
    lock->Acquire();
    DLLElement *element = new DLLElement(item, 0);
    element->key=min_key--;
    if (IsEmpty()) {		// list is empty
	 first = element;
	 last = element;
    } else {			// else put it before first
	 element->next = first;
	 first->prev = element;
	 first = element;
          }
    //printf("the %d is preadd\n",element->key);
    lock->Release();
}

//----------------------------------------------------------
void
DLList::Append(void *item)
{
    lock->Acquire();
    DLLElement *element = new DLLElement(item, 0);
    element->key=max_key++;
    if (IsEmpty()) {		// list is empty
	 first = element;
	 last = element;
    } else {			// else put it after last
	 last->next = element;
	 element->prev = last;
	 last = element;
          }
    // printf("the %d is appadd\n",element->key);
    lock->Release();

}

//-----------------------------------------------------------

void *
DLList::Remove(int *keyPtr)
{   
    lock->Acquire();
    DLLElement *element = first;
    void *thing;

    if (IsEmpty()){
    lock->Release();
	 return NULL;}

    thing = first->item;
    if (first == last) {	// list had one item, now has none
        first = NULL;
	     last = NULL;currentThread->Yield();
    } else {
        first = element->next; 
		  first->prev = NULL;
         }
    if (keyPtr != NULL)
        {* keyPtr = element->key;}

    delete element;
    lock->Release();
    return thing;
    
}

//--------------------------------------------------------------
bool
DLList::IsEmpty()
{
    if (first == NULL)
        return TRUE;
    else
	return FALSE;
}
//-----------------------------------------------------------------
void
DLList::SortedInsert(void *item, int sortKey)
{   
    lock->Acquire();
    DLLElement *element = new DLLElement(item, sortKey);
    DLLElement *ptr;		// keep track
    
    if (IsEmpty()) {	// if list is empty, put
        first = element;currentThread->Yield();
        last = element;
          } 
    else if (sortKey < first->key) {	// item goes on front of list
	     element->next = first;  
	     first->prev = element;
	     first = element;
    } else {		// look for first elt in list bigger than item
          for (ptr = first; ptr->next != NULL; ptr = ptr->next) {
             if (sortKey < ptr->next->key) {
	                 	element->next = ptr->next;
		               ptr->next->prev = element;
		               element->prev = ptr;
	                  ptr->next = element;
                     lock->Release();
		               return;
	                           }
	                 }
	    last->next = element;	
	    element->prev = last;// item goes at end of list
	    last = element;
             }
   lock->Release();
}
//--------------------------------------------------------------
void *
DLList::SortedRemove(int sortKey)
{
    lock->Acquire();
    DLLElement *element = first;
    void *thing;
     
    if (IsEmpty()){lock->Release();
	 return NULL;}

    if (sortKey < first->key){lock->Release();return NULL;}
      else {
         for (element = first; element != NULL; element = element->next) {
            if (sortKey == element->key) {
                thing = element->item;
                            if(element == first){ 
                                      first = element->next;
		                                if(first)first->prev = NULL;else last=NULL;currentThread->Yield();
                                      delete element;lock->Release();
                                      return thing;}
                            if(element == last){
                                      last = element->prev;
		                                if(last)last->next = NULL;else first=NULL;
                                      delete element;lock->Release();
                                      return thing;}
				       
                 element->prev->next = element->next;
                 element->next->prev = element->prev;
                 currentThread->Yield();
                 delete element;lock->Release();
				     return thing;
			     }
		    }
	     }
     lock->Release();
     return NULL;
}




//------------------------------------------
void
DLList::ReadFront()
{DLLElement *element = first;printf("f");
        while(element!=NULL){
                     printf("--%d",element->key);
                     element=element->next;}
printf("\n");
}
//------------------------------------------
void
DLList::ReadBack()
{
  DLLElement *element = last;printf("l");
        while(element!=NULL){
                     printf("--%d",element->key);
                     element=element->prev;}
printf("\n");
}