src/util.c

   1 #include "redis.h"
   2 #include <ctype.h>
   3 #include <limits.h>
   4 #include <math.h>
   5
   6 /* Glob-style pattern matching. */
   7 int stringmatchlen(const char *pattern, int patternLen,
   8         const char *string, int stringLen, int nocase)
   9 {
  10     while(patternLen) {
  11         switch(pattern[0]) {
  12         case '*':
  13             while (pattern[1] == '*') {
  14                 pattern++;
  15                 patternLen--;
  16             }
  17             if (patternLen == 1)
  18                 return 1; /* match */
  19             while(stringLen) {
  20                 if (stringmatchlen(pattern+1, patternLen-1,
  21                             string, stringLen, nocase))
  22                     return 1; /* match */
  23                 string++;
  24                 stringLen--;
  25             }
  26             return 0; /* no match */
  27             break;
  28         case '?':
  29             if (stringLen == 0)
  30                 return 0; /* no match */
  31             string++;
  32             stringLen--;
  33             break;
  34         case '[':
  35         {
  36             int not, match;
  37
  38             pattern++;
  39             patternLen--;
  40             not = pattern[0] == '^';
  41             if (not) {
  42                 pattern++;
  43                 patternLen--;
  44             }
  45             match = 0;
  46             while(1) {
  47                 if (pattern[0] == '\\') {
  48                     pattern++;
  49                     patternLen--;
  50                     if (pattern[0] == string[0])
  51                         match = 1;
  52                 } else if (pattern[0] == ']') {
  53                     break;
  54                 } else if (patternLen == 0) {
  55                     pattern--;
  56                     patternLen++;
  57                     break;
  58                 } else if (pattern[1] == '-' && patternLen >= 3) {
  59                     int start = pattern[0];
  60                     int end = pattern[2];
  61                     int c = string[0];
  62                     if (start > end) {
  63                         int t = start;
  64                         start = end;
  65                         end = t;
  66                     }
  67                     if (nocase) {
  68                         start = tolower(start);
  69                         end = tolower(end);
  70                         c = tolower(c);
  71                     }
  72                     pattern += 2;
  73                     patternLen -= 2;
  74                     if (c >= start && c <= end)
  75                         match = 1;
  76                 } else {
  77                     if (!nocase) {
  78                         if (pattern[0] == string[0])
  79                             match = 1;
  80                     } else {
  81                         if (tolower((int)pattern[0]) == tolower((int)string[0]))
  82                             match = 1;
  83                     }
  84                 }
  85                 pattern++;
  86                 patternLen--;
  87             }
  88             if (not)
  89                 match = !match;
  90             if (!match)
  91                 return 0; /* no match */
  92             string++;
  93             stringLen--;
  94             break;
  95         }
  96         case '\\':
  97             if (patternLen >= 2) {
  98                 pattern++;
  99                 patternLen--;
 100             }
 101             /* fall through */
 102         default:
 103             if (!nocase) {
 104                 if (pattern[0] != string[0])
 105                     return 0; /* no match */
 106             } else {
 107                 if (tolower((int)pattern[0]) != tolower((int)string[0]))
 108                     return 0; /* no match */
 109             }
 110             string++;
 111             stringLen--;
 112             break;
 113         }
 114         pattern++;
 115         patternLen--;
 116         if (stringLen == 0) {
 117             while(*pattern == '*') {
 118                 pattern++;
 119                 patternLen--;
 120             }
 121             break;
 122         }
 123     }
 124     if (patternLen == 0 && stringLen == 0)
 125         return 1;
 126     return 0;
 127 }
 128
 129 int stringmatch(const char *pattern, const char *string, int nocase) {
 130     return stringmatchlen(pattern,strlen(pattern),string,strlen(string),nocase);
 131 }
 132
 133 /* Convert a string representing an amount of memory into the number of
 134  * bytes, so for instance memtoll("1Gi") will return 1073741824 that is
 135  * (1024*1024*1024).
 136  *
 137  * On parsing error, if *err is not NULL, it's set to 1, otherwise it's
 138  * set to 0 */
 139 long long memtoll(const char *p, int *err) {
 140     const char *u;
 141     char buf[128];
 142     long mul; /* unit multiplier */
 143     long long val;
 144     unsigned int digits;
 145
 146     if (err) *err = 0;
 147     /* Search the first non digit character. */
 148     u = p;
 149     if (*u == '-') u++;
 150     while(*u && isdigit(*u)) u++;
 151     if (*u == '\0' || !strcasecmp(u,"b")) {
 152         mul = 1;
 153     } else if (!strcasecmp(u,"k")) {
 154         mul = 1000;
 155     } else if (!strcasecmp(u,"kb")) {
 156         mul = 1024;
 157     } else if (!strcasecmp(u,"m")) {
 158         mul = 1000*1000;
 159     } else if (!strcasecmp(u,"mb")) {
 160         mul = 1024*1024;
 161     } else if (!strcasecmp(u,"g")) {
 162         mul = 1000L*1000*1000;
 163     } else if (!strcasecmp(u,"gb")) {
 164         mul = 1024L*1024*1024;
 165     } else {
 166         if (err) *err = 1;
 167         mul = 1;
 168     }
 169     digits = u-p;
 170     if (digits >= sizeof(buf)) {
 171         if (err) *err = 1;
 172         return LLONG_MAX;
 173     }
 174     memcpy(buf,p,digits);
 175     buf[digits] = '\0';
 176     val = strtoll(buf,NULL,10);
 177     return val*mul;
 178 }
 179
 180 /* Convert a long long into a string. Returns the number of
 181  * characters needed to represent the number, that can be shorter if passed
 182  * buffer length is not enough to store the whole number. */
 183 int ll2string(char *s, size_t len, long long value) {
 184     char buf[32], *p;
 185     unsigned long long v;
 186     size_t l;
 187
 188     if (len == 0) return 0;
 189     v = (value < 0) ? -value : value;
 190     p = buf+31; /* point to the last character */
 191     do {
 192         *p-- = '0'+(v%10);
 193         v /= 10;
 194     } while(v);
 195     if (value < 0) *p-- = '-';
 196     p++;
 197     l = 32-(p-buf);
 198     if (l+1 > len) l = len-1; /* Make sure it fits, including the nul term */
 199     memcpy(s,p,l);
 200     s[l] = '\0';
 201     return l;
 202 }
 203
 204 /* Convert a string into a long long. Returns 1 if the string could be parsed
 205  * into a (non-overflowing) long long, 0 otherwise. The value will be set to
 206  * the parsed value when appropriate. */
 207 int string2ll(char *s, size_t slen, long long *value) {
 208     char *p = s;
 209     size_t plen = 0;
 210     int negative = 0;
 211     unsigned long long v;
 212
 213     if (plen == slen)
 214         return 0;
 215
 216     if (p[0] == '-') {
 217         negative = 1;
 218         p++; plen++;
 219
 220         /* Abort on only a negative sign. */
 221         if (plen == slen)
 222             return 0;
 223     }
 224
 225     /* First digit should be 1-9. */
 226     if (p[0] >= '1' && p[0] <= '9') {
 227         v = p[0]-'0';
 228         p++; plen++;
 229     } else {
 230         return 0;
 231     }
 232
 233     while (plen < slen && p[0] >= '0' && p[0] <= '9') {
 234         if (v > (ULLONG_MAX / 10)) /* Overflow. */
 235             return 0;
 236         v *= 10;
 237
 238         if (v > (ULLONG_MAX - (p[0]-'0'))) /* Overflow. */
 239             return 0;
 240         v += p[0]-'0';
 241
 242         p++; plen++;
 243     }
 244
 245     /* Return if not all bytes were used. */
 246     if (plen < slen)
 247         return 0;
 248
 249     if (negative) {
 250         if (v > (-(unsigned long long)LLONG_MIN)) /* Overflow. */
 251             return 0;
 252         if (value != NULL) *value = -v;
 253     } else {
 254         if (v > LLONG_MAX) /* Overflow. */
 255             return 0;
 256         if (value != NULL) *value = v;
 257     }
 258     return 1;
 259 }
 260
 261 /* Convert a double to a string representation. Returns the number of bytes
 262  * required. The representation should always be parsable by stdtod(3). */
 263 int d2string(char *buf, size_t len, double value) {
 264     if (isnan(value)) {
 265         len = snprintf(buf,len,"nan");
 266     } else if (isinf(value)) {
 267         if (value < 0)
 268             len = snprintf(buf,len,"-inf");
 269         else
 270             len = snprintf(buf,len,"inf");
 271     } else if (value == 0) {
 272         /* See: http://en.wikipedia.org/wiki/Signed_zero, "Comparisons". */
 273         if (1.0/value < 0)
 274             len = snprintf(buf,len,"-0");
 275         else
 276             len = snprintf(buf,len,"0");
 277     } else {
 278 #if (DBL_MANT_DIG >= 52) && (LLONG_MAX == 0x7fffffffffffffffLL)
 279         /* Check if the float is in a safe range to be casted into a
 280          * long long. We are assuming that long long is 64 bit here.
 281          * Also we are assuming that there are no implementations around where
 282          * double has precision < 52 bit.
 283          *
 284          * Under this assumptions we test if a double is inside an interval
 285          * where casting to long long is safe. Then using two castings we
 286          * make sure the decimal part is zero. If all this is true we use
 287          * integer printing function that is much faster. */
 288         double min = -4503599627370495; /* (2^52)-1 */
 289         double max = 4503599627370496; /* -(2^52) */
 290         if (val > min && val < max && value == ((double)((long long)value)))
 291             len = ll2string(buf,len,(long long)value);
 292         else
 293 #endif
 294             len = snprintf(buf,len,"%.17g",value);
 295     }
 296
 297     return len;
 298 }
 299
 300 /* Check if the sds string 's' can be represented by a long long
 301  * (that is, is a number that fits into long without any other space or
 302  * character before or after the digits, so that converting this number
 303  * back to a string will result in the same bytes as the original string).
 304  *
 305  * If so, the function returns REDIS_OK and *llongval is set to the value
 306  * of the number. Otherwise REDIS_ERR is returned */
 307 int isStringRepresentableAsLongLong(sds s, long long *llongval) {
 308     char buf[32], *endptr;
 309     long long value;
 310     int slen;
 311
 312     value = strtoll(s, &endptr, 10);
 313     if (endptr[0] != '\0') return REDIS_ERR;
 314     slen = ll2string(buf,32,value);
 315
 316     /* If the number converted back into a string is not identical
 317      * then it's not possible to encode the string as integer */
 318     if (sdslen(s) != (unsigned)slen || memcmp(buf,s,slen)) return REDIS_ERR;
 319     if (llongval) *llongval = value;
 320     return REDIS_OK;
 321 }
 322
 323 int isStringRepresentableAsLong(sds s, long *longval) {
 324     long long ll;
 325
 326     if (isStringRepresentableAsLongLong(s,&ll) == REDIS_ERR) return REDIS_ERR;
 327     if (ll < LONG_MIN || ll > LONG_MAX) return REDIS_ERR;
 328     *longval = (long)ll;
 329     return REDIS_OK;
 330 }
 331
 332 int isObjectRepresentableAsLongLong(robj *o, long long *llongval) {
 333     redisAssert(o->type == REDIS_STRING);
 334     if (o->encoding == REDIS_ENCODING_INT) {
 335         if (llongval) *llongval = (long) o->ptr;
 336         return REDIS_OK;
 337     } else {
 338         return isStringRepresentableAsLongLong(o->ptr,llongval);
 339     }
 340 }