ll.h File Reference

"Invasive" Linked List C templates More...

#include "pp.h"

Include dependency graph for ll.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines

#define sll_decllink(type, mlabel)   type* mlabel
 Declare a singly linked list "next" member template.
#define sll_initlink(type, mlabel, self)   (self)->mlabel = NULL
 Initialize a link.
#define sll_decllist(type, mlabel, ilabel)   type* ilabel
 Declare a singly linked list template.
#define sll_autolist(type, mlabel, ilabel)   type* ilabel = NULL
 Make a linked list from auto variables for stack or global use Uses non-standard ANSI extension: non-const initializers.
#define sll_autolist_static(type, mlabel, ilabel)   static type* ilabel = NULL
 Make a static linked list from auto variables for stack or global use Uses non-standard ANSI extension: non-const initializers.
#define sll_externlist(type, mlabel, ilabel)   extern type* ilabel
 Declare an extern linked list for sll_autolist or sll_decllist.
#define sll_initlist(type, mlabel, ilabel)   (ilabel) = NULL
 Initialize an empty list.
#define sll_initarray(type, mlabel, ilabel, array, count)
 Initialize a singly linked list from an array of objects.
#define sll_empty(type, mlabel, ilabel)   ( NULL == (ilabel) )
 Tell us if a list is empty.
#define sll_reset(type, mlabel, ilabel)
 Unlink all members; ilabel will be empty.
#define sll_next(type, mlabel, ilabel, curr)   ((curr) = (curr) ? ((curr)->mlabel) : NULL)
 Iterate to next member.
#define sll_foreach_const(type, mlabel, ilabel, iterator)
 Iterate through all members of a singly linked list with a const pointer. This is the simplest and fastest way to do it, but you can't modify the list while you do it. This will generally need to be wrapped in its own {} scope There is not enough state maintained here to remove a member, so don't try it.
#define sll_foreach(type, mlabel, ilabel, iterator)
 Iterate through all members of a singly linked list with a writable pointer This is the simplest and fastest way to do it, but you can't modify the list while you do it. This will generally need to be wrapped in its own {} scope There is not enough state maintained here to remove a member, so don't try it.
#define sll_foreach_deletable(type, mlabel, ilabel, iterator)
 Iterate through all members of a singly linked list, allowing deletions with 'sll_foreach_deletecurr' Deletion is possible, and iteration may continue after a deletion This will generally need to be wrapped in its own {} scope.
#define sll_foreach_deletable_reverse(type, mlabel, ilabel, iterator)
 Iterate through all members of a singly linked list; LIST ORDER WILL BE REVERSED AFTER THIS IS DONE This will generally need to be wrapped in its own {} scope Why? It's often necessary during animation cycles to do a list forwards, then backwards. Do it twice to get original list.
#define sll_foreach_deletecurr(type, mlabel, ilabel, iterator)
 ONLY in sll_foreach_deletable, or sll_foreach_deletable_reverse, safely remove current member during iteration.
#define sll_push_front(type, mlabel, ilabel, item)
 Push a new item onto front of a singly linked list Preferred method.
#define sll_push_back(type, mlabel, ilabel, item)
 Add a new item onto the FAR END of the list Use sll_push_front whenever possible: This has to iterate through the whole list!
#define sll_front(type, mlabel, ilabel, get)   {(get) = (ilabel);}
 Get first item in the list.
#define sll_back(type, mlabel, ilabel, get)
 Get last item in the list (requires traversal of list!).
#define sll_pop_front(type, mlabel, ilabel, get)
 Pop first item in list off; unlinks and returns first member.
#define sll_pop_back(type, mlabel, ilabel, get)
 Pop LAST item in list off; unlinks and returns last member (requires traversal of list!).
#define sll_erase(type, mlabel, ilabel, item)
 Seek a member and remove it (requires traversal of list!) I recommend you mark members for later deletion, or identify deleted items while traversing with 'deletable' iterator, instead.
#define sll_remove_filter(type, mlabel, ilabel, criteria)
 Seek member(s) in the list and remove it(them) based on a callback.
#define sll_move_filter(type, mlabel, ilabel, criteria, target)
 Seek member(s) in the list and move it(them) to "target" based on a callback.
#define sll_size(type, mlabel, ilabel, count)
 Tally members and return total in 'count'.
#define sll_assert_size(type, mlabel, ilabel, count)
 Tally members and compare to a count.
#define sll_splice(type, mlabel, toFirst, fromFirst)
 Append members from one singly linked list (OF THE SAME KIND) to another.
#define sll_bsort(type, mlabel, ilabel, compare)
 BUBBLE Sort members by some criteria.
