chapter5.html

Kernighan and Ritchie - The C Programming Language c程序设计语言（第二版）称作是C语言学习的圣经

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

       for (n = 0; *s != '\0', s++)
           n++;
       return n;
   }
</pre>
Since <tt>s</tt> is a pointer, incrementing it is perfectly legal; <tt>s++</tt> has
no effect on the character string in the function that called <tt>strlen</tt>,
but merely increments <tt>strlen</tt>'s private copy of the pointer. That means
that calls like
<pre>
   strlen("hello, world");   /* string constant */
   strlen(array);            /* char array[100]; */
   strlen(ptr);              /* char *ptr; */
</pre>
all work.
<p>
As formal parameters in a function definition,
<pre>
   char s[];
</pre>
and
<pre>
   char *s;
</pre>
are equivalent; we prefer the latter because it says more explicitly that the
variable is a pointer. When an array name is passed to a function, the
function can at its convenience believe that it has been handed either an
array or a pointer, and manipulate it accordingly. It can even use both
notations if it seems appropriate and clear.
<p>
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 <tt>a</tt> is an array,
<pre>
   f(&a[2])
</pre>
and
<pre>
   f(a+2)
</pre>
both pass to the function <tt>f</tt> the address of the subarray that starts at
<tt>a[2]</tt>. Within <tt>f</tt>, the parameter declaration can read
<pre>
   f(int arr[]) { ... }
</pre>
or
<pre>
   f(int *arr) { ... }
</pre>
So as far as <tt>f</tt> is concerned, the fact that the parameter refers to part
of a larger array is of no consequence.
<p>
If one is sure that the elements exist, it is also possible to index
backwards in an array; <tt>p[-1]</tt>, <tt>p[-2]</tt>, and so on are syntactically
legal, and refer to the elements that immediately precede <tt>p[0]</tt>. Of
course, it is illegal to refer to objects that are not within the array
bounds.

<h2><a name="s5.4">5.4 Address Arithmetic</a></h2>
If <tt>p</tt> is a pointer to some element of an array, then <tt>p++</tt>
increments <tt>p</tt> to point to the next element, and <tt>p+=i</tt>
increments it to point <tt>i</tt> elements beyond where it currently does.
These and similar constructions are the simples forms of pointer or address
arithmetic.
<p>
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, <tt>alloc(n)</tt>, returns a
pointer to <tt>n</tt> consecutive character positions, which can be used by
the caller of <tt>alloc</tt> for storing characters. The second,
<tt>afree(p)</tt>, releases the storage thus acquired so it can be re-used
later. The routines are ``rudimentary'' because the calls to <tt>afree</tt>
must be made in the opposite order to the calls made on <tt>alloc</tt>. That
is, the storage managed by <tt>alloc</tt> and <tt>afree</tt> is a stack, or
last-in, first-out. The standard library provides analogous functions called
<tt>malloc</tt> and <tt>free</tt> that have no such restrictions; in
<a href="chapter8.html#s8.7">Section 8.7</a> we will show how they can be
implemented.
<p>
The easiest implementation is to have <tt>alloc</tt> hand out pieces of a
large character array that we will call <tt>allocbuf</tt>. This array is
private to <tt>alloc</tt> and <tt>afree</tt>. Since they deal in pointers,
not array indices, no other routine need know the name of the array, which
can be declared <tt>static</tt> in the source file containing <tt>alloc</tt>
and <tt>afree</tt>, 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 <tt>malloc</tt> or by asking the operating system for a
pointer to some unnamed block of storage.
<p>
The other information needed is how much of <tt>allocbuf</tt> has been used.
We use a pointer, called <tt>allocp</tt>, that points to the next free
element. When <tt>alloc</tt> is asked for <tt>n</tt> characters, it checks to
see if there is enough room left in <tt>allocbuf</tt>. If so, <tt>alloc</tt>
returns the current value of <tt>allocp</tt> (i.e., the beginning of the free
block), then increments it by <tt>n</tt> to point to the next free area. If
there is no room, <tt>alloc</tt> returns zero. <tt>afree(p)</tt> merely sets
<tt>allocp</tt> to <tt>p</tt> if <tt>p</tt> is inside <tt>allocbuf</tt>.
<p align="center">
<img src="pic56.gif">
<p>
<pre>
   #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 &gt;= 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 &gt;= allocbuf && p &lt; allocbuf + ALLOCSIZE)
           allocp = p;
   }
