Redis系列（六）：數據結構List雙向鏈表LPUSH、LPOP、RPUSH、RPOP、LLEN命令

2020 年 6 月 27 日
筆記
Redis

1.介紹

redis中的list既實現了棧（先進後出）又實現了隊列（先進先出）

1.示意圖

2.各命令詳解

LPUSH/RPUSH

LPUSH:

從隊列的左邊入隊一個或多個元素

將所有指定的值插入到存於 key 的列表的頭部。如果 key 不存在，那麼在進行 push 操作前會創建一個空列表。如果 key 對應的值不是一個 list 的話，那麼會返回一個錯誤。

可以使用一個命令把多個元素 push 進入列表，只需在命令末尾加上多個指定的參數。元素是從最左端的到最右端的、一個接一個被插入到 list 的頭部。

所以對於這個命令例子 LPUSH mylist a b c，返回的列表是 c 為第一個元素， b 為第二個元素， a 為第三個元素。

RPUSH:

從隊列的右邊入隊一個元素

向存於 key 的列表的尾部插入所有指定的值。如果 key 不存在，那麼會創建一個空的列表然後再進行 push 操作。當 key 保存的不是一個列表，那麼會返回一個錯誤。

可以使用一個命令把多個元素打入隊列，只需要在命令後面指定多個參數。元素是從左到右一個接一個從列表尾部插入。比如命令 RPUSH mylist a b c 會返回一個列表，其第一個元素是 a ，第二個元素是 b ，第三個元素是 c。

兩個命令都返回list的長度

時間複雜度O(1) 相對於i++的操作

127.0.0.1:6379> lpush mylist c b a
(integer) 3
127.0.0.1:6379> rpush mylist d e f
(integer) 6
127.0.0.1:6379> lrange mylist 0 5
1) "a"
2) "b"
3) "c"
4) "d"
5) "e"
6) "f"
127.0.0.1:6379>

源碼解析

    {"rpush",rpushCommand,-3,
     "write use-memory fast @list",
     0,NULL,1,1,1,0,0,0},

    {"lpush",lpushCommand,-3,
     "write use-memory fast @list",
     0,NULL,1,1,1,0,0,0},

LPUSH和RPUSH都是調的同一個函數通過傳入LIST_HEAD和LIST_TAIL來判斷怎麼入隊列

void lpushCommand(client *c) {
    pushGenericCommand(c,LIST_HEAD);
}

void rpushCommand(client *c) {
    pushGenericCommand(c,LIST_TAIL);
}

void pushGenericCommand(client *c, int where) {
    int j, pushed = 0;
    robj *lobj = lookupKeyWrite(c->db,c->argv[1]);

    if (lobj && lobj->type != OBJ_LIST) {
        addReply(c,shared.wrongtypeerr);
        return;
    }

    for (j = 2; j < c->argc; j++) {
        if (!lobj) {
            lobj = createQuicklistObject();
            quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size,
                                server.list_compress_depth);
            dbAdd(c->db,c->argv[1],lobj);
        }
        listTypePush(lobj,c->argv[j],where);
        pushed++;
    }
    addReplyLongLong(c, (lobj ? listTypeLength(lobj) : 0));
    if (pushed) {
        char *event = (where == LIST_HEAD) ? "lpush" : "rpush";

        signalModifiedKey(c,c->db,c->argv[1]);
        notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);
    }
    server.dirty += pushed;
}

LPOP/RPOP

LPOP:

移除並且返回 key 對應的 list 的第一個元素。

RPOP:

移除並返回存於 key 的 list 的最後一個元素。

兩個命令都返回被移除的元素

時間複雜度O(1) 相對於i–的操作

127.0.0.1:6379> lpop mylist
"a"
127.0.0.1:6379> rpop mylist
"f"
127.0.0.1:6379> lrange mylist 0 5
1) "b"
2) "c"
3) "d"
4) "e"
127.0.0.1:6379>

源碼解析

    {"rpop",rpopCommand,2,
     "write fast @list",
     0,NULL,1,1,1,0,0,0},

    {"lpop",lpopCommand,2,
     "write fast @list",
     0,NULL,1,1,1,0,0,0},

void lpopCommand(client *c) {
    popGenericCommand(c,LIST_HEAD);
}

void rpopCommand(client *c) {
    popGenericCommand(c,LIST_TAIL);
}

可見和push一樣通過判斷LIST_HEAD，來確定刪除db中元素

void popGenericCommand(client *c, int where) {
    robj *o = lookupKeyWriteOrReply(c,c->argv[1],shared.null[c->resp]);
    if (o == NULL || checkType(c,o,OBJ_LIST)) return;

    robj *value = listTypePop(o,where);
    if (value == NULL) {
        addReplyNull(c);
    } else {
        char *event = (where == LIST_HEAD) ? "lpop" : "rpop";

        addReplyBulk(c,value);
        decrRefCount(value);
        notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id);
        if (listTypeLength(o) == 0) {
            notifyKeyspaceEvent(NOTIFY_GENERIC,"del",
                                c->argv[1],c->db->id);
            dbDelete(c->db,c->argv[1]);
        }
        signalModifiedKey(c,c->db,c->argv[1]);
        server.dirty++;
    }
}

LLEN

返回存儲在 key 里的list的長度。如果 key 不存在，那麼就被看作是空list，並且返回長度為 0。當存儲在 key 里的值不是一個list的話，會返回error。

時間複雜度：O(1) 相當於常量操作

127.0.0.1:6379> llen mylist
(integer) 4
127.0.0.1:6379>

源碼解析

    {"llen",llenCommand,2,
     "read-only fast @list",
     0,NULL,1,1,1,0,0,0},

void llenCommand(client *c) {
    robj *o = lookupKeyReadOrReply(c,c->argv[1],shared.czero);
    if (o == NULL || checkType(c,o,OBJ_LIST)) return;
    addReplyLongLong(c,listTypeLength(o));
}

unsigned long listTypeLength(const robj *subject) {
    if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
        return quicklistCount(subject->ptr);
    } else {
        serverPanic("Unknown list encoding");
    }
}

unsigned long quicklistCount(const quicklist *ql) { return ql->count; }

Tags: Redis