X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/3fbf9001ce88f2b3d154b099bcf2fd3783f24940..1cd92e7f040702e07e4930e8faa3f0f692658cdc:/redis.c diff --git a/redis.c b/redis.c index 2a488283..33750b93 100644 --- a/redis.c +++ b/redis.c @@ -2984,9 +2984,17 @@ static robj *dupStringObject(robj *o) { 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) { @@ -3544,38 +3552,32 @@ static int rdbSaveRawString(FILE *fp, unsigned char *s, size_t len) { 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 @@ -3628,16 +3630,37 @@ static int rdbSaveObject(FILE *fp, robj *o) { 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 */ @@ -4004,34 +4027,48 @@ static int rdbLoadDoubleValue(FILE *fp, double *val) { /* 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 */ @@ -4794,19 +4831,20 @@ static robj *lPop(robj *subject, int where) { 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; @@ -4840,15 +4878,24 @@ static unsigned long lLength(robj *subject) { 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) { @@ -4864,35 +4911,54 @@ static void lReleaseIterator(lIterator *li) { 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"); @@ -4900,50 +4966,39 @@ static robj *lGet(lIterator *li) { 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"); } @@ -4956,8 +5011,7 @@ static void pushGenericCommand(redisClient *c, int where) { 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 { @@ -4997,15 +5051,15 @@ static void lindexCommand(redisClient *c) { 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); @@ -5037,7 +5091,7 @@ static void lsetCommand(redisClient *c) { 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); @@ -5089,6 +5143,7 @@ static void lrangeCommand(redisClient *c) { 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; @@ -5111,12 +5166,12 @@ static void lrangeCommand(redisClient *c) { /* 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); } @@ -5177,7 +5232,7 @@ static void lremCommand(redisClient *c) { 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; @@ -5189,21 +5244,17 @@ static void lremCommand(redisClient *c) { 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); @@ -5232,47 +5283,37 @@ static void lremCommand(redisClient *c) { * 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++; } }