| 2 |
- |
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 */
|