pvector/example-hashvector.c

   1 #include <arpa/inet.h>
   2 #include <errno.h>
   3 #include <fcntl.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7 #include <sys/stat.h>
   8 #include <sys/types.h>
   9 #include <unistd.h>
  10 #include "hashvector.h"
  11
  12 typedef struct _ipslot {
  13     int family;
  14     unsigned char data[32];
  15     unsigned int bits;
  16 } ipslot;
  17
  18 static unsigned long voidp_hashcode(void *key) {
  19     return hashvector_hashcode( key, sizeof( ipslot ) );
  20 }
  21
  22 static void* voidp_itemkey(void *item) {
  23     return item;
  24 }
  25
  26 static int voidp_haskey(void *item,void *key) {
  27     return memcmp( item, key, sizeof( ipslot ) ) == 0;
  28 }
  29
  30 static struct {
  31     hashvector hv;
  32     long fill;
  33 } table = {
  34     .hv = {
  35         .table = { 12000, 0 },
  36         .fill = 0,
  37         .holes = 0,
  38         .keyhashcode = voidp_hashcode,
  39         .itemkey = voidp_itemkey,
  40         .haskey = voidp_haskey
  41     },
  42     .fill = 0
  43 };
  44
  45 #define BUFSZ 10000
  46 static struct {
  47     char data[ BUFSZ ];
  48     int cur;
  49     int end;
  50 } stream;
  51
  52 static int readline(int fd,char **outp) {
  53     for ( ;; ) {
  54         char *curp = stream.data + stream.cur;
  55         char *endp = stream.data + stream.end;
  56         char *top = curp;
  57         while  ( curp < endp ) {
  58             if ( *(curp++) == '\n' ) {
  59                 stream.cur = curp - stream.data;
  60                 (*outp) = top;
  61                 return curp - top;
  62             }
  63         }
  64         if ( top != stream.data ) {
  65             curp = stream.data;
  66             while ( top < endp ) {
  67                 *(curp++) = *(top++);
  68             }
  69             endp = curp;
  70             stream.end = endp - stream.data;
  71         }
  72         stream.cur = 0;
  73         ssize_t n = read( fd, endp, BUFSZ - stream.end );
  74         if ( n <= 0 ) {
  75             if ( stream.end == 0 ) {
  76                 return -1; // No more data
  77             }
  78             (*outp) = stream.data;
  79             return stream.end;
  80         }
  81         stream.end += n;
  82     }
  83     //unreachable
  84 }
  85
  86 // Scan to NUL, CR or c. Return pointer not including character.
  87 static char *scanto(char *p, char c) {
  88     while ( *p && *p != '\n' && *p != c ) {
  89         p++;
  90     }
  91     return p;
  92 }
  93
  94 static int parse_addr(char *line,ipslot *addr) {
  95     char *end = scanto( line, '\n' );
  96     char *slash = scanto( line, '/' );
  97     *slash = 0;
  98     *end = 0;
  99     if ( inet_pton( AF_INET6, line, addr->data ) == 1 ) {
 100         addr->bits = 128;
 101         addr->family = AF_INET6;
 102     } else if ( inet_pton( AF_INET, line, addr->data ) == 1 ) {
 103         addr->bits = 32;
 104         addr->family = AF_INET;
 105     } else {
 106         return 1;
 107     }
 108     if ( slash != end && sscanf( slash+1, "%u", &addr->bits ) != 1 ) {
 109         return 2;
 110     }
 111     return 0;
 112 }
 113
 114
 115 static void add_entry(ipslot *tmp) {
 116     ipslot *p = (ipslot *) malloc( sizeof( ipslot ) );
 117     memmove( p, tmp, sizeof( ipslot ) );
 118     hashvector_add( &table.hv, p );
 119     table.fill++;
 120 #if 0
 121     pvector *pv = &table.hv.table;
 122     if ( pv->size == table.fill ) {
 123         (void) pvector_resize( pv, table.fill + 256, 0, 0 );
 124     }
 125     pvector_set( pv, table.fill++, p );
 126 #endif
 127 }
 128
 129 static void load_file(const char *filename) {
 130     int fd = open( filename, O_RDONLY );
 131     if ( fd < 0 ) {
 132         perror( filename );
 133         exit( errno );
 134     }
 135     char *line;
 136     int n;
 137     while ( ( n = readline( fd, &line ) ) >= 0 ) {
 138         ipslot addr;
 139         if ( parse_addr( line, &addr ) ) {
 140             fprintf( stderr, "Bad address: %s\n", line );
 141             continue;
 142         }
 143         add_entry( &addr );
 144     }
 145 }
 146
 147 static int int_reclaim(pvector *pv,unsigned long index,void *item,void *data) {
 148     return 0;
 149 }
 150
 151 static int dumpitem(unsigned long index,void *item) {
 152     fprintf( stdout, "[%ld] %p\n", index, item );
 153     return 0;
 154 }
 155
 156 static int dump_ipslot(unsigned long index,void *item) {
 157     static char buffer[100];
 158     ipslot *ip = (ipslot*) item;
 159     const char *p = inet_ntop( ip->family, ip->data, buffer, 100 );
 160     fprintf( stdout, "[%ld] %s/%d\n", index, p, ip->bits );
 161     return 0;
 162 }
 163
 164 static int compare_ipslot(void *ax,void *bx) {
 165     ipslot *a = (ipslot *) ax;
 166     ipslot *b = (ipslot *) bx;
 167     int x = b->family - a->family;
 168     if ( x ) {
 169         return ( x > 0 )? 1 : -1;
 170     }
 171     x = a->bits < b->bits? a->bits : b->bits;
 172     unsigned char *ap = a->data;
 173     unsigned char *bp = b->data;
 174     int d;
 175     for ( ; x >= 8; x -= 8 ) {
 176         d = *(bp++) - *(ap++);
 177         if ( d ) {
 178             return ( d > 0 )? 1 : -1;
 179         }
 180     }
 181     if ( x ) {
 182         x = 7 - x;
 183         d = ( (*bp) >> x ) - ( (*ap) >> x );
 184         if ( d ) {
 185             return ( d > 0 )? 1 : -1;
 186         }
 187     }
 188     x = b->bits - a->bits;
 189     if ( x ) {
 190         return ( x > 0 )? 1 : -1;
 191     }
 192     return 0;
 193 }
 194
 195 int main(int argc,char **argv) {
 196     pvector test = { 0 };
 197     pvector_resize( &test, 100, 0, 0 );
 198     pvector_set( &test, 5, (void*) 500 );
 199     pvector_set( &test, 55, (void*) 600 );
 200     //pvector_set( &test, 550, (void*) 800 );
 201     pvector_resize( &test, 300, 0, 0 );
 202     pvector_set( &test, 55, (void*) 650 );
 203     pvector_resize( &test, 30000, 0, 0 );
 204     pvector_set( &test, 22255, (void*) 26 );
 205     pvector_dump( &test, dumpitem );
 206     pvector_resize( &test, 100, int_reclaim, 0 );
 207     pvector_set( &test, 5, (void*) 2 );
 208     pvector_dump( &test, dumpitem );
 209     pvector_resize( &test, 0, int_reclaim, 0 ); // clear out the pvector
 210
 211     int i;
 212     for ( i = 1; i < argc; i++ ) {
 213         load_file( argv[ i ] );
 214     }
 215     fprintf( stdout, "---- hashvector after filling it %ld/%ld/%ld\n",
 216              table.hv.fill, table.hv.holes, table.hv.table.size );
 217     pvector_dump( &table.hv.table, dump_ipslot );
 218     if ( hashvector_contents( &table.hv, &test ) < 0 ) {
 219         fprintf( stdout, "test is not empty\n" );
 220     }
 221     fprintf( stdout, "---- hashvector contents in hash order\n" );
 222     pvector_dump( &test, dump_ipslot );
 223     pvector_qsort( &test, compare_ipslot );
 224     fprintf( stdout, "---- contents after sorting\n" );
 225     pvector_dump( &test, dump_ipslot );
 226     return 0;
 227 }