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