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. */
#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,
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);
{"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},
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"));
/* 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) {
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;
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;
/* 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;
}
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:
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) ?
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) ?
assert_encoding list $key
}
+ test {LPUSHX, RPUSHX - generic} {
+ r del xlist
+ assert_equal 0 [r lpushx xlist a]
+ assert_equal 0 [r llen xlist]
+ assert_equal 0 [r rpushx xlist a]
+ assert_equal 0 [r llen xlist]
+ }
+
+ foreach type {ziplist list} {
+ test "LPUSHX, RPUSHX - $type" {
+ create_$type xlist {b c}
+ assert_equal 3 [r rpushx xlist d]
+ assert_equal 4 [r lpushx xlist a]
+ assert_equal {a b c d} [r lrange xlist 0 -1]
+ }
+
+ test "LINSERT - $type" {
+ create_$type xlist {a b c d}
+ assert_equal 5 [r linsert xlist before c zz]
+ assert_equal {a b zz c d} [r lrange xlist 0 10]
+ assert_equal 6 [r linsert xlist after c yy]
+ assert_equal {a b zz c yy d} [r lrange xlist 0 10]
+ assert_equal 7 [r linsert xlist after d dd]
+ assert_equal -1 [r linsert xlist after bad ddd]
+ assert_equal {a b zz c yy d dd} [r lrange xlist 0 10]
+ assert_equal 8 [r linsert xlist before a aa]
+ assert_equal -1 [r linsert xlist before bad aaa]
+ assert_equal {aa a b zz c yy d dd} [r lrange xlist 0 10]
+
+ # check inserting integer encoded value
+ assert_equal 9 [r linsert xlist before aa 42]
+ assert_equal 42 [r lrange xlist 0 0]
+ }
+ }
+
+ test {LPUSHX, RPUSHX convert from ziplist to list} {
+ set large_value "aaaaaaaaaaaaaaaaa"
+
+ # convert when a large value is pushed
+ create_ziplist xlist a
+ assert_equal 2 [r rpushx xlist $large_value]
+ assert_encoding list xlist
+ create_ziplist xlist a
+ assert_equal 2 [r lpushx xlist $large_value]
+ assert_encoding list xlist
+
+ # convert when the length threshold is exceeded
+ create_ziplist xlist [lrepeat 256 a]
+ assert_equal 257 [r rpushx xlist b]
+ assert_encoding list xlist
+ create_ziplist xlist [lrepeat 256 a]
+ assert_equal 257 [r lpushx xlist b]
+ assert_encoding list xlist
+ }
+
+ test {LINSERT convert from ziplist to list} {
+ set large_value "aaaaaaaaaaaaaaaaa"
+
+ # convert when a large value is inserted
+ create_ziplist xlist a
+ assert_equal 2 [r linsert xlist before a $large_value]
+ assert_encoding list xlist
+ create_ziplist xlist a
+ assert_equal 2 [r linsert xlist after a $large_value]
+ assert_encoding list xlist
+
+ # convert when the length threshold is exceeded
+ create_ziplist xlist [lrepeat 256 a]
+ assert_equal 257 [r linsert xlist before a a]
+ assert_encoding list xlist
+ create_ziplist xlist [lrepeat 256 a]
+ assert_equal 257 [r linsert xlist after a a]
+ assert_encoding list xlist
+
+ # don't convert when the value could not be inserted
+ create_ziplist xlist [lrepeat 256 a]
+ assert_equal -1 [r linsert xlist before foo a]
+ assert_encoding ziplist xlist
+ create_ziplist xlist [lrepeat 256 a]
+ assert_equal -1 [r linsert xlist after foo a]
+ assert_encoding ziplist xlist
+ }
+
foreach {type num} {ziplist 250 list 500} {
proc check_numbered_list_consistency {key} {
set len [r llen $key]
#include <assert.h>
#include <limits.h>
#include "zmalloc.h"
-#include "sds.h"
#include "ziplist.h"
/* Important note: the ZIP_END value is used to depict the end of the
return __ziplistInsert(zl,p,s,slen);
}
-unsigned char *ziplistPop(unsigned char *zl, sds *target, int where) {
- zlentry entry;
- unsigned char *p;
- long long value;
- if (target) *target = NULL;
-
- /* Get pointer to element to remove */
- p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_TAIL(zl);
- if (*p == ZIP_END) return zl;
-
- entry = zipEntry(p);
- if (target) {
- if (entry.encoding == ZIP_ENC_RAW) {
- *target = sdsnewlen(p+entry.headersize,entry.len);
- } else {
- value = zipLoadInteger(p+entry.headersize,entry.encoding);
- *target = sdscatprintf(sdsempty(), "%lld", value);
- }
- }
-
- zl = __ziplistDelete(zl,p,1);
- return zl;
-}
-
/* Returns an offset to use for iterating with ziplistNext. When the given
* index is negative, the list is traversed back to front. When the list
* doesn't contain an element at the provided index, NULL is returned. */
}
}
+void pop(unsigned char *zl, int where) {
+ unsigned char *p, *vstr;
+ unsigned int vlen;
+ long long vlong;
+
+ p = ziplistIndex(zl,where == ZIPLIST_HEAD ? 0 : -1);
+ if (ziplistGet(p,&vstr,&vlen,&vlong)) {
+ if (where == ZIPLIST_HEAD)
+ printf("Pop head: ");
+ else
+ printf("Pop tail: ");
+
+ if (vstr)
+ fwrite(vstr,vlen,1,stdout);
+ else
+ printf("%lld", vlong);
+
+ printf("\n");
+ ziplistDeleteRange(zl,-1,1);
+ } else {
+ printf("ERROR: Could not pop\n");
+ exit(1);
+ }
+}
+
int main(int argc, char **argv) {
unsigned char *zl, *p;
unsigned char *entry;
unsigned int elen;
long long value;
- sds s;
zl = createIntList();
ziplistRepr(zl);
zl = createList();
ziplistRepr(zl);
- zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
- printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
+ pop(zl,ZIPLIST_TAIL);
ziplistRepr(zl);
- zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
- printf("Pop head: %s (length %ld)\n", s, sdslen(s));
+ pop(zl,ZIPLIST_HEAD);
ziplistRepr(zl);
- zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
- printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
+ pop(zl,ZIPLIST_TAIL);
ziplistRepr(zl);
- zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
- printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
+ pop(zl,ZIPLIST_TAIL);
ziplistRepr(zl);
printf("Get element at index 3:\n");
projects / redis.git / commitdiff
