struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;         /* 已使用长度，1字节 */
    uint8_t alloc;       /* 总分配长度，1字节 */
    unsigned char flags; /* 低3位是类型，高5位未使用 */
    char buf[];          /* 实际字符串内容 */
};

/* 伪代码：Listpack 的物理布局 */
struct ListpackLayout {
    uint32_t total_bytes;   // 整个包大小
    uint16_t num_elements;  // 元素个数
    
    // 接下来是 N 个 Entry，紧密排列
    struct Entry entries[] {
        // encoding: 包含类型和数据长度
        // data: 实际数据
        // len: 记录本 Entry 的总长度
    };
    
    uint8_t end_byte; // 固定为 0xFF
};

typedef struct listpackEx {
    ExpireMeta meta;
    void *lp;  /* listpack that contains field-value-ttl tuples */
} listpackEx;

小 List:
  redisObject(OBJ_LIST, LISTPACK) -> [a][b][c]

变大后:
  redisObject(OBJ_LIST, QUICKLIST)
    -> quicklistNode(listpack)
    -> quicklistNode(listpack)
    -> quicklistNode(listpack)

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* 所有 listpack 中的元素总数 */
    unsigned long len;          /* quicklistNode 节点个数 */
    size_t alloc_size;          /* 总分配内存（字节） */
    signed int fill : QL_FILL_BITS;       /* 单节点填充因子 */
    unsigned int compress : QL_COMP_BITS; /* 两端不压缩的节点深度；0=关闭压缩 */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *entry;
    size_t sz;             /* entry 占用字节数 */
    unsigned int count : 16;     /* 该 listpack 中的元素个数 */
    unsigned int encoding : 2;   /* RAW==1 或 LZF==2 */
    unsigned int container : 2;  /* PLAIN==1 或 PACKED==2 */
    unsigned int recompress : 1; /* 该节点是否需要重新压缩（临时解压后标记） */
    unsigned int attempted_compress : 1; /* 节点太小，无法压缩 */
    unsigned int dont_compress : 1; /* 禁止压缩（该 entry 稍后会被使用） */
    unsigned int extra : 9; /* 预留位，供未来使用 */
} quicklistNode;
typedef struct quicklistLZF {
    size_t sz; /* LZF 压缩后的字节数 */
    char compressed[];
} quicklistLZF;

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

