/*******************************   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 <stdio.h>#include <memory.h>#include <malloc.h>#include <string.h>#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 );#elsestatic 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 intExpandArray( 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 voidISort( 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 voidQSort( 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**/voidStrListAppend( 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**/voidStrListAppendFile( 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**/StrListStrListCreate()   {   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**/voidStrListDestroy( 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**/intStrListEqual( 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**/intStrListSize( 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**/voidStrListSort( 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**/voidStrListUnique( 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 */