// 基于本地 Redis 仓 (unstable, 2026-03), src/rax.h
#define RAX_NODE_MAX_SIZE ((1<<29)-1)   // size 位域只有 29 bit, 单个压缩节点最多存 2^29-1 字节
typedef struct raxNode {
    uint32_t iskey:1;     /* Does this node contain a key? */               // 任何中间节点都能当 key 终点, 不限于叶子: "foo" 和 "foobar" 共存靠它
    uint32_t isnull:1;    /* Associated value is NULL (don't store it). */  // NULL 值连指针都不分配, rax 当有序 set 用时零 value 开销
    uint32_t iscompr:1;   /* Node is compressed. */
    uint32_t size:29;     /* Number of children, or compressed string len. */  // 同一个字段两种语义, 由 iscompr 决定
    /* Data layout is as follows:
     * ...
     * [header iscompr=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)   // 非压缩: size 个有序字符 + size 个子指针, 字符存在父节点的"边"上
     * ...
     * [header iscompr=1][xyz][z-ptr](value-ptr?)                 // 压缩: 一串单链字符, 但只有 1 个子指针(指向最后一个字符对应的节点)
     * ... */
    unsigned char data[];   // 变长区: 没有具名字段, 全靠宏做指针运算访问
} raxNode;

typedef struct rax {
    raxNode *head;
    uint64_t numele;        // key 个数, raxSize() O(1) 直接返回
    uint64_t numnodes;      // 节点总数, 远小于所有 key 的字符总量: 这就是压缩的效果
    size_t *alloc_size;     // 新版加的内存记账: 每次节点 malloc/realloc/free 都同步累计, 外部可精确观测 rax 内存占用
    void *metadata[];
} rax;

// 基于本地 Redis 仓 (unstable, 2026-03), src/rax.c
#define raxPadding(nodesize) ((sizeof(void*)-(((nodesize)+4) % sizeof(void*))) & (sizeof(void*)-1))

#define raxNodeCurrentLength(n) ( \
    sizeof(raxNode)+(n)->size+ \
    raxPadding((n)->size)+ \
    ((n)->iscompr ? sizeof(raxNode*) : sizeof(raxNode*)*(n)->size)+ \
    (((n)->iskey && !(n)->isnull)*sizeof(void*)) \
)

// 基于本地 Redis 仓 (unstable, 2026-03), src/rax.c
static inline size_t raxLowWalk(rax *rax, unsigned char *s, size_t len, raxNode **stopnode, raxNode ***plink, int *splitpos, raxStack *ts) {
    raxNode *h = rax->head;
    raxNode **parentlink = &rax->head;  // "父节点里存我地址的那个槽位": 节点 realloc 会搬家, 这是唯一稳定的锚点

    size_t i = 0; /* Position in the string. */
    size_t j = 0; /* Position in the node children (or bytes if compressed).*/
    while(h->size && i < len) {
        debugnode("Lookup current node",h);
        unsigned char *v = h->data;

        if (h->iscompr) {
            for (j = 0; j < h->size && i < len; j++, i++) {
                if (v[j] != s[i]) break;    // 压缩串必须整段逐字节匹配, 失配就停
            }
            if (j != h->size) break;        // j 停在失配位置, 正是插入时 ALGO 1 的分裂点
        } else {
            /* Children are sorted. Check the last child first: for
             * sequential inserts the match is almost always at the end,
             * and for random keys the extra compare is negligible vs
             * the O(n) scan that follows on miss. */
            if (v[h->size - 1] == s[i]) {   // 先比最右分支: Stream ID 单调递增, 顺序插入几乎总命中最后一个孩子, O(size) 变 O(1)
                j = h->size - 1;
            } else if (s[i] > v[h->size - 1]) {
                j = h->size;                // 比最大分支还大, 必然不存在, 直接判 miss
                break;
            } else {
                /* Even when h->size is large, linear scan provides good
                 * performances compared to other approaches that are in theory
                 * more sounding, like performing a binary search. */
                for (j = 0; j < h->size; j++) {
                    if (v[j] == s[i]) break;
                }
                if (j == h->size) break;
            }
            i++;
        }

        if (ts) raxStackPush(ts,h); /* Save stack of parent nodes. */   // 节点为省内存不存 parent 指针, 需要父链的操作(删除/迭代)下行时现记
        raxNode **children = raxNodeFirstChildPtr(h);
        if (h->iscompr) j = 0; /* Compressed node only child is at index 0. */
        memcpy(&h,children+j,sizeof(h));    // data[] 里的指针没有字段名, 读写一律 memcpy + 偏移
        parentlink = children+j;
        j = 0; /* If the new node is non compressed and we do not
                  iterate again (since i == len) set the split
                  position to 0 to signal this node represents
                  the searched key. */
    }
    debugnode("Lookup stop node is",h);
    if (stopnode) *stopnode = h;
    if (plink) *plink = parentlink;
    if (splitpos && h->iscompr) *splitpos = j;
    return i;
}