/* 向 intset 中插入一个整数 */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 1;

    /* 必要时升级编码。需要升级时，新值必然在数组最前（< 0）或最后（> 0），
     * 因为它超出了当前编码的表示范围。 */
    if (valenc > intrev32ifbe(is->encoding)) {
        /* 升级操作必定成功，无需设置 *success */
        return intsetUpgradeAndAdd(is,value);
    } else {
        /* 二分查找判断值是否已存在。
         * 若不存在，pos 会被设置为应插入的位置。 */
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }

        is = intsetResize(is,intrev32ifbe(is->length)+1);
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    _intsetSet(is,pos,value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

/* 将 intset 升级到更宽的编码并插入指定整数 */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;

    /* 设置新编码并扩容 */
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* 从后向前迁移，避免覆盖未迁移的数据。
     * prepend 变量确保在数组开头或末尾留出空位。 */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* 将新值放在数组开头或末尾 */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

robj *setTypeCreate(sds value, size_t size_hint) {
    if (isSdsRepresentableAsLongLong(value,NULL) == C_OK &&
        size_hint <= server.set_max_intset_entries)
        return createIntsetObject();

    if (size_hint <= server.set_max_listpack_entries)
        return createSetListpackObject();

    robj *o = createSetObject();
    dictExpand(o->ptr, size_hint);
    return o;
}

intset + 整数
  -> 继续 intset；超过 intset 数量阈值则转 hashtable

intset + 非整数
  -> 如果整体仍适合 listpack，转 listpack
  -> 否则转 hashtable

listpack + 新元素
  -> 如果 entries/value/安全扩容检查都通过，继续 listpack
  -> 否则转 hashtable

typedef struct redisDb {
    kvstore *keys;      /* 当前 DB 的全部 key */
    kvstore *expires;   /* 设置了 TTL 的 key */
    estore *subexpires; /* sub-key 过期，目前主要用于 hash field */
} redisDb;

struct dict {
    dictType *type;

    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx; /* rehash 进度，-1 表示未进行 rehash */

    /* 注：pauserehash 使用完整的 unsigned，避免迭代器自增时
     * 与其他位域在同一存储单元上产生读-改-写冲突 */
    unsigned pauserehash; /* >0 时暂停 rehash */

    /* 小变量放末尾，优化结构体对齐填充 */
    signed char ht_size_exp[2]; /* 表大小的指数 (size = 1<<exp) */
    int16_t pauseAutoResize;  /* >0 时禁止自动扩缩容 (<0 表示编程错误) */
    void *metadata[];
};

struct dictEntry {
    struct dictEntry *next;  /* 必须为第一个字段 */
    void *key;               /* 必须为第二个字段 */
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
};

// Set 专用哈希表（无 value）
typedef struct dictEntryNoValue {
    dictEntry *next; /* 必须为第一个字段 */
    void *key;       /* 必须为第二个字段 */
} dictEntryNoValue;

/* 向哈希表中添加元素 */
int dictAdd(dict *d, void *key __stored_key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    if (!d->type->no_value) dictSetVal(d, entry, val);
    return DICT_OK;
}
dictEntry *dictAddRaw(dict *d, void *key __stored_key, dictEntry **existing)
{
    /* 获取新 key 的插入位置，若 key 已存在则返回 NULL */
    void *position = dictFindLinkForInsert(d, dictStoredKey2Key(d, key), existing);
    if (!position) return NULL;

    /* 必要时复制 key */
    if (d->type->keyDup) key = d->type->keyDup(d, key);

    return dictInsertKeyAtLink(d, key, position);
}

/* 查找 key 应插入的位置。若 key 不存在，返回待插入的 bucket 指针，
 * 配合 dictInsertKeyAtLink() 使用。若 key 已存在，返回 NULL，
 * 并通过 existing 参数返回已有的 entry。 */
dictEntryLink dictFindLinkForInsert(dict *d, const void *key, dictEntry **existing) {
    unsigned long idx, table;
    dictCmpCache cmpCache = {0};
    dictEntry *he;
    uint64_t hash = dictGetHash(d, key);
    if (existing) *existing = NULL;
    idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[0]);

    /* 必要时推进一步 rehash */
    _dictRehashStepIfNeeded(d,idx);

    /* 必要时扩容 */
    _dictExpandIfNeeded(d);
    keyCmpFunc cmpFunc = dictGetCmpFunc(d);

    for (table = 0; table <= 1; table++) {
        if (table == 0 && (long)idx < d->rehashidx) continue; 
        idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        /* 检查该 bucket 中是否已存在相同的 key */
        he = d->ht_table[table][idx];
        while(he) {
            const void *he_key = dictStoredKey2Key(d, dictGetKey(he));            
            if (key == he_key || cmpFunc(&cmpCache, key, he_key)) {
                if (existing) *existing = he;
                return NULL;
            }
            he = dictGetNext(he);
        }
        if (!dictIsRehashing(d)) break;
    }

    /* rehash 期间，新插入的 bucket 始终来自新表 ht_table[1] */
    dictEntry **bucket = &d->ht_table[dictIsRehashing(d) ? 1 : 0][idx];
    return bucket;
}

static void _dictRehashStepIfNeeded(dict *d, uint64_t visitedIdx) {
    if ((!dictIsRehashing(d)) || (d->pauserehash != 0))
        return;
    /* rehashidx == -1 表示未在 rehash */
    if ((long)visitedIdx >= d->rehashidx && d->ht_table[0][visitedIdx]) {
        /* 当前访问的 bucket 在 ht0 中有数据，就地迁移该 bucket（CPU 缓存友好） */
        _dictBucketRehash(d, visitedIdx);
    } else {
        /* ht0 中该位置无数据，按 rehashidx 顺序推进一步（缓存不友好） */
        dictRehash(d,1);
    }
}

/* dictRehash 和 dictBucketRehash 的辅助函数，
 * 将旧表 ht_table[0] 中下标为 idx 的 bucket 中所有 key 迁移到新表 */
