#include <stdio.h>

/* file_context_node

 * A node used in a linked list of file contexts.

 * Each node contains the regular expression, the type and 

 *  the context, as well as information about the regular

 *  expression. The regular expression data (meta, stem_len

 *  and str_len) can be filled in by using the fc_fill_data

 *  function after the regular expression has been loaded.

 * next points to the next node in the linked list.

 */

struct file_context_node { 

	char* regex;

	char* type;

        char* context;

        int meta;

        int stem_len;

        int str_len;

        struct file_context_node* next;

};

/* file_context_bucket

 * A node used in a linked list of buckets that contain

 *  file_context_node's.

 * Each node contains a pointer to a file_context_node which

 *  is the header of its linked list. This linked list is the

 *  content of this bucket.

 * next points to the next bucket in the linked list.

 */

struct file_context_bucket {

	struct file_context_node* data;

	struct file_context_bucket* next;

};

/* fc_merge

 * Merges two sorted file context linked lists into one

 *  sorted one.

 * Pass two lists a and b, and after the completion of fc_merge,

 *  the final list is contained in a, and b is empty.

 */

struct file_context_node* fc_merge( struct file_context_node* a, struct file_context_node* b )

{

        struct file_context_node* a_current;

        struct file_context_node* b_current;

        struct file_context_node* temp;

        struct file_context_node* jumpto;

        /* If a is a empty list, and b is not,

         *  set a as b and proceed to the end. */

        if( !a && b )

                a = b;

        /* If b is an empty list, leave a as it is. */

        else if( !b ) { }

        else {

                /* Make it so the list a has the lesser

                 *  first element always. */

                if( fc_compare( a, b ) == 1 ) {

                        temp = a;

                        a = b;

                        b = temp;

                }

                a_current = a;

                b_current = b;

                /* Merge by inserting b's nodes inbetween a's nodes. */

                while( a_current->next && b_current ) {

                        jumpto = a_current->next;

                        /* Insert b's nodes inbetween the current a node

                         *  and the next a node.*/

                        while( b_current && a_current->next &&

                               fc_compare( a_current->next, b_current) != -1 ) {                                temp = a_current->next;

                                a_current->next = b_current;

                                b_current = b_current->next;

                                a_current->next->next = temp;

                                a_current = a_current->next;

                        }

                        /* Skip all the inserted node from b to the

                         *  next node in the original a. */

                        a_current = jumpto;

                }

                /* if there is anything left in b to be inserted,

                   put it on the end */

                if( b_current ) {

                        a_current->next = b_current;

                }

        }

        b = NULL;

        return a;

}

/* fc_merge_sort

 * Sorts file contexts from least specific to more specific.

 * The bucket linked list is passed and after the completion

 *  of the fc_merge_sort function, there is only one bucket

 *  (pointed to by master) that contains a linked list

 *  of all the file contexts, in sorted order.

 * Explanation of the algorithm:

 *  The algorithm implemented in fc_merge_sort is an iterative

 *   implementation of merge sort.

 *  At first, each bucket has a linked list of file contexts

 *   that are 1 element each.

 *  Each pass, each odd numbered bucket is merged into the bucket

 *   before it. This halves the number of buckets each pass.

 *  It will continue passing over the buckets (as described above)

 *   until there is only  one bucket left, containing the list of

 *   file contexts, sorted.

 */

void fc_merge_sort( struct file_context_bucket* master )

{

        int i;

        struct file_context_bucket* current;

        struct file_context_bucket* temp;

        struct file_context_node* ncurrent;

        struct file_context_node* ntemp;

	/* Loop until master is the only bucket left

         * so that this will stop when master contains

	 * the sorted list. */

        while( master->next ) {

                current = master;

		/* This loop merges buckets two-by-two. */

		while( current ) {

                        if( current->next ) {

				/* Merge the next one into the current one. */

                                current->data = fc_merge( current->data, current->next->data );

                        	/* remove the next bucket that is now empty. */

				temp = current->next;

                                current->next = current->next->next;

                                free( temp );

                        }

                        current = current->next;

                }

        }

}

/* fc_compare

 * Compares two file contexts' regular expressions and returns:

 *    -1 if a is less specific than b

 *     0 if a and be are equally specific

 *     1 if a is more specific than b

 * The comparison is based on the following statements,

 *  in order from most important to least important, given a and b:

 *     If a is a regular expression and b is not,

 *      -> a is less specific than b.

 *     If a's stem length is shorter than b's stem length,

 *      -> a is less specific than b.

 *     If a's string length is shorter than b's string length,

 *      -> a is less specific than b.

 *     If a does not have a specified type and b does not,

 *      -> a is less specific than b.

 */

