json

发布日期: 2021-08-23

json learn

之前收藏过miloyip的json教程，现在想学习一下。

为什么现在要学习这个呢？

首先这几天我对未来的方向越发的清晰了，未来我想从事有关计算机图形学底层相关职业，所以我想重新学习计算机图形学，将之前的游戏引擎重新实现一遍。

想要重写之前的游戏引擎就必须将模型加载自己实现一次，虽然github上有一个tinyobj_loader的项目，但是我现在看不懂，还需要学习更加多的底层知识才可以。

要想增强自己的底层开发能力，必须跟着几个项目进行学习。目前可以学习的资源有：tinyobj_loader，database, 郑刚的操作系统，c4编译器等。

目前我正在准备考研，所以并没有太多时间，只能先学习一些小的项目，不然的话做项目上瘾就没有时间准备考研了。

思来想去，目前来看最合适的项目就是这个json教程了。学完这个教程可以实现一个递归下降的解析器，这又为学习C4做了准备，同时也为CDB做了准备。

于是决定学习json

从零开始的JSON库教程

GitHub

json简介

json有六种数据类型，如下：

null 表示为 null
布尔值表示为 true false
数字表示为 12345
string 表示为 “12345”
数组表示为 [1,”23”,45,{“a”:1,”b”:2},[1,2]]
对象表示为键值对,key必须为字符串，value任意，如下：

{
    "姓名": "崔文耀",
    "a": 1,
    "b": [2,3],
    "c": null,
    "d": 
    {
        "e": true,
        "f": false
    }
}

一个基本的json库需要拥有下面三种功能：

将json文件解析为数据结构 parse
将数据结构保存为json文件 stringify
对外提供接口访问解析出来的数据结构 access

解析器

由于json数据包含上述的六种形式，所以对其分别进行判断以及解析即可。

当前要解析的json字符串内容已经保存在一个数据结构”context”中，目标是将其解析到内存中并保存为”value”，这两个数据结构如下：

typedef struct _JSON_VALUE_ json_value;
typedef struct _JSON_OBJECT_MEMBER_ json_object_member;

//json是一个树形结构，每一个结点使用json_value来表示
typedef struct _JSON_VALUE_
{
    union
    {
        /* string */
        struct
        {
            char *string;
            size_t length;
        } s;
        /* array */
        struct
        {
            json_value *e;
            size_t size; //代表元素的个数
        } a;
        /* opbject */
        struct
        {
            json_object_member *m;
            size_t size;
        } o;
        /* number */
        double number;
    } u;
    json_type type;
} json_value;

typedef struct _JSON_OBJECT_MEMBER_
{
    char *k;
    json_value v;
    size_t k_len;
} json_object_member;

//json解析上下文
typedef struct
{
    const char *json;
    char *stack;
    size_t size;
    size_t top;
} json_context;

其中context中的stack用于解析时的缓冲。

json解析的层次架构为：

json_parse():解析入口和出口
json_parse_value():解析出要解析的字符串的类型，并交到下一层。
json_parse_literal,json_parse_number,json_parse_string,json_parse_array,json_parse_object():分别接受来自上层json_parse_value的信息，解析不同种类的额数据。并返回相应的解析结果。

由于每一种数据的首字母都不同，所以json_parse_value可以通过判断首字母来确定是哪一种数据。

以上就是解析器的主要构成。

生成器

生成器相比于解析器来讲就更加简单了。由于生成器时已经确定的，所以没那么多的错误情况。生成器的任务就是将一个value的信息表示成json字符串的形式。层次架构如下：

json_stringify():负责读入一个value，处理生成一个字符串。
json_stringify_value():从上层读入一个value，根据不同的情况写入不同的字符到context的堆栈中，没什么好说的。

访问

访问即提供一个接口令其他程序可以使用并操控数据。

测试

这次学习这一个项目，我学到的最重要的知识就是测试开发TDD，test-drive-development。

测试可以确保每一次改动代码不会影响程序正确性，其实正常写代码的话都是使用了TDD的思想，只不过没有将其结构化而已，现在我来学习一下TDD的结构。

我们期望每一个测试都有一个程序得到的值和自己确定的正确的值之间的比较来反映测试是否通过，不通过的话就告知错误测试用例的位置。
我们希望可以被告知错误的结果和正确的结果以DEBUG。

可以将每一个测试都写为一个函数，使用全局变量保存测试的信息。这样固然可行，但是json库教程上的测试则不是这样做的，为了学习还是使用教程上的吧。

有一个测试的基石用来告知一个测试是否通过。这里使用宏是因为宏展开后是一行代码，这样**LINE**就可以指示出哪行测试没有通过了，这就要求测试用例也需要写成宏的形式。

#define EXPECT_EQ_BASE(equality, expect, actual, format)                                                           \
    do                                                                                                             \
    {                                                                                                              \
        test_count++;                                                                                              \
        if (equality)                                                                                              \
            test_pass++;                                                                                           \
        else                                                                                                       \
        {                                                                                                          \
            fprintf(stderr, "%s:%d: expect: " format " actual: " format "\n", __FILE__, __LINE__, expect, actual); \
            main_ret = 1;                                                                                          \
        }                                                                                                          \
    } while (0)

学到的知识

TDD驱动开发
宏的编写技巧 do{code}while(0)
层次驱动开发
文件的读取，如下：

FILE *fp;
char *json = (char *)malloc(255 * sizeof(char));
fp = fopen("test.json", "rb");
//fgets( json,255, fp ); 读取255-1=254个字符到json中，但是遇到换行回车空格等空白字符就停止。
//printf("%s",json);
size_t size = 0;
while ((json[size++] = getc(fp)) != EOF)    //读一个字符，包括换行回车空格等空白字符，直到结束
    ;
json[size] = '\0';
printf("%s\n", json);

代码

json.h

#ifndef JSON_H
#define JSON_H

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <errno.h>
#include <math.h>
#include <io.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

//json解析时的栈初始内存大小
#ifndef JSON_PARSE_STACK_INIT_SIZE
#define JSON_PARSE_STACK_INIT_SIZE 256
#endif

#define EXPECT(context, ch)             \
    do                                  \
    {                                   \
        assert(*context->json == (ch)); \
        context->json++;                \
    } while (0)

