static robj *createListObject(void) {
list *l = listCreate();
-
+ robj *o = createObject(REDIS_LIST,l);
listSetFreeMethod(l,decrRefCount);
- return createObject(REDIS_LIST,l);
+ o->encoding = REDIS_ENCODING_LIST;
+ return o;
+}
+
+static robj *createZiplistObject(void) {
+ unsigned char *zl = ziplistNew();
+ robj *o = createObject(REDIS_LIST,zl);
+ o->encoding = REDIS_ENCODING_ZIPLIST;
+ return o;
}
static robj *createSetObject(void) {
return 0;
}
+/* Save a long long value as either an encoded string or a string. */
+static int rdbSaveLongLongAsStringObject(FILE *fp, long long value) {
+ unsigned char buf[32];
+ int enclen = rdbEncodeInteger(value,buf);
+ if (enclen > 0) {
+ if (fwrite(buf,enclen,1,fp) == 0) return -1;
+ } else {
+ /* Encode as string */
+ enclen = ll2string((char*)buf,32,value);
+ redisAssert(enclen < 32);
+ if (rdbSaveLen(fp,enclen) == -1) return -1;
+ if (fwrite(buf,enclen,1,fp) == 0) return -1;
+ }
+ return 0;
+}
+
/* Like rdbSaveStringObjectRaw() but handle encoded objects */
static int rdbSaveStringObject(FILE *fp, robj *obj) {
- int retval;
-
/* Avoid to decode the object, then encode it again, if the
* object is alrady integer encoded. */
if (obj->encoding == REDIS_ENCODING_INT) {
- long val = (long) obj->ptr;
- unsigned char buf[5];
- int enclen;
-
- if ((enclen = rdbEncodeInteger(val,buf)) > 0) {
- if (fwrite(buf,enclen,1,fp) == 0) return -1;
- return 0;
- }
- /* otherwise... fall throught and continue with the usual
- * code path. */
- }
-
- /* Avoid incr/decr ref count business when possible.
- * This plays well with copy-on-write given that we are probably
- * in a child process (BGSAVE). Also this makes sure key objects
- * of swapped objects are not incRefCount-ed (an assert does not allow
- * this in order to avoid bugs) */
- if (obj->encoding != REDIS_ENCODING_RAW) {
- obj = getDecodedObject(obj);
- retval = rdbSaveRawString(fp,obj->ptr,sdslen(obj->ptr));
- decrRefCount(obj);
+ return rdbSaveLongLongAsStringObject(fp,(long)obj->ptr);
} else {
- retval = rdbSaveRawString(fp,obj->ptr,sdslen(obj->ptr));
+ redisAssert(obj->encoding == REDIS_ENCODING_RAW);
+ return rdbSaveRawString(fp,obj->ptr,sdslen(obj->ptr));
}
- return retval;
}
/* Save a double value. Doubles are saved as strings prefixed by an unsigned
if (rdbSaveStringObject(fp,o) == -1) return -1;
} else if (o->type == REDIS_LIST) {
/* Save a list value */
- list *list = o->ptr;
- listIter li;
- listNode *ln;
-
- if (rdbSaveLen(fp,listLength(list)) == -1) return -1;
- listRewind(list,&li);
- while((ln = listNext(&li))) {
- robj *eleobj = listNodeValue(ln);
+ if (o->encoding == REDIS_ENCODING_ZIPLIST) {
+ unsigned char *p;
+ unsigned char *vstr;
+ unsigned int vlen;
+ long long vlong;
+
+ if (rdbSaveLen(fp,ziplistLen(o->ptr)) == -1) return -1;
+ p = ziplistIndex(o->ptr,0);
+ while(ziplistGet(p,&vstr,&vlen,&vlong)) {
+ if (vstr) {
+ if (rdbSaveRawString(fp,vstr,vlen) == -1)
+ return -1;
+ } else {
+ if (rdbSaveLongLongAsStringObject(fp,vlong) == -1)
+ return -1;
+ }
+ p = ziplistNext(o->ptr,p);
+ }
+ } else if (o->encoding == REDIS_ENCODING_LIST) {
+ list *list = o->ptr;
+ listIter li;
+ listNode *ln;
- if (rdbSaveStringObject(fp,eleobj) == -1) return -1;
+ if (rdbSaveLen(fp,listLength(list)) == -1) return -1;
+ listRewind(list,&li);
+ while((ln = listNext(&li))) {
+ robj *eleobj = listNodeValue(ln);
+ if (rdbSaveStringObject(fp,eleobj) == -1) return -1;
+ }
+ } else {
+ redisPanic("Unknown list encoding");
}
} else if (o->type == REDIS_SET) {
/* Save a set value */
/* Load a Redis object of the specified type from the specified file.
* On success a newly allocated object is returned, otherwise NULL. */
static robj *rdbLoadObject(int type, FILE *fp) {
- robj *o;
+ robj *o, *ele, *dec;
+ size_t len;
redisLog(REDIS_DEBUG,"LOADING OBJECT %d (at %d)\n",type,ftell(fp));
if (type == REDIS_STRING) {
/* Read string value */
if ((o = rdbLoadEncodedStringObject(fp)) == NULL) return NULL;
o = tryObjectEncoding(o);
- } else if (type == REDIS_LIST || type == REDIS_SET) {
- /* Read list/set value */
- uint32_t listlen;
+ } else if (type == REDIS_LIST) {
+ /* Read list value */
+ if ((len = rdbLoadLen(fp,NULL)) == REDIS_RDB_LENERR) return NULL;
- if ((listlen = rdbLoadLen(fp,NULL)) == REDIS_RDB_LENERR) return NULL;
- o = (type == REDIS_LIST) ? createListObject() : createSetObject();
+ o = createZiplistObject();
+
+ /* Load every single element of the list */
+ while(len--) {
+ if ((ele = rdbLoadEncodedStringObject(fp)) == NULL) return NULL;
+
+ if (o->encoding == REDIS_ENCODING_ZIPLIST) {
+ dec = getDecodedObject(ele);
+ o->ptr = ziplistPush(o->ptr,dec->ptr,sdslen(dec->ptr),REDIS_TAIL);
+ decrRefCount(dec);
+ decrRefCount(ele);
+ } else {
+ ele = tryObjectEncoding(ele);
+ listAddNodeTail(o->ptr,ele);
+ incrRefCount(ele);
+ }
+ }
+ } else if (type == REDIS_SET) {
+ /* Read list/set value */
+ if ((len = rdbLoadLen(fp,NULL)) == REDIS_RDB_LENERR) return NULL;
+ o = createSetObject();
/* It's faster to expand the dict to the right size asap in order
* to avoid rehashing */
- if (type == REDIS_SET && listlen > DICT_HT_INITIAL_SIZE)
- dictExpand(o->ptr,listlen);
+ if (len > DICT_HT_INITIAL_SIZE)
+ dictExpand(o->ptr,len);
/* Load every single element of the list/set */
- while(listlen--) {
- robj *ele;
-
+ while(len--) {
if ((ele = rdbLoadEncodedStringObject(fp)) == NULL) return NULL;
ele = tryObjectEncoding(ele);
- if (type == REDIS_LIST) {
- listAddNodeTail((list*)o->ptr,ele);
- } else {
- dictAdd((dict*)o->ptr,ele,NULL);
- }
+ dictAdd((dict*)o->ptr,ele,NULL);
}
} else if (type == REDIS_ZSET) {
/* Read list/set value */
robj *value = NULL;
if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
unsigned char *p;
- char *v;
+ unsigned char *vstr;
unsigned int vlen;
- long long vval;
+ long long vlong;
int pos = (where == REDIS_HEAD) ? 0 : -1;
p = ziplistIndex(subject->ptr,pos);
- if (ziplistGet(p,&v,&vlen,&vval)) {
- if (v) {
- value = createStringObject(v,vlen);
+ if (ziplistGet(p,&vstr,&vlen,&vlong)) {
+ if (vstr) {
+ value = createStringObject((char*)vstr,vlen);
} else {
- value = createStringObjectFromLongLong(vval);
+ value = createStringObjectFromLongLong(vlong);
}
+ /* We only need to delete an element when it exists */
+ subject->ptr = ziplistDelete(subject->ptr,&p);
}
- subject->ptr = ziplistDelete(subject->ptr,&p,ZIPLIST_TAIL);
} else if (subject->encoding == REDIS_ENCODING_LIST) {
list *list = subject->ptr;
listNode *ln;
typedef struct {
robj *subject;
unsigned char encoding;
+ unsigned char direction; /* Iteration direction */
unsigned char *zi;
listNode *ln;
} lIterator;
+/* Structure for an entry while iterating over a list. */
+typedef struct {
+ lIterator *li;
+ unsigned char *zi; /* Entry in ziplist */
+ listNode *ln; /* Entry in linked list */
+} lEntry;
+
/* Initialize an iterator at the specified index. */
-static lIterator *lInitIterator(robj *subject, int index) {
+static lIterator *lInitIterator(robj *subject, int index, unsigned char direction) {
lIterator *li = zmalloc(sizeof(lIterator));
li->subject = subject;
li->encoding = subject->encoding;
+ li->direction = direction;
if (li->encoding == REDIS_ENCODING_ZIPLIST) {
li->zi = ziplistIndex(subject->ptr,index);
} else if (li->encoding == REDIS_ENCODING_LIST) {
zfree(li);
}
-/* Whether the entry pointed at is a valid entry. */
-static int lIsEntry(lIterator *li) {
+/* Stores pointer to current the entry in the provided entry structure
+ * and advances the position of the iterator. Returns 1 when the current
+ * entry is in fact an entry, 0 otherwise. */
+static int lNext(lIterator *li, lEntry *entry) {
+ entry->li = li;
if (li->encoding == REDIS_ENCODING_ZIPLIST) {
- return li->zi != NULL;
+ entry->zi = li->zi;
+ if (entry->zi != NULL) {
+ if (li->direction == REDIS_TAIL)
+ li->zi = ziplistNext(li->subject->ptr,li->zi);
+ else
+ li->zi = ziplistPrev(li->subject->ptr,li->zi);
+ return 1;
+ }
} else if (li->encoding == REDIS_ENCODING_LIST) {
- return li->ln != NULL;
+ entry->ln = li->ln;
+ if (entry->ln != NULL) {
+ if (li->direction == REDIS_TAIL)
+ li->ln = li->ln->next;
+ else
+ li->ln = li->ln->prev;
+ return 1;
+ }
} else {
redisPanic("Unknown list encoding");
}
+ return 0;
}
/* Return entry or NULL at the current position of the iterator. */
-static robj *lGet(lIterator *li) {
+static robj *lGet(lEntry *entry) {
+ lIterator *li = entry->li;
robj *value = NULL;
if (li->encoding == REDIS_ENCODING_ZIPLIST) {
- char *v;
+ unsigned char *vstr;
unsigned int vlen;
- long long vval;
- redisAssert(li->zi != NULL);
- if (ziplistGet(li->zi,&v,&vlen,&vval)) {
- if (v) {
- value = createStringObject(v,vlen);
+ long long vlong;
+ redisAssert(entry->zi != NULL);
+ if (ziplistGet(entry->zi,&vstr,&vlen,&vlong)) {
+ if (vstr) {
+ value = createStringObject((char*)vstr,vlen);
} else {
- value = createStringObjectFromLongLong(vval);
+ value = createStringObjectFromLongLong(vlong);
}
}
} else if (li->encoding == REDIS_ENCODING_LIST) {
- redisAssert(li->ln != NULL);
- value = listNodeValue(li->ln);
+ redisAssert(entry->ln != NULL);
+ value = listNodeValue(entry->ln);
incrRefCount(value);
} else {
redisPanic("Unknown list encoding");
return value;
}
-/* Delete the element pointed to. */
-static void lDelete(lIterator *li, int direction) {
- if (li->encoding == REDIS_ENCODING_ZIPLIST) {
- direction = (direction == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
- li->subject->ptr = ziplistDelete(li->subject->ptr,&li->zi,direction);
- } else if (li->encoding == REDIS_ENCODING_LIST) {
- listNode *next;
- if (direction == REDIS_HEAD)
- next = li->ln->prev;
- else
- next = li->ln->next;
- listDelNode(li->subject->ptr,li->ln);
- li->ln = next;
- } else {
- redisPanic("Unknown list encoding");
- }
-}
-
/* Compare the given object with the entry at the current position. */
-static int lEqualTo(lIterator *li, robj *o) {
+static int lEqual(lEntry *entry, robj *o) {
+ lIterator *li = entry->li;
if (li->encoding == REDIS_ENCODING_ZIPLIST) {
redisAssert(o->encoding == REDIS_ENCODING_RAW);
- return ziplistCompare(li->zi,o->ptr,sdslen(o->ptr));
+ return ziplistCompare(entry->zi,o->ptr,sdslen(o->ptr));
} else if (li->encoding == REDIS_ENCODING_LIST) {
- return equalStringObjects(o,listNodeValue(li->ln));
+ return equalStringObjects(o,listNodeValue(entry->ln));
} else {
redisPanic("Unknown list encoding");
}
}
-/* Move to the next or previous entry in the list. */
-static void lMove(lIterator *li, int where) {
+/* Delete the element pointed to. */
+static void lDelete(lEntry *entry) {
+ lIterator *li = entry->li;
if (li->encoding == REDIS_ENCODING_ZIPLIST) {
- redisAssert(li->zi != NULL);
- if (where == REDIS_HEAD)
- li->zi = ziplistPrev(li->zi);
+ unsigned char *p = entry->zi;
+ li->subject->ptr = ziplistDelete(li->subject->ptr,&p);
+
+ /* Update position of the iterator depending on the direction */
+ if (li->direction == REDIS_TAIL)
+ li->zi = p;
else
- li->zi = ziplistNext(li->zi);
- } else if (li->encoding == REDIS_ENCODING_LIST) {
- redisAssert(li->ln != NULL);
- if (where == REDIS_HEAD)
- li->ln = li->ln->prev;
+ li->zi = ziplistPrev(li->subject->ptr,p);
+ } else if (entry->li->encoding == REDIS_ENCODING_LIST) {
+ listNode *next;
+ if (li->direction == REDIS_TAIL)
+ next = entry->ln->next;
else
- li->ln = li->ln->next;
+ next = entry->ln->prev;
+ listDelNode(li->subject->ptr,entry->ln);
+ li->ln = next;
} else {
redisPanic("Unknown list encoding");
}
addReply(c,shared.cone);
return;
}
- lobj = createObject(REDIS_LIST,ziplistNew());
- lobj->encoding = REDIS_ENCODING_ZIPLIST;
+ lobj = createZiplistObject();
dictAdd(c->db->dict,c->argv[1],lobj);
incrRefCount(c->argv[1]);
} else {
if (o->encoding == REDIS_ENCODING_ZIPLIST) {
unsigned char *p;
- char *v;
+ unsigned char *vstr;
unsigned int vlen;
- long long vval;
+ long long vlong;
p = ziplistIndex(o->ptr,index);
- if (ziplistGet(p,&v,&vlen,&vval)) {
- if (v) {
- value = createStringObject(v,vlen);
+ if (ziplistGet(p,&vstr,&vlen,&vlong)) {
+ if (vstr) {
+ value = createStringObject((char*)vstr,vlen);
} else {
- value = createStringObjectFromLongLong(vval);
+ value = createStringObjectFromLongLong(vlong);
}
addReplyBulk(c,value);
decrRefCount(value);
if (p == NULL) {
addReply(c,shared.outofrangeerr);
} else {
- o->ptr = ziplistDelete(o->ptr,&p,ZIPLIST_TAIL);
+ o->ptr = ziplistDelete(o->ptr,&p);
value = getDecodedObject(value);
o->ptr = ziplistInsert(o->ptr,p,value->ptr,sdslen(value->ptr));
decrRefCount(value);
int end = atoi(c->argv[3]->ptr);
int llen;
int rangelen, j;
+ lEntry entry;
if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptymultibulk)) == NULL
|| checkType(c,o,REDIS_LIST)) return;
/* Return the result in form of a multi-bulk reply */
addReplySds(c,sdscatprintf(sdsempty(),"*%d\r\n",rangelen));
- lIterator *li = lInitIterator(o,start);
+ lIterator *li = lInitIterator(o,start,REDIS_TAIL);
for (j = 0; j < rangelen; j++) {
- value = lGet(li);
- redisAssert(value != NULL);
+ redisAssert(lNext(li,&entry));
+ value = lGet(&entry);
addReplyBulk(c,value);
- lMove(li,REDIS_TAIL);
+ decrRefCount(value);
}
lReleaseIterator(li);
}
robj *subject, *obj = c->argv[3];
int toremove = atoi(c->argv[2]->ptr);
int removed = 0;
- int direction;
+ lEntry entry;
subject = lookupKeyWriteOrReply(c,c->argv[1],shared.czero);
if (subject == NULL || checkType(c,subject,REDIS_LIST)) return;
lIterator *li;
if (toremove < 0) {
toremove = -toremove;
- direction = REDIS_HEAD;
- li = lInitIterator(subject,-1);
+ li = lInitIterator(subject,-1,REDIS_HEAD);
} else {
- direction = REDIS_TAIL;
- li = lInitIterator(subject,0);
+ li = lInitIterator(subject,0,REDIS_TAIL);
}
- while (lIsEntry(li)) {
- if (lEqualTo(li,obj)) {
- lDelete(li,direction);
+ while (lNext(li,&entry)) {
+ if (lEqual(&entry,obj)) {
+ lDelete(&entry);
server.dirty++;
removed++;
if (toremove && removed == toremove) break;
- } else {
- lMove(li,direction);
}
}
lReleaseIterator(li);
* as well. This command was originally proposed by Ezra Zygmuntowicz.
*/
static void rpoplpushcommand(redisClient *c) {
- robj *sobj;
- list *srclist;
- listNode *ln;
-
+ robj *sobj, *value;
if ((sobj = lookupKeyWriteOrReply(c,c->argv[1],shared.nullbulk)) == NULL ||
checkType(c,sobj,REDIS_LIST)) return;
- srclist = sobj->ptr;
- ln = listLast(srclist);
- if (ln == NULL) {
+ if (lLength(sobj) == 0) {
addReply(c,shared.nullbulk);
} else {
robj *dobj = lookupKeyWrite(c->db,c->argv[2]);
- robj *ele = listNodeValue(ln);
- list *dstlist;
-
- if (dobj && dobj->type != REDIS_LIST) {
- addReply(c,shared.wrongtypeerr);
- return;
- }
+ if (dobj && checkType(c,dobj,REDIS_LIST)) return;
+ value = lPop(sobj,REDIS_TAIL);
/* Add the element to the target list (unless it's directly
* passed to some BLPOP-ing client */
- if (!handleClientsWaitingListPush(c,c->argv[2],ele)) {
- if (dobj == NULL) {
- /* Create the list if the key does not exist */
- dobj = createListObject();
+ if (!handleClientsWaitingListPush(c,c->argv[2],value)) {
+ /* Create the list if the key does not exist */
+ if (!dobj) {
+ dobj = createZiplistObject();
dictAdd(c->db->dict,c->argv[2],dobj);
incrRefCount(c->argv[2]);
}
- dstlist = dobj->ptr;
- listAddNodeHead(dstlist,ele);
- incrRefCount(ele);
+ lPush(dobj,value,REDIS_HEAD);
}
/* Send the element to the client as reply as well */
- addReplyBulk(c,ele);
+ addReplyBulk(c,value);
+
+ /* lPop returns an object with its refcount incremented */
+ decrRefCount(value);
- /* Finally remove the element from the source list */
- listDelNode(srclist,ln);
- if (listLength(srclist) == 0) deleteKey(c->db,c->argv[1]);
+ /* Delete the source list when it is empty */
+ if (lLength(sobj) == 0) deleteKey(c->db,c->argv[1]);
server.dirty++;
}
}
projects / redis.git / blobdiff