Features

Pointer-Pointers In C

Anthony Dos Reis and Li Yun

Anthony Dos Reis is an assistant professor of computer science at the College of New Paltz in New York. Li Yun is a graduate student in the college's Mathematics and Computer Science Department.

Pointer-pointers are literally pointers that point to other pointers. They are used in functions that must change the value stored in a parameter. Because variables in C are passed by value, not by reference, such functions must be passed the variable's address (pass-by-reference), not its value. A parameter can be a pointer. A pointer's address is, of course, just a pointer-pointer.

For example, the increment function below increments an integer pointer. It declares parameter p as

   int **p;
Breaking this declaration into two parts — int * and *p — makes its meaning clear. *p indicates that p is a pointer. int * means that p points to an integer pointer. In the function body, (*p) references the integer pointer to which p points. Thus, (*p)++ increments this integer pointer.

increment (p)
   int **p;
{
(*p)++;
}
Using a typedef statement for int* simplifies the parameter declaration.

typedef int * LINK;
increment (p)
   LINK *p;
{
(*p)++;
}
Using pointer-pointers carefully can considerably reduce the complexity of functions that perform pointer manipulation. For example, consider two functions that both add a node to a binary search tree. The first function, add1, uses the standard textbook technique of two pointers, one trailing the other, to determine the insertion point for the new node. The two pointers, current and previous, move down the tree until current takes the value NULL. The function then adds the new node to the previous node. Notice that though add1 is passed a pointer-pointer (rootpp), its use is limited to accessing the root pointer of the tree.

The add1 function is more complex than add2 in several respects. First, it moves two pointers, current and previous, instead of one. Second, add1 performs a special test to determine if the tree is NULL (in which case the new node becomes the root of the tree). add2 needs no special test. Third, after finding the leaf at which the insertion must occur, add1 must determine whether to add to the left or to the right of the leaf, even though this left/right test was just performed in the preceding while loop. In contrast, add2 exits its while loop with pp pointing to the left or right field that must be modified to add the new node.

Pointer-pointers may be a bit harder to understand at first, but the investment can pay off in simpler code.

Listing 1