Chapter 14: What's Next?

This last handout contains a brief list of the significant topics in C which we have not covered, and which you'll want to investigate further if you want to know all of C.

Types and Declarations

We have not talked about the void, short int, and long double types. void is a type with no values, used as a placeholder to indicate functions that do not return values or that accept no arguments, and in the ``generic'' pointer type void * that can point to anything. short int is an integer type that might use less space than a plain int; long double is a floating-point type that might have even more range or precision than plain double.

The char type and the various sizes of int also have ``unsigned'' versions, which are declared using the keyword unsigned. Unsigned types cannot hold negative values but have guaranteed properties on overflow. (Whether a plain char is signed or unsigned is implementation-defined; you can use the keyword signed to force a character type to contain signed characters.) Unsigned types are also useful when manipulating individual bits and bytes, when ``sign extension'' might otherwise be a problem.

Two additional type qualifiers const and volatile allow you to declare variables (or pointers to data) which you promise not to change, or which might change in unexpected ways behind the program's back.

There are user-defined structure and union types. A structure or struct is a ``record'' consisting of one or more values of one or more types concreted together into one entity which can be manipulated as a whole. A union is a type which, at any one time, can hold a value from one of a specified set of types.

There are user-defined enumeration types (``enum'') which are like integers but which always contain values from some fixed, predefined set, and for which the values are referred to by name instead of by number.

Pointers can point to functions as well as to data types.

Types can be arbitrarily complicated, when you start using multiple levels of pointers, arrays, functions, structures, and/or unions. Eventually, it's important to understand the concept of a declarator: in the declaration

        int i, *ip, *fpi();

