Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
// 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 {
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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment