SourceBrowser

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