Redis源码阅读 - Redis数据结构基数树(rax)

typedef struct rax {
    raxNode *head;    // rax的根节点，通常不保存任何字符串数据，也不代表任何 key
    uint64_t numele;  // 当前树中存储的 key 的数量
    uint64_t numnodes;  // 整个 rax 中的节点总数（raxNode 个数）
    size_t *alloc_size;  // 记录整个 rax 分配的内存总大小
    void *metadata[];    // 一个可变长度数组，用来存储额外信息
} rax;

typedef struct raxNode {
    uint32_t iskey:1;     // 节点是否包含key
    uint32_t isnull:1;    // 节点的值是否为NULL
    uint32_t iscompr:1;   // 是否是压缩节点
    uint32_t size:29;     // 节点大小
    unsigned char data[]; // 节点的实际存储数据
} raxNode;

#define RAX_STACK_STATIC_ITEMS 32
typedef struct raxStack {
    void **stack;      // 指向当前使用的“栈数组”
    size_t items, maxitems;   // 当前栈中有多少节点 & 当前栈的总容量
    void *static_items[RAX_STACK_STATIC_ITEMS]; // 一个内嵌的小数组,避免小规模使用时频繁 malloc
    int oom;   // 是否发生过内存分配失败（Out Of Memory）
} raxStack;

static inline void raxStackInit(raxStack *ts) {
    ts->stack = ts->static_items;      // 将当前使用的栈数据指向内部的数组
    ts->items = 0;                     // 设置当前栈中的节点数为0
    ts->maxitems = RAX_STACK_STATIC_ITEMS;  // 设置栈的总容量大小为32
    ts->oom = 0;                       // 记录栈申请内存失败的次数为0
}

static inline int raxStackPush(raxStack *ts, void *ptr) {
    if (ts->items == ts->maxitems) {   // 如果栈的节点数量已经达到最大，即和容量一样大时
        if (ts->stack == ts->static_items) {   // 如果目前使用的是内置数组，即当前栈中节点总数量为32
            ts->stack = rax_malloc(sizeof(void*)*ts->maxitems*2);   // 申请比当前容量扩大一倍的内存大小
            if (ts->stack == NULL) {   // 申请失败返回0
                ts->stack = ts->static_items;
                ts->oom = 1;
                errno = ENOMEM;
                return 0;
            }
            memcpy(ts->stack,ts->static_items,sizeof(void*)*ts->maxitems);   // 把内置数组中的数据拷贝到新申请的内存空间(不再使用内置数组)
        } else {                            // 这个分支代表当前栈中节点总数量已经超过32
            void **newalloc = rax_realloc(ts->stack,sizeof(void*)*ts->maxitems*2);
            if (newalloc == NULL) {
                ts->oom = 1;
                errno = ENOMEM;
                return 0;
            }
            ts->stack = newalloc;
        }
        ts->maxitems *= 2;
    }
    ts->stack[ts->items] = ptr;   // 给栈中数组的下一个指针设置为 入栈的节点 ptr
    ts->items++;    // 总节点数量 + 1
    return 1;
}

static inline void *raxStackPop(raxStack *ts) {
    if (ts->items == 0) return NULL;   // 如果栈内已经没数据，直接返回NULL
    ts->items--;                       // 栈内节点总数减1
    return ts->stack[ts->items];       // 返回当前栈顶的元素，即数组中节点总数-1 的索引位置
}

static inline void *raxStackPeek(raxStack *ts) {
    if (ts->items == 0) return NULL;
    return ts->stack[ts->items-1];
}

static inline void raxStackFree(raxStack *ts) {
    if (ts->stack != ts->static_items) rax_free(ts->stack);
}

rax *raxNewWithMetadata(int metaSize, size_t *alloc_size) {
    size_t usable;
    rax *rax = rax_malloc_usable(sizeof(*rax) + metaSize, &usable);  // 申请内存，并记录实际可以内存大小(操作系统一般会按照字节对齐比实际需求申请的大)
    if (rax == NULL) return NULL;
    rax->numele = 0;  // 设置key数量为0
    rax->numnodes = 1;  // 设置节点数量为1，即trax结构本身包含的根节点
    rax->alloc_size = alloc_size;  // 如果传入了内存大小就直接给属性赋值
    if (rax->alloc_size) *rax->alloc_size += usable;  // 如果没有传入即不需要携带额外数据，就把usable赋给rax->alloc_size
    rax->head = raxNewNode(rax, 0, 0);  // 创建根节点
    if (rax->head == NULL) {  // 如果根节点申请失败，就释放内存
        if (rax->alloc_size) *rax->alloc_size -= usable;
        rax_free(rax);
        return NULL;
    } else {
        return rax;
    }
}

rax *raxNew(void) {
    return raxNewWithMetadata(0, NULL);
}

raxNode *raxNewNode(rax *rax, size_t children, int datafield) {
    size_t nodesize = sizeof(raxNode)+children+raxPadding(children)+
                      sizeof(raxNode*)*children;
    if (datafield) nodesize += sizeof(void*);  // 计算所需要的内存大小
    size_t usable;
    raxNode *node = rax_malloc_usable(nodesize,&usable);  // 申请内存
    if (node == NULL) return NULL;
    node->iskey = 0;   // 新节点初始化
    node->isnull = 0;
    node->iscompr = 0;
    node->size = children;  // 设置节点的子节点数量
    if (rax->alloc_size) *rax->alloc_size += usable;  // 这个节点的申请内存记录到 rax->alloc_size 上，用于统计rax结果使用的总内存
    return node;
}

