ReactOS 0.4.15-dev-7681-g776c3a3
xpath.c File Reference
#include "libxml.h"
#include <limits.h>
#include <string.h>
#include <stddef.h>
#include <math.h>
#include <float.h>
#include <ctype.h>
#include <libxml/xmlmemory.h>
#include <libxml/tree.h>
#include <libxml/valid.h>
#include <libxml/xpath.h>
#include <libxml/xpathInternals.h>
#include <libxml/parserInternals.h>
#include <libxml/hash.h>
#include <libxml/xmlerror.h>
#include <libxml/threads.h>
#include <libxml/globals.h>
#include "buf.h"
#include "timsort.h"
Include dependency graph for xpath.c:

Go to the source code of this file.

Macros

#define IN_LIBXML
 
#define TODO
 
#define WITH_TIM_SORT
 
#define XP_OPTIMIZED_NON_ELEM_COMPARISON
 
#define XP_OPTIMIZED_FILTER_FIRST
 
#define XPATH_MAX_STEPS   1000000
 
#define XPATH_MAX_STACK_DEPTH   1000000
 
#define XPATH_MAX_NODESET_LENGTH   10000000
 
#define XPATH_MAX_RECURSION_DEPTH   5000
 
#define SORT_NAME   libxml_domnode
 
#define SORT_TYPE   xmlNodePtr
 
#define SORT_CMP(x, y)   (wrap_cmp(x, y))
 

Functions

static int xmlXPathCmpNodesExt (xmlNodePtr node1, xmlNodePtr node2)
 
static int wrap_cmp (xmlNodePtr x, xmlNodePtr y)
 

Macro Definition Documentation

◆ IN_LIBXML

#define IN_LIBXML

Definition at line 22 of file xpath.c.

◆ SORT_CMP

#define SORT_CMP (   x,
  y 
)    (wrap_cmp(x, y))

Definition at line 466 of file xpath.c.

◆ SORT_NAME

#define SORT_NAME   libxml_domnode

Definition at line 439 of file xpath.c.

◆ SORT_TYPE

#define SORT_TYPE   xmlNodePtr

Definition at line 440 of file xpath.c.

◆ TODO

#define TODO
Value:
"Unimplemented block at %s:%d\n", \
__FILE__, __LINE__);
XMLPUBVAR void * xmlGenericErrorContext
Definition: globals.h:353
XMLPUBVAR xmlGenericErrorFunc xmlGenericError
Definition: globals.h:337

Definition at line 58 of file xpath.c.

◆ WITH_TIM_SORT

#define WITH_TIM_SORT

WITH_TIM_SORT:

Use the Timsort algorithm provided in timsort.h to sort nodeset as this is a great improvement over the old Shell sort used in xmlXPathNodeSetSort()

Definition at line 70 of file xpath.c.

◆ XP_OPTIMIZED_FILTER_FIRST

#define XP_OPTIMIZED_FILTER_FIRST

Definition at line 88 of file xpath.c.

◆ XP_OPTIMIZED_NON_ELEM_COMPARISON

#define XP_OPTIMIZED_NON_ELEM_COMPARISON

Definition at line 81 of file xpath.c.

◆ XPATH_MAX_NODESET_LENGTH

#define XPATH_MAX_NODESET_LENGTH   10000000

Definition at line 123 of file xpath.c.

◆ XPATH_MAX_RECURSION_DEPTH

#define XPATH_MAX_RECURSION_DEPTH   5000

Definition at line 133 of file xpath.c.

◆ XPATH_MAX_STACK_DEPTH

#define XPATH_MAX_STACK_DEPTH   1000000

Definition at line 113 of file xpath.c.

◆ XPATH_MAX_STEPS

#define XPATH_MAX_STEPS   1000000

Definition at line 104 of file xpath.c.

Function Documentation

◆ wrap_cmp()

static int wrap_cmp ( xmlNodePtr  x,
xmlNodePtr  y 
)
static

wrap_cmp: @x: a node @y: another node

Comparison function for the Timsort implementation

Returns -2 in case of error -1 if first point < second point, 0 if it's the same node, +1 otherwise

Definition at line 454 of file xpath.c.

455 {
456 int res = xmlXPathCmpNodesExt(x, y);
457 return res == -2 ? res : -res;
458 }
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLuint res
Definition: glext.h:9613
static int xmlXPathCmpNodesExt(xmlNodePtr node1, xmlNodePtr node2)
Definition: xpath.c:156

◆ xmlXPathCmpNodesExt()

static int xmlXPathCmpNodesExt ( xmlNodePtr  node1,
xmlNodePtr  node2 
)
static

