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