diff options
Diffstat (limited to 'examples/redis-unstable/src/t_list.c')
| -rw-r--r-- | examples/redis-unstable/src/t_list.c | 1465 |
1 files changed, 0 insertions, 1465 deletions
diff --git a/examples/redis-unstable/src/t_list.c b/examples/redis-unstable/src/t_list.c deleted file mode 100644 index 8e59844..0000000 --- a/examples/redis-unstable/src/t_list.c +++ /dev/null @@ -1,1465 +0,0 @@ -/* - * Copyright (c) 2009-Present, Redis Ltd. - * All rights reserved. - * - * Licensed under your choice of (a) the Redis Source Available License 2.0 - * (RSALv2); or (b) the Server Side Public License v1 (SSPLv1); or (c) the - * GNU Affero General Public License v3 (AGPLv3). - */ - -#include "server.h" -#include "util.h" - -/*----------------------------------------------------------------------------- - * List API - *----------------------------------------------------------------------------*/ - -/* Check the length and size of a number of objects that will be added to list to see - * if we need to convert a listpack to a quicklist. Note that we only check string - * encoded objects as their string length can be queried in constant time. - * - * If callback is given the function is called in order for caller to do some work - * before the list conversion. */ -static void listTypeTryConvertListpack(robj *o, robj **argv, int start, int end, - beforeConvertCB fn, void *data) -{ - serverAssert(o->encoding == OBJ_ENCODING_LISTPACK); - - size_t add_bytes = 0; - size_t add_length = 0; - - if (argv) { - for (int i = start; i <= end; i++) { - if (!sdsEncodedObject(argv[i])) - continue; - add_bytes += sdslen(argv[i]->ptr); - } - add_length = end - start + 1; - } - - if (quicklistNodeExceedsLimit(server.list_max_listpack_size, - lpBytes(o->ptr) + add_bytes, lpLength(o->ptr) + add_length)) - { - /* Invoke callback before conversion. */ - if (fn) fn(data); - - quicklist *ql = quicklistNew(server.list_max_listpack_size, server.list_compress_depth); - - /* Append listpack to quicklist if it's not empty, otherwise release it. */ - if (lpLength(o->ptr)) - quicklistAppendListpack(ql, o->ptr); - else - lpFree(o->ptr); - o->ptr = ql; - o->encoding = OBJ_ENCODING_QUICKLIST; - } -} - -/* Check the length and size of a quicklist to see if we need to convert it to listpack. - * - * 'shrinking' is 1 means that the conversion is due to a list shrinking, to avoid - * frequent conversions of quicklist and listpack due to frequent insertion and - * deletion, we don't convert quicklist to listpack until its length or size is - * below half of the limit. - * - * If callback is given the function is called in order for caller to do some work - * before the list conversion. */ -static void listTypeTryConvertQuicklist(robj *o, int shrinking, beforeConvertCB fn, void *data) { - serverAssert(o->encoding == OBJ_ENCODING_QUICKLIST); - - size_t sz_limit; - unsigned int count_limit; - quicklist *ql = o->ptr; - - /* A quicklist can be converted to listpack only if it has only one packed node. */ - if (ql->len != 1 || ql->head->container != QUICKLIST_NODE_CONTAINER_PACKED) - return; - - /* Check the length or size of the quicklist is below the limit. */ - quicklistNodeLimit(server.list_max_listpack_size, &sz_limit, &count_limit); - if (shrinking) { - sz_limit /= 2; - count_limit /= 2; - } - if (ql->head->sz > sz_limit || ql->count > count_limit) return; - - /* Invoke callback before conversion. */ - if (fn) fn(data); - - /* Extract the listpack from the unique quicklist node, - * then reset it and release the quicklist. */ - o->ptr = ql->head->entry; - ql->head->entry = NULL; - ql->alloc_size -= ql->head->sz; - quicklistRelease(ql); - o->encoding = OBJ_ENCODING_LISTPACK; -} - -/* Check if the list needs to be converted to appropriate encoding due to - * growing, shrinking or other cases. - * - * 'lct' can be one of the following values: - * LIST_CONV_AUTO - Used after we built a new list, and we want to let the - * function decide on the best encoding for that list. - * LIST_CONV_GROWING - Used before or right after adding elements to the list, - * in which case we are likely to only consider converting - * from listpack to quicklist. - * 'argv' is only used in this case to calculate the size - * of a number of objects that will be added to list. - * LIST_CONV_SHRINKING - Used after removing an element from the list, in which case we - * wanna consider converting from quicklist to listpack. When we - * know we're shrinking, we use a lower (more strict) threshold in - * order to avoid repeated conversions on every list change. */ -static void listTypeTryConversionRaw(robj *o, list_conv_type lct, - robj **argv, int start, int end, - beforeConvertCB fn, void *data) -{ - if (o->encoding == OBJ_ENCODING_QUICKLIST) { - if (lct == LIST_CONV_GROWING) return; /* Growing has nothing to do with quicklist */ - listTypeTryConvertQuicklist(o, lct == LIST_CONV_SHRINKING, fn, data); - } else if (o->encoding == OBJ_ENCODING_LISTPACK) { - if (lct == LIST_CONV_SHRINKING) return; /* Shrinking has nothing to do with listpack */ - listTypeTryConvertListpack(o, argv, start, end, fn, data); - } else { - serverPanic("Unknown list encoding"); - } -} - -/* This is just a wrapper for listTypeTryConversionRaw() that is - * able to try conversion without passing 'argv'. */ -void listTypeTryConversion(robj *o, list_conv_type lct, beforeConvertCB fn, void *data) { - listTypeTryConversionRaw(o, lct, NULL, 0, 0, fn, data); -} - -/* This is just a wrapper for listTypeTryConversionRaw() that is - * able to try conversion before adding elements to the list. */ -void listTypeTryConversionAppend(robj *o, robj **argv, int start, int end, - beforeConvertCB fn, void *data) -{ - listTypeTryConversionRaw(o, LIST_CONV_GROWING, argv, start, end, fn, data); -} - -/* The function pushes an element to the specified list object 'subject', - * at head or tail position as specified by 'where'. - * - * There is no need for the caller to increment the refcount of 'value' as - * the function takes care of it if needed. */ -void listTypePush(robj *subject, robj *value, int where) { - if (subject->encoding == OBJ_ENCODING_QUICKLIST) { - int pos = (where == LIST_HEAD) ? QUICKLIST_HEAD : QUICKLIST_TAIL; - if (value->encoding == OBJ_ENCODING_INT) { - char buf[32]; - ll2string(buf, 32, (long)value->ptr); - quicklistPush(subject->ptr, buf, strlen(buf), pos); - } else { - quicklistPush(subject->ptr, value->ptr, sdslen(value->ptr), pos); - } - } else if (subject->encoding == OBJ_ENCODING_LISTPACK) { - if (value->encoding == OBJ_ENCODING_INT) { - subject->ptr = (where == LIST_HEAD) ? - lpPrependInteger(subject->ptr, (long)value->ptr) : - lpAppendInteger(subject->ptr, (long)value->ptr); - } else { - subject->ptr = (where == LIST_HEAD) ? - lpPrepend(subject->ptr, value->ptr, sdslen(value->ptr)) : - lpAppend(subject->ptr, value->ptr, sdslen(value->ptr)); - } - } else { - serverPanic("Unknown list encoding"); - } -} - -void *listPopSaver(unsigned char *data, size_t sz) { - return createStringObject((char*)data,sz); -} - -robj *listTypePop(robj *subject, int where) { - robj *value = NULL; - - if (subject->encoding == OBJ_ENCODING_QUICKLIST) { - long long vlong; - int ql_where = where == LIST_HEAD ? QUICKLIST_HEAD : QUICKLIST_TAIL; - if (quicklistPopCustom(subject->ptr, ql_where, (unsigned char **)&value, - NULL, &vlong, listPopSaver)) { - if (!value) - value = createStringObjectFromLongLong(vlong); - } - } else if (subject->encoding == OBJ_ENCODING_LISTPACK) { - unsigned char *p; - unsigned char *vstr; - int64_t vlen; - unsigned char intbuf[LP_INTBUF_SIZE]; - - p = (where == LIST_HEAD) ? lpFirst(subject->ptr) : lpLast(subject->ptr); - if (p) { - vstr = lpGet(p, &vlen, intbuf); - value = createStringObject((char*)vstr, vlen); - subject->ptr = lpDelete(subject->ptr, p, NULL); - } - } else { - serverPanic("Unknown list encoding"); - } - return value; -} - -unsigned long listTypeLength(const robj *subject) { - if (subject->encoding == OBJ_ENCODING_QUICKLIST) { - return quicklistCount(subject->ptr); - } else if (subject->encoding == OBJ_ENCODING_LISTPACK) { - return lpLength(subject->ptr); - } else { - serverPanic("Unknown list encoding"); - } -} - -size_t listTypeAllocSize(const robj *o) { - serverAssertWithInfo(NULL,o,o->type == OBJ_LIST); - size_t size = 0; - if (o->encoding == OBJ_ENCODING_QUICKLIST) { - size = quicklistAllocSize(o->ptr); - } else if (o->encoding == OBJ_ENCODING_LISTPACK) { - size = lpBytes(o->ptr); - } else { - serverPanic("Unknown list encoding"); - } - return size; -} - -/* Initialize an iterator at the specified index. */ -void listTypeInitIterator(listTypeIterator *li, robj *subject, - long index, unsigned char direction) { - li->subject = subject; - li->encoding = subject->encoding; - li->direction = direction; - /* LIST_HEAD means start at TAIL and move *towards* head. - * LIST_TAIL means start at HEAD and move *towards* tail. */ - if (li->encoding == OBJ_ENCODING_QUICKLIST) { - int iter_direction = direction == LIST_HEAD ? AL_START_TAIL : AL_START_HEAD; - quicklistInitIteratorAtIdx(&li->iter, li->subject->ptr, iter_direction, index); - } else if (li->encoding == OBJ_ENCODING_LISTPACK) { - li->lpi = lpSeek(subject->ptr, index); - } else { - serverPanic("Unknown list encoding"); - } -} - -/* Sets the direction of an iterator. */ -void listTypeSetIteratorDirection(listTypeIterator *li, listTypeEntry *entry, unsigned char direction) { - if (li->direction == direction) return; - - li->direction = direction; - if (li->encoding == OBJ_ENCODING_QUICKLIST) { - int dir = direction == LIST_HEAD ? AL_START_TAIL : AL_START_HEAD; - quicklistSetDirection(&li->iter, dir); - } else if (li->encoding == OBJ_ENCODING_LISTPACK) { - unsigned char *lp = li->subject->ptr; - /* Note that the iterator for listpack always points to the next of the current entry, - * so we need to update position of the iterator depending on the direction. */ - li->lpi = (direction == LIST_TAIL) ? lpNext(lp, entry->lpe) : lpPrev(lp, entry->lpe); - } else { - serverPanic("Unknown list encoding"); - } -} - -/* Clean up the iterator. */ -void listTypeResetIterator(listTypeIterator *li) { - if (li->encoding == OBJ_ENCODING_QUICKLIST) - quicklistResetIterator(&li->iter); -} - -/* Stores pointer to current the entry in the provided entry structure - * and advances the position of the iterator. Returns 1 when the current - * entry is in fact an entry, 0 otherwise. */ -int listTypeNext(listTypeIterator *li, listTypeEntry *entry) { - /* Protect from converting when iterating */ - serverAssert(li->subject->encoding == li->encoding); - - entry->li = li; - if (li->encoding == OBJ_ENCODING_QUICKLIST) { - return quicklistNext(&li->iter, &entry->entry); - } else if (li->encoding == OBJ_ENCODING_LISTPACK) { - entry->lpe = li->lpi; - if (entry->lpe != NULL) { - li->lpi = (li->direction == LIST_TAIL) ? - lpNext(li->subject->ptr,li->lpi) : lpPrev(li->subject->ptr,li->lpi); - return 1; - } - } else { - serverPanic("Unknown list encoding"); - } - return 0; -} - -/* Get entry value at the current position of the iterator. - * When the function returns NULL, it populates the integer value by - * reference in 'lval'. Otherwise a pointer to the string is returned, - * and 'vlen' is set to the length of the string. */ -unsigned char *listTypeGetValue(listTypeEntry *entry, size_t *vlen, long long *lval) { - unsigned char *vstr = NULL; - if (entry->li->encoding == OBJ_ENCODING_QUICKLIST) { - if (entry->entry.value) { - vstr = entry->entry.value; - *vlen = entry->entry.sz; - } else { - *lval = entry->entry.longval; - } - } else if (entry->li->encoding == OBJ_ENCODING_LISTPACK) { - unsigned int slen; - vstr = lpGetValue(entry->lpe, &slen, lval); - *vlen = slen; - } else { - serverPanic("Unknown list encoding"); - } - return vstr; -} - -/* Return entry or NULL at the current position of the iterator. */ -robj *listTypeGet(listTypeEntry *entry) { - unsigned char *vstr; - size_t vlen; - long long lval; - - vstr = listTypeGetValue(entry, &vlen, &lval); - if (vstr) - return createStringObject((char *)vstr, vlen); - else - return createStringObjectFromLongLong(lval); -} - -void listTypeInsert(listTypeEntry *entry, robj *value, int where) { - robj *subject = entry->li->subject; - value = getDecodedObject(value); - sds str = value->ptr; - size_t len = sdslen(str); - - if (entry->li->encoding == OBJ_ENCODING_QUICKLIST) { - if (where == LIST_TAIL) { - quicklistInsertAfter(&entry->li->iter, &entry->entry, str, len); - } else if (where == LIST_HEAD) { - quicklistInsertBefore(&entry->li->iter, &entry->entry, str, len); - } - } else if (entry->li->encoding == OBJ_ENCODING_LISTPACK) { - int lpw = (where == LIST_TAIL) ? LP_AFTER : LP_BEFORE; - subject->ptr = lpInsertString(subject->ptr, (unsigned char *)str, - len, entry->lpe, lpw, &entry->lpe); - } else { - serverPanic("Unknown list encoding"); - } - decrRefCount(value); -} - -/* Replaces entry at the current position of the iterator. */ -void listTypeReplace(listTypeEntry *entry, robj *value) { - robj *subject = entry->li->subject; - value = getDecodedObject(value); - sds str = value->ptr; - size_t len = sdslen(str); - - if (entry->li->encoding == OBJ_ENCODING_QUICKLIST) { - quicklistReplaceEntry(&entry->li->iter, &entry->entry, str, len); - } else if (entry->li->encoding == OBJ_ENCODING_LISTPACK) { - subject->ptr = lpReplace(subject->ptr, &entry->lpe, (unsigned char *)str, len); - } else { - serverPanic("Unknown list encoding"); - } - - decrRefCount(value); -} - -/* Replace entry at offset 'index' by 'value'. - * - * Returns 1 if replace happened. - * Returns 0 if replace failed and no changes happened. */ -int listTypeReplaceAtIndex(robj *o, int index, robj *value) { - value = getDecodedObject(value); - sds vstr = value->ptr; - size_t vlen = sdslen(vstr); - int replaced = 0; - - if (o->encoding == OBJ_ENCODING_QUICKLIST) { - quicklist *ql = o->ptr; - replaced = quicklistReplaceAtIndex(ql, index, vstr, vlen); - } else if (o->encoding == OBJ_ENCODING_LISTPACK) { - unsigned char *p = lpSeek(o->ptr,index); - if (p) { - o->ptr = lpReplace(o->ptr, &p, (unsigned char *)vstr, vlen); - replaced = 1; - } - } else { - serverPanic("Unknown list encoding"); - } - - decrRefCount(value); - return replaced; -} - -/* Compare the given object with the entry at the current position. - * - * If the list encoding is quicklist, delegates to quicklistCompare(), - * passing along the cached integer conversion state. - * - * If the list encoding is listpack, uses lpCompare(). - * - * Returns 1 if equal, 0 otherwise. - */ -int listTypeEqual(listTypeEntry *entry, robj *o, size_t object_len, - long long *cached_longval, int *cached_valid) { - serverAssertWithInfo(NULL,o,sdsEncodedObject(o)); - if (entry->li->encoding == OBJ_ENCODING_QUICKLIST) { - return quicklistCompare(&entry->entry,o->ptr,object_len,cached_longval,cached_valid); - } else if (entry->li->encoding == OBJ_ENCODING_LISTPACK) { - return lpCompare(entry->lpe,o->ptr,object_len,cached_longval,cached_valid); - } else { - serverPanic("Unknown list encoding"); - } -} - -/* Delete the element pointed to. */ -void listTypeDelete(listTypeIterator *iter, listTypeEntry *entry) { - if (entry->li->encoding == OBJ_ENCODING_QUICKLIST) { - quicklistDelEntry(&iter->iter, &entry->entry); - } else if (entry->li->encoding == OBJ_ENCODING_LISTPACK) { - unsigned char *p = entry->lpe; - iter->subject->ptr = lpDelete(iter->subject->ptr,p,&p); - - /* Update position of the iterator depending on the direction */ - if (iter->direction == LIST_TAIL) - iter->lpi = p; - else { - if (p) { - iter->lpi = lpPrev(iter->subject->ptr,p); - } else { - /* We deleted the last element, so we need to set the - * iterator to the last element. */ - iter->lpi = lpLast(iter->subject->ptr); - } - } - } else { - serverPanic("Unknown list encoding"); - } -} - -/* This is a helper function for the COPY command. - * Duplicate a list object, with the guarantee that the returned object - * has the same encoding as the original one. - * - * The resulting object always has refcount set to 1 */ -robj *listTypeDup(robj *o) { - robj *lobj; - - serverAssert(o->type == OBJ_LIST); - - switch (o->encoding) { - case OBJ_ENCODING_LISTPACK: - lobj = createObject(OBJ_LIST, lpDup(o->ptr)); - break; - case OBJ_ENCODING_QUICKLIST: - lobj = createObject(OBJ_LIST, quicklistDup(o->ptr)); - break; - default: - serverPanic("Unknown list encoding"); - break; - } - lobj->encoding = o->encoding; - return lobj; -} - -/* Delete a range of elements from the list. */ -void listTypeDelRange(robj *subject, long start, long count) { - if (subject->encoding == OBJ_ENCODING_QUICKLIST) { - quicklistDelRange(subject->ptr, start, count); - } else if (subject->encoding == OBJ_ENCODING_LISTPACK) { - subject->ptr = lpDeleteRange(subject->ptr, start, count); - } else { - serverPanic("Unknown list encoding"); - } -} - -/*----------------------------------------------------------------------------- - * List Commands - *----------------------------------------------------------------------------*/ - -/* Implements LPUSH/RPUSH/LPUSHX/RPUSHX. - * 'xx': push if key exists. */ -void pushGenericCommand(client *c, int where, int xx) { - unsigned long llen; - dictEntryLink link; - int j; - size_t oldsize = 0; - - kvobj *lobj = lookupKeyWriteWithLink(c->db, c->argv[1], &link); - if (checkType(c,lobj,OBJ_LIST)) return; - if (!lobj) { - if (xx) { - addReply(c, shared.czero); - return; - } - - lobj = createListListpackObject(); - dbAddByLink(c->db, c->argv[1], &lobj, &link); - } - - if (server.memory_tracking_per_slot) - oldsize = listTypeAllocSize(lobj); - listTypeTryConversionAppend(lobj,c->argv,2,c->argc-1,NULL,NULL); - for (j = 2; j < c->argc; j++) { - listTypePush(lobj,c->argv[j],where); - server.dirty++; - } - - llen = listTypeLength(lobj); - addReplyLongLong(c, llen); - - char *event = (where == LIST_HEAD) ? "lpush" : "rpush"; - keyModified(c,c->db,c->argv[1],lobj,1); - notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id); - updateKeysizesHist(c->db, getKeySlot(c->argv[1]->ptr), OBJ_LIST, llen - (c->argc - 2), llen); - if (server.memory_tracking_per_slot) - updateSlotAllocSize(c->db, getKeySlot(c->argv[1]->ptr), oldsize, listTypeAllocSize(lobj)); -} - -/* LPUSH <key> <element> [<element> ...] */ -void lpushCommand(client *c) { - pushGenericCommand(c,LIST_HEAD,0); -} - -/* RPUSH <key> <element> [<element> ...] */ -void rpushCommand(client *c) { - pushGenericCommand(c,LIST_TAIL,0); -} - -/* LPUSHX <key> <element> [<element> ...] */ -void lpushxCommand(client *c) { - pushGenericCommand(c,LIST_HEAD,1); -} - -/* RPUSHX <key> <element> [<element> ...] */ -void rpushxCommand(client *c) { - pushGenericCommand(c,LIST_TAIL,1); -} - -/* LINSERT <key> (BEFORE|AFTER) <pivot> <element> */ -void linsertCommand(client *c) { - int where; - kvobj *subject; - listTypeIterator iter; - listTypeEntry entry; - int inserted = 0; - size_t oldsize = 0; - - if (strcasecmp(c->argv[2]->ptr,"after") == 0) { - where = LIST_TAIL; - } else if (strcasecmp(c->argv[2]->ptr,"before") == 0) { - where = LIST_HEAD; - } else { - addReplyErrorObject(c,shared.syntaxerr); - return; - } - - if ((subject = lookupKeyWriteOrReply(c,c->argv[1],shared.czero)) == NULL || - checkType(c,subject,OBJ_LIST)) return; - - /* 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 listpack to a regular list if necessary. */ - if (server.memory_tracking_per_slot) - oldsize = listTypeAllocSize(subject); - listTypeTryConversionAppend(subject,c->argv,4,4,NULL,NULL); - - /* Seek pivot from head to tail */ - listTypeInitIterator(&iter, subject, 0, LIST_TAIL); - const size_t object_len = sdslen(c->argv[3]->ptr); - long long cached_longval = 0; - int cached_valid = 0; - while (listTypeNext(&iter, &entry)) { - if (listTypeEqual(&entry,c->argv[3],object_len,&cached_longval,&cached_valid)) { - listTypeInsert(&entry,c->argv[4],where); - inserted = 1; - break; - } - } - listTypeResetIterator(&iter); - if (server.memory_tracking_per_slot) - updateSlotAllocSize(c->db, getKeySlot(c->argv[1]->ptr), oldsize, listTypeAllocSize(subject)); - - if (inserted) { - keyModified(c,c->db,c->argv[1],subject,1); - notifyKeyspaceEvent(NOTIFY_LIST,"linsert", - c->argv[1],c->db->id); - server.dirty++; - unsigned long ll = listTypeLength(subject); - updateKeysizesHist(c->db, getKeySlot(c->argv[1]->ptr), OBJ_LIST, ll-1, ll); - } else { - /* Notify client of a failed insert */ - addReplyLongLong(c,-1); - return; - } - - addReplyLongLong(c,listTypeLength(subject)); -} - -/* LLEN <key> */ -void llenCommand(client *c) { - kvobj *kv = lookupKeyReadOrReply(c,c->argv[1],shared.czero); - if (kv == NULL || checkType(c,kv,OBJ_LIST)) return; - addReplyLongLong(c,listTypeLength(kv)); -} - -/* LINDEX <key> <index> */ -void lindexCommand(client *c) { - kvobj *o = lookupKeyReadOrReply(c,c->argv[1],shared.null[c->resp]); - if (o == NULL || checkType(c,o,OBJ_LIST)) return; - long index; - - if ((getLongFromObjectOrReply(c, c->argv[2], &index, NULL) != C_OK)) - return; - - listTypeIterator iter; - listTypeEntry entry; - unsigned char *vstr; - size_t vlen; - long long lval; - - listTypeInitIterator(&iter, o, index, LIST_TAIL); - if (listTypeNext(&iter, &entry)) { - vstr = listTypeGetValue(&entry,&vlen,&lval); - if (vstr) { - addReplyBulkCBuffer(c, vstr, vlen); - } else { - addReplyBulkLongLong(c, lval); - } - } else { - addReplyNull(c); - } - - listTypeResetIterator(&iter); -} - -/* LSET <key> <index> <element> */ -void lsetCommand(client *c) { - kvobj *o = lookupKeyWriteOrReply(c, c->argv[1], shared.nokeyerr); - if (o == NULL || checkType(c,o,OBJ_LIST)) return; - long index; - robj *value = c->argv[3]; - size_t oldsize = 0; - - if ((getLongFromObjectOrReply(c, c->argv[2], &index, NULL) != C_OK)) - return; - - if (server.memory_tracking_per_slot) - oldsize = listTypeAllocSize(o); - listTypeTryConversionAppend(o,c->argv,3,3,NULL,NULL); - if (listTypeReplaceAtIndex(o,index,value)) { - /* We might replace a big item with a small one or vice versa, but we've - * already handled the growing case in listTypeTryConversionAppend() - * above, so here we just need to try the conversion for shrinking. */ - listTypeTryConversion(o,LIST_CONV_SHRINKING,NULL,NULL); - addReply(c,shared.ok); - keyModified(c,c->db,c->argv[1],o,1); - notifyKeyspaceEvent(NOTIFY_LIST,"lset",c->argv[1],c->db->id); - server.dirty++; - } else { - addReplyErrorObject(c,shared.outofrangeerr); - } - /* Always update db allocation sizes since listTypeTryConversionAppend() - * might have changed object encoding. */ - if (server.memory_tracking_per_slot) - updateSlotAllocSize(c->db, getKeySlot(c->argv[1]->ptr), oldsize, listTypeAllocSize(o)); -} - -/* A helper function like addListRangeReply, more details see below. - * The difference is that here we are returning nested arrays, like: - * 1) keyname - * 2) 1) element1 - * 2) element2 - * - * And also actually pop out from the list by calling listElementsRemoved. - * We maintain the server.dirty and notifications there. - * - * 'deleted' is an optional output argument to get an indication - * if the key got deleted by this function. */ -void listPopRangeAndReplyWithKey(client *c, robj *o, robj *key, int where, long count, int signal, int *deleted) { - long llen = listTypeLength(o); - long rangelen = (count > llen) ? llen : count; - long rangestart = (where == LIST_HEAD) ? 0 : -rangelen; - long rangeend = (where == LIST_HEAD) ? rangelen - 1 : -1; - int reverse = (where == LIST_HEAD) ? 0 : 1; - - /* We return key-name just once, and an array of elements */ - addReplyArrayLen(c, 2); - addReplyBulk(c, key); - addListRangeReply(c, o, rangestart, rangeend, reverse); - - /* Pop these elements. */ - size_t oldsize = 0; - if (server.memory_tracking_per_slot) - oldsize = listTypeAllocSize(o); - listTypeDelRange(o, rangestart, rangelen); - /* Maintain the notifications and dirty. */ - listElementsRemoved(c, key, where, o, rangelen, oldsize, signal, deleted); -} - -/* Extracted from `addListRangeReply()` to reply with a quicklist list. - * Note that the purpose is to make the methods small so that the - * code in the loop can be inlined better to improve performance. */ -void addListQuicklistRangeReply(client *c, robj *o, int from, int rangelen, int reverse) { - /* Return the result in form of a multi-bulk reply */ - addReplyArrayLen(c,rangelen); - - int direction = reverse ? AL_START_TAIL : AL_START_HEAD; - quicklistIter iter; - quicklistInitIteratorAtIdx(&iter, o->ptr, direction, from); - while(rangelen--) { - quicklistEntry qe; - serverAssert(quicklistNext(&iter, &qe)); /* fail on corrupt data */ - if (qe.value) { - addReplyBulkCBuffer(c,qe.value,qe.sz); - } else { - addReplyBulkLongLong(c,qe.longval); - } - } - quicklistResetIterator(&iter); -} - -/* Extracted from `addListRangeReply()` to reply with a listpack list. - * Note that the purpose is to make the methods small so that the - * code in the loop can be inlined better to improve performance. */ -void addListListpackRangeReply(client *c, robj *o, int from, int rangelen, int reverse) { - unsigned char *lp = o->ptr; - unsigned char *p = lpSeek(lp, from); - const size_t lpbytes = lpBytes(lp); - int64_t vlen; - - /* Return the result in form of a multi-bulk reply */ - addReplyArrayLen(c,rangelen); - - while(rangelen--) { - serverAssert(p); /* fail on corrupt data */ - unsigned char buf[LP_INTBUF_SIZE]; - unsigned char *vstr = lpGet(p,&vlen,buf); - addReplyBulkCBuffer(c,vstr,vlen); - p = reverse ? lpPrev(lp,p) : lpNextWithBytes(lp,p,lpbytes); - } -} - -/* A helper for replying with a list's range between the inclusive start and end - * indexes as multi-bulk, with support for negative indexes. Note that start - * must be less than end or an empty array is returned. When the reverse - * argument is set to a non-zero value, the reply is reversed so that elements - * are returned from end to start. */ -void addListRangeReply(client *c, robj *o, long start, long end, int reverse) { - long rangelen, 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.emptyarray); - return; - } - if (end >= llen) end = llen-1; - rangelen = (end-start)+1; - - int from = reverse ? end : start; - if (o->encoding == OBJ_ENCODING_QUICKLIST) - addListQuicklistRangeReply(c, o, from, rangelen, reverse); - else if (o->encoding == OBJ_ENCODING_LISTPACK) - addListListpackRangeReply(c, o, from, rangelen, reverse); - else - serverPanic("Unknown list encoding"); -} - -/* A housekeeping helper for list elements popping tasks. - * - * If 'signal' is 0, skip calling keyModified(). - * - * 'deleted' is an optional output argument to get an indication - * if the key got deleted by this function. */ -void listElementsRemoved(client *c, robj *key, int where, robj *o, long count, size_t oldsize, int signal, int *deleted) { - char *event = (where == LIST_HEAD) ? "lpop" : "rpop"; - unsigned long llen = listTypeLength(o); - - notifyKeyspaceEvent(NOTIFY_LIST, event, key, c->db->id); - updateKeysizesHist(c->db, getKeySlot(key->ptr), OBJ_LIST, llen + count, llen); - if (llen == 0) { - if (deleted) *deleted = 1; - - if (server.memory_tracking_per_slot) - updateSlotAllocSize(c->db, getKeySlot(key->ptr), oldsize, listTypeAllocSize(o)); - dbDelete(c->db, key); - notifyKeyspaceEvent(NOTIFY_GENERIC, "del", key, c->db->id); - } else { - listTypeTryConversion(o, LIST_CONV_SHRINKING, NULL, NULL); - if (server.memory_tracking_per_slot) - updateSlotAllocSize(c->db, getKeySlot(key->ptr), oldsize, listTypeAllocSize(o)); - if (deleted) *deleted = 0; - } - if (signal) - keyModified(c, c->db, key, llen ? o : NULL, 1); - server.dirty += count; -} - -/* Implements the generic list pop operation for LPOP/RPOP. - * The where argument specifies which end of the list is operated on. An - * optional count may be provided as the third argument of the client's - * command. */ -void popGenericCommand(client *c, int where) { - int hascount = (c->argc == 3); - long count = 0; - robj *value; - - if (c->argc > 3) { - addReplyErrorArity(c); - return; - } else if (hascount) { - /* Parse the optional count argument. */ - if (getPositiveLongFromObjectOrReply(c,c->argv[2],&count,NULL) != C_OK) - return; - } - - kvobj *o = lookupKeyWriteOrReply(c, c->argv[1], hascount ? shared.nullarray[c->resp] : shared.null[c->resp]); - if (o == NULL || checkType(c, o, OBJ_LIST)) - return; - - if (hascount && !count) { - /* Fast exit path. */ - addReply(c,shared.emptyarray); - return; - } - - size_t oldsize = 0; - if (server.memory_tracking_per_slot) - oldsize = listTypeAllocSize(o); - if (!count) { - /* Pop a single element. This is POP's original behavior that replies - * with a bulk string. */ - value = listTypePop(o,where); - serverAssert(value != NULL); - addReplyBulk(c,value); - decrRefCount(value); - listElementsRemoved(c,c->argv[1],where,o,1,oldsize,1,NULL); - } else { - /* Pop a range of elements. An addition to the original POP command, - * which replies with a multi-bulk. */ - long llen = listTypeLength(o); - long rangelen = (count > llen) ? llen : count; - long rangestart = (where == LIST_HEAD) ? 0 : -rangelen; - long rangeend = (where == LIST_HEAD) ? rangelen - 1 : -1; - int reverse = (where == LIST_HEAD) ? 0 : 1; - - addListRangeReply(c,o,rangestart,rangeend,reverse); - listTypeDelRange(o,rangestart,rangelen); - listElementsRemoved(c,c->argv[1],where,o,rangelen,oldsize,1,NULL); - } -} - -/* Like popGenericCommand but work with multiple keys. - * Take multiple keys and return multiple elements from just one key. - * - * 'numkeys' the number of keys. - * 'count' is the number of elements requested to pop. - * - * Always reply with array. */ -void mpopGenericCommand(client *c, robj **keys, int numkeys, int where, long count) { - int j; - robj *o; - robj *key; - - for (j = 0; j < numkeys; j++) { - key = keys[j]; - o = lookupKeyWrite(c->db, key); - - /* Non-existing key, move to next key. */ - if (o == NULL) continue; - - if (checkType(c, o, OBJ_LIST)) return; - - long llen = listTypeLength(o); - /* Empty list, move to next key. */ - if (llen == 0) continue; - - /* Pop a range of elements in a nested arrays way. */ - listPopRangeAndReplyWithKey(c, o, key, where, count, 1, NULL); - - /* Replicate it as [LR]POP COUNT. */ - robj *count_obj = createStringObjectFromLongLong((count > llen) ? llen : count); - rewriteClientCommandVector(c, 3, - (where == LIST_HEAD) ? shared.lpop : shared.rpop, - key, count_obj); - decrRefCount(count_obj); - return; - } - - /* Look like we are not able to pop up any elements. */ - addReplyNullArray(c); -} - -/* LPOP <key> [count] */ -void lpopCommand(client *c) { - popGenericCommand(c,LIST_HEAD); -} - -/* RPOP <key> [count] */ -void rpopCommand(client *c) { - popGenericCommand(c,LIST_TAIL); -} - -/* LRANGE <key> <start> <stop> */ -void lrangeCommand(client *c) { - kvobj *o; - long start, end; - - if ((getLongFromObjectOrReply(c, c->argv[2], &start, NULL) != C_OK) || - (getLongFromObjectOrReply(c, c->argv[3], &end, NULL) != C_OK)) return; - - if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptyarray)) == NULL - || checkType(c,o,OBJ_LIST)) return; - - addListRangeReply(c,o,start,end,0); -} - -/* LTRIM <key> <start> <stop> */ -void ltrimCommand(client *c) { - kvobj *o; - long start, end, llen, ltrim, rtrim, llenNew; - size_t oldsize = 0; - - if ((getLongFromObjectOrReply(c, c->argv[2], &start, NULL) != C_OK) || - (getLongFromObjectOrReply(c, c->argv[3], &end, NULL) != C_OK)) return; - - if ((o = lookupKeyWriteOrReply(c,c->argv[1],shared.ok)) == NULL || - checkType(c,o,OBJ_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 (server.memory_tracking_per_slot) - oldsize = listTypeAllocSize(o); - if (o->encoding == OBJ_ENCODING_QUICKLIST) { - quicklistDelRange(o->ptr,0,ltrim); - quicklistDelRange(o->ptr,-rtrim,rtrim); - } else if (o->encoding == OBJ_ENCODING_LISTPACK) { - o->ptr = lpDeleteRange(o->ptr,0,ltrim); - o->ptr = lpDeleteRange(o->ptr,-rtrim,rtrim); - } else { - serverPanic("Unknown list encoding"); - } - - if (server.memory_tracking_per_slot) - updateSlotAllocSize(c->db, getKeySlot(c->argv[1]->ptr), oldsize, listTypeAllocSize(o)); - notifyKeyspaceEvent(NOTIFY_LIST,"ltrim",c->argv[1],c->db->id); - if ((llenNew = listTypeLength(o)) == 0) { - dbDeleteSkipKeysizesUpdate(c->db,c->argv[1]); - notifyKeyspaceEvent(NOTIFY_GENERIC,"del",c->argv[1],c->db->id); - llenNew = -1; /* Indicate key deleted to updateKeysizesHist() */ - } else { - listTypeTryConversion(o,LIST_CONV_SHRINKING,NULL,NULL); - } - updateKeysizesHist(c->db, getKeySlot(c->argv[1]->ptr), OBJ_LIST, llen, llenNew); - keyModified(c, c->db, c->argv[1], (llenNew > 0) ? o : NULL, 1); - server.dirty += (ltrim + rtrim); - addReply(c,shared.ok); -} - -/* LPOS key element [RANK rank] [COUNT num-matches] [MAXLEN len] - * - * The "rank" is the position of the match, so if it is 1, the first match - * is returned, if it is 2 the second match is returned and so forth. - * It is 1 by default. If negative has the same meaning but the search is - * performed starting from the end of the list. - * - * If COUNT is given, instead of returning the single element, a list of - * all the matching elements up to "num-matches" are returned. COUNT can - * be combined with RANK in order to returning only the element starting - * from the Nth. If COUNT is zero, all the matching elements are returned. - * - * MAXLEN tells the command to scan a max of len elements. If zero (the - * default), all the elements in the list are scanned if needed. - * - * The returned elements indexes are always referring to what LINDEX - * would return. So first element from head is 0, and so forth. */ -void lposCommand(client *c) { - robj *ele; - ele = c->argv[2]; - int direction = LIST_TAIL; - long rank = 1, count = -1, maxlen = 0; /* Count -1: option not given. */ - - /* Parse the optional arguments. */ - for (int j = 3; j < c->argc; j++) { - char *opt = c->argv[j]->ptr; - int moreargs = (c->argc-1)-j; - - if (!strcasecmp(opt,"RANK") && moreargs) { - j++; - if (getRangeLongFromObjectOrReply(c, c->argv[j], -LONG_MAX, LONG_MAX, &rank, NULL) != C_OK) - return; - if (rank == 0) { - addReplyError(c,"RANK can't be zero: use 1 to start from " - "the first match, 2 from the second ... " - "or use negative to start from the end of the list"); - return; - } - } else if (!strcasecmp(opt,"COUNT") && moreargs) { - j++; - if (getPositiveLongFromObjectOrReply(c, c->argv[j], &count, - "COUNT can't be negative") != C_OK) - return; - } else if (!strcasecmp(opt,"MAXLEN") && moreargs) { - j++; - if (getPositiveLongFromObjectOrReply(c, c->argv[j], &maxlen, - "MAXLEN can't be negative") != C_OK) - return; - } else { - addReplyErrorObject(c,shared.syntaxerr); - return; - } - } - - /* A negative rank means start from the tail. */ - if (rank < 0) { - rank = -rank; - direction = LIST_HEAD; - } - - /* We return NULL or an empty array if there is no such key (or - * if we find no matches, depending on the presence of the COUNT option. */ - kvobj *o = lookupKeyRead(c->db,c->argv[1]); - if (o == NULL) { - if (count != -1) - addReply(c,shared.emptyarray); - else - addReply(c,shared.null[c->resp]); - return; - } - if (checkType(c,o,OBJ_LIST)) return; - - /* If we got the COUNT option, prepare to emit an array. */ - void *arraylenptr = NULL; - if (count != -1) arraylenptr = addReplyDeferredLen(c); - - /* Seek the element. */ - listTypeIterator li; - listTypeEntry entry; - listTypeInitIterator(&li, o, direction == LIST_HEAD ? -1 : 0, direction); - long llen = listTypeLength(o); - long index = 0, matches = 0, matchindex = -1, arraylen = 0; - const size_t ele_len = sdslen(ele->ptr); - long long cached_longval = 0; - int cached_valid = 0; - while (listTypeNext(&li, &entry) && (maxlen == 0 || index < maxlen)) { - if (listTypeEqual(&entry,ele,ele_len,&cached_longval,&cached_valid)) { - matches++; - matchindex = (direction == LIST_TAIL) ? index : llen - index - 1; - if (matches >= rank) { - if (arraylenptr) { - arraylen++; - addReplyLongLong(c,matchindex); - if (count && matches-rank+1 >= count) break; - } else { - break; - } - } - } - index++; - matchindex = -1; /* Remember if we exit the loop without a match. */ - } - listTypeResetIterator(&li); - - /* Reply to the client. Note that arraylenptr is not NULL only if - * the COUNT option was selected. */ - if (arraylenptr != NULL) { - setDeferredArrayLen(c,arraylenptr,arraylen); - } else { - if (matchindex != -1) - addReplyLongLong(c,matchindex); - else - addReply(c,shared.null[c->resp]); - } -} - -/* LREM <key> <count> <element> */ -void lremCommand(client *c) { - robj *obj; - obj = c->argv[3]; - long toremove; - long removed = 0; - - if (getRangeLongFromObjectOrReply(c, c->argv[2], -LONG_MAX, LONG_MAX, &toremove, NULL) != C_OK) - return; - - kvobj *subject = lookupKeyWriteOrReply(c, c->argv[1], shared.czero); - if (subject == NULL || checkType(c,subject,OBJ_LIST)) return; - - listTypeIterator li; - if (toremove < 0) { - toremove = -toremove; - listTypeInitIterator(&li, subject, -1, LIST_HEAD); - } else { - listTypeInitIterator(&li, subject, 0, LIST_TAIL); - } - - listTypeEntry entry; - const size_t object_len = sdslen(c->argv[3]->ptr); - long long cached_longval = 0; - int cached_valid = 0; - size_t oldsize = 0; - if (server.memory_tracking_per_slot) - oldsize = listTypeAllocSize(subject); - while (listTypeNext(&li, &entry)) { - if (listTypeEqual(&entry,obj,object_len,&cached_longval,&cached_valid)) { - listTypeDelete(&li, &entry); - server.dirty++; - removed++; - if (toremove && removed == toremove) break; - } - } - listTypeResetIterator(&li); - - if (removed) { - long ll = listTypeLength(subject); - if (server.memory_tracking_per_slot) - updateSlotAllocSize(c->db, getKeySlot(c->argv[1]->ptr), oldsize, listTypeAllocSize(subject)); - updateKeysizesHist(c->db, getKeySlot(c->argv[1]->ptr), OBJ_LIST, ll + removed, ll); - notifyKeyspaceEvent(NOTIFY_LIST,"lrem",c->argv[1],c->db->id); - - if (ll == 0) { - dbDelete(c->db,c->argv[1]); - notifyKeyspaceEvent(NOTIFY_GENERIC,"del",c->argv[1],c->db->id); - } else { - listTypeTryConversion(subject,LIST_CONV_SHRINKING,NULL,NULL); - } - keyModified(c, c->db, c->argv[1], ll ? subject : NULL, 1); - } - - addReplyLongLong(c,removed); -} - -void lmoveHandlePush(client *c, robj *dstkey, robj *dstobj, robj *value, - int where) { - size_t oldsize = 0; - /* Create the list if the key does not exist */ - if (!dstobj) { - dstobj = createListListpackObject(); - dbAdd(c->db, dstkey, &dstobj); - } - if (server.memory_tracking_per_slot) - oldsize = listTypeAllocSize(dstobj); - listTypeTryConversionAppend(dstobj,&value,0,0,NULL,NULL); - listTypePush(dstobj,value,where); - if (server.memory_tracking_per_slot) - updateSlotAllocSize(c->db, getKeySlot(dstkey->ptr), oldsize, listTypeAllocSize(dstobj)); - keyModified(c,c->db,dstkey,dstobj,1); - - notifyKeyspaceEvent(NOTIFY_LIST, - where == LIST_HEAD ? "lpush" : "rpush", - dstkey, - c->db->id); - /* Always send the pushed value to the client. */ - addReplyBulk(c,value); -} - -int getListPositionFromObjectOrReply(client *c, robj *arg, int *position) { - if (strcasecmp(arg->ptr,"right") == 0) { - *position = LIST_TAIL; - } else if (strcasecmp(arg->ptr,"left") == 0) { - *position = LIST_HEAD; - } else { - addReplyErrorObject(c,shared.syntaxerr); - return C_ERR; - } - return C_OK; -} - -robj *getStringObjectFromListPosition(int position) { - if (position == LIST_HEAD) { - return shared.left; - } else { - // LIST_TAIL - return shared.right; - } -} - -void lmoveGenericCommand(client *c, int wherefrom, int whereto) { - size_t oldsize = 0; - kvobj *kvsrc = lookupKeyWriteOrReply(c,c->argv[1],shared.null[c->resp]); - if (kvsrc == NULL || checkType(c,kvsrc,OBJ_LIST)) return; - - if (listTypeLength(kvsrc) == 0) { - /* This may only happen after loading very old RDB files. Recent - * versions of Redis delete keys of empty lists. */ - addReplyNull(c); - } else { - robj *kvdst, *skey = c->argv[1]; - int64_t oldlen = 0, newlen = 1; /* init lengths assuming new dst object */ - - if ((kvdst = lookupKeyWrite(c->db,c->argv[2])) != NULL) { - if (checkType(c,kvdst,OBJ_LIST)) return; - /* dst object exists */ - oldlen = (int64_t) listTypeLength(kvdst); - newlen = oldlen + 1; - } - - if (server.memory_tracking_per_slot) - oldsize = listTypeAllocSize(kvsrc); - robj *value = listTypePop(kvsrc, wherefrom); - serverAssert(value); /* assertion for valgrind (avoid NPD) */ - if (server.memory_tracking_per_slot) - updateSlotAllocSize(c->db, getKeySlot(c->argv[1]->ptr), oldsize, listTypeAllocSize(kvsrc)); - lmoveHandlePush(c, c->argv[2], kvdst, value, whereto); - /* Update dst obj cardinality in KEYSIZES */ - updateKeysizesHist(c->db, getKeySlot(c->argv[2]->ptr), OBJ_LIST, oldlen, newlen); - /* Update src obj cardinality in KEYSIZES by listElementsRemoved() */ - listElementsRemoved(c, skey, wherefrom, kvsrc, 1, listTypeAllocSize(kvsrc), 1, NULL); - /* listTypePop returns an object with its refcount incremented */ - decrRefCount(value); - - if (c->cmd->proc == blmoveCommand) { - rewriteClientCommandVector(c,5,shared.lmove, - c->argv[1],c->argv[2],c->argv[3],c->argv[4]); - } else if (c->cmd->proc == brpoplpushCommand) { - rewriteClientCommandVector(c,3,shared.rpoplpush, - c->argv[1],c->argv[2]); - } - } -} - -/* LMOVE <source> <destination> (LEFT|RIGHT) (LEFT|RIGHT) */ -void lmoveCommand(client *c) { - int wherefrom, whereto; - if (getListPositionFromObjectOrReply(c,c->argv[3],&wherefrom) - != C_OK) return; - if (getListPositionFromObjectOrReply(c,c->argv[4],&whereto) - != C_OK) return; - lmoveGenericCommand(c, wherefrom, whereto); -} - -/* This is the semantic of this command: - * RPOPLPUSH srclist dstlist: - * IF LLEN(srclist) > 0 - * element = RPOP srclist - * LPUSH dstlist element - * RETURN element - * ELSE - * RETURN nil - * END - * END - * - * The idea is to be able to get an element from a list in a reliable way - * since the element is not just returned but pushed against another list - * as well. This command was originally proposed by Ezra Zygmuntowicz. - */ -void rpoplpushCommand(client *c) { - lmoveGenericCommand(c, LIST_TAIL, LIST_HEAD); -} - -/* Blocking RPOP/LPOP/LMPOP - * - * 'numkeys' is the number of keys. - * 'timeout_idx' parameter position of block timeout. - * 'where' LIST_HEAD for LEFT, LIST_TAIL for RIGHT. - * 'count' is the number of elements requested to pop, or -1 for plain single pop. - * - * When count is -1, a reply of a single bulk-string will be used. - * When count > 0, an array reply will be used. */ -void blockingPopGenericCommand(client *c, robj **keys, int numkeys, int where, int timeout_idx, long count) { - robj *o; - robj *key; - mstime_t timeout; - int j; - - if (getTimeoutFromObjectOrReply(c,c->argv[timeout_idx],&timeout,UNIT_SECONDS) - != C_OK) return; - - /* Traverse all input keys, we take action only based on one key. */ - for (j = 0; j < numkeys; j++) { - key = keys[j]; - o = lookupKeyWrite(c->db, key); - - /* Non-existing key, move to next key. */ - if (o == NULL) continue; - - if (checkType(c, o, OBJ_LIST)) return; - - long llen = listTypeLength(o); - /* Empty list, move to next key. */ - if (llen == 0) continue; - - if (count != -1) { - /* BLMPOP, non empty list, like a normal [LR]POP with count option. - * The difference here we pop a range of elements in a nested arrays way. */ - listPopRangeAndReplyWithKey(c, o, key, where, count, 1, NULL); - - /* Replicate it as [LR]POP COUNT. */ - robj *count_obj = createStringObjectFromLongLong((count > llen) ? llen : count); - rewriteClientCommandVector(c, 3, - (where == LIST_HEAD) ? shared.lpop : shared.rpop, - key, count_obj); - decrRefCount(count_obj); - return; - } - - /* Non empty list, this is like a normal [LR]POP. */ - size_t oldsize = 0; - if (server.memory_tracking_per_slot) - oldsize = listTypeAllocSize(o); - robj *value = listTypePop(o,where); - serverAssert(value != NULL); - - addReplyArrayLen(c,2); - addReplyBulk(c,key); - addReplyBulk(c,value); - decrRefCount(value); - listElementsRemoved(c,key,where,o,1,oldsize,1,NULL); - - /* Replicate it as an [LR]POP instead of B[LR]POP. */ - rewriteClientCommandVector(c,2, - (where == LIST_HEAD) ? shared.lpop : shared.rpop, - key); - return; - } - - /* If we are not allowed to block the client, the only thing - * we can do is treating it as a timeout (even with timeout 0). */ - if (c->flags & CLIENT_DENY_BLOCKING) { - addReplyNullArray(c); - return; - } - - /* If the keys do not exist we must block */ - blockForKeys(c,BLOCKED_LIST,keys,numkeys,timeout,0); -} - -/* BLPOP <key> [<key> ...] <timeout> */ -void blpopCommand(client *c) { - blockingPopGenericCommand(c,c->argv+1,c->argc-2,LIST_HEAD,c->argc-1,-1); -} - -/* BRPOP <key> [<key> ...] <timeout> */ -void brpopCommand(client *c) { - blockingPopGenericCommand(c,c->argv+1,c->argc-2,LIST_TAIL,c->argc-1,-1); -} - -void blmoveGenericCommand(client *c, int wherefrom, int whereto, mstime_t timeout) { - robj *key = lookupKeyWrite(c->db, c->argv[1]); - if (checkType(c,key,OBJ_LIST)) return; - - if (key == NULL) { - if (c->flags & CLIENT_DENY_BLOCKING) { - /* Blocking against an empty list when blocking is not allowed - * returns immediately. */ - addReplyNull(c); - } else { - /* The list is empty and the client blocks. */ - blockForKeys(c,BLOCKED_LIST,c->argv + 1,1,timeout,0); - } - } else { - /* The list exists and has elements, so - * the regular lmoveCommand is executed. */ - serverAssertWithInfo(c,key,listTypeLength(key) > 0); - lmoveGenericCommand(c,wherefrom,whereto); - } -} - -/* BLMOVE <source> <destination> (LEFT|RIGHT) (LEFT|RIGHT) <timeout> */ -void blmoveCommand(client *c) { - mstime_t timeout; - int wherefrom, whereto; - if (getListPositionFromObjectOrReply(c,c->argv[3],&wherefrom) - != C_OK) return; - if (getListPositionFromObjectOrReply(c,c->argv[4],&whereto) - != C_OK) return; - if (getTimeoutFromObjectOrReply(c,c->argv[5],&timeout,UNIT_SECONDS) - != C_OK) return; - blmoveGenericCommand(c,wherefrom,whereto,timeout); -} - -/* BRPOPLPUSH <source> <destination> <timeout> */ -void brpoplpushCommand(client *c) { - mstime_t timeout; - if (getTimeoutFromObjectOrReply(c,c->argv[3],&timeout,UNIT_SECONDS) - != C_OK) return; - blmoveGenericCommand(c, LIST_TAIL, LIST_HEAD, timeout); -} - -/* LMPOP/BLMPOP - * - * 'numkeys_idx' parameter position of key number. - * 'is_block' this indicates whether it is a blocking variant. */ -void lmpopGenericCommand(client *c, int numkeys_idx, int is_block) { - long j; - long numkeys = 0; /* Number of keys. */ - int where = 0; /* HEAD for LEFT, TAIL for RIGHT. */ - long count = -1; /* Reply will consist of up to count elements, depending on the list's length. */ - - /* Parse the numkeys. */ - if (getRangeLongFromObjectOrReply(c, c->argv[numkeys_idx], 1, LONG_MAX, - &numkeys, "numkeys should be greater than 0") != C_OK) - return; - - /* Parse the where. where_idx: the index of where in the c->argv. */ - long where_idx = numkeys_idx + numkeys + 1; - if (where_idx >= c->argc) { - addReplyErrorObject(c, shared.syntaxerr); - return; - } - if (getListPositionFromObjectOrReply(c, c->argv[where_idx], &where) != C_OK) - return; - - /* Parse the optional arguments. */ - for (j = where_idx + 1; j < c->argc; j++) { - char *opt = c->argv[j]->ptr; - int moreargs = (c->argc - 1) - j; - - if (count == -1 && !strcasecmp(opt, "COUNT") && moreargs) { - j++; - if (getRangeLongFromObjectOrReply(c, c->argv[j], 1, LONG_MAX, - &count,"count should be greater than 0") != C_OK) - return; - } else { - addReplyErrorObject(c, shared.syntaxerr); - return; - } - } - - if (count == -1) count = 1; - - if (is_block) { - /* BLOCK. We will handle CLIENT_DENY_BLOCKING flag in blockingPopGenericCommand. */ - blockingPopGenericCommand(c, c->argv+numkeys_idx+1, numkeys, where, 1, count); - } else { - /* NON-BLOCK */ - mpopGenericCommand(c, c->argv+numkeys_idx+1, numkeys, where, count); - } -} - -/* LMPOP numkeys <key> [<key> ...] (LEFT|RIGHT) [COUNT count] */ -void lmpopCommand(client *c) { - lmpopGenericCommand(c, 1, 0); -} - -/* BLMPOP timeout numkeys <key> [<key> ...] (LEFT|RIGHT) [COUNT count] */ -void blmpopCommand(client *c) { - lmpopGenericCommand(c, 2, 1); -} |