SourceBrowser

auxsparsearray.c /size: 26 Kb last modification: 2025-02-21 11:03
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/*  
17    
18    We could do this: 
19
20        v // 4  v % 4  =>  v >> 2  v & 3
21
22    but let's just assume that the compiler optimzes it. 
23
24    We could also pack the catcodes in single bytes but then we need to work with 
25    
26        nn = odd(n) ? n + 1 : n; 
27
28    and things like:
29
30        >> 1 
31        & 0xF
32
33    and for the setter that is more work because we need to overwrite the existing byte that now has
34    two values and we also have the stack to deal with. We would save some memory but not that much. 
35
36*/
37
38/* 
39 
40    We don't need to test if a tree is defined because we assuem that this happens in the callers 
41    which saves some overhead here. (See older code for commented tests.)
42
43 */
44
45# include "luametatex.h"
46
47sparse_state_info lmt_sparse_state = {
48    .sparse_data = {
49        .minimum   = memory_data_unset,
50        .maximum   = memory_data_unset,
51        .size      = memory_data_unset,
52        .step      = memory_data_unset,
53        .allocated = 0,
54        .itemsize  = 1,
55        .top       = memory_data_unset,
56        .ptr       = memory_data_unset,
57        .initial   = memory_data_unset,
58        .offset    = 0,
59        .extra     = 0, 
60}
61};
62
63void *sa_malloc_array(int recordsize, int size)
64{
65    int allocated = recordsize * size;
66    lmt_sparse_state.sparse_data.allocated += allocated;
67    return lmt_memory_malloc((size_t) allocated);
68}
69
70void *sa_realloc_array(void *p, int recordsize, int size, int step)
71{
72    int deallocated = recordsize * size;
73    int allocated = recordsize * (size + step);
74    lmt_sparse_state.sparse_data.allocated += (allocated - deallocated);
75    return lmt_memory_realloc(p, (size_t) allocated);
76}
77
78void *sa_calloc_array(int recordsize, int size)
79{
80    int allocated = recordsize * size;
81    lmt_sparse_state.sparse_data.allocated += allocated;
82    return lmt_memory_calloc((size_t) size, recordsize);
83}
84
85void sa_wipe_array(void *head, int recordsize, int size)
86{
87    memset(head, 0, recordsize * ((size_t) size));
88}
89
90void *sa_free_array(void *p)
91{
92    lmt_memory_free(p);
93    return NULL;
94}
95
96/*tex
97
98    Once we have two variants allocated we can dump and undump a |LOWPART| array in one go. But
99    not yet. Currently the waste of one extra dummy int is cheaper than multiple functions. We 
100    anyway only save when needed (which saves 4 million stores on the mathincontext manual which 
101    is actually not noticeable in performance at all). 
102
103*/
104
105static void sa_aux_store_stack(const sa_tree head, int n, const sa_tree_item v1, const sa_tree_item v2, int gl)
106{
107    sa_stack_item st = {
108        .code    = n,
109        .value_1 = v1,
110        .value_2 = v2,
111        .level   = gl
112    };
113    if (! head->stack) {
114        head->stack = sa_malloc_array(sizeof(sa_stack_item), head->sa_stack_size);
115    } else if (((head->sa_stack_ptr) + 1) >= head->sa_stack_size) {
116        head->stack = sa_realloc_array(head->stack, sizeof(sa_stack_item), head->sa_stack_size, head->sa_stack_step);
117        head->sa_stack_size += head->sa_stack_step;
118     // printf("bumping %i stack to %i\n",head->identifier,head->sa_stack_size);
119    }
120    (head->sa_stack_ptr)++;
121 // printf("store %i @ %i: code %i, v1 %i, v2 %i, level %i\n",head->identifier,head->sa_stack_ptr,st.code,st.value_1.int_value,st.value_2.int_value,st.level);
122    head->stack[head->sa_stack_ptr] = st;
123}
124
125static void sa_aux_skip_in_stack(const sa_tree head, int n)
126{
127    if (head->stack) {
128        int p = head->sa_stack_ptr;
129        while (p > 0) {
130            if (head->stack[p].code == n && head->stack[p].level > 0) {
131                head->stack[p].level = -(head->stack[p].level);
132            }
133         // printf("skip %i: code %i, v1 %i, v2 %i, level %i\n",head->identifier,head->stack[p].code,head->stack[p].value_1.int_value,head->stack[p].value_2.int_value,head->stack[p].level);
134            p--;
135        }
136    }
137}
138
139// # define LMT_SA_L_PART_1(n) (LMT_SA_L_PART(n)/4)
140// # define LMT_SA_L_SLOT_1(n) (n%4)
141// # define LMT_SA_LOWPART_1   (LMT_SA_LOWPART/4)
142// 
143// # define LMT_SA_L_PART_2(n) (LMT_SA_L_PART(n)/2)
144// # define LMT_SA_L_SLOT_2(n) (n%2)
145// # define LMT_SA_LOWPART_2   (LMT_SA_LOWPART/2)
146// 
147// # define LMT_SA_L_PART_4(n) (LMT_SA_L_PART(n))
148// # define LMT_SA_L_SLOT_4(n) (n)
149// # define LMT_SA_LOWPART_4   (LMT_SA_LOWPART)
150
151int sa_get_item_0(const sa_tree head, int n)
152{
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            return get_nibble(head->tree[h][m][LMT_SA_L_PART(n)/8].uint_value, n);
158        }
159    }
160    return (int) get_nibble(head->dflt.uint_value,0);
161}
162
163int sa_get_item_1(const sa_tree head, int n)
164{
165    int h = LMT_SA_H_PART(n);
166    if (head->tree[h]) {
167        int m = LMT_SA_M_PART(n);
168        if (head->tree[h][m]) {
169            return head->tree[h][m][LMT_SA_L_PART(n)/4].uchar_value[n%4];
170        }
171    }
172    return (int) head->dflt.uchar_value[0];
173}
174
175int sa_get_item_2(const sa_tree head, int n)
176{
177    int h = LMT_SA_H_PART(n);
178    if (head->tree[h]) {
179        int m = LMT_SA_M_PART(n);
180        if (head->tree[h][m]) {
181            return head->tree[h][m][LMT_SA_L_PART(n)/2].ushort_value[n%2];
182        }
183    }
184    return (int) head->dflt.ushort_value[0];
185}
186
187int sa_get_item_4(const sa_tree head, int n, sa_tree_item *v)
188{
189    int h = LMT_SA_H_PART(n);
190    if (head->tree[h]) {
191        int m = LMT_SA_M_PART(n);
192        if (head->tree[h][m]) {
193            *v = head->tree[h][m][LMT_SA_L_PART(n)];
194            return 1;
195        }
196    }
197    *v = head->dflt;
198    return 0;
199}
200
201int sa_get_item_8(const sa_tree head, int n, sa_tree_item *v1, sa_tree_item *v2)
202{
203    int h = LMT_SA_H_PART(n);
204    if (head->tree[h]) {
205        int m = LMT_SA_M_PART(n);
206        if (head->tree[h][m]) {
207            int l = 2*LMT_SA_L_PART(n);
208            *v1 = head->tree[h][m][l];
209            *v2 = head->tree[h][m][l+1];
210            return 1;
211        }
212    }
213    *v1 = head->dflt;
214    *v2 = head->dflt;
215    return 0;
216}
217
218void sa_set_item_0(const sa_tree head, int n, int v, int gl)
219{
220    int h = LMT_SA_H_PART(n);
221    int m = LMT_SA_M_PART(n);
222    int l = LMT_SA_L_PART(n);
223    if (! head->tree[h]) {
224        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
225    }
226    if (! head->tree[h][m]) {
227        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART/8);
228        for (int i = 0; i < LMT_SA_LOWPART/8; i++) {
229            head->tree[h][m][i] = head->dflt;
230        }
231    }
232    if (gl <= 1) {
233        sa_aux_skip_in_stack(head, n);
234    } else if (get_nibble(head->tree[h][m][l/8].uint_value,n) != (unsigned int) v) {
235        sa_aux_store_stack(head, n, head->tree[h][m][l/8], (sa_tree_item) { 0 }, gl);
236    } else { 
237        /*tex There is no change so we don't need to save the old value. */
238    }
239    head->tree[h][m][l/8].uint_value = set_nibble(head->tree[h][m][l/8].uint_value, n, v);
240}
241
242void sa_set_item_1(const sa_tree head, int n, int v, int gl)
243{
244    int h = LMT_SA_H_PART(n);
245    int m = LMT_SA_M_PART(n);
246    int l = LMT_SA_L_PART(n);
247    if (! head->tree[h]) {
248        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
249    }
250    if (! head->tree[h][m]) {
251        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART/4);
252        for (int i = 0; i < LMT_SA_LOWPART/4; i++) {
253            head->tree[h][m][i] = head->dflt;
254        }
255    }
256    if (gl <= 1) {
257        sa_aux_skip_in_stack(head, n);
258    } else if (head->tree[h][m][l/4].uchar_value[n%4] != v) {
259        sa_aux_store_stack(head, n, head->tree[h][m][l/4], (sa_tree_item) { 0 }, gl);
260    } else { 
261        /*tex There is no change so we don't need to save the old value. */
262    }
263    head->tree[h][m][l/4].uchar_value[n%4] = (unsigned char) v;
264}
265
266void sa_set_item_2(const sa_tree head, int n, int v, int gl)
267{
268    int h = LMT_SA_H_PART(n);
269    int m = LMT_SA_M_PART(n);
270    int l = LMT_SA_L_PART(n);
271    if (! head->tree[h]) {
272        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
273    }
274    if (! head->tree[h][m]) {
275        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART/2);
276        for (int i = 0; i < LMT_SA_LOWPART/2; i++) {
277            head->tree[h][m][i] = head->dflt;
278        }
279    }
280    if (gl <= 1) {
281        sa_aux_skip_in_stack(head, n);
282    } else if (head->tree[h][m][l/2].ushort_value[n%2] != v) {
283        sa_aux_store_stack(head, n, head->tree[h][m][l/2], (sa_tree_item) { 0 }, gl);
284    } else { 
285        /*tex There is no change so we don't need to save the old value. */
286    }
287    head->tree[h][m][l/2].ushort_value[n%2] = (unsigned short) v;
288}
289
290void sa_set_item_4(const sa_tree head, int n, const sa_tree_item v, int gl)
291{
292    int h = LMT_SA_H_PART(n);
293    int m = LMT_SA_M_PART(n);
294    int l = LMT_SA_L_PART(n);
295    if (! head->tree[h]) {
296        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
297    }
298    if (! head->tree[h][m]) {
299        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART);
300        for (int i = 0; i < LMT_SA_LOWPART; i++) {
301            head->tree[h][m][i] = head->dflt;
302        }
303    }
304    if (gl <= 1) {
305        sa_aux_skip_in_stack(head, n);
306    } else if (head->tree[h][m][l].uint_value != v.uint_value) {
307        sa_aux_store_stack(head, n, head->tree[h][m][l], (sa_tree_item) { 0 }, gl);
308    } else { 
309        /*tex There is no change so we don't need to save the old value. */
310    }
311    head->tree[h][m][l] = v;
312}
313
314void sa_set_item_8(const sa_tree head, int n, const sa_tree_item v1, const sa_tree_item v2, int gl)
315{
316    int h = LMT_SA_H_PART(n);
317    int m = LMT_SA_M_PART(n);
318    int l = 2*LMT_SA_L_PART(n);
319    if (! head->tree[h]) {
320        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
321    }
322    if (! head->tree[h][m]) {
323        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), 2 * LMT_SA_LOWPART);
324        for (int i = 0; i < 2 * LMT_SA_LOWPART; i++) {
325            head->tree[h][m][i] = head->dflt;
326        }
327    }
328    if (gl <= 1) {
329        sa_aux_skip_in_stack(head, n);
330    } else if (head->tree[h][m][l].uint_value != v1.uint_value || head->tree[h][m][l+1].uint_value != v2.uint_value) {
331        sa_aux_store_stack(head, n, head->tree[h][m][l], head->tree[h][m][l+1], gl);
332    } else { 
333        /*tex There is no change so we don't need to save the old value. */
334   }
335    head->tree[h][m][l] = v1;
336    head->tree[h][m][l+1] = v2;
337}
338
339void sa_set_item_n(const sa_tree head, int n, int v, int gl)
340{
341    int h = LMT_SA_H_PART(n);
342    int m = LMT_SA_M_PART(n);
343    int l = LMT_SA_L_PART(n);
344    int d = head->bytes == 0 ? 8 : (head->bytes == 1 ? 4 : (head->bytes == 2 ? 2 : 1));
345    if (! head->tree[h]) {
346        head->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
347    }
348    if (! head->tree[h][m]) {
349        head->tree[h][m] = (sa_tree_item *) sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART/d);
350        for (int i = 0; i < LMT_SA_LOWPART/d; i++) {
351            head->tree[h][m][i] = head->dflt;
352        }
353    }
354    if (gl <= 1) {
355        sa_aux_skip_in_stack(head, n);
356    } else {
357        sa_aux_store_stack(head, n, head->tree[h][m][l/d], (sa_tree_item) { 0 }, gl);
358    }
359    switch (head->bytes) {
360        case 0:
361            head->tree[h][m][l/8].uint_value = set_nibble(head->tree[h][m][l/8].uint_value,n,v);
362            break;
363        case 1:
364            head->tree[h][m][l/4].uchar_value[n%4] = (unsigned char) (v < 0 ? 0 : (v > 0xFF ? 0xFF : v));
365            break;
366        case 2:
367            head->tree[h][m][l/2].ushort_value[n%2] = (unsigned short) (v < 0 ? 0 : (v > 0xFFFF ? 0xFFFF : v));
368            break;
369        case 4:
370            head->tree[h][m][l].int_value = v;
371            break;
372    }
373}
374
375int sa_get_item_n(const sa_tree head, int n)
376{
377    int h = LMT_SA_H_PART(n);
378    if (head->tree[h]) {
379        int m = LMT_SA_M_PART(n);
380        if (head->tree[h][m]) {
381            switch (head->bytes) {
382                case 0 : return (int) get_nibble(head->tree[h][m][LMT_SA_L_PART(n)/8].uint_value,n);
383                case 1 : return (int) head->tree[h][m][LMT_SA_L_PART(n)/4].uchar_value[n%4];
384                case 2 : return (int) head->tree[h][m][LMT_SA_L_PART(n)/2].ushort_value[n%2];
385                case 4 : return (int) head->tree[h][m][LMT_SA_L_PART(n)  ].int_value;
386            }
387        }
388    }
389    switch (head->bytes) {
390        case 0 : return (int) get_nibble(head->dflt.uint_value,0);
391        case 1 : return (int) head->dflt.uchar_value[0];
392        case 2 : return (int) head->dflt.ushort_value[0];
393        case 4 : return (int) head->dflt.int_value;
394        default: return 0;
395    }
396}
397
398void sa_clear_stack(const sa_tree a)
399{
400    if (a) {
401        a->stack = sa_free_array(a->stack);
402        a->sa_stack_ptr = 0;
403        a->sa_stack_size = a->sa_stack_step;
404    }
405}
406
407void sa_destroy_tree(sa_tree a)
408{
409    if (a) {
410        for (int h = 0; h < LMT_SA_HIGHPART; h++) {
411            if (a->tree[h]) {
412                for (int m = 0; m < LMT_SA_MIDPART; m++) {
413                    a->tree[h][m] = sa_free_array(a->tree[h][m]);
414                }
415                a->tree[h] = sa_free_array(a->tree[h]);
416            }
417        }
418        a->stack = sa_free_array(a->stack);
419        a = sa_free_array(a);
420    }
421}
422
423sa_tree sa_copy_tree(const sa_tree b)
424{
425    sa_tree a = (sa_tree) sa_malloc_array(sizeof(sa_tree_head), 1);
426    a->sa_stack_step = b->sa_stack_step;
427    a->sa_stack_size = b->sa_stack_size;
428    a->bytes = b->bytes;
429    a->identifier = b->identifier;
430    a->dflt = b->dflt;
431    a->stack = NULL;
432    a->sa_stack_ptr = 0;
433    sa_wipe_array(a->tree, sizeof(sa_tree_item *), LMT_SA_HIGHPART);
434    for (int h = 0; h < LMT_SA_HIGHPART; h++) {
435        if (b->tree[h]) {
436            int slide = LMT_SA_LOWPART;
437            switch (b->bytes) {
438                case 0: slide =   LMT_SA_LOWPART/8; break;
439                case 1: slide =   LMT_SA_LOWPART/4; break;
440                case 2: slide =   LMT_SA_LOWPART/2; break;
441                case 4: slide =   LMT_SA_LOWPART  ; break;
442                case 8: slide = 2*LMT_SA_LOWPART  ; break;
443            }
444            a->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(void *), LMT_SA_MIDPART);
445            for (int m = 0; m < LMT_SA_MIDPART; m++) {
446                if (b->tree[h][m]) {
447                    a->tree[h][m] = sa_malloc_array(sizeof(sa_tree_item), slide);
448                    memcpy(a->tree[h][m], b->tree[h][m], sizeof(sa_tree_item) * slide);
449                }
450            }
451        }
452    }
453    return a;
454}
455
456/*tex
457
458    The main reason to fill in the lowest entry branches here immediately is that most of the sparse
459    arrays have a bias toward \ASCII\ values. Allocating those here immediately improves the chance
460    of the structure |a->tree[0][0][x]| being close together in actual memory locations. We could
461    save less for type 0 stacks.
462
463*/
464
465sa_tree sa_new_tree(int identifier, int stacksize, int stackstep, int bytes, const sa_tree_item dflt)
466{
467    sa_tree_head *a = (sa_tree_head *) lmt_memory_malloc(sizeof(sa_tree_head));
468    a->dflt = dflt;
469    a->stack = NULL;
470    sa_wipe_array(a->tree, sizeof(sa_tree_item *), LMT_SA_HIGHPART);
471    a->tree[0] = (sa_tree_item **) sa_calloc_array(sizeof(sa_tree_item *), LMT_SA_MIDPART);
472    a->sa_stack_size = stacksize;
473    a->sa_stack_step = stackstep;
474    a->bytes = bytes;
475    a->identifier = identifier;
476    a->sa_stack_ptr = 0;
477    return (sa_tree) a;
478}
479
480void sa_restore_stack(const sa_tree head, int gl)
481{
482    if (head->stack) {
483        while (head->sa_stack_ptr > 0 && abs(head->stack[head->sa_stack_ptr].level) >= gl) {
484            sa_stack_item st = head->stack[head->sa_stack_ptr];
485            if (st.level > 0) {
486                int code = st.code;
487                switch (head->bytes) {
488                    case 0:
489                        {
490                            head->tree[LMT_SA_H_PART(code)][LMT_SA_M_PART(code)][LMT_SA_L_PART(code)/8].uint_value = st.value_1.uint_value;
491                        }
492                        break;
493                    case 1:
494                        {
495                            int c = code % 4;
496                            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];
497                        }
498                        break;
499                    case 2:
500                        {
501                            int c = code % 2;
502                            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];
503                        }
504                        break;
505                    case 4:
506                        {
507                            head->tree[LMT_SA_H_PART(code)][LMT_SA_M_PART(code)][LMT_SA_L_PART(code)] = st.value_1;
508                        }
509                        break;
510                    case 8:
511                        {
512                            int l = 2 * LMT_SA_L_PART(code);
513                            head->tree[LMT_SA_H_PART(code)][LMT_SA_M_PART(code)][l] = st.value_1;
514                            head->tree[LMT_SA_H_PART(code)][LMT_SA_M_PART(code)][l+1] = st.value_2;
515                        }
516                        break;
517
518                }
519            }
520            --head->sa_stack_ptr;
521        }
522    }
523}
524void sa_reinit_stack(const sa_tree head, int level)
525{
526    if (head->stack) {
527        /*tex Stack slot 0 is a dummy. */
528        for (int i = head->sa_stack_ptr; i > 0 ; i--) {
529            sa_stack_item st = head->stack[i];
530            if (st.level > 0) {
531             // printf("reinit %i: code %i, v1 %i, v2 %i, level %i\n",head->identifier,st.code,st.value_1.int_value,st.value_2.int_value,st.level);
532                switch (head->bytes) {
533                    case 0 : sa_set_item_0(head, st.code, st.value_1.uint_value, level); break;
534                    case 1 : sa_set_item_1(head, st.code, st.value_1.uchar_value[st.code%4], level); break;
535                    case 2 : sa_set_item_2(head, st.code, st.value_1.ushort_value[st.code%2], level); break;
536                    case 4 : sa_set_item_4(head, st.code, st.value_1, level); break;
537                }
538            }
539        }
540    }
541}
542
543void sa_show_stack(const sa_tree head)
544{
545    if (head->stack) {
546        /*tex Stack slot 0 is a dummy. */
547        tex_print_format("[codestack %i, size %i]\n", head->identifier, head->sa_stack_ptr - 1);
548        for (int i = 1; i <= head->sa_stack_ptr; i++) {
549            sa_stack_item st = head->stack[i];
550            int value = 0;
551            switch (head->bytes) {
552                case 0 : value = get_nibble(st.value_1.int_value,st.code); break;
553                case 1 : value = st.value_1.uchar_value[st.code%4]; break;
554                case 2 : value = st.value_1.ushort_value[st.code%2]; break;
555                case 4 : value = st.value_1.int_value; break;
556            }
557            tex_print_format("%l[%i: level %i, code %i, value %i]\n",i, st.level,st.code,value);
558        }
559        tex_print_format("%l[codestack %i bottom]\n", head->identifier);
560    }
561}
562
563void sa_dump_tree(dumpstream f, sa_tree a)
564{
565    unsigned char bytes = (unsigned char) a->bytes;
566    dump_int(f, a->identifier);
567    dump_int(f, a->sa_stack_step);
568    dump_int(f, a->dflt.int_value);
569    /*tex A marker: */
570    dump_via_uchar(f, 1);
571    dump_via_uchar(f, bytes);
572    for (int h = 0; h < LMT_SA_HIGHPART; h++) {
573        if (a->tree[h]) {
574            for (int m = 0; m < LMT_SA_MIDPART; m++) {
575                if (a->tree[h][m]) {
576                    /*tex
577                        It happens a lot that the value is the same as the index, for instance
578                        with case mappings.
579
580                        Using mode 3 for the case where all values are the default value saves
581                        In \CONTEXT\ some 128 * 5 dumps which is not worth the trouble but it
582                        is neat anyway.
583
584                        1 : values are kind of unique
585                        2 : for all values : value == self
586                        3 : for all values : value == default
587
588                        Actually, we could decide not to save at all in the third mode because
589                        unset equals default.
590                    */
591                    unsigned char mode = 1;
592                    if (bytes != 8) {
593                        /*tex Check for default values. */
594                        int slide = bytes == 0 ? LMT_SA_LOWPART/8 : (bytes == 1 ? LMT_SA_LOWPART/4 : (bytes == 2 ? LMT_SA_LOWPART/2 : LMT_SA_LOWPART));
595                        mode = 3;
596                        for (int l = 0; l < slide; l++) {
597                            if (a->tree[h][m][l].uint_value != a->dflt.uint_value) {
598                                mode = 1;
599                                break;
600                            }
601                        }
602                    }
603                    if (mode == 1 && bytes == 4) {
604                        /*tex Check for identity values. */
605                        unsigned int hm = h * LMT_SA_HIGHPART + m * LMT_SA_MIDPART * LMT_SA_LOWPART ;
606                        mode = 2;
607                        for (int l = 0; l < LMT_SA_LOWPART; l++) {
608                            if (a->tree[h][m][l].uint_value == hm) {
609                                hm++;
610                            } else {
611                                mode = 1;
612                                break;
613                            }
614                        }
615                    }
616                    dump_via_uchar(f, (unsigned char) h);
617                    dump_via_uchar(f, (unsigned char) m);
618                    dump_uchar(f, mode);
619                    if (mode == 1) {
620                        /*tex
621                            We have unique values. By avoiding this branch we save some 85 Kb
622                            on the \CONTEXT\ format. We could actually save this property in
623                            the tree but there is not that much to gain.
624                        */
625                        int slide = LMT_SA_LOWPART;
626                        switch (bytes) {
627                            case 0: slide =   LMT_SA_LOWPART/8; break;
628                            case 1: slide =   LMT_SA_LOWPART/4; break;
629                            case 2: slide =   LMT_SA_LOWPART/2; break;
630                            case 4: slide =   LMT_SA_LOWPART  ; break;
631                            case 8: slide = 2*LMT_SA_LOWPART  ; break;
632                        }
633                        dump_items(f, &a->tree[h][m][0], sizeof(sa_tree_item), slide);
634                    } else {
635                        /*tex We have a self value or defaults. */
636                    }
637                }
638            }
639        }
640    }
641    dump_via_uchar(f, 0xFF);
642    dump_via_uchar(f, 0xFF);
643    dump_via_uchar(f, 0xFF);
644}
645
646sa_tree sa_undump_tree(dumpstream f)
647{
648    unsigned char marker;
649    sa_tree a = (sa_tree) sa_malloc_array(sizeof(sa_tree_head), 1);
650    undump_int(f, a->identifier);
651    undump_int(f, a->sa_stack_step);
652    undump_int(f, a->dflt.int_value);
653    a->sa_stack_size = a->sa_stack_step;
654    a->stack = sa_calloc_array(sizeof(sa_stack_item), a->sa_stack_size);
655    a->sa_stack_ptr = 0;
656    sa_wipe_array(a->tree, sizeof(sa_tree_item **), LMT_SA_HIGHPART);
657    /*tex The marker: */
658    undump_uchar(f, marker);
659    if (marker != 0) {
660        unsigned char bytes;
661        undump_uchar(f, bytes);
662        a->bytes = bytes;
663        while (1) {
664            unsigned char h = 0; 
665            unsigned char m = 0; 
666            unsigned char mode;
667            undump_uchar(f, h);
668            undump_uchar(f, m);
669            undump_uchar(f, mode);
670            if (mode == 0xFF) {
671                if (h != 0xFF || m != 0xFF) {
672                    printf("\nfatal format error, mode %i, bytes %i, high %i, middle %i\n", mode, bytes, h, m);
673                    tex_fatal_undump_error("bad sa tree");
674                }
675                break;
676            } else { 
677                if (! a->tree[h]) {
678                    a->tree[h] = (sa_tree_item **) sa_calloc_array(sizeof(void *), LMT_SA_MIDPART);
679                }
680                switch (mode) {
681                    case 1:
682                        /*tex
683                            We have a unique values.
684                        */
685                        {
686                            int slide = LMT_SA_LOWPART;
687                            switch (bytes) {
688                                case 0: slide =   LMT_SA_LOWPART/8; break;
689                                case 1: slide =   LMT_SA_LOWPART/4; break;
690                                case 2: slide =   LMT_SA_LOWPART/2; break;
691                                case 4: slide =   LMT_SA_LOWPART  ; break;
692                                case 8: slide = 2*LMT_SA_LOWPART  ; break;
693                            }
694                            if (! a->tree[h][m]) {
695                                a->tree[h][m] = sa_calloc_array(sizeof(sa_tree_item), slide);
696                            }
697                            undump_items(f, &a->tree[h][m][0], sizeof(sa_tree_item), slide);
698                        }
699                        break;
700                    case 2:
701                        /*tex
702                            We have a self value. We only have this when we have integers. Other
703                            cases are math anyway, so not much to gain.
704                        */
705                        {
706                            if (bytes == 4) {
707                                int hm = h * 128 * LMT_SA_HIGHPART + m * LMT_SA_MIDPART;
708                                if (! a->tree[h][m]) {
709                                    a->tree[h][m] = sa_malloc_array(sizeof(sa_tree_item), LMT_SA_LOWPART);
710                                }
711                                for (int l = 0; l < LMT_SA_LOWPART; l++) {
712                                    a->tree[h][m][l].int_value = hm;
713                                    hm++;
714                                }
715                            } else {
716                                printf("\nfatal format error, mode %i, bytes %i\n", mode, bytes);
717                                tex_fatal_undump_error("bad sa tree");
718                            }
719                        }
720                        break;
721                    case 3:
722                        /*tex
723                            We have all default values. so no need to set them. In fact, we
724                            cannot even end up here.
725                        */
726                        break;
727                    default:
728                        /*tex
729                            We have no values set.
730                        */
731                        break;
732                }
733            }
734        }
735    }
736    return a;
737}
738
Source Browser ?
