]> git.saurik.com Git - redis.git/blobdiff - src/util.c
popcount() optimization for speed.
[redis.git] / src / util.c
index 2404c77cd2bfbb8cc44c4e75bfef68bb17596501..bcdafc6394e47e87cf31e760f5825a5d0d961fc9 100644 (file)
@@ -1,7 +1,14 @@
-#include "redis.h"
+#include "fmacros.h"
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
 #include <ctype.h>
 #include <limits.h>
 #include <math.h>
 #include <ctype.h>
 #include <limits.h>
 #include <math.h>
+#include <unistd.h>
+#include <sys/time.h>
+
+#include "util.h"
 
 /* Glob-style pattern matching. */
 int stringmatchlen(const char *pattern, int patternLen,
 
 /* Glob-style pattern matching. */
 int stringmatchlen(const char *pattern, int patternLen,
@@ -204,8 +211,8 @@ int ll2string(char *s, size_t len, long long value) {
 /* Convert a string into a long long. Returns 1 if the string could be parsed
  * into a (non-overflowing) long long, 0 otherwise. The value will be set to
  * the parsed value when appropriate. */
 /* Convert a string into a long long. Returns 1 if the string could be parsed
  * into a (non-overflowing) long long, 0 otherwise. The value will be set to
  * the parsed value when appropriate. */
-int string2ll(char *s, size_t slen, long long *value) {
-    char *p = s;
+int string2ll(const char *s, size_t slen, long long *value) {
+    const char *p = s;
     size_t plen = 0;
     int negative = 0;
     unsigned long long v;
     size_t plen = 0;
     int negative = 0;
     unsigned long long v;
@@ -213,6 +220,12 @@ int string2ll(char *s, size_t slen, long long *value) {
     if (plen == slen)
         return 0;
 
     if (plen == slen)
         return 0;
 
+    /* Special case: first and only digit is 0. */
+    if (slen == 1 && p[0] == '0') {
+        if (value != NULL) *value = 0;
+        return 1;
+    }
+
     if (p[0] == '-') {
         negative = 1;
         p++; plen++;
     if (p[0] == '-') {
         negative = 1;
         p++; plen++;
@@ -250,7 +263,7 @@ int string2ll(char *s, size_t slen, long long *value) {
         return 0;
 
     if (negative) {
         return 0;
 
     if (negative) {
-        if (v > (-(unsigned long long)LLONG_MIN)) /* Overflow. */
+        if (v > ((unsigned long long)(-(LLONG_MIN+1))+1)) /* Overflow. */
             return 0;
         if (value != NULL) *value = -v;
     } else {
             return 0;
         if (value != NULL) *value = -v;
     } else {
@@ -261,6 +274,22 @@ int string2ll(char *s, size_t slen, long long *value) {
     return 1;
 }
 
     return 1;
 }
 
+/* Convert a string into a long. Returns 1 if the string could be parsed into a
+ * (non-overflowing) long, 0 otherwise. The value will be set to the parsed
+ * value when appropriate. */
+int string2l(const char *s, size_t slen, long *lval) {
+    long long llval;
+
+    if (!string2ll(s,slen,&llval))
+        return 0;
+
+    if (llval < LONG_MIN || llval > LONG_MAX)
+        return 0;
+
+    *lval = (long)llval;
+    return 1;
+}
+
 /* Convert a double to a string representation. Returns the number of bytes
  * required. The representation should always be parsable by stdtod(3). */
 int d2string(char *buf, size_t len, double value) {
 /* Convert a double to a string representation. Returns the number of bytes
  * required. The representation should always be parsable by stdtod(3). */
 int d2string(char *buf, size_t len, double value) {
@@ -300,44 +329,162 @@ int d2string(char *buf, size_t len, double value) {
     return len;
 }
 
     return len;
 }
 
-/* Check if the sds string 's' can be represented by a long long
- * (that is, is a number that fits into long without any other space or
- * character before or after the digits, so that converting this number
- * back to a string will result in the same bytes as the original string).
- *
- * If so, the function returns REDIS_OK and *llongval is set to the value
- * of the number. Otherwise REDIS_ERR is returned */
-int isStringRepresentableAsLongLong(sds s, long long *llongval) {
-    char buf[32], *endptr;
-    long long value;
-    int slen;
-
-    value = strtoll(s, &endptr, 10);
-    if (endptr[0] != '\0') return REDIS_ERR;
-    slen = ll2string(buf,32,value);
-
-    /* If the number converted back into a string is not identical
-     * then it's not possible to encode the string as integer */
-    if (sdslen(s) != (unsigned)slen || memcmp(buf,s,slen)) return REDIS_ERR;
-    if (llongval) *llongval = value;
-    return REDIS_OK;
+/* Generate the Redis "Run ID", a SHA1-sized random number that identifies a
+ * given execution of Redis, so that if you are talking with an instance
+ * having run_id == A, and you reconnect and it has run_id == B, you can be
+ * sure that it is either a different instance or it was restarted. */
+void getRandomHexChars(char *p, unsigned int len) {
+    FILE *fp = fopen("/dev/urandom","r");
+    char *charset = "0123456789abcdef";
+    unsigned int j;
+
+    if (fp == NULL || fread(p,len,1,fp) == 0) {
+        /* If we can't read from /dev/urandom, do some reasonable effort
+         * in order to create some entropy, since this function is used to
+         * generate run_id and cluster instance IDs */
+        char *x = p;
+        unsigned int l = len;
+        struct timeval tv;
+        pid_t pid = getpid();
+
+        /* Use time and PID to fill the initial array. */
+        gettimeofday(&tv,NULL);
+        if (l >= sizeof(tv.tv_usec)) {
+            memcpy(x,&tv.tv_usec,sizeof(tv.tv_usec));
+            l -= sizeof(tv.tv_usec);
+            x += sizeof(tv.tv_usec);
+        }
+        if (l >= sizeof(tv.tv_sec)) {
+            memcpy(x,&tv.tv_sec,sizeof(tv.tv_sec));
+            l -= sizeof(tv.tv_sec);
+            x += sizeof(tv.tv_sec);
+        }
+        if (l >= sizeof(pid)) {
+            memcpy(x,&pid,sizeof(pid));
+            l -= sizeof(pid);
+            x += sizeof(pid);
+        }
+        /* Finally xor it with rand() output, that was already seeded with
+         * time() at startup. */
+        for (j = 0; j < len; j++)
+            p[j] ^= rand();
+    }
+    /* Turn it into hex digits taking just 4 bits out of 8 for every byte. */
+    for (j = 0; j < len; j++)
+        p[j] = charset[p[j] & 0x0F];
+    fclose(fp);
+}
+
+#ifdef UTIL_TEST_MAIN
+#include <assert.h>
+
+void test_string2ll(void) {
+    char buf[32];
+    long long v;
+
+    /* May not start with +. */
+    strcpy(buf,"+1");
+    assert(string2ll(buf,strlen(buf),&v) == 0);
+
+    /* Leading space. */
+    strcpy(buf," 1");
+    assert(string2ll(buf,strlen(buf),&v) == 0);
+
+    /* Trailing space. */
+    strcpy(buf,"1 ");
+    assert(string2ll(buf,strlen(buf),&v) == 0);
+
+    /* May not start with 0. */
+    strcpy(buf,"01");
+    assert(string2ll(buf,strlen(buf),&v) == 0);
+
+    strcpy(buf,"-1");
+    assert(string2ll(buf,strlen(buf),&v) == 1);
+    assert(v == -1);
+
+    strcpy(buf,"0");
+    assert(string2ll(buf,strlen(buf),&v) == 1);
+    assert(v == 0);
+
+    strcpy(buf,"1");
+    assert(string2ll(buf,strlen(buf),&v) == 1);
+    assert(v == 1);
+
+    strcpy(buf,"99");
+    assert(string2ll(buf,strlen(buf),&v) == 1);
+    assert(v == 99);
+
+    strcpy(buf,"-99");
+    assert(string2ll(buf,strlen(buf),&v) == 1);
+    assert(v == -99);
+
+    strcpy(buf,"-9223372036854775808");
+    assert(string2ll(buf,strlen(buf),&v) == 1);
+    assert(v == LLONG_MIN);
+
+    strcpy(buf,"-9223372036854775809"); /* overflow */
+    assert(string2ll(buf,strlen(buf),&v) == 0);
+
+    strcpy(buf,"9223372036854775807");
+    assert(string2ll(buf,strlen(buf),&v) == 1);
+    assert(v == LLONG_MAX);
+
+    strcpy(buf,"9223372036854775808"); /* overflow */
+    assert(string2ll(buf,strlen(buf),&v) == 0);
 }
 
 }
 
-int isStringRepresentableAsLong(sds s, long *longval) {
-    long long ll;
+void test_string2l(void) {
+    char buf[32];
+    long v;
+
+    /* May not start with +. */
+    strcpy(buf,"+1");
+    assert(string2l(buf,strlen(buf),&v) == 0);
+
+    /* May not start with 0. */
+    strcpy(buf,"01");
+    assert(string2l(buf,strlen(buf),&v) == 0);
+
+    strcpy(buf,"-1");
+    assert(string2l(buf,strlen(buf),&v) == 1);
+    assert(v == -1);
 
 
-    if (isStringRepresentableAsLongLong(s,&ll) == REDIS_ERR) return REDIS_ERR;
-    if (ll < LONG_MIN || ll > LONG_MAX) return REDIS_ERR;
-    *longval = (long)ll;
-    return REDIS_OK;
+    strcpy(buf,"0");
+    assert(string2l(buf,strlen(buf),&v) == 1);
+    assert(v == 0);
+
+    strcpy(buf,"1");
+    assert(string2l(buf,strlen(buf),&v) == 1);
+    assert(v == 1);
+
+    strcpy(buf,"99");
+    assert(string2l(buf,strlen(buf),&v) == 1);
+    assert(v == 99);
+
+    strcpy(buf,"-99");
+    assert(string2l(buf,strlen(buf),&v) == 1);
+    assert(v == -99);
+
+#if LONG_MAX != LLONG_MAX
+    strcpy(buf,"-2147483648");
+    assert(string2l(buf,strlen(buf),&v) == 1);
+    assert(v == LONG_MIN);
+
+    strcpy(buf,"-2147483649"); /* overflow */
+    assert(string2l(buf,strlen(buf),&v) == 0);
+
+    strcpy(buf,"2147483647");
+    assert(string2l(buf,strlen(buf),&v) == 1);
+    assert(v == LONG_MAX);
+
+    strcpy(buf,"2147483648"); /* overflow */
+    assert(string2l(buf,strlen(buf),&v) == 0);
+#endif
 }
 
 }
 
-int isObjectRepresentableAsLongLong(robj *o, long long *llongval) {
-    redisAssert(o->type == REDIS_STRING);
-    if (o->encoding == REDIS_ENCODING_INT) {
-        if (llongval) *llongval = (long) o->ptr;
-        return REDIS_OK;
-    } else {
-        return isStringRepresentableAsLongLong(o->ptr,llongval);
-    }
+int main(int argc, char **argv) {
+    test_string2ll();
+    test_string2l();
+    return 0;
 }
 }
+#endif