Repository: valkey-io/valkey
File: src/t_zset.c (C)

Code before:
     * field is instead used for storing the height of the node. */
    x->level[0].span = height;
}

/* Create a skiplist node with the specified number of levels.
 * By embedding elements and levels into the skiplist nodes,
 * we achieve better cache-friendliness and a more compact memory structure.
 *
 * The memory layout is as follows:
 *
 *     +-------+------------------+---------+-----+---------+-------------+
 *     | score | backward-pointer | level-0 | ... | level-N | element-sds |
 *     +-------+------------------+---------+-----+---------+-------------+
 */
static zskiplistNode *zslCreateNode(int height, double score, sds ele) {
    size_t ele_sds_len = ele ? sdslen(ele) : 0;
    char ele_sds_type = ele ? sdsReqType(ele_sds_len) : 0;
    size_t ele_sds_size = ele ? sdsReqSize(ele_sds_len, ele_sds_type) : 0;
    /* Allocate enough space for the node, levels, and the element SDS string.
     * The +1 is for the header size of the SDS string. */
    zskiplistNode *zn = zmalloc(sizeof(*zn) + height * sizeof(struct zskiplistLevel) + 1 + ele_sds_size);
    zn->score = score;
    zslSetNodeHeight(zn, height);
    if (ele) {
        char *data = ((char *)(zn + 1)) + height * sizeof(struct zskiplistLevel);
        *data++ = sdsHdrSize(ele_sds_type);
        sdswrite(data, ele_sds_size, ele_sds_type, ele, ele_sds_len);
    }
    return zn;
}

sds zslGetNodeElement(const zskiplistNode *x) {
    unsigned char *data = (void *)(x + 1);
    data += zslGetNodeHeight(x) * sizeof(struct zskiplistLevel);
    uint8_t hdr_size = *(uint8_t *)data;
    data += 1 + hdr_size;
    return (sds)data;
}

/* Create a new skiplist. */
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL, 0, NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;

Review comment (suggestion):
Q: why do we need to maintain sds header size? can we just keep all pointers to the sds iteself and from there we can always reach the skiplist data... I think the most reasonable layout is?:
```
+------------------+--------+------+----------+------+---------------+
+ backward-pointer | level-N | ... | level-0 | score  |   element-sds |
+------------------+--------+------+----------+------+---------------+
                                                      |
                                                      |
                                                      Node ptr
```

Code after:
     * field is instead used for storing the height of the node. */
    x->level[0].span = height;
}

/* Create a skiplist node with the specified number of levels.
 * By embedding elements and levels into the skiplist nodes,
 * we achieve good cache-friendliness and a compact memory structure.
 *
 * The memory layout is as follows:
 *
 *   +-------+------------------+---------+-----+---------+-----------------+-------------+
 *   | score | backward-pointer | level-0 | ... | level-N | sds-header-size | element-sds |
 *   +-------+------------------+---------+-----+---------+-----------------+-------------+
 *
 *   sds-header-size and element-sds are only valid for non-header nodes.
 */
static zskiplistNode *zslCreateNode(int height, double score, const_sds ele) {
    size_t ele_sds_len = sdslen(ele);
    char ele_sds_type = sdsReqType(ele_sds_len);
    size_t ele_sds_size = sdsReqSize(ele_sds_len, ele_sds_type);
    /* Allocate enough space for the node, levels, and the element sds.
     * We include one extra byte representing the sds header size,
     * which is the offset into the embedded sds data where the
     * string content starts. */
    zskiplistNode *zn = zmalloc(sizeof(*zn) + height * sizeof(struct zskiplistLevel) + 1 + ele_sds_size);
    zn->score = score;
    zslSetNodeHeight(zn, height);
    char *data = ((char *)(zn + 1)) + height * sizeof(struct zskiplistLevel);
    *data++ = sdsHdrSize(ele_sds_type);
    sdswrite(data, ele_sds_size, ele_sds_type, ele, ele_sds_len);
    return zn;
}

static zskiplistNode *zslCreateHeaderNode(void) {
    /* Allocate enough space for the node and levels. */
    zskiplistNode *zn = zmalloc(sizeof(*zn) + ZSKIPLIST_MAXLEVEL * sizeof(struct zskiplistLevel));
    zslSetNodeHeight(zn, ZSKIPLIST_MAXLEVEL);
    return zn;
}

/* Helper function to return the element string from a skip list node. */
sds zslGetNodeElement(const zskiplistNode *x) {
    unsigned char *data = (void *)(x + 1);
    data += zslGetNodeHeight(x) * sizeof(struct zskiplistLevel);
    uint8_t hdr_size = *(uint8_t *)data;
    data += 1 + hdr_size;
    return (sds)data;
}

/* Create a new skiplist. */
zskiplist *zslCreate(void) {