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