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

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

static inline void zslSetNodeHeight(zskiplistNode *x, int height) {
    /* Since the span at level 0 is always 1 (or 0 for the last node), this
     * 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, const_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));

Review comment (suggestion):
This extra byte deserves some more explanation. We've used it in other places where we embedded sds but the reader of this code might not be aware of that. Something like this?

```suggestion
    /* Allocate enough space for the node, levels, and the element SDS string.
     * Before the embedded 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. */
```

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

static inline void zslSetNodeHeight(zskiplistNode *x, int height) {
    /* Since the span at level 0 is always 1 (or 0 for the last node), this
     * 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;