BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file LinkedList3.h
3 * @author Ambroz Bizjak <ambrop7@gmail.com>
4 *
5 * @section LICENSE
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the author nor the
15 * names of its contributors may be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 * @section DESCRIPTION
30 *
31 * Doubly linked list that support multiple iterations and removing
32 * aritrary elements during iteration, without a central object to
33 * represent the list.
34 */
35  
36 #ifndef BADVPN_STRUCTURE_LINKEDLIST3_H
37 #define BADVPN_STRUCTURE_LINKEDLIST3_H
38  
39 #include <stddef.h>
40 #include <stdint.h>
41  
42 #include <misc/debug.h>
43  
44 struct _LinkedList3Iterator;
45  
46 /**
47 * Linked list node.
48 */
49 typedef struct _LinkedList3Node {
50 struct _LinkedList3Node *p;
51 struct _LinkedList3Node *n;
52 struct _LinkedList3Iterator *it;
53 } LinkedList3Node;
54  
55 /**
56 * Linked list iterator.
57 */
58 typedef struct _LinkedList3Iterator {
59 int8_t dir;
60 struct _LinkedList3Node *e;
61 struct _LinkedList3Iterator *pi;
62 struct _LinkedList3Iterator *ni;
63 } LinkedList3Iterator;
64  
65 /**
66 * Initializes a list node to form a new list consisting of a
67 * single node.
68 *
69 * @param node list node structure to initialize. The node must remain
70 * available until it is freed with {@link LinkedList3Node_Free},
71 * or the list is no longer required.
72 */
73 static void LinkedList3Node_InitLonely (LinkedList3Node *node);
74  
75 /**
76 * Initializes a list node to go after an existing node.
77 *
78 * @param node list node structure to initialize. The node must remain
79 * available until it is freed with {@link LinkedList3Node_Free},
80 * or the list is no longer required.
81 * @param ref existing list node
82 */
83 static void LinkedList3Node_InitAfter (LinkedList3Node *node, LinkedList3Node *ref);
84  
85 /**
86 * Initializes a list node to go before an existing node.
87 *
88 * @param node list node structure to initialize. The node must remain
89 * available until it is freed with {@link LinkedList3Node_Free},
90 * or the list is no longer required.
91 * @param ref existing list node
92 */
93 static void LinkedList3Node_InitBefore (LinkedList3Node *node, LinkedList3Node *ref);
94  
95 /**
96 * Frees a list node, removing it a list (if there were other nodes
97 * in the list).
98 *
99 * @param node list node to free
100 */
101 static void LinkedList3Node_Free (LinkedList3Node *node);
102  
103 /**
104 * Determines if a list node is a single node in a list.
105 *
106 * @param node list node
107 * @return 1 if the node ia a single node, 0 if not
108 */
109 static int LinkedList3Node_IsLonely (LinkedList3Node *node);
110  
111 /**
112 * Returnes the node preceding this node (if there is one),
113 * the node following this node (if there is one), or NULL,
114 * respectively.
115 *
116 * @param node list node
117 * @return neighbour node or NULL if none
118 */
119 static LinkedList3Node * LinkedList3Node_PrevOrNext (LinkedList3Node *node);
120  
121 /**
122 * Returnes the node following this node (if there is one),
123 * the node preceding this node (if there is one), or NULL,
124 * respectively.
125 *
126 * @param node list node
127 * @return neighbour node or NULL if none
128 */
129 static LinkedList3Node * LinkedList3Node_NextOrPrev (LinkedList3Node *node);
130  
131 /**
132 * Returns the node preceding this node, or NULL if there is none.
133 *
134 * @param node list node
135 * @return left neighbour, or NULL if none
136 */
137 static LinkedList3Node * LinkedList3Node_Prev (LinkedList3Node *node);
138  
139 /**
140 * Returns the node following this node, or NULL if there is none.
141 *
142 * @param node list node
143 * @return right neighbour, or NULL if none
144 */
145 static LinkedList3Node * LinkedList3Node_Next (LinkedList3Node *node);
146  
147 /**
148 * Returns the first node in the list which this node is part of.
149 * It is found by iterating the list from this node to the beginning.
150 *
151 * @param node list node
152 * @return first node in the list
153 */
154 static LinkedList3Node * LinkedList3Node_First (LinkedList3Node *node);
155  
156 /**
157 * Returns the last node in the list which this node is part of.
158 * It is found by iterating the list from this node to the end.
159 *
160 * @param node list node
161 * @return last node in the list
162 */
163 static LinkedList3Node * LinkedList3Node_Last (LinkedList3Node *node);
164  
165 /**
166 * Initializes a linked list iterator.
167 * The iterator structure must remain available until either of these occurs:
168 * - the list is no longer needed, or
169 * - the iterator is freed with {@link LinkedList3Iterator_Free}, or
170 * - the iterator reaches the end of iteration.
171 *
172 * @param it uninitialized iterator to initialize
173 * @param e initial position of the iterator. NULL for end of iteration.
174 * @param dir direction of iteration. Must be 1 (forward) or -1 (backward).
175 */
176 static void LinkedList3Iterator_Init (LinkedList3Iterator *it, LinkedList3Node *e, int dir);
177  
178 /**
179 * Frees a linked list iterator.
180 *
181 * @param it iterator to free
182 */
183 static void LinkedList3Iterator_Free (LinkedList3Iterator *it);
184  
185 /**
186 * Moves the iterator one node forward or backward (depending on its direction), or,
187 * if it's at the last or first node (depending on the direction), it reaches
188 * the end of iteration, or, if it's at the end of iteration, it remains there.
189 * Returns the the previous position.
190 *
191 * @param it the iterator
192 * @return node on the position of iterator before it was (possibly) moved, or NULL
193 * if it was at the end of iteration
194 */
195 static LinkedList3Node * LinkedList3Iterator_Next (LinkedList3Iterator *it);
196  
197 void LinkedList3Node_InitLonely (LinkedList3Node *node)
198 {
199 node->p = NULL;
200 node->n = NULL;
201 node->it = NULL;
202 }
203  
204 void LinkedList3Node_InitAfter (LinkedList3Node *node, LinkedList3Node *ref)
205 {
206 ASSERT(ref)
207  
208 node->p = ref;
209 node->n = ref->n;
210 ref->n = node;
211 if (node->n) {
212 node->n->p = node;
213 }
214 node->it = NULL;
215 }
216  
217 void LinkedList3Node_InitBefore (LinkedList3Node *node, LinkedList3Node *ref)
218 {
219 ASSERT(ref)
220  
221 node->n = ref;
222 node->p = ref->p;
223 ref->p = node;
224 if (node->p) {
225 node->p->n = node;
226 }
227 node->it = NULL;
228 }
229  
230 void LinkedList3Node_Free (LinkedList3Node *node)
231 {
232 // jump iterators
233 while (node->it) {
234 LinkedList3Iterator_Next(node->it);
235 }
236  
237 if (node->p) {
238 node->p->n = node->n;
239 }
240 if (node->n) {
241 node->n->p = node->p;
242 }
243 }
244  
245 int LinkedList3Node_IsLonely (LinkedList3Node *node)
246 {
247 return (!node->p && !node->n);
248 }
249  
250 LinkedList3Node * LinkedList3Node_PrevOrNext (LinkedList3Node *node)
251 {
252 if (node->p) {
253 return node->p;
254 }
255 if (node->n) {
256 return node->n;
257 }
258 return NULL;
259 }
260  
261 LinkedList3Node * LinkedList3Node_NextOrPrev (LinkedList3Node *node)
262 {
263 if (node->n) {
264 return node->n;
265 }
266 if (node->p) {
267 return node->p;
268 }
269 return NULL;
270 }
271  
272 LinkedList3Node * LinkedList3Node_Prev (LinkedList3Node *node)
273 {
274 return node->p;
275 }
276  
277 LinkedList3Node * LinkedList3Node_Next (LinkedList3Node *node)
278 {
279 return node->n;
280 }
281  
282 LinkedList3Node * LinkedList3Node_First (LinkedList3Node *node)
283 {
284 while (node->p) {
285 node = node->p;
286 }
287  
288 return node;
289 }
290  
291 LinkedList3Node * LinkedList3Node_Last (LinkedList3Node *node)
292 {
293 while (node->n) {
294 node = node->n;
295 }
296  
297 return node;
298 }
299  
300 void LinkedList3Iterator_Init (LinkedList3Iterator *it, LinkedList3Node *e, int dir)
301 {
302 ASSERT(dir == -1 || dir == 1)
303  
304 it->dir = dir;
305 it->e = e;
306  
307 if (e) {
308 // link into node's iterator list
309 it->pi = NULL;
310 it->ni = e->it;
311 if (e->it) {
312 e->it->pi = it;
313 }
314 e->it = it;
315 }
316 }
317  
318 void LinkedList3Iterator_Free (LinkedList3Iterator *it)
319 {
320 if (it->e) {
321 // remove from node's iterator list
322 if (it->ni) {
323 it->ni->pi = it->pi;
324 }
325 if (it->pi) {
326 it->pi->ni = it->ni;
327 } else {
328 it->e->it = it->ni;
329 }
330 }
331 }
332  
333 LinkedList3Node * LinkedList3Iterator_Next (LinkedList3Iterator *it)
334 {
335 // remember original entry
336 LinkedList3Node *orig = it->e;
337  
338 // jump to next entry
339 if (it->e) {
340 // get next entry
341 LinkedList3Node *next = NULL; // to remove warning
342 switch (it->dir) {
343 case 1:
344 next = it->e->n;
345 break;
346 case -1:
347 next = it->e->p;
348 break;
349 default:
350 ASSERT(0);
351 }
352 // destroy interator
353 LinkedList3Iterator_Free(it);
354 // re-initialize at next entry
355 LinkedList3Iterator_Init(it, next, it->dir);
356 }
357  
358 // return original entry
359 return orig;
360 }
361  
362 #endif