From 3cb0a5b799686068172de48232d3dea6ac7caed4 Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Fri, 22 Jul 2022 15:43:12 +1000 Subject: [PATCH] changed ABI --- vector/Vector.c | 87 ++++++++++++++++++++++++++++++++++--------------- 1 file changed, 61 insertions(+), 26 deletions(-) diff --git a/vector/Vector.c b/vector/Vector.c index 35833a5..c65f66b 100644 --- a/vector/Vector.c +++ b/vector/Vector.c @@ -3,6 +3,39 @@ #include #include +/** + * \brief Re-allocate memory for the index of a Single_index_level + * Vector. + */ +static VectorPage* Vector_single_realloc(Vector *pv,size_t new_size) { + new_size = new_size * sizeof( void* ); + VectorPage *p = (VectorPage*) malloc( new_size ); + if ( p ) { + size_t old_size = pv->size * sizeof( void* ); + if ( old_size < new_size ) { + memset( ((char*)p) + old_size, 0, new_size - old_size ); + memcpy( p, pv->entries, old_size ); + } else { + memcpy( p, pv->entries, new_size ); + } + free( pv->entries ); + } + return p; +} + +/** + * \brief Re-allocate memory for the index of a Single_index_level + * Vector. + */ +static VectorPage* Vector_indexpage_calloc(Vector *pv) { + size_t size = VECTOR_SLOTS( pv ) * sizeof( void* ); + VectorPage *p = (VectorPage*) malloc( size ); + if ( p ) { + memset( p, 0, size ); + } + return p; +} + /** * Representing a Vector of void* accessible via an indexing structure * as levels of same-size pages. A "VectorPage" is a contiguous array @@ -39,7 +72,7 @@ typedef struct { unsigned long VECTOR_INDEX_PART(Vector *pv,VectorIndex *index, int level) { unsigned char *px = (unsigned char *) index; switch ( pv->variant ) { - case byte_index_levels: { + case Byte_index_levels: { Byte *pp = (Byte*)(px + level); return pp->a; } @@ -61,7 +94,7 @@ unsigned long VECTOR_INDEX_PART(Vector *pv,VectorIndex *index, int level) { } break; } - case single_index_level: + case Single_index_level: return (*index); } return 0; @@ -76,7 +109,7 @@ static unsigned long VECTOR_INDEX_PART_INC( { unsigned char *px = (unsigned char *) index; switch ( pv->variant ) { - case byte_index_levels: { + case Byte_index_levels: { Byte *pp = (Byte*)( px + level ); return ++(pp->a); } @@ -98,7 +131,7 @@ static unsigned long VECTOR_INDEX_PART_INC( } break; } - case single_index_level: + case Single_index_level: return ++(*index); } return 0; @@ -113,7 +146,7 @@ static unsigned long VECTOR_INDEX_PART_DEC( { unsigned char *px = (unsigned char *) index; switch ( pv->variant ) { - case byte_index_levels: { + case Byte_index_levels: { Byte *pp = (Byte*)( px + level ); return (pp->a)--; } @@ -135,7 +168,7 @@ static unsigned long VECTOR_INDEX_PART_DEC( } break; } - case single_index_level: + case Single_index_level: return (*index)--; } return 0; @@ -163,24 +196,26 @@ static void VECTOR_INDEX_LAST(Vector *pv,VectorIndex *index, int level) { // Return number of slots for a Vector variant. unsigned long VECTOR_SLOTS(Vector *pv) { switch ( pv->variant ) { - case byte_index_levels: return 256; + case Byte_index_levels: return 256; case Nibble_index_levels: return 16; case BitPair_index_levels: return 4; - case single_index_level: return pv->size; + case Single_index_level: return pv->size; } return 0; } -// The number of levels to span Vector pv wrt its size and variant -static unsigned int Vector_levels(Vector *pv,unsigned int size) { - if ( size < 4 ) { +// The number of levels to span a given size for Vector pv +static unsigned int Vector_levels(Vector *pv,unsigned long size) { + if ( size < 4 || pv->variant == Single_index_level ) { return 1; } + // N:o bits in size. + int w = 63 - __builtin_clzl( size ); switch ( pv->variant ) { - case byte_index_levels: return ((int)(log2( size - 1 ) / 8)) + 1; - case Nibble_index_levels: return ((int)(log2( size - 1 ) / 4)) + 1; - case BitPair_index_levels: return ((int)(log2( size - 1 ) / 2)) + 1; - case single_index_level: return 1; + case Byte_index_levels: return ((int)(w / 8)) + 1; + case Nibble_index_levels: return ((int)(w / 4)) + 1; + case BitPair_index_levels: return ((int)(w / 2)) + 1; + case Single_index_level: return 1; } return 0; } @@ -345,7 +380,7 @@ void **Vector_prev_used(Vector *pv,VectorIndex *index) { // Reclaim tree of unused pages for a given level static void Vector_reclaim(Vector *pv,VectorPage *page,unsigned int level) { - int i = 0; + unsigned long i = 0; if ( level > 0 ) { for ( ; i < VECTOR_SLOTS( pv ); i++ ) { if ( (*page)[i] ) { @@ -396,11 +431,10 @@ int Vector_resize( // At this point we know that there are no slots used after // the new_size size, so now it's time to remove and reclaim // any superflouous top level pages. - if ( pv->variant == single_index_level ) { + if ( pv->variant == Single_index_level ) { // Follow Vector size using realloc if ( new_size > 0 ) { - entries = (VectorPage*) - realloc( pv->entries, new_size * sizeof( void* ) ); + entries = Vector_single_realloc( pv, new_size ); if ( entries == 0 ) { return -2; // OOM } @@ -431,10 +465,9 @@ int Vector_resize( } } else { // Vector is growing. Maybe insert levels. - if ( pv->variant == single_index_level ) { + if ( pv->variant == Single_index_level ) { // Follow Vector size using realloc - entries = (VectorPage *)realloc( - pv->entries, new_size * sizeof( void* ) ); + entries = Vector_single_realloc( pv, new_size ); if ( entries == 0 ) { return -2; // OOM } @@ -443,8 +476,7 @@ int Vector_resize( ( new_size - pv->size ) * sizeof( void* ) ); } else { for ( ; level.old < level.new; level.old++ ) { - VectorPage *p = (VectorPage *) - calloc( VECTOR_SLOTS( pv ), sizeof( void* ) ); + VectorPage *p = Vector_indexpage_calloc( pv ); if ( p == 0 ) { return -2; // OOM } @@ -470,7 +502,7 @@ void **Vector_access(Vector *pv,VectorIndex index,int level,int add) { int i = Vector_levels( pv, pv->size ); while ( i-- > level ) { if ( add && (*page) == 0 ) { - (*page) = calloc( VECTOR_SLOTS( pv ), sizeof( void* ) ); + (*page) = Vector_indexpage_calloc( pv ); } page = (*page); if ( page == 0 ) { @@ -505,11 +537,13 @@ inline void *Vector_get(Vector *pv,VectorIndex index) { } int Vector_free_any(Vector *pv,VectorIndex ix,void *item,void *data) { + (void)pv; (void)ix; (void)data; free( item ); return 0; } int Vector_clear_any(Vector *pv,VectorIndex ix,void *item,void *data) { + (void)pv; (void)ix; (void)item; (void)data; return 0; } @@ -576,7 +610,8 @@ static void Vector_qsort_part( VectorIndex hi = m - 1; void **mp = Vector_entry( pv, m ); - void **lop, **hip; + void **lop = 0; + void **hip = 0; for ( ;; ) { // Find index of first item "above" mp scanning from lo and up for ( ; lo < m; lo++ ) { -- 2.39.2