// 基于本地 Redis 仓 (unstable, 2026-03), src/server.h
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */   // 每升一层概率 1/4：期望上层节点数是下层的 1/4，塔更矮更省内存

/* Node info placed in level[0].span since it's unused at level 0 (static assert verified) */
typedef struct zskiplistNodeInfo {
    uint16_t sdsoffset;  /* Offset from node start to sds data (after sds header) */   // 节点首地址到内嵌 sds 数据的偏移
    uint8_t levels;      /* Number of levels in this node (1-32) */   // 本节点层高；老版节点自己不知道层高，要用时得额外传
    uint8_t reserved;
} zskiplistNodeInfo;

typedef struct zskiplistNode {
    double score;                       // 排序主键；score 相同再比成员字典序，保证全序
    struct zskiplistNode *backward;     // 后退指针只有一根（第 0 层），够 ZREVRANGE 反向走就行，省 31 根指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        /* Span is the number of elements between this node and the next node at this level.
         * At level 0, span is repurposed to store zskiplistNodeInfo for regular nodes, */
        unsigned long span;             // 跨度：到 forward 之间隔几个节点，ZRANK O(logN) 靠它；第 0 层跨度恒为 1，字段被挪用存 nodeInfo
    } level[];                          // 柔性数组，节点几层就分配几个
    /* sds ele is embedded after level[] array (assist zslGetNodeElement(node) to access it) */
    // 成员字符串直接内嵌在节点尾部：老版这里是 sds ele 指针，指向另一块独立分配的内存
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;  // header 是哨兵，不存数据，固定 32 层
    unsigned long length;                 // 节点数，不含 header
    int level;                            // 当前实际最高层，查找从这层起步而不是从 32 层
    size_t alloc_size;                    // 缓存总内存占用，MEMORY USAGE 不用遍历
} zskiplist;

typedef struct zset {
    dict *dict;      // 存跳表节点指针，按 member 查：ZSCORE 单点 O(1)
    zskiplist *zsl;  // 按 score 有序：范围/排名 O(logN)。双结构指向同一批节点，成员只存一份
} zset;

// 基于本地 Redis 仓 (unstable, 2026-03), src/t_zset.c
static inline unsigned long zslGetNodeSpanAtLevel(zskiplistNode *x, int level) {
    if (level > 0) return x->level[level].span;
    return x->level[0].forward ? 1 : 0;   // 第 0 层真实跨度必然是 1（尾节点 0），不用存，现场算
}
// ... zslSetNodeSpanAtLevel / zslIncrNodeSpanAtLevel / zslDecrNodeSpanAtLevel 同理：level 0 一律跳过不写

/* Get embedded sds from node. Uses the stored offset to directly access the sds data */
sds zslGetNodeElement(const zskiplistNode *node) {
    zskiplistNodeInfo *info = zslGetNodeInfo(node);
    debugServerAssert(info->sdsoffset != ZSL_OFFSET_NO_ELE);   // header 无成员，用哨兵偏移标记
    return (char*)node + info->sdsoffset;   // 指针加偏移直达，不经过第二次内存跳转
}

/* Compare {score, ele} with node. Returns: 1=bigger 0=equal -1=smaller */
int zslCompareWithNode(double score, sds ele, const zskiplistNode *n) {
    if (/*score < */ n == NULL) return -1; /* NULL is +infinity, comes after any real node */   // 把「走到本层末尾」统一成一次比较，循环条件不用单独判 NULL
    if (score < n->score) return -1;
    if (score > n->score) return 1;
    /* Scores are equal, compare elements lexicographically */
    return sdscmp(ele, zslGetNodeElement(n));
}

static int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1;
    while (random() < threshold)   // 每次 1/4 概率再升一层：概率均衡代替旋转再平衡，期望层高 O(logN)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

/* Insert an already-created node, with its score, element set into the skiplist
 * at the correct position. Updates all forward/backward pointers and spans. */
