1 /* Copyright (C) 1998 Aladdin Enterprises. All rights reserved. 2 3 This software is provided AS-IS with no warranty, either express or 4 implied. 5 6 This software is distributed under license and may not be copied, 7 modified or distributed except as expressly authorized under the terms 8 of the license contained in the file LICENSE in this distribution. 9 10 For more information about licensing, please refer to 11 http://www.ghostscript.com/licensing/. For information on 12 commercial licensing, go to http://www.artifex.com/licensing/ or 13 contact Artifex Software, Inc., 101 Lucas Valley Road #110, 14 San Rafael, CA 94903, U.S.A., +1(415)492-9861. 15 */ 16 17 /* $Id: idictdef.h,v 1.4 2002/02/21 22:24:53 giles Exp $ */ 18 /* Internals of dictionary implementation */ 19 20 #ifndef idictdef_INCLUDED 21 # define idictdef_INCLUDED 22 23 /* 24 * A dictionary of capacity M is a structure containing the following 25 * elements (refs): 26 * 27 * keys - a t_shortarray or t_array of M+1 elements, containing 28 * the keys. 29 * 30 * values - a t_array of M+1 elements, containing the values. 31 * 32 * count - a t_integer whose value tells how many entries are 33 * occupied (N). 34 * 35 * maxlength - a t_integer whose value gives the client's view of 36 * the capacity (C). C may be less than M (see below). 37 * 38 * memory - a foreign t_struct referencing the allocator used to 39 * create this dictionary, which will also be used to expand or 40 * unpack it if necessary. 41 * 42 * C < M is possible because on large-memory systems, we usually round up M 43 * so that M is a power of 2 (see idict.h for details); this allows us to 44 * use masking rather than division for computing the initial hash probe. 45 * However, C is always the maxlength specified by the client, so clients 46 * get a consistent story. 47 * 48 * As noted above, the keys may be either in packed or unpacked form. 49 * The markers for unused and deleted entries are different in the two forms. 50 * In the packed form: 51 * unused entries contain packed_key_empty; 52 * deleted entries contain packed_key_deleted. 53 * In the unpacked form: 54 * unused entries contain a literal null; 55 * deleted entries contain an executable null. 56 * 57 * The first entry is always marked deleted, to reduce the cost of the 58 * wrap-around check. 59 * 60 * Note that if the keys slot in the dictionary is new, 61 * all the key slots are new (more recent than the last save). 62 * We use this fact to avoid saving stores into packed keys 63 * for newly created dictionaries. 64 * 65 * Note that name keys with indices above packed_name_max_index require using 66 * the unpacked form. */ 67 #define dict_is_packed(dct) r_has_type(&(dct)->keys, t_shortarray) 68 #define packed_key_empty (pt_tag(pt_integer) + 0) 69 #define packed_key_deleted (pt_tag(pt_integer) + 1) 70 #define packed_key_impossible pt_tag(pt_full_ref) /* never matches */ 71 #define packed_name_key(nidx)\ 72 ((nidx) <= packed_name_max_index ? pt_tag(pt_literal_name) + (nidx) :\ 73 packed_key_impossible) 74 /* 75 * Using a special mark for deleted entries causes lookup time to degrade 76 * as entries are inserted and deleted. This is not a problem, because 77 * entries are almost never deleted. 78 */ 79 #define d_maxlength(dct) ((uint)((dct)->maxlength.value.intval)) 80 #define d_set_maxlength(dct,siz) ((dct)->maxlength.value.intval = (siz)) 81 #define nslots(dct) r_size(&(dct)->values) 82 #define npairs(dct) (nslots(dct) - 1) 83 #define d_length(dct) ((uint)((dct)->count.value.intval)) 84 85 /* 86 * Define macros for searching a packed dictionary. Free variables: 87 * ref_packed kpack - holds the packed key. 88 * uint hash - holds the hash of the name. 89 * dict *pdict - points to the dictionary. 90 * uint size - holds npairs(pdict). 91 * Note that the macro is *not* enclosed in {}, so that we can access 92 * the values of kbot and kp after leaving the loop. 93 * 94 * We break the macro into two to avoid overflowing some preprocessors. 95 */ 96 /* packed_search_body also uses kp and kbot as free variables. */ 97 #define packed_search_value_pointer (pdict->values.value.refs + (kp - kbot)) 98 #define packed_search_body(found1,found2,del,miss)\ 99 { if_debug2('D', "[D]probe 0x%lx: 0x%x\n", (ulong)kp, *kp);\ 100 if ( *kp == kpack )\ 101 { found1;\ 102 found2;\ 103 }\ 104 else if ( !r_packed_is_name(kp) )\ 105 { /* Empty, deleted, or wraparound. Figure out which. */\ 106 if ( *kp == packed_key_empty ) miss;\ 107 if ( kp == kbot ) break; /* wrap */\ 108 else { del; }\ 109 }\ 110 } 111 #define packed_search_1(found1,found2,del,miss)\ 112 const ref_packed *kbot = pdict->keys.value.packed;\ 113 register const ref_packed *kp;\ 114 for ( kp = kbot + dict_hash_mod(hash, size) + 1; ; kp-- )\ 115 packed_search_body(found1,found2,del,miss) 116 #define packed_search_2(found1,found2,del,miss)\ 117 for ( kp += size; ; kp-- )\ 118 packed_search_body(found1,found2,del,miss) 119 120 #endif /* idictdef_INCLUDED */ 121