1 /* DOMC Document Object Model library in C
2 * Copyright (c) 2001 Michael B. Allen <mba2000 ioplex.com>
3 *
4 * The MIT License
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included
14 * in all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
20 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
21 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
22 * OTHER DEALINGS IN THE SOFTWARE.
23 */
24
25 /* nodelist.c - the DOM_NodeList interface
26 */
27
28 #include "defines.h"
29 #include <mba/msgno.h>
30 #include "domc.h"
31 #include "dom.h"
32
33 #if FAST_NODELIST
34
35 /* The number of nodes required in a list before hashing starts */
36 #define FAST_FILLFACTOR 16
37
_removeFromMap(DOM_NodeList * nl,DOM_Node * key)38 static void _removeFromMap(DOM_NodeList* nl, DOM_Node* key)
39 {
40 if (nl->_map) {
41 if (hashmap_get(nl->_map, key) != NULL) {
42 void* d = NULL;
43 void* k = key;
44 hashmap_remove(nl->_map, &k, &d);
45 }
46 }
47 }
48
_addToMap(DOM_NodeList * nl,DOM_Node * key,NodeEntry * val)49 static int _addToMap(DOM_NodeList* nl, DOM_Node* key, NodeEntry* val)
50 {
51 if (!nl->_map && nl->length > FAST_FILLFACTOR) {
52
53 nl->_map = hashmap_new(0, NULL, NULL, NULL);
54
55 /* Hash what we currently have */
56 if (nl->_map) {
57 NodeEntry *e = nl->first;
58 while (e) {
59 _addToMap(nl, e->node, e);
60 e = e->next;
61 }
62 }
63 }
64
65 if (nl->_map) {
66 _removeFromMap(nl, key);
67
68 if (hashmap_put(nl->_map, key, val) == -1) {
69 DOM_Exception = errno;
70 return -1;
71 }
72 }
73
74 return 0;
75 }
76
77 #endif
78
_lookupNode(DOM_NodeList * nl,DOM_Node * node)79 static NodeEntry* _lookupNode(DOM_NodeList* nl, DOM_Node* node)
80 {
81 NodeEntry* s;
82
83 #if FAST_NODELIST
84 if (nl->_map)
85 s = (NodeEntry*)hashmap_get(nl->_map, node);
86 else
87 #endif
88 for (s = nl->first; s != NULL && s->node != node; s = s->next) {
89 ;
90 }
91
92 return s;
93 }
94
95 /* NodeList
96 */
97
98 DOM_NodeList *
Document_createNodeList(DOM_Document * doc)99 Document_createNodeList(DOM_Document *doc)
100 {
101 DOM_NodeList *r;
102
103 if ((r = calloc(sizeof *r, 1)) == NULL) {
104 DOM_Exception = errno;
105 PMNO(DOM_Exception);
106 }
107 r->_ownerDocument = doc;
108
109 return r;
110 }
111 void
DOM_Document_destroyNodeList(DOM_Document * doc,DOM_NodeList * nl,int free_nodes)112 DOM_Document_destroyNodeList(DOM_Document *doc, DOM_NodeList *nl, int free_nodes)
113 {
114 if (nl) {
115 if (nl->filter == 0) {
116 NodeEntry *e, *tmp;
117
118 e = nl->first;
119 while (e != NULL) {
120 if (free_nodes) {
121 DOM_Document_destroyNode(doc, e->node);
122 }
123 tmp = e;
124 e = e->next;
125 free(tmp);
126 }
127 }
128
129 #if FAST_NODELIST
130 if(nl->_map)
131 hashmap_del(nl->_map, NULL, NULL, NULL);
132 #endif
133
134 free(nl);
135 }
136 }
137
138 DOM_Node *
NodeList_itemFiltered(const DOM_NodeList * list,int index,unsigned short nodeType)139 NodeList_itemFiltered(const DOM_NodeList *list, int index, unsigned short nodeType)
140 {
141 if (list && index >= 0 && index < list->length) {
142 NodeEntry *e;
143
144 for (e = list->first; e != NULL; e = e->next) {
145 if (e->node->nodeType == nodeType) {
146 if (index == 0) {
147 return e->node;
148 }
149 index--;
150 }
151 }
152 }
153
154 return NULL;
155 }
156 DOM_Node *
DOM_NodeList_item(const DOM_NodeList * list,int index)157 DOM_NodeList_item(const DOM_NodeList *list, int index)
158 {
159 if (list) {
160 if (list->filter) {
161 return NodeList_itemFiltered(list->list, index, list->filter);
162 }
163
164 if (index >= 0 && index < list->length) {
165 NodeEntry *e;
166
167 for (e = list->first; e != NULL; e = e->next, index--) {
168 if (index == 0) {
169 return e->node;
170 }
171 }
172 }
173 }
174
175 return NULL;
176 }
177 NodeEntry *
NodeList_insert(DOM_NodeList * nl,DOM_Node * newChild,DOM_Node * refChild)178 NodeList_insert(DOM_NodeList *nl, DOM_Node *newChild, DOM_Node *refChild)
179 {
180 NodeEntry *e;
181 NodeEntry *s = NULL;
182
183 if (nl == NULL) {
184 DOM_Exception = NULL_POINTER_ERR;
185 PMNO(DOM_Exception);
186 return NULL;
187 }
188 if (nl->filter) {
189 DOM_Exception = DOM_FILTERED_LIST_ERR;
190 PMNO(DOM_Exception);
191 return NULL;
192 }
193
194 if(refChild != NULL)
195 {
196 s = _lookupNode(nl, refChild);
197 if(s == NULL || s->node != refChild) {
198 DOM_Exception = DOM_NOT_FOUND_ERR;
199 PMNO(DOM_Exception);
200 return NULL;
201 }
202 }
203
204 if ((e = calloc(sizeof *e, 1)) == NULL) {
205 DOM_Exception = errno;
206 PMNO(DOM_Exception);
207 return NULL;
208 }
209
210 #if FAST_NODELIST
211 if (_addToMap(nl, newChild, e) == -1) {
212 PMNO(DOM_Exception);
213 free(e);
214 return NULL;
215 }
216 #endif
217
218 e->node = newChild;
219 if (nl->length == 0) {
220 nl->first = nl->last = e;
221 } else if (refChild == NULL) {
222 e->prev = nl->last;
223 nl->last->next = e;
224 nl->last = e;
225 } else {
226 e->prev = s->prev;
227 e->next = s;
228 if (s == nl->first) {
229 nl->first = e;
230 } else {
231 s->prev->next = e;
232 }
233 s->prev = e;
234 }
235 nl->length++;
236
237 /* If an attribute is being added this is probably a NamedNodeMap
238 * in which case we must set the ownerElement.
239 */
240 if (newChild->nodeType == DOM_ATTRIBUTE_NODE) {
241 newChild->u.Attr.ownerElement = nl->_ownerElement;
242 }
243
244 return e;
245 }
246 NodeEntry *
NodeList_replace(DOM_NodeList * nl,DOM_Node * newChild,DOM_Node * oldChild)247 NodeList_replace(DOM_NodeList *nl, DOM_Node *newChild, DOM_Node *oldChild)
248 {
249 NodeEntry *e;
250
251 if (nl == NULL) {
252 DOM_Exception = NULL_POINTER_ERR;
253 PMNO(DOM_Exception);
254 return NULL;
255 }
256 if (nl->filter) {
257 DOM_Exception = DOM_FILTERED_LIST_ERR;
258 PMNO(DOM_Exception);
259 return NULL;
260 }
261
262 e = _lookupNode(nl, oldChild);
263 if (e == NULL) {
264 DOM_Exception = DOM_NOT_FOUND_ERR;
265 PMNO(DOM_Exception);
266 return NULL;
267 }
268
269 #if FAST_NODELIST
270 _removeFromMap(nl, oldChild);
271 if(_addToMap(nl, newChild, e) == -1) {
272 PMNO(DOM_Exception);
273 return NULL;
274 }
275 #endif
276
277 e->node = newChild;
278
279 if (oldChild->nodeType == DOM_ATTRIBUTE_NODE) {
280 oldChild->u.Attr.ownerElement = NULL;
281 }
282
283 return e;
284 }
285 NodeEntry *
NodeList_remove(DOM_NodeList * nl,DOM_Node * oldChild)286 NodeList_remove(DOM_NodeList *nl, DOM_Node *oldChild)
287 {
288 NodeEntry *e;
289
290 if (nl == NULL) {
291 DOM_Exception = NULL_POINTER_ERR;
292 PMNO(DOM_Exception);
293 return NULL;
294 }
295 if (nl->filter) {
296 DOM_Exception = DOM_FILTERED_LIST_ERR;
297 PMNO(DOM_Exception);
298 return NULL;
299 }
300
301 e = _lookupNode(nl, oldChild);
302 if (e == NULL) {
303 return NULL;
304 }
305
306 #if FAST_NODELIST
307 _removeFromMap(nl, oldChild);
308 #endif
309
310 if (nl->first == nl->last) {
311 nl->first = nl->last = NULL;
312 } else if (e == nl->first) {
313 nl->first = e->next;
314 nl->first->prev = NULL;
315 } else if (e == nl->last) {
316 nl->last = e->prev;
317 nl->last->next = NULL;
318 } else {
319 e->prev->next = e->next;
320 e->next->prev = e->prev;
321 }
322 nl->length--;
323
324 /* Decrement a filtered node list too? */
325
326 if (oldChild->nodeType == DOM_ATTRIBUTE_NODE) {
327 oldChild->u.Attr.ownerElement = NULL;
328 }
329
330 return e;
331 }
332 extern const char *node_names[];
333 NodeEntry *
NodeList_append(DOM_NodeList * nl,DOM_Node * newChild)334 NodeList_append(DOM_NodeList *nl, DOM_Node *newChild)
335 {
336 NodeEntry *e;
337 DOM_DocumentType *doctype;
338
339 if (nl == NULL) {
340 DOM_Exception = NULL_POINTER_ERR;
341 PMNF(DOM_Exception, ": %p", newChild);
342 return NULL;
343 }
344 if (nl->filter) {
345 DOM_Exception = DOM_FILTERED_LIST_ERR;
346 PMNO(DOM_Exception);
347 return NULL;
348 }
349
350 if ((e = calloc(sizeof *e, 1)) == NULL) {
351 DOM_Exception = errno;
352 PMNO(DOM_Exception);
353 return NULL;
354 }
355
356 #if FAST_NODELIST
357 if(_addToMap(nl, newChild, e) == -1) {
358 PMNO(DOM_Exception);
359 free(e);
360 return NULL;
361 }
362 #endif
363
364 e->node = newChild;
365 if (nl->first == NULL) {
366 nl->first = nl->last = e;
367 } else {
368 nl->last->next = e;
369 e->prev = nl->last;
370 nl->last = e;
371 }
372
373 nl->length++;
374
375 /* If the node list is the DocumentType children and a Notation
376 * or Entity is being added we must artificially update the length
377 * member of those filtered lists
378 */
379 if (newChild->ownerDocument &&
380 (doctype = newChild->ownerDocument->u.Document.doctype) &&
381 nl == doctype->childNodes) {
382 if (newChild->nodeType == DOM_NOTATION_NODE) {
383 doctype->u.DocumentType.notations->length++;
384 } else if (newChild->nodeType == DOM_ENTITY_NODE) {
385 doctype->u.DocumentType.entities->length++;
386 }
387 }
388 /* If an attribute is being added this is probably a NamedNodeMap
389 * in which case we must set the ownerElement.
390 */
391 if (newChild->nodeType == DOM_ATTRIBUTE_NODE) {
392 newChild->u.Attr.ownerElement = nl->_ownerElement;
393 }
394
395 return e;
396 }
397 int
NodeList_exists(DOM_NodeList * nl,DOM_Node * child)398 NodeList_exists(DOM_NodeList *nl, DOM_Node *child)
399 {
400 NodeEntry *e;
401
402 if (nl == NULL || nl->filter) {
403 return 0;
404 }
405
406 e = _lookupNode(nl, child);
407 return e != NULL;
408 }
409
410