Source Browser ?

1/*
2    See license.txt in the root of this project.
3*/
4
5/*tex
6
7    Here we implement sparse arrays with an embedded save stack. These functions are called very
8    often but a few days of experimenting proved that there is not much to gain (if at all) from
9    using macros or optimizations like preallocating and fast access to the first 128 entries. In
10    practice the overhead is mostly in accessing memory and not in (probably inlined) calls. So, we
11    should accept fate and wait for faster memory. It's the price we pay for being unicode on the
12    one hand and sparse on the other.
13
14*/
15
16# include "luametatex.h"
17
18sparse_state_info lmt_sparse_state = {
19    .sparse_data = {
20        .minimum   = memory_data_unset,
21        .maximum   = memory_data_unset,
22        .size      = memory_data_unset,
23        .step      = memory_data_unset,
24        .allocated = 0,
25        .itemsize  = 1,
26        .top       = memory_data_unset,
27        .ptr       = memory_data_unset,
28        .initial   = memory_data_unset,
29        .offset    = 0,
30}
31};
32
33void *sa_malloc_array(int recordsize, int size)
34{
35    int allocated = recordsize * size;
36    lmt_sparse_state.sparse_data.allocated += allocated;
37    return lmt_memory_malloc((size_t) allocated);
38}
39
40void *sa_realloc_array(void *p, int recordsize, int size, int step)
41{
42    int deallocated = recordsize * size;
43    int allocated = recordsize * (size + step);
44    lmt_sparse_state.sparse_data.allocated += (allocated - deallocated);
45    return lmt_memory_realloc(p, (size_t) allocated);
46}
47
48void *sa_calloc_array(int recordsize, int size)
49{
50    int allocated = recordsize * size;
51    lmt_sparse_state.sparse_data.allocated += allocated;
52    return lmt_memory_calloc((size_t) size, recordsize);
53}
54
55void sa_wipe_array(void *head, int recordsize, int size)
56{
57    memset(head, 0, recordsize * ((size_t) size));
58}
59
60void *sa_free_array(void *p)
61{
62    lmt_memory_free(p);
63    return NULL;
64}
65
66/*tex
67
68    Once we have two variants allocated we can dump and undump a |LOWPART| array in one go. But
69    not yet. Currently the waste of one extra dummy int is cheaper than multiple functions.
70
71*/
72
73static void sa_aux_store_stack(const sa_tree a, int n, sa_tree_item v1, sa_tree_item v2, int gl)
74{
75    sa_stack_item st = {
76        .code    = n,
77        .value_1 = v1,
78        .value_2 = v2,
79        .level   = gl
80    };
81    if (! a->stack) {
82        a->stack = sa_malloc_array(sizeof(sa_stack_item), a->sa_stack_size);
83    } else if (((a->sa_stack_ptr) + 1) >= a->sa_stack_size) {
84        a->stack = sa_realloc_array(a->stack, sizeof(sa_stack_item), a->sa_stack_size, a->sa_stack_step);
85        a->sa_stack_size += a->sa_stack_step;
86    }
87    (a->sa_stack_ptr)++;
88    a->stack[a->sa_stack_ptr] = st;
89}
90
91static void sa_aux_skip_in_stack(const sa_tree a, int n)
92{
93    if (a->stack) {
94        int p = a->sa_stack_ptr;
95        while (p > 0) {
96            if (a->stack[p].code == n && a->stack[p].level > 0) {
97                a->stack[p].level = -(a->stack[p].level);
98            }
99            p--;
100        }
101    }
102}
103
104# if (1) 
105
106    int sa_get_item_1(const sa_tree head, int n)
107    {
108     // if (head->tree) {
109            int h = LMT_SA_H_PART(n);
110            if (head->tree[h]) {
111                int m = LMT_SA_M_PART(n);
112                if (head->tree[h][m]) {
113                    return head->tree[h][m][LMT_SA_L_PART(n)/4].uchar_value[n%4];
114                }
115            }
116     // }
117        return (int) head->dflt.uchar_value[0];
118    }
119
120    int sa_get_item_2(const sa_tree head, int n)
121    {
122     // if (head->tree) {
123            int h = LMT_SA_H_PART(n);
124            if (head->tree[h]) {
125                int m = LMT_SA_M_PART(n);
126                if (head->tree[h][m]) {
127                    return head->tree[h][m][LMT_SA_L_PART(n)/2].ushort_value[n%2];
128                }
129            }
130     // }
131        return (int) head->dflt.ushort_value[0];
132    }
133
134    int sa_get_item_4(const sa_tree head, int n, sa_tree_item *v)
135    {
136     // if (head->tree) {
137            int h = LMT_SA_H_PART(n);
138            if (head->tree[h]) {
139                int m = LMT_SA_M_PART(n);
140                if (head->tree[h][m]) {
141                    *v = head->tree[h][m][LMT_SA_L_PART(n)];
142                    return 1;
143                }
144            }
145     // }
146        *v = head->dflt;
147        return 0;
148    }
149
150    int sa_get_item_8(const sa_tree head, int n, sa_tree_item *v1, sa_tree_item *v2)
151    {
152     // if (head->tree) {
153            int h = LMT_SA_H_PART(n);
154            if (head->tree[h]) {
155                int m = LMT_SA_M_PART(n);
156                if (head->tree[h][m]) {
157                    int l = 2*LMT_SA_L_PART(n);
158                    *v1 = head->tree[h][m][l];
159                    *v2 = head->tree[h][m][l+1];
160                    return 1;
161                }
162            }
163     // }
164        *v1 = head->dflt;
165        *v2 = head->dflt;
166        return 0;
167    }
168
169# endif 
170
171void sa_set_item_1(const sa_tree head, int n, int v, int gl)
172{
173    int h = LMT_SA_H_PART(n);
174    int m = LMT_SA_M_PART(n);
175    int l = LMT_SA_L_PART(n);
176 // if (! head->tree) {
177 //     head->tree = (sa_tree_item ***) sa_calloc_array(sizeof(sa_tree_item **), LMT_SA_HIGHPART);
178 // }
179    if (! head->tree[h]) {
180        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
181    }
182    if (! head->tree[h][m]) {
183        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART/4);
184        for (int i = 0; i < LMT_SA_LOWPART/4; i++) {
185            head->tree[h][m][i] = head->dflt;
186        }
187    }
188    if (gl <= 1) {
189        sa_aux_skip_in_stack(head, n);
190    } else {
191        sa_aux_store_stack(head, n, head->tree[h][m][l/4], (sa_tree_item) { 0 }, gl);
192    }
193    head->tree[h][m][l/4].uchar_value[n%4] = (unsigned char) v;
194}
195
196void sa_set_item_2(const sa_tree head, int n, int v, int gl)
197{
198    int h = LMT_SA_H_PART(n);
199    int m = LMT_SA_M_PART(n);
200    int l = LMT_SA_L_PART(n);
201 // if (! head->tree) {
202 //     head->tree = (sa_tree_item ***) sa_calloc_array(sizeof(sa_tree_item **), LMT_SA_HIGHPART);
203 // }
204    if (! head->tree[h]) {
205        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
206    }
207    if (! head->tree[h][m]) {
208        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART/2);
209        for (int i = 0; i < LMT_SA_LOWPART/2; i++) {
210            head->tree[h][m][i] = head->dflt;
211        }
212    }
213    if (gl <= 1) {
214        sa_aux_skip_in_stack(head, n);
215    } else {
216        sa_aux_store_stack(head, n, head->tree[h][m][l/2], (sa_tree_item) { 0 }, gl);
217    }
218    head->tree[h][m][l/2].ushort_value[n%2] = (unsigned short) v;
219}
220
221void sa_set_item_4(const sa_tree head, int n, sa_tree_item v, int gl)
222{
223    int h = LMT_SA_H_PART(n);
224    int m = LMT_SA_M_PART(n);
225    int l = LMT_SA_L_PART(n);
226 // if (! head->tree) {
227 //     head->tree = (sa_tree_item ***) sa_calloc_array(sizeof(sa_tree_item **), LMT_SA_HIGHPART);
228 // }
229    if (! head->tree[h]) {
230        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
231    }
232    if (! head->tree[h][m]) {
233        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART);
234        for (int i = 0; i < LMT_SA_LOWPART; i++) {
235            head->tree[h][m][i] = head->dflt;
236        }
237    }
238    if (gl <= 1) {
239        sa_aux_skip_in_stack(head, n);
240    } else {
241        sa_aux_store_stack(head, n, head->tree[h][m][l], (sa_tree_item) { 0 }, gl);
242    }
243    head->tree[h][m][l] = v;
244}
245
246void sa_set_item_8(const sa_tree head, int n, sa_tree_item v1, sa_tree_item v2, int gl)
247{
248    int h = LMT_SA_H_PART(n);
249    int m = LMT_SA_M_PART(n);
250    int l = 2*LMT_SA_L_PART(n);
251 // if (! head->tree) {
252 //     head->tree = (sa_tree_item ***) sa_calloc_array(sizeof(sa_tree_item **), LMT_SA_HIGHPART);
253 // }
254    if (! head->tree[h]) {
255        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
256    }
257    if (! head->tree[h][m]) {
258        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), 2 * LMT_SA_LOWPART);
259        for (int i = 0; i < 2 * LMT_SA_LOWPART; i++) {
260            head->tree[h][m][i] = head->dflt;
261        }
262    }
263    if (gl <= 1) {
264        sa_aux_skip_in_stack(head, n);
265    } else {
266        sa_aux_store_stack(head, n, head->tree[h][m][l], head->tree[h][m][l+1], gl);
267    }
268    head->tree[h][m][l] = v1;
269    head->tree[h][m][l+1] = v2;
270}
271
272void sa_set_item_n(const sa_tree head, int n, int v, int gl)
273{
274    int h = LMT_SA_H_PART(n);
275    int m = LMT_SA_M_PART(n);
276    int l = LMT_SA_L_PART(n);
277    int d = head->bytes == 1 ? 4 : (head->bytes == 2 ? 2 : 1);
278 // if (! head->tree) {
279 //     head->tree = (sa_tree_item ***) sa_calloc_array(sizeof(sa_tree_item **), LMT_SA_HIGHPART);
280 // }
281    if (! head->tree[h]) {
282        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
283    }
284    if (! head->tree[h][m]) {
285        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART/d);
286        for (int i = 0; i < LMT_SA_LOWPART/d; i++) {
287            head->tree[h][m][i] = head->dflt;
288        }
289    }
290    if (gl <= 1) {
291        sa_aux_skip_in_stack(head, n);
292    } else {
293        sa_aux_store_stack(head, n, head->tree[h][m][l/d], (sa_tree_item) { 0 }, gl);
294    }
295    switch (head->bytes) {
296        case 1:
297            head->tree[h][m][l/4].uchar_value[n%4] = (unsigned char) (v < 0 ? 0 : (v > 0xFF ? 0xFF : v));
298            break;
299        case 2:
300            head->tree[h][m][l/2].ushort_value[n%2] = (unsigned char) (v < 0 ? 0 : (v > 0xFFFF ? 0xFFFF : v));
301            break;
302        case 4:
303            head->tree[h][m][l].int_value = v;
304            break;
305    }
306}
307
308int sa_get_item_n(const sa_tree head, int n)
309{
310 // if (head->tree) {
311        int h = LMT_SA_H_PART(n);
312        if (head->tree[h]) {
313            int m = LMT_SA_M_PART(n);
314            if (head->tree[h][m]) {
315                switch (head->bytes) {
316                    case 1 : return (int) head->tree[h][m][LMT_SA_L_PART(n)/4].uchar_value[n%4];
317                    case 2 : return (int) head->tree[h][m][LMT_SA_L_PART(n)/2].ushort_value[n%2];
318                    case 4 : return (int) head->tree[h][m][LMT_SA_L_PART(n)  ].int_value;
319                }
320            }
321        }
322 // }
323    switch (head->bytes) {
324        case 1 : return (int) head->dflt.uchar_value[n%4];
325        case 2 : return (int) head->dflt.ushort_value[n%2];
326        case 4 : return (int) head->dflt.int_value;
327        default: return 0;
328    }
329}
330
331void sa_clear_stack(const sa_tree a)
332{
333    if (a) {
334        a->stack = sa_free_array(a->stack);
335        a->sa_stack_ptr = 0;
336        a->sa_stack_size = a->sa_stack_step;
337    }
338}
339
340void sa_destroy_tree(sa_tree a)
341{
342    if (a) {
343  //   if (a->tree) {
344            for (int h = 0; h < LMT_SA_HIGHPART; h++) {
345                if (a->tree[h]) {
346                    for (int m = 0; m < LMT_SA_MIDPART; m++) {
347                        a->tree[h][m] = sa_free_array(a->tree[h][m]);
348                    }
349                    a->tree[h] = sa_free_array(a->tree[h]);
350                }
351            }
352  //        a->tree = sa_free_array(a->tree);
353  //    }
354        a->stack = sa_free_array(a->stack);
355        a = sa_free_array(a);
356    }
357}
358
359sa_tree sa_copy_tree(const sa_tree b)
360{
361    sa_tree a = (sa_tree) sa_malloc_array(sizeof(sa_tree_head), 1);
362    a->sa_stack_step = b->sa_stack_step;
363    a->sa_stack_size = b->sa_stack_size;
364    a->bytes = b->bytes;
365    a->dflt = b->dflt;
366    a->stack = NULL;
367    a->sa_stack_ptr = 0;
368    sa_wipe_array(a->tree, sizeof(sa_tree_item *), LMT_SA_HIGHPART);
369 // a->tree = NULL;
370 // if (b->tree) {
371 //     a->tree = (sa_tree_item ***) sa_calloc_array(sizeof(void *), LMT_SA_HIGHPART);
372        for (int h = 0; h < LMT_SA_HIGHPART; h++) {
373            if (b->tree[h]) {
374                int slide = LMT_SA_LOWPART;
375                switch (b->bytes) {
376                    case 1: slide =   LMT_SA_LOWPART/4; break;
377                    case 2: slide =   LMT_SA_LOWPART/2; break;
378                    case 4: slide =   LMT_SA_LOWPART  ; break;
379                    case 8: slide = 2*LMT_SA_LOWPART  ; break;
380                }
381                a->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(void *), LMT_SA_MIDPART);
382                for (int m = 0; m < LMT_SA_MIDPART; m++) {
383                    if (b->tree[h][m]) {
384                        a->tree[h][m] = sa_malloc_array(sizeof(sa_tree_item), slide);
385                        memcpy(a->tree[h][m], b->tree[h][m], sizeof(sa_tree_item) * slide);
386                    }
387                }
388            }
389        }
390 // }
391    return a;
392}
393
394/*tex
395
396    The main reason to fill in the lowest entry branches here immediately is that most of the sparse
397    arrays have a bias toward \ASCII\ values. Allocating those here immediately improves the chance
398    of the structure |a->tree[0][0][x]| being close together in actual memory locations. We could
399    save less for type 0 stacks.
400
401*/
402
403sa_tree sa_new_tree(int size, int bytes, sa_tree_item dflt)
404{
405    sa_tree_head *a = (sa_tree_head *) lmt_memory_malloc(sizeof(sa_tree_head));
406    a->dflt = dflt;
407    a->stack = NULL;
408 // a->tree = (sa_tree_item ***) sa_calloc_array(sizeof(sa_tree_item **), LMT_SA_HIGHPART);
409    sa_wipe_array(a->tree, sizeof(sa_tree_item *), LMT_SA_HIGHPART);
410    a->tree[0] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
411    a->sa_stack_size = size;
412    a->sa_stack_step = size;
413    a->bytes = bytes;
414    a->sa_stack_ptr = 0;
415    return (sa_tree) a;
416}
417
418void sa_restore_stack(const sa_tree head, int gl)
419{
420    if (head->stack) {
421        while (head->sa_stack_ptr > 0 && abs(head->stack[head->sa_stack_ptr].level) >= gl) {
422            sa_stack_item st = head->stack[head->sa_stack_ptr];
423            if (st.level > 0) {
424                int code = st.code;
425                switch (head->bytes) {
426                    case 1:
427                        {
428                            int c = code % 4;
429                            head->tree[LMT_SA_H_PART(code)][LMT_SA_M_PART(code)][LMT_SA_L_PART(code)/4].uchar_value[c] = st.value_1.uchar_value[c];
430                        }
431                        break;
432                    case 2:
433                        {
434                            int c = code % 2;
435                            head->tree[LMT_SA_H_PART(code)][LMT_SA_M_PART(code)][LMT_SA_L_PART(code)/2].ushort_value[c] = st.value_1.ushort_value[c];
436                        }
437                        break;
438                    case 4:
439                        {
440                            head->tree[LMT_SA_H_PART(code)][LMT_SA_M_PART(code)][LMT_SA_L_PART(code)] = st.value_1;
441                        }
442                        break;
443                    case 8:
444                        {
445                            int l = 2 * LMT_SA_L_PART(code);
446                            head->tree[LMT_SA_H_PART(code)][LMT_SA_M_PART(code)][l] = st.value_1;
447                            head->tree[LMT_SA_H_PART(code)][LMT_SA_M_PART(code)][l+1] = st.value_2;
448                        }
449                        break;
450
451                }
452            }
453            (head->sa_stack_ptr)--;
454        }
455    }
456}
457
458void sa_dump_tree(dumpstream f, sa_tree a)
459{
460    int bytes = a->bytes;
461    dump_int(f, a->sa_stack_step);
462    dump_int(f, a->dflt.int_value);
463 // if (a->tree) {
464 //     int bytes = a->bytes;
465        /*tex A marker: */
466        dump_via_int(f, 1);
467        dump_int(f, bytes);
468        for (int h = 0; h < LMT_SA_HIGHPART; h++) {
469            if (a->tree[h]) {
470                dump_via_int(f, 1);
471                for (int m = 0; m < LMT_SA_MIDPART; m++) {
472                    if (a->tree[h][m]) {
473                        /*tex
474                            It happens a lot that the value is the same as the index, for instance
475                            with case mappings.
476
477                            Using mode 3 for the case where all values are the default value saves
478                            In \CONTEXT\ some 128 * 5 dumps which is not worth the trouble but it
479                            is neat anyway.
480
481                            1 : values are kind of unique
482                            2 : for all values : value == self
483                            3 : for all values : value == default
484
485                            Actually, we could decide not to save at all in the third mode because
486                            unset equals default.
487                        */
488                        int mode = 1;
489                        if (bytes != 8) {
490                            /*tex Check for default values. */
491                            int slide = bytes == 1 ? LMT_SA_LOWPART/4 : (bytes == 2 ? LMT_SA_LOWPART/2 : LMT_SA_LOWPART);
492                            mode = 3;
493                            for (int l = 0; l < slide; l++) {
494                                if (a->tree[h][m][l].uint_value != a->dflt.uint_value) {
495                                    mode = 1;
496                                    break;
497                                }
498                            }
499                        }
500                        if (mode == 1 && bytes == 4) {
501                            /*tex Check for identity values. */
502                            unsigned int hm = h * LMT_SA_HIGHPART + m * LMT_SA_MIDPART * LMT_SA_LOWPART ;
503                            mode = 2;
504                            for (int l = 0; l < LMT_SA_LOWPART; l++) {
505                                if (a->tree[h][m][l].uint_value == hm) {
506                                    hm++;
507                                } else {
508                                    mode = 1;
509                                    break;
510                                }
511                            }
512                        }
513                        dump_int(f, mode);
514                        if (mode == 1) {
515                            /*tex
516                                We have unique values. By avoiding this branch we save some 85 Kb
517                                on the \CONTEXT\ format. We could actually save this property in
518                                the tree but there is not that much to gain.
519                            */
520                            int slide = LMT_SA_LOWPART;
521                            switch (bytes) {
522                                case 1: slide =   LMT_SA_LOWPART/4; break;
523                                case 2: slide =   LMT_SA_LOWPART/2; break;
524                                case 4: slide =   LMT_SA_LOWPART  ; break;
525                                case 8: slide = 2*LMT_SA_LOWPART  ; break;
526                            }
527                            dump_items(f, &a->tree[h][m][0], sizeof(sa_tree_item), slide);
528                        } else {
529                            /*tex We have a self value or defaults. */
530                        }
531                    } else {
532                        dump_via_int(f, 0);
533                    }
534                }
535            } else {
536                dump_via_int(f, 0);
537            }
538        }
539 // } else {
540 //     /*tex A marker: */
541 //     dump_via_int(f, 0);
542 // }
543}
544
545sa_tree sa_undump_tree(dumpstream f)
546{
547    int x;
548    sa_tree a = (sa_tree) sa_malloc_array(sizeof(sa_tree_head), 1);
549    undump_int(f,a->sa_stack_step);
550    undump_int(f,a->dflt.int_value);
551    a->sa_stack_size = a->sa_stack_step;
552    a->stack = sa_calloc_array(sizeof(sa_stack_item), a->sa_stack_size);
553    a->sa_stack_ptr = 0;
554 // a->tree = NULL;
555    sa_wipe_array(a->tree, sizeof(sa_tree_item *), LMT_SA_HIGHPART);
556    /*tex The marker: */
557    undump_int(f, x);
558    if (x != 0) {
559        int bytes, mode;
560  //    a->tree = (sa_tree_item ***) sa_calloc_array(sizeof(void *), LMT_SA_HIGHPART);
561        undump_int(f, bytes);
562        a->bytes = bytes;
563        for (int h = 0; h < LMT_SA_HIGHPART; h++) {
564            undump_int(f, mode); /* more a trigger */
565            if (mode > 0) {
566                a->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(void *), LMT_SA_MIDPART);
567                for (int m = 0; m < LMT_SA_MIDPART; m++) {
568                    undump_int(f, mode);
569                    switch (mode) {
570                        case 1:
571                            /*tex
572                                We have a unique values.
573                            */
574                            {
575                                int slide = LMT_SA_LOWPART;
576                                switch (bytes) {
577                                    case 1: slide =   LMT_SA_LOWPART/4; break;
578                                    case 2: slide =   LMT_SA_LOWPART/2; break;
579                                    case 4: slide =   LMT_SA_LOWPART  ; break;
580                                    case 8: slide = 2*LMT_SA_LOWPART  ; break;
581                                }
582                                a->tree[h][m] = sa_malloc_array(sizeof(sa_tree_item), slide);
583                                undump_items(f, &a->tree[h][m][0], sizeof(sa_tree_item), slide);
584                            }
585                            break;
586                        case 2:
587                            /*tex
588                                We have a self value. We only have this when we have integers. Other
589                                cases are math anyway, so not much to gain.
590                            */
591                            {
592                                if (bytes == 4) {
593                                    int hm = h * 128 * LMT_SA_HIGHPART + m * LMT_SA_MIDPART;
594                                    a->tree[h][m] = sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART);
595                                    for (int l = 0; l < LMT_SA_LOWPART; l++) {
596                                        a->tree[h][m][l].int_value = hm;
597                                        hm++;
598                                    }
599                                } else {
600                                    printf("\nfatal format error, mode %i, bytes %i\n", mode, bytes);
601                                }
602                            }
603                            break;
604                        case 3:
605                            /*tex
606                                We have all default values. so no need to set them. In fact, we
607                                cannot even end up here.
608                            */
609                            break;
610                        default:
611                            /*tex
612                                We have no values set.
613                            */
614                            break;
615                    }
616                }
617            }
618        }
619    }
620    return a;
621}
622