ll.h

Go to the documentation of this file.

#ifndef LL_H
#define LL_H

/* If assert hasn't been included, skip extra sanity checks */
#ifndef assert
#define assert(v)
#endif

/* Get preprocessor macros this needs */
#ifndef PP_H
#include "pp.h"
#endif

#define sll_decllink(type,mlabel)\
    type*   mlabel

#define sll_initlink(type,mlabel, self)\
    (self)->mlabel = NULL

#define sll_decllist(type,mlabel, ilabel)\
    type*   ilabel

#define sll_autolist(type,mlabel, ilabel)\
    type*   ilabel = NULL

#define sll_autolist_static(type,mlabel, ilabel)\
    static type*    ilabel = NULL

#define sll_externlist(type,mlabel, ilabel)\
    extern type*    ilabel

#define sll_initlist(type,mlabel, ilabel ) \
    (ilabel) = NULL

#define sll_initarray(type,mlabel, ilabel, array,count) \
    {\
        type* ppScr2(sllInit,array) = (array);\
        type* ppScr2(sllInit,last) = ppScr2(sllInit,array) + (count) - 1;\
        type* ppScr2(sllInit,curr) = ppScr2(sllInit,last);\
        ppScr2(sllInit,last)->mlabel = NULL;\
        while( ppScr2(sllInit,curr)-- > ppScr2(sllInit,array) )\
            ppScr2(sllInit,curr)->mlabel = ppScr2(sllInit,last)--;\
        (ilabel) = ppScr2(sllInit,array);\
    }

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

#define sll_reset(type,mlabel, ilabel) \
    {\
        type* __ll_curr = (array);\
        type* __ll_next;\
        while( __ll_curr ) \
        {\
            __ll_next = __ll_curr->mlabel;\
            __ll_curr->mlabel = NULL;\
            __ll_curr = __ll_next;\
        }\
        (ilabel) = NULL;\
    }

#define sll_next(type,mlabel, ilabel, curr ) \
    ((curr) = (curr) ? ((curr)->mlabel) : NULL)

#define sll_foreach_const(type,mlabel, ilabel, iterator ) \
    const type* iterator = (ilabel); \
    for ( ; iterator; iterator = iterator->mlabel )

#define sll_foreach(type,mlabel, ilabel, iterator ) \
    type* iterator = (ilabel); \
    for ( ; iterator; iterator = iterator->mlabel )

#define sll_foreach_deletable(type,mlabel, ilabel, iterator ) \
    type* ppConcat3(__ll_,iterator,_prev) = NULL; \
    type* iterator = (ilabel);\
    type* ppConcat3(__ll_,iterator,_next) = iterator?iterator->mlabel:NULL; \
    for ( ; iterator; ppConcat3(__ll_,iterator,_prev) = iterator, iterator = ppConcat3(__ll_,iterator,_next), sll_next(type,mlabel, ilabel, ppConcat3(__ll_,iterator,_next) )  )

#define sll_foreach_deletable_reverse(type,mlabel, ilabel, iterator ) \
    type* ppConcat3(__ll_,iterator,_prev) = NULL; \
    type* iterator = (ilabel);\
    type* ppConcat3(__ll_,iterator,_next) = iterator?iterator->mlabel:NULL; \
    for ( ; iterator; iterator->mlabel = ppConcat3(__ll_,iterator,_prev), ppConcat3(__ll_,iterator,_prev) = (ilabel) = iterator, iterator = ppConcat3(__ll_,iterator,_next), sll_next(type,mlabel, ilabel, ppConcat3(__ll_,iterator,_next) )  )

#define sll_foreach_deletecurr(type,mlabel, ilabel, iterator ) \
    if( iterator )\
    {\
        if ( ppConcat3(__ll_,iterator,_prev) )\
        {\
            ppConcat3(__ll_,iterator,_prev)->mlabel = ppConcat3(__ll_,iterator,_next);\
        }\
        else\
        {\
            ilabel = ppConcat3(__ll_,iterator,_next);\
        }\
        iterator->mlabel = NULL;\
    }

#define sll_push_front(type,mlabel, ilabel, item ) \
    {\
        (item)->mlabel = (ilabel);\
        (ilabel) = (item);\
    }

#define sll_push_back(type,mlabel, ilabel, item ) \
    {\
        type* __ll_iterate_add;\
        sll_back(type,mlabel, ilabel, __ll_iterate_add );\
        if( __ll_iterate_add ) \
        { \
            __ll_iterate_add->mlabel = (item);\
        } \
        else \
        { \
            (ilabel) = (item);\
        } \
        (item)->mlabel = NULL;\
    }

