SPOP implemented. Hash table resizing for Sets and Expires too. Changed the resize...

diff --git a/dict.h b/dict.h
index 90d46f488d94d81d643401e236ea64117e6d34a4..bd935d5f4e75684acc2d3a2faa7474a03df4a2d0 100644 (file)
--- a/dict.h
+++ b/dict.h
@@ -73,7 +73,7 @@ typedef struct dictIterator {
 } dictIterator;
 
 /* This is the initial size of every hash table */
 } dictIterator;
 
 /* This is the initial size of every hash table */

-#define DICT_HT_INITIAL_SIZE     16
+#define DICT_HT_INITIAL_SIZE     4

 
 /* ------------------------------- Macros ------------------------------------*/
 #define dictFreeEntryVal(ht, entry) \
 
 /* ------------------------------- Macros ------------------------------------*/
 #define dictFreeEntryVal(ht, entry) \

diff --git a/doc/Credits.html b/doc/Credits.html
index e4e35fa432d23be0716bbc74b98839e71d8143f2..fefc44400390349a05e3930b5ddf922494240d48 100644 (file)
--- a/doc/Credits.html
+++ b/doc/Credits.html
@@ -26,7 +26,7 @@
                 </div>
 
                 <div class="narrow">
                 </div>
 
                 <div class="narrow">

-                    <h1><a name="Credits">Credits</a></h1><ul><li> The Redis server was designed and written by <a href="http://invece.org" target="_blank">Salvatore Sanfilippo (aka antirez)</a></li><li> <a href="http://brainspl.at/" target="_blank">Ezra Zygmuntowicz (aka ezmobius)</a> - Ruby client lib initial version and hacking</li><li> <a href="http://qix.it" target="_blank">Ludovico Magnocavallo (aka ludo)</a> - Python clinet lib</li><li> <a href="http://www.adroll.com/" target="_blank">Valentino Volonghi of Adroll</a> - Erlang client lib</li><li> <b>brettbender</b> - found and fixed a bug in sds.c that caused the server to crash at least on 64 bit systems, and anyway to be buggy since we used the same vararg thing against vsprintf without to call va_start and va_end every time.</li><li> <a href="http://www.rot13.org/~dpavlin" target="_blank">Dobrica Pavlinusic</a> - Perl client lib</li><li> Brian Hammond - AUTH command implementation, C++ client lib</li><li> <a href="http://www.clorophilla.net/" target="_blank">Daniele Alessandri</a> - Lua client lib</li><li> Corey Stup - C99 cleanups</li><li> Taylor Weibley - Ruby client improvements</li><li> Bob Potter - Rearrange redisObject struct to reduce memory usage in 64bit environments</li><li> Luca Guidi and Brian McKinney - Ruby client improvements</li><li> Aman Gupta - SDIFF / SDIFFSTORE, other Set operations improvements, ability to disable clients timeout.</li></ul>
+                    <h1><a name="Credits">Credits</a></h1><ul><li> The Redis server was designed and written by <a href="http://invece.org" target="_blank">Salvatore Sanfilippo (aka antirez)</a></li><li> <a href="http://brainspl.at/" target="_blank">Ezra Zygmuntowicz (aka ezmobius)</a> - Ruby client lib initial version and hacking</li><li> <a href="http://qix.it" target="_blank">Ludovico Magnocavallo (aka ludo)</a> - Python clinet lib</li><li> <a href="http://www.adroll.com/" target="_blank">Valentino Volonghi of Adroll</a> - Erlang client lib</li><li> <b>brettbender</b> - found and fixed a bug in sds.c that caused the server to crash at least on 64 bit systems, and anyway to be buggy since we used the same vararg thing against vsprintf without to call va_start and va_end every time.</li><li> <a href="http://www.rot13.org/~dpavlin" target="_blank">Dobrica Pavlinusic</a> - Perl client lib</li><li> Brian Hammond - AUTH command implementation, C++ client lib</li><li> <a href="http://www.clorophilla.net/" target="_blank">Daniele Alessandri</a> - Lua client lib</li><li> Corey Stup - C99 cleanups</li><li> Taylor Weibley - Ruby client improvements</li><li> Bob Potter - Rearrange redisObject struct to reduce memory usage in 64bit environments</li><li> Luca Guidi and Brian McKinney - Ruby client improvements</li><li> Aman Gupta - SDIFF / SDIFFSTORE, other Set operations improvements, ability to disable clients timeout.</li><li> Diego Rosario Brogna - Code and ideas about dumping backtrace on sigsegv and similar error conditions.</li></ul>

 p.s. sorry to take this file in sync is hard in this early days. Please drop me an email if I forgot to add your name here!
 
                 </div>
 p.s. sorry to take this file in sync is hard in this early days. Please drop me an email if I forgot to add your name here!
 
                 </div>