int raxFind(rax *rax, unsigned char *s, size_t len, void **value) {
    raxNode *h;
    int splitpos = 0;
    size_t i = raxLowWalk(rax,s,len,&h,NULL,&splitpos,NULL);
    if (i != len || (h->iscompr && splitpos != 0) || !h->iskey)
        return 0;
    if (value != NULL) *value = raxGetData(h);  // 通过raxGetData获取到key对应的value
    return 1;
}

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;  // 指向“当前节点指针的地址”

    size_t i = 0;                       // 当前匹配到字符串 s 的第几个字符
    size_t j = 0;                       // 当前在 node 内部的位置：压缩节点 → 在字符串里  普通节点 → 在 children 数组里
    while(h->size && i < len) {         // 主循环，循环条件是当前节点有内容，目标字符串未匹配完
        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;    // 判断是否完全匹配， 如果中途不匹配就break
        } else {                        // 普通节点，一个节点有多个分支（children）
            for (j = 0; j < h->size; j++) {   // 查找匹配的子节点
                if (v[j] == s[i]) break;
            }
            if (j == h->size) break;   // 没有对应分支 → 查找结束
            i++;                       // 找到了, i++ 消耗目标字符串一个字符
        }

        if (ts) raxStackPush(ts,h);    // 把当前节点压入栈, 用于插入时回溯或删除时修复
        raxNode **children = raxNodeFirstChildPtr(h);    // 跳到子节点 , 获取 children 指针数组
        if (h->iscompr) j = 0;          // 压缩节点：只有一个子节点 固定在 index 0
        memcpy(&h,children+j,sizeof(h));  // 
        parentlink = children+j;    // 当前节点在父节点里的位置
        j = 0;
    }
    if (stopnode) *stopnode = h;
    if (plink) *plink = parentlink;
    if (splitpos && h->iscompr) *splitpos = j;
    return i;     // 成功匹配了多少字符
}

int raxGenericInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old, int overwrite)

while(i < len) {     // 按照字符长度循环
        raxNode *child;
        if (h->size == 0 && len-i > 1) {    // 走这个分支，因为头节点的size=0，此时
            size_t comprsize = len-i;       // 计算压缩节点的长度
            raxNode *newh = raxCompressNode(rax,h,s+i,comprsize,&child);  // 申请一个新的压缩节点，并给这个压缩节点创建唯一的子节点，这个新的子节点为空。
            h = newh;
            memcpy(parentlink,&h,sizeof(h));
            parentlink = raxNodeLastChildPtr(h);  // 把 parentlink 移动到当前新节点 h 的“子节点指针槽位”，方便下一步继续往下挂节点
            i += comprsize;
        } 
        ......
        rax->numnodes++;   // rax的节点数量+1
        h = child;         // h指向压缩节点的子节点
    }
    ...
    raxNode *newh = raxReallocForData(rax,h,data);   // 给唯一的空子节点申请空间
    h = newh;
    if (!h->iskey) rax->numele++;
    raxSetData(h,data);           // 这里把子节点设置为key，并且把key对应的value值存储到这个空子节点。
    memcpy(parentlink,&h,sizeof(h));
    return 1; /* Element inserted. */

// 在 rax 中删除长度为 len 的 s
int raxRemove(rax *rax, unsigned char *s, size_t len, void **old);
// 释放 rax
void raxFree(rax *rax);
// 释放 rax, 释放每个 key 时，都会调用 free_callback 方法
void raxFreeWithCallback(rax *rax, void (*free_callback)(void*));

    raxNode *h;
    raxStack ts;
    
    raxStackInit(&ts); // 保存路径
    int splitpos = 0;
    size_t i = raxLowWalk(rax,s,len,&h,NULL,&splitpos,&ts);
    if (i != len || (h->iscompr && splitpos != 0) || !h->iskey) { // 未找到目标 key, 直接退出
        raxStackFree(&ts);
        return 0;
    }

typedef struct raxIterator {
    int flags;               // 控制迭代行为的标志位, 控制是否 EOF（结束）、是否处于 seek 状态等等
    rax *rt;                 // 当前遍历的 radix tree
    unsigned char *key;     // 前遍历到的 key（字符串）
    void *data;             // 当前 key 对应的 value
    size_t key_len;         // 当前 key 的长度
    size_t key_max;         // key buffer 当前最大容量
    unsigned char key_static_string[RAX_ITER_STATIC_LEN];   // 一个小的 栈上 buffer
    raxNode *node;          // 当前所在节点，只在 unsafe iteration（非安全迭代） 时使用
    raxStack stack;         // 遍历路径栈（核心）
    raxNodeCallback node_cb; // 节点回调函数（可选）
    void *privdata;         // 传给 node_cb 的上下文数据
} raxIterator;

void raxStart(raxIterator *it, rax *rt);
int raxSeek(raxIterator *it, const char *op, unsigned char *ele, size_t len);
int raxNext(raxIterator *it);
int raxPrev(raxIterator *it);