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