parsetreelist.c

編譯器的虛擬yacc工具

/***********************************************************************
 
 What This Is:      Implementation of ParseTreeHdl List ADT
 Author:            Laura Deddens
 Email:             [e-mail]
 Last Modified:     5 September 1996
 
***********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <parseTree.h>
#include <parseTreeList.h>

typedef struct ListNodeStruct * ListNodePtr;
typedef struct ListNodeStruct
{
   ParseTreeHdl data;
   ListNodePtr next,
               prev;
} ListNodeStruct;

typedef struct ParseTreeListStruct
{
   int         length;
   ListNodePtr first,
               last,
               flagged;
                  /* when the abstract flag is unassociated this
                   * field will be NULL, otherwise it points to
                   * the ListNodeStruct that holds the ParseTreeHdl
                   * which the flag is associated with
                   */
} ParseTreeListStruct;


/*----------Functions local to this ADT----------*/
void CreateListNode(ListNodePtr * theNode, ParseTreeHdl theData);
void DestroyListNode(ListNodePtr * theNode);


/*----------Creation and deletion procedures----------*/
void CreateParseTreeList(ParseTreeListHdl * theList)
{
   assert (*theList == NULL);

   *theList = (ParseTreeListHdl)malloc(sizeof(ParseTreeListStruct));
   (*theList)->length = 0;	
   (*theList)->first = NULL;
   (*theList)->last = NULL;
   (*theList)->flagged = NULL;

}

void DestroyParseTreeList(ParseTreeListHdl * theList)
{
   assert(*theList != NULL);

   while(!IsEmpty(*theList))
      {
      DeleteFirst(*theList);
      }
   free(*theList);
   *theList = NULL;
}


/*----------Query functions----------*/
int IsEmpty(ParseTreeListHdl theList)
{
   assert(theList != NULL);

   return(!(theList->first));
      /*We know the list is empty if first is NULL*/
}

int AtFirst(ParseTreeListHdl theList)
{
   assert(theList != NULL);
   assert(!IsEmpty(theList));
      /*AtFirst is meaningless if there is no first*/

   return(theList->first == theList->flagged);
}

int AtLast(ParseTreeListHdl theList)
{
   assert(theList != NULL);
   assert(!IsEmpty(theList));
      /*AtLast is meaningless if there is no last*/

   return(theList->last == theList->flagged);
}

int ExistsFlagged(ParseTreeListHdl theList)
{
   assert(theList != NULL);

   return(theList->flagged != NULL);
}

ParseTreeHdl FlaggedParseTreeHdl(ParseTreeListHdl theList)
{
   assert(theList != NULL);
   assert(ExistsFlagged(theList));

   return(theList->flagged->data);
}

int NumberOfElements(ParseTreeListHdl theList)
{
   assert(theList != NULL);

   return(theList->length);
}


/*----------Manipulation procedures----------*/
void MoveFirst(ParseTreeListHdl theList)
{
   assert(theList != NULL);
   assert(!IsEmpty(theList));

   theList->flagged = theList->first;
}

void MoveLast(ParseTreeListHdl theList)
{
   assert(theList != NULL);
   assert(!IsEmpty(theList));
   
   theList->flagged = theList->last;
}

void MovePrev(ParseTreeListHdl theList)
{
   assert(theList != NULL);
   assert(!IsEmpty(theList));
   assert(ExistsFlagged(theList));

   theList->flagged = theList->flagged->prev;
}

void MoveNext(ParseTreeListHdl theList)
{
   assert(theList != NULL);
   assert(!IsEmpty(theList));
   assert(ExistsFlagged(theList));
   
   theList->flagged = theList->flagged->next;
}

void AddFirst(ParseTreeListHdl theList, ParseTreeHdl theData)
{
   ListNodePtr new = NULL;

   assert(theList != NULL);

   CreateListNode(&new, theData);
   if (IsEmpty(theList))
      {
      theList->last = new;
      }
   else
      {
      theList->first->prev = new;
      new->next = theList->first;
      }
   theList->first = new;
   theList->length++;
}

void AddLast(ParseTreeListHdl theList, ParseTreeHdl theData)
{
   ListNodePtr new = NULL;

   assert(theList != NULL);
   
   CreateListNode(&new, theData);
   if (IsEmpty(theList))
      {
      theList->first = new;
      }
   else
      {
      theList->last->next = new;
      new->prev = theList->last;
      }
   theList->last = new;
   theList->length++;
}