#define sll_front(type,mlabel, ilabel, get ) \
    {(get) = (ilabel);}

#define sll_back(type,mlabel, ilabel, get ) \
    {\
        type* __ll_iterate = (ilabel);\
        if( __ll_iterate ) \
            while( __ll_iterate->mlabel )\
                __ll_iterate = __ll_iterate->mlabel;\
        (get) = __ll_iterate;\
    }

#define sll_pop_front(type,mlabel, ilabel, get ) \
    {\
        (get) = (ilabel);\
        (ilabel) = (get)->mlabel;\
        (get)->mlabel = NULL;\
    }

#define sll_pop_back(type,mlabel, ilabel, get ) \
    {\
        type* __ll_iterate = (ilabel);\
        type* __ll_iterate_prev = NULL;\
        if( __ll_iterate ) \
        {\
            while( __ll_iterate->mlabel )\
            {\
                __ll_iterate_prev = __ll_iterate->mlabel;\
                __ll_iterate = __ll_iterate->mlabel;\
            }\
            if( __ll_iterate_prev )\
            {\
                __ll_iterate_prev = NULL;\
            }\
            else\
            {\
                (ilabel) = NULL;\
            }\
        }\
        (get) = __ll_iterate;\
    }

#define sll_erase(type,mlabel, ilabel, item ) \
    {\
        type* ppConcat(__ll_iterate_remove,_prev) = NULL; \
        type* __ll_iterate_remove = (ilabel); \
        while( __ll_iterate_remove )\
        {\
            if ( __ll_iterate_remove == (item) )\
            {\
                if ( ppConcat(__ll_iterate_remove,_prev) )\
                {\
                    ppConcat(__ll_iterate_remove,_prev)->mlabel = __ll_iterate_remove->mlabel;\
                }\
                else\
                {\
                    ilabel = __ll_iterate_remove->mlabel;\
                }\
                break;\
            }\
            ppConcat(__ll_iterate_remove,_prev) = __ll_iterate_remove;\
            __ll_iterate_remove = __ll_iterate_remove->mlabel;\
        }\
    }

#define sll_remove_filter(type,mlabel, ilabel, criteria ) \
    {\
        sll_foreach_deletable(type,mlabel, ilabel, __ll_iterate_delete )\
        {\
            if ( criteria(__ll_iterate_delete) ) \
                sll_foreach_deletecurr(type,mlabel, ilabel, __ll_iterate_delete ); \
        }\
    }

#define sll_move_filter(type,mlabel, ilabel, criteria, target ) \
    {\
        sll_foreach_deletable(type,mlabel, ilabel, __ll_iterate_move )\
        {\
            if ( criteria(__ll_iterate_move) ) \
            {\
                sll_foreach_deletecurr(type,mlabel, ilabel, __ll_iterate_move ); \
                sll_push_front(type,mlabel, target, __ll_iterate_move );\
            }\
        }\
    }

#define sll_size(type,mlabel, ilabel, count) \
    {\
        size_t ppScr2(__sll_size_,tally) = 0;\
        type* ppScr2(__sll_size_,iterator);\
        for ( ppScr2(__sll_size_,iterator) = (ilabel); ppScr2(__sll_size_,iterator); ppScr2(__sll_size_,iterator) = ppScr2(__sll_size_,iterator)->mlabel, ppScr2(__sll_size_,tally)++ )\
            ;\
        (count) = ppScr2(__sll_size_,tally);\
    }

#ifndef NDEBUG
#define sll_assert_size(type,mlabel, ilabel, count) \
    {\
        size_t ppScr2(__sll_assert_size,tally) = 0;\
        sll_size(type,mlabel, ilabel, ppScr2(__sll_assert_size,tally));\
        assert( ppScr2(__sll_assert_size,tally) == (count) );\
    }
#else
#define sll_assert_size(type,mlabel, ilabel, count)
#endif

#define sll_splice(type,mlabel, toFirst, fromFirst) \
    {\
        if( toFirst ) \
        {\
            type* sllTail;\
            sll_back(type,mlabel, toFirst, sllTail );\
            sllTail->mlabel = (fromFirst);\
        }\
        else\
        {\
            (toFirst) = (fromFirst);\
        }\
        (fromFirst) = NULL;\
    }

