queue.c

PHP v6.0 For Linux 运行环境：Win9X/ WinME/ WinNT/ Win2K/ WinXP

static const char rcsid[] = "#(@) $Id: queue.c,v 1.4 2002/07/05 04:43:53 danda Exp $";

/* 
 * Date last modified: Jan 2001
 * Modifications by Dan Libby ([e-mail]), including:
 *  - various fixes, null checks, etc
 *  - addition of Q_Iter funcs, macros
 */


/*-**************************************************************
 *
 *  File : q.c
 *
 *  Author: Peter Yard [1993.01.02] -- 02 Jan 1993
 *
 *  Disclaimer: This code is released to the public domain.
 *
 *  Description:
 *      Generic double ended queue (Deque pronounced DEK) for handling
 *      any data types, with sorting.
 *
 *      By use of various functions in this module the caller
 *      can create stacks, queues, lists, doubly linked lists,
 *      sorted lists, indexed lists.  All lists are dynamic.
 *
 *      It is the responsibility of the caller to malloc and free
 *      memory for insertion into the queue. A pointer to the object
 *      is used so that not only can any data be used but various kinds
 *      of data can be pushed on the same queue if one so wished e.g.
 *      various length string literals mixed with pointers to structures
 *      or integers etc.
 *
 *  Enhancements:
 *      A future improvement would be the option of multiple "cursors"
 *      so that multiple locations could occur in the one queue to allow
 *      placemarkers and additional flexibility.  Perhaps even use queue
 *      itself to have a list of cursors.
 *
 * Usage:
 *
 *          /x init queue x/
 *          queue  q;
 *          Q_Init(&q);
 *
 *      To create a stack :
 *
 *          Q_PushHead(&q, &mydata1); /x push x/
 *          Q_PushHead(&q, &mydata2);
 *          .....
 *          data_ptr = Q_PopHead(&q); /x pop x/
 *          .....
 *          data_ptr = Q_Head(&q);   /x top of stack x/
 *
 *      To create a FIFO:
 *
 *          Q_PushHead(&q, &mydata1);
 *          .....
 *          data_ptr = Q_PopTail(&q);
 *
 *      To create a double list:
 *
 *          data_ptr = Q_Head(&q);
 *          ....
 *          data_ptr = Q_Next(&q);
 *          data_ptr = Q_Tail(&q);
 *          if (Q_IsEmpty(&q)) ....
 *          .....
 *          data_ptr = Q_Previous(&q);
 *
 *      To create a sorted list:
 *
 *          Q_PushHead(&q, &mydata1); /x push x/
 *          Q_PushHead(&q, &mydata2);
 *          .....
 *          if (!Q_Sort(&q, MyFunction))
 *              .. error ..
 *
 *          /x fill in key field of mydata1.
 *           * NB: Q_Find does linear search
 *           x/
 *
 *          if (Q_Find(&q, &mydata1, MyFunction))
 *          {
 *              /x found it, queue cursor now at correct record x/
 *              /x can retrieve with x/
 *              data_ptr = Q_Get(&q);
 *
 *              /x alter data , write back with x/
 *              Q_Put(&q, data_ptr);
 *          }
 *
 *          /x Search with binary search x/
 *          if (Q_Seek(&q, &mydata, MyFunction))
 *              /x etc x/
 *
 *
 ****************************************************************/

#ifdef _WIN32
#include "xmlrpc_win32.h"
#endif
#include <stdlib.h>
#include "queue.h"


static void QuickSort(void *list[], int low, int high,
                      int (*Comp)(const void *, const void *));
static int  Q_BSearch(queue *q, void *key,
                      int (*Comp)(const void *, const void *));

/* The index: a pointer to pointers */

static  void        **index;
static  datanode    **posn_index;


/***
 *
 ** function    : Q_Init
 *
 ** purpose     : Initialise queue object and pointers.
 *
 ** parameters  : 'queue' pointer.
 *
 ** returns     : True_ if init successful else False_
 *
 ** comments    :
 ***/

int Q_Init(queue  *q)
{
   if(q) {
      q->head = q->tail = NULL;
      q->cursor = q->head;
      q->size = 0;
      q->sorted = False_;
   }

   return True_;
}

/***
 *
 ** function    : Q_AtHead
 *
 ** purpose     : tests if cursor is at head of queue
 *
 ** parameters  : 'queue' pointer.
 *
 ** returns     : boolean - True_ is at head else False_
 *
 ** comments    :
 *
 ***/

int Q_AtHead(queue *q)
{
   return(q && q->cursor == q->head);
}


/***
 *
 ** function    : Q_AtTail
 *
 ** purpose     : boolean test if cursor at tail of queue
 *
 ** parameters  : 'queue' pointer to test.
 *
 ** returns     : True_ or False_
 *
 ** comments    :
 *
 ***/

int Q_AtTail(queue *q)
{
   return(q && q->cursor == q->tail);
}


/***
 *
 ** function    : Q_IsEmpty
 *
 ** purpose     : test if queue has nothing in it.
 *
 ** parameters  : 'queue' pointer
 *
 ** returns     : True_ if IsEmpty queue, else False_
 *
 ** comments    :
 *
 ***/

inline int Q_IsEmpty(queue *q)
{
   return(!q || q->size == 0);
}

