2 * Copyright (c) 2010 Your File System Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
25 /* A better queue implementation.
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.
33 #ifndef OPENAFS_OPR_QUEUE_H
34 #define OPENAFS_OPR_QUEUE_H 1
40 #define NULL (void *)0
45 struct opr_queue
*next
;
46 struct opr_queue
*prev
;
49 #define opr_queue_Scan(head, cursor) \
50 cursor = (head)->next; cursor != (head); cursor = cursor->next
52 #define opr_queue_ScanSafe(head, cursor, store) \
53 cursor = (head)->next, store = cursor->next; \
55 cursor = store, store = store->next
57 #define opr_queue_ScanBackwards(head, cursor) \
58 cursor = (head)->prev; cursor != (head); cursor = cursor->prev
60 #define opr_queue_ScanBackwardsSafe(head, cursor, store) \
61 cursor = (head)->prev, store = cursor->prev; \
63 cursor = store, store = store->prev
66 opr_queue_Zero(struct opr_queue
*q
) {
67 q
->prev
= q
->next
= NULL
;
71 opr_queue_Init(struct opr_queue
*q
) {
72 q
->prev
= q
->next
= q
;
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
;
85 opr_queue_Append(struct opr_queue
*queue
, struct opr_queue
*element
) {
86 opr_queue_add(element
, queue
->prev
, queue
);
90 opr_queue_Prepend(struct opr_queue
*queue
, struct opr_queue
*element
) {
91 opr_queue_add(element
, queue
, queue
->next
);
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
);
103 opr_queue_InsertAfter(struct opr_queue
*exist
, struct opr_queue
*adding
) {
104 opr_queue_add(adding
, exist
, exist
->next
);
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
;
116 opr_queue_IsEmpty(struct opr_queue
*q
) {
117 return (q
->prev
== q
);
121 opr_queue_IsOnQueue(struct opr_queue
*q
) {
122 return (q
->prev
!= NULL
);
126 opr_queue_IsEnd(struct opr_queue
*q
, struct opr_queue
*cursor
) {
127 return (cursor
== q
);
131 opr_queue_IsLast(struct opr_queue
*q
, struct opr_queue
*cursor
) {
132 return (cursor
->next
== q
);
136 opr_queue_Count(struct opr_queue
*q
) {
137 struct opr_queue
*cursor
;
140 for (opr_queue_Scan(q
, cursor
)) {
147 opr_queue_Swap(struct opr_queue
*a
, struct opr_queue
*b
)
149 struct opr_queue tq
= *b
;
152 b
->prev
= b
->next
= b
;
160 a
->prev
= a
->next
= a
;
168 /* Remove the members before pivot from Q1, and append them to Q2 */
171 opr_queue_SplitBeforeAppend(struct opr_queue
*q1
, struct opr_queue
*q2
,
172 struct opr_queue
*pivot
) {
174 if (q1
== pivot
->prev
)
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
;
182 /* Pull ourselves out of list q1. */
187 /* Remove the members after the pivot from Q1, and prepend them onto Q2 */
189 opr_queue_SplitAfterPrepend(struct opr_queue
*q1
, struct opr_queue
*q2
,
190 struct opr_queue
*pivot
) {
192 if (q1
== pivot
->next
)
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
;
202 /* Q1 now ends after pivot */
208 opr_queue_SpliceAppend(struct opr_queue
*target
, struct opr_queue
*source
)
211 if (source
->next
== source
)
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
;
220 /* Reinitialise source */
221 source
->next
= source
->prev
= source
;
225 opr_queue_SplicePrepend(struct opr_queue
*target
, struct opr_queue
*source
)
228 if (source
->next
== source
)
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
;
237 /* Reinitialise source */
238 source
->next
= source
->prev
= source
;
241 #define opr_queue_Entry(queue, structure, member) \
242 ((structure *)((char *)(queue)-(char *)(&((structure *)NULL)->member)))
244 #define opr_queue_First(queue, structure, member) \
245 opr_queue_Entry((queue)->next, structure, member)
247 #define opr_queue_Last(queue, structure, member) \
248 opr_queue_Entry((queue)->prev, structure, member)
250 #define opr_queue_Next(entry, structure, member) \
251 opr_queue_Entry((entry)->next, structure, member)
253 #define opr_queue_Prev(entry, structure, member) \
254 opr_queue_Entry((entry)->prev, structure, member)