#define sll_bsort(type,mlabel, ilabel, compare ) \
{\
    if( (ilabel) && (ilabel)->mlabel )\
    {\
        type* first = ilabel;\
        type* sortBefore, *sortPrev, *sortNext;\
        int sorted;\
        do\
        {\
            sorted = 0;\
            sortBefore = NULL;\
            sortPrev = first;\
            sortNext = sortPrev->mlabel;\
            while( sortNext )\
            {\
                if( compare( sortPrev, sortNext ) > 0 )\
                {\
                    if( sortBefore )\
                    {\
                        sortBefore->mlabel = sortNext;\
                    }\
                    else\
                    {\
                        first = sortNext;\
                    }\
                    sortPrev->mlabel = sortNext->mlabel;\
                    sortNext->mlabel = sortPrev;\
                    sorted++;\
                }\
                sortBefore = sortPrev;\
                sortPrev = sortNext;\
                sortNext = sortNext->mlabel;\
            }\
        }\
        while( sorted );\
        ilabel = first;\
    }\
}

#define sll_decl_qsort(type,mlabel, ilabel, name ) \
    void name( type** front, type** back, int (*compare)(const void* p1, const void* p2) )

#define sll_qsort(type,mlabel, ilabel, name, compare ) \
        name( &(ilabel), NULL, (int (*)(const void*, const void*))(compare) );\


#define sll_mfg_qsort(type,mlabel, ilabel, deref, name ) \
sll_decl_qsort(type,mlabel, ilabel, name )\
{\
    if( *front && (*front)->mlabel )\
    {\
        type* lesser = NULL;\
        type* tlesser = NULL;\
        type* greater = NULL;\
        type* tgreater = NULL;\
        type* equal = *front;\
        type* tequal = equal;\
        type* curr = equal->mlabel;\
        while( curr )\
        {\
            type* next = curr->mlabel;\
            int val = compare(deref(equal),deref(curr));\
            if( val > 0 )\
            {\
                if( tlesser )\
                {\
                    tlesser->mlabel = curr;\
                    tlesser = curr;\
                }\
                else\
                {\
                    tlesser = lesser = curr;\
                }\
            }\
            else if( val < 0 )\
            {\
                if( tgreater )\
                {\
                    tgreater->mlabel = curr;\
                    tgreater = curr;\
                }\
                else\
                {\
                    tgreater = greater = curr;\
                }\
            }\
            else /* val==0 */\
            {\
                assert(val==0);\
                tequal->mlabel = curr;\
                tequal = curr;\
            }\
            curr = next;\
        }\
        /* Terminate lists */\
        if( lesser )\
        {\
            tlesser->mlabel = NULL;\
            if( lesser != tlesser )\
            {\
                tlesser->mlabel = NULL;\
                name( &lesser, &tlesser, compare );\
            }\
        }\
        /* equal are all the same value... */\
        if( greater )\
        {\
            tgreater->mlabel = NULL;\
            if( greater != tgreater )\
            {\
                name( &greater, &tgreater, compare );\
            }\
        }\
        /* Splice lists together again */\
        if( tlesser )\
        {\
            *front = lesser;\
            tlesser->mlabel = equal;\
        }\
        else\
        {\
            *front = equal;\
        }\
        tequal->mlabel = greater;\
        if( back )\
            *back = tgreater ? tgreater : tequal;\
    }\
}


/* 
 * \defgroup Doubly Doubly Linked Lists
 * \ingroup Containers
 * 
 * last->next and first->prev members of doubly linked list are NULL
 * The stl version ends with a loop back to first.  
 * That's a bit more complicated to iterate, and we iterate more than we delete.
 * For one thing, we can iterate without constantly referring back to the list.
**/
#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)\
    type*   _dllprev(mlabel);\
    type*   _dllnext(mlabel)

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

#define dll_decllist(type,mlabel, ilabel)\
    type*   _dllfront(ilabel);\
    type*   _dllback(ilabel)

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

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

#define dll_autolist(type,mlabel, ilabel)\
    type* _dllfront(ilabel) = NULL;\
    type* _dllback(ilabel) = NULL

#define dll_autolist_static(type,mlabel, ilabel)\
    static type* _dllfront(ilabel) = NULL;\
    static type* _dllback(ilabel) = NULL

#define dll_externlist(type,mlabel, ilabel)\
    extern type* _dllfront(ilabel);\
    extern type* _dllback(ilabel)

#define dll_initarray(type,mlabel, ilabel, array,count) \
    {\
        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;\
    }


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

#define dll_check_link(type,mlabel, ilabel, item ) \
    ( \
        (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)) )\
    )

