Princeton University
COS 217: Introduction to Programming Systems

Purpose

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 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 MyString module that contains versions of the most commonly used standard string functions. Specifically, your MyString module should contain these functions, each of which behaves the same as a corresponding standard C function:

MyString Function	Standard C Function
MyString_length()	strlen()
MyString_copy()	strcpy()
MyString_ncopy()	strncpy()
MyString_concat()	strcat()
MyString_nconcat()	strncat()
MyString_compare()	strcmp()
MyString_ncompare()	strncmp()
MyString_search()	strstr()

The Details

You should use "design by contract." Each function comment should describe that function's "checked runtime errors." Each function definition should call the assert() macro to enforce those checked runtime errors. (In that way your MyString functions should differ from the standard string functions.) Specifically, each function definition should call assert() to make sure that none of its pointer/array formal parameters is NULL.

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

1. Is it possible for MyString_copy(), MyString_ncopy(), MyString_concat(), or MyString_nconcat() to call assert() to verify that the specified destination memory area is large enough? Explain.
2. Is it possible for MyString_ncopy(), MyString_nconcat(), or MyString_ncompare() to call assert() to verify that the specified length parameter is non-negative? Explain.

You should define the MyString module's interface in a file named mystring.h. You may use either array or pointer notation in the interface.

You should define two implementations of your MyString module. The first implementation should reside in a file named mystringa.c. It should contain definitions of your MyString functions that use array notation, and not pointer notation. For example, in mystringa.c you might define the MyString_length() function like this:

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

(As you may know, 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." Several of the standard string functions use type size_t, and so several of your functions should use it too.)

The second implementation should reside in a file named mystringp.c. It should contain definitions of your MyString functions that use pointer notation, and not array notation. For example, in mystringp.c you might define the MyString_length() function like this:

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

We encourage you to define the functions in mystringp.c more efficiently, by moving beyond a simple translation of "a[i]" to "*(a + i)". For example:

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

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

Pay special attention to boundary cases. In particular, make sure that your functions work when given empty strings as arguments. For example, make sure that the function call MyString_length("") returns 0.

You should 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.

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

Using 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 MyString_length() function like this:

size_t MyString_length(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 MyString_length(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.

Logistics

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

Code that you can use to test your MyString module is available in the file /u/cos217/Assignment2/testmystring.c.

Create a "readme" text file that contains:

• Your name.
• A description of whatever help (if any) you received from others while doing the assignment, and the names of any individuals with whom you collaborated, as prescribed by the course "Policies" web page.
• The answers to the two questions shown above.
• (Optionally) An indication of how much time you spent doing the assignment.
• (Optionally) Your assessment of the assignment: Did it help you to learn? What did it help you to learn? Do you have any suggestions for improvement? Etc.
• (Optionally) Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.

Submit your work electronically on hats via the command:

/u/cos217/bin/i686/submit 2 mystring.h mystringa.c mystringp.c readme

Grading

Program Understandability

(1) Uses a consistent and appropriate indentation scheme. All statements that are nested within a compound, if, switch, while, for, or do...while statement should be indented. Most programmers use either a 3- or 4-space indentation scheme. Note that the xemacs editor can automatically apply a consistent indentation scheme to your program.

(2) Uses descriptive identifiers. The names of variables, constants, structures, types, and functions should indicate their purpose. Remember: C can handle identifiers of any length, and the first 31 characters are significant. We encourage you 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.

(3) Contains carefully worded comments. You should begin each program file with a comment that includes your name, the number of the assignment, and the name of the file. Each function should begin with a comment that describes what the computer does when it executes that function. That comment should explicitly state what (if anything) the computer reads from stdin (or any other stream), and what (if anything) the computer writes to stdout (or any other stream). The function's comment should also describe what the computer does when it executes that function by explicitly referring to the function's parameters and return value. The comment should also explicitly state the function's checked runtime errors. The comment should appear in both the interface (.h) file for the sake of the clients of the function and the implementation (.c) file for the sake of the maintainers of the function.

For example, here is an appropriate way to comment the MyString_length() function:

In file mystring.h:

...

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

...

...

size_t MyString_length(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);
}

...

A Hint: "Const" and the MyString_search Function

The use of the "const" keyword within the MyString_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 MyString_search() also should be of type const char*. Why aren't they of type char*?

Answer

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

char *MyString_search(char *pc1, char *pc2) { ... }

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

const char *pcString1 = "hello";
const char *pcString2 = "lo";
...
... MyString_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 pc1 is of type char*, would generate a warning on the function call. Thus pc1 (and pc2) 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 MyString_search() also should be of type char*. Why isn't the return type const char*?

Answer

Suppose you were to define MyString_search() like this:

const char *MyString_search(const char *pc1, const char *pc2) { ... }

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

char *pcString1 = "hello";
char *pcString2 = "lo";
char *pc;
...
pc = MyString_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 MyString_search() is of type const char*, would generate a warning on the assignment statement. Thus the return type of MyString_search() should be char* and should not be const char*.

Question

Within the definition of MyString_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 *MyString_search(const char *pc1, const char *pc2)
{
   ...
   pc = pc1;
   ...
   /* 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, that inelegant technique often is unavoidable.