14
\$\begingroup\$

In response to another recent question I mentioned that one mechanism to avoid runtime overhead for creating a data structure was to create it at compile time and use it directly. Since there was some interest in that concept, I thought I would write code to show how that might be done and submit it for review here.

The theory

There are two pieces to this code.

The first is code that is used to construct an AVL tree of arbitrary data. For illustration purposes, the data inserted into the tree are the names of the months (in English) and the number of days in each month. The month name is used as the key for lookup and the number of days is the associated data retrieved. This first piece of code constructs the tree and then emits it as a C source code representing the resulting structure.

The second piece of code is the part that would be compiled and linked with the object file resulting from the first piece.

makeavl.c

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

typedef struct node {
    char *key;
    int data;

    struct node *left;
    struct node *right;
} node;

node *new_node(char *key, int data)
{
    node *p = malloc(sizeof(*p));
    if (p != NULL) {
        p->key = key;
        p->data = data;
        p->left = NULL;
        p->right = NULL;
    }
    return p;
}

int max(int a, int b)
{
    return a > b ? a : b;
}

int nodecount(node *p)
{
    int count = 0;
    if (p != NULL) {
        ++count;
        count += nodecount(p->left);
        count += nodecount(p->right);
    }
    return count;
}

int relheight(node *p, int count)
{
    if (p == NULL)
        return count;
    return max(relheight(p->left, count+1), relheight(p->right, count+1));
}

int height(node * p)
{
    return relheight(p, 0);
}

node *rotate_right(node * p)
{
    node *q = p->left;

    p->left = q->right;
    q->right = p;

    return q;
}

node *rotate_left(node * p)
{
    node *q = p->right;
    p->right = q->left;
    q->left = p;

    return q;
}

node *balance(node * p)
{
    if (height(p->left) - height(p->right) == 2) {
        if (height(p->left->right) > height(p->left->left))
            p->left = rotate_left(p->left);
        return rotate_right(p);
    } else if (height(p->right) - height(p->left) == 2) {
        if (height(p->right->left) > height(p->right->right))
            p->right = rotate_right(p->right);
        return rotate_left(p);
    }
    return p;
}

node *insert(node * p, char *key, int data)
{
    if (p == NULL)
        return new_node(key, data);

    int keycmp = strcmp(key, p->key);
    if (keycmp < 0)
        p->left = insert(p->left, key, data);
    else if (keycmp > 0)
        p->right = insert(p->right, key, data);
    else
        p->data = data;

    return balance(p);
}

void free_tree(node * p)
{
    if (p == NULL)
        return;

    free_tree(p->left);
    free_tree(p->right);
    free(p);
}

void emit(FILE * out, node * p, const char *name, int *count)
{
    if (p != NULL) {
        fprintf(out, "/* %d */ ", *count);
        fprintf(out, "{ \"%s\", %d, ", p->key, p->data);
        ++(*count);
        if (p->left) {
            fprintf(out, "&%s[%d], ", name, *count);
        } else {
            fprintf(out, "NULL, ");
        }
        if (p->right) {
            fprintf(out, "&%s[%d] },\n", name, *count + nodecount(p->left));
        } else {
            fprintf(out, "NULL },\n");
        }
        emit(out, p->left, name, count);
        emit(out, p->right, name, count);
    }
}

void makeC(FILE *out, node *p, const char *name)
{
    int count = 0;
    fprintf(out, "node %s[] = {\n", name);
    emit(out, p, name, &count);
    fprintf(out, "};\n");
}

