[redis.git] / src / util.c

#include "redis.h"
#include <ctype.h>
#include <limits.h>
#include <math.h>

/* Glob-style pattern matching. */
int stringmatchlen(const char *pattern, int patternLen,
        const char *string, int stringLen, int nocase)
{
    while(patternLen) {
        switch(pattern[0]) {
        case '*':
            while (pattern[1] == '*') {
                pattern++;
                patternLen--;
            }
            if (patternLen == 1)
                return 1; /* match */
            while(stringLen) {
                if (stringmatchlen(pattern+1, patternLen-1,
                            string, stringLen, nocase))
                    return 1; /* match */
                string++;
                stringLen--;
            }
            return 0; /* no match */
            break;
        case '?':
            if (stringLen == 0)
                return 0; /* no match */
            string++;
            stringLen--;
            break;
        case '[':
        {
            int not, match;

            pattern++;
            patternLen--;
            not = pattern[0] == '^';
            if (not) {
                pattern++;
                patternLen--;
            }
            match = 0;
            while(1) {
                if (pattern[0] == '\\') {
                    pattern++;
                    patternLen--;
                    if (pattern[0] == string[0])
                        match = 1;
                } else if (pattern[0] == ']') {
                    break;
                } else if (patternLen == 0) {
                    pattern--;
                    patternLen++;
                    break;
                } else if (pattern[1] == '-' && patternLen >= 3) {
                    int start = pattern[0];
                    int end = pattern[2];
                    int c = string[0];
                    if (start > end) {
                        int t = start;
                        start = end;
                        end = t;
                    }
                    if (nocase) {
                        start = tolower(start);
                        end = tolower(end);
                        c = tolower(c);
                    }
                    pattern += 2;
                    patternLen -= 2;
                    if (c >= start && c <= end)
                        match = 1;
                } else {
                    if (!nocase) {
                        if (pattern[0] == string[0])
                            match = 1;
                    } else {
                        if (tolower((int)pattern[0]) == tolower((int)string[0]))
                            match = 1;
                    }
                }
                pattern++;
                patternLen--;
            }
            if (not)
                match = !match;
            if (!match)
                return 0; /* no match */
            string++;
            stringLen--;
            break;
        }
        case '\\':
            if (patternLen >= 2) {
                pattern++;
                patternLen--;
            }
            /* fall through */
        default:
            if (!nocase) {
                if (pattern[0] != string[0])
                    return 0; /* no match */
            } else {
                if (tolower((int)pattern[0]) != tolower((int)string[0]))
                    return 0; /* no match */
            }
            string++;
            stringLen--;
            break;
        }
        pattern++;
        patternLen--;
        if (stringLen == 0) {
            while(*pattern == '*') {
                pattern++;
                patternLen--;
            }
            break;
        }
    }
    if (patternLen == 0 && stringLen == 0)
        return 1;
    return 0;
}

int stringmatch(const char *pattern, const char *string, int nocase) {
    return stringmatchlen(pattern,strlen(pattern),string,strlen(string),nocase);
}

/* Convert a string representing an amount of memory into the number of
 * bytes, so for instance memtoll("1Gi") will return 1073741824 that is
 * (1024*1024*1024).
 *
 * On parsing error, if *err is not NULL, it's set to 1, otherwise it's
 * set to 0 */
long long memtoll(const char *p, int *err) {
    const char *u;
    char buf[128];
    long mul; /* unit multiplier */
    long long val;
    unsigned int digits;

    if (err) *err = 0;
    /* Search the first non digit character. */
    u = p;
    if (*u == '-') u++;
    while(*u && isdigit(*u)) u++;
    if (*u == '\0' || !strcasecmp(u,"b")) {
        mul = 1;
    } else if (!strcasecmp(u,"k")) {
        mul = 1000;
    } else if (!strcasecmp(u,"kb")) {
        mul = 1024;
    } else if (!strcasecmp(u,"m")) {
        mul = 1000*1000;
    } else if (!strcasecmp(u,"mb")) {
        mul = 1024*1024;
    } else if (!strcasecmp(u,"g")) {
        mul = 1000L*1000*1000;
    } else if (!strcasecmp(u,"gb")) {
        mul = 1024L*1024*1024;
    } else {
        if (err) *err = 1;
        mul = 1;
    }
    digits = u-p;
    if (digits >= sizeof(buf)) {
        if (err) *err = 1;
        return LLONG_MAX;
    }
    memcpy(buf,p,digits);
    buf[digits] = '\0';
    val = strtoll(buf,NULL,10);
    return val*mul;
}

