SourceBrowser

lmtsparselib.c /size: 9755 b last modification: 2024-01-16 10:22
1/*
2    See license.txt in the root of this project.
3*/
4
5# include "luametatex.h"
6
7/*tex
8    This module just provides as a more compact alternative for storing bitsets. I have no clue if
9    it ever will be used but we had this sparse tree mechanism so the overhead in terms of code is
10    neglectable. A possible application is bitmaps. Because we cross the c boundary it's about three
11    times slower when we get/set values than staying in \LUA\ although traversing from |min| to
12    |max| is performance wise the same. We could actually gain a bit when we add more helpers (like
13    |inc| and |dec| or so).
14
15    So, for the moment I consider this a low impact, and thereby undocumented, fun project.
16*/
17
18# define SPARSE_STACK 8
19# define SPARSE_BYTES 4
20
21typedef struct sa_tree_object {
22    sa_tree tree;
23    int     min;
24    int     max;
25} sa_tree_object;
26
27static sa_tree_object *sparselib_aux_check_is_sa_object(lua_State *L, int n)
28{
29    sa_tree_object *o = (sa_tree_object *) lua_touserdata(L, n);
30    if (o && lua_getmetatable(L, n)) {
31        lua_get_metatablelua(sparse_instance);
32        if (! lua_rawequal(L, -1, -2)) {
33            o = NULL;
34        }
35        lua_pop(L, 2);
36        if (o) {
37            return o;
38        }
39    }
40    tex_normal_warning("sparse lib", "lua <sparse object> expected");
41    return NULL;
42}
43
44/* bytes=1|2|4, default=0|* */
45
46static int sparselib_new(lua_State *L)
47{
48    int bytes = lmt_optinteger(L, 1, SPARSE_BYTES);
49    int defval = lmt_optinteger(L, 2, 0);
50    sa_tree_item item = { .int_value = defval };
51    sa_tree_object *o = lua_newuserdatauv(L, sizeof(sa_tree_object), 0);
52    switch (bytes) {
53        case 1:
54            {
55                int d = defval < 0 ? 0 : (defval > 0xFF ? 0xFF : defval);
56                for (int i = 0; i <= 3; i++) {
57                    item.uchar_value[i] = (unsigned char) d;
58                }
59                break;
60            }
61        case 2:
62            {
63                int d =  defval < 0 ? 0 : (defval > 0xFFFF ? 0xFFFF : defval);
64                for (int i = 0; i <= 1; i++) {
65                    item.ushort_value[i] = (unsigned short) d;
66                }
67                break;
68            }
69        case 4:
70            break;
71        default:
72            bytes = SPARSE_BYTES;
73            break;
74    }
75    o->tree = sa_new_tree(SPARSE_STACK, bytes, item);
76    o->min = -1;
77    o->max = -1;
78    luaL_setmetatable(L, SPARSE_METATABLE_INSTANCE);
79    return 1;
80}
81
82static int sparselib_gc(lua_State *L)
83{
84    sa_tree_object *o = (sa_tree_object *) lua_touserdata(L, 1);
85    if (o) {
86       sa_destroy_tree(o->tree);
87    }
88    return 0;
89}
90
91static int sparselib_tostring(lua_State *L) {
92    sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1);
93    if (o) {
94        lua_pushfstring(L, "<sa.object %p>", o->tree);
95        return 1;
96    } else {
97        return 0;
98    }
99}
100
101/* sparse, index, value */
102
103static int sparselib_set(lua_State *L) /* maybe also globalset as fast one */
104{
105    sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1);
106    if (o) {
107        quarterword level;
108        int slot = lmt_check_for_level(L, 2, &level, cur_level);
109        int n = lmt_tointeger(L, slot++);
110        if (n >= 0) {
111            int v = lmt_optinteger(L, slot++, 1);
112            if (o->min < 0) {
113                o->min = n;
114                o->max = n;
115            } else if (n < o->min) {
116                o->min = n;
117            } else if (n > o->max) {
118                o->max = n;
119            }
120            sa_set_item_n(o->tree, n, v, (int) level);
121        }
122    }
123    return 0;
124}
125
126/* sparse, index */
127
128static int sparselib_get(lua_State *L)
129{
130    sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1);
131    if (o) {
132        int n = lmt_tointeger(L, 2);
133        if (n >= 0) {
134            lua_pushinteger(L, sa_get_item_n(o->tree, n));
135            return 1;
136        }
137    }
138    lua_pushnil(L);
139    return 1;
140}
141
142static int sparselib_min(lua_State *L)
143{
144    sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1);
145    if (o) {
146        lua_pushinteger(L, o->min >= 0 ? o->min : 0);
147    } else {
148        lua_pushnil(L);
149    }
150    return 1;
151}
152
153static int sparselib_max(lua_State *L)
154{
155    sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1);
156    if (o) {
157        lua_pushinteger(L, o->max >= 0 ? o->max : 0);
158    } else {
159        lua_pushnil(L);
160    }
161    return 1;
162}
163
164static int sparselib_range(lua_State *L)
165{
166    sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1);
167    if (o) {
168        lua_pushinteger(L, o->min >= 0 ? o->min : 0);
169        lua_pushinteger(L, o->max >= 0 ? o->max : 0);
170    } else {
171        lua_pushnil(L);
172        lua_pushnil(L);
173    }
174    return 2;
175}
176
177static int sparselib_aux_nil(lua_State *L)
178{
179    lua_pushnil(L);
180    return 1;
181}
182
183static int sparselib_aux_next(lua_State *L)
184{
185    sa_tree_object *o = (sa_tree_object *) lua_touserdata(L, lua_upvalueindex(1));
186    int ind = lmt_tointeger(L, lua_upvalueindex(2));
187    if (ind <= o->max) {
188        lua_pushinteger(L, (lua_Integer) ind + 1);
189        lua_replace(L, lua_upvalueindex(2));
190        lua_pushinteger(L, ind);
191        lua_pushinteger(L, sa_get_item_n(o->tree, ind));
192        return 2;
193    } else {
194        return 0;
195    }
196}
197
198static int sparselib_traverse(lua_State *L)
199{
200    sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1);
201    if (o && o->min >= 0) {
202        lua_settop(L, 1);
203        lua_pushinteger(L, o->min);
204        lua_pushcclosure(L, sparselib_aux_next, 2);
205    } else {
206        lua_pushcclosure(L, sparselib_aux_nil, 0);
207    }
208    return 1;
209}
210
211typedef enum concat_options { 
212    concat_as_byte = 0,
213    concat_as_lsb  = 1,
214    concat_as_msb  = 2,
215} concat_options;
216
217inline static char sparselib_aux_concat(sa_tree t, int i)
218{
219    int h = LMT_SA_H_PART(i);
220    if (t->tree[h]) {
221        int m = LMT_SA_M_PART(i);
222        if (t->tree[h][m]) {
223            return (char) t->tree[h][m][LMT_SA_L_PART(i)/4].uchar_value[i%4];
224        } else {
225            return (char) t->dflt.uchar_value[i%4];
226        }
227    } else {
228        return (char) t->dflt.uchar_value[i%4];
229    }
230}
231
232static int sparselib_concat(lua_State *L)
233{
234    sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1);
235    if (o) {
236        sa_tree t = o->tree;
237        if (t->bytes == 1) {
238            /* quick hack: we can add whole slices */
239            luaL_Buffer buffer;
240            int min = lmt_optinteger(L, 2, o->min);
241            int max = lmt_optinteger(L, 3, o->max);
242            int how = lmt_optinteger(L, 4, concat_as_byte);
243            int siz = 0;
244            if (min < 0) {
245                min = 0;
246            }
247            if (max < min) {
248                max = min;
249            }
250            siz = (size_t) max - (size_t) min + 1;
251            luaL_buffinitsize(L, &buffer, siz);
252            switch (how) { 
253                case concat_as_lsb:
254                case concat_as_msb:
255                    {
256                        int n = 0;
257                        char b = 0;
258                        luaL_buffinitsize(L, &buffer, (siz / 8) + 1);
259                        for (int i = min; i <= max; i++) {
260                            char c = sparselib_aux_concat(t, i);
261                            if (c) { 
262                                b |= how == concat_as_lsb ? (1 << n) : (1 << (7 - n));
263                            }
264                            if (++n == 8) { 
265                                luaL_addlstring(&buffer, &b, 1);
266                                n = 0;
267                            }
268                        }
269                        if (n) { 
270                            luaL_addlstring(&buffer, &b, 1);
271                        }
272                    }
273                    break;
274                default:
275                    {
276                        luaL_buffinitsize(L, &buffer, siz);
277                        for (int i = min; i <= max; i++) {
278                            char c = sparselib_aux_concat(t, i);
279                            luaL_addlstring(&buffer, &c, 1);
280                        }
281                    }
282                    break;
283            }
284            luaL_pushresult(&buffer);
285            return 1;
286        }
287    }
288    lua_pushnil(L);
289    return 1;
290}
291
292static int sparselib_restore(lua_State *L)
293{
294    sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1);
295    if (o) {
296     /* restore_sa_stack(o->tree, cur_level); */
297        sa_restore_stack(o->tree, cur_level+1);
298    }
299    return 0;
300}
301
302static int sparselib_wipe(lua_State *L)
303{
304    sa_tree_object *o = sparselib_aux_check_is_sa_object(L, 1);
305    if (o) {
306        int bytes = o->tree->bytes;
307        sa_tree_item dflt = o->tree->dflt;
308        sa_destroy_tree(o->tree);
309        o->tree = sa_new_tree(SPARSE_STACK, bytes, dflt);
310        o->min = -1;
311        o->max = -1;
312    }
313    return 0;
314}
315
316static const struct luaL_Reg sparselib_instance[] = {
317    { "__tostring", sparselib_tostring },
318    { "__gc",       sparselib_gc       },
319    { "__index",    sparselib_get      },
320    { "__newindex", sparselib_set      },
321    { NULL,         NULL               },
322};
323
324static const luaL_Reg sparselib_function_list[] =
325{
326    { "new",      sparselib_new      },
327    { "set",      sparselib_set      },
328    { "get",      sparselib_get      },
329    { "min",      sparselib_min      },
330    { "max",      sparselib_max      },
331    { "range",    sparselib_range    },
332    { "traverse", sparselib_traverse },
333    { "concat",   sparselib_concat   },
334    { "restore",  sparselib_restore  },
335    { "wipe",     sparselib_wipe     },
336    { NULL,       NULL               },
337};
338
339int luaopen_sparse(lua_State *L)
340{
341    luaL_newmetatable(L, SPARSE_METATABLE_INSTANCE);
342    luaL_setfuncs(L, sparselib_instance, 0);
343    lua_newtable(L);
344    luaL_setfuncs(L, sparselib_function_list, 0);
345    return 1;
346}
347
Source Browser ?
