A programmer needs to know several things, in order to write reliable programs using C data structures (simple and complex):
1. The exact meaning of "data types of variables and expressions": Type mismatches are usually accompanied by a bug; the code is likely to be either erroneous, or hard-to-modify, or non-portable.
2. What is available in the C library: Libary knowledge is required for correct use of the functions and avoidance of potentially buggy "re-inventing the wheel."
3. The meaning of "properties of data": Starting with the simple distinction between "defined" and "undefined," a grasp of data properties is essential to producing correct programs.
4. Relevant algorithms, including static structures, dynamic structures, and files.
5. How to create re-useable libraries of functions and macros.
Here is what a programmer needs to do to create reliable programs:
1. Follow a design discipline that ensures that data objects and program control structures have clear invariants.
2. Wherever possible, make use of re-useable code (headers and libraries) to avoid "re-inventing."
3. Write in a style that would allow all possible automated checking assistance. Whether or not automated assistance is used, the discipline means fewer reliability problems.
4. As much as possible, preserve the defining properties of data objects, and give warning in the transitional regions of code.
5. Use executable assertions wherever practical.
There is an important relationship between reliability and portability. A successful C program is very likely to be ported to new environments. If it was not written with due regard for portability, reliability problems pop up when the code is ported. Thus, in most cases it is not adequate for the program to work in only one environment.
There is, of course, an important role for code which is intentionally targeted to just one environment. C can be used to replace assembler code for low-level applications where one controls the special resources of a particular machine. What reliability demands in these cases is that the environment-dependent nature of the code be clearly documented, preferably with explicit mention of the environment-dependent features.
To give you now a brief overview of the book's contents, Chapter 1 describes the definition capabilities of C, describing both the preprocessor and the use of typedef. Header files are presented both for the standard library and for the functions that will be presented in the book.
Chapter 2 covers the reliable use of the scalar data types of C: floating-point numbers, integers, and characters. The relevant libaries are discussed, along with suggestions for the handling of errors.
Chapter 3 describes arrays. The use of loop invariants and assertions is described in the context of two algorithms for sorting an array. Strings, and other arrays of characters, are covered, along with the library functions that use them.
Chapter 4 deals with pointers, their types and their properties.
Chapter 5 discusses the standard I/O facilities of the C library, as well as methods for direct control of screen-oriented I/O.
Chapter 6 covers structures, unions, bit-fields, and the use of structures to create a handler for "menu" interactions.
Chapter 7 describes dynamic data structures, the malloc and free functions, and the macros and functions needed to create stacks, queues, double-ended queues ("deques"), and trees.
Chapter 8 covers file I/O of both the "stream" and "record" varieties. Binary I/O, direct access, and "hashed" files are used to implement a simple database.
An appendix summarizes the reliability rules presented in the text, along with notes on the state of the ANSI C draft.
One consistent focus of this book is precision of speaking and of documentation. To this end, I have made use of several abbreviations borrowed from various sources. Each will be explained in its proper context, but it will be useful to provide a brief preview here:
nul means the char value '\0'
{lo:hi} means the range of values from lo to hi
a[i:j] means the subarray a[i] through a[j]
a[*] means the entire array a (for emphasis)
p[*] means the array to which pointer p provides access
a[*] => sorted means that a[*] is now sorted
a[*] : string means that a[*] must be a string
None of these notations are part of C syntax. They just provide a concise way to describe the behavior of a program. You could replace each of them with a verbal phrase, if you prefer.
In this book, the use of the word "reliable" as applied to programs is meant to have very practical connotations: Reliable programs produce no surprises. The actual behavior of the code is readily determined by a reading of the program. The program does what it appears to do. This is easy to say, and not quite so easy to do.
Our quest for reliable C programs begins with the definition capabilities of C, which is the subject of the first chapter.