diff --git a/doc/SinterCommand.html b/doc/SinterCommand.html
index 0d1267dca1a5976d27416bcca6549145ae342d87..7a8259b49ab493f21299c292bcaf4ddb2d0abed1 100644 (file)
--- a/doc/SinterCommand.html
+++ b/doc/SinterCommand.html
@@ -27,7 +27,7 @@
 
                 <div class="narrow">
                     <h1><a name="SINTER _key1_ _key2_ ... _keyN_">SINTER _key1_ _key2_ ... _keyN_</a></h1>
 
                 <div class="narrow">
                     <h1><a name="SINTER _key1_ _key2_ ... _keyN_">SINTER _key1_ _key2_ ... _keyN_</a></h1>

-<i>Time complexity O(N<b>M) worst case where N is the cardinality of the smallest set and M the number of sets_<br/><br/><blockquote>Return the members of a set resulting from the intersection of all thesets hold at the specified keys. Like in LRANGE the result is sent tothe client as a multi-bulk reply (see the protocol specification formore information). If just a single key is specified, then this commandproduces the same result as SELEMENTS. Actually SELEMENTS is just syntaxsugar for SINTERSECT.</blockquote>
+<i>Time complexity O(N<b>M) worst case where N is the cardinality of the smallest set and M the number of sets_<br/><br/><blockquote>Return the members of a set resulting from the intersection of all thesets hold at the specified keys. Like in LRANGE the result is sent tothe client as a multi-bulk reply (see the protocol specification formore information). If just a single key is specified, then this commandproduces the same result as SMEMBERS. Actually SMEMBERS is just syntaxsugar for SINTERSECT.</blockquote>

 <blockquote>Non existing keys are considered like empty sets, so if one of the keys ismissing an empty set is returned (since the intersection with an emptyset always is an empty set).</blockquote>
 <h2><a name="Return value">Return value</a></h2><a href="ReplyTypes.html">Multi bulk reply</a>, specifically the list of common elements.<h2><a name="See also">See also</a></h2>
 <blockquote>* <a href="SaddCommand.html">SADD</a>* <a href="SremCommand.html">SREM</a>* <a href="SismemberCommand.html">SISMEMBER</a>* <a href="ScardCommand.html">SCARD</a>* <a href="SmembersCommand.html">SMEMBERS</a>* <a href="SinterstoreCommand.html">SINTERSTORE</a>* <a href="SunionCommand.html">SUNION</a>* <a href="SunionstoreCommand.html">SUNIONSTORE</a>* <a href="SmoveCommand.html">SMOVE</a></blockquote></b></i>
 <blockquote>Non existing keys are considered like empty sets, so if one of the keys ismissing an empty set is returned (since the intersection with an emptyset always is an empty set).</blockquote>
 <h2><a name="Return value">Return value</a></h2><a href="ReplyTypes.html">Multi bulk reply</a>, specifically the list of common elements.<h2><a name="See also">See also</a></h2>
 <blockquote>* <a href="SaddCommand.html">SADD</a>* <a href="SremCommand.html">SREM</a>* <a href="SismemberCommand.html">SISMEMBER</a>* <a href="ScardCommand.html">SCARD</a>* <a href="SmembersCommand.html">SMEMBERS</a>* <a href="SinterstoreCommand.html">SINTERSTORE</a>* <a href="SunionCommand.html">SUNION</a>* <a href="SunionstoreCommand.html">SUNIONSTORE</a>* <a href="SmoveCommand.html">SMOVE</a></blockquote></b></i>