#define dll_check(type,mlabel, ilabel ) \
    (\
        ( !_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) )\
            )\
        )\
    )


#define dll_check_thorough(type,mlabel, ilabel, onfailure ) \
    {\
        if( dll_check(type,mlabel, ilabel ) )\
        {\
            const type* fromBack = _dllback(ilabel);\
            const type* fromFront = _dllfront(ilabel);\
            while( fromBack && fromFront )\
            {\
                if( !dll_check_link(type,mlabel, ilabel, fromBack ) )\
                {\
                    onfailure("List prev link bad", _dllfront(ilabel),_dllback(ilabel), fromBack);\
                    fromBack = fromFront = NULL; /* So we don't get two failures */\
                    break;\
                }\
                if( !dll_check_link(type,mlabel, ilabel, fromFront ) )\
                {\
                    onfailure("List next link bad", _dllfront(ilabel),_dllback(ilabel), fromFront);\
                    fromBack = fromFront = NULL; /* So we don't get two failures */\
                    break;\
                }\
                fromBack = fromBack->_dllprev(mlabel);\
                fromFront = fromFront->_dllnext(mlabel);\
            }\
            if( fromBack )\
                onfailure("List prev count higher than next count.", _dllfront(ilabel),_dllback(ilabel), fromBack);\
            if( fromFront )\
                onfailure("List next count higher than prev count.", _dllfront(ilabel),_dllback(ilabel), fromFront);\
        }\
        else\
        {\
            onfailure("List front/back links bad", _dllfront(ilabel),_dllback(ilabel),NULL);\
        }\
    }

#define dll_reset(type,mlabel, ilabel) \
    {\
        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;\
        }\
    }

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

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

#define dll_foreach_const(type,mlabel, ilabel, iterator ) \
    const type* iterator = (_dllfront(ilabel)); \
    for ( ; iterator; iterator = iterator->_dllnext(mlabel) )

#define dll_foreach_reverse_const(type,mlabel, ilabel, iterator ) \
    const type* iterator = (_dllback(ilabel)); \
    for( ; iterator; iterator = iterator->_dllprev(mlabel) )

#define dll_foreach(type,mlabel, ilabel, iterator ) \
    type* iterator = (_dllfront(ilabel)); \
    for ( ; iterator; iterator = iterator->_dllnext(mlabel) )

#define dll_foreach_reverse(type,mlabel, ilabel, iterator ) \
    type* iterator = (_dllback(ilabel)); \
    for( ; iterator; iterator = iterator->_dllprev(mlabel) )

#define dll_foreach_deletable(type,mlabel, ilabel, iterator ) \
    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) ) )

#define dll_foreach_deletable_reverse(type,mlabel, ilabel, iterator ) \
    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) ) )

#define dll_push_front(type,mlabel, ilabel, item ) \
    {\
        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);\
    }

#define dll_push_back(type,mlabel, ilabel, item ) \
    {\
        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);\
    }

#define dll_insert(type,mlabel, ilabel, after, item ) \
    {\
        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);\
        }\
    }

#define dll_insert_before(type,mlabel, ilabel, before, item ) \
    {\
        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);\
        }\
    }

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

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

#define dll_pop_front(type,mlabel, ilabel, get ) \
    {\
        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;\
        }\
    }

#define dll_pop_back(type,mlabel, ilabel, get ) \
    {\
        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;\
        }\
    }

#define dll_erase(type,mlabel, ilabel, item ) \
    {\
        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 );\
    }

#define dll_remove_filter(type,mlabel, ilabel, criteria ) \
    {\
        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 );\
            }\
        }\
    }

#define dll_move_filter(type,mlabel, ilabel, criteria, target ) \
    {\
        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 );\
                }\
            }\
        }\
    }

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

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

#define dll_splice(type,mlabel, ilabelto, ilabelfrom ) \
    {\
        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;\
    }


#define dll_rebuild_back(type,mlabel, ilabel ) \
    {\
        /* 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;\
    }\


#define dll_rebuild_front(type,mlabel, ilabel ) \
    {\
        /* 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;\
    }\


#define dll_bsort(type,mlabel, ilabel, compare ) \
    {\
        assert( dll_check(type,mlabel, ilabel ) ); /* List sanity */\
        sll_bsort(type,_dllnext(mlabel), _dllfront(ilabel), compare );\
        dll_rebuild_back(type,mlabel, ilabel );\
    }

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

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

#define dll_qsort(type,mlabel, ilabel, name, compare ) \
    {\
        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 );\
    }


#endif /* LL_H */