view release on metacpan or  search on metacpan

radix.h  view on Meta::CPAN

 * Layout math + node-pool / arena accessors
 *
 * Layout: Header -> reader_slots[1024] -> node_pool[node_cap] -> arena[arena_cap]
 * RdxNode is 8-byte aligned (sizeof %8 == 0) and RdxReaderSlot is 16 bytes,
 * so node_pool_off is 8-byte aligned.  The arena is raw bytes (no alignment
 * requirement) and follows the node pool.
 * ================================================================ */

typedef struct { uint64_t reader_slots, node_pool, arena; } RdxLayout;

static inline RdxLayout rdx_layout(uint32_t node_cap) {
    RdxLayout L;
    L.reader_slots = sizeof(RdxHeader);
    L.node_pool    = L.reader_slots + (uint64_t)RDX_READER_SLOTS * sizeof(RdxReaderSlot);
    L.arena        = L.node_pool + (uint64_t)node_cap * sizeof(RdxNode);
    return L;
}

static inline uint64_t rdx_total_size(uint32_t node_cap, uint32_t arena_cap) {
    RdxLayout L = rdx_layout(node_cap);
    return L.arena + (uint64_t)arena_cap;
}

static inline RdxNode *rdx_nodes(RdxHandle *h) {
    return (RdxNode *)((char *)h->base + h->hdr->node_pool_off);
}
static inline uint8_t *rdx_arena(RdxHandle *h) {
    return (uint8_t *)((char *)h->base + h->hdr->arena_off);
}

/* ================================================================
 * Node allocation + arena append.  Callers hold the WRITE lock.
 * ================================================================ */

/* Allocate a node: bump node_used, else 0 (pool exhausted).  Returns a zeroed
 * node index.  v1 has no freelist (delete is lazy and never frees nodes), so a
 * node always comes off the high-water mark.  The caller pre-checks capacity
 * before any mutation, so a 0 return must not happen mid-insert. */
static inline uint32_t rdx_alloc_node(RdxHandle *h) {
    RdxHeader *hdr = h->hdr;
    RdxNode *nodes = rdx_nodes(h);
    if (hdr->node_used < hdr->node_cap) {
        uint32_t idx = hdr->node_used++;
        memset(&nodes[idx], 0, sizeof(RdxNode));
        return idx;
    }
    return 0;
}

/* Append `len` bytes to the arena, returning the offset of the first byte.
 * Append-only: existing bytes never move, so pointers into the arena stay
 * valid across appends.  The caller pre-checked that len bytes fit. */
static inline uint32_t rdx_arena_append(RdxHandle *h, const uint8_t *bytes, uint32_t len) {
    RdxHeader *hdr = h->hdr;
    uint32_t off = hdr->arena_used;
    if (len) memcpy(rdx_arena(h) + off, bytes, len);
    hdr->arena_used += len;
    return off;
}

/* Worst case any single insert consumes: up to 2 new nodes (a split makes a
 * mid node + a leaf node) and up to klen arena bytes (the leaf's label).
 * v1 has no freelist, so the 2 nodes must come fresh from the high-water mark.
 * Returns 1 if both fit, 0 otherwise.  Caller holds the write lock. */
static inline int rdx_insert_has_room(RdxHandle *h, uint32_t klen) {
    RdxHeader *hdr = h->hdr;
    if (hdr->node_cap - hdr->node_used < 2) return 0;
    if (hdr->arena_cap - hdr->arena_used < klen) return 0;
    return 1;
}

/* ================================================================
 * Radix-tree core
 * ================================================================ */

#ifndef RDX_MIN
#define RDX_MIN(a, b) ((a) < (b) ? (a) : (b))
#endif

/* Common-prefix length: number of leading bytes where a[i]==b[i], up to max. */
static inline uint32_t rdx_cpl(const uint8_t *a, const uint8_t *b, uint32_t max) {
    uint32_t i = 0;
    while (i < max && a[i] == b[i]) i++;
    return i;
}

/* Insert key -> value.  Returns 1 if a new key was added, 0 if an existing key
 * was updated.  Caller holds the write lock AND has verified rdx_insert_has_room
 * (so every rdx_alloc_node / rdx_arena_append below is guaranteed to succeed,
 * keeping the tree consistent -- no partial-split-on-OOM possibility). */
static inline int rdx_insert_locked(RdxHandle *h, const uint8_t *key, uint32_t klen, uint64_t value) {
    RdxHeader *hdr = h->hdr;
    RdxNode *nodes = rdx_nodes(h);
    uint8_t *arena = rdx_arena(h);
    uint32_t cur = hdr->root, kpos = 0;
    for (;;) {
        if (kpos == klen) {                       /* key ends here -> mark this node */
            int isnew = !nodes[cur].has_value;
            nodes[cur].has_value = 1;
            nodes[cur].value = value;
            if (isnew) hdr->keys++;
            return isnew;
        }
        uint8_t b = key[kpos];
        uint32_t ch = nodes[cur].children[b];
        if (ch == 0) {                            /* no child on b -> new leaf with the rest as its label */
            uint32_t leaf = rdx_alloc_node(h);
            nodes = rdx_nodes(h);                 /* base is stable, but re-fetch defensively after alloc */
            nodes[leaf].label_off = rdx_arena_append(h, key + kpos, klen - kpos);
            nodes[leaf].label_len = klen - kpos;
            nodes[leaf].has_value = 1;
            nodes[leaf].value = value;
            /* Publish the fully-initialized leaf before linking it in, so a
             * process that takes the lock after a mid-insert SIGKILL + dead-
             * writer recovery never sees children[b]==leaf while the leaf's
             * label_off/len are still garbage (which would drive an out-of-
             * bounds arena read). The link is the single-word commit; a crash
             * before it leaks the node but keeps the tree consistent. */
            __atomic_thread_fence(__ATOMIC_RELEASE);
            nodes[cur].children[b] = leaf;
            hdr->keys++;