#define ISDIGIT(num) (num >= '0' && num <= '9')

#define DIGITBT1TO9(num) (num >= '1' && num <= '9')

#define ISSURROGATE(num) (num <= 0xd8ff && num >= 0xd800)

#define STRING_ERROR(error) \
    do                      \
    {                       \
        c->top = top;       \
        return error;       \
    } while (0);

#define json_set_null(v) json_free(v)

#define json_init(v)                  \
    do                                \
    {                                 \
        (v)->u.o.m = NULL;            \
        (v)->u.o.size = 0;            \
        (v)->u.a.e = NULL;            \
        (v)->u.a.size = 0;            \
        (v)->u.s.string = NULL;       \
        (v)->u.s.length = 0;          \
        (v)->type = JSON_UNKONE_TYPE; \
    } while (0)

#define json_init_object_member(m) \
    do                             \
    {                              \
        (m)->k = NULL;             \
        (m)->k_len = 0;            \
    } while (0)

#define json_init_context(c) \
    do                       \
    {                        \
        (c)->stack = NULL;   \
        (c)->json = NULL;    \
        (c)->size = 0;       \
        (c)->top = 0;        \
    } while (0)

#define PUTC(c, ch)                                         \
    do                                                      \
    {                                                       \
        *(char *)json_context_push(c, sizeof(char)) = (ch); \
    } while (0)

#define PUTS(c, s, len) memcpy((char *)json_context_push(c, len) - len, s, len);

//json数据类型
typedef enum
{
    JSON_NULL,
    JSON_TRUE,
    JSON_FALSE,
    JSON_NUMBER,
    JSON_STRING,
    JSON_ARRAY,
    JSON_OBJECT,
    JSON_UNKONE_TYPE
} json_type;

typedef struct _JSON_VALUE_ json_value;
typedef struct _JSON_OBJECT_MEMBER_ json_object_member;

//json是一个树形结构，每一个结点使用json_value来表示
typedef struct _JSON_VALUE_
{
    union
    {
        /* string */
        struct
        {
            char *string;
            size_t length;
        } s;
        /* array */
        struct
        {
            json_value *e;
            size_t size; //代表元素的个数
        } a;
        /* opbject */
        struct
        {
            json_object_member *m;
            size_t size;
        } o;
        /* number */
        double number;
    } u;
    json_type type;
} json_value;

typedef struct _JSON_OBJECT_MEMBER_
{
    char *k;
    json_value v;
    size_t k_len;
} json_object_member;

//parse 解析结果
typedef enum
{
    PARSE_OK,                           //解析成功
    PARSE_EXPECT_VALUE,                 //只有空白
    PARSE_INVALID_VALUE,                //不合法
    PARSE_ROOT_NOT_SINGULAR,            //在一个值之后仍然有其他字符
    PARSE_NUMBER_TOO_BIG,               //数太大
    PARSE_MISS_QUOTATION_MARK,          //双引号错误
    PARSE_INVALID_STRING_ESCAPE,        //不合法的转义字符
    PARSE_INVALID_UNICODE_HEX,          //不合法的Unicode16进制数
    PARSE_INVALID_UNICODE_SURROGATE,    //不合法的unicode高代理项
    PARSE_MISS_COMMA_OR_SQUARE_BRACKET, //数组缺失引号或者括号
    PARSE_MISS_COMMA_OR_CURLY_BRACKET,  //对象缺失逗号或者花括号
    PARSE_MISS_KEY,                     //对象缺失key
    PARSE_MISS_COLON,                   //对象缺失冒号
    PARSE_MISS_VALUE,                   //对象缺失值
    STRINGIFY_OK,                       //字符串化成功
    STRINGIFY_ERROR,                    //字符串化失败
    PARSE_RESULT_UNDIFINED
} parse_result;

//json解析上下文
typedef struct
{
    const char *json;
    char *stack;
    size_t size;
    size_t top;
} json_context;

//解析 传入一个字符串解析出一个json值（结点） 返回解析结果
parse_result json_parse(json_value *value, const char *json);

//获取 type 传入一个解析结果
json_type json_get_type(const json_value *value);

bool json_get_boolean(const json_value *value);
void json_set_boolean(json_value *value, bool boolean);
//获取 number 当type为JSON_NUMBER时有效
double json_get_number(const json_value *value);
void json_set_number(json_value *value, double number);
const char *json_get_string(const json_value *value);
size_t json_get_string_length(const json_value *value);
size_t json_get_array_size(const json_value *v);
json_value *json_get_array_element(const json_value *v, size_t index);
size_t json_get_object_size(const json_value *v);
json_object_member *json_get_object_element(const json_value *v, size_t index);
//EXPECT_EQ_STRING("a",json_get_object_element(&v,0)->k,json_get_object_element(&v,0)->k_len);
//处理空白字符 让context中的json指向第一个非空白符
static void json_parse_whitespace(json_context *context);

static parse_result json_parse_value(json_context *context, json_value *value);
//解析  /* value = null / false / true */
static parse_result json_parse_literal(json_context *context, json_value *value, const char *literal, json_type type);
//解析 number
static parse_result json_parse_number(json_context *context, json_value *value);
//解析 string
static parse_result json_parse_string(json_context *c, json_value *v);
//解析 array
static parse_result json_parse_array(json_context *c, json_value *v);
//解析 object
static parse_result json_parse_object(json_context *c, json_value *v);

//赋值字符串的内容到value
void json_set_string(json_value *v, const char *s, size_t len);
//释放value
void json_free(json_value *v);
//释放object_member
void json_free_object_member(json_object_member *o);

//压入数据，单位为字节 更新栈顶并返回
static void *json_context_push(json_context *c, size_t size);
//弹出数据
static void *json_context_pop(json_context *c, size_t size);

//解析四位16进制的数 p指向这四位数的起始，解析结果放入u中
static const char *json_parse_hex4(const char *p, size_t *u);
//将一个4位16进制的数，编码位utf-8
static const char *json_encode_utf8(json_context *c, size_t u);

parse_result json_stringify(const json_value *v, char **str, size_t *length);
static parse_result json_stringify_value(json_context *c, const json_value *v, size_t *length);

#endif

json.c

#include "json.h"

