原址
本文是《从零开始的 JSON 库教程》的第八个单元。代码位于 json-tutorial/tutorial08。
（题图Photo by Rob Lambert）
1. 对象键值查询
我们在第六个单元实现了 JSON 对象的数据结构，它仅为一个 lept_value 的数组：
struct lept_value {union {struct { lept_member* m; size_t size; }o;/* ... */}u;lept_type type;};struct lept_member {char* k; size_t klen; /* member key string, key string length */lept_value v; /* member value */};
为了做相应的解析测试，我们实现了最基本的查询功能：
size_t lept_get_object_size(const lept_value* v);const char* lept_get_object_key(const lept_value* v, size_t index);size_t lept_get_object_key_length(const lept_value* v, size_t index);lept_value* lept_get_object_value(lept_value* v, size_t index);
在实际使用时，我们许多时候需要查询一个键值是否存在，如存在，要获得其相应的值。我们可以提供一个函数，简单地用线性搜寻实现这个查询功能（时间复杂度 
）：
#define LEPT_KEY_NOT_EXIST ((size_t)-1)size_t lept_find_object_index(const lept_value* v, const char* key, size_t klen) {size_t i;assert(v != NULL && v->type == LEPT_OBJECT && key != NULL);for (i = 0; i < v->u.o.size; i++)if (v->u.o.m[i].klen == klen && memcmp(v->u.o.m[i].k, key, klen) == 0)return i;return LEPT_KEY_NOT_EXIST;}}
若对象内没有所需的键，此函数返回 LEPT_KEY_NOT_EXIST。使用时：
lept_value o;size_t index;lept_init(&o);lept_parse(&o, "{\"name\":\"Milo\", \"gender\":\"M\"}");index = lept_find_object_index(&o, "name", 4);if (index != LEPT_KEY_NOT_EXIST) {lept_value* v = lept_get_object_value(&o, index);printf("%s\n", lept_get_string(v));}lept_free(&o);
由于一般也是希望获取键对应的值，而不需要索引，我们再加入一个辅助函数，返回类型改为 lept_value*：
lept_value* lept_find_object_value(lept_value* v, const char* key, size_t klen) {size_t index = lept_find_object_index(v, key, klen);return index != LEPT_KEY_NOT_EXIST ? &v->u.o.m[index].v : NULL;}
上述例子便可简化为：
lept_value o, *v;/* ... */if ((v = lept_find_object_value(&o, "name", 4)) != NULL)printf("%s\n", lept_get_string(v));
2. 相等比较
在实现数组和对象的修改之前，为了测试结果的正确性，我们先实现 lept_value 的相等比较（equality comparison）。首先，两个值的类型必须相同，对于 true、false、null 这三种类型，比较类型后便完成比较。而对于数字和字符串，需进一步检查是否相等：
int lept_is_equal(const lept_value* lhs, const lept_value* rhs) {assert(lhs != NULL && rhs != NULL);if (lhs->type != rhs->type)return 0;switch (lhs->type) {case LEPT_STRING:return lhs->u.s.len == rhs->u.s.len &&memcmp(lhs->u.s.s, rhs->u.s.s, lhs->u.s.len) == 0;case LEPT_NUMBER:return lhs->u.n == rhs->u.n;/* ... */default:return 1;}}
由于值可能复合类型（数组和对象），也就是一个树形结构。当我们要比较两个树是否相等，可通过递归实现。例如，对于数组，我们先比较元素数目是否相等，然后递归检查对应的元素是否相等：
int lept_is_equal(const lept_value* lhs, const lept_value* rhs) {size_t i;/* ... */switch (lhs->type) {/* ... */case LEPT_ARRAY:if (lhs->u.a.size != rhs->u.a.size)return 0;for (i = 0; i < lhs->u.a.size; i++)if (!lept_is_equal(&lhs->u.a.e[i], &rhs->u.a.e[i]))return 0;return 1;/* ... */}}
而对象与数组的不同之处，在于概念上对象的键值对是无序的。例如，{“a”:1,”b”:2} 和 {“b”:2,”a”:1} 虽然键值的次序不同，但这两个 JSON 对象是相等的。我们可以简单地利用 lept_find_object_index() 去找出对应的值，然后递归作比较。这部分留给读者作为练习。
3. 复制、移动与交换
本单元的重点，在于修改数组和对象的内容。我们将会实现一些接口做修改的操作，例如，为对象设置一个键值，我们可能会这么设计：
void lept_set_object_value(lept_value* v, const char* key, size_t klen, const lept_value* value);void f() {lept_value v, s;lept_init(&v);lept_parse(&v, "{}");lept_init(&s);lept_set_string(&s, "Hello", 5);lept_set_object_keyvalue(&v, "s", &s); /* {"s":"Hello"} */lept_free(&v)lept_free(&s); /* 第二次释放！*/}
凡涉及赋值，都可能会引起资源拥有权（resource ownership）的问题。值 s 并不能以指针方式简单地写入对象 v，因为这样便会有两个地方都拥有 s，会做成重复释放的 bug。我们有两个选择：
- 在 lept_set_object_value() 中，把参数 value深度复制（deep copy）一个值，即把整个树复制一份，写入其新增的键值对中。
- 在 lept_set_object_value() 中，把参数 value 拥有权转移至新增的键值对，再把 value 设置成 null 值。这就是所谓的移动语意（move semantics）。
深度复制是一个常用功能，使用者也可能会用到，例如把一个 JSON 复制一个版本出来修改，保持原来的不变。所以，我们实现一个公开的深度复制函数：
void lept_copy(lept_value* dst, const lept_value* src) {size_t i;assert(src != NULL && dst != NULL && src != dst);switch (src->type) {case LEPT_STRING:lept_set_string(dst, src->u.s.s, src->u.s.len);break;case LEPT_ARRAY:/* \todo */break;case LEPT_OBJECT:/* \todo */break;default:lept_free(dst);memcpy(dst, src, sizeof(lept_value));break;}}
C++11 加入了右值引用的功能，可以从语言层面区分复制和移动语意。而在 C 语言中，我们也可以通过实现不同版本的接口（不同名字的函数），实现这两种语意。但为了令接口更简单和正交（orthgonal），我们修改了 lept_set_object_value() 的设计，让它返回新增键值对的值指针，所以我们可以用 lept_copy() 去复制赋值，也可以简单地改变新增的键值：
/* 返回新增键值对的指针 */lept_value* lept_set_object_value(lept_value* v, const char* key, size_t klen);void f() {lept_value v;lept_init(&v);lept_parse(&v, "{}");lept_set_string(lept_set_object_value(&v, "s"), "Hello", 5);/* {"s":"Hello"} */lept_copy(lept_add_object_keyvalue(&v, "t"),lept_get_object_keyvalue(&v, "s", 1));/* {"s":"Hello","t":"Hello"} */lept_free(&v);}
我们还提供了 lept_move()，它的实现也非常简单：
void lept_move(lept_value* dst, lept_value* src) {assert(dst != NULL && src != NULL && src != dst);lept_free(dst);memcpy(dst, src, sizeof(lept_value));lept_init(src);}
类似地，我们也实现了一个交换值的接口：
void lept_swap(lept_value* lhs, lept_value* rhs) {assert(lhs != NULL && rhs != NULL);if (lhs != rhs) {lept_value temp;memcpy(&temp, lhs, sizeof(lept_value));memcpy(lhs, rhs, sizeof(lept_value));memcpy(rhs, &temp, sizeof(lept_value));}}
当我们要修改对象或数组里的值时，我们可以利用这 3 个函数。例如：
const char* json = "{\"a\":[1,2],\"b\":3}";char *out;lept_value v;lept_init(&v);lept_parse(&v, json);lept_copy(lept_find_object_value(&v, "b", 1),lept_find_object_value(&v, "a", 1));printf("%s\n", out = lept_stringify(&v, NULL)); /* {"a":[1,2],"b":[1,2]} */free(out);lept_parse(&v, json);lept_move(lept_find_object_value(&v, "b", 1),lept_find_object_value(&v, "a", 1));printf("%s\n", out = lept_stringify(&v, NULL)); /* {"a":null,"b":[1,2]} */free(out);lept_parse(&v, json);lept_swap(lept_find_object_value(&v, "b", 1),lept_find_object_value(&v, "a", 1));printf("%s\n", out = lept_stringify(&v, NULL)); /* {"a":3,"b":[1,2]} */free(out);lept_free(&v);
在使用时，可尽量避免 lept_copy()，而改用 lept_move() 或 lept_swap()，因为后者不需要分配内存。当中 lept_swap() 更是无须做释放的工作，令它达到 
时间复杂度，其性能与值的内容无关。
4. 动态数组
在此单元之前的实现里，每个数组的元素数目在解析后是固定不变的，其数据结构是：
struct lept_value {union {/* ... */struct { lept_value* e; size_t size; }a; /* array: elements, element count*//* ... */}u;lept_type type;};
用这种数据结构增删元素时，我们需要重新分配一个数组，把适当的旧数据拷贝过去。但这种做法是非常低效的。例如我们想要从一个空的数组加入 
个元素，便要做 
次元素复制，即 
的时间复杂度。
其中一个改进方法，是使用动态数组（dynamic array，或称可增长数组／growable array）的数据结构。C++ STL 标准库中最常用的 std::vector 也是使用这种数据结构的容器。
改动也很简单，只需要在数组中加入容量 capacity 字段，表示当前已分配的元素数目，而 size 则表示现时的有效元素数目：
/* ... */struct { lept_value* e; size_t size, capacity; }a; /* array: elements, element count, capacity *//* ... */
我们终于提供设置数组的函数，而且它可提供初始的容量：
void lept_set_array(lept_value* v, size_t capacity) {assert(v != NULL);lept_free(v);v->type = LEPT_ARRAY;v->u.a.size = 0;v->u.a.capacity = capacity;v->u.a.e = capacity > 0 ? (lept_value*)malloc(capacity * sizeof(lept_value)) : NULL;}
我们需要稍修改 lept_parse_array()，调用 lept_set_array() 去设置类型和分配空间。
另外，类似于 lept_get_array_size()，也加入获取当前容量的函数：
size_t lept_get_array_capacity(const lept_value* v) {assert(v != NULL && v->type == LEPT_ARRAY);return v->u.a.capacity;}
如果当前的容量不足，我们需要扩大容量，标准库的 realloc() 可以分配新的内存并把旧的数据拷背过去：
void lept_reserve_array(lept_value* v, size_t capacity) {assert(v != NULL && v->type == LEPT_ARRAY);if (v->u.a.capacity < capacity) {v->u.a.capacity = capacity;v->u.a.e = (lept_value*)realloc(v->u.a.e, capacity * sizeof(lept_value));}}
当数组不需要再修改，可以使用以下的函数，把容量缩小至刚好能放置现有元素：
void lept_shrink_array(lept_value* v) {assert(v != NULL && v->type == LEPT_ARRAY);if (v->u.a.capacity > v->u.a.size) {v->u.a.capacity = v->u.a.size;v->u.a.e = (lept_value*)realloc(v->u.a.e, v->u.a.capacity * sizeof(lept_value));}}
我们不逐一检视每个数组修改函数，仅介绍一下两个例子：
lept_value* lept_pushback_array_element(lept_value* v) {assert(v != NULL && v->type == LEPT_ARRAY);if (v->u.a.size == v->u.a.capacity)lept_reserve_array(v, v->u.a.capacity == 0 ? 1 : v->u.a.capacity * 2);lept_init(&v->u.a.e[v->u.a.size]);return &v->u.a.e[v->u.a.size++];}void lept_popback_array_element(lept_value* v) {assert(v != NULL && v->type == LEPT_ARRAY && v->u.a.size > 0);lept_free(&v->u.a.e[--v->u.a.size]);}
lept_pushback_array_element() 在数组末端压入一个元素，返回新的元素指针。如果现有的容量不足，就需要调用 lept_reserve_array() 扩容。我们现在用了一个最简单的扩容公式：若容量为 0，则分配 1 个元素；其他情况倍增容量。
lept_popback_array_element() 则做相反的工作，记得删去的元素需要调用 lept_free()。
下面这 3 个函数留给读者练习：
- lept_insert_array_element() 在 index 位置插入一个元素；
- lept_erase_array_element() 删去在 index 位置开始共 count 个元素（不改容量）；
- lept_clear_array() 清除所有元素（不改容量）。
lept_value* lept_insert_array_element(lept_value* v, size_t index);void lept_erase_array_element(lept_value* v, size_t index, size_t count);void lept_clear_array(lept_value* v);
5. 动态对象
动态对象也是采用上述相同的结构，所以直接留给读者修改结构体，并实现以下函数：
void lept_set_object(lept_value* v, size_t capacity);size_t lept_get_object_capacity(const lept_value* v);void lept_reserve_object(lept_value* v, size_t capacity);void lept_shrink_object(lept_value* v);void lept_clear_object(lept_value* v);lept_value* lept_set_object_value(lept_value* v, const char* key, size_t klen);void lept_remove_object_value(lept_value* v, size_t index);
注意 lept_set_object_value() 会先搜寻是否存在现有的键，若存在则直接返回该值的指针，不存在时才新增。
6. 总结与练习
本单元主要加入了数组和对象的访问、修改方法。当中的赋值又引申了三种赋值的方式（复制、移动、交换）。这些问题是各种编程语言中都需要考虑的事情，为了减少深度复制的成本，有些程序库或运行时还会采用写入时复制（copy-on-write, COW）。而浅复制（shallow copy）则需要 引用计数（reference count）或 垃圾回收（garbage collection, GC）等技术。
另外，我们实现了以动态数组的数据结构，能较高效地对数组和对象进行增删操作。至此，我们已经完成本教程的所有核心功能。做完下面的练习后，我们还会作简单讲解，然后将迎来本教程的最后一个单元。
本单元练习内容：
- 完成 lept_is_equal() 里的对象比较部分。不需要考虑对象内有重复键的情况。
- 打开 test_array_access() 里的 #if 0，实现 lept_insert_array_element()、lept_erase_array_element() 和 lept_clear_array()。
- 打开 test_object_access() 里的 #if 0，参考动态数组，实现第 5 部分列出的所有函数。
- 完成 lept_copy() 里的数组和对象的复制部分。
如果你遇到问题，有不理解的地方，或是有建议，都欢迎在评论或 issue 中提出，让所有人一起讨论。
若有收获，就点个赞吧
0 人点赞
