From: antirez Date: Fri, 11 Jun 2010 18:27:56 +0000 (+0200) Subject: Merge branch 'lists' of git://github.com/pietern/redis X-Git-Url: https://git.saurik.com/redis.git/commitdiff_plain/ac9b8cfe577d1a27dd0f377e3b9578a7505cf00f?hp=-c Merge branch 'lists' of git://github.com/pietern/redis --- ac9b8cfe577d1a27dd0f377e3b9578a7505cf00f diff --combined redis.c index 3e7a17d8,2b0e5d37..8ac16295 --- a/redis.c +++ b/redis.c @@@ -261,7 -261,7 +261,7 @@@ typedef struct redisObject unsigned lru:22; /* lru time (relative to server.lruclock) */ int refcount; void *ptr; - /* VM fields, this are only allocated if VM is active, otherwise the + /* VM fields are only allocated if VM is active, otherwise the * object allocation function will just allocate * sizeof(redisObjct) minus sizeof(redisObjectVM), so using * Redis without VM active will not have any overhead. */ @@@ -538,7 -538,7 +538,7 @@@ typedef struct zset #define REDIS_SHARED_INTEGERS 10000 struct sharedObjectsStruct { - robj *crlf, *ok, *err, *emptybulk, *czero, *cone, *pong, *space, + robj *crlf, *ok, *err, *emptybulk, *czero, *cone, *cnegone, *pong, *space, *colon, *nullbulk, *nullmultibulk, *queued, *emptymultibulk, *wrongtypeerr, *nokeyerr, *syntaxerr, *sameobjecterr, *outofrangeerr, *plus, @@@ -692,6 -692,9 +692,9 @@@ static void renameCommand(redisClient * static void renamenxCommand(redisClient *c); static void lpushCommand(redisClient *c); static void rpushCommand(redisClient *c); + static void lpushxCommand(redisClient *c); + static void rpushxCommand(redisClient *c); + static void linsertCommand(redisClient *c); static void lpopCommand(redisClient *c); static void rpopCommand(redisClient *c); static void llenCommand(redisClient *c); @@@ -792,6 -795,9 +795,9 @@@ static struct redisCommand readonlyComm {"mget",mgetCommand,-2,REDIS_CMD_INLINE,NULL,1,-1,1}, {"rpush",rpushCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,NULL,1,1,1}, {"lpush",lpushCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,NULL,1,1,1}, + {"rpushx",rpushxCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,NULL,1,1,1}, + {"lpushx",lpushxCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,NULL,1,1,1}, + {"linsert",linsertCommand,5,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,NULL,1,1,1}, {"rpop",rpopCommand,2,REDIS_CMD_INLINE,NULL,1,1,1}, {"lpop",lpopCommand,2,REDIS_CMD_INLINE,NULL,1,1,1}, {"brpop",brpopCommand,-3,REDIS_CMD_INLINE,NULL,1,1,1}, @@@ -1671,6 -1677,7 +1677,7 @@@ static void createSharedObjects(void) shared.emptybulk = createObject(REDIS_STRING,sdsnew("$0\r\n\r\n")); shared.czero = createObject(REDIS_STRING,sdsnew(":0\r\n")); shared.cone = createObject(REDIS_STRING,sdsnew(":1\r\n")); + shared.cnegone = createObject(REDIS_STRING,sdsnew(":-1\r\n")); shared.nullbulk = createObject(REDIS_STRING,sdsnew("$-1\r\n")); shared.nullmultibulk = createObject(REDIS_STRING,sdsnew("*-1\r\n")); shared.emptymultibulk = createObject(REDIS_STRING,sdsnew("*0\r\n")); @@@ -4240,8 -4247,8 +4247,8 @@@ static robj *rdbLoadObject(int type, FI while(hashlen--) { robj *key, *val; - if ((key = rdbLoadStringObject(fp)) == NULL) return NULL; - if ((val = rdbLoadStringObject(fp)) == NULL) return NULL; + if ((key = rdbLoadEncodedStringObject(fp)) == NULL) return NULL; + if ((val = rdbLoadEncodedStringObject(fp)) == NULL) return NULL; /* If we are using a zipmap and there are too big values * the object is converted to real hash table encoding. */ if (o->encoding != REDIS_ENCODING_HT && @@@ -4920,7 -4927,7 +4927,7 @@@ static void listTypePush(robj *subject /* Check if we need to convert the ziplist */ listTypeTryConversion(subject,value); if (subject->encoding == REDIS_ENCODING_ZIPLIST && - ziplistLen(subject->ptr) > server.list_max_ziplist_entries) + ziplistLen(subject->ptr) >= server.list_max_ziplist_entries) listTypeConvert(subject,REDIS_ENCODING_LIST); if (subject->encoding == REDIS_ENCODING_ZIPLIST) { @@@ -5082,6 -5089,36 +5089,36 @@@ static robj *listTypeGet(listTypeEntry return value; } + static void listTypeInsert(listTypeEntry *entry, robj *value, int where) { + robj *subject = entry->li->subject; + if (entry->li->encoding == REDIS_ENCODING_ZIPLIST) { + value = getDecodedObject(value); + if (where == REDIS_TAIL) { + unsigned char *next = ziplistNext(subject->ptr,entry->zi); + + /* When we insert after the current element, but the current element + * is the tail of the list, we need to do a push. */ + if (next == NULL) { + subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),REDIS_TAIL); + } else { + subject->ptr = ziplistInsert(subject->ptr,next,value->ptr,sdslen(value->ptr)); + } + } else { + subject->ptr = ziplistInsert(subject->ptr,entry->zi,value->ptr,sdslen(value->ptr)); + } + decrRefCount(value); + } else if (entry->li->encoding == REDIS_ENCODING_LIST) { + if (where == REDIS_TAIL) { + listInsertNode(subject->ptr,entry->ln,value,AL_START_TAIL); + } else { + listInsertNode(subject->ptr,entry->ln,value,AL_START_HEAD); + } + incrRefCount(value); + } else { + redisPanic("Unknown list encoding"); + } + } + /* Compare the given object with the entry at the current position. */ static int listTypeEqual(listTypeEntry *entry, robj *o) { listTypeIterator *li = entry->li; @@@ -5174,6 -5211,75 +5211,75 @@@ static void rpushCommand(redisClient *c pushGenericCommand(c,REDIS_TAIL); } + static void pushxGenericCommand(redisClient *c, robj *refval, robj *val, int where) { + robj *subject; + listTypeIterator *iter; + listTypeEntry entry; + int inserted = 0; + + if ((subject = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL || + checkType(c,subject,REDIS_LIST)) return; + + if (refval != NULL) { + /* Note: we expect refval to be string-encoded because it is *not* the + * last argument of the multi-bulk LINSERT. */ + redisAssert(refval->encoding == REDIS_ENCODING_RAW); + + /* We're not sure if this value can be inserted yet, but we cannot + * convert the list inside the iterator. We don't want to loop over + * the list twice (once to see if the value can be inserted and once + * to do the actual insert), so we assume this value can be inserted + * and convert the ziplist to a regular list if necessary. */ + listTypeTryConversion(subject,val); + + /* Seek refval from head to tail */ + iter = listTypeInitIterator(subject,0,REDIS_TAIL); + while (listTypeNext(iter,&entry)) { + if (listTypeEqual(&entry,refval)) { + listTypeInsert(&entry,val,where); + inserted = 1; + break; + } + } + listTypeReleaseIterator(iter); + + if (inserted) { + /* Check if the length exceeds the ziplist length threshold. */ + if (subject->encoding == REDIS_ENCODING_ZIPLIST && + ziplistLen(subject->ptr) > server.list_max_ziplist_entries) + listTypeConvert(subject,REDIS_ENCODING_LIST); + server.dirty++; + } else { + /* Notify client of a failed insert */ + addReply(c,shared.cnegone); + return; + } + } else { + listTypePush(subject,val,where); + server.dirty++; + } + + addReplyUlong(c,listTypeLength(subject)); + } + + static void lpushxCommand(redisClient *c) { + pushxGenericCommand(c,NULL,c->argv[2],REDIS_HEAD); + } + + static void rpushxCommand(redisClient *c) { + pushxGenericCommand(c,NULL,c->argv[2],REDIS_TAIL); + } + + static void linsertCommand(redisClient *c) { + if (strcasecmp(c->argv[2]->ptr,"after") == 0) { + pushxGenericCommand(c,c->argv[3],c->argv[4],REDIS_TAIL); + } else if (strcasecmp(c->argv[2]->ptr,"before") == 0) { + pushxGenericCommand(c,c->argv[3],c->argv[4],REDIS_HEAD); + } else { + addReply(c,shared.syntaxerr); + } + } + static void llenCommand(redisClient *c) { robj *o = lookupKeyReadOrReply(c,c->argv[1],shared.czero); if (o == NULL || checkType(c,o,REDIS_LIST)) return; @@@ -7918,7 -8024,6 +8024,7 @@@ static void discardCommand(redisClient freeClientMultiState(c); initClientMultiState(c); c->flags &= (~REDIS_MULTI); + unwatchAllKeys(c); addReply(c,shared.ok); } @@@ -9585,8 -9690,10 +9691,10 @@@ static double computeObjectSwappability /* actual age can be >= minage, but not < minage. As we use wrapping * 21 bit clocks with minutes resolution for the LRU. */ time_t minage = abs(server.lruclock - o->lru); - long asize = 0; + long asize = 0, elesize; + robj *ele; list *l; + listNode *ln; dict *d; struct dictEntry *de; int z; @@@ -9601,17 -9708,18 +9709,18 @@@ } break; case REDIS_LIST: - l = o->ptr; - listNode *ln = listFirst(l); - - asize = sizeof(list); - if (ln) { - robj *ele = ln->value; - long elesize; - - elesize = (ele->encoding == REDIS_ENCODING_RAW) ? - (sizeof(*o)+sdslen(ele->ptr)) : sizeof(*o); - asize += (sizeof(listNode)+elesize)*listLength(l); + if (o->encoding == REDIS_ENCODING_ZIPLIST) { + asize = sizeof(*o)+ziplistSize(o->ptr); + } else { + l = o->ptr; + ln = listFirst(l); + asize = sizeof(list); + if (ln) { + ele = ln->value; + elesize = (ele->encoding == REDIS_ENCODING_RAW) ? + (sizeof(*o)+sdslen(ele->ptr)) : sizeof(*o); + asize += (sizeof(listNode)+elesize)*listLength(l); + } } break; case REDIS_SET: @@@ -9622,9 -9730,6 +9731,6 @@@ asize = sizeof(dict)+(sizeof(struct dictEntry*)*dictSlots(d)); if (z) asize += sizeof(zset)-sizeof(dict); if (dictSize(d)) { - long elesize; - robj *ele; - de = dictGetRandomKey(d); ele = dictGetEntryKey(de); elesize = (ele->encoding == REDIS_ENCODING_RAW) ? @@@ -9649,9 -9754,6 +9755,6 @@@ d = o->ptr; asize = sizeof(dict)+(sizeof(struct dictEntry*)*dictSlots(d)); if (dictSize(d)) { - long elesize; - robj *ele; - de = dictGetRandomKey(d); ele = dictGetEntryKey(de); elesize = (ele->encoding == REDIS_ENCODING_RAW) ?