#define sll_decl_qsort(type, mlabel, ilabel, name)   void name( type** front, type** back, int (*compare)(const void* p1, const void* p2) )
 Declare a singly linked qsort.
#define sll_qsort(type, mlabel, ilabel, name, compare)   name( &(ilabel), NULL, (int (*)(const void*, const void*))(compare) );\
 Invoke singly linked bubble sort.
#define sll_mfg_qsort(type, mlabel, ilabel, deref, name)
 Manufacture a singly linked bubble sort.
#define _dllnext(mlabel)   ppConcat(mlabel,_next)
#define _dllprev(mlabel)   ppConcat(mlabel,_prev)
#define _dllfront(ilabel)   ppConcat(ilabel,_front)
#define _dllback(ilabel)   ppConcat(ilabel,_back)
#define dll_decllink(type, mlabel)
 Declare a doubly linked list member template.
#define dll_initlink(type, mlabel, curr)   (curr)->_dllprev(mlabel) = (curr)->_dllnext(mlabel) = NULL
 Initialize a link.
#define dll_decllist(type, mlabel, ilabel)
 Declare a doubly linked list template.
#define dll_islinked(type, mlabel, ilabel, curr)   ( (curr)->_dllprev(mlabel) || (curr)->_dllnext(mlabel) || (_dllfront(ilabel)==(curr) && _dllback(ilabel)==(curr)) )
 Check to see if a link is part of a list somewhere.
#define dll_initlist(type, mlabel, ilabel)   _dllfront(ilabel) = _dllback(ilabel) = NULL
 Make a singly linked list initially empty.
#define dll_autolist(type, mlabel, ilabel)
 Make a linked list from auto variables for stack or global use.
#define dll_autolist_static(type, mlabel, ilabel)
 Make a static linked list from auto variables for stack or global use.
#define dll_externlist(type, mlabel, ilabel)
 Declare an extern linked list for dll_autolist or dll_decllist.
#define dll_initarray(type, mlabel, ilabel, array, count)
 Initialize a doubly linked list from an array of objects.
#define dll_empty(type, mlabel, ilabel)   ( NULL == _dllfront(ilabel) )
 Tell us if a list is empty.
#define dll_check_link(type, mlabel, ilabel, item)
 Look at a link: see if its neighbors point back it it.
#define dll_check(type, mlabel, ilabel)
 Just check the _dllfront(ilabel) and _dllback(ilabel) members of a list for sanity.
#define dll_check_thorough(type, mlabel, ilabel, onfailure)
 Check list and loop through whole list for sanity - Very time consuming TOP-LEVEL check.
#define dll_reset(type, mlabel, ilabel)
 Unlink all members.
#define dll_next(type, mlabel, ilabel, curr)   ((curr) = (curr) ? ((curr)->_dllnext(mlabel)) : NULL)
 Safely iterate to next member.
#define dll_prev(type, mlabel, ilabel, curr)   ((curr) = (curr) ? ((curr)->_dllprev(mlabel)) : NULL)
 Iterate to previous member.
#define dll_foreach_const(type, mlabel, ilabel, iterator)
 Iterate through all members of a doubly linked list with a constant iterator.
#define dll_foreach_reverse_const(type, mlabel, ilabel, iterator)
 Iterate through all members of a doubly linked list BACKWARDS with a constant iterator.
#define dll_foreach(type, mlabel, ilabel, iterator)
 Iterate through all members of a doubly linked list.
#define dll_foreach_reverse(type, mlabel, ilabel, iterator)
 Iterate through all members of a doubly linked list - BACKWARDS.
#define dll_foreach_deletable(type, mlabel, ilabel, iterator)
 Iterate through all members of a singly linked list, allowing deletions.
#define dll_foreach_deletable_reverse(type, mlabel, ilabel, iterator)
 Iterate through all members of a singly linked list backwards.
#define dll_push_front(type, mlabel, ilabel, item)
 Push a new item onto the singly linked list.
#define dll_push_back(type, mlabel, ilabel, item)
 Add a new item onto the FAR END of the list.
#define dll_insert(type, mlabel, ilabel, after, item)
 Add a new item after a particular item.
#define dll_insert_before(type, mlabel, ilabel, before, item)
 Add a new item before a particular item.
#define dll_front(type, mlabel, ilabel, get)   {(get) = (_dllfront(ilabel));}
 Get the first item in the list.
#define dll_back(type, mlabel, ilabel, get)   {(get) = (_dllback(ilabel));}
 Get the last item in the list.
#define dll_pop_front(type, mlabel, ilabel, get)
 Get AND REMOVE the first item in the list.
