#include #include #include #include /* public */ enum jn_json_type { JN_STRING=1, JN_NUMBER, JN_TRUE, JN_FALSE, JN_NULL, JN_ARRAY, JN_OBJECT, JN_KEYVALUE }; /* public */ typedef struct jn_tok_st { char* s; int len; } jn_tok_t; /* public */ typedef struct jn_json_st jn_json_t; /* private */ typedef struct jn_json_st { int type; jn_tok_t k; struct jn_json_st* v; struct jn_json_st* r; /* right */ #ifdef JN_AVLTREE struct jn_json_st* l; struct jn_json_st* p; #endif } jn_json_t; #define JN_ALLOCATOR #undef JN_ALLOCATOR #define JN_ALLOCATOR /* public */ typedef struct jn_alloc_st { jn_json_t* (*alloc) (int, struct jn_alloc_st*); void (*free) (jn_json_t* ,struct jn_alloc_st*); #ifdef JN_ALLOCATOR jn_json_t* nodes; int cnt; #endif } jn_alloc_t; #define JN_MAX_LIMIT (0x100000) /* public */ void jn_init_alloc(jn_alloc_t* a); int jn_parse(jn_alloc_t* a, char* in_buf, jn_json_t** out_json); void jn_print_json(jn_json_t* json); /* private */ jn_json_t* jn_alloc_json (int size, jn_alloc_t* a); void jn_free_json (jn_json_t* n , jn_alloc_t* a); int jn_scan(char* in_buf, jn_tok_t* out_toks, int* out_len); void _jn_print_json(jn_json_t* json, int indent, int kv); /* optimized tokenizer */ int jn_scan(char* in_buf, jn_tok_t* out_toks, int* out_len) { static int eqcls[256] = { 0x8, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x2, 0x2, 0x0, 0x0, 0x2, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x2, 0x0, 0x33, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x1000, 0x1, 0x1104, 0x400, 0x20, 0x2e84, 0x2f84, 0x2f84, 0x2f84, 0x2f84, 0x2f84, 0x2f84, 0x2f84, 0x2f84, 0x2f84, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x80, 0x80, 0x80, 0x80, 0x880, 0x80, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x1, 0x38, 0x1, 0x0, 0x0, 0x0, 0x20080, 0xa0, 0x80, 0x80, 0x110880, 0xa6, 0x0, 0x0, 0x0, 0x0, 0x0, 0x440000, 0x0, 0x27, 0x0, 0x0, 0x0, 0x4020, 0x80000, 0x25, 0x208040, 0x0, 0x0, 0x0, 0x0, 0x0, 0x1, 0x0, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 }; static int tbl[] = { 0x200, 0xa00, 0x7000d01, 0x7000c01, 0x3030e09, 0x3080a18, 0x10e0e36, 0x1110e3c, 0x1150e44, 0x3031609, 0x1200, 0x7001501, 0x305160d, 0x1a00, 0x3031e09, 0x1071e10, 0x2200, 0x1072612, 0x2a00, 0x1072e14, 0x3200, 0x1073616, 0x3a00, 0x3033e09, 0x4200, 0x308461c, 0x3084620, 0x3084624, 0x4a00, 0x4a00, 0x3084e20, 0x3084e24, 0x30a5228, 0x5200, 0x5200, 0x5200, 0x30a5a28, 0x5a00, 0x3085e24, 0x3085e24, 0x7006101, 0x30a662c, 0x30c6630, 0x6200, 0x7006901, 0x6a00, 0x30c6e30, 0x30a6e2c, 0x7200, 0x30c7633, 0x30c7633, 0x7007901, 0x7a00, 0x30c7e33, 0x8200, 0x10f8638, 0x8a00, 0x1108e3a, 0x9200, 0x7009501, 0x9a00, 0x1129e3e, 0xa200, 0x113a640, 0xaa00, 0x114ae42, 0xb200, 0x700b501, 0xba00, 0x116be46, 0xc200, 0x116c648, 0xca00, 0x700cd01 }; //start = 0x7000201 char* p = in_buf; char* s = in_buf; jn_tok_t* t = out_toks; int state = 0x7000201; unsigned int cls = 0; do { p += (state>>10) & 0x1; t->s = s; t->len = p - s; t += (state>>8) & 0x1; s += (p - s) & (UINT_MAX + ((state>>9) & 0x1)); cls = eqcls[(unsigned char)(*p)]; cls = (cls>>((state & 0x00FF0000)>>16))&(state>>24); state = tbl[ (state & 0x000000FF) + cls ]; } while( (state & 0x000000FF) > 0); *out_len = t - out_toks; if(*p == 0) { return 1; /* SUCCESS */ } cls = ((state & 0xf800) >> 11); /* fail state idx */ if(cls < 1) /* fail state idx */ { /* fail msg */ } return 0; } /* simple memory allocator */ void jn_init_alloc(jn_alloc_t* a) { #ifdef JN_ALLOCATOR static jn_json_t json_nodes[JN_MAX_LIMIT]; memset(json_nodes, 0x00 ,sizeof(json_nodes)); a->nodes = json_nodes; a->cnt = 0; #endif a->alloc = jn_alloc_json; a->free = jn_free_json; } jn_json_t* jn_alloc_json (int size, jn_alloc_t* a) { jn_json_t* ret = NULL; #ifdef JN_ALLOCATOR ret = &(a->nodes[a->cnt]); a->cnt += size; #else ret = (jn_json_t*)malloc( size * sizeof(jn_json_t)); #endif memset(ret, 0x00, size * sizeof(sizeof(jn_json_t))); return ret; } void jn_free_json (jn_json_t* n , jn_alloc_t* a) { #ifdef JN_ALLOCATOR /* pass */ #else free(n); #endif } typedef struct jn_stack_st { int state; jn_tok_t* token; jn_json_t* json; int cls; } jn_stack_t; int jn_parse(jn_alloc_t* a, char* in_buf, jn_json_t** out_json) { static int eqcls[] = { 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,8 ,2 ,0 ,0 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 ,11 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,6 ,0 ,7 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , 4 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,5 ,0 ,0 ,0 ,0 ,0 ,3 ,0 ,0 ,0 ,0 ,0 ,0 ,9 ,0 ,10 ,0 ,0 }; static int tbl[] = { 0, 4, 6, 7, 8, 9, 10, 0, 0, 5, 0, 0, 1, 2, 0, 3, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 0, 31, 31, 0, 31, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 32, 32, 0, 32, 0, 0, 0, 0, 0, 0, 0, 26, 0, 0, 0, 0, 0, 0, 26, 26, 0, 26, 0, 0, 0, 0, 0, 0, 0, 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, 11, 12, 27, 0, 0, 0, 0, 0, 0, 27, 27, 0, 27, 0, 0, 0, 0, 0, 0, 0, 28, 0, 0, 0, 0, 0, 0, 28, 28, 0, 28, 0, 0, 0, 0, 0, 0, 0, 29, 0, 0, 0, 0, 0, 0, 29, 29, 0, 29, 0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 30, 30, 0, 30, 0, 0, 0, 0, 0, 0, 0, 0, 4, 6, 7, 8, 9, 10, 17, 0, 5, 0, 0, 15, 2, 16, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 19, 0, 39, 0, 0, 0, 0, 0, 0, 0, 37, 0, 0, 0, 0, 0, 0, 37, 37, 0, 37, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 35, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 22, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 33, 0, 0, 0, 0, 0, 0, 33, 33, 0, 33, 0, 0, 0, 0, 0, 0, 0, 38, 0, 0, 0, 0, 0, 0, 38, 38, 0, 38, 0, 0, 0, 0, 0, 0, 0, 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 23, 12, 0, 4, 6, 7, 8, 9, 10, 0, 0, 5, 0, 0, 24, 2, 0, 3, 0, 0, 0, 4, 6, 7, 8, 9, 10, 0, 0, 5, 0, 0, 15, 2, 25, 3, 0, 0, 34, 0, 0, 0, 0, 0, 0, 34, 34, 0, 34, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 41, 0, 41, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; static jn_stack_t stack[JN_MAX_LIMIT]; /* */ static jn_tok_t toks[JN_MAX_LIMIT]; int tok_len = 0; int tok_idx = 0; int ret = 0; /* */ int state =0; int top = 0; /* stack top */ int top_state = 0; int top_cls = 0; jn_tok_t* top_tok = NULL; jn_json_t* top_json = NULL; /* tokenizing */ ret = jn_scan(in_buf, toks, &tok_len); if(ret == 0) { return 0; /* fail */ } toks[tok_len].s = ""; toks[tok_len].len = 0; tok_idx = 0; /* parsing */ do { jn_tok_t* t = &(toks[tok_idx]); int cls = eqcls[(unsigned char)(*toks[tok_idx].s)]; state = tbl[stack[top].state * 18 + cls]; switch(state) { case 0: break; /* value: STR | NUM | TRUE | FALSE | NULL */ case 26: case 27: case 28: case 29: case 30: top_json = a->alloc(1, a); /* alloc */ top_json->type = state - 25; top_json->k = *(stack[top].token); top -= 1; top_cls = 12; /* value */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; /* value: array | object */ case 31: case 32: top_json = stack[top].json; /* pass */ top -= 1; top_cls = 12; /* value */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; /* array: [] */ case 33: top_json = a->alloc(1, a); /* alloc */ top_json->type = JN_ARRAY; top -= 2; top_cls = 13; /* array */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; /* array: [ elements ] */ case 34: top_json = a->alloc(1, a); /* alloc */ top_json->type = JN_ARRAY; top_json->v = stack[top-1].json; top -= 3; top_cls = 13; /* array */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; /* elements: value */ case 35: top_json = stack[top].json; /* pass */ top -= 1; top_cls = 14; /* elements */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; /* elements: value , elements */ case 36: top_json = stack[top-2].json; top_json->r = stack[top].json; top -= 3; top_cls = 14; /* elements */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; /* object: {} */ case 37: top_json = a->alloc(1, a); /* alloc */ top_json->type = JN_OBJECT; top -= 2; top_cls = 15; /* object */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; /* object: { members } */ case 38: top_json = a->alloc(1, a); /* alloc */ top_json->type = JN_OBJECT; top_json->v = stack[top-1].json; top -= 3; top_cls = 15; /* object */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; /* members: member */ case 39: top_json = stack[top].json; /* pass */ top -= 1; top_cls = 16; /* members */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; /* members: member , members */ case 40: top_json = stack[top-2].json; top_json->r = stack[top].json; top -= 3; top_cls = 16; /* members */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; /* member : str : value */ case 41: top_json = a->alloc(1, a); /* alloc */ top_json->type = JN_KEYVALUE; top_json->k = *(stack[top-2].token); top_json->v = stack[top].json; top -= 3; top_cls = 17; /* members */ top_state = tbl[stack[top].state * 18 + top_cls]; top_tok = NULL; break; default: /* shift */ top_cls = cls; top_state = state; top_tok = t; top_json = NULL; tok_idx++; break; } if(state > 0) { top++; stack[top].cls = top_cls; stack[top].state = top_state; stack[top].token = top_tok; stack[top].json = top_json; } }while(state > 0 && tok_idx <= tok_len); if(state == -1) /* accept */ { *out_json = stack[top].json; return 1; /* success */ } else { /* TODO: free all json memory */ *out_json = NULL; } return 0; } void jn_print_json(jn_json_t* json) { _jn_print_json(json, 0, 0); } void _jn_print_json(jn_json_t* json, int indent, int kv) { if(json != NULL) { int i=0; for(i=0; i < indent && kv == 0; i++) { printf(" "); } switch(json->type) { case JN_STRING: case JN_NUMBER: case JN_TRUE: case JN_FALSE: case JN_NULL: printf("%.*s", json->k.len, json->k.s); break; case JN_ARRAY: printf("[\n"); _jn_print_json(json->v, indent+1, 0); printf("\n"); for(i=0; i < indent; i++) { printf(" "); } printf("]"); break; case JN_OBJECT: printf("{\n"); _jn_print_json(json->v, indent+1, 0); printf("\n"); for(i=0; i < indent; i++) { printf(" "); } printf("}"); break; case JN_KEYVALUE: printf("%.*s: ", json->k.len, json->k.s); _jn_print_json(json->v, indent, 1); break; } if(json->r != NULL) { printf(",\n"); _jn_print_json(json->r, indent, 0); } else { printf(""); } } } /* LALR table -------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+- [ ] | $ | str | num | true | false | null | [ | ] | , | { | } | = | value | array | elements | object | members | member | -------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+- [ 0] | | s 4 | s 6 | s 7 | s 8 | s 9 | s 10 | | | s 5 | | | 1 | 2 | | 3 | | | [ 1] | ACC | | | | | | | | | | | | | | | | | | [ 2] | r 6 | | | | | | | r 6 | r 6 | | r 6 | | | | | | | | [ 3] | r 7 | | | | | | | r 7 | r 7 | | r 7 | | | | | | | | [ 4] | r 1 | | | | | | | r 1 | r 1 | | r 1 | | | | | | | | [ 5] | | s 14 | | | | | | | | | s 13 | | | | | | 11 | 12 | [ 6] | r 2 | | | | | | | r 2 | r 2 | | r 2 | | | | | | | | [ 7] | r 3 | | | | | | | r 3 | r 3 | | r 3 | | | | | | | | [ 8] | r 4 | | | | | | | r 4 | r 4 | | r 4 | | | | | | | | [ 9] | r 5 | | | | | | | r 5 | r 5 | | r 5 | | | | | | | | [ 10] | | s 4 | s 6 | s 7 | s 8 | s 9 | s 10 | s 17 | | s 5 | | | 15 | 2 | 16 | 3 | | | [ 11] | | | | | | | | | | | s 18 | | | | | | | | [ 12] | | | | | | | | | s 19 | | r 14 | | | | | | | | [ 13] | r 12 | | | | | | | r 12 | r 12 | | r 12 | | | | | | | | [ 14] | | | | | | | | | | | | s 20 | | | | | | | [ 15] | | | | | | | | r 10 | s 21 | | | | | | | | | | [ 16] | | | | | | | | s 22 | | | | | | | | | | | [ 17] | r 8 | | | | | | | r 8 | r 8 | | r 8 | | | | | | | | [ 18] | r 13 | | | | | | | r 13 | r 13 | | r 13 | | | | | | | | [ 19] | | s 14 | | | | | | | | | | | | | | | 23 | 12 | [ 20] | | s 4 | s 6 | s 7 | s 8 | s 9 | s 10 | | | s 5 | | | 24 | 2 | | 3 | | | [ 21] | | s 4 | s 6 | s 7 | s 8 | s 9 | s 10 | | | s 5 | | | 15 | 2 | 25 | 3 | | | [ 22] | r 9 | | | | | | | r 9 | r 9 | | r 9 | | | | | | | | [ 23] | | | | | | | | | | | r 15 | | | | | | | | [ 24] | | | | | | | | | r 16 | | r 16 | | | | | | | | [ 25] | | | | | | | | r 11 | | | | | | | | | | | -------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+- value: str | num | true | false | null | array | object ; array: [ ] | [ elements ] ; elements: value | value , elements ; object: { } | { members } ; members: member | member , members ; member: str = value ; */ int main(void) { jn_alloc_t a; char* succ_json1 = "{\"key1\": \"this is test json\", \"key2\": [0, 1, 12, 0.123, 12.234, -293, -394.294E-23]}"; char* succ_json2 = "{\"gram\":[{\"head\":\"value\",\"body\":[\"str\"],\"op\":\"str\"},{\"head\":\"value\",\"body\":[\"num\"],\"op\":\"num\"},{\"head\":\"value\",\"body\":[\"true\"],\"op\":\"true\"},{\"head\":\"value\",\"body\":[\"false\"],\"op\":\"false\"},{\"head\":\"value\",\"body\":[\"null\"],\"op\":\"null\"},{\"head\":\"value\",\"body\":[\"array\"],\"op\":null},{\"head\":\"value\",\"body\":[\"object\"],\"op\":null},{\"head\":\"array\",\"body\":[\"[\",\"]\"],\"op\":\"]\"},{\"head\":\"array\",\"body\":[\"[\",\"elements\",\"]\"],\"op\":\"]\"},{\"head\":\"elements\",\"body\":[\"value\"],\"op\":null},{\"head\":\"elements\",\"body\":[\"value\",\",\",\"elements\"],\"op\":\",\"},{\"head\":\"object\",\"body\":[\"{\",\"}\"],\"op\":\"}\"},{\"head\":\"object\",\"body\":[\"{\",\"members\",\"}\"],\"op\":\"}\"},{\"head\":\"members\",\"body\":[\"member\"],\"op\":null},{\"head\":\"members\",\"body\":[\"member\",\",\",\"members\"],\"op\":\",\"},{\"head\":\"member\",\"body\":[\"str\",\"=\",\"value\"],\"op\":\"=\"}],\"non\":{\"value\":0,\"array\":1,\"elements\":2,\"object\":3,\"members\":4,\"member\":5},\"ter\":{\"str\":0,\"num\":1,\"true\":2,\"false\":3,\"null\":4,\"[\":5,\"]\":6,\",\":7,\"{\":8,\"}\":9,\"=\":10}}"; jn_json_t* out = NULL; printf("------------\n"); out = NULL; jn_init_alloc(&a); if(jn_parse(&a, succ_json1, &out)) jn_print_json(out); printf("------------\n"); out = NULL; jn_init_alloc(&a); if(jn_parse(&a, succ_json2, &out)) jn_print_json(out); return 0; }