uuid: hashes are positive ints
[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->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