1 /* Copyright (C) 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: idstack.c,v 1.7 2004/08/24 15:36:19 igor Exp $ */
18 /* Implementation of dictionary stacks */
19 #include "ghost.h"
20 #include "idict.h"
21 #include "idictdef.h"
22 #include "idstack.h"
23 #include "inamedef.h"
24 #include "iname.h"
25 #include "ipacked.h"
26 #include "iutil.h"
27 #include "ivmspace.h"
28
29 /* Debugging statistics */
30 #ifdef DEBUG
31 #include "idebug.h"
32 #define MAX_STATS_DEPTH 6
33 struct stats_dstack_s {
34 long lookups; /* total lookups */
35 long probes[2]; /* successful lookups on 1 or 2 probes */
36 long depth[MAX_STATS_DEPTH + 1]; /* stack depth of lookups requiring search */
37 } stats_dstack;
38 # define INCR(v) (++stats_dstack.v)
39 #else
40 # define INCR(v) DO_NOTHING
41 #endif
42
43 #ifdef DEBUG
44 /* Wrapper for dstack_find_name_by_index */
45 ref *real_dstack_find_name_by_index(dict_stack_t * pds, uint nidx);
46 ref *
dstack_find_name_by_index(dict_stack_t * pds,uint nidx)47 dstack_find_name_by_index(dict_stack_t * pds, uint nidx)
48 {
49 ref *pvalue = real_dstack_find_name_by_index(pds, nidx);
50 dict *pdict = pds->stack.p->value.pdict;
51
52 INCR(lookups);
53 if (dict_is_packed(pdict)) {
54 uint hash =
55 dict_hash_mod(dict_name_index_hash(nidx), npairs(pdict)) + 1;
56
57 if (pdict->keys.value.packed[hash] ==
58 pt_tag(pt_literal_name) + nidx
59 )
60 INCR(probes[0]);
61 else if (pdict->keys.value.packed[hash - 1] ==
62 pt_tag(pt_literal_name) + nidx
63 )
64 INCR(probes[1]);
65 }
66 if (gs_debug_c('d') && !(stats_dstack.lookups % 1000))
67 dlprintf3("[d]lookups=%ld probe1=%ld probe2=%ld\n",
68 stats_dstack.lookups, stats_dstack.probes[0],
69 stats_dstack.probes[1]);
70 return pvalue;
71 }
72 #define dstack_find_name_by_index real_dstack_find_name_by_index
73 #endif
74
75 /* Check whether a dictionary is one of the permanent ones on the d-stack. */
76 bool
dstack_dict_is_permanent(const dict_stack_t * pds,const ref * pdref)77 dstack_dict_is_permanent(const dict_stack_t * pds, const ref * pdref)
78 {
79 dict *pdict = pdref->value.pdict;
80 int i;
81
82 if (pds->stack.extension_size == 0) { /* Only one block of d-stack. */
83 for (i = 0; i < pds->min_size; ++i)
84 if (pds->stack.bot[i].value.pdict == pdict)
85 return true;
86 } else { /* More than one block of d-stack. */
87 uint count = ref_stack_count(&pds->stack);
88
89 for (i = count - pds->min_size; i < count; ++i)
90 if (ref_stack_index(&pds->stack, i)->value.pdict == pdict)
91 return true;
92 }
93 return false;
94 }
95
96 /*
97 * Look up a name on the dictionary stack.
98 * Return the pointer to the value if found, 0 if not.
99 */
100 ref *
dstack_find_name_by_index(dict_stack_t * pds,uint nidx)101 dstack_find_name_by_index(dict_stack_t * pds, uint nidx)
102 {
103 ds_ptr pdref = pds->stack.p;
104
105 /* Since we know the hash function is the identity function, */
106 /* there's no point in allocating a separate variable for it. */
107 #define hash dict_name_index_hash(nidx)
108 ref_packed kpack = packed_name_key(nidx);
109
110 do {
111 dict *pdict = pdref->value.pdict;
112 uint size = npairs(pdict);
113 const gs_memory_t *mem = dict_mem(pdict);
114 #ifdef DEBUG
115 if (gs_debug_c('D')) {
116 ref dnref;
117
118 name_index_ref(mem, nidx, &dnref);
119 dlputs("[D]lookup ");
120 debug_print_name(mem, &dnref);
121 dprintf3(" in 0x%lx(%u/%u)\n",
122 (ulong) pdict, dict_length(pdref),
123 dict_maxlength(pdref));
124 }
125 #endif
126 #define INCR_DEPTH(pdref)\
127 INCR(depth[min(MAX_STATS_DEPTH, pds->stack.p - pdref)])
128 if (dict_is_packed(pdict)) {
129 packed_search_1(INCR_DEPTH(pdref),
130 return packed_search_value_pointer,
131 DO_NOTHING, goto miss);
132 packed_search_2(INCR_DEPTH(pdref),
133 return packed_search_value_pointer,
134 DO_NOTHING, break);
135 miss:;
136 } else {
137 ref *kbot = pdict->keys.value.refs;
138 register ref *kp;
139 int wrap = 0;
140
141 /* Search the dictionary */
142 for (kp = kbot + dict_hash_mod(hash, size) + 2;;) {
143 --kp;
144 if (r_has_type(kp, t_name)) {
145 if (name_index(mem, kp) == nidx) {
146 INCR_DEPTH(pdref);
147 return pdict->values.value.refs + (kp - kbot);
148 }
149 } else if (r_has_type(kp, t_null)) { /* Empty, deleted, or wraparound. */
150 /* Figure out which. */
151 if (!r_has_attr(kp, a_executable))
152 break;
153 if (kp == kbot) { /* wrap */
154 if (wrap++)
155 break; /* 2 wraps */
156 kp += size + 1;
157 }
158 }
159 }
160 }
161 #undef INCR_DEPTH
162 }
163 while (pdref-- > pds->stack.bot);
164 /* The name isn't in the top dictionary block. */
165 /* If there are other blocks, search them now (more slowly). */
166 if (!pds->stack.extension_size) /* no more blocks */
167 return (ref *) 0;
168 { /* We could use the STACK_LOOP macros, but for now, */
169 /* we'll do things the simplest way. */
170 ref key;
171 uint i = pds->stack.p + 1 - pds->stack.bot;
172 uint size = ref_stack_count(&pds->stack);
173 ref *pvalue;
174
175 dict *pdict = pds->stack.p->value.pdict;
176 const gs_memory_t *mem = dict_mem(pdict);
177
178 name_index_ref(mem, nidx, &key);
179 for (; i < size; i++) {
180 if (dict_find(ref_stack_index(&pds->stack, i),
181 &key, &pvalue) > 0
182 ) {
183 INCR(depth[min(MAX_STATS_DEPTH, i)]);
184 return pvalue;
185 }
186 }
187 }
188 return (ref *) 0;
189 #undef hash
190 }
191
192 /* Set the cached values computed from the top entry on the dstack. */
193 /* See idstack.h for details. */
194 private const ref_packed no_packed_keys[2] =
195 {packed_key_deleted, packed_key_empty};
196 void
dstack_set_top(dict_stack_t * pds)197 dstack_set_top(dict_stack_t * pds)
198 {
199 ds_ptr dsp = pds->stack.p;
200 dict *pdict = dsp->value.pdict;
201
202 if_debug3('d', "[d]dsp = 0x%lx -> 0x%lx, key array type = %d\n",
203 (ulong) dsp, (ulong) pdict, r_type(&pdict->keys));
204 if (dict_is_packed(pdict) &&
205 r_has_attr(dict_access_ref(dsp), a_read)
206 ) {
207 pds->top_keys = pdict->keys.value.packed;
208 pds->top_npairs = npairs(pdict);
209 pds->top_values = pdict->values.value.refs;
210 } else {
211 pds->top_keys = no_packed_keys;
212 pds->top_npairs = 1;
213 }
214 if (!r_has_attr(dict_access_ref(dsp), a_write))
215 pds->def_space = -1;
216 else
217 pds->def_space = r_space(dsp);
218 }
219
220 /* After a garbage collection, scan the permanent dictionaries and */
221 /* update the cached value pointers in names. */
222 void
dstack_gc_cleanup(dict_stack_t * pds)223 dstack_gc_cleanup(dict_stack_t * pds)
224 {
225 uint count = ref_stack_count(&pds->stack);
226 uint dsi;
227
228 for (dsi = pds->min_size; dsi > 0; --dsi) {
229 const dict *pdict =
230 ref_stack_index(&pds->stack, count - dsi)->value.pdict;
231 uint size = nslots(pdict);
232 ref *pvalue = pdict->values.value.refs;
233 uint i;
234
235 for (i = 0; i < size; ++i, ++pvalue) {
236 ref key;
237 ref *old_pvalue;
238
239 array_get(dict_mem(pdict), &pdict->keys, (long)i, &key);
240 if (r_has_type(&key, t_name) &&
241 pv_valid(old_pvalue = key.value.pname->pvalue)
242 ) { /*
243 * The name only has a single definition,
244 * so it must be this one. Check to see if
245 * no relocation is actually needed; if so,
246 * we can skip the entire dictionary.
247 */
248 if (old_pvalue == pvalue) {
249 if_debug1('d', "[d]skipping dstack entry %d\n",
250 dsi - 1);
251 break;
252 }
253 /* Update the value pointer. */
254 key.value.pname->pvalue = pvalue;
255 }
256 }
257 }
258 }
259