ecnelises

好了好了，这篇文章拖了真久啊，活活三个月。不过之前承诺要经常更新博客的，所以先把这个烂尾的坑给填了。

之前提到了cJSON这个C语言写成的JSON解析库的接口，也就是头文件里的内容。这一次我们来分析一下实现。上车吧。

还是按照源代码的逻辑走。我们发现cJSON最开始有一个全局的字符指针ep，以及一个用以返回ep的函数。可以看出，这个ep是用来存储错误信息的。这种实现是C语言的常用手法，即把一些状态用static的方式隐藏在单个文件中，并实现一些函数当作接口。

static const char *ep;
const char *cJSON_GetErrorPtr(void) {return ep;}

下面是一个大小写无关的字符串比较函数。看后面的源码可以发现这个函数用在了JSON对象名的查找当中。实现没有什么特别的难点，所以就不提了。顺便说一句，在C++里要实现这个大小写无关比较，可以用STL里的一个方法叫做lexicographical_compare，搭配lambda表达式可以轻松达到目的。

作者把负责动态内存分配和释放的函数直接「填」成了标准库的malloc和free，像C++的allocator一样。如果担心内存碎片的问题，可以自己再当个二道贩子，实现一个内存池，不过那有点背离本文的主题了。作者自己实现了一个版本的strdup，里面也是用这个用户可以更换的cJSON_malloc进行内存分配的。

新建JSON和释放JSON的工作不难，前者就是内存分配的问题，后者就判断一下JSON的type，如果是基本类型就直接释放，如果是数组或者对象就递归删除（类似二叉树）。

目前好戏来了。第一个函数是解析数的。写过词法分析器的就懂，这个用自动机很容易描述，不过这里实在是没有什么好的能在电脑上绘制自动机图的工具，所以用列表表示这个过程，看看应该能体会。

开头有负号吗？有就记下来，向前走。
第一个数字是0吗？是就前进，反正默认的结果都是0.
这是小数点以前的部分，一位一位地循环解析就好了，到第一个非数字的字符为止。
有点并且点后面有数字吗？有就把小数部分也解析了加上去。
有E或者e吗？有就算10的幂次方。

简单吧？我们接着往下走。看到一个…奇怪的函数。

static int pow2gt (int x)
{
    --x;
    x|=x>>1;
    x|=x>>2;
    x|=x>>4;
    x|=x>>8;
    x|=x>>16;
    return x+1;
}

看见这个函数心里大概会想——什么鬼？名字看不懂，内容也看不懂。唔，不过看在它参数和返回值都是简单的int类型，不妨写个小程序测试一下结果。（限于篇幅省略结果）跑完之后我们猜测，这个函数的目的大概是返回一个不小于x的2的整数次幂。（对2的整数次幂还不敏感吗？）那我们来根据代码验证一下。

先略过这个减1的过程，看看位运算。我们假设整数的二进制形式从右向左，最后一个值为1的位是第n位，那么运算的过程是：

首轮，第n位右移1位，经过按位或运算，第n和n-1位（n右边那一位）确保为1.
第二轮，类似地，n和n-1都右移2位，所以n-3到n都是1.
第三轮，同样，此时n-7到n位都可以确保为1.
第四第五轮后，从1到n位都是1了。右移到16截止是因为这里的整数只有32位。

最后往这n位连续的1上再加个1，就是1后n个0，即2^n了。起来这个过程有点故弄玄虚的意思，因为我们也可以用循环的方式来解决。不过这里作者巧妙利用了整数位数的限制，用五次位运算达成了对任意整数都有效的效果。为什么要减1呢？因为不减1再加回去的话，对一个已经是2^n的数进行运算会得到2^(n+1)，不符合我们的预期。实际上，这样的位运算技巧在《高效算法的奥秘》和《深入理解计算机系统》中都有相关的阐述。

这个函数有什么用呢？搜索一下就会发现。它只用在了一个地方，就是下面这个ensure函数。继续追踪可以发现，这个函数包括下面的update以及printbuffer这个结构体，都是用来存储缓冲区的。在缓冲区里面空间成2倍地扩大。不过我们的重点在字符串解析和内部的数据结构。

到这里，我们回过头来整理一下思路。JSON的类型有6种，而操作又都有解析和输出两种。

null和bool，由于bool只有两种固定的值，所以对于这两者，输出和解析都是简单的strcmp、strcpy就可以。
string，解析本身难度不是太大，去掉两端引号中间的就是字符串内容。但是有两个（或者说就是一个）问题，一是要注意反斜杠’\’开头的转义字符，二是字符串涉及到utf16到utf8的转换。输出的话不是什么太大问题。
number的解析前面已经说过了，浮点数输出要考虑一下精度，IEEE754标准和utf8都是坑。
array和object都是递归解析。如果要按格式输出，缩进是一个问题。

唔，好尴尬，写到这里突然不知道怎么继续了。在这里贴一下主要的解析函数parse_value的代码。

/* Parser core - when encountering text, process appropriately. */
static const char *parse_value(cJSON *item,const char *value)
{
   if (!value)         return 0;   /* Fail on null. */
   if (!strncmp(value,"null",4))   { item->type=cJSON_NULL;  return value+4; }
   if (!strncmp(value,"false",5))  { item->type=cJSON_False; return value+5; }
   if (!strncmp(value,"true",4))   { item->type=cJSON_True; item-&gt;valueint=1;    return value+4; }
   if (*value=='\"')               { return parse_string(item,value); }
   if (*value=='-' || (*value>='0' && *value<='9')){ return parse_number(item,value); }
   if (*value=='[')                { return parse_array(item,value); }
   if (*value=='{')                { return parse_object(item,value); }
   ep=value;return 0;  /* failure. */
}

跟我前面的分类一样，很清楚了。至于空格，这个函数在每次被调用之前都会先调用一次skip函数，用来跳过空白的：

/* Utility to jump whitespace and cr/lf */
static const char *skip(const char *in)
{
    while (in && *in && (unsigned char)*in<=32)
        in++;
    return in;
}

查看ASCII码表就可以知道32之前的基本都是不可见的控制字符或者空白，这里的条件判断真是简单粗暴。

parse_array的过程已经说得比较清楚了，就是不断地跳过空格、读取逗号、再跳过空格、读取一个新的对象的循环……直到遇到反方括号。前面那个指针ep的用途也明白了，就是指向读取失败的地方。parse_object类似，只是每次循环还要插入一个读名字的过程。

输出部分没有什么特别值得提的地方（其实是懒），要注意的就是输出array和object的时候需要控制一下缩进。总的来说，cJSON的代码逻辑就是这个样子。阅读这样「接地气」的代码，好处在于能够快速学到很多这门语言的最佳实践，但是繁杂的工程细节也会让人厌烦。好在大一些的项目往往在抽象上做得更好，方便我们抽丝剥茧，寻得新知。

cJSON源码分析－实现