Listing 1: The initial "classless" implementation of xr

// xr.cpp - generate a cross-reference of words

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

struct list_node
    {
    unsigned number;
    list_node *next;
    };

struct tree_node
    {
    char *word;
    list_node *first, *last;
    tree_node *left, *right;
    };

int get_token(char *s, size_t n);

tree_node *
add_tree(tree_node *t, char const *w, unsigned n);

void put_tree(tree_node const *t);

#define MAX_TOKEN 256

int main()
    {
    tree_node *xr = NULL;
    char token[MAX_TOKEN];
    unsigned ln = 1;
    while (get_token(token, MAX_TOKEN))
        if (isalpha(token[0]) || token[0] == '_')
            xr = add_tree(xr, token, ln);
        else // if (token[0] == '\n')
            ++ln;
    put_tree(xr);
    return 0;
    }

int get_token(char *s, size_t n)
    {
    int c;
    while ((c = fgetc(stdin)) != EOF)
        if (isalpha(c) || c == '_' || c == '\n')
            break;
    if (c == EOF)
        {
        *s = '\0';
        return 0;
        }
    *s++ = c;
    n -= 2;
    if (c != '\n')
        {
        while (isalnum(c = fgetc(stdin)) || c == '_')
            if (n > 0)
                {
                *s++ = c;
                --n;
                }
        ungetc(c, stdin);
        }
    *s = '\0';
    return 1;
    }

tree_node *add_tree
    (
    tree_node *t,
    char const *const w,
    unsigned const n
    )
    {
    int cmp;
    if (t == NULL)
        {
        t = new tree_node;
        t->word = new char [strlen(w) + 1];
        strcpy(t->word, w);
        t->first = new list_node;
        t->first->number = n;
        t->first->next = NULL;
        t->last = t->first;
        t->left = t->right = NULL;
        }
    else if ((cmp = strcmp(w, t->word)) < 0)
        t->left = add_tree(t->left, w, n);
    else if (cmp > 0)
        t->right = add_tree(t->right, w, n);
    else if (n != t->last->number)
        {
        t->last->next = new list_node;
        t->last = t->last->next;
        t->last->number = n;
        t->last->next = NULL;
        }
    return t;
    }

void put_tree(tree_node const *const t)
    {
    list_node const *p;
    if (t != NULL)
        {
        put_tree(t->left);
        printf("%12s:", t->word);
        for (p = t->first; p != NULL; p = p->next)
            printf(" %4d", p->number);
        printf("\n");
        put_tree(t->right);
        }
    }
/* End of File */