vec.c

// A sketch of partially persistent (linear, non-branching history) vectors with the in-place v2 trick.

typedef struct Leaf Leaf;
typedef struct Node Node;
typedef struct Vec Vec;

typedef uint32_t Ver;
typedef uint64_t Val;
typedef int32_t RelPtr;

struct Leaf {
    Val vals[32];
};

struct Node {
    Ver v2_ver;
    uint8_t v2_idx;
    RelPtr ptrs[32];
    RelPtr v2_ptr;
};

// Keeping the len in the descriptor lets us zero-copy share prefixes of vectors, and it means we don't
// have to store internal node/leaf info about occupancy. Could expand this with start/len to support slicing.
// Appends that grow nodes/leaves can add their new data in place if the current array entry is empty; to detect
// empty entries for in-place appends, we can use 0 for node ptrs but for leaf vals we need an unused sentinel value or an
// occupancy count. So, most of the time first-time appends don't need to use the v2 data and don't allocate at all but just
// append the data in place and return a Vec descriptor with an increased len; old Vec descriptors don't see the appended data
// since their shorter len corresponds to the original prefix.
struct Vec {
    uint32_t len;
    Ver ver;
    RelPtr ptr;
};

char *vec_heap;

Val *find(Vec v, uint32_t i) {
    // Once we've done this len check we dont need to validate the ptr accesses during the bit slice traversal.
    if (i >= v.len) {
        return 0;
    }
    Node *node = (Node *)(vec_heap + v.ptr);
    int depth = clog32(v.len);
    Leaf *leaf;
    // Find leaf by walking node->ptrs using bit slices of i starting from 5*depth.
    // If v.ver == node->v2_ver and bit slice matches node->v2_idx then instead use node->v2_ptr.
    return &leaf->vals[i & 31];
}