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: idict.c 9545 2009-03-11 13:46:33Z alexcher $ */
15 /* Dictionary implementation */
16 #include "math_.h" /* for frexp */
17 #include "string_.h" /* for strlen */
18 #include "ghost.h"
19 #include "gxalloc.h" /* for accessing masks */
20 #include "ierrors.h"
21 #include "imemory.h"
22 #include "idebug.h" /* for debug_print_name */
23 #include "inamedef.h"
24 #include "iname.h"
25 #include "ipacked.h"
26 #include "isave.h" /* for value cache in names */
27 #include "store.h"
28 #include "idict.h" /* interface definition */
29 #include "idictdef.h"
30 #include "iutil.h"
31 #include "ivmspace.h" /* for store check */
32 /*
33 #include "idicttpl.h" - Do not remove this comment.
34 "idicttpl.h" is included below.
35 */
36
37 /*
38 * Dictionaries per se aren't supposed to know anything about the
39 * dictionary stack, let alone the interpreter's dictionary stack.
40 * Unfortunately, there is are two design couplings between them:
41 * dictionary stacks cache some of the elements of their top dictionary
42 * (requiring updating when that dictionary grows or is unpacked),
43 * and names may cache a pointer to their definition (requiring a
44 * check whether a dictionary appears on the dictionary stack).
45 * Therefore, we need iddstack.h here.
46 * We'd really like to fix this, but we don't see how.
47 */
48 #include "iddstack.h"
49
50 /*
51 * Define the size of the largest valid dictionary.
52 * This is limited by the size field of the keys and values refs,
53 * and by the enumeration interface, which requires the size to
54 * fit in an int. As it happens, max_array_size will always be
55 * smaller than max_int.
56 */
57 const uint dict_max_size = max_array_size - 1;
58
59 /* Define whether dictionaries are packed by default. */
60 bool dict_default_pack = true;
61
62 /*
63 * Define the check for whether we can set the 1-element cache.
64 * We only set the cache if we aren't inside a save.
65 * This way, we never have to undo setting the cache.
66 */
67 #define CAN_SET_PVALUE_CACHE(pds, pdref, mem)\
68 (pds && dstack_dict_is_permanent(pds, pdref) && !ref_saving_in(mem))
69
70 /* Forward references */
71 static int dict_create_contents(uint size, const ref * pdref, bool pack);
72
73 /* Debugging statistics */
74 #ifdef DEBUG
75 struct stats_dict_s {
76 long lookups; /* total lookups */
77 long probe1; /* successful lookups on only 1 probe */
78 long probe2; /* successful lookups on 2 probes */
79 } stats_dict;
80
81 /* Wrapper for dict_find */
82 int real_dict_find(const ref * pdref, const ref * key, ref ** ppvalue);
83 int
dict_find(const ref * pdref,const ref * pkey,ref ** ppvalue)84 dict_find(const ref * pdref, const ref * pkey, ref ** ppvalue)
85 {
86 dict *pdict = pdref->value.pdict;
87 int code = real_dict_find(pdref, pkey, ppvalue);
88
89 stats_dict.lookups++;
90 if (r_has_type(pkey, t_name) && dict_is_packed(pdict)) {
91 uint nidx = name_index(dict_mem(pdict), pkey);
92 uint hash =
93 dict_hash_mod(dict_name_index_hash(nidx), npairs(pdict)) + 1;
94
95 if (pdict->keys.value.packed[hash] ==
96 pt_tag(pt_literal_name) + nidx
97 )
98 stats_dict.probe1++;
99 else if (pdict->keys.value.packed[hash - 1] ==
100 pt_tag(pt_literal_name) + nidx
101 )
102 stats_dict.probe2++;
103 }
104 /* Do the cheap flag test before the expensive remainder test. */
105 if (gs_debug_c('d') && !(stats_dict.lookups % 1000))
106 dlprintf3("[d]lookups=%ld probe1=%ld probe2=%ld\n",
107 stats_dict.lookups, stats_dict.probe1, stats_dict.probe2);
108 return code;
109 }
110 #define dict_find real_dict_find
111 #endif
112
113 /* Round up the size of a dictionary. Return 0 if too large. */
114 uint
dict_round_size_small(uint rsize)115 dict_round_size_small(uint rsize)
116 {
117 return (rsize > dict_max_size ? 0 : rsize);
118 }
119 uint
dict_round_size_large(uint rsize)120 dict_round_size_large(uint rsize)
121 { /* Round up to a power of 2 if not huge. */
122 /* If the addition overflows, the new rsize will be zero, */
123 /* which will (correctly) be interpreted as a limitcheck. */
124 if (rsize > dict_max_non_huge)
125 return (rsize > dict_max_size ? 0 : rsize);
126 while (rsize & (rsize - 1))
127 rsize = (rsize | (rsize - 1)) + 1;
128 return (rsize <= dict_max_size ? rsize : dict_max_non_huge);
129 }
130
131 /* Create a dictionary using the given allocator. */
132 int
dict_alloc(gs_ref_memory_t * mem,uint size,ref * pdref)133 dict_alloc(gs_ref_memory_t * mem, uint size, ref * pdref)
134 {
135 ref arr;
136 int code =
137 gs_alloc_ref_array(mem, &arr, a_all, sizeof(dict) / sizeof(ref),
138 "dict_alloc");
139 dict *pdict;
140 ref dref;
141
142 if (code < 0)
143 return code;
144 pdict = (dict *) arr.value.refs;
145 make_tav(&dref, t_dictionary,
146 r_space(&arr) | imemory_new_mask(mem) | a_all,
147 pdict, pdict);
148 make_struct(&pdict->memory, avm_foreign, mem);
149 code = dict_create_contents(size, &dref, dict_default_pack);
150 if (code < 0) {
151 gs_free_ref_array(mem, &arr, "dict_alloc");
152 return code;
153 }
154 *pdref = dref;
155 return 0;
156 }
157 /* Create unpacked keys for a dictionary. */
158 /* The keys are allocated using the same allocator as the dictionary. */
159 static int
dict_create_unpacked_keys(uint asize,const ref * pdref)160 dict_create_unpacked_keys(uint asize, const ref * pdref)
161 {
162 dict *pdict = pdref->value.pdict;
163 gs_ref_memory_t *mem = dict_memory(pdict);
164 int code;
165
166 code = gs_alloc_ref_array(mem, &pdict->keys, a_all, asize,
167 "dict_create_unpacked_keys");
168 if (code >= 0) {
169 uint new_mask = imemory_new_mask(mem);
170 ref *kp = pdict->keys.value.refs;
171
172 r_set_attrs(&pdict->keys, new_mask);
173 refset_null_new(kp, asize, new_mask);
174 r_set_attrs(kp, a_executable); /* wraparound entry */
175 }
176 return code;
177 }
178 /* Create the contents (keys and values) of a newly allocated dictionary. */
179 /* Allocate in the current VM space, which is assumed to be the same as */
180 /* the VM space where the dictionary is allocated. */
181 static int
dict_create_contents(uint size,const ref * pdref,bool pack)182 dict_create_contents(uint size, const ref * pdref, bool pack)
183 {
184 dict *pdict = pdref->value.pdict;
185 gs_ref_memory_t *mem = dict_memory(pdict);
186 uint new_mask = imemory_new_mask(mem);
187 uint asize = dict_round_size((size == 0 ? 1 : size));
188 int code;
189 register uint i;
190
191 if (asize == 0 || asize > max_array_size - 1) /* too large */
192 return_error(e_limitcheck);
193 asize++; /* allow room for wraparound entry */
194 code = gs_alloc_ref_array(mem, &pdict->values, a_all, asize,
195 "dict_create_contents(values)");
196 if (code < 0)
197 return code;
198 r_set_attrs(&pdict->values, new_mask);
199 refset_null_new(pdict->values.value.refs, asize, new_mask);
200 if (pack) {
201 uint ksize = (asize + packed_per_ref - 1) / packed_per_ref;
202 ref arr;
203 ref_packed *pkp;
204 ref_packed *pzp;
205
206 code = gs_alloc_ref_array(mem, &arr, a_all, ksize,
207 "dict_create_contents(packed keys)");
208 if (code < 0)
209 return code;
210 pkp = (ref_packed *) arr.value.refs;
211 make_tasv(&pdict->keys, t_shortarray,
212 r_space(&arr) | a_all | new_mask,
213 asize, packed, pkp);
214 for (pzp = pkp, i = 0; i < asize || i % packed_per_ref; pzp++, i++)
215 *pzp = packed_key_empty;
216 *pkp = packed_key_deleted; /* wraparound entry */
217 } else { /* not packed */
218 int code = dict_create_unpacked_keys(asize, pdref);
219
220 if (code < 0)
221 return code;
222 }
223 make_tav(&pdict->count, t_integer, new_mask, intval, 0);
224 make_tav(&pdict->maxlength, t_integer, new_mask, intval, size);
225 return 0;
226 }
227
228 /*
229 * Ensure that a dictionary uses the unpacked representation for keys.
230 * We can't just use dict_resize, because the values slots mustn't move.
231 */
232 int
dict_unpack(ref * pdref,dict_stack_t * pds)233 dict_unpack(ref * pdref, dict_stack_t *pds)
234 {
235 dict *pdict = pdref->value.pdict;
236
237 if (!dict_is_packed(pdict))
238 return 0; /* nothing to do */
239 {
240 gs_ref_memory_t *mem = dict_memory(pdict);
241 uint count = nslots(pdict);
242 const ref_packed *okp = pdict->keys.value.packed;
243 ref old_keys;
244 int code;
245 ref *nkp;
246
247 old_keys = pdict->keys;
248 if (ref_must_save_in(mem, &old_keys))
249 ref_do_save_in(mem, pdref, &pdict->keys, "dict_unpack(keys)");
250 code = dict_create_unpacked_keys(count, pdref);
251 if (code < 0)
252 return code;
253 for (nkp = pdict->keys.value.refs; count--; okp++, nkp++)
254 if (r_packed_is_name(okp)) {
255 packed_get((const gs_memory_t *)mem, okp, nkp);
256 ref_mark_new_in(mem, nkp);
257 } else if (*okp == packed_key_deleted)
258 r_set_attrs(nkp, a_executable);
259 if (!ref_must_save_in(mem, &old_keys))
260 gs_free_ref_array(mem, &old_keys, "dict_unpack(old keys)");
261 if (pds)
262 dstack_set_top(pds); /* just in case */
263 }
264 return 0;
265 }
266
267 /*
268 * Look up a key in a dictionary. Store a pointer to the value slot
269 * where found, or to the (value) slot for inserting.
270 * See idict.h for the possible return values.
271 */
272 int
dict_find(const ref * pdref,const ref * pkey,ref ** ppvalue)273 dict_find(const ref * pdref, const ref * pkey,
274 ref ** ppvalue /* result is stored here */ )
275 {
276 dict *pdict = pdref->value.pdict;
277 uint size = npairs(pdict);
278 register int etype;
279 uint nidx;
280 ref_packed kpack;
281 uint hash;
282 int ktype;
283 const gs_memory_t *mem = dict_mem(pdict);
284
285 /* Compute hash. The only types we bother with are strings, */
286 /* names, and (unlikely, but worth checking for) integers. */
287 switch (r_type(pkey)) {
288 case t_name:
289 nidx = name_index(mem, pkey);
290 nh:
291 hash = dict_name_index_hash(nidx);
292 kpack = packed_name_key(nidx);
293 ktype = t_name;
294 break;
295 case t_string: /* convert to a name first */
296 {
297 ref nref;
298 int code;
299
300 if (!r_has_attr(pkey, a_read))
301 return_error(e_invalidaccess);
302 code = name_ref(mem, pkey->value.bytes, r_size(pkey), &nref, 1);
303 if (code < 0)
304 return code;
305 nidx = name_index(mem, &nref);
306 }
307 goto nh;
308 case t_real:
309 /*
310 * Make sure that equal reals and integers hash the same.
311 */
312 {
313 int expt, i;
314 double mant = frexp(pkey->value.realval, &expt);
315 /*
316 * The value is mant * 2^expt, where 0.5 <= mant < 1,
317 * or else expt == mant == 0.
318 */
319
320 if (expt < sizeof(long) * 8 || pkey->value.realval == min_long)
321 i = (int)pkey->value.realval;
322 else
323 i = (int)(mant * min_long); /* MSVC 6.00.8168.0 cannot compile this */
324 hash = (uint)i * 30503; /* with -O2 as a single expression */
325 }
326 goto ih;
327 case t_integer:
328 hash = (uint)pkey->value.intval * 30503;
329 ih:
330 kpack = packed_key_impossible;
331 ktype = -1;
332 nidx = 0; /* only to pacify gcc */
333 break;
334 case t_null: /* not allowed as a key */
335 return_error(e_typecheck);
336 default:
337 hash = r_btype(pkey) * 99; /* yech */
338 kpack = packed_key_impossible;
339 ktype = -1;
340 nidx = 0; /* only to pacify gcc */
341 }
342 /* Search the dictionary */
343 if (dict_is_packed(pdict)) {
344 const ref_packed *pslot = 0;
345
346 # define found *ppvalue = packed_search_value_pointer; return 1
347 # define deleted if (pslot == 0) pslot = kp
348 # define missing goto miss
349 # include "idicttpl.h"
350 # undef missing
351 # undef deleted
352 # undef found
353 /*
354 * Double wraparound, dict is full.
355 * Note that even if there was an empty slot (pslot != 0),
356 * we must return dictfull if length = maxlength.
357 */
358 if (pslot == 0 || d_length(pdict) == d_maxlength(pdict))
359 return_error(e_dictfull);
360 *ppvalue = pdict->values.value.refs + (pslot - kbot);
361 return 0;
362 miss: /* Key is missing, not double wrap. See above re dictfull. */
363 if (d_length(pdict) == d_maxlength(pdict))
364 return_error(e_dictfull);
365 if (pslot == 0)
366 pslot = kp;
367 *ppvalue = pdict->values.value.refs + (pslot - kbot);
368 return 0;
369 } else {
370 ref *kbot = pdict->keys.value.refs;
371 register ref *kp;
372 ref *pslot = 0;
373 int wrap = 0;
374
375 for (kp = kbot + dict_hash_mod(hash, size) + 2;;) {
376 --kp;
377 if ((etype = r_type(kp)) == ktype) { /* Fast comparison if both keys are names */
378 if (name_index(mem, kp) == nidx) {
379 *ppvalue = pdict->values.value.refs + (kp - kbot);
380 return 1;
381 }
382 } else if (etype == t_null) { /* Empty, deleted, or wraparound. */
383 /* Figure out which. */
384 if (kp == kbot) { /* wrap */
385 if (wrap++) { /* wrapped twice */
386 if (pslot == 0)
387 return_error(e_dictfull);
388 break;
389 }
390 kp += size + 1;
391 } else if (r_has_attr(kp, a_executable)) { /* Deleted entry, save the slot. */
392 if (pslot == 0)
393 pslot = kp;
394 } else /* key not found */
395 break;
396 } else {
397 if (obj_eq(mem, kp, pkey)) {
398 *ppvalue = pdict->values.value.refs + (kp - kbot);
399 return 1;
400 }
401 }
402 }
403 if (d_length(pdict) == d_maxlength(pdict))
404 return_error(e_dictfull);
405 *ppvalue = pdict->values.value.refs +
406 ((pslot != 0 ? pslot : kp) - kbot);
407 return 0;
408 }
409 }
410
411 /*
412 * Look up a (constant) C string in a dictionary.
413 * Return 1 if found, <= 0 if not.
414 */
415 int
dict_find_string(const ref * pdref,const char * kstr,ref ** ppvalue)416 dict_find_string(const ref * pdref, const char *kstr, ref ** ppvalue)
417 {
418 int code;
419 ref kname;
420 if ( pdref != 0 ) {
421 dict *pdict = pdref->value.pdict;
422
423 if ((code = name_ref(dict_mem(pdict),
424 (const byte *)kstr, strlen(kstr), &kname, -1)) < 0)
425 return code;
426 code = dict_find(pdref, &kname, ppvalue);
427 if (code == e_dictfull)
428 return_error(e_undefined);
429 return code;
430 }
431 return 0;
432 }
433
434 /*
435 * Enter a key-value pair in a dictionary.
436 * See idict.h for the possible return values.
437 */
438 int
dict_put(ref * pdref,const ref * pkey,const ref * pvalue,dict_stack_t * pds)439 dict_put(ref * pdref /* t_dictionary */ , const ref * pkey, const ref * pvalue,
440 dict_stack_t *pds)
441 {
442 dict *pdict = pdref->value.pdict;
443 gs_ref_memory_t *mem = dict_memory(pdict);
444 gs_memory_t *pmem = dict_mem(pdict);
445 int rcode = 0;
446 int code;
447 ref *pvslot, kname;
448
449 /* Check the value. */
450 store_check_dest(pdref, pvalue);
451 top:if ((code = dict_find(pdref, pkey, &pvslot)) <= 0) { /* not found *//* Check for overflow */
452 uint index;
453
454 switch (code) {
455 case 0:
456 break;
457 case e_dictfull:
458 if (!pmem->gs_lib_ctx->dict_auto_expand)
459 return_error(e_dictfull);
460 code = dict_grow(pdref, pds);
461 if (code < 0)
462 return code;
463 goto top; /* keep things simple */
464 default: /* e_typecheck */
465 return code;
466 }
467 index = pvslot - pdict->values.value.refs;
468 /* If the key is a string, convert it to a name. */
469 if (r_has_type(pkey, t_string)) {
470 int code;
471
472 if (!r_has_attr(pkey, a_read))
473 return_error(e_invalidaccess);
474 code = name_from_string(pmem, pkey, &kname);
475 if (code < 0)
476 return code;
477 pkey = &kname;
478 }
479 if (dict_is_packed(pdict)) {
480 ref_packed *kp;
481
482 if (!r_has_type(pkey, t_name) ||
483 name_index(pmem, pkey) > packed_name_max_index
484 ) { /* Change to unpacked representation. */
485 int code = dict_unpack(pdref, pds);
486
487 if (code < 0)
488 return code;
489 goto top;
490 }
491 kp = pdict->keys.value.writable_packed + index;
492 if (ref_must_save_in(mem, &pdict->keys)) { /* See initial comment for why it is safe */
493 /* not to save the change if the keys */
494 /* array itself is new. */
495 ref_do_save_in(mem, &pdict->keys, kp, "dict_put(key)");
496 }
497 *kp = pt_tag(pt_literal_name) + name_index(pmem, pkey);
498 } else {
499 ref *kp = pdict->keys.value.refs + index;
500
501 if_debug2('d', "[d]0x%lx: fill key at 0x%lx\n",
502 (ulong) pdict, (ulong) kp);
503 store_check_dest(pdref, pkey);
504 ref_assign_old_in(mem, &pdict->keys, kp, pkey,
505 "dict_put(key)"); /* set key of pair */
506 }
507 ref_save_in(mem, pdref, &pdict->count, "dict_put(count)");
508 pdict->count.value.intval++;
509 /* If the key is a name, update its 1-element cache. */
510 if (r_has_type(pkey, t_name)) {
511 name *pname = pkey->value.pname;
512
513 if (pname->pvalue == pv_no_defn &&
514 CAN_SET_PVALUE_CACHE(pds, pdref, mem)
515 ) { /* Set the cache. */
516 if_debug0('d', "[d]set cache\n");
517 pname->pvalue = pvslot;
518 } else { /* The cache can't be used. */
519 if_debug0('d', "[d]no cache\n");
520 pname->pvalue = pv_other;
521 }
522 }
523 rcode = 1;
524 }
525 if_debug8('d', "[d]0x%lx: put key 0x%lx 0x%lx\n value at 0x%lx: old 0x%lx 0x%lx, new 0x%lx 0x%lx\n",
526 (ulong) pdref->value.pdict,
527 ((const ulong *)pkey)[0], ((const ulong *)pkey)[1],
528 (ulong) pvslot,
529 ((const ulong *)pvslot)[0], ((const ulong *)pvslot)[1],
530 ((const ulong *)pvalue)[0], ((const ulong *)pvalue)[1]);
531 ref_assign_old_in(mem, &pdref->value.pdict->values, pvslot, pvalue,
532 "dict_put(value)");
533 return rcode;
534 }
535
536 /*
537 * Enter a key-value pair where the key is a (constant) C string.
538 */
539 int
dict_put_string(ref * pdref,const char * kstr,const ref * pvalue,dict_stack_t * pds)540 dict_put_string(ref * pdref, const char *kstr, const ref * pvalue,
541 dict_stack_t *pds)
542 {
543 int code;
544 ref kname;
545 dict *pdict = pdref->value.pdict;
546
547 if ((code = name_ref(dict_mem(pdict),
548 (const byte *)kstr, strlen(kstr), &kname, 0)) < 0)
549 return code;
550 return dict_put(pdref, &kname, pvalue, pds);
551 }
552
553 /* Remove an element from a dictionary. */
554 int
dict_undef(ref * pdref,const ref * pkey,dict_stack_t * pds)555 dict_undef(ref * pdref, const ref * pkey, dict_stack_t *pds)
556 {
557 gs_ref_memory_t *mem;
558 ref *pvslot;
559 dict *pdict;
560 uint index;
561 int code = dict_find(pdref, pkey, &pvslot);
562
563 switch (code) {
564 case 0:
565 case e_dictfull:
566 return_error(e_undefined);
567 case 1:
568 break;
569 default: /* other error */
570 return code;
571 }
572 /* Remove the entry from the dictionary. */
573 pdict = pdref->value.pdict;
574 index = pvslot - pdict->values.value.refs;
575 mem = dict_memory(pdict);
576 if (dict_is_packed(pdict)) {
577 ref_packed *pkp = pdict->keys.value.writable_packed + index;
578 bool must_save = ref_must_save_in(mem, &pdict->keys);
579
580 if_debug3('d', "[d]0x%lx: removing key at 0%lx: 0x%x\n",
581 (ulong)pdict, (ulong)pkp, (uint)*pkp);
582 /* See the initial comment for why it is safe not to save */
583 /* the change if the keys array itself is new. */
584 if (must_save)
585 ref_do_save_in(mem, &pdict->keys, pkp, "dict_undef(key)");
586 /*
587 * Accumulating deleted entries slows down lookup.
588 * Detect the easy case where we can use an empty entry
589 * rather than a deleted one, namely, when the next entry
590 * in the probe order is empty.
591 */
592 if (pkp[-1] == packed_key_empty) {
593 /*
594 * In this case we can replace any preceding deleted keys with
595 * empty ones as well.
596 */
597 uint end = nslots(pdict);
598
599 *pkp = packed_key_empty;
600 if (must_save) {
601 while (++index < end && *++pkp == packed_key_deleted) {
602 ref_do_save_in(mem, &pdict->keys, pkp, "dict_undef(key)");
603 *pkp = packed_key_empty;
604 }
605 } else {
606 while (++index < end && *++pkp == packed_key_deleted)
607 *pkp = packed_key_empty;
608 }
609 } else
610 *pkp = packed_key_deleted;
611 } else { /* not packed */
612 ref *kp = pdict->keys.value.refs + index;
613
614 if_debug4('d', "[d]0x%lx: removing key at 0%lx: 0x%lx 0x%lx\n",
615 (ulong)pdict, (ulong)kp, ((ulong *)kp)[0], ((ulong *)kp)[1]);
616 make_null_old_in(mem, &pdict->keys, kp, "dict_undef(key)");
617 /*
618 * Accumulating deleted entries slows down lookup.
619 * Detect the easy case where we can use an empty entry
620 * rather than a deleted one, namely, when the next entry
621 * in the probe order is empty.
622 */
623 if (!r_has_type(kp - 1, t_null) || /* full entry */
624 r_has_attr(kp - 1, a_executable) /* deleted or wraparound */
625 )
626 r_set_attrs(kp, a_executable); /* mark as deleted */
627 }
628 ref_save_in(mem, pdref, &pdict->count, "dict_undef(count)");
629 pdict->count.value.intval--;
630 /* If the key is a name, update its 1-element cache. */
631 if (r_has_type(pkey, t_name)) {
632 name *pname = pkey->value.pname;
633
634 if (pv_valid(pname->pvalue)) {
635 #ifdef DEBUG
636 /* Check the the cache is correct. */
637 if (!(pds && dstack_dict_is_permanent(pds, pdref)))
638 lprintf1("dict_undef: cached name value pointer 0x%lx is incorrect!\n",
639 (ulong) pname->pvalue);
640 #endif
641 /* Clear the cache */
642 pname->pvalue = pv_no_defn;
643 }
644 }
645 make_null_old_in(mem, &pdict->values, pvslot, "dict_undef(value)");
646 return 0;
647 }
648
649 /* Return the number of elements in a dictionary. */
650 uint
dict_length(const ref * pdref)651 dict_length(const ref * pdref /* t_dictionary */ )
652 {
653 return d_length(pdref->value.pdict);
654 }
655
656 /* Return the capacity of a dictionary. */
657 uint
dict_maxlength(const ref * pdref)658 dict_maxlength(const ref * pdref /* t_dictionary */ )
659 {
660 return d_maxlength(pdref->value.pdict);
661 }
662
663 /* Return the maximum index of a slot within a dictionary. */
664 uint
dict_max_index(const ref * pdref)665 dict_max_index(const ref * pdref /* t_dictionary */ )
666 {
667 return npairs(pdref->value.pdict) - 1;
668 }
669
670 /*
671 * Copy one dictionary into another.
672 * If COPY_NEW_ONLY is set, only copy entries whose keys
673 * aren't already present in the destination.
674 * If COPY_FOR_RESIZE is set, reset any valid name cache entries to
675 * pv_no_defn before doing the dict_put.
676 */
677 #define COPY_NEW_ONLY 1
678 #define COPY_FOR_RESIZE 2
679 static int
dict_copy_elements(const ref * pdrfrom,ref * pdrto,int options,dict_stack_t * pds)680 dict_copy_elements(const ref * pdrfrom /* t_dictionary */ ,
681 ref * pdrto /* t_dictionary */ , int options,
682 dict_stack_t *pds)
683 {
684 int space = r_space(pdrto);
685 int index;
686 ref elt[2];
687 ref *pvslot;
688 int code;
689
690 if (space != avm_max) {
691 /* Do the store check before starting the copy. */
692 index = dict_first(pdrfrom);
693 while ((index = dict_next(pdrfrom, index, elt)) >= 0)
694 if (!(options & COPY_NEW_ONLY) ||
695 dict_find(pdrto, &elt[0], &pvslot) <= 0
696 ) {
697 store_check_space(space, &elt[0]);
698 store_check_space(space, &elt[1]);
699 }
700 }
701 /* Now copy the contents. */
702 index = dict_first(pdrfrom);
703 while ((index = dict_next(pdrfrom, index, elt)) >= 0) {
704 ref *pvalue = pv_no_defn;
705
706 if ((options & COPY_NEW_ONLY) &&
707 dict_find(pdrto, &elt[0], &pvslot) > 0
708 )
709 continue;
710 if ((options & COPY_FOR_RESIZE) &&
711 r_has_type(&elt[0], t_name) &&
712 (pvalue = elt[0].value.pname->pvalue, pv_valid(pvalue))
713 )
714 elt[0].value.pname->pvalue = pv_no_defn;
715 if ((code = dict_put(pdrto, &elt[0], &elt[1], pds)) < 0) {
716 /*
717 * If COPY_FOR_RESIZE is set, the dict_put isn't supposed to
718 * be able to fail, but we don't want to depend on this.
719 */
720 if (pvalue != pv_no_defn)
721 elt[0].value.pname->pvalue = pvalue;
722 return code;
723 }
724 }
725 return 0;
726 }
727 int
dict_copy_entries(const ref * pdrfrom,ref * pdrto,bool new_only,dict_stack_t * pds)728 dict_copy_entries(const ref *pdrfrom, ref *pdrto, bool new_only,
729 dict_stack_t *pds)
730 {
731 return dict_copy_elements(pdrfrom, pdrto, (new_only ? COPY_NEW_ONLY : 0),
732 pds);
733 }
734
735 /* Resize a dictionary. */
736 int
dict_resize(ref * pdref,uint new_size,dict_stack_t * pds)737 dict_resize(ref * pdref, uint new_size, dict_stack_t *pds)
738 {
739 dict *pdict = pdref->value.pdict;
740 gs_ref_memory_t *mem = dict_memory(pdict);
741 uint new_mask = imemory_new_mask(mem);
742 ushort orig_attrs = r_type_attrs(&pdict->values) & (a_all | a_executable);
743 dict dnew;
744 ref drto;
745 int code;
746
747 if (new_size < d_length(pdict)) {
748 if (!mem->gs_lib_ctx->dict_auto_expand)
749 return_error(e_dictfull);
750 new_size = d_length(pdict);
751 }
752 make_tav(&drto, t_dictionary, r_space(pdref) | a_all | new_mask,
753 pdict, &dnew);
754 dnew.memory = pdict->memory;
755 if ((code = dict_create_contents(new_size, &drto, dict_is_packed(pdict))) < 0)
756 return code;
757 /*
758 * We must suppress the store check, in case we are expanding
759 * systemdict or another global dictionary that is allowed
760 * to reference local objects.
761 */
762 r_set_space(&drto, avm_local);
763 /*
764 * If we are expanding a permanent dictionary, we must make sure that
765 * dict_put doesn't think this is a second definition for any
766 * single-definition names. This in turn requires that
767 * dstack_dict_is_permanent must be true for the second ("to")
768 * argument of dict_copy_elements, which requires temporarily
769 * setting *pdref = drto.
770 */
771 if (CAN_SET_PVALUE_CACHE(pds, pdref, mem)) {
772 ref drfrom;
773
774 drfrom = *pdref;
775 *pdref = drto;
776 dict_copy_elements(&drfrom, pdref, COPY_FOR_RESIZE, pds);
777 *pdref = drfrom;
778 } else {
779 dict_copy_elements(pdref, &drto, 0, pds);
780 }
781 /* Save or free the old dictionary. */
782 if (ref_must_save_in(mem, &pdict->values))
783 ref_do_save_in(mem, pdref, &pdict->values, "dict_resize(values)");
784 else
785 gs_free_ref_array(mem, &pdict->values, "dict_resize(old values)");
786 if (ref_must_save_in(mem, &pdict->keys))
787 ref_do_save_in(mem, pdref, &pdict->keys, "dict_resize(keys)");
788 else
789 gs_free_ref_array(mem, &pdict->keys, "dict_resize(old keys)");
790 ref_assign(&pdict->keys, &dnew.keys);
791 ref_assign(&pdict->values, &dnew.values);
792 r_store_attrs(&pdict->values, a_all | a_executable, orig_attrs);
793 ref_save_in(dict_memory(pdict), pdref, &pdict->maxlength,
794 "dict_resize(maxlength)");
795 d_set_maxlength(pdict, new_size);
796 if (pds)
797 dstack_set_top(pds); /* just in case this is the top dict */
798 return 0;
799 }
800
801 /* Grow a dictionary for dict_put. */
802 int
dict_grow(ref * pdref,dict_stack_t * pds)803 dict_grow(ref * pdref, dict_stack_t *pds)
804 {
805 dict *pdict = pdref->value.pdict;
806 /* We might have maxlength < npairs, if */
807 /* dict_round_size increased the size. */
808 ulong new_size = (ulong) d_maxlength(pdict);
809 /* Adobe does this */
810 if (new_size < 20)
811 new_size += 10;
812 else if (new_size < 200)
813 new_size *= 2;
814 else
815 new_size += new_size / 2;
816 #if arch_sizeof_int < arch_sizeof_long
817 if (new_size > max_uint)
818 new_size = max_uint;
819 #endif
820 if (new_size > npairs(pdict)) {
821 int code = dict_resize(pdref, (uint) new_size, pds);
822
823 if (code >= 0)
824 return code;
825 /* new_size was too big. */
826 if (npairs(pdict) < dict_max_size) {
827 code = dict_resize(pdref, dict_max_size, pds);
828 if (code >= 0)
829 return code;
830 }
831 if (npairs(pdict) == d_maxlength(pdict)) { /* Can't do it. */
832 return code;
833 }
834 /* We can't grow to new_size, but we can grow to npairs. */
835 new_size = npairs(pdict);
836 }
837 /* maxlength < npairs, we can grow in place */
838 ref_save_in(dict_memory(pdict), pdref, &pdict->maxlength,
839 "dict_put(maxlength)");
840 d_set_maxlength(pdict, new_size);
841 return 0;
842 }
843
844 /* Prepare to enumerate a dictionary. */
845 int
dict_first(const ref * pdref)846 dict_first(const ref * pdref)
847 {
848 return (int)nslots(pdref->value.pdict);
849 }
850
851 /* Enumerate the next element of a dictionary. */
852 int
dict_next(const ref * pdref,int index,ref * eltp)853 dict_next(const ref * pdref, int index, ref * eltp /* ref eltp[2] */ )
854 {
855 dict *pdict = pdref->value.pdict;
856 ref *vp = pdict->values.value.refs + index;
857
858 while (vp--, --index >= 0) {
859 array_get(dict_mem(pdict), &pdict->keys, (long)index, eltp);
860 /* Make sure this is a valid entry. */
861 if (r_has_type(eltp, t_name) ||
862 (!dict_is_packed(pdict) && !r_has_type(eltp, t_null))
863 ) {
864 eltp[1] = *vp;
865 if_debug6('d', "[d]0x%lx: index %d: %lx %lx, %lx %lx\n",
866 (ulong) pdict, index,
867 ((ulong *) eltp)[0], ((ulong *) eltp)[1],
868 ((ulong *) vp)[0], ((ulong *) vp)[1]);
869 return index;
870 }
871 }
872 return -1; /* no more elements */
873 }
874
875 /* Return the index of a value within a dictionary. */
876 int
dict_value_index(const ref * pdref,const ref * pvalue)877 dict_value_index(const ref * pdref, const ref * pvalue)
878 {
879 return (int)(pvalue - pdref->value.pdict->values.value.refs - 1);
880 }
881
882 /* Return the entry at a given index within a dictionary. */
883 /* If the index designates an unoccupied entry, return e_undefined. */
884 int
dict_index_entry(const ref * pdref,int index,ref * eltp)885 dict_index_entry(const ref * pdref, int index, ref * eltp /* ref eltp[2] */ )
886 {
887 const dict *pdict = pdref->value.pdict;
888
889 array_get(dict_mem(pdict), &pdict->keys, (long)(index + 1), eltp);
890 if (r_has_type(eltp, t_name) ||
891 (!dict_is_packed(pdict) && !r_has_type(eltp, t_null))
892 ) {
893 eltp[1] = pdict->values.value.refs[index + 1];
894 return 0;
895 }
896 return e_undefined;
897 }
898