1 /* Copyright (C) 2001-2012 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.,  7 Mt. Lassen Drive - Suite A-134, San Rafael,
13    CA  94903, 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 e_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 e_rangecheck or
122  * e_invalidaccess.
123  */
124 #ifndef gs_dual_memory_DEFINED
125 #  define gs_dual_memory_DEFINED
126 typedef struct gs_dual_memory_s gs_dual_memory_t;
127 #endif
128 int ref_stack_store(const ref_stack_t *pstack, ref *parray, uint count,
129                     uint skip, int age, bool check,
130                     gs_dual_memory_t *idmem, client_name_t cname);
131 
132 /*
133  * Pop the top N elements off a stack.
134  * The number must not exceed the number of elements in use.
135  */
136 void ref_stack_pop(ref_stack_t *pstack, uint count);
137 
138 #define ref_stack_clear(pstk) ref_stack_pop(pstk, ref_stack_count(pstk))
139 #define ref_stack_pop_to(pstk, depth)\
140   ref_stack_pop(pstk, ref_stack_count(pstk) - (depth))
141 
142 /* Pop the top block off a stack.  May return underflow_error. */
143 int ref_stack_pop_block(ref_stack_t *pstack);
144 
145 /*
146  * Extend a stack to recover from an overflow condition.
147  * Uses the requested value to decide what to do.
148  * May return overflow_error or e_VMerror.
149  */
150 int ref_stack_extend(ref_stack_t *pstack, uint request);
151 
152 /*
153  * Push N empty slots onto a stack.  These slots are not initialized:
154  * the caller must immediately fill them.  May return overflow_error
155  * (if max_stack would be exceeded, or the stack has no allocator)
156  * or e_VMerror.
157  */
158 int ref_stack_push(ref_stack_t *pstack, uint count);
159 
160 /*
161  * Enumerate the blocks of a stack from top to bottom, as follows:
162 
163    ref_stack_enum_t rsenum;
164 
165    ref_stack_enum_begin(&rsenum, pstack);
166    do {
167       ... process rsenum.size refs starting at rsenum.ptr ...
168    } while (ref_stack_enum_next(&rsenum));
169 
170  */
171 typedef struct ref_stack_enum_s {
172     ref_stack_block *block;
173     ref *ptr;
174     uint size;
175 } ref_stack_enum_t;
176 void ref_stack_enum_begin(ref_stack_enum_t *prse, const ref_stack_t *pstack);
177 bool ref_stack_enum_next(ref_stack_enum_t *prse);
178 
179 /* Clean up a stack for garbage collection. */
180 void ref_stack_cleanup(ref_stack_t *pstack);
181 
182 /*
183  * Free the entire contents of a stack, including the bottom block.  The
184  * client must still free the ref_stack_t object.  Note that after calling
185  * ref_stack_release, the stack is no longer usable.
186  */
187 void ref_stack_release(ref_stack_t *pstack);
188 
189 /*
190  * Release a stack and then free the stack object.
191  */
192 void ref_stack_free(ref_stack_t *pstack);
193 
194 #endif /* istack_INCLUDED */
195