int fc_compare( struct file_context_node* a, struct file_context_node* b )

{

	/* Check to see if either a or b have meta characters

         *  and the other doesn't. */

        if( a->meta && !b->meta )

                return -1;

        if( b->meta && !a->meta )

                return 1;

	/* Check to see if either a or b have a shorter stem

         *  length than the other. */

        if( a->stem_len < b->stem_len )

                return -1;

        if( b->stem_len < a->stem_len )

                return 1;

	/* Check to see if either a or b have a shorter string

         *  length than the other. */

        if( a->str_len < b->str_len )

                return -1;

        if( b->str_len < b->str_len )

                return 1;

	/* Check to see if either a or b has a specified type

         *  and the other doesn't. */

        if( !a->type && b->type )

                return -1;

        if( !b->type && a->type )

                return 1;

	/* If none of the above conditions were satisfied, 

         * then a and b are equally specific. */

        return 0;

}

/* fc_fill_data

 * This processes a regular expression in a file context

 *  and sets the data held in file_context_node, namely

 *  meta, str_len and stem_len. 

 * The following changes are made to fc_node after the

 *  the completion of the function:

 *     fc_node->meta =		1 if regex has a meta character,

 *                       	0 if not.

 *     fc_node->str_len =	The string length of the regular

 *                               expression.

 *     fc_node->stem_len = 	The number of characters up until

 *				 the first meta character.

 */

void fc_fill_data( struct file_context_node* fc_node )

{

        int c = 0;

        fc_node->meta = 0;

        fc_node->stem_len = 0;

        fc_node->str_len = 0;

	/* Process until the string termination character

         *  has been reached.

	 * Note: this while loop has been adapted from

         *  spec_hasMetaChars in matchpathcon.c from

         *  libselinux-1.22. */

        while( fc_node->regex[c] != 0 ) {

                switch( fc_node->regex[c] ) {

                        case '.':

                        case '^':

                        case '$':

                        case '?':

                        case '*':

                        case '+':

                        case '|':

                        case '[':

                        case '(':

                        case '{':

            			/* If a meta character is found,

                                 *  set meta to one */

		                fc_node->meta = 1;

                                break;

                        case '\\':

				/* If a escape character is found,

                                 *  skip the next character. */

                                c++;

                        default:

				/* If no meta character has been found yet,

				 *  add one to the stem length. */

                                if( !fc_node->meta ) fc_node->stem_len++;

                                break;

                }

		fc_node->str_len++;

                c++;

        }

}

/* main

 * This program takes in two arguments, the input filename and the

 *  output filename. The input file should be syntactically correct.

 * Overall what is done in the main is read in the file and store each

 *  line of code, sort it, then output it to the output file.

 */

int main( int argc, char *argv[])

