// Redis 7.2 源码：src/intset.h
typedef struct intset {
    uint32_t encoding;  // 编码方式：int16_t/int32_t/int64_t
    uint32_t length;    // 元素个数
    int8_t contents[];  // 柔性数组，实际存储元素
} intset;

// src/intset.c - intsetUpgradeAndAdd 函数
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32(if(is->encoding));  // 当前编码
    uint8_t newenc = _intsetValueEncoding(value);  // 新编码
    int length = intrev32(if(is->length));
    int prepend = value < 0 ? 1 : 0;  // 是否需要向前插入（负数情况）
    
    // 重新分配内存空间
    is->encoding = intrev32(newenc);
    is = intsetResize(is, intrev32(if(is->length)) + 1);
    
    // 从后向前迁移数据，防止覆盖
    while(length--)
        _intsetSet(is, length + prepend, 
                   _intsetGetEncoded(is, length, curenc));
    
    // 插入新元素
    if (prepend)
        _intsetSet(is, 0, value);
    else
        _intsetSet(is, intrev32(if(is->length)), value);
    
    is->length = intrev32(if(is->length) + 1);
    return is;
}

// src/intset.c - intsetFind 函数
uint8_t intsetFind(intset *is, int64_t value) {
    uint8_t valenc = _intsetValueEncoding(value);
    // 编码不匹配直接返回 false
    if (valenc > intrev32(if(is->encoding))) return 0;
    
    // 二分查找
    return intsetSearch(is, value, NULL);
}

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32(if(is->length)) - 1;
    int64_t cur;
    
    // 空集合处理
    if (intrev32(if(is->length)) == 0) {
        if (pos) *pos = 0;
        return 0;
    }
    
    // 边界检查
    if (value > _intsetGet(is, max)) {
        if (pos) *pos = intrev32(if(is->length));
        return 0;
    }
    if (value < _intsetGet(is, 0)) {
        if (pos) *pos = 0;
        return 0;
    }
    
    // 二分查找主循环
    while(max >= min) {
        int mid = (min + max) >> 1;  // 无符号右移
        cur = _intsetGet(is, mid);
        
        if (value > cur) {
            min = mid + 1;
        } else if (value < cur) {
            max = mid - 1;
        } else {
            break;  // 找到目标值
        }
    }
    
    if (pos) *pos = min;
    return value == cur;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

// 模拟 intset 结构
typedef struct {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

int main() {
    // 创建一个 intset: [1, 2, 3]
    // 初始编码为 INT16 (假设)
    size_t size = sizeof(uint32_t) * 2 + sizeof(int16_t) * 3;
    intset *is = malloc(size);
    is->encoding = 2;  // INT16
    is->length = 3;
    
    // 设置元素
    int16_t *ptr = (int16_t *)is->contents;
    ptr[0] = 1;
    ptr[1] = 2;
    ptr[2] = 3;
    
    printf("intset created: [%d, %d, %d]\n", ptr[0], ptr[1], ptr[2]);
    
    free(is);
    return 0;
}

// Redis 7.2 源码：src/ziplist.h (简化版)
typedef struct {
    uint32_t bytes;      // ziplist 占用总字节数
    uint32_t tail_offset; // 尾部节点到起始位置的偏移量
    uint16_t length;     // 节点数量（当超过 2^14-1 时值为 2^14）
    uint8_t tail;        // 实际存储节点
} ziplist;

// src/ziplist.c - ziplistEncodeLength 函数
unsigned int ziplistEncodeLength(unsigned char *p, unsigned int len) {
    if (len < 254) {
        p[0] = len;
        return 1;
    } else {
        p[0] = 254;
        memwrite(p+1, len, 4);  // 小端序存储
        return 5;
    }
}

// src/ziplist.c - zipEntry 函数
#define ZIP_ENTRY_PTR(zl, offset) ((zl) + (offset))

void zipEntry(unsigned char *p, zlentry *e) {
    ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
    ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
    e->headersize = e->prevrawlensize + e->lensize;
    e->p = p;
}

// Redis 7.2 源码：src/server.h (简化版)
typedef struct zskiplistNode {
    sds ele;                      // 成员对象
    double score;                 // 分值
    struct zskiplistNode *backward;  // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 前进指针
        unsigned long span;             // 跨度
    } level[];                  // 层
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;  // 头尾节点
    unsigned long length;                 // 节点数量
    int level;                            // 最大层数
} zskiplist;

// Redis 7.2 源码：src/t_zset.c - zslInsert 函数
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    
    x = zsl->header;
    
    // 第一步：从高到低查找插入位置
    for (i = zsl->level-1; i >= 0; i--) {
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        
        while (x->level[i].forward &&
               (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                 sdscmp(x->level[i].forward->ele, ele) < 0)))
        {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    
    // 第二步：随机计算新节点的层数
    level = zslRandomLevel();
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    
    // 第三步：创建新节点并调整指针
    x = zslCreateNode(level, score, ele);
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
    
    // 处理高层节点的 span
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
    
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    
    zsl->length++;
    return x;
}

