From: Pieter Noordhuis <pcnoordhuis@gmail.com>
Date: Thu, 4 Mar 2010 15:35:57 +0000 (+0100)
Subject: merged memory reduction patch
X-Git-Url: https://git.saurik.com/redis.git/commitdiff_plain/a50ea45c841e980f7692a9cd97130f0f37e5917b

merged memory reduction patch
---

a50ea45c841e980f7692a9cd97130f0f37e5917b
diff --cc redis.c
index bff1cdfc,0353940e..4f7d3efc
--- a/redis.c
+++ b/redis.c
@@@ -4909,7 -4864,11 +4910,7 @@@ static void zslInsert(zskiplist *zsl, d
              (x->forward[i]->score < score ||
                  (x->forward[i]->score == score &&
                  compareStringObjects(x->forward[i]->obj,obj) < 0))) {
-             span[i] += x->span[i];
 -            if (i > 0) {
 -                rank[i] += x->span[i-1];
 -            } else {
 -                rank[i]++;
 -            }
++            rank[i] += i > 0 ? x->span[i-1] : 1;
              x = x->forward[i];
          }
          update[i] = x;
@@@ -5054,53 -5023,6 +5065,53 @@@ static zskiplistNode *zslFirstWithScore
      return x->forward[0];
  }
  
 +/* Find the rank for an element by both score and key.
 + * Returns 0 when the element cannot be found, rank otherwise.
 + * Note that the rank is 1-based due to the span of zsl->header to the
 + * first element. */
 +static unsigned long zslGetRank(zskiplist *zsl, double score, robj *o) {
 +    zskiplistNode *x;
 +    unsigned long rank = 0;
 +    int i;
 +
 +    x = zsl->header;
 +    for (i = zsl->level-1; i >= 0; i--) {
 +        while (x->forward[i] &&
 +            (x->forward[i]->score < score ||
 +                (x->forward[i]->score == score &&
 +                compareStringObjects(x->forward[i]->obj,o) <= 0))) {
-             rank += x->span[i];
++            rank += i > 0 ? x->span[i-1] : 1;
 +            x = x->forward[i];
 +        }
 +
 +        /* x might be equal to zsl->header, so test if obj is non-NULL */
 +        if (x->obj && compareStringObjects(x->obj,o) == 0) {
 +            return rank;
 +        }
 +    }
 +    return 0;
 +}
 +
 +/* Finds an element by its rank. The rank argument needs to be 1-based. */
 +zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank) {
 +    zskiplistNode *x;
 +    unsigned long traversed = 0;
 +    int i;
 +
 +    x = zsl->header;
 +    for (i = zsl->level-1; i >= 0; i--) {
-         while (x->forward[i] && (traversed + x->span[i]) <= rank) {
-             traversed += x->span[i];
++        while (x->forward[i] && (traversed + (i > 0 ? x->span[i-1] : 1)) <= rank) {
++            traversed += i > 0 ? x->span[i-1] : 1;
 +            x = x->forward[i];
 +        }
 +
 +        if (traversed == rank) {
 +            return x;
 +        }
 +    }
 +    return NULL;
 +}
 +
  /* The actual Z-commands implementations */
  
  /* This generic command implements both ZADD and ZINCRBY.