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