基础的list相关的命令,t_list.c

rpush——rpushCommand

示例：RPUSH KEY_NAME VALUE1..VALUEN

  • 执行 RPUSH 操作后，列表的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
void rpushCommand(redisClient *c) {
    pushGenericCommand(c,REDIS_TAIL);
}
 
void pushGenericCommand(redisClient *c, int where) {
    int j, waiting = 0, pushed = 0;
    // 取出列表对象
    robj *lobj = lookupKeyWrite(c->db,c->argv[1]);
    // 如果列表对象不存在，那么可能有客户端在等待这个键的出现
    int may_have_waiting_clients = (lobj == NULL);
    if (lobj && lobj->type != REDIS_LIST) {
        addReply(c,shared.wrongtypeerr);
        return;
    }
    // 将列表状态设置为就绪
    if (may_have_waiting_clients) signalListAsReady(c,c->argv[1]);
    // 遍历所有输入值，并将它们添加到列表中
    for (j = 2; j < c->argc; j++) {
        // 编码值
        c->argv[j] = tryObjectEncoding(c->argv[j]);
        // 如果列表对象不存在，那么创建一个，并关联到数据库
        if (!lobj) {
            lobj = createZiplistObject();
            dbAdd(c->db,c->argv[1],lobj);
        }
        // 将值推入到列表
        listTypePush(lobj,c->argv[j],where);
        pushed++;
    }
    // 返回添加的节点数量
    addReplyLongLong(c, waiting + (lobj ? listTypeLength(lobj) : 0));
    // 如果至少有一个元素被成功推入，那么执行以下代码
    if (pushed) {
        char *event = (where == REDIS_HEAD) ? "lpush" : "rpush";
        // 发送键修改信号
        signalModifiedKey(c->db,c->argv[1]);
        // 发送事件通知
        notifyKeyspaceEvent(REDIS_NOTIFY_LIST,event,c->argv[1],c->db->id);
    }
    server.dirty += pushed;
}
  
/* The function pushes an element to the specified list object 'subject',
 * at head or tail position as specified by 'where'.
 *
 * 将给定元素添加到列表的表头或表尾。
 *
 * 参数 where 决定了新元素添加的位置：
 *
 *  - REDIS_HEAD 将新元素添加到表头
 *
 *  - REDIS_TAIL 将新元素添加到表尾
 *
 * There is no need for the caller to increment the refcount of 'value' as
 * the function takes care of it if needed.
 *
 * 调用者无须担心 value 的引用计数，因为这个函数会负责这方面的工作。
 */
void listTypePush(robj *subject, robj *value, int where) {
    /* Check if we need to convert the ziplist */
    // 是否需要转换编码？
    listTypeTryConversion(subject,value);
    if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
        ziplistLen(subject->ptr) >= server.list_max_ziplist_entries)
            listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
    // ZIPLIST
    if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
        int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
        // 取出对象的值，因为 ZIPLIST 只能保存字符串或整数
        value = getDecodedObject(value);
        subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),pos);
        decrRefCount(value);
    // 双端链表
    } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
        if (where == REDIS_HEAD) {
            listAddNodeHead(subject->ptr,value);
        } else {
            listAddNodeTail(subject->ptr,value);
        }
        incrRefCount(value);
    // 未知编码
    } else {
        redisPanic("Unknown list encoding");
    }
}

说明：需要判断是压缩列表还是双端链表，并且根据value值，判断是否需要从压缩列表转换到双端列表；并根据插入列头还是列尾选用不同的方式。

复杂度：压缩列表O(N), 最坏O(N2) 连锁更新; 双端列表：O(1)

lpush——lpushCommand

示例: LPUSH KEY_NAME VALUE1.. VALUEN

  • 执行 LPUSH 命令后，列表的长度。
1
2
3
void lpushCommand(redisClient *c) {
    pushGenericCommand(c,REDIS_HEAD);
}

说明\复杂度： 同rpushCommand

rpushx——rpushxCommand

