（二十四）--- tool工具類（2） · Redis源碼分析

? ? ? ? ? 在上篇文章中初步的分析了一下，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: /* 如果沒有正則表達式的關鍵字符，則直接比較 */ 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代碼中的一些亮點。