/*****************************************************************************
 *                                                                           *
 *  Copyright (c) 1993, 1994, Elan Feingold (elan@tasha.cheme.cornell.edu)   *
 *                                                                           *
 *     PERMISSION TO USE, COPY, MODIFY, AND TO DISTRIBUTE THIS SOFTWARE      *
 *     AND ITS DOCUMENTATION FOR ANY PURPOSE IS HEREBY GRANTED WITHOUT       *
 *     FEE, PROVIDED THAT THE ABOVE COPYRIGHT NOTICE APPEAR IN ALL           *
 *     COPIES AND MODIFIED COPIES AND THAT BOTH THAT COPYRIGHT NOTICE AND    *
 *     THIS PERMISSION NOTICE APPEAR IN SUPPORTING DOCUMENTATION.  THERE     *
 *     IS NO REPRESENTATIONS ABOUT THE SUITABILITY OF THIS SOFTWARE FOR      *
 *     ANY PURPOSE.  THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS       *
 *     OR IMPLIED WARRANTY.                                                  *
 *                                                                           *
 *****************************************************************************/

#include <stdio.h> 
#include <stdlib.h> 
 
#include "debug.h" 
#include "queue.h" 
#include "standard.h"
#include "types.h" 
 
/* Private function prototypes */ 
QNode *AllocQNode(void); 
 
/************************************************************************ 
 *  FUNCTION: q_create 
 *  HISTORY: 
 *     09/12/93  ESF  Created 
 *  PURPOSE: 
 *     Creates a Queue object.  Initially the queue can hold 
 *     QUEUE_INIT_SIZE objects.  Returns a pointer to the new Queue. 
 *  NOTES: 
 ************************************************************************/ 
Queue q_create(void) 
{ 
  PQueue  pQueue; 
 
  /* Allocate memory and make sure there was memory to allocate */ 
  pQueue = (PQueue)MEM_Alloc(sizeof(struct _Queue)); 
  D_Assert(pQueue!=NULL, "Out of Memory!"); 
 
  /* Initialize the fields of the Queue, and init the queue to the empty 
   * state, which is the Head pointing to a valid, free node, and the 
   * tail pointing to NULL.  This way, we don't have to deal with special 
   * cases later in the code. 
   */ 
 
  pQueue->ptrTail = AllocQNode(); 
  pQueue->ptrTail->next = pQueue->ptrTail; 
  pQueue->ptrHead = NULL; 
 
  return (pQueue); 
} 
 
 
/************************************************************************ 
 *  FUNCTION: q_destroy 
 *  HISTORY: 
 *     09/12/93  ESF  Created 
 *     10/24/93  ESF  Changed to linearizing queue, because it didn't 
 *                    work under LINUX for some reason.
 *  PURPOSE: 
 *     This function frees up all of the memory taken up by a Queue. 
 *     After the function returns, pQueue must not be referenced again, 
 *     as it will point ot memory that has been freed. 
 *  NOTES: 
 ************************************************************************/ 
void q_destroy(Queue pQueue) 
{ 
  QNode *pNode, *qNode; 

  if(!pQueue)
    return;

  /* Take the circularity out of the queue */
  qNode = pQueue->ptrTail->next;
  pQueue->ptrTail->next = NULL;

  /* Now run along the list freeing everything until we hit a NULL */
  for(pNode=qNode; pNode; pNode=qNode)
    {
      qNode = pNode->next;
      MEM_Free(pNode); 
    }

  MEM_Free(pQueue);
} 
 
 
/************************************************************************ 
 *  FUNCTION: q_cut_in_line
 *  HISTORY: 
 *     11/01/93  ESF  Created. 
 *     11/08/93  ESF  Fixed bug, not setting pQueue->ptrHead.
 *  PURPOSE: 
 *  NOTES: 
 ************************************************************************/ 
