From a0be49ff8fda77c328424c09d6d0ad4a9f7e8f66 Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Mon, 27 Jun 2022 23:53:37 +1000 Subject: [PATCH] debugging" vector" and added regression test --- tests/Makefile | 13 +++ tests/example-hashvector.c | 2 +- tests/vectortests.c | 207 +++++++++++++++++++++++++++++++++++++ vector/Makefile | 7 +- vector/hashvector.c | 18 ++-- vector/hashvector.h | 2 +- vector/vector.c | 154 ++++++++++++++++++++------- vector/vector.h | 70 ++++++++----- 8 files changed, 394 insertions(+), 79 deletions(-) create mode 100644 tests/Makefile create mode 100644 tests/vectortests.c diff --git a/tests/Makefile b/tests/Makefile new file mode 100644 index 0000000..b050eda --- /dev/null +++ b/tests/Makefile @@ -0,0 +1,13 @@ +SRC = $(wildcard *.c) +OBJ = ${SRC:.c=.o} +BIN = ${SRC:.c=} + +default: ${BIN} + +CFLAGS = -Wall -I../vector -g -fmax-errors=1 +LDLIBS = -L../vector -lvector + +.INTERMEDIATE: ${OBJ} + +clean: + rm -f ${BIN} ${OBJ} diff --git a/tests/example-hashvector.c b/tests/example-hashvector.c index 63c5582..7bd57a5 100644 --- a/tests/example-hashvector.c +++ b/tests/example-hashvector.c @@ -54,7 +54,7 @@ int main(int argc,char **argv) { } for ( i = 256; i < 260; i++ ) { vector_index index = i; - void ** slot = vector_next_used( &hv.table, &index, 0, 0 ); + void ** slot = vector_next_used( &hv.table, &index ); if ( slot && *slot != HV_HOLE ) { hashvector_delete( &hv, *slot ); } diff --git a/tests/vectortests.c b/tests/vectortests.c new file mode 100644 index 0000000..30169dc --- /dev/null +++ b/tests/vectortests.c @@ -0,0 +1,207 @@ +/** + * A sequence of tests of the vector.h functions. + */ + +#include +#include +#include + +#define OUT(...) fprintf( stderr, __VA_ARGS__ ) + +// dump an item; return 0 to stop +static void itemdump(const vector_index index,const void *slot) { + if ( slot ) { + OUT ( "[%ld] %s\n", index, (const char*) slot ); + } +} + +// pretend-reclaim item and return data (as int) +static int itemreclaim(vector *pv,vector_index index,void *item,void *data) { + int r = data? 1 : 0; + OUT( "reclaim [%ld] (%p) => %d\n", index, item, r ); + return r; +} + +// Compare two items strings, or nulls +static int itemcmp(const void *a,const void *b) { + return a? ( b? strcmp( (char*)b, (char*)a ) : 1 ) : ( b? -1 : 0 ); +} + +// Iterator function +static int itemiter(vector_index index,void *item,void *data) { + char *s = ""; + if ( item ) { + s = (char*) item; + } + OUT( "[%ld] %p %s\n", index, item, s ); + return ( index < 12 ) == 0; +} + +// check if item before, at or after the key +int itemfind(const void *key, const void *item) { + char *a = (char*) key; + size_t an = a? strlen( a ) : 0; + char *b = (char*) item; + size_t bn = b? strlen( b ) : 0; + OUT( "itemfind %p \"%s\" %p \"%s\"\n", + a, a? a : "(null)", b, b? b : "(null)" ); + return strncmp( a, b, (an [%ld] %p\n", t0[i], index, slot ); + } + + OUT( "vector_prev_used:\n" ); + for ( i = 0; i < 6; i++ ) { + vector_index index = t0[i]; + slot = vector_prev_used( &v, &index ); + OUT( " [%d] => [%ld] %p\n", t0[i], index, slot ); + } + + vector_set( &v, 75, "this is second item" ); + OUT( "vector v has 2 non-empty slots\n" ); + my_vector_dump( &v, itemdump ); + + OUT( "vector_next_used:\n" ); + for ( i = 0; i < 6; i++ ) { + vector_index index = t0[i]; + slot = vector_next_used( &v, &index ); + OUT( " [%d] => [%ld] %p\n", t0[i], index, slot ); + } + + OUT( "vector_prev_used:\n" ); + for ( i = 0; i < 6; i++ ) { + vector_index index = t0[i]; + slot = vector_prev_used( &v, &index ); + OUT( " [%d] => [%ld] %p\n", t0[i], index, slot ); + } + + OUT( "shrinking the vector:\n" ); + // int vector_resize( + // vector *pv, vector_index new_size, + // int (*reclaim)(vector *pv,vector_index index,void *item,void *data), + // void *data ); + i = vector_resize( &v, 50, itemreclaim, (void*)1 ); + OUT( "shrink to 50 (reclaim refused) = %d\n", i ); + + + i = vector_resize( &v, 50, itemreclaim, (void*)0 ); + OUT( "shrink to 50 (accept reclaim) = %d\n", i ); + + i = vector_resize( &v, 508, 0, 0 ); + OUT( "grow to 508 (no reclaim) = %d\n", i ); + + // void **vector_entry(vector *pv,vector_index index); +#define SLOTSTR(slot) (slot? ((*slot)? *slot : "(nil)") : "(unassigned)" ) + slot = vector_entry( &v, 24 ); + itemdump( 24, SLOTSTR(slot) ); + + slot = vector_entry( &v, 25 ); + itemdump( 25, SLOTSTR(slot) ); + + slot = vector_entry( &v, 300 ); + itemdump( 300, SLOTSTR( slot ) ); + + //#define vector_size(pv) ((vector_index) (pv)->size) + OUT( "vector size: %ld\n", vector_size( &v ) ); + + // void *vector_get_set(vector *pv,vector_index index,void *value); + item = vector_get_set( &v, 25, "another value" ); + // void *vector_get(vector *pv,vector_index index); + OUT( "old: \"%s\", new: \"%s\"\n", + (char*)item, (char*)vector_get( &v, 25 ) ); + + // void vector_append(vector *pv,void *value); + vector_append( &v, "the very last item" ); + OUT( "vector size: %ld\n", vector_size( &v ) ); + my_vector_dump( &v, itemdump ); + + vector v2 = { 200, 0 }; + // void vector_copy( + // vector *dst,vector_index di, + // vector *src,vector_index si, + // vector_index n); + vector_copy( &v2, 20, &v, 10, 20 ); + my_vector_dump( &v2, itemdump ); + + vector_resize( &v2, 0, itemreclaim, 0 ); // Reset vector v2 + my_vector_dump( &v2, itemdump ); + + vector_append( &v2, "9 the very last item" ); + vector_append( &v2, "3 the very last item" ); + vector_append( &v2, "4 the very last item" ); + vector_append( &v2, "6 the very last item" ); + vector_append( &v2, "5 the very last item" ); + vector_resize( &v2, vector_size( &v2 ) + 3, 0, 0 ); + vector_append( &v2, "2 the very last item" ); + vector_append( &v2, "8 the very last item" ); + vector_append( &v2, "1 the very last item" ); + vector_append( &v2, 0 ); + vector_append( &v2, "7 the very last item" ); + vector_append( &v2, "0 the very last item" ); + my_vector_dump( &v2, itemdump ); + + // void vector_qsort(vector *pv,int (*compar)(const void *,const void *)); + OUT( "sorted:" ); + vector_qsort( &v2, itemcmp ); + my_vector_dump( &v2, itemdump ); + + // void vector_iterate(vector *pv, + // vector_index start, + // int (*itemfn)(vector_index,void *item,void *data), + // void *data); + OUT( "showing all slots\n" ); + vector_iterate( &v2, 4, itemiter, 0 ); + + // void *vector_bsearch(vector *pv,vector_index *index,const void *key, + // int (*compare)(const void *key, const void *item)); + char *pfx[5] = { "4", "9", "0", "3", "10" }; + for ( i = 0; i < ( sizeof( pfx ) / sizeof( char* ) ); i++ ) { + char *prefix = pfx[i]; + vector_index index = 0; + OUT( "lookup prefix \"%s\":\n", prefix ); + item = vector_bsearch( &v2, &index, prefix, itemfind ); + OUT( "[%ld] %p %s\n", index, item, ( item? (char*)item : "(null)" ) ); + } + + return 0; +} diff --git a/vector/Makefile b/vector/Makefile index edd309f..76c8213 100644 --- a/vector/Makefile +++ b/vector/Makefile @@ -1,14 +1,11 @@ LIBRARY = libvector.a -LIBOBJS = vector.o hashvector.o - -# This is overridable on command line -VECTOR_LEVEL_BITS = 8 +LIBOBJS = vector.o hashvector.o fifovector.o default: $(LIBRARY) all: default -CFLAGS = -Wall -g -fmax-errors=1 -DVECTOR_LEVEL_BITS=$(VECTOR_LEVEL_BITS) +CFLAGS = -Wall -g -fmax-errors=1 -I. define STDCC .INTERMEDIATE: $1.o diff --git a/vector/hashvector.c b/vector/hashvector.c index 1afae80..bd6fb97 100644 --- a/vector/hashvector.c +++ b/vector/hashvector.c @@ -48,7 +48,7 @@ int hashvector_find(hashvector *hv,void *key,void **x) { } static int capture_item(vector *pv,unsigned long ix,void *item,void *data) { - if ( item != HV_HOLE ) { + if ( item && item != HV_HOLE ) { hashvector_add( (hashvector *) data, item ); } return 0; @@ -70,7 +70,7 @@ static void hashvector_resize(hashvector *hv,unsigned long new_size) { if ( new_size < hv->table.size ) { vector_resize( &tmp.table, 0, capture_item, hv ); } else { - vector_iterate( &tmp.table, iter_item, hv ); + vector_iterate( &tmp.table, 0, iter_item, hv ); } } @@ -119,16 +119,14 @@ int hashvector_contents(hashvector *hv,vector *pv) { } unsigned long from = 0; unsigned long to = 0; - while ( to < hv->fill ) { - void **slot = vector_next_used( &hv->table, &from, 0, 0 ); - if ( slot ) { - if ( *slot != HV_HOLE ) { - vector_set( pv, to++, *slot ); - } - from++; - } else { + for ( ; to < hv->fill; from++ ) { + void **slot = vector_next_used( &hv->table, &from ); + if ( slot == 0 ) { break; } + if ( *slot != HV_HOLE ) { + vector_set( pv, to++, *slot ); + } } return 0; } diff --git a/vector/hashvector.h b/vector/hashvector.h index 71b6253..1994b66 100644 --- a/vector/hashvector.h +++ b/vector/hashvector.h @@ -20,7 +20,7 @@ * size when item numbers reduces below 50%. */ -#include "vector.h" +#include /*! * Type: hashvector diff --git a/vector/vector.c b/vector/vector.c index c4482a7..5b38488 100644 --- a/vector/vector.c +++ b/vector/vector.c @@ -1,3 +1,4 @@ +#include #include #include "vector.h" @@ -7,6 +8,7 @@ * void*, and an index is "unsigned long" (64 bits). */ +/** ============================================================ **/ #if VECTOR_LEVEL_BITS == 4 typedef union { vector_index as_whole; @@ -32,6 +34,15 @@ static int VECTOR_INDEX_PART_INC(vector_index *index,int part) { } return ++VECTOR_PART_BYTE(index,part).msb; } + +static int VECTOR_INDEX_PART_INC(vector_index *index,int part) { + if ( part & 1 ) { + return VECTOR_PART_BYTE(index,part).lsb--; + } + return VECTOR_PART_BYTE(index,part).msb--; +} + +/** ============================================================ **/ #elif VECTOR_LEVEL_BITS == 8 #define VECTOR_LEVEL_MASK ( VECTOR_SLOTS - 1 ) @@ -45,7 +56,10 @@ typedef union { #define VECTOR_INDEX_PART_INC(i,p) (++VECTOR_INDEX_PART(i,p)) +#define VECTOR_INDEX_PART_DEC(i,p) (VECTOR_INDEX_PART(i,p)--) + #endif +/** ============================================================ **/ /** * Advances a vector index to the next used slot at or below the @@ -82,6 +96,7 @@ static void **vector_level_next_used( return 0; } + // The least number of levels to span index S (typically the size of a // vector) static unsigned int vector_levels(vector_index S) { @@ -94,13 +109,10 @@ static unsigned int vector_levels(vector_index S) { } // Find the next used slot at given index or later. Returns pointer to -// the slot. -void **vector_next_used( - vector *pv,vector_index *index, - int (*reclaim)(vector *pv,vector_index index,void *item,void *data), - void *data ) -{ - if ( pv->entries == 0 ) { +// the slot. This allows for a reclaim function that may reclaim slot +// items on the way to next used slot. +void **vector_next_used(vector *pv,vector_index *index) { + if ( pv->entries == 0 || *index >= pv->size ) { *index = pv->size; return 0; } @@ -109,18 +121,11 @@ void **vector_next_used( void **slot = vector_level_next_used( pv->entries, index, levels - 1, pv->size ) ; if ( slot == 0 ) { - // reached the end of the vector - *index = pv->size; - break; - } - if ( *slot ) { - // Try reclaiming the slot, - if ( reclaim && reclaim( pv, *index, *slot, data ) == 0 ) { - *slot = 0; - } else { - return slot; - } + *index = pv->size; // reached the end of the vector + } else if ( *slot == 0 ) { + continue; } + return slot; } return 0; } @@ -139,11 +144,11 @@ static void vector_reclaim(vector_page *page,unsigned int level) { } // Resize vector, using the reclaim function as needed, to handle any -// excess items or to veto the resize. Returns the index of the veto, if -// any, or <0 otherwise, with -1 indicating success and -2 indicating -// OOM while growing. +// excess items or to veto the resize. Returns the index of the veto, +// if any, or <0 otherwise, with -1 indicating success and -2 +// indicating OOM // -// Nothe that resizing may result in the introduction/removal of +// Note that resizing may result in the introduction/removal of // indexing levels and pages, so as to keep the leveling accurate for // the size. int vector_resize( @@ -179,8 +184,13 @@ int vector_resize( // A shrinking vector might be veto-ed if ( new_size < pv->size ) { vector_index index = new_size; - void **slot = vector_next_used( pv, &index, reclaim, data ); - if ( slot ) { + void **slot = vector_next_used( pv, &index ); + while ( slot ) { + if ( *slot && reclaim && reclaim( pv, index, *slot, data ) == 0 ) { + *slot = 0; + slot = vector_next_used( pv, &index ); + continue; + } return index; } // At this point we know that there are no slots used after @@ -226,11 +236,9 @@ int vector_resize( return -1; } -// Return a pointer to the indexed item the given page level, adding -// intermediate pages if requested. Returns 0 if addition fails (OOM), -// or if not requested and page is missing. -// Level 0 = pointer to the item entry itself. -// Level VECTORLEVELS( pv->size ) - 1 = +// Return pointer to the indexed page slot at the requested level, and +// adding intermediate index pages if so requested. Returns 0 if +// addition fails (OOM), or if not requested and page is missing. static void **vector_access( vector *pv,vector_index index,int level,int add) { @@ -252,6 +260,41 @@ static void **vector_access( return page; } +// Find the first in-use slot at or before the index, at the level +static void **vector_prev_used_level(vector *pv,vector_index *index,int lv) { + void **slot = vector_access( pv, *index, lv, 0 ); + if ( slot == 0 ) { + return 0; + } + do { + if ( *slot ) { + if ( lv == 0 ) { + return slot; + } + void **sub = vector_prev_used_level( pv, index, lv - 1 ); + if ( sub ) { + return sub; + } + } + slot--; + } while ( VECTOR_INDEX_PART_DEC( index, lv ) != 0 ); + return 0; +} + +// Find nearest used slot at or prior to the given index. +void **vector_prev_used(vector *pv,vector_index *index) { + if ( pv->entries == 0 || *index >= pv->size ) { + *index = pv->size; + return 0; + } + void **slot = vector_prev_used_level( + pv, index, vector_levels( pv->size ) - 1 ); + if ( slot == 0 ) { + *index = pv->size; + } + return slot; +} + // Map index into a value slot void **vector_entry(vector *pv,vector_index index) { return vector_access( pv, index, 0, 1 ); @@ -259,11 +302,21 @@ void **vector_entry(vector *pv,vector_index index) { inline void vector_set(vector *pv,vector_index index,void *value) { void **p = vector_entry( pv, index ); + //assert( p != 0 ); + *p = value; +} + +// Set value at index but return the old value +void *vector_get_set(vector *pv,vector_index index,void *value) { + void **p = vector_entry( pv, index ); + void *old = *p; *p = value; + return old; } inline void *vector_get(vector *pv,vector_index index) { - return *(vector_entry( pv, index )); + void **p = vector_entry( pv, index ); + return *p; } int vector_reclaim_any(vector *pv,vector_index ix,void *item,void *data) { @@ -294,10 +347,10 @@ void vector_copy(vector *dst,vector_index di, } void vector_dump(vector *pv, - int (*itemdump)(const vector_index,const void *)) { + void (*itemdump)(const vector_index,const void *)) { vector_index index = 0; for ( ; index < pv->size; index++ ) { - void **slot = vector_next_used( pv, &index, 0, 0 ); + void **slot = vector_next_used( pv, &index ); if ( slot == 0 ) { break; } @@ -308,7 +361,7 @@ void vector_dump(vector *pv, //// Quicksort // Returns 1 for "in order", 0 for equal, and -1 for "wrong order" -typedef int (*comparfn)(const void *,const void *); + typedef int (*comparfn)(const void *,const void *); static void vector_qsort_part( vector *pv,comparfn compar, @@ -365,12 +418,13 @@ void vector_qsort(vector *pv,comparfn compar) { } void vector_iterate(vector *pv, - int (*itemfn)(vector_index,void*,void*), - void *data ) + vector_index start, + int (*itemfn)(vector_index,void*,void*), + void *data ) { - vector_index index = 0; + vector_index index = start; while ( index < pv->size ) { - void **slot = vector_next_used( pv, &index, 0, 0 ); + void **slot = vector_next_used( pv, &index ); if ( slot == 0 ) { break; } @@ -382,3 +436,29 @@ void vector_iterate(vector *pv, } } } + +// 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)) { + vector_index lo = 0; + vector_index hi = pv->size; + if ( hi-- == 0 || vector_prev_used( pv, &hi ) == 0 ) { + return 0; + } + hi++; + while ( lo < hi ) { + vector_index m = lo + ( hi - lo ) / 2; + void **slot = vector_next_used( pv, &m ); + int c = compare( key, *slot ); + if ( c == 0 ) { + *index = m; + return *slot; + } + if ( c < 0 ) { + hi = m; + } else { + lo = m + 1; + } + } + return 0; +} diff --git a/vector/vector.h b/vector/vector.h index ccd57f3..62e1195 100644 --- a/vector/vector.h +++ b/vector/vector.h @@ -62,15 +62,14 @@ typedef struct _vector { } vector; /*! - * Find the next used slot at given index or later. With a reclaim - * function, it will be invoked for verifying that the item is - * actually in use, in which case it returns 1. Otherwise it should - * reclaim any memory for the item and return 0; + * Find the nearest used (non-null) slot at given or higher index. */ -void **vector_next_used( - vector *pv,vector_index *index, - int (*reclaim)(vector *pv,vector_index index,void *item,void *data), - void *data ); +extern void **vector_next_used(vector *pv,vector_index *index); + +/*! + * Find the nearest used (non-null) slot at given or lower index. + */ +extern void **vector_prev_used(vector *pv,vector_index *index); /*! * Function: int vector_resize( @@ -100,7 +99,7 @@ void **vector_next_used( * duly changed. Otherwise the function retains the current size and * returns -index-1 for the index of the veto-ed entry. */ -int vector_resize( +extern int vector_resize( vector *pv, vector_index new_size, int (*reclaim)(vector *pv,vector_index index,void *item,void *data), void *data ); @@ -120,30 +119,51 @@ int vector_resize( extern void **vector_entry(vector *pv,vector_index index); /*! - * Function: vector_index vector_size(vector *pv) - * \param pv - the vector record + * Macro: vector_size(v) + * \param v - the vector record * \returns the size of the vector. */ -inline vector_index vector_size(vector *pv) { - return pv->size; -} +#define vector_size(pv) ((vector_index) (pv)->size) -void vector_set(vector *pv,vector_index index,void *value); +extern void vector_set(vector *pv,vector_index index,void *value); -void *vector_get(vector *pv,vector_index index); +// Set value at index but return the old value +extern void *vector_get_set(vector *pv,vector_index index,void *value); -void vector_append(vector *pv,void *value); +extern void *vector_get(vector *pv,vector_index index); -void vector_copy(vector *dst,vector_index di, - vector *src,vector_index si,vector_index n); +extern void vector_append(vector *pv,void *value); -void vector_dump(vector *pv, - int (*itemdump)(const vector_index ,const void *)); +extern void vector_copy( + vector *dst,vector_index di, + vector *src,vector_index si, + vector_index n); -void vector_qsort(vector *pv,int (*compar)(const void *,const void *)); +/** + * Invoking the itemdup function for all used (non-null) slots. + */ +extern void vector_dump( + vector *pv, + void (*itemdump)(const vector_index ,const void *)); + +extern void vector_qsort(vector *pv,int (*compar)(const void *,const void *)); -void vector_iterate(vector *pv, - int (*itemfn)(vector_index,void*,void*), - void*); +/*! + * Function: void vector_iterate(vector *pv, + * vector_index start, + * int (*itemfn)(vector_index,void*,void*), + * void*); + * + * Steps through the vector item by item invoking the given function + * for each. Continues stepping while the item function returns 0. + */ +extern void vector_iterate( + vector *pv, vector_index start, + int (*itemfn)(vector_index,void *item,void *data), + void *data); + +extern void *vector_bsearch( + vector *pv, vector_index *index, const void *key, + int (*compare)(const void *key, const void *item)); #endif -- 2.39.2