← Back to branch summary

~ubuntu-branches/ubuntu/hardy/php5/hardy-updates

« back to all changes in this revision

Viewing changes to ext/xmlrpc/libxmlrpc/queue.c

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-10-09 03:14:32 UTC
  • Revision ID: james.westby@ubuntu.com-20051009031432-kspik3lobxstafv9
Tags: upstream-5.0.5
Import upstream version 5.0.5

Show diffs side-by-side

added added

removed removed

Lines of Context:
ext/xmlrpc/libxmlrpc/queue.c
 
1
static const char rcsid[] = "#(@) $Id: queue.c,v 1.4 2002/07/05 04:43:53 danda Exp $";
 
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
}