Cost of nested dereferencing negligible?

Question

I have a family of large recursive functions that operate on trees. These trees are defined using "polymorphism", like so

struct foo {
    enum abctype type;
    union {
        struct a ay;
        struct b bee;
        struct c cee;
    }
};

where struct a... c are all nodes in the tree. Each node in the tree (i.e., any object of type struct a... c), points to an object of struct foo. For example:

struct a {
    /* definitions */
    /*...*/
    struct foo *next;
};

Because of this, the struct dereferences end up getting very nested even though my functions aren't overreaching their purposes.

In this case, the nested dereferences are inevitable. It would be absurd to write cute little wrapper functions just to get rid of a ->. But, I've heard many programmers say that you shouldn't go past 3-4 dereferences or your "algorithm needs fixing".

So, what's the verdict? Does my code need fixing? are nested dereferences inefficient?

Edit: Here's what my data structure looks like in more depth (they're not trees, as I have been told, unless linked list == tree):

struct a {
    /* definitions */
    /*...*/
    struct foo *longitudinal;
};

struct b {
    /* definitions */
    /*...*/
    struct foo *longitudinal;
    struct b *transverse;
};

struct c {
    /* definitions */
    /*...*/
    struct foo *longitudinal;
    struct c *transverse;
};

Basically, the data structures are this way because the data they handle is organized this way (in my head). I just don't see a way to convert this to a binary tree.

Answer 1

