vector.h

Go to the documentation of this file.

#ifndef DG_VECTOR_H
#define DG_VECTOR_H

#ifndef ctl_vector_delta
#define ctl_vector_delta    16
#endif

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

#define ctl_declare_vector(label,type)\
    typedef type ppConcat(label,_type);\
    typedef struct label\
    {\
        type*   array;  /* The array */\
        size_t  count;  /* How many members in array */\
        size_t  delta;  /* How many members until we need to grow 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 );\
    /* Change the number of members, destroying any excess */\
    void ppConcat(label,_resize)( label* self, size_t size );\
    /* Make sure the array is pre-allocated for a certain quantity of elements - RECOMMENDED */\
    void ppConcat(label,_reserve)( label* self, size_t size );\
    /* 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_vector_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_vector_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_vector_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_vector_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_vector_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_vector_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_vector(label,type,rawcook)\
const bool ppConcat(label,_isscalar) = false;\
/* Initialize */\
void ppConcat(label,_init)( label* self ) \
{\
    assertobjptr(self);\
    self->array = NULL;\
    self->count = 0;\
    self->delta = 0;\
}\
/* Copy a vector */\
void ppConcat(label,_copy)( label* dst, const label* src ) \
{\
    assertobjconst(src);\
    ppConcat(label,_init)(dst);\
    ppConcat(label,_reserve)(dst,src->count);\
    {\
        ctl_vector_foreach_const( label, src, curr )\
            ppConcat(type,_copy)(ppConcat(label,_push_back)(dst),curr);\
    }\
}\
/* Copy a vector */\
void ppConcat(label,_move)( label* dst, label* src ) \
{\
    assertobjptr(dst);\
    assertobjptr(src);\
    dst->array = src->array;\
    dst->count = src->count;\
    dst->delta = src->delta;\
    src->array = NULL;\
}\
/* Destroy the vector */\
void ppConcat(label,_destroy)( label* self ) \
{\
    assertobjptr(self);\
    ppConcat(label,_clear)(self);\
}\
/* Swap contents between two vectors */\
void ppConcat(label,_swap)( label* p1, label* p2 )\
{\
    assertobjptr(p1);\
    assertobjptr(p2);\
    {\
        type* a1 = p1->array;\
        p1->array = p2->array;\
        p2->array = a1;\
    }\
    {\
        size_t c1 = p1->count;\
        p1->count = p2->count;\
        p2->count = c1;\
    }\
    {\
        size_t d1 = p1->delta;\
        p1->delta = p2->delta;\
        p2->delta = d1;\
    }\
}\
/* 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 vector looks valid */\
bool ppConcat(label,_valid)( const label* self ) \
{\
    if( !self )\
        return false;\
    assertobjconst(self);\
    if( self->count > self->delta )\
        return false;\
    {\
        ctl_vector_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) + (self->delta * sizeof(type));\
    }\
    else\
    {\
        size_t total = sizeof(*self) + ((self->delta-self->count) * sizeof(type));\
        ctl_vector_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 = ctl_serial_size_size( self->count );\
    if( ppConcat(type,_isscalar) )\
    {\
        total += (self->count * ppConcat(type,_serial_size)(ppConcat(label,_front)(self)));\
    }\
    else\
    {\
        ctl_vector_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 ) \
{\
    ctl_serial_writesize( self->count, serial ); \
    {\
        ctl_vector_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 = ctl_serial_readsize( serial ); \
    ppConcat(label,_reserve)( self, readsize );\
    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 = 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_vector_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 = ctl_record_write_container_begin( "container", #type, 0,self->count, serial, szlabel );\
    { \
        ctl_vector_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 = *serial;\
    if( ctl_record_find( &pserial, szlabel ) )\
    {\
        size_t count = ctl_record_container_validatedata( &pserial, "container", szconst(char,#type) );\
        ppConcat(label,_reserve)( self, count );\
        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 ) \
{\
    ctl_xmlwrite_containertag( xml, #type, self->count, szlabel ); \
    ctl_xmlwrite_indent( xml );\
    {\
        ctl_vector_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 ) \
{\
    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);\
            ppConcat(label,_reserve)(self,count);\
            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)\
{\
    return self->count;\
}\
/* Tell us if an object is part of this container */\
bool ppConcat(label,_ismember)( const label* self, const type* mbr )\
{\
    return mbr >= self->array && mbr < self->array + self->count;\
}\
/* Destroy all members, release all memory */\
void ppConcat(label,_clear)( label* self )\
{\
    if( self->array )\
    {\
        rawcook( ctl_vector_foreach( label, self, curr ) ppConcat( type,_destroy )(curr); )\
        ctl_free( self->array );\
        self->count = 0;\
        self->delta = 0;\
    }\
}\
/* Make sure the array is pre-allocated for a certain quantity of elements */\
void ppConcat(label,_reserve)( label* self, size_t size )\
{\
    assertobjptr(self);\
    if( self->delta <= size )\
    {\
        type* newarray;\
        ctl_malloc( newarray, (size+ctl_vector_delta) * sizeof(type) );\
        {\
            type* src = self->array;\
            type* dst = newarray;\
            size_t count = self->count;\
            while( count-- )\
                ppConcat(type,_move)( dst++, src++ );\
            ctl_free(self->array);\
            self->array = newarray;\
            self->delta = size+ctl_vector_delta;\
        }\
    }\
}\
/* Change the number of members, destroying any excess */\
void ppConcat(label,_resize)( label* self, size_t size )\
{\
    /* Throws assertion for size being out of bounds */\
    assertobjptr(self);\
    assert( size >= 0 );\
    if( size > self->count )\
    {\
        ppConcat(label,_reserve)( self, size );\
        {\
            rawcook( type* end = self->array + size; )\
            rawcook( type* curr = self->array + self->count; )\
            rawcook( while( curr < end ) ppConcat( type,_init )(curr++); )\
        }\
        self->count = size;\
    }\
    else if( size < self->count )\
    {\
        rawcook( type* end = self->array + self->count; )\
        rawcook( type* curr = self->array + size; )\
        rawcook( while( curr < end ) ppConcat( type,_destroy )(curr++); )\
        self->count = size;\
    }\
}\
/* Add a new member to back end of container, return a pointer to it */\
type* ppConcat(label,_push_back)(label* self)\
{\
    assertobjptr(self);\
    ppConcat(label,_reserve)( self, self->count+1 );\
    {\
        type* ret = self->array+self->count++;\
        rawcook( ppConcat( type,_init )(ret); )\
        return ret;\
    }\
}\
/* Add a new member to front end of container, return a pointer to it */\
type* ppConcat(label,_push_front)(label* self)\
{\
    assertobjptr(self);\
    ppConcat(label,_reserve)( self, self->count+1 );\
    {\
        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;\
    }\
}\
/* 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)\
{\
    assertobjptr(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 )\
    {\
        throwassert(ppTokStr(ppConcat(label,_at)) ":Out of bounds");\
        return NULL;\
    }\
    if( index >= (int)self->count )\
        ppConcat(label,_resize)( self, 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);\
        ppConcat(label,_reserve)( self, self->count+1 );\
        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(ppTokStr(ppConcat(label,_insert)) ":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);\
    if( ppConcat(label,_ismember)( self, mbr ) )\
    {\
        size_t ombr = indexof(self->array,mbr);\
        ppConcat(label,_reserve)( self, self->count+count );\
        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(ppTokStr(ppConcat(label,_insert_range)) ":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) )\
{\
    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);\
    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);\
    {\
        ctl_vector_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);\
    ppConcat(label,_reserve)( self, self->count+from->count );\
    {\
        ctl_vector_foreach( label, from, curr )\
            ppConcat(type,_move)( ppConcat(label,_push_back)(self), curr );\
    }\
    from->count = 0;\
    ppConcat(label,_clear)(from);\
}\

#endif /* DG_VECTOR_H */