1. 背景

keywordCode()函数的作用是解析sqlite内置关键字，例如CREATE, VALUES, WITH, FOR等等。该函数是由工具自动生成的，源码注释中特别说明该工具是mkkeywordhash.c文件：

从sqlite3官网中下载src code（不是 amalgamation版本）。当前下载的是sqlite-src-3280000版本。

解压缩后进入到sqlite-src-3280000\tool文件夹下，找到mkkeywordhash.c文件。该文件是一个独立的c文件，可以直接在VS2017中编译。创建VS2017工程的方法：文件->新建项目->空项目，然后将mkkeywordhash.c添加到工程中的“源文件”即可。

mkkeywordhash.c文件中有main函数，可以直接编译运行，我们自然也能单步调试咯，稍后我会将main函数中的源码依次进行讲解，enjoy~~

2. mkkeywordhash.c源码分析

这个文件的核心算法是“字符串压缩”，即将多个字符串连接到一起，占用的空间越小越好。大家可能会有一个疑问，这有什么难的，把多个字符串“串型”连接到一起不就行啦。这样做当然可以，并且十分直觉，但是有个最大的问题就是浪费空间。

以下图为例，有6个字符串，分别为“abc”、“bcd”、“cde”、“def”、“efg”、“fgh”。Version1就是最直觉的方法，将这6个字符串“串型”连接到一起，构成了一个长度为18个字节的字符串“abcbcdcdedefefgfgh”。

我们仔细观察一下会发现，“abc”的后两个字符与“bcd”的前两个字符相同，可以将相同的部分（“bc”）合并到一起构成“abcd”，然后再与剩下4个字符串“串型”连接到一起，就得到了Version1.1.

在Version1.1中，“abcd”的后两个字符与“cde”的前两个字符相同，可以将相同的部分（“cd”）合并到一起构成“abcde”，然后再与剩下3个字符串“串型”连接到一起，就得到了Version1.2.

在Version1.2中，“abcde”的后两个字符与“def”的前两个字符相同，可以将相同的部分（“de”）合并到一起构成“abcdef”，然后再与剩下2个字符串“串型”连接到一起，就得到了Version1.3.

在Version1.3中，“abcdef”的后两个字符与“efg”的前两个字符相同，可以将相同的部分（“ef”）合并到一起构成“abcdefg”，然后再与剩下的1个字符串“串型”连接到一起，就得到了Version1.4.

在Version1.4中，“abcdefg”的后两个字符与“fgh”的前两个字符相同，可以将相同的部分（“fg”）合并到一起构成“abcdefgh”，这就是“字符串压缩”后的最终版本——Version2，压缩后的字符串只有8个字节，而Version1中得到的字符串有18个字节，节省了10个字节的存储空间。

上面的例子是我通过阅读mkkeywordhash.c源码后，根据实现思路所举的一个例子，目的是提前给大家打下“预防针”，不然看后面的讲解过程估计会晕掉^^。源码的实现大致就是基于这个思路，接下来我们开始逐行研究源码。如果大家先略读一遍整个代码，会发现整个实现流程就是由几个for循环代码块构成，我们研究的思路就是按照for循环代码块来逐个分析。

2.1 对关键字数组做“压缩”，将无需解析的关键字剔除

aKeywordTable[]包含了sqlite中所支持的所有关键字，目前一共有140个。关键字的总数保存到全局变量nKeyword。每个关键字都是Keyword类型，其中一个属性是mask。如果mask的值是0，表示当前关键字被“抛弃”，即不再需要解析该关键字，则该关键字将被后面的关键字覆盖。例如，aKeywordTable[10].mask=0, aKeywordTable[11].mask != 0，则aKeywordTable[10]将被aKeywordTable[11]覆盖。这一步骤相当于在做“数组压缩”，以保证aKeywordTable[]中只保存真正要被解析的关键字。

for循环中的局部变量i用于记录“数组压缩”前的关键字总数，每次for循环都会让i自加1。j用于记录“数组压缩”后的关键字总数，只有当mask不为0的时候，说明当前的关键字要被解析，所以j自加1；当mask为0的时候，说明当前的关键字被剔除，关键字数量保持不变，故j保持不变。

for循环结束后，j中保存的是“数组压缩”后一共需要解析的关键字的总数。将j赋值给全局变量nKeyword，之后的数据处理中一旦要用到关键字总数就会调用nKeyword.

2.2 更新关键字数组中的参数——关键字字符串长度、哈希值、关键字ID

Line380 :: 遍历整个数组的时候，使用局部变量指针p指向当前关键字，作用是让整个代码看起来更加赶紧整洁。

Line381 :: zName是关键字的名字，下图是aKeywordTable[]局部截图，第一列是关键字的名字，即zName指向的字符串。len保存关键字名字的字符串长度。

