list.h

#ifndef DG_LIST_H
#define DG_LIST_H

#ifndef LL_H
#include "ctl/ll.h"
#endif

#define ctl_declare_list(label,type)\
    typedef type ppConcat(label,_type);\
    typedef struct ppConcat(label,_node)\
    {\
        dll_decllink(struct ppConcat(label,_node),link); /* Invasive linked list base */ \
        type            obj;        /* The actual member */ \
        ppDebug(const struct label* container;)\
    } ppConcat(label,_node);\
    typedef struct label\
    {\
        dll_decllist(ppConcat(label,_node),link, list);\
        size_t count;\
    } label;\
    /* So we can monitor memory use/leaks */\
    extern ctl_pool(ppConcat(label,_node)) ppConcat(label,_pool);\
    /* The standard pattern functions */\
    ctl_datagen_declare_functions(label);\
    /* How many members in this list */\
    size_t ppConcat(label,_count)( const label* self);\
    /* Tell us if an object is part of this list */\
    bool ppConcat(label,_ismember)( const label* self, const type* mbr );\
    /* Destroy all members, release all memory */\
    void ppConcat(label,_clear)( label* self );\
    /* Get a pointer to the back end member of list */\
    type* ppConcat(label,_back)(const label* self);\
    /* Get a pointer to the front end member of list */\
    type* ppConcat(label,_front)(const label* self);\
    /* Get a pointer to the member before 'curr' of list self, or NULL if we hit end */\
    type* ppConcat(label,_prev)(const label* self, const type* curr);\
    /* Get a pointer to the member after 'curr' of list self, or NULL if we hit end */\
    type* ppConcat(label,_next)(const label* self, const type* curr);\
    /* Add a new member to back end of list, return a pointer to it */\
    type* ppConcat(label,_push_back)(label* self);\
    /* Add a new member to front end of list, return a pointer to it */\
    type* ppConcat(label,_push_front)(label* self);\
    /* Insert a new member at the current position */\
    type* ppConcat(label,_insert)(label* self, type* mbr );\
    /* Remove (and destroy) last member */\
    void  ppConcat(label,_pop_back)(label* self);\
    /* Remove (and destroy) first member */\
    void  ppConcat(label,_pop_front)(label* self);\
    /* Erase (and destroy) a member by its pointer */\
    void  ppConcat(label,_erase)(label* self, type* mbr );\
    /* Quicker-Sort by qsort-like criteria */\
    void  ppConcat(label,_sort)( label* self, int (*compare)(const type* p1, const type* p2) );\
    /* Splice the list 'from' to this one and clear() from */\
    void  ppConcat(label,_splice)( label* self, label* from );\


#define ctl_list_foreach( label, instance, iterator ) \
    ppConcat(label,_type)* iterator;\
    ppConcat(label,_node)* ppConcat(_,iterator) = (instance)->_dllfront(list);\
    for( ; NULL != ppConcat(_,iterator) && intentional_assignment(iterator = &ppConcat(_,iterator)->obj); ppConcat(_,iterator) = ppConcat(_,iterator)->_dllnext(link) )

#define ctl_list_foreach_reverse( label, instance, iterator )\
    ppConcat(label,_type)* iterator;\
    ppConcat(label,_node)* ppConcat(_,iterator) = (instance)->_dllback(list);\
    for( ; NULL != ppConcat(_,iterator) && intentional_assignment(iterator = &ppConcat(_,iterator)->obj); ppConcat(_,iterator) = ppConcat(_,iterator)->_dllprev(link) )

#define ctl_list_foreach_const( label, instance, iterator ) \
    const ppConcat(label,_type)* iterator;\
    const ppConcat(label,_node)* ppConcat(_,iterator) = (instance)->_dllfront(list);\
    for( ; NULL != ppConcat(_,iterator) && intentional_assignment(iterator = &ppConcat(_,iterator)->obj); ppConcat(_,iterator) = ppConcat(_,iterator)->_dllnext(link) )