/* Find a key in the rax: return 1 if the item is found, 0 otherwise.
 * If there is an item and 'value' is passed in a non-NULL pointer,
 * the value associated with the item is set at that address. */
int raxFind(rax *rax, unsigned char *s, size_t len, void **value) {  // Redis 8.0 起改成 int + 出参; 老版本返回 void* 与 raxNotFound 哨兵比较
    raxNode *h;

    debugf("### Lookup: %.*s\n", (int)len, s);
    int splitpos = 0;
    size_t i = raxLowWalk(rax,s,len,&h,NULL,&splitpos,NULL);
    if (i != len || (h->iscompr && splitpos != 0) || !h->iskey)  // 三个条件缺一不可: 没走完 / 停在压缩串中间 / 终点节点不是 key
        return 0;
    if (value != NULL) *value = raxGetData(h);
    return 1;
}

// 基于本地 Redis 仓 (unstable, 2026-03), src/rax.c
int raxGenericInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old, int overwrite) {
    size_t i, usable;
    int j = 0; /* Split position. If raxLowWalk() stops in a compressed
                  node, the index 'j' represents the char we stopped within the
                  compressed node, that is, the position where to split the
                  node for insertion. */
    raxNode *h, **parentlink;
    // ...
    i = raxLowWalk(rax,s,len,&h,&parentlink,&j,NULL);

    // ... 局面一: key 已有对应节点, 只需(可能)追加 value 指针
    if (i == len && (!h->iscompr || j == 0 /* not in the middle if j is 0 */)) {
        /* Make space for the value pointer if needed. */
        if (!h->iskey || (h->isnull && overwrite)) {
            h = raxReallocForData(rax,h,data);          // realloc 后节点地址可能变
            if (h) memcpy(parentlink,&h,sizeof(h));     // 所以必须同步改写父节点的槽位, parentlink 的意义就在这
        }
        if (h == NULL) {
            errno = ENOMEM;
            return 0;
        }

        /* Update the existing key if there is already one. */
        if (h->iskey) {
            if (old) *old = raxGetData(h);
            if (overwrite) raxSetData(h,data);
            errno = 0;
            return 0; /* Element already exists. */
        }

        /* Otherwise set the node as a key. Note that raxSetData()
         * will set h->iskey. */
        raxSetData(h,data);
        rax->numele++;
        return 1; /* Element inserted. */
    }

    // ... 源码此处有 70 行注释, 用 "ANNIBALE"->"SCO"->[] 树推演了插入的全部 5 种 case, 值得直接读

    /* ------------------------- ALGORITHM 1 --------------------------- */
    if (h->iscompr && i != len) {   // 局面二: 在压缩串第 j 个字符失配, 一拆三: trimmed(公共前缀) + splitnode(分叉点) + postfix(原串剩余)
        // ...
        /* 1: Save next pointer. */
        raxNode **childfield = raxNodeLastChildPtr(h);
        raxNode *next;
        memcpy(&next,childfield,sizeof(next));
        // ...

        /* Set the length of the additional nodes we will need. */
        size_t trimmedlen = j;
        size_t postfixlen = h->size - j - 1;
        int split_node_is_key = !trimmedlen && h->iskey && !h->isnull;  // 只有从第 0 个字符就分裂时, 原节点的 key 身份才落到 split 节点上
        size_t nodesize;

        /* 2: Create the split node. Also allocate the other nodes we'll need
         *    ASAP, so that it will be simpler to handle OOM. */
        raxNode *splitnode = raxNewNode(rax, 1, split_node_is_key);
        raxNode *trimmed = NULL;
        raxNode *postfix = NULL;
        // ... 按需分配 trimmed/postfix; 任一 OOM 则全部释放并返回 0 —— 此刻树还没动过, 天然原子
        splitnode->data[0] = h->data[j];    // split 节点先只挂原串的失配字符; key 一侧的失配字符由函数末尾的通用循环补上

        if (j == 0) {
            /* 3a: Replace the old node with the split node. */
            if (h->iskey) {
                void *ndata = raxGetData(h);
                raxSetData(splitnode,ndata);
            }
            memcpy(parentlink,&splitnode,sizeof(splitnode));
        } else {
            /* 3b: Trim the compressed node. */
            trimmed->size = j;
            memcpy(trimmed->data,h->data,j);
            trimmed->iscompr = j > 1 ? 1 : 0;   // 只剩 1 个字符时压缩与非压缩布局相同, 统一按非压缩记
            trimmed->iskey = h->iskey;
            trimmed->isnull = h->isnull;
            if (h->iskey && !h->isnull) {
                void *ndata = raxGetData(h);
                raxSetData(trimmed,ndata);      // 原节点若是 key, key 身份跟着公共前缀走(前缀才是原 key 的终点)
            }
            raxNode **cp = raxNodeLastChildPtr(trimmed);
            memcpy(cp,&splitnode,sizeof(splitnode));
            memcpy(parentlink,&trimmed,sizeof(trimmed));
            parentlink = cp; /* Set parentlink to splitnode parent. */
            rax->numnodes++;
        }

        /* 4: Create the postfix node: what remains of the original
         * compressed node after the split. */
        if (postfixlen) {
            /* 4a: create a postfix node. */
            postfix->iskey = 0;
            postfix->isnull = 0;
            postfix->size = postfixlen;
            postfix->iscompr = postfixlen > 1;
            memcpy(postfix->data,h->data+j+1,postfixlen);
            raxNode **cp = raxNodeLastChildPtr(postfix);
            memcpy(cp,&next,sizeof(next));
            rax->numnodes++;
        } else {
            /* 4b: just use next as postfix node. */
            postfix = next;     // 失配正好在最后一个字符: 后缀为空, 直接接回原 child
        }

        /* 5: Set splitnode first child as the postfix node. */
        raxNode **splitchild = raxNodeLastChildPtr(splitnode);
        memcpy(splitchild,&postfix,sizeof(postfix));

        /* 6. Continue insertion: this will cause the splitnode to
         * get a new child (the non common character at the currently
         * inserted key). */
        raxFreeNode(rax,h);
        h = splitnode;
    } else if (h->iscompr && i == len) {
    /* ------------------------- ALGORITHM 2 --------------------------- */
        // ... 局面三: key 耗尽在压缩串中间(插 "ANNI" 到 "ANNIBALE"): 拆成 trimmed("ANNI") + postfix("BALE"),
        // ... key 落在 trimmed 上, 直接 return 1, 不用走下面的循环
    }

    /* We walked the radix tree as far as we could, but still there are left
     * chars in our string. We need to insert the missing nodes. */
    while(i < len) {
        raxNode *child;

        /* If this node is going to have a single child, and there
         * are other characters, so that that would result in a chain
         * of single-childed nodes, turn it into a compressed node. */
        if (h->size == 0 && len-i > 1) {    // 剩余部分是全新单链路径: 一次打包成压缩节点, 而不是一字符一节点
            debugf("Inserting compressed node\n");
            size_t comprsize = len-i;
            if (comprsize > RAX_NODE_MAX_SIZE)
                comprsize = RAX_NODE_MAX_SIZE;  // 29 bit 上限, 超长 key 拆成多个压缩节点接力
            raxNode *newh = raxCompressNode(rax,h,s+i,comprsize,&child);
            if (newh == NULL) goto oom;
            h = newh;
            memcpy(parentlink,&h,sizeof(h));
            parentlink = raxNodeLastChildPtr(h);
            i += comprsize;
        } else {
            debugf("Inserting normal node\n");
            raxNode **new_parentlink;
            raxNode *newh = raxAddChild(rax,h,s[i],&child,&new_parentlink);  // 按序插入新字符+新指针, 整个节点 realloc 重排
            if (newh == NULL) goto oom;
            h = newh;
            memcpy(parentlink,&h,sizeof(h));
            parentlink = new_parentlink;
            i++;
        }
        rax->numnodes++;
        h = child;
    }
    raxNode *newh = raxReallocForData(rax,h,data);
    if (newh == NULL) goto oom;
    h = newh;
    if (!h->iskey) rax->numele++;
    raxSetData(h,data);
    memcpy(parentlink,&h,sizeof(h));
    return 1; /* Element inserted. */

oom:
    // ... 半途 OOM: 把已建好的半截路径临时标成 key, 再调 raxRemove 原路回滚, 树恢复一致
    errno = ENOMEM;
    return 0;
}