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: idictdef.h 9043 2008-08-28 22:48:19Z giles $ */ 15 /* Internals of dictionary implementation */ 16 17 #ifndef idictdef_INCLUDED 18 # define idictdef_INCLUDED 19 20 /* 21 * A dictionary of capacity M is a structure containing the following 22 * elements (refs): 23 * 24 * keys - a t_shortarray or t_array of M+1 elements, containing 25 * the keys. 26 * 27 * values - a t_array of M+1 elements, containing the values. 28 * 29 * count - a t_integer whose value tells how many entries are 30 * occupied (N). 31 * 32 * maxlength - a t_integer whose value gives the client's view of 33 * the capacity (C). C may be less than M (see below). 34 * 35 * memory - a foreign t_struct referencing the allocator used to 36 * create this dictionary, which will also be used to expand or 37 * unpack it if necessary. 38 * 39 * C < M is possible because on large-memory systems, we usually round up M 40 * so that M is a power of 2 (see idict.h for details); this allows us to 41 * use masking rather than division for computing the initial hash probe. 42 * However, C is always the maxlength specified by the client, so clients 43 * get a consistent story. 44 * 45 * As noted above, the keys may be either in packed or unpacked form. 46 * The markers for unused and deleted entries are different in the two forms. 47 * In the packed form: 48 * unused entries contain packed_key_empty; 49 * deleted entries contain packed_key_deleted. 50 * In the unpacked form: 51 * unused entries contain a literal null; 52 * deleted entries contain an executable null. 53 * 54 * The first entry is always marked deleted, to reduce the cost of the 55 * wrap-around check. 56 * 57 * Note that if the keys slot in the dictionary is new, 58 * all the key slots are new (more recent than the last save). 59 * We use this fact to avoid saving stores into packed keys 60 * for newly created dictionaries. 61 * 62 * Note that name keys with indices above packed_name_max_index require using 63 * the unpacked form. */ 64 #define dict_is_packed(dct) r_has_type(&(dct)->keys, t_shortarray) 65 #define packed_key_empty (pt_tag(pt_integer) + 0) 66 #define packed_key_deleted (pt_tag(pt_integer) + 1) 67 #define packed_key_impossible pt_tag(pt_full_ref) /* never matches */ 68 #define packed_name_key(nidx)\ 69 ((nidx) <= packed_name_max_index ? pt_tag(pt_literal_name) + (nidx) :\ 70 packed_key_impossible) 71 /* 72 * Using a special mark for deleted entries causes lookup time to degrade 73 * as entries are inserted and deleted. This is not a problem, because 74 * entries are almost never deleted. 75 */ 76 #define d_maxlength(dct) ((uint)((dct)->maxlength.value.intval)) 77 #define d_set_maxlength(dct,siz) ((dct)->maxlength.value.intval = (siz)) 78 #define nslots(dct) r_size(&(dct)->values) 79 #define npairs(dct) (nslots(dct) - 1) 80 #define d_length(dct) ((uint)((dct)->count.value.intval)) 81 82 /* packed_search_value_pointer simplifies the access to 83 packed dictionary search template data - see idicttpl.h . */ 84 #define packed_search_value_pointer (pdict->values.value.refs + (kp - kbot)) 85 86 #endif /* idictdef_INCLUDED */ 87