/******************************* strlist.c ********************************* Purpose: String list abstract data type implementation. Notes: This module implements a straightforward string ordered list abstract data type. It is optimized for appending and deleting from the end of the list. Since they are ordered lists, string lists may be sorted, and their members are addressed by ordinal position (starting from 0). **/ #include #include #include #include #include "strlist.h" /******************************************************************************/ /****************** Private Defines and Data Structures *******************/ #define FALSE 0 #define TRUE 1 #define EOS '\0' #define INCREMENT 32 /* increase size by this much */ #define MAX_LINE 128 /* when reading text files */ typedef struct _StrListStruct { short size; /* current length of the list */ short max_size; /* room for this many strings */ char **string; /* the string array */ } StrListStruct; /********* GetMemory and FreeMemory Macros ********/ #define GetMemory(b,s) ( (b) ? realloc(b,s) : malloc(s) ) #define FreeMemory(b) ( (void)free( b ) ) /******************************************************************************/ /********************** Private Routine Declarations **********************/ #ifdef __STDC__ static int ExpandArray( StrList list ); static void ISort( char *string, int lb, int ub ); static void QSort( char **string, int lb, int ub ); #else static int ExpandArray( /* list */ ); static void ISort( /* string, lb, ub */ ); static void QSort( /* string, lb, ub */ ); #endif /*FN************************************************************************** ExpandArray( list ) Returns: int -- TRUE (1) on success, FALSE (0) otherwise Purpose: Increase the string array to hold more data Plan: Part 1: Increase the maximum list size to its new value Part 2: Allocate a new chunk of memory Part 3: Return an indication of success Notes: None **/ static int ExpandArray( list ) StrList list; /* in: string list whose string array is enlarged */ { /* Part 1: Increase the maximum list size to its new value */ list->max_size += INCREMENT; /* Part 2: Allocate a new chunk of memory */ list->string = (char **)GetMemory( (char *)list->string, (list->max_size*sizeof(char *)) ); /* Part 3: Return an indication of success */ return( (list->string) ? TRUE : FALSE ); } /* ExpandArray */ /*FN************************************************************************** ISort( string, lb, ub ) Returns: void Purpose: Insertion sort a string array forward using strcmp ordering Plan: Part 1: Put smallest in place as a sentinal Part 2: Insert as necessary Notes: None **/ static void ISort( string, lb, ub ) char **string; /* in/out: string array sorted */ int lb,ub; /* in: array bounds for sort */ { register int i,j; /* for scanning through the list */ char *tmp; /* for swaps */ /* Part 1: Put smallest in place as a sentinal */ for ( j = lb, i = lb+1; i <= ub; i++ ) if ( 0 < strcmp(string[j],string[i]) ) j = i; tmp = string[lb]; string[lb] = string[j]; string[j] = tmp; /* Part 2: Insert as necessary */ for ( i = lb+2; i <= ub; i++ ) { tmp = string[i]; for ( j = i; 0 < strcmp(string[j-1],tmp); j-- ) string[j] = string[j-1]; string[j] = tmp; } } /* ISort*/ /*FN************************************************************************** QSort( string, lb, ub ) Returns: void Purpose: Quicksort an array of strings forward using strcmp ordering Plan: Part 1: Use insertion sort of the list is short Part 2: Do median of three pivot value selection Part 3: Put the pivot out of the way at the top Part 5: Swap the pivot back into the mid of the list Part 6: Recursively sort the sublists Notes: Standard quicksort function with the two main enhancements: median of three partitioning to find a good pivot value, and sorting small arrays with insertion sort. **/ static void QSort( string, lb, ub ) char **string; /* in/out: string array sorted */ int lb,ub; /* in: array bounds for sort */ { register int lft; /* list pointer that closes from the left */ register int rgt; /* list pointer that closes from the right */ register int mid; /* index of the median of three value */ char *tmp; /* for string pointer swaps */ char *pivot; /* the pivot value string */ /* Part 1: Use insertion sort of the list is short */ if ( ub-lb < 12 ) { ISort( string, lb, ub ); return; } /* Part 2: Do median of three pivot value selection */ mid = (lb+ub)/2; if ( strcmp(string[mid],string[lb]) < 0 ) { tmp = string[mid]; string[mid] = string[lb]; string[lb] = tmp; } if ( strcmp(string[ub],string[mid]) < 0 ) { tmp = string[mid]; string[mid] = string[ub]; string[ub] = tmp; } if ( strcmp(string[mid],string[lb]) < 0 ) { tmp = string[mid]; string[mid] = string[lb]; string[lb] = tmp; } /* Part 3: Put the pivot out of the way at the top */ tmp = string[mid]; string[mid] = string[ub-1]; string[ub-1] = tmp; /* Part 4: Partition around the pivot value */ lft = lb; rgt = ub-1; pivot = string[ub-1]; do { do lft++; while ( strcmp(string[lft],pivot) < 0 ); do rgt--; while ( strcmp(pivot,string[rgt]) < 0 ); tmp = string[lft]; string[lft] = string[rgt]; string[rgt] = tmp; } while ( lft < rgt ); /* Part 5: Swap the pivot back into the mid of the list */ string[rgt] = string[lft]; string[lft] = string[ub-1]; string[ub-1] = tmp; /* Part 6: Recursively sort the sublists */ QSort( string, lb, lft-1 ); QSort( string, rgt+1, ub ); } /* QSort */ /******************************************************************************/ /********************** Public Routine Declarations ***********************/ /*FN*************************************************************************** StrListAppend( list, string ) Returns: void Purpose: Place a string on the end of a string list Plan: Part 1: Standard parameter sanity check Part 2: Expand the list as necessary Part 3: Append the new string to the tail Notes: None **/ void StrListAppend( list, string ) StrList list; /* in/out: list appended to */ char *string; /* in: the appended string */ { int length; /* of the added string and its terminator */ /* Part 1: Standard parameter sanity check */ if ( !list || !string ) return; /* Part 2: Expand the list as necessary */ if ( (list->size == list->max_size) && !ExpandArray(list) ) return; /* Part 3: Append the new string to the tail */ length = strlen( string ) + 1; list->string[list->size] = GetMemory( NULL, length ); (void)memcpy( list->string[list->size], string, length ); list->size++; } /* StrListAppend */ /*FN*************************************************************************** StrListAppendFile( list, filename ) Returns: void Purpose: Place all lines from a file on the end of a string list Plan: Part 1: Standard parameter sanity check Part 2: Expand the list as necessary Part 3: Append the new string to the tail Notes: None **/ void StrListAppendFile( list, filename ) StrList list; /* in/out: list appended to */ char *filename; /* in: the appended file */ { FILE *file; /* file handle for the text input file */ char buffer[MAX_LINE]; /* for storing text input file lines */ int length; /* of the added string and its terminator */ register int i; /* for looping through the TextBlock lines */ /* Part 1: Standard parameter sanity check */ if ( !list || !filename ) return; /* Part 2: Open the text input file; check for error */ if ( NULL == (file = fopen(filename,"r")) ) return; /* Part 3: Append to the list, checking for errors */ while ( NULL != fgets(buffer,MAX_LINE,file) ) { if ( (list->size == list->max_size) && !ExpandArray(list) ) return; i = list->size; length = strlen( buffer ); list->string[i] = GetMemory( NULL, (unsigned)length ); if ( NULL == list->string[i] ) return; (void)memcpy( list->string[i], buffer, length ); list->string[i][length-1] = EOS; list->size++; } /* Part 4: Close the text input file */ (void)fclose( file ); } /* StrListAppendFile */ /*FN*************************************************************************** StrListCreate() Returns: StrList -- a new structure, or NULL on failure Purpose: Allocate and initialize a new string list structure Plan: Part 1: Allocate space for the string list object Part 2: Initialize the structure fields Part 3: Return the new string list Notes: None **/ StrList StrListCreate() { StrList list; /* the new list returned */ /* Part 1: Allocate space for the string list object */ if ( !(list = (StrList)GetMemory(NULL,sizeof(StrListStruct))) ) return( NULL ); /* Part 2: Initialize the structure fields */ list->string = NULL; list->size = list->max_size = 0; if ( !ExpandArray(list) ) { FreeMemory( (char *)list ); return( NULL ); } /* Part 3: Return the new string list */ return( list ); } /* StrListCreate */ /*FN*************************************************************************** StrListDestroy( list ) Returns: void Purpose: Deallocate the space used for a string list Plan: Part 1: Standard parameter sanity check Part 2: Free all the space Notes: None **/ void StrListDestroy( list ) StrList list; /* in: the list destroyed */ { register int i; /* for scanning through the list */ /* Part 1: Standard parameter sanity check */ if ( !list ) return; /* Part 2: Free all the space */ for ( i = 0; i < list->size; i++ ) FreeMemory( (char *)(list->string[i]) ); FreeMemory( (char *)list ); } /* StrListDestroy */ /*FN*************************************************************************** StrListEqual( list1, list2 ) Returns: int -- TRUE if the lists are equivalent, FALSE otherwise Purpose: See if two lists have identical elements Plan: Part 1: Say not equal if the parameters are bad Part 2: Say not equal if sizes are different Part 3: Compare lists element by element Part 4: Say equal if everything checks out Notes: None **/ int StrListEqual( list1, list2 ) StrList list1,list2; /* in: lists compared */ { register int i; /* for scanning through the lists */ /* Part 1: Say not equal if the parameters are bad */ if ( !list1 || !list2 ) return( FALSE ); /* Part 2: Say not equal if sizes are different */ if ( list1->size != list2->size ) return( FALSE ); /* Part 3: Compare the lists element by element */ for ( i = 0; i < list1->size; i++ ) if ( *(list1->string[i]) != *(list2->string[i]) ) return( FALSE ); else if ( 0 != strcmp(list1->string[i],list2->string[i]) ) return( FALSE ); /* Part 5: Say equal if everything checks out */ return( TRUE ); } /* StrListEqual */ /*FN*************************************************************************** StrListPeek( list, index ) Returns: char * -- pointer to the requested string; NULL on error Purpose: Peek a string by its list index Plan: Part 1: Standard parameter sanity check Part 2: Return the requested string Notes: Note that this function is a hole in the data type encapsulation: it should return a copy, but this would force the consumer to deallocate the string. Design call. **/ char * StrListPeek( list, index ) StrList list; /* in: list retrieved from */ int index; /* in: which string to fetch */ { /* Part 1: Standard parameter sanity check */ if ( !list || (index < 0) || (list->size <= index) ) return( NULL ); /* Part 2: Return the requested string */ return( list->string[index] ); } /* StrListPeek */ /*FN*************************************************************************** StrListSize( list ) Returns: int -- the size of the list, 0 on error Purpose: Grab the list size Plan: Return the list size field Notes: None **/ int StrListSize( list ) StrList list; /* in: list queried */ { if ( !list ) return( 0 ); else return( list->size ); } /* StrListSize */ /*FN*************************************************************************** StrListSort( list ) Returns: void Purpose: Sort a single string list using strcmp ordering Plan: Part 1: Do parameter sanity checks, then sort Notes: None **/ void StrListSort( list ) StrList list; /* in/out: list sorted */ { /* Part 1: Do parameter sanity checks, then sort */ if ( !list ) return; QSort( list->string, 0, list->size-1 ); } /* StrListSort */ /*FN*************************************************************************** StrListUnique( list ) Returns: void Purpose: Sort a single string list using strcmp ordering, then remove duplicates. Plan: Part 1: Do parameters sanity checks Part 2: Sort the list Part 3: Remove duplicate strings Notes: None **/ void StrListUnique( list ) StrList list; /* in/out: list sorted and uniqued */ { register i,j; /* counters for copying down over duplicates */ /* Part 1: Do parameter sanity checks */ if ( !list ) return; /* Part 2: Sort the list */ QSort( list->string, 0, list->size-1 ); /* Part 3: Remove duplicate strings */ if ( 1 < list->size ) { for ( j = 0, i = 1; i < list->size; i++ ) { if ( 0 == strcmp(list->string[i],list->string[j]) ) (void)free( list->string[j] ); else j++; if ( j < i ) list->string[j] = list->string[i]; } list->size = j + 1; } } /* StrListUnique */