在上篇文章中初步的分析了一下，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] = 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[i]);
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:
/* 假设没有正則表達式的keyword符，则直接比較 */
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/facebook-engineering/three-optimization-tips-for-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[i];
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[i];
} /* Add sign. */
if (negative) dst[0] = '-';
return length;
}
digit[201]就是从00-99的数字字符，余数的赋值就通过这个数组，高效，方便，是提高了非常多的速度。又发现了Redis代码中的一些亮点。