#include /* 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; }