#define dll_pop_back(type, mlabel, ilabel, get)
 Get AND REMOVE the last item in the list.
#define dll_erase(type, mlabel, ilabel, item)
 Seek a member and remove it.
#define dll_remove_filter(type, mlabel, ilabel, criteria)
 Seek member(s) in the list and remove it(them) based on a callback.
#define dll_move_filter(type, mlabel, ilabel, criteria, target)
 Seek member(s) in the list and move it(them) to "target" based on a callback.
#define dll_size(type, mlabel, ilabel, count)   sll_size( type,_dllnext(mlabel), _dllfront(ilabel), count )
 Tally members.
#define dll_assert_size(type, mlabel, ilabel, count)   sll_assert_size( type,_dllnext(mlabel), _dllfront(ilabel), count )
 Verify the expected size.
#define dll_splice(type, mlabel, ilabelto, ilabelfrom)
 Append members from one singly linked list (OF THE SAME KIND) to another.
#define dll_rebuild_back(type, mlabel, ilabel)
 Rebuild list "prev" links from front "next" links.
#define dll_rebuild_front(type, mlabel, ilabel)
 Rebuild list "next" links from front "prev" links.
#define dll_bsort(type, mlabel, ilabel, compare)
 Invoke doubly linked bubble sort.
#define dll_decl_qsort(type, mlabel, ilabel, name)   sll_decl_qsort(type,_dllnext(mlabel), _dllfront(ilabel), name )
 Declare a doubly linked qsort.
#define dll_mfg_qsort(type, mlabel, ilabel, deref, name)   sll_mfg_qsort(type,_dllnext(mlabel), _dllfront(ilabel), deref, name )
 Manufacture a doubly linked qsort.
#define dll_qsort(type, mlabel, ilabel, name, compare)
 Invoke doubly linked qsort.

Detailed Description

"Invasive" Linked List C templates

Author:
David Mace
This allows for the same object (provided multiple links) to be in multiple lists. Most invasive solutions don't allow that.

Various lists can share the same link. In other words, the link for "free" and "in use" lists can be the same link in the structure/class, so there can be no confusion about which list it is in.

The doubly-linked list is compatible with the singly-linked one.

Extremely low-overhead. No allocations; suitable for embedded solutions where you don't want to seperately allocate links, but will probably link most of everything that has a link in it.

The singly linked list is FAR more efficient if you PUSH to the front, and mark for later deletion while some other (deletable) iteration is occurring.

A bubble sort and basic qsort are provided for both lists.

Template parameters: type Type of struct link resides in mlabel Name of the link member we're linking with in that struct ilabel Name of the list instance we're dealing with, WITH any indirection needed to find it.

In other words, if you have:

typedef struct thing { sll_decllink(struct thing,thingNext ); } thing; typedef struct ThingContainer { sll_decllist(thing,thingNext, things ); } ThingContainer; ThingContainer myThings;

sll_initlist(thing,thingNext, &myThings.things );

Though this indirection's purpose is not particularly obvious at first glance, consider that for the doubly-linked list, we need to access two different variables (prev and next) from the same directive. The prev and next differentiation is token-pasted onto the end of what's passed.

BTW, ThingContainer does not have to be a different thing from 'thing'... thing myThings2; sll_initlist(thing,thingNext, &myThings2.thingNext );

So, yes, we do support trivially turning links into lists.

Generally, these are meant to be put into functions that perform operations, rather than be operations and interfaces unto themselves. Like STL, massive code bloat can result from careless use of some of these macros.

Two tools are your best friend when dealing with these macros: cpp: The c preprocessor. Most comilers will do this job with a flag. indent (or equivalent): The gnu code beautifier.

If there are problems, preprocess into a file and 'indent' the file to make it viewable. You'll generally want to make a batch/script that does the job with the appropriate search paths and flags for your project. Paste the functions/code that are giving you grief (at compile or run time) into your code where the macro expanded, and comment out the macro invokation. Now you can step through the result and see the errors clearly. Don't forget to put the ORIGINAL code back, or you'll sit there like an fool making changes, wondering why they don't have effects.

You may even want to add a step to your makefile to preprocess (preserving line formatting, comments, etc.) and indent the result while building. Doing it this way you will always get to "step" the actual code that was generated, which is a BIG winning factor over C++ templatss. CPP is actually quite fast when you keep the dependencies in check. So is indent. I wish compilers had a mode to generate their output based on this behavior.

This preprocess/indent technique is also useful for "source code" or "object code" distributions that you don't want to be changed or "hacked". Once a certain amount of repetitive code exists, making changes and having them work goes from progressively more difficult to nearly impossible. In case you're evil.

More on this in the bigger, fatter, nastier macro behavior.