diff --git a/redis-cli.c b/redis-cli.c
index 343ee0a144a7e07d65c75013f71ed52f055e7f9b..9acf92dc2f33b815925dbd5cf3ea783bb43591b4 100644 (file)
--- a/redis-cli.c
+++ b/redis-cli.c
@@ -79,6 +79,7 @@ static struct redisCommand cmdTable[] = {
     {"smove",4,REDIS_CMD_BULK},
     {"sismember",3,REDIS_CMD_BULK},
     {"scard",2,REDIS_CMD_INLINE},
     {"smove",4,REDIS_CMD_BULK},
     {"sismember",3,REDIS_CMD_BULK},
     {"scard",2,REDIS_CMD_INLINE},

+    {"spop",2,REDIS_CMD_INLINE},

     {"sinter",-2,REDIS_CMD_INLINE},
     {"sinterstore",-3,REDIS_CMD_INLINE},
     {"sunion",-2,REDIS_CMD_INLINE},
     {"sinter",-2,REDIS_CMD_INLINE},
     {"sinterstore",-3,REDIS_CMD_INLINE},
     {"sunion",-2,REDIS_CMD_INLINE},

diff --git a/redis.c b/redis.c
index 2caf06c34ee3e1fede62b919a272ec6721b0ccdf..fa653d21e9d05fc9897ec52da77f634a0dedfb06 100644 (file)
--- a/redis.c
+++ b/redis.c
@@ -85,7 +85,6 @@
 
 /* Hash table parameters */
 #define REDIS_HT_MINFILL        10      /* Minimal hash table fill 10% */
 
 /* Hash table parameters */
 #define REDIS_HT_MINFILL        10      /* Minimal hash table fill 10% */

-#define REDIS_HT_MINSLOTS       16384   /* Never resize the HT under this */

 
 /* Command flags */
 #define REDIS_CMD_BULK          1       /* Bulk write command */
 
 /* Command flags */
 #define REDIS_CMD_BULK          1       /* Bulk write command */


@@ -370,6 +369,7 @@ static void sremCommand(redisClient *c);
 static void smoveCommand(redisClient *c);
 static void sismemberCommand(redisClient *c);
 static void scardCommand(redisClient *c);
 static void smoveCommand(redisClient *c);
 static void sismemberCommand(redisClient *c);
 static void scardCommand(redisClient *c);

+static void spopCommand(redisClient *c);

 static void sinterCommand(redisClient *c);
 static void sinterstoreCommand(redisClient *c);
 static void sunionCommand(redisClient *c);
 static void sinterCommand(redisClient *c);
 static void sinterstoreCommand(redisClient *c);
 static void sunionCommand(redisClient *c);


@@ -417,6 +417,7 @@ static struct redisCommand cmdTable[] = {
     {"smove",smoveCommand,4,REDIS_CMD_BULK},
     {"sismember",sismemberCommand,3,REDIS_CMD_BULK},
     {"scard",scardCommand,2,REDIS_CMD_INLINE},
     {"smove",smoveCommand,4,REDIS_CMD_BULK},
     {"sismember",sismemberCommand,3,REDIS_CMD_BULK},
     {"scard",scardCommand,2,REDIS_CMD_INLINE},

+    {"spop",spopCommand,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},
     {"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},


@@ -691,22 +692,28 @@ static void closeTimedoutClients(void) {
     }
 }
 
     }
 }
 

+static int htNeedsResize(dict *dict) {
+    long long size, used;
+
+    size = dictSlots(dict);
+    used = dictSize(dict);
+    return (size && used && size > DICT_HT_INITIAL_SIZE &&
+            (used*100/size < REDIS_HT_MINFILL));
+}
+

 /* If the percentage of used slots in the HT reaches REDIS_HT_MINFILL
  * we resize the hash table to save memory */
 static void tryResizeHashTables(void) {
     int j;
 
     for (j = 0; j < server.dbnum; j++) {
 /* If the percentage of used slots in the HT reaches REDIS_HT_MINFILL
  * we resize the hash table to save memory */
 static void tryResizeHashTables(void) {
     int j;
 
     for (j = 0; j < server.dbnum; j++) {

-        long long size, used;
-
-        size = dictSlots(server.db[j].dict);
-        used = dictSize(server.db[j].dict);
-        if (size && used && size > REDIS_HT_MINSLOTS &&
-            (used*100/size < REDIS_HT_MINFILL)) {
-            redisLog(REDIS_NOTICE,"The hash table %d is too sparse, resize it...",j);
+        if (htNeedsResize(server.db[j].dict)) {
+            redisLog(REDIS_DEBUG,"The hash table %d is too sparse, resize it...",j);

             dictResize(server.db[j].dict);
             dictResize(server.db[j].dict);

-            redisLog(REDIS_NOTICE,"Hash table %d resized.",j);
+            redisLog(REDIS_DEBUG,"Hash table %d resized.",j);

         }
         }

+        if (htNeedsResize(server.db[j].expires))
+            dictResize(server.db[j].expires);

     }
 }
 
     }
 }
 