示例：RPUSHX KEY_NAME VALUE1..VALUEN

  • 执行 Rpushx 操作后，列表的长度。如果列表不存在，则操作无效
1
2
3
4
void rpushxCommand(redisClient *c) {
    c->argv[2] = tryObjectEncoding(c->argv[2]);
    pushxGenericCommand(c,NULL,c->argv[2],REDIS_TAIL);
}

说明\复杂度： 同rpushCommand

lpushx——lpushxCommand

示例：LPUSHX KEY_NAME VALUE1.. VALUEN

  • LPUSHX 命令执行之后，列表的长度。
1
2
3
4
void lpushxCommand(redisClient *c) {
    c->argv[2] = tryObjectEncoding(c->argv[2]);
    pushxGenericCommand(c,NULL,c->argv[2],REDIS_HEAD);
}

说明\复杂度： 同rpushCommand

linsert——linsertCommand

示例：LINSERT key BEFORE|AFTER pivot value

  • 如果命令执行成功，返回插入操作完成之后，列表的长度。 如果没有找到指定元素 ，返回 -1 。 如果 key 不存在或为空列表，返回 0 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
void linsertCommand(redisClient *c) {
    // 编码 refval 对象
    c->argv[4] = tryObjectEncoding(c->argv[4]);
    if (strcasecmp(c->argv[2]->ptr,"after") == 0) {
        pushxGenericCommand(c,c->argv[3],c->argv[4],REDIS_TAIL);
    } else if (strcasecmp(c->argv[2]->ptr,"before") == 0) {
        pushxGenericCommand(c,c->argv[3],c->argv[4],REDIS_HEAD);
    } else {
        addReply(c,shared.syntaxerr);
    }
}
  
void pushxGenericCommand(redisClient *c, robj *refval, robj *val, int where) {
    robj *subject;
    listTypeIterator *iter;
    listTypeEntry entry;
    int inserted = 0;
    // 取出列表对象
    if ((subject = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
        checkType(c,subject,REDIS_LIST)) return;
    // 执行的是 LINSERT 命令
    if (refval != NULL) {
        /* We're not sure if this value can be inserted yet, but we cannot
         * convert the list inside the iterator. We don't want to loop over
         * the list twice (once to see if the value can be inserted and once
         * to do the actual insert), so we assume this value can be inserted
         * and convert the ziplist to a regular list if necessary. */
        // 看保存值 value 是否需要将列表编码转换为双端链表
        listTypeTryConversion(subject,val);
        /* Seek refval from head to tail */
        // 在列表中查找 refval 对象
        iter = listTypeInitIterator(subject,0,REDIS_TAIL);
        while (listTypeNext(iter,&entry)) {
            if (listTypeEqual(&entry,refval)) {
                // 找到了，将值插入到节点的前面或后面
                listTypeInsert(&entry,val,where);
                inserted = 1;
                break;
            }
        }
        listTypeReleaseIterator(iter);
        if (inserted) {
            /* Check if the length exceeds the ziplist length threshold. */
            // 查看插入之后是否需要将编码转换为双端链表
            if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
                ziplistLen(subject->ptr) > server.list_max_ziplist_entries)
                    listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
            signalModifiedKey(c->db,c->argv[1]);
            notifyKeyspaceEvent(REDIS_NOTIFY_LIST,"linsert",
                                c->argv[1],c->db->id);
            server.dirty++;
        } else {
            /* Notify client of a failed insert */
            // refval 不存在，插入失败
            addReply(c,shared.cnegone);
            return;
        }
    // 执行的是 LPUSHX 或 RPUSHX 命令
    } else {
        char *event = (where == REDIS_HEAD) ? "lpush" : "rpush";
        listTypePush(subject,val,where);
        signalModifiedKey(c->db,c->argv[1]);
        notifyKeyspaceEvent(REDIS_NOTIFY_LIST,event,c->argv[1],c->db->id);
        server.dirty++;
    }
    addReplyLongLong(c,listTypeLength(subject));
}

说明：列表中插入新节点，双向列表很容易插入；压缩列表可能引起连锁更新