Line383 :: 我看到这行代码后产生的第一个疑问是zName和zOrigName有什么区别？如果只看这一部分代码确实看不出两者的区别——两者的值是完全一样的。但是在后面的处理中，zName会发生改变，而zOrigName将保持不变。以第2部分提到的字符串压缩算法为例，Version1.1中由于“bcd”中的前两项与“abc”的后两项相同，“bcd”中的前两项被“压缩没了”，最终变成了“d”，则zName变成了"d"，但是zOrigName仍是“bcd”。zOrigName是关键字真实的名字，zName是关键字被“压缩”后的名字。

Line384 :: 记录所有关键字名字的总长，单位是字节。

Line385 :: 计算当前关键字的hash值，算法是(关键字的第一个字符*4)^(关键字的最后一个字符*3)^(关键字名字的长度)。

Line386 :: 每一个关键字都有唯一的ID，从1开始依次向上增加。

2.3 根据关键字名字的长度进行升序排列

Line391 :: qsort()函数源自于C 标准库 - <stdlib.h>。关键的地方是比较函数keywordCompare1()。qsort()函数中比较函数的用法是:

• 如果 keywordCompare1返回值小于 0（< 0），那么a所指向元素会被排在b所指向元素的前面。
• 如果 keywordCompare1返回值等于 0（= 0），那么a所指向元素与 b所指向元素的顺序不确定。
• 如果 keywordCompare1返回值大于 0（> 0），那么a所指向元素会被排在b所指向元素的后面。

Line318 :: 根据上面三点原则，按照关键字名字的长度进行升序排列。

Line319~322 :: 当n为0时，说明关键字a和b的名字长度一样。然后需要比较两者是否完全一样，如果完全一样说明关键字数组中有重复元素，这是被禁止的，所以一旦检查两个关键字完全一样，就会在Line322抛出异常。

2.4 关键字数组压缩的第一步——检查某个关键字名字是否是另一个关键字名字的一部分

举例说明，有两个字符串“todolist”和“do”，后者是前者的一部分，在做字符串压缩的时候，压缩后的字符串是“todolist”，“do”将被“压缩没了”。这段代码的作用就是为了寻找某个关键字是否是另一个关键字名字的一部分。

Line394 :: 这是最外层for循环。在2.3部分已经将关键字的名字长度按照升序排列，nKeyword-2是关键字数组的倒数第二个元素，每次for循环i都自减1，直到指向关键字数组的第一个元素。

Line396 :: 这是中层for循环。nKeyword-1是关键字数组的倒数第一个元素（最后一个元素）。j>i说明中层for循环要以最外层for循环为基准，假设i=100，j的取值顺序是139、138...101，从后向前依次取出关键字与第100个关键字进行比较。先忽略p->substrId==0这个判断条件，稍后会做解释。

Line400~404（先跳过Line398和399） :: 这是内层for循环。目的是为了检查i所对应的关键字是否是j所对应关键字名字的一部分。还是使用Line396的例子，假设i=100，j的取值顺序是139、138...101。进一步假设i对应的关键字是INDEX，j=120且对应的关键字是REINDEX，之前(139~121)均检查失败。j取得的关键字长度(pOther->len)一定比i取得的关键字长度(p->len)长（这就是2.3步中升序排序的作用），两者的差值是k的上限，本例上限是2。下图中的k=0，k=1，k=2分别表示了内层for循环的三次对比，只有最后一次对比成功，进入Line402~404的if判断内部。i所对应的关键字是j所对应关键字名字的一部分，将j所对应关键字的ID记录到i所对应关键字的substrId中（本例该值是120），将i所对应关键字名字在j所对应关键字名字的偏移记录到substrOffset中（本例中该值是2）。

Line396 :: 我们再回过头来看一下p->substrId==0条件的作用，当p->substrId!=0说明当前的关键字已经找到它的“上家”了（我把“上家”定义为包含有其它关键字的关键字），无需再找，所以可以直接退出中层for循环，继续进行外层for循环，对下一个关键字进行处理。

Line398 :: 对于这行代码我觉得只有举例说明才能让大家明白：假设有三个关键字，“abc”、“bc”、“d”，其id分别为1，2，3。根据算法：

1. “bc“先与”abc“进行比较，发现”bc“在”abc“内，因此，”bc”->substrId=1。
2. ”d“先后分别与”abc“，”bc“进行比较。当与”abc“对比的时候，会进入内层for循环逐个字符遍历，但是对比失败。当与“bc”对比的时候，发现“bc”有“上家”（bc”->substrId=1），不执行内层for循环。逻辑是这样的，由于发现”bc“有”上家“，且这个”上家“一定在”bc“的前面，”d“在与”bc“比较的时候，一定先遇到”bc“的上家，但是没有比对成功，说明”d“一定不在”上家“的关键字内，而”bc“是其”上家“关键字的一部分，则”d“一定不在”bc“内。这段逻辑是不是很精彩哦。
3. 通过判断当前待比较关键字是否有”上家“，可以节约一次内层for循环，提高了代码执行速率。大家说这行代码精彩不精彩！！

