probabilistic splay tree
[rxpd] / llist.h
1 /*
2     llist.h - simple intrusive cyclic double linked list
3
4   Copyright (C)
5     2003, 2005          Christian Thaeter <chth@gmx.net>
6   Copyright (C)         CinelerraCV
7     2007,               Christian Thaeter <ct@pipapo.org>
8
9   This program is free software; you can redistribute it and/or
10   modify it under the terms of the GNU General Public License as
11   published by the Free Software Foundation; either version 2 of the
12   License, or (at your option) any later version.
13
14   This program is distributed in the hope that it will be useful,
15   but WITHOUT ANY WARRANTY; without even the implied warranty of
16   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17   GNU General Public License for more details.
18
19   You should have received a copy of the GNU General Public License
20   along with this program; if not, write to the Free Software
21   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
22 */
23
24 #ifndef LLIST_H
25 #define LLIST_H
26
27 #include <stddef.h>
28
29 /**
30  * @file Intrusive cyclic double linked list
31  * There is only one node type which contains a forward and a backward pointer. In a empty initialized node,
32  * this pointers point to the node itself. Note that these pointers can never ever become NULL.
33  * This lists are used by using one node as 'root' node where its both pointers are the head/tail pointer to the actual list.
34  * Care needs to be taken to ensure not to apply any operations meant to be applied to data nodes to the root node.
35  * This way is the prefered way to use this lists.
36  * Alternatively one can store only a chain of data nodes and use a LList pointer to point to the first item
37  * (which might be NULL in case no data is stored). When using the 2nd approach care must be taken since most functions
38  * below expect lists to have a root node.
39  *
40  * This header can be used in 2 different ways:
41  * 1) (prerefered) just including it provides all functions as static inlined functions. This is the default
42  * 2) #define LLIST_INTERFACE before including this header gives only the declarations
43  *    #define LLIST_IMPLEMENTATION before including this header yields in definitions
44  *    this can be used to generate a library. This is currently untested and not recommended.
45  * The rationale for using inlined functions is that most functions are very small and likely to be used in performance critical parts.
46  * Inlining can give a hughe performance and optimization improvement here.
47  * The few functions which are slightly larger are expected to be the less common used ones, so inlining them too shouldn't be a problem either
48  */
49
50
51 /* TODO __STDC_VERSION__ 199901L
52 150) This macro was not specified in ISO/IEC 9899:1990 and was specified as 199409L in
53 ISO/IEC 9899/AMD1:1995. The intention is that this will remain an integer constant of type long
54 int that is increased with each revision of this International Standard.
55 */
56 #ifdef HAVE_INLINE
57 #       define LLIST_MACRO static inline
58 #else
59 #       ifdef __GNUC__
60 #               define LLIST_MACRO static __inline__
61 #       else
62 #               define LLIST_MACRO static
63 #       endif
64 #endif
65
66 #if defined(LLIST_INTERFACE)
67 /* only the interface is generated */
68 #define LLIST_FUNC(proto, ...) proto
69 #elif defined(LLIST_IMPLEMENTATION)
70 /* generate a non inlined implementation */
71 #define LLIST_FUNC(proto, ...) proto { __VA_ARGS__ }
72 #else
73 /* all functions are macro-like inlined */
74 #define LLIST_FUNC(proto, ...) LLIST_MACRO proto { __VA_ARGS__ }
75 #endif
76
77
78 /*
79  * Type of a llist node.
80  */
81 struct llist_struct
82 {
83   struct llist_struct *next;
84   struct llist_struct *prev;
85 };
86 typedef struct llist_struct llist;
87 typedef llist * LList;
88 typedef const llist * const_LList;
89 typedef llist ** LList_ref;
90
91 /**
92  * Macro to instantiate a local llist.
93  * @param name of the llist node
94  */
95 #define LLIST_AUTO(name) llist name = {&name,&name}
96
97
98 /**
99  * cast back from a member of a structure to a pointer of the structure
100  */
101 /* example:
102    struct foo
103    {
104      int bar;
105      llist l;
106    } x;
107    LLIST_TO_STRUCTP (&x.l, foo, l)->bar
108 */
109 #define LLIST_TO_STRUCTP(llist, type, member) \
110   ((type*)(((char*)(llist)) - offsetof(type, member)))
111
112 /**
113  * Iterate forward over a list.
114  * @param list the root node of the list to be iterated
115  * @param node pointer to the iterated node
116  */
117 #define LLIST_FOREACH(list, node)               \
118   if (!list); else                              \
119     for (LList node = llist_head (list);        \
120          ! llist_is_end (node, list);           \
121          llist_forward (&node))
122
123 /**
124  * Iterate backward over a list.
125  * @param list the root node of the list to be iterated
126  * @param node pointer to the iterated node
127  */
128 #define LLIST_FOREACH_REV(list, node)           \
129   if (!list); else                              \
130     for (LList node = llist_tail (list);        \
131          ! llist_is_end (node, list);           \
132          llist_backward (&node))
133
134 /**
135  * Consume a list from head.
136  * The body of this statement should remove the head from the list, else it would be a infinite loop
137  * @param list the root node of the list to be consumed
138  * @param head pointer to the head node
139  */
140 #define LLIST_WHILE_HEAD(list, head)            \
141   if (!list); else                              \
142     for (LList head = llist_head (list);        \
143          !llist_is_empty (list);                \
144          head = llist_head (list))
145
146 /**
147  * Consume a list from tail.
148  * The body of this statement should remove the tail from the list, else it would be a infinite loop
149  * @param list the root node of the list to be consumed
150  * @param tail pointer to the tail node
151  */
152 #define LLIST_WHILE_TAIL(list, tail)            \
153   if (!list); else                              \
154     for (LList tail = llist_tail (list);        \
155          !llist_is_empty (list);                \
156          tail = llist_tail (list))
157
158 /**
159  * Initialize a new llist.
160  * Must not be applied to a list node which is not empty! Lists need to be initialized
161  * before any other operation on them is called.
162  * @param self node to be initialized
163  */
164 LLIST_FUNC (void llist_init (LList self),
165             self->next = self->prev = self;
166 );
167
168 /**
169  * Check if a node is not linked with some other node.
170  */
171 LLIST_FUNC (int llist_is_empty (const_LList self),
172             return self->next == self;
173 );
174
175 /**
176  * Check if self is the only node in a list or self is not in a list.
177  * @param self node to be checked
178  */
179 LLIST_FUNC (int llist_is_single (const_LList self),
180             return self->next->next == self;
181 );
182
183 /**
184  * Check for the head of a list.
185  * @param self root of the list
186  * @param head expected head of the list
187  */
188 LLIST_FUNC (int llist_is_head (const_LList self, const_LList head),
189             return self->next == head;
190 );
191
192 /**
193  * Check for the tail of a list.
194  * @param self root of the list
195  * @param tail expected tail of the list
196  */
197 LLIST_FUNC (int llist_is_tail (const_LList self, const_LList tail),
198             return self->prev == tail;
199 );
200
201 /**
202  * Check for the end of a list.
203  * The end is by definition one past the tail of a list, which is the root node itself.
204  * @param self root node of the list
205  * @param end expected end of the list
206  */
207 LLIST_FUNC (int llist_is_end (const_LList self, const_LList end),
208             return self == end;
209 );
210
211 /**
212  * Check if a node is a member of a list.
213  * @param self root node of the list
214  * @param member node to be searched
215  */
216 LLIST_FUNC (int llist_is_member (const_LList self, const_LList member),
217             for (const_LList i = member->next; i != member; i = i->next)
218               {
219                 if (i == self)
220                   return 1;
221               }
222             return 0;
223 );
224
225 /**
226  * Check the order of elements in a list.
227  * @param self root node of the list
228  * @param before expected to be before after
229  * @param after expected to be after before
230  */
231 LLIST_FUNC (int llist_is_before_after (const_LList self, const_LList before, const_LList after),
232             for (const_LList i = before->next; i != self; i = i->next)
233               {
234                 if (i == after)
235                   return 1;
236               }
237             return 0;
238 );
239
240 /**
241  * Count the nodes of a list.
242  * @param self root node of the list
243  * @return number of nodes in self
244  */
245 LLIST_FUNC (unsigned llist_count (const_LList self),
246             unsigned cnt = 0;
247             const_LList i = self;
248             for (; i->next != self; ++cnt, i = i->next);
249             return cnt;
250 );
251
252 /* private, unlink self some any list but leaves self in a uninitialized state */
253 LLIST_FUNC (void llist_unlink_fast_ (LList self),
254             LList nxt = self->next, pre = self->prev;
255             nxt->prev = pre;
256             pre->next = nxt;
257 );
258
259 /**
260  * Remove a node from a list.
261  * @param self node to be removed
262  * @return self
263  */
264 LLIST_FUNC (LList llist_unlink (LList self),
265             llist_unlink_fast_ (self);
266             return self->next = self->prev = self;
267 );
268
269 /**
270  * Fix a node which got relocated in memory.
271  * It is supported to realloc/move list nodes in memory but one must call 'list_relocate' after doing so.
272  * @param self node which got relocated
273  * @return self
274  */
275 LLIST_FUNC (LList llist_relocate (LList self),
276             return self->next->prev = self->prev->next = self;
277 );
278
279 /**
280  * Insert a node after another.
281  * @param self node after which we want to insert
282  * @param next node which shall be inserted after self. Could already linked to a list from where it will be removed.
283  * @return self
284  */
285 LLIST_FUNC (LList llist_insert_next (LList self, LList next),
286             llist_unlink_fast_ (next);
287             self->next->prev = next;
288             next->prev = self;
289             next->next = self->next;
290             self->next = next;
291             return self;
292 );
293
294 /**
295  * Insert a node before another.
296  * @param self node before which we want to insert
297  * @param prev node which shall be inserted nefore self. Could already linked to a list from where it will be removed.
298  * @return self
299  */
300 LLIST_FUNC (LList llist_insert_prev (LList self, LList prev),
301             llist_unlink_fast_ (prev);
302             self->prev->next = prev;
303             prev->next = self;
304             prev->prev = self->prev;
305             self->prev = prev;
306             return self;
307 );
308
309
310 /**
311  * Move the content of a list after a node in another list.
312  * @param self node after which we want to insert a list
313  * @param next rootnode of the list which shall be inserted after self
314  * @return self
315  * next is a empty list after this call
316  */
317 LLIST_FUNC (LList llist_insertlist_next (LList self, LList next),
318             if (!llist_is_empty (next))
319               {
320                 self->next->prev = next->prev;
321                 self->next = next->next;
322
323                 next->next->prev = self; 
324                 next->prev->next = self->next;
325
326                 next->prev = next->next = next;
327               }
328             return self;
329 );
330
331 /**
332  * Move the content of a list before a node in another list.
333  * @param self node before which we want to insert a list
334  * @param prev rootnode of the list which shall be inserted before self
335  * @return self
336  * prev is a empty list after this call
337  */
338 LLIST_FUNC (LList llist_insertlist_prev (LList self, LList prev),
339             if (!llist_is_empty (prev))
340               {
341                 self->prev->next = prev->next;
342                 self->prev = prev->prev;
343
344                 prev->prev->next = self; 
345                 prev->next->prev = self->prev;
346
347                 prev->prev = prev->next = prev;
348               }
349             return self;
350 );
351
352 #if 0             //BUG("needs temporary")
353 /**
354  * Move a range of nodes after a given node.
355  * @param self node after which the range shall be inserted
356  * @param start first node in range to be moved
357  * @param end node after the last node of the range
358  */
359 LLIST_FUNC (LList llist_insertafter_range (LList self, LList start, LList end),
360             self->next->prev = end->prev;
361             end->prev->next = self->next;
362             end->prev = start->prev;
363             start->prev->next = end;
364             self->next = start;
365             start->prev = self;
366             return self;
367 );
368 #endif
369
370 #if 0             //BUG("needs temporary")
371 /**
372  * Move a range of nodes before a given node.
373  * @param self node before which the range shall be inserted
374  * @param start first node in range to be moved
375  * @param end node after the last node of the range
376  */
377 LLIST_FUNC (LList llist_inserbefore_range (LList self, LList start, LList end),
378             self->prev->next = start;
379             start->prev->next = end;
380             end->prev = start->prev;
381             start->prev = self->prev;
382             self->prev = end->prev;
383             end->prev->next = self;
384             return self;
385 );
386 #endif
387
388 /**
389  * Swap a node with its next node.
390  * @param self node to be advaced
391  * @return self
392  * advancing will not stop at tail, one has to check that if this is intended
393  */
394 LLIST_FUNC (LList llist_advance (LList self),
395             LList tmp = self->next->next;
396             tmp->prev = self;
397             self->next->prev = self->prev;
398             self->prev->next = self->next;
399             self->prev = self->next;
400             self->next->next = self;
401             self->next = tmp;
402             return self;
403 );
404
405 /**
406  * Swap a node with its previous node.
407  * @param self node to be retreated
408  * @return self
409  * retreating will not stop at head, one has to check that if this is intended
410  */
411 LLIST_FUNC (LList llist_retreat (LList self),
412             LList tmp = self->prev->prev;
413             tmp->next = self;
414             self->prev->next = self->next;
415             self->next->prev = self->prev;
416             self->next = self->prev;
417             self->prev->prev = self;
418             self->prev = tmp;
419             return self;
420 );
421
422
423 /**
424  * Get next node.
425  * @param self current node
426  * @return node after self
427  * Will not stop at tail
428  */
429 LLIST_FUNC (LList llist_next (const_LList self),
430             return self->next;
431 );
432
433 /**
434  * Get previous node.
435  * @param self current node
436  * @return node before self
437  * Will not stop at head
438  */
439 LLIST_FUNC (LList llist_prev (const_LList self),
440             return self->prev;
441 );
442
443 /**
444  * Advance a pointer to a node to its next node.
445  * @param self pointer-to-pointer to the current node
446  * *self will point to the next node after this call
447  */
448 LLIST_FUNC (void llist_forward (LList_ref self),
449             *self = (*self)->next;
450 );
451
452 /**
453  * Retreat a pointer to a node to its previous node.
454  * @param self pointer-to-pointer to the current node
455  * *self will point to the previous node after this call
456  */
457 LLIST_FUNC (void llist_backward (LList_ref self),
458             *self = (*self)->prev;
459 );
460
461 /**
462  * Get the nth element of a list.
463  * @param self list to be queried
464  * @param n nth element after (positive n) or before (negative n) self
465  * this function does not stop at head/tail.
466  */
467 LLIST_FUNC (LList llist_nth (LList self, int n),
468             if (n>0)
469               while (n--)
470                 self = llist_next (self);
471             else
472               while (n++)
473                 self = llist_prev (self);
474             return self;
475 );
476
477 /**
478  * Get the nth element of a list with a stop node.
479  * @param self list to be queried
480  * @param n nth element after (positive n) or before (negative n) self
481  * @param stop node which will abort the iteration
482  */
483 LLIST_FUNC (LList llist_get_nth_stop (LList self, int n, const_LList stop),
484             if (n>0)
485               while (n--)
486                 {
487                   self = llist_next (self);
488                   if (self == stop)
489                     return NULL;
490                 }
491             else
492               while (n++)
493                 {
494                   self = llist_prev (self);
495                   if (self == stop)
496                     return NULL;
497                 }
498             return self;
499 );
500
501 /*
502   some macros for convenience
503 */
504 #define llist_insert_head(list, element) llist_insert_next (list, element)
505 #define llist_insert_tail(list, element) llist_insert_prev (list, element)
506 #define llist_head llist_next
507 #define llist_tail llist_prev
508
509 #endif /* LLIST_H */
510 /*
511 // Local Variables:
512 // mode: C
513 // c-file-style: "gnu"
514 // End:
515 // arch-tag: e8fe4a59-fd55-4c45-b860-5cd1e0771213
516 // end_of_file
517 */