void q_cut_in_line(PQueue pQueue, any_ptr pvObject) 
{
  if (pQueue->ptrTail->next == pQueue->ptrHead)
    {
      QNode *ptrNode;

      /* No room, have to create and insert a node */
      ptrNode = AllocQNode();
      ptrNode->pvObject = pvObject;
      ptrNode->next = pQueue->ptrHead;
      pQueue->ptrTail->next = ptrNode;
      pQueue->ptrHead = ptrNode;
    }
  else
    {
      QNode *q;

      /* There were free nodes cached, use one */
      for (q=pQueue->ptrTail; q->next!=pQueue->ptrHead; q=q->next)
	; /* TwidleThumbs() */
      
      q->pvObject = pvObject;
      pQueue->ptrHead = q;
    }
}


/************************************************************************ 
 *  FUNCTION: q_insert 
 *  HISTORY: 
 *     09/12/93  ESF  Created 
 *  PURPOSE: 
 *     Inserts an Object into the Queue passed in.  If there are nodes in 
 *     the free node pool (linked after the head of the queue), use these, 
 *     otherwise allocate a new one and bind it to the rest of the queue. 
 *     Returns w/o doing anything if the queue passed in is NULL; 
 *  NOTES: 
 ************************************************************************/ 
void q_insert(Queue pQueue, any_ptr pvObject) 
{ 
  if(!pQueue) 
    return; 
 
  /* Are there available nodes?  If not, allocate memory for a new one. 
   * If there are, the creation is free, and we simply take a node off 
   * of the free node pool by moving the ptrTail along one node. 
   * The picture is as follows: 
   * 
   *      ======================================================= 
   *      |                                                     | 
   *   ---------      ---------       ---------             --------- 
   *   | QNode | ===> | QNode | ===>  | QNode | === ... ==> | QNode | 
   *   ---------      ---------       ---------             --------- 
   *      ^                               ^ 
   *      |___ ptrHead                    |___ ptrTail 
   * 
   *   (The "..." represent free nodes.) 
   */
 
  /* See if there is free space inbetween the Head and the Tail */
  if(pQueue->ptrTail->next != pQueue->ptrHead)
    ; /* Insertion was cheap! */
  else 
   { 
    QNode *ptrNode; 
 
    /* Allocate new node, and insert it after the head. */ 
    ptrNode = AllocQNode(); 
    ptrNode->next = pQueue->ptrTail->next; 
    pQueue->ptrTail->next = ptrNode; 
   } 
 
  /* Advance the Queue head */ 
  pQueue->ptrTail = pQueue->ptrTail->next; 
 
  /*** Assert: pQueue->ptrTail points to a valid, free, QNode ***/ 
 
  /* If ptrHead is NULL, it was out of the game from a previous q_delete */ 
  if(pQueue->ptrHead == NULL) 
    pQueue->ptrHead = pQueue->ptrTail; 
 
  /* Put the Object in the Queue */ 
  pQueue->ptrTail->pvObject = pvObject; 
} 
 
 
/************************************************************************ 
 *  FUNCTION: q_remove
 *  HISTORY:
 *     09/12/93  ESF  Created
 *  PURPOSE:
 *     Returns a pointer to the Object at the head of the Queue,
 *     checking of course for a valid queue.  If a valid remove
 *     occurs, the node gets "dumped" into the Node Pool for subsequent
 *     use.
 *  NOTES:
 ************************************************************************/ 
any_ptr q_remove(Queue pQueue) 
{ 
  QNode *pNode; 
 
  if(q_is_empty(pQueue)) 
    return NULL; 
 
  /* Hold on to the node to be returned */ 
  pNode = pQueue->ptrHead; 
 
  /* Remove the node from the Queue, checking for a now empty Queue */ 
  if(pQueue->ptrHead == pQueue->ptrTail) 
    pQueue->ptrHead = NULL;  /* Empty Queue */ 
  else 
    pQueue->ptrHead = pQueue->ptrHead->next; 
 
  return(pNode->pvObject); 
} 
 
 
/************************************************************************ 
 *  FUNCTION: q_is_empty 
 *  HISTORY: 
 *     09/12/93  ESF  Created 
 *  PURPOSE: 
 * 
 *  NOTES: 
 ************************************************************************/ 