</pre>
In general a pointer can be initialized just as any other variable can,
though normally the only meaningful values are zero or an expression
involving the address of previously defined data of appropriate type. The
declaration
<pre>
   static char *allocp = allocbuf;
</pre>
defines <tt>allocp</tt> to be a character pointer and initializes it to point to
the beginning of <tt>allocbuf</tt>, which is the next free position when the
program starts. This could also have been written
<pre>
   static char *allocp = &allocbuf[0];
</pre>
since the array name <em>is</em> the address of the zeroth element.
<p>
The test
<pre>
       if (allocbuf + ALLOCSIZE - allocp &gt;= n) {  /* it fits */
</pre>
checks if there's enough room to satisfy a request for <tt>n</tt> characters. If
there is, the new value of <tt>allocp</tt> would be at most one beyond the end
of <tt>allocbuf</tt>. If the request can be satisfied, <tt>alloc</tt> returns a
pointer to the beginning of a block of characters (notice the declaration of
the function itself). If not, <tt>alloc</tt> must return some signal that there
is no space left. C guarantees that zero is never a valid address for data,
so a return value of zero can be used to signal an abnormal event, in this
case no space.
<p>
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 <tt>NULL</tt> is often used in
place of zero, as a mnemonic to indicate more clearly that this is a special
value for a pointer. <tt>NULL</tt> is defined in <tt>&lt;stdio.h&gt;</tt>. We
will use <tt>NULL</tt> henceforth.
<p>
Tests like
<pre>
       if (allocbuf + ALLOCSIZE - allocp &gt;= n) {  /* it fits */
</pre>
and
<pre>
       if (p &gt;= allocbuf && p &lt; allocbuf + ALLOCSIZE)
</pre>
show several important facets of pointer arithmetic. First, pointers may be
compared under certain circumstances. If <tt>p</tt> and <tt>q</tt> point to
members of the same array, then relations like <tt>==</tt>, <tt>!=</tt>,
<tt>&lt;</tt>, <tt>&gt;=</tt>, etc., work properly. For example,
<pre>
   p &lt; q
</pre>
is true if <tt>p</tt> points to an earlier element of the array than <tt>q</tt>
does. Any pointer can be meaningfully compared for equality or inequality
with zero. But the behavior is undefined for arithmetic or comparisons with
pointers that do not point to members of the same array. (There is one
exception: the address of the first element past the end of an array can be
used in pointer arithmetic.)
<p>
Second, we have already observed that a pointer and an integer may be added
or subtracted. The construction
<pre>
   p + n
</pre>
means the address of the <tt>n</tt>-th object beyond the one <tt>p</tt>
currently points to. This is true regardless of the kind of object <tt>p</tt>
points to; <tt>n</tt> is scaled according to the size of the objects
<tt>p</tt> points to, which is determined by the declaration of <tt>p</tt>.
If an <tt>int</tt> is four bytes, for example, the <tt>int</tt> will be
scaled by four.
<p>
Pointer subtraction is also valid: if <tt>p</tt> and <tt>q</tt> point to
elements of the same array, and <tt>p&lt;q</tt>, then <tt>q-p+1</tt> is the
number of elements from <tt>p</tt> to <tt>q</tt> inclusive. This fact can be
used to write yet another version of <tt>strlen</tt>:
<pre>
   /* strlen:  return length of string s */
   int strlen(char *s)
   {
       char *p = s;

       while (*p != '\0')
           p++;
       return p - s;
   }
</pre>
In its declaration, <tt>p</tt> is initialized to <tt>s</tt>, that is, to
point to the first character of the string. In the <tt>while</tt> loop, each
character in turn is examined until the <tt>'\0'</tt> at the end is seen.
Because <tt>p</tt> points to characters, <tt>p++</tt> advances <tt>p</tt> to
the next character each time, and <tt>p-s</tt> gives the number of characters
advanced over, that is, the string length. (The number of characters in the
string could be too large to store in an <tt>int</tt>. The header
<tt>&lt;stddef.h&gt;</tt> defines a type <tt>ptrdiff_t</tt> that is large
enough to hold the signed difference of two pointer values. If we were being
cautious, however, we would use <tt>size_t</tt> for the return value of
<tt>strlen</tt>, to match the standard library version. <tt>size_t</tt> is
the unsigned integer type returned by the <tt>sizeof</tt> operator.
<p>
Pointer arithmetic is consistent: if we had been dealing with
<tt>float</tt>s, which occupy more storage that <tt>char</tt>s, and if
<tt>p</tt> were a pointer to <tt>float</tt>, <tt>p++</tt> would advance to
the next <tt>float</tt>. Thus we could write another version of
<tt>alloc</tt> that maintains <tt>float</tt>s instead of <tt>char</tt>s,
merely by changing <tt>char</tt> to <tt>float</tt> throughout <tt>alloc</tt>
and <tt>afree</tt>. All the pointer manipulations automatically take into
account the size of the objects pointed to.
<p>
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
<tt>float</tt> or <tt>double</tt> to them, or even, except for <tt>void *</tt>,
to assign a pointer of one type to a pointer of another type without a cast.

<h2><a name="s5.5">5.5 Character Pointers and Functions</a></h2>
A <em>string constant</em>, written as
<pre>
   "I am a string"
</pre>
is an array of characters. In the internal representation, the array is
terminated with the null character <tt>'\0'</tt> so that programs can find
the end. The length in storage is thus one more than the number of characters
between the double quotes.
<p>
Perhaps the most common occurrence of string constants is as arguments to
functions, as in
<pre>
   printf("hello, world\n");
</pre>
When a character string like this appears in a program, access to it is
through a character pointer; <tt>printf</tt> receives a pointer to the beginning
of the character array. That is, a string constant is accessed by a pointer
to its first element.
<p>
String constants need not be function arguments. If <tt>pmessage</tt> is
declared as
<pre>
   char *pmessage;
</pre>
then the statement
<pre>
   pmessage = "now is the time";
</pre>
assigns to <tt>pmessage</tt> a pointer to the character array. This is
<em>not</em> a string copy; only pointers are involved. C does not provide
any operators for processing an entire string of characters as a unit.
<p>
There is an important difference between these definitions:
<pre>
   char amessage[] = "now is the time"; /* an array */
   char *pmessage = "now is the time"; /* a pointer */
</pre>
<tt>amessage</tt> is an array, just big enough to hold the sequence of
characters and <tt>'\0'</tt> that initializes it. Individual characters within
the array may be changed but <tt>amessage</tt> will always refer to the same
storage. On the other hand, <tt>pmessage</tt> is a pointer, initialized to point
to a string constant; the pointer may subsequently be modified to point
elsewhere, but the result is undefined if you try to modify the string
contents.
<p align="center">
<img src="pic57.gif">
<p>
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 <tt>strcpy(s,t)</tt>, which copies the string <tt>t</tt> to the string <tt>s</tt>.
It would be nice just to say <tt>s=t</tt> but this copies the pointer, not the
characters. To copy the characters, we need a loop. The array version first:
<pre>
   /* 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++;
   }
</pre>
For contrast, here is a version of <tt>strcpy</tt> with pointers:
<pre>
   /* strcpy:  copy t to s; pointer version */
   void strcpy(char *s, char *t)
   {
       int i;

       i = 0;
       while ((*s = *t) != '\0') {
           s++;
           t++;
       }
   }
</pre>
Because arguments are passed by value, <tt>strcpy</tt> can use the parameters
<tt>s</tt> and <tt>t</tt> in any way it pleases. Here they are conveniently
initialized pointers, which are marched along the arrays a character at a
time, until the <tt>'\0'</tt> that terminates <tt>t</tt> has been copied into
<tt>s</tt>.
<p>
In practice, <tt>strcpy</tt> would not be written as we showed it above.
Experienced C programmers would prefer
<pre>
   /* strcpy:  copy t to s; pointer version 2 */