xmlXPathCmpNodesExt: @node1: the first node @node2: the second node

Compare two nodes w.r.t document order. This one is optimized for handling of non-element nodes.

Returns -2 in case of error 1 if first point < second point, 0 if it's the same node, -1 otherwise

Definition at line 156 of file xpath.c.

156 {
157 int depth1, depth2;
158 int misc = 0, precedence1 = 0, precedence2 = 0;
159 xmlNodePtr miscNode1 = NULL, miscNode2 = NULL;
161 ptrdiff_t l1, l2;
162
163 if ((node1 == NULL) || (node2 == NULL))
164 return(-2);
165
166 if (node1 == node2)
167 return(0);
168
169 /*
170 * a couple of optimizations which will avoid computations in most cases
171 */
172 switch (node1->type) {
173 case XML_ELEMENT_NODE:
174 if (node2->type == XML_ELEMENT_NODE) {
175 if ((0 > (ptrdiff_t) node1->content) &&
176 (0 > (ptrdiff_t) node2->content) &&
177 (node1->doc == node2->doc))
178 {
179 l1 = -((ptrdiff_t) node1->content);
180 l2 = -((ptrdiff_t) node2->content);
181 if (l1 < l2)
182 return(1);
183 if (l1 > l2)
184 return(-1);
185 } else
186 goto turtle_comparison;
187 }
188 break;
190 precedence1 = 1; /* element is owner */
191 miscNode1 = node1;
192 node1 = node1->parent;
193 misc = 1;
194 break;
195 case XML_TEXT_NODE:
197 case XML_COMMENT_NODE:
198 case XML_PI_NODE: {
199 miscNode1 = node1;
200 /*
201 * Find nearest element node.
202 */
203 if (node1->prev != NULL) {
204 do {
205 node1 = node1->prev;
206 if (node1->type == XML_ELEMENT_NODE) {
207 precedence1 = 3; /* element in prev-sibl axis */
208 break;
209 }
210 if (node1->prev == NULL) {
211 precedence1 = 2; /* element is parent */
212 /*
213 * URGENT TODO: Are there any cases, where the
214 * parent of such a node is not an element node?
215 */
216 node1 = node1->parent;
217 break;
218 }
219 } while (1);
220 } else {
221 precedence1 = 2; /* element is parent */
222 node1 = node1->parent;
223 }
224 if ((node1 == NULL) || (node1->type != XML_ELEMENT_NODE) ||
225 (0 <= (ptrdiff_t) node1->content)) {
226 /*
227 * Fallback for whatever case.
228 */
229 node1 = miscNode1;
230 precedence1 = 0;
231 } else
232 misc = 1;
233 }
234 break;
236 /*
237 * TODO: why do we return 1 for namespace nodes?
238 */
239 return(1);
240 default:
241 break;
242 }
243 switch (node2->type) {
244 case XML_ELEMENT_NODE:
245 break;
247 precedence2 = 1; /* element is owner */
248 miscNode2 = node2;
249 node2 = node2->parent;
250 misc = 1;
251 break;
252 case XML_TEXT_NODE:
254 case XML_COMMENT_NODE:
255 case XML_PI_NODE: {
256 miscNode2 = node2;
257 if (node2->prev != NULL) {
258 do {
259 node2 = node2->prev;
260 if (node2->type == XML_ELEMENT_NODE) {
261 precedence2 = 3; /* element in prev-sibl axis */
262 break;
263 }
264 if (node2->prev == NULL) {
265 precedence2 = 2; /* element is parent */
266 node2 = node2->parent;
267 break;
268 }
269 } while (1);
270 } else {
271 precedence2 = 2; /* element is parent */
272 node2 = node2->parent;
273 }
274 if ((node2 == NULL) || (node2->type != XML_ELEMENT_NODE) ||
275 (0 <= (ptrdiff_t) node2->content))
276 {
277 node2 = miscNode2;
278 precedence2 = 0;
279 } else
280 misc = 1;
281 }
282 break;
284 return(1);
285 default:
286 break;
287 }
288 if (misc) {
289 if (node1 == node2) {
290 if (precedence1 == precedence2) {
291 /*
292 * The ugly case; but normally there aren't many
293 * adjacent non-element nodes around.
294 */
295 cur = miscNode2->prev;
296 while (cur != NULL) {
297 if (cur == miscNode1)
298 return(1);
299 if (cur->type == XML_ELEMENT_NODE)
300 return(-1);
301 cur = cur->prev;
302 }
303 return (-1);
304 } else {
305 /*
306 * Evaluate based on higher precedence wrt to the element.
307 * TODO: This assumes attributes are sorted before content.
308 * Is this 100% correct?
309 */
310 if (precedence1 < precedence2)
311 return(1);
312 else
313 return(-1);
314 }
315 }
316 /*
317 * Special case: One of the helper-elements is contained by the other.
318 * <foo>
319 * <node2>
320 * <node1>Text-1(precedence1 == 2)</node1>
321 * </node2>
322 * Text-6(precedence2 == 3)
323 * </foo>
324 */
325 if ((precedence2 == 3) && (precedence1 > 1)) {
326 cur = node1->parent;
327 while (cur) {
328 if (cur == node2)
329 return(1);
330 cur = cur->parent;
331 }
332 }
333 if ((precedence1 == 3) && (precedence2 > 1)) {
334 cur = node2->parent;
335 while (cur) {
336 if (cur == node1)
337 return(-1);
338 cur = cur->parent;
339 }
340 }
341 }
342
343 /*
344 * Speedup using document order if available.
345 */
346 if ((node1->type == XML_ELEMENT_NODE) &&
347 (node2->type == XML_ELEMENT_NODE) &&
348 (0 > (ptrdiff_t) node1->content) &&
349 (0 > (ptrdiff_t) node2->content) &&
350 (node1->doc == node2->doc)) {
351
352 l1 = -((ptrdiff_t) node1->content);
353 l2 = -((ptrdiff_t) node2->content);
354 if (l1 < l2)
355 return(1);
356 if (l1 > l2)
357 return(-1);
358 }
359
360turtle_comparison:
361
362 if (node1 == node2->prev)
363 return(1);
364 if (node1 == node2->next)
365 return(-1);
366 /*
367 * compute depth to root
368 */
369 for (depth2 = 0, cur = node2; cur->parent != NULL; cur = cur->parent) {
370 if (cur->parent == node1)
371 return(1);
372 depth2++;
373 }
374 root = cur;
375 for (depth1 = 0, cur = node1; cur->parent != NULL; cur = cur->parent) {
376 if (cur->parent == node2)
377 return(-1);
378 depth1++;
379 }
380 /*
381 * Distinct document (or distinct entities :-( ) case.
382 */
383 if (root != cur) {
384 return(-2);
385 }
386 /*
387 * get the nearest common ancestor.
388 */
389 while (depth1 > depth2) {
390 depth1--;
391 node1 = node1->parent;
392 }
393 while (depth2 > depth1) {
394 depth2--;
395 node2 = node2->parent;
396 }
397 while (node1->parent != node2->parent) {
398 node1 = node1->parent;
399 node2 = node2->parent;
400 /* should not happen but just in case ... */
401 if ((node1 == NULL) || (node2 == NULL))
402 return(-2);
403 }
404 /*
405 * Find who's first.
406 */
407 if (node1 == node2->prev)
408 return(1);
409 if (node1 == node2->next)
410 return(-1);
411 /*
412 * Speedup using document order if available.
413 */
414 if ((node1->type == XML_ELEMENT_NODE) &&
415 (node2->type == XML_ELEMENT_NODE) &&
416 (0 > (ptrdiff_t) node1->content) &&
417 (0 > (ptrdiff_t) node2->content) &&
418 (node1->doc == node2->doc)) {
419
420 l1 = -((ptrdiff_t) node1->content);
421 l2 = -((ptrdiff_t) node2->content);
422 if (l1 < l2)
423 return(1);
424 if (l1 > l2)
425 return(-1);
426 }
427
428 for (cur = node1->next;cur != NULL;cur = cur->next)
429 if (cur == node2)
430 return(1);
431 return(-1); /* assume there is no sibling list corruption */
432}
struct _root root
#define NULL
Definition: types.h:112
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
FxCollectionEntry * cur
@ XML_ATTRIBUTE_NODE
Definition: tree.h:161
@ XML_CDATA_SECTION_NODE
Definition: tree.h:163
@ XML_TEXT_NODE
Definition: tree.h:162
@ XML_PI_NODE
Definition: tree.h:166
@ XML_COMMENT_NODE
Definition: tree.h:167
@ XML_NAMESPACE_DECL
Definition: tree.h:177
@ XML_ELEMENT_NODE
Definition: tree.h:160
Definition: tree.h:489
xmlChar * content
Definition: tree.h:502
struct _xmlNode * next
Definition: tree.h:496
struct _xmlDoc * doc
Definition: tree.h:498
xmlElementType type
Definition: tree.h:491
struct _xmlNode * parent
Definition: tree.h:495
struct _xmlNode * prev
Definition: tree.h:497

Referenced by wrap_cmp().