Test: more MIGRATE tests.

[redis.git] / src / bitops.c

diff --git a/src/bitops.c b/src/bitops.c
index 0b9c7b02fb6c095e1b92b8b97f28fcb7a785f7e3..3ef0a8f3d6cbb4cab3fc673f7a02c166e27833c7 100644 (file)
--- a/src/bitops.c
+++ b/src/bitops.c
@@ -1,3 +1,33 @@
+/* Bit operations.
+ *
+ * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ *   * Redistributions of source code must retain the above copyright notice,
+ *     this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ *   * Neither the name of Redis nor the names of its contributors may be used
+ *     to endorse or promote products derived from this software without
+ *     specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+

 #include "redis.h"
 
 /* -----------------------------------------------------------------------------
 #include "redis.h"
 
 /* -----------------------------------------------------------------------------


@@ -114,14 +144,14 @@ void setbitCommand(redisClient *c) {
     o->ptr = sdsgrowzero(o->ptr,byte+1);
 
     /* Get current values */
     o->ptr = sdsgrowzero(o->ptr,byte+1);
 
     /* Get current values */

-    byteval = ((char*)o->ptr)[byte];
+    byteval = ((uint8_t*)o->ptr)[byte];

     bit = 7 - (bitoffset & 0x7);
     bitval = byteval & (1 << bit);
 
     /* Update byte with new bit value and return original value */
     byteval &= ~(1 << bit);
     byteval |= ((on & 0x1) << bit);
     bit = 7 - (bitoffset & 0x7);
     bitval = byteval & (1 << bit);
 
     /* Update byte with new bit value and return original value */
     byteval &= ~(1 << bit);
     byteval |= ((on & 0x1) << bit);

-    ((char*)o->ptr)[byte] = byteval;
+    ((uint8_t*)o->ptr)[byte] = byteval;

     signalModifiedKey(c->db,c->argv[1]);
     server.dirty++;
     addReply(c, bitval ? shared.cone : shared.czero);
     signalModifiedKey(c->db,c->argv[1]);
     server.dirty++;
     addReply(c, bitval ? shared.cone : shared.czero);


@@ -148,7 +178,7 @@ void getbitCommand(redisClient *c) {
             bitval = llbuf[byte] & (1 << bit);
     } else {
         if (byte < sdslen(o->ptr))
             bitval = llbuf[byte] & (1 << bit);
     } else {
         if (byte < sdslen(o->ptr))

-            bitval = ((char*)o->ptr)[byte] & (1 << bit);
+            bitval = ((uint8_t*)o->ptr)[byte] & (1 << bit);

     }
 
     addReply(c, bitval ? shared.cone : shared.czero);
     }
 
     addReply(c, bitval ? shared.cone : shared.czero);