Definition in file ll.h.

Define Documentation

#define _dllback ( ilabel   )     ppConcat(ilabel,_back)

Token paster to make list instance/label into list instance/label_back

Definition at line 787 of file ll.h.

#define _dllfront ( ilabel   )     ppConcat(ilabel,_front)

Token paster to make list instance/label into list instance/label_front

Definition at line 785 of file ll.h.

#define _dllnext ( mlabel   )     ppConcat(mlabel,_next)

Token paster to make member label into member label_next

Definition at line 781 of file ll.h.

#define _dllprev ( mlabel   )     ppConcat(mlabel,_prev)

Token paster to make member label into member label_prev

Definition at line 783 of file ll.h.

#define dll_assert_size ( type,
mlabel,
ilabel,
count   )     sll_assert_size( type,_dllnext(mlabel), _dllfront(ilabel), count )

Verify the expected size.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
count The count we're verifying

Definition at line 1408 of file ll.h.

#define dll_autolist ( type,
mlabel,
ilabel   ) 

Value:

type* _dllfront(ilabel) = NULL;\
    type* _dllback(ilabel) = NULL
Make a linked list from auto variables for stack or global use.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist

Definition at line 848 of file ll.h.

#define dll_autolist_static ( type,
mlabel,
ilabel   ) 

Value:

static type* _dllfront(ilabel) = NULL;\
    static type* _dllback(ilabel) = NULL
Make a static linked list from auto variables for stack or global use.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist

Definition at line 859 of file ll.h.

#define dll_back ( type,
mlabel,
ilabel,
get   )     {(get) = (_dllback(ilabel));}

Get the last item in the list.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
get type* Pointer to receive value

Definition at line 1264 of file ll.h.

#define dll_bsort ( type,
mlabel,
ilabel,
compare   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        sll_bsort(type,_dllnext(mlabel), _dllfront(ilabel), compare );\
        dll_rebuild_back(type,mlabel, ilabel );\
    }
Invoke doubly linked bubble sort.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
compare Like qsort comparison function, but can be a macro

Definition at line 1488 of file ll.h.

#define dll_check ( type,
mlabel,
ilabel   ) 

Value:

(\
        ( !_dllback(ilabel) && !_dllfront(ilabel) ) ||\
        (\
            ( _dllback(ilabel) && _dllfront(ilabel) && !_dllfront(ilabel)->_dllprev(mlabel) && !_dllback(ilabel)->_dllnext(mlabel) ) &&\
            (\
                ( _dllback(ilabel) == _dllfront(ilabel) ) ||\
                ( _dllfront(ilabel)->_dllnext(mlabel)->_dllprev(mlabel) == _dllfront(ilabel) && _dllback(ilabel)->_dllprev(mlabel)->_dllnext(mlabel) == _dllback(ilabel) )\
            )\
        )\
    )
Just check the _dllfront(ilabel) and _dllback(ilabel) members of a list for sanity.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist

Definition at line 933 of file ll.h.

#define dll_check_link ( type,
mlabel,
ilabel,
item   ) 

Value:

( \
        (item) && \
        ( (item)->_dllprev(mlabel) ? ((item)->_dllprev(mlabel)->_dllnext(mlabel) == (item)) : (item) == (_dllfront(ilabel)) ) &&\
        ( (item)->_dllnext(mlabel) ? ((item)->_dllnext(mlabel)->_dllprev(mlabel) == (item)) : (item) == (_dllback(ilabel)) )\
    )
Look at a link: see if its neighbors point back it it.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
item The link to check

Definition at line 919 of file ll.h.

#define dll_check_thorough ( type,
mlabel,
ilabel,
onfailure   ) 

Check list and loop through whole list for sanity - Very time consuming TOP-LEVEL check.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
onfailure Callback for list check failure; a macro or function that takes a string, then a (type*) for the head, tail and bent link it failed on. OnFailure is a macro or function in the form of void onfailure( const char* sz, type* front, type* back, type* link ) and is called with details about problems.

Definition at line 956 of file ll.h.

#define dll_decl_qsort ( type,
mlabel,
ilabel,
name   )     sll_decl_qsort(type,_dllnext(mlabel), _dllfront(ilabel), name )

Declare a doubly linked qsort.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
name What to call the resulting function

Definition at line 1503 of file ll.h.

#define dll_decllink ( type,
mlabel   ) 

Value:

type*   _dllprev(mlabel);\
    type*   _dllnext(mlabel)
Declare a doubly linked list member template.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link

Definition at line 795 of file ll.h.

#define dll_decllist ( type,
mlabel,
ilabel   ) 

Value:

