Code sample: C

The C language is the lingua franca of unix. Developers of other languages use C to write them. C itself is written in C.

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 );
}

Return to language index.


A publication of the School of Tyrannus

Copyright © 1998, The School of Tyrannus
All rights reserved