static const char rcsid[] = "#(@) $Id$";
/*
* Date last modified: Jan 2001
* Modifications by Dan Libby (dan@libby.com), 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 ;
}
/***
*
** function : Q_Previous
*
** purpose : Opposite of Q_Next. Move to next element closer to the
* head of the queue.
*
** parameters : pointer to queue
*
** returns : pointer to data of new element else NULL if queue IsEmpty
*
** comments : Makes cursor move towards the head of the queue.
*
***/
void *Q_Previous(queue *q)
{
if(!q)
return NULL;
if(q->cursor->prev == NULL)
return NULL;
q->cursor = (node *)q->cursor->prev;
return q->cursor->data;
}
void *Q_Iter_Del(queue *q, q_iter iter)
{
void *d;
datanode *n, *p;
if(!q)
return NULL;
if(iter == NULL)
return NULL;
if(iter == (q_iter)q->head)
return Q_PopHead(q);
if(iter == (q_iter)q->tail)
return Q_PopTail(q);
n = ((node*)iter)->next;
p = ((node*)iter)->prev;
d = ((node*)iter)->data;
free(iter);
if(p) {
p->next = n;
}
if (q->cursor == (node*)iter) {
if (p) {
q->cursor = p;
} else {
q->cursor = n;
}
}
if (n != NULL) {
n->prev = p;
}
q->size--;
q->sorted = False_;
return d;
}
/***
*
** function : Q_DelCur
*
** purpose : Delete the current queue element as pointed to by
* the cursor.
*
** parameters : queue pointer
*
** returns : pointer to data element.
*
** comments : WARNING! It is the responsibility of the caller to
* free any memory. Queue cannot distinguish between
* pointers to literals and malloced memory.
*
***/
void *Q_DelCur(queue* q) {
if(q) {
return Q_Iter_Del(q, (q_iter)q->cursor);
}
return 0;
}
/***
*
** function : Q_Destroy
*
** purpose : Free all queue resources
*
** parameters : queue pointer
*
** returns : null.
*
** comments : WARNING! It is the responsibility of the caller to
* free any memory. Queue cannot distinguish between
* pointers to literals and malloced memory.
*
***/
void Q_Destroy(queue *q)
{
while(!Q_IsEmpty(q)) {
Q_PopHead(q);
}
}
/***
*
** function : Q_Get
*
** purpose : get the pointer to the data at the cursor location
*
** parameters : queue pointer
*
** returns : data element pointer
*
** comments :
*
***/
void *Q_Get(queue *q)
{
if(!q)
return NULL;
if(q->cursor == NULL)
return NULL;
return q->cursor->data;
}
/***
*
** function : Q_Put
*
** purpose : replace pointer to data with new pointer to data.
*
** parameters : queue pointer, data pointer
*
** returns : boolean- True_ if successful, False_ if cursor at NULL
*
** comments :
*
***/
int Q_Put(queue *q, void *data)
{
if(q && data) {
if(q->cursor == NULL)
return False_;
q->cursor->data = data;
return True_;
}
return False_;
}
/***
*
** function : Q_Find
*
** purpose : Linear search of queue for match with key in *data
*
** parameters : queue pointer q, data pointer with data containing key
* comparison function here called Comp.
*
** returns : True_ if found , False_ if not in queue.
*
** comments : Useful for small queues that are constantly changing
* and would otherwise need constant sorting with the
* Q_Seek function.
* For description of Comp see Q_Sort.
* Queue cursor left on position found item else at end.
*
***/
int Q_Find(queue *q, void *data,
int (*Comp)(const void *, const void *))
{
void *d;
if (q == NULL) {
return False_;
}
d = Q_Head(q);
do {
if(Comp(d, data) == 0)
return True_;
d = Q_Next(q);
} while(!Q_AtTail(q));
if(Comp(d, data) == 0)
return True_;
return False_;
}
/*======== Sorted Queue and Index functions ========= */
static void QuickSort(void *list[], int low, int high,
int (*Comp)(const void *, const void *))
{
int flag = 1, i, j;
void *key, *temp;
if(low < high) {
i = low;
j = high + 1;
key = list[ low ];
while(flag) {
i++;
while(Comp(list[i], key) < 0)
i++;
j--;
while(Comp(list[j], key) > 0)
j--;
if(i < j) {
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
else flag = 0;
}
temp = list[low];
list[low] = list[j];
list[j] = temp;
QuickSort(list, low, j-1, Comp);
QuickSort(list, j+1, high, Comp);
}
}
/***
*
** function : Q_Sort
*
** purpose : sort the queue and allow index style access.
*
** parameters : queue pointer, comparison function compatible with
* with 'qsort'.
*
** returns : True_ if sort succeeded. False_ if error occurred.
*
** comments : Comp function supplied by caller must return
* -1 if data1 < data2
* 0 if data1 == data2
* +1 if data1 > data2
*
* for Comp(data1, data2)
*
* If queue is already sorted it frees the memory of the
* old index and starts again.
*
***/
int Q_Sort(queue *q, int (*Comp)(const void *, const void *))
{
int i;
void *d;
datanode *dn;
/* if already sorted free memory for tag array */
if(q->sorted) {
free(index);
free(posn_index);
q->sorted = False_;
}
/* Now allocate memory of array, array of pointers */
index = malloc(q->size * sizeof(q->cursor->data));
if(index == NULL)
return False_;
posn_index = malloc(q->size * sizeof(q->cursor));
if(posn_index == NULL) {
free(index);
return False_;
}
/* Walk queue putting pointers into array */
d = Q_Head(q);
for(i=0; i < q->size; i++) {
index[i] = d;
posn_index[i] = q->cursor;
d = Q_Next(q);
}
/* Now sort the index */
QuickSort(index, 0, q->size - 1, Comp);
/* Rearrange the actual queue into correct order */
dn = q->head;
i = 0;
while(dn != NULL) {
dn->data = index[i++];
dn = dn->next;
}
/* Re-position to original element */
if(d != NULL)
Q_Find(q, d, Comp);
else Q_Head(q);
q->sorted = True_;
return True_;
}
/***
*
** function : Q_BSearch
*
** purpose : binary search of queue index for node containing key
*
** parameters : queue pointer 'q', data pointer of key 'key',
* Comp comparison function.
*
** returns : integer index into array of node pointers,
* or -1 if not found.
*
** comments : see Q_Sort for description of 'Comp' function.
*
***/
static int Q_BSearch( queue *q, void *key,
int (*Comp)(const void *, const void*))
{
int low, mid, hi, val;
low = 0;
hi = q->size - 1;
while(low <= hi) {
mid = (low + hi) / 2;
val = Comp(key, index[ mid ]);
if(val < 0)
hi = mid - 1;
else if(val > 0)
low = mid + 1;
else /* Success */
return mid;
}
/* Not Found */
return -1;
}
/***
*
** function : Q_Seek
*
** purpose : use index to locate data according to key in 'data'
*
** parameters : queue pointer 'q', data pointer 'data', Comp comparison
* function.
*
** returns : pointer to data or NULL if could not find it or could
* not sort queue.
*
** comments : see Q_Sort for description of 'Comp' function.
*
***/
void *Q_Seek(queue *q, void *data, int (*Comp)(const void *, const void *))
{
int idx;
if (q == NULL) {
return NULL;
}
if(!q->sorted) {
if(!Q_Sort(q, Comp))
return NULL;
}
idx = Q_BSearch(q, data, Comp);
if(idx < 0)
return NULL;
q->cursor = posn_index[idx];
return index[idx];
}
/***
*
** function : Q_Insert
*
** purpose : Insert an element into an indexed queue
*
** parameters : queue pointer 'q', data pointer 'data', Comp comparison
* function.
*
** returns : pointer to data or NULL if could not find it or could
* not sort queue.
*
** comments : see Q_Sort for description of 'Comp' function.
* WARNING! This code can be very slow since each new
* element means a new Q_Sort. Should only be used for
* the insertion of the odd element ,not the piecemeal
* building of an entire queue.
***/
int Q_Insert(queue *q, void *data, int (*Comp)(const void *, const void *))
{
if (q == NULL) {
return False_;
}
Q_PushHead(q, data);
if(!Q_Sort(q, Comp))
return False_;
return True_;
}
/* read only funcs for iterating through queue. above funcs modify queue */
q_iter Q_Iter_Head(queue *q) {
return q ? (q_iter)q->head : NULL;
}
q_iter Q_Iter_Tail(queue *q) {
return q ? (q_iter)q->tail : NULL;
}
q_iter Q_Iter_Next(q_iter qi) {
return qi ? (q_iter)((node*)qi)->next : NULL;
}
q_iter Q_Iter_Prev(q_iter qi) {
return qi ? (q_iter)((node*)qi)->prev : NULL;
}
void * Q_Iter_Get(q_iter qi) {
return qi ? ((node*)qi)->data : NULL;
}
int Q_Iter_Put(q_iter qi, void* data) {
if(qi) {
((node*)qi)->data = data;
return True_;
}
return False_;
}