src/rx/rx_queue.h

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 /* queue.h:  Simple double linked queue package */
  11
  12 /* It's simple, but, I think, it's pretty nice to use, and it's *very* efficient (especially so with a good optimizing compiler).   WARNING:  Since these functions are implemented as macros, it is best to use only *VERY* simple expressions for all parameters.  Double warning:  this uses a lot of type coercion, so you have to be *REAL* careful.  But C doesn't give me a reasonable alternative (i.e.. in-line expanded functions). */
  13
  14 #ifndef _RX_QUEUE_
  15 #define _RX_QUEUE_
  16
  17 /* A queue head is simply a queue element linked to itself (i.e. the null queue is a queue with exactly one element).  Queue elements can be prepended to any structure:  these macros assume that the structure passed is coercible to a (struct q).  Since all of these operations are implemented as macros, the user should beware of side-effects in macro parameters.  Also beware that implicit casting of queue types occurs, so be careful to supply the right parameters at the right times! */
  18 #undef queue                    /* Since some OS (ultrix, etc) have their own */
  19 struct rx_queue {
  20     struct rx_queue *prev;
  21     struct rx_queue *next;
  22 };
  23
  24 /* Sample usages:
  25
  26 (*A queue head:*)
  27 struct rx_queue myqueue;
  28
  29 (*An element for my queue type:*)
  30 struct myelement {
  31     struct rx_queue queue_header;
  32     int mydata;
  33 };
  34
  35 (*Initialize the queue:*)
  36 queue_Init(&myqueue);
  37
  38 (*Append a bunch of items to the queue:*)
  39 for (i=0; i<20; i++) {
  40     struct myelement *item = (struct myelement *) malloc(sizeof *item);
  41     item->mydata = i;
  42     queue_Append(&myqueue, item);
  43 }
  44
  45 (*Scan a queue, incrementing the mydata field in each element, and removing any entries for which mydata>MAX.  Nqe is used by the scan to hold the next queue element, so the current queue element may be removed safely. *)
  46 struct myelement *qe, *nqe;
  47 for (queue_Scan(&myqueue, qe, nqe, myelement)) {
  48     if (++qe->mydata > MAX)  queue_Remove(qe);
  49 }
  50
  51 (* Count the number of elements in myqueue.  The queue_Scan macro specifies all three elements of the for loop, but an additional initializer and an additional incrementor can be added *)
  52 struct myelement *qe, *nqe;
  53 int n;
  54 for (n=0, queue_Scan(&myqueue, qe, nqe, myelement), n++) {}
  55
  56 */
  57
  58 /* INTERNAL macros */
  59
  60 /* This one coerces the user's structure to a queue element (or queue head) */
  61 #define _RXQ(x) ((struct rx_queue *)(x))
  62
  63 /* This one adds a queue element (i) before or after another queue element (or queue head) (q), doubly linking everything together.  It's called by the user usable macros, below.  If (a,b) is (next,prev) then the element i is linked after q; if it is (prev,next) then it is linked before q */
  64 /* N.B.  I don't think it is possible to write this expression, correctly, with less than one comma (you can easily write an alternative expression with no commas that works with most or all compilers, but it's not clear that it really is un-ambiguous, legal C-code). */
  65 #define _RXQA(q,i,a,b) (((i->a=q->a)->b=i)->b=q, q->a=i)
  66
  67 /* These ones splice two queues together.  If (a,b) is (next,prev) then (*q2) is prepended to (*q1), otherwise (*q2) is appended to (*q1). */
  68 #define _RXQS(q1,q2,a,b) if (queue_IsEmpty(q2)); else \
  69     ((((q2->a->b=q1)->a->b=q2->b)->a=q1->a, q1->a=q2->a), queue_Init(q2))
  70
  71 /* This one removes part of queue (*q1) and attaches it to queue (*q2).
  72  * If (a,b) is (next,prev) then the subchain is prepended to (*q2),
  73  * otherwise the subchain is appended to (*q2).
  74  * If (c,d) is (prev,next) then the subchain is the elements in (*q1) before (i),
  75  * otherwise the subchain is the elements in (*q1) after (i).
  76  * If (x,y) is (q1,i) then operation is either BeforePrepend of AfterAppend.
  77  * If (x,y) is (i,q1) then operation is either BeforeAppend or AfterPrepend. */
  78 #define _RXQSP(q1,q2,i,a,b,c,d,x,y) if (!queue_IsEnd(q1,i->c)) \
  79     (((y->b->a=q2->a)->b=y->b), ((x->a->b=q2)->a=x->a), ((i->c=q1)->d=i))
  80
  81 /* Basic remove operation.  Doesn't update the queue item to indicate it's been removed */
  82 #define _RXQR(i) ((_RXQ(i)->prev->next=_RXQ(i)->next)->prev=_RXQ(i)->prev)
  83
  84 /* EXPORTED macros */
  85
  86 /* Initialize a queue head (*q).  A queue head is just a queue element */
  87 #define queue_Init(q) (_RXQ(q))->prev = (_RXQ(q))->next = (_RXQ(q))
  88
  89 /* Prepend a queue element (*i) to the head of the queue, after the queue head (*q).  The new queue element should not currently be on any list. */
  90 #define queue_Prepend(q,i) _RXQA(_RXQ(q),_RXQ(i),next,prev)
  91
  92 /* Append a queue element (*i) to the end of the queue, before the queue head (*q).  The new queue element should not currently be on any list. */
  93 #define queue_Append(q,i) _RXQA(_RXQ(q),_RXQ(i),prev,next)
  94
  95 /* Insert a queue element (*i2) before another element (*i1) in the queue.  The new queue element should not currently be on any list. */
  96 #define queue_InsertBefore(i1,i2) _RXQA(_RXQ(i1),_RXQ(i2),prev,next)
  97
  98 /* Insert a queue element (*i2) after another element (*i1) in the queue.  The new queue element should not currently be on any list. */
  99 #define queue_InsertAfter(i1,i2) _RXQA(_RXQ(i1),_RXQ(i2),next,prev)
 100
 101 /* Spice the members of (*q2) to the beginning of (*q1), re-initialize (*q2) */
 102 #define queue_SplicePrepend(q1,q2) _RXQS(_RXQ(q1),_RXQ(q2),next,prev)
 103
 104 /* Splice the members of queue (*q2) to the end of (*q1), re-initialize (*q2) */
 105 #define queue_SpliceAppend(q1,q2) _RXQS(_RXQ(q1),_RXQ(q2),prev,next)
 106
 107 /* split the members after i off of queue (*q1), and append them onto queue (*q2) */
 108 #define queue_SplitAfterAppend(q1,q2,i) _RXQSP(_RXQ(q1),_RXQ(q2),_RXQ(i),prev,next,next,prev,_RXQ(q1),_RXQ(i))
 109
 110 /* split the members after i off of queue (*q1), and prepend them onto queue (*q2) */
 111 #define queue_SplitAfterPrepend(q1,q2,i) _RXQSP(_RXQ(q1),_RXQ(q2),_RXQ(i),next,prev,next,prev,_RXQ(i),_RXQ(q1))
 112
 113 /* split the members before i off of queue (*q1), and append them onto queue (*q2) */
 114 #define queue_SplitBeforeAppend(q1,q2,i) _RXQSP(_RXQ(q1),_RXQ(q2),_RXQ(i),prev,next,prev,next,_RXQ(i),_RXQ(q1))
 115
 116 /* split the members before i off of queue (*q1), and prepend them onto queue (*q2) */
 117 #define queue_SplitBeforePrepend(q1,q2,i) _RXQSP(_RXQ(q1),_RXQ(q2),_RXQ(i),next,prev,prev,next,_RXQ(q1),_RXQ(i))
 118
 119 /* Replace the queue (*q1) with the contents of the queue (*q2), re-initialize (*q2) */
 120 #define queue_Replace(q1,q2) if (queue_IsEmpty(q2)) queue_Init(q1); else \
 121     (*_RXQ(q1) = *_RXQ(q2), _RXQ(q1)->next->prev = _RXQ(q1)->prev->next = _RXQ(q1), queue_Init(q2))
 122
 123 /* Remove a queue element (*i) from it's queue.  The next field is 0'd, so that any further use of this q entry will hopefully cause a core dump.  Multiple removes of the same queue item are not supported */
 124 #define queue_Remove(i) (_RXQR(i), _RXQ(i)->next = 0)
 125
 126 /* Move the queue element (*i) from it's queue to the end of the queue (*q) */
 127 #define queue_MoveAppend(q,i) (_RXQR(i), queue_Append(q,i))
 128
 129 /* Move the queue element (*i) from it's queue to the head of the queue (*q) */
 130 #define queue_MovePrepend(q,i) (_RXQR(i), queue_Prepend(q,i))
 131
 132 /* Return the first element of a queue, coerced too the specified structure s */
 133 /* Warning:  this returns the queue head, if the queue is empty */
 134 #define queue_First(q,s) ((struct s *)_RXQ(q)->next)
 135
 136 /* Return the last element of a queue, coerced to the specified structure s */
 137 /* Warning:  this returns the queue head, if the queue is empty */
 138 #define queue_Last(q,s) ((struct s *)_RXQ(q)->prev)
 139
 140 /* Return the next element in a queue, beyond the specified item, coerced to the specified structure s */
 141 /* Warning:  this returns the queue head, if the item specified is the last in the queue */
 142 #define queue_Next(i,s) ((struct s *)_RXQ(i)->next)
 143
 144 /* Return the previous element to a specified element of a queue, coerced to the specified structure s */
 145 /* Warning:  this returns the queue head, if the item specified is the first in the queue */
 146 #define queue_Prev(i,s) ((struct s *)_RXQ(i)->prev)
 147
 148 /* Return true if the queue is empty, i.e. just consists of a queue head.  The queue head must have been initialized some time prior to this call */
 149 #define queue_IsEmpty(q) (_RXQ(q)->next == _RXQ(q))
 150
 151 /* Return true if the queue is non-empty, i.e. consists of a queue head plus at least one queue item */
 152 #define queue_IsNotEmpty(q) (_RXQ(q)->next != _RXQ(q))
 153
 154 /* Return true if the queue item is currently in a queue */
 155 /* Returns false if the item was removed from a queue OR is uninitialized (zero) */
 156 #define queue_IsOnQueue(i) (_RXQ(i)->next != 0)
 157
 158 /* Returns true if the queue item (i) is the first element of the queue (q) */
 159 #define queue_IsFirst(q,i) (_RXQ(q)->first == _RXQ(i))
 160
 161 /* Returns true if the queue item (i) is the last element of the queue (q) */
 162 #define queue_IsLast(q,i) (_RXQ(q)->prev == _RXQ(i))
 163
 164 /* Returns true if the queue item (i) is the end of the queue (q), that is, i is the head of the queue */
 165 #define queue_IsEnd(q,i) (_RXQ(q) == _RXQ(i))
 166
 167 /* Prototypical loop to scan an entire queue forwards.  q is the queue
 168  * head, qe is the loop variable, next is a variable used to store the
 169  * queue entry for the next iteration of the loop, s is the user's
 170  * queue structure name.  Called using "for (queue_Scan(...)) {...}".
 171  * Note that extra initializers can be added before the queue_Scan,
 172  * and additional expressions afterwards.  So "for (sum=0,
 173  * queue_Scan(...), sum += value) {value = qe->value}" is possible.
 174  * If the current queue entry is deleted, the loop will work
 175  * correctly.  Care must be taken if other elements are deleted or
 176  * inserted.  Next may be updated within the loop to alter the item
 177  * used in the next iteration. */
 178 #define queue_Scan(q, qe, next, s)                      \
 179     (qe) = queue_First(q, s), next = queue_Next(qe, s); \
 180         !queue_IsEnd(q, qe);                            \
 181         (qe) = (next), next = queue_Next(qe, s)
 182
 183 /* This is similar to queue_Scan, but scans from the end of the queue to the beginning.  Next is the previous queue entry.  */
 184 #define queue_ScanBackwards(q, qe, prev, s)             \
 185     (qe) = queue_Last(q, s), prev = queue_Prev(qe, s);  \
 186         !queue_IsEnd(q, qe);                            \
 187         (qe) = prev, prev = queue_Prev(qe, s)
 188
 189 #define queue_Count(q, qe, nqe, s, n)                   \
 190     for (n=0, queue_Scan(q, qe, nqe, s), n++) {}
 191 #endif /* _RX_QUEUE_ */