From d8c1ccad095640b40192055bff9ad37e98216970 Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Sun, 26 Jun 2022 15:01:08 +1000 Subject: [PATCH] debugging --- {pvector => tests}/aaa | 0 tests/example-vector.c | 163 +++++++++++++++++++++++++++++++++++++++++ vector/vector.c | 41 +++++++++-- vector/vector.h | 23 +----- 4 files changed, 200 insertions(+), 27 deletions(-) rename {pvector => tests}/aaa (100%) create mode 100644 tests/example-vector.c diff --git a/pvector/aaa b/tests/aaa similarity index 100% rename from pvector/aaa rename to tests/aaa diff --git a/tests/example-vector.c b/tests/example-vector.c new file mode 100644 index 0000000..48403fc --- /dev/null +++ b/tests/example-vector.c @@ -0,0 +1,163 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "vector.h" + +typedef struct _ipslot { + int family; + unsigned int bits; + char data[16]; +} ipslot; + +static struct { + vector data; + int fill; +} table; + +#define BUFSZ 10000 +static struct { + char data[ BUFSZ ]; + int cur; + int end; +} stream; + +static int readline(int fd,char **outp) { + for ( ;; ) { + char *curp = stream.data + stream.cur; + char *endp = stream.data + stream.end; + char *top = curp; + while ( curp < endp ) { + if ( *(curp++) == '\n' ) { + stream.cur = curp - stream.data; + (*outp) = top; + return curp - top; + } + } + if ( top != stream.data ) { + curp = stream.data; + while ( top < endp ) { + *(curp++) = *(top++); + } + endp = curp; + stream.end = endp - stream.data; + } + stream.cur = 0; + ssize_t n = read( fd, endp, BUFSZ - stream.end ); + if ( n <= 0 ) { + if ( stream.end == 0 ) { + return -1; // No more data + } + (*outp) = stream.data; + return stream.end; + } + stream.end += n; + } + //unreachable +} + +// Scan to NUL, CR or c. Return pointer not including character. +static char *scanto(char *p, char c) { + while ( *p && *p != '\n' && *p != c ) { + p++; + } + return p; +} + +static int parse_addr(char *line,ipslot *addr) { + char *end = scanto( line, '\n' ); + char *slash = scanto( line, '/' ); + *slash = 0; + *end = 0; + if ( scanto( line, ':' ) != slash ) { + fprintf( stdout, "AF_INET6: %s\n", line ); + if ( inet_pton( AF_INET6, line, addr->data ) == 1 ) { + addr->family = AF_INET6; + addr->bits = 128; + } else { + return 1; + } + } else if ( inet_pton( AF_INET, line, addr->data ) == 1 ) { + fprintf( stdout, "AF_INET: %s\n", line ); + addr->family = AF_INET; + addr->bits = 32; + } else { + return 1; + } + if ( slash != end && sscanf( slash+1, "%u", &addr->bits ) != 1 ) { + return 1; + } + return 0; +} + +static void add_entry(ipslot *tmp) { + ipslot *p = (ipslot *) malloc( sizeof( ipslot ) ); + memmove( p, tmp, sizeof( ipslot ) ); + if ( table.data.size == table.fill ) { + (void) vector_resize( &table.data, table.fill + 256, 0, 0 ); + } + vector_set( &table.data, table.fill++, p ); +} + +static void load_file(const char *filename) { + int fd = open( filename, O_RDONLY ); + if ( fd < 0 ) { + perror( filename ); + exit( errno ); + } + char *line; + int n; + while ( ( n = readline( fd, &line ) ) >= 0 ) { + ipslot addr; + if ( parse_addr( line, &addr ) ) { + fprintf( stderr, "Bad address: %s\n", line ); + continue; + } + add_entry( &addr ); + } +} + +static int int_reclaim(vector *pv,unsigned long index,void *item,void *data) { + return 0; +} + +static int dumpitem(const unsigned long index,const void *item) { + fprintf( stdout, "[%ld] %p\n", index, item ); + return 0; +} + +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 ); + fprintf( stdout, "[%ld] %s/%d\n", index, p, ip->bits ); + return 0; +} + +int main(int argc,char **argv) { + vector test = { 0 }; + vector_resize( &test, 100, 0, 0 ); + vector_set( &test, 5, (void*) 500 ); + vector_set( &test, 55, (void*) 600 ); + vector_resize( &test, 300, 0, 0 ); + vector_set( &test, 55, (void*) 650 ); + vector_resize( &test, 30000, 0, 0 ); + vector_set( &test, 22255, (void*) 26 ); + vector_dump( &test, dumpitem ); + vector_resize( &test, 100, int_reclaim, 0 ); + vector_set( &test, 5, (void*) 2 ); + vector_dump( &test, dumpitem ); + + int i; + for ( i = 1; i < argc; i++ ) { + load_file( argv[ i ] ); + } + vector_dump( &table.data, dump_ipslot ); + + return 0; +} diff --git a/vector/vector.c b/vector/vector.c index 8dadf00..129ba02 100644 --- a/vector/vector.c +++ b/vector/vector.c @@ -7,6 +7,31 @@ * void*, and an index is "unsigned long" (64 bits). */ +#if VECTOR_LEVEL_BITS == 4 +typedef union { + vector_index as_whole; + struct { + unsigned int msb:4; unsigned int lsb:4; + } __attribute__ ((__packed__)) as_byte[8]; +} vector_indexing; + +#define VECTOR_PART_BYTE(i,p) ((vector_indexing*)(i))->as_byte[ (p)/2 ] + +static int VECTOR_INDEX_PART(vector_index *index,int part) { + if ( part & 1 ) { + return VECTOR_PART_BYTE(index,part).lsb; + } + 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; +} +#endif + /** * Advances a vector index to the next used slot at or below the * given level, starting from the indexed entry (inclusive) and up. @@ -35,7 +60,7 @@ static void **vector_level_next_used( *p = 0; } } - if ( ++VECTOR_INDEX_PART( index, level ) == 0 ) { + if ( VECTOR_INDEX_PART_INC( index, level ) == 0 ) { break; // cycling this level => nothing found } } @@ -149,15 +174,21 @@ int vector_resize( vector_page *entries; vector_page **pp = &pv->entries; while ( level.old-- > level.new ) { - pp = (vector_page **)(*pp)[0]; + if ( pp ) { + pp = (vector_page **)(*pp)[0]; + } } if ( pp != &pv->entries ) { entries = pv->entries; - pv->entries = *pp; - *pp = 0; + if ( pp ) { + pv->entries = *pp; + *pp = 0; // Detach subtree + } else { + pv->entries = 0; + } vector_reclaim( entries, level.old ); } - if ( new_size == 0 ) { + if ( new_size == 0 && pv->entries ) { free( pv->entries ); pv->entries = 0; } diff --git a/vector/vector.h b/vector/vector.h index 1227860..d84c08c 100644 --- a/vector/vector.h +++ b/vector/vector.h @@ -22,7 +22,7 @@ typedef unsigned long vector_index; * Macro: VECTOR_INDEX_BITS * This defines the number of bits of a vector index */ -#define VECTOR_INDEX_BITS sizeof( vector_index ) +#define VECTOR_INDEX_BITS ( sizeof( vector_index ) * 8 ) /*! * Macro: VECTOR_INDEX_FIELDS @@ -44,27 +44,6 @@ typedef unsigned long vector_index; */ typedef void* vector_page[ VECTOR_SLOTS ]; -/*! - * Type: vector_field - * This is VECTOR_LEVEL_BITS size bit field - */ -typedef struct { int bits:VECTOR_LEVEL_BITS; } vector_field; - -/*! - * Type: vector_indexing - * - * A vector index is ether viewed in whole as an VECTOR_INDEX_BITS wide - * unsigned, or in levels as a packed array of vector_field index - * parts. This implementation assumes LE integer layout. - */ -typedef union { - vector_index whole; // as a whole - vector_field level[ VECTOR_INDEX_FIELDS ]; // qua bits fields -} vector_indexing; - -// The indexing part for level part p in index i -#define VECTOR_INDEX_PART(i,p) (((vector_indexing*)(i))->level[ p ].bits) - /*! * Type: vector * -- 2.39.2