Homework #15:  A Better String


OVERVIEW

Strings in C are represented as sequences of characters terminated by
an ASCII 0 (null byte). The sequences may be declared as either:
	char *
    or
	char []	

In either case, the string has a maximum capacity, i.e., there is
a limit on the number of characters that the string may contain.
C, unfortunately, does not complain if the capacity is exceeded;
rather the storage past the string becomes corrupted with the
characters that overflow outside the string.

The determination of the proper capacity for a particular string
and ensuring one does not exceed it is the cause of much grief
to the average programmer. Consider the following fragments of code:

	char s1[5] = "Hello";	/* Wrong - null byte makes it 6 */

	char *s;
	fgets(s,WHATEVER,stdin);
		/* Wrong - No storage has been allocated for the string */

	char s[] = "Hello";
		/* Good! - lets the compiler compute the proper capacity */
	char s2[] =  "world";	
		/* Good! - lets the compiler compute the proper capacity */

	strcat(s, s2);
		/* Wrong - concatenation overflows s capacity */

We would like to avoid such problems. To do so, we will introduce
a new data type. We will have a structure, which we name String:

	typedef struct {
		char *val;		/* Points to the actual string */
		int length;		/* Contains the length of the string */
	} String;

Our String data type consists of two fields, a char * which
points to the actual string (e.g., "Hello, world", etc.)
and the length of that string (excluding the terminating null byte). 

The important aspect of our String data type is that we will
always make sure the capacity of the string pointed to by val
is one greater than the length. This will guarantee that none
of the problems displayed above can occur. The extra byte of
capacity is due to the terminating null byte not being included
in the length.

Rather than using the functions supplied in string.h, which
is not aware of our new type, we will create a new set of
functions. We will name these functions so that they remind
us of the ones in string.h: StringCat, StringLen, StringCpy,
and so on. A full list of the functions to be implemented is
presented below.

==============================================================================

YOUR ASSIGNMENT

Implement and test the above data type. That is, you are
to create the following:

** A header/interface (String.h) file which contains the above structure
   declaration as well as the prototypes for the functions presented below.

** An implementation (String.c) file which contains the definitions
   of the functions (as well as anything else you deem appropriate
   for that file).

** A test driver (TestString.c) file. This file should contain at the very
   least a main function which tests your data type. You may wish
   to break the tests up into several functions for clarity.

==============================================================================

THE INTERFACE

typedef struct {
	char *val;
	int length;
} String;


void StringInit(String *s, char *str);	/* Initializes s to sequence of chars in str*/
void StringClr(String *s);		/* Resets s to the empty string		*/
int StringLen(String s);		/* Returns length of s 			*/
char *StringAt(String s, int n);	/* Returns pointer to nth char in s;	*/
					/*   null if n is outside legal range of s*/

int StringCmp(String s1, String s2);	/* Compares s1 with s2-- returns j<0	*/
					/* if s1 is less than s2, returns j==0	*/
					/* if s1 equals s2, returns j>0 otherwise*/
String *StringCpy(String *s1, String s2);/* Copies s2 to s1, returns pointer to s1 */
String *StringCat(String *s1, String s2);/* Catenates s2 to s1, returns pointer to s1 */
String *StringGet(String *s);		/* Reads characters into s until (and	*/
					/* including) the newline; returns s	*/
					/* if successful; null otherwise	*/     
					/* Do Not Assume that the maximum length */
					/* is any preset value!!!		*/
void StringPut(String s);		/* Prints s to stdout 			*/

String *StringFGet(String *s, FILE *f);/* Reads characters into s from f until	*/
					/*   (and includeing) the newline; 	*/
					/*   returns s if successful; null otherwise */ 
					/* Do NOT assume that the maximum string*/
					/* length is any preset value!!		*/
void StringFPut(String s, FILE *f);	/* Prints s to f 	

==============================================================================

REMARK ON IMPLEMENTATION

(1) Review the discussion of malloc - pages 361 on in text.

(2) Note that the value of val in the String structure will always come
	from malloc.  Do not set it pointing to a fixed array.

(3) To help you out with the above, here is an implementation of a
	hypothetical function  called "StringResetABC". This function
	is passed a pointer to a String that has already been
	initialized using malloc and resets it so that it represents
	the sequence of characters 'A' 'B' 'C':

	void
	StringResetABC(String *s) {
		char	ABC[] = "ABC";
		(*s).length = strlen(ABC);
		free((*s).val);		/* free old storage */
		(*s).val = (char *) malloc(1+(*s).length);
		strcpy((*s).val,ABC);
	}

(4) Thus, to set up a new value for a String, one must free the storage
	previously referenced by the val field and then malloc new
	storage and initialize it.

==============================================================================

A SAMPLE USE OF String

main () {
	String s1,s2,*s3p, s4;

	StringInit(&s1, "Hello");
	StringInit(&s2,  "world");
	StringCat(&s1, s2);
	StringPut(s1);

	fprintf(stdout,"Length of s1: %d\n", StringLen(s1));

	s3p = &s4;
	StringPut(*StringCpy(s3p, s1));	

	fprintf(stdout,"Enter as string: ");
	StringGet(s3p);
}

==============================================================================

TESTING

Make sure all operations are thoroughly tested. Make sure you handle the
empty string() correctly.

==============================================================================

SOMETHING TO REFLECT ON

Consider this String type. Is it the kind of "fullfledged"
type that we have discussed in class? Where does it fall
short?

==============================================================================

SUBMITTING YOUR HOMEWORK:

	Use the toteach command to submit String.c String.h TestString.c