From: Robey Pointer Date: Fri, 11 Jun 2010 08:08:59 +0000 (+0200) Subject: squashed merge from robey/twitter3: LINSERT BEFORE|AFTER, LPUSHX, RPUSHX X-Git-Url: https://git.saurik.com/redis.git/commitdiff_plain/dedff272f640b2df73062da06b8f3b82e19de2c2 squashed merge from robey/twitter3: LINSERT BEFORE|AFTER, LPUSHX, RPUSHX --- diff --git a/adlist.c b/adlist.c index fd2d6fd1..015012f5 100644 --- a/adlist.c +++ b/adlist.c @@ -123,6 +123,35 @@ list *listAddNodeTail(list *list, void *value) return list; } +list *listInsertNode(list *list, listNode *old_node, void *value, int after) { + listNode *node; + + if ((node = zmalloc(sizeof(*node))) == NULL) + return NULL; + node->value = value; + if (after) { + node->prev = old_node; + node->next = old_node->next; + if (list->tail == old_node) { + list->tail = node; + } + } else { + node->next = old_node; + node->prev = old_node->prev; + if (list->head == old_node) { + list->head = node; + } + } + if (node->prev != NULL) { + node->prev->next = node; + } + if (node->next != NULL) { + node->next->prev = node; + } + list->len++; + return list; +} + /* Remove the specified node from the specified list. * It's up to the caller to free the private value of the node. * @@ -183,9 +212,9 @@ void listRewindTail(list *list, listIter *li) { * or NULL if there are no more elements, so the classical usage patter * is: * - * iter = listGetItarotr(list,); - * while ((node = listNextIterator(iter)) != NULL) { - * DoSomethingWith(listNodeValue(node)); + * iter = listGetIterator(list,); + * while ((node = listNext(iter)) != NULL) { + * doSomethingWith(listNodeValue(node)); * } * * */ diff --git a/adlist.h b/adlist.h index 41ca13f1..a1209f62 100644 --- a/adlist.h +++ b/adlist.h @@ -74,6 +74,7 @@ list *listCreate(void); void listRelease(list *list); list *listAddNodeHead(list *list, void *value); list *listAddNodeTail(list *list, void *value); +list *listInsertNode(list *list, listNode *old_node, void *value, int after); void listDelNode(list *list, listNode *node); listIter *listGetIterator(list *list, int direction); listNode *listNext(listIter *iter); diff --git a/redis.c b/redis.c index f970425e..5d44e827 100644 --- a/redis.c +++ b/redis.c @@ -261,7 +261,7 @@ typedef struct redisObject { unsigned lru:22; /* lru time (relative to server.lruclock) */ int refcount; void *ptr; - /* VM fields, this are only allocated if VM is active, otherwise the + /* VM fields are only allocated if VM is active, otherwise the * object allocation function will just allocate * sizeof(redisObjct) minus sizeof(redisObjectVM), so using * Redis without VM active will not have any overhead. */ @@ -692,6 +692,9 @@ static void renameCommand(redisClient *c); static void renamenxCommand(redisClient *c); static void lpushCommand(redisClient *c); static void rpushCommand(redisClient *c); +static void lpushxCommand(redisClient *c); +static void rpushxCommand(redisClient *c); +static void linsertCommand(redisClient *c); static void lpopCommand(redisClient *c); static void rpopCommand(redisClient *c); static void llenCommand(redisClient *c); @@ -792,6 +795,9 @@ static struct redisCommand readonlyCommandTable[] = { {"mget",mgetCommand,-2,REDIS_CMD_INLINE,NULL,1,-1,1}, {"rpush",rpushCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,NULL,1,1,1}, {"lpush",lpushCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,NULL,1,1,1}, + {"rpushx",rpushxCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,NULL,1,1,1}, + {"lpushx",lpushxCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,NULL,1,1,1}, + {"linsert",linsertCommand,5,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,NULL,1,1,1}, {"rpop",rpopCommand,2,REDIS_CMD_INLINE,NULL,1,1,1}, {"lpop",lpopCommand,2,REDIS_CMD_INLINE,NULL,1,1,1}, {"brpop",brpopCommand,-3,REDIS_CMD_INLINE,NULL,1,1,1}, @@ -5174,6 +5180,82 @@ static void rpushCommand(redisClient *c) { pushGenericCommand(c,REDIS_TAIL); } +static void listTypeInsert(robj *subject, listTypeEntry *old_entry, robj *new_obj, int where) { + listTypeTryConversion(subject,new_obj); + if (subject->encoding == REDIS_ENCODING_ZIPLIST) { + if (where == REDIS_HEAD) { + unsigned char *next = ziplistNext(subject->ptr,old_entry->zi); + if (next == NULL) { + listTypePush(subject,new_obj,REDIS_TAIL); + } else { + subject->ptr = ziplistInsert(subject->ptr,next,new_obj->ptr,sdslen(new_obj->ptr)); + } + } else { + subject->ptr = ziplistInsert(subject->ptr,old_entry->zi,new_obj->ptr,sdslen(new_obj->ptr)); + } + } else if (subject->encoding == REDIS_ENCODING_LIST) { + if (where == REDIS_HEAD) { + listInsertNode(subject->ptr,old_entry->ln,new_obj,1); + } else { + listInsertNode(subject->ptr,old_entry->ln,new_obj,0); + } + incrRefCount(new_obj); + } else { + redisPanic("Unknown list encoding"); + } +} + +static void pushxGenericCommand(redisClient *c, int where, robj *old_obj, robj *new_obj) { + robj *subject; + listTypeIterator *iter; + listTypeEntry entry; + + if ((subject = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || + checkType(c,subject,REDIS_LIST)) return; + if (handleClientsWaitingListPush(c,c->argv[1],new_obj)) { + addReply(c,shared.cone); + return; + } + + if (old_obj != NULL) { + if (where == REDIS_HEAD) { + iter = listTypeInitIterator(subject,0,REDIS_TAIL); + } else { + iter = listTypeInitIterator(subject,-1,REDIS_HEAD); + } + while (listTypeNext(iter,&entry)) { + if (listTypeEqual(&entry,old_obj)) { + listTypeInsert(subject,&entry,new_obj,where); + break; + } + } + listTypeReleaseIterator(iter); + } else { + listTypePush(subject,new_obj,where); + } + + server.dirty++; + addReplyUlong(c,listTypeLength(subject)); +} + +static void lpushxCommand(redisClient *c) { + pushxGenericCommand(c,REDIS_HEAD,NULL,c->argv[2]); +} + +static void rpushxCommand(redisClient *c) { + pushxGenericCommand(c,REDIS_TAIL,NULL,c->argv[2]); +} + +static void linsertCommand(redisClient *c) { + if (strcasecmp(c->argv[2]->ptr,"after") == 0) { + pushxGenericCommand(c,REDIS_HEAD,c->argv[3],c->argv[4]); + } else if (strcasecmp(c->argv[2]->ptr,"before") == 0) { + pushxGenericCommand(c,REDIS_TAIL,c->argv[3],c->argv[4]); + } else { + addReply(c,shared.syntaxerr); + } +} + static void llenCommand(redisClient *c) { robj *o = lookupKeyReadOrReply(c,c->argv[1],shared.czero); if (o == NULL || checkType(c,o,REDIS_LIST)) return; diff --git a/tests/support/redis.tcl b/tests/support/redis.tcl index 0f4e401f..8f7d7711 100644 --- a/tests/support/redis.tcl +++ b/tests/support/redis.tcl @@ -40,7 +40,7 @@ array set ::redis::multibulkarg {} # Flag commands requiring last argument as a bulk write operation foreach redis_bulk_cmd { - set setnx rpush lpush lset lrem sadd srem sismember echo getset smove zadd zrem zscore zincrby append zrank zrevrank hget hdel hexists setex + set setnx rpush lpush rpushx lpushx linsert lset lrem sadd srem sismember echo getset smove zadd zrem zscore zincrby append zrank zrevrank hget hdel hexists setex } { set ::redis::bulkarg($redis_bulk_cmd) {} } diff --git a/tests/unit/type/list.tcl b/tests/unit/type/list.tcl index 22f40958..691040ec 100644 --- a/tests/unit/type/list.tcl +++ b/tests/unit/type/list.tcl @@ -52,6 +52,54 @@ start_server { assert_equal $large_value [r lindex mylist2 2] } + test {LPUSHX, RPUSHX, LPUSHXAFTER, RPUSHXAFTER - ziplist} { + r del xlist + assert_equal 0 [r lpushx xlist a] + assert_equal 0 [r rpushx xlist a] + assert_equal 1 [r rpush xlist b] + assert_equal 2 [r rpush xlist c] + assert_equal 3 [r rpushx xlist d] + assert_equal 4 [r lpushx xlist a] + assert_encoding ziplist xlist + assert_equal {a b c d} [r lrange xlist 0 10] + + assert_equal 5 [r linsert xlist before c zz] + assert_equal {a b zz c d} [r lrange xlist 0 10] + assert_equal 6 [r linsert xlist after c yy] + assert_equal {a b zz c yy d} [r lrange xlist 0 10] + assert_equal 7 [r linsert xlist after d dd] + assert_equal 7 [r linsert xlist after bad ddd] + assert_equal {a b zz c yy d dd} [r lrange xlist 0 10] + assert_equal 8 [r linsert xlist before a aa] + assert_equal 8 [r linsert xlist before bad aaa] + assert_equal {aa a b zz c yy d dd} [r lrange xlist 0 10] + } + + test {LPUSHX, RPUSHX, LPUSHXAFTER, RPUSHXAFTER - regular list} { + set large_value "aaaaaaaaaaaaaaaaa" + + r del xlist + assert_equal 0 [r lpushx xlist a] + assert_equal 0 [r rpushx xlist a] + assert_equal 1 [r rpush xlist $large_value] + assert_equal 2 [r rpush xlist c] + assert_equal 3 [r rpushx xlist d] + assert_equal 4 [r lpushx xlist a] + assert_encoding list xlist + assert_equal {a aaaaaaaaaaaaaaaaa c d} [r lrange xlist 0 10] + + assert_equal 5 [r linsert xlist before c zz] + assert_equal {a aaaaaaaaaaaaaaaaa zz c d} [r lrange xlist 0 10] + assert_equal 6 [r linsert xlist after c yy] + assert_equal {a aaaaaaaaaaaaaaaaa zz c yy d} [r lrange xlist 0 10] + assert_equal 7 [r linsert xlist after d dd] + assert_equal 7 [r linsert xlist after bad ddd] + assert_equal {a aaaaaaaaaaaaaaaaa zz c yy d dd} [r lrange xlist 0 10] + assert_equal 8 [r linsert xlist before a aa] + assert_equal 8 [r linsert xlist before bad aaa] + assert_equal {aa a aaaaaaaaaaaaaaaaa zz c yy d dd} [r lrange xlist 0 10] + } + test {DEL a list - ziplist} { assert_equal 1 [r del myziplist2] assert_equal 0 [r exists myziplist2]