{

	int i, j, lines;

	int start, finish;

	char* str;

	struct file_context_node* temp;

	struct file_context_node* head;

	struct file_context_node* current;

	struct file_context_node* array; 

	struct file_context_bucket* master;

	struct file_context_bucket* bcurrent;

	FILE *path;

	char line_buf[ 127 ];

	/* Check for the correct number of command line arguments. */

	if( argc != 3 ) {

		printf( "Error: invalid number of command line arguments.\n" );

		return -1;

	}

	i = j = lines = 0;

	/* Allocate the head of the file_context linked list. */

	if( !( current = head = (struct file_context_node*)malloc( sizeof( struct file_context_node ) ) ) ) {

		printf( "Error: failure allocating memory.\n" );

		return -1;

	}

	/* Make sure to have a terminating character, always. */

	line_buf[127] = 0;

	/* Open the input file. */

	if( !( path = fopen( argv[1], "r" ) ) ) {

		printf( "Error: failure opening input file for read.\n" );

		return -1;

	}

	/* Parse the file into a file_context linked list. */

	while( fgets( line_buf, 126, path ) != NULL ) {

		/* Get rid of whitespace from the front of the line. */

		i = 0;

		while( line_buf[i] && line_buf[i] <= 32 ) i++;

		/* Check if the line isn't empty and isn't a comment */

		if( line_buf[i] && line_buf[i] != '#' ) {

			/* Allocate a new node. */

			temp = (struct file_context_node*)malloc( sizeof( struct file_context_node ) );

			if( !temp ) {

				printf( "Error: failure allocating memory.\n" );

				return -1;

			}

			temp->next = NULL;

			/* Parse out the regular expression from the line. */

			start = i;

			while( line_buf[i] > 32 )i++;

			finish = i;

			/* Allocate a character array to hold the regular

 			 *  expression. */

			temp->regex = (char*)malloc( sizeof( char ) * ( finish - start + 1) );

			if( !( temp->regex ) ) {

				printf( "Error: failure allocating memory.\n" );

				return -1;

			}

			temp->regex[0] = 0;

			/* Fill the regular expression array. */

			temp->regex[ ( finish - start ) ] = 0;

			for( j = 0; j < finish - start; j++ ) {

				temp->regex[j] = line_buf[j + start];

			}

			/* Get rid of whitespace after the regular

                         *  expression. */

			while( line_buf[i] <= 32 ) i++;

			/* Parse out the type from the line (if it 

                         *  is there). */

			if( line_buf[i] == '-' ) {

				/* Allocate a character array to

                                 *  hold the type. */

				temp->type = (char*)malloc( sizeof( char ) * 3 );

				if( !( temp->type ) ) {

					printf( "Error: failure allocating memory.\n" );

					return -1;

				}

				/* Fill the type into the array. */

				temp->type[0] = line_buf[i];

				temp->type[1] = line_buf[i + 1];

				i += 2;

				temp->type[2] = 0;

				/* Get rid of whitespace after the type. */

				while( line_buf[i] <= 32 ) i++;

			}

			/* Parse out the context from the line. */

                        start = i;

                        while( line_buf[i] > 32 ) i++;

                        finish = i;

			/* Allocate a character array to hold the context. */

                        temp->context = (char*)malloc( sizeof( char ) * ( finish - start + 1 ) );

			if( !( temp->context ) ) {

				printf( "Error: failure allocating memory.\n" );

				return -1;

			}

			temp->context[0] = 0;

			/* Fill the context array. */

                        temp->context[ ( finish - start ) ] = 0;

                        for( j = 0; j < finish - start; j++ ) {

                                temp->context[j] = line_buf[j + start];

                        }

			/* Set all the data about the regular

                         *  expression. */

			fc_fill_data( temp );

			/* Link this line of code at the end of

                         *  the linked list. */

			current->next = temp;

			current = current->next;

			lines++;

		}

	}

	fclose( path );

	/* Create the bucket linked list from the earlier linked list. */

	current = head->next;

	bcurrent = master = (struct file_context_bucket*)malloc( sizeof( struct file_context_bucket ) );

	/* Go until all the nodes have been put in individual buckets. */

	while( current ) {

		/* Copy over the file context line into the bucket. */

		bcurrent->data = current;

		current = current->next;

		/* Detatch the node in the bucket from the old list. */

		bcurrent->data->next = NULL;

		/* If there should be another bucket, put one at the end. */

		if( current ) {

			bcurrent->next = (struct file_context_bucket*) malloc( sizeof( struct file_context_bucket ) );

			if( !( bcurrent->next ) ) {

				printf( "Error: failure allocating memory.\n" );

				return -1;

			}

			/* Make sure the new bucket thinks it's the end of the

                         *  list. */

			bcurrent->next->next = NULL;

			bcurrent = bcurrent->next;

		}

	}

	/* Sort the bucket list. */

	fc_merge_sort( master );

	/* Open the output file. */

	if( !(path = fopen( argv[2], "w" ) ) ) {

		printf( "Error: failure opening output file for write.\n" );

		return -1;

	}

	/* Output the sorted file_context linked list to the output file. */

	current = master->data;

	while( current ) {

		/* Output the regular expression. */

		i = 0;

		while( current->regex[i] != 0 ) {

			fprintf( path, "%c", current->regex[i] );

			i++;

		}

		fprintf( path, "\t" );

		/* Output the type, if there is one. */

		if( current->type ) {

			i = 0;

			while( current->type[i] != 0 ) {

				fprintf( path, "%c", current->type[i] );

				i++;

			}

			fprintf( path, "\t" ); 	

		}

		/* Output the context. */

		i = 0;

		while( current->context[i] != 0 ) {

			fprintf( path, "%c", current->context[i] );

			i++;

		}

		fprintf( path, "\n" );

		/* Remove the node. */

		temp = current;

		current = current->next;

		free( temp->regex );

		if( temp->type)

			free( temp->type );

		free( temp->context );		

		free( temp );

	}

	free( master );

	fclose( path );

	return 0;

}