//解析 传入一个字符串解析出一个json值（结点） 返回解析结果
parse_result json_parse(json_value *value, const char *json)
{
    assert(value != NULL);
    json_init(value);
    json_context context;
    context.json = json;
    context.stack = NULL;
    context.size = 0;
    context.top = -1;
    parse_result res = PARSE_RESULT_UNDIFINED;
    //删去空白符
    json_parse_whitespace(&context);
    //解析值
    res = json_parse_value(&context, value);
    //解析成功一个之后是否还存在其他的
    if (res == PARSE_OK)
    {
        json_parse_whitespace(&context);
        if (context.json[0] != '\0')
            res = PARSE_ROOT_NOT_SINGULAR;
    }
    assert(context.top == -1);
    return res;
}

//获取 type 传入一个解析结果
json_type json_get_type(const json_value *value)
{
    return value->type;
}
bool json_get_boolean(const json_value *value)
{
    assert(value && (value->type == JSON_TRUE || value->type == JSON_FALSE));
    if (value->type == JSON_TRUE)
        return true;
    else if (value->type == false)
        return false;
}
void json_set_boolean(json_value *value, bool boolean)
{
    assert(value && (value->type == JSON_TRUE || value->type == JSON_FALSE));
    if (boolean == true)
        value->type = JSON_TRUE;
    else if (boolean == false)
        value->type = JSON_FALSE;
}
//获取 number 当type为JSON_NUMBER时有效
double json_get_number(const json_value *value)
{
    assert(value && value->type == JSON_NUMBER);
    return value->u.number;
}
void json_set_number(json_value *value, double number)
{
    assert(value && value->type == JSON_NUMBER);
    value->u.number = number;
}
const char *json_get_string(const json_value *value)
{
    assert(value && value->type == JSON_STRING);
    return value->u.s.string;
}
size_t json_get_string_length(const json_value *value)
{
    assert(value && value->type == JSON_STRING);
    return value->u.s.length;
}
size_t json_get_array_size(const json_value *v)
{
    assert(v && v->type == JSON_ARRAY);
    return v->u.a.size;
}
json_value *json_get_array_element(const json_value *v, size_t index)
{
    assert(v && v->type == JSON_ARRAY && index < v->u.a.size);
    return v->u.a.e + index;
}
size_t json_get_object_size(const json_value *v)
{
    assert(v && v->type == JSON_OBJECT);
    return v->u.o.size;
}
json_object_member *json_get_object_element(const json_value *v, size_t index)
{
    assert(v && v->type == JSON_OBJECT && index < v->u.o.size);
    return v->u.o.m + index;
}
void json_set_string(json_value *v, const char *s, size_t len)
{
    assert(v != NULL && (s != NULL || len == 0));
    json_free(v);
    //free(v->u.s.string);
    v->u.s.string = (char *)malloc((len + 1) * sizeof(char));
    if (!v->u.s.string)
        exit(EXIT_FAILURE);
    memcpy(v->u.s.string, s, len * sizeof(char));
    v->u.s.string[len] = '\0';
    v->u.s.length = len;
    v->type = JSON_STRING;
}
/* ws = *(%x20 / %x09 / %x0A / %x0D) */
static void json_parse_whitespace(json_context *context)
{
    const char *p = context->json;
    //p指向第一个非空白字符
    while (*p == ' ' || *p == '\t' || *p == '\n' || *p == '\r')
        p++;
    context->json = p;
}

//解析  /* value = null / false / true */
static parse_result json_parse_value(json_context *context, json_value *value)
{
    parse_result res;
    switch (*context->json)
    {
    case 'n':
        res = json_parse_literal(context, value, "null", JSON_NULL); //null
        break;
    case 't':
        res = json_parse_literal(context, value, "true", JSON_TRUE); //true
        break;
    case 'f':
        res = json_parse_literal(context, value, "false", JSON_FALSE); //false
        break;
    case '\"':
        res = json_parse_string(context, value);
        break;
    case '[':
        res = json_parse_array(context, value);
        break;
    case '{':
        res = json_parse_object(context, value);
        break;
    case '\0':
        res = PARSE_EXPECT_VALUE; //没有值
        break;
    default:
        res = json_parse_number(context, value); //其余情况，数字
        break;
    }
    return res;
}

static parse_result json_parse_literal(json_context *context, json_value *value, const char *literal, json_type type)
{
    //逐字对比context->json 和 literal
    size_t index = 0;
    for (index = 0; literal[index] != '\0'; index++)
        if (context->json[index] != literal[index])
            return PARSE_INVALID_VALUE;
    context->json += index;
    value->type = type;
    return PARSE_OK;
}
//解析 number
static parse_result json_parse_number(json_context *context, json_value *value)
{
    /*
    number = [ "-" ] int [ frac ] [ exp ]
    int = "0" / digit1-9 *digit
    frac = "." 1*digit
    exp = ("e" / "E") ["-" / "+"] 1*digit
    */
    const char *p = context->json;
    //DFA判断语法是否正确
    if (*p == '-')
        p++;
    if (!ISDIGIT(*p))
        return PARSE_INVALID_VALUE;
    if (*p == '0')
        p++;
    else
        while (ISDIGIT(*p))
            p++;
    if (*p == '.')
    {
        p++;
        if (!ISDIGIT(*p))
            return PARSE_INVALID_VALUE;
        while (ISDIGIT(*p))
            p++;
    }
    if (*p == 'e' || *p == 'E')
    {
        p++;
        if (*p == '-' || *p == '+')
            p++;
        while (ISDIGIT(*p))
            p++;
    }
    if (*p != '\0' && *p != ']' && *p != ',' && *p != ' ')
        return PARSE_INVALID_VALUE;
    //到这里说明数字的语法正确，使用strtod进行解析
    errno = 0;
    value->u.number = strtod(context->json, NULL);
    if (errno == ERANGE && value->u.number == HUGE_VAL)
        return PARSE_NUMBER_TOO_BIG;
    context->json = p;
    value->type = JSON_NUMBER;
    return PARSE_OK;
}

