Mini-Unix/usr/doc/c/c6
.ul
16. Examples.
.et
These examples are intended to illustrate
some typical C constructions as well as
a serviceable style of writing C programs.
.ms
16.1 Inner product
.et
This function returns the inner product of
its array arguments.
.sp .7
.nf
.bG
double inner^(^v1, v2, n^)^
double v1^[^^]^, v2^[^^]^;
{
double sum^;
int i^;
sum = 0.0^;
for ^(^i=0^; i<n^; i\fR++\fG^)^
sum \fR=+\fG v1^[^i^] \** v2^[^i^]^;
return^(^sum^)^;
}
.fi
.eG
.sp .7
The following version is somewhat more efficient,
but perhaps a little less clear.
It uses the facts that parameter arrays are
really pointers, and that all parameters are passed
by value.
.sp .7
.nf
.bG
double inner^(^v1, v2, n^)^
double \**v1, \**v2^;
{
double sum^;
sum = 0.0^;
while^(^n\fR\fR\(mi\(mi\fG\fG^)^
sum \fR=+\fG \**v1\fR++\fG \** \**v2\fR++\fG^;
return^(^sum^)^;
}
.fi
.eG
.sp .7
The declarations for the parameters are really exactly
the same as in the last example.
In the first case array declarations ``^[^^^]^'' were given
to emphasize that the parameters would be referred
to as arrays; in the second, pointer declarations
were given because the indirection operator and
++ were used.
.ms
16.2 Tree and character processing
.et
Here is a complete C program
^(^courtesy of R. Haight^)^ which reads a document
and produces an alphabetized list of words
found therein together with
the number of occurrences of each word.
The method keeps a binary tree of words
such that the left descendant tree for
each word has all the words lexicographically smaller than
the given word,
and the right descendant has all the larger
words.
Both the insertion and the printing routine
are recursive.
.pg
The program calls the library routines \fIgetchar\fR to
pick up characters
and \fIexit\fR to terminate execution.
\fIPrintf\fR is called to print
the results according to a format
string.
A version of
\fIprintf\fR is given below ^(^\(sc16.3^)^.
.pg
Because all the external definitions for
data are given at the top, no \fGextern\fR
declarations are necessary within the functions.
To stay within the rules, a type declaration
is given for each non-integer function
when the function is used before
it is defined.
However, since all such
functions return pointers which are
simply assigned to other pointers,
no actual harm would result from
leaving out the declarations; the
supposedly \fGint\fR function values would be assigned
without error or complaint.
.sp .7
.nf
.in .5i
.bG
.ta .5i 1i 3i
# define nwords 100 /\** number of different words \**/
# define wsize 20 /\** max chars per word \**/
struct tnode { /\** the basic structure \**/
char tword^[^wsize^]^;
int count^;
struct tnode \**left^;
struct tnode \**right^;
}^;
.sp .7
struct tnode space^[^nwords^]^; /\** the words themselves \**/
int nnodes nwords^; /\** number of remaining slots \**/
struct tnode \**spacep space^; /\** next available slot \**/
struct tnode \**freep^; /\** free list \**/
/\**
\** The main routine reads words until end-of-file \
^(^\(aa\\0\(aa returned from "getchar"^)^
\** "tree" is called to sort each word into the tree.
\**/
.ta .5i 1i 1.5i 2i 2.5i 3i
main^(^^)^
{
struct tnode \**top, \**tree^(^^)^;
char c, word^[^wsize^]^;
int i^;
.sp .5
i = top = 0^;
while ^(^c=getchar^(^^)^^)^
if ^(^\(aaa\(aa<=c && c<=\(aaz\(aa \(or\(or \(aaA\(aa<=c && c <=\(aaZ\(aa^)^ {
if ^(^i<wsize\(mi1^)^
word^[^i\fR++\fG^]^ = c^;
} else
if ^(^i^)^ {
word^[^i\fR++\fG^]^ = \(aa\\0\(aa^;
top = tree^(^top, word^)^;
i = 0^;
}
tprint^(^top^)^;
}
/\**
\** The central routine. If the subtree pointer is null, \
allocate a new node for it.
\** If the new word and the node\(aas word are the same, increase \
the node\(aas count.
\** Otherwise, recursively sort the word into the left or right subtree according
\** as the argument word is less or greater \
than the node\(aas word.
\**/
struct tnode \**tree^(^p, word^)^
struct tnode \**p^;
char word^[^^]^;
{
struct tnode \**alloc^(^^)^;
int cond^;
.sp .5
/\** Is pointer null? \**/
if ^(^p\fR==\fG0^)^ {
p = alloc^(^^)^;
copy^(^word, p\(mi>tword^)^;
p\(mi>count = 1^;
p\(mi>right = p\(mi>left = 0^;
return^(^p^)^;
}
/\** Is word repeated? \**/
if ^(^^(^cond=compar^(^p\(mi>tword, word^)^^)^ \fR==\fG 0^)^ {
p\(mi>count\fR++\fG^;
return^(^p^)^;
}
/\** Sort into left or right \**/
if ^(^cond<0^)^
p\(mi>left = tree^(^p\(mi>left, word^)^;
else
p\(mi>right = tree^(^p\(mi>right, word^)^;
return^(^p^)^;
}
/\**
\** Print the tree by printing the left subtree, the \
given node, and the right subtree.
\**/
tprint^(^p^)^
struct tnode \**p^;
{
while ^(^p^)^ {
tprint^(^p\(mi>left^)^;
printf^(^"%d: %s\\n", p\(mi>count, p\(mi>tword^)^;
p = p\(mi>right^;
}
}
/\**
\** String comparison: return number ^(^>, =, <^)^ 0
\** according as s1 ^(^>, =, <^)^ s2.
\**/
compar^(^s1, s2^)^
char \**s1, \**s2^;
{
int c1, c2^;
.sp .5
while^(^^(^c1 = \**s1\fR++\fG^)^ \fR==\fG ^(^c2 = \**s2\fR++\fG^)^^)^
if ^(^c1\fR==\fG\(aa\\0\(aa^)^
return^(^0^)^;
return^(^c2\(mic1^)^;
}
/\**
\** String copy: copy s1 into s2 until the null
\** character appears.
\**/
copy^(^s1, s2^)^
char \**s1, \**s2^;
{
while^(^\**s2\fR++\fG = \**s1\fR++\fG^)^;
}
/\**
\** Node allocation: return pointer to a free node.
\** Bomb out when all are gone. Just for fun, there
\** is a mechanism for using nodes that have been
\** freed, even though no one here calls "free."
\**/
struct tnode \**alloc^(^^)^
{
struct tnode \**t^;
.sp .5
if ^(^freep^)^ {
t = freep^;
freep = freep\(mi>left^;
return^(^t^)^;
}
if ^(^\fR\(mi\(mi\fGnnodes < 0^)^ {
printf^(^"Out of space\\n"^)^;
exit^(^^)^;
}
return^(^spacep\fR++\fG^)^;
}
/\**
\** The uncalled routine which puts a node on the free list.
\**/
free^(^p^)^
struct tnode \**p^;
{
p\(mi>left = freep^;
freep = p^;
}
.sp .7
.fi
.eG
.in 0
To illustrate a slightly different technique of
handling the same problem, we will repeat
fragments of this example with the tree nodes
treated explicitly as members of an array.
The fundamental change is to
deal with the subscript
of the array member under
discussion, instead of a pointer to it.
The \fGstruct\fR declaration becomes
.sp .7
.nf
.bG
struct tnode {
char tword^[^wsize^]^;
int count;
int left;
int right;
};
.fi
.eG
.sp .7
and \fIalloc\fR becomes
.sp .7
.nf
.bG
alloc^(^^)^
{
int t;
.sp .5
t = \fR\(mi\(mi\fGnnodes;
if ^(^t<=0^)^ {
printf^(^"Out of space\\n"^)^;
exit^(^^)^;
}
return^(^t^)^;
}
.fi
.eG
.sp .7
The \fIfree\fR stuff has disappeared because
if we deal with exclusively with
subscripts some sort of map has
to be kept, which is too much trouble.
.pg
Now the \fItree\fR routine returns
a subscript also, and it becomes:
.sp .7
.nf
.bG
tree^(^p, word^)^
char word^[^^]^;
{
int cond;
.sp .5
if ^(^p\fR==\fG0^)^ {
p = alloc^(^^)^;
copy^(^word, space^[^p^]^.tword^)^;
space^[^p^]^.count = 1;
space^[^p^]^.right = space^[^p^]^.left = 0;
return^(^p^)^;
}
if ^(^^(^cond=compar^(^space^[^p^]^.tword, word^)^^)^ \fR==\fG 0^)^ {
space^[^p^]^.count\fR++\fG;
return^(^p^)^;
}
if ^(^cond<0^)^
space^[^p^]^.left = tree^(^space^[^p^]^.left, word^)^;
else
space^[^p^]^.right = tree^(^space^[^p^]^.right, word^)^;
return^(^p^)^;
}
.fi
.eG
.sp .7
The other routines are changed similarly.
It must be pointed out that
this version is noticeably
less efficient than the first because
of the multiplications which
must be done
to compute an offset in \fIspace\fR
corresponding to the subscripts.
.pg
The observation that subscripts
^(^like ``a^[^i^]^''^)^ are less efficient
than pointer indirection ^(^like ``\**ap''^)^
holds true independently of whether or not
structures are involved.
There are of course many situations where subscripts
are indispensable, and others where the loss
in efficiency is worth a gain in clarity.
.ms
16.3 Formatted output
.et
Here is a simplified version of the \fIprintf\fR routine, which is
available in the C library.
It accepts a string ^(^character array^)^
as first argument, and prints subsequent arguments
according to specifications contained in
this format string.
Most characters in the string are simply
copied to the output; two-character sequences beginning
with ``%'' specify that the next argument
should be printed in a style as follows:
.sp .7
.nf
%d decimal number
%o octal number
%c \s8ASCII\s10 character, or 2 characters if \
upper character is not null
%s string ^(^null-terminated array of characters^)
%f floating-point number
.sp .7
.fi
The actual parameters for each function
call are laid out contiguously in
increasing storage locations;
therefore, a function with a variable number
of arguments
may take the address of ^(^say^)^ its first argument,
and access the remaining arguments by use
of subscripting ^(^regarding the arguments
as an array^)^
or by indirection combined with
pointer incrementation.
.pg
If in such a situation
the arguments have mixed types, or if in general
one wishes to insist that an lvalue should
be treated as having a given type, then
\fGstruct\fR declarations like those illustrated below
will be useful.
It should be evident, though,
that such techniques are implementation dependent.
.pg
\fIPrintf\fR depends as well on the fact that
\fGchar\fR and \fGfloat\fR arguments
are widened respectively to \fGint\fR and \fGdouble\fR,
so there are effectively only two sizes of arguments
to deal with.
\fIPrintf\fR calls the library routines
\fIputchar\fR to write out single characters
and \fIftoa\fR to dispose of
floating-point numbers.
.sp .7
.in .5i
.bG
.nf
printf^(^fmt, args^)^
char fmt^[^^]^;
{
char \**s^;
struct { char \**\**charpp^; };
struct { double \**doublep^; };
int \**ap, x, c^;
.sp .5
ap = &args^; /\** argument pointer \**/
for ( ; ; ) {
while^(^^(^c = \**fmt\fR++\fG^)^ != \(aa%\(aa^)^ {
if^(^c \fR==\fG \(aa\\0\(aa^)^
return^;
putchar^(^c^)^;
}
switch ^(^c = \**fmt\fR++\fG^)^ {
/\** decimal \**/
case \(aad^\(aa:
x = \**ap\fR++\fG^;
if^(^x < 0^)^ {
x = \(mix^;
if^(^x<0^)^ { /\** is \(mi infinity \**/
printf^(^"\(mi32768"^)^;
continue^;
}
putchar^(^\(aa\(mi\(aa^)^;
}
printd^(^x^)^;
continue^;
/\** octal \**/
case \(aao\(aa:
printo^(^\**ap\fR++\fG^)^;
continue^;
/\** float, double \**/
case ^^\(aaf^\(aa:
/\** let ftoa do the real work \**/
ftoa^(^\**ap.doublep\fR++\fG^)^;
continue^;
/\** character \**/
case \(aac\(aa:
putchar^(^\**ap\fR++\fG^)^;
continue^;
/\** string \**/
case \(aas\(aa:
s = \**ap.charpp\fR++\fG^;
while^(^c = \**s\fR++\fG^)^
putchar^(^c^)^;
continue^;
}
putchar^(^c^)^;
}
}
/\**
\** Print n in decimal^; n must be non-negative
\**/
printd^(^n^)^
{
int a^;
if ^(^a=n/10^)^
printd^(^a^)^;
putchar^(^n%10 + \(aa0\(aa^)^;
}
/\**
\** Print n in octal, with exactly 1 leading 0
\**/
printo^(^n^)^
{
if ^(^n^)^
printo^(^^(^n>>3^)^&017777^)^;
putchar^(^^(^n&07^)^+\(aa0\(aa^)^;
}
.br
.fi
.eG
.in 0