复杂度：压缩列表O(N), 最坏O(N2) 连锁更新; 双端列表：O(1)

rpop——rpopCommand

示例：RPOP KEY_NAME

  • 列表的最后一个元素。 当列表不存在时，返回 nil 。
1
2
3
void rpopCommand(redisClient *c) {
    popGenericCommand(c,REDIS_TAIL);
}

说明：列表中删除新节点，双向列表很容易删除；压缩列表可能引起连锁更新

复杂度：压缩列表O(N), 最坏O(N2) 连锁更新; 双端列表：O(1)

lpop——lpopCommand

示例：Lpop KEY_NAME

  • 列表的第一个元素。 当列表 key 不存在时，返回 nil 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void lpopCommand(redisClient *c) {
    popGenericCommand(c,REDIS_HEAD);
}
void popGenericCommand(redisClient *c, int where) {
    // 取出列表对象
    robj *o = lookupKeyWriteOrReply(c,c->argv[1],shared.nullbulk);
    if (o == NULL || checkType(c,o,REDIS_LIST)) return;
    // 弹出列表元素
    robj *value = listTypePop(o,where);
    // 根据弹出元素是否为空，决定后续动作
    if (value == NULL) {
        addReply(c,shared.nullbulk);
    } else {
        char *event = (where == REDIS_HEAD) ? "lpop" : "rpop";
        addReplyBulk(c,value);
        decrRefCount(value);
        notifyKeyspaceEvent(REDIS_NOTIFY_LIST,event,c->argv[1],c->db->id);
        if (listTypeLength(o) == 0) {
            notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",
                                c->argv[1],c->db->id);
            dbDelete(c->db,c->argv[1]);
        }
        signalModifiedKey(c->db,c->argv[1]);
        server.dirty++;
    }
}

说明：列表中删除新节点，双向列表很容易删除；压缩列表可能引起连锁更新

复杂度：压缩列表O(N), 最坏O(N2) 连锁更新; 双端列表：O(1)

brpop——brpopCommand

示例：BRPOP LIST1 LIST2 .. LISTN TIMEOUT

  • 假如在指定时间内没有任何元素被弹出，则返回一个 nil 和等待时长。 反之，返回一个含有两个元素的列表，第一个元素是被弹出元素所属的 key ，第二个元素是被弹出元素的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
void brpopCommand(redisClient *c) {
    blockingPopGenericCommand(c,REDIS_TAIL);
}
 
 
/* Blocking RPOP/LPOP */
void blockingPopGenericCommand(redisClient *c, int where) {
    robj *o;
    mstime_t timeout;
    int j;
    // 取出 timeout 参数
    if (getTimeoutFromObjectOrReply(c,c->argv[c->argc-1],&timeout,UNIT_SECONDS)
        != REDIS_OK) return;
    // 遍历所有列表键
    for (j = 1; j < c->argc-1; j++) {
        // 取出列表键
        o = lookupKeyWrite(c->db,c->argv[j]);
        // 有非空列表？
        if (o != NULL) {
            if (o->type != REDIS_LIST) {
                addReply(c,shared.wrongtypeerr);
                return;
            } else {
                // 非空列表
                if (listTypeLength(o) != 0) {
                    /* Non empty list, this is like a non normal [LR]POP. */
                    char *event = (where == REDIS_HEAD) ? "lpop" : "rpop";
                    // 弹出值
                    robj *value = listTypePop(o,where);
                    redisAssert(value != NULL);
                    // 回复客户端
                    addReplyMultiBulkLen(c,2);
                    // 回复弹出元素的列表
                    addReplyBulk(c,c->argv[j]);
                    // 回复弹出值
                    addReplyBulk(c,value);
                    decrRefCount(value);
                    notifyKeyspaceEvent(REDIS_NOTIFY_LIST,event,
                                        c->argv[j],c->db->id);
                    // 删除空列表
                    if (listTypeLength(o) == 0) {
                        dbDelete(c->db,c->argv[j]);
                        notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",
                                            c->argv[j],c->db->id);
                    }
                    signalModifiedKey(c->db,c->argv[j]);
                    server.dirty++;
                    /* Replicate it as an [LR]POP instead of B[LR]POP. */
                    // 传播一个 [LR]POP 而不是 B[LR]POP
                    rewriteClientCommandVector(c,2,
                        (where == REDIS_HEAD) ? shared.lpop : shared.rpop,
                        c->argv[j]);
                    return;
                }
            }
        }
    }
    /* If we are inside a MULTI/EXEC and the list is empty the only thing
     * we can do is treating it as a timeout (even with timeout 0). */
    // 如果命令在一个事务中执行，那么为了不产生死等待
    // 服务器只能向客户端发送一个空回复
    if (c->flags & REDIS_MULTI) {
        addReply(c,shared.nullmultibulk);
        return;
    }
    /* If the list is empty or the key does not exists we must block */
    // 所有输入列表键都不存在，只能阻塞了
    blockForKeys(c, c->argv + 1, c->argc - 2, timeout, NULL);
}
void blockForKeys(redisClient *c, robj **keys, int numkeys, mstime_t timeout, robj *target) {
    dictEntry *de;
    list *l;
    int j;
    // 设置阻塞状态的超时和目标选项
    c->bpop.timeout = timeout;
    // target 在执行 RPOPLPUSH 命令时使用
    c->bpop.target = target;
    if (target != NULL) incrRefCount(target);
    // 关联阻塞客户端和键的相关信息
    for (j = 0; j < numkeys; j++) {
        /* If the key already exists in the dict ignore it. */
        // c->bpop.keys 是一个集合（值为 NULL 的字典）
        // 它记录所有造成客户端阻塞的键
        // 以下语句在键不存在于集合的时候，将它添加到集合
        if (dictAdd(c->bpop.keys,keys[j],NULL) != DICT_OK) continue;
        incrRefCount(keys[j]);
        /* And in the other "side", to map keys -> clients */
        // c->db->blocking_keys 字典的键为造成客户端阻塞的键
        // 而值则是一个链表，链表中包含了所有被阻塞的客户端
        // 以下程序将阻塞键和被阻塞客户端关联起来
        de = dictFind(c->db->blocking_keys,keys[j]);
        if (de == NULL) {
            // 链表不存在，新创建一个，并将它关联到字典中
            int retval;
            /* For every key we take a list of clients blocked for it */
            l = listCreate();
            retval = dictAdd(c->db->blocking_keys,keys[j],l);
            incrRefCount(keys[j]);
            redisAssertWithInfo(c,keys[j],retval == DICT_OK);
        } else {
            l = dictGetVal(de);
        }
        // 将客户端填接到被阻塞客户端的链表中
        listAddNodeTail(l,c);
    }
    blockClient(c,REDIS_BLOCKED_LIST);
}

说明：如果多个列表中，任意有一个有value，则直接返回value，删除列表中的value；

都无value，则直接阻塞，会在db->blocking_keys 的dict中记录对应的客户端，如key是LIST1，value是列表，列表中记录阻塞的客户端

其中，timeout是必传项，如果最后一个不是整数，会报错

复杂度：压缩列表O(N), 最坏O(N2) 连锁更新; 双端列表：O(1)

brpoplpush——brpoplpushCommand

