dllist.cc

nachos下的并发程序设计

#include "dllist.h"
#include <iostream>
#include "system.h"
extern int testnum; 

DLLElement::DLLElement(void *itemPtr, int sortKey)  //initialize a dllist
{
	  key = sortKey;       
      next = NULL;
      prior = NULL;  //dllist
      item = itemPtr;
      
}
DLList::DLList()   //initialize
{
     first = NULL;
     last = NULL;
                
}

bool DLList::IsEmpty()   //Returns TRUE if the list is empty
{
     if (first == NULL)
            return  true;

     else return  false;
}

DLList::~DLList()
{    
     if (!IsEmpty())
     {
           while (first != last)   //when the list is not empty ,delete the first element
           {
                  DLLElement  *p = first;
                  first = first->next;
                  delete p; 
           }
           delete first;
     }
}


void DLList::Prepend(void *item)  // Put item at the beginning of the list
{
     if (IsEmpty())
     {

           DLLElement  *element = new DLLElement(item,random(50));  //insert a random number between 0~50
           last = first = element;
           
     }
     else
     {
         DLLElement *element = new DLLElement(item,random(50));
         element->next = first;
         first->prior = element;
         first = element;
     }
}

void DLList::Append(void *item)   // Put item at the end of the list
{
     if (IsEmpty())
     {
		 DLLElement *element = new DLLElement(item,random(50));
         first = element;
         last = element;
     }
     else
     {
		 DLLElement *element = new DLLElement(item,random(50));
         last->next = element;
         element->prior = last;
         last = element;
     }
}

void *DLList::Remove(int *keyPtr)   // Take item off the front of the list
{
    if (IsEmpty())
     {
	     keyPtr = NULL;
         return NULL;
     }
     else
     {
         DLLElement *rm = first;

         if (testnum == 3)
			 currentThread->Yield();

	     void *thing = first->item;

         *keyPtr = first->key;

		 if (first == last)
		 {
			 last = first = NULL; 
		 }
		 else
		 {   
             first = first->next;
             first->prior = NULL;
		 }  

		 delete rm;

         if (testnum == 3)
			 currentThread->Yield();
         return thing;
		 
     }
}

void DLList::SortedInsert(void *item, int sortKey)
{
	 DLLElement *element = new DLLElement(item,sortKey);

     if (IsEmpty())
     {
        if (testnum == 4) 
			currentThread->Yield();

         last = first = element;

        if (testnum == 4)  
			currentThread->Yield();         
     }
     else
     {
         if (first->key > sortKey)    //the smallest num ,insert in the front
         {
               element->next = first;
               first->prior = element;
               first = element;
         }
         else
         {
                DLLElement *head = first;
                while (head->next != NULL)
                {
					if (sortKey < head->next->key)
					{
						element->next = head->next;
						element->prior = head;
						head->next->prior = element;
						head->next = element;
						return;
					}
					else
					{
                        head = head->next;
					}
                }

                head->next = element;
                element->prior = head;
                last = element; 
		 }
     }    
}
	 

void *DLList::SortedRemove(int sortKey)
{
     if (IsEmpty()) 
		 return NULL;

     if (first->key == sortKey)
     {
	    void *thing = first->item;
         DLLElement *rm = first;
         first = first->next;
         first->prior = NULL;
         delete rm;
         return thing;            
     } 
     else
     {
         DLLElement *head1 = first;
         DLLElement *head2 = first;

         while ((head1->key != sortKey) && (head1 != NULL))
         {
               head1 = head1->next;
               head2 = head1;
         }

         if (head1 == NULL)
         {
               return NULL;
         }
         else
         {
          
	         void *thing = head1->item;
             head2->next = head1->next;

             if (head1->next != NULL)
		           head1->next->prior = head2;

	         delete head1;
             return thing;
         }
     }
}