static void zslInsertNode(zskiplist *zsl, zskiplistNode *node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];  // 每层「插入点的前驱」，之后穿针引线全靠它
    unsigned long rank[ZSKIPLIST_MAXLEVEL];     // 每层前驱的排名，用来拆 span
    zskiplistNode *x;
    int i, level;
    double score = node->score;
    sds ele = zslGetNodeElement(node);
    level = zslGetNodeInfo(node)->levels;
    serverAssert(!isnan(score));                // NaN 无法全序比较，进来直接断言死

    /* Find the position where this node should be inserted */
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {       // 从最高层往下：每层向右走到「下一个就该更大」为止再降层，O(logN) 的来源
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];   // 下层排名接着上层累加，不用重算
        while (zslCompareWithNode(score, ele, x->level[i].forward) > 0) {
            rank[i] += zslGetNodeSpanAtLevel(x, i);
            x = x->level[i].forward;
        }
        update[i] = x;
    }

    /* Update skiplist level if needed */
    if (level > zsl->level) {                   // 新节点比整表还高：高出的层前驱只能是 header
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            zslSetNodeSpanAtLevel(update[i], i, zsl->length);   // header 在新层暂时跨过全表，下面会被拆
        }
        zsl->level = level;
        zslGetNodeInfo(zsl->header)->levels = level;
    }

    /* Insert the node at the found position */
    for (i = 0; i < level; i++) {               // 每层做一次链表插入，同时把前驱的 span 拆成两段
        node->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = node;

        /* update span covered by update[i] as node is inserted here */
        zslSetNodeSpanAtLevel(node, i, zslGetNodeSpanAtLevel(update[i], i) - (rank[0] - rank[i]));
        zslSetNodeSpanAtLevel(update[i], i, (rank[0] - rank[i]) + 1);   // rank[0]-rank[i] = 前驱到新节点的距离
    }

    /* increment span for untouched levels */
    for (i = level; i < zsl->level; i++) {
        zslIncrNodeSpanAtLevel(update[i], i, 1);   // 新节点没够到的高层：跨越它的 span 集体 +1，否则 ZRANK 全错
    }

    /* Update backward pointers */
    node->backward = (update[0] == zsl->header) ? NULL : update[0];   // backward 不指 header，反向遍历到 NULL 即停
    if (node->level[0].forward)
        node->level[0].forward->backward = node;
    else
        zsl->tail = node;

    zsl->length++;
}

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    int level;
    serverAssert(!isnan(score));
    // ... 注释省略：调用方需先查 dict 保证元素不存在
    level = zslRandomLevel();
    zskiplistNode *node = zslCreateNode(zsl, level, score, ele);   // 单块 zmalloc：节点头 + level[] + 内嵌 sds 一次分配
    zslInsertNode(zsl, node);
    return node;
}

/* Update the score of an element inside the sorted set skiplist. */
static void zslUpdateScore(zskiplist *zsl, zskiplistNode *node, double newscore) {
    /* Fast path: if the node, after the score update, would be still exactly
     * at the same position, we can just update the score without
     * actually removing and re-inserting the element in the skiplist. */
    if ((node->backward == NULL || node->backward->score < newscore) &&
        (node->level[0].forward == NULL || node->level[0].forward->score > newscore))
    {
        node->score = newscore;   // 没越过左右邻居就原地改，一根指针都不动；ZINCRBY 小步调分大多走这里
        return;
    }
    // ... 慢路径省略：重找 update[]，zslUnlinkNode 摘下 + 改 score + zslInsertNode 重挂，复用同一个节点
}

/* Find the rank for an element by both score and key.
 * Note that the rank is 1-based due to the span of zsl->header to the
 * first element. */
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x;
    unsigned long rank = 0;
    int i;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        while (zslCompareWithNode(score, ele, x->level[i].forward) >= 0) {   // >=：相等也前进，这样 rank 会把目标自己数进去
            rank += zslGetNodeSpanAtLevel(x, i);   // 查找顺路累加 span 就是排名，ZRANK 不用回头再数一遍
            x = x->level[i].forward;
        }

        if (x != zsl->header && zslCompareWithNode(score, ele, x) == 0) {
            return rank;
        }
    }
    return 0;   // 0 表示没找到，所以排名设计成 1-based
}

// 基于本地 Redis 仓 (unstable, 2026-03), src/t_zset.c
int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore) {
    // ... 参数与 listpack 分支省略：元素少走 listpack；超过 zset-max-listpack-entries/value
    //     时 zsetConvertAndExpand() 升级成 skiplist 编码，随后落进下面的分支
    if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        zset *zs = zobj->ptr;
        zskiplistNode *znode;
        dictEntry *de;
        dictEntryLink bucket, link;

        link = dictFindLink(zs->dict, ele, &bucket);   // 一次哈希查找同时拿到「存在与否」和「该插哪个桶」，新增路径省掉 dictAdd 的第二次查找

        if (link != NULL) {
            de = *link;
            // ... NX / GT / LT 短路省略
            znode = dictGetKey(de);     // dict 的 key 就是跳表节点指针，score 直接从节点上读，dict 不存 value
            curscore = znode->score;
            // ... INCR 加分与 NaN 检查省略

            /* Remove and re-insert when score changes. */
            if (score != curscore) {
                zslUpdateScore(zs->zsl, znode, score);   // 节点指针不变，所以 dict 完全不用动
                *out_flags |= ZADD_OUT_UPDATED;
            }
            return 1;
        } else if (!xx) {
            /* Element doesn't exist - create node with embedded sds and add to skiplist */
            znode = zslInsert(zs->zsl, score, ele);

            /* Add node pointer to dict using the bucket we already found */
            dictSetKeyAtLink(zs->dict, znode, &bucket, 1);   // 双结构各写一次，但成员字符串只存节点里那一份

            *out_flags |= ZADD_OUT_ADDED;
            if (newscore) *newscore = score;
            return 1;
        } else {
            *out_flags |= ZADD_OUT_NOP;
            return 1;
        }
    }
    // ...
}