Tag pointers to avoid node type byte

[adamsch1]

nice code thanks for sharing!

Was wondering if you have considered using the low bits on each child pointer to indicate the node type. Would remove the need for a 8 bit node type. There are only 4 node types I believe, and on 64 bit systems with 8 byte alignment you can use just the lower 2 bits.

Sorry not an issue really just a question :)

[mattsta]

The "leafness" is already stored as a 1-bit tag:

/* Macros to manipulate pointer tags */
#define IS_LEAF(x) (((uintptr_t)x & 1))
#define SET_LEAF(x) ((void *)((uintptr_t)x | 1))
#define LEAF_RAW(x) ((artLeaf *)((void *)((uintptr_t)x & ~1ULL)))

But over in my libart fork I did refactor bitfields for the type:

#define MAX_PREFIX_LEN 14
typedef struct artNode {
    uint8_t partialLen; /* length of 'partial' (could be 4 bits, but less
                           efficient) */
    uint8_t type : 2;
    uint8_t childrenCount : 6;
    uint8_t partial[MAX_PREFIX_LEN];
} artNode;

Seems 16 bytes is the smallest we can get for the common node metadata (having prefix len 14), so throwing two more bits away doesn't help us much right now.