we have the base type int and three declarators i, *ip, and *fpi(). The declarator gives the name of a variable (or function) and also indicates whether it is a simple variable or a pointer, array, function, or some more elaborate combination (array of pointers, function returning pointer, etc.). In the example, i is declared to be a plain int, ip is declared to be a pointer to int, and fpi is declared to be a function returning pointer to int. (Complicated declarators may also contain parentheses for grouping, since there's a precedence hierarchy in declarators as well as expressions: [] for arrays and () for functions have higher precedence than * for pointers.)

We have not said much about pointers to pointers, or arrays of arrays (i.e. multidimensional arrays), or the ramifications of array/pointer equivalence on multidimensional arrays. (In particular, a reference to an array of arrays does not generate a pointer to a pointer; it generates a pointer to an array. You cannot pass a multidimensional array to a function which accepts pointers to pointers.)

Variables can be declared with a hint that they be placed in high-speed CPU registers, for efficiency. (These hints are rarely needed or used today, because modern compilers do a good job of register allocation by themselves, without hints.)

A mechanism called typedef allows you to define user-defined aliases (i.e. new and perhaps more-convenient names) for other types.

Operators

The bitwise operators &, |, ^, and ~ operate on integers thought of as binary numbers or strings of bits. The & operator is bitwise AND, the | operator is bitwise OR, the ^ operator is bitwise exclusive-OR (XOR), and the ~ operator is a bitwise negation or complement. (&, |, and ^ are ``binary'' in that they take two operands; ~ is unary.) These operators let you work with the individual bits of a variable; one common use is to treat an integer as a set of single-bit flags. You might define the 3rd (2**2) bit as the ``verbose'' flag bit by defining

        #define VERBOSE 4

Then you can ``turn the verbose bit on'' in an integer variable flags by executing

        flags = flags | VERBOSE;

or

        flags |= VERBOSE;

and turn it off with

        flags = flags & ~VERBOSE;

or

        flags &= ~VERBOSE;

and test whether it's set with

        if(flags & VERBOSE)

The left-shift and right-shift operators << and >> let you shift an integer left or right by some number of bit positions; for example, value << 2 shifts value left by two bits.

The ?: or conditional operator (also called the ``ternary operator'') essentially lets you embed an if/then statement in an expression. The assignment

        a = expr ? b : c;

is roughly equivalent to

        if(expr)

               a = b;

        else    a = c;

Since you can use ?: anywhere in an expression, it can do things that if/then can't, or that would be cumbersome with if/then. For example, the function call

        f(a, b, c ? d : e);

is roughly equivalent to

        if(c)

               f(a, b, d);

        else    f(a, b, e);

(Exercise: what would the call

        g(a, b, c ? d : e, h ? i : j, k);

be equivalent to?)

The comma operator lets you put two separate expressions where one is required; the expressions are executed one after the other. The most common use for comma operators is when you want multiple variables controlling a for loop, for example:

        for(i = 0, j = 10; i < j; i++, j--)

A cast operator allows you to explicitly force conversion of a value from one type to another. A cast consists of a type name in parentheses. For example, you could convert an int to a double by typing

        int i = 10;

        double d;

        d = (double)i;

(In this case, though, the cast is redundant, since this is a conversion that C would have performed for you automatically, i.e. if you'd just said d = i .) You use explicit casts in those circumstances where C does not do a needed conversion automatically. One example is division: if you're dividing two integers and you want a floating-point result, you must explicitly force at least one of the operands to floating-point, otherwise C will perform an integer division and will discard the remainder. The code

        int i = 1, j = 2;

        double d = i / j;

will set d to 0, but

        d = (double)i / j;

will set d to 0.5. You can also ``cast to void'' to explicitly indicate that you're ignoring a function's return value, as in

        (void)fclose(fp);

or

        (void)printf("Hello, world!\n");

(Usually, it's a bad idea to ignore return values, but in some cases it's essentially inevitable, and the (void) cast keeps some compilers from issuing warnings every time you ignore a value.)

There's a precise, mildly elaborate set of rules which C uses for converting values automatically, in the absence of explicit casts.

The . and -> operators let you access the members (components) of structures and unions.

Statements

The switch statement allows you to jump to one of a number of numeric case labels depending on the value of an expression; it's more convenient than a long if/else chain. (However, you can use switch only when the expression is integral and all of the case labels are compile-time constants.)

The do/while loop is a loop that tests its controlling expression at the bottom of the loop, so that the body of the loop always executes once even if the condition is initially false. (C's do/while loop is therefore like Pascal's repeat/until loop, while C's while loop is like Pascal's while/do loop.)

Finally, when you really need to write ``spaghetti code,'' C does have the all-purpose goto statement, and labels to go to.

Functions

Functions can't return arrays, and it's tricky to write a function as if it returns an array (perhaps by simulating the array with a pointer) because you have to be careful about allocating the memory that the returned pointer points to.

The functions we've written have all accepted a well-defined, fixed number of arguments. printf accepts a variable number of arguments (depending on how many % signs there are in the format string) but we haven't seen how to declare and write functions that do this.

C Preprocessor

If you're careful, it's possible (and can be useful) to use #include within a header file, so that you end up with ``nested header files.''

It's possible to use #define to define ``function-like'' macros that accept arguments; the expansion of the macro can therefore depend on the arguments it's ``invoked'' with.

Two special preprocessing operators # and ## let you control the expansion of macro arguments in fancier ways.

The preprocessor directive #if lets you conditionally include (or, with #else, conditionally not include) a section of code depending on some arbitrary compile-time expression. (#if can also do the same macro-definedness tests as #ifdef and #ifndef, because the expression can use a defined() operator.)

Other preprocessing directives are #elif, #error, #line, and #pragma.

There are a few predefined preprocessor macros, some required by the C standard, others perhaps defined by particular compilation environments. These are useful for conditional compilation (#ifdef, #ifndef).

Standard Library Functions

C's standard library contains many features and functions which we haven't seen.

We've seen many of printf's formatting capabilities, but not all. Besides format specifier characters for a few types we haven't seen, you can also control the width, precision, justification (left or right) and a few other attributes of printf's format conversions. (In their full complexity, printf formats are about as elaborate and powerful as FORTRAN format statements.)

A scanf function lets you do ``formatted input'' analogous to printf's formatted output. scanf reads from the standard input; a variant fscanf reads from a specified file pointer.

The sprintf and sscanf functions let you ``print'' and ``read'' to and from in-memory strings instead of files. We've seen that atoi lets you convert a numeric string into an integer; the inverse operation can be performed with sprintf:

        int i = 10;

        char str[10];

        sprintf(str, "%d", i);

We've used printf and fprintf to write formatted output, and getchar, getc, putchar, and putc to read and write characters. There are also functions gets, fgets, puts, and fputs for reading and writing lines (though we rarely need these, especially if we're using our own getline and maybe fgetline), and also fread and fwrite for reading or writing arbitrary numbers of characters.

It's possible to ``un-read'' a character, that is, to push it back on an input stream, with ungetc. (This is useful if you accidentally read one character too far, and would prefer that some other part of your program read that character instead.)

You can use the ftell, fseek, and rewind functions to jump around in files, performing random access (as opposed to sequential) I/O.

The feof and ferror functions will tell you whether you got EOF due to an actual end-of-file condition or due to a read error of some sort. You can clear errors and end-of-file conditions with clearerr.

You can open files in ``binary'' mode, or for simultaneous reading and writing. (These options involve extra characters appended to fopen's mode string: b for binary, + for read/write.)

There are several more string functions in . A second set of string functions strncpy, strncat, and strncmp all accept a third argument telling them to stop after n characters if they haven't found the \0 marking the end of the string. A third set of ``mem'' functions, including memcpy and memcmp, operate on blocks of memory which aren't necessarily strings and where \0 is not treated as a terminator. The strchr and strrchr functions find characters in strings. There is a motley collection of ``span'' and ``scan'' functions, strspn, strcspn, and strpbrk, for searching out or skipping over sequences of characters all drawn from a specified set of characters. The strtok function aids in breaking up a string into words or ``tokens,'' much like our own getwords function.

The header file contains several functions which let you classify and manipulate characters: check for letters or digits, convert between upper- and lower-case, etc.

A host of mathematical functions are defined in the header file . (As we've mentioned, besides including , you may on some Unix systems have to ask for a special library containing the math functions while compiling/linking.)

There's a random-number generator, rand, and a way to ``seed'' it, srand. rand returns integers from 0 up to RAND_MAX (where RAND_MAX is a constant #defined in ). One way of getting random integers from 1 to n is to call

        (int)(rand() / (RAND_MAX + 1.0) * n) + 1

Another way is

        rand() / (RAND_MAX / n + 1) + 1

It seems like it would be simpler to just say

        rand() % n + 1

but this method is imperfect (or rather, it's imperfect if n is a power of two and your system's implementation of rand() is imperfect, as all too many of them are).

Several functions let you interact with the operating system under which your program is running. The exit function returns control to the operating system immediately, terminating your program and returning an ``exit status.'' The getenv function allows you to read your operating system's or process's ``environment variables'' (if any). The system function allows you to invoke an operating-system command (i.e. another program) from within your program.

The qsort function allows you to sort an array (of any type); you supply a comparison function (via a function pointer) which knows how to compare two array elements, and qsort does the rest. The bsearch function allows you to search for elements in sorted arrays; it, too, operates in terms of a caller-supplied comparison function.

Several functions--time, asctime, gmtime, localtime, asctime, mktime, difftime, and strftime--allow you to determine the current date and time, print dates and times, and perform other date/time manipulations. For example, to print today's date in a program, you can write

        #include 

        time_t now;

        now = time((time_t *)NULL);

        printf("It's %.24s", ctime(&now));

The header file lets you manipulate variable-length function argument lists (such as the ones printf is called with). Additional members of the printf family of functions let you write your own functions which accept printf-like format specifiers and variable numbers of arguments but call on the standard printf to do most of the work.

There are facilities for dealing with multibyte and ``wide'' characters and strings, for use with multinational character sets.

Chapter 13: Reading the Command Line

We've mentioned several times that a program is rarely useful if it does exactly the same thing every time you run it. Another way of giving a program some variable input to work on is by invoking it with command line arguments.

(We should probably admit that command line user interfaces are a bit old-fashioned, and currently somewhat out of favor. If you've used Unix or MS-DOS, you know what a command line is, but if your experience is confined to the Macintosh or Microsoft Windows or some other Graphical User Interface, you may never have seen a command line. In fact, if you're learning C on a Mac or under Windows, it can be tricky to give your program a command line at all. Think C for the Macintosh provides a way; I'm not sure about other compilers. If your compilation environment doesn't provide an easy way of simulating an old-fashioned command line, you may skip this chapter.)

C's model of the command line is that it consists of a sequence of words, typically separated by whitespace. Your main program can receive these words as an array of strings, one word per string. In fact, the C run-time startup code is always willing to pass you this array, and all you have to do to receive it is to declare main as accepting two parameters, like this:

        int main(int argc, char *argv[])

        {

        ...

        }

When main is called, argc will be a count of the number of command-line arguments, and argv will be an array (``vector'') of the arguments themselves. Since each word is a string which is represented as a pointer-to-char, argv is an array-of-pointers-to-char. Since we are not defining the argv array, but merely declaring a parameter which references an array somewhere else (namely, in main's caller, the run-time startup code), we do not have to supply an array dimension for argv. (Actually, since functions never receive arrays as parameters in C, argv can also be thought of as a pointer-to-pointer-to-char, or char **. But multidimensional arrays and pointers to pointers can be confusing, and we haven't covered them, so we'll talk about argv as if it were an array.) (Also, there's nothing magic about the names argc and argv. You can give main's two parameters any names you like, as long as they have the appropriate types. The names argc and argv are traditional.)

The first program to write when playing with argc and argv is one which simply prints its arguments:

#include 

main(int argc, char *argv[])

{

int i;

for(i = 0; i < argc; i++)

        printf("arg %d: %s\n", i, argv[i]);

return 0;

}

(This program is essentially the Unix or MS-DOS echo command.)

If you run this program, you'll discover that the set of ``words'' making up the command line includes the command you typed to invoke your program (that is, the name of your program). In other words, argv[0] typically points to the name of your program, and argv[1] is the first argument.

There are no hard-and-fast rules for how a program should interpret its command line. There is one set of conventions for Unix, another for MS-DOS, another for VMS. Typically you'll loop over the arguments, perhaps treating some as option flags and others as actual arguments (input files, etc.), interpreting or acting on each one. Since each argument is a string, you'll have to use strcmp or the like to match arguments against any patterns you might be looking for. Remember that argc contains the number of words on the command line, and that argv[0] is the command name, so if argc is 1, there are no arguments to inspect. (You'll never want to look at argv[i], for i >= argc, because it will be a null or invalid pointer.)

As another example, also illustrating fopen and the file I/O techniques of the previous chapter, here is a program which copies one or more input files to its standard output. Since ``standard output'' is usually the screen by default, this is therefore a useful program for displaying files. (It's analogous to the obscurely-named Unix cat command, and to the MS-DOS type command.) You might also want to compare this program to the character-copying program of section 6.2.

#include 

main(int argc, char *argv[])

{

int i;

FILE *fp;

int c;

for(i = 1; i < argc; i++)

        {

        fp = fopen(argv[i], "r");

        if(fp == NULL)

               {

               fprintf(stderr, "cat: can't open %s\n", argv[i]);

               continue;

               }

        while((c = getc(fp)) != EOF)

               putchar(c);

        fclose(fp);

        }

return 0;

}

As a historical note, the Unix cat program is so named because it can be used to concatenate two files together, like this:

        cat a b > c

This illustrates why it's a good idea to print error messages to stderr, so that they don't get redirected. The ``can't open file'' message in this example also includes the name of the program as well as the name of the file.

Yet another piece of information which it's usually appropriate to include in error messages is the reason why the operation failed, if known. For operating system problems, such as inability to open a file, a code indicating the error is often stored in the global variable errno. The standard library function strerror will convert an errno value to a human-readable error message string. Therefore, an even more informative error message printout would be

        fp = fopen(argv[i], "r");

        if(fp == NULL)

               fprintf(stderr, "cat: can't open %s: %s\n",

                               argv[i], strerror(errno));

If you use code like this, you can #include to get the declaration for errno, and to get the declaration for strerror().

Chapter 12: Input and Output

So far, we've been calling printf to print formatted output to the ``standard output'' (wherever that is). We've also been calling getchar to read single characters from the ``standard input,'' and putchar to write single characters to the standard output. ``Standard input'' and ``standard output'' are two predefined I/O streams which are implicitly available to us. In this chapter we'll learn how to take control of input and output by opening our own streams, perhaps connected to data files, which we can read from and write to.

12.1 File Pointers and fopen

How will we specify that we want to access a particular data file? It would theoretically be possible to mention the name of a file each time it was desired to read from or write to it. But such an approach would have a number of drawbacks. Instead, the usual approach (and the one taken in C's stdio library) is that you mention the name of the file once, at the time you open it. Thereafter, you use some little token--in this case, the file pointer--which keeps track (both for your sake and the library's) of which file you're talking about. Whenever you want to read from or write to one of the files you're working with, you identify that file by using its file pointer (that is, the file pointer you obtained when you opened the file). As we'll see, you store file pointers in variables just as you store any other data you manipulate, so it is possible to have several files open, as long as you use distinct variables to store the file pointers.

You declare a variable to store a file pointer like this:

        FILE *fp;

The type FILE is predefined for you by . It is a data structure which holds the information the standard I/O library needs to keep track of the file for you. For historical reasons, you declare a variable which is a pointer to this FILE type. The name of the variable can (as for any variable) be anything you choose; it is traditional to use the letters fp in the variable name (since we're talking about a file pointer). If you were reading from two files at once you'd probably use two file pointers:

        FILE *fp1, *fp2;

If you were reading from one file and writing to another you might declare and input file pointer and an output file pointer:

        FILE *ifp, *ofp;

Like any pointer variable, a file pointer isn't any good until it's initialized to point to something. (Actually, no variable of any type is much good until you've initialized it.) To actually open a file, and receive the ``token'' which you'll store in your file pointer variable, you call fopen. fopen accepts a file name (as a string) and a mode value indicating among other things whether you intend to read or write this file. (The mode variable is also a string.) To open the file input.dat for reading you might call

        ifp = fopen("input.dat", "r");

The mode string "r" indicates reading. Mode "w" indicates writing, so we could open output.dat for output like this:

        ofp = fopen("output.dat", "w");

The other values for the mode string are less frequently used. The third major mode is "a" for append. (If you use "w" to write to a file which already exists, its old contents will be discarded.) You may also add a + character to the mode string to indicate that you want to both read and write, or a b character to indicate that you want to do ``binary'' (as opposed to text) I/O.

One thing to beware of when opening files is that it's an operation which may fail. The requested file might not exist, or it might be protected against reading or writing. (These possibilities ought to be obvious, but it's easy to forget them.) fopen returns a null pointer if it can't open the requested file, and it's important to check for this case before going off and using fopen's return value as a file pointer. Every call to fopen will typically be followed with a test, like this:

        ifp = fopen("input.dat", "r");

        if(ifp == NULL)

               {

               printf("can't open file\n");

               exit or return

               }

If fopen returns a null pointer, and you store it in your file pointer variable and go off and try to do I/O with it, your program will typically crash.

It's common to collapse the call to fopen and the assignment in with the test:

        if((ifp = fopen("input.dat", "r")) == NULL)

               {

               printf("can't open file\n");

               exit or return

               }

You don't have to write these ``collapsed'' tests if you're not comfortable with them, but you'll see them in other people's code, so you should be able to read them.

12.2 I/O with File Pointers

For each of the I/O library functions we've been using so far, there's a companion function which accepts an additional file pointer argument telling it where to read from or write to. The companion function to printf is fprintf, and the file pointer argument comes first. To print a string to the output.dat file we opened in the previous section, we might call

        fprintf(ofp, "Hello, world!\n");

The companion function to getchar is getc, and the file pointer is its only argument. To read a character from the input.dat file we opened in the previous section, we might call

        int c;

        c = getc(ifp);

The companion function to putchar is putc, and the file pointer argument comes last. To write a character to output.dat, we could call

        putc(c, ofp);

Our own getline function calls getchar and so always reads the standard input. We could write a companion fgetline function which reads from an arbitrary file pointer:

#include 

/* Read one line from fp, */

/* copying it to line array (but no more than max chars). */

/* Does not place terminating \n in line array. */

/* Returns line length, or 0 for empty line, or EOF for end-of-file. */

int fgetline(FILE *fp, char line[], int max)

{

int nch = 0;

int c;

max = max - 1;                 /* leave room for '\0' */

while((c = getc(fp)) != EOF)

        {

        if(c == '\n')

               break;

        if(nch < max)

               {

               line[nch] = c;

               nch = nch + 1;

               }

        }

if(c == EOF && nch == 0)

        return EOF;

line[nch] = '\0';

return nch;

}

Now we could read one line from ifp by calling

        char line[MAXLINE];

        ...

        fgetline(ifp, line, MAXLINE);

12.3 Predefined Streams

Besides the file pointers which we explicitly open by calling fopen, there are also three predefined streams. stdin is a constant file pointer corresponding to standard input, and stdout is a constant file pointer corresponding to standard output. Both of these can be used anywhere a file pointer is called for; for example, getchar() is the same as getc(stdin) and putchar(c) is the same as putc(c, stdout). The third predefined stream is stderr. Like stdout, stderr is typically connected to the screen by default. The difference is that stderr is not redirected when the standard output is redirected. For example, under Unix or MS-DOS, when you invoke

        program > filename

anything printed to stdout is redirected to the file filename, but anything printed to stderr still goes to the screen. The intent behind stderr is that it is the ``standard error output''; error messages printed to it will not disappear into an output file. For example, a more realistic way to print an error message when a file can't be opened would be

        if((ifp = fopen(filename, "r")) == NULL)

               {

               fprintf(stderr, "can't open file %s\n", filename);

               exit or return

               }

where filename is a string variable indicating the file name to be opened. Not only is the error message printed to stderr, but it is also more informative in that it mentions the name of the file that couldn't be opened. (We'll see another example in the next chapter.)

12.4 Closing Files

Although you can open multiple files, there's a limit to how many you can have open at once. If your program will open many files in succession, you'll want to close each one as you're done with it; otherwise the standard I/O library could run out of the resources it uses to keep track of open files. Closing a file simply involves calling fclose with the file pointer as its argument:

        fclose(fp);

Calling fclose arranges that (if the file was open for output) any last, buffered output is finally written to the file, and that those resources used by the operating system (and the C library) for this file are released. If you forget to close a file, it will be closed automatically when the program exits.

12.5 Example: Reading a Data File

Suppose you had a data file consisting of rows and columns of numbers:

        1       2       34

        5       6       78

        9       10      112

Suppose you wanted to read these numbers into an array. (Actually, the array will be an array of arrays, or a ``multidimensional'' array; see section 4.1.2.) We can write code to do this by putting together several pieces: the fgetline function we just showed, and the getwords function from chapter 10. Assuming that the data file is named input.dat, the code would look like this:

#define MAXLINE 100

#define MAXROWS 10

#define MAXCOLS 10

int array[MAXROWS][MAXCOLS];

char *filename = "input.dat";

FILE *ifp;

char line[MAXLINE];

char *words[MAXCOLS];

int nrows = 0;

int n;

int i;

ifp = fopen(filename, "r");

if(ifp == NULL)

        {

        fprintf(stderr, "can't open %s\n", filename);

        exit(EXIT_FAILURE);

        }

while(fgetline(ifp, line, MAXLINE) != EOF)

        {

        if(nrows >= MAXROWS)

               {

               fprintf(stderr, "too many rows\n");

               exit(EXIT_FAILURE);

               }

        n = getwords(line, words, MAXCOLS);

        for(i = 0; i < n; i++)

               array[nrows][i] = atoi(words[i]);

        nrows++;

        }

Each trip through the loop reads one line from the file, using fgetline. Each line is broken up into ``words'' using getwords; each ``word'' is actually one number. The numbers are however still represented as strings, so each one is converted to an int by calling atoi before being stored in the array. The code checks for two different error conditions (failure to open the input file, and too many lines in the input file) and if one of these conditions occurs, it prints an error message, and exits. The exit function is a Standard library function which terminates your program. It is declared in , and accepts one argument, which will be the exit status of the program. EXIT_FAILURE is a code, also defined by , which indicates that the program failed. Success is indicated by a code of EXIT_SUCCESS, or simply 0. (These values can also be returned from main(); calling exit with a particular status value is essentially equivalent to returning that same status value from main.)

Chapter 11: Memory Allocation

In this chapter, we'll meet malloc, C's dynamic memory allocation function, and we'll cover dynamic memory allocation in some detail.

As we begin doing dynamic memory allocation, we'll begin to see (if we haven't seen it already) what pointers can really be good for. Many of the pointer examples in the previous chapter (those which used pointers to access arrays) didn't do all that much for us that we couldn't have done using arrays. However, when we begin doing dynamic memory allocation, pointers are the only way to go, because what malloc returns is a pointer to the memory it gives us. (Due to the equivalence between pointers and arrays, though, we will still be able to think of dynamically allocated regions of storage as if they were arrays, and even to use array-like subscripting notation on them.)

You have to be careful with dynamic memory allocation. malloc operates at a pretty ``low level''; you will often find yourself having to do a certain amount of work to manage the memory it gives you. If you don't keep accurate track of the memory which malloc has given you, and the pointers of yours which point to it, it's all too easy to accidentally use a pointer which points ``nowhere'', with generally unpleasant results. (The basic problem is that if you assign a value to the location pointed to by a pointer:

        *p = 0;

and if the pointer p points ``nowhere'', well actually it can be construed to point somewhere, just not where you wanted it to, and that ``somewhere'' is where the 0 gets written. If the ``somewhere'' is memory which is in use by some other part of your program, or even worse, if the operating system has not protected itself from you and ``somewhere'' is in fact in use by the operating system, things could get ugly.)

11.1 Allocating Memory with malloc

[This section corresponds to parts of K&R Secs. 5.4, 5.6, 6.5, and 7.8.5]

A problem with many simple programs, including in particular little teaching programs such as we've been writing so far, is that they tend to use fixed-size arrays which may or may not be big enough. We have an array of 100 ints for the numbers which the user enters and wishes to find the average of--what if the user enters 101 numbers? We have an array of 100 chars which we pass to getline to receive the user's input--what if the user types a line of 200 characters? If we're lucky, the relevant parts of the program check how much of an array they've used, and print an error message or otherwise gracefully abort before overflowing the array. If we're not so lucky, a program may sail off the end of an array, overwriting other data and behaving quite badly. In either case, the user doesn't get his job done. How can we avoid the restrictions of fixed-size arrays?

The answers all involve the standard library function malloc. Very simply, malloc returns a pointer to n bytes of memory which we can do anything we want to with. If we didn't want to read a line of input into a fixed-size array, we could use malloc, instead. Here's the first step:

        #include 

        char *line;

        int linelen = 100;

        line = malloc(linelen);

        /* incomplete -- malloc's return value not checked */

        getline(line, linelen);

malloc is declared in , so we #include that header in any program that calls malloc. A ``byte'' in C is, by definition, an amount of storage suitable for storing one character, so the above invocation of malloc gives us exactly as many chars as we ask for. We could illustrate the resulting pointer like this:

The 100 bytes of memory (not all of which are shown) pointed to by line are those allocated by malloc. (They are brand-new memory, conceptually a bit different from the memory which the compiler arranges to have allocated automatically for our conventional variables. The 100 boxes in the figure don't have a name next to them, because they're not storage for a variable we've declared.)

As a second example, we might have occasion to allocate a piece of memory, and to copy a string into it with strcpy:

        char *p = malloc(15);

        /* incomplete -- malloc's return value not checked */

        strcpy(p, "Hello, world!");

When copying strings, remember that all strings have a terminating \0 character. If you use strlen to count the characters in a string for you, that count will not include the trailing \0, so you must add one before calling malloc:

        char *somestring, *copy;

        ...

        copy = malloc(strlen(somestring) + 1);                /* +1 for \0 */

        /* incomplete -- malloc's return value not checked */

        strcpy(copy, somestring);

What if we're not allocating characters, but integers? If we want to allocate 100 ints, how many bytes is that? If we know how big ints are on our machine (i.e. depending on whether we're using a 16- or 32-bit machine) we could try to compute it ourselves, but it's much safer and more portable to let C compute it for us. C has a sizeof operator, which computes the size, in bytes, of a variable or type. It's just what we need when calling malloc. To allocate space for 100 ints, we could call

        int *ip = malloc(100 * sizeof(int));

The use of the sizeof operator tends to look like a function call, but it's really an operator, and it does its work at compile time.

Since we can use array indexing syntax on pointers, we can treat a pointer variable after a call to malloc almost exactly as if it were an array. In particular, after the above call to malloc initializes ip to point at storage for 100 ints, we can access ip[0], ip[1], ... up to ip[99]. This way, we can get the effect of an array even if we don't know until run time how big the ``array'' should be. (In a later section we'll see how we might deal with the case where we're not even sure at the point we begin using it how big an ``array'' will eventually have to be.)

Our examples so far have all had a significant omission: they have not checked malloc's return value. Obviously, no real computer has an infinite amount of memory available, so there is no guarantee that malloc will be able to give us as much memory as we ask for. If we call malloc(100000000), or if we call malloc(10) 10,000,000 times, we're probably going to run out of memory.

When malloc is unable to allocate the requested memory, it returns a null pointer. A null pointer, remember, points definitively nowhere. It's a ``not a pointer'' marker; it's not a pointer you can use. (As we said in section 9.4, a null pointer can be used as a failure return from a function that returns pointers, and malloc is a perfect example.) Therefore, whenever you call malloc, it's vital to check the returned pointer before using it! If you call malloc, and it returns a null pointer, and you go off and use that null pointer as if it pointed somewhere, your program probably won't last long. Instead, a program should immediately check for a null pointer, and if it receives one, it should at the very least print an error message and exit, or perhaps figure out some way of proceeding without the memory it asked for. But it cannot go on to use the null pointer it got back from malloc in any way, because that null pointer by definition points nowhere. (``It cannot use a null pointer in any way'' means that the program cannot use the * or [] operators on such a pointer value, or pass it to any function that expects a valid pointer.)

A call to malloc, with an error check, typically looks something like this:

        int *ip = malloc(100 * sizeof(int));

        if(ip == NULL)

               {

               printf("out of memory\n");

               exit or return

               }

After printing the error message, this code should return to its caller, or exit from the program entirely; it cannot proceed with the code that would have used ip.

Of course, in our examples so far, we've still limited ourselves to ``fixed size'' regions of memory, because we've been calling malloc with fixed arguments like 10 or 100. (Our call to getline is still limited to 100-character lines, or whatever number we set the linelen variable to; our ip variable still points at only 100 ints.) However, since the sizes are now values which can in principle be determined at run-time, we've at least moved beyond having to recompile the program (with a bigger array) to accommodate longer lines, and with a little more work, we could arrange that the ``arrays'' automatically grew to be as large as required. (For example, we could write something like getline which could read the longest input line actually seen.) We'll begin to explore this possibility in a later section.

11.2 Freeing Memory

Memory allocated with malloc lasts as long as you want it to. It does not automatically disappear when a function returns, as automatic-duration variables do, but it does not have to remain for the entire duration of your program, either. Just as you can use malloc to control exactly when and how much memory you allocate, you can also control exactly when you deallocate it.

In fact, many programs use memory on a transient basis. They allocate some memory, use it for a while, but then reach a point where they don't need that particular piece any more. Because memory is not inexhaustible, it's a good idea to deallocate (that is, release or free) memory you're no longer using.

Dynamically allocated memory is deallocated with the free function. If p contains a pointer previously returned by malloc, you can call

        free(p);

which will ``give the memory back'' to the stock of memory (sometimes called the ``arena'' or ``pool'') from which malloc requests are satisfied. Calling free is sort of the ultimate in recycling: it costs you almost nothing, and the memory you give back is immediately usable by other parts of your program. (Theoretically, it may even be usable by other programs.)

(Freeing unused memory is a good idea, but it's not mandatory. When your program exits, any memory which it has allocated but not freed should be automatically released. If your computer were to somehow ``lose'' memory just because your program forgot to free it, that would indicate a problem or deficiency in your operating system.)

Naturally, once you've freed some memory you must remember not to use it any more. After calling

        free(p);

it is probably the case that p still points at the same memory. However, since we've given it back, it's now ``available,'' and a later call to malloc might give that memory to some other part of your program. If the variable p is a global variable or will otherwise stick around for a while, one good way to record the fact that it's not to be used any more would be to set it to a null pointer:

        free(p);

        p = NULL;

Now we don't even have the pointer to the freed memory any more, and (as long as we check to see that p is non-NULL before using it), we won't misuse any memory via the pointer p.

When thinking about malloc, free, and dynamically-allocated memory in general, remember again the distinction between a pointer and what it points to. If you call malloc to allocate some memory, and store the pointer which malloc gives you in a local pointer variable, what happens when the function containing the local pointer variable returns? If the local pointer variable has automatic duration (which is the default, unless the variable is declared static), it will disappear when the function returns. But for the pointer variable to disappear says nothing about the memory pointed to! That memory still exists and, as far as malloc and free are concerned, is still allocated. The only thing that has disappeared is the pointer variable you had which pointed at the allocated memory. (Furthermore, if it contained the only copy of the pointer you had, once it disappears, you'll have no way of freeing the memory, and no way of using it, either. Using memory and freeing memory both require that you have at least one pointer to the memory!)

11.3 Reallocating Memory Blocks

Sometimes you're not sure at first how much memory you'll need. For example, if you need to store a series of items you read from the user, and if the only way to know how many there are is to read them until the user types some ``end'' signal, you'll have no way of knowing, as you begin reading and storing the first few, how many you'll have seen by the time you do see that ``end'' marker. You might want to allocate room for, say, 100 items, and if the user enters a 101st item before entering the ``end'' marker, you might wish for a way to say ``uh, malloc, remember those 100 items I asked for? Could I change my mind and have 200 instead?''

In fact, you can do exactly this, with the realloc function. You hand realloc an old pointer (such as you received from an initial call to malloc) and a new size, and realloc does what it can to give you a chunk of memory big enough to hold the new size. For example, if we wanted the ip variable from an earlier example to point at 200 ints instead of 100, we could try calling

        ip = realloc(ip, 200 * sizeof(int));

Since you always want each block of dynamically-allocated memory to be contiguous (so that you can treat it as if it were an array), you and realloc have to worry about the case where realloc can't make the old block of memory bigger ``in place,'' but rather has to relocate it elsewhere in order to find enough contiguous space for the new requested size. realloc does this by returning a new pointer. If realloc was able to make the old block of memory bigger, it returns the same pointer. If realloc has to go elsewhere to get enough contiguous memory, it returns a pointer to the new memory, after copying your old data there. (In this case, after it makes the copy, it frees the old block.) Finally, if realloc can't find enough memory to satisfy the new request at all, it returns a null pointer. Therefore, you usually don't want to overwrite your old pointer with realloc's return value until you've tested it to make sure it's not a null pointer. You might use code like this:

        int *newp;

        newp = realloc(ip, 200 * sizeof(int));

        if(newp != NULL)

               ip = newp;

        else    {

               printf("out of memory\n");

               /* exit or return */

               /* but ip still points at 100 ints */

               }

If realloc returns something other than a null pointer, it succeeded, and we set ip to what it returned. (We've either set ip to what it used to be or to a new pointer, but in either case, it points to where our data is now.) If realloc returns a null pointer, however, we hang on to our old pointer in ip which still points at our original 100 values.

Putting this all together, here is a piece of code which reads lines of text from the user, treats each line as an integer by calling atoi, and stores each integer in a dynamically-allocated ``array'':

#define MAXLINE 100

char line[MAXLINE];

int *ip;

int nalloc, nitems;

nalloc = 100;

ip = malloc(nalloc * sizeof(int));            /* initial allocation */

if(ip == NULL)

        {

        printf("out of memory\n");

        exit(1);

        }

nitems = 0;

while(getline(line, MAXLINE) != EOF)

        {

        if(nitems >= nalloc)

               {                              /* increase allocation */

               int *newp;

               nalloc += 100;

               newp = realloc(ip, nalloc * sizeof(int));

               if(newp == NULL)

                       {

                       printf("out of memory\n");

                       exit(1);

                       }

               ip = newp;

               }

        ip[nitems++] = atoi(line);

        }

We use two different variables to keep track of the ``array'' pointed to by ip. nalloc is how many elements we've allocated, and nitems is how many of them are in use. Whenever we're about to store another item in the ``array,'' if nitems >= nalloc, the old ``array'' is full, and it's time to call realloc to make it bigger.

Finally, we might ask what the return type of malloc and realloc is, if they are able to return pointers to char or pointers to int or (though we haven't seen it yet) pointers to any other type. The answer is that both of these functions are declared (in ) as returning a type we haven't seen, void * (that is, pointer to void). We haven't really seen type void, either, but what's going on here is that void * is specially defined as a ``generic'' pointer type, which may be used (strictly speaking, assigned to or from) any pointer type.

11.4 Pointer Safety

At the beginning of the previous chapter, we said that the hard thing about pointers is not so much manipulating them as ensuring that the memory they point to is valid. When a pointer doesn't point where you think it does, if you inadvertently access or modify the memory it points to, you can damage other parts of your program, or (in some cases) other programs or the operating system itself!

When we use pointers to simple variables, as in section 10.1, there's not much that can go wrong. When we use pointers into arrays, as in section 10.2, and begin moving the pointers around, we have to be more careful, to ensure that the roving pointers always stay within the bounds of the array(s). When we begin passing pointers to functions, and especially when we begin returning them from functions (as in the strstr function of section 10.4) we have to be more careful still, because the code using the pointer may be far removed from the code which owns or allocated the memory.

One particular problem concerns functions that return pointers. Where is the memory to which the returned pointer points? Is it still around by the time the function returns? The strstr function returns either a null pointer (which points definitively nowhere, and which the caller presumably checks for) or it returns a pointer which points into the input string, which the caller supplied, which is pretty safe. One thing a function must not do, however, is return a pointer to one of its own, local, automatic-duration arrays. Remember that automatic-duration variables (which includes all non-static local variables), including automatic-duration arrays, are deallocated and disappear when the function returns. If a function returns a pointer to a local array, that pointer will be invalid by the time the caller tries to use it.

Finally, when we're doing dynamic memory allocation with malloc, realloc, and free, we have to be most careful of all. Dynamic allocation gives us a lot more flexibility in how our programs use memory, although with that flexibility comes the responsibility that we manage dynamically allocated memory carefully. The possibilities for misdirected pointers and associated mayhem are greatest in programs that make heavy use of dynamic memory allocation. You can reduce these possibilities by designing your program in such a way that it's easy to ensure that pointers are used correctly and that memory is always allocated and deallocated correctly. (If, on the other hand, your program is designed in such a way that meeting these guarantees is a tedious nuisance, sooner or later you'll forget or neglect to, and maintenance will be a nightmare.)

Chapter 10: Pointers

Pointers are often thought to be the most difficult aspect of C. It's true that many people have various problems with pointers, and that many programs founder on pointer-related bugs. Actually, though, many of the problems are not so much with the pointers per se but rather with the memory they point to, and more specifically, when there isn't any valid memory which they point to. As long as you're careful to ensure that the pointers in your programs always point to valid memory, pointers can be useful, powerful, and relatively trouble-free tools. (We'll talk about memory allocation in the next chapter.)

[This chapter is the only one in this series that contains any graphics. If you are using a text-only browser, there are a few figures you won't be able to see.]

A pointer is a variable that points at, or refers to, another variable. That is, if we have a pointer variable of type ``pointer to int,`` it might point to the int variable i, or to the third cell of the int array a. Given a pointer variable, we can ask questions like, ``What's the value of the variable that this pointer points to?''

Why would we want to have a variable that refers to another variable? Why not just use that other variable directly? The answer is that a level of indirection can be very useful. (Indirection is just another word for the situation when one variable refers to another.)

Imagine a club which elects new officers each year. In its clubroom, it might have a set of mailboxes for each member, along with special mailboxes for the president, secretary, and treasurer. The bank doesn't mail statements to the treasurer under the treasurer's name; it mails them to ``treasurer,'' and the statements go to the mailbox marked ``treasurer.'' This way, the bank doesn't have to change the mailing address it uses every year. The mailboxes labeled ``president,'' ``treasurer,'' and ``secretary'' are a little bit like pointers--they don't refer to people directly.

If we make the analogy that a mailbox holding letters is like a variable holding numbers, then mailboxes for the president, secretary, and treasurer aren't quite like pointers, because they're still mailboxes which in principle could hold letters directly. But suppose that mail is never actually put in those three mailboxes: suppose each of the officers' mailboxes contains a little marker listing the name of the member currently holding that office. When you're sorting mail, and you have a letter for the treasurer, you first go to the treasurer's mailbox, but rather than putting the letter there, you read the name on the marker there, and put the mail in the mailbox for that person. Similarly, if the club is poorly organized, and the treasurer stops doing his job, and you're the president, and one day you get a call from the bank saying that the club's account is in arrears and the treasurer hasn't done anything about it and asking if you, the president, can look into it; and if the club is so poorly organized that you've forgotten who the treasurer is, you can go to the treasurer's mailbox, read the name on the marker there, and go to that mailbox (which is probably overflowing) to find all the treasury-related mail.

We could say that the markers in the mailboxes for the president, secretary, and treasurer were pointers to other mailboxes. In an analogous way, pointer variables in C contain pointers to other variables or memory locations.

10.1 Basic Pointer Operations

[This section corresponds to K&R Sec. 5.1]

The first things to do with pointers are to declare a pointer variable, set it to point somewhere, and finally manipulate the value that it points to. A simple pointer declaration looks like this:

        int *ip;

This declaration looks like our earlier declarations, with one obvious difference: that asterisk. The asterisk means that ip, the variable we're declaring, is not of type int, but rather of type pointer-to-int. (Another way of looking at it is that *ip, which as we'll see is the value pointed to by ip, will be an int.)

We may think of setting a pointer variable to point to another variable as a two-step process: first we generate a pointer to that other variable, then we assign this new pointer to the pointer variable. We can say (but we have to be careful when we're saying it) that a pointer variable has a value, and that its value is ``pointer to that other variable''. This will make more sense when we see how to generate pointer values.

Pointers (that is, pointer values) are generated with the ``address-of'' operator &, which we can also think of as the ``pointer-to'' operator. We demonstrate this by declaring (and initializing) an int variable i, and then setting ip to point to it:

        int i = 5;

        ip = &i;

The assignment expression ip = &i; contains both parts of the ``two-step process'': &i generates a pointer to i, and the assignment operator assigns the new pointer to (that is, places it ``in'') the variable ip. Now ip ``points to'' i, which we can illustrate with this picture:

i is a variable of type int, so the value in its box is a number, 5. ip is a variable of type pointer-to-int, so the ``value'' in its box is an arrow pointing at another box. Referring once again back to the ``two-step process'' for setting a pointer variable: the & operator draws us the arrowhead pointing at i's box, and the assignment operator =, with the pointer variable ip on its left, anchors the other end of the arrow in ip's box.

We discover the value pointed to by a pointer using the ``contents-of'' operator, *. Placed in front of a pointer, the * operator accesses the value pointed to by that pointer. In other words, if ip is a pointer, then the expression *ip gives us whatever it is that's in the variable or location pointed to by ip. For example, we could write something like

        printf("%d\n", *ip);

which would print 5, since ip points to i, and i is (at the moment) 5.

(You may wonder how the asterisk * can be the pointer contents-of operator when it is also the multiplication operator. There is no ambiguity here: it is the multiplication operator when it sits between two variables, and it is the contents-of operator when it sits in front of a single variable. The situation is analogous to the minus sign: between two variables or expressions it's the subtraction operator, but in front of a single operator or expression it's the negation operator. Technical terms you may hear for these distinct roles are unary and binary: a binary operator applies to two operands, usually on either side of it, while a unary operator applies to a single operand.)

The contents-of operator * does not merely fetch values through pointers; it can also set values through pointers. We can write something like

        *ip = 7;

which means ``set whatever ip points to to 7.'' Again, the * tells us to go to the location pointed to by ip, but this time, the location isn't the one to fetch from--we're on the left-hand sign of an assignment operator, so *ip tells us the location to store to. (The situation is no different from array subscripting expressions such as a[3] which we've already seen appearing on both sides of assignments.)

The result of the assignment *ip = 7 is that i's value is changed to 7, and the picture changes to:

If we called printf("%d\n", *ip) again, it would now print 7.

At this point, you may be wondering why we're going through this rigamarole--if we wanted to set i to 7, why didn't we do it directly? We'll begin to explore that next, but first let's notice the difference between changing a pointer (that is, changing what variable it points to) and changing the value at the location it points to. When we wrote *ip = 7, we changed the value pointed to by ip, but if we declare another variable j:

        int j = 3;

and write

        ip = &j;

we've changed ip itself. The picture now looks like this:

We have to be careful when we say that a pointer assignment changes ``what the pointer points to.'' Our earlier assignment

        *ip = 7;

changed the value pointed to by ip, but this more recent assignment

        ip = &j;

has changed what variable ip points to. It's true that ``what ip points to'' has changed, but this time, it has changed for a different reason. Neither i (which is still 7) nor j (which is still 3) has changed. (What has changed is ip's value.) If we again call

        printf("%d\n", *ip);

this time it will print 3.

We can also assign pointer values to other pointer variables. If we declare a second pointer variable:

        int *ip2;

then we can say

        ip2 = ip;

Now ip2 points where ip does; we've essentially made a ``copy'' of the arrow:

Now, if we set ip to point back to i again:

        ip = &i;

the two arrows point to different places:

We can now see that the two assignments

        ip2 = ip;

and

        *ip2 = *ip;

do two very different things. The first would make ip2 again point to where ip points (in other words, back to i again). The second would store, at the location pointed to by ip2, a copy of the value pointed to by ip; in other words (if ip and ip2 still point to i and j respectively) it would set j to i's value, or 7.

It's important to keep very clear in your mind the distinction between a pointer and what it points to. The two are like apples and oranges (or perhaps oil and water); you can't mix them. You can't ``set ip to 5'' by writing something like

        ip = 5;                /* WRONG */

5 is an integer, but ip is a pointer. You probably wanted to ``set the value pointed to by ip to 5,'' which you express by writing

        *ip = 5;

Similarly, you can't ``see what ip is'' by writing

        printf("%d\n", ip);    /* WRONG */

Again, ip is a pointer-to-int, but %d expects an int. To print what ip points to, use

        printf("%d\n", *ip);

Finally, a few more notes about pointer declarations. The * in a pointer declaration is related to, but different from, the contents-of operator *. After we declare a pointer variable

        int *ip;

the expression

        ip = &i

sets what ip points to (that is, which location it points to), while the expression

        *ip = 5

sets the value of the location pointed to by ip. On the other hand, if we declare a pointer variable and include an initializer:

        int *ip3 = &i;

we're setting the initial value for ip3, which is where ip3 will point, so that initial value is a pointer. (In other words, the * in the declaration int *ip3 = &i; is not the contents-of operator, it's the indicator that ip3 is a pointer.)

If you have a pointer declaration containing an initialization, and you ever have occasion to break it up into a simple declaration and a conventional assignment, do it like this:

        int *ip3;

        ip3 = &i;

Don't write

        int *ip3;

        *ip3 = &i;

or you'll be trying to mix oil and water again.

Also, when we write

        int *ip;

although the asterisk affects ip's type, it goes with the identifier name ip, not with the type int on the left. To declare two pointers at once, the declaration looks like

        int *ip1, *ip2;

Some people write pointer declarations like this:

        int* ip;

This works for one pointer, because C essentially ignores whitespace. But if you ever write

        int* ip1, ip2;         /* PROBABLY WRONG */

it will declare one pointer-to-int ip1 and one plain int ip2, which is probably not what you meant.

What is all of this good for? If it was just for changing variables like i from 5 to 7, it would not be good for much. What it's good for, among other things, is when for various reasons we don't know exactly which variable we want to change, just like the bank didn't know exactly which club member it wanted to send the statement to.

10.2 Pointers and Arrays; Pointer Arithmetic

[This section corresponds to K&R Sec. 5.3]

Pointers do not have to point to single variables. They can also point at the cells of an array. For example, we can write

        int *ip;

        int a[10];

        ip = &a[3];

and we would end up with ip pointing at the fourth cell of the array a (remember, arrays are 0-based, so a[0] is the first cell). We could illustrate the situation like this:

We'd use this ip just like the one in the previous section: *ip gives us what ip points to, which in this case will be the value in a[3].

Once we have a pointer pointing into an array, we can start doing pointer arithmetic. Given that ip is a pointer to a[3], we can add 1 to ip:

        ip + 1

What does it mean to add one to a pointer? In C, it gives a pointer to the cell one farther on, which in this case is a[4]. To make this clear, let's assign this new pointer to another pointer variable:

        ip2 = ip + 1;

Now the picture looks like this:

If we now do

        *ip2 = 4;

we've set a[4] to 4. But it's not necessary to assign a new pointer value to a pointer variable in order to use it; we could also compute a new pointer value and use it immediately:

        *(ip + 1) = 5;

In this last example, we've changed a[4] again, setting it to 5. The parentheses are needed because the unary ``contents of'' operator * has higher precedence (i.e., binds more tightly than) the addition operator. If we wrote *ip + 1, without the parentheses, we'd be fetching the value pointed to by ip, and adding 1 to that value. The expression *(ip + 1), on the other hand, accesses the value one past the one pointed to by ip.

Given that we can add 1 to a pointer, it's not surprising that we can add and subtract other numbers as well. If ip still points to a[3], then

        *(ip + 3) = 7;

sets a[6] to 7, and

        *(ip - 2) = 4;

sets a[1] to 4.

Up above, we added 1 to ip and assigned the new pointer to ip2, but there's no reason we can't add one to a pointer, and change the same pointer:

        ip = ip + 1;

Now ip points one past where it used to (to a[4], if we hadn't changed it in the meantime). The shortcuts we learned in a previous chapter all work for pointers, too: we could also increment a pointer using

        ip += 1;

or

        ip++;

Of course, pointers are not limited to ints. It's quite common to use pointers to other types, especially char. Here is the innards of the mystrcmp function we saw in a previous chapter, rewritten to use pointers. (mystrcmp, you may recall, compares two strings, character by character.)

        char *p1 = &str1[0], *p2 = &str2[0];

        while(1)

               {

               if(*p1 != *p2)

                       return *p1 - *p2;

               if(*p1 == '\0' || *p2 == '\0')

                       return 0;

               p1++;

               p2++;

               }

The autoincrement operator ++ (like its companion, --) makes it easy to do two things at once. We've seen idioms like a[i++] which accesses a[i] and simultaneously increments i, leaving it referencing the next cell of the array a. We can do the same thing with pointers: an expression like *ip++ lets us access what ip points to, while simultaneously incrementing ip so that it points to the next element. The preincrement form works, too: *++ip increments ip, then accesses what it points to. Similarly, we can use notations like *ip-- and *--ip.

As another example, here is the strcpy (string copy) loop from a previous chapter, rewritten to use pointers:

        char *dp = &dest[0], *sp = &src[0];

        while(*sp != '\0')

               *dp++ = *sp++;

        *dp = '\0';

(One question that comes up is whether the expression *p++ increments p or what it points to. The answer is that it increments p. To increment what p points to, you can use (*p)++.)

When you're doing pointer arithmetic, you have to remember how big the array the pointer points into is, so that you don't ever point outside it. If the array a has 10 elements, you can't access a[50] or a[-1] or even a[10] (remember, the valid subscripts for a 10-element array run from 0 to 9). Similarly, if a has 10 elements and ip points to a[3], you can't compute or access ip + 10 or ip - 5. (There is one special case: you can, in this case, compute, but not access, a pointer to the nonexistent element just beyond the end of the array, which in this case is &a[10]. This becomes useful when you're doing pointer comparisons, which we'll look at next.)

10.3 Pointer Subtraction and Comparison

As we've seen, you can add an integer to a pointer to get a new pointer, pointing somewhere beyond the original (as long as it's in the same array). For example, you might write

        ip2 = ip1 + 3;

Applying a little algebra, you might wonder whether

        ip2 - ip1 = 3

and the answer is, yes. When you subtract two pointers, as long as they point into the same array, the result is the number of elements separating them. You can also ask (again, as long as they point into the same array) whether one pointer is greater or less than another: one pointer is ``greater than'' another if it points beyond where the other one points. You can also compare pointers for equality and inequality: two pointers are equal if they point to the same variable or to the same cell in an array, and are (obviously) unequal if they don't. (When testing for equality or inequality, the two pointers do not have to point into the same array.)

One common use of pointer comparisons is when copying arrays using pointers. Here is a code fragment which copies 10 elements from array1 to array2, using pointers. It uses an end pointer, ep, to keep track of when it should stop copying.

        int array1[10], array2[10];

        int *ip1, *ip2 = &array2[0];

        int *ep = &array1[10];

        for(ip1 = &array1[0]; ip1 < ep; ip1++)

               *ip2++ = *ip1;

As we mentioned, there is no element array1[10], but it is legal to compute a pointer to this (nonexistent) element, as long as we only use it in pointer comparisons like this (that is, as long as we never try to fetch or store the value that it points to.)

10.4 Null Pointers

We said that the value of a pointer variable is a pointer to some other variable. There is one other value a pointer may have: it may be set to a null pointer. A null pointer is a special pointer value that is known not to point anywhere. What this means that no other valid pointer, to any other variable or array cell or anything else, will ever compare equal to a null pointer.

The most straightforward way to ``get'' a null pointer in your program is by using the predefined constant NULL, which is defined for you by several standard header files, including , , and . To initialize a pointer to a null pointer, you might use code like

        #include 

        int *ip = NULL;

and to test it for a null pointer before inspecting the value pointed to you might use code like

        if(ip != NULL)

               printf("%d\n", *ip);

It is also possible to refer to the null pointer by using a constant 0, and you will see some code that sets null pointers by simply doing

        int *ip = 0;

(In fact, NULL is a preprocessor macro which typically has the value, or replacement text, 0.)

Furthermore, since the definition of ``true'' in C is a value that is not equal to 0, you will see code that tests for non-null pointers with abbreviated code like

        if(ip)

               printf("%d\n", *ip);

This has the same meaning as our previous example; if(ip) is equivalent to if(ip != 0) and to if(ip != NULL).

All of these uses are legal, and although I recommend that you use the constant NULL for clarity, you will come across the other forms, so you should be able to recognize them.

You can use a null pointer as a placeholder to remind yourself (or, more importantly, to help your program remember) that a pointer variable does not point anywhere at the moment and that you should not use the ``contents of'' operator on it (that is, you should not try to inspect what it points to, since it doesn't point to anything). A function that returns pointer values can return a null pointer when it is unable to perform its task. (A null pointer used in this way is analogous to the EOF value that functions like getchar return.)

As an example, let us write our own version of the standard library function strstr, which looks for one string within another, returning a pointer to the string if it can, or a null pointer if it cannot. Here is the function, using the obvious brute-force algorithm: at every character of the input string, the code checks for a match there of the pattern string:

#include 

char *mystrstr(char input[], char pat[])

{

        char *start, *p1, *p2;

        for(start = &input[0]; *start != '\0'; start++)

               {              /* for each position in input string... */

               p1 = pat;      /* prepare to check for pattern string there */

               p2 = start;

               while(*p1 != '\0')

                       {

                       if(*p1 != *p2) /* characters differ */

                               break;

                       p1++;

                       p2++;

                       }

               if(*p1 == '\0')        /* found match */

                       return start;

               }

        return NULL;

}

The start pointer steps over each character position in the input string. At each character, the inner loop checks for a match there, by using p1 to step over the pattern string (pat), and p2 to step over the input string (starting at start). We compare successive characters until either (a) we reach the end of the pattern string (*p1 == '\0'), or (b) we find two characters which differ. When we're done with the inner loop, if we reached the end of the pattern string (*p1 == '\0'), it means that all preceding characters matched, and we found a complete match for the pattern starting at start, so we return start. Otherwise, we go around the outer loop again, to try another starting position. If we run out of those (if *start == '\0'), without finding a match, we return a null pointer.

Notice that the function is declared as returning (and does in fact return) a pointer-to-char.

We can use mystrstr (or its standard library counterpart strstr) to determine whether one string contains another:

        if(mystrstr("Hello, world!", "lo") == NULL)

               printf("no\n");

        else    printf("yes\n");

In general, C does not initialize pointers to null for you, and it never tests pointers to see if they are null before using them. If one of the pointers in your programs points somewhere some of the time but not all of the time, an excellent convention to use is to set it to a null pointer when it doesn't point anywhere valid, and to test to see if it's a null pointer before using it. But you must use explicit code to set it to NULL, and to test it against NULL. (In other words, just setting an unused pointer variable to NULL doesn't guarantee safety; you also have to check for the null value before using the pointer.) On the other hand, if you know that a particular pointer variable is always valid, you don't have to insert a paranoid test against NULL before using it.

10.5 ``Equivalence'' between Pointers and Arrays

There are a number of similarities between arrays and pointers in C. If you have an array

        int a[10];

you can refer to a[0], a[1], a[2], etc., or to a[i] where i is an int. If you declare a pointer variable ip and set it to point to the beginning of an array:

        int *ip = &a[0];

you can refer to *ip, *(ip+1), *(ip+2), etc., or to *(ip+i) where i is an int.

There are also differences, of course. You cannot assign two arrays; the code

        int a[10], b[10];

        a = b;                         /* WRONG */

is illegal. As we've seen, though, you can assign two pointer variables:

        int *ip1, *ip2;

        ip1 = &a[0];

        ip2 = ip1;

Pointer assignment is straightforward; the pointer on the left is simply made to point wherever the pointer on the right does. We haven't copied the data pointed to (there's still just one copy, in the same place); we've just made two pointers point to that one place.

The similarities between arrays and pointers end up being quite useful, and in fact C builds on the similarities, leading to what is called ``the equivalence of arrays and pointers in C.'' When we speak of this ``equivalence'' we do not mean that arrays and pointers are the same thing (they are in fact quite different), but rather that they can be used in related ways, and that certain operations may be used between them.

The first such operation is that it is possible to (apparently) assign an array to a pointer:

        int a[10];

        int *ip;

        ip = a;

What can this mean? In that last assignment ip = a, aren't we mixing apples and oranges again? It turns out that we are not; C defines the result of this assignment to be that ip receives a pointer to the first element of a. In other words, it is as if you had written

        ip = &a[0];

The second facet of the equivalence is that you can use the ``array subscripting'' notation [i] on pointers, too. If you write

        ip[3]

it is just as if you had written

        *(ip + 3)

So when you have a pointer that points to a block of memory, such as an array or a part of an array, you can treat that pointer ``as if'' it were an array, using the convenient [i] notation. In other words, at the beginning of this section when we talked about *ip, *(ip+1), *(ip+2), and *(ip+i), we could have written ip[0], ip[1], ip[2], and ip[i]. As we'll see, this can be quite useful (or at least convenient).

The third facet of the equivalence (which is actually a more general version of the first one we mentioned) is that whenever you mention the name of an array in a context where the ``value'' of the array would be needed, C automatically generates a pointer to the first element of the array, as if you had written &array[0]. When you write something like

        int a[10];

        int *ip;

        ip = a + 3;

it is as if you had written

        ip = &a[0] + 3;

which (and you might like to convince yourself of this) gives the same result as if you had written

        ip = &a[3];

For example, if the character array

        char string[100];

contains some string, here is another way to find its length:

        int len;

        char *p;

        for(p = string; *p != '\0'; p++)

               ;

        len = p - string;

After the loop, p points to the '\0' terminating the string. The expression p - string is equivalent to p - &string[0], and gives the length of the string. (Of course, we could also call strlen; in fact here we've essentially written another implementation of strlen.)

10.6 Arrays and Pointers as Function Arguments

[This section corresponds to K&R Sec. 5.2]

Earlier, we learned that functions in C receive copies of their arguments. (This means that C uses call by value; it means that a function can modify one of its arguments without modifying the value in the caller.) We didn't say so at the time, but when a function is called, the copies of the arguments are made as if by assignment. But since arrays can't be assigned, how can a function receive an array as an argument? The answer will explain why arrays are an apparent exception to the rule that functions cannot modify their arguments.

We've been regularly calling a function getline like this:

        char line[100];

        getline(line, 100);

with the intention that getline read the next line of input into the character array line. But in the previous paragraph, we learned that when we mention the name of an array in an expression, the compiler generates a pointer to its first element. So the call above is as if we had written

        char line[100];

        getline(&line[0], 100);

In other words, the getline function does not receive an array of char at all; it actually receives a pointer to char!

As we've seen throughout this chapter, it's straightforward to manipulate the elements of an array using pointers, so there's no particular insurmountable difficulty if getline receives a pointer. One question remains, though: we had been defining getline with its line parameter declared as an array:

        int getline(char line[], int max)

        {

        ...

        }

We mentioned that we didn't have to specify a size for the line parameter, with the explanation that getline really used the array in its caller, where the actual size was specified. But that declaration certainly does look like an array--how can it work when getline actually receives a pointer?

The answer is that the C compiler does a little something behind your back. It knows that whenever you mention an array name in an expression, it (the compiler) generates a pointer to the array's first element. Therefore, it knows that a function can never actually receive an array as a parameter. Therefore, whenever it sees you defining a function that seems to accept an array as a parameter, the compiler quietly pretends that you had declared it as accepting a pointer, instead. The definition of getline above is compiled exactly as if it had been written

        int getline(char *line, int max)

        {

        ...

        }

Let's look at how getline might be written if we thought of its first parameter (argument) as a pointer, instead:

int getline(char *line, int max)

{

int nch = 0;

int c;

max = max - 1;                 /* leave room for '\0' */

#ifndef FGETLINE

while((c = getchar()) != EOF)

#else

while((c = getc(fp)) != EOF)

#endif

        {

        if(c == '\n')

               break;

        if(nch < max)

               {

               *(line + nch) = c;

               nch = nch + 1;

               }

        }

if(c == EOF && nch == 0)

        return EOF;

*(line + nch) = '\0';

return nch;

}

But, as we've learned, we can also use ``array subscript'' notation with pointers, so we could rewrite the pointer version of getline like this:

int getline(char *line, int max)

{

int nch = 0;

int c;

max = max - 1;                 /* leave room for '\0' */

#ifndef FGETLINE

while((c = getchar()) != EOF)

#else

while((c = getc(fp)) != EOF)

#endif

        {

        if(c == '\n')

               break;

        if(nch < max)

               {

               line[nch] = c;

               nch = nch + 1;

               }

        }

if(c == EOF && nch == 0)

        return EOF;

line[nch] = '\0';

return nch;

}

But this is exactly what we'd written before (see chapter 6, Sec. 6.3), except that the declaration of the line parameter is different. In other words, within the body of the function, it hardly matters whether we thought line was an array or a pointer, since we can use array subscripting notation with both arrays and pointers.

These games that the compiler is playing with arrays and pointers may seem bewildering at first, and it may seem faintly miraculous that everything comes out in the wash when you declare a function like getline that seems to accept an array. The equivalence in C between arrays and pointers can be confusing, but it does work and is one of the central features of C. If the games which the compiler plays (pretending that you declared a parameter as a pointer when you thought you declared it as an array) bother you, you can do two things:

1. Continue to pretend that functions can receive arrays as parameters; declare and use them that way, but remember that unlike other arguments, a function can modify the copy in its caller of an argument that (seems to be) an array.
2. Realize that arrays are always passed to functions as pointers, and always declare your functions as accepting pointers.

10.7 Strings

Because of the ``equivalence'' of arrays and pointers, it is extremely common to refer to and manipulate strings as character pointers, or char *'s. It is so common, in fact, that it is easy to forget that strings are arrays, and to imagine that they're represented by pointers. (Actually, in the case of strings, it may not even matter that much if the distinction gets a little blurred; there's certainly nothing wrong with referring to a character pointer, suitably initialized, as a ``string.'') Let's look at a few of the implications:

1. Any function that manipulates a string will actually accept it as a char * argument. The caller may pass an array containing a string, but the function will receive a pointer to the array's (string's) first element (character).
2. The %s format in printf expects a character pointer.
3. Although you have to use strcpy to copy a string from one array to another, you can use simple pointer assignment to assign a string to a pointer. The string being assigned might either be in an array or pointed to by another pointer. In other words, given

4.                   char string[] = "Hello, world!";

5.                   char *p1, *p2;

both

  p1 = string

and

  p2 = p1

are legal. (Remember, though, that when you assign a pointer, you're making a copy of the pointer but not of the data it points to. In the first example, p1 ends up pointing to the string in string. In the second example, p2 ends up pointing to the same string as p1. In any case, after a pointer assignment, if you ever change the string (or other data) pointed to, the change is ``visible'' to both pointers.

6. Many programs manipulate strings exclusively using character pointers, never explicitly declaring any actual arrays. As long as these programs are careful to allocate appropriate memory for the strings, they're perfectly valid and correct.

When you start working heavily with strings, however, you have to be aware of one subtle fact.

When you initialize a character array with a string constant:

        char string[] = "Hello, world!";

you end up with an array containing the string, and you can modify the array's contents to your heart's content:

        string[0] = 'J';

However, it's possible to use string constants (the formal term is string literals) at other places in your code. Since they're arrays, the compiler generates pointers to their first elements when they're used in expressions, as usual. That is, if you say

        char *p1 = "Hello";

        int len = strlen("world");

it's almost as if you'd said

        char internal_string_1[] = "Hello";

        char internal_string_2[] = "world";

        char *p1 = &internal_string_1[0];

        int len = strlen(&internal_string_2[0]);

Here, the arrays named internal_string_1 and internal_string_2 are supposed to suggest the fact that the compiler is actually generating little temporary arrays every time you use a string constant in your code. However, the subtle fact is that the arrays which are ``behind'' the string constants are not necessarily modifiable. In particular, the compiler may store them in read-only-memory. Therefore, if you write

        char *p3 = "Hello, world!";

        p3[0] = 'J';

your program may crash, because it may try to store a value (in this case, the character 'J') into nonwritable memory.

The moral is that whenever you're building or modifying strings, you have to make sure that the memory you're building or modifying them in is writable. That memory should either be an array you've allocated, or some memory which you've dynamically allocated by the techniques which we'll see in the next chapter. Make sure that no part of your program will ever try to modify a string which is actually one of the unnamed, unwritable arrays which the compiler generated for you in response to one of your string constants. (The only exception is array initialization, because if you write to such an array, you're writing to the array, not to the string literal which you used to initialize the array.)

10.8 Example: Breaking a Line into ``Words''

In an earlier assignment, an ``extra credit'' version of a problem asked you to write a little checkbook balancing program that accepted a series of lines of the form

        deposit 1000

        check 10

        check 12.34

        deposit 50

        check 20

It was a surprising nuisance to do this in an ad hoc way, using only the tools we had at the time. It was easy to read each line, but it was cumbersome to break it up into the word (``deposit'' or ``check'') and the amount.

I find it very convenient to use a more general approach: first, break lines like these into a series of whitespace-separated words, then deal with each word separately. To do this, we will use an array of pointers to char, which we can also think of as an ``array of strings,'' since a string is an array of char, and a pointer-to-char can easily point at a string. Here is the declaration of such an array:

        char *words[10];

This is the first complicated C declaration we've seen: it says that words is an array of 10 pointers to char. We're going to write a function, getwords, which we can call like this:

        int nwords;

        nwords = getwords(line, words, 10);

where line is the line we're breaking into words, words is the array to be filled in with the (pointers to the) words, and nwords (the return value from getwords) is the number of words which the function finds. (As with getline, we tell the function the size of the array so that if the line should happen to contain more words than that, it won't overflow the array).

Here is the definition of the getwords function. It finds the beginning of each word, places a pointer to it in the array, finds the end of that word (which is signified by at least one whitespace character) and terminates the word by placing a '\0' character after it. (The '\0' character will overwrite the first whitespace character following the word.) Note that the original input string is therefore modified by getwords: if you were to try to print the input line after calling getwords, it would appear to contain only its first word (because of the first inserted '\0').

#include 

#include 

getwords(char *line, char *words[], int maxwords)

{

char *p = line;

int nwords = 0;

while(1)

        {

        while(isspace(*p))

               p++;

        if(*p == '\0')

               return nwords;

        words[nwords++] = p;

        while(!isspace(*p) && *p != '\0')

               p++;

        if(*p == '\0')

               return nwords;

        *p++ = '\0';

        if(nwords >= maxwords)

               return nwords;

        }

}

Each time through the outer while loop, the function tries to find another word. First it skips over whitespace (which might be leading spaces on the line, or the space(s) separating this word from the previous one). The isspace function is new: it's in the standard library, declared in the header file , and it returns nonzero (``true'') if the character you hand it is a space character (a space or a tab, or any other whitespace character there might happen to be).

When the function finds a non-whitespace character, it has found the beginning of another word, so it places the pointer to that character in the next cell of the words array. Then it steps though the word, looking at non-whitespace characters, until it finds another whitespace character, or the \0 at the end of the line. If it finds the \0, it's done with the entire line; otherwise, it changes the whitespace character to a \0, to terminate the word it's just found, and continues. (If it's found as many words as will fit in the words array, it returns prematurely.)

Each time it finds a word, the function increments the number of words (nwords) it has found. Since arrays in C start at [0], the number of words the function has found so far is also the index of the cell in the words array where the next word should be stored. The function actually assigns the next word and increments nwords in one expression:

        words[nwords++] = p;

You should convince yourself that this arrangement works, and that (in this case) the preincrement form

        words[++nwords] = p;           /* WRONG */

would not behave as desired.

When the function is done (when it finds the \0 terminating the input line, or when it runs out of cells in the words array) it returns the number of words it has found.

Here is a complete example of calling getwords:

        char line[] = "this is a test";

        int i;

        nwords = getwords(line, words, 10);

        for(i = 0; i < nwords; i++)

               printf("%s\n", words[i]);