src/util.c

   1 #include "fmacros.h"
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #include <string.h>
   5 #include <ctype.h>
   6 #include <limits.h>
   7 #include <math.h>
   8 #include <unistd.h>
   9 #include <sys/time.h>
  10 #include <float.h>
  11
  12 #include "util.h"
  13
  14 /* Glob-style pattern matching. */
  15 int stringmatchlen(const char *pattern, int patternLen,
  16         const char *string, int stringLen, int nocase)
  17 {
  18     while(patternLen) {
  19         switch(pattern[0]) {
  20         case '*':
  21             while (pattern[1] == '*') {
  22                 pattern++;
  23                 patternLen--;
  24             }
  25             if (patternLen == 1)
  26                 return 1; /* match */
  27             while(stringLen) {
  28                 if (stringmatchlen(pattern+1, patternLen-1,
  29                             string, stringLen, nocase))
  30                     return 1; /* match */
  31                 string++;
  32                 stringLen--;
  33             }
  34             return 0; /* no match */
  35             break;
  36         case '?':
  37             if (stringLen == 0)
  38                 return 0; /* no match */
  39             string++;
  40             stringLen--;
  41             break;
  42         case '[':
  43         {
  44             int not, match;
  45
  46             pattern++;
  47             patternLen--;
  48             not = pattern[0] == '^';
  49             if (not) {
  50                 pattern++;
  51                 patternLen--;
  52             }
  53             match = 0;
  54             while(1) {
  55                 if (pattern[0] == '\\') {
  56                     pattern++;
  57                     patternLen--;
  58                     if (pattern[0] == string[0])
  59                         match = 1;
  60                 } else if (pattern[0] == ']') {
  61                     break;
  62                 } else if (patternLen == 0) {
  63                     pattern--;
  64                     patternLen++;
  65                     break;
  66                 } else if (pattern[1] == '-' && patternLen >= 3) {
  67                     int start = pattern[0];
  68                     int end = pattern[2];
  69                     int c = string[0];
  70                     if (start > end) {
  71                         int t = start;
  72                         start = end;
  73                         end = t;
  74                     }
  75                     if (nocase) {
  76                         start = tolower(start);
  77                         end = tolower(end);
  78                         c = tolower(c);
  79                     }
  80                     pattern += 2;
  81                     patternLen -= 2;
  82                     if (c >= start && c <= end)
  83                         match = 1;
  84                 } else {
  85                     if (!nocase) {
  86                         if (pattern[0] == string[0])
  87                             match = 1;
  88                     } else {
  89                         if (tolower((int)pattern[0]) == tolower((int)string[0]))
  90                             match = 1;
  91                     }
  92                 }
  93                 pattern++;
  94                 patternLen--;
  95             }
  96             if (not)
  97                 match = !match;
  98             if (!match)
  99                 return 0; /* no match */
 100             string++;
 101             stringLen--;
 102             break;
 103         }
 104         case '\\':
 105             if (patternLen >= 2) {
 106                 pattern++;
 107                 patternLen--;
 108             }
 109             /* fall through */
 110         default:
 111             if (!nocase) {
 112                 if (pattern[0] != string[0])
 113                     return 0; /* no match */
 114             } else {
 115                 if (tolower((int)pattern[0]) != tolower((int)string[0]))
 116                     return 0; /* no match */
 117             }
 118             string++;
 119             stringLen--;
 120             break;
 121         }
 122         pattern++;
 123         patternLen--;
 124         if (stringLen == 0) {
 125             while(*pattern == '*') {
 126                 pattern++;
 127                 patternLen--;
 128             }
 129             break;
 130         }
 131     }
 132     if (patternLen == 0 && stringLen == 0)
 133         return 1;
 134     return 0;
 135 }
 136
 137 int stringmatch(const char *pattern, const char *string, int nocase) {
 138     return stringmatchlen(pattern,strlen(pattern),string,strlen(string),nocase);
 139 }
 140
 141 /* Convert a string representing an amount of memory into the number of
 142  * bytes, so for instance memtoll("1Gi") will return 1073741824 that is
 143  * (1024*1024*1024).
 144  *
 145  * On parsing error, if *err is not NULL, it's set to 1, otherwise it's
 146  * set to 0 */
 147 long long memtoll(const char *p, int *err) {
 148     const char *u;
 149     char buf[128];
 150     long mul; /* unit multiplier */
 151     long long val;
 152     unsigned int digits;
 153
 154     if (err) *err = 0;
 155     /* Search the first non digit character. */
 156     u = p;
 157     if (*u == '-') u++;
 158     while(*u && isdigit(*u)) u++;
 159     if (*u == '\0' || !strcasecmp(u,"b")) {
 160         mul = 1;
 161     } else if (!strcasecmp(u,"k")) {
 162         mul = 1000;
 163     } else if (!strcasecmp(u,"kb")) {
 164         mul = 1024;
 165     } else if (!strcasecmp(u,"m")) {
 166         mul = 1000*1000;
 167     } else if (!strcasecmp(u,"mb")) {
 168         mul = 1024*1024;
 169     } else if (!strcasecmp(u,"g")) {
 170         mul = 1000L*1000*1000;
 171     } else if (!strcasecmp(u,"gb")) {
 172         mul = 1024L*1024*1024;
 173     } else {
 174         if (err) *err = 1;
 175         mul = 1;
 176     }
 177     digits = u-p;
 178     if (digits >= sizeof(buf)) {
 179         if (err) *err = 1;
 180         return LLONG_MAX;
 181     }
 182     memcpy(buf,p,digits);
 183     buf[digits] = '\0';
 184     val = strtoll(buf,NULL,10);
 185     return val*mul;
 186 }
 187
 188 /* Convert a long long into a string. Returns the number of
 189  * characters needed to represent the number, that can be shorter if passed
 190  * buffer length is not enough to store the whole number. */
 191 int ll2string(char *s, size_t len, long long value) {
 192     char buf[32], *p;
 193     unsigned long long v;
 194     size_t l;
 195
 196     if (len == 0) return 0;
 197     v = (value < 0) ? -value : value;
 198     p = buf+31; /* point to the last character */
 199     do {
 200         *p-- = '0'+(v%10);
 201         v /= 10;
 202     } while(v);
 203     if (value < 0) *p-- = '-';
 204     p++;
 205     l = 32-(p-buf);
 206     if (l+1 > len) l = len-1; /* Make sure it fits, including the nul term */
 207     memcpy(s,p,l);
 208     s[l] = '\0';
 209     return l;
 210 }
 211
 212 /* Convert a string into a long long. Returns 1 if the string could be parsed
 213  * into a (non-overflowing) long long, 0 otherwise. The value will be set to
 214  * the parsed value when appropriate. */
 215 int string2ll(const char *s, size_t slen, long long *value) {
 216     const char *p = s;
 217     size_t plen = 0;
 218     int negative = 0;
 219     unsigned long long v;
 220
 221     if (plen == slen)
 222         return 0;
 223
 224     /* Special case: first and only digit is 0. */
 225     if (slen == 1 && p[0] == '0') {
 226         if (value != NULL) *value = 0;
 227         return 1;
 228     }
 229
 230     if (p[0] == '-') {
 231         negative = 1;
 232         p++; plen++;
 233
 234         /* Abort on only a negative sign. */
 235         if (plen == slen)
 236             return 0;
 237     }
 238
 239     /* First digit should be 1-9, otherwise the string should just be 0. */
 240     if (p[0] >= '1' && p[0] <= '9') {
 241         v = p[0]-'0';
 242         p++; plen++;
 243     } else if (p[0] == '0' && slen == 1) {
 244         *value = 0;
 245         return 1;
 246     } else {
 247         return 0;
 248     }
 249
 250     while (plen < slen && p[0] >= '0' && p[0] <= '9') {
 251         if (v > (ULLONG_MAX / 10)) /* Overflow. */
 252             return 0;
 253         v *= 10;
 254
 255         if (v > (ULLONG_MAX - (p[0]-'0'))) /* Overflow. */
 256             return 0;
 257         v += p[0]-'0';
 258
 259         p++; plen++;
 260     }
 261
 262     /* Return if not all bytes were used. */
 263     if (plen < slen)
 264         return 0;
 265
 266     if (negative) {
 267         if (v > ((unsigned long long)(-(LLONG_MIN+1))+1)) /* Overflow. */
 268             return 0;
 269         if (value != NULL) *value = -v;
 270     } else {
 271         if (v > LLONG_MAX) /* Overflow. */
 272             return 0;
 273         if (value != NULL) *value = v;
 274     }
 275     return 1;
 276 }
 277
 278 /* Convert a string into a long. Returns 1 if the string could be parsed into a
 279  * (non-overflowing) long, 0 otherwise. The value will be set to the parsed
 280  * value when appropriate. */
 281 int string2l(const char *s, size_t slen, long *lval) {
 282     long long llval;
 283
 284     if (!string2ll(s,slen,&llval))
 285         return 0;
 286
 287     if (llval < LONG_MIN || llval > LONG_MAX)
 288         return 0;
 289
 290     *lval = (long)llval;
 291     return 1;
 292 }
 293
 294 /* Convert a double to a string representation. Returns the number of bytes
 295  * required. The representation should always be parsable by stdtod(3). */
 296 int d2string(char *buf, size_t len, double value) {
 297     if (isnan(value)) {
 298         len = snprintf(buf,len,"nan");
 299     } else if (isinf(value)) {
 300         if (value < 0)
 301             len = snprintf(buf,len,"-inf");
 302         else
 303             len = snprintf(buf,len,"inf");
 304     } else if (value == 0) {
 305         /* See: http://en.wikipedia.org/wiki/Signed_zero, "Comparisons". */
 306         if (1.0/value < 0)
 307             len = snprintf(buf,len,"-0");
 308         else
 309             len = snprintf(buf,len,"0");
 310     } else {
 311 #if (DBL_MANT_DIG >= 52) && (LLONG_MAX == 0x7fffffffffffffffLL)
 312         /* Check if the float is in a safe range to be casted into a
 313          * long long. We are assuming that long long is 64 bit here.
 314          * Also we are assuming that there are no implementations around where
 315          * double has precision < 52 bit.
 316          *
 317          * Under this assumptions we test if a double is inside an interval
 318          * where casting to long long is safe. Then using two castings we
 319          * make sure the decimal part is zero. If all this is true we use
 320          * integer printing function that is much faster. */
 321         double min = -4503599627370495; /* (2^52)-1 */
 322         double max = 4503599627370496; /* -(2^52) */
 323         if (value > min && value < max && value == ((double)((long long)value)))
 324             len = ll2string(buf,len,(long long)value);
 325         else
 326 #endif
 327             len = snprintf(buf,len,"%.17g",value);
 328     }
 329
 330     return len;
 331 }
 332
 333 /* Generate the Redis "Run ID", a SHA1-sized random number that identifies a
 334  * given execution of Redis, so that if you are talking with an instance
 335  * having run_id == A, and you reconnect and it has run_id == B, you can be
 336  * sure that it is either a different instance or it was restarted. */
 337 void getRandomHexChars(char *p, unsigned int len) {
 338     FILE *fp = fopen("/dev/urandom","r");
 339     char *charset = "0123456789abcdef";
 340     unsigned int j;
 341
 342     if (fp == NULL || fread(p,len,1,fp) == 0) {
 343         /* If we can't read from /dev/urandom, do some reasonable effort
 344          * in order to create some entropy, since this function is used to
 345          * generate run_id and cluster instance IDs */
 346         char *x = p;
 347         unsigned int l = len;
 348         struct timeval tv;
 349         pid_t pid = getpid();
 350
 351         /* Use time and PID to fill the initial array. */
 352         gettimeofday(&tv,NULL);
 353         if (l >= sizeof(tv.tv_usec)) {
 354             memcpy(x,&tv.tv_usec,sizeof(tv.tv_usec));
 355             l -= sizeof(tv.tv_usec);
 356             x += sizeof(tv.tv_usec);
 357         }
 358         if (l >= sizeof(tv.tv_sec)) {
 359             memcpy(x,&tv.tv_sec,sizeof(tv.tv_sec));
 360             l -= sizeof(tv.tv_sec);
 361             x += sizeof(tv.tv_sec);
 362         }
 363         if (l >= sizeof(pid)) {
 364             memcpy(x,&pid,sizeof(pid));
 365             l -= sizeof(pid);
 366             x += sizeof(pid);
 367         }
 368         /* Finally xor it with rand() output, that was already seeded with
 369          * time() at startup. */
 370         for (j = 0; j < len; j++)
 371             p[j] ^= rand();
 372     }
 373     /* Turn it into hex digits taking just 4 bits out of 8 for every byte. */
 374     for (j = 0; j < len; j++)
 375         p[j] = charset[p[j] & 0x0F];
 376     fclose(fp);
 377 }
 378
 379 #ifdef UTIL_TEST_MAIN
 380 #include <assert.h>
 381
 382 void test_string2ll(void) {
 383     char buf[32];
 384     long long v;
 385
 386     /* May not start with +. */
 387     strcpy(buf,"+1");
 388     assert(string2ll(buf,strlen(buf),&v) == 0);
 389
 390     /* Leading space. */
 391     strcpy(buf," 1");
 392     assert(string2ll(buf,strlen(buf),&v) == 0);
 393
 394     /* Trailing space. */
 395     strcpy(buf,"1 ");
 396     assert(string2ll(buf,strlen(buf),&v) == 0);
 397
 398     /* May not start with 0. */
 399     strcpy(buf,"01");
 400     assert(string2ll(buf,strlen(buf),&v) == 0);
 401
 402     strcpy(buf,"-1");
 403     assert(string2ll(buf,strlen(buf),&v) == 1);
 404     assert(v == -1);
 405
 406     strcpy(buf,"0");
 407     assert(string2ll(buf,strlen(buf),&v) == 1);
 408     assert(v == 0);
 409
 410     strcpy(buf,"1");
 411     assert(string2ll(buf,strlen(buf),&v) == 1);
 412     assert(v == 1);
 413
 414     strcpy(buf,"99");
 415     assert(string2ll(buf,strlen(buf),&v) == 1);
 416     assert(v == 99);
 417
 418     strcpy(buf,"-99");
 419     assert(string2ll(buf,strlen(buf),&v) == 1);
 420     assert(v == -99);
 421
 422     strcpy(buf,"-9223372036854775808");
 423     assert(string2ll(buf,strlen(buf),&v) == 1);
 424     assert(v == LLONG_MIN);
 425
 426     strcpy(buf,"-9223372036854775809"); /* overflow */
 427     assert(string2ll(buf,strlen(buf),&v) == 0);
 428
 429     strcpy(buf,"9223372036854775807");
 430     assert(string2ll(buf,strlen(buf),&v) == 1);
 431     assert(v == LLONG_MAX);
 432
 433     strcpy(buf,"9223372036854775808"); /* overflow */
 434     assert(string2ll(buf,strlen(buf),&v) == 0);
 435 }
 436
 437 void test_string2l(void) {
 438     char buf[32];
 439     long v;
 440
 441     /* May not start with +. */
 442     strcpy(buf,"+1");
 443     assert(string2l(buf,strlen(buf),&v) == 0);
 444
 445     /* May not start with 0. */
 446     strcpy(buf,"01");
 447     assert(string2l(buf,strlen(buf),&v) == 0);
 448
 449     strcpy(buf,"-1");
 450     assert(string2l(buf,strlen(buf),&v) == 1);
 451     assert(v == -1);
 452
 453     strcpy(buf,"0");
 454     assert(string2l(buf,strlen(buf),&v) == 1);
 455     assert(v == 0);
 456
 457     strcpy(buf,"1");
 458     assert(string2l(buf,strlen(buf),&v) == 1);
 459     assert(v == 1);
 460
 461     strcpy(buf,"99");
 462     assert(string2l(buf,strlen(buf),&v) == 1);
 463     assert(v == 99);
 464
 465     strcpy(buf,"-99");
 466     assert(string2l(buf,strlen(buf),&v) == 1);
 467     assert(v == -99);
 468
 469 #if LONG_MAX != LLONG_MAX
 470     strcpy(buf,"-2147483648");
 471     assert(string2l(buf,strlen(buf),&v) == 1);
 472     assert(v == LONG_MIN);
 473
 474     strcpy(buf,"-2147483649"); /* overflow */
 475     assert(string2l(buf,strlen(buf),&v) == 0);
 476
 477     strcpy(buf,"2147483647");
 478     assert(string2l(buf,strlen(buf),&v) == 1);
 479     assert(v == LONG_MAX);
 480
 481     strcpy(buf,"2147483648"); /* overflow */
 482     assert(string2l(buf,strlen(buf),&v) == 0);
 483 #endif
 484 }
 485
 486 int main(int argc, char **argv) {
 487     test_string2ll();
 488     test_string2l();
 489     return 0;
 490 }
 491 #endif