/* Convert a long long into a string. Returns the number of
 * characters needed to represent the number, that can be shorter if passed
 * buffer length is not enough to store the whole number. */
int ll2string(char *s, size_t len, long long value) {
    char buf[32], *p;
    unsigned long long v;
    size_t l;

    if (len == 0) return 0;
    v = (value < 0) ? -value : value;
    p = buf+31; /* point to the last character */
    do {
        *p-- = '0'+(v%10);
        v /= 10;
    } while(v);
    if (value < 0) *p-- = '-';
    p++;
    l = 32-(p-buf);
    if (l+1 > len) l = len-1; /* Make sure it fits, including the nul term */
    memcpy(s,p,l);
    s[l] = '\0';
    return l;
}

/* 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;
    size_t plen = 0;
    int negative = 0;
    unsigned long long v;

    if (plen == slen)
        return 0;

    if (p[0] == '-') {
        negative = 1;
        p++; plen++;

        /* Abort on only a negative sign. */
        if (plen == slen)
            return 0;
    }

    /* First digit should be 1-9, otherwise the string should just be 0. */
    if (p[0] >= '1' && p[0] <= '9') {
        v = p[0]-'0';
        p++; plen++;
    } else if (p[0] == '0' && slen == 1) {
        *value = 0;
        return 1;
    } else {
        return 0;
    }

    while (plen < slen && p[0] >= '0' && p[0] <= '9') {
        if (v > (ULLONG_MAX / 10)) /* Overflow. */
            return 0;
        v *= 10;

        if (v > (ULLONG_MAX - (p[0]-'0'))) /* Overflow. */
            return 0;
        v += p[0]-'0';

        p++; plen++;
    }

    /* Return if not all bytes were used. */
    if (plen < slen)
        return 0;

    if (negative) {
        if (v > (-(unsigned long long)LLONG_MIN)) /* Overflow. */
            return 0;
        if (value != NULL) *value = -v;
    } else {
        if (v > LLONG_MAX) /* Overflow. */
            return 0;
        if (value != NULL) *value = v;
    }
    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) {
    if (isnan(value)) {
        len = snprintf(buf,len,"nan");
    } else if (isinf(value)) {
        if (value < 0)
            len = snprintf(buf,len,"-inf");
        else
            len = snprintf(buf,len,"inf");
    } else if (value == 0) {
        /* See: http://en.wikipedia.org/wiki/Signed_zero, "Comparisons". */
        if (1.0/value < 0)
            len = snprintf(buf,len,"-0");
        else
            len = snprintf(buf,len,"0");
    } else {
#if (DBL_MANT_DIG >= 52) && (LLONG_MAX == 0x7fffffffffffffffLL)
        /* Check if the float is in a safe range to be casted into a
         * long long. We are assuming that long long is 64 bit here.
         * Also we are assuming that there are no implementations around where
         * double has precision < 52 bit.
         *
         * Under this assumptions we test if a double is inside an interval
         * where casting to long long is safe. Then using two castings we
         * make sure the decimal part is zero. If all this is true we use
         * integer printing function that is much faster. */
        double min = -4503599627370495; /* (2^52)-1 */
        double max = 4503599627370496; /* -(2^52) */
        if (val > min && val < max && value == ((double)((long long)value)))
            len = ll2string(buf,len,(long long)value);
        else
#endif
            len = snprintf(buf,len,"%.17g",value);
    }

    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;
}

int isStringRepresentableAsLong(sds s, long *longval) {
    long long ll;

    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;
}

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);
    }
}
Commit	Line	Data
e2641e09	1	#include "redis.h"
	2	#include <ctype.h>
	3	#include <limits.h>
672b0a1b	4	#include <math.h>
e2641e09	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	* (102410241024).
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 = 1000L10001000;
163	} else if (!strcasecmp(u,"gb")) {
164	mul = 1024L10241024;
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
d4e07f17 PN	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
5cbe90db	225	/* First digit should be 1-9, otherwise the string should just be 0. */
d4e07f17 PN	226	if (p[0] >= '1' && p[0] <= '9') {
	227	v = p[0]-'0';
	228	p++; plen++;
5cbe90db	229	} else if (p[0] == '0' && slen == 1) {
	230	*value = 0;
	231	return 1;
d4e07f17 PN	232	} else {
	233	return 0;
	234	}
	235
	236	while (plen < slen && p[0] >= '0' && p[0] <= '9') {
	237	if (v > (ULLONG_MAX / 10)) /* Overflow. */
	238	return 0;
	239	v *= 10;
	240
	241	if (v > (ULLONG_MAX - (p[0]-'0'))) /* Overflow. */
	242	return 0;
	243	v += p[0]-'0';
	244
	245	p++; plen++;
	246	}
	247
	248	/* Return if not all bytes were used. */
	249	if (plen < slen)
	250	return 0;
	251
	252	if (negative) {
	253	if (v > (-(unsigned long long)LLONG_MIN)) /* Overflow. */
	254	return 0;
	255	if (value != NULL) *value = -v;
	256	} else {
	257	if (v > LLONG_MAX) /* Overflow. */
	258	return 0;
	259	if (value != NULL) *value = v;
	260	}
	261	return 1;
	262	}
	263
