这一节讲parse_object
数据结构JSON的Object 是以键值对的方式存储的。
{ key:value}这里我们默认key为JSON字符串。
要表示键值对的集合，数据结构有很多种：
- 动态数组（dynamic array）：可扩展容量的数组，如 C++ 的 std::vector。
- 有序动态数组（sorted dynamic array）：和动态数组相同，但保证元素已排序，可用二分搜寻查询成员。
- 平衡树（balanced tree）：平衡二叉树可有序地遍历成员，如红黑树和 C++ 的 std::map（std::multi_map 支持重复键）。
- 哈希表（hash table）：通过哈希函数能实现平均 O(1) 查询，如 C++11 的 std::unordered_map（unordered_multimap 支持重复键）。
设一个对象有 n 个成员，数据结构的容量是 m，n ⩽ m，那么一些常用 *** 作的时间／空间复杂度如下：
| 动态数组 | 有序动态数组 | 平衡树 | 哈希表 | |
|---|---|---|---|---|
| 有序 | 否 | 是 | 是 | 否 |
| 自定成员次序 | 可 | 否 | 否 | 否 |
| 初始化 n 个成员 | O(n) | O(n log n) | O(n log n) | 平均 O(n)、最坏 O(n^2) |
| 加入成员 | 分摊 O(1) | O(n) | O(log n) | 平均 O(1)、最坏 O(n) |
| 移除成员 | O(n) | O(n) | O(log n) | 平均 O(1)、最坏 O(n) |
| 查询成员 | O(n) | O(log n) | O(log n) | 平均 O(1)、最坏 O(n) |
| 遍历成员 | O(n) | O(n) | O(n) | O(m) |
| 检测对象相等 | O(n^2) | O(n) | O(n) | 平均 O(n)、最坏 O(n^2) |
| 空间 | O(m) | O(m) | O(n) | O(m) |
为了简单起见，我们的 leptjson 选择用动态数组的方案。
因为object用的数据结构也是动态数组，就导致了object和array非常的相像，基本唯一的区别就只有键值对了。
typedef struct lept_value lept_value;//前向声明
typedef struct lept_member lept_member;
struct lept_value{
//我们可使用 C 语言的 union 来节省内存：
union{
struct { lept_member* m; size_t size,capacity; }m_obj;
struct { lept_value* e; size_t size,capacity; }m_arr;/* array */
struct { char* s; size_t len; }m_str; /* string */
double m_num; /* number */
}u;
lept_type type;
};
struct lept_member {
char* k; size_t klen; /* member key string, key string length */
lept_value v; /* member value */
};
还记得我之前在string类时提到，string_parse里有一个string_parse_raw是后期object 在parse key值时重构得到的。那么就是在这里了。
{key :value,key:value}
我们在解析object时，左花括号({)确认是object,而后解析空白，解析键值，解析冒号，解析value，有逗号解析逗号，没有逗号解析右花括号，最后解析完毕，把整个object值给copy过去。
在内存分配上的 *** 作和array几乎一样。
static int lept_parse_object(lept_context& c, lept_value& v) {
size_t size;
lept_member m;//创建一个member
int ret;//需要返回的object解析状态flag
EXPECT(c, '{');//确定第一个字符为{右花括号
lept_parse_whitespace(c);//解析空白
if (*c.json == '}') {//空对象
c.json++;
v.type = LEPT_OBJECT;
v.u.m_obj.m = 0;
v.u.m_obj.size = 0;
return LEPT_PARSE_OK;
}
m.k = NULL;//member key置空
size = 0;//size 置零
for (;;) {
char* str; //创建一个临时字符串
lept_init(m.v);//初始化member value值
/* 1. parse key */
if (*c.json != '"') {//如果key值不是由"开头，则解析错误
ret = LEPT_PARSE_MISS_KEY;
break;
}
//如果key值解析不成功，退出循环
if ((ret = lept_parse_string_raw(c, str, m.klen)) != LEPT_PARSE_OK)
break;
//解析成功则将解析得到的值copy给member key
memcpy(m.k = (char*)malloc(m.klen + 1), str, m.klen);
m.k[m.klen] = ';'//key 尾置为空字符/* 2. parse ws colon ws */
//解析空白和冒号
lept_parse_whitespace
()c;if
( *.c!=json ':' )= {
ret ; LEPT_PARSE_MISS_COLONbreak
;}
.
c++json;lept_parse_whitespace
()c;/* parse value */
if
( (=ret lept_parse_value (,c. m)v)!= ) LEPT_PARSE_OKbreak
;//value值解析成功则压栈
memcpy
(lept_context_push(,csizeof ()lept_member),& ,msizeof ()lept_member);++
size;//压栈后将临时member init
.
m=k NULL ;/* ownership is transferred to member on stack */ /* 4. parse ws [comma | right-curly-brace] ws */
//解析空白和之后的逗号或者右花括号
lept_parse_whitespace
()c;if
( *.c==json ',' ). {
c++json;lept_parse_whitespace
()c;}
else
if ( *.c==json '}' )= {
size_t s sizeof ()lept_member* ; size//s为整个object的大小.
c++json;.
v=type ; LEPT_OBJECT.
v.u.m_obj=size ; size//如果是右花括号则object解析完毕，分配s大小的内存给v
//将栈中元素d出并copy至分配的内存中中
memcpy
(.v.u.m_obj=m ( *lept_member)malloc()s,lept_context_pop (,c) s,) s;//返回整个object解析成功
return
; LEPT_PARSE_OK}
else
= {
ret ; LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKETbreak
;}
}
//所有解析失败都会回到这里，进行一个member的释放
/* Pop and free members on the stack */
free
(.m)k;//先将member的key值释放for
( int= i 0 ;< i ; size++ i)//member值置为栈中的第i个元素 {
*
lept_member= m ( *lept_member)lept_context_pop(,csizeof ()lept_member);free
()m->k;//释放栈中第i个元素的keylept_free
()m->v;//释放栈中的第i个元素的value}
.
v=type ; LEPT_NULL//整个value置为null typereturn
; ret}
case
object作为复合类型，也是需要我们进行一个从下至上的释放的。
: LEPT_OBJECTfor
( =i 0 ;< i . v.u.m_obj;size++ i)free {
(.v.u.m_obj[m]i.)k;//释放key值lept_free
(.v.u.m_obj[m]i.)v;//释放value值}
free
(.v.u.m_obj)m;//释放整个memberbreak
;static
object的单元测试和array的不同点也主要是在key值。
void test_parse_object (); {
lept_value v;
size_t ilept_init
()v;//空对象解析
EXPECT_EQ_INT
(,LEPT_PARSE_OKlept_parse (,v" { } " ));//type测试
EXPECT_EQ_INT
(,LEPT_OBJECTlept_get_type ()v);//size测试
EXPECT_EQ_SIZE_T
(0,lept_get_object_size ()v);lept_free
()v;lept_init
()v;//多类型元素对象解析
EXPECT_EQ_INT
(,LEPT_PARSE_OKlept_parse (,v" { "
"\"n\" : null , "
"\"f\" : false , "
"\"t\" : true , "
"\"i\" : 123 , "
"\"s\" : \"abc\", "
"\"a\" : [ 1, 2, 3 ],"
"\"o\" : { \"1\" : 1, \"2\" : 2, \"3\" : 3 }"
" } "
)
);EXPECT_EQ_INT
(,LEPT_OBJECTlept_get_type ()v);EXPECT_EQ_SIZE_T
(7,lept_get_object_size ()v);//元素key值测试
EXPECT_EQ_STRING
("n",lept_get_object_key (,v0 ),lept_get_object_key_length (,v0 ));//元素type测试
EXPECT_EQ_INT
(,LEPT_NULLlept_get_type (lept_get_object_value(,v0 )));EXPECT_EQ_STRING
("f",lept_get_object_key (,v1 ),lept_get_object_key_length (,v1 ));EXPECT_EQ_INT
(,LEPT_FALSElept_get_type (lept_get_object_value(,v1 )));EXPECT_EQ_STRING
("t",lept_get_object_key (,v2 ),lept_get_object_key_length (,v2 ));EXPECT_EQ_INT
(,LEPT_TRUElept_get_type (lept_get_object_value(,v2 )));EXPECT_EQ_STRING
("i",lept_get_object_key (,v3 ),lept_get_object_key_length (,v3 ));EXPECT_EQ_INT
(,LEPT_NUMBERlept_get_type (lept_get_object_value(,v3 )));//元素value测试
EXPECT_EQ_DOUBLE
(123.0,lept_get_number (lept_get_object_value(,v3 )));EXPECT_EQ_STRING
("s",lept_get_object_key (,v4 ),lept_get_object_key_length (,v4 ));EXPECT_EQ_INT
(,LEPT_STRINGlept_get_type (lept_get_object_value(,v4 )));//元素value测试
EXPECT_EQ_STRING
("abc",lept_get_string (lept_get_object_value(,v4 )),lept_get_string_length (lept_get_object_value(,v4 )));EXPECT_EQ_STRING
("a",lept_get_object_key (,v5 ),lept_get_object_key_length (,v5 ));//元素array测试
EXPECT_EQ_INT
(,LEPT_ARRAYlept_get_type (lept_get_object_value(,v5 )));EXPECT_EQ_SIZE_T
(3,lept_get_array_size (lept_get_object_value(,v5 )));for
( =i 0 ;< i 3 ;++ i)& {
lept_value= e lept_get_array_element (lept_get_object_value(,v5 ),) i;EXPECT_EQ_INT
(,LEPT_NUMBERlept_get_type ()e);EXPECT_EQ_DOUBLE
(+i 1.0 ,lept_get_number ()e);}
EXPECT_EQ_STRING
("o",lept_get_object_key (,v6 ),lept_get_object_key_length (,v6 ));//元素object嵌套测试
&
{
lept_value= o lept_get_object_value (,v6 );EXPECT_EQ_INT
(,LEPT_OBJECTlept_get_type ()o);for
( =i 0 ;< i 3 ;++ i)& {
lept_value= ov lept_get_object_value (,o) i;EXPECT_TRUE
('1'+ == i lept_get_object_key (,o) i[0]);EXPECT_EQ_SIZE_T
(1,lept_get_object_key_length (,o) i);EXPECT_EQ_INT
(,LEPT_NUMBERlept_get_type ()ov);EXPECT_EQ_DOUBLE
(+i 1.0 ,lept_get_number ()ov);}
}
lept_free
()v;}
//错误测试之缺少key值
static
void test_parse_miss_key ()TEST_ERROR {
(,LEPT_PARSE_MISS_KEY"{:1," );TEST_ERROR
(,LEPT_PARSE_MISS_KEY"{1:1," );TEST_ERROR
(,LEPT_PARSE_MISS_KEY"{true:1," );TEST_ERROR
(,LEPT_PARSE_MISS_KEY"{false:1," );TEST_ERROR
(,LEPT_PARSE_MISS_KEY"{null:1," );TEST_ERROR
(,LEPT_PARSE_MISS_KEY"{[]:1," );TEST_ERROR
(,LEPT_PARSE_MISS_KEY) "{{}:1,";TEST_ERROR
(,LEPT_PARSE_MISS_KEY"{\"a\":1," );}
//错误测试之缺少冒号
static
void test_parse_miss_colon ()TEST_ERROR {
(,LEPT_PARSE_MISS_COLON"{\"a\"}" );TEST_ERROR
(,LEPT_PARSE_MISS_COLON"{\"a\",\"b\"}" );}
//错误测试之缺少逗号或者右花括号
static
void test_parse_miss_comma_or_curly_bracket ()TEST_ERROR {
(,LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET"{\"a\":1" );TEST_ERROR
(,LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET"{\"a\":1]" );TEST_ERROR
(,LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET"{\"a\":1 \"b\"" );TEST_ERROR
(,LEPT_PARSE_MISS_COMMA_OR_CURLY_BRACKET"{\"a\":{}" );}
lept_get_object_size
调用的接口：
size_t (const& lept_value) vassert
{
(&!=v NULL ) ;assert
(.v==type ) LEPT_OBJECT;return
. v.u.m_obj;size}
const
char *lept_get_object_key (const& lept_value, v) size_t indexassert
{
(&!=v NULL ) ;assert
(. v==type ) LEPT_OBJECT;assert
(<index . v.u.m_obj)size;return
. v.u.m_obj[m]index.;k}
lept_get_object_key_length
size_t (const& lept_value, v) size_t indexassert
{
(&!=v NULL );assert
(.v==type ) LEPT_OBJECT;assert
(<index . v.u.m_obj)size;return
. v.u.m_obj[m]index.;klen}
&
lept_valuelept_get_object_value (const& lept_value, v) size_t indexassert
{
(&!=v NULL );assert
(.v==type ) LEPT_OBJECT;assert
(<index . v.u.m_obj)size;return
. v.u.m_obj[m]index.;v}
至此，json中的6中数据类型的解析我就全部贴完了一遍代码。
想要练习的话可以试着将array的数据结构改为链表存储
将object的存储结构改为其它类型以分析不同的数据类型在具体实现时应该怎么写，以及其算法的时间复杂度的变化带来的实质上的性能变化之类的（反正我是没有搞这么多）
之后的小节就简单的贴一下stringify和API就没了。以上
lept_json Github：https://github.com/miloyip/json-tutorial
本人流星画魂第六次在csdn上做笔记，有什么错误或者是需要改进的地方请即时提出
我只是一个对编程感兴趣的人，但懒得要死，学得又不认真，希望读者能骂就骂两句，真的太懒了
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）