//parse string 将c中字符串进行解析结果放进v
static parse_result json_parse_string(json_context *c, json_value *v)
{
    /* "      "  */
    // v需要 string , length
    EXPECT(c, '\"');
    json_init(v);
    size_t length = 0;
    size_t top = c->top;
    size_t u = 0;
    size_t u2 = 0;
    const char *p = c->json;
    while (1)
    {
        //  "Hello\\nWorld"
        switch (*p)
        {
        case '\"':
            v->type = JSON_STRING;
            length = c->top - top;
            json_set_string(v, (const char *)json_context_pop(c, length), length);
            c->json = ++p;
            return PARSE_OK;
        case '\0':
            STRING_ERROR(PARSE_MISS_QUOTATION_MARK);
        case '\\':
            p++;
            switch (*p++)
            {
            case '\"':
                PUTC(c, '\"');
                break;
            case '\\':
                PUTC(c, '\\');
                break;
            case '/':
                PUTC(c, '/');
                break;
            case 'b':
                PUTC(c, '\b');
                break;
            case 'f':
                PUTC(c, '\f');
                break;
            case 'n':
                PUTC(c, '\n');
                break;
            case 'r':
                PUTC(c, '\r');
                break;
            case 't':
                PUTC(c, '\t');
                break;
            case 'u':
                //处理unicode
                if (!(p = json_parse_hex4(p, &u)))
                    STRING_ERROR(PARSE_INVALID_UNICODE_HEX);
                //高代理项
                if (ISSURROGATE(u))
                {
                    if (!(*p == '\\' && (*(p + 1) == 'u')))
                        STRING_ERROR(PARSE_INVALID_UNICODE_SURROGATE);
                    p += 2;
                    if (!(p = json_parse_hex4(p, &u2)))
                        STRING_ERROR(PARSE_INVALID_UNICODE_HEX);
                    if (ISSURROGATE(u2))
                        STRING_ERROR(PARSE_INVALID_UNICODE_SURROGATE);
                    u = (((u - 0xD800) << 10) | (u2 - 0xDC00)) + 0x10000;
                }
                json_encode_utf8(c, u);
                break;
            default:
                STRING_ERROR(PARSE_INVALID_STRING_ESCAPE);
            }
            break;
        default:
            PUTC(c, *p++);
            break;
        }
    }
}
//解析 array  [ 1, [1,2],true,\"123\"]
static parse_result json_parse_array(json_context *c, json_value *v)
{
    EXPECT(c, '[');
    parse_result res;
    //清除空白
    json_parse_whitespace(c);
    if (*c->json == ']')
    {
        //数组解析完成
        c->json++;
        v->type = JSON_ARRAY;
        return PARSE_OK;
    }
    while (1)
    {
        //解析到数组中的每一个元素，使用json_parse_value判断其类型和值板寸到一个新的json_value中，然后将新的json_value附加到根value中即可。
        json_parse_whitespace(c);
        json_value *temp_value = (json_value *)malloc(sizeof(json_value));
        json_init(temp_value);
        if ((res = json_parse_value(c, temp_value)) != PARSE_OK)
            return res;
        //将该元素加到根value中。
        v->u.a.e = (json_value *)realloc(v->u.a.e, (v->u.a.size + 1) * sizeof(json_value));
        assert(v->u.a.e);
        memcpy(v->u.a.e + (v->u.a.size), temp_value, sizeof(json_value));
        free(temp_value);
        temp_value = NULL;
        v->u.a.size++;
        json_parse_whitespace(c);
        if (*c->json == ',')
        {
            c->json++;
        }
        else if (*c->json == ']')
        {
            c->json++;
            v->type = JSON_ARRAY;
            return PARSE_OK;
        }
        else
            return PARSE_MISS_COMMA_OR_SQUARE_BRACKET;
    }
}
//解析 object {"a": 1, "b": [2,3], "c":null, "d": {"e":true, "f": false} }
static parse_result json_parse_object(json_context *c, json_value *v)
{
    EXPECT(c, '{');
    parse_result res;
    json_parse_whitespace(c);
    if (*c->json == '}')
    {
        v->type = JSON_OBJECT;
        c->json++;
        return PARSE_OK;
    }
    while (1)
    {
        //解析对象中的每一个元素，将解析结果放在一个temp_member中，解析完成之后加入到根结果中。
        json_parse_whitespace(c);
        //先解析出一个字符串z作为key，然后expect一个冒号，接着解析下一个值作为value。
        //完成上面一轮解析之后判断遇到的是什么符号，若果是 } 则说明解析完成。 ‘，’说明需要继续解析下一个值。其余说明解析失败。
        //1. 解析一个字符串 key
        if (*c->json != '\"')
            return PARSE_MISS_COMMA_OR_CURLY_BRACKET;
        json_value *temp_key = (json_value *)malloc(sizeof(json_value));
        assert(temp_key);
        json_init(temp_key);
        if ((res = json_parse_string(c, temp_key)) != PARSE_OK)
        {
            free(temp_key);
            temp_key = NULL;
            return PARSE_MISS_KEY;
        }
        //2. 解析出一个值 value
        json_parse_whitespace(c);
        if (*c->json != ':')
        {
            free(temp_key);
            temp_key = NULL;
            return PARSE_MISS_COMMA_OR_CURLY_BRACKET;
        }
        c->json++;
        json_parse_whitespace(c);
        json_value *temp_value = (json_value *)malloc(sizeof(json_value));
        assert(temp_value);
        json_init(temp_value);
        if ((res = json_parse_value(c, temp_value)) != PARSE_OK)
        {
            free(temp_key);
            temp_key = NULL;
            free(temp_value);
            temp_value = NULL;
            return PARSE_MISS_VALUE;
        }
        //3. 解析正常，将解析的值放入一个对象中，并将该对象加到根值中。
        json_object_member *temp_member = (json_object_member *)malloc(sizeof(json_object_member));
        temp_member->k = (char *)malloc((temp_key->u.s.length + 1) * sizeof(char));
        assert(temp_member && temp_member->k);
        memcpy(temp_member->k, temp_key->u.s.string, (temp_key->u.s.length + 1) * sizeof(char));
        memcpy(&temp_member->v, temp_value, sizeof(json_value));
        temp_member->k_len = temp_key->u.s.length;
        //将解析出的对象加入根值中。
        v->u.o.m = (json_object_member *)realloc(v->u.o.m, (v->u.o.size + 1) * sizeof(json_object_member));
        memcpy(v->u.o.m + v->u.o.size, temp_member, sizeof(json_object_member));
        (v->u.o.m + v->u.o.size)->k = (char *)malloc((temp_member->k_len + 1) * sizeof(char));
        memcpy((v->u.o.m + v->u.o.size)->k, temp_member->k, (temp_member->k_len + 1) * sizeof(char));
        v->u.o.size++;
        //加入完毕，继续解析
        //free(temp_member->k);
        temp_member->k = NULL;
        //json_free_object_member(temp_member);
        //json_free(temp_key);
        //json_free(temp_value);
        temp_key = NULL;
        temp_value = NULL;
        temp_member = NULL;
        json_parse_whitespace(c);
        if (*c->json == '}')
        {
            //解析完成。
            c->json++;
            v->type = JSON_OBJECT;
            return PARSE_OK;
        }
        else if (*c->json == ',')
        {
            //继续解析下一个
            c->json++;
        }
        else
            return PARSE_MISS_COMMA_OR_CURLY_BRACKET;
    }
}
void json_free(json_value *v)
{
    assert(v != NULL);
    if ((v->type == JSON_STRING) && (v->u.s.string != NULL))
        free(v->u.s.string);
    v->u.s.string = NULL;
    if (v->type == JSON_ARRAY && v->u.a.e != NULL)
    {
        for (int i = 0; i <= v->u.a.size - 1; i++)
        {
            json_free(&v->u.a.e[i]);
        }
        free(v->u.a.e);
        v->u.a.e = NULL;
        v->u.a.size = 0;
    }
    if (v->type == JSON_OBJECT && v->u.o.m != NULL)
    {
        for (int i = 0; i <= v->u.o.size - 1; i++)
        {
            json_free_object_member(&v->u.o.m[i]);
        }
        free(v->u.o.m);
        v->u.o.m = NULL;
        v->u.o.size = 0;
    }
    v->type = JSON_UNKONE_TYPE;
}
//释放object_member
void json_free_object_member(json_object_member *o)
{
    assert(o);
    free(o->k);
    o->k = NULL;
    o->k_len = 0;
    free(o);
    o = NULL;
}
//压入数据，单位为字节 更新栈顶并返回
static void *json_context_push(json_context *c, size_t size)
{
    assert(c && size >= 0);
    if (c->top + size >= c->size)
        if (c->size == 0)
            c->size = JSON_PARSE_STACK_INIT_SIZE;
    while (c->top + size >= c->size)
        c->size += c->size >> 1;
    //现在c->size为应该为c->stack分配的空间大小
    c->stack = (void *)realloc(c->stack, c->size);
    c->top += size;
    return c->stack + c->top;
}
//弹出数据
static void *json_context_pop(json_context *c, size_t size)
{
    assert(c && size >= 0 && size <= c->size);
    c->top -= size;
    return c->stack + c->top + 1;
}
static const char *json_parse_hex4(const char *p, size_t *u)
{
    assert(p);
    int ch;
    *u ^= *u;
    for (int i = 0; i <= 3; i++)
    {
        ch = *p++;
        *u <<= 4;
        //p指向的数据为一个字符而已。
        //0-F
        if (ch <= '9' && ch >= '0')
            *u |= ch - '0';
        else if (ch <= 'Z' && ch >= 'A')
            *u |= ch - 'A' + 10;
        else if (ch <= 'z' && ch >= 'a')
            *u |= ch - 'a' + 10;
        else
            return NULL;
    }
    return p;
}
//将一个4位16进制的数，编码位utf-8
static const char *json_encode_utf8(json_context *c, size_t u)
{
    if (u <= 0x007f)
    {
        PUTC(c, u & 0xff);
    }
    else if (u <= 0x07ff)
    {
        PUTC(c, ((u >> 6) & 0x3f) | 0xc0);
        PUTC(c, (u & 0x3f) | 0x80);
    }
    else if (u <= 0xffff)
    {
        PUTC(c, ((u >> 12) & 0x0f) | 0xe0);
        PUTC(c, ((u >> 6) & 0x3f) | 0x80);
        PUTC(c, (u & 0x3f) | 0x80);
    }
    else if (u <= 0x10FFFF)
    {
        PUTC(c, ((u >> 18) & 0x07) | 0xf0);
        PUTC(c, ((u >> 12) & 0x3f) | 0x80);
        PUTC(c, ((u >> 6) & 0x3f) | 0x80);
        PUTC(c, (u & 0x3f) | 0x80);
    }
}
//将value转化为一个字符串
parse_result json_stringify(const json_value *v, char **str, size_t *length)
{
    assert(v && v->type != JSON_UNKONE_TYPE);
    json_context *c = (json_context *)malloc(sizeof(json_context));
    assert(c);
    json_init_context(c);
    parse_result res;
    if ((res = json_stringify_value(c, v, length)) != STRINGIFY_OK)
    {
        *length = 0;
        return STRINGIFY_ERROR;
    }
    //assert(c->top > -1);
    PUTC(c, '\0');
    *length = c->top - 1;
    *str = (char *)malloc((c->top + 1) * sizeof(char));
    memcpy(*str, c->stack, c->top);
    (*str)[(*length)] = '\0';
    printf("%s\n", *str);
    return res;
}
parse_result json_stringify_value(json_context *c, const json_value *v, size_t *length)
{
    //根据不同类型项向c中push进去不同的数据
    parse_result res = PARSE_RESULT_UNDIFINED;
    switch (v->type)
    {
    case JSON_NULL:
        PUTS(c, "null", 4);
        res = STRINGIFY_OK;
        break;
    case JSON_TRUE:
        PUTS(c, "true", 4);
        res = STRINGIFY_OK;
        break;
    case JSON_FALSE:
        PUTS(c, "false", 5);
        res = STRINGIFY_OK;
        break;
    case JSON_NUMBER:
    {
        char buffer[32];
        int length = sprintf(buffer, "%.17g", v->u.number);
        PUTS(c, buffer, length);
        res = STRINGIFY_OK;
        break;
    }
    case JSON_STRING:
    {
        PUTS(c, "\"", 1);
        PUTS(c, v->u.s.string, v->u.s.length);
        PUTS(c, "\"", 1);
        res = STRINGIFY_OK;
        break;
    }
    case JSON_ARRAY:
    {
        PUTS(c, "[", 1)
        for (size_t i = 0; i <= v->u.a.size - 1; i++)
        {
            if ((res = json_stringify_value(c, &v->u.a.e[i], length)) != STRINGIFY_OK)
                exit(EXIT_FAILURE);
            if (i != v->u.a.size - 1)
                PUTS(c, ",", 1);
        }
        PUTS(c, "]", 1);
        res = STRINGIFY_OK;
        break;
    }
    case JSON_OBJECT:
    {
        PUTS(c, "{\n", 2)
        for (size_t i = 0; i <= v->u.o.size - 1; i++)
        {
            //key
            PUTS(c, "\"", 1);
            PUTS(c, v->u.o.m[i].k, v->u.o.m[i].k_len);
            PUTS(c, "\"", 1);
            PUTS(c, ": ", 2);
            if ((res = json_stringify_value(c, &v->u.o.m[i].v, length)) != STRINGIFY_OK)
                exit(EXIT_FAILURE);
            if (i != v->u.o.size - 1)
                PUTS(c, ",\n", 2);
        }

        PUTS(c, "}", 1);
        res = STRINGIFY_OK;
        break;
    }
    default:
        return STRINGIFY_ERROR;
    }
    return res;
}

