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