Import Ghostscript 9.50ghostscript-9.50

Signed-off-by: Thomas Deutschmann <whissi@gentoo.org>

1 files changed, 300 insertions, 0 deletions

diff --git a/psi/dstack.h b/psi/dstack.h
new file mode 100644
index 00000000..ab99fead
--- /dev/null
+++ b/psi/dstack.h
@@ -0,0 +1,300 @@
+/* Copyright (C) 2001-2019 Artifex Software, Inc.
+   All Rights Reserved.
+
+   This software is provided AS-IS with no warranty, either express or
+   implied.
+
+   This software is distributed under license and may not be copied,
+   modified or distributed except as expressly authorized under the terms
+   of the license contained in the file LICENSE in this distribution.
+
+   Refer to licensing information at http://www.artifex.com or contact
+   Artifex Software, Inc.,  1305 Grant Avenue - Suite 200, Novato,
+   CA 94945, U.S.A., +1(415)492-9861, for further information.
+*/
+
+
+/* Definitions for the interpreter's dictionary stack */
+
+#ifndef dstack_INCLUDED
+#  define dstack_INCLUDED
+
+#include "idstack.h"
+#include "icstate.h"		/* for access to dict_stack */
+
+/* Define the dictionary stack instance for operators. */
+#define idict_stack (i_ctx_p->dict_stack)
+#define d_stack (idict_stack.stack)
+
+/* Define the interpreter-specific versions of the generic dstack API. */
+#define min_dstack_size (idict_stack.min_size)
+#define dstack_userdict_index (idict_stack.userdict_index)
+#define dsspace (idict_stack.def_space)
+#define dtop_can_store(pvalue) ((int)r_space(pvalue) <= dsspace)
+#define dtop_keys (idict_stack.top_keys)
+#define dtop_npairs (idict_stack.top_npairs)
+#define dtop_values (idict_stack.top_values)
+#define dict_set_top() dstack_set_top(&idict_stack);
+#define dict_is_permanent_on_dstack(pdict)\
+  dstack_dict_is_permanent(&idict_stack, pdict)
+#define dicts_gc_cleanup() dstack_gc_cleanup(&idict_stack)
+#define systemdict (&idict_stack.system_dict)
+
+/* Define the dictionary stack pointers. */
+#define dsbot (d_stack.bot)
+#define dsp (d_stack.p)
+#define dstop (d_stack.top)
+
+/* Macro to ensure enough room on the dictionary stack */
+#define check_dstack(n)\
+  if ( dstop - dsp < (n) )\
+    { int ds_code_ = ref_stack_extend(&d_stack, n);\
+      if ( ds_code_ < 0 ) return ds_code_;\
+    }
+
+/*
+ * The dictionary stack is implemented as a linked list of blocks;
+ * operators that access the entire d-stack must take this into account.
+ * These are:
+ *      countdictstack  dictstack
+ * In addition, name lookup requires searching the entire stack, not just
+ * the top block, and the underflow check for the dictionary stack
+ * (`end' operator) is not just a check for underflowing the top block.
+ */
+
+/* Name lookup */
+#define dict_find_name_by_index(nidx)\
+  dstack_find_name_by_index(&idict_stack, nidx)
+#define dict_find_name(pnref) dict_find_name_by_index(name_index(imemory, pnref))
+#define dict_find_name_by_index_inline(nidx, htemp)\
+  dstack_find_name_by_index_inline(&idict_stack, nidx, htemp)
+#define if_dict_find_name_by_index_top(nidx, htemp, pvslot)\
+  if_dstack_find_name_by_index_top(&idict_stack, nidx, htemp, pvslot)
+
+/*
+Notes on dictionary lookup performance
+======================================
+
+We mark heavily used operations with a * below; moderately heavily used
+operations with a +.
+
+The following operations look up keys on the dictionary stack:
+        *(interpreter name lookup)
+        load
+        where
+
+The following operations change the contents of dictionaries:
+        *def, +put
+        undef
+        restore
+        (grow)
+We implement store in PostScript, and copy as a series of puts.  Many
+other operators also do puts (e.g., ScaleMatrix in makefont,
+Implementation in makepattern, ...).  Note that put can do an implicit
+.setmaxlength (if it has to grow the dictionary).
+
+The following operations change the dictionary stack:
+        +begin, +end
+        +?(context switch)
+        readonly (on a dictionary that is on the stack)
+        noaccess (on a dictionary that is on the stack)
+We implement cleardictstack as a series of ends.
+
+Current design
+==============
+
+Each name N has a pointer N.V that has one of 3 states:
+        - This name has no definitions.
+        - This name has exactly one definition, in systemdict or userdict.
+        In this case, N.V points to the value slot.
+        - This name has some other status.
+
+We cache some pointers to the top dictionary on the stack if it is a
+readable dictionary with packed keys, which allows us to do fast,
+single-probe lookups in this dictionary.  We also cache a value that
+allows us to do a fast check for stores into the top dictionary
+(writability + space check).
+
+Improved design
+===============
+
+Data structures
+---------------
+
+With each dictionary stack (or equivalently with each context), we
+associate:
+
+    * A name lookup cache, C.  Each entry C[i] in the cache consists of:
+
+        A key, K (a name index).
+
+        A dictionary stack level (depth), L.  C[i] is valid iff the
+        current dictionary stack depth, |dstack|, is equal to L.
+        (L is always less than or equal to |dstack|.)
+
+        A value pointer, V, which points to some value slot of some
+        dictionary on the stack.
+
+    * A lookup cache restoration stack, R.  Each entry R[j] on this stack
+    consists of:
+
+        An index i in C.
+
+        The previous (K,D,V) of C[i].
+
+C needs to be large enough to satisfy the overwhelming majority of name
+lookups with only 1-3 probes.  In a single-context system, C can be large
+(perhaps 8K entries = 80K bytes, which is enough to accommodate every name
+in a typical run with no reprobes).  In a multiple-context system, one can
+choose a variety of different strategies for managing C, such as:
+
+        A single cache that is cleared on every context switch;
+
+        A small cache (e.g., .5K entries) for each context;
+
+        A cache that starts out small and grows adaptively if the hit rate
+        is too low.
+
+R needs to be able to grow dynamically; in the worst case, it may have |C|
+entries per level of the dictionary stack.  We assume that R will always be
+able to grow as needed (i.e., inability to allocate space for R is a
+VMerror, like inability to allocate space for the undo-save information for
+'save').
+
+With each entry E[j] on the dictionary stack, we associate:
+
+    * A value U that gives the depth of R at the time that E[j] was pushed
+    on the stack.  E[j].U = 0 for 0 <= j < the initial depth of the dictionary
+    stack (normally 3).
+
+With each dictionary D we associate:
+
+    * A counter S that gives the total number of occurrences of D on all
+    dictionary stacks.  If this counter overflows, it is pinned at its maximum
+    value.
+
+In order to be effective, D.S needs to be able to count up to a small
+multiple of the total number of contexts: 16 bits should be plenty.
+
+As at present, we also maintain a pair of pointers that bracket the value
+region of the top dictionary on the stack, for fast checking in def.  If the
+top dictionary is readonly or noaccess, the pointers designate an empty
+area.  We call this the "def region cache".
+
+Now we describe the implementation of each of the above operations.
+
+(name lookup)
+-------------
+
+To look up a name with index N, compute a hash index 0 <= i < |C|.  There
+are three cases:
+
+        1. C[i].K == N and C[i].L == |dstack|.  Nothing more is needed:
+        C[i].V points to the N's value.
+
+        2. C[i].K == N but C[i].L < |dstack|.  Look up N in the top |dstack|
+        - L entries on the dictionary stack; push i and C[i] onto R; set
+        C[i].V to point to the value if found, and in any case set C[i].L =
+        |dstack|.
+
+        3. C[i].K != N.  Reprobe some small number of times.
+
+If all reprobes fail, look up N on the (full) dictionary stack.  Pick an
+index i (one of the probed entries) in C to replace.  If C[i].L != |dstack|,
+push i and C[i] onto R.  Then replace C[i] with K = N, L = |dstack|, and V
+pointing to N's value.
+
+load
+----
+
+Proceed as for name lookup.  However, it might be worth not making the new
+cache entry in case 3, since names looked up by load will rarely be looked
+up again.
+
+where
+-----
+
+Just do a full lookup, ignoring C.
+
+def
+---
+
+As at present: start by doing one or two fast probes in the def region
+cache; if they succeed, just store the new value; otherwise, do a normal
+dictionary lookup and access check.  If a new dictionary entry is created
+and the key is a name, check all possible probe slots of the name in C; if
+the name is present, update its entry in C as for a lookup.  Then if D.S >
+1, scan as for 'grow' below.
+
+put
+---
+
+If the key is a name, the dictionary entry is new, and D.S != 0, scan as for
+'grow' below.
+
+undef
+-----
+
+If the key is a name and D.S != 0, scan as for 'grow' below.  It might be
+worth checking for D.S == 1 and D = the top dictionary on the stack as a
+special case, which only requires removing the name from C, similar to
+'def'.
+
+restore
+-------
+
+The undo-save machinery must be enhanced so that grow, def/put, and undef
+operations can be recognized as such.  TBD.
+
+(grow)
+------
+
+If D.S == 0, do nothing special.  Otherwise, scan C, R, and the dictionary
+stack (first for the current context, and then for other contexts if needed)
+until D.S occurrences of D have been processed.  (If D is in local VM, it is
+only necessary to scan contexts that share local VM with the current one; if
+D is in global VM, it is necessary to scan contexts that share global VM
+with the current one.)  Entries in C whose V pointed within D's old values
+array are updated; entries in R whose V pointed within the old values array
+are replaced with empty entries.
+
+begin
+-----
+
+After pushing the new dictionary, set dstack[|dstack| - 1].U = |R|.  Reset
+the def region cache.
+
+end
+---
+
+Before popping the top entry, for dstack[|dstack| - 1].U <= j < |R|, restore
+C[R[j].i] from R[j].(K,L,V), popping R.  Reset the def region cache.
+
+(context switch)
+----------------
+
+Reset the def region cache.
+
+readonly
+--------
+
+If the dictionary is the top one on the stack, reset the def region cache.
+
+noaccess
+--------
+
+If D.S != 0, scan as for 'grow' above, removing every C and R entry whose V
+points into D.  Also reset the def region cache if the dictionary is the top
+one on the stack.
+
+(garbage collection)
+--------------------
+
+The garbage collector must mark names referenced from C and R.  Dictionaries
+referenced from C and R are also referenced from the dictionary stack, so
+they do not need to be marked specially; however, pointers to those
+dictionaries' values arrays from C and R need to be relocated.
+
+ */
+
+#endif /* dstack_INCLUDED */