void AddAfterFlagged(ParseTreeListHdl theList, ParseTreeHdl theData)
{
   ListNodePtr new = NULL;

   assert(theList != NULL);
   assert(ExistsFlagged(theList));

   if (AtLast(theList))
      {
      AddLast(theList, theData);
      }
   else
      {
      CreateListNode(&new, theData);
      new->prev = theList->flagged;
      new->next = theList->flagged->next;
      theList->flagged->next->prev = new;
      theList->flagged->next = new;
      theList->length++;
      }
}

void DeleteFirst(ParseTreeListHdl theList)
{
   assert(theList != NULL);
   assert(!IsEmpty(theList));

   if(AtFirst(theList))
      {
      theList->flagged = NULL;
      }

   if(theList->first == theList->last)
      {
      theList->last = NULL;
      DestroyListNode(&(theList->first));
         /*DestroyListNode sets theList->first to NULL*/
      }
   else
      {
      theList->first = theList->first->next;
      DestroyListNode(&(theList->first->prev));
         /*DestroyListNode sets theList->first->prev to NULL*/
      }
   theList->length--;
}

void DeleteLast(ParseTreeListHdl theList)
{ 
   assert(theList != NULL);
   assert(!IsEmpty(theList));

   if(AtLast(theList))
      {
      theList->flagged = NULL;
      }

   if(theList->first == theList->last)
      {
      DeleteFirst(theList);
      }  
   else
      {
      theList->last = theList->last->prev;
      DestroyListNode(&(theList->last->next));
         /*DestroyListNode set theList->last->next to NULL*/
      theList->length--;
      }
}

void DeleteFlagged(ParseTreeListHdl theList)
{
   assert(theList != NULL);
   assert(!IsEmpty(theList));
   assert(ExistsFlagged(theList));

   if(AtFirst(theList))
      {
      DeleteFirst(theList);
      }
   else if(AtLast(theList))
      {
      DeleteLast(theList);
      }
   else
      {
      theList->flagged->prev->next = theList->flagged->next;
      theList->flagged->next->prev = theList->flagged->prev;
      DestroyListNode(&(theList->flagged));
         /*DestroyListNode sets theList->flagged to NULL*/
      theList->length--;
      }
}


/*----------Functions local to this ADT----------*/
/***********************************************************************
 This allocates memory to store theData in.
 Precondition:   theNode is NULL.
 Postcondition:  theNode will be initialized to contain theData and its
    prev and next fields will be NULL
***********************************************************************/
void CreateListNode(ListNodePtr * theNode, ParseTreeHdl theData)
{
   assert(*theNode == NULL);

   *theNode = (ListNodePtr)malloc(sizeof(ListNodeStruct));
   (*theNode)->next = NULL;
   (*theNode)->prev = NULL;
   (*theNode)->data = theData;
}

/***********************************************************************
 This procedure frees the memory used by theNode
 Precondition:   theNode has been initialized by CreateListNode
 Postcondition:  theNode is set to NULL.  The memory previous used
    by theNode is now freed and shouldn't be accessed
***********************************************************************/
void DestroyListNode(ListNodePtr * theNode)
{
   assert(*theNode != NULL);

   free(*theNode);
   *theNode = NULL;
}


/*----------Debugging procedures----------*/
void DumpList(ParseTreeListHdl theList)
{
   ListNodePtr cur;

   if(theList == NULL)
      {
      fprintf(stderr, "The list is NULL\n");
      }
   else
      {
      fprintf(stderr, "The list:   ");
      cur = theList->first;
      while(cur != NULL)
         {
         if(cur == theList->first)
            {
            fprintf(stderr, "first: ");
            }
         if(cur == theList->flagged)
            {
            fprintf(stderr, "_");
            }
         fprintf(stderr, "%d", (int)cur->data);
         if(cur == theList->flagged)
            {
            fprintf(stderr, "_");
            }
         fprintf(stderr, " ");
         if(cur == theList->last)
            {
            fprintf(stderr, ":last ");
            }
         cur = cur->next;
         }
      fprintf(stderr, "\n");
      fprintf(stderr, "The length is: %d\n", theList->length);
      fprintf(stderr, "The first ptr is: %p\n", theList->first);
      fprintf(stderr, "The last ptr is: %p\n", theList->last);
      fprintf(stderr, "The flagged ptr is: %p\n", theList->flagged);
      }
}