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 /* Remove the members before pivot from Q1, and append them to Q2 */
 142
 143 static_inline void
 144 opr_queue_SplitBeforeAppend(struct opr_queue *q1, struct opr_queue *q2,
 145                             struct opr_queue *pivot) {
 146
 147     if (q1 == pivot->prev)
 148         return;
 149     /* Add ourselves to the end of list 2 */
 150     q2->prev->next = q1->next; /* end of list 2, is now the start of list 1 */
 151     q1->next->prev = q2->prev;
 152     pivot->prev->next = q2; /* entry before the pivot is it at end of q2 */
 153     q2->prev = pivot->prev;
 154
 155     /* Pull ourselves out of list q1. */
 156     q1->next = pivot;
 157     pivot->prev = q1;
 158 }
 159
 160 /* Remove the members after the pivot from Q1, and prepend them onto Q2 */
 161 static_inline void
 162 opr_queue_SplitAfterPrepend(struct opr_queue *q1, struct opr_queue *q2,
 163                             struct opr_queue *pivot) {
 164
 165     if (q1 == pivot->next)
 166         return;
 167
 168     /* start of q2 has last element of q1 before it */
 169     q2->next->prev = q1->prev;
 170     q1->prev->next = q2->next;
 171     /* item that we're breaking at (pivot->next) is at start of q2 */
 172     q2->next = pivot->next;
 173     pivot->next->prev = q2;
 174
 175     /* Q1 now ends after pivot */
 176     pivot->next = q1;
 177     q1->prev = pivot;
 178 }
 179
 180 static_inline void
 181 opr_queue_SpliceAppend(struct opr_queue *target, struct opr_queue *source)
 182 {
 183
 184     if (source->next == source)
 185         return;
 186
 187     /* Stick the contents of source onto the end of target */
 188     target->prev->next = source->next;
 189     source->next->prev = target->prev;
 190     source->prev->next = target;
 191     target->prev = source->prev;
 192
 193     /* Reinitialise source */
 194     source->next = source->prev = source;
 195 }
 196
 197 static_inline void
 198 opr_queue_SplicePrepend(struct opr_queue *target, struct opr_queue *source)
 199 {
 200
 201     if (source->next == source)
 202         return;
 203
 204     /* Contents of source go onto the beginning of target */
 205     target->next->prev = source->prev;
 206     source->prev->next = target->next;
 207     source->next->prev = target;
 208     target->next = source->next;
 209
 210     /* Reinitialise source */
 211     source->next = source->prev = source;
 212 }
 213
 214 #define opr_queue_Entry(queue, structure, member) \
 215     ((structure *)((char *)(queue)-(char *)(&((structure *)NULL)->member)))
 216
 217 #define opr_queue_First(queue, structure, member) \
 218     opr_queue_Entry((queue)->next, structure, member)
 219
 220 #define opr_queue_Last(queue, structure, member) \
 221     opr_queue_Entry((queue)->prev, structure, member)
 222
 223 #define opr_queue_Next(entry, structure, member) \
 224     opr_queue_Entry((entry)->next, structure, member)
 225
 226 #define opr_queue_Prev(entry, structure, member) \
 227     opr_queue_Entry((entry)->prev, structure, member)
 228
 229 #endif