cjson 源碼分析

cjson 的源碼大約1000行左右澄者，用C語言實現(xiàn)了一個json的解析器笆呆。c語言沒有字典或key-value這樣的數(shù)據結構，所以處理json需要自己定義數(shù)據結構來處理粱挡，想想都是一個很激動的事情赠幕。

cjson的官網： http://www.json.org/
下載源碼： https://sourceforge.net/projects/cjson/

另外，在源碼里面可以看到對json字符串的解析過程（其實本質是一個自動機）询筏，還有一個問題就是內存的管理榕堰，由于c的特性需要自己用戶管理內存（即自定義 malloc 和 free）。這幾天看完cjson嫌套，這個的確是一個很好的教程逆屡，來幫助你更好的理解底層，即使你平常不用c寫代碼踱讨。

cjson源碼里面試圖解決的幾個問題

定義的數(shù)據結構是什么魏蔗？
如何進行內存管理？
2.1 如何創(chuàng)建結點
2.2 如何刪除結點
如果將一個json類型的字符串轉解析成對應的數(shù)據結構痹筛？
3.1 如何解析字符串
3.2 如何解析數(shù)組
3.3 如何解析數(shù)字
3.4 如何解析嵌套的json對象
對json結點的操作
4.1 添加結點
4.2 刪除結點
4.3 查找結點
4.4 修改結點
輸出和序列化

理解源碼沫勿，可以按照這個來對照一個挨约，看看作者的思路是如何干的，如果是你产雹，你會怎么做诫惭。

1. 定義的數(shù)據結構

    struct cJSON *next,*prev;   /同一級的元素使用雙向列表儲存/
    struct cJSON *child;        /* 如果是個 object 或 array 的話，第一個兒子的指針 */
    int type;                   /* value 的類型 */
    char *valuestring;          /* 如果這個 value 是 字符串 的話蔓挖，字符串值 */
    int valueint;               /* 如果是數(shù)字的話夕土，整數(shù)值 */
    double valuedouble;         /* 如果是數(shù)字的話，浮點數(shù)值 */
    char *string;               /* 如果是對象的 key-value 元素的話瘟判， key 值 */

type字段的類型怨绣，表示的當前json結點的數(shù)據類型：

#define cJSON_False 0      
#define cJSON_True 1
#define cJSON_NULL 2
#define cJSON_Number 3      #數(shù)字，注意這個數(shù)字表示的并不是int類型的數(shù)組拷获，而是字符串類型的數(shù)字
#define cJSON_String 4      #字符串
#define cJSON_Array 5       #數(shù)組
#define cJSON_Object 6      #嵌套json的類型

如果是對象或者數(shù)組篮撑，采用的是雙向鏈表來實現(xiàn)，鏈表中的每一個節(jié)點表示數(shù)組中的一個元素或者對象中的一個字段匆瓜。其中child表示頭結點赢笨，next、prev分別表示下一個節(jié)點和前一個節(jié)點驮吱。valuestring茧妒、valueint、valuedouble分別表示字符串左冬、整數(shù)桐筏、浮點數(shù)的字面量。

一個如下的json拇砰，如果用這個數(shù)據結構去表示的話梅忌，結構如下：

image.png

如果是一個json的嵌套，那么結構如下所示：

image.png

2. 內存管理

內存管理指的是創(chuàng)建一個JSON結點和刪除一個JSON結點除破，創(chuàng)建結點就是使用malloc內存分配铸鹰，刪除結點就判斷一下JSON的type，如果是基本類型就直接釋放皂岔，如果是數(shù)組或者對象就遞歸刪除（類似二叉樹）。

//創(chuàng)建結點
static cJSON *cJSON_New_Item(void) {
    cJSON* node = (cJSON*)cJSON_malloc(sizeof(cJSON));
    if (node) memset(node,0,sizeof(cJSON));
    return node;
}

//刪除結點展姐，注意看遞歸刪除的部分
void cJSON_Delete(cJSON *c) {
    cJSON *next;
    while (c) {
        next=c->next;
        if (!(c->type&cJSON_IsReference) && c->child) cJSON_Delete(c->child);
        if (!(c->type&cJSON_IsReference) && c->valuestring) cJSON_free(c->valuestring);
        if (c->string) cJSON_free(c->string);
        cJSON_free(c);
        c=next;
    }
}

3. json解析