#define ctl_list_foreach_const_reverse( label, instance, iterator )\
    const ppConcat(label,_type)* iterator;\
    const ppConcat(label,_node)* ppConcat(_,iterator) = (instance)->_dllback(list);\
    for( ; NULL != ppConcat(_,iterator) && intentional_assignment(iterator = &ppConcat(_,iterator)->obj); ppConcat(_,iterator) = ppConcat(_,iterator)->_dllprev(link) )

#define ctl_list_foreach_mutable( label, instance, iterator )\
    ppConcat(label,_type)* iterator;\
    ppConcat(label,_node)* ppConcat(_,iterator) = (instance)->_dllback(list);\
    ppConcat(label,_node)* ppConcat3(_,iterator,_next) = ppConcat(_,iterator)?ppConcat(_,iterator)->_dllnext(link):NULL; \
    for ( ; NULL != ppConcat(_,iterator) && intentional_assignment(iterator = &ppConcat(_,iterator)->obj); (void)(intentional_assignment(ppConcat(_,iterator) = ppConcat3(_,iterator,_next) ) && intentional_assignment(ppConcat3(_,iterator,_next) = ppConcat3(_,iterator,_next)->_dllnext(link))) )

#define ctl_list_foreach_mutable_reverse( label, instance, iterator )\
    ppConcat(label,_type)* iterator;\
    ppConcat(label,_node)* ppConcat(_,iterator) = (instance)->_dllfront(list);\
    ppConcat(label,_node)* ppConcat3(_,iterator,_prev) = ppConcat(_,iterator)?ppConcat(_,iterator)->_dllprev(link):NULL; \
    for ( ; NULL != ppConcat(_,iterator) && intentional_assignment(iterator = &ppConcat(_,iterator)->obj); (void)(intentional_assignment(ppConcat(_,iterator) = ppConcat3(_,iterator,_prev)) && intentional_assignment(ppConcat3(_,iterator,_prev) = ppConcat3(_,iterator,_prev)->_dllprev(link))) )


#ifndef CTL_POOL_DELTA

#define CTL_POOL_DELTA  16
#endif
/* Needed by the list qsort manufacture */
#define ctl_deref_list_mbr(node)    &((node)->obj)

