source/texk/web2c/luatexdir/utils/managed-sa.w

   1 % managed-sa.w
   2 %
   3 % Copyright 2006-2010 Taco Hoekwater <taco@@luatex.org>
   4 %
   5 % This file is part of LuaTeX.
   6 %
   7 % LuaTeX is free software; you can redistribute it and/or modify it under
   8 % the terms of the GNU General Public License as published by the Free
   9 % Software Foundation; either version 2 of the License, or (at your
  10 % option) any later version.
  11 %
  12 % LuaTeX is distributed in the hope that it will be useful, but WITHOUT
  13 % ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 % FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15 % License for more details.
  16 %
  17 % You should have received a copy of the GNU General Public License along
  18 % with LuaTeX; if not, see <http://www.gnu.org/licenses/>.
  19
  20 @* Sparse arrays with an embedded save stack.
  21
  22 These functions are called very often but a few days of experimenting proved that
  23 there is not much to gain (if at all) from using macros or optimizations like
  24 preallocating and fast access to the first 128 entries. In practice the overhead
  25 is mostly in accessing memory and not in (probably inlined) calls. So, we should
  26 accept fate and wait for faster memory. It's the price we pay for being unicode
  27 on the one hand and sparse on the other.
  28
  29 @ @c
  30
  31 #include "ptexlib.h"
  32
  33 @ @c
  34 static void store_sa_stack(sa_tree a, int n, sa_tree_item v, int gl)
  35 {
  36     sa_stack_item st;
  37     st.code = n;
  38     st.value = v;
  39     st.level = gl;
  40     if (a->stack == NULL) {
  41         a->stack = Mxmalloc_array(sa_stack_item, a->stack_size);
  42     } else if (((a->stack_ptr) + 1) >= a->stack_size) {
  43         a->stack_size += a->stack_step;
  44         a->stack = Mxrealloc_array(a->stack, sa_stack_item, a->stack_size);
  45     }
  46     (a->stack_ptr)++;
  47     a->stack[a->stack_ptr] = st;
  48 }
  49
  50 @ @c
  51 static void skip_in_stack(sa_tree a, int n)
  52 {
  53     int p = a->stack_ptr;
  54     if (a->stack == NULL)
  55         return;
  56     while (p > 0) {
  57         if (a->stack[p].code == n && a->stack[p].level > 0) {
  58             a->stack[p].level = -(a->stack[p].level);
  59         }
  60         p--;
  61     }
  62 }
  63
  64 @ @c
  65 sa_tree_item get_sa_item(const sa_tree head, const int n)
  66 {
  67     if (head->tree != NULL) {
  68         register int h = HIGHPART_PART(n);
  69         if (head->tree[h] != NULL) {
  70             register int m = MIDPART_PART(n);
  71             if (head->tree[h][m] != NULL) {
  72                 return head->tree[h][m][LOWPART_PART(n)];
  73             }
  74         }
  75     }
  76     return head->dflt;
  77 }
  78
  79 @ @c
  80 void set_sa_item(sa_tree head, int n, sa_tree_item v, int gl)
  81 {
  82     int h = HIGHPART_PART(n);
  83     int m = MIDPART_PART(n);
  84     int l = LOWPART_PART(n);
  85     if (head->tree == NULL) {
  86         head->tree = (sa_tree_item ***) Mxcalloc_array(sa_tree_item **, HIGHPART);
  87     }
  88     if (head->tree[h] == NULL) {
  89         head->tree[h] = (sa_tree_item **) Mxcalloc_array(sa_tree_item *, MIDPART);
  90     }
  91     if (head->tree[h][m] == NULL) {
  92         int i;
  93         head->tree[h][m] = (sa_tree_item *) Mxmalloc_array(sa_tree_item, LOWPART);
  94         for (i = 0; i < LOWPART; i++) {
  95             head->tree[h][m][i] = head->dflt;
  96         }
  97     }
  98     if (gl <= 1) {
  99         skip_in_stack(head, n);
 100     } else {
 101         store_sa_stack(head, n, head->tree[h][m][l], gl);
 102     }
 103     head->tree[h][m][l] = v;
 104 }
 105
 106 @ @c
 107 void rawset_sa_item(sa_tree head, int n, sa_tree_item v)
 108 {
 109     head->tree[HIGHPART_PART(n)][MIDPART_PART(n)][LOWPART_PART(n)] = v;
 110 }
 111
 112 @ @c
 113 void clear_sa_stack(sa_tree a)
 114 {
 115     xfree(a->stack);
 116     a->stack_ptr = 0;
 117     a->stack_size = a->stack_step;
 118 }
 119
 120 @ @c
 121 void destroy_sa_tree(sa_tree a)
 122 {
 123     if (a == NULL)
 124         return;
 125     if (a->tree != NULL) {
 126         int h, m;
 127         for (h = 0; h < HIGHPART; h++) {
 128             if (a->tree[h] != NULL) {
 129                 for (m = 0; m < MIDPART; m++) {
 130                     xfree(a->tree[h][m]);
 131                 }
 132                 xfree(a->tree[h]);
 133             }
 134         }
 135         xfree(a->tree);
 136     }
 137     xfree(a->stack);
 138     xfree(a);
 139 }
 140
 141 @ @c
 142 sa_tree copy_sa_tree(sa_tree b)
 143 {
 144     sa_tree a = (sa_tree) Mxmalloc_array(sa_tree_head, 1);
 145     a->stack_step = b->stack_step;
 146     a->stack_size = b->stack_size;
 147     a->stack_type = b->stack_type;
 148     a->dflt = b->dflt;
 149     a->stack = NULL;
 150     a->stack_ptr = 0;
 151     a->tree = NULL;
 152     if (b->tree != NULL) {
 153         int h, m;
 154         a->tree = (sa_tree_item ***) Mxcalloc_array(void *, HIGHPART);
 155         for (h = 0; h < HIGHPART; h++) {
 156             if (b->tree[h] != NULL) {
 157                 a->tree[h] = (sa_tree_item **) Mxcalloc_array(void *, MIDPART);
 158                 for (m = 0; m < MIDPART; m++) {
 159                     if (b->tree[h][m] != NULL) {
 160                         a->tree[h][m] = Mxmalloc_array(sa_tree_item, LOWPART);
 161                         memcpy(a->tree[h][m], b->tree[h][m],
 162                                sizeof(sa_tree_item) * LOWPART);
 163                     }
 164                 }
 165             }
 166         }
 167     }
 168     return a;
 169 }
 170
 171 @ The main reason to fill in the lowest entry branches here immediately
 172 is that most of the sparse arrays have a bias toward ASCII values.
 173
 174 Allocating those here immediately improves the chance of the structure
 175 |a->tree[0][0][x]| being close together in actual memory locations
 176
 177 @c
 178
 179 /* we could save less for type 0 stacks */
 180
 181 sa_tree new_sa_tree(int size, int type, sa_tree_item dflt)
 182 {
 183     sa_tree_head *a;
 184     a = (sa_tree_head *) xmalloc(sizeof(sa_tree_head));
 185     a->dflt = dflt;
 186     a->stack = NULL;
 187     a->tree = (sa_tree_item ***) Mxcalloc_array(sa_tree_item **, HIGHPART);
 188     a->tree[0] = (sa_tree_item **) Mxcalloc_array(sa_tree_item *, MIDPART);
 189     a->stack_size = size;
 190     a->stack_step = size;
 191     a->stack_type = type;
 192     a->stack_ptr = 0;
 193  /* printf("creating sa tree of type %d\n",type); */
 194     return (sa_tree) a;
 195 }
 196
 197 @ @c
 198 void restore_sa_stack(sa_tree head, int gl)
 199 {
 200     sa_stack_item st;
 201     if (head->stack == NULL)
 202         return;
 203     while (head->stack_ptr > 0 && abs(head->stack[head->stack_ptr].level) >= gl) {
 204         st = head->stack[head->stack_ptr];
 205         if (st.level > 0) {
 206             rawset_sa_item(head, st.code, st.value);
 207         }
 208         (head->stack_ptr)--;
 209     }
 210 }
 211
 212 @ @c
 213 void dump_sa_tree(sa_tree a, const char * name)
 214 {
 215     boolean f;
 216     int x, n;
 217     int h, m, l;
 218     dump_int(a->stack_step);
 219     x = a->dflt.int_value;
 220     dump_int(x);
 221     if (a->tree != NULL) {
 222         dump_int(1); /* marker */
 223         n = a->stack_type;
 224         dump_int(n);
 225      /* printf("dumping sa tree %s with type %d\n",name,n); */
 226         for (h = 0; h < HIGHPART; h++) {
 227             if (a->tree[h] != NULL) {
 228                 f = 1;
 229                 dump_qqqq(f);
 230                 for (m = 0; m < MIDPART; m++) {
 231                     if (a->tree[h][m] != NULL) {
 232                         f = 1;
 233                         dump_qqqq(f);
 234                         for (l = 0; l < LOWPART; l++) {
 235                             if (n == 2) {
 236                                 x = a->tree[h][m][l].dump_uint.value_1;
 237                                 dump_int(x);
 238                                 x = a->tree[h][m][l].dump_uint.value_2;
 239                                 dump_int(x);
 240                             } else {
 241                                 x = a->tree[h][m][l].uint_value;
 242                                 dump_int(x);
 243                             }
 244                         }
 245                     } else {
 246                         f = 0;
 247                         dump_qqqq(f);
 248                     }
 249                 }
 250             } else {
 251                 f = 0;
 252                 dump_qqqq(f);
 253             }
 254         }
 255     } else {
 256         dump_int(0); /* marker */
 257     }
 258 }
 259
 260 @ @c
 261 sa_tree undump_sa_tree(const char * name)
 262 {
 263     int x, n;
 264     int h, m, l;
 265     boolean f;
 266     sa_tree a = (sa_tree) Mxmalloc_array(sa_tree_head, 1);
 267     undump_int(x);
 268     a->stack_step = x;
 269     a->stack_size = x;
 270     undump_int(x);
 271     a->dflt.int_value = x;
 272     a->stack = Mxmalloc_array(sa_stack_item, a->stack_size);
 273     a->stack_ptr = 0;
 274     a->tree = NULL;
 275     undump_int(x); /* marker */
 276     if (x == 0)
 277         return a;
 278     a->tree = (sa_tree_item ***) Mxcalloc_array(void *, HIGHPART);
 279     undump_int(n);
 280     a->stack_type = n;
 281  /* printf("undumping sa tree %s with type %d\n",name,n); */
 282     for (h = 0; h < HIGHPART; h++) {
 283         undump_qqqq(f);
 284         if (f > 0) {
 285             a->tree[h] = (sa_tree_item **) Mxcalloc_array(void *, MIDPART);
 286             for (m = 0; m < MIDPART; m++) {
 287                 undump_qqqq(f);
 288                 if (f > 0) {
 289                     a->tree[h][m] = Mxmalloc_array(sa_tree_item, LOWPART);
 290                     for (l = 0; l < LOWPART; l++) {
 291                         if (n == 2) {
 292                             undump_int(x);
 293                             a->tree[h][m][l].dump_uint.value_1 = x;
 294                             undump_int(x);
 295                             a->tree[h][m][l].dump_uint.value_2 = x;
 296                         } else {
 297                             undump_int(x);
 298                             a->tree[h][m][l].uint_value = x;
 299                         }
 300                     }
 301                 }
 302             }
 303         }
 304     }
 305     return a;
 306 }