test.c

#include "json.c"

//测试框架
static int main_ret = 0;
static int test_count = 0;
static int test_pass = 0;

//使用 do,while(0) 声明宏，这样的宏展开后不会出现一些奇怪的问题。
//将文件名和对应行号输出到标准错误输出
#define EXPECT_EQ_BASE(equality, expect, actual, format)                                                           \
    do                                                                                                             \
    {                                                                                                              \
        test_count++;                                                                                              \
        if (equality)                                                                                              \
            test_pass++;                                                                                           \
        else                                                                                                       \
        {                                                                                                          \
            fprintf(stderr, "%s:%d: expect: " format " actual: " format "\n", __FILE__, __LINE__, expect, actual); \
            main_ret = 1;                                                                                          \
        }                                                                                                          \
    } while (0)

#define EXPECT_EQ_INT(expect, actual) EXPECT_EQ_BASE((expect) == (actual), expect, actual, "%d")

#define EXPECT_EQ_DOUBLE(expect, actual) EXPECT_EQ_BASE((expect) == (actual), expect, actual, "%lf")

#define EXPECT_EQ_STRING(expect, actual, length) EXPECT_EQ_BASE(sizeof(expect) - 1 == length && !memcmp(expect, actual, length), expect, actual, "%s")

#define EXPECT_EQ_SIZE_T(expect, actual) EXPECT_EQ_BASE((expect) == (actual), (size_t)expect, (size_t)actual, "%zu")

#define TEST_ERROR(error, json)                     \
    do                                              \
    {                                               \
        json_value v;                               \
        EXPECT_EQ_INT(error, json_parse(&v, json)); \
    } while (0)

//number测试
#define TEST_NUMBER(expect, json)                      \
    do                                                 \
    {                                                  \
        json_value v;                                  \
        v.type = JSON_UNKONE_TYPE;                     \
        EXPECT_EQ_INT(PARSE_OK, json_parse(&v, json)); \
        EXPECT_EQ_INT(JSON_NUMBER, json_get_type(&v)); \
        EXPECT_EQ_DOUBLE(expect, json_get_number(&v)); \
    } while (0)

//string
#define TEST_STRING(expect, json)                                                  \
    do                                                                             \
    {                                                                              \
        json_value v;                                                              \
        json_init(&v);                                                             \
        EXPECT_EQ_INT(PARSE_OK, json_parse(&v, json));                             \
        EXPECT_EQ_INT(JSON_STRING, json_get_type(&v));                             \
        EXPECT_EQ_STRING(expect, json_get_string(&v), json_get_string_length(&v)); \
        json_free(&v);                                                             \
    } while (0)

#define TEST_ROUNDTRIP(json)                                              \
    do                                                                    \
    {                                                                     \
        json_value v;                                                     \
        char *json2;                                                      \
        size_t length;                                                    \
        json_init(&v);                                                    \
        EXPECT_EQ_INT(PARSE_OK, json_parse(&v, json));                    \
        EXPECT_EQ_INT(STRINGIFY_OK, json_stringify(&v, &json2, &length)); \
        EXPECT_EQ_STRING(json, json2, length);                            \
        json_free(&v);                                                    \
        free(json2);                                                      \
    } while (0)

//解析测试 NULL
static void test_parse_null()
{
    json_value v;
    v.type = JSON_UNKONE_TYPE;
    //正常解析
    EXPECT_EQ_INT(PARSE_OK, json_parse(&v, "null"));
    EXPECT_EQ_INT(JSON_NULL, json_get_type(&v));
    EXPECT_EQ_INT(PARSE_OK, json_parse(&v, " \n \r \t null \n \r \t "));
    EXPECT_EQ_INT(JSON_NULL, json_get_type(&v));
    //测试空字符解析
    EXPECT_EQ_INT(PARSE_EXPECT_VALUE, json_parse(&v, ""));
    //测试 PARSE_ROOT_NOT_SINGULAR
    EXPECT_EQ_INT(PARSE_ROOT_NOT_SINGULAR, json_parse(&v, "null f"));
    //测试 PARSE_INVALID_VALUE
    EXPECT_EQ_INT(PARSE_INVALID_VALUE, json_parse(&v, "nul"));
}
static void test_parse_true()
{
    json_value v;
    v.type = JSON_UNKONE_TYPE;
    //正常解析
    EXPECT_EQ_INT(PARSE_OK, json_parse(&v, "true"));
    EXPECT_EQ_INT(JSON_TRUE, json_get_type(&v));
    EXPECT_EQ_INT(PARSE_OK, json_parse(&v, " \n \r \t true \n \r \t "));
    EXPECT_EQ_INT(JSON_TRUE, json_get_type(&v));
    //测试空字符解析
    EXPECT_EQ_INT(PARSE_EXPECT_VALUE, json_parse(&v, ""));
    //测试 PARSE_ROOT_NOT_SINGULAR
    EXPECT_EQ_INT(PARSE_ROOT_NOT_SINGULAR, json_parse(&v, "true f"));
    //测试 PARSE_INVALID_VALUE
    EXPECT_EQ_INT(PARSE_INVALID_VALUE, json_parse(&v, "tru"));
}
static void test_parse_false()
{
    json_value v;
    v.type = JSON_UNKONE_TYPE;
    //正常解析
    EXPECT_EQ_INT(PARSE_OK, json_parse(&v, "false"));
    EXPECT_EQ_INT(JSON_FALSE, json_get_type(&v));
    EXPECT_EQ_INT(PARSE_OK, json_parse(&v, " \n \r \t false \n \r \t "));
    EXPECT_EQ_INT(JSON_FALSE, json_get_type(&v));
    //测试空字符解析
    EXPECT_EQ_INT(PARSE_EXPECT_VALUE, json_parse(&v, ""));
    //测试 PARSE_ROOT_NOT_SINGULAR
    EXPECT_EQ_INT(PARSE_ROOT_NOT_SINGULAR, json_parse(&v, "false f"));
    //测试 PARSE_INVALID_VALUE
    EXPECT_EQ_INT(PARSE_INVALID_VALUE, json_parse(&v, "fals"));
}

static void test_parse_number()
{
    TEST_NUMBER(0.0, "0");
    TEST_NUMBER(0.0, "-0");
    TEST_NUMBER(0.0, "-0.0");
    TEST_NUMBER(1.0, "1");
    TEST_NUMBER(-1.0, "-1");
    TEST_NUMBER(1.5, "1.5");
    TEST_NUMBER(-1.5, "-1.5");
    TEST_NUMBER(200, " 200 ");
    TEST_NUMBER(3.1416, "3.1416");
    TEST_NUMBER(1E10, "1E10");
    TEST_NUMBER(1e10, "1e10");
    TEST_NUMBER(1E+10, "1E+10");
    TEST_NUMBER(1E-10, "1E-10");
    TEST_NUMBER(-1E10, "-1E10");
    TEST_NUMBER(-1e10, "-1e10");
    TEST_NUMBER(-1E+10, "-1E+10");
    TEST_NUMBER(-1E-10, "-1E-10");
    TEST_NUMBER(1.234E+10, "1.234E+10");
    TEST_NUMBER(1.234E-10, "1.234E-10");
    TEST_NUMBER(0.0, "1e-10000");                                    /* must underflow */
    TEST_NUMBER(1.0000000000000002, "1.0000000000000002");           /* the smallest number > 1 */
    TEST_NUMBER(4.9406564584124654e-324, "4.9406564584124654e-324"); /* minimum denormal */
    TEST_NUMBER(-4.9406564584124654e-324, "-4.9406564584124654e-324");
    TEST_NUMBER(2.2250738585072009e-308, "2.2250738585072009e-308"); /* Max subnormal double */
    TEST_NUMBER(-2.2250738585072009e-308, "-2.2250738585072009e-308");
    TEST_NUMBER(2.2250738585072014e-308, "2.2250738585072014e-308"); /* Min normal positive double */
    TEST_NUMBER(-2.2250738585072014e-308, "-2.2250738585072014e-308");
    TEST_NUMBER(1.7976931348623157e+308, "1.7976931348623157e+308"); /* Max double */
    TEST_NUMBER(-1.7976931348623157e+308, "-1.7976931348623157e+308");
}
static void test_parse_invalid_value()
{
    /* ... */
    /* invalid number */
    TEST_ERROR(PARSE_INVALID_VALUE, "+0");
    TEST_ERROR(PARSE_INVALID_VALUE, "+1");
    TEST_ERROR(PARSE_INVALID_VALUE, ".123"); /* at least one digit before '.' */
    TEST_ERROR(PARSE_INVALID_VALUE, "1.");   /* at least one digit after '.' */
    TEST_ERROR(PARSE_INVALID_VALUE, "INF");
    TEST_ERROR(PARSE_INVALID_VALUE, "inf");
    TEST_ERROR(PARSE_INVALID_VALUE, "NAN");
    TEST_ERROR(PARSE_INVALID_VALUE, "nan");
    TEST_ERROR(PARSE_ROOT_NOT_SINGULAR, "200 0");
    TEST_ERROR(PARSE_NUMBER_TOO_BIG, "9.9e100000000");
}

static void test_access_string()
{
    json_value v;
    json_init(&v);
    json_set_string(&v, "", 0);
    EXPECT_EQ_STRING("", json_get_string(&v), json_get_string_length(&v));
    json_set_string(&v, "Hello", 5);
    EXPECT_EQ_STRING("Hello", json_get_string(&v), json_get_string_length(&v));
}
static void test_parse_string()
{
    TEST_STRING("", "\"\"");
    TEST_STRING("Hello", "\"Hello\"");
    TEST_STRING("Hello\nWorld", "\"Hello\\nWorld\"");
    TEST_STRING("\" \\ / \b \f \n \r \t", "\"\\\" \\\\ \\/ \\b \\f \\n \\r \\t\"");
    TEST_STRING("Hello\0World", "\"Hello\\u0000World\"");
    TEST_STRING("\x24", "\"\\u0024\"");                    /* Dollar sign U+0024 */
    TEST_STRING("\xC2\xA2", "\"\\u00A2\"");                /* Cents sign U+00A2 */
    TEST_STRING("\xE2\x82\xAC", "\"\\u20AC\"");            /* Euro sign U+20AC */
    TEST_STRING("\xF0\x9D\x84\x9E", "\"\\uD834\\uDD1E\""); /* G clef sign U+1D11E */
    TEST_STRING("\xF0\x9D\x84\x9E", "\"\\ud834\\udd1e\""); /* G clef sign U+1D11E */
}
//测试array
static void test_access_array()
{
    json_value v;
    json_init(&v);
    EXPECT_EQ_INT(PARSE_OK, json_parse(&v, "[ 1, [[1],2],true,\"123\"]"));
    EXPECT_EQ_INT(JSON_ARRAY, json_get_type(&v));
    EXPECT_EQ_SIZE_T(4, json_get_array_size(&v));
    json_free(&v);
}
//测试array
static void test_parse_array()
{
    json_value v;
    json_init(&v);
    EXPECT_EQ_INT(PARSE_OK, json_parse(&v, "[ 1,[], [[1],2],true,\"array\"]"));
    EXPECT_EQ_INT(JSON_ARRAY, json_get_type(&v));
    EXPECT_EQ_SIZE_T(5, json_get_array_size(&v));
    //测试数组的第0个元素
    EXPECT_EQ_INT(JSON_NUMBER, json_get_array_element(&v, 0)->type);
    EXPECT_EQ_INT(1, json_get_array_element(&v, 0)->u.number);
    //测试数组的第1个元素
    EXPECT_EQ_INT(JSON_ARRAY, json_get_array_element(&v, 1)->type);
    EXPECT_EQ_SIZE_T(0, json_get_array_element(&v, 1)->u.a.size);
    //测试数组的第2个元素
    EXPECT_EQ_INT(JSON_ARRAY, json_get_type(&v.u.a.e[2]));
    EXPECT_EQ_SIZE_T(2, json_get_array_size(&v.u.a.e[2]));
    //2.1
    EXPECT_EQ_INT(JSON_ARRAY, json_get_type(&v.u.a.e[2].u.a.e[0]));
    EXPECT_EQ_INT(1, v.u.a.e[2].u.a.e[0].u.a.e[0].u.number);
    EXPECT_EQ_SIZE_T(1, json_get_array_size(&v.u.a.e[2].u.a.e[0]));
    //2.2
    EXPECT_EQ_INT(JSON_NUMBER, json_get_type(&v.u.a.e[2].u.a.e[1]));
    EXPECT_EQ_INT(2, v.u.a.e[2].u.a.e[1].u.number);
    //测试数组的第3个元素
    EXPECT_EQ_INT(JSON_TRUE, json_get_type(&v.u.a.e[3]));
    //测试数组的第4个元素
    EXPECT_EQ_INT(JSON_STRING, json_get_type(&v.u.a.e[4]));
    EXPECT_EQ_INT(strlen("array"), v.u.a.e[4].u.s.length);
    EXPECT_EQ_STRING("array", v.u.a.e[4].u.s.string, v.u.a.e[4].u.s.length);
    json_free(&v);
}

// {"a": 1, "b": [2,3], "c":null, "d": {"e":true, "f": false} }
static void test_access_object()
{
    json_value v;
    json_init(&v);
    EXPECT_EQ_INT(PARSE_OK, json_parse(&v, "{\"a\": 1, \"b\": [2,3], \"c\":null, \"d\": {\"e\":true, \"f\": false} }"));
    EXPECT_EQ_INT(JSON_OBJECT, json_get_type(&v));
    EXPECT_EQ_SIZE_T(4, json_get_object_size(&v));
    json_free(&v);
}
static void test_parse_object()
{
    json_value v;
    json_init(&v);
    EXPECT_EQ_INT(PARSE_OK, json_parse(&v, "{\"a\": 1, \"b\": [2,3], \"c\":null, \"d\": {\"e\":true, \"f\": false} }"));
    EXPECT_EQ_INT(JSON_OBJECT, json_get_type(&v));
    EXPECT_EQ_SIZE_T(4, json_get_object_size(&v));
    //第0个元素
    EXPECT_EQ_STRING("a", v.u.o.m[0].k, v.u.o.m[0].k_len);
    EXPECT_EQ_INT(JSON_NUMBER, v.u.o.m[0].v.type);
    EXPECT_EQ_INT(1, v.u.o.m[0].v.u.number);
    //第1个元素
    EXPECT_EQ_STRING("b", v.u.o.m[1].k, v.u.o.m[1].k_len);
    EXPECT_EQ_INT(JSON_ARRAY, v.u.o.m[1].v.type);
    EXPECT_EQ_INT(2, v.u.o.m[1].v.u.a.e[0].u.number);
    EXPECT_EQ_INT(3, v.u.o.m[1].v.u.a.e[1].u.number);
    //第2个元素
    EXPECT_EQ_STRING("c", v.u.o.m[2].k, v.u.o.m[2].k_len);
    EXPECT_EQ_INT(JSON_NULL, v.u.o.m[2].v.type);
    //第3个元素
    EXPECT_EQ_STRING("d", v.u.o.m[3].k, v.u.o.m[3].k_len);
    EXPECT_EQ_INT(JSON_OBJECT, v.u.o.m[3].v.type);
    EXPECT_EQ_SIZE_T(2, v.u.o.m[3].v.u.o.size);
    //3.1
    EXPECT_EQ_STRING("e", v.u.o.m[3].v.u.o.m[0].k, v.u.o.m[3].v.u.o.m[0].k_len);
    EXPECT_EQ_INT(JSON_TRUE, v.u.o.m[3].v.u.o.m[0].v.type);
    //3.2
    EXPECT_EQ_STRING("f", v.u.o.m[3].v.u.o.m[1].k, v.u.o.m[3].v.u.o.m[1].k_len);
    EXPECT_EQ_INT(JSON_FALSE, v.u.o.m[3].v.u.o.m[1].v.type);

    json_free(&v);
}

static void test_stringify()
{
    TEST_ROUNDTRIP("null");
    TEST_ROUNDTRIP("false");
    TEST_ROUNDTRIP("true");
    TEST_ROUNDTRIP("{\"a\": 1,\"b\": [2,3],\"c\": null,\"d\": {\"e\": true,\"f\": false}}"); //这个测试是正确的，只因测试程序判断不出空格
    /* ... */
}

static void test_file()
{
    FILE *fp;
    char *json = (char *)malloc(255 * sizeof(char));
    fp = fopen("test.json", "rb");
    //fgets( json,255, fp );
    //printf("%s",json);
    size_t size = 0;
    while ((json[size++] = getc(fp)) != EOF)
        ;
    json[size] = '\0';
    printf("%s\n", json);
}
//解析 测试
static void test_parse()
{
    test_parse_null();
    test_parse_true();
    test_parse_false();
    test_parse_number();
    test_parse_invalid_value();
    test_access_string();
    test_parse_string();
    test_access_array();
    test_parse_array();
    test_access_object();
    test_parse_object();
    test_stringify();
    test_file();
}

main.c

#include "test.c"

int main()
{
    test_parse();
    printf("%d/%d (%3.2f%%) passed\n", test_pass, test_count, test_pass * 100.0 / test_count);
    return main_ret;
}

崔文耀

http://myblog.cuimouren.cn

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源崔文耀 !

json

数据结构十排序

2021-08-24 数据结构排序

数据结构排序

数据结构九堆

2021-08-23 数据结构堆

数据结构堆