1 /*
2 * This file is part of libdom.
3 * Licensed under the MIT License,
4 * http://www.opensource.org/licenses/mit-license.php
5 * Copyright 2007 John-Mark Bell <jmb@netsurf-browser.org>
6 * Copyright 2009 Bo Yang <struggleyb.nku@gmail.com>
7 */
8
9 #include <assert.h>
10 #include <stdlib.h>
11
12 #include <dom/core/node.h>
13 #include <dom/core/document.h>
14 #include <dom/core/nodelist.h>
15 #include <dom/core/string.h>
16
17 #include "core/document.h"
18 #include "core/node.h"
19 #include "core/nodelist.h"
20
21 #include "utils/utils.h"
22
23 /**
24 * DOM node list
25 */
26 struct dom_nodelist {
27 dom_document *owner; /**< Owning document */
28
29 dom_node_internal *root;
30 /**< Root of applicable subtree */
31
32 nodelist_type type; /**< Type of this list */
33
34 union {
35 struct {
36 dom_string *name;
37 /**< Tag name to match */
38 bool any_name; /**< The name is '*' */
39 } n;
40 struct {
41 bool any_namespace; /**< The namespace is '*' */
42 bool any_localname; /**< The localname is '*' */
43 dom_string *namespace; /**< Namespace */
44 dom_string *localname; /**< Localname */
45 } ns; /**< Data for namespace matching */
46 } data;
47
48 uint32_t refcnt; /**< Reference count */
49 };
50
51 /**
52 * Create a nodelist
53 *
54 * \param doc Owning document
55 * \param type The type of the NodeList
56 * \param root Root node of subtree that list applies to
57 * \param tagname Name of nodes in list (or NULL)
58 * \param namespace Namespace part of nodes in list (or NULL)
59 * \param localname Local part of nodes in list (or NULL)
60 * \param list Pointer to location to receive list
61 * \return DOM_NO_ERR on success, DOM_NO_MEM_ERR on memory exhaustion
62 *
63 * ::root must be a node owned by ::doc
64 *
65 * The returned list will already be referenced, so the client need not
66 * do so explicitly. The client must unref the list once finished with it.
67 */
_dom_nodelist_create(dom_document * doc,nodelist_type type,dom_node_internal * root,dom_string * tagname,dom_string * namespace,dom_string * localname,dom_nodelist ** list)68 dom_exception _dom_nodelist_create(dom_document *doc, nodelist_type type,
69 dom_node_internal *root, dom_string *tagname,
70 dom_string *namespace, dom_string *localname,
71 dom_nodelist **list)
72 {
73 dom_nodelist *l;
74
75 l = malloc(sizeof(dom_nodelist));
76 if (l == NULL)
77 return DOM_NO_MEM_ERR;
78
79 dom_node_ref(doc);
80 l->owner = doc;
81
82 dom_node_ref(root);
83 l->root = root;
84
85 l->type = type;
86
87 if (type == DOM_NODELIST_BY_NAME ||
88 type == DOM_NODELIST_BY_NAME_CASELESS) {
89 assert(tagname != NULL);
90 l->data.n.any_name = false;
91 if (dom_string_byte_length(tagname) == 1) {
92 const char *ch = dom_string_data(tagname);
93 if (*ch == '*') {
94 l->data.n.any_name = true;
95 }
96 }
97
98 l->data.n.name = dom_string_ref(tagname);
99 } else if (type == DOM_NODELIST_BY_NAMESPACE ||
100 type == DOM_NODELIST_BY_NAMESPACE_CASELESS) {
101 l->data.ns.any_localname = false;
102 l->data.ns.any_namespace = false;
103 if (localname != NULL) {
104 if (dom_string_byte_length(localname) == 1) {
105 const char *ch = dom_string_data(localname);
106 if (*ch == '*') {
107 l->data.ns.any_localname = true;
108 }
109 }
110 dom_string_ref(localname);
111 }
112 if (namespace != NULL) {
113 if (dom_string_byte_length(namespace) == 1) {
114 const char *ch = dom_string_data(namespace);
115 if (*ch == '*') {
116 l->data.ns.any_namespace = true;
117 }
118 }
119 dom_string_ref(namespace);
120 }
121
122 l->data.ns.namespace = namespace;
123 l->data.ns.localname = localname;
124 }
125
126 l->refcnt = 1;
127
128 *list = l;
129
130 return DOM_NO_ERR;
131 }
132
133 /**
134 * Claim a reference on a DOM node list
135 *
136 * \param list The list to claim a reference on
137 */
dom_nodelist_ref(dom_nodelist * list)138 void dom_nodelist_ref(dom_nodelist *list)
139 {
140 assert(list != NULL);
141 list->refcnt++;
142 }
143
144 /**
145 * Release a reference on a DOM node list
146 *
147 * \param list The list to release the reference from
148 *
149 * If the reference count reaches zero, any memory claimed by the
150 * list will be released
151 */
dom_nodelist_unref(dom_nodelist * list)152 void dom_nodelist_unref(dom_nodelist *list)
153 {
154 if (list == NULL)
155 return;
156
157 if (--list->refcnt == 0) {
158 dom_node_internal *owner = (dom_node_internal *) list->owner;
159 switch (list->type) {
160 case DOM_NODELIST_CHILDREN:
161 /* Nothing to do */
162 break;
163 case DOM_NODELIST_BY_NAMESPACE:
164 case DOM_NODELIST_BY_NAMESPACE_CASELESS:
165 if (list->data.ns.namespace != NULL)
166 dom_string_unref(list->data.ns.namespace);
167 if (list->data.ns.localname != NULL)
168 dom_string_unref(list->data.ns.localname);
169 break;
170 case DOM_NODELIST_BY_NAME:
171 case DOM_NODELIST_BY_NAME_CASELESS:
172 assert(list->data.n.name != NULL);
173 dom_string_unref(list->data.n.name);
174 break;
175 }
176
177 dom_node_unref(list->root);
178
179 /* Remove list from document */
180 _dom_document_remove_nodelist(list->owner, list);
181
182 /* Destroy the list object */
183 free(list);
184
185 /* And release our reference on the owning document
186 * This must be last as, otherwise, it's possible that
187 * the document is destroyed before we are */
188 dom_node_unref(owner);
189 }
190 }
191
192 /**
193 * Retrieve the length of a node list
194 *
195 * \param list List to retrieve length of
196 * \param length Pointer to location to receive length
197 * \return DOM_NO_ERR.
198 */
dom_nodelist_get_length(dom_nodelist * list,uint32_t * length)199 dom_exception dom_nodelist_get_length(dom_nodelist *list, uint32_t *length)
200 {
201 dom_node_internal *cur = list->root->first_child;
202 uint32_t len = 0;
203
204 /* Traverse data structure */
205 while (cur != NULL) {
206 /* Process current node */
207 if (list->type == DOM_NODELIST_CHILDREN) {
208 len++;
209 } else if (list->type == DOM_NODELIST_BY_NAME) {
210 if (list->data.n.any_name == true || (
211 cur->name != NULL &&
212 dom_string_isequal(cur->name,
213 list->data.n.name))) {
214 if (cur->type == DOM_ELEMENT_NODE)
215 len++;
216 }
217 } else if (list->type == DOM_NODELIST_BY_NAME_CASELESS) {
218 if (list->data.n.any_name == true || (
219 cur->name != NULL &&
220 dom_string_caseless_isequal(cur->name,
221 list->data.n.name))) {
222 if (cur->type == DOM_ELEMENT_NODE)
223 len++;
224 }
225 } else if (list->type == DOM_NODELIST_BY_NAMESPACE) {
226 if (list->data.ns.any_namespace == true ||
227 dom_string_isequal(cur->namespace,
228 list->data.ns.namespace)) {
229 if (list->data.ns.any_localname == true ||
230 (cur->name != NULL &&
231 dom_string_isequal(cur->name,
232 list->data.ns.localname))) {
233 if (cur->type == DOM_ELEMENT_NODE)
234 len++;
235 }
236 }
237 } else if (list->type == DOM_NODELIST_BY_NAMESPACE_CASELESS) {
238 if (list->data.ns.any_namespace == true ||
239 dom_string_caseless_isequal(
240 cur->namespace,
241 list->data.ns.namespace)) {
242 if (list->data.ns.any_localname == true ||
243 (cur->name != NULL &&
244 dom_string_caseless_isequal(
245 cur->name,
246 list->data.ns.localname))) {
247 if (cur->type == DOM_ELEMENT_NODE)
248 len++;
249 }
250 }
251 } else {
252 assert("Unknown list type" == NULL);
253 }
254
255 /* Now, find next node */
256 if (list->type == DOM_NODELIST_CHILDREN) {
257 /* Just interested in sibling list */
258 cur = cur->next;
259 } else {
260 /* Want a full in-order tree traversal */
261 if (cur->first_child != NULL) {
262 /* Has children */
263 cur = cur->first_child;
264 } else if (cur->next != NULL) {
265 /* No children, but has siblings */
266 cur = cur->next;
267 } else {
268 /* No children or siblings.
269 * Find first unvisited relation. */
270 dom_node_internal *parent = cur->parent;
271
272 while (parent != list->root &&
273 cur == parent->last_child) {
274 cur = parent;
275 parent = parent->parent;
276 }
277
278 cur = cur->next;
279 }
280 }
281 }
282
283 *length = len;
284
285 return DOM_NO_ERR;
286 }
287
288 /**
289 * Retrieve an item from a node list
290 *
291 * \param list The list to retrieve the item from
292 * \param index The list index to retrieve
293 * \param node Pointer to location to receive item
294 * \return DOM_NO_ERR.
295 *
296 * ::index is a zero-based index into ::list.
297 * ::index lies in the range [0, length-1]
298 *
299 * The returned node will have had its reference count increased. The client
300 * should unref the node once it has finished with it.
301 *
302 * NOTE: If \ref node contains a node pointer already, it will *NOT* be
303 * unreffed. Managing the lifetime of that is up to the caller.
304 */
_dom_nodelist_item(dom_nodelist * list,uint32_t index,dom_node ** node)305 dom_exception _dom_nodelist_item(dom_nodelist *list,
306 uint32_t index, dom_node **node)
307 {
308 dom_node_internal *cur = list->root->first_child;
309 uint32_t count = 0;
310
311 /* Traverse data structure */
312 while (cur != NULL) {
313 /* Process current node */
314 if (list->type == DOM_NODELIST_CHILDREN) {
315 count++;
316 } else if (list->type == DOM_NODELIST_BY_NAME) {
317 if (list->data.n.any_name == true || (
318 cur->name != NULL &&
319 dom_string_isequal(cur->name,
320 list->data.n.name))) {
321 if (cur->type == DOM_ELEMENT_NODE)
322 count++;
323 }
324 } else if (list->type == DOM_NODELIST_BY_NAME_CASELESS) {
325 if (list->data.n.any_name == true || (
326 cur->name != NULL &&
327 dom_string_caseless_isequal(cur->name,
328 list->data.n.name))) {
329 if (cur->type == DOM_ELEMENT_NODE)
330 count++;
331 }
332 } else if (list->type == DOM_NODELIST_BY_NAMESPACE) {
333 if (list->data.ns.any_namespace == true ||
334 (cur->namespace != NULL &&
335 dom_string_isequal(cur->namespace,
336 list->data.ns.namespace))) {
337 if (list->data.ns.any_localname == true ||
338 (cur->name != NULL &&
339 dom_string_isequal(cur->name,
340 list->data.ns.localname))) {
341 if (cur->type == DOM_ELEMENT_NODE)
342 count++;
343 }
344 }
345 } else if (list->type == DOM_NODELIST_BY_NAMESPACE_CASELESS) {
346 if (list->data.ns.any_namespace == true ||
347 (cur->namespace != NULL &&
348 dom_string_caseless_isequal(
349 cur->namespace,
350 list->data.ns.namespace))) {
351 if (list->data.ns.any_localname == true ||
352 (cur->name != NULL &&
353 dom_string_caseless_isequal(
354 cur->name,
355 list->data.ns.localname))) {
356 if (cur->type == DOM_ELEMENT_NODE)
357 count++;
358 }
359 }
360 } else {
361 assert("Unknown list type" == NULL);
362 }
363
364 /* Stop if this is the requested index */
365 if ((index + 1) == count) {
366 break;
367 }
368
369 /* Now, find next node */
370 if (list->type == DOM_NODELIST_CHILDREN) {
371 /* Just interested in sibling list */
372 cur = cur->next;
373 } else {
374 /* Want a full in-order tree traversal */
375 if (cur->first_child != NULL) {
376 /* Has children */
377 cur = cur->first_child;
378 } else if (cur->next != NULL) {
379 /* No children, but has siblings */
380 cur = cur->next;
381 } else {
382 /* No children or siblings.
383 * Find first unvisited relation. */
384 dom_node_internal *parent = cur->parent;
385
386 while (parent != list->root &&
387 cur == parent->last_child) {
388 cur = parent;
389 parent = parent->parent;
390 }
391
392 cur = cur->next;
393 }
394 }
395 }
396
397 if (cur != NULL) {
398 dom_node_ref(cur);
399 }
400 *node = (dom_node *) cur;
401
402 return DOM_NO_ERR;
403 }
404
405 /**
406 * Match a nodelist instance against a set of nodelist creation parameters
407 *
408 * \param list List to match
409 * \param type The type of the NodeList
410 * \param root Root node of subtree that list applies to
411 * \param tagname Name of nodes in list (or NULL)
412 * \param namespace Namespace part of nodes in list (or NULL)
413 * \param localname Local part of nodes in list (or NULL)
414 * \return true if list matches, false otherwise
415 */
_dom_nodelist_match(dom_nodelist * list,nodelist_type type,dom_node_internal * root,dom_string * tagname,dom_string * namespace,dom_string * localname)416 bool _dom_nodelist_match(dom_nodelist *list, nodelist_type type,
417 dom_node_internal *root, dom_string *tagname,
418 dom_string *namespace, dom_string *localname)
419 {
420 if (list->root != root)
421 return false;
422
423 if (list->type != type)
424 return false;
425
426 switch (list->type) {
427 case DOM_NODELIST_CHILDREN:
428 return true;
429 case DOM_NODELIST_BY_NAME:
430 return dom_string_isequal(list->data.n.name, tagname);
431 case DOM_NODELIST_BY_NAMESPACE:
432 return dom_string_isequal(list->data.ns.namespace, namespace) &&
433 dom_string_isequal(list->data.ns.localname, localname);
434 case DOM_NODELIST_BY_NAME_CASELESS:
435 return dom_string_caseless_isequal(list->data.n.name, tagname);
436 case DOM_NODELIST_BY_NAMESPACE_CASELESS:
437 return dom_string_caseless_isequal(list->data.ns.namespace,
438 namespace) &&
439 dom_string_caseless_isequal(list->data.ns.localname,
440 localname);
441 }
442
443 return false;
444 }
445
446 /**
447 * Test whether the two NodeList are equal
448 *
449 * \param l1 One list
450 * \param l2 The other list
451 * \reutrn true for equal, false otherwise.
452 */
_dom_nodelist_equal(dom_nodelist * l1,dom_nodelist * l2)453 bool _dom_nodelist_equal(dom_nodelist *l1, dom_nodelist *l2)
454 {
455 return _dom_nodelist_match(l1, l1->type, l2->root, l2->data.n.name,
456 l2->data.ns.namespace, l2->data.ns.localname);
457 }
458
459