A trivial change makes the new implementation O(log(N)) instead of O(log(N))+O(M...

diff --git a/redis.c b/redis.c
index 0fb6b1e8e64a1a178bd9cee902c038dcb74a51f3..1c07dbc2f1e02145acb1582df9b3bf176680f5d8 100644 (file)
--- a/redis.c
+++ b/redis.c
@@ -3855,7 +3855,10 @@ static void zslInsert(zskiplist *zsl, double score, robj *obj) {
 
     x = zsl->header;
     for (i = zsl->level-1; i >= 0; i--) {
 
     x = zsl->header;
     for (i = zsl->level-1; i >= 0; i--) {

-        while (x->forward[i] && x->forward[i]->score < score)
+        while (x->forward[i] &&
+            (x->forward[i]->score < score ||
+                (x->forward[i]->score == score &&
+                compareStringObjects(x->forward[i]->obj,obj) < 0)))

             x = x->forward[i];
         update[i] = x;
     }
             x = x->forward[i];
         update[i] = x;
     }


@@ -3888,34 +3891,34 @@ static int zslDelete(zskiplist *zsl, double score, robj *obj) {
 
     x = zsl->header;
     for (i = zsl->level-1; i >= 0; i--) {
 
     x = zsl->header;
     for (i = zsl->level-1; i >= 0; i--) {

-        while (x->forward[i] && x->forward[i]->score < score)
+        while (x->forward[i] &&
+            (x->forward[i]->score < score ||
+                (x->forward[i]->score == score &&
+                compareStringObjects(x->forward[i]->obj,obj) < 0)))

             x = x->forward[i];
         update[i] = x;
     }
     /* We may have multiple elements with the same score, what we need
      * is to find the element with both the right score and object. */
     x = x->forward[0];
             x = x->forward[i];
         update[i] = x;
     }
     /* We may have multiple elements with the same score, what we need
      * is to find the element with both the right score and object. */
     x = x->forward[0];

-    while(x->score == score) {
-        if (compareStringObjects(x->obj,obj) == 0) {
-            for (i = 0; i < zsl->level; i++) {
-                if (update[i]->forward[i] != x) break;
-                update[i]->forward[i] = x->forward[i];
-            }
-            if (x->forward[0]) {
-                x->forward[0]->backward = (x->backward == zsl->header) ?
-                                            NULL : x->backward;
-            } else {
-                zsl->tail = x->backward;
-            }
-            zslFreeNode(x);
-            while(zsl->level > 1 && zsl->header->forward[zsl->level-1] == NULL)
-                zsl->level--;
-            zsl->length--;
-            return 1;
+    if (compareStringObjects(x->obj,obj) == 0) {
+        for (i = 0; i < zsl->level; i++) {
+            if (update[i]->forward[i] != x) break;
+            update[i]->forward[i] = x->forward[i];
+        }
+        if (x->forward[0]) {
+            x->forward[0]->backward = (x->backward == zsl->header) ?
+                                        NULL : x->backward;

         } else {
         } else {

-            x = x->forward[0];
-            if (!x) return 0; /* end of the list reached, not found */
+            zsl->tail = x->backward;

         }
         }

+        zslFreeNode(x);
+        while(zsl->level > 1 && zsl->header->forward[zsl->level-1] == NULL)
+            zsl->level--;
+        zsl->length--;
+        return 1;
+    } else {
+        return 0; /* not found */

     }
     return 0; /* not found */
 }
     }
     return 0; /* not found */
 }