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