From 6c786664c89167fcc8e41e3c6cd5ee6d340e37f9 Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Wed, 22 Jun 2022 23:43:24 +1000 Subject: [PATCH] debugging --- pvector/Makefile | 8 ++++-- pvector/example-hashvector.c | 42 ++++++++++++++++++++++++++-- pvector/example-pvector.c | 4 +-- pvector/hashvector.c | 17 ++++++++++-- pvector/pvector.c | 54 +++++++++++++++++++++++++++--------- pvector/pvector.h | 13 +++++---- 6 files changed, 110 insertions(+), 28 deletions(-) diff --git a/pvector/Makefile b/pvector/Makefile index ea0496c..170aa4a 100644 --- a/pvector/Makefile +++ b/pvector/Makefile @@ -1,5 +1,7 @@ default: libpvector.a +all: default example-hashvector example-pvector + #.INTERMEDIATE: pvector.o pvector.o: CFLAGS = -Wall -g pvector.o: pvector.c | pvector.h @@ -16,13 +18,13 @@ CLEANRM += libpvector.a example-pvector: CFLAGS = -Wall -g example-pvector: LDLIBS = libpvector.a example-pvector: example-pvector.o libpvector.a -CLEANRM += example-pvector +CLEANRM += example-pvector example-pvector.o #.INTERMEDIATE: example-hashvector.o -example-hashvector: CFLAGS = -Wall -g +example-hashvector: CFLAGS = -Wall -g ${TEST} example-hashvector: LDLIBS = libpvector.a example-hashvector: example-hashvector.o libpvector.a -CLEANRM += example-hashvector +CLEANRM += example-hashvector example-hashvector.o clean: rm -f $(CLEANRM) diff --git a/pvector/example-hashvector.c b/pvector/example-hashvector.c index f752426..0d64c9e 100644 --- a/pvector/example-hashvector.c +++ b/pvector/example-hashvector.c @@ -148,12 +148,12 @@ static int int_reclaim(pvector *pv,unsigned long index,void *item,void *data) { return 0; } -static int dumpitem(unsigned long index,void *item) { +static int dumpitem(const unsigned long index,const void *item) { fprintf( stdout, "[%ld] %p\n", index, item ); return 0; } -static int dump_ipslot(unsigned long index,void *item) { +static int dump_ipslot(const unsigned long index,const void *item) { static char buffer[100]; ipslot *ip = (ipslot*) item; const char *p = inet_ntop( ip->family, ip->data, buffer, 100 ); @@ -161,7 +161,7 @@ static int dump_ipslot(unsigned long index,void *item) { return 0; } -static int compare_ipslot(void *ax,void *bx) { +static int compare_ipslot(const void *ax,const void *bx) { ipslot *a = (ipslot *) ax; ipslot *b = (ipslot *) bx; int x = b->family - a->family; @@ -192,7 +192,20 @@ static int compare_ipslot(void *ax,void *bx) { return 0; } +static int shrink(pvector *pv,unsigned long index,void *item,void *data) { + if ( item ) { + if ( item == HV_HOLE ) { + ((hashvector*) data)->holes--; + } else { + free( item ); + ((hashvector*) data)->fill--; + } + } + return 0; +} + int main(int argc,char **argv) { +#if TEST0 pvector test = { 0 }; pvector_resize( &test, 100, 0, 0 ); pvector_set( &test, 5, (void*) 500 ); @@ -223,5 +236,28 @@ int main(int argc,char **argv) { pvector_qsort( &test, compare_ipslot ); fprintf( stdout, "---- contents after sorting\n" ); pvector_dump( &test, dump_ipslot ); +#endif +#if TEST1 + hashvector hv = { + .table = { 4, 0 }, + .fill = 0, + .holes = 0, + .keyhashcode = voidp_hashcode, + .itemkey = voidp_itemkey, + .haskey = voidp_haskey + }; + int i = 0; + for ( ; i < 259; i++ ) { + ipslot *item = (ipslot*) calloc( 1, sizeof( ipslot ) ); + if ( i > 250 ) { + int n = i; + i = n; + } + item->family = i; + memcpy( item->data, "10.10.10.1", 10 ); + hashvector_add( &hv, item ); + } + pvector_resize( &hv.table, 256, shrink, &hv ); +#endif return 0; } diff --git a/pvector/example-pvector.c b/pvector/example-pvector.c index 12154b5..d1eb474 100644 --- a/pvector/example-pvector.c +++ b/pvector/example-pvector.c @@ -116,12 +116,12 @@ static int int_reclaim(pvector *pv,unsigned long index,void *item,void *data) { return 0; } -static int dumpitem(unsigned long index,void *item) { +static int dumpitem(const unsigned long index,const void *item) { fprintf( stdout, "[%ld] %p\n", index, item ); return 0; } -static int dump_ipslot(unsigned long index,void *item) { +static int dump_ipslot(const unsigned long index,const void *item) { static char buffer[100]; ipslot *ip = (ipslot*) item; const char *p = inet_ntop( (ip->bits <= 32)? AF_INET : AF_INET6, diff --git a/pvector/hashvector.c b/pvector/hashvector.c index 5efbd8a..5164ffe 100644 --- a/pvector/hashvector.c +++ b/pvector/hashvector.c @@ -39,7 +39,9 @@ static void **hashvector_find_slot(hashvector *hv,void *key) { int hashvector_find(hashvector *hv,void *key,void **x) { void **p = hashvector_find_slot( hv, key ); if ( p && *p && *p != HV_HOLE ) { - *x = *p; + if ( x ) { + *x = *p; + } return 1; } return 0; @@ -52,13 +54,24 @@ static int capture_item(pvector *pv,unsigned long ix,void *item,void *data) { return 0; } +static int iter_item(unsigned long ix,void *item,void *data) { + if ( item && item != HV_HOLE ) { + hashvector_add( (hashvector *) data, item ); + } + return 0; +} + static void hashvector_resize(hashvector *hv,unsigned long new_size) { hashvector tmp = *hv; hv->table.size = new_size; hv->table.entries = 0; hv->fill = 0; hv->holes = 0; - pvector_resize( &tmp.table, 0, capture_item, hv ); + if ( new_size < hv->table.size ) { + pvector_resize( &tmp.table, 0, capture_item, hv ); + } else { + pvector_iterate( &tmp.table, iter_item, hv ); + } } // Add the given element. diff --git a/pvector/pvector.c b/pvector/pvector.c index 3179376..0838954 100644 --- a/pvector/pvector.c +++ b/pvector/pvector.c @@ -42,6 +42,13 @@ static void **pvector_level_next_used( return 0; } +static unsigned int pvector_levels(unsigned long S) { + if ( S <= 1 ) { + return 1; + } + return (unsigned int) ( 39 - __builtin_clz( S - 1 ) ) / 8; +} + // Find the next used slot at given index or later. Returns pointer to // the slot. void **pvector_next_used( @@ -53,7 +60,7 @@ void **pvector_next_used( *index = pv->size; return 0; } - int levels = PV_LEVELS( pv->size ); + int levels = pvector_levels( pv->size ); for ( ; *index < pv->size; (*index)++ ) { void **slot = pvector_level_next_used( pv->entries, index, levels - 1, pv->size ) ; @@ -70,17 +77,18 @@ void **pvector_next_used( return slot; } } - (*index)++; } return 0; } // Reclaim tree of unused pages -static void pvector_reclaim(pvector_page *page) { +static void pvector_reclaim(pvector_page *page,unsigned int level) { int i = 0; - for ( ; i < 256; i++ ) { - if ( (*page)[i] ) { - pvector_reclaim( (pvector_page *) (*page)[i] ); + if ( level > 0 ) { + for ( ; i < 256; i++ ) { + if ( (*page)[i] ) { + pvector_reclaim( (pvector_page *) (*page)[i], level - 1 ); + } } } free( page ); @@ -117,8 +125,8 @@ int pvector_resize( int old; int new; } level = { - PV_LEVELS( pv->size ), - PV_LEVELS( new_size ) + pvector_levels( pv->size ), + pvector_levels( new_size ) }; if ( pv->entries == 0 ) { pv->size = new_size; @@ -143,7 +151,7 @@ int pvector_resize( entries = pv->entries; pv->entries = *pp; *pp = 0; - pvector_reclaim( entries ); + pvector_reclaim( entries, level.old ); } if ( new_size == 0 ) { free( pv->entries ); @@ -180,7 +188,7 @@ static void **pvector_access( return 0; } void **page = (void**) &pv->entries; - int i = PV_LEVELS( pv->size ); + int i = pvector_levels( pv->size ); while ( i-- > level ) { if ( add && (*page) == 0 ) { (*page) = calloc( 256, sizeof( void* ) ); @@ -235,7 +243,8 @@ void pvector_copy(pvector *dst,unsigned long di, } } -void pvector_dump(pvector *pv,int (*itemdump)(unsigned long,void *)) { +void pvector_dump(pvector *pv, + int (*itemdump)(const unsigned long,const void *)) { unsigned long index = 0; for ( ; index < pv->size; index++ ) { void **slot = pvector_next_used( pv, &index, 0, 0 ); @@ -249,7 +258,7 @@ void pvector_dump(pvector *pv,int (*itemdump)(unsigned long,void *)) { //// Quicksort // Returns 1 for "in order", 0 for equal, and -1 for "wrong order" -typedef int (*comparfn)(void *,void *); +typedef int (*comparfn)(const void *,const void *); static void pvector_qsort_part( pvector *pv,comparfn compar, @@ -301,6 +310,25 @@ static void pvector_qsort_part( pvector_qsort_part( pv, compar, m+1, high ); } -void pvector_qsort(pvector *pv,int (*compar)(void *,void *)) { +void pvector_qsort(pvector *pv,comparfn compar) { pvector_qsort_part( pv, compar, 0, pv->size ); } + +void pvector_iterate(pvector *pv, + int (*itemfn)(unsigned long,void*,void*), + void *data ) +{ + unsigned long index = 0; + while ( index < pv->size ) { + void **slot = pvector_next_used( pv, &index, 0, 0 ); + if ( slot == 0 ) { + break; + } + int i = index & 0xff; + for ( ; i < 256 && index < pv->size; i++, index++, slot++ ) { + if ( itemfn( index, *slot, data ) ) { + return; + } + } + } +} diff --git a/pvector/pvector.h b/pvector/pvector.h index b41b151..ce3b315 100644 --- a/pvector/pvector.h +++ b/pvector/pvector.h @@ -42,9 +42,7 @@ typedef struct _pvector { pvector_page *entries; //!< Pointer to entries indexing } pvector; -// Number of page levels for size S -#define PV_LEVELS(S) ((int)(( 39 - __builtin_clz( ((S)-1) | 1) ) / 8 )) - +// Number of slots for page S #define PV_LEVEL_SIZE(S) ((int)(exp( 256, (S) ))) // The indexing part for level part p in index i @@ -126,8 +124,13 @@ void pvector_append(pvector *pv,void *value); void pvector_copy(pvector *dst,unsigned long di, pvector *src,unsigned long si,unsigned long n); -void pvector_dump(pvector *pv,int (*itemdump)(unsigned long ,void *)); +void pvector_dump(pvector *pv, + int (*itemdump)(const unsigned long ,const void *)); + +void pvector_qsort(pvector *pv,int (*compar)(const void *,const void *)); -void pvector_qsort(pvector *pv,int (*compar)(void *,void *)); +void pvector_iterate(pvector *pv, + int (*itemfn)(unsigned long,void*,void*), + void*); #endif -- 2.39.2