summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/luatexdir/utils/managed-sa.w
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/web2c/luatexdir/utils/managed-sa.w')
-rw-r--r--Build/source/texk/web2c/luatexdir/utils/managed-sa.w284
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;
+}