From c2fcc2eaad945b2bee685ca8b71c565158da0e18 Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Sun, 26 Jun 2022 11:01:52 +1000 Subject: [PATCH] renamed pvector to vector and changed into generalized code --- pvector/Makefile | 36 --- pvector/example-hashvector.c | 263 --------------------- pvector/example-pvector.c | 156 ------------- pvector/pvector.c | 334 --------------------------- pvector/pvector.h | 134 ----------- pvector/qvector.h | 170 -------------- vector/Makefile | 26 +++ {pvector => vector}/hashvector.c | 24 +- {pvector => vector}/hashvector.h | 18 +- pvector/qvector.c => vector/vector.c | 164 ++++++------- vector/vector.h | 168 ++++++++++++++ 11 files changed, 296 insertions(+), 1197 deletions(-) delete mode 100644 pvector/Makefile delete mode 100644 pvector/example-hashvector.c delete mode 100644 pvector/example-pvector.c delete mode 100644 pvector/pvector.c delete mode 100644 pvector/pvector.h delete mode 100644 pvector/qvector.h create mode 100644 vector/Makefile rename {pvector => vector}/hashvector.c (83%) rename {pvector => vector}/hashvector.h (87%) rename pvector/qvector.c => vector/vector.c (58%) create mode 100644 vector/vector.h diff --git a/pvector/Makefile b/pvector/Makefile deleted file mode 100644 index be1ab86..0000000 --- a/pvector/Makefile +++ /dev/null @@ -1,36 +0,0 @@ -default: libpvector.a - -all: default example-hashvector example-pvector - -#.INTERMEDIATE: pvector.o -pvector.o: CFLAGS = -Wall -g -pvector.o: pvector.c | pvector.h -CLEANRM += pvector.o - -#.INTERMEDIATE: qvector.o -qvector.o: CFLAGS = -Wall -g -qvector.o: qvector.c | qvector.h -CLEANRM += qvector.o - -#.INTERMEDIATE: hashvector.o -hashvector.o: CFLAGS = -Wall -g -hashvector.o: hashvector.c | pvector.h hashvector.h - -libpvector.a: pvector.o qvector.o hashvector.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 example-pvector.o - -#.INTERMEDIATE: example-hashvector.o -example-hashvector: CFLAGS = -Wall -g ${TEST} -example-hashvector: LDLIBS = libpvector.a -example-hashvector: example-hashvector.o libpvector.a -CLEANRM += example-hashvector example-hashvector.o - -clean: - rm -f $(CLEANRM) diff --git a/pvector/example-hashvector.c b/pvector/example-hashvector.c deleted file mode 100644 index 0d64c9e..0000000 --- a/pvector/example-hashvector.c +++ /dev/null @@ -1,263 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include "hashvector.h" - -typedef struct _ipslot { - int family; - unsigned char data[32]; - unsigned int bits; -} ipslot; - -static unsigned long voidp_hashcode(void *key) { - return hashvector_hashcode( key, sizeof( ipslot ) ); -} - -static void* voidp_itemkey(void *item) { - return item; -} - -static int voidp_haskey(void *item,void *key) { - return memcmp( item, key, sizeof( ipslot ) ) == 0; -} - -static struct { - hashvector hv; - long fill; -} table = { - .hv = { - .table = { 12000, 0 }, - .fill = 0, - .holes = 0, - .keyhashcode = voidp_hashcode, - .itemkey = voidp_itemkey, - .haskey = voidp_haskey - }, - .fill = 0 -}; - -#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 ( inet_pton( AF_INET6, line, addr->data ) == 1 ) { - addr->bits = 128; - addr->family = AF_INET6; - } else if ( inet_pton( AF_INET, line, addr->data ) == 1 ) { - addr->bits = 32; - addr->family = AF_INET; - } else { - return 1; - } - if ( slash != end && sscanf( slash+1, "%u", &addr->bits ) != 1 ) { - return 2; - } - return 0; -} - - -static void add_entry(ipslot *tmp) { - ipslot *p = (ipslot *) malloc( sizeof( ipslot ) ); - memmove( p, tmp, sizeof( ipslot ) ); - hashvector_add( &table.hv, p ); - table.fill++; -#if 0 - pvector *pv = &table.hv.table; - if ( pv->size == table.fill ) { - (void) pvector_resize( pv, table.fill + 256, 0, 0 ); - } - pvector_set( pv, table.fill++, p ); -#endif -} - -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,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; -} - -static int compare_ipslot(const void *ax,const void *bx) { - ipslot *a = (ipslot *) ax; - ipslot *b = (ipslot *) bx; - int x = b->family - a->family; - if ( x ) { - return ( x > 0 )? 1 : -1; - } - x = a->bits < b->bits? a->bits : b->bits; - unsigned char *ap = a->data; - unsigned char *bp = b->data; - int d; - for ( ; x >= 8; x -= 8 ) { - d = *(bp++) - *(ap++); - if ( d ) { - return ( d > 0 )? 1 : -1; - } - } - if ( x ) { - x = 7 - x; - d = ( (*bp) >> x ) - ( (*ap) >> x ); - if ( d ) { - return ( d > 0 )? 1 : -1; - } - } - x = b->bits - a->bits; - if ( x ) { - return ( x > 0 )? 1 : -1; - } - 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 ); - pvector_set( &test, 55, (void*) 600 ); - //pvector_set( &test, 550, (void*) 800 ); - pvector_resize( &test, 300, 0, 0 ); - pvector_set( &test, 55, (void*) 650 ); - pvector_resize( &test, 30000, 0, 0 ); - pvector_set( &test, 22255, (void*) 26 ); - pvector_dump( &test, dumpitem ); - pvector_resize( &test, 100, int_reclaim, 0 ); - pvector_set( &test, 5, (void*) 2 ); - pvector_dump( &test, dumpitem ); - pvector_resize( &test, 0, int_reclaim, 0 ); // clear out the pvector - - int i; - for ( i = 1; i < argc; i++ ) { - load_file( argv[ i ] ); - } - fprintf( stdout, "---- hashvector after filling it %ld/%ld/%ld\n", - table.hv.fill, table.hv.holes, table.hv.table.size ); - pvector_dump( &table.hv.table, dump_ipslot ); - if ( hashvector_contents( &table.hv, &test ) < 0 ) { - fprintf( stdout, "test is not empty\n" ); - } - fprintf( stdout, "---- hashvector contents in hash order\n" ); - pvector_dump( &test, dump_ipslot ); - 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 deleted file mode 100644 index d1eb474..0000000 --- a/pvector/example-pvector.c +++ /dev/null @@ -1,156 +0,0 @@ -#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, 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,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->bits <= 32)? AF_INET : AF_INET6, - ip->data, buffer, 100 ); - - fprintf( stdout, "[%ld] %s/%d\n", index, p, ip->bits ); - return 0; -} - -int main(int argc,char **argv) { - pvector test = { 0 }; - pvector_resize( &test, 100, 0, 0 ); - pvector_set( &test, 5, (void*) 500 ); - pvector_set( &test, 55, (void*) 600 ); - //pvector_set( &test, 550, (void*) 800 ); - pvector_resize( &test, 300, 0, 0 ); - pvector_set( &test, 55, (void*) 650 ); - pvector_resize( &test, 30000, 0, 0 ); - pvector_set( &test, 22255, (void*) 26 ); - pvector_dump( &test, dumpitem ); - pvector_resize( &test, 100, int_reclaim, 0 ); - pvector_set( &test, 5, (void*) 2 ); - pvector_dump( &test, dumpitem ); - - int i; - for ( i = 1; i < argc; i++ ) { - load_file( argv[ i ] ); - } - pvector_dump( &table.data, dump_ipslot ); - - return 0; -} diff --git a/pvector/pvector.c b/pvector/pvector.c deleted file mode 100644 index 0838954..0000000 --- a/pvector/pvector.c +++ /dev/null @@ -1,334 +0,0 @@ -#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 long *index,int level,unsigned long 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; -} - -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( - pvector *pv,unsigned long *index, - int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data), - void *data ) -{ - if ( pv->entries == 0 ) { - *index = pv->size; - return 0; - } - int levels = pvector_levels( pv->size ); - for ( ; *index < pv->size; (*index)++ ) { - void **slot = pvector_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; - } - } - } - return 0; -} - -// Reclaim tree of unused pages -static void pvector_reclaim(pvector_page *page,unsigned int level) { - int i = 0; - if ( level > 0 ) { - for ( ; i < 256; i++ ) { - if ( (*page)[i] ) { - pvector_reclaim( (pvector_page *) (*page)[i], level - 1 ); - } - } - } - 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 long new_size, - int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data), - void *data ) -{ - // 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 = { - pvector_levels( pv->size ), - pvector_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 long index = new_size; - void **slot = pvector_next_used( pv, &index, reclaim, data ); - 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, level.old ); - } - if ( new_size == 0 ) { - free( pv->entries ); - pv->entries = 0; - } - } 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 long index,int level,int add) -{ - if ( index >= pv->size ) { - return 0; - } - void **page = (void**) &pv->entries; - int i = pvector_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 long index) { - return pvector_access( pv, index, 0, 1 ); -} - -inline void pvector_set(pvector *pv,unsigned long index,void *value) { - void **p = pvector_entry( pv, index ); - *p = value; -} - -inline void *pvector_get(pvector *pv,unsigned long index) { - return *(pvector_entry( pv, index )); -} - -int pvector_reclaim_any(pvector *pv,unsigned long ix,void *item,void *data) { - free( item ); - return 0; -} - -void pvector_append(pvector *pv,void *value) { - pvector_resize( pv, pv->size + 1, 0, 0 ); - pvector_set( pv, pv->size - 1, value ); -} - -// copy block of n items from src[si] to dst[di] -// no efficiency hacks -void pvector_copy(pvector *dst,unsigned long di, - pvector *src,unsigned long si,unsigned long n) { - if ( dst != src || di < si ) { - while ( n-- != 0 ) { - pvector_set( dst, di++, pvector_get( src, si++ ) ); - } - } else if ( di > si ){ - di += n - 1; - si += n - 1; - while ( n-- != 0 ) { - pvector_set( dst, di--, pvector_get( src, si-- ) ); - } - } -} - -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 ); - if ( slot == 0 ) { - break; - } - itemdump( index, *slot ); - } -} - -//// Quicksort - -// Returns 1 for "in order", 0 for equal, and -1 for "wrong order" -typedef int (*comparfn)(const void *,const void *); - -static void pvector_qsort_part( - pvector *pv,comparfn compar, - unsigned long low,unsigned long high) -{ - if ( low >= high ) { - return; - } - unsigned long lo = low; - unsigned long m = high - 1; - - if ( lo >= m ) { - return; - } - - unsigned long hi = m - 1; - void **mp = pvector_entry( pv, m ); - void **lop, **hip; - for ( ;; ) { - // Find index of first item "above" mp scanning from lo and up - for ( ; lo < m; lo++ ) { - lop = pvector_entry( pv, lo ); - if ( compar( *lop, *mp ) < 0 ) { - break; - } - } - // if lo == m, then lop is wrong!! - // Find index of first item "below" mp scanning from hi and down - for ( ; hi > lo; hi-- ) { - hip = pvector_entry( pv, hi ); - if ( compar( *mp, *hip ) < 0 ) { - break; - } - } - if ( lo >= hi ) { - if ( lo < m ) { - void *x = *lop; - *lop = *mp; - *mp = x; - m = lo; - } - break; - } - void *x = *lop; - *lop = *hip; - *hip = x; - } - pvector_qsort_part( pv, compar, low, m ); - pvector_qsort_part( pv, compar, m+1, high ); -} - -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 deleted file mode 100644 index f2236f3..0000000 --- a/pvector/pvector.h +++ /dev/null @@ -1,134 +0,0 @@ -#ifndef pvector_H -#define pvector_H - -/** - * A pvector is a dynamic pointer array implemented as an access tree - * of index pages of 256 pointers. - */ - -/*! - * 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 long whole; // 64-bit unsigned integer - unsigned char level[8]; -} 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 long size; //!< Limit for the logical entries[] - pvector_page *entries; //!< Pointer to entries indexing -} pvector; - -// 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 -#define PV_PART(p,i) (((unsigned char*)&i)[p]) - -/*! - * 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; - */ -void **pvector_next_used( - pvector *pv,unsigned long *index, - int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data), - void *data ); - -/*! - * Function: int pvector_resize( - * pvector *pv,unsigned long new_size, - * int (*reclaim)(pvector *,unsigned long,void *item,void *data), - * void *data ) - * \param pv - * \param new_size - * \param reclaim - * \param data - * - * 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 data argument is passed on to the reclaim function. - * - * 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 long new_size, - int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data), - void *data ); - -/*! - * Function: void **pvector_entry(pvector *pv,unsigned long 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 long index); - -/*! - * Function: unsigned long pvector_size(pvector *pv) - * \param pv - the pvector record - * \returns the size of the pvector. - */ -inline unsigned long pvector_size(pvector *pv) { - return pv->size; -} - -void pvector_set(pvector *pv,unsigned long index,void *value); - -void *pvector_get(pvector *pv,unsigned long index); - -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)(const unsigned long ,const void *)); - -void pvector_qsort(pvector *pv,int (*compar)(const void *,const void *)); - -void pvector_iterate(pvector *pv, - int (*itemfn)(unsigned long,void*,void*), - void*); - -#endif diff --git a/pvector/qvector.h b/pvector/qvector.h deleted file mode 100644 index dfdad4b..0000000 --- a/pvector/qvector.h +++ /dev/null @@ -1,170 +0,0 @@ -#ifndef qvector_H -#define qvector_H - -/** - * A qvector is a dynamic pointer array implemented as an access tree - * of index pages. The indexing is done using "unsigned long" indexes. - */ - -/*! - * Type: qvector_index - * This is the general indexing used for qvector access. - */ -typedef unsigned long qvector_index; - -/*! - * Macro: QV_LEVEL_BITS - * This defines the number of bits in the indexing bit field. - */ -#define QV_LEVEL_BITS 4 - -/*! - * Macro: QV_INDEX_BITS - * This defines the number of bits of a qvector index - */ -#define QV_INDEX_BITS sizeof( qvector_index ) - -/*! - * Macro: QV_INDEX_FIELDS - * This defines the number of bit fields in an qvector index - */ -#define QV_INDEX_FIELDS ( ( QV_INDEX_BITS - 1 ) / QV_LEVEL_BITS + 1 ) - -/*! - * Macro: QV_SLOTS - * This defines the number of slots spanned by an index level - */ -#define QV_SLOTS ( 1 << QV_LEVEL_BITS ) - -/*! - * Type: qvector_page - * - * A qvector_page is an array of 16 void* items. - */ -typedef void* qvector_page[ QV_SLOTS ]; - -/*! - * Type: qvector_field - * This is QV_LEVEL_BITS size bit field - */ -typedef struct { int bits:QV_LEVEL_BITS; } qvector_field; - -/*! - * Type: qvector_indexing - * - * A qvector index is ether viewed in whole as an QV_INDEX_BITS wide - * unsigned, or in levels as a packed array of qvector_field index - * parts. This implementation assumes LE integer layout. - */ -typedef union { - qvector_index whole; // as a whole - qvector_field level[ QV_INDEX_FIELDS ]; // qua bits fields -} qvector_indexing; - -/*! - * Type: qvector - * - * A qvector is a compound of a size and a qvector_page pointer, which - * when non-null points out the top-most page of the qvector. The - * number of levels is derived from its size with level 0 being the - * leaf level of actual content. E.g., a qvector larger than 16 - * items, has at least two levels, and generally N levels may span up - * to 16^N content entries. - */ -typedef struct _qvector { - qvector_index size; //!< Limit for the logical entries[] - qvector_page *entries; //!< Pointer to entries indexing -} qvector; - -// Number of slots for page S -#define PV_LEVEL_SIZE(S) ((int)(exp( 16, (S) ))) - -// The indexing part for level part p in index i -#define PV_PART(i,p) (((qvector_indexing*)(i))->level[ p ].bits) - -/*! - * 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; - */ -void **qvector_next_used( - qvector *pv,qvector_index *index, - int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data), - void *data ); - -/*! - * Function: int qvector_resize( - * qvector *pv,qvector_index new_size, - * int (*reclaim)(qvector *,qvector_index,void *item,void *data), - * void *data ) - * \param pv - * \param new_size - * \param reclaim - * \param data - * - * Tries to resize the given qvector to a new size. This may result in - * the introduction or removal of indexing pages, so that the leveling - * is consistent with the qvector size. Thus, if it grows into a new - * 16^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 qvector size - * change. The data argument is passed on to the reclaim function. - * - * The qvector_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 qvector_resize( - qvector *pv, qvector_index new_size, - int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data), - void *data ); - -/*! - * Function: void **qvector_entry(qvector *pv,qvector_index index) - * \param pv - the qvector 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 qvector size is - * unchanged. - */ -extern void **qvector_entry(qvector *pv,qvector_index index); - -/*! - * Function: qvector_index qvector_size(qvector *pv) - * \param pv - the qvector record - * \returns the size of the qvector. - */ -inline qvector_index qvector_size(qvector *pv) { - return pv->size; -} - -void qvector_set(qvector *pv,qvector_index index,void *value); - -void *qvector_get(qvector *pv,qvector_index index); - -void qvector_append(qvector *pv,void *value); - -void qvector_copy(qvector *dst,qvector_index di, - qvector *src,qvector_index si,qvector_index n); - -void qvector_dump(qvector *pv, - int (*itemdump)(const qvector_index ,const void *)); - -void qvector_qsort(qvector *pv,int (*compar)(const void *,const void *)); - -void qvector_iterate(qvector *pv, - int (*itemfn)(qvector_index,void*,void*), - void*); - -#endif diff --git a/vector/Makefile b/vector/Makefile new file mode 100644 index 0000000..f8b05a7 --- /dev/null +++ b/vector/Makefile @@ -0,0 +1,26 @@ +LIBRARY = libvector.a +LIBOBJS = vector.o hashvector.o + +# This is overridable on command line +VECTOR_LEVEL_BITS = 4 + +default: $(LIBRARY) + +all: default + +CFLAGS = -Wall -g -fmax-errors=1 -DVECTOR_LEVEL_BITS=$(VECTOR_LEVEL_BITS) + +define STDCC +.INTERMEDIATE: $1.o +CLEANRM += $1.o +$1.o: $1.c | $1.h +endef + +$(foreach OBJ,$(LIBOBJS:.o=),$(eval $(call STDCC,$(OBJ)))) + +CLEANRM += $(LIBRARY) +$(LIBRARY): $(LIBOBJS) + $(AR) r $@ $^ + +clean: + rm -f $(CLEANRM) diff --git a/pvector/hashvector.c b/vector/hashvector.c similarity index 83% rename from pvector/hashvector.c rename to vector/hashvector.c index 11fdae8..1afae80 100644 --- a/pvector/hashvector.c +++ b/vector/hashvector.c @@ -10,7 +10,7 @@ static void **hashvector_find_slot(hashvector *hv,void *key) { void **hole = 0; void **p = 0; for ( ;; ) { - p = pvector_entry(&hv->table, i); + p = vector_entry(&hv->table, i); if ( p == 0 ) { return 0; // This basically means OOM, and is a failure condition. } @@ -47,7 +47,7 @@ int hashvector_find(hashvector *hv,void *key,void **x) { return 0; } -static int capture_item(pvector *pv,unsigned long ix,void *item,void *data) { +static int capture_item(vector *pv,unsigned long ix,void *item,void *data) { if ( item != HV_HOLE ) { hashvector_add( (hashvector *) data, item ); } @@ -68,9 +68,9 @@ static void hashvector_resize(hashvector *hv,unsigned long new_size) { hv->fill = 0; hv->holes = 0; if ( new_size < hv->table.size ) { - pvector_resize( &tmp.table, 0, capture_item, hv ); + vector_resize( &tmp.table, 0, capture_item, hv ); } else { - pvector_iterate( &tmp.table, iter_item, hv ); + vector_iterate( &tmp.table, iter_item, hv ); } } @@ -106,26 +106,24 @@ int hashvector_delete(hashvector *hv,void *item) { *p = HV_HOLE; hv->holes++; hv->fill--; - if ( hv->table.size > 256 ) { - if ( hv->fill < hv->table.size / 4 ) { - hashvector_resize( hv, hv->table.size / 2 ); - } + if ( hv->table.size > VECTOR_SLOTS && hv->fill < hv->table.size / 4 ) { + hashvector_resize( hv, hv->table.size / 2 ); } return 1; } -// Copy items into a pvector. Returns 0 on success and -1 on failure. -int hashvector_contents(hashvector *hv,pvector *pv) { - if ( pvector_resize( pv, hv->fill, 0, 0 ) ) { +// Copy items into a vector. Returns 0 on success and -1 on failure. +int hashvector_contents(hashvector *hv,vector *pv) { + if ( vector_resize( pv, hv->fill, 0, 0 ) ) { return -1; } unsigned long from = 0; unsigned long to = 0; while ( to < hv->fill ) { - void **slot = pvector_next_used( &hv->table, &from, 0, 0 ); + void **slot = vector_next_used( &hv->table, &from, 0, 0 ); if ( slot ) { if ( *slot != HV_HOLE ) { - pvector_set( pv, to++, *slot ); + vector_set( pv, to++, *slot ); } from++; } else { diff --git a/pvector/hashvector.h b/vector/hashvector.h similarity index 87% rename from pvector/hashvector.h rename to vector/hashvector.h index a5b426b..71b6253 100644 --- a/pvector/hashvector.h +++ b/vector/hashvector.h @@ -2,7 +2,7 @@ #define hashvector_H /** - * hashvector is a use of pvector as a hashtable. The hashvector + * A hashvector is a use of vector as a hashtable. The hashvector * includes three functions to, respectively, obtain the hashcode of a * given key, to obtain the key of a given item, and to tell whether * or not a given item has a given key. The hashvector manipulations @@ -20,15 +20,15 @@ * size when item numbers reduces below 50%. */ -#include "pvector.h" +#include "vector.h" /*! * Type: hashvector - * This combines a pvector (for contents) with fill and hole counters + * This combines a vector (for contents) with fill and hole counters * and the three functions. */ typedef struct _hashvector { - pvector table; + vector table; unsigned long fill; // number of added elements unsigned long holes; // number of deleted unsigned long (*keyhashcode)(void *key); // The hashcode of a key @@ -75,15 +75,15 @@ int hashvector_add(hashvector *hv,void *item); int hashvector_delete(hashvector *hv,void *item); /*! - * Function: int hashvector_contents(hashvector *hv,pvector *pv) + * Function: int hashvector_contents(hashvector *hv,vector *pv) * - * Copy content items into a pvector, which must be empty. The - * function returns -1 if the resizing of the pvector to the + * Copy content items into a vector, which must be empty. The + * function returns -1 if the resizing of the vector to the * hashvector fill fails, otherwise 0 after having copied the * hashvector items in their internal order of appearance into the - * pvector. + * vector. */ -int hashvector_contents(hashvector *hv,pvector *pv); +int hashvector_contents(hashvector *hv,vector *pv); /*! * Function unsigned long hashvector_hashcode( diff --git a/pvector/qvector.c b/vector/vector.c similarity index 58% rename from pvector/qvector.c rename to vector/vector.c index 1fc34ed..8dadf00 100644 --- a/pvector/qvector.c +++ b/vector/vector.c @@ -1,31 +1,31 @@ #include -#include "qvector.h" +#include "vector.h" /** * Representing a vector of void* accessible via an indexing structure - * as levels of same-size pages. A "qvector_page" is a contiguous - * array of 16 void*. + * as levels of same-size pages. A "vector_page" is a contiguous array + * void*, and an index is "unsigned long" (64 bits). */ /** - * Advances a qvector index to the next used slot at or below the + * Advances a vector 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 **qvector_level_next_used( - qvector_page *page,qvector_index *index,int level,qvector_index end) { - void **p = (void**)&(*page)[ PV_PART( index, level ) ]; +static void **vector_level_next_used( + vector_page *page,vector_index *index,int level,vector_index end) { + void **p = (void**)&(*page)[ VECTOR_INDEX_PART( index, 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 = PV_PART( index, level - 1 ) == 0; - void **x = qvector_level_next_used( *p, index, level - 1, end ); + int whole = VECTOR_INDEX_PART( index, level - 1 ) == 0; + void **x = vector_level_next_used( *p, index, level - 1, end ); if ( x ) { return x; // Used slot was found; return it. } @@ -35,7 +35,7 @@ static void **qvector_level_next_used( *p = 0; } } - if ( ++PV_PART( index, level ) == 0 ) { + if ( ++VECTOR_INDEX_PART( index, level ) == 0 ) { break; // cycling this level => nothing found } } @@ -43,30 +43,30 @@ static void **qvector_level_next_used( } // The least number of levels to span index S (typically the size of a -// qvector) -static unsigned int qvector_levels(qvector_index S) { +// vector) +static unsigned int vector_levels(vector_index S) { unsigned int N = 0; do { N++; - S /= QV_SLOTS; + S /= VECTOR_SLOTS; } while ( S ); return N; } // Find the next used slot at given index or later. Returns pointer to // the slot. -void **qvector_next_used( - qvector *pv,qvector_index *index, - int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data), +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 ) { *index = pv->size; return 0; } - int levels = qvector_levels( pv->size ); + int levels = vector_levels( pv->size ); for ( ; *index < pv->size; (*index)++ ) { - void **slot = qvector_level_next_used( + void **slot = vector_level_next_used( pv->entries, index, levels - 1, pv->size ) ; if ( slot == 0 ) { // reached the end of the vector @@ -86,12 +86,12 @@ void **qvector_next_used( } // Reclaim tree of unused pages -static void qvector_reclaim(qvector_page *page,unsigned int level) { +static void vector_reclaim(vector_page *page,unsigned int level) { int i = 0; if ( level > 0 ) { - for ( ; i < QV_SLOTS; i++ ) { + for ( ; i < VECTOR_SLOTS; i++ ) { if ( (*page)[i] ) { - qvector_reclaim( (qvector_page *) (*page)[i], level - 1 ); + vector_reclaim( (vector_page *) (*page)[i], level - 1 ); } } } @@ -106,9 +106,9 @@ static void qvector_reclaim(qvector_page *page,unsigned int level) { // 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 qvector_resize( - qvector *pv,qvector_index new_size, - int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data), +int vector_resize( + vector *pv,vector_index new_size, + int (*reclaim)(vector *pv,vector_index index,void *item,void *data), void *data ) { // Table of number of slots for a level above that of the number @@ -116,56 +116,56 @@ int qvector_resize( // 15 slots to the one slot of no index page. Level 1 adds 15*16 // slots, level 2 adds 15*(16^2), and generically level i adds // 15*(16^i) slots. - static int level_delta[ QV_INDEX_FIELDS ]; + static int level_delta[ VECTOR_INDEX_FIELDS ]; if ( level_delta[ 0 ] == 0 ) { int d = 1; int i; - for ( i = 0; i < QV_INDEX_FIELDS; i++ ) { - level_delta[ i ] = 15 * d; - d = 16 * d; + for ( i = 0; i < VECTOR_INDEX_FIELDS; i++ ) { + level_delta[ i ] = ( VECTOR_SLOTS - 1 ) * d; + d = VECTOR_SLOTS * d; } } struct { int old; int new; } level = { - qvector_levels( pv->size ), - qvector_levels( new_size ) + vector_levels( pv->size ), + vector_levels( new_size ) }; if ( pv->entries == 0 ) { pv->size = new_size; return 0; } - // A shrinking qvector might be veto-ed + // A shrinking vector might be veto-ed if ( new_size < pv->size ) { - qvector_index index = new_size; - void **slot = qvector_next_used( pv, &index, reclaim, data ); + vector_index index = new_size; + void **slot = vector_next_used( pv, &index, reclaim, data ); 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. - qvector_page *entries; - qvector_page **pp = &pv->entries; + vector_page *entries; + vector_page **pp = &pv->entries; while ( level.old-- > level.new ) { - pp = (qvector_page **)(*pp)[0]; + pp = (vector_page **)(*pp)[0]; } if ( pp != &pv->entries ) { entries = pv->entries; pv->entries = *pp; *pp = 0; - qvector_reclaim( entries, level.old ); + vector_reclaim( entries, level.old ); } if ( new_size == 0 ) { free( pv->entries ); pv->entries = 0; } } else { - // qvector is growing. Maybe insert levels. + // vector is growing. Maybe insert levels. while ( level.old < level.new ) { - qvector_page *p = (qvector_page *) - calloc( 1, sizeof( qvector_page ) ); + vector_page *p = (vector_page *) + calloc( 1, sizeof( vector_page ) ); if ( p == 0 ) { return -2; // OOM } @@ -184,74 +184,74 @@ int qvector_resize( // 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 QVECTORLEVELS( pv->size ) - 1 = -static void **qvector_access( - qvector *pv,qvector_index index,int level,int add) +// Level VECTORLEVELS( pv->size ) - 1 = +static void **vector_access( + vector *pv,vector_index index,int level,int add) { if ( index >= pv->size ) { return 0; } void **page = (void**) &pv->entries; - int i = qvector_levels( pv->size ); + int i = vector_levels( pv->size ); while ( i-- > level ) { if ( add && (*page) == 0 ) { - (*page) = calloc( QV_SLOTS, sizeof( void* ) ); + (*page) = calloc( VECTOR_SLOTS, sizeof( void* ) ); } page = (*page); if ( page == 0 ) { return 0; } - page += PV_PART( &index, i ); + page += VECTOR_INDEX_PART( &index, i ); } return page; } // Map index into a value slot -void **qvector_entry(qvector *pv,qvector_index index) { - return qvector_access( pv, index, 0, 1 ); +void **vector_entry(vector *pv,vector_index index) { + return vector_access( pv, index, 0, 1 ); } -inline void qvector_set(qvector *pv,qvector_index index,void *value) { - void **p = qvector_entry( pv, index ); +inline void vector_set(vector *pv,vector_index index,void *value) { + void **p = vector_entry( pv, index ); *p = value; } -inline void *qvector_get(qvector *pv,qvector_index index) { - return *(qvector_entry( pv, index )); +inline void *vector_get(vector *pv,vector_index index) { + return *(vector_entry( pv, index )); } -int qvector_reclaim_any(qvector *pv,qvector_index ix,void *item,void *data) { +int vector_reclaim_any(vector *pv,vector_index ix,void *item,void *data) { free( item ); return 0; } -void qvector_append(qvector *pv,void *value) { - qvector_resize( pv, pv->size + 1, 0, 0 ); - qvector_set( pv, pv->size - 1, value ); +void vector_append(vector *pv,void *value) { + vector_resize( pv, pv->size + 1, 0, 0 ); + vector_set( pv, pv->size - 1, value ); } // copy block of n items from src[si] to dst[di] // no efficiency hacks -void qvector_copy(qvector *dst,qvector_index di, - qvector *src,qvector_index si,qvector_index n) { +void vector_copy(vector *dst,vector_index di, + vector *src,vector_index si,vector_index n) { if ( dst != src || di < si ) { while ( n-- != 0 ) { - qvector_set( dst, di++, qvector_get( src, si++ ) ); + vector_set( dst, di++, vector_get( src, si++ ) ); } } else if ( di > si ){ di += n - 1; si += n - 1; while ( n-- != 0 ) { - qvector_set( dst, di--, qvector_get( src, si-- ) ); + vector_set( dst, di--, vector_get( src, si-- ) ); } } } -void qvector_dump(qvector *pv, - int (*itemdump)(const qvector_index,const void *)) { - qvector_index index = 0; +void vector_dump(vector *pv, + int (*itemdump)(const vector_index,const void *)) { + vector_index index = 0; for ( ; index < pv->size; index++ ) { - void **slot = qvector_next_used( pv, &index, 0, 0 ); + void **slot = vector_next_used( pv, &index, 0, 0 ); if ( slot == 0 ) { break; } @@ -264,27 +264,27 @@ void qvector_dump(qvector *pv, // Returns 1 for "in order", 0 for equal, and -1 for "wrong order" typedef int (*comparfn)(const void *,const void *); -static void qvector_qsort_part( - qvector *pv,comparfn compar, - qvector_index low,qvector_index high) +static void vector_qsort_part( + vector *pv,comparfn compar, + vector_index low,vector_index high) { if ( low >= high ) { return; } - qvector_index lo = low; - qvector_index m = high - 1; + vector_index lo = low; + vector_index m = high - 1; if ( lo >= m ) { return; } - qvector_index hi = m - 1; - void **mp = qvector_entry( pv, m ); + vector_index hi = m - 1; + void **mp = vector_entry( pv, m ); void **lop, **hip; for ( ;; ) { // Find index of first item "above" mp scanning from lo and up for ( ; lo < m; lo++ ) { - lop = qvector_entry( pv, lo ); + lop = vector_entry( pv, lo ); if ( compar( *lop, *mp ) < 0 ) { break; } @@ -292,7 +292,7 @@ static void qvector_qsort_part( // if lo == m, then lop is wrong!! // Find index of first item "below" mp scanning from hi and down for ( ; hi > lo; hi-- ) { - hip = qvector_entry( pv, hi ); + hip = vector_entry( pv, hi ); if ( compar( *mp, *hip ) < 0 ) { break; } @@ -310,26 +310,26 @@ static void qvector_qsort_part( *lop = *hip; *hip = x; } - qvector_qsort_part( pv, compar, low, m ); - qvector_qsort_part( pv, compar, m+1, high ); + vector_qsort_part( pv, compar, low, m ); + vector_qsort_part( pv, compar, m+1, high ); } -void qvector_qsort(qvector *pv,comparfn compar) { - qvector_qsort_part( pv, compar, 0, pv->size ); +void vector_qsort(vector *pv,comparfn compar) { + vector_qsort_part( pv, compar, 0, pv->size ); } -void qvector_iterate(qvector *pv, - int (*itemfn)(qvector_index,void*,void*), +void vector_iterate(vector *pv, + int (*itemfn)(vector_index,void*,void*), void *data ) { - qvector_index index = 0; + vector_index index = 0; while ( index < pv->size ) { - void **slot = qvector_next_used( pv, &index, 0, 0 ); + void **slot = vector_next_used( pv, &index, 0, 0 ); if ( slot == 0 ) { break; } int i = index & 0xff; - for ( ; i < QV_SLOTS && index < pv->size; i++, index++, slot++ ) { + for ( ; i < VECTOR_SLOTS && index < pv->size; i++, index++, slot++ ) { if ( itemfn( index, *slot, data ) ) { return; } diff --git a/vector/vector.h b/vector/vector.h new file mode 100644 index 0000000..1227860 --- /dev/null +++ b/vector/vector.h @@ -0,0 +1,168 @@ +#ifndef vector_H +#define vector_H + +/** + * A vector is a dynamic pointer array implemented as an access tree + * of index pages. The indexing is done using "unsigned long" indexes. + */ + +/*! + * Macro: VECTOR_LEVEL_BITS + * This defines the number of bits in the indexing bit field. + */ +#define VECTOR_LEVEL_BITS 4 + +/*! + * Type: vector_index + * This is the general indexing used for vector access. + */ +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 ) + +/*! + * Macro: VECTOR_INDEX_FIELDS + * This defines the number of bit fields in an vector index + */ +#define VECTOR_INDEX_FIELDS \ + ( ( VECTOR_INDEX_BITS - 1 ) / VECTOR_LEVEL_BITS + 1 ) + +/*! + * Macro: VECTOR_SLOTS + * This defines the number of slots spanned by an index level + */ +#define VECTOR_SLOTS ( 1 << VECTOR_LEVEL_BITS ) + +/*! + * Type: vector_page + * + * A vector_page is an array of 16 void* items. + */ +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 + * + * A vector is a compound of a size and a vector_page pointer, which + * when non-null points out the top-most page of the vector. The + * number of levels is derived from its size with level 0 being the + * leaf level of actual content. E.g., a vector larger than 16 + * items, has at least two levels, and generally N levels may span up + * to 16^N content entries. + */ +typedef struct _vector { + vector_index size; //!< Limit for the logical entries[] + vector_page *entries; //!< Pointer to entries indexing +} 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; + */ +void **vector_next_used( + vector *pv,vector_index *index, + int (*reclaim)(vector *pv,vector_index index,void *item,void *data), + void *data ); + +/*! + * Function: int vector_resize( + * vector *pv,vector_index new_size, + * int (*reclaim)(vector *,vector_index,void *item,void *data), + * void *data ) + * \param pv + * \param new_size + * \param reclaim + * \param data + * + * Tries to resize the given vector to a new size. This may result in + * the introduction or removal of indexing pages, so that the leveling + * is consistent with the vector size. Thus, if it grows into a new + * 16^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 vector size + * change. The data argument is passed on to the reclaim function. + * + * The vector_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 vector_resize( + vector *pv, vector_index new_size, + int (*reclaim)(vector *pv,vector_index index,void *item,void *data), + void *data ); + +/*! + * Function: void **vector_entry(vector *pv,vector_index index) + * \param pv - the vector 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 vector size is + * unchanged. + */ +extern void **vector_entry(vector *pv,vector_index index); + +/*! + * Function: vector_index vector_size(vector *pv) + * \param pv - the vector record + * \returns the size of the vector. + */ +inline vector_index vector_size(vector *pv) { + return pv->size; +} + +void vector_set(vector *pv,vector_index index,void *value); + +void *vector_get(vector *pv,vector_index index); + +void vector_append(vector *pv,void *value); + +void vector_copy(vector *dst,vector_index di, + vector *src,vector_index si,vector_index n); + +void vector_dump(vector *pv, + int (*itemdump)(const vector_index ,const void *)); + +void vector_qsort(vector *pv,int (*compar)(const void *,const void *)); + +void vector_iterate(vector *pv, + int (*itemfn)(vector_index,void*,void*), + void*); + +#endif -- 2.39.2