+/* Populate the rangespec according to the objects min and max. */
+static int zslParseRange(robj *min, robj *max, zrangespec *spec) {
+ char *eptr;
+ spec->minex = spec->maxex = 0;
+
+ /* Parse the min-max interval. If one of the values is prefixed
+ * by the "(" character, it's considered "open". For instance
+ * ZRANGEBYSCORE zset (1.5 (2.5 will match min < x < max
+ * ZRANGEBYSCORE zset 1.5 2.5 will instead match min <= x <= max */
+ if (min->encoding == REDIS_ENCODING_INT) {
+ spec->min = (long)min->ptr;
+ } else {
+ if (((char*)min->ptr)[0] == '(') {
+ spec->min = strtod((char*)min->ptr+1,&eptr);
+ if (eptr[0] != '\0' || isnan(spec->min)) return REDIS_ERR;
+ spec->minex = 1;
+ } else {
+ spec->min = strtod((char*)min->ptr,&eptr);
+ if (eptr[0] != '\0' || isnan(spec->min)) return REDIS_ERR;
+ }
+ }
+ if (max->encoding == REDIS_ENCODING_INT) {
+ spec->max = (long)max->ptr;
+ } else {
+ if (((char*)max->ptr)[0] == '(') {
+ spec->max = strtod((char*)max->ptr+1,&eptr);
+ if (eptr[0] != '\0' || isnan(spec->max)) return REDIS_ERR;
+ spec->maxex = 1;
+ } else {
+ spec->max = strtod((char*)max->ptr,&eptr);
+ if (eptr[0] != '\0' || isnan(spec->max)) return REDIS_ERR;
+ }
+ }
+
+ return REDIS_OK;
+}
+
+/*-----------------------------------------------------------------------------
+ * Ziplist-backed sorted set API
+ *----------------------------------------------------------------------------*/
+
+double zzlGetScore(unsigned char *sptr) {
+ unsigned char *vstr;
+ unsigned int vlen;
+ long long vlong;
+ char buf[128];
+ double score;
+
+ redisAssert(sptr != NULL);
+ redisAssert(ziplistGet(sptr,&vstr,&vlen,&vlong));
+
+ if (vstr) {
+ memcpy(buf,vstr,vlen);
+ buf[vlen] = '\0';
+ score = strtod(buf,NULL);
+ } else {
+ score = vlong;
+ }
+
+ return score;
+}
+
+/* Compare element in sorted set with given element. */
+int zzlCompareElements(unsigned char *eptr, unsigned char *cstr, unsigned int clen) {
+ unsigned char *vstr;
+ unsigned int vlen;
+ long long vlong;
+ unsigned char vbuf[32];
+ int minlen, cmp;
+
+ redisAssert(ziplistGet(eptr,&vstr,&vlen,&vlong));
+ if (vstr == NULL) {
+ /* Store string representation of long long in buf. */
+ vlen = ll2string((char*)vbuf,sizeof(vbuf),vlong);
+ vstr = vbuf;
+ }
+
+ minlen = (vlen < clen) ? vlen : clen;
+ cmp = memcmp(vstr,cstr,minlen);
+ if (cmp == 0) return vlen-clen;
+ return cmp;
+}
+
+unsigned int zzlLength(unsigned char *zl) {
+ return ziplistLen(zl)/2;
+}
+
+/* Move to next entry based on the values in eptr and sptr. Both are set to
+ * NULL when there is no next entry. */
+void zzlNext(unsigned char *zl, unsigned char **eptr, unsigned char **sptr) {
+ unsigned char *_eptr, *_sptr;
+ redisAssert(*eptr != NULL && *sptr != NULL);
+
+ _eptr = ziplistNext(zl,*sptr);
+ if (_eptr != NULL) {
+ _sptr = ziplistNext(zl,_eptr);
+ redisAssert(_sptr != NULL);
+ } else {
+ /* No next entry. */
+ _sptr = NULL;
+ }
+
+ *eptr = _eptr;
+ *sptr = _sptr;
+}
+
+/* Move to the previous entry based on the values in eptr and sptr. Both are
+ * set to NULL when there is no next entry. */
+void zzlPrev(unsigned char *zl, unsigned char **eptr, unsigned char **sptr) {
+ unsigned char *_eptr, *_sptr;
+ redisAssert(*eptr != NULL && *sptr != NULL);
+
+ _sptr = ziplistPrev(zl,*eptr);
+ if (_sptr != NULL) {
+ _eptr = ziplistPrev(zl,_sptr);
+ redisAssert(_eptr != NULL);
+ } else {
+ /* No previous entry. */
+ _eptr = NULL;
+ }
+
+ *eptr = _eptr;
+ *sptr = _sptr;
+}
+
+/* Returns if there is a part of the zset is in range. Should only be used
+ * internally by zzlFirstInRange and zzlLastInRange. */
+int zzlIsInRange(unsigned char *zl, zrangespec *range) {
+ unsigned char *p;
+ double score;
+
+ /* Test for ranges that will always be empty. */
+ if (range->min > range->max ||
+ (range->min == range->max && (range->minex || range->maxex)))
+ return 0;
+
+ p = ziplistIndex(zl,-1); /* Last score. */
+ redisAssert(p != NULL);
+ score = zzlGetScore(p);
+ if (!zslValueGteMin(score,range))
+ return 0;
+
+ p = ziplistIndex(zl,1); /* First score. */
+ redisAssert(p != NULL);
+ score = zzlGetScore(p);
+ if (!zslValueLteMax(score,range))
+ return 0;
+
+ return 1;
+}
+
+/* Find pointer to the first element contained in the specified range.
+ * Returns NULL when no element is contained in the range. */
+unsigned char *zzlFirstInRange(robj *zobj, zrangespec range) {
+ unsigned char *zl = zobj->ptr;
+ unsigned char *eptr = ziplistIndex(zl,0), *sptr;
+ double score;
+
+ /* If everything is out of range, return early. */
+ if (!zzlIsInRange(zl,&range)) return NULL;
+
+ while (eptr != NULL) {
+ sptr = ziplistNext(zl,eptr);
+ redisAssert(sptr != NULL);
+
+ score = zzlGetScore(sptr);
+ if (zslValueGteMin(score,&range))
+ return eptr;
+
+ /* Move to next element. */
+ eptr = ziplistNext(zl,sptr);
+ }
+
+ return NULL;
+}
+
+/* Find pointer to the last element contained in the specified range.
+ * Returns NULL when no element is contained in the range. */
+unsigned char *zzlLastInRange(robj *zobj, zrangespec range) {
+ unsigned char *zl = zobj->ptr;
+ unsigned char *eptr = ziplistIndex(zl,-2), *sptr;
+ double score;
+
+ /* If everything is out of range, return early. */
+ if (!zzlIsInRange(zl,&range)) return NULL;
+
+ while (eptr != NULL) {
+ sptr = ziplistNext(zl,eptr);
+ redisAssert(sptr != NULL);
+
+ score = zzlGetScore(sptr);
+ if (zslValueLteMax(score,&range))
+ return eptr;
+
+ /* Move to previous element by moving to the score of previous element.
+ * When this returns NULL, we know there also is no element. */
+ sptr = ziplistPrev(zl,eptr);
+ if (sptr != NULL)
+ redisAssert((eptr = ziplistPrev(zl,sptr)) != NULL);
+ else
+ eptr = NULL;
+ }
+
+ return NULL;
+}
+
+unsigned char *zzlFind(robj *zobj, robj *ele, double *score) {
+ unsigned char *zl = zobj->ptr;
+ unsigned char *eptr = ziplistIndex(zl,0), *sptr;
+
+ ele = getDecodedObject(ele);
+ while (eptr != NULL) {
+ sptr = ziplistNext(zl,eptr);
+ redisAssert(sptr != NULL);
+
+ if (ziplistCompare(eptr,ele->ptr,sdslen(ele->ptr))) {
+ /* Matching element, pull out score. */
+ if (score != NULL) *score = zzlGetScore(sptr);
+ decrRefCount(ele);
+ return eptr;
+ }
+
+ /* Move to next element. */
+ eptr = ziplistNext(zl,sptr);
+ }
+
+ decrRefCount(ele);
+ return NULL;
+}
+
+/* Delete (element,score) pair from ziplist. Use local copy of eptr because we
+ * don't want to modify the one given as argument. */
+int zzlDelete(robj *zobj, unsigned char *eptr) {
+ unsigned char *zl = zobj->ptr;
+ unsigned char *p = eptr;
+
+ /* TODO: add function to ziplist API to delete N elements from offset. */
+ zl = ziplistDelete(zl,&p);
+ zl = ziplistDelete(zl,&p);
+ zobj->ptr = zl;
+ return REDIS_OK;
+}
+
+int zzlInsertAt(robj *zobj, robj *ele, double score, unsigned char *eptr) {
+ unsigned char *zl = zobj->ptr;
+ unsigned char *sptr;
+ char scorebuf[128];
+ int scorelen;
+ int offset;
+
+ redisAssert(ele->encoding == REDIS_ENCODING_RAW);
+ scorelen = d2string(scorebuf,sizeof(scorebuf),score);
+ if (eptr == NULL) {
+ zl = ziplistPush(zl,ele->ptr,sdslen(ele->ptr),ZIPLIST_TAIL);
+ zl = ziplistPush(zl,(unsigned char*)scorebuf,scorelen,ZIPLIST_TAIL);
+ } else {
+ /* Keep offset relative to zl, as it might be re-allocated. */
+ offset = eptr-zl;
+ zl = ziplistInsert(zl,eptr,ele->ptr,sdslen(ele->ptr));
+ eptr = zl+offset;
+
+ /* Insert score after the element. */
+ redisAssert((sptr = ziplistNext(zl,eptr)) != NULL);
+ zl = ziplistInsert(zl,sptr,(unsigned char*)scorebuf,scorelen);
+ }
+
+ zobj->ptr = zl;
+ return REDIS_OK;
+}
+
+/* Insert (element,score) pair in ziplist. This function assumes the element is
+ * not yet present in the list. */
+int zzlInsert(robj *zobj, robj *ele, double score) {
+ unsigned char *zl = zobj->ptr;
+ unsigned char *eptr = ziplistIndex(zl,0), *sptr;
+ double s;
+
+ ele = getDecodedObject(ele);
+ while (eptr != NULL) {
+ sptr = ziplistNext(zl,eptr);
+ redisAssert(sptr != NULL);
+ s = zzlGetScore(sptr);
+
+ if (s > score) {
+ /* First element with score larger than score for element to be
+ * inserted. This means we should take its spot in the list to
+ * maintain ordering. */
+ zzlInsertAt(zobj,ele,score,eptr);
+ break;
+ } else if (s == score) {
+ /* Ensure lexicographical ordering for elements. */
+ if (zzlCompareElements(eptr,ele->ptr,sdslen(ele->ptr)) > 0) {
+ zzlInsertAt(zobj,ele,score,eptr);
+ break;
+ }
+ }
+
+ /* Move to next element. */
+ eptr = ziplistNext(zl,sptr);
+ }
+
+ /* Push on tail of list when it was not yet inserted. */
+ if (eptr == NULL)
+ zzlInsertAt(zobj,ele,score,NULL);
+
+ decrRefCount(ele);
+ return REDIS_OK;
+}
+
+unsigned long zzlDeleteRangeByScore(robj *zobj, zrangespec range) {
+ unsigned char *zl = zobj->ptr;
+ unsigned char *eptr, *sptr;
+ double score;
+ unsigned long deleted = 0;
+
+ eptr = zzlFirstInRange(zobj,range);
+ if (eptr == NULL) return deleted;
+
+
+ /* When the tail of the ziplist is deleted, eptr will point to the sentinel
+ * byte and ziplistNext will return NULL. */
+ while ((sptr = ziplistNext(zl,eptr)) != NULL) {
+ score = zzlGetScore(sptr);
+ if (zslValueLteMax(score,&range)) {
+ /* Delete both the element and the score. */
+ zl = ziplistDelete(zl,&eptr);
+ zl = ziplistDelete(zl,&eptr);
+ deleted++;
+ } else {
+ /* No longer in range. */
+ break;
+ }
+ }
+
+ return deleted;
+}
+
+/* Delete all the elements with rank between start and end from the skiplist.
+ * Start and end are inclusive. Note that start and end need to be 1-based */
+unsigned long zzlDeleteRangeByRank(robj *zobj, unsigned int start, unsigned int end) {
+ unsigned int num = (end-start)+1;
+ zobj->ptr = ziplistDeleteRange(zobj->ptr,2*(start-1),2*num);
+ return num;
+}
+
+/*-----------------------------------------------------------------------------
+ * Common sorted set API
+ *----------------------------------------------------------------------------*/
+
+int zsLength(robj *zobj) {
+ int length = -1;
+ if (zobj->encoding == REDIS_ENCODING_ZIPLIST) {
+ length = zzlLength(zobj->ptr);
+ } else if (zobj->encoding == REDIS_ENCODING_RAW) {
+ length = ((zset*)zobj->ptr)->zsl->length;
+ } else {
+ redisPanic("Unknown sorted set encoding");
+ }
+ return length;
+}
+
+void zsConvert(robj *zobj, int encoding) {
+ zset *zs;
+ zskiplistNode *node, *next;
+ robj *ele;
+ double score;
+
+ if (zobj->encoding == encoding) return;
+ if (zobj->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *zl = zobj->ptr;
+ unsigned char *eptr, *sptr;
+ unsigned char *vstr;
+ unsigned int vlen;
+ long long vlong;
+
+ if (encoding != REDIS_ENCODING_RAW)
+ redisPanic("Unknown target encoding");
+
+ zs = zmalloc(sizeof(*zs));
+ zs->dict = dictCreate(&zsetDictType,NULL);
+ zs->zsl = zslCreate();
+
+ eptr = ziplistIndex(zl,0);
+ redisAssert(eptr != NULL);
+ sptr = ziplistNext(zl,eptr);
+ redisAssert(sptr != NULL);
+
+ while (eptr != NULL) {
+ score = zzlGetScore(sptr);
+ redisAssert(ziplistGet(eptr,&vstr,&vlen,&vlong));
+ if (vstr == NULL)
+ ele = createStringObjectFromLongLong(vlong);
+ else
+ ele = createStringObject((char*)vstr,vlen);
+
+ /* Has incremented refcount since it was just created. */
+ node = zslInsert(zs->zsl,score,ele);
+ redisAssert(dictAdd(zs->dict,ele,&node->score) == DICT_OK);
+ incrRefCount(ele); /* Added to dictionary. */
+ zzlNext(zl,&eptr,&sptr);
+ }
+
+ zfree(zobj->ptr);
+ zobj->ptr = zs;
+ zobj->encoding = REDIS_ENCODING_RAW;
+ } else if (zobj->encoding == REDIS_ENCODING_RAW) {
+ unsigned char *zl = ziplistNew();
+
+ if (encoding != REDIS_ENCODING_ZIPLIST)
+ redisPanic("Unknown target encoding");
+
+ /* Approach similar to zslFree(), since we want to free the skiplist at
+ * the same time as creating the ziplist. */
+ zs = zobj->ptr;
+ dictRelease(zs->dict);
+ node = zs->zsl->header->level[0].forward;
+ zfree(zs->zsl->header);
+ zfree(zs->zsl);
+
+ /* Immediately store pointer to ziplist in object because it will
+ * change because of reallocations when pushing to the ziplist. */
+ zobj->ptr = zl;
+
+ while (node) {
+ ele = getDecodedObject(node->obj);
+ redisAssert(zzlInsertAt(zobj,ele,node->score,NULL) == REDIS_OK);
+ decrRefCount(ele);
+
+ next = node->level[0].forward;
+ zslFreeNode(node);
+ node = next;
+ }
+
+ zfree(zs);
+ zobj->encoding = REDIS_ENCODING_ZIPLIST;
+ } else {
+ redisPanic("Unknown sorted set encoding");
+ }
+}
+
projects / redis.git / blobdiff