@@ -159,8 +189,10 @@ void bitopCommand(redisClient *c) {
     char *opname = c->argv[1]->ptr;
     robj *o, *targetkey = c->argv[2];
     long op, j, numkeys;
     char *opname = c->argv[1]->ptr;
     robj *o, *targetkey = c->argv[2];
     long op, j, numkeys;

+    robj **objects;      /* Array of soruce objects. */

     unsigned char **src; /* Array of source strings pointers. */
     long *len, maxlen = 0; /* Array of length of src strings, and max len. */
     unsigned char **src; /* Array of source strings pointers. */
     long *len, maxlen = 0; /* Array of length of src strings, and max len. */

+    long minlen = 0;    /* Min len among the input keys. */

     unsigned char *res = NULL; /* Resulting string. */
 
     /* Parse the operation name. */
     unsigned char *res = NULL; /* Resulting string. */
 
     /* Parse the operation name. */


@@ -187,23 +219,33 @@ void bitopCommand(redisClient *c) {
     numkeys = c->argc - 3;
     src = zmalloc(sizeof(unsigned char*) * numkeys);
     len = zmalloc(sizeof(long) * numkeys);
     numkeys = c->argc - 3;
     src = zmalloc(sizeof(unsigned char*) * numkeys);
     len = zmalloc(sizeof(long) * numkeys);

+    objects = zmalloc(sizeof(robj*) * numkeys);

     for (j = 0; j < numkeys; j++) {
         o = lookupKeyRead(c->db,c->argv[j+3]);
         /* Handle non-existing keys as empty strings. */
         if (o == NULL) {
     for (j = 0; j < numkeys; j++) {
         o = lookupKeyRead(c->db,c->argv[j+3]);
         /* Handle non-existing keys as empty strings. */
         if (o == NULL) {

+            objects[j] = NULL;

             src[j] = NULL;
             len[j] = 0;
             src[j] = NULL;
             len[j] = 0;

+            minlen = 0;

             continue;
         }
         /* Return an error if one of the keys is not a string. */
         if (checkType(c,o,REDIS_STRING)) {
             continue;
         }
         /* Return an error if one of the keys is not a string. */
         if (checkType(c,o,REDIS_STRING)) {

+            for (j = j-1; j >= 0; j--) {
+                if (objects[j])
+                    decrRefCount(objects[j]);
+            }

             zfree(src);
             zfree(len);
             zfree(src);
             zfree(len);

+            zfree(objects);

             return;
         }
             return;
         }

-        src[j] = o->ptr;
-        len[j] = sdslen(o->ptr);
+        objects[j] = getDecodedObject(o);
+        src[j] = objects[j]->ptr;
+        len[j] = sdslen(objects[j]->ptr);

         if (len[j] > maxlen) maxlen = len[j];
         if (len[j] > maxlen) maxlen = len[j];

+        if (j == 0 || len[j] < minlen) minlen = len[j];

     }
 
     /* Compute the bit operation, if at least one string is not empty. */
     }
 
     /* Compute the bit operation, if at least one string is not empty. */


@@ -212,7 +254,73 @@ void bitopCommand(redisClient *c) {
         unsigned char output, byte;
         long i;
 
         unsigned char output, byte;
         long i;
 

-        for (j = 0; j < maxlen; j++) {
+        /* Fast path: as far as we have data for all the input bitmaps we
+         * can take a fast path that performs much better than the
+         * vanilla algorithm. */
+        j = 0;
+        if (minlen && numkeys <= 16) {
+            unsigned long *lp[16];
+            unsigned long *lres = (unsigned long*) res;
+
+            /* Note: sds pointer is always aligned to 8 byte boundary. */
+            memcpy(lp,src,sizeof(unsigned long*)*numkeys);
+            memcpy(res,src[0],minlen);
+
+            /* Different branches per different operations for speed (sorry). */
+            if (op == BITOP_AND) {
+                while(minlen >= sizeof(unsigned long)*4) {
+                    for (i = 1; i < numkeys; i++) {
+                        lres[0] &= lp[i][0];
+                        lres[1] &= lp[i][1];
+                        lres[2] &= lp[i][2];
+                        lres[3] &= lp[i][3];
+                        lp[i]+=4;
+                    }
+                    lres+=4;
+                    j += sizeof(unsigned long)*4;
+                    minlen -= sizeof(unsigned long)*4;
+                }
+            } else if (op == BITOP_OR) {
+                while(minlen >= sizeof(unsigned long)*4) {
+                    for (i = 1; i < numkeys; i++) {
+                        lres[0] |= lp[i][0];
+                        lres[1] |= lp[i][1];
+                        lres[2] |= lp[i][2];
+                        lres[3] |= lp[i][3];
+                        lp[i]+=4;
+                    }
+                    lres+=4;
+                    j += sizeof(unsigned long)*4;
+                    minlen -= sizeof(unsigned long)*4;
+                }
+            } else if (op == BITOP_XOR) {
+                while(minlen >= sizeof(unsigned long)*4) {
+                    for (i = 1; i < numkeys; i++) {
+                        lres[0] ^= lp[i][0];
+                        lres[1] ^= lp[i][1];
+                        lres[2] ^= lp[i][2];
+                        lres[3] ^= lp[i][3];
+                        lp[i]+=4;
+                    }
+                    lres+=4;
+                    j += sizeof(unsigned long)*4;
+                    minlen -= sizeof(unsigned long)*4;
+                }
+            } else if (op == BITOP_NOT) {
+                while(minlen >= sizeof(unsigned long)*4) {
+                    lres[0] = ~lres[0];
+                    lres[1] = ~lres[1];
+                    lres[2] = ~lres[2];
+                    lres[3] = ~lres[3];
+                    lres+=4;
+                    j += sizeof(unsigned long)*4;
+                    minlen -= sizeof(unsigned long)*4;
+                }
+            }
+        }
+
+        /* j is set to the next byte to process by the previous loop. */
+        for (; j < maxlen; j++) {

             output = (len[0] <= j) ? 0 : src[0][j];
             if (op == BITOP_NOT) output = ~output;
             for (i = 1; i < numkeys; i++) {
             output = (len[0] <= j) ? 0 : src[0][j];
             if (op == BITOP_NOT) output = ~output;
             for (i = 1; i < numkeys; i++) {


@@ -226,8 +334,13 @@ void bitopCommand(redisClient *c) {
             res[j] = output;
         }
     }
             res[j] = output;
         }
     }

+    for (j = 0; j < numkeys; j++) {
+        if (objects[j])
+            decrRefCount(objects[j]);
+    }

     zfree(src);
     zfree(len);
     zfree(src);
     zfree(len);

+    zfree(objects);

 
     /* Store the computed value into the target key */
     if (maxlen) {
 
     /* Store the computed value into the target key */
     if (maxlen) {


@@ -244,10 +357,9 @@ void bitopCommand(redisClient *c) {
 /* BITCOUNT key [start end] */
 void bitcountCommand(redisClient *c) {
     robj *o;
 /* BITCOUNT key [start end] */
 void bitcountCommand(redisClient *c) {
     robj *o;

-    long start, end;
+    long start, end, strlen;

     unsigned char *p;
     char llbuf[32];
     unsigned char *p;
     char llbuf[32];

-    size_t strlen;

 
     /* Lookup, check for type, and return 0 for non existing keys. */
     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||
 
     /* Lookup, check for type, and return 0 for non existing keys. */
     if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.czero)) == NULL ||


@@ -274,7 +386,7 @@ void bitcountCommand(redisClient *c) {
         if (end < 0) end = strlen+end;
         if (start < 0) start = 0;
         if (end < 0) end = 0;
         if (end < 0) end = strlen+end;
         if (start < 0) start = 0;
         if (end < 0) end = 0;

-        if ((unsigned)end >= strlen) end = strlen-1;
+        if (end >= strlen) end = strlen-1;

     } else if (c->argc == 2) {
         /* The whole string. */
         start = 0;
     } else if (c->argc == 2) {
         /* The whole string. */
         start = 0;