1 static const char rcsid[] = "#(@) $Id$";
4 * Date last modified: Jan 2001
5 * Modifications by Dan Libby (dan@libby.com), including:
6 * - various fixes, null checks, etc
7 * - addition of Q_Iter funcs, macros
11 /*-**************************************************************
15 * Author: Peter Yard [1993.01.02] -- 02 Jan 1993
17 * Disclaimer: This code is released to the public domain.
20 * Generic double ended queue (Deque pronounced DEK) for handling
21 * any data types, with sorting.
23 * By use of various functions in this module the caller
24 * can create stacks, queues, lists, doubly linked lists,
25 * sorted lists, indexed lists. All lists are dynamic.
27 * It is the responsibility of the caller to malloc and free
28 * memory for insertion into the queue. A pointer to the object
29 * is used so that not only can any data be used but various kinds
30 * of data can be pushed on the same queue if one so wished e.g.
31 * various length string literals mixed with pointers to structures
35 * A future improvement would be the option of multiple "cursors"
36 * so that multiple locations could occur in the one queue to allow
37 * placemarkers and additional flexibility. Perhaps even use queue
38 * itself to have a list of cursors.
48 * Q_PushHead(&q, &mydata1); /x push x/
49 * Q_PushHead(&q, &mydata2);
51 * data_ptr = Q_PopHead(&q); /x pop x/
53 * data_ptr = Q_Head(&q); /x top of stack x/
57 * Q_PushHead(&q, &mydata1);
59 * data_ptr = Q_PopTail(&q);
61 * To create a double list:
63 * data_ptr = Q_Head(&q);
65 * data_ptr = Q_Next(&q);
66 * data_ptr = Q_Tail(&q);
67 * if (Q_IsEmpty(&q)) ....
69 * data_ptr = Q_Previous(&q);
71 * To create a sorted list:
73 * Q_PushHead(&q, &mydata1); /x push x/
74 * Q_PushHead(&q, &mydata2);
76 * if (!Q_Sort(&q, MyFunction))
79 * /x fill in key field of mydata1.
80 * * NB: Q_Find does linear search
83 * if (Q_Find(&q, &mydata1, MyFunction))
85 * /x found it, queue cursor now at correct record x/
86 * /x can retrieve with x/
87 * data_ptr = Q_Get(&q);
89 * /x alter data , write back with x/
90 * Q_Put(&q, data_ptr);
93 * /x Search with binary search x/
94 * if (Q_Seek(&q, &mydata, MyFunction))
98 ****************************************************************/
101 #include "xmlrpc_win32.h"
107 static void QuickSort(void *list[], int low, int high,
108 int (*Comp)(const void *, const void *));
109 static int Q_BSearch(queue *q, void *key,
110 int (*Comp)(const void *, const void *));
112 /* The index: a pointer to pointers */
115 static datanode **posn_index;
122 ** purpose : Initialise queue object and pointers.
124 ** parameters : 'queue' pointer.
126 ** returns : True_ if init successful else False_
134 q->head = q->tail = NULL;
145 ** function : Q_AtHead
147 ** purpose : tests if cursor is at head of queue
149 ** parameters : 'queue' pointer.
151 ** returns : boolean - True_ is at head else False_
157 int Q_AtHead(queue *q)
159 return(q && q->cursor == q->head);
165 ** function : Q_AtTail
167 ** purpose : boolean test if cursor at tail of queue
169 ** parameters : 'queue' pointer to test.
171 ** returns : True_ or False_
177 int Q_AtTail(queue *q)
179 return(q && q->cursor == q->tail);
185 ** function : Q_IsEmpty
187 ** purpose : test if queue has nothing in it.
189 ** parameters : 'queue' pointer
191 ** returns : True_ if IsEmpty queue, else False_
197 inline int Q_IsEmpty(queue *q)
199 return(!q || q->size == 0);
206 ** purpose : return the number of elements in the queue
208 ** parameters : queue pointer
210 ** returns : number of elements
218 return q ? q->size : 0;
226 ** purpose : position queue cursor to first element (head) of queue.
228 ** parameters : 'queue' pointer
230 ** returns : pointer to data at head. If queue is IsEmpty returns NULL
236 void *Q_Head(queue *q)
243 return q->cursor->data;
251 ** purpose : locate cursor at tail of queue.
253 ** parameters : 'queue' pointer
255 ** returns : pointer to data at tail , if queue IsEmpty returns NULL
261 void *Q_Tail(queue *q)
268 return q->cursor->data;
274 ** function : Q_PushHead
276 ** purpose : put a data pointer at the head of the queue
278 ** parameters : 'queue' pointer, void pointer to the data.
280 ** returns : True_ if success else False_ if unable to push data.
286 int Q_PushHead(queue *q, void *d)
292 p = malloc(sizeof(datanode));
299 q->head->prev = NULL;
302 q->head->next = NULL;
306 q->head->next = (datanode*)n;
326 ** function : Q_PushTail
328 ** purpose : put a data element pointer at the tail of the queue
330 ** parameters : queue pointer, pointer to the data
332 ** returns : True_ if data pushed, False_ if data not inserted.
338 int Q_PushTail(queue *q, void *d)
344 n = malloc(sizeof(datanode));
352 q->tail->prev = NULL;
356 q->tail->prev = (datanode *)p;
360 q->tail->next = NULL;
377 ** function : Q_PopHead
379 ** purpose : remove and return the top element at the head of the
382 ** parameters : queue pointer
384 ** returns : pointer to data element or NULL if queue is IsEmpty.
390 void *Q_PopHead(queue *q)
405 q->head = q->tail = q->cursor = NULL;
408 q->head->prev = NULL;
420 ** function : Q_PopTail
422 ** purpose : remove element from tail of queue and return data.
424 ** parameters : queue pointer
426 ** returns : pointer to data element that was at tail. NULL if queue
433 void *Q_PopTail(queue *q)
447 q->head = q->tail = q->cursor = NULL;
450 q->tail->next = NULL;
465 ** purpose : Move to the next element in the queue without popping
467 ** parameters : queue pointer.
469 ** returns : pointer to data element of new element or NULL if end
472 ** comments : This uses the cursor for the current position. Q_Next
473 * only moves in the direction from the head of the queue
477 void *Q_Next(queue *q)
482 if(!q->cursor || q->cursor->next == NULL)
485 q->cursor = (node *)q->cursor->next;
487 return q->cursor->data ;
494 ** function : Q_Previous
496 ** purpose : Opposite of Q_Next. Move to next element closer to the
499 ** parameters : pointer to queue
501 ** returns : pointer to data of new element else NULL if queue IsEmpty
503 ** comments : Makes cursor move towards the head of the queue.
507 void *Q_Previous(queue *q)
512 if(q->cursor->prev == NULL)
515 q->cursor = (node *)q->cursor->prev;
517 return q->cursor->data;
521 void *Q_Iter_Del(queue *q, q_iter iter)
532 if(iter == (q_iter)q->head)
535 if(iter == (q_iter)q->tail)
538 n = ((node*)iter)->next;
539 p = ((node*)iter)->prev;
540 d = ((node*)iter)->data;
547 if (q->cursor == (node*)iter) {
571 ** function : Q_DelCur
573 ** purpose : Delete the current queue element as pointed to by
576 ** parameters : queue pointer
578 ** returns : pointer to data element.
580 ** comments : WARNING! It is the responsibility of the caller to
581 * free any memory. Queue cannot distinguish between
582 * pointers to literals and malloced memory.
586 void *Q_DelCur(queue* q) {
588 return Q_Iter_Del(q, (q_iter)q->cursor);
596 ** function : Q_Destroy
598 ** purpose : Free all queue resources
600 ** parameters : queue pointer
604 ** comments : WARNING! It is the responsibility of the caller to
605 * free any memory. Queue cannot distinguish between
606 * pointers to literals and malloced memory.
610 void Q_Destroy(queue *q)
612 while(!Q_IsEmpty(q)) {
622 ** purpose : get the pointer to the data at the cursor location
624 ** parameters : queue pointer
626 ** returns : data element pointer
632 void *Q_Get(queue *q)
637 if(q->cursor == NULL)
639 return q->cursor->data;
648 ** purpose : replace pointer to data with new pointer to data.
650 ** parameters : queue pointer, data pointer
652 ** returns : boolean- True_ if successful, False_ if cursor at NULL
658 int Q_Put(queue *q, void *data)
661 if(q->cursor == NULL)
664 q->cursor->data = data;
675 ** purpose : Linear search of queue for match with key in *data
677 ** parameters : queue pointer q, data pointer with data containing key
678 * comparison function here called Comp.
680 ** returns : True_ if found , False_ if not in queue.
682 ** comments : Useful for small queues that are constantly changing
683 * and would otherwise need constant sorting with the
685 * For description of Comp see Q_Sort.
686 * Queue cursor left on position found item else at end.
690 int Q_Find(queue *q, void *data,
691 int (*Comp)(const void *, const void *))
701 if(Comp(d, data) == 0)
704 } while(!Q_AtTail(q));
706 if(Comp(d, data) == 0)
712 /*======== Sorted Queue and Index functions ========= */
715 static void QuickSort(void *list[], int low, int high,
716 int (*Comp)(const void *, const void *))
729 while(Comp(list[i], key) < 0)
733 while(Comp(list[j], key) > 0)
748 QuickSort(list, low, j-1, Comp);
749 QuickSort(list, j+1, high, Comp);
758 ** purpose : sort the queue and allow index style access.
760 ** parameters : queue pointer, comparison function compatible with
763 ** returns : True_ if sort succeeded. False_ if error occurred.
765 ** comments : Comp function supplied by caller must return
766 * -1 if data1 < data2
767 * 0 if data1 == data2
768 * +1 if data1 > data2
770 * for Comp(data1, data2)
772 * If queue is already sorted it frees the memory of the
773 * old index and starts again.
777 int Q_Sort(queue *q, int (*Comp)(const void *, const void *))
783 /* if already sorted free memory for tag array */
791 /* Now allocate memory of array, array of pointers */
793 index = malloc(q->size * sizeof(q->cursor->data));
797 posn_index = malloc(q->size * sizeof(q->cursor));
798 if(posn_index == NULL) {
803 /* Walk queue putting pointers into array */
806 for(i=0; i < q->size; i++) {
808 posn_index[i] = q->cursor;
812 /* Now sort the index */
814 QuickSort(index, 0, q->size - 1, Comp);
816 /* Rearrange the actual queue into correct order */
821 dn->data = index[i++];
825 /* Re-position to original element */
839 ** function : Q_BSearch
841 ** purpose : binary search of queue index for node containing key
843 ** parameters : queue pointer 'q', data pointer of key 'key',
844 * Comp comparison function.
846 ** returns : integer index into array of node pointers,
847 * or -1 if not found.
849 ** comments : see Q_Sort for description of 'Comp' function.
853 static int Q_BSearch( queue *q, void *key,
854 int (*Comp)(const void *, const void*))
856 int low, mid, hi, val;
862 mid = (low + hi) / 2;
863 val = Comp(key, index[ mid ]);
885 ** purpose : use index to locate data according to key in 'data'
887 ** parameters : queue pointer 'q', data pointer 'data', Comp comparison
890 ** returns : pointer to data or NULL if could not find it or could
893 ** comments : see Q_Sort for description of 'Comp' function.
897 void *Q_Seek(queue *q, void *data, int (*Comp)(const void *, const void *))
910 idx = Q_BSearch(q, data, Comp);
915 q->cursor = posn_index[idx];
924 ** function : Q_Insert
926 ** purpose : Insert an element into an indexed queue
928 ** parameters : queue pointer 'q', data pointer 'data', Comp comparison
931 ** returns : pointer to data or NULL if could not find it or could
934 ** comments : see Q_Sort for description of 'Comp' function.
935 * WARNING! This code can be very slow since each new
936 * element means a new Q_Sort. Should only be used for
937 * the insertion of the odd element ,not the piecemeal
938 * building of an entire queue.
941 int Q_Insert(queue *q, void *data, int (*Comp)(const void *, const void *))
955 /* read only funcs for iterating through queue. above funcs modify queue */
956 q_iter Q_Iter_Head(queue *q) {
957 return q ? (q_iter)q->head : NULL;
960 q_iter Q_Iter_Tail(queue *q) {
961 return q ? (q_iter)q->tail : NULL;
964 q_iter Q_Iter_Next(q_iter qi) {
965 return qi ? (q_iter)((node*)qi)->next : NULL;
968 q_iter Q_Iter_Prev(q_iter qi) {
969 return qi ? (q_iter)((node*)qi)->prev : NULL;
972 void * Q_Iter_Get(q_iter qi) {
973 return qi ? ((node*)qi)->data : NULL;
976 int Q_Iter_Put(q_iter qi, void* data) {
978 ((node*)qi)->data = data;