ast_tagged_index.c

// We have five kinds of nodes: literal, negate, not, add, xor.
// In this case we only need 3 bits for the tag but you can use as many as you need.

enum Tag {
    LIT,
    NEG,
    NOT,
    ADD,
    XOR,
};

typedef uint32_t Ref;

Tag tag(Ref r) {
    return r & 7;
}

uint32_t index(Ref r) {
    return r >> 3;
}

struct Literal {
    int val;
};

struct Unary {
    Ref rhs;
};

struct Binary {
    Ref lhs, rhs;
};

Literal *literal;
Unary *unary;
Binary *binary;

// An index is only unique for a given tag. This means that slot 0 of the literal, unary and binary arrays are unrelated.
// Thus a literal or unary node doesn't need to pay for the cost of a second field. The literal/unary arrays can
// share the same physical storage (with no aliasing violations) as long as they use a shared index allocator.
int evaluate(Ref r) {
    uint32_t i = index(r);
    switch (tag(r)) {
    case LIT:
        return literal[i].val;
    case NEG:
        return -evaluate(unary[i].rhs);
    case NOT:
        return ~evaluate(unary[i].rhs);
    case ADD:
        return evaluate(binary[i].lhs) + evaluate(binary[i].rhs);
    case XOR:
        return evaluate(binary[i].lhs) ^ evaluate(binary[i].rhs);
    }
}