Boolean q_is_empty(Queue pQueue) 
{ 
  return(!pQueue || !pQueue->ptrHead); 
} 
 
 
/************************************************************************ 
 *  FUNCTION:  AllocQNode 
 *  HISTORY: 
 *     09/12/93  ESF  Created 
 *  PURPOSE: 
 *     Allocates memory for a QNode and inits the points to NULL. 
 *  NOTES: 
 ************************************************************************/ 
QNode *AllocQNode(void) 
{ 
 QNode *pQNode = (QNode *)MEM_Alloc(sizeof(QNode)); 
 
 D_Assert(pQNode!=NULL, "Out of Memory!"); 
 pQNode->next = pQNode->pvObject = NULL; 
 
 return(pQNode); 
} 
 
 
 
/************************************************************************ 
 *  FUNCTION:  q_head 
 *  HISTORY: 
 *     10/02/93  ESF  Created 
 *  PURPOSE: 
 *     Returns a pointer to the head, element, nondestructively.  May 
 *     be NULL if queue is empty. 
 *  NOTES: 
 ************************************************************************/ 
any_ptr q_head(Queue pQueue) 
{ 
  if(q_is_empty(pQueue) || pQueue->ptrHead==NULL) 
    return NULL; 
  
  return pQueue->ptrHead->pvObject; 
} 

 

/************************************************************************ 
 *  FUNCTION: q_print  
 *  HISTORY: 
 *     09/12/93  ESF  Created 
 *  PURPOSE: 
 *     Prints a queue.  Essentially used for debugging. 
 *  NOTES: 
 ************************************************************************/ 
void q_print(Queue pQueue) 
 { 
  QNode *qNode; 
 
  printf("QUEUE:\n"); 
 
  if(!pQueue || q_is_empty(pQueue)) 
    return; 
 
  for(qNode=pQueue->ptrHead; qNode!=pQueue->ptrTail; qNode=qNode->next) 
    printf("\tNODE [0x%08lx]\n", (UInt)qNode->pvObject); 
  printf("\tNODE [0x%08lx]\n", (UInt)qNode->pvObject); 
} 
 
/************************************************************************ 
 *  FUNCTION: q_journey
 *  HISTORY:
 *     04/13/94  Fare'  Created
 *  PURPOSE:
 *     Journey through a queue, executing some function for each
 *   member of the queue.
 *  NOTES:
 *     Perhaps additional parameters to a JFun should be the Queue
 *   itself and the current node, so the JFun can do global changes on
 *   the queue...
 ************************************************************************/ 

void* q_journey(Queue pQueue,JFun_t* JFun,void* pState)
 {
  QNode *qNode;

  if(!pQueue || q_is_empty(pQueue)) 
    return pState;

  for(qNode=pQueue->ptrHead; qNode!=pQueue->ptrTail; qNode=qNode->next) 
    pState = (*JFun) (pState,qNode->pvObject);
}

/************************************************************************ 
 *  FUNCTION: q_size
 *  HISTORY:
 *     04/13/94  Fare'  Created
 *  PURPOSE:
 *     counts the number of nodes in the queue
 *  NOTES:
 ************************************************************************/ 

static UInt increment (UInt count) { return count+1 ; }

UInt q_size(Queue pQueue)
{
  return (UInt) q_journey (pQueue,(JFun_t*)increment,(any_ptr)0 ) ;
}

/************************************************************************
 *  FUNCTION: q_realsize
 *  HISTORY:
 *     04/13/94  Fare'  Created
 *  PURPOSE:
 *     journey through a queue, executing some function for each
 *   member of the queue.
 *  NOTES:
 *     I use it to count the max. size reached by a queue...
 *     Perhaps the name is ill choosen...
 ************************************************************************/

UInt q_realsize(Queue pQueue)
{
  struct _Queue RealQ ;

  if(!pQueue) return 0 ;
  RealQ.ptrHead = RealQ.ptrTail = pQueue->ptrHead ;
  return q_size(&RealQ) ;
}
