home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 5 / FreshFish_July-August1994.bin / bbs / gnu / gs-2.6.1.4-src.lha / src / amiga / gs-2.6.1.4 / idict.c < prev    next >
C/C++ Source or Header  |  1994-01-27  |  22KB  |  670 lines
  1. /* Copyright (C) 1989, 1992 Aladdin Enterprises.  All rights reserved.
  2.  
  3. This file is part of Ghostscript.
  4.  
  5. Ghostscript is distributed in the hope that it will be useful, but
  6. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  7. to anyone for the consequences of using it or for whether it serves any
  8. particular purpose or works at all, unless he says so in writing.  Refer
  9. to the Ghostscript General Public License for full details.
  10.  
  11. Everyone is granted permission to copy, modify and redistribute
  12. Ghostscript, but only under the conditions described in the Ghostscript
  13. General Public License.  A copy of this license is supposed to have been
  14. given to you along with Ghostscript so you can know your rights and
  15. responsibilities.  It should be in a file named COPYING.  Among other
  16. things, the copyright notice and this notice must be preserved on all
  17. copies.  */
  18.  
  19. /* idict.c */
  20. /* Dictionaries for Ghostscript */
  21. #include "ghost.h"
  22. #include "alloc.h"
  23. #include "errors.h"
  24. #include "iname.h"
  25. #include "packed.h"
  26. #include "save.h"            /* for value cache in names */
  27. #include "store.h"
  28. #include "iutil.h"            /* for array_get and obj_eq */
  29. #include "ivmspace.h"            /* for store check */
  30. #include "dict.h"            /* interface definition */
  31. #include "dstack.h"            /* ditto */
  32.  
  33. /*
  34.  * A dictionary is a structure of three elements (refs):
  35.  *
  36.  *    count - a t_integer whose value says how many entries are
  37.  *    occupied (N), and whose size says how many elements the client
  38.  *    thinks the dictionary can hold (C).  C may be less than M (see below).
  39.  *
  40.  *    keys - a t_shortarray or t_array of M+1 elements, containing
  41.  *    the keys.
  42.  *
  43.  *    values - a t_array of M+1 elements, containing the values.
  44.  *
  45.  * C < M is possible because on 32-bit systems, we round up M so that
  46.  * M is a power of 2; this allows us to use masking rather than division
  47.  * for computing the initial hash probe.  However, C is always the
  48.  * maxlength specified by the client, so clients get a consistent story.
  49.  */
  50. #define dict_round_size (!arch_ints_are_short)
  51. #if dict_round_size
  52. #  define hash_mod(hash, size) ((hash) & ((size) - 1))
  53. #else
  54. #  define hash_mod(hash, size) ((hash) % (size))
  55. #endif
  56. /*
  57.  * The first entry is always marked deleted, to reduce the cost of the
  58.  * wrap-around check.
  59.  *
  60.  * In the packed form:
  61.  *    unused entries contain packed_key_empty;
  62.  *    deleted entries contain packed_key_deleted.
  63.  * In the unpacked form:
  64.  *    unused entries contain a literal null;
  65.  *    deleted entries contain an executable null.
  66.  *
  67.  * Note that if the keys slot in the dictionary is new,
  68.  * all the key slots are new (more recent than the last save).
  69.  * We use this fact to avoid saving stores into packed keys
  70.  * for newly created dictionaries.
  71.  */
  72. #define dict_is_packed(dct) r_has_type(&(dct)->keys, t_shortarray)
  73. #define packed_key_empty (pt_tag(pt_integer) + 0)
  74. #define packed_key_deleted (pt_tag(pt_integer) + 1)
  75. #define packed_key_impossible pt_tag(pt_full_ref)    /* never matches */
  76. #define packed_name_key(nidx)\
  77.   ((nidx) <= packed_max_name_index ? pt_tag(pt_literal_name) + (nidx) :\
  78.    packed_key_impossible)
  79. /*
  80.  * Using a special mark for deleted entries causes lookup time to degrade
  81.  * as entries are inserted and deleted.  This is not a problem, because
  82.  * entries are almost never deleted.
  83.  */
  84. #define d_maxlength(dct) r_size(&(dct)->count)
  85. #define d_set_maxlength(dct,siz) r_set_size(&(dct)->count,siz)
  86. #define nslots(dct) r_size(&(dct)->values)
  87. #define npairs(dct) (nslots(dct) - 1)
  88. #define d_length(dct) ((uint)((dct)->count.value.intval))
  89.  
  90. /* Define the size of the largest valid dictionary. */
  91. /* This is limited by the size field of the keys and values refs, */
  92. /* and by the enumeration interface, which requires the size to */
  93. /* fit in an int. */
  94. const uint dict_max_size = max_ushort / 2 - 2;
  95.  
  96. /* Define whether dictionaries expand automatically when full. */
  97. int dict_auto_expand = 0;
  98.  
  99. /* Define the hashing function for names. */
  100. /* We don't have to scramble the index, because */
  101. /* indices are assigned in a scattered order (see name_ref in iname.c). */
  102. #define dict_name_index_hash(nidx) (nidx)
  103.  
  104. /* Define whether dictionaries are packed by default. */
  105. #define default_pack 1
  106.  
  107. /* Forward references */
  108. private int dict_create_contents(P3(uint size, dict *pdict, int pack));
  109.  
  110. /* Create a dictionary. */
  111. int
  112. dict_create(uint size, ref *pref)
  113. {    ref arr;
  114.     int code = alloc_array(&arr, a_all, sizeof(dict) / sizeof(ref), "dict_create");
  115.     dict *pdict = (dict *)arr.value.refs;
  116.     if ( code < 0 ) return code;
  117.     code = dict_create_contents(size, pdict, default_pack);
  118.     if ( code < 0 ) return code;
  119.     make_tav_new(pref, t_dictionary, a_all, pdict, pdict);
  120.     return 0;
  121. }
  122. private int
  123. dict_create_unpacked_keys(uint asize, dict *pdict)
  124. {    int code = alloc_array(&pdict->keys, a_all, asize, "dict_create(keys)");
  125.     ref *kp;
  126.     ref *zp;
  127.     register uint i;
  128.     if ( code < 0 ) return code;
  129.     ref_mark_new(&pdict->keys);
  130.     for ( zp = kp = pdict->keys.value.refs, i = asize; i; zp++, i-- )
  131.         make_null_new(zp);
  132.     r_set_attrs(kp, a_executable);    /* wraparound entry */
  133.     return 0;
  134. }
  135. private int
  136. dict_create_contents(uint size, dict *pdict, int pack)
  137. {    uint csize = (size == 0 ? 1 : size);    /* client-specified size */
  138.     uint asize = csize;
  139.     int code;
  140.     register uint i;
  141.     ref *zp;
  142. #if dict_round_size
  143.     /* Round up the actual allocated size to the next higher */
  144.     /* power of 2, so we can use & instead of %. */
  145.     while ( asize & (asize - 1) ) asize = (asize | (asize >> 1)) + 1;
  146. #endif
  147.     asize++;        /* allow room for wraparound entry */
  148.     code = alloc_array(&pdict->values, a_all, asize, "dict_create(values)");
  149.     if ( code < 0 ) return code;
  150.     ref_mark_new(&pdict->values);
  151.     for ( zp = pdict->values.value.refs, i = asize; i; zp++, i-- )
  152.         make_null_new(zp);
  153.     if ( pack )
  154.        {    uint ksize = (asize + packed_per_ref - 1) / packed_per_ref;
  155.         ref arr;
  156.         ref_packed *pkp;
  157.         ref_packed *pzp;
  158.         code = alloc_array(&arr, a_all, ksize, "dict_create(packed keys)");
  159.         if ( code < 0 ) return code;
  160.         pkp = (ref_packed *)arr.value.refs;
  161.         make_tasv_new(&pdict->keys, t_shortarray, a_all, asize,
  162.                   packed, pkp);
  163.         for ( pzp = pkp, i = 0; i < asize || i % packed_per_ref; pzp++, i++ )
  164.             *pzp = packed_key_empty;
  165.         *pkp = packed_key_deleted;    /* wraparound entry */
  166.        }
  167.     else                /* not packed */
  168.        {    int code = dict_create_unpacked_keys(asize, pdict);
  169.         if ( code < 0 ) return code;
  170.        }
  171.     make_tv_new(&pdict->count, t_integer, intval, 0);
  172.     d_set_maxlength(pdict, csize);
  173.     return 0;
  174. }
  175.  
  176. /*
  177.  * Define a macro for searching a packed dictionary.  Free variables:
  178.  *    ref_packed kpack - holds the packed key.
  179.  *    uint hash - holds the hash of the name.
  180.  *    dict *pdict - points to the dictionary.
  181.  *    uint size - holds npairs(pdict).
  182.  * Note that the macro is *not* enclosed in {}, so that we can access
  183.  * the values of kbot and kp after leaving the loop.
  184.  *
  185.  * We break the macro into two to avoid overflowing some preprocessors.
  186.  */
  187. #define packed_search_1(del,pre,post,miss)\
  188.    const ref_packed *kbot = pdict->keys.value.packed;\
  189.    register const ref_packed *kp;\
  190.    for ( kp = kbot + hash_mod(hash, size) + 2; ; )\
  191.     { if ( *--kp == kpack )\
  192.        { pre (pdict->values.value.refs + (kp - kbot));\
  193.      post;\
  194.        }\
  195.       else if ( !packed_ref_is_name(kp) )\
  196.        { /* Empty, deleted, or wraparound. Figure out which. */\
  197.      if ( *kp == packed_key_empty ) miss;\
  198.      if ( kp == kbot ) break;    /* wrap */\
  199.      else { del; }\
  200.        }\
  201.     }
  202. #define packed_search_2(del,pre,post,miss)\
  203.    for ( kp += size + 1; ; )\
  204.     { if ( *--kp == kpack )\
  205.        { pre (pdict->values.value.refs + (kp - kbot));\
  206.      post;\
  207.        }\
  208.       else if ( !packed_ref_is_name(kp) )\
  209.        { /* Empty, deleted, or wraparound. Figure out which. */\
  210.      if ( *kp == packed_key_empty ) miss;\
  211.      if ( kp == kbot ) break;    /* wrap */\
  212.      else { del; }\
  213.        }\
  214.     }
  215.  
  216. /*
  217.  * Look up in a stack of dictionaries.  Store a pointer to the value slot
  218.  * where found, or to the (value) slot for inserting.
  219.  * Return 1 if found, 0 if not and there is room for a new entry in
  220.  * the top dictionary on the stack, or e_dictfull if the top dictionary
  221.  * is full and the key is missing.
  222.  * Note that pdbot <= pdtop, and the search starts at pdtop.
  223.  */
  224. int
  225. dict_lookup(const ref *pdbot, const ref