X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/846d8b3ea558fadd8aa4eb5ad5f8d3bf4717b731..f483ce5f:/redis.c

diff --git a/redis.c b/redis.c
index 16384d87..085d3553 100644
--- a/redis.c
+++ b/redis.c
@@ -77,7 +77,6 @@
 #include "zipmap.h" /* Compact dictionary-alike data structure */
 #include "ziplist.h" /* Compact list data structure */
 #include "sha1.h"   /* SHA1 is used for DEBUG DIGEST */
-#include "release.h" /* Release and/or git repository information */
 
 /* Error codes */
 #define REDIS_OK                0
@@ -130,11 +129,11 @@
 #define REDIS_ENCODING_INT 1     /* Encoded as integer */
 #define REDIS_ENCODING_HT 2      /* Encoded as hash table */
 #define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
-#define REDIS_ENCODING_LIST 4    /* Encoded as zipmap */
+#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
 #define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
 
 static char* strencoding[] = {
-    "raw", "int", "hashtable", "zipmap", "list", "ziplist"
+    "raw", "int", "hashtable", "zipmap", "linkedlist", "ziplist"
 };
 
 /* Object types only used for dumping to disk */
@@ -237,9 +236,11 @@ static char* strencoding[] = {
 #define APPENDFSYNC_ALWAYS 1
 #define APPENDFSYNC_EVERYSEC 2
 
-/* Hashes related defaults */
+/* Zip structure related defaults */
 #define REDIS_HASH_MAX_ZIPMAP_ENTRIES 64
 #define REDIS_HASH_MAX_ZIPMAP_VALUE 512
+#define REDIS_LIST_MAX_ZIPLIST_ENTRIES 1024
+#define REDIS_LIST_MAX_ZIPLIST_VALUE 32
 
 /* We can print the stacktrace, so our assert is defined this way: */
 #define redisAssert(_e) ((_e)?(void)0 : (_redisAssert(#_e,__FILE__,__LINE__),_exit(1)))
@@ -259,7 +260,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. */
@@ -425,9 +426,11 @@ struct redisServer {
     off_t vm_page_size;
     off_t vm_pages;
     unsigned long long vm_max_memory;
-    /* Hashes config */
+    /* Zip structure config */
     size_t hash_max_zipmap_entries;
     size_t hash_max_zipmap_value;
+    size_t list_max_ziplist_entries;
+    size_t list_max_ziplist_value;
     /* Virtual memory state */
     FILE *vm_fp;
     int vm_fd;
@@ -534,7 +537,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,
@@ -571,6 +574,8 @@ typedef struct iojob {
 } iojob;
 
 /*================================ Prototypes =============================== */
+char *redisGitSHA1(void);
+char *redisGitDirty(void);
 
 static void freeStringObject(robj *o);
 static void freeListObject(robj *o);
@@ -646,6 +651,7 @@ static struct redisCommand *lookupCommand(char *name);
 static void call(redisClient *c, struct redisCommand *cmd);
 static void resetClient(redisClient *c);
 static void convertToRealHash(robj *o);
+static void listTypeConvert(robj *o, int enc);
 static int pubsubUnsubscribeAllChannels(redisClient *c, int notify);
 static int pubsubUnsubscribeAllPatterns(redisClient *c, int notify);
 static void freePubsubPattern(void *p);
@@ -687,6 +693,9 @@ static void renameCommand(redisClient *c);
 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);
@@ -787,6 +796,9 @@ static struct redisCommand readonlyCommandTable[] = {
     {"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},
@@ -1247,7 +1259,7 @@ static dictType keyptrDictType = {
     NULL,                      /* key dup */
     NULL,                      /* val dup */
     dictSdsKeyCompare,         /* key compare */
-    dictSdsDestructor,         /* key destructor */
+    NULL,                      /* key destructor */
     NULL                       /* val destructor */
 };
 
@@ -1666,6 +1678,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"));
@@ -1755,6 +1768,8 @@ static void initServerConfig() {
     server.vm_blocked_clients = 0;
     server.hash_max_zipmap_entries = REDIS_HASH_MAX_ZIPMAP_ENTRIES;
     server.hash_max_zipmap_value = REDIS_HASH_MAX_ZIPMAP_VALUE;
+    server.list_max_ziplist_entries = REDIS_LIST_MAX_ZIPLIST_ENTRIES;
+    server.list_max_ziplist_value = REDIS_LIST_MAX_ZIPLIST_VALUE;
     server.shutdown_asap = 0;
 
     resetServerSaveParams();
@@ -2033,6 +2048,10 @@ static void loadServerConfig(char *filename) {
             server.hash_max_zipmap_entries = memtoll(argv[1], NULL);
         } else if (!strcasecmp(argv[0],"hash-max-zipmap-value") && argc == 2){
             server.hash_max_zipmap_value = memtoll(argv[1], NULL);
+        } else if (!strcasecmp(argv[0],"list-max-ziplist-entries") && argc == 2){
+            server.list_max_ziplist_entries = memtoll(argv[1], NULL);
+        } else if (!strcasecmp(argv[0],"list-max-ziplist-value") && argc == 2){
+            server.list_max_ziplist_value = memtoll(argv[1], NULL);
         } else {
             err = "Bad directive or wrong number of arguments"; goto loaderr;
         }
@@ -3040,7 +3059,7 @@ static robj *createListObject(void) {
     list *l = listCreate();
     robj *o = createObject(REDIS_LIST,l);
     listSetFreeMethod(l,decrRefCount);
-    o->encoding = REDIS_ENCODING_LIST;
+    o->encoding = REDIS_ENCODING_LINKEDLIST;
     return o;
 }
 
@@ -3082,7 +3101,7 @@ static void freeStringObject(robj *o) {
 
 static void freeListObject(robj *o) {
     switch (o->encoding) {
-    case REDIS_ENCODING_LIST:
+    case REDIS_ENCODING_LINKEDLIST:
         listRelease((list*) o->ptr);
         break;
     case REDIS_ENCODING_ZIPLIST:
@@ -3514,12 +3533,10 @@ static robj *dbRandomKey(redisDb *db) {
 
 /* Delete a key, value, and associated expiration entry if any, from the DB */
 static int dbDelete(redisDb *db, robj *key) {
-    int retval;
-
-    if (dictSize(db->expires)) dictDelete(db->expires,key->ptr);
-    retval = dictDelete(db->dict,key->ptr);
-
-    return retval == DICT_OK;
+    /* Deleting an entry from the expires dict will not free the sds of
+     * the key, because it is shared with the main dictionary. */
+    if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr);
+    return dictDelete(db->dict,key->ptr) == DICT_OK;
 }
 
 /*============================ RDB saving/loading =========================== */
@@ -3760,7 +3777,7 @@ static int rdbSaveObject(FILE *fp, robj *o) {
                 }
                 p = ziplistNext(o->ptr,p);
             }
-        } else if (o->encoding == REDIS_ENCODING_LIST) {
+        } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) {
             list *list = o->ptr;
             listIter li;
             listNode *ln;
@@ -4154,12 +4171,24 @@ static robj *rdbLoadObject(int type, FILE *fp) {
         /* Read list value */
         if ((len = rdbLoadLen(fp,NULL)) == REDIS_RDB_LENERR) return NULL;
 
-        o = createZiplistObject();
+        /* Use a real list when there are too many entries */
+        if (len > server.list_max_ziplist_entries) {
+            o = createListObject();
+        } else {
+            o = createZiplistObject();
+        }
 
         /* Load every single element of the list */
         while(len--) {
             if ((ele = rdbLoadEncodedStringObject(fp)) == NULL) return NULL;
 
+            /* If we are using a ziplist and the value is too big, convert
+             * the object to a real list. */
+            if (o->encoding == REDIS_ENCODING_ZIPLIST &&
+                ele->encoding == REDIS_ENCODING_RAW &&
+                sdslen(ele->ptr) > server.list_max_ziplist_value)
+                    listTypeConvert(o,REDIS_ENCODING_LINKEDLIST);
+
             if (o->encoding == REDIS_ENCODING_ZIPLIST) {
                 dec = getDecodedObject(ele);
                 o->ptr = ziplistPush(o->ptr,dec->ptr,sdslen(dec->ptr),REDIS_TAIL);
@@ -4168,7 +4197,6 @@ static robj *rdbLoadObject(int type, FILE *fp) {
             } else {
                 ele = tryObjectEncoding(ele);
                 listAddNodeTail(o->ptr,ele);
-                incrRefCount(ele);
             }
         }
     } else if (type == REDIS_SET) {
@@ -4218,23 +4246,31 @@ static robj *rdbLoadObject(int type, FILE *fp) {
         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 &&
-               (sdslen(key->ptr) > server.hash_max_zipmap_value ||
-                sdslen(val->ptr) > server.hash_max_zipmap_value))
+               ((key->encoding == REDIS_ENCODING_RAW &&
+                sdslen(key->ptr) > server.hash_max_zipmap_value) ||
+                (val->encoding == REDIS_ENCODING_RAW &&
+                sdslen(val->ptr) > server.hash_max_zipmap_value)))
             {
                     convertToRealHash(o);
             }
 
             if (o->encoding == REDIS_ENCODING_ZIPMAP) {
                 unsigned char *zm = o->ptr;
+                robj *deckey, *decval;
 
-                zm = zipmapSet(zm,key->ptr,sdslen(key->ptr),
-                                  val->ptr,sdslen(val->ptr),NULL);
+                /* We need raw string objects to add them to the zipmap */
+                deckey = getDecodedObject(key);
+                decval = getDecodedObject(val);
+                zm = zipmapSet(zm,deckey->ptr,sdslen(deckey->ptr),
+                                  decval->ptr,sdslen(decval->ptr),NULL);
                 o->ptr = zm;
+                decrRefCount(deckey);
+                decrRefCount(decval);
                 decrRefCount(key);
                 decrRefCount(val);
             } else {
@@ -4882,13 +4918,31 @@ static void moveCommand(redisClient *c) {
 }
 
 /* =================================== Lists ================================ */
-static void lPush(robj *subject, robj *value, int where) {
+
+
+/* Check the argument length to see if it requires us to convert the ziplist
+ * to a real list. Only check raw-encoded objects because integer encoded
+ * objects are never too long. */
+static void listTypeTryConversion(robj *subject, robj *value) {
+    if (subject->encoding != REDIS_ENCODING_ZIPLIST) return;
+    if (value->encoding == REDIS_ENCODING_RAW &&
+        sdslen(value->ptr) > server.list_max_ziplist_value)
+            listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
+}
+
+static void listTypePush(robj *subject, robj *value, int where) {
+    /* 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)
+            listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);
+
     if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
         int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
         value = getDecodedObject(value);
         subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),pos);
         decrRefCount(value);
-    } else if (subject->encoding == REDIS_ENCODING_LIST) {
+    } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
         if (where == REDIS_HEAD) {
             listAddNodeHead(subject->ptr,value);
         } else {
@@ -4900,7 +4954,7 @@ static void lPush(robj *subject, robj *value, int where) {
     }
 }
 
-static robj *lPop(robj *subject, int where) {
+static robj *listTypePop(robj *subject, int where) {
     robj *value = NULL;
     if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
         unsigned char *p;
@@ -4918,7 +4972,7 @@ static robj *lPop(robj *subject, int where) {
             /* We only need to delete an element when it exists */
             subject->ptr = ziplistDelete(subject->ptr,&p);
         }
-    } else if (subject->encoding == REDIS_ENCODING_LIST) {
+    } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
         list *list = subject->ptr;
         listNode *ln;
         if (where == REDIS_HEAD) {
@@ -4937,10 +4991,10 @@ static robj *lPop(robj *subject, int where) {
     return value;
 }
 
-static unsigned long lLength(robj *subject) {
+static unsigned long listTypeLength(robj *subject) {
     if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
         return ziplistLen(subject->ptr);
-    } else if (subject->encoding == REDIS_ENCODING_LIST) {
+    } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
         return listLength((list*)subject->ptr);
     } else {
         redisPanic("Unknown list encoding");
@@ -4954,24 +5008,24 @@ typedef struct {
     unsigned char direction; /* Iteration direction */
     unsigned char *zi;
     listNode *ln;
-} lIterator;
+} listTypeIterator;
 
 /* Structure for an entry while iterating over a list. */
 typedef struct {
-    lIterator *li;
+    listTypeIterator *li;
     unsigned char *zi;  /* Entry in ziplist */
     listNode *ln;       /* Entry in linked list */
-} lEntry;
+} listTypeEntry;
 
 /* Initialize an iterator at the specified index. */
-static lIterator *lInitIterator(robj *subject, int index, unsigned char direction) {
-    lIterator *li = zmalloc(sizeof(lIterator));
+static listTypeIterator *listTypeInitIterator(robj *subject, int index, unsigned char direction) {
+    listTypeIterator *li = zmalloc(sizeof(listTypeIterator));
     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) {
+    } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) {
         li->ln = listIndex(subject->ptr,index);
     } else {
         redisPanic("Unknown list encoding");
@@ -4980,14 +5034,17 @@ static lIterator *lInitIterator(robj *subject, int index, unsigned char directio
 }
 
 /* Clean up the iterator. */
-static void lReleaseIterator(lIterator *li) {
+static void listTypeReleaseIterator(listTypeIterator *li) {
     zfree(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) {
+static int listTypeNext(listTypeIterator *li, listTypeEntry *entry) {
+    /* Protect from converting when iterating */
+    redisAssert(li->subject->encoding == li->encoding);
+
     entry->li = li;
     if (li->encoding == REDIS_ENCODING_ZIPLIST) {
         entry->zi = li->zi;
@@ -4998,7 +5055,7 @@ static int lNext(lIterator *li, lEntry *entry) {
                 li->zi = ziplistPrev(li->subject->ptr,li->zi);
             return 1;
         }
-    } else if (li->encoding == REDIS_ENCODING_LIST) {
+    } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) {
         entry->ln = li->ln;
         if (entry->ln != NULL) {
             if (li->direction == REDIS_TAIL)
@@ -5014,8 +5071,8 @@ static int lNext(lIterator *li, lEntry *entry) {
 }
 
 /* Return entry or NULL at the current position of the iterator. */
-static robj *lGet(lEntry *entry) {
-    lIterator *li = entry->li;
+static robj *listTypeGet(listTypeEntry *entry) {
+    listTypeIterator *li = entry->li;
     robj *value = NULL;
     if (li->encoding == REDIS_ENCODING_ZIPLIST) {
         unsigned char *vstr;
@@ -5029,7 +5086,7 @@ static robj *lGet(lEntry *entry) {
                 value = createStringObjectFromLongLong(vlong);
             }
         }
-    } else if (li->encoding == REDIS_ENCODING_LIST) {
+    } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) {
         redisAssert(entry->ln != NULL);
         value = listNodeValue(entry->ln);
         incrRefCount(value);
@@ -5039,13 +5096,43 @@ static robj *lGet(lEntry *entry) {
     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_LINKEDLIST) {
+        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 lEqual(lEntry *entry, robj *o) {
-    lIterator *li = entry->li;
+static int listTypeEqual(listTypeEntry *entry, robj *o) {
+    listTypeIterator *li = entry->li;
     if (li->encoding == REDIS_ENCODING_ZIPLIST) {
         redisAssert(o->encoding == REDIS_ENCODING_RAW);
         return ziplistCompare(entry->zi,o->ptr,sdslen(o->ptr));
-    } else if (li->encoding == REDIS_ENCODING_LIST) {
+    } else if (li->encoding == REDIS_ENCODING_LINKEDLIST) {
         return equalStringObjects(o,listNodeValue(entry->ln));
     } else {
         redisPanic("Unknown list encoding");
@@ -5053,8 +5140,8 @@ static int lEqual(lEntry *entry, robj *o) {
 }
 
 /* Delete the element pointed to. */
-static void lDelete(lEntry *entry) {
-    lIterator *li = entry->li;
+static void listTypeDelete(listTypeEntry *entry) {
+    listTypeIterator *li = entry->li;
     if (li->encoding == REDIS_ENCODING_ZIPLIST) {
         unsigned char *p = entry->zi;
         li->subject->ptr = ziplistDelete(li->subject->ptr,&p);
@@ -5064,7 +5151,7 @@ static void lDelete(lEntry *entry) {
             li->zi = p;
         else
             li->zi = ziplistPrev(li->subject->ptr,p);
-    } else if (entry->li->encoding == REDIS_ENCODING_LIST) {
+    } else if (entry->li->encoding == REDIS_ENCODING_LINKEDLIST) {
         listNode *next;
         if (li->direction == REDIS_TAIL)
             next = entry->ln->next;
@@ -5077,6 +5164,28 @@ static void lDelete(lEntry *entry) {
     }
 }
 
+static void listTypeConvert(robj *subject, int enc) {
+    listTypeIterator *li;
+    listTypeEntry entry;
+    redisAssert(subject->type == REDIS_LIST);
+
+    if (enc == REDIS_ENCODING_LINKEDLIST) {
+        list *l = listCreate();
+        listSetFreeMethod(l,decrRefCount);
+
+        /* listTypeGet returns a robj with incremented refcount */
+        li = listTypeInitIterator(subject,0,REDIS_TAIL);
+        while (listTypeNext(li,&entry)) listAddNodeTail(l,listTypeGet(&entry));
+        listTypeReleaseIterator(li);
+
+        subject->encoding = REDIS_ENCODING_LINKEDLIST;
+        zfree(subject->ptr);
+        subject->ptr = l;
+    } else {
+        redisPanic("Unsupported list conversion");
+    }
+}
+
 static void pushGenericCommand(redisClient *c, int where) {
     robj *lobj = lookupKeyWrite(c->db,c->argv[1]);
     if (lobj == NULL) {
@@ -5096,8 +5205,8 @@ static void pushGenericCommand(redisClient *c, int where) {
             return;
         }
     }
-    lPush(lobj,c->argv[2],where);
-    addReplyLongLong(c,lLength(lobj));
+    listTypePush(lobj,c->argv[2],where);
+    addReplyLongLong(c,listTypeLength(lobj));
     server.dirty++;
 }
 
@@ -5109,10 +5218,79 @@ 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_LINKEDLIST);
+            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;
-    addReplyUlong(c,lLength(o));
+    addReplyUlong(c,listTypeLength(o));
 }
 
 static void lindexCommand(redisClient *c) {
@@ -5138,7 +5316,7 @@ static void lindexCommand(redisClient *c) {
         } else {
             addReply(c,shared.nullbulk);
         }
-    } else if (o->encoding == REDIS_ENCODING_LIST) {
+    } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) {
         listNode *ln = listIndex(o->ptr,index);
         if (ln != NULL) {
             value = listNodeValue(ln);
@@ -5157,6 +5335,7 @@ static void lsetCommand(redisClient *c) {
     int index = atoi(c->argv[2]->ptr);
     robj *value = c->argv[3];
 
+    listTypeTryConversion(o,value);
     if (o->encoding == REDIS_ENCODING_ZIPLIST) {
         unsigned char *p, *zl = o->ptr;
         p = ziplistIndex(zl,index);
@@ -5170,7 +5349,7 @@ static void lsetCommand(redisClient *c) {
             addReply(c,shared.ok);
             server.dirty++;
         }
-    } else if (o->encoding == REDIS_ENCODING_LIST) {
+    } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) {
         listNode *ln = listIndex(o->ptr,index);
         if (ln == NULL) {
             addReply(c,shared.outofrangeerr);
@@ -5190,13 +5369,13 @@ static void popGenericCommand(redisClient *c, int where) {
     robj *o = lookupKeyWriteOrReply(c,c->argv[1],shared.nullbulk);
     if (o == NULL || checkType(c,o,REDIS_LIST)) return;
 
-    robj *value = lPop(o,where);
+    robj *value = listTypePop(o,where);
     if (value == NULL) {
         addReply(c,shared.nullbulk);
     } else {
         addReplyBulk(c,value);
         decrRefCount(value);
-        if (lLength(o) == 0) dbDelete(c->db,c->argv[1]);
+        if (listTypeLength(o) == 0) dbDelete(c->db,c->argv[1]);
         server.dirty++;
     }
 }
@@ -5215,19 +5394,19 @@ static void lrangeCommand(redisClient *c) {
     int end = atoi(c->argv[3]->ptr);
     int llen;
     int rangelen, j;
-    lEntry entry;
+    listTypeEntry entry;
 
     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptymultibulk)) == NULL
          || checkType(c,o,REDIS_LIST)) return;
-    llen = lLength(o);
+    llen = listTypeLength(o);
 
     /* convert negative indexes */
     if (start < 0) start = llen+start;
     if (end < 0) end = llen+end;
     if (start < 0) start = 0;
-    if (end < 0) end = 0;
 
-    /* indexes sanity checks */
+    /* Invariant: start >= 0, so this test will be true when end < 0.
+     * The range is empty when start > end or start >= length. */
     if (start > end || start >= llen) {
         /* Out of range start or start > end result in empty list */
         addReply(c,shared.emptymultibulk);
@@ -5238,14 +5417,14 @@ 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,REDIS_TAIL);
+    listTypeIterator *li = listTypeInitIterator(o,start,REDIS_TAIL);
     for (j = 0; j < rangelen; j++) {
-        redisAssert(lNext(li,&entry));
-        value = lGet(&entry);
+        redisAssert(listTypeNext(li,&entry));
+        value = listTypeGet(&entry);
         addReplyBulk(c,value);
         decrRefCount(value);
     }
-    lReleaseIterator(li);
+    listTypeReleaseIterator(li);
 }
 
 static void ltrimCommand(redisClient *c) {
@@ -5259,15 +5438,15 @@ static void ltrimCommand(redisClient *c) {
 
     if ((o = lookupKeyWriteOrReply(c,c->argv[1],shared.ok)) == NULL ||
         checkType(c,o,REDIS_LIST)) return;
-    llen = lLength(o);
+    llen = listTypeLength(o);
 
     /* convert negative indexes */
     if (start < 0) start = llen+start;
     if (end < 0) end = llen+end;
     if (start < 0) start = 0;
-    if (end < 0) end = 0;
 
-    /* indexes sanity checks */
+    /* Invariant: start >= 0, so this test will be true when end < 0.
+     * The range is empty when start > end or start >= length. */
     if (start > end || start >= llen) {
         /* Out of range start or start > end result in empty list */
         ltrim = llen;
@@ -5282,7 +5461,7 @@ static void ltrimCommand(redisClient *c) {
     if (o->encoding == REDIS_ENCODING_ZIPLIST) {
         o->ptr = ziplistDeleteRange(o->ptr,0,ltrim);
         o->ptr = ziplistDeleteRange(o->ptr,-rtrim,rtrim);
-    } else if (o->encoding == REDIS_ENCODING_LIST) {
+    } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) {
         list = o->ptr;
         for (j = 0; j < ltrim; j++) {
             ln = listFirst(list);
@@ -5295,7 +5474,7 @@ static void ltrimCommand(redisClient *c) {
     } else {
         redisPanic("Unknown list encoding");
     }
-    if (lLength(o) == 0) dbDelete(c->db,c->argv[1]);
+    if (listTypeLength(o) == 0) dbDelete(c->db,c->argv[1]);
     server.dirty++;
     addReply(c,shared.ok);
 }
@@ -5304,7 +5483,7 @@ static void lremCommand(redisClient *c) {
     robj *subject, *obj = c->argv[3];
     int toremove = atoi(c->argv[2]->ptr);
     int removed = 0;
-    lEntry entry;
+    listTypeEntry entry;
 
     subject = lookupKeyWriteOrReply(c,c->argv[1],shared.czero);
     if (subject == NULL || checkType(c,subject,REDIS_LIST)) return;
@@ -5313,29 +5492,29 @@ static void lremCommand(redisClient *c) {
     if (subject->encoding == REDIS_ENCODING_ZIPLIST)
         obj = getDecodedObject(obj);
 
-    lIterator *li;
+    listTypeIterator *li;
     if (toremove < 0) {
         toremove = -toremove;
-        li = lInitIterator(subject,-1,REDIS_HEAD);
+        li = listTypeInitIterator(subject,-1,REDIS_HEAD);
     } else {
-        li = lInitIterator(subject,0,REDIS_TAIL);
+        li = listTypeInitIterator(subject,0,REDIS_TAIL);
     }
 
-    while (lNext(li,&entry)) {
-        if (lEqual(&entry,obj)) {
-            lDelete(&entry);
+    while (listTypeNext(li,&entry)) {
+        if (listTypeEqual(&entry,obj)) {
+            listTypeDelete(&entry);
             server.dirty++;
             removed++;
             if (toremove && removed == toremove) break;
         }
     }
-    lReleaseIterator(li);
+    listTypeReleaseIterator(li);
 
     /* Clean up raw encoded object */
     if (subject->encoding == REDIS_ENCODING_ZIPLIST)
         decrRefCount(obj);
 
-    if (lLength(subject) == 0) dbDelete(c->db,c->argv[1]);
+    if (listTypeLength(subject) == 0) dbDelete(c->db,c->argv[1]);
     addReplySds(c,sdscatprintf(sdsempty(),":%d\r\n",removed));
 }
 
@@ -5359,12 +5538,12 @@ static void rpoplpushcommand(redisClient *c) {
     if ((sobj = lookupKeyWriteOrReply(c,c->argv[1],shared.nullbulk)) == NULL ||
         checkType(c,sobj,REDIS_LIST)) return;
 
-    if (lLength(sobj) == 0) {
+    if (listTypeLength(sobj) == 0) {
         addReply(c,shared.nullbulk);
     } else {
         robj *dobj = lookupKeyWrite(c->db,c->argv[2]);
         if (dobj && checkType(c,dobj,REDIS_LIST)) return;
-        value = lPop(sobj,REDIS_TAIL);
+        value = listTypePop(sobj,REDIS_TAIL);
 
         /* Add the element to the target list (unless it's directly
          * passed to some BLPOP-ing client */
@@ -5374,17 +5553,17 @@ static void rpoplpushcommand(redisClient *c) {
                 dobj = createZiplistObject();
                 dbAdd(c->db,c->argv[2],dobj);
             }
-            lPush(dobj,value,REDIS_HEAD);
+            listTypePush(dobj,value,REDIS_HEAD);
         }
 
         /* Send the element to the client as reply as well */
         addReplyBulk(c,value);
 
-        /* lPop returns an object with its refcount incremented */
+        /* listTypePop returns an object with its refcount incremented */
         decrRefCount(value);
 
         /* Delete the source list when it is empty */
-        if (lLength(sobj) == 0) dbDelete(c->db,c->argv[1]);
+        if (listTypeLength(sobj) == 0) dbDelete(c->db,c->argv[1]);
         server.dirty++;
     }
 }
@@ -6007,7 +6186,7 @@ static zskiplistNode *zslFirstWithScore(zskiplist *zsl, double score) {
  * 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) {
+static unsigned long zslistTypeGetRank(zskiplist *zsl, double score, robj *o) {
     zskiplistNode *x;
     unsigned long rank = 0;
     int i;
@@ -6031,7 +6210,7 @@ static unsigned long zslGetRank(zskiplist *zsl, double score, robj *o) {
 }
 
 /* Finds an element by its rank. The rank argument needs to be 1-based. */
-zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank) {
+zskiplistNode* zslistTypeGetElementByRank(zskiplist *zsl, unsigned long rank) {
     zskiplistNode *x;
     unsigned long traversed = 0;
     int i;
@@ -6230,9 +6409,9 @@ static void zremrangebyrankCommand(redisClient *c) {
     if (start < 0) start = llen+start;
     if (end < 0) end = llen+end;
     if (start < 0) start = 0;
-    if (end < 0) end = 0;
 
-    /* indexes sanity checks */
+    /* Invariant: start >= 0, so this test will be true when end < 0.
+     * The range is empty when start > end or start >= length. */
     if (start > end || start >= llen) {
         addReply(c,shared.czero);
         return;
@@ -6483,11 +6662,10 @@ static void zrangeGenericCommand(redisClient *c, int reverse) {
     if (start < 0) start = llen+start;
     if (end < 0) end = llen+end;
     if (start < 0) start = 0;
-    if (end < 0) end = 0;
 
-    /* indexes sanity checks */
+    /* Invariant: start >= 0, so this test will be true when end < 0.
+     * The range is empty when start > end or start >= length. */
     if (start > end || start >= llen) {
-        /* Out of range start or start > end result in empty list */
         addReply(c,shared.emptymultibulk);
         return;
     }
@@ -6497,10 +6675,10 @@ static void zrangeGenericCommand(redisClient *c, int reverse) {
     /* check if starting point is trivial, before searching
      * the element in log(N) time */
     if (reverse) {
-        ln = start == 0 ? zsl->tail : zslGetElementByRank(zsl, llen-start);
+        ln = start == 0 ? zsl->tail : zslistTypeGetElementByRank(zsl, llen-start);
     } else {
         ln = start == 0 ?
-            zsl->header->forward[0] : zslGetElementByRank(zsl, start+1);
+            zsl->header->forward[0] : zslistTypeGetElementByRank(zsl, start+1);
     }
 
     /* Return the result in form of a multi-bulk reply */
@@ -6697,7 +6875,7 @@ static void zrankGenericCommand(redisClient *c, int reverse) {
     }
 
     score = dictGetEntryVal(de);
-    rank = zslGetRank(zsl, *score, c->argv[2]);
+    rank = zslistTypeGetRank(zsl, *score, c->argv[2]);
     if (rank) {
         if (reverse) {
             addReplyLongLong(c, zsl->length - rank);
@@ -6724,7 +6902,7 @@ static void zrevrankCommand(redisClient *c) {
 /* Check the length of a number of objects to see if we need to convert a
  * zipmap to a real hash. Note that we only check string encoded objects
  * as their string length can be queried in constant time. */
-static void hashTryConversion(robj *subject, robj **argv, int start, int end) {
+static void hashTypeTryConversion(robj *subject, robj **argv, int start, int end) {
     int i;
     if (subject->encoding != REDIS_ENCODING_ZIPMAP) return;
 
@@ -6739,7 +6917,7 @@ static void hashTryConversion(robj *subject, robj **argv, int start, int end) {
 }
 
 /* Encode given objects in-place when the hash uses a dict. */
-static void hashTryObjectEncoding(robj *subject, robj **o1, robj **o2) {
+static void hashTypeTryObjectEncoding(robj *subject, robj **o1, robj **o2) {
     if (subject->encoding == REDIS_ENCODING_HT) {
         if (o1) *o1 = tryObjectEncoding(*o1);
         if (o2) *o2 = tryObjectEncoding(*o2);
@@ -6749,7 +6927,7 @@ static void hashTryObjectEncoding(robj *subject, robj **o1, robj **o2) {
 /* Get the value from a hash identified by key. Returns either a string
  * object or NULL if the value cannot be found. The refcount of the object
  * is always increased by 1 when the value was found. */
-static robj *hashGet(robj *o, robj *key) {
+static robj *hashTypeGet(robj *o, robj *key) {
     robj *value = NULL;
     if (o->encoding == REDIS_ENCODING_ZIPMAP) {
         unsigned char *v;
@@ -6771,7 +6949,7 @@ static robj *hashGet(robj *o, robj *key) {
 
 /* Test if the key exists in the given hash. Returns 1 if the key
  * exists and 0 when it doesn't. */
-static int hashExists(robj *o, robj *key) {
+static int hashTypeExists(robj *o, robj *key) {
     if (o->encoding == REDIS_ENCODING_ZIPMAP) {
         key = getDecodedObject(key);
         if (zipmapExists(o->ptr,key->ptr,sdslen(key->ptr))) {
@@ -6789,7 +6967,7 @@ static int hashExists(robj *o, robj *key) {
 
 /* Add an element, discard the old if the key already exists.
  * Return 0 on insert and 1 on update. */
-static int hashSet(robj *o, robj *key, robj *value) {
+static int hashTypeSet(robj *o, robj *key, robj *value) {
     int update = 0;
     if (o->encoding == REDIS_ENCODING_ZIPMAP) {
         key = getDecodedObject(key);
@@ -6818,7 +6996,7 @@ static int hashSet(robj *o, robj *key, robj *value) {
 
 /* Delete an element from a hash.
  * Return 1 on deleted and 0 on not found. */
-static int hashDelete(robj *o, robj *key) {
+static int hashTypeDelete(robj *o, robj *key) {
     int deleted = 0;
     if (o->encoding == REDIS_ENCODING_ZIPMAP) {
         key = getDecodedObject(key);
@@ -6833,7 +7011,7 @@ static int hashDelete(robj *o, robj *key) {
 }
 
 /* Return the number of elements in a hash. */
-static unsigned long hashLength(robj *o) {
+static unsigned long hashTypeLength(robj *o) {
     return (o->encoding == REDIS_ENCODING_ZIPMAP) ?
         zipmapLen((unsigned char*)o->ptr) : dictSize((dict*)o->ptr);
 }
@@ -6850,10 +7028,10 @@ typedef struct {
 
     dictIterator *di;
     dictEntry *de;
-} hashIterator;
+} hashTypeIterator;
 
-static hashIterator *hashInitIterator(robj *subject) {
-    hashIterator *hi = zmalloc(sizeof(hashIterator));
+static hashTypeIterator *hashTypeInitIterator(robj *subject) {
+    hashTypeIterator *hi = zmalloc(sizeof(hashTypeIterator));
     hi->encoding = subject->encoding;
     if (hi->encoding == REDIS_ENCODING_ZIPMAP) {
         hi->zi = zipmapRewind(subject->ptr);
@@ -6865,7 +7043,7 @@ static hashIterator *hashInitIterator(robj *subject) {
     return hi;
 }
 
-static void hashReleaseIterator(hashIterator *hi) {
+static void hashTypeReleaseIterator(hashTypeIterator *hi) {
     if (hi->encoding == REDIS_ENCODING_HT) {
         dictReleaseIterator(hi->di);
     }
@@ -6874,7 +7052,7 @@ static void hashReleaseIterator(hashIterator *hi) {
 
 /* Move to the next entry in the hash. Return REDIS_OK when the next entry
  * could be found and REDIS_ERR when the iterator reaches the end. */
-static int hashNext(hashIterator *hi) {
+static int hashTypeNext(hashTypeIterator *hi) {
     if (hi->encoding == REDIS_ENCODING_ZIPMAP) {
         if ((hi->zi = zipmapNext(hi->zi, &hi->zk, &hi->zklen,
             &hi->zv, &hi->zvlen)) == NULL) return REDIS_ERR;
@@ -6886,7 +7064,7 @@ static int hashNext(hashIterator *hi) {
 
 /* Get key or value object at current iteration position.
  * This increases the refcount of the field object by 1. */
-static robj *hashCurrent(hashIterator *hi, int what) {
+static robj *hashTypeCurrent(hashTypeIterator *hi, int what) {
     robj *o;
     if (hi->encoding == REDIS_ENCODING_ZIPMAP) {
         if (what & REDIS_HASH_KEY) {
@@ -6905,7 +7083,7 @@ static robj *hashCurrent(hashIterator *hi, int what) {
     return o;
 }
 
-static robj *hashLookupWriteOrCreate(redisClient *c, robj *key) {
+static robj *hashTypeLookupWriteOrCreate(redisClient *c, robj *key) {
     robj *o = lookupKeyWrite(c->db,key);
     if (o == NULL) {
         o = createHashObject();
@@ -6924,24 +7102,24 @@ static void hsetCommand(redisClient *c) {
     int update;
     robj *o;
 
-    if ((o = hashLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
-    hashTryConversion(o,c->argv,2,3);
-    hashTryObjectEncoding(o,&c->argv[2], &c->argv[3]);
-    update = hashSet(o,c->argv[2],c->argv[3]);
+    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
+    hashTypeTryConversion(o,c->argv,2,3);
+    hashTypeTryObjectEncoding(o,&c->argv[2], &c->argv[3]);
+    update = hashTypeSet(o,c->argv[2],c->argv[3]);
     addReply(c, update ? shared.czero : shared.cone);
     server.dirty++;
 }
 
 static void hsetnxCommand(redisClient *c) {
     robj *o;
-    if ((o = hashLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
-    hashTryConversion(o,c->argv,2,3);
+    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
+    hashTypeTryConversion(o,c->argv,2,3);
 
-    if (hashExists(o, c->argv[2])) {
+    if (hashTypeExists(o, c->argv[2])) {
         addReply(c, shared.czero);
     } else {
-        hashTryObjectEncoding(o,&c->argv[2], &c->argv[3]);
-        hashSet(o,c->argv[2],c->argv[3]);
+        hashTypeTryObjectEncoding(o,&c->argv[2], &c->argv[3]);
+        hashTypeSet(o,c->argv[2],c->argv[3]);
         addReply(c, shared.cone);
         server.dirty++;
     }
@@ -6956,11 +7134,11 @@ static void hmsetCommand(redisClient *c) {
         return;
     }
 
-    if ((o = hashLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
-    hashTryConversion(o,c->argv,2,c->argc-1);
+    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
+    hashTypeTryConversion(o,c->argv,2,c->argc-1);
     for (i = 2; i < c->argc; i += 2) {
-        hashTryObjectEncoding(o,&c->argv[i], &c->argv[i+1]);
-        hashSet(o,c->argv[i],c->argv[i+1]);
+        hashTypeTryObjectEncoding(o,&c->argv[i], &c->argv[i+1]);
+        hashTypeSet(o,c->argv[i],c->argv[i+1]);
     }
     addReply(c, shared.ok);
     server.dirty++;
@@ -6971,8 +7149,8 @@ static void hincrbyCommand(redisClient *c) {
     robj *o, *current, *new;
 
     if (getLongLongFromObjectOrReply(c,c->argv[3],&incr,NULL) != REDIS_OK) return;
-    if ((o = hashLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
-    if ((current = hashGet(o,c->argv[2])) != NULL) {
+    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
+    if ((current = hashTypeGet(o,c->argv[2])) != NULL) {
         if (getLongLongFromObjectOrReply(c,current,&value,
             "hash value is not an integer") != REDIS_OK) {
             decrRefCount(current);
@@ -6985,8 +7163,8 @@ static void hincrbyCommand(redisClient *c) {
 
     value += incr;
     new = createStringObjectFromLongLong(value);
-    hashTryObjectEncoding(o,&c->argv[2],NULL);
-    hashSet(o,c->argv[2],new);
+    hashTypeTryObjectEncoding(o,&c->argv[2],NULL);
+    hashTypeSet(o,c->argv[2],new);
     decrRefCount(new);
     addReplyLongLong(c,value);
     server.dirty++;
@@ -6997,7 +7175,7 @@ static void hgetCommand(redisClient *c) {
     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.nullbulk)) == NULL ||
         checkType(c,o,REDIS_HASH)) return;
 
-    if ((value = hashGet(o,c->argv[2])) != NULL) {
+    if ((value = hashTypeGet(o,c->argv[2])) != NULL) {
         addReplyBulk(c,value);
         decrRefCount(value);
     } else {
@@ -7018,7 +7196,7 @@ static void hmgetCommand(redisClient *c) {
      * an empty hash. The reply should then be a series of NULLs. */
     addReplySds(c,sdscatprintf(sdsempty(),"*%d\r\n",c->argc-2));
     for (i = 2; i < c->argc; i++) {
-        if (o != NULL && (value = hashGet(o,c->argv[i])) != NULL) {
+        if (o != NULL && (value = hashTypeGet(o,c->argv[i])) != NULL) {
             addReplyBulk(c,value);
             decrRefCount(value);
         } else {
@@ -7032,8 +7210,8 @@ static void hdelCommand(redisClient *c) {
     if ((o = lookupKeyWriteOrReply(c,c->argv[1],shared.czero)) == NULL ||
         checkType(c,o,REDIS_HASH)) return;
 
-    if (hashDelete(o,c->argv[2])) {
-        if (hashLength(o) == 0) dbDelete(c->db,c->argv[1]);
+    if (hashTypeDelete(o,c->argv[2])) {
+        if (hashTypeLength(o) == 0) dbDelete(c->db,c->argv[1]);
         addReply(c,shared.cone);
         server.dirty++;
     } else {
@@ -7046,13 +7224,13 @@ static void hlenCommand(redisClient *c) {
     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
         checkType(c,o,REDIS_HASH)) return;
 
-    addReplyUlong(c,hashLength(o));
+    addReplyUlong(c,hashTypeLength(o));
 }
 
 static void genericHgetallCommand(redisClient *c, int flags) {
     robj *o, *lenobj, *obj;
     unsigned long count = 0;
-    hashIterator *hi;
+    hashTypeIterator *hi;
 
     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptymultibulk)) == NULL
         || checkType(c,o,REDIS_HASH)) return;
@@ -7061,22 +7239,22 @@ static void genericHgetallCommand(redisClient *c, int flags) {
     addReply(c,lenobj);
     decrRefCount(lenobj);
 
-    hi = hashInitIterator(o);
-    while (hashNext(hi) != REDIS_ERR) {
+    hi = hashTypeInitIterator(o);
+    while (hashTypeNext(hi) != REDIS_ERR) {
         if (flags & REDIS_HASH_KEY) {
-            obj = hashCurrent(hi,REDIS_HASH_KEY);
+            obj = hashTypeCurrent(hi,REDIS_HASH_KEY);
             addReplyBulk(c,obj);
             decrRefCount(obj);
             count++;
         }
         if (flags & REDIS_HASH_VALUE) {
-            obj = hashCurrent(hi,REDIS_HASH_VALUE);
+            obj = hashTypeCurrent(hi,REDIS_HASH_VALUE);
             addReplyBulk(c,obj);
             decrRefCount(obj);
             count++;
         }
     }
-    hashReleaseIterator(hi);
+    hashTypeReleaseIterator(hi);
 
     lenobj->ptr = sdscatprintf(sdsempty(),"*%lu\r\n",count);
 }
@@ -7098,7 +7276,7 @@ static void hexistsCommand(redisClient *c) {
     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
         checkType(c,o,REDIS_HASH)) return;
 
-    addReply(c, hashExists(o,c->argv[2]) ? shared.cone : shared.czero);
+    addReply(c, hashTypeExists(o,c->argv[2]) ? shared.cone : shared.czero);
 }
 
 static void convertToRealHash(robj *o) {
@@ -7219,7 +7397,7 @@ static robj *lookupKeyByPattern(redisDb *db, robj *pattern, robj *subst) {
         /* Retrieve value from hash by the field name. This operation
          * already increases the refcount of the returned object. */
         initStaticStringObject(fieldobj,((char*)&fieldname)+(sizeof(long)*2));
-        o = hashGet(o, &fieldobj);
+        o = hashTypeGet(o, &fieldobj);
     } else {
         if (o->type != REDIS_STRING) return NULL;
 
@@ -7344,7 +7522,7 @@ static void sortCommand(redisClient *c) {
 
     /* Load the sorting vector with all the objects to sort */
     switch(sortval->type) {
-    case REDIS_LIST: vectorlen = lLength(sortval); break;
+    case REDIS_LIST: vectorlen = listTypeLength(sortval); break;
     case REDIS_SET: vectorlen =  dictSize((dict*)sortval->ptr); break;
     case REDIS_ZSET: vectorlen = dictSize(((zset*)sortval->ptr)->dict); break;
     default: vectorlen = 0; redisPanic("Bad SORT type"); /* Avoid GCC warning */
@@ -7353,15 +7531,15 @@ static void sortCommand(redisClient *c) {
     j = 0;
 
     if (sortval->type == REDIS_LIST) {
-        lIterator *li = lInitIterator(sortval,0,REDIS_TAIL);
-        lEntry entry;
-        while(lNext(li,&entry)) {
-            vector[j].obj = lGet(&entry);
+        listTypeIterator *li = listTypeInitIterator(sortval,0,REDIS_TAIL);
+        listTypeEntry entry;
+        while(listTypeNext(li,&entry)) {
+            vector[j].obj = listTypeGet(&entry);
             vector[j].u.score = 0;
             vector[j].u.cmpobj = NULL;
             j++;
         }
-        lReleaseIterator(li);
+        listTypeReleaseIterator(li);
     } else {
         dict *set;
         dictIterator *di;
@@ -7479,7 +7657,7 @@ static void sortCommand(redisClient *c) {
             listIter li;
 
             if (!getop) {
-                lPush(sobj,vector[j].obj,REDIS_TAIL);
+                listTypePush(sobj,vector[j].obj,REDIS_TAIL);
             } else {
                 listRewind(operations,&li);
                 while((ln = listNext(&li))) {
@@ -7490,10 +7668,10 @@ static void sortCommand(redisClient *c) {
                     if (sop->type == REDIS_SORT_GET) {
                         if (!val) val = createStringObject("",0);
 
-                        /* lPush does an incrRefCount, so we should take care
+                        /* listTypePush does an incrRefCount, so we should take care
                          * care of the incremented refcount caused by either
                          * lookupKeyByPattern or createStringObject("",0) */
-                        lPush(sobj,val,REDIS_TAIL);
+                        listTypePush(sobj,val,REDIS_TAIL);
                         decrRefCount(val);
                     } else {
                         /* always fails */
@@ -7582,8 +7760,8 @@ static sds genRedisInfoString(void) {
         "vm_enabled:%d\r\n"
         "role:%s\r\n"
         ,REDIS_VERSION,
-        REDIS_GIT_SHA1,
-        strtol(REDIS_GIT_DIRTY,NULL,10) > 0,
+        redisGitSHA1(),
+        strtol(redisGitDirty(),NULL,10) > 0,
         (sizeof(long) == 8) ? "64" : "32",
         aeGetApiName(),
         (long) getpid(),
@@ -7684,6 +7862,9 @@ static void monitorCommand(redisClient *c) {
 
 /* ================================= Expire ================================= */
 static int removeExpire(redisDb *db, robj *key) {
+    /* An expire may only be removed if there is a corresponding entry in the
+     * main dict. Otherwise, the key will never be freed. */
+    redisAssert(dictFind(db->dict,key->ptr) != NULL);
     if (dictDelete(db->expires,key->ptr) == DICT_OK) {
         return 1;
     } else {
@@ -7692,9 +7873,11 @@ static int removeExpire(redisDb *db, robj *key) {
 }
 
 static int setExpire(redisDb *db, robj *key, time_t when) {
-    sds copy = sdsdup(key->ptr);
-    if (dictAdd(db->expires,copy,(void*)when) == DICT_ERR) {
-        sdsfree(copy);
+    dictEntry *de;
+
+    /* Reuse the sds from the main dict in the expire dict */
+    redisAssert((de = dictFind(db->dict,key->ptr)) != NULL);
+    if (dictAdd(db->expires,dictGetEntryKey(de),(void*)when) == DICT_ERR) {
         return 0;
     } else {
         return 1;
@@ -7710,39 +7893,32 @@ static time_t getExpire(redisDb *db, robj *key) {
     if (dictSize(db->expires) == 0 ||
        (de = dictFind(db->expires,key->ptr)) == NULL) return -1;
 
+    /* The entry was found in the expire dict, this means it should also
+     * be present in the main dict (safety check). */
+    redisAssert(dictFind(db->dict,key->ptr) != NULL);
     return (time_t) dictGetEntryVal(de);
 }
 
 static int expireIfNeeded(redisDb *db, robj *key) {
-    time_t when;
-    dictEntry *de;
-
-    /* No expire? return ASAP */
-    if (dictSize(db->expires) == 0 ||
-       (de = dictFind(db->expires,key->ptr)) == NULL) return 0;
+    time_t when = getExpire(db,key);
+    if (when < 0) return 0;
 
-    /* Lookup the expire */
-    when = (time_t) dictGetEntryVal(de);
+    /* Return when this key has not expired */
     if (time(NULL) <= when) return 0;
 
     /* Delete the key */
-    dbDelete(db,key);
     server.stat_expiredkeys++;
-    return 1;
+    server.dirty++;
+    return dbDelete(db,key);
 }
 
 static int deleteIfVolatile(redisDb *db, robj *key) {
-    dictEntry *de;
-
-    /* No expire? return ASAP */
-    if (dictSize(db->expires) == 0 ||
-       (de = dictFind(db->expires,key->ptr)) == NULL) return 0;
+    if (getExpire(db,key) < 0) return 0;
 
     /* Delete the key */
-    server.dirty++;
     server.stat_expiredkeys++;
-    dictDelete(db->expires,key->ptr);
-    return dictDelete(db->dict,key->ptr) == DICT_OK;
+    server.dirty++;
+    return dbDelete(db,key);
 }
 
 static void expireGenericCommand(redisClient *c, robj *key, robj *param, long offset) {
@@ -7852,6 +8028,7 @@ static void discardCommand(redisClient *c) {
     freeClientMultiState(c);
     initClientMultiState(c);
     c->flags &= (~REDIS_MULTI);
+    unwatchAllKeys(c);
     addReply(c,shared.ok);
 }
 
@@ -8973,7 +9150,7 @@ static int rewriteAppendOnlyFile(char *filename) {
                         }
                         p = ziplistNext(zl,p);
                     }
-                } else if (o->encoding == REDIS_ENCODING_LIST) {
+                } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) {
                     list *list = o->ptr;
                     listNode *ln;
                     listIter li;
@@ -9518,8 +9695,10 @@ static double computeObjectSwappability(robj *o) {
     /* 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;
@@ -9534,17 +9713,18 @@ static double computeObjectSwappability(robj *o) {
         }
         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:
@@ -9555,9 +9735,6 @@ static double computeObjectSwappability(robj *o) {
         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) ?
@@ -9582,9 +9759,6 @@ static double computeObjectSwappability(robj *o) {
             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) ?
@@ -11012,14 +11186,14 @@ static void computeDatasetDigest(unsigned char *final) {
             if (o->type == REDIS_STRING) {
                 mixObjectDigest(digest,o);
             } else if (o->type == REDIS_LIST) {
-                lIterator *li = lInitIterator(o,0,REDIS_TAIL);
-                lEntry entry;
-                while(lNext(li,&entry)) {
-                    robj *eleobj = lGet(&entry);
+                listTypeIterator *li = listTypeInitIterator(o,0,REDIS_TAIL);
+                listTypeEntry entry;
+                while(listTypeNext(li,&entry)) {
+                    robj *eleobj = listTypeGet(&entry);
                     mixObjectDigest(digest,eleobj);
                     decrRefCount(eleobj);
                 }
-                lReleaseIterator(li);
+                listTypeReleaseIterator(li);
             } else if (o->type == REDIS_SET) {
                 dict *set = o->ptr;
                 dictIterator *di = dictGetIterator(set);
@@ -11049,23 +11223,23 @@ static void computeDatasetDigest(unsigned char *final) {
                 }
                 dictReleaseIterator(di);
             } else if (o->type == REDIS_HASH) {
-                hashIterator *hi;
+                hashTypeIterator *hi;
                 robj *obj;
 
-                hi = hashInitIterator(o);
-                while (hashNext(hi) != REDIS_ERR) {
+                hi = hashTypeInitIterator(o);
+                while (hashTypeNext(hi) != REDIS_ERR) {
                     unsigned char eledigest[20];
 
                     memset(eledigest,0,20);
-                    obj = hashCurrent(hi,REDIS_HASH_KEY);
+                    obj = hashTypeCurrent(hi,REDIS_HASH_KEY);
                     mixObjectDigest(eledigest,obj);
                     decrRefCount(obj);
-                    obj = hashCurrent(hi,REDIS_HASH_VALUE);
+                    obj = hashTypeCurrent(hi,REDIS_HASH_VALUE);
                     mixObjectDigest(eledigest,obj);
                     decrRefCount(obj);
                     xorDigest(digest,eledigest,20);
                 }
-                hashReleaseIterator(hi);
+                hashTypeReleaseIterator(hi);
             } else {
                 redisPanic("Unknown object type");
             }
@@ -11268,7 +11442,7 @@ static void daemonize(void) {
 
 static void version() {
     printf("Redis server version %s (%s:%d)\n", REDIS_VERSION,
-        REDIS_GIT_SHA1, atoi(REDIS_GIT_DIRTY) > 0);
+        redisGitSHA1(), atoi(redisGitDirty()) > 0);
     exit(0);
 }