From 4a9c4d9ada3ef81415854b0ea5de844d5298eb43 Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Fri, 17 Jun 2022 17:59:26 +1000 Subject: [PATCH] added pvector --- pvector/Makefile | 18 ++++ pvector/aaa | 3 + pvector/example-pvector.c | 140 +++++++++++++++++++++++++++ pvector/pvector.c | 192 ++++++++++++++++++++++++++++++++++++++ pvector/pvector.h | 109 ++++++++++++++++++++++ 5 files changed, 462 insertions(+) create mode 100644 pvector/Makefile create mode 100644 pvector/aaa create mode 100644 pvector/example-pvector.c create mode 100644 pvector/pvector.c create mode 100644 pvector/pvector.h diff --git a/pvector/Makefile b/pvector/Makefile new file mode 100644 index 0000000..10beb6f --- /dev/null +++ b/pvector/Makefile @@ -0,0 +1,18 @@ +default: libpvector.a + +#.INTERMEDIATE: pvector.o +pvector.o: CFLAGS = -Wall -g +pvector.o: pvector.c | pvector.h + +libpvector.a: pvector.o + $(AR) r $@ $^ +CLEANRM += libpvector.a + +#.INTERMEDIATE: example-pvector.o +example-pvector: CFLAGS = -Wall -g +example-pvector: LDLIBS = libpvector.a +example-pvector: example-pvector.o libpvector.a +CLEANRM += example-pvector + +clean: + rm -f $(CLEANRM) diff --git a/pvector/aaa b/pvector/aaa new file mode 100644 index 0000000..6cf4f0b --- /dev/null +++ b/pvector/aaa @@ -0,0 +1,3 @@ +127.0.0.0/8 +10.0.0.0/8 +196.168.0.0/16 diff --git a/pvector/example-pvector.c b/pvector/example-pvector.c new file mode 100644 index 0000000..73beeb1 --- /dev/null +++ b/pvector/example-pvector.c @@ -0,0 +1,140 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "pvector.h" + +typedef struct _ipslot { + char data[16]; + unsigned int bits; +} ipslot; + +static struct { + pvector 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; + if ( inet_pton( AF_INET, line, addr->data ) == 0 ) { + addr->bits = 32; + } if ( inet_pton( AF_INET6, line, addr->data ) == 0 ) { + addr->bits = 128; + } 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) pvector_resize( &table.data, table.fill + 256, 0 ); + } + pvector_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(pvector *pv,int index,void *item) { + return 1; +} + + +int main(int argc,char **argv) { + pvector test; + pvector_resize( &test, 100, 0 ); + pvector_set( &test, 5, (void*) 500 ); + pvector_set( &test, 55, (void*) 600 ); + //pvector_set( &test, 550, (void*) 800 ); + pvector_resize( &test, 300, 0 ); + pvector_set( &test, 55, (void*) 650 ); + pvector_resize( &test, 30000, 0 ); + pvector_set( &test, 22255, (void*) 26 ); + pvector_resize( &test, 100, int_reclaim ); + pvector_set( &test, 5, (void*) 2 ); + +#if 0 + int i; + for ( i = 1; i < argc; i++ ) { + load_file( argv[ i ] ); + } +#endif + return 0; +} diff --git a/pvector/pvector.c b/pvector/pvector.c new file mode 100644 index 0000000..5dbb7d9 --- /dev/null +++ b/pvector/pvector.c @@ -0,0 +1,192 @@ +#include +#include "pvector.h" + +/** + * Representing a vector of void* accessible via an indexing structure + * as levels of same-size pages. A "pvector_page" is a contiguous + * array of 256 void*. + */ + +/** + * Advances a pvector index to the next used slot at or below the + * given level, starting from the indexed entry (inclusive) and up. + * The function will free any empty pages it discovers, and then + * update the index slots accordingly. The given index is advanced + * cyclically to match the found slot. The function returns a slot + * pointer to the used slot, if any, and 0 otherwise. + */ +static void **pvector_level_next_used( + pvector_page *page,unsigned int *index,int level,int end) { + void **p = (void**)&(*page)[ ((pvector_index*)index)->level[ level ] ]; + for( ; *index < end; p++ ) { + if ( *p ) { + if ( level == 0 ) { + return p; // This is a used entry + } + // *p is an index that needs to be inspected recursively + int whole = ((pvector_index*)index)->level[ level - 1 ] == 0; + void **x = pvector_level_next_used( *p, index, level - 1, end ); + if ( x ) { + return x; // Used slot was found; return it. + } + // The page *p is all empty, so can/should be reclaimed. + if ( whole ) { + free( *p ); + *p = 0; + } + } + if ( ++(((pvector_index*)index)->level[ level ]) == 0 ) { + break; // cycling this level => nothing found + } + } + return 0; +} + +// Find the next used slot at given index or later +void **pvector_next_used(pvector *pv,unsigned int *index, + int (*reclaim)(pvector *,int,void*) ) +{ + int levels = PV_LEVELS( pv->size ); + while ( *index < pv->size ) { + void **slot = pvector_level_next_used( + pv->entries, index, levels - 1, pv->size ) ; + if ( slot && *slot ) { + if ( reclaim && reclaim( pv, *index, *slot ) == 0 ) { + *slot = 0; + } else { + return *slot; + } + } + (*index)++; + } + return 0; +} + +// Reclaim tree of unused pages +static void pvector_reclaim(pvector_page *page) { + int i = 0; + for ( ; i < 256; i++ ) { + if ( (*page)[i] ) { + pvector_reclaim( (pvector_page *) (*page)[i] ); + } + } + free( page ); +} + +// 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. +// +// Nothe that resizing may result in the introduction/removal of +// indexing levels and pages, so as to keep the leveling accurate for +// the size. +int pvector_resize( + pvector *pv,unsigned int new_size, + int (*reclaim)(pvector *,int,void*) ) +{ + // Table of number of slots for a level above that of the number + // at the prior lower level. + // The first level (i.e., level 0) adds 255 slots to the one slot + // of no index page. Level 1 adds 255*256 slots, level 2 adds + // 255*(256^2), and generically level i adds 255*(256^i) slots. + static int level_delta[8]; + if ( level_delta[ 0 ] == 0 ) { + int d = 1; + int i; + for ( i = 0; i < 8; i++ ) { + level_delta[ i ] = 255 * d; + d = 256 * d; + } + } + struct { + int old; + int new; + } level = { + PV_LEVELS( pv->size ), + PV_LEVELS( new_size ) + }; + if ( pv->entries == 0 ) { + pv->size = new_size; + return 0; + } + // A shrinking pvector might be veto-ed + if ( new_size < pv->size ) { + unsigned int index = new_size; + void **slot = pvector_next_used( pv, &index, reclaim ); + if ( slot ) { + return index; + } + // 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. + pvector_page *entries; + pvector_page **pp = &pv->entries; + while ( level.old-- > level.new ) { + pp = (pvector_page **)(*pp)[0]; + } + if ( pp != &pv->entries ) { + entries = pv->entries; + pv->entries = *pp; + *pp = 0; + pvector_reclaim( entries ); + } + } else { + // pvector is growing. Maybe insert levels. + while ( level.old < level.new ) { + pvector_page *p = (pvector_page *) + calloc( 1, sizeof( pvector_page ) ); + if ( p == 0 ) { + return -2; // OOM + } + (*p)[0] = pv->entries; + pv->entries = p; + pv->size += level_delta[ level.old++ ]; + // Note that the last level addition might make the size + // larger than requested, which gets corrected below. + } + } + pv->size = new_size; + 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 PVECTORLEVELS( pv->size ) - 1 = +static void **pvector_access( + pvector *pv,unsigned int index,int level,int add) +{ + if ( index >= pv->size ) { + return 0; + } + void **page = (void**) &pv->entries; + int i = PV_LEVELS( pv->size ); + while ( i-- > level ) { + if ( add && (*page) == 0 ) { + (*page) = calloc( 256, sizeof( void* ) ); + } + page = (*page); + if ( page == 0 ) { + return 0; + } + page += ((pvector_index)index).level[ i ]; + } + return page; +} + +// Map index into a value slot +void **pvector_entry(pvector *pv,unsigned int index) { + return pvector_access( pv, index, 0, 1 ); +} + +inline void pvector_set(pvector *pv,unsigned int index,void *value) { + void **p = pvector_entry( pv, index ); + *p = value; +} + +inline void *pvector_get(pvector *pv,unsigned int index) { + return *(pvector_entry( pv, index )); +} + diff --git a/pvector/pvector.h b/pvector/pvector.h new file mode 100644 index 0000000..bc42bec --- /dev/null +++ b/pvector/pvector.h @@ -0,0 +1,109 @@ +#ifndef pvector_H +#define pvector_H + +/** + * A pvector is a dynamic pointer array implemented as an access tree + * of index pages of 256 pointers. + */ + +//#include + +/*! + * Type: pvector_page + * + * A pvector_page is an array of 256 void* items. + */ +typedef void* pvector_page[256]; + +/*! + * Type: pvector_index + * + * A pvector index is ether viewed in whole as an unsigned 64-bit + * integer, or in levels as 8 unsigned char level indexes. This + * implementation assumes LE integer layout. + */ +typedef union { + unsigned int whole; + unsigned char level[4]; +} pvector_index; + +/*! + * Type: pvector + * + * A pvector is a compound of a size and a pvector_page pointer, which + * when non-null points out the top-most page of the pvector. The + * number of levels is derived from its size with level 0 being the + * leaf level of actual content. E.g., a pvector larger than 256 + * items, has at least two levels, and generally N levels may span up + * to 256^N content entries. + */ +typedef struct _pvector { + unsigned int size; //!< Limit for the logical entries[] + 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 )) + +#define PV_LEVEL_SIZE(S) ((int)(exp( 256, (S) ))) + +// The indexing part for level part p in index i +#define PV_PART(p,i) (((unsigned char*)&i)[p]) + +/*! + * Function: int pvector_resize( pvector *pv,unsigned int new_size, + * int (*reclaim)(pvector *,int,void*) ) + * \param pv + * \param new_size + * \param reclaim + * + * Tries to resize the given pvector to a new size. This may result in + * the introduction or removal of indexing pages, so that the leveling + * is consistent with the pvector size. Thus, if it grows into a new + * 256^N level, then one or more new upper level pages are inserted as + * needed. If it shrinks below the current level, then top-level pages + * are remove. + * + * Also, if the new size is smaller than currently, then the now + * excess tail of entries is scanned for any used slots and the given + * reclaim function is invoked successively for these. The reclaim + * function must, in addition to memory-managing the entry, return 0 + * upon success and non-zero to veto the attempted pvector size + * change. + * + * The pvector_resize function returns 0 on success, with the size + * duly changed. Otherwise the function retains the current size and + * returns -index-1 for the index of the veto-ed entry. + */ +int pvector_resize( + pvector *pv,unsigned int new_size, + int (*reclaim)(pvector *,int,void*) ); + +/*! + * Function: void **pvector_entry(pvector *pv,unsigned int index) + * \param pv - the pvector record + * \param index - the slot index + * + * [pgix,epix] = modulo( index, pv->page ); + * + * \returns a direct pointer to the slot of the given index in the + * array, or 0 if the index is beyond the array limits (0-limit). Note + * that slot pointers are only valid while the pvector size is + * unchanged. + */ +extern void **pvector_entry(pvector *pv,unsigned int index); + +/*! + * Function: unsigned int pvector_size(pvector *pv) + * \param pv - the pvector record + * \returns the size of the pvector. + */ +inline unsigned int pvector_size(pvector *pv) { + return pv->size; +} + +void pvector_set(pvector *pv,unsigned int index,void *value); + +void *pvector_get(pvector *pv,unsigned int index); + +#endif -- 2.39.2