A single pointer does not make a tree; it makes a list. Trees require at least two pointers. (You can find exceptions described at Wikipedia, but it is unlikely — though not impossible — that you're intending to use such an organization for your tree structure.)

I think your data organization is … well, if it is not wrong, then it is at least sub-optimal. You should almost certainly be using a structure more like:

struct tree
{
    struct tree *left;
    struct tree *right;
    enum abctype type;
    union {
        struct a aye;
        struct b bee;
        struct c cee;
    };
};

Where each of the single-letter structure types contains only the relevant (variant) data and not any tree-related pointers:

struct a
{
    /* definitions */
    /* …no struct tree *next; or anything similar… */
};

The tree traversal is now nice and uniform. Compare what used to be necessary with what is now necessary. Given the old struct foo *tp, your original code (probably) needed to do ghastly stuff like:

if (tp->type == TYPE_A)
    process_next(tp->ay.next);
else if (tp->type == TYPE_B)
    process_next(tp->bee.next);
else if (tp->type == TYPE_C)
    process_next(tp->cee.next);
else
    …report error…

(and similarly with a prev or left and right pointers, or whatever else you used to create an actual tree structure — though even as a list, this is more than a trifle messy).

With the revised scheme, given a struct tree *tp;, you now just use:

process_tree(tp->left);
process_data(tp);
process_tree(tp->right);

The data handling has to deal with the enumeration and accessing the appropriate portion of the anonymous union. This is much the same as before (except you don't need to futz with the tree structure pointers).

---

Working code

I observe that since you've not shown data for the structures a, b, and c, I've had to guess at what might be appropriate. If that sort of detail matters to you, it is important that you put that information in the question before people get to answer it. (That means, in part, don't go adding data fields to the structures now — you've already blown the opportunity to specify what is in them.)

This code works, more or less. The memory management doesn't have memory access errors, at least with the test data. The data isn't freed; that's an exercise for you to play with. Not all the error checking that should be there is there; that's another exercise for you. And the testing isn't all that comprehensive — guess what that means?

There could be some confusion about how your data structure is supposed to work. I've interpreted it as:

• You can have a (longitudinal) list of items in arbitrary order, of type A, B or C. These are stored via struct foo, complete with the anonymous union.
• Items of type B can have a transverse list of more type B items.
• Items of type C can have a transverse list of more type C items.

Here's some code that works:

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

struct a
{
    char name[20];
};

struct b
{
    double x;
    double y;
    struct b *transverse;
};

struct c
{
    int height;
    int width;
    int depth;
    struct c *transverse;
};

enum abctype { TYPE_A, TYPE_B, TYPE_C };

struct foo
{
    struct foo *longitudinal;
    enum abctype type;
    union
    {
        struct a aye;
        struct b bee;
        struct c cee;
    };
};

static struct foo *add_a_long(struct foo *head, const char *name)
{
    struct foo *new_foo = malloc(sizeof(*new_foo));
    if (new_foo != 0)
    {
        strncpy(new_foo->aye.name, name, sizeof(new_foo->aye.name)-1);
        new_foo->aye.name[sizeof(new_foo->aye.name)-1] = '\0';
        new_foo->type = TYPE_A;
        new_foo->longitudinal = head;
    }
    return new_foo;
}

static struct foo *add_b_long(struct foo *head, double x, double y)
{
    struct foo *new_foo = malloc(sizeof(*new_foo));
    if (new_foo != 0)
    {
        new_foo->bee.x = x;
        new_foo->bee.y = y;
        new_foo->bee.transverse = 0;
        new_foo->type = TYPE_B;
        new_foo->longitudinal = head;
    }
    return new_foo;
}

static struct foo *add_c_long(struct foo *head, int height, int width, int depth)
{
    struct foo *new_foo = malloc(sizeof(*new_foo));
    if (new_foo != 0)
    {
        new_foo->cee.height = height;
        new_foo->cee.width = width;
        new_foo->cee.depth = depth;
        new_foo->cee.transverse = 0;
        new_foo->type = TYPE_C;
        new_foo->longitudinal = head;
    }
    return new_foo;
}

static void add_b_trans(struct b *b, double x, double y)
{
    struct b *new_b = malloc(sizeof(*new_b));
    if (new_b != 0)
    {
        new_b->x = x;
        new_b->y = y;
        new_b->transverse = 0;
        while (b->transverse != 0)
            b = b->transverse;
        b->transverse = new_b;
    }
}

static void add_c_trans(struct c *c, int height, int width, int depth)
{
    struct c *new_c = malloc(sizeof(*new_c));
    if (new_c != 0)
    {
        new_c->height = height;
        new_c->width = width;
        new_c->depth = depth;
        new_c->transverse = 0;
        while (c->transverse != 0)
            c = c->transverse;
        c->transverse = new_c;
    }
}

static void print_foo(const char *tag, const struct foo *head)
{
    printf("\n%s:\n", tag);
    while (head != 0)
    {
        switch (head->type)
        {
        case TYPE_A:
            printf("A: %s\n", head->aye.name);
            break;
        case TYPE_B:
            {
            const struct b *bp = &head->bee;
            printf("B-main:  (%f,%f)\n", bp->x, bp->y);
            while ((bp = bp->transverse) != 0)
                printf("B-trans: (%f,%f)\n", bp->x, bp->y);
            }
            break;
        case TYPE_C:
            {
            const struct c *cp = &head->cee;
            printf("C-main:  (%d,%d,%d)\n", cp->height, cp->width, cp->depth);
            while ((cp = cp->transverse) != 0)
                printf("C-trans: (%d,%d,%d)\n", cp->height, cp->width, cp->depth);
            }
            break;
        }
        head = head->longitudinal;
    }
}

int main(void)
{
    struct foo *head = 0;
    head = add_a_long(head, "Caterpillar");
    print_foo("1 item", head);
    head = add_a_long(head, "Ununtrium");
    print_foo("2 items", head);
    head = add_b_long(head, 1.00000, 1.00000);
    head = add_b_long(head, 3.14159, 2.78128);
    print_foo("4 items", head);
    assert(head->type == TYPE_B);
    add_b_trans(&head->bee, 1.2345, 2.3456);
    add_b_trans(&head->bee, 9.8765, 6.5432);
    print_foo("4 items, 2 transverse B", head);
    head = add_a_long(head, "Ununpentium");
    head = add_c_long(head, 3, 4, 5);
    head = add_c_long(head, 5, 12, 13);
    print_foo("6 items", head);
    assert(head->type == TYPE_C);
    add_c_trans(&head->cee, 7, 20, 27);
    add_c_trans(&head->cee, 9, 35, 36);
    head = add_a_long(head, "Ununseptium");
    head = add_a_long(head, "Ununoctium");
    print_foo("Final", head);
    return 0;
}

And this is the sample output I get:

1 item:
A: Caterpillar

2 items:
A: Ununtrium
A: Caterpillar

4 items:
B-main:  (3.141590,2.781280)
B-main:  (1.000000,1.000000)
A: Ununtrium
A: Caterpillar

4 items, 2 transverse B:
B-main:  (3.141590,2.781280)
B-trans: (1.234500,2.345600)
B-trans: (9.876500,6.543200)
B-main:  (1.000000,1.000000)
A: Ununtrium
A: Caterpillar

6 items:
C-main:  (5,12,13)
C-main:  (3,4,5)
A: Ununpentium
B-main:  (3.141590,2.781280)
B-trans: (1.234500,2.345600)
B-trans: (9.876500,6.543200)
B-main:  (1.000000,1.000000)
A: Ununtrium
A: Caterpillar

Final:
A: Ununoctium
A: Ununseptium
C-main:  (5,12,13)
C-trans: (7,20,27)
C-trans: (9,35,36)
C-main:  (3,4,5)
A: Ununpentium
B-main:  (3.141590,2.781280)
B-trans: (1.234500,2.345600)
B-trans: (9.876500,6.543200)
B-main:  (1.000000,1.000000)
A: Ununtrium
A: Caterpillar

Answer 2

The canonical way to go about this is to really use the structs like derived classes. I. e.:

struct base {
    enum abctype type;
};

struct a {
    struct base super;
    //whatever other data members `a` happens to have
};

With this approach, you write functions taking a struct base*, which is subsequently cast to one of the subclasses once. Further manipulation of the object uses the derived class pointer with only a single ->.

---

Btw: If you include a function pointer within struct base, you can directly call the derived class's function (no switch required). Bonus points for grouping the function pointers in a struct of their own (instanciated as global tables), with a single pointer in struct base pointing to the correct function table. That would very, very close to what C++ does under the hood...

struct base_vtable {
    void (*foo)(int, double);
    int (*bar)(struct base*);
    int (*baz)();
};

struct a_vtable {
    struct base_vtable super;
    double (*bim)();
    dobule (*bam)();
};

struct base {
    struct base_vtable vtable;
};

struct a {
    struct base super;
    //whatever
};

And then, somewhere in a .c file:

static struct a_vtable g_a_vtable = {
    .super.foo = &a_foo,
    .super.bar = &a_bar,
    .super.baz = &a_baz,
    .bim = a_bim,
    .bam = a_bam
};

struct a* a_create(...) {
    struct a* me = malloc(sizeof(*me));
    me->super->vtable = g_a_vtable;
    //further initialization
};