1 /* Copyright (C) 2001-2019 Artifex Software, Inc.
2    All Rights Reserved.
3 
4    This software is provided AS-IS with no warranty, either express or
5    implied.
6 
7    This software is distributed under license and may not be copied,
8    modified or distributed except as expressly authorized under the terms
9    of the license contained in the file LICENSE in this distribution.
10 
11    Refer to licensing information at http://www.artifex.com or contact
12    Artifex Software, Inc.,  1305 Grant Avenue - Suite 200, Novato,
13    CA 94945, U.S.A., +1(415)492-9861, for further information.
14 */
15 
16 
17 /* Definitions for expandable stacks of refs */
18 /* Requires iref.h */
19 
20 #ifndef istack_INCLUDED
21 #  define istack_INCLUDED
22 
23 #include "isdata.h"
24 
25 /*
26  * The 3 principal Ghostscript stacks (operand, execution, and dictionary)
27  * are implemented as a linked list of blocks.
28  *
29  * Since all operators exit cleanly in case of stack under- or overflow,
30  * we handle all issues related to stack blocks in the top-level error
31  * recovery code in interp.c.  A few situations require special treatment:
32  * see ostack.h, estack.h, and dstack.h for details.
33  */
34 
35 /*
36  * Define the structure for a stack block.
37  * In order to simplify allocation, stack blocks are implemented as
38  * t_array objects, with the first few elements used for special purposes.
39  * The actual layout is as follows:
40  *              ref_stack_block structure
41  *              bottom guard if any (see below)
42  *              used elements of block
43  *              unused elements of block
44  *              top guard if any (see below)
45  * The `next' member of the next higher stack block includes all of this.
46  * The `used' member only includes the used elements of this block.
47  * Notes:
48  *      - In the top block, the size of the `used' member may not be correct.
49  *      - In all blocks but the top, we fill the unused elements with nulls.
50  */
51 typedef struct ref_stack_block_s {
52     ref next;			/* t_array, next lower block on stack */
53     ref used;			/* t_array, subinterval of this block */
54     /* Actual stack starts here */
55 } ref_stack_block;
56 
57 #define stack_block_refs (sizeof(ref_stack_block) / sizeof(ref))
58 
59 /* ------ Procedural interface ------ */
60 
61 /*
62  * Initialize a stack.  Note that this allocates the stack parameter
63  * structure iff params is not NULL.
64  */
65 int ref_stack_init(ref_stack_t *pstack, const ref *pblock_array,
66                    uint bot_guard, uint top_guard,
67                    const ref *pguard_value, gs_ref_memory_t *mem,
68                    ref_stack_params_t *params);
69 
70 /* Set whether a stack is allowed to expand.  The initial value is true. */
71 void ref_stack_allow_expansion(ref_stack_t *pstack, bool expand);
72 
73 /* Set the error codes for under- and overflow.  The initial values are -1. */
74 void ref_stack_set_error_codes(ref_stack_t *pstack, int underflow_error,
75                                int overflow_error);
76 
77 /*
78  * Set the maximum number of elements allowed on a stack.
79  * Note that the value is a long, not a uint or a ulong.
80  */
81 int ref_stack_set_max_count(ref_stack_t *pstack, long nmax);
82 
83 /*
84  * Set the margin between the limit and the top of the stack.
85  * Note that this may require allocating a block.
86  */
87 int ref_stack_set_margin(ref_stack_t *pstack, uint margin);
88 
89 /* Return the number of elements on a stack. */
90 uint ref_stack_count(const ref_stack_t *pstack);
91 
92 #define ref_stack_count_inline(pstk)\
93   ((pstk)->p + 1 - (pstk)->bot + (pstk)->extension_used)
94 
95 /* Return the maximum number of elements allowed on a stack. */
96 #define ref_stack_max_count(pstk) (uint)((pstk)->max_stack.value.intval)
97 
98 /*
99  * Return a pointer to a given element from the stack, counting from
100  * 0 as the top element.  If the index is out of range, return 0.
101  * Note that the index is a long, not a uint or a ulong.
102  */
103 ref *ref_stack_index(const ref_stack_t *pstack, long index);
104 
105 /*
106  * Count the number of elements down to and including the first mark.
107  * If no mark is found, return 0.
108  */
109 uint ref_stack_counttomark(const ref_stack_t *pstack);
110 
111 /*
112  * Do the store check for storing 'count' elements of a stack, starting
113  * 'skip' elements below the top, into an array.  Return 0 or gs_error_invalidaccess.
114  */
115 int ref_stack_store_check(const ref_stack_t *pstack, ref *parray,
116                           uint count, uint skip);
117 
118 /*
119  * Store the top 'count' elements of a stack, starting 'skip' elements below
120  * the top, into an array, with or without store/undo checking.  age=-1 for
121  * no check, 0 for old, 1 for new.  May return gs_error_rangecheck or
122  * gs_error_invalidaccess.
123  */
124 int ref_stack_store(const ref_stack_t *pstack, ref *parray, uint count,
125                     uint skip, int age, bool check,
126                     gs_dual_memory_t *idmem, client_name_t cname);
127 
128 int
129 ref_stack_array_sanitize(i_ctx_t *i_ctx_p, ref *sarr, ref *darr);
130 
131 /*
132  * Pop the top N elements off a stack.
133  * The number must not exceed the number of elements in use.
134  */
135 void ref_stack_pop(ref_stack_t *pstack, uint count);
136 
137 #define ref_stack_clear(pstk) ref_stack_pop(pstk, ref_stack_count(pstk))
138 #define ref_stack_pop_to(pstk, depth)\
139   ref_stack_pop(pstk, ref_stack_count(pstk) - (depth))
140 
141 /* Pop the top block off a stack.  May return underflow_error. */
142 int ref_stack_pop_block(ref_stack_t *pstack);
143 
144 /*
145  * Extend a stack to recover from an overflow condition.
146  * Uses the requested value to decide what to do.
147  * May return overflow_error or gs_error_VMerror.
148  */
149 int ref_stack_extend(ref_stack_t *pstack, uint request);
150 
151 /*
152  * Push N empty slots onto a stack.  These slots are not initialized:
153  * the caller must immediately fill them.  May return overflow_error
154  * (if max_stack would be exceeded, or the stack has no allocator)
155  * or gs_error_VMerror.
156  */
157 int ref_stack_push(ref_stack_t *pstack, uint count);
158 
159 /*
160  * Enumerate the blocks of a stack from top to bottom, as follows:
161 
162    ref_stack_enum_t rsenum;
163 
164    ref_stack_enum_begin(&rsenum, pstack);
165    do {
166       ... process rsenum.size refs starting at rsenum.ptr ...
167    } while (ref_stack_enum_next(&rsenum));
168 
169  */
170 typedef struct ref_stack_enum_s {
171     ref_stack_block *block;
172     ref *ptr;
173     uint size;
174 } ref_stack_enum_t;
175 void ref_stack_enum_begin(ref_stack_enum_t *prse, const ref_stack_t *pstack);
176 bool ref_stack_enum_next(ref_stack_enum_t *prse);
177 
178 /* Clean up a stack for garbage collection. */
179 void ref_stack_cleanup(ref_stack_t *pstack);
180 
181 /*
182  * Free the entire contents of a stack, including the bottom block.  The
183  * client must still free the ref_stack_t object.  Note that after calling
184  * ref_stack_release, the stack is no longer usable.
185  */
186 void ref_stack_release(ref_stack_t *pstack);
187 
188 /*
189  * Release a stack and then free the stack object.
190  */
191 void ref_stack_free(ref_stack_t *pstack);
192 
193 #endif /* istack_INCLUDED */
194