示例：BRPOPLPUSH LIST1 ANOTHER_LIST TIMEOUT

  • 假如在指定时间内没有任何元素被弹出，则返回一个 nil 和等待时长。 反之，返回一个含有两个元素的列表，第一个元素是被弹出元素所属的 key ，第二个元素是被弹出元素的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void brpoplpushCommand(redisClient *c) {
    mstime_t timeout;
    // 取出 timeout 参数
    if (getTimeoutFromObjectOrReply(c,c->argv[3],&timeout,UNIT_SECONDS)
        != REDIS_OK) return;
    // 取出列表键
    robj *key = lookupKeyWrite(c->db, c->argv[1]);
    // 键为空，阻塞
    if (key == NULL) {
        if (c->flags & REDIS_MULTI) {
            /* Blocking against an empty list in a multi state
             * returns immediately. */
            addReply(c, shared.nullbulk);
        } else {
            /* The list is empty and the client blocks. */
            blockForKeys(c, c->argv + 1, 1, timeout, c->argv[2]);
        }
    // 键非空，执行 RPOPLPUSH
    } else {
        if (key->type != REDIS_LIST) {
            addReply(c, shared.wrongtypeerr);
        } else {
            /* The list exists and has elements, so
             * the regular rpoplpushCommand is executed. */
            redisAssertWithInfo(c,key,listTypeLength(key) > 0);
            rpoplpushCommand(c);
        }
    }
}

说明：pop和push的命令组合

blpop——blpopCommand

示例：BLPOP LIST1 LIST2 .. LISTN TIMEOUT

  • 如果列表为空，返回一个 nil 。 否则，返回一个含有两个元素的列表，第一个元素是被弹出元素所属的 key ，第二个元素是被弹出元素的值。
1
2
3
void blpopCommand(redisClient *c) {
    blockingPopGenericCommand(c,REDIS_HEAD);
}

说明：同brpopCommand

llen——llenCommand

示例：LLEN KEY_NAME

  • 列表的长度。
1
2
3
4
5
void llenCommand(redisClient *c) {
    robj *o = lookupKeyReadOrReply(c,c->argv[1],shared.czero);
    if (o == NULL || checkType(c,o,REDIS_LIST)) return;
    addReplyLongLong(c,listTypeLength(o));
}

说明：获取列表长度

复杂度：O(1)

lindex——lindexCommand

示例:LINDEX KEY_NAME INDEX_POSITION

  • 列表中下标为指定索引值的元素。 如果指定索引值不在列表的区间范围内，返回 nil 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void lindexCommand(redisClient *c) {
    robj *o = lookupKeyReadOrReply(c,c->argv[1],shared.nullbulk);
    if (o == NULL || checkType(c,o,REDIS_LIST)) return;
    long index;
    robj *value = NULL;
    // 取出整数值对象 index
    if ((getLongFromObjectOrReply(c, c->argv[2], &index, NULL) != REDIS_OK))
        return;
    // 根据索引，遍历 ziplist ，直到指定位置
    if (o->encoding == REDIS_ENCODING_ZIPLIST) {
        unsigned char *p;
        unsigned char *vstr;
        unsigned int vlen;
        long long vlong;
        p = ziplistIndex(o->ptr,index);
        if (ziplistGet(p,&vstr,&vlen,&vlong)) {
            if (vstr) {
                value = createStringObject((char*)vstr,vlen);
            } else {
                value = createStringObjectFromLongLong(vlong);
            }
            addReplyBulk(c,value);
            decrRefCount(value);
        } else {
            addReply(c,shared.nullbulk);
        }
    // 根据索引，遍历双端链表，直到指定位置
    } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) {
        listNode *ln = listIndex(o->ptr,index);
        if (ln != NULL) {
            value = listNodeValue(ln);
            addReplyBulk(c,value);
        } else {
            addReply(c,shared.nullbulk);
        }
    } else {
        redisPanic("Unknown list encoding");
    }
}

说明：获取index节点的value

复杂度: O(N)

lset——lsetCommand

示例：LSET KEY_NAME INDEX VALUE

  • 操作成功返回 ok ，否则返回错误信息。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