Line399 :: 由于关键字已经按照升序排列了，小于号肯定不会取到，只会用到等号。原因是当两个关键字长度相等的时候，肯定不会存在包含关系，除非两者相同，而这又是被禁止的。之所以会使用小于等于而不是等于，是因为小于等于号的判断范围更广，虽然正常情况下小于号是不可能用到的，但是会有异常情况，比如代码跑飞了，此时小于号就能排上用场了。

2.5 计算关键字名字的最长后缀

对每个关键字（看作是master），都要遍历其他所有的关键字（看作是slave），然后逐个比较检查slave关键字是否是master关键字的后缀部分（必须是后缀，而不能是其中的一部分），如果是，则slave字符串的长度作为master关键字的longestSuffix值。如果多个slave关键字都是master关键字的后缀，取得字符串长度最长的那个slave关键字的长度，并保存到master关键字的longestSuffix。比如，有四个字符串“abcde”、“de”、“cde”、“bcde”，且“de”、“cde”、“bcde”都是
“abcde”的后缀，但是“bcde”是“abcde”的最长后缀，所以，“abcde”的longestSuffix值是4.

Line413&418 :: 当关键字有“上家”，直接continue。原因是当master属于另外某个关键字的一部分的时候，我们不能将它作为master，即它的longestSuffix值为0.

Line419 :: k=p->longestSuffix+1，如果多个slave都是master的后缀，从slave中最长的作为longestSuffix.

2.6 按照longestSuffix的长度为进行降序排列

最终按照longestSuffix降序排列，即longestSuffix长的关键字排到前面，短的排到后面。

2.7 将所有的关键字紧密排列到一起，并计算每个关键字在整个字符串中的偏移（字符串压缩算法）

Line433&439 :: 在2.6节中对所有关键字按照longestSuffix降序排列，longestSuffix长的关键字排到前面，短的排到后面。因此，指针p指向的关键字，其longestSuffix始终不小于pOther所指向关键字对应的longestSuffix。

Line437&442 :: 每取得一个master关键字，都要从master关键字的第1个（从0开始）字符开始遍历直到最后一个字符，以开始的字符为起始截取剩余部分字符串（k是截取部分字符串的长度）。将此字符串与pOther指向的关键字（slave）进行对比，检查slave关键字是否是master关键字的后缀。如果是：

• Line443 :: TBD
• Line ::
• Line::

2.8 根据关键字的offset升序排列

2.9 在哈希冲突情况下得到最小哈希表

这部分代码是为了解决哈希冲突。代码的逻辑是，以关键字数量的平方作为上限，以关键字数量的一半作为下限，在此区间内取值作为hash取模的对象，目标是使取模后得到的值最不容易重复。如何以数学的方式表达“最不容易重复”？可以设置一个“惩罚因子”——此处是Line473中的数字2（也可以是3,4,5，实际上任意除1之外的正整数都可以），每次取模后的结果都要乘以这个“惩罚因子”，重复的次数与2的幂次方成正比——增长速度是非常快的。Line476对所有模值求和，意味着重复项越多，最终求得的和越大。举两个例子：

1. 有5个关键字，Line472计算得到的哈希值分别为0,1,2,3,4，最终aKWHash[0]~aKWHash[4]全部都为1（aKWHash数组默认值都是0），求和的值为5.
2. 有5个关键字，Line472计算得到的哈希值全部都是0，最终aKWHash[0]=(((1*2+1)*2+1)*2+1)*2+1=31

从上面两个例子可以知道，“惩罚因子”会对整个数组的求和产生决定性的影响，重复次数越多，最终的和就越大。

不过，随着i的增加（Line469::遍历整个区间），最终计算得到的哈希值会变得一样“稀疏”，也就意味着求和的结果都是一样的。

Line477~479 :: 目标是得到最小的和，并记录对应的i，保存到bestSize中。

2.10 计算得到哈希值

Line486 :: 2.9节计算得到哈希表的最小长度（bestSize），并根据该最小长度作为取模对象，计算得到哈希值（h）。

Line487 :: 如果没有哈希冲突，意味着每个哈希值都对应唯一的aKWHash[h]，由于aKWHash[]数组默认值是0（Line484），因此每个关键字的iNext值都是0。如果存在哈希冲突，则aKWHash[h]中是非零值。该非零值减1即表示与当前关键字产生哈希冲突的关键字的索引值。

Line488 :: 将当前关键字在aKeywordtable数组中的位置（对应for循环中的i值）加1的结果保存到该哈希值对应的aKWHash[]数组中，之所以加1，是因为0表示不存在哈希冲突，非零值表示哈希冲突，与当前关键字产生哈希冲突的关键字可以通过iNext减1得到其索引值.例如iNext=1表示当前关键字与#0号（iNext-1=1-1=0）关键字哈希冲突。