opr: Don't confuse isLast and isEnd
[openafs.git] / 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 == q);
128 }
129
130 static_inline int
131 opr_queue_IsLast(struct opr_queue *q, struct opr_queue *cursor) {
132     return (cursor->next == q);
133 }
134
135 static_inline int
136 opr_queue_Count(struct opr_queue *q) {
137     struct opr_queue *cursor;
138     int n = 0;
139
140     for (opr_queue_Scan(q, cursor)) {
141         n++;
142     }
143     return n;
144 }
145
146 static_inline void
147 opr_queue_Swap(struct opr_queue *a, struct opr_queue *b)
148 {
149     struct opr_queue tq = *b;
150
151     if (a->prev == a) {
152         b->prev = b->next = b;
153     } else {
154         *b = *a;
155         b->prev->next = b;
156         b->next->prev = b;
157     }
158
159     if (tq.prev == b) {
160         a->prev = a->next = a;
161     } else {
162         *a = tq;
163         a->prev->next = a;
164         a->next->prev = a;
165     }
166 }
167
168 /* Remove the members before pivot from Q1, and append them to Q2 */
169
170 static_inline void
171 opr_queue_SplitBeforeAppend(struct opr_queue *q1, struct opr_queue *q2,
172                             struct opr_queue *pivot) {
173
174     if (q1 == pivot->prev)
175         return;
176     /* Add ourselves to the end of list 2 */
177     q2->prev->next = q1->next; /* end of list 2, is now the start of list 1 */
178     q1->next->prev = q2->prev;
179     pivot->prev->next = q2; /* entry before the pivot is it at end of q2 */
180     q2->prev = pivot->prev;
181
182     /* Pull ourselves out of list q1. */
183     q1->next = pivot;
184     pivot->prev = q1;
185 }
186
187 /* Remove the members after the pivot from Q1, and prepend them onto Q2 */
188 static_inline void
189 opr_queue_SplitAfterPrepend(struct opr_queue *q1, struct opr_queue *q2,
190                             struct opr_queue *pivot) {
191
192     if (q1 == pivot->next)
193         return;
194
195     /* start of q2 has last element of q1 before it */
196     q2->next->prev = q1->prev;
197     q1->prev->next = q2->next;
198     /* item that we're breaking at (pivot->next) is at start of q2 */
199     q2->next = pivot->next;
200     pivot->next->prev = q2;
201
202     /* Q1 now ends after pivot */
203     pivot->next = q1;
204     q1->prev = pivot;
205 }
206
207 static_inline void
208 opr_queue_SpliceAppend(struct opr_queue *target, struct opr_queue *source)
209 {
210
211     if (source->next == source)
212         return;
213
214     /* Stick the contents of source onto the end of target */
215     target->prev->next = source->next;
216     source->next->prev = target->prev;
217     source->prev->next = target;
218     target->prev = source->prev;
219
220     /* Reinitialise source */
221     source->next = source->prev = source;
222 }
223
224 static_inline void
225 opr_queue_SplicePrepend(struct opr_queue *target, struct opr_queue *source)
226 {
227
228     if (source->next == source)
229         return;
230
231     /* Contents of source go onto the beginning of target */
232     target->next->prev = source->prev;
233     source->prev->next = target->next;
234     source->next->prev = target;
235     target->next = source->next;
236
237     /* Reinitialise source */
238     source->next = source->prev = source;
239 }
240
241 #define opr_queue_Entry(queue, structure, member) \
242     ((structure *)((char *)(queue)-(char *)(&((structure *)NULL)->member)))
243
244 #define opr_queue_First(queue, structure, member) \
245     opr_queue_Entry((queue)->next, structure, member)
246
247 #define opr_queue_Last(queue, structure, member) \
248     opr_queue_Entry((queue)->prev, structure, member)
249
250 #define opr_queue_Next(entry, structure, member) \
251     opr_queue_Entry((entry)->next, structure, member)
252
253 #define opr_queue_Prev(entry, structure, member) \
254     opr_queue_Entry((entry)->prev, structure, member)
255
256 #endif