type*   _dllfront(ilabel);\
    type*   _dllback(ilabel)
Declare a doubly linked list template.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template: What to call this label in the container it's declared in

Definition at line 816 of file ll.h.

#define dll_empty ( type,
mlabel,
ilabel   )     ( NULL == _dllfront(ilabel) )

Tell us if a list is empty.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist

Definition at line 909 of file ll.h.

#define dll_erase ( type,
mlabel,
ilabel,
item   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        assert( dll_check_link(type,mlabel, ilabel, item ) ); /* Link sanity */\
        if( (item)->_dllprev(mlabel) )\
        {\
            (item)->_dllprev(mlabel)->_dllnext(mlabel) = (item)->_dllnext(mlabel);\
        }\
        else\
        {\
            (_dllfront(ilabel)) = (item)->_dllnext(mlabel);\
        }\
        if( (item)->_dllnext(mlabel) )\
        {\
            (item)->_dllnext(mlabel)->_dllprev(mlabel) = (item)->_dllprev(mlabel);\
        }\
        else\
        {\
            (_dllback(ilabel)) = (item)->_dllprev(mlabel);\
        }\
        dll_initlink(type,mlabel, item );\
    }
Seek a member and remove it.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
item Item to remove
Item MUST be a member of this list; you will definitely cause "bad things" if it isn't

Definition at line 1323 of file ll.h.

#define dll_externlist ( type,
mlabel,
ilabel   ) 

Value:

extern type* _dllfront(ilabel);\
    extern type* _dllback(ilabel)
Declare an extern linked list for dll_autolist or dll_decllist.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist

Definition at line 870 of file ll.h.

#define dll_foreach ( type,
mlabel,
ilabel,
iterator   ) 

Value:

type* iterator = (_dllfront(ilabel)); \
    for ( ; iterator; iterator = iterator->_dllnext(mlabel) )
Iterate through all members of a doubly linked list.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
iterator What you want to call the iterator
This is the simplest and fastest way to do it, but you can't modify the list while you do it. This will generally need to be wrapped in its own {} scope

Definition at line 1072 of file ll.h.

Referenced by ctl_memory_dump().

#define dll_foreach_const ( type,
mlabel,
ilabel,
iterator   ) 

Value:

const type* iterator = (_dllfront(ilabel)); \
    for ( ; iterator; iterator = iterator->_dllnext(mlabel) )
Iterate through all members of a doubly linked list with a constant iterator.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
iterator What you want to call the iterator
This is the simplest and fastest way to do it, but you can't modify the list while you do it. This will generally need to be wrapped in its own {} scope

Definition at line 1042 of file ll.h.

#define dll_foreach_deletable ( type,
mlabel,
ilabel,
iterator   ) 

Value:

type* iterator = (_dllfront(ilabel));\
    type* ppConcat3(__ll_,iterator,_next) = iterator?iterator->_dllnext(mlabel):NULL; \
    for ( ; iterator; iterator = ppConcat3(__ll_,iterator,_next), dll_next(type,mlabel, ilabel, ppConcat3(__ll_,iterator,_next) ) )
Iterate through all members of a singly linked list, allowing deletions.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
iterator What you want to call the iterator
This will generally need to be wrapped in its own {} scope

Definition at line 1101 of file ll.h.

#define dll_foreach_deletable_reverse ( type,
mlabel,
ilabel,
iterator   ) 

Value:

type* iterator = (_dllback(ilabel));\
    type* ppConcat3(__ll_,iterator,_next) = iterator?iterator->_dllprev(mlabel):NULL; \
    for ( ; iterator; iterator = ppConcat3(__ll_,iterator,_next), dll_prev(type,mlabel, ilabel, ppConcat3(__ll_,iterator,_next) ) )
Iterate through all members of a singly linked list backwards.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
iterator What you want to call the iterator
This will generally need to be wrapped in its own {} scope

Definition at line 1116 of file ll.h.

#define dll_foreach_reverse ( type,
mlabel,
ilabel,
iterator   ) 

Value:

type* iterator = (_dllback(ilabel)); \
    for( ; iterator; iterator = iterator->_dllprev(mlabel) )
Iterate through all members of a doubly linked list - BACKWARDS.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
iterator What you want to call the iterator
This is the simplest and fastest way to do it, but you can't modify the list while you do it. This will generally need to be wrapped in its own {} scope

Definition at line 1087 of file ll.h.

#define dll_foreach_reverse_const ( type,
mlabel,
ilabel,
iterator   ) 

Value:

const type* iterator = (_dllback(ilabel)); \
    for( ; iterator; iterator = iterator->_dllprev(mlabel) )
