a478b089fba3b91f44f105f6e988f0fd7dc2dc4d
[webgit] / src / 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     for (LList node = llist_head (list);        \
119          ! llist_is_end (node, list);           \
120          llist_forward (&node))
121
122 /**
123  * Iterate backward over a list.
124  * @param list the root node of the list to be iterated
125  * @param node pointer to the iterated node
126  */
127 #define LLIST_FOREACH_REV(list, node)           \
128     for (LList node = llist_tail (list);        \
129          ! llist_is_end (node, list);           \
130          llist_backward (&node))
131
132
133 /**
134  * Iterate forward over a range.
135  * @param start first node to be interated
136  * @param end node after the last node be iterated
137  * @param node pointer to the iterated node
138  */
139 #define LLIST_FORRANGE(start, end, node)        \
140     for (LList node = start;                    \
141          node != end;                           \
142          llist_forward (&node))
143
144 /**
145  * Iterate backward over a range.
146  * @param rstart first node to be interated
147  * @param rend node before the last node be iterated
148  * @param node pointer to the iterated node
149  */
150 #define LLIST_FORRANGE_REV(rstart, rend, node)  \
151     for (LList node = rstart;                   \
152          node != rend;                          \
153          llist_backward (&node))
154
155
156 /**
157  * Consume a list from head.
158  * The body of this statement should remove the head from the list, else it would be a infinite loop
159  * @param list the root node of the list to be consumed
160  * @param head pointer to the head node
161  */
162 #define LLIST_WHILE_HEAD(list, head)            \
163     for (LList head = llist_head (list);        \
164          !llist_is_empty (list);                \
165          head = llist_head (list))
166
167 /**
168  * Consume a list from tail.
169  * The body of this statement should remove the tail from the list, else it would be a infinite loop
170  * @param list the root node of the list to be consumed
171  * @param tail pointer to the tail node
172  */
173 #define LLIST_WHILE_TAIL(list, tail)            \
174     for (LList tail = llist_tail (list);        \
175          !llist_is_empty (list);                \
176          tail = llist_tail (list))
177
178 /**
179  * Initialize a new llist.
180  * Must not be applied to a list node which is not empty! Lists need to be initialized
181  * before any other operation on them is called.
182  * @param self node to be initialized
183  */
184 LLIST_FUNC (void llist_init (LList self),
185             self->next = self->prev = self;
186 );
187
188 /**
189  * Check if a node is not linked with some other node.
190  */
191 LLIST_FUNC (int llist_is_empty (const_LList self),
192             return self->next == self;
193 );
194
195 /**
196  * Check if self is the only node in a list or self is not in a list.
197  * @param self node to be checked
198  */
199 LLIST_FUNC (int llist_is_single (const_LList self),
200             return self->next->next == self;
201 );
202
203 /**
204  * Check for the head of a list.
205  * @param self root of the list
206  * @param head expected head of the list
207  */
208 LLIST_FUNC (int llist_is_head (const_LList self, const_LList head),
209             return self->next == head;
210 );
211
212 /**
213  * Check for the tail of a list.
214  * @param self root of the list
215  * @param tail expected tail of the list
216  */
217 LLIST_FUNC (int llist_is_tail (const_LList self, const_LList tail),
218             return self->prev == tail;
219 );
220
221 /**
222  * Check for the end of a list.
223  * The end is by definition one past the tail of a list, which is the root node itself.
224  * @param self root node of the list
225  * @param end expected end of the list
226  */
227 LLIST_FUNC (int llist_is_end (const_LList self, const_LList end),
228             return self == end;
229 );
230
231 /**
232  * Check if a node is a member of a list.
233  * @param self root node of the list
234  * @param member node to be searched
235  */
236 LLIST_FUNC (int llist_is_member (const_LList self, const_LList member),
237             for (const_LList i = member->next; i != member; i = i->next)
238               {
239                 if (i == self)
240                   return 1;
241               }
242             return 0;
243 );
244
245 /**
246  * Check the order of elements in a list.
247  * @param self root node of the list
248  * @param before expected to be before after
249  * @param after expected to be after before
250  */
251 LLIST_FUNC (int llist_is_before_after (const_LList self, const_LList before, const_LList after),
252             for (const_LList i = before->next; i != self; i = i->next)
253               {
254                 if (i == after)
255                   return 1;
256               }
257             return 0;
258 );
259
260 /**
261  * Count the nodes of a list.
262  * @param self root node of the list
263  * @return number of nodes in self
264  */
265 LLIST_FUNC (unsigned llist_count (const_LList self),
266             unsigned cnt = 0;
267             const_LList i = self;
268             for (; i->next != self; ++cnt, i = i->next);
269             return cnt;
270 );
271
272 /* private, unlink self some any list but leaves self in a uninitialized state */
273 LLIST_FUNC (void llist_unlink_fast_ (LList self),
274             LList nxt = self->next, pre = self->prev;
275             nxt->prev = pre;
276             pre->next = nxt;
277 );
278
279 /**
280  * Remove a node from a list.
281  * @param self node to be removed
282  * @return self
283  */
284 LLIST_FUNC (LList llist_unlink (LList self),
285             llist_unlink_fast_ (self);
286             return self->next = self->prev = self;
287 );
288
289 /**
290  * Fix a node which got relocated in memory.
291  * It is supported to realloc/move list nodes in memory but one must call 'list_relocate' after doing so.
292  * @param self node which got relocated
293  * @return self
294  */
295 LLIST_FUNC (LList llist_relocate (LList self),
296             return self->next->prev = self->prev->next = self;
297 );
298
299 /**
300  * Insert a node after another.
301  * @param self node after which we want to insert
302  * @param next node which shall be inserted after self. Could already linked to a list from where it will be removed.
303  * @return self
304  */
305 LLIST_FUNC (LList llist_insert_next (LList self, LList next),
306             llist_unlink_fast_ (next);
307             self->next->prev = next;
308             next->prev = self;
309             next->next = self->next;
310             self->next = next;
311             return self;
312 );
313
314 /**
315  * Insert a node before another.
316  * @param self node before which we want to insert
317  * @param prev node which shall be inserted before self. Could already linked to a list from where it will be removed.
318  * @return self
319  */
320 LLIST_FUNC (LList llist_insert_prev (LList self, LList prev),
321             llist_unlink_fast_ (prev);
322             self->prev->next = prev;
323             prev->next = self;
324             prev->prev = self->prev;
325             self->prev = prev;
326             return self;
327 );
328
329
330 /**
331  * Move the content of a list after a node in another list.
332  * @param self node after which we want to insert a list
333  * @param next rootnode of the list which shall be inserted after self
334  * @return self
335  * next is a empty list after this call
336  */
337 LLIST_FUNC (LList llist_insertlist_next (LList self, LList next),
338             if (!llist_is_empty (next))
339               {
340                 self->next->prev = next->prev;
341                 next->prev->next = self->next;
342                 self->next = next->next;
343                 next->next->prev = self;
344
345                 next->prev = next->next = next;
346               }
347             return self;
348 );
349
350 /**
351  * Move the content of a list before a node in another list.
352  * @param self node before which we want to insert a list
353  * @param prev rootnode of the list which shall be inserted before self
354  * @return self
355  * prev is a empty list after this call
356  */
357 LLIST_FUNC (LList llist_insertlist_prev (LList self, LList prev),
358             if (!llist_is_empty (prev))
359               {
360                 self->prev->next = prev->next;
361                 prev->next->prev = self->prev;
362                 self->prev = prev->prev;
363                 prev->prev->next = self;
364
365                 prev->prev = prev->next = prev;
366               }
367             return self;
368 );
369
370 #if 0             //BUG("needs temporary")
371 /**
372  * Move a range of nodes after a given node.
373  * @param self node after 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_insertafter_range (LList self, LList start, LList end),
378             self->next->prev = end->prev;
379             end->prev->next = self->next;
380             end->prev = start->prev;
381             start->prev->next = end;
382             self->next = start;
383             start->prev = self;
384             return self;
385 );
386 #endif
387
388 #if 0             //BUG("needs temporary")
389 /**
390  * Move a range of nodes before a given node.
391  * @param self node before which the range shall be inserted
392  * @param start first node in range to be moved
393  * @param end node after the last node of the range
394  */
395 LLIST_FUNC (LList llist_inserbefore_range (LList self, LList start, LList end),
396             self->prev->next = start;
397             start->prev->next = end;
398             end->prev = start->prev;
399             start->prev = self->prev;
400             self->prev = end->prev;
401             end->prev->next = self;
402             return self;
403 );
404 #endif
405
406 /**
407  * Swap a node with its next node.
408  * @param self node to be advaced
409  * @return self
410  * advancing will not stop at tail, one has to check that if this is intended
411  */
412 LLIST_FUNC (LList llist_advance (LList self),
413             LList tmp = self->next->next;
414             tmp->prev = self;
415             self->next->prev = self->prev;
416             self->prev->next = self->next;
417             self->prev = self->next;
418             self->next->next = self;
419             self->next = tmp;
420             return self;
421 );
422
423 /**
424  * Swap a node with its previous node.
425  * @param self node to be retreated
426  * @return self
427  * retreating will not stop at head, one has to check that if this is intended
428  */
429 LLIST_FUNC (LList llist_retreat (LList self),
430             LList tmp = self->prev->prev;
431             tmp->next = self;
432             self->prev->next = self->next;
433             self->next->prev = self->prev;
434             self->next = self->prev;
435             self->prev->prev = self;
436             self->prev = tmp;
437             return self;
438 );
439
440
441 /**
442  * Get next node.
443  * @param self current node
444  * @return node after self
445  * Will not stop at tail
446  */
447 LLIST_FUNC (LList llist_next (const_LList self),
448             return self->next;
449 );
450
451 /**
452  * Get previous node.
453  * @param self current node
454  * @return node before self
455  * Will not stop at head
456  */
457 LLIST_FUNC (LList llist_prev (const_LList self),
458             return self->prev;
459 );
460
461 /**
462  * Advance a pointer to a node to its next node.
463  * @param self pointer-to-pointer to the current node
464  * *self will point to the next node after this call
465  */
466 LLIST_FUNC (void llist_forward (LList_ref self),
467             *self = (*self)->next;
468 );
469
470 /**
471  * Retreat a pointer to a node to its previous node.
472  * @param self pointer-to-pointer to the current node
473  * *self will point to the previous node after this call
474  */
475 LLIST_FUNC (void llist_backward (LList_ref self),
476             *self = (*self)->prev;
477 );
478
479 /**
480  * Get the nth element of a list.
481  * @param self list to be queried
482  * @param n nth element after (positive n) or before (negative n) self
483  * this function does not stop at head/tail.
484  */
485 LLIST_FUNC (LList llist_nth (LList self, int n),
486             if (n>0)
487               while (n--)
488                 self = llist_next (self);
489             else
490               while (n++)
491                 self = llist_prev (self);
492             return self;
493 );
494
495 /**
496  * Get the nth element of a list with a stop node.
497  * @param self list to be queried
498  * @param n nth element after (positive n) or before (negative n) self
499  * @param stop node which will abort the iteration
500  */
501 LLIST_FUNC (LList llist_get_nth_stop (LList self, int n, const_LList stop),
502             if (n>0)
503               while (n--)
504                 {
505                   self = llist_next (self);
506                   if (self == stop)
507                     return NULL;
508                 }
509             else
510               while (n++)
511                 {
512                   self = llist_prev (self);
513                   if (self == stop)
514                     return NULL;
515                 }
516             return self;
517 );
518
519 /*
520   some macros for convenience
521 */
522 #define llist_insert_head(list, element) llist_insert_next (list, element)
523 #define llist_insert_tail(list, element) llist_insert_prev (list, element)
524 #define llist_head llist_next
525 #define llist_tail llist_prev
526
527 #endif /* LLIST_H */
528 /*
529 // Local Variables:
530 // mode: C
531 // c-file-style: "gnu"
532 // End:
533 // arch-tag: e8fe4a59-fd55-4c45-b860-5cd1e0771213
534 // end_of_file
535 */
536
537 /*
538 //      Local Variables:
539 //      mode: C
540 //      c-file-style: "gnu"
541 //      indent-tabs-mode: nil
542 //      End:
543 */