Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/mujs/jsproperty.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 #include "jsi.h"
2
3 #include <assert.h>
4
5 /*
6 Use an AA-tree to quickly look up properties in objects:
7
8 The level of every leaf node is one.
9 The level of every left child is one less than its parent.
10 The level of every right child is equal or one less than its parent.
11 The level of every right grandchild is less than its grandparent.
12 Every node of level greater than one has two children.
13
14 A link where the child's level is equal to that of its parent is called a horizontal link.
15 Individual right horizontal links are allowed, but consecutive ones are forbidden.
16 Left horizontal links are forbidden.
17
18 skew() fixes left horizontal links.
19 split() fixes consecutive right horizontal links.
20 */
21
22 static js_Property sentinel = {
23 &sentinel, &sentinel,
24 0, 0,
25 { { {0}, JS_TUNDEFINED } },
26 NULL, NULL, ""
27 };
28
29 static js_Property *newproperty(js_State *J, js_Object *obj, const char *name)
30 {
31 int n = strlen(name) + 1;
32 js_Property *node = js_malloc(J, offsetof(js_Property, name) + n);
33 node->left = node->right = &sentinel;
34 node->level = 1;
35 node->atts = 0;
36 node->value.t.type = JS_TUNDEFINED;
37 node->value.u.number = 0;
38 node->getter = NULL;
39 node->setter = NULL;
40 memcpy(node->name, name, n);
41 ++obj->count;
42 ++J->gccounter;
43 return node;
44 }
45
46 static js_Property *lookup(js_Property *node, const char *name)
47 {
48 while (node != &sentinel) {
49 int c = strcmp(name, node->name);
50 if (c == 0)
51 return node;
52 else if (c < 0)
53 node = node->left;
54 else
55 node = node->right;
56 }
57 return NULL;
58 }
59
60 static js_Property *skew(js_Property *node)
61 {
62 if (node->left->level == node->level) {
63 js_Property *temp = node;
64 node = node->left;
65 temp->left = node->right;
66 node->right = temp;
67 }
68 return node;
69 }
70
71 static js_Property *split(js_Property *node)
72 {
73 if (node->right->right->level == node->level) {
74 js_Property *temp = node;
75 node = node->right;
76 temp->right = node->left;
77 node->left = temp;
78 ++node->level;
79 }
80 return node;
81 }
82
83 static js_Property *insert(js_State *J, js_Object *obj, js_Property *node, const char *name, js_Property **result)
84 {
85 if (node != &sentinel) {
86 int c = strcmp(name, node->name);
87 if (c < 0)
88 node->left = insert(J, obj, node->left, name, result);
89 else if (c > 0)
90 node->right = insert(J, obj, node->right, name, result);
91 else
92 return *result = node;
93 node = skew(node);
94 node = split(node);
95 return node;
96 }
97 return *result = newproperty(J, obj, name);
98 }
99
100 static void freeproperty(js_State *J, js_Object *obj, js_Property *node)
101 {
102 js_free(J, node);
103 --obj->count;
104 }
105
106 static js_Property *unlinkproperty(js_Property *node, const char *name, js_Property **garbage)
107 {
108 js_Property *temp, *a, *b;
109 if (node != &sentinel) {
110 int c = strcmp(name, node->name);
111 if (c < 0) {
112 node->left = unlinkproperty(node->left, name, garbage);
113 } else if (c > 0) {
114 node->right = unlinkproperty(node->right, name, garbage);
115 } else {
116 *garbage = node;
117 if (node->left == &sentinel && node->right == &sentinel) {
118 return &sentinel;
119 }
120 else if (node->left == &sentinel) {
121 a = node->right;
122 while (a->left != &sentinel)
123 a = a->left;
124 b = unlinkproperty(node->right, a->name, &temp);
125 temp->level = node->level;
126 temp->left = node->left;
127 temp->right = b;
128 node = temp;
129 }
130 else {
131 a = node->left;
132 while (a->right != &sentinel)
133 a = a->right;
134 b = unlinkproperty(node->left, a->name, &temp);
135 temp->level = node->level;
136 temp->left = b;
137 temp->right = node->right;
138 node = temp;
139 }
140 }
141
142 if (node->left->level < node->level - 1 || node->right->level < node->level - 1)
143 {
144 if (node->right->level > --node->level)
145 node->right->level = node->level;
146 node = skew(node);
147 node->right = skew(node->right);
148 node->right->right = skew(node->right->right);
149 node = split(node);
150 node->right = split(node->right);
151 }
152 }
153 return node;
154 }
155
156 static js_Property *deleteproperty(js_State *J, js_Object *obj, js_Property *tree, const char *name)
157 {
158 js_Property *garbage = &sentinel;
159 tree = unlinkproperty(tree, name, &garbage);
160 if (garbage != &sentinel)
161 freeproperty(J, obj, garbage);
162 return tree;
163 }
164
165 js_Object *jsV_newobject(js_State *J, enum js_Class type, js_Object *prototype)
166 {
167 js_Object *obj = js_malloc(J, sizeof *obj);
168 memset(obj, 0, sizeof *obj);
169 obj->gcmark = 0;
170 obj->gcnext = J->gcobj;
171 J->gcobj = obj;
172 ++J->gccounter;
173
174 obj->type = type;
175 obj->properties = &sentinel;
176 obj->prototype = prototype;
177 obj->extensible = 1;
178 return obj;
179 }
180
181 js_Property *jsV_getownproperty(js_State *J, js_Object *obj, const char *name)
182 {
183 return lookup(obj->properties, name);
184 }
185
186 js_Property *jsV_getpropertyx(js_State *J, js_Object *obj, const char *name, int *own)
187 {
188 *own = 1;
189 do {
190 js_Property *ref = lookup(obj->properties, name);
191 if (ref)
192 return ref;
193 obj = obj->prototype;
194 *own = 0;
195 } while (obj);
196 return NULL;
197 }
198
199 js_Property *jsV_getproperty(js_State *J, js_Object *obj, const char *name)
200 {
201 do {
202 js_Property *ref = lookup(obj->properties, name);
203 if (ref)
204 return ref;
205 obj = obj->prototype;
206 } while (obj);
207 return NULL;
208 }
209
210 static js_Property *jsV_getenumproperty(js_State *J, js_Object *obj, const char *name)
211 {
212 do {
213 js_Property *ref = lookup(obj->properties, name);
214 if (ref && !(ref->atts & JS_DONTENUM))
215 return ref;
216 obj = obj->prototype;
217 } while (obj);
218 return NULL;
219 }
220
221 js_Property *jsV_setproperty(js_State *J, js_Object *obj, const char *name)
222 {
223 js_Property *result;
224
225 if (!obj->extensible) {
226 result = lookup(obj->properties, name);
227 if (J->strict && !result)
228 js_typeerror(J, "object is non-extensible");
229 return result;
230 }
231
232 obj->properties = insert(J, obj, obj->properties, name, &result);
233
234 return result;
235 }
236
237 void jsV_delproperty(js_State *J, js_Object *obj, const char *name)
238 {
239 obj->properties = deleteproperty(J, obj, obj->properties, name);
240 }
241
242 /* Flatten hierarchy of enumerable properties into an iterator object */
243
244 static js_Iterator *itnewnode(js_State *J, const char *name, js_Iterator *next) {
245 int n = strlen(name) + 1;
246 js_Iterator *node = js_malloc(J, offsetof(js_Iterator, name) + n);
247 node->next = next;
248 memcpy(node->name, name, n);
249 return node;
250 }
251
252 static js_Iterator *itwalk(js_State *J, js_Iterator *iter, js_Property *prop, js_Object *seen)
253 {
254 if (prop->right != &sentinel)
255 iter = itwalk(J, iter, prop->right, seen);
256 if (!(prop->atts & JS_DONTENUM)) {
257 if (!seen || !jsV_getenumproperty(J, seen, prop->name)) {
258 iter = itnewnode(J, prop->name, iter);
259 }
260 }
261 if (prop->left != &sentinel)
262 iter = itwalk(J, iter, prop->left, seen);
263 return iter;
264 }
265
266 static js_Iterator *itflatten(js_State *J, js_Object *obj)
267 {
268 js_Iterator *iter = NULL;
269 if (obj->prototype)
270 iter = itflatten(J, obj->prototype);
271 if (obj->properties != &sentinel)
272 iter = itwalk(J, iter, obj->properties, obj->prototype);
273 return iter;
274 }
275
276 js_Object *jsV_newiterator(js_State *J, js_Object *obj, int own)
277 {
278 js_Object *io = jsV_newobject(J, JS_CITERATOR, NULL);
279 io->u.iter.target = obj;
280 io->u.iter.i = 0;
281 io->u.iter.n = 0;
282 if (own) {
283 io->u.iter.head = NULL;
284 if (obj->properties != &sentinel)
285 io->u.iter.head = itwalk(J, io->u.iter.head, obj->properties, NULL);
286 } else {
287 io->u.iter.head = itflatten(J, obj);
288 }
289 io->u.iter.current = io->u.iter.head;
290
291 if (obj->type == JS_CSTRING)
292 io->u.iter.n = obj->u.s.length;
293
294 if (obj->type == JS_CARRAY && obj->u.a.simple)
295 io->u.iter.n = obj->u.a.flat_length;
296
297 return io;
298 }
299
300 const char *jsV_nextiterator(js_State *J, js_Object *io)
301 {
302 if (io->type != JS_CITERATOR)
303 js_typeerror(J, "not an iterator");
304 if (io->u.iter.i < io->u.iter.n) {
305 js_itoa(J->scratch, io->u.iter.i);
306 io->u.iter.i++;
307 return J->scratch;
308 }
309 while (io->u.iter.current) {
310 const char *name = io->u.iter.current->name;
311 io->u.iter.current = io->u.iter.current->next;
312 if (jsV_getproperty(J, io->u.iter.target, name))
313 return name;
314 }
315 return NULL;
316 }
317
318 /* Walk all the properties and delete them one by one for arrays */
319
320 void jsV_resizearray(js_State *J, js_Object *obj, int newlen)
321 {
322 char buf[32];
323 const char *s;
324 int k;
325 assert(!obj->u.a.simple);
326 if (newlen < obj->u.a.length) {
327 if (obj->u.a.length > obj->count * 2) {
328 js_Object *it = jsV_newiterator(J, obj, 1);
329 while ((s = jsV_nextiterator(J, it))) {
330 k = jsV_numbertointeger(jsV_stringtonumber(J, s));
331 if (k >= newlen && !strcmp(s, jsV_numbertostring(J, buf, k)))
332 jsV_delproperty(J, obj, s);
333 }
334 } else {
335 for (k = newlen; k < obj->u.a.length; ++k) {
336 jsV_delproperty(J, obj, js_itoa(buf, k));
337 }
338 }
339 }
340 obj->u.a.length = newlen;
341 }