1 /* Copyright (C) 1989, 1995, 1997, 1998 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: idict.h,v 1.6 2004/08/04 19:36:12 stefan Exp $ */ 18 /* Interfaces for Ghostscript dictionary package */ 19 20 #ifndef idict_INCLUDED 21 # define idict_INCLUDED 22 23 #include "iddstack.h" 24 25 /* 26 * Contrary to our usual practice, we expose the (first-level) 27 * representation of a dictionary in the interface file, 28 * because it is so important that access checking go fast. 29 * The access attributes for the dictionary are stored in 30 * the values ref. 31 */ 32 struct dict_s { 33 ref values; /* t_array, values */ 34 ref keys; /* t_shortarray or t_array, keys */ 35 ref count; /* t_integer, count of occupied entries */ 36 /* (length) */ 37 ref maxlength; /* t_integer, maxlength as seen by client. */ 38 ref memory; /* foreign t_struct, the allocator that */ 39 /* created this dictionary */ 40 #define dict_memory(pdict) r_ptr(&(pdict)->memory, gs_ref_memory_t) 41 #define dict_mem(pdict) r_ptr(&(pdict)->memory, gs_memory_t) 42 }; 43 44 /* 45 * Define the maximum size of a dictionary. 46 */ 47 extern const uint dict_max_size; 48 49 /* 50 * Define whether dictionaries expand automatically when full. Note that 51 * if dict_auto_expand is true, dict_put, dict_copy, dict_resize, and 52 * dict_grow cannot return e_dictfull; however, they can return e_VMerror. 53 * (dict_find can return e_dictfull even if dict_auto_expand is true.) 54 */ 55 extern bool dict_auto_expand; 56 57 /* 58 * Create a dictionary. 59 */ 60 #ifndef gs_ref_memory_DEFINED 61 # define gs_ref_memory_DEFINED 62 typedef struct gs_ref_memory_s gs_ref_memory_t; 63 #endif 64 int dict_alloc(gs_ref_memory_t *, uint maxlength, ref * pdref); 65 66 #define dict_create(maxlen, pdref)\ 67 dict_alloc(iimemory, maxlen, pdref) 68 69 /* 70 * Return a pointer to a ref that holds the access attributes 71 * for a dictionary. 72 */ 73 #define dict_access_ref(pdref) (&(pdref)->value.pdict->values) 74 /* 75 * Check a dictionary for read or write permission. 76 * Note: this does NOT check the type of its operand! 77 */ 78 #define check_dict_read(dref) check_read(*dict_access_ref(&dref)) 79 #define check_dict_write(dref) check_write(*dict_access_ref(&dref)) 80 81 /* 82 * Look up a key in a dictionary. Store a pointer to the value slot 83 * where found, or to the (value) slot for inserting. 84 * The caller is responsible for checking that the dictionary is readable. 85 * Return 1 if found, 0 if not and there is room for a new entry, 86 * Failure returns: 87 * e_typecheck if the key is null; 88 * e_invalidaccess if the key is a string lacking read access; 89 * e_VMerror or e_limitcheck if the key is a string and the corresponding 90 * error occurs from attempting to convert it to a name; 91 * e_dictfull if the dictionary is full and the key is missing. 92 */ 93 int dict_find(const ref * pdref, const ref * key, ref ** ppvalue); 94 95 /* 96 * Look up a (constant) C string in a dictionary. 97 * Return 1 if found, <= 0 if not. 98 */ 99 int dict_find_string(const ref * pdref, const char *kstr, ref ** ppvalue); 100 101 /* 102 * Enter a key-value pair in a dictionary. 103 * The caller is responsible for checking that the dictionary is writable. 104 * Return 1 if this was a new entry, 0 if this replaced an existing entry. 105 * Failure returns are as for dict_find, except that e_dictfull doesn't 106 * occur if the dictionary is full but expandable, plus: 107 * e_invalidaccess for an attempt to store a younger key or value into 108 * an older dictionary, or as described just below; 109 * e_VMerror if a VMerror occurred while trying to expand the 110 * dictionary. 111 * Note that this procedure, and all procedures that may change the 112 * contents of a dictionary, take a pointer to a dictionary stack, 113 * so they can update the cached 'top' values and also update the cached 114 * value pointer in names. A NULL pointer for the dictionary stack is 115 * allowed, but in this case, if the dictionary is present on any dictionary 116 * stack, an e_invalidaccess error will occur if cached values need updating. 117 * THIS ERROR CHECK IS NOT IMPLEMENTED YET. 118 */ 119 int dict_put(ref * pdref, const ref * key, const ref * pvalue, 120 dict_stack_t *pds); 121 122 /* 123 * Enter a key-value pair where the key is a (constant) C string. 124 */ 125 int dict_put_string(ref * pdref, const char *kstr, const ref * pvalue, 126 dict_stack_t *pds); 127 128 /* 129 * Remove a key-value pair from a dictionary. 130 * Return 0 or e_undefined. 131 */ 132 int dict_undef(ref * pdref, const ref * key, dict_stack_t *pds); 133 134 /* 135 * Return the number of elements in a dictionary. 136 */ 137 uint dict_length(const ref * pdref); 138 139 /* 140 * Return the capacity of a dictionary. 141 */ 142 uint dict_maxlength(const ref * pdref); 143 144 /* 145 * Return the maximum index of a slot within a dictionary. 146 * Note that this may be greater than maxlength. 147 */ 148 uint dict_max_index(const ref * pdref); 149 150 /* 151 * Copy one dictionary into another. 152 * Return 0 or e_dictfull. 153 * If new_only is true, only copy entries whose keys 154 * aren't already present in the destination. 155 */ 156 int dict_copy_entries(const ref * dfrom, ref * dto, bool new_only, 157 dict_stack_t *pds); 158 159 #define dict_copy(dfrom, dto, pds) dict_copy_entries(dfrom, dto, false, pds) 160 #define dict_copy_new(dfrom, dto, pds) dict_copy_entries(dfrom, dto, true, pds) 161 162 /* 163 * Grow or shrink a dictionary. 164 * Return 0, e_dictfull, or e_VMerror. 165 */ 166 int dict_resize(ref * pdref, uint newmaxlength, dict_stack_t *pds); 167 168 /* 169 * Grow a dictionary in the same way as dict_put does. 170 * We export this for some special-case code in zop_def. 171 */ 172 int dict_grow(ref * pdref, dict_stack_t *pds); 173 174 /* 175 * Ensure that a dictionary uses the unpacked representation for keys. 176 * (This is of no interest to ordinary clients.) 177 */ 178 int dict_unpack(ref * pdref, dict_stack_t *pds); 179 180 /* 181 * Prepare to enumerate a dictionary. 182 * Return an integer suitable for the first call to dict_next. 183 */ 184 int dict_first(const ref * pdref); 185 186 /* 187 * Enumerate the next element of a dictionary. 188 * index is initially the result of a call on dict_first. 189 * Either store a key and value at eltp[0] and eltp[1] 190 * and return an updated index, or return -1 191 * to signal that there are no more elements in the dictionary. 192 */ 193 int dict_next(const ref * pdref, int index, ref * eltp); 194 195 /* 196 * Given a value pointer return by dict_find, return an index that 197 * identifies the entry within the dictionary. (This may, but need not, 198 * be the same as the index returned by dict_next.) 199 * The index is in the range [0..max_index-1]. 200 */ 201 int dict_value_index(const ref * pdref, const ref * pvalue); 202 203 /* 204 * Given an index in [0..max_index-1], as returned by dict_value_index, 205 * return the key and value, as returned by dict_next. 206 * If the index designates an unoccupied entry, return e_undefined. 207 */ 208 int dict_index_entry(const ref * pdref, int index, ref * eltp); 209 210 /* 211 * The following are some internal details that are used in both the 212 * implementation and some high-performance clients. 213 */ 214 215 /* On machines with reasonable amounts of memory, we round up dictionary 216 * sizes to the next power of 2 whenever possible, to allow us to use 217 * masking rather than division for computing the hash index. 218 * Unfortunately, if we required this, it would cut the maximum size of a 219 * dictionary in half. Therefore, on such machines, we distinguish 220 * "huge" dictionaries (dictionaries whose size is larger than the largest 221 * power of 2 less than dict_max_size) as a special case: 222 * 223 * - If the top dictionary on the stack is huge, we set the dtop 224 * parameters so that the fast inline lookup will always fail. 225 * 226 * - For general lookup, we use the slower hash_mod algorithm for 227 * huge dictionaries. 228 */ 229 #define dict_max_non_huge ((uint)(max_array_size / 2 + 1)) 230 231 /* Define the hashing function for names. */ 232 /* We don't have to scramble the index, because */ 233 /* indices are assigned in a scattered order (see name_ref in iname.c). */ 234 #define dict_name_index_hash(nidx) (nidx) 235 236 /* Hash an arbitrary non-negative or unsigned integer into a dictionary. */ 237 #define dict_hash_mod_rem(hash, size) ((hash) % (size)) 238 #define dict_hash_mod_mask(hash, size) ((hash) & ((size) - 1)) 239 #define dict_hash_mod_small(hash, size) dict_hash_mod_rem(hash, size) 240 #define dict_hash_mod_inline_small(hash, size) dict_hash_mod_rem(hash, size) 241 #define dict_hash_mod_large(hash, size)\ 242 (size > dict_max_non_huge ? dict_hash_mod_rem(hash, size) :\ 243 dict_hash_mod_mask(hash, size)) 244 #define dict_hash_mod_inline_large(hash, size) dict_hash_mod_mask(hash, size) 245 /* Round up the requested size of a dictionary. Return 0 if too big. */ 246 uint dict_round_size_small(uint rsize); 247 uint dict_round_size_large(uint rsize); 248 249 /* Choose the algorithms depending on the size of memory. */ 250 #if arch_small_memory 251 # define dict_hash_mod(h, s) dict_hash_mod_small(h, s) 252 # define dict_hash_mod_inline(h, s) dict_hash_mod_inline_small(h, s) 253 # define dict_round_size(s) dict_round_size_small(s) 254 #else 255 # ifdef DEBUG 256 # define dict_hash_mod(h, s)\ 257 (gs_debug_c('.') ? dict_hash_mod_small(h, s) :\ 258 dict_hash_mod_large(h, s)) 259 # define dict_hash_mod_inline(h, s)\ 260 (gs_debug_c('.') ? dict_hash_mod_inline_small(h, s) :\ 261 dict_hash_mod_inline_large(h, s)) 262 # define dict_round_size(s)\ 263 (gs_debug_c('.') ? dict_round_size_small(s) :\ 264 dict_round_size_large(s)) 265 # else 266 # define dict_hash_mod(h, s) dict_hash_mod_large(h, s) 267 # define dict_hash_mod_inline(h, s) dict_hash_mod_inline_large(h, s) 268 # define dict_round_size(s) dict_round_size_large(s) 269 # endif 270 #endif 271 272 #endif /* idict_INCLUDED */ 273