void lsetCommand(redisClient *c) {
    // 取出列表对象
    robj *o = lookupKeyWriteOrReply(c,c->argv[1],shared.nokeyerr);
    if (o == NULL || checkType(c,o,REDIS_LIST)) return;
    long index;
    // 取出值对象 value
    robj *value = (c->argv[3] = tryObjectEncoding(c->argv[3]));
    // 取出整数值对象 index
    if ((getLongFromObjectOrReply(c, c->argv[2], &index, NULL) != REDIS_OK))
        return;
    // 查看保存 value 值是否需要转换列表的底层编码
    listTypeTryConversion(o,value);
    // 设置到 ziplist
    if (o->encoding == REDIS_ENCODING_ZIPLIST) {
        unsigned char *p, *zl = o->ptr;
        // 查找索引
        p = ziplistIndex(zl,index);
        if (p == NULL) {
            addReply(c,shared.outofrangeerr);
        } else {
            // 删除现有的值
            o->ptr = ziplistDelete(o->ptr,&p);
            // 插入新值到指定索引
            value = getDecodedObject(value);
            o->ptr = ziplistInsert(o->ptr,p,value->ptr,sdslen(value->ptr));
            decrRefCount(value);
            addReply(c,shared.ok);
            signalModifiedKey(c->db,c->argv[1]);
            notifyKeyspaceEvent(REDIS_NOTIFY_LIST,"lset",c->argv[1],c->db->id);
            server.dirty++;
        }
    // 设置到双端链表
    } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) {
        listNode *ln = listIndex(o->ptr,index);
        if (ln == NULL) {
            addReply(c,shared.outofrangeerr);
        } else {
            // 删除旧值对象
            decrRefCount((robj*)listNodeValue(ln));
            // 指向新对象
            listNodeValue(ln) = value;
            incrRefCount(value);
            addReply(c,shared.ok);
            signalModifiedKey(c->db,c->argv[1]);
            notifyKeyspaceEvent(REDIS_NOTIFY_LIST,"lset",c->argv[1],c->db->id);
            server.dirty++;
        }
    } else {
        redisPanic("Unknown list encoding");
    }
}

说明：在index节点的插入key，value

复杂度：压缩列表O(N), 最坏O(N2) 连锁更新; 双端列表：O(1)，只要涉及到列表的新增，删除，修改，压缩列表最坏情况都是O(N2)；所以在复杂度上压缩列表整体更好，只是在内存占用上有优势，性能和内存折中的结果。

lrange——lrangeCommand

示例：LRANGE KEY_NAME START END

  • 一个列表，包含指定区间内的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
void lrangeCommand(redisClient *c) {
    robj *o;
    long start, end, llen, rangelen;
    // 取出索引值 start 和 end
    if ((getLongFromObjectOrReply(c, c->argv[2], &start, NULL) != REDIS_OK) ||
        (getLongFromObjectOrReply(c, c->argv[3], &end, NULL) != REDIS_OK)) return;
    // 取出列表对象
    if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptymultibulk)) == NULL
         || checkType(c,o,REDIS_LIST)) return;
    // 取出列表长度
    llen = listTypeLength(o);
    /* convert negative indexes */
    // 将负数索引转换成正数索引
    if (start < 0) start = llen+start;
    if (end < 0) end = llen+end;
    if (start < 0) start = 0;
    /* Invariant: start >= 0, so this test will be true when end < 0.
     * The range is empty when start > end or start >= length. */
    if (start > end || start >= llen) {
        addReply(c,shared.emptymultibulk);
        return;
    }
    if (end >= llen) end = llen-1;
    rangelen = (end-start)+1;
    /* Return the result in form of a multi-bulk reply */
    addReplyMultiBulkLen(c,rangelen);
    if (o->encoding == REDIS_ENCODING_ZIPLIST) {
        unsigned char *p = ziplistIndex(o->ptr,start);
        unsigned char *vstr;
        unsigned int vlen;
        long long vlong;
        // 遍历 ziplist ，并将指定索引上的值添加到回复中
        while(rangelen--) {
            ziplistGet(p,&vstr,&vlen,&vlong);
            if (vstr) {
                addReplyBulkCBuffer(c,vstr,vlen);
            } else {
                addReplyBulkLongLong(c,vlong);
            }
            p = ziplistNext(o->ptr,p);
        }
    } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) {
        listNode *ln;
        /* If we are nearest to the end of the list, reach the element
         * starting from tail and going backward, as it is faster. */
        if (start > llen/2) start -= llen;
        ln = listIndex(o->ptr,start);
        // 遍历双端链表，将指定索引上的值添加到回复
        while(rangelen--) {
            addReplyBulk(c,ln->value);
            ln = ln->next;
        }
    } else {
        redisPanic("List encoding is not LINKEDLIST nor ZIPLIST!");
    }
}

