Skip to content

Instantly share code, notes, and snippets.

@pervognsen pervognsen/vec.c

Last active May 13, 2020
What would you like to do?
// A sketch of persistent 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];
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.