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