1 static const char rcsid[] = "#(@) $Id$";
2
3 /*
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
8 */
9
10
11 /*-**************************************************************
12 *
13 * File : q.c
14 *
15 * Author: Peter Yard [1993.01.02] -- 02 Jan 1993
16 *
17 * Disclaimer: This code is released to the public domain.
18 *
19 * Description:
20 * Generic double ended queue (Deque pronounced DEK) for handling
21 * any data types, with sorting.
22 *
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.
26 *
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
32 * or integers etc.
33 *
34 * Enhancements:
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.
39 *
40 * Usage:
41 *
42 * /x init queue x/
43 * queue q;
44 * Q_Init(&q);
45 *
46 * To create a stack :
47 *
48 * Q_PushHead(&q, &mydata1); /x push x/
49 * Q_PushHead(&q, &mydata2);
50 * .....
51 * data_ptr = Q_PopHead(&q); /x pop x/
52 * .....
53 * data_ptr = Q_Head(&q); /x top of stack x/
54 *
55 * To create a FIFO:
56 *
57 * Q_PushHead(&q, &mydata1);
58 * .....
59 * data_ptr = Q_PopTail(&q);
60 *
61 * To create a double list:
62 *
63 * data_ptr = Q_Head(&q);
64 * ....
65 * data_ptr = Q_Next(&q);
66 * data_ptr = Q_Tail(&q);
67 * if (Q_IsEmpty(&q)) ....
68 * .....
69 * data_ptr = Q_Previous(&q);
70 *
71 * To create a sorted list:
72 *
73 * Q_PushHead(&q, &mydata1); /x push x/
74 * Q_PushHead(&q, &mydata2);
75 * .....
76 * if (!Q_Sort(&q, MyFunction))
77 * .. error ..
78 *
79 * /x fill in key field of mydata1.
80 * * NB: Q_Find does linear search
81 * x/
82 *
83 * if (Q_Find(&q, &mydata1, MyFunction))
84 * {
85 * /x found it, queue cursor now at correct record x/
86 * /x can retrieve with x/
87 * data_ptr = Q_Get(&q);
88 *
89 * /x alter data , write back with x/
90 * Q_Put(&q, data_ptr);
91 * }
92 *
93 * /x Search with binary search x/
94 * if (Q_Seek(&q, &mydata, MyFunction))
95 * /x etc x/
96 *
97 *
98 ****************************************************************/
99
100 #ifdef _WIN32
101 #include "xmlrpc_win32.h"
102 #endif
103 #include <stdlib.h>
104 #include "queue.h"
105
106
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 *));
111
112 /* The index: a pointer to pointers */
113
114 static void **index;
115 static datanode **posn_index;
116
117
118 /***
119 *
120 ** function : Q_Init
121 *
122 ** purpose : Initialise queue object and pointers.
123 *
124 ** parameters : 'queue' pointer.
125 *
126 ** returns : True_ if init successful else False_
127 *
128 ** comments :
129 ***/
130
131 int Q_Init(queue *q)
132 {
133 if(q) {
134 q->head = q->tail = NULL;
135 q->cursor = q->head;
136 q->size = 0;
137 q->sorted = False_;
138 }
139
140 return True_;
141 }
142
143 /***
144 *
145 ** function : Q_AtHead
146 *
147 ** purpose : tests if cursor is at head of queue
148 *
149 ** parameters : 'queue' pointer.
150 *
151 ** returns : boolean - True_ is at head else False_
152 *
153 ** comments :
154 *
155 ***/
156
157 int Q_AtHead(queue *q)
158 {
159 return(q && q->cursor == q->head);
160 }
161
162
163 /***
164 *
165 ** function : Q_AtTail
166 *
167 ** purpose : boolean test if cursor at tail of queue
168 *
169 ** parameters : 'queue' pointer to test.
170 *
171 ** returns : True_ or False_
172 *
173 ** comments :
174 *
175 ***/
176
177 int Q_AtTail(queue *q)
178 {
179 return(q && q->cursor == q->tail);
180 }
181
182
183 /***
184 *
185 ** function : Q_IsEmpty
186 *
187 ** purpose : test if queue has nothing in it.
188 *
189 ** parameters : 'queue' pointer
190 *
191 ** returns : True_ if IsEmpty queue, else False_
192 *
193 ** comments :
194 *
195 ***/
196
197 inline int Q_IsEmpty(queue *q)
198 {
199 return(!q || q->size == 0);
200 }
201
202 /***
203 *
204 ** function : Q_Size
205 *
206 ** purpose : return the number of elements in the queue
207 *
208 ** parameters : queue pointer
209 *
210 ** returns : number of elements
211 *
212 ** comments :
213 *
214 ***/
215
216 int Q_Size(queue *q)
217 {
218 return q ? q->size : 0;
219 }
220
221
222 /***
223 *
224 ** function : Q_Head
225 *
226 ** purpose : position queue cursor to first element (head) of queue.
227 *
228 ** parameters : 'queue' pointer
229 *
230 ** returns : pointer to data at head. If queue is IsEmpty returns NULL
231 *
232 ** comments :
233 *
234 ***/
235
236 void *Q_Head(queue *q)
237 {
238 if(Q_IsEmpty(q))
239 return NULL;
240
241 q->cursor = q->head;
242
243 return q->cursor->data;
244 }
245
246
247 /***
248 *
249 ** function : Q_Tail
250 *
251 ** purpose : locate cursor at tail of queue.
252 *
253 ** parameters : 'queue' pointer
254 *
255 ** returns : pointer to data at tail , if queue IsEmpty returns NULL
256 *
257 ** comments :
258 *
259 ***/
260
261 void *Q_Tail(queue *q)
262 {
263 if(Q_IsEmpty(q))
264 return NULL;
265
266 q->cursor = q->tail;
267
268 return q->cursor->data;
269 }
270
271
272 /***
273 *
274 ** function : Q_PushHead
275 *
276 ** purpose : put a data pointer at the head of the queue
277 *
278 ** parameters : 'queue' pointer, void pointer to the data.
279 *
280 ** returns : True_ if success else False_ if unable to push data.
281 *
282 ** comments :
283 *
284 ***/
285
286 int Q_PushHead(queue *q, void *d)
287 {
288 if(q && d) {
289 node *n;
290 datanode *p;
291
292 p = malloc(sizeof(datanode));
293 if(p == NULL)
294 return False_;
295
296 n = q->head;
297
298 q->head = (node*)p;
299 q->head->prev = NULL;
300
301 if(q->size == 0) {
302 q->head->next = NULL;
303 q->tail = q->head;
304 }
305 else {
306 q->head->next = (datanode*)n;
307 n->prev = q->head;
308 }
309
310 q->head->data = d;
311 q->size++;
312
313 q->cursor = q->head;
314
315 q->sorted = False_;
316
317 return True_;
318 }
319 return False_;
320 }
321
322
323
324 /***
325 *
326 ** function : Q_PushTail
327 *
328 ** purpose : put a data element pointer at the tail of the queue
329 *
330 ** parameters : queue pointer, pointer to the data
331 *
332 ** returns : True_ if data pushed, False_ if data not inserted.
333 *
334 ** comments :
335 *
336 ***/
337
338 int Q_PushTail(queue *q, void *d)
339 {
340 if(q && d) {
341 node *p;
342 datanode *n;
343
344 n = malloc(sizeof(datanode));
345 if(n == NULL)
346 return False_;
347
348 p = q->tail;
349 q->tail = (node *)n;
350
351 if(q->size == 0) {
352 q->tail->prev = NULL;
353 q->head = q->tail;
354 }
355 else {
356 q->tail->prev = (datanode *)p;
357 p->next = q->tail;
358 }
359
360 q->tail->next = NULL;
361
362 q->tail->data = d;
363 q->cursor = q->tail;
364 q->size++;
365
366 q->sorted = False_;
367
368 return True_;
369 }
370 return False_;
371 }
372
373
374
375 /***
376 *
377 ** function : Q_PopHead
378 *
379 ** purpose : remove and return the top element at the head of the
380 * queue.
381 *
382 ** parameters : queue pointer
383 *
384 ** returns : pointer to data element or NULL if queue is IsEmpty.
385 *
386 ** comments :
387 *
388 ***/
389
390 void *Q_PopHead(queue *q)
391 {
392 datanode *n;
393 void *d;
394
395 if(Q_IsEmpty(q))
396 return NULL;
397
398 d = q->head->data;
399 n = q->head->next;
400 free(q->head);
401
402 q->size--;
403
404 if(q->size == 0)
405 q->head = q->tail = q->cursor = NULL;
406 else {
407 q->head = (node *)n;
408 q->head->prev = NULL;
409 q->cursor = q->head;
410 }
411
412 q->sorted = False_;
413
414 return d;
415 }
416
417
418 /***
419 *
420 ** function : Q_PopTail
421 *
422 ** purpose : remove element from tail of queue and return data.
423 *
424 ** parameters : queue pointer
425 *
426 ** returns : pointer to data element that was at tail. NULL if queue
427 * IsEmpty.
428 *
429 ** comments :
430 *
431 ***/
432
433 void *Q_PopTail(queue *q)
434 {
435 datanode *p;
436 void *d;
437
438 if(Q_IsEmpty(q))
439 return NULL;
440
441 d = q->tail->data;
442 p = q->tail->prev;
443 free(q->tail);
444 q->size--;
445
446 if(q->size == 0)
447 q->head = q->tail = q->cursor = NULL;
448 else {
449 q->tail = (node *)p;
450 q->tail->next = NULL;
451 q->cursor = q->tail;
452 }
453
454 q->sorted = False_;
455
456 return d;
457 }
458
459
460
461 /***
462 *
463 ** function : Q_Next
464 *
465 ** purpose : Move to the next element in the queue without popping
466 *
467 ** parameters : queue pointer.
468 *
469 ** returns : pointer to data element of new element or NULL if end
470 * of the queue.
471 *
472 ** comments : This uses the cursor for the current position. Q_Next
473 * only moves in the direction from the head of the queue
474 * to the tail.
475 ***/
476
477 void *Q_Next(queue *q)
478 {
479 if(!q)
480 return NULL;
481
482 if(!q->cursor || q->cursor->next == NULL)
483 return NULL;
484
485 q->cursor = (node *)q->cursor->next;
486
487 return q->cursor->data ;
488 }
489
490
491
492 /***
493 *
494 ** function : Q_Previous
495 *
496 ** purpose : Opposite of Q_Next. Move to next element closer to the
497 * head of the queue.
498 *
499 ** parameters : pointer to queue
500 *
501 ** returns : pointer to data of new element else NULL if queue IsEmpty
502 *
503 ** comments : Makes cursor move towards the head of the queue.
504 *
505 ***/
506
507 void *Q_Previous(queue *q)
508 {
509 if(!q)
510 return NULL;
511
512 if(q->cursor->prev == NULL)
513 return NULL;
514
515 q->cursor = (node *)q->cursor->prev;
516
517 return q->cursor->data;
518 }
519
520
521 void *Q_Iter_Del(queue *q, q_iter iter)
522 {
523 void *d;
524 datanode *n, *p;
525
526 if(!q)
527 return NULL;
528
529 if(iter == NULL)
530 return NULL;
531
532 if(iter == (q_iter)q->head)
533 return Q_PopHead(q);
534
535 if(iter == (q_iter)q->tail)
536 return Q_PopTail(q);
537
538 n = ((node*)iter)->next;
539 p = ((node*)iter)->prev;
540 d = ((node*)iter)->data;
541
542 free(iter);
543
544 if(p) {
545 p->next = n;
546 }
547 if (q->cursor == (node*)iter) {
548 if (p) {
549 q->cursor = p;
550 } else {
551 q->cursor = n;
552 }
553 }
554
555
556 if (n != NULL) {
557 n->prev = p;
558 }
559
560 q->size--;
561
562 q->sorted = False_;
563
564 return d;
565 }
566
567
568
569 /***
570 *
571 ** function : Q_DelCur
572 *
573 ** purpose : Delete the current queue element as pointed to by
574 * the cursor.
575 *
576 ** parameters : queue pointer
577 *
578 ** returns : pointer to data element.
579 *
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.
583 *
584 ***/
585
586 void *Q_DelCur(queue* q) {
587 if(q) {
588 return Q_Iter_Del(q, (q_iter)q->cursor);
589 }
590 return 0;
591 }
592
593
594 /***
595 *
596 ** function : Q_Destroy
597 *
598 ** purpose : Free all queue resources
599 *
600 ** parameters : queue pointer
601 *
602 ** returns : null.
603 *
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.
607 *
608 ***/
609
610 void Q_Destroy(queue *q)
611 {
612 while(!Q_IsEmpty(q)) {
613 Q_PopHead(q);
614 }
615 }
616
617
618 /***
619 *
620 ** function : Q_Get
621 *
622 ** purpose : get the pointer to the data at the cursor location
623 *
624 ** parameters : queue pointer
625 *
626 ** returns : data element pointer
627 *
628 ** comments :
629 *
630 ***/
631
632 void *Q_Get(queue *q)
633 {
634 if(!q)
635 return NULL;
636
637 if(q->cursor == NULL)
638 return NULL;
639 return q->cursor->data;
640 }
641
642
643
644 /***
645 *
646 ** function : Q_Put
647 *
648 ** purpose : replace pointer to data with new pointer to data.
649 *
650 ** parameters : queue pointer, data pointer
651 *
652 ** returns : boolean- True_ if successful, False_ if cursor at NULL
653 *
654 ** comments :
655 *
656 ***/
657
658 int Q_Put(queue *q, void *data)
659 {
660 if(q && data) {
661 if(q->cursor == NULL)
662 return False_;
663
664 q->cursor->data = data;
665 return True_;
666 }
667 return False_;
668 }
669
670
671 /***
672 *
673 ** function : Q_Find
674 *
675 ** purpose : Linear search of queue for match with key in *data
676 *
677 ** parameters : queue pointer q, data pointer with data containing key
678 * comparison function here called Comp.
679 *
680 ** returns : True_ if found , False_ if not in queue.
681 *
682 ** comments : Useful for small queues that are constantly changing
683 * and would otherwise need constant sorting with the
684 * Q_Seek function.
685 * For description of Comp see Q_Sort.
686 * Queue cursor left on position found item else at end.
687 *
688 ***/
689
690 int Q_Find(queue *q, void *data,
691 int (*Comp)(const void *, const void *))
692 {
693 void *d;
694
695 if (q == NULL) {
696 return False_;
697 }
698
699 d = Q_Head(q);
700 do {
701 if(Comp(d, data) == 0)
702 return True_;
703 d = Q_Next(q);
704 } while(!Q_AtTail(q));
705
706 if(Comp(d, data) == 0)
707 return True_;
708
709 return False_;
710 }
711
712 /*======== Sorted Queue and Index functions ========= */
713
714
715 static void QuickSort(void *list[], int low, int high,
716 int (*Comp)(const void *, const void *))
717 {
718 int flag = 1, i, j;
719 void *key, *temp;
720
721 if(low < high) {
722 i = low;
723 j = high + 1;
724
725 key = list[ low ];
726
727 while(flag) {
728 i++;
729 while(Comp(list[i], key) < 0)
730 i++;
731
732 j--;
733 while(Comp(list[j], key) > 0)
734 j--;
735
736 if(i < j) {
737 temp = list[i];
738 list[i] = list[j];
739 list[j] = temp;
740 }
741 else flag = 0;
742 }
743
744 temp = list[low];
745 list[low] = list[j];
746 list[j] = temp;
747
748 QuickSort(list, low, j-1, Comp);
749 QuickSort(list, j+1, high, Comp);
750 }
751 }
752
753
754 /***
755 *
756 ** function : Q_Sort
757 *
758 ** purpose : sort the queue and allow index style access.
759 *
760 ** parameters : queue pointer, comparison function compatible with
761 * with 'qsort'.
762 *
763 ** returns : True_ if sort succeeded. False_ if error occurred.
764 *
765 ** comments : Comp function supplied by caller must return
766 * -1 if data1 < data2
767 * 0 if data1 == data2
768 * +1 if data1 > data2
769 *
770 * for Comp(data1, data2)
771 *
772 * If queue is already sorted it frees the memory of the
773 * old index and starts again.
774 *
775 ***/
776
777 int Q_Sort(queue *q, int (*Comp)(const void *, const void *))
778 {
779 int i;
780 void *d;
781 datanode *dn;
782
783 /* if already sorted free memory for tag array */
784
785 if(q->sorted) {
786 free(index);
787 free(posn_index);
788 q->sorted = False_;
789 }
790
791 /* Now allocate memory of array, array of pointers */
792
793 index = malloc(q->size * sizeof(q->cursor->data));
794 if(index == NULL)
795 return False_;
796
797 posn_index = malloc(q->size * sizeof(q->cursor));
798 if(posn_index == NULL) {
799 free(index);
800 return False_;
801 }
802
803 /* Walk queue putting pointers into array */
804
805 d = Q_Head(q);
806 for(i=0; i < q->size; i++) {
807 index[i] = d;
808 posn_index[i] = q->cursor;
809 d = Q_Next(q);
810 }
811
812 /* Now sort the index */
813
814 QuickSort(index, 0, q->size - 1, Comp);
815
816 /* Rearrange the actual queue into correct order */
817
818 dn = q->head;
819 i = 0;
820 while(dn != NULL) {
821 dn->data = index[i++];
822 dn = dn->next;
823 }
824
825 /* Re-position to original element */
826
827 if(d != NULL)
828 Q_Find(q, d, Comp);
829 else Q_Head(q);
830
831 q->sorted = True_;
832
833 return True_;
834 }
835
836
837 /***
838 *
839 ** function : Q_BSearch
840 *
841 ** purpose : binary search of queue index for node containing key
842 *
843 ** parameters : queue pointer 'q', data pointer of key 'key',
844 * Comp comparison function.
845 *
846 ** returns : integer index into array of node pointers,
847 * or -1 if not found.
848 *
849 ** comments : see Q_Sort for description of 'Comp' function.
850 *
851 ***/
852
853 static int Q_BSearch( queue *q, void *key,
854 int (*Comp)(const void *, const void*))
855 {
856 int low, mid, hi, val;
857
858 low = 0;
859 hi = q->size - 1;
860
861 while(low <= hi) {
862 mid = (low + hi) / 2;
863 val = Comp(key, index[ mid ]);
864
865 if(val < 0)
866 hi = mid - 1;
867
868 else if(val > 0)
869 low = mid + 1;
870
871 else /* Success */
872 return mid;
873 }
874
875 /* Not Found */
876
877 return -1;
878 }
879
880
881 /***
882 *
883 ** function : Q_Seek
884 *
885 ** purpose : use index to locate data according to key in 'data'
886 *
887 ** parameters : queue pointer 'q', data pointer 'data', Comp comparison
888 * function.
889 *
890 ** returns : pointer to data or NULL if could not find it or could
891 * not sort queue.
892 *
893 ** comments : see Q_Sort for description of 'Comp' function.
894 *
895 ***/
896
897 void *Q_Seek(queue *q, void *data, int (*Comp)(const void *, const void *))
898 {
899 int idx;
900
901 if (q == NULL) {
902 return NULL;
903 }
904
905 if(!q->sorted) {
906 if(!Q_Sort(q, Comp))
907 return NULL;
908 }
909
910 idx = Q_BSearch(q, data, Comp);
911
912 if(idx < 0)
913 return NULL;
914
915 q->cursor = posn_index[idx];
916
917 return index[idx];
918 }
919
920
921
922 /***
923 *
924 ** function : Q_Insert
925 *
926 ** purpose : Insert an element into an indexed queue
927 *
928 ** parameters : queue pointer 'q', data pointer 'data', Comp comparison
929 * function.
930 *
931 ** returns : pointer to data or NULL if could not find it or could
932 * not sort queue.
933 *
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.
939 ***/
940
941 int Q_Insert(queue *q, void *data, int (*Comp)(const void *, const void *))
942 {
943 if (q == NULL) {
944 return False_;
945 }
946
947 Q_PushHead(q, data);
948
949 if(!Q_Sort(q, Comp))
950 return False_;
951
952 return True_;
953 }
954
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;
958 }
959
960 q_iter Q_Iter_Tail(queue *q) {
961 return q ? (q_iter)q->tail : NULL;
962 }
963
964 q_iter Q_Iter_Next(q_iter qi) {
965 return qi ? (q_iter)((node*)qi)->next : NULL;
966 }
967
968 q_iter Q_Iter_Prev(q_iter qi) {
969 return qi ? (q_iter)((node*)qi)->prev : NULL;
970 }
971
972 void * Q_Iter_Get(q_iter qi) {
973 return qi ? ((node*)qi)->data : NULL;
974 }
975
976 int Q_Iter_Put(q_iter qi, void* data) {
977 if(qi) {
978 ((node*)qi)->data = data;
979 return True_;
980 }
981 return False_;
982 }