squashed merge from robey/twitter3: LINSERT BEFORE|AFTER, LPUSHX, RPUSHX

diff --git a/adlist.c b/adlist.c
index fd2d6fd142790c5331b1d1450866875f11c6796a..015012f5ce392f57b340808d32e69989967148ea 100644 (file)
--- a/adlist.c
+++ b/adlist.c
@@ -123,6 +123,35 @@ list *listAddNodeTail(list *list, void *value)
     return list;
 }
 
     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.
  *
 /* 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:
  *
  * or NULL if there are no more elements, so the classical usage patter
  * is:
  *

- * iter = listGetItarotr(list,<direction>);
- * while ((node = listNextIterator(iter)) != NULL) {
- *     DoSomethingWith(listNodeValue(node));
+ * iter = listGetIterator(list,<direction>);
+ * while ((node = listNext(iter)) != NULL) {
+ *     doSomethingWith(listNodeValue(node));

  * }
  *
  * */
  * }
  *
  * */

diff --git a/adlist.h b/adlist.h
index 41ca13f1fc772e0f7d4bb9f87d13059dd04c2953..a1209f62faaf8537ea752c250fe8c65f5c5b247c 100644 (file)
--- 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);
 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);
 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 f970425e4fa9f24e478d44b2df59a5e930663986..5d44e8275c298d91736a4cf404b8674fefd93bf2 100644 (file)
--- 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;
     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. */
      * 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 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);
 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},
     {"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},
     {"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);
 }
 
     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;
 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 0f4e401ffc1d5881f99ca77ed0a5abd88d890e90..8f7d77114947948b0a6a637441e7f6b027c9a65f 100644 (file)
--- 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 {
 
 # 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) {}
 }
 } {
     set ::redis::bulkarg($redis_bulk_cmd) {}
 }

diff --git a/tests/unit/type/list.tcl b/tests/unit/type/list.tcl
index 22f409587015691181698a2e9c00ee9dc4119987..691040ece9abdc34771ce6559359b09de29c58b5 100644 (file)
--- 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]
     }
 
         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]
     test {DEL a list - ziplist} {
         assert_equal 1 [r del myziplist2]
         assert_equal 0 [r exists myziplist2]