#define ctl_implement_list(label,type)\
ctl_pool_auto(ppConcat(label,_node),ppConcat(label,_pool),16);\
const bool ppConcat(label,_isscalar) = false;\
/* Initialize this record to a known, default state */\
void ppConcat(label,_init)( label* self )\
{\
    assertobjptr(self);\
    dll_initlist(ppConcat(label,_node),link, self->list);\
    self->count = 0;\
}\
/* Replicate a record, copying from 'src' to 'dst' */\
void ppConcat(label,_copy)( label* dst, const label* src )\
{\
    assertobjptr(dst);\
    assertobjconst(src);\
    ppConcat(label,_init)( dst );\
    {\
        ctl_list_foreach_const( label, src, curr )\
            ppConcat(type,_copy)(ppConcat(label,_push_back)(dst),curr);\
    }\
}\
/* Move contents from 'src' to 'dst', leaving 'dst' uninitialized. */\
void ppConcat(label,_move)( label* dst, label* src )\
{\
    assertobjptr(dst);\
    assertobjptr(src);\
    {\
        ppDebug(ppConcat(label,_node)* curr = src->_dllfront(list);)\
        ppDebug(while( curr ) { curr->container = dst; curr = curr->_dllnext(link); } )\
        _dllfront(dst->list) = _dllfront(src->list);\
        _dllback(dst->list) = _dllback(src->list);\
        dst->count = src->count;\
        src->count = 0;\
        dll_initlist(ppConcat(label,_node),link, src->list);\
    }\
}\
/* Swap contents of two records */\
void ppConcat(label,_swap)( label* p1, label* p2 )\
{\
    assertobjptr(p1);\
    assertobjptr(p2);\
    {\
        ppDebug(ppConcat(label,_node)* curr;)\
        label tmp = *p1;\
        *p1 = *p2;\
        *p2 = tmp;\
        ppDebug(curr = p1->_dllfront(list);)\
        ppDebug(while( curr ) { curr->container = p1; curr = curr->_dllnext(link); } )\
        ppDebug(curr = p2->_dllfront(list);)\
        ppDebug(while( curr ) { curr->container = p2; curr = curr->_dllnext(link); } )\
    }\
}\
/* Destroy this record, freeing any contained data */\
void ppConcat(label,_destroy)( label* self )\
{\
    ppConcat(label,_clear)( self );\
}\
/* Compare this record to another record for sorting */\
int ppConcat(label,_rcompare)( const label* p1, const label* p2 ) { return ppConcat(label,_compare)( p2,p1 ); }\
/* Compare this record to another record for sorting */\
int ppConcat(label,_compare)( const label* p1, const label* p2 )\
{\
    if( !p1 && !p2 )\
        return 0;\
    assertobjconst(p1);\
    assertobjconst(p2);\
    {\
        size_t compareLen = min(p1->count,p2->count);\
        const ppConcat(label,_node)* scan1;\
        const ppConcat(label,_node)* scan2;\
        dll_front(ppConcat(label,_node),link, p1->list, scan1 );\
        dll_front(ppConcat(label,_node),link, p2->list, scan2 );\
        while( compareLen-- && scan1 && scan2 )\
        {\
            int result = ppConcat(type,_compare)( &scan1->obj, &scan2->obj );\
            if( result )\
                return result;\
            scan1 = scan1->_dllnext(link);\
            scan2 = scan2->_dllnext(link);\
        }\
        /* If we fell through to here, something's amiss with the links/count */\
        assert(compareLen == -1);\
        if( p1->count < p2->count )\
            return -1;\
        if( p1->count > p2->count )\
            return 1;\
        return 0;\
    }\
}\
/* Determine if a record is valid-looking; all validated members in expected range */\
bool ppConcat(label,_valid)( const label* self )\
{\
    if( !self )\
        return false;\
    assertobjconst(self);\
    if( !dll_check(ppConcat(label,_node),link, self->list ) ) \
        return false;\
    return true;\
}\
/* Determine total memory footprint of this list */\
size_t ppConcat(label,_size)( const label* self )\
{\
    assertobjconst(self);\
    if( ppConcat(type,_isscalar) )\
    {\
        return sizeof(*self) + (self->count * sizeof(ppConcat(label,_node)));\
    }\
    else\
    {\
        size_t ret = sizeof *self;\
        ctl_list_foreach_const( label, self, curr )\
            ret += ppConcat(type,_size)(curr) + sizeof(ppConcat(label,_node))-sizeof(type);\
        ret += (sizeof(ppConcat(label,_node))-sizeof(type))*self->count;\
        return ret;\
    }\
}\
/* Determine total size of this record as stingy serial data */\
size_t ppConcat(label,_serial_size)( const label* self )\
{\
    assertobjconst(self);\
    if( ppConcat(type,_isscalar) )\
    {\
        return ctl_serial_size_size( self->count ) + (self->count * ppConcat(type,_serial_size)(ppConcat(label,_front)(self)));\
    }\
    else\
    {\
        size_t total = ctl_serial_size_size( self->count );\
        ctl_list_foreach_const( label, self, curr )\
            total += ppConcat(type,_serial_size)(curr);\
        return total;\
    }\
}\
/* Write data to a stingy serial record */\
void ppConcat(label,_serial_write)( const label* self, ctl_serial* serial )\
{\
    assertobjconst(self);\
    assertobjptr(serial);\
    ctl_serial_writesize( self->count, serial ); \
    {\
        ctl_list_foreach_const( label, self, curr )\
            ppConcat(type,_serial_write)(curr,serial);\
    }\
}\
/* Read data from a stingy serial record */\
void ppConcat(label,_serial_read)( label* self, ctl_serial* serial )\
{\
    assertobjptr(self);\
    assertobjptr(serial);\
    {\
        size_t readsize = ctl_serial_readsize( serial ); \
        while( readsize-- )\
            ppConcat(type,_serial_read)( ppConcat(label,_push_back)(self), serial );\
    }\
}\
/* Determine total size of this record as robust/archive serial data */\
size_t ppConcat(label,_record_size)( const label* self, const char* szlabel )\
{\
    assertobjconst(self);\
    assertconst(szlabel,1);\
    if( self->count )\
    {\
        size_t result = ctl_record_objarray_head_size( szlabel, "container", #type );\
        if( ppConcat(type,_isscalar) )\
        {\
            result += (self->count * ppConcat(type,_record_size)(ppConcat(label,_front)(self),szlabel));\
        }\
        else\
        { \
            ctl_list_foreach_const(label,self,curr) \
                result += ppConcat(type,_record_size)(curr,szlabel); \
        }\
        return result;\
    }\
    return 0;\
}\
/* Write data to a robust binary serial record */\
void ppConcat(label,_record_write)( const label* self, ctl_serial* serial, const char* szlabel )\
{\
    assertobjconst(self);\
    assertobjptr(serial);\
    assertconst(szlabel,1);\
    if( self->count )\
    {\
        uint8* rectemp = ctl_record_write_container_begin( "container", #type, 0,self->count, serial, szlabel );\
        { \
            ctl_list_foreach_const(label,self,curr) \
                ppConcat(type,_record_write)(curr,serial,szlabel); \
        }\
        ctl_record_write_end( rectemp, serial );\
    }\
}\
/* Read data from a robust/archive binary serial record */\
bool ppConcat(label,_record_read)( label* self, ctl_serial* serial, const char* szlabel )\
{\
    assertobjptr(self);\
    assertobjptr(serial);\
    assertconst(szlabel,1);\
    {\
        ctl_serial pserial = *serial;\
        ppConcat(label,_clear)(self);\
        if( ctl_record_find( &pserial, szlabel ) )\
        {\
            size_t count = ctl_record_container_validatedata( &pserial, "container", szconst(char,#type) );\
            while( count-- )\
            {\
                ppConcat(type,_record_read)( ppConcat(label,_push_back)(self), &pserial, szlabel );\
                ctl_record_next( &pserial );\
            }\
            if( pserial.curr != pserial.end )\
                ctl_serial_except( &pserial, szconst(char,#label) szconst(char,"_record_read: Wrong data length!") );\
            return true;\
        }\
    }\
    return false;\
}\
/* Write data to an XML record */\
void ppConcat(label,_xml_write)( const label* self, ctl_xmlwrite* xml, const char* szlabel )\
{\
    assertobjconst(self);\
    assertobjptr(xml);\
    assertconst(szlabel,1);\
    if( self->count )\
    {\
        ctl_xmlwrite_containertag( xml, #type, self->count, szlabel ); \
        ctl_xmlwrite_indent( xml );\
        {\
            ctl_list_foreach_const(label,self, curr ) \
                ppConcat(type,_xml_write)(curr,xml,NULL);\
        } \
        ctl_xmlwrite_outdent( xml );\
        ctl_xmlwrite_endtag( xml, #type, szlabel ); \
    }\
}\
/* Read data from an XML record */\
bool ppConcat(label,_xml_read)( label* self, ctl_xmlread* xml, const char* szlabel )\
{\
    assertobjptr(self);\
    assertobjptr(xml);\
    assertconst(szlabel,1);\
    if( ctl_xmlread_find( xml, szlabel ) )\
    {\
        int32 count = 0;\
        if( ctl_xmlread_getattribute_int( xml, CTL_LABEL_COUNT, &count ) )\
        {\
            ctl_xmlread arraydata;\
            ctl_xmlread_recurse(&arraydata,xml);\
            while( count-- && ppConcat(type,_xml_read)( ppConcat(label,_push_back)(self), &arraydata, NULL ) )\
                ctl_xmlread_next(&arraydata);\
        }\
        else\
        {\
            xml->except( xml, szconst(char,#label) szconst(char,"_xml_read: Missing size attribute!"), xml->szpCurr, NULL );\
        }\
        return true;\
    }\
    return false;\
}\
/* How many members in this list */\
size_t ppConcat(label,_count)( const label* self)\
{\
    assertobjconst(self);\
    return self->count;\
}\
/* Tell us if an object is part of this list */\
bool ppConcat(label,_ismember)( const label* self, const type* data )\
{\
    assertobjconst(self);\
    assertobjconst(data);\
    ppDebug(return dereference(ppConcat(label,_node),obj,data)->container == self;)\
    ppRelease({ ctl_list_foreach_const(label,self,curr) if( curr == data ) return true; })\
    ppRelease(return false;)\
}\
/* Destroy all members, release all memory */\
void ppConcat(label,_clear)( label* self )\
{\
    assertobjptr(self);\
    for( ;; )\
    {\
        ppConcat(label,_node)* curr;\
        dll_pop_back(ppConcat(label,_node),link, self->list, curr );\
        if( curr )\
        {\
            ppConcat(type,_destroy)(&curr->obj);\
            ctl_pool_free(ppConcat(label,_node),&ppConcat(label,_pool), curr);\
        }\
        else\
            break;\
    }\
    self->count = 0;\
}\
/* Get a pointer to the back end member of list */\
type* ppConcat(label,_back)(const label* self)\
{\
    assertobjconst(self);\
    {\
        const ppConcat(label,_node)* ret;\
        dll_back(ppConcat(label,_node),link, self->list, ret );\
        return (type*)(ret?&ret->obj:NULL);\
    }\
}\
/* Get a pointer to the front end member of list */\
type* ppConcat(label,_front)(const label* self)\
{\
    assertobjconst(self);\
    {\
        const ppConcat(label,_node)* ret;\
        dll_front(ppConcat(label,_node),link, self->list, ret );\
        return (type*)(ret?&ret->obj:NULL);\
    }\
}\
/* Get a pointer to the member before 'curr' of list self, or NULL if we hit end */\
type* ppConcat(label,_prev)(const label* self, const type* curr)\
{\
    if( curr )\
    {\
        const ppConcat(label,_node)* node = dereference(ppConcat(label,_node),obj, curr);\
        assert( node->container == self );\
        node = node->_dllprev(link);\
        if( node )\
            return (type*)&node->obj;\
    }\
    return NULL;\
}\
/* Get a pointer to the member after 'curr' of list self, or NULL if we hit end */\
type* ppConcat(label,_next)(const label* self, const type* curr)\
{\
    if( curr )\
    {\
        const ppConcat(label,_node)* node = dereference(ppConcat(label,_node),obj, curr);\
        assert( node->container == self );\
        node = node->_dllnext(link);\
        if( node )\
            return (type*)&node->obj;\
    }\
    return NULL;\
}\
/* Get a pointer to the next member of list, given a current member */\
type* ppConcat(label,_push_back)(label* self)\
{\
    assertobjptr(self);\
    {\
        ppConcat(label,_node)* node;\
        ctl_pool_alloc(ppConcat(label,_node),&ppConcat(label,_pool), node);\
        dll_push_back(ppConcat(label,_node),link, self->list, node );\
        ppConcat(type,_init)(&node->obj);\
        ppDebug(node->container = self;)\
        self->count++;\
        return &node->obj;\
    }\
}\
/* Add a new member to front end of list, return a pointer to it */\
type* ppConcat(label,_push_front)(label* self)\
{\
    assertobjptr(self);\
    {\
        ppConcat(label,_node)* node;\
        ctl_pool_alloc(ppConcat(label,_node),&ppConcat(label,_pool), node);\
        dll_push_front(ppConcat(label,_node),link, self->list, node );\
        ppConcat(type,_init)(&node->obj);\
        ppDebug(node->container = self;)\
        self->count++;\
        return &node->obj;\
    }\
}\
/* Insert a new member at the current position */\
type* ppConcat(label,_insert)(label* self, type* mbr )\
{\
    assertobjptr(self);\
    assertobjptr(mbr);\
    {\
        ppConcat(label,_node)* inode = dereference(ppConcat(label,_node),obj, mbr);\
        assert( inode->container == self );\
        {\
            ppConcat(label,_node)* node;\
            ctl_pool_alloc(ppConcat(label,_node),&ppConcat(label,_pool), node);\
            dll_insert_before(ppConcat(label,_node),link, self->list, inode, node );\
            ppConcat(type,_init)(&node->obj);\
            ppDebug(node->container = self;)\
            self->count++;\
            return &node->obj;\
        }\
    }\
}\
/* Remove (and destroy) last member */\
void  ppConcat(label,_pop_back)(label* self)\
{\
    assertobjptr(self);\
    {\
        ppConcat(label,_node)* node;\
        dll_pop_back(ppConcat(label,_node),link, self->list, node );\
        if( node )\
        {\
            ppConcat(type,_destroy)(&node->obj);\
            ctl_pool_free(ppConcat(label,_node),&ppConcat(label,_pool), node);\
            self->count--;\
        }\
    }\
}\
/* Remove (and destroy) first member */\
void  ppConcat(label,_pop_front)(label* self)\
{\
    assertobjptr(self);\
    {\
        ppConcat(label,_node)* node;\
        dll_pop_front(ppConcat(label,_node),link, self->list, node );\
        if( node )\
        {\
            ppConcat(type,_destroy)(&node->obj);\
            ctl_pool_free(ppConcat(label,_node),&ppConcat(label,_pool), node);\
            self->count--;\
        }\
    }\
}\
/* Erase (and destroy) a member by its pointer */\
void  ppConcat(label,_erase)(label* self, type* mbr )\
{\
    assertobjptr(self);\
    assertobjptr(mbr);\
    {\
        ppConcat(label,_node)* node = dereference(ppConcat(label,_node),obj, mbr);\
        assertobjptr(node);\
        assert( node->container == self );\
        {\
            ppConcat(type,_destroy)(&node->obj);\
            dll_erase(ppConcat(label,_node),link, self->list, node );\
            self->count--;\
            ctl_pool_free(ppConcat(label,_node),&ppConcat(label,_pool), node);\
        }\
    }\
}\
/* Quicker-Sort internals */\
dll_mfg_qsort(ppConcat(label,_node),link, list, ctl_deref_list_mbr, ppConcat(label,_qsort) );\
/* Quicker-Sort by qsort-like criteria */\
void  ppConcat(label,_sort)( label* self, int (*compare)(const type* p1, const type* p2) )\
{\
    assertobjptr(self);\
    assertcodeptr(compare);\
    dll_qsort(ppConcat(label,_node),link, self->list, ppConcat(label,_qsort), compare );\
}\
/* Splice the list 'from' to this one and clear() from */\
void  ppConcat(label,_splice)( label* self, label* from )\
{\
    assertobjptr(self);\
    assertobjptr(from);\
    {\
        /* For debug code, take an extra step and sign all the links */\
        ppDebug(ppConcat(label,_node)* curr = from->_dllfront(list);)\
        ppDebug(while( curr ) { curr->container = self; curr = curr->_dllnext(link); } )\
        dll_splice(ppConcat(label,_node),link, self->list, from->list );\
        self->count += from->count;\
        from->count = 0;\
    }\
}\

#endif /* DG_LIST_H */