Back to Chapter 4 --  Index --  Chapter 6

Chapter 5 - Pointers and Arrays

Pointers have been lumped with the goto statement as a marvelous way to create impossible-to-understand programs. This is certainly true when they are used carelessly, and it is easy to create pointers that point somewhere unexpected. With discipline, however, pointers can also be used to achieve clarity and simplicity. This is the aspect that we will try to illustrate.

The main change in ANSI C is to make explicit the rules about how pointers can be manipulated, in effect mandating what good programmers already practice and good compilers already enforce. In addition, the type void * (pointer to void) replaces char * as the proper type for a generic pointer.

5.1 Pointers and Addresses

The unary operator & gives the address of an object, so the statement

   p = &c;

The unary operator * is the indirection or dereferencing operator; when applied to a pointer, it accesses the object the pointer points to. Suppose that x and y are integers and ip is a pointer to int. This artificial sequence shows how to declare a pointer and how to use & and *:

   int x = 1, y = 2, z[10];
   int *ip;          /* ip is a pointer to int */

   ip = &x;          /* ip now points to x */
   y = *ip;          /* y is now 1 */
   *ip = 0;          /* x is now 0 */
   ip = &z[0];       /* ip now points to z[0] */

   int *ip;

   double *dp, atof(char *);

You should also note the implication that a pointer is constrained to point to a particular kind of object: every pointer points to a specific data type. (There is one exception: a ``pointer to void'' is used to hold any type of pointer but cannot be dereferenced itself. We'll come back to it in Section 5.11.)

If ip points to the integer x, then *ip can occur in any context where x could, so

   *ip = *ip + 10;

The unary operators * and & bind more tightly than arithmetic operators, so the assignment

   y = *ip + 1

   *ip += 1

   ++*ip

   (*ip)++

Finally, since pointers are variables, they can be used without dereferencing. For example, if iq is another pointer to int,

   iq = ip

5.2 Pointers and Function Arguments

   swap(a, b);

   void swap(int x, int y)  /* WRONG */
   {
       int temp;

       temp = x;
       x = y;
       y = temp;
   }

The way to obtain the desired effect is for the calling program to pass pointers to the values to be changed:

   swap(&a, &b);

   void swap(int *px, int *py)  /* interchange *px and *py */
   {
       int temp;

       temp = *px;
       *px = *py;
       *py = temp;
   }

Pointer arguments enable a function to access and change objects in the function that called it. As an example, consider a function getint that performs free-format input conversion by breaking a stream of characters into integer values, one integer per call. getint has to return the value it found and also signal end of file when there is no more input. These values have to be passed back by separate paths, for no matter what value is used for EOF, that could also be the value of an input integer.

One solution is to have getint return the end of file status as its function value, while using a pointer argument to store the converted integer back in the calling function. This is the scheme used by scanf as well; see Section 7.4.

The following loop fills an array with integers by calls to getint:

   int n, array[SIZE], getint(int *);

   for (n = 0; n < SIZE && getint(&array[n]) != EOF; n++)
       ;

Our version of getint returns EOF for end of file, zero if the next input is not a number, and a positive value if the input contains a valid number.

   #include <ctype.h>

   int getch(void);
   void ungetch(int);

   /* getint:  get next integer from input into *pn */
   int getint(int *pn)
   {
       int c, sign;

       while (isspace(c = getch()))   /* skip white space */
           ;
       if (!isdigit(c) && c != EOF && c != '+' && c != '-') {
           ungetch(c);  /* it is not a number */
           return 0;
       }
       sign = (c == '-') ? -1 : 1;
       if (c == '+' || c == '-')
           c = getch();
       for (*pn = 0; isdigit(c), c = getch())
           *pn = 10 * *pn + (c - '0');
       *pn *= sign;
       if (c != EOF)
           ungetch(c);
       return c;
   }

Exercise 5-1. As written, getint treats a + or - not followed by a digit as a valid representation of zero. Fix it to push such a character back on the input.

Exercise 5-2. Write getfloat, the floating-point analog of getint. What type does getfloat return as its function value?

5.3 Pointers and Arrays

The declaration

   int a[10];

The notation a[i] refers to the i-th element of the array. If pa is a pointer to an integer, declared as

   int *pa;

   pa = &a[0];

Now the assignment

   x = *pa;

If pa points to a particular element of an array, then by definition pa+1 points to the next element, pa+i points i elements after pa, and pa-i points i elements before. Thus, if pa points to a[0],

   *(pa+1)

These remarks are true regardless of the type or size of the variables in the array a. The meaning of ``adding 1 to a pointer,'' and by extension, all pointer arithmetic, is that pa+1 points to the next object, and pa+i points to the i-th object beyond pa.

The correspondence between indexing and pointer arithmetic is very close. By definition, the value of a variable or expression of type array is the address of element zero of the array. Thus after the assignment

   pa = &a[0];

   pa = a;

There is one difference between an array name and a pointer that must be kept in mind. A pointer is a variable, so pa=a and pa++ are legal. But an array name is not a variable; constructions like a=pa and a++ are illegal.

When an array name is passed to a function, what is passed is the location of the initial element. Within the called function, this argument is a local variable, and so an array name parameter is a pointer, that is, a variable containing an address. We can use this fact to write another version of strlen, which computes the length of a string.

   /* strlen:  return length of string s */
   int strlen(char *s)
   {
       int n;

       for (n = 0; *s != '\0', s++)
           n++;
       return n;
   }

   strlen("hello, world");   /* string constant */
   strlen(array);            /* char array[100]; */
   strlen(ptr);              /* char *ptr; */

As formal parameters in a function definition,

   char s[];

   char *s;

It is possible to pass part of an array to a function, by passing a pointer to the beginning of the subarray. For example, if a is an array,

   f(&a[2])

   f(a+2)

   f(int arr[]) { ... }

   f(int *arr) { ... }

If one is sure that the elements exist, it is also possible to index backwards in an array; p[-1], p[-2], and so on are syntactically legal, and refer to the elements that immediately precede p[0]. Of course, it is illegal to refer to objects that are not within the array bounds.

5.4 Address Arithmetic

C is consistent and regular in its approach to address arithmetic; its integration of pointers, arrays, and address arithmetic is one of the strengths of the language. Let us illustrate by writing a rudimentary storage allocator. There are two routines. The first, alloc(n), returns a pointer to n consecutive character positions, which can be used by the caller of alloc for storing characters. The second, afree(p), releases the storage thus acquired so it can be re-used later. The routines are ``rudimentary'' because the calls to afree must be made in the opposite order to the calls made on alloc. That is, the storage managed by alloc and afree is a stack, or last-in, first-out. The standard library provides analogous functions called malloc and free that have no such restrictions; in Section 8.7 we will show how they can be implemented.

The easiest implementation is to have alloc hand out pieces of a large character array that we will call allocbuf. This array is private to alloc and afree. Since they deal in pointers, not array indices, no other routine need know the name of the array, which can be declared static in the source file containing alloc and afree, and thus be invisible outside it. In practical implementations, the array may well not even have a name; it might instead be obtained by calling malloc or by asking the operating system for a pointer to some unnamed block of storage.

The other information needed is how much of allocbuf has been used. We use a pointer, called allocp, that points to the next free element. When alloc is asked for n characters, it checks to see if there is enough room left in allocbuf. If so, alloc returns the current value of allocp (i.e., the beginning of the free block), then increments it by n to point to the next free area. If there is no room, alloc returns zero. afree(p) merely sets allocp to p if p is inside allocbuf.

   #define ALLOCSIZE 10000 /* size of available space */

   static char allocbuf[ALLOCSIZE]; /* storage for alloc */
   static char *allocp = allocbuf;  /* next free position */

   char *alloc(int n)    /* return pointer to n characters */
   {
       if (allocbuf + ALLOCSIZE - allocp >= n) {  /* it fits */
           allocp += n;
           return allocp - n; /* old p */
       } else      /* not enough room */
           return 0;
   }

   void afree(char *p)  /* free storage pointed to by p */
   {
       if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
           allocp = p;
   }

   static char *allocp = allocbuf;

   static char *allocp = &allocbuf[0];

The test

       if (allocbuf + ALLOCSIZE - allocp >= n) {  /* it fits */

Pointers and integers are not interchangeable. Zero is the sole exception: the constant zero may be assigned to a pointer, and a pointer may be compared with the constant zero. The symbolic constant NULL is often used in place of zero, as a mnemonic to indicate more clearly that this is a special value for a pointer. NULL is defined in <stdio.h>. We will use NULL henceforth.

Tests like

       if (allocbuf + ALLOCSIZE - allocp >= n) {  /* it fits */

       if (p >= allocbuf && p < allocbuf + ALLOCSIZE)

   p < q

Second, we have already observed that a pointer and an integer may be added or subtracted. The construction

   p + n

Pointer subtraction is also valid: if p and q point to elements of the same array, and p<q, then q-p+1 is the number of elements from p to q inclusive. This fact can be used to write yet another version of strlen:

   /* strlen:  return length of string s */
   int strlen(char *s)
   {
       char *p = s;

       while (*p != '\0')
           p++;
       return p - s;
   }

Pointer arithmetic is consistent: if we had been dealing with floats, which occupy more storage that chars, and if p were a pointer to float, p++ would advance to the next float. Thus we could write another version of alloc that maintains floats instead of chars, merely by changing char to float throughout alloc and afree. All the pointer manipulations automatically take into account the size of the objects pointed to.

The valid pointer operations are assignment of pointers of the same type, adding or subtracting a pointer and an integer, subtracting or comparing two pointers to members of the same array, and assigning or comparing to zero. All other pointer arithmetic is illegal. It is not legal to add two pointers, or to multiply or divide or shift or mask them, or to add float or double to them, or even, except for void *, to assign a pointer of one type to a pointer of another type without a cast.

5.5 Character Pointers and Functions

   "I am a string"

Perhaps the most common occurrence of string constants is as arguments to functions, as in

   printf("hello, world\n");

String constants need not be function arguments. If pmessage is declared as

   char *pmessage;

   pmessage = "now is the time";

There is an important difference between these definitions:

   char amessage[] = "now is the time"; /* an array */
   char *pmessage = "now is the time"; /* a pointer */

We will illustrate more aspects of pointers and arrays by studying versions of two useful functions adapted from the standard library. The first function is strcpy(s,t), which copies the string t to the string s. It would be nice just to say s=t but this copies the pointer, not the characters. To copy the characters, we need a loop. The array version first:

   /* strcpy:  copy t to s; array subscript version */
   void strcpy(char *s, char *t)
   {
       int i;

       i = 0;
       while ((s[i] = t[i]) != '\0')
           i++;
   }

   /* strcpy:  copy t to s; pointer version */
   void strcpy(char *s, char *t)
   {
       int i;

       i = 0;
       while ((*s = *t) != '\0') {
           s++;
           t++;
       }
   }

In practice, strcpy would not be written as we showed it above. Experienced C programmers would prefer

   /* strcpy:  copy t to s; pointer version 2 */
   void strcpy(char *s, char *t)
   {
       while ((*s++ = *t++) != '\0')
           ;
   }

As the final abbreviation, observe that a comparison against '\0' is redundant, since the question is merely whether the expression is zero. So the function would likely be written as

   /* strcpy:  copy t to s; pointer version 3 */
   void strcpy(char *s, char *t)
   {
       while (*s++ = *t++)
           ;
   }

The strcpy in the standard library (<string.h>) returns the target string as its function value.

The second routine that we will examine is strcmp(s,t), which compares the character strings s and t, and returns negative, zero or positive if s is lexicographically less than, equal to, or greater than t. The value is obtained by subtracting the characters at the first position where s and t disagree.

   /* strcmp:  return <0 if s<t, 0 if s==t, >0 if s>t */
   int strcmp(char *s, char *t)
   {
       int i;

       for (i = 0; s[i] == t[i]; i++)
           if (s[i] == '\0')
               return 0;
       return s[i] - t[i];
   }

   /* strcmp:  return <0 if s<t, 0 if s==t, >0 if s>t */
   int strcmp(char *s, char *t)
   {
       for ( ; *s == *t; s++, t++)
           if (*s == '\0')
               return 0;
       return *s - *t;
   }

   *--p

   *p++ = val;  /* push val onto stack */
   val = *--p;  /* pop top of stack into val */

The header <string.h> contains declarations for the functions mentioned in this section, plus a variety of other string-handling functions from the standard library.

Exercise 5-3. Write a pointer version of the function strcat that we showed in Chapter 2: strcat(s,t) copies the string t to the end of s.

Exercise 5-4. Write the function strend(s,t), which returns 1 if the string t occurs at the end of the string s, and zero otherwise.

Exercise 5-5. Write versions of the library functions strncpy, strncat, and strncmp, which operate on at most the first n characters of their argument strings. For example, strncpy(s,t,n) copies at most n characters of t to s. Full descriptions are in Appendix B.

Exercise 5-6. Rewrite appropriate programs from earlier chapters and exercises with pointers instead of array indexing. Good possibilities include getline (Chapters 1 and 4), atoi, itoa, and their variants (Chapters 2, 3, and 4), reverse (Chapter 3), and strindex and getop (Chapter 4).

5.6 Pointer Arrays; Pointers to Pointers

In Chapter 3, we presented a Shell sort function that would sort an array of integers, and in Chapter 4 we improved on it with a quicksort. The same algorithms will work, except that now we have to deal with lines of text, which are of different lengths, and which, unlike integers, can't be compared or moved in a single operation. We need a data representation that will cope efficiently and conveniently with variable-length text lines.

This is where the array of pointers enters. If the lines to be sorted are stored end-to-end in one long character array, then each line can be accessed by a pointer to its first character. The pointers themselves can bee stored in an array. Two lines can be compared by passing their pointers to strcmp. When two out-of-order lines have to be exchanged, the pointers in the pointer array are exchanged, not the text lines themselves.

This eliminates the twin problems of complicated storage management and high overhead that would go with moving the lines themselves.

The sorting process has three steps:

  read all the lines of input
  sort them
  print them in order

As usual, it's best to divide the program into functions that match this natural division, with the main routine controlling the other functions. Let us defer the sorting step for a moment, and concentrate on the data structure and the input and output.

The input routine has to collect and save the characters of each line, and build an array of pointers to the lines. It will also have to count the number of input lines, since that information is needed for sorting and printing. Since the input function can only cope with a finite number of input lines, it can return some illegal count like -1 if too much input is presented.

The output routine only has to print the lines in the order in which they appear in the array of pointers.

   #include <stdio.h>
   #include <string.h>

   #define MAXLINES 5000     /* max #lines to be sorted */

   char *lineptr[MAXLINES];  /* pointers to text lines */

   int readlines(char *lineptr[], int nlines);
   void writelines(char *lineptr[], int nlines);

   void qsort(char *lineptr[], int left, int right);

   /* sort input lines */
   main()
   {
       int nlines;     /* number of input lines read */

       if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
           qsort(lineptr, 0, nlines-1);
           writelines(lineptr, nlines);
           return 0;
       } else {
           printf("error: input too big to sort\n");
           return 1;
       }
   }

   #define MAXLEN 1000  /* max length of any input line */
   int getline(char *, int);
   char *alloc(int);

   /* readlines:  read input lines */
   int readlines(char *lineptr[], int maxlines)
   {
       int len, nlines;
       char *p, line[MAXLEN];

       nlines = 0;
       while ((len = getline(line, MAXLEN)) > 0)
           if (nlines >= maxlines || p = alloc(len) == NULL)
               return -1;
           else {
               line[len-1] = '\0';  /* delete newline */
               strcpy(p, line);
               lineptr[nlines++] = p;
           }
       return nlines;
   }

   /* writelines:  write output lines */
   void writelines(char *lineptr[], int nlines)
   {
       int i;

       for (i = 0; i < nlines; i++)
           printf("%s\n", lineptr[i]);
   }

The main new thing is the declaration for lineptr:

   char *lineptr[MAXLINES]

Since lineptr is itself the name of an array, it can be treated as a pointer in the same manner as in our earlier examples, and writelines can be written instead as

   /* writelines:  write output lines */
   void writelines(char *lineptr[], int nlines)
   {
       while (nlines-- > 0)
           printf("%s\n", *lineptr++);
   }

With input and output under control, we can proceed to sorting. The quicksort from Chapter 4 needs minor changes: the declarations have to be modified, and the comparison operation must be done by calling strcmp. The algorithm remains the same, which gives us some confidence that it will still work.

   /* qsort:  sort v[left]...v[right] into increasing order */
   void qsort(char *v[], int left, int right)
   {
       int i, last;
       void swap(char *v[], int i, int j);

       if (left >= right)  /* do nothing if array contains */
           return;         /* fewer than two elements */
       swap(v, left, (left + right)/2);
       last = left;
       for (i = left+1; i <= right; i++)
           if (strcmp(v[i], v[left]) < 0)
               swap(v, ++last, i);
       swap(v, left, last);
       qsort(v, left, last-1);
       qsort(v, last+1, right);
   }

   /* swap:  interchange v[i] and v[j] */
   void swap(char *v[], int i, int j)
   {
       char *temp;

       temp = v[i];
       v[i] = v[j];
       v[j] = temp;
   }

Exercise 5-7. Rewrite readlines to store lines in an array supplied by main, rather than calling alloc to maintain storage. How much faster is the program?

5.7 Multi-dimensional Arrays

Consider the problem of date conversion, from day of the month to day of the year and vice versa. For example, March 1 is the 60th day of a non-leap year, and the 61st day of a leap year. Let us define two functions to do the conversions: day_of_year converts the month and day into the day of the year, and month_day converts the day of the year into the month and day. Since this latter function computes two values, the month and day arguments will be pointers:

   month_day(1988, 60, &m, &d)

These functions both need the same information, a table of the number of days in each month (``thirty days hath September ...''). Since the number of days per month differs for leap years and non-leap years, it's easier to separate them into two rows of a two-dimensional array than to keep track of what happens to February during computation. The array and the functions for performing the transformations are as follows:

   static char daytab[2][13] = {
       {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
       {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
   };

   /* day_of_year:  set day of year from month & day */
   int day_of_year(int year, int month, int day)
   {
       int i, leap;
       leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
       for (i = 1; i < month; i++)
           day += daytab[leap][i];
       return day;
   }

   /* month_day:  set month, day from day of year */
   void month_day(int year, int yearday, int *pmonth, int *pday)
   {
       int i, leap;

       leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
       for (i = 1; yearday > daytab[leap][i]; i++)
           yearday -= daytab[leap][i];
       *pmonth = i;
       *pday = yearday;
   }

The array daytab has to be external to both day_of_year and month_day, so they can both use it. We made it char to illustrate a legitimate use of char for storing small non-character integers.

daytab is the first two-dimensional array we have dealt with. In C, a two-dimensional array is really a one-dimensional array, each of whose elements is an array. Hence subscripts are written as

   daytab[i][j]    /* [row][col] */

   daytab[i,j]    /* WRONG */

An array is initialized by a list of initializers in braces; each row of a two-dimensional array is initialized by a corresponding sub-list. We started the array daytab with a column of zero so that month numbers can run from the natural 1 to 12 instead of 0 to 11. Since space is not at a premium here, this is clearer than adjusting the indices.

If a two-dimensional array is to be passed to a function, the parameter declaration in the function must include the number of columns; the number of rows is irrelevant, since what is passed is, as before, a pointer to an array of rows, where each row is an array of 13 ints. In this particular case, it is a pointer to objects that are arrays of 13 ints. Thus if the array daytab is to be passed to a function f, the declaration of f would be:

   f(int daytab[2][13]) { ... }

   f(int daytab[][13]) { ... }

   f(int (*daytab)[13]) { ... }

   int *daytab[13]

Section 5.12 has a further discussion of complicated declarations.

Exercise 5-8. There is no error checking in day_of_year or month_day. Remedy this defect.

5.8 Initialization of Pointer Arrays

The syntax is similar to previous initializations:

   /* month_name:  return name of n-th month */
   char *month_name(int n)
   {
       static char *name[] = {
           "Illegal month",
           "January", "February", "March",
           "April", "May", "June",
           "July", "August", "September",
           "October", "November", "December"
       };

       return (n < 1 || n > 12) ? name[0] : name[n];
   }

5.9 Pointers vs. Multi-dimensional Arrays

   int a[10][20];
   int *b[10];

Although we have phrased this discussion in terms of integers, by far the most frequent use of arrays of pointers is to store character strings of diverse lengths, as in the function month_name. Compare the declaration and picture for an array of pointers:

   char *name[] = { "Illegal month", "Jan", "Feb", "Mar" };

with those for a two-dimensional array:

   char aname[][15] = { "Illegal month", "Jan", "Feb", "Mar" };

Exercise 5-9. Rewrite the routines day_of_year and month_day with pointers instead of indexing.

5.10 Command-line Arguments

The simplest illustration is the program echo, which echoes its command-line arguments on a single line, separated by blanks. That is, the command

   echo hello, world

   hello, world

The first version of echo treats argv as an array of character pointers:

   #include <stdio.h>

   /* echo command-line arguments; 1st version */
   main(int argc, char *argv[])
   {
       int i;

       for (i = 1; i < argc; i++)
           printf("%s%s", argv[i], (i < argc-1) ? " " : "");
       printf("\n");
       return 0;
   }

   #include <stdio.h>

   /* echo command-line arguments; 2nd version */
   main(int argc, char *argv[])
   {
       while (--argc > 0)
           printf("%s%s", *++argv, (argc > 1) ? " " : "");
       printf("\n");
       return 0;
   }

Alternatively, we could write the printf statement as

   printf((argc > 1) ? "%s " : "%s", *++argv);

As a second example, let us make some enhancements to the pattern-finding program from Section 4.1. If you recall, we wired the search pattern deep into the program, an obviously unsatisfactory arrangement. Following the lead of the UNIX program grep, let us enhance the program so the pattern to be matched is specified by the first argument on the command line.

   #include <stdio.h>
   #include <string.h>
   #define MAXLINE 1000

   int getline(char *line, int max);

   /* find:  print lines that match pattern from 1st arg */
   main(int argc, char *argv[])
   {
       char line[MAXLINE];
       int found = 0;

       if (argc != 2)
           printf("Usage: find pattern\n");
       else
           while (getline(line, MAXLINE) > 0)
               if (strstr(line, argv[1]) != NULL) {
                   printf("%s", line);
                   found++;
               }
       return found;
   }

The model can now be elaborated to illustrate further pointer constructions. Suppose we want to allow two optional arguments. One says ``print all the lines except those that match the pattern;'' the second says ``precede each printed line by its line number.''

A common convention for C programs on UNIX systems is that an argument that begins with a minus sign introduces an optional flag or parameter. If we choose -x (for ``except'') to signal the inversion, and -n (``number'') to request line numbering, then the command

   find -x -npattern

Optional arguments should be permitted in any order, and the rest of the program should be independent of the number of arguments that we present. Furthermore, it is convenient for users if option arguments can be combined, as in

   find -nx pattern

   #include <stdio.h>
   #include <string.h>
   #define MAXLINE 1000

   int getline(char *line, int max);

   /* find: print lines that match pattern from 1st arg */
   main(int argc, char *argv[])
   {
       char line[MAXLINE];
       long lineno = 0;
       int c, except = 0, number = 0, found = 0;

       while (--argc > 0 && (*++argv)[0] == '-')
           while (c = *++argv[0])
               switch (c) {
               case 'x':
                   except = 1;
                   break;
               case 'n':
                   number = 1;
                   break;
               default:
                   printf("find: illegal option %c\n", c);
                   argc = 0;
                   found = -1;
                   break;
               }
       if (argc != 1)
           printf("Usage: find -x -n pattern\n");
       else
           while (getline(line, MAXLINE) > 0) {
               lineno++;
               if ((strstr(line, *argv) != NULL) != except) {
                   if (number)
                       printf("%ld:", lineno);
                   printf("%s", line);
                   found++;
               }
           }
       return found;
   }

It is rare that one uses pointer expressions more complicated than these; in such cases, breaking them into two or three steps will be more intuitive.

Exercise 5-10. Write the program expr, which evaluates a reverse Polish expression from the command line, where each operator or operand is a separate argument. For example,

   expr 2 3 4 + *

Exercise 5-11. Modify the program entab and detab (written as exercises in Chapter 1) to accept a list of tab stops as arguments. Use the default tab settings if there are no arguments.

Exercise 5-12. Extend entab and detab to accept the shorthand

   entab -m +n

Exercise 5-13. Write the program tail, which prints the last n lines of its input. By default, n is set to 10, let us say, but it can be changed by an optional argument so that

   tail -n

5.11 Pointers to Functions

A sort often consists of three parts - a comparison that determines the ordering of any pair of objects, an exchange that reverses their order, and a sorting algorithm that makes comparisons and exchanges until the objects are in order. The sorting algorithm is independent of the comparison and exchange operations, so by passing different comparison and exchange functions to it, we can arrange to sort by different criteria. This is the approach taken in our new sort.

Lexicographic comparison of two lines is done by strcmp, as before; we will also need a routine numcmp that compares two lines on the basis of numeric value and returns the same kind of condition indication as strcmp does. These functions are declared ahead of main and a pointer to the appropriate one is passed to qsort. We have skimped on error processing for arguments, so as to concentrate on the main issues.

   #include <stdio.h>
   #include <string.h>

   #define MAXLINES 5000     /* max #lines to be sorted */
   char *lineptr[MAXLINES];  /* pointers to text lines */

   int readlines(char *lineptr[], int nlines);
   void writelines(char *lineptr[], int nlines);

   void qsort(void *lineptr[], int left, int right,
              int (*comp)(void *, void *));
   int numcmp(char *, char *);

   /* sort input lines */
   main(int argc, char *argv[])
   {
       int nlines;        /* number of input lines read */
       int numeric = 0;   /* 1 if numeric sort */

       if (argc > 1 && strcmp(argv[1], "-n") == 0)
           numeric = 1;
       if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
           qsort((void**) lineptr, 0, nlines-1,
             (int (*)(void*,void*))(numeric ? numcmp : strcmp));
           writelines(lineptr, nlines);
           return 0;
       } else {
           printf("input too big to sort\n");
           return 1;
       }
   }

We have written qsort so it can process any data type, not just character strings. As indicated by the function prototype, qsort expects an array of pointers, two integers, and a function with two pointer arguments. The generic pointer type void * is used for the pointer arguments. Any pointer can be cast to void * and back again without loss of information, so we can call qsort by casting arguments to void *. The elaborate cast of the function argument casts the arguments of the comparison function. These will generally have no effect on actual representation, but assure the compiler that all is well.

   /* qsort:  sort v[left]...v[right] into increasing order */
   void qsort(void *v[], int left, int right,
              int (*comp)(void *, void *))
   {
       int i, last;

       void swap(void *v[], int, int);

       if (left >= right)    /* do  nothing if array contains */
           return;           /* fewer than two elements */
       swap(v, left, (left + right)/2);
       last = left;
       for (i = left+1; i <= right;  i++)
           if ((*comp)(v[i], v[left]) < 0)
               swap(v, ++last, i);
       swap(v, left, last);
       qsort(v, left, last-1, comp);
       qsort(v, last+1, right, comp);
   }

   int (*comp)(void *, void *)

The use of comp in the line

   if ((*comp)(v[i], v[left]) < 0)

   (*comp)(v[i], v[left])

   int *comp(void *, void *)    /* WRONG */

We have already shown strcmp, which compares two strings. Here is numcmp, which compares two strings on a leading numeric value, computed by calling atof:

   #include <stdlib.h>

   /* numcmp:  compare s1 and s2 numerically */
   int numcmp(char *s1, char *s2)
   {
       double v1, v2;

       v1 = atof(s1);
       v2 = atof(s2);
       if (v1 < v2)
           return -1;
       else if (v1 > v2)
           return 1;
       else
           return 0;
   }

   void swap(void *v[],  int i, int j;)
   {
       void *temp;

       temp = v[i];
       v[i] = v[j];
       v[j] = temp;
   }

Exercise 5-14. Modify the sort program to handle a -r flag, which indicates sorting in reverse (decreasing) order. Be sure that -r works with -n.

Exercise 5-15. Add the option -f to fold upper and lower case together, so that case distinctions are not made during sorting; for example, a and A compare equal.

Exercise 5-16. Add the -d (``directory order'') option, which makes comparisons only on letters, numbers and blanks. Make sure it works in conjunction with -f.

Exercise 5-17. Add a field-searching capability, so sorting may bee done on fields within lines, each field sorted according to an independent set of options. (The index for this book was sorted with -df for the index category and -n for the page numbers.)

5.12 Complicated Declarations

   int *f();       /* f: function returning pointer to int */

   int (*pf)();    /* pf: pointer to function returning int */ 

Although truly complicated declarations rarely arise in practice, it is important to know how to understand them, and, if necessary, how to create them. One good way to synthesize declarations is in small steps with typedef, which is discussed in Section 6.7. As an alternative, in this section we will present a pair of programs that convert from valid C to a word description and back again. The word description reads left to right.

The first, dcl, is the more complex. It converts a C declaration into a word description, as in these examples:

char **argv
    argv:  pointer to char
int (*daytab)[13]
    daytab:  pointer to array[13] of int
int *daytab[13]
    daytab:  array[13] of pointer to int
void *comp()
    comp: function returning pointer to void
void (*comp)()
    comp: pointer to function returning void
char (*(*x())[])()
    x: function returning pointer to array[] of
    pointer to function returning char
char (*(*x[3])())[5]
    x: array[3] of pointer to function returning
    pointer to array[5] of char

dcl:       optional *'s direct-dcl
direct-dcl name
                 (dcl)
                 direct-dcl()
                 direct-dcl[optional size]

This grammar can be used to parse functions. For instance, consider this declarator:

   (*pfa[])()

The heart of the dcl program is a pair of functions, dcl and dirdcl, that parse a declaration according to this grammar. Because the grammar is recursively defined, the functions call each other recursively as they recognize pieces of a declaration; the program is called a recursive-descent parser.

   /* dcl:  parse a declarator */
   void dcl(void)
   {
       int ns;

       for (ns = 0; gettoken() == '*'; ) /* count *'s */
           ns++;
       dirdcl();
       while (ns-- > 0)
           strcat(out, " pointer to");
   }

   /* dirdcl:  parse a direct declarator */
   void dirdcl(void)
   {
       int type;

       if (tokentype == '(') {         /* ( dcl ) */
           dcl();
           if (tokentype != ')')
               printf("error: missing )\n");
       } else if (tokentype == NAME)  /* variable name */
           strcpy(name, token);
       else
           printf("error: expected name or (dcl)\n");
       while ((type=gettoken()) == PARENS || type == BRACKETS)
           if (type == PARENS)
               strcat(out, " function returning");
           else {
               strcat(out, " array");
               strcat(out, token);
               strcat(out, " of");
           }
   }

Here are the global variables and the main routine:

   #include <stdio.h>
   #include <string.h>
   #include <ctype.h>

   #define MAXTOKEN  100

   enum { NAME, PARENS, BRACKETS };

   void dcl(void);
   void dirdcl(void);

   int gettoken(void);
   int tokentype;           /* type of last token */
   char token[MAXTOKEN];    /* last token string */
   char name[MAXTOKEN];     /* identifier name */
   char datatype[MAXTOKEN]; /* data type = char, int, etc. */
   char out[1000];

   main()  /* convert declaration to words */
   {
       while (gettoken() != EOF) {   /* 1st token on line */
           strcpy(datatype, token);  /* is the datatype */
           out[0] = '\0';
           dcl();       /* parse rest of line */
           if (tokentype != '\n')
               printf("syntax error\n");
           printf("%s: %s %s\n", name, out, datatype);
       }
       return 0;
   }

   int gettoken(void)  /* return next token */
   {
       int c, getch(void);
       void ungetch(int);
       char *p = token;

       while ((c = getch()) == ' ' || c == '\t')
           ;
       if (c == '(') {
           if ((c = getch()) == ')') {
               strcpy(token, "()");
               return tokentype = PARENS;
           } else {
               ungetch(c);
               return tokentype = '(';
           }
       } else if (c == '[') {
           for (*p++ = c; (*p++ = getch()) != ']'; )
               ;
           *p = '\0';
           return tokentype = BRACKETS;
       } else if (isalpha(c)) {
           for (*p++ = c; isalnum(c = getch()); )
               *p++ = c;
           *p = '\0';
           ungetch(c);
           return tokentype = NAME;
       } else
           return tokentype = c;

   }

Going in the other direction is easier, especially if we do not worry about generating redundant parentheses. The program undcl converts a word description like ``x is a function returning a pointer to an array of pointers to functions returning char,'' which we will express as

    x () * [] * () char

   char (*(*x())[])()

   /* undcl:  convert word descriptions to declarations */
   main()
   {
       int type;
       char temp[MAXTOKEN];

       while (gettoken() != EOF) {
           strcpy(out, token);
           while ((type = gettoken()) != '\n')
               if (type == PARENS || type == BRACKETS)
                   strcat(out, token);
               else if (type == '*') {
                   sprintf(temp, "(*%s)", out);
                   strcpy(out, temp);
               } else if (type == NAME) {
                   sprintf(temp, "%s %s", token, out);
                   strcpy(out, temp);
               } else
                   printf("invalid input at %s\n", token);
       }
       return 0;
   }

Exercise 5-19. Modify undcl so that it does not add redundant parentheses to declarations.

Exercise 5-20. Expand dcl to handle declarations with function argument types, qualifiers like const, and so on.

Back to Chapter 4 --  Index --  Chapter 6