dg/array.h

Go to the documentation of this file.

#ifndef DG_ARRAY_H
#define DG_ARRAY_H

#ifndef CTL_ALGORITHM_H
#include "ctl/algorithm.h"
#endif
#ifndef CTL_ALGORITHM_TEMP_H
#include "ctl/algorithm.temp.h"
#endif

#define ctl_declare_array(label,type,size)\
    typedef type ppConcat(label,_type);\
    typedef struct label\
    {\
        size_t  count;  /* How many members in array */\
        type    array[size];/* The array */\
    } label;\
    /* The standard pattern functions */\
    ctl_datagen_declare_functions(label);\
    /* How many members in this container */\
    size_t ppConcat(label,_count)( const label* self);\
    /* Tell us if an object is part of this container */\
    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 container */\
    type* ppConcat(label,_back)(const label* self);\
    /* Get a pointer to the front end member of container */\
    type* ppConcat(label,_front)(const label* self);\
    /* Get a pointer to the member of container */\
    type* ppConcat(label,_prev)(const label* self, const type* curr);\
    /* Get a pointer to the member after 'curr' of self, or NULL if we hit end */\
    type* ppConcat(label,_next)(const label* self, const type* curr );\
    /* Get a pointer to the member before 'curr' of self, or NULL if we hit end */\
    type* ppConcat(label,_at)(label* self, int index);\
    /* Add a new member to back end of container, return a pointer to it */\
    type* ppConcat(label,_push_back)(label* self);\
    /* Add a new member to front end of container, return a pointer to it */\
    type* ppConcat(label,_push_front)(label* self);\
    /* Insert a new member at the current position, return a pointer to it */\
    type* ppConcat(label,_insert)(label* self, type* mbr );\
    /* Insert a new set of members at the position pointed to by mbr, return a pointer to the start of that array */\
    type* ppConcat(label,_insert_range)(label* self, type* mbr, size_t count );\
    /* Remove last member */\
    void  ppConcat(label,_pop_back)(label* self);\
    /* Remove first member */\
    void  ppConcat(label,_pop_front)(label* self);\
    /* Erase a member by its pointer */\
    void  ppConcat(label,_erase)(label* self, type* mbr );\
    /* Erase a range of members by their pointers */\
    void  ppConcat(label,_erase_range)(label* self, type* mbr, size_t count );\
    /* Erase a member by its pointer, and we don't care about order */\
    void  ppConcat(label,_bag_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 container 'from' to this one and clear() from */\
    void  ppConcat(label,_splice)( label* self, label* from )

#define ctl_array_foreach_const( label, instance, iterator ) \
    const ppConcat(label,_type)* iterator = (instance)->array;\
    const ppConcat(label,_type)* ppConcat(end_,iterator) = iterator + (instance)->count;\
    for( ; iterator < ppConcat(end_,iterator); iterator++ )

#define ctl_array_foreach_const_reverse( label, instance, iterator )\
    const ppConcat(label,_type)* ppConcat(end_,iterator) = (instance)->array;\
    const ppConcat(label,_type)* iterator = ppConcat(end_,iterator) + (instance)->count;\
    while( iterator-- > ppConcat(end_,iterator) )

#define ctl_array_foreach( label, instance, iterator ) \
    ppConcat(label,_type)* iterator = (instance)->array;\
    const ppConcat(label,_type)* ppConcat(end_,iterator) = iterator + (instance)->count;\
    for( ; iterator < ppConcat(end_,iterator); iterator++ )

#define ctl_array_foreach_reverse( label, instance, iterator )\
    ppConcat(label,_type)* ppConcat(end_,iterator) = (instance)->array;\
    const ppConcat(label,_type)* iterator = ppConcat(end_,iterator) + (instance)->count;\
    while( iterator-- > ppConcat(end_,iterator) )

#define ctl_array_foreach_mutable( label, instance, iterator ) \
    ppConcat(label,_type)* iterator;\
    int ppConcat(index_,iterator);\
    label* ppConcat(instance_,iterator) = (instance);\
    for( ppConcat(index_,iterator) = 0; ppConcat(index_,iterator) < (int)ppConcat(instance_,iterator)->count && intentional_assignment(iterator=ppConcat(instance_,iterator)->array + ppConcat(index_,iterator)); ppConcat(index_,iterator)++ )

#define ctl_array_foreach_mutable_reverse( label, instance, iterator )\
    ppConcat(label,_type)* iterator;\
    int ppConcat(index_,iterator);\
    label* ppConcat(instance_,iterator) = (instance);\
    for( ppConcat(index_,iterator) = (int)ppConcat(instance_,iterator)->count; ppConcat(index_,iterator) > 0 && intentional_assignment(iterator=ppConcat(instance_,iterator)->array + ppConcat(index_,iterator)-1); ppConcat(index_,iterator) = min(ppConcat(index_,iterator)-1,(int)ppConcat(instance_,iterator)->count) )

#define ctl_cooked(text)    text

#define ctl_raw(text)

#define ctl_implement_array(label,type,rawcook)\
const bool ppConcat(label,_isscalar) = false;\
/* Initialize */\
void ppConcat(label,_init)( label* self ) \
{\
    assertobjptr(self);\
    self->count = 0;\
}\
/* Copy a array */\
void ppConcat(label,_copy)( label* dst, const label* src ) \
{\
    assertobjptr(dst);\
    assertobjconst(src);\
    ppConcat(label,_init)(dst);\
    {\
        ctl_array_foreach_const( label, src, curr )\
            ppConcat(type,_copy)(ppConcat(label,_push_back)(dst),curr);\
    }\
}\
/* Copy a array */\
void ppConcat(label,_move)( label* dst, label* src ) \
{\
    assertobjptr(dst);\
    assertobjptr(src);\
    ppConcat(label,_init)(dst);\
    {\
        ctl_array_foreach( label, src, curr )\
            ppConcat(type,_move)(ppConcat(label,_push_back)(dst),curr);\
    }\
    dst->count = src->count;\
    ppConcat(label,_destroy)(src);\
}\
/* Destroy the array */\
void ppConcat(label,_destroy)( label* self ) \
{\
    assertobjptr(self);\
    ppConcat(label,_clear)(self);\
}\
/* Swap contents between two arrays */\
void ppConcat(label,_swap)( label* p1, label* p2 )\
{\
    type *pbig, *pless;\
    size_t bigger, lesser;\
    assertobjptr(p1);\
    assertobjptr(p2);\
    if( p1->count > p2->count )\
    {\
        pbig = p1->array;\
        pless = p2->array;\
        lesser = p2->count;\
        bigger = p1->count - lesser;\
    }\
    else\
    {\
        pbig = p2->array;\
        pless = p1->array;\
        lesser = p1->count;\
        bigger = p2->count - lesser;\
    }\
    while( lesser-- )\
    {   /* Swap items where both arrays have them */\
        ppConcat(type,_swap)(pless,pbig);\
        pbig++;pless++;\
    }\
    while( bigger-- )\
    {   /* Copy items where only one array had it */\
        ppConcat(type,_copy)(pless,pbig);\
        pbig++;pless++;\
    }\
    {\
        size_t c1 = p1->count;\
        p1->count = p2->count;\
        p2->count = c1;\
    }\
}\
/* Compare this record to another record for sorting backwards */\
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( NULL == p1 )\
    {\
        if( NULL == p2 )\
            return 0;\
        return -1;\
    }\
    else if( NULL == p2 )\
        return 1;\
    assertobjconst(p1);\
    assertobjconst(p2);\
    {\
        size_t compareLen = min(p1->count,p2->count);\
        const type* p1curr = p1->array; \
        const type* p2curr = p2->array; \
        while( compareLen-- ) \
        {\
            int result = ppConcat(type,_compare)(p1curr++,p2curr++);\
            if( result )\
                return result;\
        }\
        if( p1->count < p2->count )\
            return -1;\
        if( p1->count > p2->count )\
            return 1;\
        return 0;\
    }\
}\
/* See if a array looks valid */\
bool ppConcat(label,_valid)( const label* self ) \
{\
    if( !self )\
        return false;\
    assertobjconst(self);\
    if( self->count > countof(self->array) )\
        return false;\
    {\
        ctl_array_foreach_const( label, self, curr )\
            if( !ppConcat(type,_valid)(curr) )\
                return false;\
    }\
    return true;\
}\
/* How much memory does this consume */\
size_t ppConcat(label,_size)( const label* self )\
{\
    if( ppConcat(type,_isscalar) )\
    {\
        return sizeof(*self);\
    }\
    else\
    {\
        size_t total = sizeof(*self);\
        ctl_array_foreach_const( label, self, curr )\
            total += ppConcat(type,_size)(curr);\
        return total;\
    }\
}\
/* How big will this be as serial data */\
size_t ppConcat(label,_serial_size)( const label* self ) \
{\
    size_t total;\
    assertobjconst(self);\
    total = ctl_serial_size_size( self->count );\
    if( ppConcat(type,_isscalar) )\
    {\
        total += (self->count * ppConcat(type,_serial_size)(ppConcat(label,_front)(self)));\
    }\
    else\
    {\
        ctl_array_foreach_const( label, self, curr )\
            total += ppConcat(type,_serial_size)(curr);\
    }\
    return total;\
}\
/* Write as serial data */\
void ppConcat(label,_serial_write)( const label* self, ctl_serial* serial ) \
{\
    assertobjconst(self);\
    assertobjptr(serial);\
    ctl_serial_writesize( self->count, serial ); \
    {\
        ctl_array_foreach_const( label, self, curr )\
            ppConcat(type,_serial_write)(curr,serial);\
    }\
}\
/* Read from serial data */\
void ppConcat(label,_serial_read)( label* self, ctl_serial* serial ) \
{\
    size_t readsize; \
    assertobjptr(self);\
    assertobjptr(serial);\
    readsize = ctl_serial_readsize( serial ); \
    if( countof(self->array) < readsize )\
        readsize = countof(self->array);\
    while( readsize-- )\
        ppConcat(type,_serial_read)( ppConcat(label,_push_back)(self), serial );\
}\
/* How big will a record made of this be? */\
size_t ppConcat(label,_record_size)( const label* self, const char* szlabel ) \
{\
    size_t result;\
    assertobjconst(self);\
    assertconst(szlabel,1);\
    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_array_foreach_const(label,self,curr) \
            result += ppConcat(type,_record_size)(curr,szlabel); \
    }\
    return result;\
}\
/* Write a record */\
void ppConcat(label,_record_write)( const label* self, ctl_serial* serial, const char* szlabel ) \
{\
    uint8* rectemp;\
    assertobjconst(self);\
    assertobjptr(serial);\
    assertconst(szlabel,1);\
    rectemp = ctl_record_write_container_begin( "container", #type, 0,self->count, serial, szlabel );\
    { \
        ctl_array_foreach_const(label,self,curr) \
            ppConcat(type,_record_write)(curr,serial,szlabel); \
    }\
    ctl_record_write_end( rectemp, serial );\
}\
/* Read a record */\
bool ppConcat(label,_record_read)( label* self, ctl_serial* serial, const char* szlabel ) \
{\
    ctl_serial pserial;\
    assertobjptr(self);\
    assertobjptr(serial);\
    assertconst(szlabel,1);\
    pserial = *serial;\
    if( ctl_record_find( &pserial, szlabel ) )\
    {\
        size_t count = ctl_record_container_validatedata( &pserial, "container", szconst(char,#type) );\
        if( countof(self->array) < count )\
            count = countof(self->array);\
        while( count-- && pserial.curr < pserial.end )\
        {\
            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 XML record */\
void ppConcat(label,_xml_write)( const label* self, ctl_xmlwrite* xml, const char* szlabel ) \
{\
    assertobjconst(self);\
    assertobjptr(xml);\
    assertconst(szlabel,1);\
    ctl_xmlwrite_containertag( xml, #type, self->count, szlabel ); \
    ctl_xmlwrite_indent( xml );\
    {\
        ctl_array_foreach_const(label,self, curr ) \
            ppConcat(type,_xml_write)(curr,xml,NULL);\
    } \
    ctl_xmlwrite_outdent( xml );\
    ctl_xmlwrite_endtag( xml, #type, szlabel ); \
}\
/* Read XML record */\
bool ppConcat(label,_xml_read)( label* self, struct 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);\
            if( countof(self->array) < count )\
                count = countof(self->array);\
            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 container */\
size_t ppConcat(label,_count)( const label* self)\
{\
    assertobjconst(self);\
    return self->count;\
}\
/* Tell us if an object is part of this container */\
bool ppConcat(label,_ismember)( const label* self, const type* mbr )\
{\
    assertobjconst(self);\
    return mbr >= self->array && mbr < self->array + self->count;\
}\
/* Destroy all members, release all memory */\
void ppConcat(label,_clear)( label* self )\
{\
    assertobjptr(self);\
    rawcook( { ctl_array_foreach( label, self, curr ) ppConcat( type,_destroy )(curr); } )\
    self->count = 0;\
}\
/* Add a new member to back end of container, return a pointer to it */\
type* ppConcat(label,_push_back)(label* self)\
{\
    assertobjptr(self);\
    if(self->count+1 <= countof(self->array) )\
    {\
        type* ret = self->array+self->count++;\
        rawcook( ppConcat( type,_init )(ret); )\
        return ret;\
    }\
    throwassert("Out of bounds");\
    return NULL;\
}\
/* Add a new member to front end of container, return a pointer to it */\
type* ppConcat(label,_push_front)(label* self)\
{\
    assertobjptr(self);\
    if(self->count+1 <= countof(self->array) )\
    {\
        type* curr = self->array + self->count++;\
        while( curr-- > self->array )\
            ppConcat(type,_move)( curr+1,curr );\
        rawcook( ppConcat( type,_init )(self->array); )\
        return self->array;\
    }\
    throwassert("Out of bounds");\
    return NULL;\
}\
/* Get a pointer to the back end member of container */\
type* ppConcat(label,_back)(const label* self)\
{\
    assertobjconst(self);\
    if( self->count > 0 )\
        return (type*)(self->array + (self->count-1));\
    return (type*)self->array;\
}\
/* Get a pointer to the front end member of container */\
type* ppConcat(label,_front)(const label* self)\
{\
    assertobjconst(self);\
    return (type*)self->array;\
}\
/* 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)\
{\
    assertobjconst(self);\
    if( curr )\
    {\
        assert( ppConcat(label,_ismember)(self,curr) );\
        if( --curr >= self->array )\
            return (type*)curr;\
    }\
    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 )\
{\
    assertobjconst(self);\
    if( curr )\
    {\
        assert( ppConcat(label,_ismember)(self,curr) );\
        if( ++curr < self->array + self->count )\
            return (type*)curr;\
    }\
    return NULL;\
}\
/* Remove last member */\
void  ppConcat(label,_pop_back)(label* self)\
{\
    assertobjptr(self);\
    assert(self->count > 0 );\
    if( self->count > 0 )\
    {\
        --self->count;\
        ctl_cooked( ppConcat( type,_destroy )( self->array + self->count); )\
    }\
}\
/* Remove first member */\
void  ppConcat(label,_pop_front)(label* self)\
{\
    assert(self->count > 0 );\
    if(self->count > 0 )\
    {\
        type* curr = self->array;\
        type* end = self->array + self->count;\
        rawcook(ppConcat( type,_destroy )(curr++);)\
        while( curr < end )\
        {\
            ppConcat(type,_move)( curr,curr+1 );\
            curr++;\
        }\
    }\
}\
/* Look up a member by its index in the array */\
type* ppConcat(label,_at)(label* self, int index)\
{\
    assertobjptr(self);\
    if( index < 0 || index >= countof(self->array) )\
    {\
        throwassert("Out of bounds");\
        return NULL;\
    }\
    if( index >= (int)self->count )\
    {\
        rawcook( type* end = self->array + index + 1; )\
        rawcook( type* curr = self->array + self->count; )\
        rawcook( while( curr < end ) { ppConcat( type,_init )(curr); curr++; }  )\
        self->count = 1+index;\
    }\
    return (type*)self->array + index;\
}\
/* Insert a new member at the current position, return a pointer to it */\
type* ppConcat(label,_insert)(label* self, type* mbr )\
{\
    assertobjptr(self);\
    if( ppConcat(label,_ismember)( self, mbr ) )\
    {\
        size_t ombr = indexof(self->array,mbr);\
        if(self->count+1 <= countof(self->array) )\
        {\
            mbr = self->array + ombr;\
            {\
                type* curr = self->array + self->count++;\
                while( curr-- > mbr )\
                    ppConcat(type,_move)( curr+1,curr );\
            }\
            rawcook(ppConcat( type,_init )(mbr));\
            return mbr;\
        }\
    }\
    throwassert("Out of bounds");\
    return NULL;\
}\
/* Insert a new set of members at the position pointed to by mbr, return a pointer to the start of that array */\
type* ppConcat(label,_insert_range)(label* self, type* mbr, size_t count )\
{\
    assertobjptr(self);\
    assertconst(mbr,count*sizeof(type));\
    if( ppConcat(label,_ismember)( self, mbr ) )\
    {\
        size_t ombr = indexof(self->array,mbr);\
        if(self->count+count <= countof(self->array) )\
        {\
            mbr = self->array + ombr;\
            {\
                type* dst = self->array + self->count + count;\
                type* src = self->array + self->count;\
                while( src > mbr )\
                    ppConcat(type,_move)( --dst,--src );\
                self->count += count;\
                rawcook( dst = mbr; )\
                rawcook( while( count-- ) ppConcat( type,_init )(dst++); )\
            }\
            return mbr;\
        }\
    }\
    throwassert("Out of bounds");\
    return NULL;\
}\
/* Erase a member by its pointer */\
void  ppConcat(label,_erase)(label* self, type* mbr )\
{\
    assertobjptr(self);\
    if( ppConcat(label,_ismember)( self, mbr ) )\
    {\
        type* curr = mbr;\
        type* end = self->array + self->count;\
        ppConcat( type,_destroy )(curr++);\
        while( curr < end )\
        {\
            ppConcat(type,_move)( curr,curr+1 );\
            curr++;\
        }\
        rawcook( ppConcat( type,_destroy )(curr); )\
        self->count--;\
    }\
}\
/* Erase a range of members by their pointers */\
void  ppConcat(label,_erase_range)(label* self, type* mbr, size_t count )\
{\
    assertobjptr(self);\
    if( ppConcat(label,_ismember)( self, mbr ) && (mbr+count <= self->array+self->count) )\
    {\
        type* dst = mbr;\
        type* src = mbr + count;\
        type* end = self->array + self->count;\
        rawcook( \
            while( dst < src )\
            {\
                ppConcat(type,_destroy)( dst );\
                dst++;\
            }\
            dst = mbr;\
        )\
        while( src < end )\
            ppConcat(type,_move)( dst++,src++ );\
        self->count -= count;\
    }\
}\
/* Erase a member by its pointer, and we don't care about order */\
void  ppConcat(label,_bag_erase)(label* self, type* mbr )\
{\
    assertobjptr(self);\
    if( ppConcat(label,_ismember)( self, mbr ) )\
    {\
        type* end = self->array + self->count - 1;\
        if( end != mbr )\
        {\
            rawcook( ppConcat( type,_destroy )(mbr); )\
            ppConcat( type,_move )(mbr,end);\
        }\
    }\
}\
/* Erase a member by its pointer, and we don't care about order */\
void  ppConcat(label,_bag_erase_range)(label* self, type* mbr, size_t count )\
{\
    assertobjptr(self);\
    if( ppConcat(label,_ismember)( self, mbr ) && (mbr+count <= self->array+self->count) )\
    {\
        type* dst = mbr;\
        type* end = self->array + self->count;\
        type* src = end - count;\
        while( src < end )\
        {\
            rawcook( ppConcat( type,_destroy )(dst); )\
            ppConcat( type,_move )(dst++,src++);\
        }\
    }\
}\
/* Sort by qsort-like criteria */\
void  ppConcat(label,_sort)( label* self, int (*compare)(const type* p1, const type* p2) )\
{\
    assertobjptr(self);\
    assertcodeptr(compare);\
    ppConcat(type,_array_qsort)( self->array, self->array + self->count - 1, compare );\
}\
/* Do bsearch - in sorted array, finds unique member matching 'key' */\
type* ppConcat(label,_bsearch)( const label* self, const type* key, int (*compare)(const type* p1, const type* p2) )\
{\
    assertobjconst(self);\
    assertconst(key,sizeof(*key));\
    assertcodeptr(compare);\
    return (type*)bsearch( &key, self->array, self->count, sizeof(type), (int (*)(const void*,const void*))compare );\
}\
/* Do bsearch - in sorted array, finds unique member matching 'key' */\
type* ppConcat(label,_lsearch)( const label* self, const type* key, int (*compare)(const type* p1, const type* p2) )\
{\
    assertobjconst(self);\
    assertconst(key,sizeof(*key));\
    assertcodeptr(compare);\
    {\
        ctl_array_foreach_const( label, self, curr )\
            if( !compare(curr,key) )\
                return (type*)curr;\
    }\
    return NULL;\
}\
/* Splice the container 'from' to this one and clear() from */\
void  ppConcat(label,_splice)( label* self, label* from )\
{\
    assertobjptr(self);\
    assertobjptr(from);\
    if(self->count+from->count <= countof(self->array) )\
    {\
        ctl_array_foreach( label, from, curr )\
            ppConcat(type,_move)( ppConcat(label,_push_back)(self), curr );\
    }\
    from->count = 0;\
    ppConcat(label,_clear)(from);\
}\

#endif /* ARRAY_H */