cJSON源码分析
2017-01-14 本文已影响4634人
书呆子的复仇
cJSON是C语言中的一个JSON编解码器，非常轻量级，C文件只有不到一千行，代码的可读性也很好，很适合作为C语言项目进行学习。项目主页：
https://sourceforge.net/projects/cjson/
对于json格式编码与解码，其实就是类似于一个解释器，主要原理还是运用递归。个人认为，如果能用一些支持面向对象的语言来做这个项目，代码实现起来应该会更加优雅。
先来看一下cJSON的数据结构：
/* The cJSON structure: */
typedef struct cJSON {
struct cJSON *next,*prev; /* next/prev allow you to walk array/object chains. Alternatively, use GetArraySize/GetArrayItem/GetObjectItem */
struct cJSON *child; /* An array or object item will have a child pointer pointing to a chain of the items in the array/object. */
int type; /* The type of the item, as above. */
char *valuestring; /* The item's string, if type==cJSON_String */
int valueint; /* The item's number, if type==cJSON_Number */
double valuedouble; /* The item's number, if type==cJSON_Number */
char *string; /* The item's name string, if this item is the child of, or is in the list of subitems of an object. */
} cJSON;
不管是数值类型、字符串类型或者对象类型等都使用该结构体，类型信息通过标识符 type来进行判断，cJSON总共定义了7种类型：
/* cJSON Types: */
#define cJSON_False 0
#define cJSON_True 1
#define cJSON_NULL 2
#define cJSON_Number 3
#define cJSON_String 4
#define cJSON_Array 5
#define cJSON_Object 6
另外，如果是对象或者数组，采用的是双向链表来实现，链表中的每一个节点表示数组中的一个元素或者对象中的一个字段。其中child表示头结点，next、prev分别表示下一个节点和前一个节点。valuestring、valueint、valuedouble分别表示字符串、整数、浮点数的字面量。string表示对象中某一字段的名称，比如有这样的一个json字符串：
{'age': 20}
'age'则用结构体中的string来表示。
cJSON的api使用起来非常简单：
char *out;cJSON *json;
json=cJSON_Parse(text);
if (!json) {
printf("Error before: [%s]\n",cJSON_GetErrorPtr());
} else {
out=cJSON_Print(json);
cJSON_Delete(json);
printf("%s\n",out);
free(out);
}
代码都是自解释的就不啰嗦，唯一需要注意的是使用完成后，必须释放内存，以免内存泄露。
JSON的解析
下面我们先来看一下json字符串的解析，json的字符串的解析主要是通过cJSON_Parse函数来完成，打开cJSON_Parse函数后，我们发现该函数使用了另外一个辅助函数：
/* Default options for cJSON_Parse */
cJSON *cJSON_Parse(const char *value) {
return cJSON_ParseWithOpts(value,0,0);
}
cJSON_ParseWithOpts提供了一些额外的参数选项：
/* Parse an object - create a new root, and populate. */
cJSON *cJSON_ParseWithOpts(const char *value, const char **return_parse_end, int require_null_terminated) {
const char *end = 0;
cJSON *c = cJSON_New_Item();
ep = 0;
if (!c) return 0; /* memory fail */
end = parse_value(c, skip(value));
if (!end) {
cJSON_Delete(c);
return 0;
} /* parse failure. ep is set. */
/* if we require null-terminated JSON without appended garbage, skip and then check for a null terminator */
if (require_null_terminated) {
end = skip(end);
if (*end) {
cJSON_Delete(c);
ep = end;
return 0;
}
}
if (return_parse_end) *return_parse_end = end;
return c;
}
第一步：先调用cJSON_New_Item创建一个节点，该函数实现非常简单，就是使用malloc分配一块内存，再将分配的内存使用0来进行初始化。
/* Internal constructor. */
static cJSON *cJSON_New_Item(void)
{
cJSON* node = (cJSON*)cJSON_malloc(sizeof(cJSON));
if (node) memset(node,0,sizeof(cJSON));
return node;
}
第二步：调用parse_value函数进行真正的解析，该函数是json解析的核心部分，后面我们会重点分析。而在解析前，先对json字符串调用了一次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;
}
最后一步：函数中参数中提供了require_null_terminated是为了确保json字符串必须以'\0'字符作为结尾。若参数提供了return_parse_end，将返回json字符串解析完成后剩余的部分。
下面来看json解析算法的核心部分：
static const char *parse_value(cJSON *item, const char *value) {
if (!value) return 0; /* Fail on null. */
//若字符串等于null，直接将type标记为cJSON_NULL
if (!strncmp(value, "null", 4)) {
item->type = cJSON_NULL;
return value + 4;
}
//若字符串等于false，直接将type标记为cJSON_False
if (!strncmp(value, "false", 5)) {
item->type = cJSON_False;
return value + 5;
}
//若字符串等于true，直接将type标记为cJSON_True
if (!strncmp(value, "true", 4)) {
item->type = cJSON_True;
item->valueint = 1;
return value + 4;
}
//若字符串以\"开头，说明是一个字符串
if (*value == '\"') { return parse_string(item, value); }
//若字符串以0~9或者-开头，则是一个数值
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. */
}
上述 代码看上去应该清晰易懂，且都已加入注释。对于json为null、true或者false的情况，直接将type置为对应的类型即可。对于其他情况，需要分别再做处理，先来看json为字符串的情况：
static const char *parse_string(cJSON *item, const char *str) {
const char *ptr = str + 1;
char *ptr2;
char *out;
int len = 0;
unsigned uc, uc2;
if (*str != '\"') {
ep = str;
return 0;
} /* not a string! */
/* 这一步主要是为了确定字符串的长度，以便下一步进行内存分配
* 问题在于字符串中可能存在一定的转义字符，由于json字符串本身
* 是一个字符串，碰到像双引号必须进行转义，另外像\t这样的转义
* 字符，需要再次转义，用\\t来表示。而在解析的时候，我们不需要
* 这些多余的转义字符。（说得有点绕，不知道能不能看明白）
*/
while (*ptr != '\"' && *ptr && ++len)
if (*ptr++ == '\\') ptr++;
//分配内存，保存解析后的结果
out = (char *) cJSON_malloc(len + 1);
if (!out) return 0;
ptr = str + 1; //跳过第一个\"
ptr2 = out;
//当遇到\"时，说明到达字符串的末尾
while (*ptr != '\"' && *ptr) {
//如果不是转义字符，直接原样复制
if (*ptr != '\\') *ptr2++ = *ptr++;
else { //碰到像\\b的再转义字符，改成\b
ptr++;
switch (*ptr) {
case 'b':
*ptr2++ = '\b';
break;
case 'f':
*ptr2++ = '\f';
break;
case 'n':
*ptr2++ = '\n';
break;
case 'r':
*ptr2++ = '\r';
break;
case 't':
*ptr2++ = '\t';
break;
case 'u': /*这里将 utf16 转为 utf8，算法比较复杂，不做分析 */
uc = parse_hex4(ptr + 1);
ptr += 4; /* get the unicode char. */
if ((uc >= 0xDC00 && uc <= 0xDFFF) || uc == 0) break; /* check for invalid. */
if (uc >= 0xD800 && uc <= 0xDBFF) /* UTF16 surrogate pairs. */
{
if (ptr[1] != '\\' || ptr[2] != 'u') break; /* missing second-half of surrogate. */
uc2 = parse_hex4(ptr + 3);
ptr += 6;
if (uc2 < 0xDC00 || uc2 > 0xDFFF) break; /* invalid second-half of surrogate. */
uc = 0x10000 + (((uc & 0x3FF) << 10) | (uc2 & 0x3FF));
}
len = 4;
if (uc < 0x80) len = 1; else if (uc < 0x800) len = 2; else if (uc < 0x10000) len = 3;
ptr2 += len;
switch (len) {
case 4:
*--ptr2 = ((uc | 0x80) & 0xBF);
uc >>= 6;
case 3:
*--ptr2 = ((uc | 0x80) & 0xBF);
uc >>= 6;
case 2:
*--ptr2 = ((uc | 0x80) & 0xBF);
uc >>= 6;
case 1:
*--ptr2 = (uc | firstByteMark[len]);
}
ptr2 += len;
break;
default:
*ptr2++ = *ptr;
break;
}
ptr++;
}
}
*ptr2 = 0;
if (*ptr == '\"') ptr++;
item->valuestring = out;
item->type = cJSON_String;
return ptr;
}
解析字符串的困难之处在于可能会碰到转义字符，需要将类似于\\t这样的再转义字符转化为\t，对于如何将utf16转为utf8的算法比较复杂，我就不做分析了。其他情况原样复制即可。
下面是解析数值类型的代码：
static const char *parse_number(cJSON *item, const char *num) {
double n = 0, sign = 1, scale = 0;
int subscale = 0, signsubscale = 1;
if (*num == '-') sign = -1, num++; /*如果是负数，将sign置位-1 */
if (*num == '0') num++; /* 如果是0，直接越过 */
if (*num >= '1' && *num <= '9') /* 碰到数字1~9，用循环计算整数部分的数值 */
do n = (n * 10.0) + (*num++ - '0'); while (*num >= '0' && *num <= '9');
if (*num == '.' && num[1] >= '0' && num[1] <= '9') { /* 遇到小数点，计算小数位的数值，用scale来标记小数有多少位 */
num++;
do n = (n * 10.0) + (*num++ - '0'), scale--; while (*num >= '0' && *num <= '9');
}
if (*num == 'e' || *num == 'E') /* 遇到指数，计算指数位的数值 */
{
num++;
if (*num == '+') num++; else if (*num == '-') signsubscale = -1, num++;
while (*num >= '0' && *num <= '9') subscale = (subscale * 10) + (*num++ - '0');
}
/* 最后根据前面的得到的数值，计算最终的结果 */
n = sign * n * pow(10.0, (scale + subscale * signsubscale)); /* number = +/- number.fraction * 10^+/- exponent */
item->valuedouble = n;
item->valueint = (int) n;
item->type = cJSON_Number;
return num;
}
这部分代码也不难，花点时间应该就能看懂。主要是考虑了小数和指数的情况，会带来一定的复杂性。 吐槽一下作者把if语句块中的代码都写在一行上，导致看起来很费劲。
接下来是如何解析数组：
static const char *parse_array(cJSON *item, const char *value) {
cJSON *child;
if (*value != '[') { //不是一个数组，直接返回
ep = value;
return 0;
}
item->type = cJSON_Array;
value = skip(value + 1); //跳过前面的空白字符
if (*value == ']') return value + 1; /* 空数组 */
//创建数组的头结点，表示数组的第一个元素
item->child = child = cJSON_New_Item();
if (!item->child) return 0;
//对数组中的第一个元素递归调用parse_value
value = skip(parse_value(child, skip(value)));
if (!value) return 0;
//如果数组第一个元素后面存在逗号，说明还有其他元素
//对剩下的元素同样递归调用parse_value，并将后面的元素
//放在child节点的尾部，形成一个链表
while (*value == ',') {
cJSON *new_item;
if (!(new_item = cJSON_New_Item())) return 0;
//移动指针
child->next = new_item;
new_item->prev = child;
child = new_item;
value = skip(parse_value(child, skip(value + 1)));
if (!value) return 0;
}
if (*value == ']') return value + 1; /* 达到数组的尾部 */
ep = value;
return 0;
}
解析数组时，其基本思想是对数组中每一个元素递归调用parse_value，再将这些元素连接形成一个链表。
如果能看懂数组的解析过程，对象的解析对你来说应该也不难，直接来看代码：
static const char *parse_object(cJSON *item, const char *value) {
cJSON *child;
if (*value != '{') {
ep = value;
return 0;
} //不是一个对象，直接返回
item->type = cJSON_Object;
value = skip(value + 1);
if (*value == '}') return value + 1; /* 空对象 */
//创建节点，用于保存对象中的第一个字段
item->child = child = cJSON_New_Item();
if (!item->child) return 0;
//调用parse_string，解析第一个字段的名称
value = skip(parse_string(child, skip(value)));
if (!value) return 0;
child->string = child->valuestring;
child->valuestring = 0;
//如果字段名称后面不是冒号，则不是一个合法的json字符串，直接返回
if (*value != ':') {
ep = value;
return 0;
}
//递归调用parse_value解析第一个字段的值
value = skip(parse_value(child, skip(value + 1)));
if (!value) return 0;
//若第一个字段后面存在逗号，则说明json对象存在其他的字段
//后面的步骤基本跟解析数组时相同，也就是将各个字段放在
//child节点后面，形成一个链表，唯一不同的是需要解析每个
//字段的名称
while (*value == ',') {
cJSON *new_item;
if (!(new_item = cJSON_New_Item())) return 0;
child->next = new_item;
new_item->prev = child;
child = new_item;
value = skip(parse_string(child, skip(value + 1)));
if (!value) return 0;
child->string = child->valuestring;
child->valuestring = 0;
if (*value != ':') {
ep = value;
return 0;
}
value = skip(parse_value(child, skip(value + 1)));
if (!value) return 0;
}
if (*value == '}') return value + 1; /* 达到对象的末尾 */
ep = value;
return 0;
}
最后，客户端代码在使用完成后，需要将分配的内存释放掉：
void cJSON_Delete(cJSON *c) {
cJSON *next;
while (c) { //循环删除链表中所有节点
next = c->next;
if (c->child) cJSON_Delete(c->child); //存在子节点，递归删除
if (c->valuestring) cJSON_free(c->valuestring);
if (c->string) cJSON_free(c->string);
cJSON_free(c); //删除结构体本身
c = next;
}
}
cJSON对于json字符串的解析基本就结束了。后面还有关于一个生成好的json对象如何打印，其实就是解析的逆向过程，我就不赘述了。老实说，代码的基本原理很简单，无非就是使用递归，如果让我写个demo，花一个小时就能写出来。但是这样的代码之所以值得我去阅读，不光是对于代码的风格、设计还有可读性上。更重要的是，作者能考虑到很多我不会去考虑的东西，比如说对于字符串的解析，如果是我自己写，可能不会考虑存在转义字符或者utf16的情况。在解析数值时，也不会考虑存在指数的情况。如果给定的字符串不是一个合法的json字符串，又该去如何处理？这也是一个代码新手做出来的东西与一款成熟产品的区别所在。
如果有时间，我想根据cJSON的思路，用java面向对象的方式来进行实现，并且在这基础上加入类型信息，而不是通过一个type标识符来判断类型。