// 随机层数算法（幂次定律）
int zslRandomLevel(void) {
    int level = 1;
    // 25% 的概率增加一层
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

// Redis 7.2 源码：src/t_zset.c - zslDelete 函数
int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i;
    
    x = zsl->header;
    
    // 查找待删除节点及其前驱
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward &&
               (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                 sdscmp(x->level[i].forward->ele, ele) < 0)))
        {
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    
    x = x->level[0].forward;
    if (x && score == x->score && sdscmp(x->ele, ele) == 0) {
        // 从所有层中删除该节点
        for (i = 0; i < zsl->level; i++) {
            if (update[i]->level[i].forward == x) {
                update[i]->level[i].span += x->level[i].span - 1;
                update[i]->level[i].forward = x->level[i].forward;
            } else {
                update[i]->level[i].span -= 1;
            }
        }
        
        // 更新后退指针
        if (x->level[0].forward) {
            x->level[0].forward->backward = x->backward;
        } else {
            zsl->tail = x->backward;
        }
        
        // 移除空层
        while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL) {
            zsl->level--;
        }
        
        zsl->length--;
        if (node) *node = x;
        zslFreeNode(x);
        return 1;
    }
    return 0;
}

import redis
import time
import random

# 连接 Redis
r = redis.Redis(host='localhost', port=6379, db=0)

# ===== 1. intset 实战 =====
def demo_intset():
    """演示 intset 的使用"""
    print("=== intset 演示 ===")
    
    # 清空数据
    r.delete('myset')
    
    # 插入整数
    for i in [1, 2, 3, 100, 200]:
        r.sadd('myset', i)
    
    # 查看底层数据结构
    encoding = r.object('encoding', 'myset')
    print(f"编码类型: {encoding}")  # 应该是 intset
    
    # 验证元素
    members = r.smembers('myset')
    print(f"集合成员: {sorted(members)}")

# ===== 2. ziplist 实战 =====
def demo_ziplist():
    """演示 ziplist 的使用"""
    print("\n=== ziplist 演示 ===")
    
    # 清空数据
    r.delete('mylist')
    r.delete('myhash')
    
    # 列表使用 ziplist（元素少且短）
    r.rpush('mylist', 'a', 'b', 'c', 'd')
    encoding = r.object('encoding', 'mylist')
    print(f"列表编码: {encoding}")  # 应该是 ziplist
    
    # 哈希使用 ziplist
    r.hset('myhash', mapping={'name': 'Redis', 'type': 'DB'})
    encoding = r.object('encoding', 'myhash')
    print(f"哈希编码: {encoding}")  # 应该是 ziplist

# ===== 3. skiplist 实战 =====
def demo_skiplist():
    """演示 skiplist 的使用"""
    print("\n=== skiplist 演示 ===")
    
    # 清空数据
    r.delete('leaderboard')
    
    # 插入大量数据触发 skiplist 转换
    users = [
        ('user1', 100),
        ('user2', 200),
        ('user3', 150),
        ('user4', 300),
        ('user5', 250)
    ]
    
    for user, score in users:
        r.zadd('leaderboard', {user: score})
    
    # 查看底层数据结构
    encoding = r.object('encoding', 'leaderboard')
    print(f"有序集合编码: {encoding}")  # 可能是 skiplist
    
    # 范围查询（skiplist 的优势）
    print("\n排行榜前3名:")
    top3 = r.zrevrange('leaderboard', 0, 2, withscores=True)
    for rank, (user, score) in enumerate(top3, 1):
        print(f"  第{rank}名: {user} - {score}分")
    
    # 查找特定分数范围
    print("\n分数在 150-250 之间的用户:")
    range_users = r.zrangebyscore('leaderboard', 150, 250, withscores=True)
    for user, score in range_users:
        print(f"  {user}: {score}")

# ===== 4. 性能对比测试 =====
def benchmark_performance():
    """性能对比测试"""
    print("\n=== 性能对比测试 ===")
    
    # intset vs hashset（自动转换）
    r.delete('set_small')
    r.delete('set_large')
    
    # 小集合使用 intset
    start = time.time()
    for i in range(100):
        r.sadd('set_small', i)
    intset_time = time.time() - start
    
    # 大集合使用 hashtable
    start = time.time()
    for i in range(10000):
        r.sadd('set_large', i)
    hashtable_time = time.time() - start
    
    print(f"intset 插入 100 个元素: {intset_time:.6f} 秒")
    print(f"hashtable 插入 10000 个元素: {hashtable_time:.6f} 秒")
    print(f"小集合编码: {r.object('encoding', 'set_small')}")
    print(f"大集合编码: {r.object('encoding', 'set_large')}")

if __name__ == '__main__':
    demo_intset()
    demo_ziplist()
    demo_skiplist()
    benchmark_performance()

# 列表相关
list-max-ziplist-size -2  # 默认：每个元素不超过 64 字节
list-compress-depth 0     # 压缩深度，0 表示不压缩

# 哈希相关
hash-max-ziplist-entries 512  # 最大字段数
hash-max-ziplist-value 64     # 最大值长度（字节）

# 集合相关
set-max-intset-entries 512    # 使用 intset 的最大元素数

# 有序集合相关
zset-max-ziplist-entries 128  # 使用 ziplist 的最大元素数
zset-max-ziplist-value 64     # 最大成员长度（字节）

# 查看对象的编码
OBJECT encoding key

# 查看对象的内存占用
OBJECT memory key

# 查看对象引用数
OBJECT refcount key

# 查看底层信息（使用 MEMORY 命令）
MEMORY usage key

# 查看统计信息
INFO stats