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

之前提到了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,如果是基本类型就直接释放,如果是数组或者对象就递归删除(类似二叉树)。

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

  1. 开头有负号吗?有就记下来,向前走。
  2. 第一个数字是0吗?是就前进,反正默认的结果都是0.
  3. 这是小数点以前的部分,一位一位地循环解析就好了,到第一个非数字的字符为止。
  4. 有点并且点后面有数字吗?有就把小数部分也解析了加上去。
  5. 有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位,那么运算的过程是:

  1. 首轮,第n位右移1位,经过按位或运算,第n和n-1位(n右边那一位)确保为1.
  2. 第二轮,类似地,n和n-1都右移2位,所以n-3到n都是1.
  3. 第三轮,同样,此时n-7到n位都可以确保为1.
  4. 第四第五轮后,从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->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的代码逻辑就是这个样子。阅读这样「接地气」的代码,好处在于能够快速学到很多这门语言的最佳实践,但是繁杂的工程细节也会让人厌烦。好在大一些的项目往往在抽象上做得更好,方便我们抽丝剥茧,寻得新知。