static void rehashEntriesInBucketAtIndex(dict *d, uint64_t idx) {
    dictEntry *de = d->ht_table[0][idx];
    uint64_t h;
    dictEntry *nextde;
    while (de) {
        nextde = dictGetNext(de);
        void *storedKey = dictGetKey(de);
        /* 计算在新表中的下标 */
        if (d->ht_size_exp[1] > d->ht_size_exp[0]) {
            const void *key = dictStoredKey2Key(d, storedKey);
            h = dictGetHash(d, key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
        } else {
            /* 缩容场景。表大小是 2 的幂，
             * 直接对旧下标做位掩码即可得到新下标 */
            h = idx & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
        }
        if (d->type->no_value) {
            if (!d->ht_table[1][h]) {
                /* 目标 bucket 为空，可以直接将 key 编码进 bucket 指针，
                 * 无需分配 dictEntry。若旧 entry 是分配的，释放其内存 */                
                if (!entryIsKey(de)) zfree(decodeMaskedPtr(de));
                
                de = encodeEntryKey(d, storedKey);
                
            } else if (entryIsKey(de)) {
                /* 当前没有分配 entry 但目标 bucket 非空，需要分配一个 */
                de = createEntryNoValue(storedKey, d->ht_table[1][h]);
            } else {
                dictSetNext(de, d->ht_table[1][h]);
            }
        } else {
            dictSetNext(de, d->ht_table[1][h]);
        }
        d->ht_table[1][h] = de;
        d->ht_used[0]--;
        d->ht_used[1]++;
        de = nextde;
    }
    d->ht_table[0][idx] = NULL;
}

/* 返回 DICT_OK 表示已成功扩容或正在 rehash，无需额外处理。
 * 返回 DICT_ERR 表示未触发扩容（可考虑缩容） */
int dictExpandIfNeeded(dict *d) {
    /* 正在渐进式 rehash，直接返回 */
    if (dictIsRehashing(d)) return DICT_OK;

    /* 空表则初始化为默认大小 */
    if (DICTHT_SIZE(d->ht_size_exp[0]) == 0) {
        dictExpand(d, DICT_HT_INITIAL_SIZE);
        return DICT_OK;
    }

    /* 负载因子达到 1:1 且允许扩容，或负载因子
     * 超过强制扩容阈值，则扩容为原来的两倍 */
    if ((dict_can_resize == DICT_RESIZE_ENABLE &&
         d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0])) ||
        (dict_can_resize != DICT_RESIZE_FORBID &&
         d->ht_used[0] >= dict_force_resize_ratio * DICTHT_SIZE(d->ht_size_exp[0])))
    {
        if (dictTypeResizeAllowed(d, d->ht_used[0] + 1))
            dictExpand(d, d->ht_used[0] + 1);
        return DICT_OK;
    }
    return DICT_ERR;
}

/* ZSet 使用的跳跃表实现 */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        /* span 记录当前节点与该层下一个节点之间的距离。
         * 在 L0 层 span 始终为 1（末尾节点为 0），因此复用它存储节点层高，
         * 以便在排名计算时 O(1) 获取节点层数 */
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
    size_t alloc_size;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

[hllhdr][register 0][register 1] ... [register 16383]

ZSet:
  member = 地点名
  score  = geohash(lon, lat) 得到的 52 bit 整数

step = 26
lon_index = normalize(116.397) * 2^26
lat_index = normalize(39.908) * 2^26
score = interleave(lat_index, lon_index)   // bit 交错，得到 52 bit
ZADD shops score beijing

lat
 3 | .  .  .  .
 2 | .  .  C  .
 1 | .  .  A  B
 0 | .  .  .  .
     0  1  2  3  lon

lon = 2 = 10
lat = 1 = 01
score bits = 1 0 0 1 = 1001   // 交错后的一维编号

lat
 3 | 0101  0111  1101  1111
 2 | 0100  0110  1100  1110
 1 | 0001  0011  1001  1011
 0 | 0000  0010  1000  1010
       0     1     2     3   lon

streamID -> field-value 列表
1690000000000-0 -> user=42, action=login

stream
  rax
    1690000000000-0  -> listpack A
    1690000000123-0  -> listpack B
    1690000000456-0  -> listpack C

listpack
  master: [count][deleted][num-fields][user][action][0]
  entry1: [flags][ms-delta=0][seq-delta=0][42][login][lp-count]
  entry2: [flags][ms-delta=5][seq-delta=0][43][pay][lp-count]