sphinx 源码阅读之json, hash table配置分析器-tutorial mysql-php.cn

前言读了 sphinx 的读取配置文件的代码，心中有一个疑问： sphinx 为什么要自己造轮子呢？难道现在 sphinx 一直没人升级维护也是这个历史包袱的原因吗？不管哪么多了，先来看看 sphinx 怎么分析配置文件以及储存配置文件的吧。配置文件规则下面是一个

json-cover auto-string

前言

读了 sphinx 的读取配置文件的代码，心中有一个疑问： sphinx 为什么要自己造轮子呢？
难道现在 sphinx 一直没人升级维护也是这个历史包袱的原因吗？

不管哪么多了，先来看看 sphinx 怎么分析配置文件以及储存配置文件的吧。

配置文件规则

下面是一个简单的还有增量索引的 sphinx 配置文件。
其中 inc_source 继承 base_source 源。
inc_index 继承 inc_index 索引。然后又简单的配置了 indexer 和 searchd 选项。

source base_source {
    type            = mysql
    sql_host        = 127.0.0.1 
    sql_user        = test 
    sql_pass        = test
    sql_db          = d_test 
    sql_port        = 3306
    sql_query_pre= SET NAMES utf8
    sql_query = select c_id, c_title, c_content, c_comments, c_mtime FROM t_post;
    sql_attr_uint = c_comments
    sql_attr_string = c_title 
    sql_field_string = c_content
    sql_field_string = c_mtime
}
source inc_source : base_source{
    sql_query_pre = SET NAMES utf8
    sql_query = select c_id, c_title, c_content, c_comments FROM t_post where c_mtime >=(SELECT c_mtime FROM t_post_inc where c_id = 1) ; 
}
index base_index {
    source          = base_source 
    path            =  var/data/base_index
    docinfo         = extern
    charset_type        = zh_cn.utf-8 
    charset_dictpath =  etc/  
    ngram_len = 0
}
index inc_index : base_index{
    source = inc_source
    path =  var/data/inc_index
}
indexer{
    mem_limit       = 32M
}
searchd{
    listen          = 9312
    listen          = 9306:mysql41
    log         =  var/log/searchd.log
    query_log       =  var/log/query.log
    pid_file        =  var/log/searchd.pid
}

Salin selepas log masuk

配置文件数据结构

对于上面的配置文件，我们是可以用一个 json 来表示的。
也就是就是一系列的递归的 key-value 而已。
假设整个文件就是一个根的话，那么第一级儿子有 source, index, indexer, searchd 四个儿子。
然后对于 index 和 source 的儿子是个数组，数组的每个位置都是一个对象，因为可以配置多个 index 和 source.
对于 indexer 和 searchd 的儿子是一个对象。上面所说的对象就是一系列的 key-value 叶子节点。

对于根节点， sphinx 使用一个 hash 储存，实际上所有的节点都是使用 hash 来储存的。

/// config (hash of section types)
typedef SmallStringHash_T     CSphConfig;

Salin selepas log masuk

对于第二级节点，又是另一个 hash 对象。

/// config section type (hash of sections)
typedef SmallStringHash_T  CSphConfigType;

Salin selepas log masuk

CSphConfigSection 这一级需要表示两种类型：叶子节点和数组。
于是不是使用简单的 hash 对象，而需要在 hash 对象基础上封装一层。
实际上 sphinx 不是封装了一层，而是封装了三层。

/// config section (hash of variant values)
class CSphConfigSection : public SmallStringHash_T ;
/// small hash with string keys
template 
class SmallStringHash_T : public CSphOrderedHash ;
/// simple dynamic hash
/// implementation: fixed-size bucket + chaining
/// keeps the order, so Iterate() return the entries in the order they was inserted
/// WARNING: slow copy
template  class CSphOrderedHash;

Salin selepas log masuk

最后一层终于看到基类了。

json 与 hash table

看到这里，我们发现所有的节点都继承于 SmallStringHash_T 这个模板类。
这个类帮我们实现了储存 key-value 的方法。

那他是怎么实现的呢？
先说说需求吧，我们有一些列的 key-value, 然后我们实现快速添加和查找。