Iterate through all members of a doubly linked list BACKWARDS with a constant iterator.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
iterator What you want to call the iterator
This is the simplest and fastest way to do it, but you can't modify the list while you do it. This will generally need to be wrapped in its own {} scope

Definition at line 1057 of file ll.h.

#define dll_front ( type,
mlabel,
ilabel,
get   )     {(get) = (_dllfront(ilabel));}

Get the first item in the list.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
get type* Pointer to receive value

Definition at line 1253 of file ll.h.

#define dll_initarray ( type,
mlabel,
ilabel,
array,
count   ) 

Value:

{\
        size_t __ll_remain = (size_t)(count)-1;\
        type* __ll_fromHead = (array);\
        type* __ll_fromTail = (array)+__ll_remain;\
        (_dllfront(ilabel)) = __ll_fromHead;\
        (_dllback(ilabel)) = __ll_fromTail;\
        while( __ll_remain-- )\
        {\
            __ll_fromHead->_dllnext(mlabel) = __ll_fromHead+1;\
            __ll_fromTail->_dllprev(mlabel) = __ll_fromTail-1;\
            __ll_fromHead++;\
            __ll_fromTail--;\
        }\
        (_dllfront(ilabel))->_dllprev(mlabel) = NULL;\
        (_dllback(ilabel))->_dllnext(mlabel) = NULL;\
    }
Initialize a doubly linked list from an array of objects.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
array Pointer to start of array of members
count Count of members in array

Definition at line 883 of file ll.h.

#define dll_initlink ( type,
mlabel,
curr   )     (curr)->_dllprev(mlabel) = (curr)->_dllnext(mlabel) = NULL

Initialize a link.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
curr Instance of link we are initializing

Definition at line 806 of file ll.h.

#define dll_initlist ( type,
mlabel,
ilabel   )     _dllfront(ilabel) = _dllback(ilabel) = NULL

Make a singly linked list initially empty.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist

Definition at line 838 of file ll.h.

Referenced by SocketsShutdown().

#define dll_insert ( type,
mlabel,
ilabel,
after,
item   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        if( after )\
        {   /* Insert link after 'after' */ \
            (item)->_dllnext(mlabel) = (after)->_dllnext(mlabel);\
            (item)->_dllprev(mlabel) = (after);\
            (after)->_dllnext(mlabel) = (item);\
            if( (item)->_dllnext(mlabel) )\
                (item)->_dllnext(mlabel)->_dllprev(mlabel) = (item);\
            else\
                (_dllback(ilabel)) = (item);\
        }\
        else\
        {   /* Push front */\
            (item)->_dllnext(mlabel) = (_dllfront(ilabel));\
            (item)->_dllprev(mlabel) = NULL;\
            if( (_dllfront(ilabel)) )\
                (_dllfront(ilabel))->_dllprev(mlabel) = (item);\
            else\
                (_dllback(ilabel)) = (item);\
            (_dllfront(ilabel)) = (item);\
        }\
    }
Add a new item after a particular item.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
after Member (that MUST be in this list) to insert 'item' after
item What to add
Item MUST NOT be a member of some other list.

Definition at line 1184 of file ll.h.

#define dll_insert_before ( type,
mlabel,
ilabel,
before,
item   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        if( before )\
        {   /* Insert link before 'before' */ \
            (item)->_dllprev(mlabel) = (before)->_dllnext(mlabel);\
            (item)->_dllnext(mlabel) = (before);\
            (before)->_dllprev(mlabel) = (item);\
            if( (item)->_dllprev(mlabel) )\
                (item)->_dllprev(mlabel)->_dllnext(mlabel) = (item);\
            else\
                (_dllfront(ilabel)) = (item);\
        }\
        else\
        {   /* push_back */\
            (item)->_dllnext(mlabel) = NULL;\
            (item)->_dllprev(mlabel) = (_dllback(ilabel));\
            if( _dllback(ilabel) )\
                (_dllback(ilabel))->_dllnext(mlabel) = (item);\
            else\
                (_dllfront(ilabel)) = (item);\
            (_dllback(ilabel)) = (item);\
        }\
    }
Add a new item before a particular item.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
before Member (that MUST be in this list) to insert 'item' before
item What to add
Item MUST NOT be a member of some other list.

Definition at line 1220 of file ll.h.

#define dll_islinked ( type,
mlabel,
ilabel,
curr   )     ( (curr)->_dllprev(mlabel) || (curr)->_dllnext(mlabel) || (_dllfront(ilabel)==(curr) && _dllback(ilabel)==(curr)) )

Check to see if a link is part of a list somewhere.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
curr Instance of link we are checking

Definition at line 828 of file ll.h.

