diff options
Diffstat (limited to 'Build/source/texk/web2c/luatexdir/utils/managed-sa.w')
-rw-r--r-- | Build/source/texk/web2c/luatexdir/utils/managed-sa.w | 284 |
1 files changed, 284 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/luatexdir/utils/managed-sa.w b/Build/source/texk/web2c/luatexdir/utils/managed-sa.w new file mode 100644 index 00000000000..c451a23c0c8 --- /dev/null +++ b/Build/source/texk/web2c/luatexdir/utils/managed-sa.w @@ -0,0 +1,284 @@ +% managed-sa.w +% +% Copyright 2006-2010 Taco Hoekwater <taco@@luatex.org> + +% This file is part of LuaTeX. + +% LuaTeX is free software; you can redistribute it and/or modify it under +% the terms of the GNU General Public License as published by the Free +% Software Foundation; either version 2 of the License, or (at your +% option) any later version. + +% LuaTeX is distributed in the hope that it will be useful, but WITHOUT +% ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +% FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public +% License for more details. + +% You should have received a copy of the GNU General Public License along +% with LuaTeX; if not, see <http://www.gnu.org/licenses/>. + +@* Sparse arrays with an embedded save stack. + +@ @c +#include "ptexlib.h" + +static const char _svn_version[] = + "$Id: managed-sa.w 3584 2010-04-02 17:45:55Z hhenkel $ " +"$URL: http://foundry.supelec.fr/svn/luatex/tags/beta-0.60.0/source/texk/web2c/luatexdir/utils/managed-sa.w $"; + +@ @c +static void store_sa_stack(sa_tree a, int n, sa_tree_item v, int gl) +{ + sa_stack_item st; + st.code = n; + st.value = v; + st.level = gl; + if (a->stack == NULL) { + a->stack = Mxmalloc_array(sa_stack_item, a->stack_size); + } else if (((a->stack_ptr) + 1) >= a->stack_size) { + a->stack_size += a->stack_step; + a->stack = Mxrealloc_array(a->stack, sa_stack_item, a->stack_size); + } + (a->stack_ptr)++; + a->stack[a->stack_ptr] = st; +} + +@ @c +static void skip_in_stack(sa_tree a, int n) +{ + int p = a->stack_ptr; + if (a->stack == NULL) + return; + while (p > 0) { + if (a->stack[p].code == n && a->stack[p].level > 0) { + a->stack[p].level = -(a->stack[p].level); + } + p--; + } +} + +@ @c +sa_tree_item get_sa_item(const sa_tree head, const int n) +{ + register int h; + register int m; + if (head->tree != NULL) { + h = HIGHPART_PART(n); + if (head->tree[h] != NULL) { + m = MIDPART_PART(n); + if (head->tree[h][m] != NULL) { + return head->tree[h][m][LOWPART_PART(n)]; + } + } + } + return head->dflt; +} + +@ @c +void set_sa_item(sa_tree head, int n, sa_tree_item v, int gl) +{ + int h, m, l; + int i; + h = HIGHPART_PART(n); + m = MIDPART_PART(n); + l = LOWPART_PART(n); + if (head->tree == NULL) { + head->tree = + (sa_tree_item ***) Mxcalloc_array(sa_tree_item **, HIGHPART); + } + if (head->tree[h] == NULL) { + head->tree[h] = + (sa_tree_item **) Mxcalloc_array(sa_tree_item *, MIDPART); + } + if (head->tree[h][m] == NULL) { + head->tree[h][m] = + (sa_tree_item *) Mxmalloc_array(sa_tree_item, LOWPART); + for (i = 0; i < LOWPART; i++) { + head->tree[h][m][i] = head->dflt; + } + } + if (gl <= 1) { + skip_in_stack(head, n); + } else { + store_sa_stack(head, n, head->tree[h][m][l], gl); + } + head->tree[h][m][l] = v; +} + +@ @c +void rawset_sa_item(sa_tree head, int n, sa_tree_item v) +{ + head->tree[HIGHPART_PART(n)][MIDPART_PART(n)][LOWPART_PART(n)] = v; +} + +@ @c +void clear_sa_stack(sa_tree a) +{ + xfree(a->stack); + a->stack_ptr = 0; + a->stack_size = a->stack_step; +} + +@ @c +void destroy_sa_tree(sa_tree a) +{ + int h, m; + if (a == NULL) + return; + if (a->tree != NULL) { + for (h = 0; h < HIGHPART; h++) { + if (a->tree[h] != NULL) { + for (m = 0; m < MIDPART; m++) { + xfree(a->tree[h][m]); + } + xfree(a->tree[h]); + } + } + xfree(a->tree); + } + xfree(a->stack); + xfree(a); +} + +@ @c +sa_tree copy_sa_tree(sa_tree b) +{ + int h, m; + sa_tree a = (sa_tree) Mxmalloc_array(sa_tree_head, 1); + a->stack_step = b->stack_step; + a->stack_size = b->stack_size; + a->dflt = b->dflt; + a->stack = NULL; + a->stack_ptr = 0; + a->tree = NULL; + if (b->tree != NULL) { + a->tree = (sa_tree_item ***) Mxcalloc_array(void *, HIGHPART); + for (h = 0; h < HIGHPART; h++) { + if (b->tree[h] != NULL) { + a->tree[h] = (sa_tree_item **) Mxcalloc_array(void *, MIDPART); + for (m = 0; m < MIDPART; m++) { + if (b->tree[h][m] != NULL) { + a->tree[h][m] = Mxmalloc_array(sa_tree_item, LOWPART); + memcpy(a->tree[h][m], b->tree[h][m], + sizeof(sa_tree_item) * LOWPART); + } + } + } + } + } + return a; +} + +@ The main reason to fill in the lowest entry branches here immediately +is that most of the sparse arrays have a bias toward ASCII values. + +Allocating those here immediately improves the chance of the structure +|a->tree[0][0][x]| being close together in actual memory locations + +@c +sa_tree new_sa_tree(int size, sa_tree_item dflt) +{ + sa_tree_head *a; + a = (sa_tree_head *) xmalloc(sizeof(sa_tree_head)); + a->dflt = dflt; + a->stack = NULL; + a->tree = (sa_tree_item ***) Mxcalloc_array(sa_tree_item **, HIGHPART); + a->tree[0] = (sa_tree_item **) Mxcalloc_array(sa_tree_item *, MIDPART); + a->stack_size = size; + a->stack_step = size; + a->stack_ptr = 0; + return (sa_tree) a; +} + +@ @c +void restore_sa_stack(sa_tree head, int gl) +{ + sa_stack_item st; + if (head->stack == NULL) + return; + while (head->stack_ptr > 0 && abs(head->stack[head->stack_ptr].level) >= gl) { + st = head->stack[head->stack_ptr]; + if (st.level > 0) { + rawset_sa_item(head, st.code, st.value); + } + (head->stack_ptr)--; + } +} + + +@ @c +void dump_sa_tree(sa_tree a) +{ + boolean f; + int x; + int h, m, l; + assert(a != NULL); + dump_int(a->stack_step); + x = (int) a->dflt; + dump_int(x); + if (a->tree != NULL) { + dump_int(1); + for (h = 0; h < HIGHPART; h++) { + if (a->tree[h] != NULL) { + f = 1; + dump_qqqq(f); + for (m = 0; m < MIDPART; m++) { + if (a->tree[h][m] != NULL) { + f = 1; + dump_qqqq(f); + for (l = 0; l < LOWPART; l++) { + x = (int) a->tree[h][m][l]; + dump_int(x); + } + } else { + f = 0; + dump_qqqq(f); + } + } + } else { + f = 0; + dump_qqqq(f); + } + } + } else { + dump_int(0); + } +} + +@ @c +sa_tree undump_sa_tree(void) +{ + int x; + int h, m, l; + boolean f; + sa_tree a = (sa_tree) Mxmalloc_array(sa_tree_head, 1); + undump_int(x); + a->stack_step = x; + a->stack_size = x; + undump_int(x); + a->dflt = (sa_tree_item) x; + a->stack = Mxmalloc_array(sa_stack_item, a->stack_size); + a->stack_ptr = 0; + a->tree = NULL; + undump_int(x); + if (x == 0) + return a; + a->tree = (sa_tree_item ***) Mxcalloc_array(void *, HIGHPART); + for (h = 0; h < HIGHPART; h++) { + undump_qqqq(f); + if (f > 0) { + a->tree[h] = (sa_tree_item **) Mxcalloc_array(void *, MIDPART); + for (m = 0; m < MIDPART; m++) { + undump_qqqq(f); + if (f > 0) { + a->tree[h][m] = Mxmalloc_array(sa_tree_item, LOWPART); + for (l = 0; l < LOWPART; l++) { + undump_int(x); + a->tree[h][m][l] = (unsigned int) x; + } + } + } + } + } + return a; +} |