dllist.cc

nachos下体验Nachos下的并发程序设计

#include "dllist.h"
#include <iostream>
#include "system.h"
extern int testnum; 
DLLElement::DLLElement(void *itemPtr, int sortKey)
{
	  key = sortKey;
      next = NULL;
      prev = NULL;
      item = itemPtr;
      
}
DLList::DLList()
{
     first = NULL;
     last = NULL;
                
}

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

DLList::~DLList()
{    
     if (!IsEmpty())
     {
           while (first != last)
           {
                  DLLElement  *p = first;
                  first = first->next;
                  delete p; 
           }
           delete first;
     }
}


void DLList::Prepend(void *item)
{
     if (IsEmpty())
     {
          // if (testnum == 5) currentThread->Yield();
           DLLElement  *element = new DLLElement(item,50);
           last = first = element;
           
     }
     else
     {
         DLLElement *element = new DLLElement(item,(first->key - 1));
         element->next = first;
         first->prev = element;
         first = element;
     }
}

void DLList::Append(void *item)
{
     if (IsEmpty())
     {
		 DLLElement *element = new DLLElement(item,50);
         first = element;
         last = first;
     }
     else
     {
		 int key = last->key + 1;
		 DLLElement *element = new DLLElement(item,key);
         last->next = element;
         element->prev = last;
         last = element;
     }
}

void *DLList::Remove(int *keyPtr)
{
	//return SortedRemove(NULL);
    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->prev = 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
     {
         //DLLElement k(item,sortKey);
         if (first->key > sortKey)
         {
               element->next = first;
               first->prev = element;
               first = element;
         }
         else
         {
                DLLElement *head = first;
                while (head->next != NULL)
                {
					if (sortKey < head->next->key)
					{
						element->next = head->next;
						element->prev = head;
						head->next->prev = element;
						head->next = element;
						return;
					}
					else
					{
                        head = head->next;
					}
                }
                head->next = element;
                element->prev = head;
                last = last->next; 
		 }
     }    
}
	 

void *DLList::SortedRemove(int sortKey)
{
     if (IsEmpty()) return NULL;
     if (first->key == sortKey)
     {
	 void *thing = first->item;
         DLLElement *rm = first;
         first = first->next;
         first->prev = 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
         {
             //DLLElement *it = head1;
	     void *thing = head1->item;
             head2->next = head1->next;
             if (head1->next != NULL)
	     {
		 head1->next->prev = head2;
	     }
	     delete head1;
             return thing;
         }
     }
}