typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* buf已保存的字符串字节数，不包含结束标示 */
    uint8_t alloc; /* buf申请的总的字节数，不包含结束标示 */
    unsigned char flags; /* 不同的SDS头类型 */
    char buf[];
};

typedef struct quicklist {
    quicklistNode *head;		// 头结点指针
    quicklistNode *tail;		// 尾结点指针
    unsigned long count;    	/* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev; // 前一个指针
    struct quicklistNode *next; // 后一个指针
    unsigned char *zl;  		// 当前结点的ziplist指针
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

# 存储一个哈希表key的键值
HSET key field value   
# 获取哈希表key对应的field键值
HGET key field

# 在一个哈希表key中存储多个键值对
HMSET key field value [field value...] 
# 批量获取哈希表key中多个field键值
HMGET key field [field ...]       
# 删除哈希表key中的field键值
HDEL key field [field ...]    

# 返回哈希表key中field的数量
HLEN key       
# 返回哈希表key中所有的键值
HGETALL key 

# 为哈希表key中field键的值加上增量n
HINCRBY key field n

typedef struct dict {
    dictType *type; 		// dict 类型，不同的哈希函数
    void *privdata;  		// 私有数据，做特殊hash的时候用
    dictht ht[2]; 			// 包含两个hash表，一个是当前数据，另个为空，rehash的时候用
    long rehashidx; 		// rehash的进度
    int16_t pauserehash;	// rehash是否暂停 
} dict;

typedef struct dictht {
    dictEntry **table;   		// 指向entry 的数组
    unsigned long size;  		// 哈希表大小
    unsigned long sizemask;   	// 掩码：size - 1
    unsigned long used;  		// entry 的个数
} dictht;

typedef struct dictEntry {
    void *key;  // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;// 值
    struct dictEntry *next;// 下一个结点
} dictEntry;

# 往集合key中存入元素，元素存在则忽略，若key不存在则新建
SADD key member [member ...]
# 从集合key中删除元素
SREM key member [member ...] 
# 获取集合key中所有元素
SMEMBERS key
# 获取集合key中的元素个数
SCARD key

# 判断member元素是否存在于集合key中
SISMEMBER key member

# 从集合key中随机选出count个元素，元素不从key中删除
SRANDMEMBER key [count]
# 从集合key中随机选出count个元素，元素从key中删除
SPOP key [count]

# 交集运算
SINTER key [key ...]
# 将交集结果存入新集合destination中
SINTERSTORE destination key [key ...]

# 并集运算
SUNION key [key ...]
# 将并集结果存入新集合destination中
SUNIONSTORE destination key [key ...]

# 差集运算
SDIFF key [key ...]
# 将差集结果存入新集合destination中
SDIFFSTORE destination key [key ...]

typedef struct intset {
    uint32_t encoding; 	// 编码方式
    uint32_t length; 	// 长度
    int8_t contents[]; 	// 存储位置
} intset;

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

# 往有序集合key中加入带分值元素
ZADD key score member [[score member]...]   
# 往有序集合key中删除元素
ZREM key member [member...]                 
# 返回有序集合key中元素member的分值
ZSCORE key member
# 返回有序集合key中元素个数
ZCARD key 

# 为有序集合key中元素member的分值加上increment
ZINCRBY key increment member 

# 正序获取有序集合key从start下标到stop下标的元素
ZRANGE key start stop [WITHSCORES]
# 倒序获取有序集合key从start下标到stop下标的元素
ZREVRANGE key start stop [WITHSCORES]

# 返回有序集合中指定分数区间内的成员，分数由低到高排序。
ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]

# 返回指定成员区间内的成员，按字典正序排列, 分数必须相同。
ZRANGEBYLEX key min max [LIMIT offset count]
# 返回指定成员区间内的成员，按字典倒序排列, 分数必须相同
ZREVRANGEBYLEX key max min [LIMIT offset count]

# 并集计算(相同元素分值相加)，numberkeys一共多少个key，WEIGHTS每个key对应的分值乘积
ZUNIONSTORE destkey numberkeys key [key...] 
# 交集计算(相同元素分值相加)，numberkeys一共多少个key，WEIGHTS每个key对应的分值乘积
ZINTERSTORE destkey numberkeys key [key...]

public class SkipList {

    private final int MAX_LEVEL = 32;

    private final double factor = 0.25;

    private int level = 1;

    /**
     * 头结点
     */
    private final Node head = new Node(null, MAX_LEVEL);

    static class Node {
        Integer value;
        Node[] next;
        int size;

        public Node(Integer value, int size) {
            this.value = value;
            this.size = size;
            this.next = new Node[size];
        }
    }

    public boolean search(int value) {

        Node p = head;
        for (int i = level - 1; i >= 0; i--) {
            while (p.next[i] != null && p.next[i].value <= value) {
                if (p.next[i].value == value) {
                    return true;
                }
                p = p.next[i];
            }
        }
        return false;
    }

    public void insert(int value) {
        int randomLevel = randomLevel();
        Node newNode = new Node(value, randomLevel);

        Node p = head;
        for (int i = level - 1; i >= 0; i--) {
            while (p.next[i] != null && p.next[i].value <= value) {
                p = p.next[i];
            }

            if (p.next[i] == null) {
                p.next[i] = newNode;
            } else {
                newNode.next[i] = p.next[i];
                p.next[i] = newNode;
            }
        }

        if (randomLevel > level) {
            for (int i = level ; i < randomLevel ; i++) {
                head.next[i] = newNode;
            }
            level = randomLevel;
        }
    }

    public boolean delete(int value) {
        boolean contain = search(value);
        Node p = head;
        Node h = null;
        if (contain) {
            for (int i = level - 1; i >= 0; i--) {
                while (p.next[i] != null && p.next[i].value <= value) {
                    h = p;
                    p = p.next[i];
                }
                h.next[i] = p.next[i];
            }
        }

        return contain;
    }

    private int randomLevel() {
        int level = 1;

        Random random = new Random();
        while (random.nextDouble() <= factor && level <= MAX_LEVEL) {
            level++;
        }
        return level;
    }
}