pstoraster/idict.c

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