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 /* This one moves a chain of elements from (s) to (e) from its
  82  * current position to either before or after element (i)
  83  * if (a,b,x,y) is (prev,next,s,e) then chain is moved before (i)
  84  * if (a,b,x,y) is (next,prev,e,s) then chain is moved after (i) */
  85 #define _RXQMV(i, s, e, a, b, x, y) if (i->a != y) \
  86     (((e->next->prev=s->prev)->next=e->next), ((i->a->b=x)->a=i->a), ((y->b=i)->a=y))
  87
  88 /* Basic remove operation.  Doesn't update the queue item to indicate it's been removed */
  89 #define _RXQR(i) ((_RXQ(i)->prev->next=_RXQ(i)->next)->prev=_RXQ(i)->prev)
  90
  91 /* EXPORTED macros */
  92
  93 /* Initialize a queue head (*q).  A queue head is just a queue element */
  94 #define queue_Init(q) (_RXQ(q))->prev = (_RXQ(q))->next = (_RXQ(q))
  95
  96 /* 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. */
  97 #define queue_Prepend(q,i) _RXQA(_RXQ(q),_RXQ(i),next,prev)
  98
  99 /* 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. */
 100 #define queue_Append(q,i) _RXQA(_RXQ(q),_RXQ(i),prev,next)
 101
 102 /* Insert a queue element (*i2) before another element (*i1) in the queue.  The new queue element should not currently be on any list. */
 103 #define queue_InsertBefore(i1,i2) _RXQA(_RXQ(i1),_RXQ(i2),prev,next)
 104
 105 /* Insert a queue element (*i2) after another element (*i1) in the queue.  The new queue element should not currently be on any list. */
 106 #define queue_InsertAfter(i1,i2) _RXQA(_RXQ(i1),_RXQ(i2),next,prev)
 107
 108 /* Spice the members of (*q2) to the beginning of (*q1), re-initialize (*q2) */
 109 #define queue_SplicePrepend(q1,q2) _RXQS(_RXQ(q1),_RXQ(q2),next,prev)
 110
 111 /* Splice the members of queue (*q2) to the end of (*q1), re-initialize (*q2) */
 112 #define queue_SpliceAppend(q1,q2) _RXQS(_RXQ(q1),_RXQ(q2),prev,next)
 113
 114 /* split the members after i off of queue (*q1), and append them onto queue (*q2) */
 115 #define queue_SplitAfterAppend(q1,q2,i) _RXQSP(_RXQ(q1),_RXQ(q2),_RXQ(i),prev,next,next,prev,_RXQ(q1),_RXQ(i))
 116
 117 /* split the members after i off of queue (*q1), and prepend them onto queue (*q2) */
 118 #define queue_SplitAfterPrepend(q1,q2,i) _RXQSP(_RXQ(q1),_RXQ(q2),_RXQ(i),next,prev,next,prev,_RXQ(i),_RXQ(q1))
 119
 120 /* split the members before i off of queue (*q1), and append them onto queue (*q2) */
 121 #define queue_SplitBeforeAppend(q1,q2,i) _RXQSP(_RXQ(q1),_RXQ(q2),_RXQ(i),prev,next,prev,next,_RXQ(i),_RXQ(q1))
 122
 123 /* split the members before i off of queue (*q1), and prepend them onto queue (*q2) */
 124 #define queue_SplitBeforePrepend(q1,q2,i) _RXQSP(_RXQ(q1),_RXQ(q2),_RXQ(i),next,prev,prev,next,_RXQ(q1),_RXQ(i))
 125
 126 /* Replace the queue (*q1) with the contents of the queue (*q2), re-initialize (*q2) */
 127 #define queue_Replace(q1,q2) if (queue_IsEmpty(q2)) queue_Init(q1); else \
 128     (*_RXQ(q1) = *_RXQ(q2), _RXQ(q1)->next->prev = _RXQ(q1)->prev->next = _RXQ(q1), queue_Init(q2))
 129
 130 /* move a chain of elements beginning at (s) and ending at (e) before node (i) */
 131 #define queue_MoveChainBefore(i, s, e) _RXQMV(_RXQ(i),_RXQ(s),_RXQ(e),prev,next,_RXQ(s),_RXQ(e))
 132
 133 /* move a chain of elements beginning at (s) and ending at (e) after node (i) */
 134 #define queue_MoveChainAfter(i, s, e) _RXQMV(_RXQ(i),_RXQ(s),_RXQ(e),next,prev,_RXQ(e),_RXQ(s))
 135
 136 /* 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 */
 137 #define queue_Remove(i) (_RXQR(i), _RXQ(i)->next = 0)
 138
 139 /* Move the queue element (*i) from it's queue to the end of the queue (*q) */
 140 #define queue_MoveAppend(q,i) (_RXQR(i), queue_Append(q,i))
 141
 142 /* Move the queue element (*i) from it's queue to the head of the queue (*q) */
 143 #define queue_MovePrepend(q,i) (_RXQR(i), queue_Prepend(q,i))
 144
 145 /* Return the first element of a queue, coerced too the specified structure s */
 146 /* Warning:  this returns the queue head, if the queue is empty */
 147 #define queue_First(q,s) ((struct s *)_RXQ(q)->next)
 148
 149 /* Return the last element of a queue, coerced to the specified structure s */
 150 /* Warning:  this returns the queue head, if the queue is empty */
 151 #define queue_Last(q,s) ((struct s *)_RXQ(q)->prev)
 152
 153 /* Return the next element in a queue, beyond the specified item, coerced to the specified structure s */
 154 /* Warning:  this returns the queue head, if the item specified is the last in the queue */
 155 #define queue_Next(i,s) ((struct s *)_RXQ(i)->next)
 156
 157 /* Return the previous element to a specified element of a queue, coerced to the specified structure s */
 158 /* Warning:  this returns the queue head, if the item specified is the first in the queue */
 159 #define queue_Prev(i,s) ((struct s *)_RXQ(i)->prev)
 160
 161 /* 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 */
 162 #define queue_IsEmpty(q) (_RXQ(q)->next == _RXQ(q))
 163
 164 /* Return true if the queue is non-empty, i.e. consists of a queue head plus at least one queue item */
 165 #define queue_IsNotEmpty(q) (_RXQ(q)->next != _RXQ(q))
 166
 167 /* Return true if the queue item is currently in a queue */
 168 /* Returns false if the item was removed from a queue OR is uninitialized (zero) */
 169 #define queue_IsOnQueue(i) (_RXQ(i)->next != 0)
 170
 171 /* Returns true if the item was removed from a queue OR is uninitialized (zero) */
 172 /* Return false if the queue item is currently in a queue */
 173 #define queue_IsNotOnQueue(i) (_RXQ(i)->next == 0)
 174
 175 /* Returns true if the queue item (i) is the first element of the queue (q) */
 176 #define queue_IsFirst(q,i) (_RXQ(q)->first == _RXQ(i))
 177
 178 /* Returns true if the queue item (i) is the last element of the queue (q) */
 179 #define queue_IsLast(q,i) (_RXQ(q)->prev == _RXQ(i))
 180
 181 /* Returns true if the queue item (i) is the end of the queue (q), that is, i is the head of the queue */
 182 #define queue_IsEnd(q,i) (_RXQ(q) == _RXQ(i))
 183
 184 /* Returns false if the queue item (i) is the end of the queue (q), that is, i is the head of the queue */
 185 #define queue_IsNotEnd(q,i) (_RXQ(q) != _RXQ(i))
 186
 187 /* Prototypical loop to scan an entire queue forwards.  q is the queue
 188  * head, qe is the loop variable, next is a variable used to store the
 189  * queue entry for the next iteration of the loop, s is the user's
 190  * queue structure name.  Called using "for (queue_Scan(...)) {...}".
 191  * Note that extra initializers can be added before the queue_Scan,
 192  * and additional expressions afterwards.  So "for (sum=0,
 193  * queue_Scan(...), sum += value) {value = qe->value}" is possible.
 194  * If the current queue entry is deleted, the loop will work
 195  * correctly.  Care must be taken if other elements are deleted or
 196  * inserted.  Next may be updated within the loop to alter the item
 197  * used in the next iteration. */
 198 #define queue_Scan(q, qe, next, s)                      \
 199     (qe) = queue_First(q, s), next = queue_Next(qe, s); \
 200         !queue_IsEnd(q, qe);                            \
 201         (qe) = (next), next = queue_Next(qe, s)
 202
 203 /* similar to queue_Scan except start at element 'start' instead of the beginning */
 204 #define        queue_ScanFrom(q, start, qe, next, s)      \
 205     (qe) = (struct s*)(start), next = queue_Next(qe, s);  \
 206        !queue_IsEnd(q, qe);                               \
 207        (qe) = (next), next = queue_Next(qe, s)
 208
 209 /* This is similar to queue_Scan, but scans from the end of the queue to the beginning.  Next is the previous queue entry.  */
 210 #define queue_ScanBackwards(q, qe, prev, s)             \
 211     (qe) = queue_Last(q, s), prev = queue_Prev(qe, s);  \
 212         !queue_IsEnd(q, qe);                            \
 213         (qe) = prev, prev = queue_Prev(qe, s)
 214
 215 /* This is similar to queue_ScanBackwards, but start at element 'start' instead of the end.  Next is the previous queue entry.  */
 216 #define        queue_ScanBackwardsFrom(q, start, qe, prev, s)  \
 217     (qe) = (struct s*)(start), prev = queue_Prev(qe, s);       \
 218        !queue_IsEnd(q, qe);                                    \
 219        (qe) = prev, prev = queue_Prev(qe, s)
 220
 221 #define queue_Count(q, qe, nqe, s, n)                   \
 222     for (n=0, queue_Scan(q, qe, nqe, s), n++) {}
 223 #endif /* _RX_QUEUE_ */