672b0a1b PN	264	/* Convert a double to a string representation. Returns the number of bytes
	265	* required. The representation should always be parsable by stdtod(3). */
	266	int d2string(char *buf, size_t len, double value) {
	267	if (isnan(value)) {
	268	len = snprintf(buf,len,"nan");
	269	} else if (isinf(value)) {
	270	if (value < 0)
	271	len = snprintf(buf,len,"-inf");
	272	else
	273	len = snprintf(buf,len,"inf");
	274	} else if (value == 0) {
	275	/* See: http://en.wikipedia.org/wiki/Signed_zero, "Comparisons". */
	276	if (1.0/value < 0)
	277	len = snprintf(buf,len,"-0");
	278	else
	279	len = snprintf(buf,len,"0");
	280	} else {
	281	#if (DBL_MANT_DIG >= 52) && (LLONG_MAX == 0x7fffffffffffffffLL)
	282	/* Check if the float is in a safe range to be casted into a
	283	* long long. We are assuming that long long is 64 bit here.
	284	* Also we are assuming that there are no implementations around where
	285	* double has precision < 52 bit.
	286	*
	287	* Under this assumptions we test if a double is inside an interval
	288	* where casting to long long is safe. Then using two castings we
	289	* make sure the decimal part is zero. If all this is true we use
	290	* integer printing function that is much faster. */
	291	double min = -4503599627370495; /* (2^52)-1 */
	292	double max = 4503599627370496; /* -(2^52) */
	293	if (val > min && val < max && value == ((double)((long long)value)))
	294	len = ll2string(buf,len,(long long)value);
	295	else
	296	#endif
	297	len = snprintf(buf,len,"%.17g",value);
	298	}
	299
	300	return len;
	301	}
	302
ec7e1389	303	/* Check if the sds string 's' can be represented by a long long
e2641e09	304	* (that is, is a number that fits into long without any other space or
ec7e1389	305	* character before or after the digits, so that converting this number
ec7e1389	306	* back to a string will result in the same bytes as the original string).
e2641e09	307	*
ec7e1389	308	* If so, the function returns REDIS_OK and *llongval is set to the value
e2641e09	309	* of the number. Otherwise REDIS_ERR is returned */
ec7e1389	310	int isStringRepresentableAsLongLong(sds s, long long *llongval) {
e2641e09	311	char buf[32], *endptr;
ec7e1389	312	long long value;
e2641e09	313	int slen;
e2641e09	314
ec7e1389	315	value = strtoll(s, &endptr, 10);
e2641e09	316	if (endptr[0] != '\0') return REDIS_ERR;
	317	slen = ll2string(buf,32,value);
	318
	319	/* If the number converted back into a string is not identical
	320	* then it's not possible to encode the string as integer */
	321	if (sdslen(s) != (unsigned)slen \|\| memcmp(buf,s,slen)) return REDIS_ERR;
ec7e1389	322	if (llongval) *llongval = value;
	323	return REDIS_OK;
	324	}
	325
	326	int isStringRepresentableAsLong(sds s, long *longval) {
	327	long long ll;
	328
	329	if (isStringRepresentableAsLongLong(s,&ll) == REDIS_ERR) return REDIS_ERR;
	330	if (ll < LONG_MIN \|\| ll > LONG_MAX) return REDIS_ERR;
	331	*longval = (long)ll;
e2641e09	332	return REDIS_OK;
e2641e09	333	}
ec7e1389	334
	335	int isObjectRepresentableAsLongLong(robj o, long long llongval) {
	336	redisAssert(o->type == REDIS_STRING);
	337	if (o->encoding == REDIS_ENCODING_INT) {
	338	if (llongval) *llongval = (long) o->ptr;
	339	return REDIS_OK;
	340	} else {
	341	return isStringRepresentableAsLongLong(o->ptr,llongval);
	342	}
	343	}