这个怎么看起来好熟悉的样子？
对了，这不正是 hash table 做的事情吗？
前几天我写了两篇文章 hash table 研究与实现和 memcached 源码阅读之 hash table .
难道这次又要写一个 sphinx 的 hash table 吗？

想要知道一个 key-value 是怎么储存的，只需要看看它的 add 函数就可以了。
下面就先来看看 sphinx 的 add 操作。

/// add new entry
/// returns true on success
/// returns false if this key is already hashed
bool Add ( const T & tValue, const KEY & tKey ){
    unsigned int uHash = ( (unsigned int) HASHFUNC::Hash ( tKey ) ) % LENGTH;
    // check if this key is already hashed
    HashEntry_t * pEntry = m_dHash [ uHash ];
    HashEntry_t ** ppEntry = &m_dHash [ uHash ];
    while ( pEntry ){
        if ( pEntry->m_tKey==tKey )return false;
        ppEntry = &pEntry->m_pNextByHash;
        pEntry =   pEntry->m_pNextByHash;
    }
    pEntry = new HashEntry_t;
    // do other thing
}

Salin selepas log masuk

好吧，看到上面那个循环，我又想起了 memcached 源码阅读之 hash table 顶端的封面图了。
典型的链表式 hash 。

什么意思呢？
hash 遇到冲突了，以链表的形式储存即可。

这里就不多说 sphinx 的 hash table 了。
然后我们通过 hash-table 的递归，我们就可以实现自己的 json 了吧。

唯一的不同时 json 储存的类型比较复杂，而我们的类型比较单一，叶子节点的值都是 string 和数字。
不过这并影响我们自己实现 json 的那些功能。

配置文件解析器

看到这里，我们就会发现储存配置信息并不是难题，现在的难题是怎么把这个配置文件转化为我们储存的数据结构。

其实我们的配置文件还是蛮复杂的，当然我是和 ini配置文件对比的。
像现在的配置文件，基本上都是这个形式，而且一般内部还要再嵌套几层。
不管配置文件有多复杂，对于我们这个配置文件解析器来说，都一样的。

为什么这个说呢?
作为修电脑专业，大家上大学的时候都学过编译原理这门课吧。
那门课的最初几张就是讲这个解析器的基本原理的，即自动机。

我们定义一套规则，配置文件按这套规则配置，解析器按照这套规则解析即可。

说了这个多，还是自动机的状态吧。

sphinx 的配置文件可以用下面这几个状态表示。

enum { S_TOP, S_SKIP2NL, S_TOK, S_TYPE, S_SEC, S_CHR, S_VALUE, S_SECNAME, S_SECBASE, S_KEY }

Salin selepas log masuk

S_TOP 是开始的状态。
而 S_SKIP2NL 是注释的状态，配置文件内一般只支持行注释，所以注释标示符后面的内容我们往往忽略掉。
当然一般第一行会有特殊的用处，sphinx 也有特殊的用处。
但是这个我查了文档没有找到， sphinx 源码有大概意思是可以执行指定程序，参数是这个配置文件。
我们不管这个了。我们就假设没有这一项就行了。

一般 S_TOP 状态下，忽略空白后，第一个遇到的就是 source， index, searchd, indexer 这四个串中的一个了。
所以 S_TOP 会先调用 S_TOK 去读取一个单词(token), 然后转到 S_TYPE 状态。

S_TYPE 会根据读取得到的字符串而分出两个状态来。
其中 source 和 index 会转向 S_SECNAME 状态，而 indexer， searchd，和 common 会转向 S_SEC 状态。

为什么要这么分呢？
那是因为 source 和 index 后面会有个名字，而其他的没有名字，直接就是 key-value 了。

S_SEC 状态简单，我们先看 S_SEC 状态的转移。
当然，在转移到 S_SEC 状态前，我们需要读取一个左大括号 "{", 读取一个确定的单词由状态 S_CHR 完成。
在 S_SEC 中，我们需要做的是读取一个 key-value, 其中 key-value 用等号分割。
于是第一次遇到非空字符，我们需要先读取 key, 于是 S_SEC 转移到状态 S_KEY。
而遇到结束符 "}" 代表这个配置结束。

