opr: Add new queue implementation
[openafs.git] / src / util / 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