ltrim——ltrimCommand

示例：LTRIM KEY_NAME START STOP

  • 命令执行成功时，返回 ok 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
void ltrimCommand(redisClient *c) {
    robj *o;
    long start, end, llen, j, ltrim, rtrim;
    list *list;
    listNode *ln;
    // 取出索引值 start 和 end
    if ((getLongFromObjectOrReply(c, c->argv[2], &start, NULL) != REDIS_OK) ||
        (getLongFromObjectOrReply(c, c->argv[3], &end, NULL) != REDIS_OK)) return;
    // 取出列表对象
    if ((o = lookupKeyWriteOrReply(c,c->argv[1],shared.ok)) == NULL ||
        checkType(c,o,REDIS_LIST)) return;
    // 列表长度
    llen = listTypeLength(o);
    /* convert negative indexes */
    // 将负数索引转换成正数索引
    if (start < 0) start = llen+start;
    if (end < 0) end = llen+end;
    if (start < 0) start = 0;
    /* Invariant: start >= 0, so this test will be true when end < 0.
     * The range is empty when start > end or start >= length. */
    if (start > end || start >= llen) {
        /* Out of range start or start > end result in empty list */
        ltrim = llen;
        rtrim = 0;
    } else {
        if (end >= llen) end = llen-1;
        ltrim = start;
        rtrim = llen-end-1;
    }
    /* Remove list elements to perform the trim */
    // 删除指定列表两端的元素
    if (o->encoding == REDIS_ENCODING_ZIPLIST) {
        // 删除左端元素
        o->ptr = ziplistDeleteRange(o->ptr,0,ltrim);
        // 删除右端元素
        o->ptr = ziplistDeleteRange(o->ptr,-rtrim,rtrim);
    } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) {
        list = o->ptr;
        // 删除左端元素
        for (j = 0; j < ltrim; j++) {
            ln = listFirst(list);
            listDelNode(list,ln);
        }
        // 删除右端元素
        for (j = 0; j < rtrim; j++) {
            ln = listLast(list);
            listDelNode(list,ln);
        }
    } else {
        redisPanic("Unknown list encoding");
    }
    // 发送通知
    notifyKeyspaceEvent(REDIS_NOTIFY_LIST,"ltrim",c->argv[1],c->db->id);
    // 如果列表已经为空，那么删除它
    if (listTypeLength(o) == 0) {
        dbDelete(c->db,c->argv[1]);
        notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",c->argv[1],c->db->id);
    }
    signalModifiedKey(c->db,c->argv[1]);
    server.dirty++;
    addReply(c,shared.ok);
}

说明：删除某一端的一段数据

lrem——lremCommand

示例：LREM KEY_NAME COUNT VALUE

  • 被移除元素的数量。 列表不存在时返回 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void lremCommand(redisClient *c) {
    robj *subject, *obj;
    // 编码目标对象 elem
    obj = c->argv[3] = tryObjectEncoding(c->argv[3]);
    long toremove;
    long removed = 0;
    listTypeEntry entry;
    // 取出指定删除模式的 count 参数
    if ((getLongFromObjectOrReply(c, c->argv[2], &toremove, NULL) != REDIS_OK))
        return;
    // 取出列表对象
    subject = lookupKeyWriteOrReply(c,c->argv[1],shared.czero);
    if (subject == NULL || checkType(c,subject,REDIS_LIST)) return;
    /* Make sure obj is raw when we're dealing with a ziplist */
    if (subject->encoding == REDIS_ENCODING_ZIPLIST)
        obj = getDecodedObject(obj);
    listTypeIterator *li;
    // 根据 toremove 参数，决定是从表头还是表尾开始进行删除
    if (toremove < 0) {
        toremove = -toremove;
        li = listTypeInitIterator(subject,-1,REDIS_HEAD);
    } else {
        li = listTypeInitIterator(subject,0,REDIS_TAIL);
    }
    // 查找，比对对象，并进行删除
    while (listTypeNext(li,&entry)) {
        if (listTypeEqual(&entry,obj)) {
            listTypeDelete(&entry);
            server.dirty++;
            removed++;
            // 已经满足删除数量，停止
            if (toremove && removed == toremove) break;
        }
    }
    listTypeReleaseIterator(li);
    /* Clean up raw encoded object */
    if (subject->encoding == REDIS_ENCODING_ZIPLIST)
        decrRefCount(obj);
    // 删除空列表
    if (listTypeLength(subject) == 0) dbDelete(c->db,c->argv[1]);
    addReplyLongLong(c,removed);
    if (removed) signalModifiedKey(c->db,c->argv[1]);
}

