X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/3c68de9b0107a0a15eef09edf86464d1434048e7..947efa8d6e37f38bdd8485b64f7c139d1e310e70:/redis.c diff --git a/redis.c b/redis.c index e095e695..331aaaa0 100644 --- a/redis.c +++ b/redis.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2006-2009, Salvatore Sanfilippo + * Copyright (c) 2009-2010, Salvatore Sanfilippo * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -27,7 +27,7 @@ * POSSIBILITY OF SUCH DAMAGE. */ -#define REDIS_VERSION "1.3.3" +#define REDIS_VERSION "1.3.4" #include "fmacros.h" #include "config.h" @@ -38,6 +38,7 @@ #include #include #define __USE_POSIX199309 +#define __USE_UNIX98 #include #ifdef HAVE_BACKTRACE @@ -426,6 +427,10 @@ struct redisCommand { redisCommandProc *proc; int arity; int flags; + /* What keys should be loaded in background when calling this command? */ + int vm_firstkey; /* The first argument that's a key (0 = no keys) */ + int vm_lastkey; /* THe last argument that's a key */ + int vm_keystep; /* The step between first and last key */ }; struct redisFunctionSym { @@ -451,6 +456,7 @@ typedef struct _redisSortOperation { typedef struct zskiplistNode { struct zskiplistNode **forward; struct zskiplistNode *backward; + unsigned int *span; double score; robj *obj; } zskiplistNode; @@ -641,6 +647,7 @@ static void zaddCommand(redisClient *c); static void zincrbyCommand(redisClient *c); static void zrangeCommand(redisClient *c); static void zrangebyscoreCommand(redisClient *c); +static void zcountCommand(redisClient *c); static void zrevrangeCommand(redisClient *c); static void zcardCommand(redisClient *c); static void zremCommand(redisClient *c); @@ -648,93 +655,102 @@ static void zscoreCommand(redisClient *c); static void zremrangebyscoreCommand(redisClient *c); static void multiCommand(redisClient *c); static void execCommand(redisClient *c); +static void discardCommand(redisClient *c); static void blpopCommand(redisClient *c); static void brpopCommand(redisClient *c); +static void appendCommand(redisClient *c); +static void substrCommand(redisClient *c); +static void zrankCommand(redisClient *c); /*================================= Globals ================================= */ /* Global vars */ static struct redisServer server; /* server global state */ static struct redisCommand cmdTable[] = { - {"get",getCommand,2,REDIS_CMD_INLINE}, - {"set",setCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"setnx",setnxCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"del",delCommand,-2,REDIS_CMD_INLINE}, - {"exists",existsCommand,2,REDIS_CMD_INLINE}, - {"incr",incrCommand,2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"decr",decrCommand,2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"mget",mgetCommand,-2,REDIS_CMD_INLINE}, - {"rpush",rpushCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"lpush",lpushCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"rpop",rpopCommand,2,REDIS_CMD_INLINE}, - {"lpop",lpopCommand,2,REDIS_CMD_INLINE}, - {"brpop",brpopCommand,-3,REDIS_CMD_INLINE}, - {"blpop",blpopCommand,-3,REDIS_CMD_INLINE}, - {"llen",llenCommand,2,REDIS_CMD_INLINE}, - {"lindex",lindexCommand,3,REDIS_CMD_INLINE}, - {"lset",lsetCommand,4,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"lrange",lrangeCommand,4,REDIS_CMD_INLINE}, - {"ltrim",ltrimCommand,4,REDIS_CMD_INLINE}, - {"lrem",lremCommand,4,REDIS_CMD_BULK}, - {"rpoplpush",rpoplpushcommand,3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"sadd",saddCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"srem",sremCommand,3,REDIS_CMD_BULK}, - {"smove",smoveCommand,4,REDIS_CMD_BULK}, - {"sismember",sismemberCommand,3,REDIS_CMD_BULK}, - {"scard",scardCommand,2,REDIS_CMD_INLINE}, - {"spop",spopCommand,2,REDIS_CMD_INLINE}, - {"srandmember",srandmemberCommand,2,REDIS_CMD_INLINE}, - {"sinter",sinterCommand,-2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"sinterstore",sinterstoreCommand,-3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"sunion",sunionCommand,-2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"sunionstore",sunionstoreCommand,-3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"sdiff",sdiffCommand,-2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"sdiffstore",sdiffstoreCommand,-3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"smembers",sinterCommand,2,REDIS_CMD_INLINE}, - {"zadd",zaddCommand,4,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"zincrby",zincrbyCommand,4,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"zrem",zremCommand,3,REDIS_CMD_BULK}, - {"zremrangebyscore",zremrangebyscoreCommand,4,REDIS_CMD_INLINE}, - {"zrange",zrangeCommand,-4,REDIS_CMD_INLINE}, - {"zrangebyscore",zrangebyscoreCommand,-4,REDIS_CMD_INLINE}, - {"zrevrange",zrevrangeCommand,-4,REDIS_CMD_INLINE}, - {"zcard",zcardCommand,2,REDIS_CMD_INLINE}, - {"zscore",zscoreCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"incrby",incrbyCommand,3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"decrby",decrbyCommand,3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"getset",getsetCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"mset",msetCommand,-3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"msetnx",msetnxCommand,-3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM}, - {"randomkey",randomkeyCommand,1,REDIS_CMD_INLINE}, - {"select",selectCommand,2,REDIS_CMD_INLINE}, - {"move",moveCommand,3,REDIS_CMD_INLINE}, - {"rename",renameCommand,3,REDIS_CMD_INLINE}, - {"renamenx",renamenxCommand,3,REDIS_CMD_INLINE}, - {"expire",expireCommand,3,REDIS_CMD_INLINE}, - {"expireat",expireatCommand,3,REDIS_CMD_INLINE}, - {"keys",keysCommand,2,REDIS_CMD_INLINE}, - {"dbsize",dbsizeCommand,1,REDIS_CMD_INLINE}, - {"auth",authCommand,2,REDIS_CMD_INLINE}, - {"ping",pingCommand,1,REDIS_CMD_INLINE}, - {"echo",echoCommand,2,REDIS_CMD_BULK}, - {"save",saveCommand,1,REDIS_CMD_INLINE}, - {"bgsave",bgsaveCommand,1,REDIS_CMD_INLINE}, - {"bgrewriteaof",bgrewriteaofCommand,1,REDIS_CMD_INLINE}, - {"shutdown",shutdownCommand,1,REDIS_CMD_INLINE}, - {"lastsave",lastsaveCommand,1,REDIS_CMD_INLINE}, - {"type",typeCommand,2,REDIS_CMD_INLINE}, - {"multi",multiCommand,1,REDIS_CMD_INLINE}, - {"exec",execCommand,1,REDIS_CMD_INLINE}, - {"sync",syncCommand,1,REDIS_CMD_INLINE}, - {"flushdb",flushdbCommand,1,REDIS_CMD_INLINE}, - {"flushall",flushallCommand,1,REDIS_CMD_INLINE}, - {"sort",sortCommand,-2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM}, - {"info",infoCommand,1,REDIS_CMD_INLINE}, - {"monitor",monitorCommand,1,REDIS_CMD_INLINE}, - {"ttl",ttlCommand,2,REDIS_CMD_INLINE}, - {"slaveof",slaveofCommand,3,REDIS_CMD_INLINE}, - {"debug",debugCommand,-2,REDIS_CMD_INLINE}, - {NULL,NULL,0,0} + {"get",getCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"set",setCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,0,0,0}, + {"setnx",setnxCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,0,0,0}, + {"append",appendCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,1,1}, + {"substr",substrCommand,4,REDIS_CMD_INLINE,1,1,1}, + {"del",delCommand,-2,REDIS_CMD_INLINE,0,0,0}, + {"exists",existsCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"incr",incrCommand,2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,1,1,1}, + {"decr",decrCommand,2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,1,1,1}, + {"mget",mgetCommand,-2,REDIS_CMD_INLINE,1,-1,1}, + {"rpush",rpushCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,1,1}, + {"lpush",lpushCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,1,1}, + {"rpop",rpopCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"lpop",lpopCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"brpop",brpopCommand,-3,REDIS_CMD_INLINE,1,1,1}, + {"blpop",blpopCommand,-3,REDIS_CMD_INLINE,1,1,1}, + {"llen",llenCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"lindex",lindexCommand,3,REDIS_CMD_INLINE,1,1,1}, + {"lset",lsetCommand,4,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,1,1}, + {"lrange",lrangeCommand,4,REDIS_CMD_INLINE,1,1,1}, + {"ltrim",ltrimCommand,4,REDIS_CMD_INLINE,1,1,1}, + {"lrem",lremCommand,4,REDIS_CMD_BULK,1,1,1}, + {"rpoplpush",rpoplpushcommand,3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,1,2,1}, + {"sadd",saddCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,1,1}, + {"srem",sremCommand,3,REDIS_CMD_BULK,1,1,1}, + {"smove",smoveCommand,4,REDIS_CMD_BULK,1,2,1}, + {"sismember",sismemberCommand,3,REDIS_CMD_BULK,1,1,1}, + {"scard",scardCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"spop",spopCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"srandmember",srandmemberCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"sinter",sinterCommand,-2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,1,-1,1}, + {"sinterstore",sinterstoreCommand,-3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,2,-1,1}, + {"sunion",sunionCommand,-2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,1,-1,1}, + {"sunionstore",sunionstoreCommand,-3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,2,-1,1}, + {"sdiff",sdiffCommand,-2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,1,-1,1}, + {"sdiffstore",sdiffstoreCommand,-3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,2,-1,1}, + {"smembers",sinterCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"zadd",zaddCommand,4,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,1,1}, + {"zincrby",zincrbyCommand,4,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,1,1}, + {"zrem",zremCommand,3,REDIS_CMD_BULK,1,1,1}, + {"zremrangebyscore",zremrangebyscoreCommand,4,REDIS_CMD_INLINE,1,1,1}, + {"zrange",zrangeCommand,-4,REDIS_CMD_INLINE,1,1,1}, + {"zrangebyscore",zrangebyscoreCommand,-4,REDIS_CMD_INLINE,1,1,1}, + {"zcount",zcountCommand,4,REDIS_CMD_INLINE,1,1,1}, + {"zrevrange",zrevrangeCommand,-4,REDIS_CMD_INLINE,1,1,1}, + {"zcard",zcardCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"zscore",zscoreCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,1,1}, + {"zrank",zrankCommand,3,REDIS_CMD_INLINE,1,1,1}, + {"incrby",incrbyCommand,3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,1,1,1}, + {"decrby",decrbyCommand,3,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,1,1,1}, + {"getset",getsetCommand,3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,1,1}, + {"mset",msetCommand,-3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,-1,2}, + {"msetnx",msetnxCommand,-3,REDIS_CMD_BULK|REDIS_CMD_DENYOOM,1,-1,2}, + {"randomkey",randomkeyCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"select",selectCommand,2,REDIS_CMD_INLINE,0,0,0}, + {"move",moveCommand,3,REDIS_CMD_INLINE,1,1,1}, + {"rename",renameCommand,3,REDIS_CMD_INLINE,1,1,1}, + {"renamenx",renamenxCommand,3,REDIS_CMD_INLINE,1,1,1}, + {"expire",expireCommand,3,REDIS_CMD_INLINE,0,0,0}, + {"expireat",expireatCommand,3,REDIS_CMD_INLINE,0,0,0}, + {"keys",keysCommand,2,REDIS_CMD_INLINE,0,0,0}, + {"dbsize",dbsizeCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"auth",authCommand,2,REDIS_CMD_INLINE,0,0,0}, + {"ping",pingCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"echo",echoCommand,2,REDIS_CMD_BULK,0,0,0}, + {"save",saveCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"bgsave",bgsaveCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"bgrewriteaof",bgrewriteaofCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"shutdown",shutdownCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"lastsave",lastsaveCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"type",typeCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"multi",multiCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"exec",execCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"discard",discardCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"sync",syncCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"flushdb",flushdbCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"flushall",flushallCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"sort",sortCommand,-2,REDIS_CMD_INLINE|REDIS_CMD_DENYOOM,1,1,1}, + {"info",infoCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"monitor",monitorCommand,1,REDIS_CMD_INLINE,0,0,0}, + {"ttl",ttlCommand,2,REDIS_CMD_INLINE,1,1,1}, + {"slaveof",slaveofCommand,3,REDIS_CMD_INLINE,0,0,0}, + {"debug",debugCommand,-2,REDIS_CMD_INLINE,0,0,0}, + {NULL,NULL,0,0,0,0,0} }; /*============================ Utility functions ============================ */ @@ -871,7 +887,7 @@ static void redisLog(int level, const char *fmt, ...) { va_start(ap, fmt); if (level >= server.verbosity) { - char *c = ".-*"; + char *c = ".-*#"; char buf[64]; time_t now; @@ -954,10 +970,24 @@ static int dictEncObjKeyCompare(void *privdata, const void *key1, static unsigned int dictEncObjHash(const void *key) { robj *o = (robj*) key; - o = getDecodedObject(o); - unsigned int hash = dictGenHashFunction(o->ptr, sdslen((sds)o->ptr)); - decrRefCount(o); - return hash; + if (o->encoding == REDIS_ENCODING_RAW) { + return dictGenHashFunction(o->ptr, sdslen((sds)o->ptr)); + } else { + if (o->encoding == REDIS_ENCODING_INT) { + char buf[32]; + int len; + + len = snprintf(buf,32,"%ld",(long)o->ptr); + return dictGenHashFunction((unsigned char*)buf, len); + } else { + unsigned int hash; + + o = getDecodedObject(o); + hash = dictGenHashFunction(o->ptr, sdslen((sds)o->ptr)); + decrRefCount(o); + return hash; + } + } } /* Sets type and expires */ @@ -2119,7 +2149,7 @@ static int processCommand(redisClient *c) { } /* Exec the command */ - if (c->flags & REDIS_MULTI && cmd->proc != execCommand) { + if (c->flags & REDIS_MULTI && cmd->proc != execCommand && cmd->proc != discardCommand) { queueMultiCommand(c,cmd); addReply(c,shared.queued); } else { @@ -2312,7 +2342,8 @@ static void readQueryFromClient(aeEventLoop *el, int fd, void *privdata, int mas } else { return; } - processInputBuffer(c); + if (!(c->flags & REDIS_BLOCKED)) + processInputBuffer(c); } static int selectDb(redisClient *c, int id) { @@ -2324,7 +2355,7 @@ static int selectDb(redisClient *c, int id) { static void *dupClientReplyValue(void *o) { incrRefCount((robj*)o); - return 0; + return o; } static redisClient *createClient(int fd) { @@ -2392,6 +2423,14 @@ static void addReplyDouble(redisClient *c, double d) { (unsigned long) strlen(buf),buf)); } +static void addReplyLong(redisClient *c, long l) { + char buf[128]; + size_t len; + + len = snprintf(buf,sizeof(buf),":%ld\r\n",l); + addReplySds(c,sdsnewlen(buf,len)); +} + static void addReplyBulkLen(redisClient *c, robj *obj) { size_t len; @@ -3681,6 +3720,96 @@ static void decrbyCommand(redisClient *c) { incrDecrCommand(c,-incr); } +static void appendCommand(redisClient *c) { + int retval; + size_t totlen; + robj *o; + + o = lookupKeyWrite(c->db,c->argv[1]); + if (o == NULL) { + /* Create the key */ + retval = dictAdd(c->db->dict,c->argv[1],c->argv[2]); + incrRefCount(c->argv[1]); + incrRefCount(c->argv[2]); + totlen = stringObjectLen(c->argv[2]); + } else { + dictEntry *de; + + de = dictFind(c->db->dict,c->argv[1]); + assert(de != NULL); + + o = dictGetEntryVal(de); + if (o->type != REDIS_STRING) { + addReply(c,shared.wrongtypeerr); + return; + } + /* If the object is specially encoded or shared we have to make + * a copy */ + if (o->refcount != 1 || o->encoding != REDIS_ENCODING_RAW) { + robj *decoded = getDecodedObject(o); + + o = createStringObject(decoded->ptr, sdslen(decoded->ptr)); + decrRefCount(decoded); + dictReplace(c->db->dict,c->argv[1],o); + } + /* APPEND! */ + if (c->argv[2]->encoding == REDIS_ENCODING_RAW) { + o->ptr = sdscatlen(o->ptr, + c->argv[2]->ptr, sdslen(c->argv[2]->ptr)); + } else { + o->ptr = sdscatprintf(o->ptr, "%ld", + (unsigned long) c->argv[2]->ptr); + } + totlen = sdslen(o->ptr); + } + server.dirty++; + addReplySds(c,sdscatprintf(sdsempty(),":%lu\r\n",(unsigned long)totlen)); +} + +static void substrCommand(redisClient *c) { + robj *o; + long start = atoi(c->argv[2]->ptr); + long end = atoi(c->argv[3]->ptr); + + o = lookupKeyRead(c->db,c->argv[1]); + if (o == NULL) { + addReply(c,shared.nullbulk); + } else { + if (o->type != REDIS_STRING) { + addReply(c,shared.wrongtypeerr); + } else { + size_t rangelen, strlen; + sds range; + + o = getDecodedObject(o); + strlen = sdslen(o->ptr); + + /* convert negative indexes */ + if (start < 0) start = strlen+start; + if (end < 0) end = strlen+end; + if (start < 0) start = 0; + if (end < 0) end = 0; + + /* indexes sanity checks */ + if (start > end || (size_t)start >= strlen) { + /* Out of range start or start > end result in null reply */ + addReply(c,shared.nullbulk); + decrRefCount(o); + return; + } + if ((size_t)end >= strlen) end = strlen-1; + rangelen = (end-start)+1; + + /* Return the result */ + addReplySds(c,sdscatprintf(sdsempty(),"$%lu\r\n",rangelen)); + range = sdsnewlen((char*)o->ptr+start,rangelen); + addReplySds(c,range); + addReply(c,shared.crlf); + decrRefCount(o); + } + } +} + /* ========================= Type agnostic commands ========================= */ static void delCommand(redisClient *c) { @@ -3741,7 +3870,7 @@ static void keysCommand(redisClient *c) { dictEntry *de; sds pattern = c->argv[1]->ptr; int plen = sdslen(pattern); - unsigned long numkeys = 0, keyslen = 0; + unsigned long numkeys = 0; robj *lenobj = createObject(REDIS_STRING,NULL); di = dictGetIterator(c->db->dict); @@ -3754,17 +3883,15 @@ static void keysCommand(redisClient *c) { if ((pattern[0] == '*' && pattern[1] == '\0') || stringmatchlen(pattern,plen,key,sdslen(key),0)) { if (expireIfNeeded(c->db,keyobj) == 0) { - if (numkeys != 0) - addReply(c,shared.space); + addReplyBulkLen(c,keyobj); addReply(c,keyobj); + addReply(c,shared.crlf); numkeys++; - keyslen += sdslen(key); } } } dictReleaseIterator(di); - lenobj->ptr = sdscatprintf(sdsempty(),"$%lu\r\n",keyslen+(numkeys ? (numkeys-1) : 0)); - addReply(c,shared.crlf); + lenobj->ptr = sdscatprintf(sdsempty(),"*%lu\r\n",numkeys); } static void dbsizeCommand(redisClient *c) { @@ -3948,7 +4075,7 @@ static void pushGenericCommand(redisClient *c, int where) { lobj = lookupKeyWrite(c->db,c->argv[1]); if (lobj == NULL) { if (handleClientsWaitingListPush(c,c->argv[1],c->argv[2])) { - addReply(c,shared.ok); + addReply(c,shared.cone); return; } lobj = createListObject(); @@ -3967,7 +4094,7 @@ static void pushGenericCommand(redisClient *c, int where) { return; } if (handleClientsWaitingListPush(c,c->argv[1],c->argv[2])) { - addReply(c,shared.ok); + addReply(c,shared.cone); return; } list = lobj->ptr; @@ -3979,7 +4106,7 @@ static void pushGenericCommand(redisClient *c, int where) { incrRefCount(c->argv[2]); } server.dirty++; - addReply(c,shared.ok); + addReplySds(c,sdscatprintf(sdsempty(),":%d\r\n",listLength(list))); } static void lpushCommand(redisClient *c) { @@ -4717,6 +4844,8 @@ static zskiplistNode *zslCreateNode(int level, double score, robj *obj) { zskiplistNode *zn = zmalloc(sizeof(*zn)); zn->forward = zmalloc(sizeof(zskiplistNode*) * level); + if (level > 0) + zn->span = zmalloc(sizeof(unsigned int) * (level - 1)); zn->score = score; zn->obj = obj; return zn; @@ -4730,8 +4859,10 @@ static zskiplist *zslCreate(void) { zsl->level = 1; zsl->length = 0; zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL); - for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) + for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) { zsl->header->forward[j] = NULL; + zsl->header->span[j] = 0; + } zsl->header->backward = NULL; zsl->tail = NULL; return zsl; @@ -4740,6 +4871,7 @@ static zskiplist *zslCreate(void) { static void zslFreeNode(zskiplistNode *node) { decrRefCount(node->obj); zfree(node->forward); + zfree(node->span); zfree(node); } @@ -4747,6 +4879,7 @@ static void zslFree(zskiplist *zsl) { zskiplistNode *node = zsl->header->forward[0], *next; zfree(zsl->header->forward); + zfree(zsl->header->span); zfree(zsl->header); while(node) { next = node->forward[0]; @@ -4765,15 +4898,21 @@ static int zslRandomLevel(void) { static void zslInsert(zskiplist *zsl, double score, robj *obj) { zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; + unsigned int rank[ZSKIPLIST_MAXLEVEL]; int i, level; x = zsl->header; for (i = zsl->level-1; i >= 0; i--) { + /* store rank that is crossed to reach the insert position */ + rank[i] = i == (zsl->level-1) ? 0 : rank[i+1]; + while (x->forward[i] && (x->forward[i]->score < score || (x->forward[i]->score == score && - compareStringObjects(x->forward[i]->obj,obj) < 0))) + compareStringObjects(x->forward[i]->obj,obj) < 0))) { + rank[i] += i > 0 ? x->span[i-1] : 1; x = x->forward[i]; + } update[i] = x; } /* we assume the key is not already inside, since we allow duplicated @@ -4782,15 +4921,30 @@ static void zslInsert(zskiplist *zsl, double score, robj *obj) { * if the element is already inside or not. */ level = zslRandomLevel(); if (level > zsl->level) { - for (i = zsl->level; i < level; i++) + for (i = zsl->level; i < level; i++) { + rank[i] = 0; update[i] = zsl->header; + update[i]->span[i-1] = zsl->length; + } 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; + + /* update span covered by update[i] as x is inserted here */ + if (i > 0) { + x->span[i-1] = update[i]->span[i-1] - (rank[0] - rank[i]); + update[i]->span[i-1] = (rank[0] - rank[i]) + 1; + } + } + + /* increment span for untouched levels */ + for (i = level; i < zsl->level; i++) { + update[i]->span[i-1]++; } + x->backward = (update[0] == zsl->header) ? NULL : update[0]; if (x->forward[0]) x->forward[0]->backward = x; @@ -4818,12 +4972,19 @@ static int zslDelete(zskiplist *zsl, double score, robj *obj) { 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 (update[i]->forward[i] == x) { + if (i > 0) { + update[i]->span[i-1] += x->span[i-1] - 1; + } + update[i]->forward[i] = x->forward[i]; + } else { + /* invariant: i > 0, because update[0]->forward[0] + * is always equal to x */ + update[i]->span[i-1] -= 1; + } } if (x->forward[0]) { - x->forward[0]->backward = (x->backward == zsl->header) ? - NULL : x->backward; + x->forward[0]->backward = x->backward; } else { zsl->tail = x->backward; } @@ -4860,12 +5021,19 @@ static unsigned long zslDeleteRange(zskiplist *zsl, double min, double max, dict zskiplistNode *next; for (i = 0; i < zsl->level; i++) { - if (update[i]->forward[i] != x) break; - update[i]->forward[i] = x->forward[i]; + if (update[i]->forward[i] == x) { + if (i > 0) { + update[i]->span[i-1] += x->span[i-1] - 1; + } + update[i]->forward[i] = x->forward[i]; + } else { + /* invariant: i > 0, because update[0]->forward[0] + * is always equal to x */ + update[i]->span[i-1] -= 1; + } } if (x->forward[0]) { - x->forward[0]->backward = (x->backward == zsl->header) ? - NULL : x->backward; + x->forward[0]->backward = x->backward; } else { zsl->tail = x->backward; } @@ -4897,6 +5065,53 @@ static zskiplistNode *zslFirstWithScore(zskiplist *zsl, double score) { return x->forward[0]; } +/* Find the rank for an element by both score and key. + * Returns 0 when the element cannot be found, rank otherwise. + * Note that the rank is 1-based due to the span of zsl->header to the + * first element. */ +static unsigned long zslGetRank(zskiplist *zsl, double score, robj *o) { + zskiplistNode *x; + unsigned long rank = 0; + 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,o) <= 0))) { + rank += i > 0 ? x->span[i-1] : 1; + x = x->forward[i]; + } + + /* x might be equal to zsl->header, so test if obj is non-NULL */ + if (x->obj && compareStringObjects(x->obj,o) == 0) { + return rank; + } + } + return 0; +} + +/* Finds an element by its rank. The rank argument needs to be 1-based. */ +zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank) { + zskiplistNode *x; + unsigned long traversed = 0; + int i; + + x = zsl->header; + for (i = zsl->level-1; i >= 0; i--) { + while (x->forward[i] && (traversed + (i > 0 ? x->span[i-1] : 1)) <= rank) { + traversed += i > 0 ? x->span[i-1] : 1; + x = x->forward[i]; + } + + if (traversed == rank) { + return x; + } + } + return NULL; +} + /* The actual Z-commands implementations */ /* This generic command implements both ZADD and ZINCRBY. @@ -5096,17 +5311,15 @@ static void zrangeGenericCommand(redisClient *c, int reverse) { if (end >= llen) end = llen-1; rangelen = (end-start)+1; - /* Return the result in form of a multi-bulk reply */ + /* check if starting point is trivial, before searching + * the element in log(N) time */ if (reverse) { - ln = zsl->tail; - while (start--) - ln = ln->backward; + ln = start == 0 ? zsl->tail : zslGetElementByRank(zsl, llen - start); } else { - ln = zsl->header->forward[0]; - while (start--) - ln = ln->forward[0]; + ln = start == 0 ? zsl->header->forward[0] : zslGetElementByRank(zsl, start + 1); } + /* Return the result in form of a multi-bulk reply */ addReplySds(c,sdscatprintf(sdsempty(),"*%d\r\n", withscores ? (rangelen*2) : rangelen)); for (j = 0; j < rangelen; j++) { @@ -5130,28 +5343,64 @@ static void zrevrangeCommand(redisClient *c) { zrangeGenericCommand(c,1); } -static void zrangebyscoreCommand(redisClient *c) { +/* This command implements both ZRANGEBYSCORE and ZCOUNT. + * If justcount is non-zero, just the count is returned. */ +static void genericZrangebyscoreCommand(redisClient *c, int justcount) { robj *o; - double min = strtod(c->argv[2]->ptr,NULL); - double max = strtod(c->argv[3]->ptr,NULL); + double min, max; + int minex = 0, maxex = 0; /* are min or max exclusive? */ int offset = 0, limit = -1; + int withscores = 0; + int badsyntax = 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 (((char*)c->argv[2]->ptr)[0] == '(') { + min = strtod((char*)c->argv[2]->ptr+1,NULL); + minex = 1; + } else { + min = strtod(c->argv[2]->ptr,NULL); + } + if (((char*)c->argv[3]->ptr)[0] == '(') { + max = strtod((char*)c->argv[3]->ptr+1,NULL); + maxex = 1; + } else { + max = strtod(c->argv[3]->ptr,NULL); + } - if (c->argc != 4 && c->argc != 7) { + /* Parse "WITHSCORES": note that if the command was called with + * the name ZCOUNT then we are sure that c->argc == 4, so we'll never + * enter the following paths to parse WITHSCORES and LIMIT. */ + if (c->argc == 5 || c->argc == 8) { + if (strcasecmp(c->argv[c->argc-1]->ptr,"withscores") == 0) + withscores = 1; + else + badsyntax = 1; + } + if (c->argc != (4 + withscores) && c->argc != (7 + withscores)) + badsyntax = 1; + if (badsyntax) { addReplySds(c, sdsnew("-ERR wrong number of arguments for ZRANGEBYSCORE\r\n")); return; - } else if (c->argc == 7 && strcasecmp(c->argv[4]->ptr,"limit")) { + } + + /* Parse "LIMIT" */ + if (c->argc == (7 + withscores) && strcasecmp(c->argv[4]->ptr,"limit")) { addReply(c,shared.syntaxerr); return; - } else if (c->argc == 7) { + } else if (c->argc == (7 + withscores)) { offset = atoi(c->argv[5]->ptr); limit = atoi(c->argv[6]->ptr); if (offset < 0) offset = 0; } + /* Ok, lookup the key and get the range */ o = lookupKeyRead(c->db,c->argv[1]); if (o == NULL) { - addReply(c,shared.nullmultibulk); + addReply(c,justcount ? shared.czero : shared.nullmultibulk); } else { if (o->type != REDIS_ZSET) { addReply(c,shared.wrongtypeerr); @@ -5159,14 +5408,17 @@ static void zrangebyscoreCommand(redisClient *c) { zset *zsetobj = o->ptr; zskiplist *zsl = zsetobj->zsl; zskiplistNode *ln; - robj *ele, *lenobj; - unsigned int rangelen = 0; + robj *ele, *lenobj = NULL; + unsigned long rangelen = 0; - /* Get the first node with the score >= min */ + /* Get the first node with the score >= min, or with + * score > min if 'minex' is true. */ ln = zslFirstWithScore(zsl,min); + while (minex && ln && ln->score == min) ln = ln->forward[0]; + if (ln == NULL) { /* No element matching the speciifed interval */ - addReply(c,shared.emptymultibulk); + addReply(c,justcount ? shared.czero : shared.emptymultibulk); return; } @@ -5174,30 +5426,49 @@ static void zrangebyscoreCommand(redisClient *c) { * 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); - decrRefCount(lenobj); + if (!justcount) { + lenobj = createObject(REDIS_STRING,NULL); + addReply(c,lenobj); + decrRefCount(lenobj); + } - while(ln && ln->score <= max) { + while(ln && (maxex ? (ln->score < max) : (ln->score <= max))) { if (offset) { offset--; ln = ln->forward[0]; continue; } if (limit == 0) break; - ele = ln->obj; - addReplyBulkLen(c,ele); - addReply(c,ele); - addReply(c,shared.crlf); + if (!justcount) { + ele = ln->obj; + addReplyBulkLen(c,ele); + addReply(c,ele); + addReply(c,shared.crlf); + if (withscores) + addReplyDouble(c,ln->score); + } ln = ln->forward[0]; rangelen++; if (limit > 0) limit--; } - lenobj->ptr = sdscatprintf(sdsempty(),"*%d\r\n",rangelen); + if (justcount) { + addReplyLong(c,(long)rangelen); + } else { + lenobj->ptr = sdscatprintf(sdsempty(),"*%lu\r\n", + withscores ? (rangelen*2) : rangelen); + } } } } +static void zrangebyscoreCommand(redisClient *c) { + genericZrangebyscoreCommand(c,0); +} + +static void zcountCommand(redisClient *c) { + genericZrangebyscoreCommand(c,1); +} + static void zcardCommand(redisClient *c) { robj *o; zset *zs; @@ -5243,6 +5514,37 @@ static void zscoreCommand(redisClient *c) { } } +static void zrankCommand(redisClient *c) { + robj *o; + o = lookupKeyRead(c->db,c->argv[1]); + if (o == NULL) { + addReply(c,shared.nullbulk); + return; + } + if (o->type != REDIS_ZSET) { + addReply(c,shared.wrongtypeerr); + } else { + zset *zs = o->ptr; + zskiplist *zsl = zs->zsl; + dictEntry *de; + unsigned long rank; + + de = dictFind(zs->dict,c->argv[2]); + if (!de) { + addReply(c,shared.nullbulk); + return; + } + + double *score = dictGetEntryVal(de); + rank = zslGetRank(zsl, *score, c->argv[2]); + if (rank) { + addReplyLong(c, rank-1); + } else { + addReply(c,shared.nullbulk); + } + } +} + /* ========================= Non type-specific commands ==================== */ static void flushdbCommand(redisClient *c) { @@ -5916,6 +6218,18 @@ static void multiCommand(redisClient *c) { addReply(c,shared.ok); } +static void discardCommand(redisClient *c) { + if (!(c->flags & REDIS_MULTI)) { + addReplySds(c,sdsnew("-ERR DISCARD without MULTI\r\n")); + return; + } + + freeClientMultiState(c); + initClientMultiState(c); + c->flags &= (~REDIS_MULTI); + addReply(c,shared.ok); +} + static void execCommand(redisClient *c) { int j; robj **orig_argv; @@ -6004,7 +6318,6 @@ static void blockForKeys(redisClient *c, robj **keys, int numkeys, time_t timeou } /* Mark the client as a blocked client */ c->flags |= REDIS_BLOCKED; - aeDeleteFileEvent(server.el,c->fd,AE_READABLE); server.blpop_blocked_clients++; } @@ -6032,14 +6345,7 @@ static void unblockClientWaitingData(redisClient *c) { c->blockingkeys = NULL; c->flags &= (~REDIS_BLOCKED); server.blpop_blocked_clients--; - /* Ok now we are ready to get read events from socket, note that we - * can't trap errors here as it's possible that unblockClientWaitingDatas() is - * called from freeClient() itself, and the only thing we can do - * if we failed to register the READABLE event is to kill the client. - * Still the following function should never fail in the real world as - * we are sure the file descriptor is sane, and we exit on out of mem. */ - aeCreateFileEvent(server.el, c->fd, AE_READABLE, readQueryFromClient, c); - /* As a final step we want to process data if there is some command waiting + /* We want to process data if there is some command waiting * in the input buffer. Note that this is safe even if * unblockClientWaitingData() gets called from freeClient() because * freeClient() will be smart enough to call this function @@ -7154,8 +7460,6 @@ static void vmMarkPageUsed(off_t page) { int bit = page&7; redisAssert(vmFreePage(page) == 1); server.vm_bitmap[byte] |= 1< 100000000) { - *((char*)-1) = 'x'; - } + redisLog(REDIS_DEBUG,"Mark FREE pages: %lld pages at %lld\n", + (long long)count, (long long)page); } /* Test if the page is free */ @@ -7237,7 +7540,6 @@ static int vmFindContiguousPages(off_t *first, off_t n) { numfree = 0; } } - redisLog(REDIS_DEBUG, "THIS: %lld (%c)\n", (long long) this, vmFreePage(this) ? 'F' : 'X'); if (vmFreePage(this)) { /* This is a free page */ numfree++; @@ -7245,6 +7547,7 @@ static int vmFindContiguousPages(off_t *first, off_t n) { if (numfree == n) { *first = this-(n-1); server.vm_next_page = this+1; + redisLog(REDIS_DEBUG, "FOUND CONTIGUOUS PAGES: %lld pages at %lld\n", (long long) n, (long long) *first); return REDIS_OK; } } else { @@ -7275,11 +7578,12 @@ static int vmWriteObjectOnSwap(robj *o, off_t page) { if (fseeko(server.vm_fp,page*server.vm_page_size,SEEK_SET) == -1) { if (server.vm_enabled) pthread_mutex_unlock(&server.io_swapfile_mutex); redisLog(REDIS_WARNING, - "Critical VM problem in vmSwapObjectBlocking(): can't seek: %s", + "Critical VM problem in vmWriteObjectOnSwap(): can't seek: %s", strerror(errno)); return REDIS_ERR; } rdbSaveObject(server.vm_fp,o); + fflush(server.vm_fp); if (server.vm_enabled) pthread_mutex_unlock(&server.io_swapfile_mutex); return REDIS_OK; } @@ -7307,7 +7611,6 @@ static int vmSwapObjectBlocking(robj *key, robj *val) { (unsigned long long) page, (unsigned long long) pages); server.vm_stats_swapped_objects++; server.vm_stats_swapouts++; - fflush(server.vm_fp); return REDIS_OK; } @@ -7436,7 +7739,7 @@ static double computeObjectSwappability(robj *o) { } break; } - return (double)asize*log(1+asize); + return (double)age*log(1+asize); } /* Try to swap an object that's a good candidate for swapping. @@ -7487,10 +7790,7 @@ static int vmSwapOneObject(int usethreads) { } } } - if (best == NULL) { - redisLog(REDIS_DEBUG,"No swappable key found!"); - return REDIS_ERR; - } + if (best == NULL) return REDIS_ERR; key = dictGetEntryKey(best); val = dictGetEntryVal(best); @@ -7794,8 +8094,8 @@ static void *IOThreadEntryPoint(void *arg) { lockThreadedIO(); if (listLength(server.io_newjobs) == 0) { /* No new jobs in queue, exit. */ - redisLog(REDIS_DEBUG,"Thread %lld exiting, nothing to do", - (long long) pthread_self()); + redisLog(REDIS_DEBUG,"Thread %ld exiting, nothing to do", + (long) pthread_self()); server.io_active_threads--; unlockThreadedIO(); return NULL; @@ -7808,8 +8108,8 @@ static void *IOThreadEntryPoint(void *arg) { listAddNodeTail(server.io_processing,j); ln = listLast(server.io_processing); /* We use ln later to remove it */ unlockThreadedIO(); - redisLog(REDIS_DEBUG,"Thread %lld got a new job (type %d): %p about key '%s'", - (long long) pthread_self(), j->type, (void*)j, (char*)j->key->ptr); + redisLog(REDIS_DEBUG,"Thread %ld got a new job (type %d): %p about key '%s'", + (long) pthread_self(), j->type, (void*)j, (char*)j->key->ptr); /* Process the Job */ if (j->type == REDIS_IOJOB_LOAD) { @@ -7824,8 +8124,8 @@ static void *IOThreadEntryPoint(void *arg) { } /* Done: insert the job into the processed queue */ - redisLog(REDIS_DEBUG,"Thread %lld completed the job: %p (key %s)", - (long long) pthread_self(), (void*)j, (char*)j->key->ptr); + redisLog(REDIS_DEBUG,"Thread %ld completed the job: %p (key %s)", + (long) pthread_self(), (void*)j, (char*)j->key->ptr); lockThreadedIO(); listDelNode(server.io_processing,ln); listAddNodeTail(server.io_processed,j); @@ -8002,9 +8302,13 @@ static int waitForSwappedKey(redisClient *c, robj *key) { * Return 1 if the client is marked as blocked, 0 if the client can * continue as the keys it is going to access appear to be in memory. */ static int blockClientOnSwappedKeys(struct redisCommand *cmd, redisClient *c) { - if (cmd->proc == getCommand) { - waitForSwappedKey(c,c->argv[1]); - } + int j, last; + + if (cmd->vm_firstkey == 0) return 0; + last = cmd->vm_lastkey; + if (last < 0) last = c->argc+last; + for (j = cmd->vm_firstkey; j <= last; j += cmd->vm_keystep) + waitForSwappedKey(c,c->argv[j]); /* If the client was blocked for at least one key, mark it as blocked. */ if (listLength(c->io_keys)) { c->flags |= REDIS_IO_WAIT; @@ -8109,8 +8413,8 @@ static void debugCommand(redisClient *c) { } key = dictGetEntryKey(de); val = dictGetEntryVal(de); - if (server.vm_enabled && (key->storage == REDIS_VM_MEMORY || - key->storage == REDIS_VM_SWAPPING)) { + if (!server.vm_enabled || (key->storage == REDIS_VM_MEMORY || + key->storage == REDIS_VM_SWAPPING)) { addReplySds(c,sdscatprintf(sdsempty(), "+Key at:%p refcount:%d, value at:%p refcount:%d " "encoding:%d serializedlength:%lld\r\n", @@ -8271,7 +8575,7 @@ static void *getMcontextEip(ucontext_t *uc) { #else return (void*) uc->uc_mcontext->__ss.__eip; #endif -#elif defined(__i386__) || defined(__X86_64__) || defined(__x86_64__) +#elif defined(__i386__) || defined(__X86_64__) || defined(__x86_64__) return (void*) uc->uc_mcontext.gregs[REG_EIP]; /* Linux 32/64 bit */ #elif defined(__ia64__) /* Linux IA64 */ return (void*) uc->uc_mcontext.sc_ip;