![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to queue.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / xmlrpc / libxmlrpc|
Return to queue.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / xmlrpc / libxmlrpc |
1.1 misho 1: static const char rcsid[] = "#(@) $Id: queue.c 87765 2002-07-05 04:43:55Z danda $";
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: }