From 2bd18d410e42775bbdaab680447d1e2c43f5491c Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Tue, 5 Jul 2022 21:51:49 +1000 Subject: [PATCH] Use enum for variants; add "clone" and "find" and imporv doco --- vector/vector.c | 77 ++++++++++++++++++++++++++++++++-------------- vector/vector.h | 81 +++++++++++++++++++++++++++++++++++-------------- 2 files changed, 113 insertions(+), 45 deletions(-) diff --git a/vector/vector.c b/vector/vector.c index 2f1010c..16d5577 100644 --- a/vector/vector.c +++ b/vector/vector.c @@ -39,11 +39,11 @@ typedef struct { unsigned long VECTOR_INDEX_PART(vector *pv,vector_index *index, int level) { unsigned char *px = (unsigned char *) index; switch ( pv->variant ) { - case 0: { + case byte_index_levels: { byte *pp = (byte*)(px + level); return pp->a; } - case 1: { + case nibble_index_levels: { nibble *pp = (nibble*)( px + ( level / 2 ) ); switch ( level & 1 ) { case 0: return pp->a; @@ -51,7 +51,7 @@ unsigned long VECTOR_INDEX_PART(vector *pv,vector_index *index, int level) { } break; } - case 2: { + case bitpair_index_levels: { bitpair *pp = (bitpair*)( px + ( level / 4 ) ); switch ( level & 3 ) { case 0: return pp->a; @@ -61,7 +61,7 @@ unsigned long VECTOR_INDEX_PART(vector *pv,vector_index *index, int level) { } break; } - case 3: + case single_index_level: return (*index); } return 0; @@ -76,11 +76,11 @@ static unsigned long VECTOR_INDEX_PART_INC( { unsigned char *px = (unsigned char *) index; switch ( pv->variant ) { - case 0: { + case byte_index_levels: { byte *pp = (byte*)( px + level ); return ++(pp->a); } - case 1: { + case nibble_index_levels: { nibble *pp = (nibble*)( px + ( level / 2 ) ); switch ( level & 1 ) { case 0: return ++(pp->a); @@ -88,7 +88,7 @@ static unsigned long VECTOR_INDEX_PART_INC( } break; } - case 2: { + case bitpair_index_levels: { bitpair *pp = (bitpair*)( px + level / 4 ); switch ( level & 3 ) { case 0: return ++(pp->a); @@ -98,7 +98,7 @@ static unsigned long VECTOR_INDEX_PART_INC( } break; } - case 3: + case single_index_level: return ++(*index); } return 0; @@ -113,11 +113,11 @@ static unsigned long VECTOR_INDEX_PART_DEC( { unsigned char *px = (unsigned char *) index; switch ( pv->variant ) { - case 0: { + case byte_index_levels: { byte *pp = (byte*)( px + level ); return (pp->a)--; } - case 1: { + case nibble_index_levels: { nibble *pp = (nibble*)( px + ( level / 2 ) ); switch ( level & 1 ) { case 0: return (pp->a)--; @@ -125,7 +125,7 @@ static unsigned long VECTOR_INDEX_PART_DEC( } break; } - case 2: { + case bitpair_index_levels: { bitpair *pp = (bitpair*)( px + level / 4 ); switch ( level & 0xf ) { case 0: return (pp->a)--; @@ -135,7 +135,7 @@ static unsigned long VECTOR_INDEX_PART_DEC( } break; } - case 3: + case single_index_level: return (*index)--; } return 0; @@ -163,10 +163,10 @@ static void VECTOR_INDEX_LAST(vector *pv,vector_index *index, int level) { // Return number of slots for a vector variant. unsigned long VECTOR_SLOTS(vector *pv) { switch ( pv->variant ) { - case 0: return 256; - case 1: return 16; - case 2: return 4; - case 3: return pv->size; + 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; } return 0; } @@ -177,10 +177,10 @@ static unsigned int vector_levels(vector *pv,unsigned int size) { return 1; } switch ( pv->variant ) { - case 0: return ((int)(log2( size - 1 ) / 8)) + 1; - case 1: return ((int)(log2( size - 1 ) / 4)) + 1; - case 2: return ((int)(log2( size - 1 ) / 2)) + 1; - case 3: return 1; + 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; } return 0; } @@ -396,7 +396,8 @@ 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 == 3 ) { // Follow vector size using realloc + if ( pv->variant == single_index_level ) { + // Follow vector size using realloc if ( new_size > 0 ) { entries = (vector_page*) realloc( pv->entries, new_size * sizeof( void* ) ); @@ -430,7 +431,8 @@ int vector_resize( } } else { // vector is growing. Maybe insert levels. - if ( pv->variant == 3 ) { // Follow vector size using realloc + if ( pv->variant == single_index_level ) { + // Follow vector size using realloc entries = (vector_page *)realloc( pv->entries, new_size * sizeof( void* ) ); if ( entries == 0 ) { @@ -529,6 +531,14 @@ void vector_copy(vector *dst,vector_index di, } } +vector *vector_clone(enum vector_variant variant,vector *src) { + vector *dst = (vector*) malloc( sizeof( vector ) ); + (*dst) = (vector) { .variant = variant, .size = 0, .entries = 0 }; + vector_resize( dst, src->size, 0, 0 ); + vector_copy( dst, 0, src, 0, src->size ); + return dst; +} + void vector_dump(vector *pv, void (*itemdump)(const vector_index,const void *)) { vector_index index = 0; @@ -618,6 +628,29 @@ void vector_iterate(vector *pv, } } +struct find_data { + void *value; + vector_index index; +}; + +static int vector_find_item(vector_index index, void *item,void *data) { + struct find_data *fd = (struct find_data*)data; + if ( fd->value != item ) { + return 0; + } + fd->index = index; + return 1; +} + +vector_index vector_find(vector *pv,void *value) { + struct find_data fd = { + .value = value, + .index = pv->size + }; + vector_iterate( pv, 0, vector_find_item, &fd ); + return fd.index; +} + // Find surrounding indexes for a given item key in a sparse vector void *vector_bsearch(vector *pv,vector_index *index,const void *key, int (*compare)(const void *key, const void *item)) { diff --git a/vector/vector.h b/vector/vector.h index b18603f..33cf96a 100644 --- a/vector/vector.h +++ b/vector/vector.h @@ -1,7 +1,7 @@ #ifndef vector_H #define vector_H -/** \file vector.h +/** \file * * A vector is a dynamic pointer array implemented as an access tree * of index pages. The indexing is done using "unsigned long" indexes, @@ -10,23 +10,11 @@ * Actual vectors are assigned a leveling variant which defines the * index page size for the vector. This must not be changed for a * vector with entries. - * - * \subsubsection variantlist Variants: - * - * - 0 is 8-bit indexing parts and index pages with 256 pointers - * - 1 is 4-bit indexing parts and index pages with 16 pointers - * - 2 is 2-bit indexing parts and index pages with 4 pointers - * - 3 is for a single page sized as the vector. - * - * Variants 0-2 are managed by adding/removing full pages of the - * indexing tree upon resize and access. Variant 3 is managed by using - * realloc upon resize. In all cases shrinking a vector may mean to - * reclaim "lost" items, if any, via a provided item reclaim callback - * function which also may veto the shrinking. */ /** * \brief This is the general indexing used for vector access. + * * \related vector */ typedef unsigned long vector_index; @@ -34,19 +22,48 @@ typedef unsigned long vector_index; /** * \brief A vector_page is an array of void* items. Its size depends * on the applicable vector variant. + * * \related vector */ typedef void* vector_page[]; /** - * A vector struct is the "foot part" of an actual containing the - * applicable implementation variant for this vector, the intended - * slot size and a root pointer for the indexing structure, which - * consist of indexing pages according to the variant. - * - * Variant 0, 1 and 2, involves indexing pages of 256, 16 and 4 - * pointers respectively. Variant 3 involves a single indexing page of - * the size of the vector. + * \brief The implementation variants. + * + * - byte_index_levels (0) has 8-bit indexing parts and index pages + * with 256 pointers, + * + * - nibble_index_levels (1) has 4-bit indexing parts and index pages + * with 16 pointers, + * + * - bitpair_index_levels (2) has 2-bit indexing parts and index pages + * with 4 pointers, + * + * - single_index_level (3) has a single page that is sized as the + * vector. + * + * The first three variants are managed by adding/removing full pages + * of the indexing tree upon resize and access. The single_index_level + * variant is managed by using realloc upon resize. In all cases + * shrinking a vector might mean to reclaim items about to be "lost", + * if any, via a provided item reclaim callback function. The callback + * function may then also veto the shrinking. + * + * \related vector + */ +enum vector_variant { + byte_index_levels = 0, + nibble_index_levels = 1, + bitpair_index_levels = 2, + single_index_level = 3 +}; + +/** + * A vector struct is the "foot part" of a representation that + * constitutes the implementation variant for a vector abstraction. It + * holds the variant indicator, the intended slot size and a root + * pointer for the indexing structure, which consist of indexing pages + * according to the variant. */ typedef struct { /** @@ -54,7 +71,7 @@ typedef struct { * indexing parts. This gives 256, 16 or 4 slots per index page. * Note that variant should not be changed after initialization. */ - int variant; + enum vector_variant variant; /** * The size of the vector. @@ -273,6 +290,11 @@ extern void vector_copy( vector *src,vector_index si, vector_index n); +/** + * \brief Allocate a copy of a vector into one in the given variant. + */ +extern vector *vector_clone(enum vector_variant variant,vector *src); + /** * \brief Utility function that invokes the itemdump function for all * used (non-null) slots. @@ -329,6 +351,19 @@ extern void *vector_bsearch( vector *pv, vector_index *index, const void *key, int (*compare)(const void *key, const void *item)); +/** + * \brief Find the index for a given value + * + * \param pv is the vector concerned + * \param is the value to find + * + * This function scans the vector for the first, if any, occurrence of + * the value, or returns pv->size if not found. + * + * \related vector + */ +extern vector_index vector_find(vector *pv,void *value); + /** * \brief Find the next used slot at or after the given index. * -- 2.39.2