//  *************** LLFIFO.C *********************

// Dynamically allocated linked list FIFO

// Last modified 12/12/02 by Jonathan W. Valvano

 

// Copyright 2003 by Jonathan W. Valvano, valvano@uts.cc.utexas.edu 

//    You may use, edit, run or distribute this file 

//    as long as the above copyright notice remains 



#include "HEAP.H"

// Set the BlockSize in HEAP.H to match the size of the Node

// In this case, BlockSize=2 16-bit integers

struct Node{

  struct Node *NextPt;

  unsigned short value;

};

typedef struct Node NodeType;

typedef NodeType *NodePtr;

NodePtr PutPt;    /* Pointer to newest node, place to put */

NodePtr GetPt;    /* Pointer to oldest node, place to get */

/* Single linked list e.g., assume three elements in the Fifo

    PutPt =>  Null    <=   Prev2   <=    Prev3  <=  GetPt

              Data1        Data2         Data3            */



// initializes Heap and linked list FIFO

void LLFifo_Init(void) {

   Heap_Init();    // initialize Heap

   GetPt = null;    /* Empty when GetPt=null */

   PutPt = null;

 }



// three steps occur

//  1) creates a new linked list node (dynamic allocation), 

//  2) stores 16-bit data in node.

//  3) links the node into the linked list FIFO

// returns 0 if data can not be saved, because heap is empty

// returns 1 if data was successfully saved

int LLFifo_Put(unsigned short data) { 

NodePtr pt; int success;

  success = 0; /* failed because Heap is full?? */

  pt = (NodePtr)Heap_Allocate();

  if(pt){

    pt->value = data;   /* store data field */

    pt->NextPt = null;

    if(PutPt){

      PutPt->NextPt = pt;  /* Link existing to new structure */

    }

    else{

      GetPt = pt;  /* first one */

    }

    PutPt = pt;

    success = 1; 

  }

  return(success);

}



// three steps occur

//  1) retrieves the data from the oldest linked list node, 

//  2) unlinks the node from the linked list FIFO

//  3) releases the memory of the node (dynamic deallocation)

// returns 0 if data can not be removed, because FIFO was empty

// returns 1 if data was successfully removed

int LLFifo_Get(unsigned short *datapt){ NodePtr pt;  int success;

  success = 0; /* failed because fifo is empty?? */

  if(GetPt){

    *datapt = GetPt->value;  /* Retrieve the data */

    pt = GetPt;

    GetPt = GetPt->NextPt;

    if(GetPt==null){         /* Special case: only one entry */

      PutPt = null;

    }

    Heap_Release((unsigned short*)pt);

    success = 1; 

  }

  return(success);

}

#include "HEAP.C"