前言源码在 sphinx 官网上就可以下载到.
起初我下载的是最新版本，结果由于代码大约有 10w 行，我看了快 1w 行后发现这样看也不是个办法。
于是我想着生成一个项目关系图来阅读代码，但是我这电脑只有windows, 网上介绍的大多都是 linux 上的，于是我只好取消这个念头。
后来，我想我看sphinx源码主要是先弄明白 sphinx 的工作原理，而工作原理应该一直都是保持不变的，于是我就去下载第一个版本。
第一个版本果然给力，只有 1w 行，于是我就开始高高兴兴的开始从 main 函数开始看源代码了。
看了不就发现 sphinx 用了很多数据结构，而且是自己等装好的，还是先把这些数据结构弄明白了比较好。
于是就有了这篇文章。
为了方便读者阅读，这些数据结构和算法就从简单的慢慢罗列出来。
大家可以看右面的目录，然后去看自己感兴趣的数据结构或算法对应的小节。
如果对那个小节有疑问，可以随时留言。
两个数的最值sphinx 把最值封装成了一个宏。
#define min(a,b) ((a)(b)?(a):(b))
交换两个数为了这个通用，使用了基本的模板函数。
而交换则使用第三个缓存变量来实现这个功能。
template inline void swap(t & v1, t & v2) { t temp = v1; v1 = v2; v2 = temp;}
向量vector这个 vector 实现的功能很简单，基本的 insert，remove，get, set 等操作。
只是附加了一个排序功能。
具体实现方式这里就不多说了，这些都是一个类基本的操作，都很容易实现(需要谁需要这个vector的实现讲解，可以留言)。
template class csphvector { public: csphvector(); //初始化向量 ~csphvector(); //回收向量 t & add(); //增加一个元素，返回这个元素的引用 void add(const t & tvalue);//增加一个元素 t & last();//得到最后一个元素 void remove(int iindex);//删除指定位置的元素 void grow(int inewlimit);//扩大缓存的大小，两倍两倍的增长 void resize(int inewlength);// 原先设置数组的大小 void reset();// 重置数组 int getlength();//得到数组的长度 void sort(int istart = 0, int iend = -1);// 正常排序 void rsort(int istart = 0, int iend = -1);// 逆序 const t & operator [](int iindex) const;// 读指定位置的值 t & operator [](int iindex);// 设置指定位置的值 private: int m_ilength;//数组大小 int m_ilimit;//数组缓存大小 t * m_pdata;//数组};
string 类实现这次 sphinx 自己实现的 string 类的功能就比较多了。
这里我罗列出一些比较简单的功能。
struct csphstring{ csphstring (); //构造 csphstring ( const char * sstring ); csphstring ( const csphstring & rhs ); csphstring ( const char * svalue, int ilen ); ~csphstring (); //析构 const char * cstr () const; //得到字符串 const char * scstr() const;//得到字符串，默认未空串 inline bool operator == ( const char * t ) const; //判断两个串是否相等 inline bool operator == ( const csphstring & t ) const; inline bool operator != ( const csphstring & t ) const; bool operator != ( const char * t ) const; const csphstring & operator = ( const csphstring & rhs ); csphstring substring ( int istart, int icount ) const; bool isempty () const; csphstring & tolower (); csphstring & toupper (); int length () const; bool operator ='0' && c='a' && c='a' && c=sline && isspace(*p) ) p--; p[1] = '\0'; return sline;}static char * trim ( char * sline ){ return ltrim ( rtrim ( sline ) );}
切割字符串切割字符串也是很常用的函数。
一般需要指定分隔符，默认分隔符是空白。
具体的实现代码这里就不展示了。
void sphsplit ( csphvector & dout, const char * sin, const char * sbounds ){ if ( !sin )return; const char * p = (char*)sin; while ( *p ){ // skip until the first non-boundary character const char * snext = p; while ( *p && !strchr ( sbounds, *p ) )p++; // add the token, skip the char dout.add().setbinary ( snext, p-snext ); p++; }}
正则匹配正则表达式大家都用过吧，这次 sphinx 实现了一个简单的正则表达式检验函数。
主要用于检验一个字符串是否符合指定的格式。
bool sphwildcardmatch ( const char * sstring, const char * spattern ){ if ( !sstring || !spattern )return false; const char * s = sstring; const char * p = spattern; while ( *s ){ switch ( *p ){ case '\\': // escaped char, strict match the next one literally p++; if ( *s++!=*p++ )return false; break; case '?': // match any character s++; p++; break; case '%': // gotta match either 0 or 1 characters // well, lets look ahead and see what we need to match next p++; // just a shortcut, %* can be folded to just * if ( *p=='*' )break; // plain char after a hash? check the non-ambiguous cases if ( !sphiswild(*p) ){ if ( s[0]!=*p ){ // hash does not match 0 chars // check if we can match 1 char, or it's a no-match if ( s[1]!=*p )return false; s++; break; } else{ // hash matches 0 chars // check if we could ambiguously match 1 char too, though if ( s[1]!=*p )break; // well, fall through to scan both options route } } // could not decide yet // so just recurse both options if ( sphwildcardmatch ( s, p ) )return true; if ( sphwildcardmatch ( s+1, p ) )return true; return false; case '*': // skip all the extra stars and question marks for ( p++; *p=='*' || *p=='?'; p++ ) if ( *p=='?' ){ s++; if ( !*s )return p[1]=='\0'; } // short-circuit trailing star if ( !*p )return true; // so our wildcard expects a real character // scan forward for its occurrences and recurse for ( ;; ){ if ( !*s )return false; if ( *s==*p && sphwildcardmatch ( s+1, p+1 ) )return true; s++; } break; default: // default case, strict match if ( *s++!=*p++ )return false; break; } } // string done // pattern should be either done too, or a trailing star, or a trailing hash return p[0]=='\0'|| ( p[0]=='*' && p[1]=='\0' )|| ( p[0]=='%' && p[1]=='\0' );}
日志系统做项目的时候经常会遇到一些打日志的库，其实这个功能很简单。
基本原理都是使用和 printf 类似的方法: 变参。
static void stdoutlogger ( esphloglevel elevel, const char * sfmt, va_list ap ){ switch ( elevel ){ case sph_log_fatal: fprintf ( stdout, fatal: ); break; case sph_log_warning: fprintf ( stdout, warning: ); break; case sph_log_info: fprintf ( stdout, warning: ); break; case sph_log_debug: fprintf ( stdout, debug: ); break; } vfprintf ( stdout, sfmt, ap ); fprintf ( stdout, \n );}static sphlogger_fn g_plogger = &stdoutlogger;inline void log ( esphloglevel elevel, const char * sfmt, va_list ap ){ if ( !g_plogger ) return; ( *g_plogger ) ( elevel, sfmt, ap );}void sphwarning ( const char * sfmt, ... ){ va_list ap; va_start ( ap, sfmt ); log ( sph_log_warning, sfmt, ap ); va_end ( ap );}void sphinfo ( const char * sfmt, ... );void sphlogfatal ( const char * sfmt, ... );void sphlogdebug ( const char * sfmt, ... );
变参的实现上面的日志系统，最后还是调用了 vfprintf 函数， 没有让我们看到变参到底怎么实现的。
但是 sphinx 自己实现了一个 sphvsprintf 函数，和 vfprintf 类似，我不明白那个日志系统为什么不用自己的这个输出函数。
由于是对字符串分析，可以理解为一个简单的自动机。
遇到什么字符，期望下个字符是什么。
这里就不多说这个自动机了。
static int sphvsprintf ( char * poutput, const char * sfmt, va_list ap ){ enum estates { snormal, spercent, shavefill, sinwidth, sinprec }; estates state = snormal; int iprec = 0; int iwidth = 0; char cfill = ' '; const char * pbegin = poutput; bool bheadingspace = true; char c; while ( ( c = *sfmt++ )!=0 ){ // handle percent if ( c=='%' ){ if ( state==snormal ){ state = spercent; iprec = 0; iwidth = 0; cfill = ' '; } else{ state = snormal; *poutput++ = c; } continue; } // handle regular chars if ( state==snormal ){ *poutput++ = c; continue; } // handle modifiers switch ( c ){ case '0': if ( state==spercent ){ cfill = '0'; state = shavefill; break; } case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': if ( state==spercent || state==shavefill ) { state = sinwidth; iwidth = c - '0'; } else if ( state==sinwidth ) iwidth = iwidth * 10 + c - '0'; else if ( state==sinprec ) iprec = iprec * 10 + c - '0'; break; case '-': if ( state==spercent ) bheadingspace = false; else state = snormal; // fixme? means that bad/unhandled syntax with dash will be just ignored break; case '.': state = sinprec; iprec = 0; break; case 's': // string { const char * pvalue = va_arg ( ap, const char * ); if ( !pvalue ) pvalue = (null); int ivalue = strlen ( pvalue ); if ( iwidth && bheadingspace ) while ( ivalue < iwidth-- ) *poutput++ = ' '; if ( iprec && iprec 1) & 033333333333) - ((n >> 2) & 011111111111); return ( (tmp + (tmp >> 3) ) & 030707070707) % 63;}
整数二进制的位数/// how much bits do we need for given intinline int sphlog2 ( uint64_t uvalue ){#if use_windows dword ures; if ( bitscanreverse ( &ures, (dword)( uvalue>>32 ) ) ) return 33+ures; bitscanreverse ( &ures, dword(uvalue) ); return 1+ures;#elif __gnuc__ || __clang__ if ( !uvalue ) return 0; return 64 - __builtin_clzl(uvalue);#else int ibits = 0; while ( uvalue ) { uvalue >>= 1; ibits++; } return ibits;#endif}
模板 堆排序这个堆排序写的太奇葩了，哎，不能说什么了。
/// generic accessortemplate struct sphaccessor_t{ t & key ( t * a ) const; //得到指针的值 void copykey ( t * pmed, t * pval ) const; void swap ( t * a, t * b ) const; t * add ( t * p, int i ) const;//第i个位置的指针 int sub ( t * b, t * a ) const;//指针偏移量};/// heap sort helper// 自底向上进行堆排序//pdata 带排序数组//istart 开始位置//iend 结束位置//comp 比较函数//acc 访问指针的类template void sphsiftdown ( t * pdata, int istart, int iend, u comp, v acc ){ for ( ;; ){ int ichild = istart*2+1; if ( ichild>iend )return; int ichild1 = ichild+1; if ( ichild11; istart>=0; istart-- ) sphsiftdown ( pdata, istart, icount-1, comp, acc ); // now keep popping root into the end of array for ( int iend=icount-1; iend>0; ){ acc.swap ( pdata, acc.add ( pdata, iend ) ); sphsiftdown ( pdata, 0, --iend, comp, acc ); }}
快速排序sphinx 的快速排序也很奇葩。
一般的快速排序是递归，sphinx使用栈模拟递归。
这样栈的大小大概就是 log(n) 了。
而且栈为空的时候共有 log(n) 次。
当数据特殊的时候，快排会退化为 n^2 的复杂度，这个时候，栈为空的几率变大了。
于是 sphinx 加了个修复， 当栈为空的次数大于 2.5 * log(n)， 就是用上面那个奇葩的堆排序。
不过这个优化作用不大。
另外这个快排加了一个小优化：当需要排序的数量小于32时，使用插入排序。
template void sphsort ( t * pdata, int icount, u comp, v acc ){ if ( icount<2 )return; typedef t * p; // st0 and st1 are stacks with left and right bounds of array-part. // they allow us to avoid recursion in quicksort implementation. p st0[32], st1[32], a, b, i, j; typename v::median_type x; int k; const int small_thresh = 32; int idepthlimit = sphlog2 ( icount ); idepthlimit = ( ( idepthlimit 1; // x2.5 k = 1; st0[0] = pdata; st1[0] = acc.add ( pdata, icount-1 ); while ( k ){ k--; i = a = st0[k]; j = b = st1[k]; // if quicksort fails on this data; switch to heapsort if ( !k ){ if ( !--idepthlimit ){ sphheapsort ( a, acc.sub ( b, a )+1, comp, acc ); return; } } // for tiny arrays, switch to insertion sort int ilen = acc.sub ( b, a ); if ( ilen<=small_thresh ){ for ( i=acc.add ( a, 1 ); ia; ){ p j1 = acc.add ( j, -1 ); if ( comp.isless ( acc.key(j1), acc.key(j) ) ) break; acc.swap ( j, j1 ); j = j1; } } continue; } // attention! this copy can lead to memleaks if your copykey // copies something which is not freed by objects destructor. acc.copykey ( &x, acc.add ( a, ilen/2 ) ); while ( a 数组去重要想去重，首先需要排序，所以这里假设容器是已经排完序的了。
然后假设 idst 的上一个就是目前比较的值。
如果和上一个相等，则isrc后移。
如果和上一个不相等，则找到一个新的值，将idst位置置为新值，个数加1即可。
/// generic uniqtemplate t_counter sphuniq ( t * pdata, t_counter icount ){ if ( !icount )return 0; t_counter isrc = 1, idst = 1; while ( isrc