Annotation of embedaddon/php/ext/xmlrpc/libxmlrpc/queue.c, revision 1.1
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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[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