@@ -2961,6 +2968,7 @@ static void sremCommand(redisClient *c) {
         }
         if (dictDelete(set->ptr,c->argv[2]) == DICT_OK) {
             server.dirty++;
         }
         if (dictDelete(set->ptr,c->argv[2]) == DICT_OK) {
             server.dirty++;

+            if (htNeedsResize(set->ptr)) dictResize(set->ptr);

             addReply(c,shared.cone);
         } else {
             addReply(c,shared.czero);
             addReply(c,shared.cone);
         } else {
             addReply(c,shared.czero);


@@ -3040,6 +3048,34 @@ static void scardCommand(redisClient *c) {
     }
 }
 
     }
 }
 

+static void spopCommand(redisClient *c) {
+    robj *set;
+    dictEntry *de;
+
+    set = lookupKeyWrite(c->db,c->argv[1]);
+    if (set == NULL) {
+        addReply(c,shared.nullbulk);
+    } else {
+        if (set->type != REDIS_SET) {
+            addReply(c,shared.wrongtypeerr);
+            return;
+        }
+        de = dictGetRandomKey(set->ptr);
+        if (de == NULL) {
+            addReply(c,shared.nullbulk);
+        } else {
+            robj *ele = dictGetEntryKey(de);
+
+            addReplySds(c,sdscatprintf(sdsempty(),"$%d\r\n",sdslen(ele->ptr)));
+            addReply(c,ele);
+            addReply(c,shared.crlf);
+            dictDelete(set->ptr,ele);
+            if (htNeedsResize(set->ptr)) dictResize(set->ptr);
+            server.dirty++;
+        }
+    }
+}
+

 static int qsortCompareSetsByCardinality(const void *s1, const void *s2) {
     dict **d1 = (void*) s1, **d2 = (void*) s2;
 
 static int qsortCompareSetsByCardinality(const void *s1, const void *s2) {
     dict **d1 = (void*) s1, **d2 = (void*) s2;
 


@@ -4170,6 +4206,7 @@ static struct redisFunctionSym symsTable[] = {
 {"smoveCommand", (unsigned long)smoveCommand},
 {"sismemberCommand", (unsigned long)sismemberCommand},
 {"scardCommand", (unsigned long)scardCommand},
 {"smoveCommand", (unsigned long)smoveCommand},
 {"sismemberCommand", (unsigned long)sismemberCommand},
 {"scardCommand", (unsigned long)scardCommand},

+{"spopCommand", (unsigned long)spopCommand},

 {"sinterCommand", (unsigned long)sinterCommand},
 {"sinterstoreCommand", (unsigned long)sinterstoreCommand},
 {"sunionCommand", (unsigned long)sunionCommand},
 {"sinterCommand", (unsigned long)sinterCommand},
 {"sinterstoreCommand", (unsigned long)sinterstoreCommand},
 {"sunionCommand", (unsigned long)sunionCommand},


@@ -4296,6 +4333,9 @@ static void setupSigSegvAction(void) {
     act.sa_sigaction = segvHandler;
     sigaction (SIGSEGV, &act, NULL);
     sigaction (SIGBUS, &act, NULL);
     act.sa_sigaction = segvHandler;
     sigaction (SIGSEGV, &act, NULL);
     sigaction (SIGBUS, &act, NULL);

+    sigaction (SIGFPE, &act, NULL);
+    sigaction (SIGILL, &act, NULL);
+    sigaction (SIGBUS, &act, NULL);

     return;
 }
 #else /* HAVE_BACKTRACE */
     return;
 }
 #else /* HAVE_BACKTRACE */

diff --git a/test-redis.tcl b/test-redis.tcl
index bd58cb2e7183bea9fc62334ecad0f474ceeaf7c6..f5a03161ab023bb6d006b5f5c2f8eaa7e1343943 100644 (file)
--- a/test-redis.tcl
+++ b/test-redis.tcl
@@ -515,6 +515,14 @@ proc main {server port} {
         lsort [$r smembers sres]
     } {1 2 3 4}
 
         lsort [$r smembers sres]
     } {1 2 3 4}
 

+    test {SPOP basics} {
+        $r del myset
+        $r sadd myset 1
+        $r sadd myset 2
+        $r sadd myset 3
+        list [lsort [list [$r spop myset] [$r spop myset] [$r spop myset]]] [$r scard myset]
+    } {{1 2 3} 0}
+

     test {SAVE - make sure there are all the types as values} {
         $r lpush mysavelist hello
         $r lpush mysavelist world
     test {SAVE - make sure there are all the types as values} {
         $r lpush mysavelist hello
         $r lpush mysavelist world