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
	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	* (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
	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, otherwise the string should just be 0. */
	226	if (p[0] >= '1' && p[0] <= '9') {
	227	v = p[0]-'0';
	228	p++; plen++;
	229	} else if (p[0] == '0' && slen == 1) {
	230	*value = 0;
	231	return 1;
	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
	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
	303	/* Check if the sds string 's' can be represented by a long long
	304	* (that is, is a number that fits into long without any other space or
	305	* character before or after the digits, so that converting this number
	306	* back to a string will result in the same bytes as the original string).
	307	*
	308	* If so, the function returns REDIS_OK and *llongval is set to the value
	309	* of the number. Otherwise REDIS_ERR is returned */
	310	int isStringRepresentableAsLongLong(sds s, long long *llongval) {
	311	char buf[32], *endptr;
	312	long long value;
	313	int slen;
	314
	315	value = strtoll(s, &endptr, 10);
	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;
	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;
	332	return REDIS_OK;
	333	}
	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	}