Redis源码分析（二十四）--- tool工具类（2）

rwewqe

      在上篇文章中初步的分析了一下，Redis工具类文件中的一些用法，包括2个随机算法和循环冗余校验算法，今天，继续学习Redis中的其他的一些辅助工具类的用法。包括里面的大小端转换算法，sha算法在Redis中的实现和通用工具类算法util.c。

         先来看看大小端转换算法，大小端学习过操作系统的人一定知道是什么意思，在不同的操作系统中，高位数字的存储方式存在，高位在前，低位在后，或是高位在后，低位在前，所以这里面就涉及到转换，根据不同的操作系统，有不同的转换方式，所以Redis在这方面就开放了这样一批的API；



    /* 对于16位，32位，64位作大小端的转换 */  
    void memrev16(void *p);  
    void memrev32(void *p);  
    void memrev64(void *p);  
    uint16_t intrev16(uint16_t v);  
    uint32_t intrev32(uint32_t v);  
    uint64_t intrev64(uint64_t v);  

挑出其中的一个API的实现:



    /* Toggle the 32 bit unsigned integer pointed by *p from little endian to
     * big endian */  
    /* 32位需要4个字节，第0和第3个，第1和第2个字节作交换 */   
    void memrev32(void *p) {  
        unsigned char *x = p, t;  
      
        t = x[0];  
        x[0] = x[3];  
        x[3] = t;  
        t = x[1];  
        x[1] = x[2];  
        x[2] = t;  
    }  

总之就是做头尾部的交换。

       下面在Redis中的加密算法的实现，采用的是SHA算法，/SHA：Secure Hash Algorithm安全散列算法,与MD5算法类似，也是属于单向加密算法，在加密长度上，做了很大的扩展，安全性也更高长度不超过2^64位的字符串或二进制流，经过SHA-1编码后，生成一个160位的二进制串 。在Redis中的C语言调用:



    int  
    main(int argc, char **argv)  
    {  
        SHA1_CTX ctx;  
        unsigned char hash[20], buf[BUFSIZE];  
        int i;  
      
        for(i=0;i<BUFSIZE;i++)  
            buf = i;  
        /* Redis代码中SHA算法的调用方法 */  
        SHA1Init(&ctx);  
        for(i=0;i<1000;i++)  
            SHA1Update(&ctx, buf, BUFSIZE);  
        SHA1Final(hash, &ctx);  
      
        printf("SHA1=");  
        for(i=0;i<20;i++)  
            printf("%02x", hash);  
        printf("\n");  
        return 0;  
    }  

        最后说说里面的util.c通用工具类的算法实现，里面可是有许多亮点的存在，先给出具体的API，主要涉及的是数字和字符串之间的转换:



    int stringmatchlen(const char *p, int plen, const char *s, int slen, int nocase); /*支持glob-style的通配符格式,如*表示任意一个或多个字符,?表示任意字符,[abc]表示方括号中任意一个字母。*/  
    int stringmatch(const char *p, const char *s, int nocase); /*支持glob-style的通配符格式,长度的计算直接放在方法内部了，直接传入模式和原字符串*/  
    long long memtoll(const char *p, int *err); /* 内存大小转化为单位为字节大小的数值表示 */  
    int ll2string(char *s, size_t len, long long value); /* long long类型转化为string类型 */  
    int string2ll(const char *s, size_t slen, long long *value); /* String类型转换为long long类型 */  
    int string2l(const char *s, size_t slen, long *value); /* String类型转换为long类型，核心调用的方法还是string2ll()方法 */  
    int d2string(char *buf, size_t len, double value); /* double类型转化为String类型 */  
    sds getAbsolutePath(char *filename); /* 获取输入文件名的绝对路径 */  
    int pathIsBaseName(char *path); /* 判断一个路径是否就是纯粹的文件名，不是相对路径或是绝对路径 */  

看第一个方法，正则表达式匹配的原理实现，平时我们只知道去调用系统的正则表达式去匹配字符串，却不知道其中的原理，今天总是明白了:



    /* Glob-style pattern matching. */  
    /*支持glob-style的通配符格式,如*表示任意一个或多个字符,?表示任意字符,[abc]表示方括号中任意一个字母。*/  
    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)  
            //如果匹配字符和模式字符匹配的长度都减少到0了，说明匹配成功了  
            return 1;  
        return 0;  
    }  

非常神奇的代码吧，从来没有想过去实现正则表达式原理的代码。还有一个方法是ll2string方法，数字转字符的方法，如果是我们平常的做法，就是除10取余，加上对应的数字字符，但是要转换的可是ll类型啊，长度非常长，效率会导致比较低，所以在Redis中作者，直接按除100算，2位，2位的赋值，而且用数字字符数字，做处理，直接按下标来赋值，避免了对余数的多次判断:



    /* Convert a long long into a string. Returns the number of
     * characters needed to represent the number.
     * If the buffer is not big enough to store the string, 0 is returned.
     *
     * Based on the following article (that apparently does not provide a
     * novel approach but only publicizes an already used technique):
     *
     * https://www.facebook.com/notes/f ... c/10151361643253920
     *
     * Modified in order to handle signed integers since the original code was
     * designed for unsigned integers. */  
    /* long long类型转化为string类型 */  
    int ll2string(char* dst, size_t dstlen, long long svalue) {  
        static const char digits[201] =  
            "0001020304050607080910111213141516171819"  
            "2021222324252627282930313233343536373839"  
            "4041424344454647484950515253545556575859"  
            "6061626364656667686970717273747576777879"  
            "8081828384858687888990919293949596979899";  
        int negative;  
        unsigned long long value;  
      
        /* The main loop works with 64bit unsigned integers for simplicity, so
         * we convert the number here and remember if it is negative. */  
        /* 在这里做正负号的判断处理 */  
        if (svalue < 0) {  
            if (svalue != LLONG_MIN) {  
                value = -svalue;  
            } else {  
                value = ((unsigned long long) LLONG_MAX)+1;  
            }  
            negative = 1;  
        } else {  
            value = svalue;  
            negative = 0;  
        }  
      
        /* Check length. */  
        uint32_t const length = digits10(value)+negative;  
        if (length >= dstlen) return 0;  
      
        /* Null term. */  
        uint32_t next = length;  
        dst[next] = '\0';  
        next--;  
        while (value >= 100) {  
            //做值的换算  
            int const i = (value % 100) * 2;  
            value /= 100;  
            //i所代表的余数值用digits字符数组中的对应数字代替了  
            dst[next] = digits[i + 1];  
            dst[next - 1] = digits;  
            next -= 2;  
        }  
      
        /* Handle last 1-2 digits. */  
        if (value < 10) {  
            dst[next] = '0' + (uint32_t) value;  
        } else {  
            int i = (uint32_t) value * 2;  
            dst[next] = digits[i + 1];  
            dst[next - 1] = digits;  
        }  
      
        /* Add sign. */  
        if (negative) dst[0] = '-';  
        return length;  
    }  

digit[201]就是从00-99的数字字符，余数的赋值就通过这个数组，高效，方便，是提高了很多的速度。又发现了Redis代码中的一些亮点。