状态 S_KEY 是一个token, 所以我们需要调用 S_TOK 状态来完成读取这个 token.

在 S_KEY 中，我们需要先读取一个确定的等号 "=" (状态 S_CHR)，然后读取 value, 于是转移到状态 S_VALUE。

在状态 S_VALUE 我们需要先把读到的 value 存起来，然后在遇到结束符的时候调用添加 key-value 的函数。

这个时候我们就完成了读取 S_SEC 状态的一个 key-value，直到读取到结束符 "}" 我们就回到了 S_TOP 状态。

当 S_TOP 转向 S_SECNAME 状态时，我们需要先读取配置名字。
于是我们先转向 S_TOK 状态读取一个 token.
然后会遇到两种情况：一种遇到了开始符号 "{"，我们转向状态 S_SEC。
另一种情况我们遇到 ":", 意思是这个配置要集成与之前的某个配置。
于是我们需要先读取一个 base 的名字，即转向状态 S_SECBASE 。

S_SECBASE 状态先转向 S_TOK 来读取一个 base 的名字。
然后会把名字为 base 的配置复制到当前配置。
接着就可以用 S_CHR 读取开始符 "{" 并转向状态 S_SEC 了。

这样状态自动机就完成了。

具体可以参考下面的这幅图：

sphinx-ac

简单的状态如下

#define LOC_PUSH(_new) { eStack[iStack++] = eState; eState = _new; }
#define LOC_POP() { eState = eStack[--iStack]; }
#define LOC_BACK() { p--; }
for (;; p++) {
    // if this line is over, load next line
    // handle S_TOP state
    if (eState == S_TOP) {  
        iToken = 0;
        LOC_PUSH(S_TYPE);
        LOC_PUSH(S_TOK);
        LOC_BACK();
        continue;
    }
    // handle S_SKIP2NL state
    if (eState == S_SKIP2NL) {
        LOC_POP ();
        p = pEnd;
        continue;
    }
    // handle S_TOK state
    if (eState == S_TOK) {
        if (!sphIsAlpha(*p)) {
            LOC_POP ();
            sToken[iToken] = '\0';
            iToken = 0;
            LOC_BACK();
            continue;
        }
        if (!iToken) {
            sToken[0] = '\0';
        }
        sToken[iToken++] = *p;
        continue;
    }
    // handle S_TYPE state
    if (eState == S_TYPE) {
        if (IsPlainSection(sToken)) {
            if (!AddSection(sToken, sToken))break;
            sToken[0] = '\0';
            LOC_POP();
            LOC_PUSH(S_SEC);
            LOC_PUSH(S_CHR);
            iCh = '{';
            LOC_BACK();
            continue;
        }
        if (IsNamedSection(sToken)) {
            m_sSectionType = sToken;
            sToken[0] = '\0';
            LOC_POP ();
            LOC_PUSH(S_SECNAME);
            LOC_BACK();
            continue;
        }
    }
    // handle S_CHR state
    if (eState == S_CHR) {
        LOC_POP ();
        continue;
    }
    // handle S_SEC state
    if (eState == S_SEC) {
        if (*p == '}') {
            LOC_POP ();
            continue;
        }
        if (sphIsAlpha(*p)) {
            LOC_PUSH(S_KEY);
            LOC_PUSH(S_TOK);
            LOC_BACK();
            iValue = 0;
            sValue[0] = '\0';
            continue;
        }
    }
    // handle S_KEY state
    if (eState == S_KEY) {
        LOC_POP ();
        LOC_PUSH(S_VALUE);
        LOC_PUSH(S_CHR);
        iCh = '=';
        LOC_BACK()
        continue;
    }
    // handle S_VALUE state
    if (eState == S_VALUE) {
        if (*p == '\n') {
            AddKey(sToken, sValue);
            iValue = 0;
            LOC_POP ();
            continue;
        }
        if (iValue 
    <p class="copyright">
        原文地址：sphinx 源码阅读之json, hash table配置分析器, 感谢原作者分享。
    </p>

Salin selepas log masuk