webmcp
changeset 126:bccaa05aada7
Implemented efficient length operator for sparse JSON arrays (that may contain null values)
author | jbe |
---|---|
date | Sun Jul 27 03:54:39 2014 +0200 (2014-07-27) |
parents | e3e5bf890aad |
children | 83aced09adc7 |
files | libraries/json/json.c |
line diff
1.1 --- a/libraries/json/json.c Sun Jul 27 01:51:45 2014 +0200 1.2 +++ b/libraries/json/json.c Sun Jul 27 03:54:39 2014 +0200 1.3 @@ -3,9 +3,8 @@ 1.4 #include <stdlib.h> 1.5 #include <string.h> 1.6 1.7 -#define JSON_UPVAL_METATABLE lua_upvalueindex(1) 1.8 -#define JSON_UPVAL_NULLS lua_upvalueindex(2) 1.9 -#define JSON_UPVAL_ARYLEN lua_upvalueindex(3) 1.10 +#define JSON_UPVAL_NULLS lua_upvalueindex(1) 1.11 +#define JSON_UPVAL_METATABLE lua_upvalueindex(2) 1.12 1.13 #define JSON_STATE_VALUE 0 1.14 #define JSON_STATE_OBJECT_KEY 1 1.15 @@ -76,10 +75,7 @@ 1.16 case ']': 1.17 if (mode != JSON_STATE_ARRAY_VALUE && mode != JSON_STATE_ARRAY_SEPARATOR) 1.18 goto json_import_syntax_error; 1.19 - lua_pushvalue(L, -2); // use array table as key 1.20 - lua_insert(L, -2); // use length of array as value 1.21 - lua_rawset(L, JSON_UPVAL_ARYLEN); // store length in ephemeron table 1.22 - // leaves array table on top of stack 1.23 + lua_pop(L, 1); // pop length information 1.24 json_import_close: 1.25 pos++; 1.26 lua_pop(L, 1); // pop table that stores set of NULL values 1.27 @@ -220,12 +216,53 @@ 1.28 } 1.29 1.30 static int json_arylen(lua_State *L) { 1.31 + int lower, middle; 1.32 + int upper = 1; 1.33 + // TODO: check input for valid array! 1.34 lua_settop(L, 1); 1.35 - lua_rawget(L, JSON_UPVAL_ARYLEN); 1.36 + lua_pushvalue(L, 1); 1.37 + lua_rawget(L, JSON_UPVAL_NULLS); 1.38 + if (lua_isnil(L, -1)) goto json_arylen_default; 1.39 + lua_pushnil(L); 1.40 + if (!lua_next(L, -2)) goto json_arylen_default; 1.41 + lua_pop(L, 2); 1.42 + while (1) { 1.43 + lua_rawgeti(L, 1, upper); 1.44 + if (lua_isnil(L, -1)) { 1.45 + // TODO: require metatable set? 1.46 + lua_pop(L, 1); 1.47 + lua_pushinteger(L, upper); 1.48 + lua_rawget(L, 2); 1.49 + } 1.50 + if (lua_isnil(L, -1)) break; 1.51 + lua_pop(L, 1); 1.52 + upper *= 2; 1.53 + // TODO: avoid integer overflow! 1.54 + } 1.55 + lua_pop(L, 1); 1.56 + lower = upper / 2; 1.57 + while (upper - lower > 1) { 1.58 + middle = (lower + upper) / 2; 1.59 + lua_rawgeti(L, 1, middle); 1.60 + if (lua_isnil(L, -1)) { 1.61 + // TODO: require metatable set? 1.62 + lua_pop(L, 1); 1.63 + lua_pushinteger(L, middle); 1.64 + lua_rawget(L, 2); 1.65 + } 1.66 + if (lua_isnil(L, -1)) upper = middle; 1.67 + else lower = middle; 1.68 + lua_pop(L, 1); 1.69 + } 1.70 + lua_pushinteger(L, lower); 1.71 + return 1; 1.72 +json_arylen_default: 1.73 + lua_pushinteger(L, lua_rawlen(L, 1)); 1.74 return 1; 1.75 } 1.76 1.77 static int json_isnull(lua_State *L) { 1.78 + // TODO: require metatable set? 1.79 lua_pushvalue(L, 1); 1.80 lua_rawget(L, JSON_UPVAL_NULLS); 1.81 if (lua_isnil(L, -1)) goto json_isnull_false; 1.82 @@ -244,20 +281,26 @@ 1.83 {NULL, NULL} 1.84 }; 1.85 1.86 +static const struct luaL_Reg json_metatable_functions[] = { 1.87 + {"__len", json_arylen}, 1.88 + {NULL, NULL} 1.89 +}; 1.90 + 1.91 int luaopen_json(lua_State *L) { 1.92 - lua_newtable(L); // library table 1.93 - lua_newtable(L); // metatable for JSON objects and JSON arrays 1.94 - lua_pushvalue(L, -1); 1.95 - lua_setfield(L, -3, "metatable"); 1.96 - lua_newtable(L); // ephemeron table to store a set of keys associated with JSON-null values 1.97 - lua_newtable(L); // ephemeron table to store the length of arrays (that may contain nil's) 1.98 - lua_newtable(L); // meta table for ephemeron table 1.99 + lua_settop(L, 0); 1.100 + lua_newtable(L); // 1: library table on stack position 1.101 + lua_newtable(L); // 2: ephemeron table to store a set of keys associated with JSON-null values 1.102 + lua_newtable(L); // 3: meta table for ephemeron table 1.103 lua_pushliteral(L, "__mode"); 1.104 lua_pushliteral(L, "k"); 1.105 - lua_rawset(L, -3); 1.106 - lua_pushvalue(L, -1); 1.107 - lua_setmetatable(L, -3); 1.108 - lua_setmetatable(L, -2); 1.109 - luaL_setfuncs(L, json_module_functions, 3); 1.110 + lua_rawset(L, 3); 1.111 + lua_setmetatable(L, 2); 1.112 + lua_newtable(L); // 3: metatable for JSON objects and JSON arrays 1.113 + lua_pushvalue(L, 3); 1.114 + lua_setfield(L, 1, "metatable"); 1.115 + lua_pushvalue(L, 2); 1.116 + lua_pushvalue(L, 3); 1.117 + luaL_setfuncs(L, json_metatable_functions, 2); 1.118 + luaL_setfuncs(L, json_module_functions, 2); 1.119 return 1; 1.120 }