This program was written to perform a fast search of a list of domain names but was still incomplete when the need for it became moot. (The product it was meant to enhance was replaced by something else.)
The initialization portion reads in a list of domain names and loads them into a binary tree. Thereafter, calling the (reentrant) check_domain function will tell if the domain named in its argument is in the list. This program reads IP addresses into a separate area from the tree, but it does nothing with them. IP matching functionality was on my "to be added" list when the whole thing got shelved. But, hey, it can still serve for a bad example. ;-)
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include <sys/types.h>
#include <ctype.h>
#include <stdio.h>
#include <assert.h>
int gt( char *, char * );
int lt( char *, char * );
int insert_node( char * );
int domain_init( char * );
int check_domain( char * );
#define IDX_CHARS 7
#define NUM_BUCKETS 4
#define TRUE 1 == 1
#define FALSE !TRUE
/* The structure of the binary tree nodes. */
struct NODE {
struct NODE *root;
struct NODE *left;
struct NODE *right;
char *bufr;
};
/* This is the place from which we grow the tree. */
struct NODE domain_root;
/* These are globally visible. */
char **dom_ary;
char **ip_ary;
char *domblock;
int debug_on;
int domain_init( char *fname )
{
int swapped;
int lines;
int dom_lines;
int ip_lines;
int in_ip;
int in_dom;
int i, j;
unsigned long flen, readval;
char commentchar = ';';
char *ip_sect = "[IP Domains]";
char *nm_sect = "[Named Domains]";
char *p, *q;
FILE *fp;
extern struct NODE domain_root;
extern char **dom_ary;
extern char **ip_ary;
extern char *domblock;
assert( fname != NULL );
/* Open the domain name file. */
if ( ( fp = fopen( fname, "rb" ) ) == NULL ) {
if ( debug_on ) fprintf( stdout, "fileopen failed.\n" );
return( -1 );
};
/* And get the size. */
fseek( fp, 0, SEEK_END );
flen = ftell( fp );
fseek( fp, 0, SEEK_SET );
if ( debug_on ) fprintf( stdout,
"File %s is %d bytes long\n", fname, flen );
/* Grab the memory block and slurp in the domains. */
domblock = calloc( ( size_t )1, ( size_t )( flen + 12 ) );
if ( debug_on ) fprintf( stdout,
"Calloc'ed %d bytes at pointer %p\n", flen + 128, domblock );
readval = fread( domblock, ( size_t )1, ( size_t )flen, fp );
/* Oops. */
if ( readval < flen ) {
if ( debug_on ) fprintf( stdout, "File read failed.\n" );
free( domblock );
fclose( fp );
return( -2 );
};
fclose( fp );
/* Done with the file. Count how many lines we got. */
for ( p = domblock, lines = 0, dom_lines = 0, ip_lines = 0,
in_dom = FALSE, in_ip = FALSE;
p <= ( domblock + flen ); p = q ) {
for ( q = p;
( ( *q != 0x0a ) && ( *q != 0x0d ) && ( q <= ( domblock + flen ) ) );
q++ );
while ( ( *q == 0x0a ) || ( *q == 0x0d ) ) q++;
if ( *p == commentchar ) {
if ( debug_on ) fprintf( stdout,
"Skipping comment line.\n" );
continue;
} else if ( isspace( *p ) ) {
if ( debug_on ) fprintf( stdout,
"Skipping blank line.\n" );
continue;
};
if ( !strncmp( p, nm_sect, strlen( nm_sect ) ) ) {
in_dom = TRUE;
in_ip = FALSE;
if ( debug_on ) fprintf( stdout,
"Entering domain section.\n" );
continue;
};
if ( !strncmp( p, ip_sect, strlen( ip_sect ) ) ) {
in_dom = FALSE;
in_ip = TRUE;
if ( debug_on ) fprintf( stdout,
"Entering IP section.\n" );
continue;
};
lines++;
if ( in_ip && isdigit( *p ) ) ip_lines++;
if ( in_dom && isalpha( *p ) ) dom_lines++;
};
if ( debug_on ) fprintf( stdout,
"Counted %d lines in %s\n", lines, fname );
if ( debug_on ) fprintf( stdout,
"Counted %d ip's in %s\n", ip_lines, fname );
if ( debug_on ) fprintf( stdout,
"Counted %d domains in %s\n", dom_lines, fname );
/* Now allocate memory for the pointers. */
dom_ary = ( char** )calloc( sizeof( char * ), ( dom_lines + 1 ) );
if ( debug_on ) fprintf( stdout, "dom_ary calloc'ed at %p\n", dom_ary );
ip_ary = ( char** )calloc( sizeof( char * ), ( ip_lines + 1 ) );
if ( debug_on ) fprintf( stdout, "ip_ary calloc'ed at %p\n", ip_ary );
/* This creates a dynamic array of pointers, one for each line. */
for ( i = 0, j = 0, p = domblock, in_dom = 0, in_ip = 0;
p < ( domblock + flen ); p = q ) {
for ( q = p; ( ( *q != 0x0a ) && ( *q != 0x0d ) ); q++ );
while ( ( *q == 0x0a ) || ( *q == 0x0d ) ) *q++ = 0;
if ( debug_on ) {
fprintf( stdout, "p (%p) points to %s\n", p, p );
};
if ( !strncmp( p, nm_sect, strlen( nm_sect ) ) ) {
in_dom = TRUE;
in_ip = FALSE;
continue;
};
if ( !strncmp( p, ip_sect, strlen( ip_sect ) ) ) {
in_ip = TRUE;
in_dom = FALSE;
continue;
};
if ( in_dom ) dom_ary[ i++ ] = p;
if ( in_ip ) ip_ary[ j++ ] = p;
};
if ( debug_on ) {
fprintf( stdout, "Before sort:\n" );
for ( i = 0; i < dom_lines; i++ ) {
fprintf( stdout,
"dom_ary[ %d ] is %s\n", i, dom_ary[ i ] );
};
for ( i = 0; i < ip_lines; i++ ) {
fprintf( stdout,
"ip_ary[ %d ] is %s\n", i, ip_ary[ i ] );
};
};
/* Sort the lines. Yes, this *is* a bubble sort. So what? */
for ( swapped = TRUE; swapped == TRUE; ) {
for ( swapped = FALSE, i = 0; i < ( dom_lines - 1 ); i++ ) {
if ( gt( dom_ary[ i ], dom_ary[ i + 1 ] ) ) {
p = dom_ary[ i ];
dom_ary[ i ] = dom_ary[ i + 1 ];
dom_ary[ i + 1 ] = p;
swapped = TRUE;
};
};
};
/* And no 'sort' is complete without a 'uniq', right? */
for ( i = 0; i < ( dom_lines - 1 ); i++ ) {
if ( !( gt( dom_ary[ i ], dom_ary[ i + 1 ] ) ) &&
!( lt( dom_ary[ i ], dom_ary[ i + 1 ] ) ) ) {
for ( j = ( i + 1 ); j < dom_lines; j++ ) {
dom_ary[ j ] = dom_ary[ j + 1 ];
};
dom_lines--;
};
};
if ( debug_on ) {
fprintf( stdout, "After sort:\n" );
for ( i = 0; i < dom_lines; i++ ) {
fprintf( stdout,
"dom_ary[ %d ] is %s\n", i, dom_ary[ i ] );
};
};
if ( debug_on ) {
fprintf( stdout,
"Medial node is %s\n", dom_ary[ dom_lines >> 1 ] );
};
/* Grab the median pointer and plug it into the tree root. */
domain_root.root = &domain_root;
domain_root.left = NULL;
domain_root.right = NULL;
domain_root.bufr = dom_ary[ dom_lines >> 1 ];
/* And load the tree. */
for ( i = 2; dom_lines >> i; i++ ) {
for ( j = dom_lines >> i;
j < dom_lines; j += ( dom_lines >> i) ) {
insert_node( dom_ary[ j ] );
if ( debug_on ) {
fprintf( stdout, "i = %d; j = %d, node = %s\n",
i, j, dom_ary[ j ] );
};
};
};
/* Mop up in case we missed one. */
if ( debug_on ) fprintf( stdout, "Begin mop up operation.\n\n" );
for ( i = 0; i < dom_lines; i++ ) {
insert_node( dom_ary[ i ] );
};
return( 0 );
}
int gt( char *this, char *that )
{
char *p, *q;
assert( ( this != NULL ) && ( that != NULL ) );
for ( p = this, q = that; *p != 0; p++, q++ ) {
if ( *p == *q ) continue;
if ( *p > *q ) return( TRUE );
else break;
};
return( FALSE );
}
int lt( char *this, char *that )
{
char *p, *q;
assert( ( this != NULL ) && ( that != NULL ) );
for ( p = this, q = that; *q != 0; p++, q++ ) {
if ( *p == *q ) continue;
if ( *p < *q ) return( TRUE );
else break;
};
return( FALSE );
}
int insert_node( char *buf )
{
extern struct NODE domain_root;
struct NODE *ptr, *new;
assert( buf != NULL );
new = ( struct NODE * )calloc( sizeof( struct NODE ), 1 );
if ( new == NULL ) {
fprintf( stdout, "calloc failed building tree node\n" );
return( -1 );
};
new->bufr = buf;
new->left = NULL;
new->right = NULL;
for ( ptr = &domain_root; ; ) {
if ( gt( new->bufr, ptr->bufr ) ) {
if ( ptr->right == NULL ) {
ptr->right = new;
new->root = ptr;
break;
} else {
ptr = ptr->right;
continue;
};
} else {
if ( lt( new->bufr, ptr->bufr ) ) {
if ( ptr->left == NULL ) {
ptr->left = new;
new->root = ptr;
break;
} else {
ptr = ptr->left;
continue;
};
} else {
free( new ); /* Don't need it. */
break; /* it's the same ;-) */
};
};
};
return( 0 );
}
int check_domain( char *dname )
{
extern struct NODE domain_root;
struct NODE *ptr;
assert( dname != NULL );
for ( ptr = &domain_root; ; ) {
if ( gt( dname, ptr->bufr ) ) {
if ( ptr->right == NULL ) {
break;
} else {
ptr = ptr->right;
continue;
};
} else {
if ( lt( dname, ptr->bufr ) ) {
if ( ptr->left == NULL ) {
break;
} else {
ptr = ptr->left;
continue;
};
} else {
return( TRUE ); /* it's the same ;-) */
};
};
};
return( FALSE );
}
int main( int ac, char **av )
{
int retval;
debug_on = TRUE;
if ( ( retval == 0 ) && ( ac > 2 ) ) {
retval = domain_init( av[ 1 ] );
if ( retval == 0 ) {
fprintf( stdout, "Domain %s is %s the list\n",
av[ 2 ], ( check_domain( av[ 2 ] ) ? "in": "not in" ) );
};
};
free( dom_ary );
free( domblock );
return( retval );
}