rpoplpush——rpoplpushCommand

示例：RPOPLPUSH SOURCE_KEY_NAME DESTINATION_KEY_NAME

  • 被弹出的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void rpoplpushCommand(redisClient *c) {
    robj *sobj, *value;
     
    // 来源列表
    if ((sobj = lookupKeyWriteOrReply(c,c->argv[1],shared.nullbulk)) == NULL ||
        checkType(c,sobj,REDIS_LIST)) return;
    // 空列表，没有元素可 pop ，直接返回
    if (listTypeLength(sobj) == 0) {
        /* This may only happen after loading very old RDB files. Recent
         * versions of Redis delete keys of empty lists. */
        addReply(c,shared.nullbulk);
    // 源列表非空
    } else {
        // 目标对象
        robj *dobj = lookupKeyWrite(c->db,c->argv[2]);
        robj *touchedkey = c->argv[1];
        // 检查目标对象是否列表
        if (dobj && checkType(c,dobj,REDIS_LIST)) return;
        // 从源列表中弹出值
        value = listTypePop(sobj,REDIS_TAIL);
        /* We saved touched key, and protect it, since rpoplpushHandlePush
         * may change the client command argument vector (it does not
         * currently). */
        incrRefCount(touchedkey);
        // 将值推入目标列表中，如果目标列表不存在，那么创建一个新列表
        rpoplpushHandlePush(c,c->argv[2],dobj,value);
        /* listTypePop returns an object with its refcount incremented */
        decrRefCount(value);
        /* Delete the source list when it is empty */
        notifyKeyspaceEvent(REDIS_NOTIFY_LIST,"rpop",touchedkey,c->db->id);
        // 如果源列表已经为空，那么将它删除
        if (listTypeLength(sobj) == 0) {
            dbDelete(c->db,touchedkey);
            notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",
                                touchedkey,c->db->id);
        }
        signalModifiedKey(c->db,touchedkey);
        decrRefCount(touchedkey);
        server.dirty++;
    }
}
命令 作用 ziplist编码时间复杂度 linkedlist编码时间复杂度
LPUSH 将所有指定的值插入到存于 key 的列表的头部 平均O(n), 最坏O(N2) O(1)
RPUSH 将所有指定的值插入到存于 key 的列表的尾部 平均O(n), 最坏O(N2) O(1)
LPOP 移除并返回列表 key 的头元素 平均O(n), 最坏O(N2) O(1)
RPOP 移除并返回列表 key 的尾元素 平均O(n), 最坏O(N2) O(1)
LINDEX 返回列表 key 中，下标为 index 的元素 O(n) O(n)，N为链表长度
LLEN 返回列表 key 的长度 O(1) O(1)
LINSERT 向列表 key 中指定的元素前或者后插入元素 平均O(n), 最坏O(N2) O(n)
LREM 移除列表 key 中\ count\ 个与参数value相等的值 平均O(n), 最坏O(N2) O(n)
LTRIM 保留列表 key 中指定区间的值，其他的全部移除 平均O(n), 最坏O(N2) O(n)
LSET 将列表 key 中指定下标的值设置为value 平均O(n), 最坏O(N2) O(n)