int main()
{
    node *root = NULL;

    char *months[12] = { "January", "February", "March", "April",
        "May", "June", "July", "August", "September",
        "October", "November", "December"
    };
    int days[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    for (int i = 0; i < 12; ++i) {
        root = insert(root, months[i], days[i]);
    }
    makeC(stdout, root, "caltree");
    free_tree(root);
}

useavl.c

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

typedef struct node {
    char *key;
    int data;

    struct node *left;
    struct node *right;
} node;

node *search(node * p, char *key)
{
    if (p == NULL)
        return NULL;

    int keycmp = strcmp(key, p->key);
    if (keycmp < 0)
        return search(p->left, key);
    else if (keycmp > 0)
        return search(p->right, key);
    else
        return p;
}

int main(void)
{
#include "staticavl.c"

    node *n = search(caltree, "February");
    printf("There are %d days in %s.\n", n->data, n->key);
}

staticavl.c (generated file)

node caltree[] = {
/* 0 */ { "March", 31, &caltree[1], &caltree[8] },
/* 1 */ { "January", 31, &caltree[2], &caltree[6] },
/* 2 */ { "August", 31, &caltree[3], &caltree[4] },
/* 3 */ { "April", 30, NULL, NULL },
/* 4 */ { "February", 28, &caltree[5], NULL },
/* 5 */ { "December", 31, NULL, NULL },
/* 6 */ { "June", 30, &caltree[7], NULL },
/* 7 */ { "July", 31, NULL, NULL },
/* 8 */ { "October", 31, &caltree[9], &caltree[11] },
/* 9 */ { "May", 31, NULL, &caltree[10] },
/* 10 */ { "November", 30, NULL, NULL },
/* 11 */ { "September", 30, NULL, NULL },
};

Sample output

There are 28 days in February.

The advantage to doing things this way is that only the lookup function needs to be in the useavl program, so if it's an embedded system and especially if the data structure is large and complex, the burden for building the structure is shifted to compile time (or technically, to runtime for makeavl). It's possible, and indeed probable, that makeavl and useavl would run on different machines.

Comments welcome.

\$\endgroup\$
  • 3
    \$\begingroup\$ What if it's a leap-year? \$\endgroup\$ – nhgrif Jul 26 '15 at 21:58
  • \$\begingroup\$ @nhgrif then you put this into the search function: if (strcmp(key, "February") == 0 && is_leap_year) { ... :P \$\endgroup\$ – glampert Jul 27 '15 at 0:28
  • \$\begingroup\$ It's good to remember that it's sample data, not a calendar application. \$\endgroup\$ – Edward Jul 27 '15 at 1:03
  • \$\begingroup\$ An interesting example of this is GIMP's Export As>C source file. There's also Export As>C header file that generates a compressed file and a macro for uncompressing it. \$\endgroup\$ – jacwah Jul 27 '15 at 15:29
  • \$\begingroup\$ @nhgrif You may like to know about February 30th. \$\endgroup\$ – chux - Reinstate Monica Jul 28 '15 at 3:12
5
\$\begingroup\$

It's a little tricky to provide feedback on this code, while at the same time remembering that it's just an example. (As nhgrif mentioned in the comments, "What if it's a leap year?") In real life, we'd never want to use a binary search tree; at least we'd prefer to store the data in a sorted array and use binary search — i.e., we'd strength-reduce "dereferencing operations on pointers" to "arithmetic operations on indices", because the latter are much cheaper on our usual hardware. In fact, for just 12 pieces of data, we'd be more likely to use linear search, or perhaps a perfect hash table.

However, let's say we had a whole ton of data to store in this data structure, and for some reason we really needed it to be stored in a binary search tree with real pointers. (I can't think of such an application, but I'm willing to stipulate that one exists.)

Then your program organization, IMHO, still leaves something to be desired.

int main(void)
{
#include "staticavl.c"

    node *n = search(caltree, "February");
    printf("There are %d days in %s.\n", n->data, n->key);
}

I would greatly prefer this to be written as

#include "month_data.h"

int main(void)
{
    month_data *n = get_month_data("February");
    printf("There are %d days in %s.\n", n->days, n->name);
}

where "month_data.c" would consist of the same pieces of code you wrote, just rearranged to put the module boundary in the right place:

// month_data.h
typedef struct month_data {
    const char *name;
    int days;
} month_data;

month_data *get_month_data(const char *name);

// month_data.c
struct node {
    struct month_data data;    
    struct node *left;
    struct node *right;
};

static struct node *search(struct node *p, const char *key)
{
    if (p == NULL)
        return NULL;

    int keycmp = strcmp(key, p->data.name);
    if (keycmp < 0)
        return search(p->left, key);
    else if (keycmp > 0)
        return search(p->right, key);
    else
        return p;
}

static struct node caltree[] = {
/* 0 */ { "March", 31, &caltree[1], &caltree[8] },
/* 1 */ { "January", 31, &caltree[2], &caltree[6] },
/* 2 */ { "August", 31, &caltree[3], &caltree[4] },
/* 3 */ { "April", 30, NULL, NULL },
/* 4 */ { "February", 28, &caltree[5], NULL },
/* 5 */ { "December", 31, NULL, NULL },
/* 6 */ { "June", 30, &caltree[7], NULL },
/* 7 */ { "July", 31, NULL, NULL },
/* 8 */ { "October", 31, &caltree[9], &caltree[11] },
/* 9 */ { "May", 31, NULL, &caltree[10] },
/* 10 */ { "November", 30, NULL, NULL },
/* 11 */ { "September", 30, NULL, NULL },
};

month_data *get_month_data(const char *name)
{
     node *n = search(caltree, name);
     return n ? &n->data : NULL;
}

The advantage of this organization is that we've put the module boundary at a natural place: the month_data module is now concerned solely with getting the data for a particular month. The notion of "searching a tree" is encapsulated into it as an implementation detail, one that the user of the module doesn't have to worry about. Nor does the compiler have to worry about it, because we're no longer passing a struct node * across the module boundary; the compiler is free to inline and optimize our use of the now-static data structure.

And we're free to change the internal implementation of get_month_data; if profiling proves that a linear search in a lookup table would be faster, then we can make that change, without even requiring the client to recompile their main.o module. Using your old code, they'd have to not only recompile useavl.o, but rewrite it, unless you went out of your way to reuse the same struct node interface. (And a good engineer would also want to rename useavl.o, since it would then no longer be using an AVL tree. That's a lot of needless code-shoveling, which we could have avoided by using the right abstractions from the beginning.)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Tree structures are better in the case that a range of keys needs to be retrieved or if we need to find the nearest match, as with the spell checking question to which this question is linked. \$\endgroup\$ – Edward Jul 27 '15 at 10:57
  • \$\begingroup\$ Nope; if the dataset is immutable, there's literally zero difference between a tree structure and a sorted list (except that the sorted list doesn't need left and right pointers and thus it can fit more data into your L1 cache). \$\endgroup\$ – Quuxplusone Jul 27 '15 at 20:07
  • \$\begingroup\$ Sorry, I should have been clear that I meant better as contrasted with a hash table. (And on the embedded systems I typically work on, there is no cache!) \$\endgroup\$ – Edward Jul 27 '15 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.