dllist.cc

本次实验的目的在于将nachos中的锁机制和条件变量的实现补充完整

#include "dllist.h"
#include <iostream.h>
#include <system.h>
#include "synch-sleep.h"
Lock *sleep_lock = new Lock("sleep_lock");
Condition *sleep_condition = new Condition("sleep_condition");

DLLElement::DLLElement(int node_key)
{
    key=node_key;
    prev=next=NULL;
}

DLList::DLList()
{
    first = NULL;
    last = NULL;
    first = last;
}

DLList::~DLList()
{
    DLLElement *be_del;
    if(!IsEmpty()) return;
    for(;first;)
    {
        be_del = first;
        first = first->next;
        delete be_del;
    }
}

void DLList::Prepend(DLLElement *item)
{
    DLLElement *temp;
    if(IsEmpty())
    {
        first=last = item;
        item->next=NULL;
        item->prev=NULL;
    }
    else
    {
        item->next=first;
        item->prev=NULL;
        first->prev=item;
        first=item;
    }
    int  min_key = first->next->key;
    for(temp = first->next;temp;temp= temp->next)
        if(temp->key<min_key)
            min_key= temp->key;
    item->key=min_key-1;
}

void DLList::Append(DLLElement *item)
{
    DLLElement *temp;   
    if(IsEmpty())
    {
        first=last = item;
        item->next=NULL;
        item->prev=NULL;
        return;
    }
    else
    {
        item->prev=last;
        item->next=NULL;
        last->next=item;
        last=item;        
    }
    int  max_key = first->key;
    for(temp = first;temp!=last && temp;temp= temp->next)
        if(temp->key>max_key)
             max_key= temp->key;
    item->key=max_key+1;
}

DLLElement  *DLList::Remove()
{
    DLLElement *keyPtr;
    if(IsEmpty())
    {
        return NULL;
    } 
    else if(first != NULL && last!=NULL&& first==last)
    {
        keyPtr = first;
        first = last = NULL;
        return keyPtr;
    }
    else
    {
        keyPtr = first;
        first->next->prev = NULL;

               // currentThread->Yield();

        first = first->next;
        return  keyPtr;
    }
}

void DLList::SortedInsert(DLLElement *item,int key)
{
    DLLElement *p;
    if(IsEmpty() )
    {
        first = last =item;
        first->prev = last->next = NULL;
    }
    else if(first->key >= key)
    {
        first->prev = item;
        item->next = first;

      currentThread->Yield();

        first = item;
        first->prev = NULL;
    }
    else if(last->key < key)
    {
        last->next = item;
        item->prev = last;

        currentThread->Yield();

        last = item;
        last->next = NULL;
    }
    else
    {
        for(p=first->next; p!=NULL; p=p->next)
        {
            if(p->key >= key)
            {
                item->prev = p->prev;
                item->next = p;

               currentThread->Yield();

                p->prev->next = item;
                p->prev = item;
                break;
            }
        }
    }
}

void DLList::SortedInsert_new(DLLElement *item,int key)
{
    DLLElement *p;

         sleep_lock->Acquire();

    if(IsEmpty() )
    {
        first = last =item;
        first->prev = last->next = NULL;

           sleep_condition->Signal(sleep_lock);

    }
    else if(first->key >= key)
    {
        first->prev = item;
        item->next = first;

      currentThread->Yield();

        first = item;
        first->prev = NULL;
    }
    else if(last->key < key)
    {
        last->next = item;
        item->prev = last;

        currentThread->Yield();

        last = item;
        last->next = NULL;
    }
    else
    {
        for(p=first->next; p!=NULL; p=p->next)
        {
            if(p->key >= key)
            {
                item->prev = p->prev;
                item->next = p;

               currentThread->Yield();

                p->prev->next = item;
                p->prev = item;
                break;
            }
        }
    }

      sleep_lock->Release();

}



DLLElement *DLList::SortedRemove(int sortkey)
{
    DLLElement *p;
    if(IsEmpty() )  return NULL;
    else if(first == last)
    {
        p = first;
        first = last = NULL;
        return p;
    }
    else if(first->key == sortkey)
    {
        p = first;

        // currentThread->Yield();

        first->next->prev = NULL;

       currentThread->Yield();

        first = first->next;
        return p;
    }
    else if(last->key == sortkey)
    {
        p = last;

       // currentThread->Yield();

        last->prev->next = last;

       currentThread->Yield();

        last = last->prev;
        return p;
    }
    else
    {
        for(p=first->next; p->next != NULL ;p=p->next)
        {
            if(p->key == sortkey)
            {
                p->prev->next = p->next;

               currentThread->Yield();

                p->next->prev = p->prev;
                return p;
            }
        }
    }
    return NULL;
}

DLLElement *DLList::SortedRemove_new(int sortkey)
{
    DLLElement *p;

          sleep_lock->Acquire();

    if(IsEmpty() )  return NULL;
    else if(first == last)
    {
        p = first;
        first = last = NULL;
            sleep_lock->Release();
        return p;
    }
    else if(first->key == sortkey)
    {
        p = first;

        // currentThread->Yield();

        first->next->prev = NULL;

        currentThread->Yield();

        first = first->next;

            sleep_lock->Release();
        return p;
    }
    else if(last->key == sortkey)
    {
        p = last;

       // currentThread->Yield();

        last->prev->next = last;

       currentThread->Yield();

        last = last->prev;

            sleep_lock->Release();
        return p;
    }
    else
    {
        for(p=first->next; p->next != NULL ;p=p->next)
        {
            if(p->key == sortkey)
            {
                p->prev->next = p->next;

               currentThread->Yield();

                p->next->prev = p->prev;

                    sleep_lock->Release();
                return p;
            }
        }
    }

     sleep_lock->Release();

    return NULL;
}


void DLList::showlist()
{
     DLLElement *p;
     for(p=first;p;p=p->next)
         cout<<p->key<<"  " ;
     cout<<endl;
}


bool DLList::IsEmpty(void)
{
    if(first==NULL && last==NULL)
        return TRUE;
    else 
        return FALSE;
}