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)         Lumiera.org
   7     2008,2009,          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
  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.
  40  *
  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
  49  */
  50
  51
  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.
  56 */
  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
  66
  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
  77
  78
  79 /*
  80  * Type of a llist node.
  81  */
  82 #ifndef LLIST_DEFINED
  83 #define LLIST_DEFINED
  84 struct llist_struct
  85 {
  86   struct llist_struct *next;
  87   struct llist_struct *prev;
  88 };
  89 #endif
  90 typedef struct llist_struct llist;
  91 typedef llist * LList;
  92 typedef const llist * const_LList;
  93 typedef llist ** LList_ref;
  94
  95
  96 /**
  97  * Macro to instantiate a local llist.
  98  * @param name of the llist node
  99  */
 100 #define LLIST_AUTO(name) llist name = {&name,&name}
 101
 102
 103 /*
 104   some macros for convenience
 105 */
 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
 110
 111 /**
 112  * cast back from a member of a structure to a pointer of the structure
 113  */
 114 /* example:
 115    struct foo
 116    {
 117      int bar;
 118      llist l;
 119    } x;
 120    LLIST_TO_STRUCTP (&x.l, foo, l)->bar
 121 */
 122 #define LLIST_TO_STRUCTP(llist, type, member) \
 123   ((type*)(((char*)(llist)) - offsetof(type, member)))
 124
 125 /**
 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
 129  */
 130 #define LLIST_FOREACH(list, node)               \
 131     for (LList node = llist_head (list);        \
 132          ! llist_is_end (node, list);           \
 133          llist_forward (&node))
 134
 135 /**
 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
 139  */
 140 #define LLIST_FOREACH_REV(list, node)           \
 141     for (LList node = llist_tail (list);        \
 142          ! llist_is_end (node, list);           \
 143          llist_backward (&node))
 144
 145
 146 /**
 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
 151  */
 152 #define LLIST_FORRANGE(start, end, node)        \
 153     for (LList node = start;                    \
 154          node != end;                           \
 155          llist_forward (&node))
 156
 157 /**
 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
 162  */
 163 #define LLIST_FORRANGE_REV(rstart, rend, node)  \
 164     for (LList node = rstart;                   \
 165          node != rend;                          \
 166          llist_backward (&node))
 167
 168
 169 /**
 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
 174  */
 175 #define LLIST_WHILE_HEAD(list, head)            \
 176     for (LList head = llist_head (list);        \
 177          !llist_is_empty (list);                \
 178          head = llist_head (list))
 179
 180 /**
 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
 185  */
 186 #define LLIST_WHILE_TAIL(list, tail)            \
 187     for (LList tail = llist_tail (list);        \
 188          !llist_is_empty (list);                \
 189          tail = llist_tail (list))
 190
 191 /**
 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
 196  */
 197 LLIST_FUNC (LList llist_init (LList self),
 198             return self->next = self->prev = self;
 199 );
 200
 201 /**
 202  * Check if a node is not linked with some other node.
 203  */
 204 LLIST_FUNC (int llist_is_empty (const_LList self),
 205             return self->next == self;
 206 );
 207
 208 /**
 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
 211  */
 212 LLIST_FUNC (int llist_is_single (const_LList self),
 213             return self->next->next == self;
 214 );
 215
 216 /**
 217  * Check for the head of a list.
 218  * @param self root of the list
 219  * @param head expected head of the list
 220  */
 221 LLIST_FUNC (int llist_is_head (const_LList self, const_LList head),
 222             return self->next == head;
 223 );
 224
 225 /**
 226  * Check for the tail of a list.
 227  * @param self root of the list
 228  * @param tail expected tail of the list
 229  */
 230 LLIST_FUNC (int llist_is_tail (const_LList self, const_LList tail),
 231             return self->prev == tail;
 232 );
 233
 234 /**
 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
 239  */
 240 LLIST_FUNC (int llist_is_end (const_LList self, const_LList end),
 241             return self == end;
 242 );
 243
 244 /**
 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
 248  */
 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)
 251               {
 252                 if (i == self)
 253                   return 1;
 254               }
 255             return 0;
 256 );
 257
 258 /**
 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
 263  */
 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)
 266               {
 267                 if (i == after)
 268                   return 1;
 269               }
 270             return 0;
 271 );
 272
 273 /**
 274  * Count the nodes of a list.
 275  * @param self root node of the list
 276  * @return number of nodes in self
 277  */
 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;
 283 );
 284
 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;
 290 );
 291
 292 /**
 293  * Remove a node from a list.
 294  * @param self node to be removed
 295  * @return self
 296  */
 297 LLIST_FUNC (LList llist_unlink (LList self),
 298             llist_unlink_fast_ (self);
 299             return self->next = self->prev = self;
 300 );
 301
 302 /**
 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
 310  */
 311 LLIST_FUNC (LList llist_relocate (LList self),
 312             return self->next->prev = self->prev->next = self;
 313 );
 314
 315
 316 /**
 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
 321  */
 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;
 329 );
 330
 331 /**
 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
 336  */
 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;
 344 );
 345
 346
 347 /**
 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
 353  */
 354 LLIST_FUNC (LList llist_insertlist_next (LList self, LList next),
 355             if (!llist_is_empty (next))
 356               {
 357                 self->next->prev = next->prev;
 358                 next->prev->next = self->next;
 359                 self->next = next->next;
 360                 next->next->prev = self;
 361
 362                 next->prev = next->next = next;
 363               }
 364             return self;
 365 );
 366
 367 /**
 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
 373  */
 374 LLIST_FUNC (LList llist_insertlist_prev (LList self, LList prev),
 375             if (!llist_is_empty (prev))
 376               {
 377                 self->prev->next = prev->next;
 378                 prev->next->prev = self->prev;
 379                 self->prev = prev->prev;
 380                 prev->prev->next = self;
 381
 382                 prev->prev = prev->next = prev;
 383               }
 384             return self;
 385 );
 386
 387 #if 0             //BUG("needs temporary")
 388 /**
 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
 393  */
 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;
 402 );
 403 #endif
 404
 405 #if 0             //BUG("needs temporary")
 406 /**
 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
 411  */
 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;
 420 );
 421 #endif
 422
 423 /**
 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
 428  */
 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;
 438 );
 439
 440 /**
 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
 445  */
 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;
 455 );
 456
 457
 458 /**
 459  * Get next node.
 460  * @param self current node
 461  * @return node after self
 462  * Will not stop at tail
 463  */
 464 LLIST_FUNC (LList llist_next (const_LList self),
 465             return self->next;
 466 );
 467
 468 /**
 469  * Get previous node.
 470  * @param self current node
 471  * @return node before self
 472  * Will not stop at head
 473  */
 474 LLIST_FUNC (LList llist_prev (const_LList self),
 475             return self->prev;
 476 );
 477
 478 /**
 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
 482  */
 483 LLIST_FUNC (void llist_forward (LList_ref self),
 484             *self = (*self)->next;
 485 );
 486
 487 /**
 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
 491  */
 492 LLIST_FUNC (void llist_backward (LList_ref self),
 493             *self = (*self)->prev;
 494 );
 495
 496 /**
 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.
 501  */
 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;
 510 );
 511
 512 /**
 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
 517  */
 518 LLIST_FUNC (LList llist_get_nth_stop (LList self, int n, const_LList stop),
 519             if (n>0)
 520               while (n--)
 521                 {
 522                   self = llist_next (self);
 523                   if (self == stop)
 524                     return NULL;
 525                 }
 526             else
 527               while (n++)
 528                 {
 529                   self = llist_prev (self);
 530                   if (self == stop)
 531                     return NULL;
 532                 }
 533             return self;
 534 );
 535
 536
 537 /**
 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
 545  */
 546 typedef int (*llist_cmpfn)(const_LList a, const_LList b, void* extra);
 547
 548
 549 /**
 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
 555  */
 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))
 563               {
 564                 LLIST_WHILE_HEAD (self, head)
 565                   llist_insert_prev (++n & 1 ? &left : &right, head);
 566
 567                 llist_sort (&left, cmp, extra);
 568                 llist_sort (&right, cmp, extra);
 569
 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);
 572
 573                 if (!llist_is_empty (&left))
 574                   llist_insertlist_prev (self, &left);
 575                 if (!llist_is_empty (&right))
 576                   llist_insertlist_prev (self, &right);
 577               }
 578             return self;
 579 )
 580
 581
 582 /**
 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
 590  */
 591 LLIST_FUNC (LList llist_find (const_LList self, const_LList templ, llist_cmpfn cmp, void* extra),
 592             LLIST_FOREACH(self, node)
 593             {
 594               if (!cmp (node, templ, extra))
 595                 return node;
 596             }
 597             return NULL;
 598 )
 599
 600
 601 /**
 602  * Find a element in list.
 603  * searches the list for a element in reverse order.
 604  * Does not change the list order.
 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 or NULL if nothing found
 609  */
 610 LLIST_FUNC (LList llist_rfind (const_LList self, const_LList templ, llist_cmpfn cmp, void* extra),
 611             LLIST_FOREACH_REV(self, node)
 612             {
 613               if (!cmp (node, templ, extra))
 614                 return node;
 615             }
 616             return NULL;
 617 )
 618
 619
 620 /**
 621  * Find a element in a unsorted list.
 622  * searches the list until it finds the searched element and moves it then to the head.
 623  * Useful if the order of the list is not required and few elements are frequently searched.
 624  * @param self list to be searched
 625  * @param templ template for the element being searched
 626  * @param cmp function for comparing 2 nodes
 627  * @return pointer to the found LList element (head) or NULL if nothing found
 628  */
 629 LLIST_FUNC (LList llist_ufind (LList self, const_LList templ, llist_cmpfn cmp, void* extra),
 630             LLIST_FOREACH(self, node)
 631             {
 632               if (!cmp (node, templ, extra))
 633                 {
 634                   if (llist_next(self) != node)
 635                     llist_insert_next (self, node);
 636                   return node;
 637                 }
 638             }
 639             return NULL;
 640 )
 641
 642
 643 /**
 644  * Find a element in a sorted list.
 645  * searches the list until it find the searched element, exits searching when found an element
 646  * biggier than the searched one.
 647  * @param self list to be searched
 648  * @param templ template for the element being searched
 649  * @param cmp function for comparing 2 nodes
 650  * @return pointer to the found LList element or NULL if nothing foound
 651  */
 652 LLIST_FUNC (LList llist_sfind (const_LList self, const_LList templ, llist_cmpfn cmp, void* extra),
 653             LLIST_FOREACH(self, node)
 654             {
 655               int c = cmp (node, templ, extra);
 656               if (!c)
 657                 return node;
 658               else if (c>0)
 659                 break;
 660             }
 661             return NULL;
 662 )
 663
 664
 665
 666 #endif /* LLIST_H */
 667 /*
 668 //      Local Variables:
 669 //      mode: C
 670 //      c-file-style: "gnu"
 671 //      indent-tabs-mode: nil
 672 //      End:
 673 */