pipadoc uses some bashisms
[nobug.git] / src / llist.h
blob1a48d5922468fbb062590e4ea5110b98ee85221b
1 /*
2 llist.h - simple intrusive cyclic double linked list
4 Copyright (C)
5 2003, 2005 Christian Thaeter <chth@gmx.net>
6 Copyright (C) Lumiera.org
7 2008, Christian Thaeter <ct@pipapo.org>
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.
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.
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.
24 #ifndef LLIST_H
25 #define LLIST_H
27 #include <stddef.h>
29 /**
30 * @file
31 * Intrusive cyclic double linked list
32 * There is only one node type which contains a forward and a backward pointer. In a empty initialized node,
33 * this pointers point to the node itself. Note that these pointers can never ever become NULL.
34 * This lists are used by using one node as 'root' node where its both pointers are the head/tail pointer to the actual list.
35 * Care needs to be taken to ensure not to apply any operations meant to be applied to data nodes to the root node.
36 * This way is the prefered way to use this lists.
37 * Alternatively one can store only a chain of data nodes and use a LList pointer to point to the first item
38 * (which might be NULL in case no data is stored). When using the 2nd approach care must be taken since most functions
39 * below expect lists to have a root node.
41 * This header can be used in 2 different ways:
42 * 1) (prerefered) just including it provides all functions as static inlined functions. This is the default
43 * 2) #define LLIST_INTERFACE before including this header gives only the declarations
44 * #define LLIST_IMPLEMENTATION before including this header yields in definitions
45 * this can be used to generate a library. This is currently untested and not recommended.
46 * The rationale for using inlined functions is that most functions are very small and likely to be used in performance critical parts.
47 * Inlining can give a hughe performance and optimization improvement here.
48 * 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
52 /* TODO __STDC_VERSION__ 199901L
53 150) This macro was not specified in ISO/IEC 9899:1990 and was specified as 199409L in
54 ISO/IEC 9899/AMD1:1995. The intention is that this will remain an integer constant of type long
55 int that is increased with each revision of this International Standard.
57 #ifdef HAVE_INLINE
58 # define LLIST_MACRO static inline
59 #else
60 # ifdef __GNUC__
61 # define LLIST_MACRO static __inline__
62 # else
63 # define LLIST_MACRO static
64 # endif
65 #endif
67 #if defined(LLIST_INTERFACE)
68 /* only the interface is generated */
69 #define LLIST_FUNC(proto, ...) proto
70 #elif defined(LLIST_IMPLEMENTATION)
71 /* generate a non inlined implementation */
72 #define LLIST_FUNC(proto, ...) proto { __VA_ARGS__ }
73 #else
74 /* all functions are macro-like inlined */
75 #define LLIST_FUNC(proto, ...) LLIST_MACRO proto { __VA_ARGS__ }
76 #endif
80 * Type of a llist node.
82 #ifndef LLIST_DEFINED
83 #define LLIST_DEFINED
84 struct llist_struct
86 struct llist_struct *next;
87 struct llist_struct *prev;
89 #endif
90 typedef struct llist_struct llist;
91 typedef llist * LList;
92 typedef const llist * const_LList;
93 typedef llist ** LList_ref;
96 /**
97 * Macro to instantiate a local llist.
98 * @param name of the llist node
100 #define LLIST_AUTO(name) llist name = {&name,&name}
104 some macros for convenience
106 #define llist_insert_head(list, element) llist_insert_next (list, element)
107 #define llist_insert_tail(list, element) llist_insert_prev (list, element)
108 #define llist_head llist_next
109 #define llist_tail llist_prev
112 * cast back from a member of a structure to a pointer of the structure
114 /* example:
115 struct foo
117 int bar;
118 llist l;
119 } x;
120 LLIST_TO_STRUCTP (&x.l, foo, l)->bar
122 #define LLIST_TO_STRUCTP(llist, type, member) \
123 ((type*)(((char*)(llist)) - offsetof(type, member)))
126 * Iterate forward over a list.
127 * @param list the root node of the list to be iterated
128 * @param node pointer to the iterated node
130 #define LLIST_FOREACH(list, node) \
131 for (LList node = llist_head (list); \
132 ! llist_is_end (node, list); \
133 llist_forward (&node))
136 * Iterate backward over a list.
137 * @param list the root node of the list to be iterated
138 * @param node pointer to the iterated node
140 #define LLIST_FOREACH_REV(list, node) \
141 for (LList node = llist_tail (list); \
142 ! llist_is_end (node, list); \
143 llist_backward (&node))
147 * Iterate forward over a range.
148 * @param start first node to be interated
149 * @param end node after the last node be iterated
150 * @param node pointer to the iterated node
152 #define LLIST_FORRANGE(start, end, node) \
153 for (LList node = start; \
154 node != end; \
155 llist_forward (&node))
158 * Iterate backward over a range.
159 * @param rstart first node to be interated
160 * @param rend node before the last node be iterated
161 * @param node pointer to the iterated node
163 #define LLIST_FORRANGE_REV(rstart, rend, node) \
164 for (LList node = rstart; \
165 node != rend; \
166 llist_backward (&node))
170 * Consume a list from head.
171 * The body of this statement should remove the head from the list, else it would be a infinite loop
172 * @param list the root node of the list to be consumed
173 * @param head pointer to the head node
175 #define LLIST_WHILE_HEAD(list, head) \
176 for (LList head = llist_head (list); \
177 !llist_is_empty (list); \
178 head = llist_head (list))
181 * Consume a list from tail.
182 * The body of this statement should remove the tail from the list, else it would be a infinite loop
183 * @param list the root node of the list to be consumed
184 * @param tail pointer to the tail node
186 #define LLIST_WHILE_TAIL(list, tail) \
187 for (LList tail = llist_tail (list); \
188 !llist_is_empty (list); \
189 tail = llist_tail (list))
192 * Initialize a new llist.
193 * Must not be applied to a list node which is not empty! Lists need to be initialized
194 * before any other operation on them is called.
195 * @param self node to be initialized
197 LLIST_FUNC (LList llist_init (LList self),
198 return self->next = self->prev = self;
202 * Check if a node is not linked with some other node.
204 LLIST_FUNC (int llist_is_empty (const_LList self),
205 return self->next == self;
209 * Check if self is the only node in a list or self is not in a list.
210 * @param self node to be checked
212 LLIST_FUNC (int llist_is_single (const_LList self),
213 return self->next->next == self;
217 * Check for the head of a list.
218 * @param self root of the list
219 * @param head expected head of the list
221 LLIST_FUNC (int llist_is_head (const_LList self, const_LList head),
222 return self->next == head;
226 * Check for the tail of a list.
227 * @param self root of the list
228 * @param tail expected tail of the list
230 LLIST_FUNC (int llist_is_tail (const_LList self, const_LList tail),
231 return self->prev == tail;
235 * Check for the end of a list.
236 * The end is by definition one past the tail of a list, which is the root node itself.
237 * @param self root node of the list
238 * @param end expected end of the list
240 LLIST_FUNC (int llist_is_end (const_LList self, const_LList end),
241 return self == end;
245 * Check if a node is a member of a list.
246 * @param self root node of the list
247 * @param member node to be searched
249 LLIST_FUNC (int llist_is_member (const_LList self, const_LList member),
250 for (const_LList i = member->next; i != member; i = i->next)
252 if (i == self)
253 return 1;
255 return 0;
259 * Check the order of elements in a list.
260 * @param self root node of the list
261 * @param before expected to be before after
262 * @param after expected to be after before
264 LLIST_FUNC (int llist_is_before_after (const_LList self, const_LList before, const_LList after),
265 for (const_LList i = before->next; i != self; i = i->next)
267 if (i == after)
268 return 1;
270 return 0;
274 * Count the nodes of a list.
275 * @param self root node of the list
276 * @return number of nodes in self
278 LLIST_FUNC (unsigned llist_count (const_LList self),
279 unsigned cnt = 0;
280 const_LList i = self;
281 for (; i->next != self; ++cnt, i = i->next);
282 return cnt;
285 /* private, unlink self some any list but leaves self in a uninitialized state */
286 LLIST_FUNC (void llist_unlink_fast_ (LList self),
287 LList nxt = self->next, pre = self->prev;
288 nxt->prev = pre;
289 pre->next = nxt;
293 * Remove a node from a list.
294 * @param self node to be removed
295 * @return self
297 LLIST_FUNC (LList llist_unlink (LList self),
298 llist_unlink_fast_ (self);
299 return self->next = self->prev = self;
303 * Fix a node which got relocated in memory.
304 * It is supported to realloc/move list nodes in memory but one must call 'list_relocate' after doing so.
305 * IMPORTANT: it is not possible to relocate nodes which are empty this way, nor can this be determined
306 * after the relocation, so either llist_init them afterwards or insert a bogus node before moving the node
307 * and relocating it and remove it afterwards.
308 * @param self node which got relocated
309 * @return self
311 LLIST_FUNC (LList llist_relocate (LList self),
312 return self->next->prev = self->prev->next = self;
317 * Insert a node after another.
318 * @param self node after which we want to insert
319 * @param next node which shall be inserted after self. Could already linked to a list from where it will be removed.
320 * @return self
322 LLIST_FUNC (LList llist_insert_next (LList self, LList next),
323 llist_unlink_fast_ (next);
324 self->next->prev = next;
325 next->prev = self;
326 next->next = self->next;
327 self->next = next;
328 return self;
332 * Insert a node before another.
333 * @param self node before which we want to insert
334 * @param prev node which shall be inserted before self. Could already linked to a list from where it will be removed.
335 * @return self
337 LLIST_FUNC (LList llist_insert_prev (LList self, LList prev),
338 llist_unlink_fast_ (prev);
339 self->prev->next = prev;
340 prev->next = self;
341 prev->prev = self->prev;
342 self->prev = prev;
343 return self;
348 * Move the content of a list after a node in another list.
349 * @param self node after which we want to insert a list
350 * @param next rootnode of the list which shall be inserted after self
351 * @return self
352 * next is a empty list after this call
354 LLIST_FUNC (LList llist_insertlist_next (LList self, LList next),
355 if (!llist_is_empty (next))
357 self->next->prev = next->prev;
358 next->prev->next = self->next;
359 self->next = next->next;
360 next->next->prev = self;
362 next->prev = next->next = next;
364 return self;
368 * Move the content of a list before a node in another list.
369 * @param self node before which we want to insert a list
370 * @param prev rootnode of the list which shall be inserted before self
371 * @return self
372 * prev is a empty list after this call
374 LLIST_FUNC (LList llist_insertlist_prev (LList self, LList prev),
375 if (!llist_is_empty (prev))
377 self->prev->next = prev->next;
378 prev->next->prev = self->prev;
379 self->prev = prev->prev;
380 prev->prev->next = self;
382 prev->prev = prev->next = prev;
384 return self;
387 #if 0 //BUG("needs temporary")
389 * Move a range of nodes after a given node.
390 * @param self node after which the range shall be inserted
391 * @param start first node in range to be moved
392 * @param end node after the last node of the range
394 LLIST_FUNC (LList llist_insertafter_range (LList self, LList start, LList end),
395 self->next->prev = end->prev;
396 end->prev->next = self->next;
397 end->prev = start->prev;
398 start->prev->next = end;
399 self->next = start;
400 start->prev = self;
401 return self;
403 #endif
405 #if 0 //BUG("needs temporary")
407 * Move a range of nodes before a given node.
408 * @param self node before which the range shall be inserted
409 * @param start first node in range to be moved
410 * @param end node after the last node of the range
412 LLIST_FUNC (LList llist_inserbefore_range (LList self, LList start, LList end),
413 self->prev->next = start;
414 start->prev->next = end;
415 end->prev = start->prev;
416 start->prev = self->prev;
417 self->prev = end->prev;
418 end->prev->next = self;
419 return self;
421 #endif
424 * Swap a node with its next node.
425 * @param self node to be advaced
426 * @return self
427 * advancing will not stop at tail, one has to check that if this is intended
429 LLIST_FUNC (LList llist_advance (LList self),
430 LList tmp = self->next->next;
431 tmp->prev = self;
432 self->next->prev = self->prev;
433 self->prev->next = self->next;
434 self->prev = self->next;
435 self->next->next = self;
436 self->next = tmp;
437 return self;
441 * Swap a node with its previous node.
442 * @param self node to be retreated
443 * @return self
444 * retreating will not stop at head, one has to check that if this is intended
446 LLIST_FUNC (LList llist_retreat (LList self),
447 LList tmp = self->prev->prev;
448 tmp->next = self;
449 self->prev->next = self->next;
450 self->next->prev = self->prev;
451 self->next = self->prev;
452 self->prev->prev = self;
453 self->prev = tmp;
454 return self;
459 * Get next node.
460 * @param self current node
461 * @return node after self
462 * Will not stop at tail
464 LLIST_FUNC (LList llist_next (const_LList self),
465 return self->next;
469 * Get previous node.
470 * @param self current node
471 * @return node before self
472 * Will not stop at head
474 LLIST_FUNC (LList llist_prev (const_LList self),
475 return self->prev;
479 * Advance a pointer to a node to its next node.
480 * @param self pointer-to-pointer to the current node
481 * *self will point to the next node after this call
483 LLIST_FUNC (void llist_forward (LList_ref self),
484 *self = (*self)->next;
488 * Retreat a pointer to a node to its previous node.
489 * @param self pointer-to-pointer to the current node
490 * *self will point to the previous node after this call
492 LLIST_FUNC (void llist_backward (LList_ref self),
493 *self = (*self)->prev;
497 * Get the nth element of a list.
498 * @param self list to be queried
499 * @param n nth element after (positive n) or before (negative n) self
500 * this function does not stop at head/tail.
502 LLIST_FUNC (LList llist_nth (LList self, int n),
503 if (n>0)
504 while (n--)
505 self = llist_next (self);
506 else
507 while (n++)
508 self = llist_prev (self);
509 return self;
513 * Get the nth element of a list with a stop node.
514 * @param self list to be queried
515 * @param n nth element after (positive n) or before (negative n) self
516 * @param stop node which will abort the iteration
518 LLIST_FUNC (LList llist_get_nth_stop (LList self, int n, const_LList stop),
519 if (n>0)
520 while (n--)
522 self = llist_next (self);
523 if (self == stop)
524 return NULL;
526 else
527 while (n++)
529 self = llist_prev (self);
530 if (self == stop)
531 return NULL;
533 return self;
538 * The comparsion function function type.
539 * certain sort and find functions depend on a user supplied coparsion function
540 * @param a first operand for the comparsion
541 * @param b second operand for the comparsion
542 * @param extra user supplied data which passed through
543 * @return shall return a value less than zero, zero, biggier than zero when
544 * a is less than, equal to, biggier than b
546 typedef int (*llist_cmpfn)(const_LList a, const_LList b, void* extra);
550 * Sort a list.
551 * recursive mergesort, needs much extra stackspace (crappy implementation yet) but it reasonable fast
552 * @param self list to be sorted
553 * @param cmp function for comparing 2 nodes
554 * @param extra generic data passed to the cmp function
556 LLIST_FUNC (LList llist_sort (LList self, llist_cmpfn cmp, void* extra),
557 llist left;
558 llist right;
559 llist_init (&left);
560 llist_init (&right);
561 unsigned n = 0;
562 if (!llist_is_single (self))
564 LLIST_WHILE_HEAD (self, head)
565 llist_insert_prev (++n & 1 ? &left : &right, head);
567 llist_sort (&left, cmp, extra);
568 llist_sort (&right, cmp, extra);
570 while (!llist_is_empty (&left) && !llist_is_empty (&right))
571 llist_insert_prev (self, cmp (left.next, right.next, extra) < 0 ? left.next : right.next);
573 if (!llist_is_empty (&left))
574 llist_insertlist_prev (self, &left);
575 if (!llist_is_empty (&right))
576 llist_insertlist_prev (self, &right);
578 return self;
583 * Find a element in list.
584 * searches the list for a element.
585 * Does not change the list order.
586 * @param self list to be searched
587 * @param templ template for the element being searched
588 * @param cmp function for comparing 2 nodes
589 * @return pointer to the found LList element or NULL if nothing found
591 LLIST_FUNC (LList llist_find (const_LList self, const_LList templ, llist_cmpfn cmp, void* extra),
592 LLIST_FOREACH(self, node)
594 if (!cmp (node, templ, extra))
595 return node;
597 return NULL;
602 * Find a element in a unsorted list.
603 * searches the list until it finds the searched element and moves it then to the head.
604 * Useful if the order of the list is not required and few elements are frequently searched.
605 * @param self list to be searched
606 * @param templ template for the element being searched
607 * @param cmp function for comparing 2 nodes
608 * @return pointer to the found LList element (head) or NULL if nothing found
610 LLIST_FUNC (LList llist_ufind (LList self, const_LList templ, llist_cmpfn cmp, void* extra),
611 LLIST_FOREACH(self, node)
613 if (!cmp (node, templ, extra))
615 if (llist_next(self) != node)
616 llist_insert_next (self, node);
617 return node;
620 return NULL;
625 * Find a element in a sorted list.
626 * searches the list until it find the searched element, exits searching when found an element
627 * biggier than the searched one.
628 * @param self list to be searched
629 * @param templ template for the element being searched
630 * @param cmp function for comparing 2 nodes
631 * @return pointer to the found LList element or NULL if nothing foound
633 LLIST_FUNC (LList llist_sfind (const_LList self, const_LList templ, llist_cmpfn cmp, void* extra),
634 LLIST_FOREACH(self, node)
636 int c = cmp (node, templ, extra);
637 if (!c)
638 return node;
639 else if (c>0)
640 break;
642 return NULL;
647 #endif /* LLIST_H */
649 // Local Variables:
650 // mode: C
651 // c-file-style: "gnu"
652 // indent-tabs-mode: nil
653 // End: