Table of Contents

leptjson note3 #

从零开始的 JSON 库教程笔记.

JSON 字符串语法 #

JSON 字符串语法与 C 语言相似, 用双引号将字符串括起来 (例如 "Hello") . 在字符串使用双引号作为间隔时, 怎么表示一个带有双引号的字符串呢? 为了解决这个问题, 我们引入转义字符 (escape character). JSON 的转义字符与 C 语言相同, 为 \ . JSON 的字符串语法如下:

string = quotation-mark *char quotation-mark
char = unescaped /
   escape (
       %x22 /          ; "    quotation mark  U+0022
       %x5C /          ; \    reverse solidus U+005C
       %x2F /          ; /    solidus         U+002F
       %x62 /          ; b    backspace       U+0008
       %x66 /          ; f    form feed       U+000C
       %x6E /          ; n    line feed       U+000A
       %x72 /          ; r    carriage return U+000D
       %x74 /          ; t    tab             U+0009
       %x75 4HEXDIG )  ; uXXXX                U+XXXX
escape = %x5C          ; \
quotation-mark = %x22  ; "
unescaped = %x20-21 / %x23-5B / %x5D-10FFFF

即 JSON 字符串是由前后两个双引号夹着零至多个字符构成. 字符为无转义字符或转义序列. 转义序列有 9 种, 均以反斜线开始，如常见的 \n 代表换行符. 比较特殊的是 \uXXXX, 其中 XXXX 为 16 进位的 UTF-16 编码, 本单元暂时不处理这种转义序列.

字符串表示 #

C 语言中的字符串一般表示为空结尾字符串 (null-terminated string) , 即以空字符 \0 代表字符串的结束. 然而, JSON 字符串允许含有空字符 (例如 "Hello\u0000World", 解析后为 11 个字符) . 因此, 我们分配内存来存储解析后的字符, 并且记录字符的数目 (即字符串长度) . 由于大部分 C 程序假设字符串为空结尾字符串, 我们在解析的结果最后再加上一个 \0 .

具体实现时, lept_value 实际上是一种变体类型 (variant type) . 我们通过 type 来决定它现时是哪种类型. 由于一个值不可能同时为数字和字符串, 因此可以使用 C 语言中的 union 来节省内存:

typedef struct {
    union {
        struct { char* s; size_t len; }s;  /* string */
        double n;                          /* number */
    }u;
    lept_type type;
}lept_value;

内存管理 #

由于字符串的长度不是固定的, 因此需要动态分配内存. 使用标准库 <stdlib.h> 中的 malloc() , realloc() 和 free() 来管理内存. 当一个值为字符串时, 我们需要把参数中的字符串复制一份:

void lept_set_string(lept_value* v, const char* s, size_t len) {
    assert(v != NULL && (s != NULL || len == 0)); // 非空指针 以及 0 长度的字符串都是合法的
    lept_free(v); // 先释放内存
    v->u.s.s = (char*)malloc(len + 1);
    memcpy(v->u.s.s, s, len); // 复制字符串
    v->u.s.s[len] = '\0'; // 用 '\0' 结尾
    v->u.s.len = len;
    v->type = LEPT_STRING;
}

再看看 lept_free() :

void lept_free(lept_value* v) {
    assert(v != NULL);
    if (v->type == LEPT_STRING)
        free(v->u.s.s);
    v->type = LEPT_NULL;
}

现在仅当值是字符串类型时才处理. 在 lept_free(v) 之后, 会设置类型为 null 以避免重复释放.

由于会检查 v 的类型, 在调用所有访问函数之前, 必须初始化该类型, 为此加入 lept_free(v) , 用宏实现:

# define lept_init(v) do { (v)->type = LEPT_NULL; } while(0)

前两个单元中缺少写入的 API , 在这里补全:

# define lept_set_null(v) lept_free(v) 

int lept_get_boolean(const lept_value* v);
void lept_set_boolean(lept_value* v, int b);

double lept_get_number(const lept_value* v);
void lept_set_number(lept_value* v, double n);

const char* lept_get_string(const lept_value* v);
size_t lept_get_string_length(const lept_value* v);
void lept_set_string(lept_value* v, const char* s, size_t len);

lept_free(v) 会把类型设置为 null, 因此这里用一个宏来提供 lept_set_null 这个 API.

缓冲区与堆栈 #

解析字符串 (以及之后的数组、对象) 时, 需要把解析的结果先储存在一个临时的缓冲区, 最后再用 lept_set_string() 把缓冲区的结果存进值中. 在完成解析一个字符串之前, 缓冲区的大小是不能预知的, 因此使用动态数组 (dynamic array) . 缓冲区可以复用, 以先进后出的方式访问, 即是一个动态的堆栈 (stack) 结构. 把一个动态堆栈的数据放进 lept_context 中:

typedef struct {
    const char* json;
    char* stack;
    size_t size, top;
}lept_context;

其中, size 为当前的堆栈容量, top 是栈顶的位置. 在创建 lept_context 的时候初始化 stack 并最终释放内存:

int lept_parse(lept_value* v, const char* json) {
    lept_context c;
    int ret;
    assert(v != NULL);
    c.json = json;
    c.stack = NULL;        /* <- */
    c.size = c.top = 0;    /* <- */
    lept_init(v);
    lept_parse_whitespace(&c);
    if ((ret = lept_parse_value(&c, v)) == LEPT_PARSE_OK) {
        /* ... */
    }
    assert(c.top == 0);    /* <- */
    free(c.stack);         /* <- */
    return ret;
}

在释放时, 加入断言, 确保所有数据都被弹出.

接下来实现堆栈的压入和弹出操作, 和普通的堆栈不一样, 这个堆栈以字节形式储存, 每次可以压入任意大小的数据, 并返回数据起始的指针:

# ifndef LEPT_PARSE_STACK_INIT_SIZE

# define LEPT_PARSE_STACK_INIT_SIZE 256

# endif

static void* lept_context_push(lept_context* c, size_t size) {
    void* ret;
    assert(size > 0);
    if (c->top + size >= c->size) { // 空间不足
        if (c->size == 0) // 堆栈容量为 0 , 初始化
            c->size = LEPT_PARSE_STACK_INIT_SIZE;
        while (c->top + size >= c->size) // 扩展为 1.5 倍大小
            c->size += c->size >> 1;  /* c->size * 1.5 */
        c->stack = (char*)realloc(c->stack, c->size);
    }
    ret = c->stack + c->top; // c->stack 的类型是 char*, c->top 的类型是 size_t, 可以相加
    // ret 就是数据起始的指针
    c->top += size;
    return ret;
}

static void* lept_context_pop(lept_context* c, size_t size) {
    assert(c->top >= size);
    return c->stack + (c->top -= size); // 弹出数据
}

void* 作为返回值时, 表示返回任意类型的指针.

解析字符串 #

先备份栈顶, 将解析到的字符压栈, 最后计算出长度并一次性弹出所有字符并设置到值中. 部分实现如下:

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

static int lept_parse_string(lept_context* c, lept_value* v) {
    size_t head = c->top, len;
    const char* p;
    EXPECT(c, '\"');
    p = c->json;
    for (;;) {
        char ch = *p++;
        switch (ch) {
            case '\"':
                len = c->top - head;
                lept_set_string(v, (const char*)lept_context_pop(c, len), len);
                c->json = p;
                return LEPT_PARSE_OK;
            case '\0':
                c->top = head;
                return LEPT_PARSE_MISS_QUOTATION_MARK;
            default:
                PUTC(c, ch);
        }
    }
}