#define dll_mfg_qsort ( type,
mlabel,
ilabel,
deref,
name   )     sll_mfg_qsort(type,_dllnext(mlabel), _dllfront(ilabel), deref, name )

Manufacture a doubly linked qsort.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
deref Macro to perform dereference to sortable data
name What to call the resulting function

Definition at line 1515 of file ll.h.

#define dll_move_filter ( type,
mlabel,
ilabel,
criteria,
target   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        {\
            dll_foreach_deletable(type,mlabel, _dllfront(ilabel), __ll_iterate_move )\
            {\
                if ( criteria(__ll_iterate_delete) ) \
                {\
                    dll_erase(type,mlabel, ilabel, __ll_iterate_delete );\
                    dll_push_back(type,mlabel, target, __ll_iterate_move );\
                }\
            }\
        }\
    }
Seek member(s) in the list and move it(them) to "target" based on a callback.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
criteria A boolean macro or function that takes a list member pointer and returns non-zero if it should be removed
target List to receive removed items

Definition at line 1375 of file ll.h.

#define dll_next ( type,
mlabel,
ilabel,
curr   )     ((curr) = (curr) ? ((curr)->_dllnext(mlabel)) : NULL)

Safely iterate to next member.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
curr Pointer to current, to be modified to next

Definition at line 1017 of file ll.h.

#define dll_pop_back ( type,
mlabel,
ilabel,
get   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        (get) = (_dllback(ilabel));\
        if( (get) && (get)->_dllprev(mlabel) )\
        {\
            (_dllback(ilabel)) = (get)->_dllprev(mlabel);\
            (get)->_dllprev(mlabel)->_dllnext(mlabel) = NULL;\
        }\
        else\
        {\
            (_dllfront(ilabel)) = (_dllback(ilabel)) = NULL;\
        }\
    }
Get AND REMOVE the last item in the list.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
get type* Pointer to receive value

Definition at line 1298 of file ll.h.

#define dll_pop_front ( type,
mlabel,
ilabel,
get   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        (get) = (_dllfront(ilabel));\
        if( (get) && (get)->_dllnext(mlabel) )\
        {\
            (_dllfront(ilabel)) = (get)->_dllnext(mlabel);\
            (get)->_dllnext(mlabel)->_dllprev(mlabel) = NULL;\
        }\
        else\
        {\
            (_dllfront(ilabel)) = (_dllback(ilabel)) = NULL;\
        }\
    }
Get AND REMOVE the first item in the list.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
get type* Pointer to receive value

Definition at line 1275 of file ll.h.

#define dll_prev ( type,
mlabel,
ilabel,
curr   )     ((curr) = (curr) ? ((curr)->_dllprev(mlabel)) : NULL)

Iterate to previous member.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
curr Pointer to current, to be modified to prev

Definition at line 1028 of file ll.h.

#define dll_push_back ( type,
mlabel,
ilabel,
item   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        (item)->_dllnext(mlabel) = NULL;\
        (item)->_dllprev(mlabel) = (_dllback(ilabel));\
        if( _dllback(ilabel) )\
        {\
            (_dllback(ilabel))->_dllnext(mlabel) = (item);\
        }\
        else\
        {\
            (_dllfront(ilabel)) = (item);\
        }\
        (_dllback(ilabel)) = (item);\
    }
Add a new item onto the FAR END of the list.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
item What to add
Item MUST NOT be a member of some other list.

Definition at line 1157 of file ll.h.

Referenced by Socket_Create().

#define dll_push_front ( type,
mlabel,
ilabel,
item   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        (item)->_dllnext(mlabel) = (_dllfront(ilabel));\
        (item)->_dllprev(mlabel) = NULL;\
        if( (_dllfront(ilabel)) )\
        {\
            (_dllfront(ilabel))->_dllprev(mlabel) = (item);\
        }\
        else\
        {\
            (_dllback(ilabel)) = (item);\
        }\
        (_dllfront(ilabel)) = (item);\
    }
Push a new item onto the singly linked list.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
item What to add
Item MUST NOT be a member of some other list.

Definition at line 1131 of file ll.h.

#define dll_qsort ( type,
mlabel,
ilabel,
name,
compare   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        name( &_dllfront(ilabel), &_dllback(ilabel), (int (*)(const void*, const void*))(compare) );\
        dll_rebuild_back(type,mlabel, ilabel );\
    }
Invoke doubly linked qsort.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
compare Like qsort comparison function
name What to call the resulting function

Definition at line 1527 of file ll.h.

#define dll_rebuild_back ( type,
mlabel,
ilabel   ) 

Value:

