10 #include "hashvector.h"
12 typedef struct _ipslot {
14 unsigned char data[32];
18 static unsigned long voidp_hashcode(void *key) {
19 return hashvector_hashcode( key, sizeof( ipslot ) );
22 static void* voidp_itemkey(void *item) {
26 static int voidp_haskey(void *item,void *key) {
27 return memcmp( item, key, sizeof( ipslot ) ) == 0;
35 .table = { 12000, 0 },
38 .keyhashcode = voidp_hashcode,
39 .itemkey = voidp_itemkey,
40 .haskey = voidp_haskey
52 static int readline(int fd,char **outp) {
54 char *curp = stream.data + stream.cur;
55 char *endp = stream.data + stream.end;
57 while ( curp < endp ) {
58 if ( *(curp++) == '\n' ) {
59 stream.cur = curp - stream.data;
64 if ( top != stream.data ) {
66 while ( top < endp ) {
70 stream.end = endp - stream.data;
73 ssize_t n = read( fd, endp, BUFSZ - stream.end );
75 if ( stream.end == 0 ) {
76 return -1; // No more data
78 (*outp) = stream.data;
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 ) {
94 static int parse_addr(char *line,ipslot *addr) {
95 char *end = scanto( line, '\n' );
96 char *slash = scanto( line, '/' );
99 if ( inet_pton( AF_INET6, line, addr->data ) == 1 ) {
101 addr->family = AF_INET6;
102 } else if ( inet_pton( AF_INET, line, addr->data ) == 1 ) {
104 addr->family = AF_INET;
108 if ( slash != end && sscanf( slash+1, "%u", &addr->bits ) != 1 ) {
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 );
121 pvector *pv = &table.hv.table;
122 if ( pv->size == table.fill ) {
123 (void) pvector_resize( pv, table.fill + 256, 0, 0 );
125 pvector_set( pv, table.fill++, p );
129 static void load_file(const char *filename) {
130 int fd = open( filename, O_RDONLY );
137 while ( ( n = readline( fd, &line ) ) >= 0 ) {
139 if ( parse_addr( line, &addr ) ) {
140 fprintf( stderr, "Bad address: %s\n", line );
147 static int int_reclaim(pvector *pv,unsigned long index,void *item,void *data) {
151 static int dumpitem(const unsigned long index,const void *item) {
152 fprintf( stdout, "[%ld] %p\n", index, item );
156 static int dump_ipslot(const unsigned long index,const 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 );
164 static int compare_ipslot(const void *ax,const void *bx) {
165 ipslot *a = (ipslot *) ax;
166 ipslot *b = (ipslot *) bx;
167 int x = b->family - a->family;
169 return ( x > 0 )? 1 : -1;
171 x = a->bits < b->bits? a->bits : b->bits;
172 unsigned char *ap = a->data;
173 unsigned char *bp = b->data;
175 for ( ; x >= 8; x -= 8 ) {
176 d = *(bp++) - *(ap++);
178 return ( d > 0 )? 1 : -1;
183 d = ( (*bp) >> x ) - ( (*ap) >> x );
185 return ( d > 0 )? 1 : -1;
188 x = b->bits - a->bits;
190 return ( x > 0 )? 1 : -1;
195 static int shrink(pvector *pv,unsigned long index,void *item,void *data) {
197 if ( item == HV_HOLE ) {
198 ((hashvector*) data)->holes--;
201 ((hashvector*) data)->fill--;
207 int main(int argc,char **argv) {
209 pvector test = { 0 };
210 pvector_resize( &test, 100, 0, 0 );
211 pvector_set( &test, 5, (void*) 500 );
212 pvector_set( &test, 55, (void*) 600 );
213 //pvector_set( &test, 550, (void*) 800 );
214 pvector_resize( &test, 300, 0, 0 );
215 pvector_set( &test, 55, (void*) 650 );
216 pvector_resize( &test, 30000, 0, 0 );
217 pvector_set( &test, 22255, (void*) 26 );
218 pvector_dump( &test, dumpitem );
219 pvector_resize( &test, 100, int_reclaim, 0 );
220 pvector_set( &test, 5, (void*) 2 );
221 pvector_dump( &test, dumpitem );
222 pvector_resize( &test, 0, int_reclaim, 0 ); // clear out the pvector
225 for ( i = 1; i < argc; i++ ) {
226 load_file( argv[ i ] );
228 fprintf( stdout, "---- hashvector after filling it %ld/%ld/%ld\n",
229 table.hv.fill, table.hv.holes, table.hv.table.size );
230 pvector_dump( &table.hv.table, dump_ipslot );
231 if ( hashvector_contents( &table.hv, &test ) < 0 ) {
232 fprintf( stdout, "test is not empty\n" );
234 fprintf( stdout, "---- hashvector contents in hash order\n" );
235 pvector_dump( &test, dump_ipslot );
236 pvector_qsort( &test, compare_ipslot );
237 fprintf( stdout, "---- contents after sorting\n" );
238 pvector_dump( &test, dump_ipslot );
245 .keyhashcode = voidp_hashcode,
246 .itemkey = voidp_itemkey,
247 .haskey = voidp_haskey
250 for ( ; i < 259; i++ ) {
251 ipslot *item = (ipslot*) calloc( 1, sizeof( ipslot ) );
257 memcpy( item->data, "10.10.10.1", 10 );
258 hashvector_add( &hv, item );
260 pvector_resize( &hv.table, 256, shrink, &hv );