json解析的功能實現(xiàn)的是給出一個字符串躁垛，然后把它解析成一個cjson的數(shù)據結構的類型。

解析的核心代碼：

//根據字符串來判斷當前json結點的類型
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);
    }
    //數(shù)字類型
    if (*value=='-' || (*value>='0' && *value<='9')) {
        return parse_number(item,value);
    }
    //數(shù)組類型
    if (*value=='[') {
        return parse_array(item,value);
    }
    //object類型
    if (*value=='{') {
        return parse_object(item,value);
    }
    ep=value;
    return 0;/* failure. */
}

對于不同的字符串圾笨，調用不同的解析函數(shù)教馆。貼一個比較復雜的解析函數(shù)，就是解析object擂达，分析如下：

static const char *parse_object(cJSON *item,const char *value)
{
    printf("********* parse_object \n");
    cJSON *child;
    if (*value!='{')    {ep=value;return 0;}    /* not an object! */
    item->type=cJSON_Object;
    value=skip(value+1);
    if (*value=='}') return value+1;    /* empty array. */

    //給item 創(chuàng)建一個子節(jié)點child
    item->child=child=cJSON_New_Item();
    if (!item->child) return 0;

    //子節(jié)點　解析字符串,執(zhí)行之后土铺，child->type=cjson_string;child->valuestring="name" ,parse_string的返回值=":\"zhao\",\"age\":18" 是剩下的字符串
    value=skip(parse_string(child,skip(value)));
    if (!value) return 0;
    // child->string 在這里想表達的是json里面的key
    child->string=child->valuestring;
    child->valuestring=0;

    if (*value!=':') {ep=value;return 0;}   /* fail! */
    // 繼續(xù)解析字符串里面的value的部分
    value=skip(parse_value(child,skip(value+1)));   /* skip any spacing, get the value. */
    
    if (!value) return 0;
    while (*value==',')
    {
        cJSON *new_item;
        if (!(new_item=cJSON_New_Item()))   return 0; /* memory fail */
        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;}   /* fail! */
        value=skip(parse_value(child,skip(value+1)));   /* skip any spacing, get the value. */
        if (!value) return 0;
    }
    if (*value=='}') return value+1;    /* end of array */
    ep=value;return 0;  /* malformed. */
}

4. 對json結點的操作

對結點的操作，我覺得可以抽象的理解為一棵樹（多叉樹），這樣對結點的操作基本上和樹對結點的操作是相似的悲敷。

4.1 添加結點
4.2 刪除結點
4.3 查找結點
4.4 修改結點

5. 輸出和序列化

cjson 的做法不是邊分析 json 邊輸出究恤，而是預先將要輸?shù)膬热萑堪醋址嬖趦却嬷校?最后輸出整個字符串。所以后德，看代碼的時候部宿，可以順著這個思路去看。

PS

最近用寫論文空余的時間瓢湃，連著看了三個經典的開源項目理张，按代碼量從小到大，分別是webbench绵患，tinyhttp雾叭，cjson。感覺受益匪淺落蝙，從這些前輩的代碼里面可以快速的學到這門語言的最佳實踐织狐，解決問題的思路，coding的風格掘殴。

再有一點赚瘦，體會很深的一點是，這幾個開源的項目里面奏寨，大量的代碼都是為了考慮解決異常的情況起意，比如輸入異常，故意輸入錯誤如何處理病瞳；創(chuàng)建進程失敗揽咕，如何處理；創(chuàng)建管道出錯怎么辦套菜；內存分配失敗怎么辦等等亲善。這些繁雜的工程細節(jié)會讓人厭煩，但不得不承認逗柴，這是一個優(yōu)秀代碼的必須要有的東西蛹头。

如何在國外的網站下載源碼不方便，可以移步我的github：
與源碼相比戏溺，我在github里面的版本插入了很多printf來輸出渣蜗，應該可以更容易理解一點吧
https://github.com/zhaozhengcoder/rebuild-the-wheel/tree/master/cJSON/src

參考文獻：

http://blog.csdn.net/yzhang6_10/article/details/51615089
http://www.reibang.com/p/838f69db2f71
http://github.tiankonguse.com/blog/2014/12/18/cjson-source.html

others

webbench的源碼：http://www.reibang.com/p/e65c7efc96aa
tinyhttp的源碼：http://www.reibang.com/p/18cfd6019296