Commit | Line | Data |
---|---|---|
a6425fa5 WJ |
1 | /* Copyright (C) 1989, 1992 Aladdin Enterprises. All rights reserved. |
2 | Distributed by Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of Ghostscript. | |
5 | ||
6 | Ghostscript is distributed in the hope that it will be useful, but | |
7 | WITHOUT ANY WARRANTY. No author or distributor accepts responsibility | |
8 | to anyone for the consequences of using it or for whether it serves any | |
9 | particular purpose or works at all, unless he says so in writing. Refer | |
10 | to the Ghostscript General Public License for full details. | |
11 | ||
12 | Everyone is granted permission to copy, modify and redistribute | |
13 | Ghostscript, but only under the conditions described in the Ghostscript | |
14 | General Public License. A copy of this license is supposed to have been | |
15 | given to you along with Ghostscript so you can know your rights and | |
16 | responsibilities. It should be in a file named COPYING. Among other | |
17 | things, the copyright notice and this notice must be preserved on all | |
18 | copies. */ | |
19 | ||
20 | /* iname.c */ | |
21 | /* Name lookup for Ghostscript interpreter */ | |
22 | #include "memory_.h" | |
23 | #include "ghost.h" | |
24 | #include "alloc.h" | |
25 | #include "errors.h" | |
26 | #include "name.h" | |
27 | #include "store.h" | |
28 | ||
29 | /* Definitions and structure for the name table. */ | |
30 | /* The first entry is left unused. */ | |
31 | /* 1-character names are the next nt_1char_size entries. */ | |
32 | #define nt_log2_sub_size 7 | |
33 | #define nt_sub_size (1 << nt_log2_sub_size) | |
34 | #define nt_sub_index_mask (nt_sub_size - 1) | |
35 | #define nt_hash_size 256 /* must be a power of 2 */ | |
36 | #define nt_1char_size 256 /* must cover a full byte */ | |
37 | typedef name name_sub_table[nt_sub_size]; | |
38 | typedef struct { | |
39 | ushort hash[nt_hash_size]; | |
40 | name *table[1 << (16 - nt_log2_sub_size)]; /* name_sub_table */ | |
41 | ref count; /* t_integer */ | |
42 | #define nt_count(nt) (uint)((nt)->count.value.intval) | |
43 | #define set_nt_count(nt,cnt) ((nt)->count.value.intval = (cnt)) | |
44 | } name_table; | |
45 | #define name_index_ptr(nt, index)\ | |
46 | ((nt)->table[(index) >> nt_log2_sub_size] + ((index) & nt_sub_index_mask)) | |
47 | ||
48 | /* | |
49 | * Scramble the assignment order within a sub-table, so that | |
50 | * dictionary lookup doesn't have to scramble the index. | |
51 | * The algorithm must have three properties: | |
52 | * - It must map 0 to 0; | |
53 | * - It must only scramble the sub-table index; | |
54 | * - It must be a permutation on the sub-table index. | |
55 | * We do something very simple for now. | |
56 | */ | |
57 | #define name_count_to_index(cnt)\ | |
58 | (((cnt) & (-nt_sub_size)) + (((cnt) * 59) & nt_sub_index_mask)) | |
59 | /* We also store the reverse permutation, for age checking in restore. */ | |
60 | #define name_index_to_count(idx)\ | |
61 | ((idx) ^ name_sub_index_to_count[(idx) & nt_sub_index_mask]) | |
62 | #if nt_sub_size <= 256 | |
63 | private byte name_sub_index_to_count[nt_sub_size]; | |
64 | #else | |
65 | private ushort name_sub_index_to_count[nt_sub_size]; | |
66 | #endif | |
67 | ||
68 | /* The one and only name table (for now). */ | |
69 | private name_table *the_nt; | |
70 | ||
71 | /* Forward references */ | |
72 | private int name_alloc_sub(P1(name_table *)); | |
73 | ||
74 | /* Make a t_name ref out of a name * */ | |
75 | #define make_name(pref, pnm) make_tv(pref, t_name, pname, pnm) | |
76 | ||
77 | /* Initialize the name table */ | |
78 | void | |
79 | name_init() | |
80 | { register uint i; | |
81 | /* Initialize the index_to_count map. */ | |
82 | for ( i = 0; i < nt_sub_size; i++ ) | |
83 | { uint idx = name_count_to_index(i); | |
84 | name_sub_index_to_count[idx] = idx ^ i; | |
85 | } | |
86 | the_nt = (name_table *)alloc(1, sizeof(name_table), "name_init"); | |
87 | memset(the_nt, 0, sizeof(name_table)); | |
88 | make_int(&the_nt->count, 1); | |
89 | for ( i = 0; i <= nt_1char_size; i += nt_sub_size ) | |
90 | { set_nt_count(the_nt, i + 1); | |
91 | name_alloc_sub(the_nt); | |
92 | } | |
93 | } | |
94 | ||
95 | /* Look up or enter a name in the table. */ | |
96 | /* Return 0 or an error code. */ | |
97 | /* The return may overlap the characters of the string! */ | |
98 | /* See name.h for the meaning of enterflag. */ | |
99 | int | |
100 | name_ref(const byte *ptr, uint isize, ref *pref, int enterflag) | |
101 | { register name *pname; | |
102 | const byte *cptr; | |
103 | ushort size = (ushort)isize; /* see name.h */ | |
104 | if ( size == 1 ) | |
105 | { uint ccnt = *ptr + 1; | |
106 | uint nidx = name_count_to_index(ccnt); | |
107 | pname = name_index_ptr(the_nt, nidx); | |
108 | if ( pname->string_size != 0 ) | |
109 | { make_name(pref, pname); | |
110 | return 0; | |
111 | } | |
112 | if ( enterflag < 0 ) return e_undefined; | |
113 | pname->index = nidx; | |
114 | pname->next_index = 0; | |
115 | if_debug4('n', "[n]new name 0x%lx#%u, length=%u, count=%u\n", | |
116 | (ulong)pname, nidx, isize, ccnt); | |
117 | } | |
118 | else | |
119 | { ushort *phash = | |
120 | the_nt->hash + | |
121 | ((ushort)string_hash(ptr, size) & (nt_hash_size - 1)); | |
122 | uint nidx = *phash; | |
123 | uint ncnt; | |
124 | while ( nidx != 0 ) | |
125 | { pname = name_index_ptr(the_nt, nidx); | |
126 | if ( pname->string_size == size && | |
127 | !memcmp(ptr, pname->string_bytes, size) | |
128 | ) | |
129 | { make_name(pref, pname); | |
130 | return 0; | |
131 | } | |
132 | nidx = pname->next_index; | |
133 | } | |
134 | /* Not in table, allocate a new entry. */ | |
135 | if ( enterflag < 0 ) return e_undefined; | |
136 | if ( !(nt_count(the_nt) & (nt_sub_size - 1)) ) | |
137 | { int code = name_alloc_sub(the_nt); | |
138 | if ( code < 0 ) return code; | |
139 | } | |
140 | ncnt = nt_count(the_nt); | |
141 | nidx = name_count_to_index(ncnt); | |
142 | pname = name_index_ptr(the_nt, nidx); | |
143 | pname->index = nidx; | |
144 | pname->next_index = *phash; | |
145 | *phash = nidx; | |
146 | if_debug4('n', "[n]new name 0x%lx#%u, length=%u, count=%u\n", | |
147 | (ulong)pname, nidx, isize, ncnt); | |
148 | ref_save(&the_nt->count, "name_ref(count)"); | |
149 | set_nt_count(the_nt, ncnt + 1); | |
150 | } | |
151 | /* Name was not in the table. Make a new entry. */ | |
152 | if ( enterflag ) | |
153 | { cptr = (const byte *)alloc(size, 1, "name_ref(string)"); | |
154 | if ( cptr == 0 ) return e_VMerror; | |
155 | memcpy((byte *)cptr, ptr, size); | |
156 | } | |
157 | else | |
158 | cptr = ptr; | |
159 | pname->string_size = size; | |
160 | pname->string_bytes = cptr; | |
161 | pname->pvalue = pv_no_defn; | |
162 | make_name(pref, pname); | |
163 | return 0; | |
164 | } | |
165 | ||
166 | /* Get the string for a name. */ | |
167 | void | |
168 | name_string_ref(const ref *pnref /* t_name */, | |
169 | ref *psref /* result, t_string */) | |
170 | { name *pname = pnref->value.pname; | |
171 | make_tasv(psref, t_string, a_read+a_execute, pname->string_size, | |
172 | bytes, (byte *)pname->string_bytes); | |
173 | } | |
174 | ||
175 | /* Convert a t_string object to a name. */ | |
176 | /* Copy the executable attribute. */ | |
177 | int | |
178 | name_from_string(const ref *psref, ref *pnref) | |
179 | { int exec = r_has_attr(psref, a_executable); | |
180 | int code = name_ref(psref->value.bytes, r_size(psref), pnref, 1); | |
181 | if ( code < 0 ) return code; | |
182 | if ( exec ) r_set_attrs(pnref, a_executable); | |
183 | return code; | |
184 | } | |
185 | ||
186 | /* Enter a name during initialization. */ | |
187 | /* Fatal error if the entry fails. */ | |
188 | void | |
189 | name_enter(const char *str, ref *pref) | |
190 | { if ( name_ref((const byte *)str, strlen(str), pref, 0) ) | |
191 | lprintf1("name_enter failed - %s", str), | |
192 | gs_exit(1); | |
193 | } | |
194 | ||
195 | /* Get the name with a given index. */ | |
196 | void | |
197 | name_index_ref(uint index, ref *pnref) | |
198 | { make_name(pnref, name_index_ptr(the_nt, index)); | |
199 | } | |
200 | ||
201 | /* Get the current name count. */ | |
202 | uint | |
203 | name_count() | |
204 | { return nt_count(the_nt); | |
205 | } | |
206 | ||
207 | /* Check whether a name was created since a given count. */ | |
208 | int | |
209 | name_is_since_count(ref *pnref, uint cnt) | |
210 | { return name_index_to_count(name_index(pnref)) >= cnt; | |
211 | } | |
212 | ||
213 | /* Clean up the name table before a restore. */ | |
214 | /* The count will be reset, and added subtables will be freed. */ | |
215 | /* All we have to do is remove initial entries from the hash chains, */ | |
216 | /* since we know they are linked in decreasing index order */ | |
217 | /* (by sub-table, but not within each sub-table.) */ | |
218 | /* (There will be some spurious non-zero entries in the subtable table, */ | |
219 | /* but this doesn't matter since they will never be accessed.) */ | |
220 | void | |
221 | name_restore(uint old_count) | |
222 | { ushort *phash = &the_nt->hash[0]; | |
223 | uint old_sub = old_count & -nt_sub_size; | |
224 | register uint i; | |
225 | for ( i = 0; i < nt_hash_size; phash++, i++ ) | |
226 | { register ushort *pnh = phash; | |
227 | while ( *pnh >= old_sub ) | |
228 | { if ( name_index_to_count(*pnh) < old_count ) | |
229 | pnh = &name_index_ptr(the_nt, *pnh)->next_index; | |
230 | else | |
231 | *pnh = name_index_ptr(the_nt, *pnh)->next_index; | |
232 | } | |
233 | } | |
234 | } | |
235 | ||
236 | /* ------ Internal procedures ------ */ | |
237 | ||
238 | /* Allocate the next sub-table. */ | |
239 | private int | |
240 | name_alloc_sub(name_table *nt) | |
241 | { name *sub = (name *)alloc(1, sizeof(name_sub_table), "name_alloc_sub"); | |
242 | if ( sub == 0 ) return e_VMerror; | |
243 | memset(sub, 0, sizeof(name_sub_table)); | |
244 | nt->table[nt_count(nt) >> nt_log2_sub_size] = sub; | |
245 | return 0; | |
246 | } |