28. wordtree, twice
An adagio that knows how it ends: Mahler's Ninth spends its last page taking things away, and the silence at the bottom is the piece.
This is the sharpest contrast in the book, and the reason is that K&R §6.5
is not really about a tree. It is about malloc. The tree is the shape
the chapter needed in order to have something to allocate, and the lesson
underneath it — every allocation is yours, every pointer can be null,
every malloc has a free somewhere with your name on it — is the lesson
C had to teach because C had no other option.
wordtree counts how many times each word appears in its input and prints
the tally in alphabetical order. Both columns build a binary search tree
to do it, both walk it in order, and one of them frees it.
28.1 The malloc showpiece
The twin, whole. First the node, the declarations, and the flag that carries a failure a pointer-returning function cannot return:
/* wordtree --- count the occurrences of each input word, alphabetized.
*
* An ORIGINAL implementation, written after the manner of Kernighan and
* Ritchie, "The C Programming Language", 2nd ed., section 6.5. The
* addtree/treeprint/talloc division of labor and the recursive in-order
* walk are their teaching shape; the code below is ours, and no listing
* from that book is reproduced here. See PERMISSIONS.md.
*
* The side-by-side's subject is allocation. Every node here is a
* separate malloc, every word is a second one, every one of them can
* fail, and the program owns a matching free for each --- treefree at
* the bottom of this file exists only because malloc was called at the
* top. The original stops before writing it, which is honest about
* chapter 6's scope and is also how the leak gets into production.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAXWORD 100
struct tnode { /* one distinct word */
char *word; /* the text, separately allocated */
int count; /* how many times it has been seen */
struct tnode *left; /* words alphabetically before it */
struct tnode *right; /* words alphabetically after it */
};
static struct tnode *addtree(struct tnode *p, const char *w);
static void treeprint(const struct tnode *p);
static void treefree(struct tnode *p);
static struct tnode *talloc(void);
static char *dupstr(const char *s);
static int getword(char *word, int lim);
/* Every allocating routine can fail, so every caller has to look. The
* flag is how a recursive function reports a failure it cannot return. */
static int nomem = 0;
Then addtree, which is the section:
/* Add w to the tree at p, or bump its count. Returns the (possibly new)
* subtree root. On allocation failure it sets `nomem` and returns what
* it was given --- the only channel a pointer-returning function has. */
static struct tnode *addtree(struct tnode *p, const char *w)
{
int cond;
if (p == NULL) { /* a word not seen before */
p = talloc();
if (p == NULL) {
nomem = 1;
return NULL;
}
p->word = dupstr(w);
if (p->word == NULL) {
free(p); /* the half-built node must not leak */
nomem = 1;
return NULL;
}
p->count = 1;
p->left = NULL;
p->right = NULL;
} else if ((cond = strcmp(w, p->word)) == 0)
++p->count; /* repeated word */
else if (cond < 0)
p->left = addtree(p->left, w);
else
p->right = addtree(p->right, w);
return p;
}
Count the ways that function can fail and what each one costs. talloc
can return null, so there is a test. dupstr can return null, so there is
a second test — and by the time it fails, a node has already been
allocated, so the second test also has to free(p) before it reports, or
the failure leaks the node it was in the middle of building. addtree
returns a struct tnode *, and its return value is the new subtree root,
so it has no way to report the failure at all; that is what nomem is
for, and main has to check it after every word.
Eleven mentions of NULL in this file. Five mentions of nomem. Two
malloc call sites, which is two allocations for every new word — one for
the node, one for a copy of the text, because the text was in a stack
buffer that the next word is about to overwrite.
Then the walk, the other half of every malloc, and the two allocators:
/* In-order walk: left subtree, this node, right subtree. Alphabetical
* because the tree was built by strcmp. */
static void treeprint(const struct tnode *p)
{
if (p != NULL) {
treeprint(p->left);
printf("%4d %s\n", p->count, p->word);
treeprint(p->right);
}
}
/* The other half of every malloc above. Post-order, because a node's
* children must be freed before the node that points at them. */
static void treefree(struct tnode *p)
{
if (p != NULL) {
treefree(p->left);
treefree(p->right);
free(p->word);
free(p);
}
}
static struct tnode *talloc(void)
{
return (struct tnode *) malloc(sizeof(struct tnode));
}
static char *dupstr(const char *s)
{
char *p;
p = (char *) malloc(strlen(s) + 1);
if (p != NULL)
strcpy(p, s);
return p;
}
treeprint is 8 lines and it is the algorithm: left, self, right, and the
output comes out sorted because strcmp put it in. treefree is 9 lines
and it is not the algorithm at all. It exists because talloc and dupstr
exist. It has to be post-order — a node’s children must go before the node
that points at them — and getting that backwards is a use-after-free that
will not show up in testing.
Ritchie’s own version stops before writing treefree, and that is honest
about chapter 6’s scope. It is also, as our twin’s header comment says, how
the leak gets into production.
And the tokenizer and main:
/* Read the next alphabetic word into word[0..lim-1]. Returns the first
* character of the word, EOF, or the non-word character it found. */
static int getword(char *word, int lim)
{
int c;
char *w;
w = word;
while ((c = getchar()) != EOF && !isalpha(c) && c != '\n')
;
if (c == EOF) {
*w = '\0';
return EOF;
}
if (!isalpha(c)) {
*w++ = (char) c;
*w = '\0';
return c;
}
*w++ = (char) tolower(c);
for (; --lim > 1; w++) {
c = getchar();
if (!isalpha(c)) {
if (c != EOF)
ungetc(c, stdin);
break;
}
*w = (char) tolower(c);
}
*w = '\0';
return word[0];
}
int main(void)
{
struct tnode *root;
char word[MAXWORD];
int t;
root = NULL;
while ((t = getword(word, MAXWORD)) != EOF) {
if (isalpha(t))
root = addtree(root, word);
if (nomem) {
fprintf(stderr, "wordtree: out of memory\n");
treefree(root);
return 1;
}
}
treeprint(root);
treefree(root); /* the closing brace C does not have */
return 0;
}
Run it:
$ ./wordtree
1 moon
1 runs
3 the
1 watches
2 wolf
$ ./wordtree
3 wolf
28.2 The tree in a region
Here is the wolf node, and the two functions that build the tree:
struct Node { word: str, count: int, left: List[Node], right: List[Node] }
fn leaf(w: str) -> Node {
Node { word: w, count: 1, left: List[Node](), right: List[Node]() }
}
fn add(mut n: Node, w: str) {
if w == n.word {
n.count += 1
} else if w < n.word {
if n.left.is_empty() {
(mut n.left).push(leaf(w))
} else {
add(mut n.left[0], w)
}
} else {
if n.right.is_empty() {
(mut n.right).push(leaf(w))
} else {
add(mut n.right[0], w)
}
}
}
Two things to read there, and the first one is a word that is missing.
There is no NULL. A child that is not there is a List[Node] with
nothing in it, and n.left.is_empty() is the test. That is the same test
p == NULL was, spelled as a question about a container rather than about
a number that is allowed to be an address. It cannot be dereferenced by
accident, because there is nothing to dereference: reading n.left[0]
when the list is empty is a checked index and a bounds trap, which is
chapter 5’s contract holding at the bottom of a data structure.
And there is no allocation to check. leaf builds a Node; push puts it
in a list; the list grows its buffer. Every one of those steps allocates,
and not one of them can hand back a failure the program has to test,
because a wolf allocation that cannot be satisfied is not a value the
program gets to see. talloc, dupstr, the two NULL tests, the
free(p) on the half-built node, and nomem with its five mentions are
all gone, together, and they are gone for one reason: the failure they
guarded against is not reportable in this language.
add is 17 lines of code against addtree’s 26, and the nine-line
difference is exactly the allocation bookkeeping — the two null tests, the
two nomem sets, the two early returns, and the free. The recursive
descent, the three-way comparison and the count bump are the same in both
columns, because they are the algorithm.
Note the comparison itself. w < n.word on two str values is the
byte-lexicographic order strcmp computes, and it is an operator rather
than a call, so the three-way branch reads as a three-way branch.
28.3 Counting words
The walk, and then the whole program:
fn walk(n: Node) {
if !n.left.is_empty() { walk(n.left[0]) }
print("{n.count:>4} {n.word}")
if !n.right.is_empty() { walk(n.right[0]) }
}
Five lines, and the same five ideas as treeprint’s eight: left, self,
right, with a guard on each side. {n.count:>4} {n.word} is %4d %s.
Now the driver, and the point of the chapter:
fn main() -> !int {
let text = "The wolf runs\nthe moon watches the Wolf\n"
region words {
var forest = List[Node]()
for w in text.lower().words() {
if forest.is_empty() {
(mut forest).push(leaf(w))
} else {
add(mut forest[0], w)
}
}
if !forest.is_empty() { walk(forest[0]) }
}
0
}
text.lower().words() is the tokenizer. The C twin needs 23 lines of
getword to do it — a character loop, a case fold, a pushback with
ungetc, a lim to keep the word inside its buffer — and every one of
those lines is there because the input is a stream of characters and the
output has to go into a fixed array that the caller owns. words() returns
the words. lower() folds the case. The buffer question does not come up,
because there is no buffer for a word to be too long for.
forest is a List[Node] that holds nothing or one thing, and it is the
root = NULL line spelled the way §28.2 spelled the children. The C’s
addtree returns the new root so that main can reassign it; the wolf
version pushes the first word into forest and hands forest[0] to add
by mut after that, which is the same decision made in a different place.
Run it:
$ lupin wordtree.lu
1 moon
1 runs
3 the
1 watches
2 wolf
28.4 The alphabetized walk
Put the two outputs side by side. The C’s, from §28.1:
1 moon
1 runs
3 the
1 watches
2 wolf
And wolf’s, from §28.3:
1 moon
1 runs
3 the
1 watches
2 wolf
Byte for byte, including the four-column count field and the single space.
Both programs fold case, so The wolf and the Wolf land in the same two
nodes; both order by the same byte comparison, so the walk agrees on every
word; both count repeats the same way, because there is only one way.
One difference in the inputs is worth stating, because it is the kind of
thing a side-by-side can hide. The C’s getword takes runs of alphabetic
characters and skips everything else, so wolf, and wolf are one word to
it. words() splits on whitespace, so to it they are two. On this
chapter’s input — no punctuation — the two tokenizers agree exactly, which
is why the outputs above are identical. Feed both programs a sentence with
a comma in it and they disagree, and the C is right. Splitting
words the way getword does is 23 lines in C and it would be a similar
number in wolf; words() is the convenient answer and not the complete
one.
28.5 The closing brace
Here is the measurement, and it is the widest gap in the part:
$ wc -l samples/contrast/wordtree.c samples/projects/wordtree/wordtree.lu
162 samples/contrast/wordtree.c
45 samples/projects/wordtree/wordtree.lu
Code lines only: 115 against 41. The wolf program is a third of the size, and this is the chapter where the honesty rule has the least work to do, because there is nowhere in this comparison that the C is shorter or clearer. There is one place where it is more capable — §28.4’s tokenizer — and it costs 23 of the 115 lines.
Of the 74-line difference, here is where 61 of it went, counted:
allocation, in the C column only
addtree's failure guards (two null tests, two nomem sets,
two early returns, the half-built free) 10
talloc 4
dupstr 8
the nomem declaration 1
main's out-of-memory branch 5
treefree, and the call to it 10
----
38
tokenizing, in the C column only
getword 23
Thirty-eight lines about allocation. Twenty-three about turning characters
into words. The remaining thirteen are includes, forward declarations,
MAXWORD, and the struct the wolf column spells in one line. Take the 38
away and what is left of the C is a tree, a walk, and a tokenizer — which
is what the wolf column is.
Now look at the two lines of the wolf program that do all of that work.
The first is region words {, at the top of main. The second is the }
ten lines later.
treefree is nine lines of post-order recursion whose only job is to
match, exactly, every allocation the program made. The wolf version’s
equivalent is the closing brace of the region block. At that brace the
nodes, the lists, the buffers those lists grew, and every str the tree
copied are freed in one motion — not one call per node, and not in an
order anybody had to get right, because there is no order: the whole
region goes at once.
That is the argument chapter 8 made with a diagram, arriving as a program
with a line count. The tree inside the region can point wherever it likes;
a cycle in there would be legal, because nothing in a region can outlive
anything else in it. And the reason treefree cannot be written wrong here
is that it cannot be written at all.
Chapter 32 comes back to this page. It builds the allocator this chapter never needed, in the unsafe tier, in about a page — because you can, and because the floor is worth seeing once from below.
Exercise 28-1 (fingers · lupin) — Build the tree as printed and run
it. Then add a word that sorts before moon and one that sorts after
wolf, and predict where each appears in the output before you run it.
Exercise 28-2 (comprehension · lupin) — add compares with w < n.word on str. Predict the order of Wolf, wolf, WOLF, and wolfs
in the output without the .lower() call, and say which two of the four
end up as one node once .lower() is back.
Exercise 28-3 (extension · lupin) — Add a -n mode: print the words
in descending order of count instead of alphabetically, with ties broken
alphabetically. The tree is already sorted by word, so the shape of the
answer is a second pass — say what you collect on the first pass, and what
it costs in lines.
Exercise 28-4 (comprehension · lupin) — Delete the is_empty() guard
in walk and predict the exact failure: which trap kind, which exit code,
and at which of the two walk calls. Then check it.
Exercise 28-5 (spelunking · the C twin) — Count, in wordtree.c,
every line that would disappear if malloc could not fail, and then every
line that would disappear if the program never had to free. Give both
numbers and say which of the two the region brace replaced.
Exercise 28-6 (extension · lupin) — Take the tree’s census: write
nodes and depth and print both after the walk. Then multiply the node
count by two and say what that number is in the C column, and what it is
in the wolf one.
Exercise 28-7 (design) — K&R’s addtree returns the new subtree
root; wolf’s add takes mut n and returns nothing. Both are answers to
“how does a recursive insert report where the tree went.” Argue which is
easier to get wrong, and then say what the wolf version does about the
empty tree that the C version does not have to.