src/opr/queue.h

   1 /*
   2  * Copyright (c) 2010 Your File System Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
  14  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  15  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  16  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  17  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  18  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  19  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  20  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  22  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  23  */
  24
  25 /* A better queue implementation.
  26  *
  27  * This differs from the original queue implementation in that that would
  28  * only allow a structure to be threaded onto a single queue. This permits
  29  * a given object to be on multiple queues, providing that each queue has
  30  * a place in the structure definition.
  31  */
  32
  33 #ifndef OPENAFS_OPR_QUEUE_H
  34 #define OPENAFS_OPR_QUEUE_H 1
  35
  36 #ifndef KERNEL
  37 #include <stdlib.h>
  38 #else
  39 #ifndef NULL
  40 #define NULL (void *)0
  41 #endif
  42 #endif
  43
  44 struct opr_queue {
  45    struct opr_queue *next;
  46    struct opr_queue *prev;
  47 };
  48
  49 #define opr_queue_Scan(head, cursor) \
  50     cursor = (head)->next; cursor != (head); cursor = cursor->next
  51
  52 #define opr_queue_ScanSafe(head, cursor, store) \
  53     cursor = (head)->next, store = cursor->next; \
  54     cursor != (head); \
  55     cursor = store, store = store->next
  56
  57 #define opr_queue_ScanBackwards(head, cursor) \
  58     cursor = (head)->prev; cursor != (head); cursor = cursor->prev
  59
  60 #define opr_queue_ScanBackwardsSafe(head, cursor, store) \
  61    cursor = (head)->prev, store = cursor->prev; \
  62    cursor != (head); \
  63    cursor = store, store = store->prev
  64
  65 static_inline void
  66 opr_queue_Zero(struct opr_queue *q) {
  67     q->prev = q->next = NULL;
  68 }
  69
  70 static_inline void
  71 opr_queue_Init(struct opr_queue *q) {
  72     q->prev = q->next = q;
  73 }
  74
  75 static_inline void
  76 opr_queue_add(struct opr_queue *element,
  77               struct opr_queue *before, struct opr_queue *after) {
  78    after->prev = element;
  79    element->next = after;
  80    element->prev = before;
  81    before->next = element;
  82 }
  83
  84 static_inline void
  85 opr_queue_Append(struct opr_queue *queue, struct opr_queue *element) {
  86     opr_queue_add(element, queue->prev, queue);
  87 }
  88
  89 static_inline void
  90 opr_queue_Prepend(struct opr_queue *queue, struct opr_queue *element) {
  91     opr_queue_add(element, queue, queue->next);
  92 }
  93
  94 static_inline void
  95 opr_queue_InsertBefore(struct opr_queue *exist, struct opr_queue *adding) {
  96     /* This may seem back to front, but take a list A, B, C where we want
  97      * to add 1 before B. So, we're adding 1 with A the element before,
  98      * and B the element after, hence the following: */
  99     opr_queue_add(adding, exist->prev, exist);
 100 }
 101
 102 static_inline void
 103 opr_queue_InsertAfter(struct opr_queue *exist, struct opr_queue *adding) {
 104     opr_queue_add(adding, exist, exist->next);
 105 }
 106
 107 static_inline void
 108 opr_queue_Remove(struct opr_queue *element) {
 109     element->next->prev = element->prev;
 110     element->prev->next = element->next;
 111     element->prev = NULL;
 112     element->next = NULL;
 113 }
 114
 115 static_inline int
 116 opr_queue_IsEmpty(struct opr_queue *q) {
 117     return (q->prev == q);
 118 }
 119
 120 static_inline int
 121 opr_queue_IsOnQueue(struct opr_queue *q) {
 122     return (q->prev != NULL);
 123 }
 124
 125 static_inline int
 126 opr_queue_IsEnd(struct opr_queue *q, struct opr_queue *cursor) {
 127     return (cursor->next == q);
 128 }
 129
 130 static_inline int
 131 opr_queue_Count(struct opr_queue *q) {
 132     struct opr_queue *cursor;
 133     int n = 0;
 134
 135     for (opr_queue_Scan(q, cursor)) {
 136         n++;
 137     }
 138     return n;
 139 }
 140
 141 static_inline void
 142 opr_queue_Swap(struct opr_queue *a, struct opr_queue *b)
 143 {
 144     struct opr_queue tq = *b;
 145
 146     if (a->prev == a) {
 147         b->prev = b->next = b;
 148     } else {
 149         *b = *a;
 150         b->prev->next = b;
 151         b->next->prev = b;
 152     }
 153
 154     if (tq.prev == b) {
 155         a->prev = a->next = a;
 156     } else {
 157         *a = tq;
 158         a->prev->next = a;
 159         a->next->prev = a;
 160     }
 161 }
 162
 163 /* Remove the members before pivot from Q1, and append them to Q2 */
 164
 165 static_inline void
 166 opr_queue_SplitBeforeAppend(struct opr_queue *q1, struct opr_queue *q2,
 167                             struct opr_queue *pivot) {
 168
 169     if (q1 == pivot->prev)
 170         return;
 171     /* Add ourselves to the end of list 2 */
 172     q2->prev->next = q1->next; /* end of list 2, is now the start of list 1 */
 173     q1->next->prev = q2->prev;
 174     pivot->prev->next = q2; /* entry before the pivot is it at end of q2 */
 175     q2->prev = pivot->prev;
 176
 177     /* Pull ourselves out of list q1. */
 178     q1->next = pivot;
 179     pivot->prev = q1;
 180 }
 181
 182 /* Remove the members after the pivot from Q1, and prepend them onto Q2 */
 183 static_inline void
 184 opr_queue_SplitAfterPrepend(struct opr_queue *q1, struct opr_queue *q2,
 185                             struct opr_queue *pivot) {
 186
 187     if (q1 == pivot->next)
 188         return;
 189
 190     /* start of q2 has last element of q1 before it */
 191     q2->next->prev = q1->prev;
 192     q1->prev->next = q2->next;
 193     /* item that we're breaking at (pivot->next) is at start of q2 */
 194     q2->next = pivot->next;
 195     pivot->next->prev = q2;
 196
 197     /* Q1 now ends after pivot */
 198     pivot->next = q1;
 199     q1->prev = pivot;
 200 }
 201
 202 static_inline void
 203 opr_queue_SpliceAppend(struct opr_queue *target, struct opr_queue *source)
 204 {
 205
 206     if (source->next == source)
 207         return;
 208
 209     /* Stick the contents of source onto the end of target */
 210     target->prev->next = source->next;
 211     source->next->prev = target->prev;
 212     source->prev->next = target;
 213     target->prev = source->prev;
 214
 215     /* Reinitialise source */
 216     source->next = source->prev = source;
 217 }
 218
 219 static_inline void
 220 opr_queue_SplicePrepend(struct opr_queue *target, struct opr_queue *source)
 221 {
 222
 223     if (source->next == source)
 224         return;
 225
 226     /* Contents of source go onto the beginning of target */
 227     target->next->prev = source->prev;
 228     source->prev->next = target->next;
 229     source->next->prev = target;
 230     target->next = source->next;
 231
 232     /* Reinitialise source */
 233     source->next = source->prev = source;
 234 }
 235
 236 #define opr_queue_Entry(queue, structure, member) \
 237     ((structure *)((char *)(queue)-(char *)(&((structure *)NULL)->member)))
 238
 239 #define opr_queue_First(queue, structure, member) \
 240     opr_queue_Entry((queue)->next, structure, member)
 241
 242 #define opr_queue_Last(queue, structure, member) \
 243     opr_queue_Entry((queue)->prev, structure, member)
 244
 245 #define opr_queue_Next(entry, structure, member) \
 246     opr_queue_Entry((entry)->next, structure, member)
 247
 248 #define opr_queue_Prev(entry, structure, member) \
 249     opr_queue_Entry((entry)->prev, structure, member)
 250
 251 #endif