From ba5cab4faddcde50d4321267f775f0ab884da39e Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Mon, 20 Jun 2022 22:43:17 +1000 Subject: [PATCH] Added hashvector (actually) --- pvector/example-hashvector.c | 231 +++++++++++++++++++++++++++++++++++ pvector/hashvector.c | 117 ++++++++++++++++++ pvector/hashvector.h | 43 +++++++ 3 files changed, 391 insertions(+) create mode 100644 pvector/example-hashvector.c create mode 100644 pvector/hashvector.c create mode 100644 pvector/hashvector.h diff --git a/pvector/example-hashvector.c b/pvector/example-hashvector.c new file mode 100644 index 0000000..214738f --- /dev/null +++ b/pvector/example-hashvector.c @@ -0,0 +1,231 @@ +#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 int voidp_hashcode(void *key) { + unsigned char *p = (unsigned char *) key; + int value = 5381; + int i = 0; + for ( ; i < sizeof( ipslot ); i++ ) { + value += ( value << 5 ) + *(p++); + } + return value; +} + +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; + int 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(unsigned long index,void *item) { + fprintf( stdout, "[%ld] %p\n", index, item ); + return 0; +} + +static int dump_ipslot(unsigned long index,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(void *ax,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; +} + +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 ); + pvector_resize( &test, 0, int_reclaim, 0 ); // clear out the pvector + + int i; + for ( i = 1; i < argc; i++ ) { + load_file( argv[ i ] ); + } + pvector_dump( &table.hv.table, dump_ipslot ); + fprintf( stdout, "--------------\n" ); + if ( hashvector_pack( &table.hv, &test ) < 0 ) { + fprintf( stdout, "test is not empty\n" ); + } + pvector_dump( &test, dump_ipslot ); + fprintf( stdout, "--------------\n" ); + pvector_qsort( &test, compare_ipslot ); + pvector_dump( &test, dump_ipslot ); + return 0; +} diff --git a/pvector/hashvector.c b/pvector/hashvector.c new file mode 100644 index 0000000..35dcd2e --- /dev/null +++ b/pvector/hashvector.c @@ -0,0 +1,117 @@ +#include "hashvector.h" + +// Find the slot for the keyed element, and return pointer to it. +static void **hashvector_find_slot(hashvector *hv,void *key) { + unsigned int index = hv->keyhashcode( key ) % hv->table.size; + unsigned int i = index; + void **hole = 0; + for ( ;; ) { + void **p = pvector_entry(&hv->table, i); + if ( p == 0 ) { + return 0; + } + if ( *p ) { + if ( (*p) != HV_HOLE ) { + if ( hv->haskey( *p, key ) ) { + return p; + } + } else { + if ( hole == 0 ) { + hole = p; + } + if ( ++i == hv->table.size ) { + i = 0; + } + if ( i != index ) { + continue; + } + } + } + return ( hole )? hole : p; + } +} + +// Find the keyed element, and assign the x pointer, or assign 0. +// Returns 1 if element is found and 0 otherwise. +int hashvector_find(hashvector *hv,void *key,void **x) { + void **p = hashvector_find_slot( hv, key ); + if ( p && *p && *p != HV_HOLE ) { + *x = *p; + return 1; + } + return 0; +} + +static int capture_item(pvector *pv,unsigned long ix,void *item,void *data) { + if ( item != HV_HOLE ) { + hashvector_add( (hashvector *) data, item ); + } + return 0; +} + +static void hashvector_resize(hashvector *hv,unsigned int 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 ); +} + +// Add the given element. +void hashvector_add(hashvector *hv,void *item) { + void **p = hashvector_find_slot( hv, hv->itemkey( item ) ); + if ( p ) { + if ( *p ) { + if ( *p != HV_HOLE ) { + return; + } + hv->holes--; + } + *p = item; + hv->fill++; + if ( hv->fill + hv->holes > hv->table.size / 2 ) { + hashvector_resize( hv, hv->table.size * 2 ); + } + } +} + +// Return the next element starting at i, or 0 if there are no more. +// Also increment the index to be of the element + 1, or -1 if there +// are no more elements. +//unsigned char *htnext(htable *table,int *i); + +// Delete the given element. +void hashvector_delete(hashvector *hv,void *item) { + void **p = hashvector_find_slot( hv, hv->itemkey( item ) ); + if ( p && *p && *p != HV_HOLE ) { + *p = HV_HOLE; + hv->holes++; + if ( hv->table.size > 256 ) { + if ( hv->fill < hv->table.size / 2 ) { + hashvector_resize( hv, hv->table.size / 2 ); + } + } + } +} + +// Copy items into a pvector. Returns 0 on success and -1 on failure. +int hashvector_pack(hashvector *hv,pvector *pv) { + if ( pvector_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 ); + if ( slot ) { + if ( *slot != HV_HOLE ) { + pvector_set( pv, to++, *slot ); + } + from++; + } else { + break; + } + } + return 0; +} diff --git a/pvector/hashvector.h b/pvector/hashvector.h new file mode 100644 index 0000000..b886660 --- /dev/null +++ b/pvector/hashvector.h @@ -0,0 +1,43 @@ +#ifndef hashvector_H +#define hashvector_H + +#ifdef USE_PTHREAD +#define __USE_GNU 1 +#include +#endif + +#include "pvector.h" + +typedef struct _hashvector { + pvector table; + unsigned int fill; // number of added elements + unsigned int holes; // number of deleted + int (*keyhashcode)(void *key); + void *(*itemkey)(void *item); + int (*haskey)(void *item,void *key); +#ifdef USE_PTHREAD + pthread_mutex_t lock; +#endif +} hashvector; + +#define HV_HOLE ((void*) 1) + +// Find the keyed element, and assign the x pointer, or assign 0. +// Returns 1 if element is found and 0 otherwise. +int hashvector_find(hashvector *hv,void *key,void **x); + +// Add the given element. +void hashvector_add(hashvector *hv,void *p); + +// Return the next element starting at i, or 0 if there are no more. +// Also increment the index to be of the element + 1, or -1 if there +// are no more elements. +//unsigned char *htnext(htable *table,int *i); + +// Delete the given element. +void hashvector_delete(hashvector *hv,void *p); + +// Copy content items into pvector, which must be empty. +int hashvector_pack(hashvector *hv,pvector *pv); + +#endif -- 2.39.2