How To Implement A Binary Trie That Has Nodes That Read 4 Bits At A Time?

I am trying to find a way to sort of inline a binary trie in some sense. Basically, a binary trie has a node for every slot in a binary number, branching left on 0 and right on 1.

Solution 1:

What you describe is a radix trie base 16. By extracting 4 bits from your key, you get a number between 0 and 15 (inclusive). You can use that number to index into your node:

struct Node {
    Node *children[16];
    Value value;
};

Value *find(const char *key, int nkey, Node *node) {
    int i = 0;
    while(i < 2*nkey && node) {
        int digit = (key[i/2] >> (i%2==0 ? 0 : 4)) & 0xf;
        node = node->children[digit];
        ++i;
    }
    return node ? &node->value : 0;
}