Princeton University
COS 217: Introduction to Programming Systems

Assignment 2: A String Module


Purpose

The purpose of this assignment is to help you learn/review (1) arrays and pointers in the C programming language, (2) how to create and use stateless modules in C, (3) the "design by contract" style of programming, and (4) how to use the GNU/UNIX programming tools, especially bash, xemacs, gcc, and gdb.


Background

As you know, the C programming environment contains a standard library. The facilities provided in the standard library are declared in header files. One of those header files is string.h; it contains the declarations of "string functions," that is, functions that perform operations on character strings. Appendix D of the King textbook, Appendix B3 of the Kernighan and Ritchie textbook, Chapter 13 of the Harbison and Steele textbook, and the UNIX "man" pages describe the string functions. The string functions are used heavily in programming systems; certainly any editor, compiler, assembler, or operating system created with the C programming language would use them.


Your Task

Your task in this assignment is to use C to create a "Str" module that contains versions of the most commonly used standard string functions. Specifically, design your Str module so it contains these functions, each of which behaves the same as a corresponding standard C function:

   Str Function

   Standard C Function

   Str_getLength()    strlen()
   Str_copy()    strcpy()
   Str_ncopy()    strncpy()
   Str_concat()    strcat()
   Str_nconcat()    strncat()
   Str_compare()    strcmp()
   Str_ncompare()    strncmp()
   Str_search()    strstr()

The Details

Use "design by contract." Design each function comment so it describes that function's "checked runtime errors." Design each function definition so it calls the assert() macro to enforce those checked runtime errors. (In that way your Str functions should differ from the standard string functions.) Specifically, design each function definition so it calls assert() to make sure that none of its pointer/array formal parameters is NULL.

Do not add any other calls to assert() to your code. But consider whether it would be possible to do so. In particular, provide answers to these two questions in your readme file:

  1. Is it possible for Str_copy(), Str_ncopy(), Str_concat(), or Str_nconcat() to call assert() to verify that the specified destination memory area is large enough? Explain.
  2. Is it possible for Str_ncopy(), Str_nconcat(), or Str_ncompare() to call assert() to verify that the specified length parameter is non-negative? Explain.

Create two implementations of your Str module. Place the first implementation in a file named stra.c. Design the function definitions in stra.c such that they use array notation, and traverse each given string using an index relative to the beginning of the string. For example, in stra.c you might define the Str_getLength() function like this:

size_t Str_getLength(const char pcStr[])
{
   size_t uiLength = 0U;
   assert(pcStr != NULL);
   while (pcStr[uiLength] != '\0')
      uiLength++;
   return uiLength;
}

Note that the type of uiLength is size_t. The type size_t is defined in the standard header file stddef.h. It is a system-dependent unsigned integral type that is large enough to hold the length of any string. Typically it is defined to be identical to either unsigned int or unsigned long. On hats, it is identical to unsigned int. Several of the standard string functions use type size_t, and so several of your functions should use it too.

Note that the initial value of uiLength is 0U. The "U" suffix indicates that the literal is of type unsigned int instead of int. Simply initializing uiLength to 0 works because C allows initialization of an unsigned int variable with an int literal. However, as a matter of style, we suggest that you avoid mixing types within expressions.

Place the second implementation in a file named strp.c. Design the function definitions in strp.c such that they use pointer notation, and traverse each given string using an incremented pointer -- not using an index relative to the beginning of the string. For example, in strp.c you might define the Str_getLength() function like this:

size_t Str_getLength(const char *pcStr)
{
   const char *pcStrEnd = pcStr;
   assert(pcStr != NULL);
   while (*pcStrEnd != '\0')
      pcStrEnd++;
   return (size_t)(pcStrEnd - pcStr);
}

Place the Str module's interface in a file named str.h. You may use either array or pointer notation in the interface. The two notations are equivalent to the compiler, so both implementation match the one interface. Use the "#ifndef...#define...#endif" construct to protect your str.h file against accidental multiple inclusion.

This assignment does not focus on efficiency. Nevertheless, your functions should not be grossly inefficient. For example, a function is grossly inefficient if it traverses a (potentially long) string more than once when a single traversal would suffice.

Design your Str functions so they do not call any of the standard string functions. In the context of this assignment, pretend that the standard string functions do not exist. However your functions may call each other, and you may define additional (non-interface) functions.

Beware of type mismatches. In particular, beware of the difference between type size_t and type int: a variable of type size_t can store larger numbers than a variable of type int can. Also beware of type mismatches related to the use of the "const" keyword. Using the Splint tool (as described below) will help you to detect type mismatches.

In your assignment solution you may use any of the definitions of the Str_getLength() function given in this assignment specification.


Logistics

Create your Str module on hats using the bash shell, xemacs, gcc, and gdb.

A client that you can use to test your Str module is available in the file /u/cos217/Assignment2/teststr.c.

Create a "readme" text file that contains:

Submit your work electronically on hats via the command:

submit 2 str.h stra.c strp.c readme

Grading

We will grade your work on quality from the user's point of view and quality from the programmer's point of view. To encourage good coding practices, we will compile using "gcc -Wall -ansi -pedantic" and take off points based on warning messages.

From the user's point of view, a program has quality if it behaves as it should. The correct behavior of the Str module is defined by the previous sections of this assignment specification, and by the C90 specifications of the corresponding string.h functions.

From the programmer's point of view, a program has quality if it is well styled and thereby simple to maintain. In part, style is defined by the rules given in The Practice of Programming (Kernighan and Pike), as summarized by the Rules of Programming Style document. These additional rules apply:

Names: You should use a clear and consistent style for variable and function names. One example of such a style is to prefix each variable name with characters that indicate its type. For example, the prefix "c" might indicate that the variable is of type char, "i" might indicate int, "pc" might mean pointer to char, "ui" might mean unsigned int, etc. But it is fine to use other stylesm -- styles which do not include the type of a variable in its name, as long as they result in clear and readable programs.

Line lengths: Limit line lengths in your source code to 72 characters. Doing so allows us to print your work in two columns, thus saving paper.

Comments: Each source code file should begin with a comment that includes your name, the number of the assignment, and the name of the file.

Comments: Each function should begin with a comment that describes what the function does. The function comment should:

In short, a function's comment should describe the flow of data into and out of the function. For example, this is an appropriate way to comment the Str_getLength() function:

In file str.h:

...
size_t Str_getLength(const char pcStr[]);
/* Return the length of string pcStr.
   It is a checked runtime error for pcStr to be NULL. */
...

In file strp.c:

...
size_t Str_getLength(const char *pcStr)

/* Return the length of string pcStr.
   It is a checked runtime error for pcStr to be NULL. */

{
   const char *pcStrEnd = pcStr;
   assert(pcStr != NULL);
   while (*pcStrEnd != '\0')
      pcStrEnd++;
   return (size_t)(pcStrEnd - pcStr);
}
...

Note that the comment explicitly states what the function returns, explicitly refers to the function's parameter (pcStr), and explicitly describes the function's checked runtime error.


Special Note: Idioms

C programmers sometimes use idioms that rely on the fact that the end-of-string character, the NULL pointer, and FALSE have the same representation. You may use those idioms. For example, you may define your Str_getLength() function like this:

size_t Str_getLength(const char pcStr[])
{
   size_t uiLength = 0U;
   assert(pcStr);          /* Works because NULL and FALSE are identical. */
   while (pcStr[uiLength]) /* Works because end-of-string and FALSE are identical. */
      uiLength++;
   return uiLength;
}

or like this:

size_t Str_getLength(const char *pcStr)
{
   const char *pcStrEnd = pcStr;
   assert(pcStr);    /* Works because NULL and FALSE are identical. */
   while (*pcStrEnd) /* Works because end-of-string and FALSE are identical. */
      pcStrEnd++;
   return (size_t)(pcStrEnd - pcStr);
}

But you are not required to use those idioms. In fact, we recommend that you avoid the use of idioms that adversely affect understandability.


Special Note: "Const" and the Str_search() Function

The use of the "const" keyword within the Str_search() function is tricky, as this question/answer sequence indicates.

Question

According to the man pages, the formal parameters of the strstr() function are of type const char*. That implies that the formal parameters of Str_search() also should be of type const char*. Why aren't they of type char*?

Answer

Suppose you were to define your Str_search() function like this:

char *Str_search(char *pcHaystack, char *pcNeedle) { ... }

Further suppose the client then calls Str_search() like this:

const char *pcString1 = "hello";
const char *pcString2 = "lo";
...
... Str_search(pcString1, pcString2) ...
...

(Note that's a perfectly reasonable way to call the function.) In that case the compiler, noting that pcString1 is of type const char* and that pcHaystack is of type char*, would generate a warning on the function call. Thus pcHaystack (and pcNeedle) should be of type const char*.

Question

According to the man pages, the return type of strstr() is char*. That implies that the return type of Str_search() also should be of type char*. Why isn't the return type const char*?

Answer

Suppose you were to define Str_search() like this:

const char *Str_search(const char *pcHaystack, const char *pcNeedle) { ... }

Further suppose the client then calls Str_search() like this:

char *pcString1 = "hello";
char *pcString2 = "lo";
char *pc;
...
pc = Str_search(pcString1, pcString2);
...

(Note that's a perfectly reasonable way to call the function.) In that case the compiler, noting that pc is of type char* and that the value returned by Str_search() is of type const char*, would generate a warning on the assignment statement. Thus the return type of Str_search() should be char* and should not be const char*.

Question

Within the definition of Str_search(), I decided to define a local variable named pc that "points into" the first of the two given strings, as indicated by this code:

char *Str_search(const char *pcHaystack, const char *pcNeedle)
{
   ...
   pc = pcHaystack;
   ...
   /* Increment pc so it points to the appropriate character. */
   ...
   return pc;
}

If I define pc to be of type char*, then the assignment statement generates a warning. If I define pc to be of type const char*, then the return statement generates a warning. How can I resolve that problem?

Answer

Unfortunately, C provides no elegant solution. We recommend that you define pc to be of type const char* so the assignment statement is warningless. Then use a cast operator in the return statement:

return (char*)pc;

to explicitly inform the compiler to not generate a warning. C programmers refer to that solution as "casting away the constness" of the variable. Sadly, often that inelegant technique is unavoidable.


Special Note: Splint

Splint is a high-powered static code analysis tool that was developed at the University of Virginia. It is available to you on the hats cluster.

You typically execute Splint after your program builds cleanly. Splint writes to stdout a list of stylistic flaws that it finds in your source code. Some of Splint's flaw messages may be a bit cryptic; feel free to ask your preceptor about them as the need arises.

Assuming that you have configured your computing environment as described in the document entitled "A Minimal COS 217 Computing Environment" (from the first precept), using Splint is simple. At the bash prompt, execute the command:

splint sourcecodefiles

For example, to use Splint for this assignment, you would execute these two commands:

splint teststr.c stra.c
splint teststr.c strp.c

You should critique your code using Splint before you submit. Using Splint on your code might improve its quality, and so might result in higher grades.

If you are interested in learning more about Splint, see www.splint.org.