/***
 *
 ** function    : Q_Size
 *
 ** purpose     : return the number of elements in the queue
 *
 ** parameters  : queue pointer
 *
 ** returns     : number of elements
 *
 ** comments    :
 *
 ***/

int Q_Size(queue *q)
{
   return q ? q->size : 0;
}


/***
 *
 ** function    : Q_Head
 *
 ** purpose     : position queue cursor to first element (head) of queue.
 *
 ** parameters  : 'queue' pointer
 *
 ** returns     : pointer to data at head. If queue is IsEmpty returns NULL
 *
 ** comments    :
 *
 ***/

void *Q_Head(queue *q)
{
   if(Q_IsEmpty(q))
      return NULL;

   q->cursor = q->head;

   return  q->cursor->data;
}


/***
 *
 ** function    : Q_Tail
 *
 ** purpose     : locate cursor at tail of queue.
 *
 ** parameters  : 'queue' pointer
 *
 ** returns     : pointer to data at tail , if queue IsEmpty returns NULL
 *
 ** comments    :
 *
 ***/

void *Q_Tail(queue *q)
{
   if(Q_IsEmpty(q))
      return NULL;

   q->cursor = q->tail;

   return  q->cursor->data;
}


/***
 *
 ** function    : Q_PushHead
 *
 ** purpose     : put a data pointer at the head of the queue
 *
 ** parameters  : 'queue' pointer, void pointer to the data.
 *
 ** returns     : True_ if success else False_ if unable to push data.
 *
 ** comments    :
 *
 ***/

int Q_PushHead(queue *q, void *d)
{
   if(q && d) {
      node    *n;
      datanode *p;

      p = malloc(sizeof(datanode));
      if(p == NULL)
         return False_;

      n = q->head;

      q->head = (node*)p;
      q->head->prev = NULL;

      if(q->size == 0) {
         q->head->next = NULL;
         q->tail = q->head;
      }
      else {
         q->head->next = (datanode*)n;
         n->prev = q->head;
      }

      q->head->data = d;
      q->size++;

      q->cursor = q->head;

      q->sorted = False_;

      return True_;
   }
   return False_;
}



/***
 *
 ** function    : Q_PushTail
 *
 ** purpose     : put a data element pointer at the tail of the queue
 *
 ** parameters  : queue pointer, pointer to the data
 *
 ** returns     : True_ if data pushed, False_ if data not inserted.
 *
 ** comments    :
 *
 ***/

int Q_PushTail(queue *q, void *d)
{
   if(q && d) {
      node        *p;
      datanode    *n;

      n = malloc(sizeof(datanode));
      if(n == NULL)
         return False_;

      p = q->tail;
      q->tail = (node *)n;

      if(q->size == 0) {
         q->tail->prev = NULL;
         q->head = q->tail;
      }
      else {
         q->tail->prev = (datanode *)p;
         p->next = q->tail;
      }

      q->tail->next = NULL;

      q->tail->data =  d;
      q->cursor = q->tail;
      q->size++;

      q->sorted = False_;

      return True_;
   }
   return False_;
}



/***
 *
 ** function    : Q_PopHead
 *
 ** purpose     : remove and return the top element at the head of the
 *                queue.
 *
 ** parameters  : queue pointer
 *
 ** returns     : pointer to data element or NULL if queue is IsEmpty.
 *
 ** comments    :
 *
 ***/

void *Q_PopHead(queue *q)
{
   datanode    *n;
   void        *d;

   if(Q_IsEmpty(q))
      return NULL;

   d = q->head->data;
   n = q->head->next;
   free(q->head);

   q->size--;

   if(q->size == 0)
      q->head = q->tail = q->cursor = NULL;
   else {
      q->head = (node *)n;
      q->head->prev = NULL;
      q->cursor = q->head;
   }

   q->sorted = False_;

   return d;
}


/***
 *
 ** function    : Q_PopTail
 *
 ** purpose     : remove element from tail of queue and return data.
 *
 ** parameters  : queue pointer
 *
 ** returns     : pointer to data element that was at tail. NULL if queue
 *                IsEmpty.
 *
 ** comments    :
 *
 ***/

void *Q_PopTail(queue *q)
{
   datanode    *p;
   void        *d;

   if(Q_IsEmpty(q))
      return NULL;

   d = q->tail->data;
   p = q->tail->prev;
   free(q->tail);
   q->size--;

   if(q->size == 0)
      q->head = q->tail = q->cursor = NULL;
   else {
      q->tail = (node *)p;
      q->tail->next = NULL;
      q->cursor = q->tail;
   }

   q->sorted = False_;

   return d;
}



/***
 *
 ** function    : Q_Next
 *
 ** purpose     : Move to the next element in the queue without popping
 *
 ** parameters  : queue pointer.
 *
 ** returns     : pointer to data element of new element or NULL if end
 *                of the queue.
 *
 ** comments    : This uses the cursor for the current position. Q_Next
 *                only moves in the direction from the head of the queue
 *                to the tail.
 ***/

void *Q_Next(queue *q)
{
   if(!q)
      return NULL;

   if(!q->cursor || q->cursor->next == NULL)
      return NULL;

   q->cursor = (node *)q->cursor->next;

   return  q->cursor->data ;
}



/***