+/* ==================================== ZSets =============================== */
+
+/* ZSETs are ordered sets using two data structures to hold the same elements
+ * in order to get O(log(N)) INSERT and REMOVE operations into a sorted
+ * data structure.
+ *
+ * The elements are added to an hash table mapping Redis objects to scores.
+ * At the same time the elements are added to a skip list mapping scores
+ * to Redis objects (so objects are sorted by scores in this "view"). */
+
+/* This skiplist implementation is almost a C translation of the original
+ * algorithm described by William Pugh in "Skip Lists: A Probabilistic
+ * Alternative to Balanced Trees", modified in three ways:
+ * a) this implementation allows for repeated values.
+ * b) the comparison is not just by key (our 'score') but by satellite data.
+ * c) there is a back pointer, so it's a doubly linked list with the back
+ * pointers being only at "level 1". This allows to traverse the list
+ * from tail to head, useful for ZREVRANGE. */
+
+static zskiplistNode *zslCreateNode(int level, double score, robj *obj) {
+ zskiplistNode *zn = zmalloc(sizeof(*zn));
+
+ zn->forward = zmalloc(sizeof(zskiplistNode*) * level);
+ zn->score = score;
+ zn->obj = obj;
+ return zn;
+}
+
+static zskiplist *zslCreate(void) {
+ int j;
+ zskiplist *zsl;
+
+ zsl = zmalloc(sizeof(*zsl));
+ zsl->level = 1;
+ zsl->length = 0;
+ zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
+ for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++)
+ zsl->header->forward[j] = NULL;
+ zsl->header->backward = NULL;
+ zsl->tail = NULL;
+ return zsl;
+}
+
+static void zslFreeNode(zskiplistNode *node) {
+ decrRefCount(node->obj);
+ zfree(node->forward);
+ zfree(node);
+}
+
+static void zslFree(zskiplist *zsl) {
+ zskiplistNode *node = zsl->header->forward[0], *next;
+
+ zfree(zsl->header->forward);
+ zfree(zsl->header);
+ while(node) {
+ next = node->forward[0];
+ zslFreeNode(node);
+ node = next;
+ }
+ zfree(zsl);
+}
+
+static int zslRandomLevel(void) {
+ int level = 1;
+ while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
+ level += 1;
+ return level;
+}
+
+static void zslInsert(zskiplist *zsl, double score, robj *obj) {
+ zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
+ int i, level;
+
+ 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,obj) < 0)))
+ x = x->forward[i];
+ update[i] = x;
+ }
+ /* we assume the key is not already inside, since we allow duplicated
+ * scores, and the re-insertion of score and redis object should never
+ * happpen since the caller of zslInsert() should test in the hash table
+ * if the element is already inside or not. */
+ level = zslRandomLevel();
+ if (level > zsl->level) {
+ for (i = zsl->level; i < level; i++)
+ update[i] = zsl->header;
+ zsl->level = level;
+ }
+ x = zslCreateNode(level,score,obj);
+ for (i = 0; i < level; i++) {
+ x->forward[i] = update[i]->forward[i];
+ update[i]->forward[i] = x;
+ }
+ x->backward = (update[0] == zsl->header) ? NULL : update[0];
+ if (x->forward[0])
+ x->forward[0]->backward = x;
+ else
+ zsl->tail = x;
+ zsl->length++;
+}
+
+/* Delete an element with matching score/object from the skiplist. */
+static int zslDelete(zskiplist *zsl, double score, robj *obj) {
+ zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
+ 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,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];
+ if (x && score == x->score && 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;
+ } else {
+ return 0; /* not found */
+ }
+ return 0; /* not found */
+}
+
+/* Delete all the elements with score between min and max from the skiplist.
+ * Min and mx are inclusive, so a score >= min || score <= max is deleted.
+ * Note that this function takes the reference to the hash table view of the
+ * sorted set, in order to remove the elements from the hash table too. */
+static unsigned long zslDeleteRange(zskiplist *zsl, double min, double max, dict *dict) {
+ zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
+ unsigned long removed = 0;
+ int i;
+
+ x = zsl->header;
+ for (i = zsl->level-1; i >= 0; i--) {
+ while (x->forward[i] && x->forward[i]->score < min)
+ 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 && x->score <= max) {
+ zskiplistNode *next;
+
+ 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;
+ }
+ next = x->forward[0];
+ dictDelete(dict,x->obj);
+ zslFreeNode(x);
+ while(zsl->level > 1 && zsl->header->forward[zsl->level-1] == NULL)
+ zsl->level--;
+ zsl->length--;
+ removed++;
+ x = next;
+ }
+ return removed; /* not found */
+}
+
+/* Find the first node having a score equal or greater than the specified one.
+ * Returns NULL if there is no match. */
+static zskiplistNode *zslFirstWithScore(zskiplist *zsl, double score) {
+ zskiplistNode *x;
+ int i;
+
+ x = zsl->header;
+ for (i = zsl->level-1; i >= 0; i--) {
+ while (x->forward[i] && x->forward[i]->score < score)
+ x = x->forward[i];
+ }
+ /* We may have multiple elements with the same score, what we need
+ * is to find the element with both the right score and object. */
+ return x->forward[0];
+}
+
+/* The actual Z-commands implementations */
+
+static void zaddCommand(redisClient *c) {
+ robj *zsetobj;
+ zset *zs;
+ double *score;
+
+ zsetobj = lookupKeyWrite(c->db,c->argv[1]);
+ if (zsetobj == NULL) {
+ zsetobj = createZsetObject();
+ dictAdd(c->db->dict,c->argv[1],zsetobj);
+ incrRefCount(c->argv[1]);
+ } else {
+ if (zsetobj->type != REDIS_ZSET) {
+ addReply(c,shared.wrongtypeerr);
+ return;
+ }
+ }
+ score = zmalloc(sizeof(double));
+ *score = strtod(c->argv[2]->ptr,NULL);
+ zs = zsetobj->ptr;
+ if (dictAdd(zs->dict,c->argv[3],score) == DICT_OK) {
+ /* case 1: New element */
+ incrRefCount(c->argv[3]); /* added to hash */
+ zslInsert(zs->zsl,*score,c->argv[3]);
+ incrRefCount(c->argv[3]); /* added to skiplist */
+ server.dirty++;
+ addReply(c,shared.cone);
+ } else {
+ dictEntry *de;
+ double *oldscore;
+
+ /* case 2: Score update operation */
+ de = dictFind(zs->dict,c->argv[3]);
+ assert(de != NULL);
+ oldscore = dictGetEntryVal(de);
+ if (*score != *oldscore) {
+ int deleted;
+
+ deleted = zslDelete(zs->zsl,*oldscore,c->argv[3]);
+ assert(deleted != 0);
+ zslInsert(zs->zsl,*score,c->argv[3]);
+ incrRefCount(c->argv[3]);
+ dictReplace(zs->dict,c->argv[3],score);
+ server.dirty++;
+ } else {
+ zfree(score);
+ }
+ addReply(c,shared.czero);
+ }
+}
+
+static void zremCommand(redisClient *c) {
+ robj *zsetobj;
+ zset *zs;
+
+ zsetobj = lookupKeyWrite(c->db,c->argv[1]);
+ if (zsetobj == NULL) {
+ addReply(c,shared.czero);
+ } else {
+ dictEntry *de;
+ double *oldscore;
+ int deleted;
+
+ if (zsetobj->type != REDIS_ZSET) {
+ addReply(c,shared.wrongtypeerr);
+ return;
+ }
+ zs = zsetobj->ptr;
+ de = dictFind(zs->dict,c->argv[2]);
+ if (de == NULL) {
+ addReply(c,shared.czero);
+ return;
+ }
+ /* Delete from the skiplist */
+ oldscore = dictGetEntryVal(de);
+ deleted = zslDelete(zs->zsl,*oldscore,c->argv[2]);
+ assert(deleted != 0);
+
+ /* Delete from the hash table */
+ dictDelete(zs->dict,c->argv[2]);
+ if (htNeedsResize(zs->dict)) dictResize(zs->dict);
+ server.dirty++;
+ addReply(c,shared.cone);
+ }
+}
+
+static void zremrangebyscoreCommand(redisClient *c) {
+ double min = strtod(c->argv[2]->ptr,NULL);
+ double max = strtod(c->argv[3]->ptr,NULL);
+ robj *zsetobj;
+ zset *zs;
+
+ zsetobj = lookupKeyWrite(c->db,c->argv[1]);
+ if (zsetobj == NULL) {
+ addReply(c,shared.czero);
+ } else {
+ long deleted;
+
+ if (zsetobj->type != REDIS_ZSET) {
+ addReply(c,shared.wrongtypeerr);
+ return;
+ }
+ zs = zsetobj->ptr;
+ deleted = zslDeleteRange(zs->zsl,min,max,zs->dict);
+ if (htNeedsResize(zs->dict)) dictResize(zs->dict);
+ server.dirty += deleted;
+ addReplySds(c,sdscatprintf(sdsempty(),":%lu\r\n",deleted));
+ }
+}
+
+static void zrangeGenericCommand(redisClient *c, int reverse) {
+ robj *o;
+ int start = atoi(c->argv[2]->ptr);
+ int end = atoi(c->argv[3]->ptr);
+
+ o = lookupKeyRead(c->db,c->argv[1]);
+ if (o == NULL) {
+ addReply(c,shared.nullmultibulk);
+ } else {
+ if (o->type != REDIS_ZSET) {
+ addReply(c,shared.wrongtypeerr);
+ } else {
+ zset *zsetobj = o->ptr;
+ zskiplist *zsl = zsetobj->zsl;
+ zskiplistNode *ln;
+
+ int llen = zsl->length;
+ int rangelen, j;
+ robj *ele;
+
+ /* convert negative indexes */
+ if (start < 0) start = llen+start;
+ if (end < 0) end = llen+end;
+ if (start < 0) start = 0;
+ if (end < 0) end = 0;
+
+ /* indexes sanity checks */
+ if (start > end || start >= llen) {
+ /* Out of range start or start > end result in empty list */
+ addReply(c,shared.emptymultibulk);
+ return;
+ }
+ if (end >= llen) end = llen-1;
+ rangelen = (end-start)+1;
+
+ /* Return the result in form of a multi-bulk reply */
+ if (reverse) {
+ ln = zsl->tail;
+ while (start--)
+ ln = ln->backward;
+ } else {
+ ln = zsl->header->forward[0];
+ while (start--)
+ ln = ln->forward[0];
+ }
+
+ addReplySds(c,sdscatprintf(sdsempty(),"*%d\r\n",rangelen));
+ for (j = 0; j < rangelen; j++) {
+ ele = ln->obj;
+ addReplyBulkLen(c,ele);
+ addReply(c,ele);
+ addReply(c,shared.crlf);
+ ln = reverse ? ln->backward : ln->forward[0];
+ }
+ }
+ }
+}
+
+static void zrangeCommand(redisClient *c) {
+ zrangeGenericCommand(c,0);
+}
+
+static void zrevrangeCommand(redisClient *c) {
+ zrangeGenericCommand(c,1);
+}
+
+static void zrangebyscoreCommand(redisClient *c) {
+ robj *o;
+ double min = strtod(c->argv[2]->ptr,NULL);
+ double max = strtod(c->argv[3]->ptr,NULL);
+
+ o = lookupKeyRead(c->db,c->argv[1]);
+ if (o == NULL) {
+ addReply(c,shared.nullmultibulk);
+ } else {
+ if (o->type != REDIS_ZSET) {
+ addReply(c,shared.wrongtypeerr);
+ } else {
+ zset *zsetobj = o->ptr;
+ zskiplist *zsl = zsetobj->zsl;
+ zskiplistNode *ln;
+ robj *ele, *lenobj;
+ unsigned int rangelen = 0;
+
+ /* Get the first node with the score >= min */
+ ln = zslFirstWithScore(zsl,min);
+ if (ln == NULL) {
+ /* No element matching the speciifed interval */
+ addReply(c,shared.emptymultibulk);
+ return;
+ }
+
+ /* We don't know in advance how many matching elements there
+ * are in the list, so we push this object that will represent
+ * the multi-bulk length in the output buffer, and will "fix"
+ * it later */
+ lenobj = createObject(REDIS_STRING,NULL);
+ addReply(c,lenobj);
+
+ while(ln && ln->score <= max) {
+ ele = ln->obj;
+ addReplyBulkLen(c,ele);
+ addReply(c,ele);
+ addReply(c,shared.crlf);
+ ln = ln->forward[0];
+ rangelen++;
+ }
+ lenobj->ptr = sdscatprintf(sdsempty(),"*%d\r\n",rangelen);
+ }
+ }
+}
+
+static void zcardCommand(redisClient *c) {
+ robj *o;
+ zset *zs;
+
+ o = lookupKeyRead(c->db,c->argv[1]);
+ if (o == NULL) {
+ addReply(c,shared.czero);
+ return;
+ } else {
+ if (o->type != REDIS_ZSET) {
+ addReply(c,shared.wrongtypeerr);
+ } else {
+ zs = o->ptr;
+ addReplySds(c,sdscatprintf(sdsempty(),":%d\r\n",zs->zsl->length));
+ }
+ }
+}
+
+static void zscoreCommand(redisClient *c) {
+ robj *o;
+ zset *zs;
+
+ o = lookupKeyRead(c->db,c->argv[1]);
+ if (o == NULL) {
+ addReply(c,shared.czero);
+ return;
+ } else {
+ if (o->type != REDIS_ZSET) {
+ addReply(c,shared.wrongtypeerr);
+ } else {
+ dictEntry *de;
+
+ zs = o->ptr;
+ de = dictFind(zs->dict,c->argv[2]);
+ if (!de) {
+ addReply(c,shared.nullbulk);
+ } else {
+ char buf[128];
+ double *score = dictGetEntryVal(de);
+
+ snprintf(buf,sizeof(buf),"%.17g",*score);
+ addReplySds(c,sdscatprintf(sdsempty(),"$%d\r\n%s\r\n",
+ strlen(buf),buf));
+ }
+ }
+ }
+}
+
+/* ========================= Non type-specific commands ==================== */
+
projects / redis.git / blobdiff