Commit | Line | Data |
---|---|---|
805e021f CE |
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 |