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