diff options
Diffstat (limited to 'source/luametatex/source/luarest/lmtsparselib.c')
| -rw-r--r-- | source/luametatex/source/luarest/lmtsparselib.c | 305 |
1 files changed, 305 insertions, 0 deletions
diff --git a/source/luametatex/source/luarest/lmtsparselib.c b/source/luametatex/source/luarest/lmtsparselib.c new file mode 100644 index 000000000..a5b599cea --- /dev/null +++ b/source/luametatex/source/luarest/lmtsparselib.c @@ -0,0 +1,305 @@ +/* + See license.txt in the root of this project. +*/ + +# include "luametatex.h" + +/*tex + This module just provides as a more compact alternative for storing bitsets. I have no clue if + it ever will be used but we had this sparse tree mechanism so the overhead in terms of code is + neglectable. A possible application is bitmaps. Because we cross the c boundary it's about three + times slower when we get/set values than staying in \LUA\ although traversing from |min| to + |max| is performance wise the same. We could actually gain a bit when we add more helpers (like + |inc| and |dec| or so). + + So, for the moment I consider this a low impact, and thereby undocumented, fun project. +*/ + +# define SPARSE_STACK 8 +# define SPARSE_BYTES 4 + +typedef struct sa_tree_object { + sa_tree tree; + int min; + int max; +} sa_tree_object; + +static sa_tree_object *sparselib_aux_check_is_sa_object(lua_State *L, int n) +{ + sa_tree_object *o = (sa_tree_object *) lua_touserdata(L, n); + if (o && lua_getmetatable(L, n)) { + lua_get_metatablelua(sparse_instance); + if (! lua_rawequal(L, -1, -2)) { + o = NULL; + } + lua_pop(L, 2); + if (o) { + return o; + } + } + tex_normal_warning("sparse lib", "lua <sparse object> expected"); + return NULL; +} + +/* bytes=1|2|4, default=0|* */ + +static int sparselib_new(lua_State *L) +{ + int bytes = lmt_optinteger(L, 1, SPARSE_BYTES); + int defval = lmt_optinteger(L, 2, 0); + sa_tree_item item = { .int_value = defval }; + sa_tree_object *o = lua_newuserdatauv(L, sizeof(sa_tree_object), 0); + switch (bytes) { + case 1: + { + unsigned char d = (defval < 0 ? 0 : (defval > 0xFF ? 0xFF : defval)); + for (int i = 0; i <= 3; i++) { + item.uchar_value[i] = d ; + } + break; + } + case 2: + { + unsigned short d = (defval < 0 ? 0 : (defval > 0xFFFF ? 0xFFFF : defval)); + for (int i = 0; i <= 1; i++) { + item.ushort_value[i] = d ; + } + break; + } + case 4: + break; + default: + bytes = SPARSE_BYTES; + break; + } + o->tree = sa_new_tree(SPARSE_STACK, bytes, item); + o->min = -1; + o->max = -1; + luaL_setmetatable(L, SPARSE_METATABLE_INSTANCE); + return 1; +} + +static int sparselib_gc(lua_State *L) +{ + sa_tree_object *o = (sa_tree_object *) lua_touserdata(L, 1); + if (o) { + sa_destroy_tree(o->tree); + } + return 0; +} + +static int sparselib_tostring(lua_State *L) { + sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1); + if (o) { + lua_pushfstring(L, "<sa.object %p>", o->tree); + return 1; + } else { + return 0; + } +} + +/* sparse, index, value */ + +static int sparselib_set(lua_State *L) /* maybe also globalset as fast one */ +{ + sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1); + if (o) { + quarterword level; + int slot = lmt_check_for_level(L, 2, &level, cur_level); + int n = lmt_tointeger(L, slot++); + if (n >= 0) { + int v = lmt_tointeger(L, slot++); + if (o->min < 0) { + o->min = n; + o->max = n; + } else if (n < o->min) { + o->min = n; + } else if (n > o->max) { + o->max = n; + } + sa_set_item_n(o->tree, n, v, (int) level); + } + } + return 0; +} + +/* sparse, index */ + +static int sparselib_get(lua_State *L) +{ + sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1); + if (o) { + int n = lmt_tointeger(L, 2); + if (n >= 0) { + lua_pushinteger(L, sa_get_item_n(o->tree, n)); + return 1; + } + } + lua_pushnil(L); + return 1; +} + +static int sparselib_min(lua_State *L) +{ + sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1); + if (o) { + lua_pushinteger(L, o->min >= 0 ? o->min : 0); + } else { + lua_pushnil(L); + } + return 1; +} + +static int sparselib_max(lua_State *L) +{ + sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1); + if (o) { + lua_pushinteger(L, o->max >= 0 ? o->max : 0); + } else { + lua_pushnil(L); + } + return 1; +} + +static int sparselib_range(lua_State *L) +{ + sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1); + if (o) { + lua_pushinteger(L, o->min >= 0 ? o->min : 0); + lua_pushinteger(L, o->max >= 0 ? o->max : 0); + } else { + lua_pushnil(L); + lua_pushnil(L); + } + return 2; +} + +static int sparselib_aux_nil(lua_State *L) +{ + lua_pushnil(L); + return 1; +} + +static int sparselib_aux_next(lua_State *L) +{ + sa_tree_object *o = (sa_tree_object *) lua_touserdata(L, lua_upvalueindex(1)); + int ind = lmt_tointeger(L, lua_upvalueindex(2)); + if (ind <= o->max) { + lua_pushinteger(L, (lua_Integer) ind + 1); + lua_replace(L, lua_upvalueindex(2)); + lua_pushinteger(L, ind); + lua_pushinteger(L, sa_get_item_n(o->tree, ind)); + return 2; + } else { + return 0; + } +} + +static int sparselib_traverse(lua_State *L) +{ + sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1); + if (o && o->min >= 0) { + lua_settop(L, 1); + lua_pushinteger(L, o->min); + lua_pushcclosure(L, sparselib_aux_next, 2); + } else { + lua_pushcclosure(L, sparselib_aux_nil, 0); + } + return 1; +} + +static int sparselib_concat(lua_State *L) +{ + sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1); + if (o) { + sa_tree t = o->tree; + if (t->bytes == 1) { + luaL_Buffer buffer; + int min = lmt_optinteger(L, 2, o->min); + int max = lmt_optinteger(L, 3, o->max); + if (min < 0) { + min = 0; + } + if (max < min) { + max = min; + } + /* quick hack: we can add whole slices */ + luaL_buffinitsize(L, &buffer, (size_t) max - (size_t) min + 1); + for (int i = min; i <= max; i++) { + char c; + int h = LMT_SA_H_PART(i); + if (t->tree[h]) { + int m = LMT_SA_M_PART(i); + if (t->tree[h][m]) { + c = (char) t->tree[h][m][LMT_SA_L_PART(i)/4].uchar_value[i%4]; + } else { + c = (char) t->dflt.uchar_value[i%4]; + } + } else { + c = (char) t->dflt.uchar_value[i%4]; + } + luaL_addlstring(&buffer, &c, 1); + } + luaL_pushresult(&buffer); + return 1; + } + } + lua_pushnil(L); + return 1; +} + +static int sparselib_restore(lua_State *L) +{ + sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1); + if (o) { + /* restore_sa_stack(o->tree, cur_level); */ + sa_restore_stack(o->tree, cur_level+1); + } + return 0; +} + +static int sparselib_wipe(lua_State *L) +{ + sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1); + if (o) { + int bytes = o->tree->bytes; + sa_tree_item dflt = o->tree->dflt; + sa_destroy_tree(o->tree); + o->tree = sa_new_tree(SPARSE_STACK, bytes, dflt); + o->min = -1; + o->max = -1; + } + return 0; +} + +static const struct luaL_Reg sparselib_instance[] = { + { "__tostring", sparselib_tostring }, + { "__gc", sparselib_gc }, + { "__index", sparselib_get }, + { "__newindex", sparselib_set }, + { NULL, NULL }, +}; + +static const luaL_Reg sparselib_function_list[] = +{ + { "new", sparselib_new }, + { "set", sparselib_set }, + { "get", sparselib_get }, + { "min", sparselib_min }, + { "max", sparselib_max }, + { "range", sparselib_range }, + { "traverse", sparselib_traverse }, + { "concat", sparselib_concat }, + { "restore", sparselib_restore }, + { "wipe", sparselib_wipe }, + { NULL, NULL }, +}; + +int luaopen_sparse(lua_State *L) +{ + luaL_newmetatable(L, SPARSE_METATABLE_INSTANCE); + luaL_setfuncs(L, sparselib_instance, 0); + lua_newtable(L); + luaL_setfuncs(L, sparselib_function_list, 0); + return 1; +} |