{\
        /* Now that we've sorted the _dllnext(mlabel) links, fixup the _dllprev(mlabel) links */\
        type* __ll_iterator_prev = NULL; \
        type* iterator = (_dllfront(ilabel));\
        type* __ll_iterator_next = iterator?iterator->_dllnext(mlabel):NULL; \
        for ( ; iterator; __ll_iterator_prev = iterator, iterator = __ll_iterator_next, sll_next(type,_dllnext(mlabel), _dllfront(ilabel), __ll_iterator_next ) )\
        {\
            iterator->_dllprev(mlabel) = __ll_iterator_prev;\
        }\
        (_dllback(ilabel)) = __ll_iterator_prev;\
    }\
Rebuild list "prev" links from front "next" links.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist

Definition at line 1447 of file ll.h.

#define dll_rebuild_front ( type,
mlabel,
ilabel   ) 

Value:

{\
        /* Now that we've sorted the _dllnext(mlabel) links, fixup the _dllprev(mlabel) links */\
        type* __ll_iterator_next = NULL; \
        type* iterator = (_dllback(ilabel));\
        type* __ll_iterator_prev = iterator?iterator->_dllprev(mlabel):NULL; \
        for ( ; iterator; __ll_iterator_next = iterator, iterator = __ll_iterator_prev, sll_next(type,_dllprev(mlabel), _dllback(ilabel), __ll_iterator_prev ) )\
        {\
            iterator->_dllnext(mlabel) = __ll_iterator_next;\
        }\
        (_dllfront(ilabel)) = __ll_iterator_next;\
    }\
Rebuild list "next" links from front "prev" links.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist

Definition at line 1467 of file ll.h.

#define dll_remove_filter ( type,
mlabel,
ilabel,
criteria   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        {\
            dll_foreach_deletable(type,mlabel, ilabel, __ll_iterate_delete )\
            {\
                if ( criteria(__ll_iterate_delete) ) \
                    dll_erase(type,mlabel, ilabel, __ll_iterate_delete );\
            }\
        }\
    }
Seek member(s) in the list and remove it(them) based on a callback.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
criteria A boolean macro or function that takes a list member pointer and returns non-zero if it should be removed

Definition at line 1354 of file ll.h.

#define dll_reset ( type,
mlabel,
ilabel   ) 

Value:

{\
        type* __dllCurr = (_dllfront(ilabel));\
        (_dllfront(ilabel)) = (_dllback(ilabel)) = NULL;\
        while( _dllCurr )\
        {\
            type* __dllNext = __dllCurr->_dllnext(mlabel);\
            __dllCurr->_dllnext(mlabel) = __dllCurr->_dllprev(mlabel) = NULL;\
            __dllCurr = __dllNext;\
        }\
    }
Unlink all members.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist

Definition at line 997 of file ll.h.

#define dll_size ( type,
mlabel,
ilabel,
count   )     sll_size( type,_dllnext(mlabel), _dllfront(ilabel), count )

Tally members.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist
count A size_t to receive count of members

Definition at line 1398 of file ll.h.

#define dll_splice ( type,
mlabel,
ilabelto,
ilabelfrom   ) 

Value:

{\
        assert( dll_check(type,mlabel, ilabelto ) ); /* List sanity */\
        assert( dll_check(type,mlabel, ilabelfrom ) ); /* List sanity */\
        if( _dllback(ilabelto) )\
        {\
            if( _dllfront(ilabelfrom) )\
            {\
                (_dllfront(ilabelfrom))->_dllprev(mlabel) = (_dllback(ilabelto));\
                (_dllback(ilabelto))->_dllnext(mlabel) = (_dllfront(ilabelfrom));\
                (_dllback(ilabelto)) = (_dllback(ilabelfrom));\
            }\
        }\
        else\
        {\
            (_dllfront(ilabelto)) = (_dllfront(ilabelfrom));\
            (_dllback(ilabelto)) = (_dllback(ilabelfrom));\
        }\
        _dllfront(ilabelfrom) = _dllback(ilabelfrom) = NULL;\
    }
Append members from one singly linked list (OF THE SAME KIND) to another.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabelto List that will contain both lists
ilabelfrom List that will be empty after this, because all of its members are in ilabelto

Definition at line 1418 of file ll.h.

#define sll_empty ( type,
mlabel,
ilabel   )     ( NULL == (ilabel) )

Tell us if a list is empty.

Parameters:
type Template: Structure type this link belongs to.
mlabel Template: A unique label for this link
ilabel Template/param: Whatever dereferencing is required + the base ilabel from sll_decllist

Definition at line 225 of file ll.h.

Generated on Fri Jan 2 15:28:35 2009 for Squat by  doxygen 1.5.6