ReactOS  0.4.15-dev-3295-gaa8fc87
xpath.c File Reference
#include "libxml.h"
#include <limits.h>
#include <string.h>
#include <stddef.h>
#include <sys/types.h>
#include <math.h>
#include <float.h>
#include <ctype.h>
#include <signal.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 "elfgcchack.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))
 
#define bottom_xpath
 

Functions

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

Macro Definition Documentation

◆ bottom_xpath

#define bottom_xpath

Definition at line 14733 of file xpath.c.

◆ 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 479 of file xpath.c.

◆ SORT_NAME

#define SORT_NAME   libxml_domnode

Definition at line 452 of file xpath.c.

◆ SORT_TYPE

#define SORT_TYPE   xmlNodePtr

Definition at line 453 of file xpath.c.

◆ TODO

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

Definition at line 71 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 83 of file xpath.c.

◆ XP_OPTIMIZED_FILTER_FIRST

#define XP_OPTIMIZED_FILTER_FIRST

Definition at line 101 of file xpath.c.

◆ XP_OPTIMIZED_NON_ELEM_COMPARISON

#define XP_OPTIMIZED_NON_ELEM_COMPARISON

Definition at line 94 of file xpath.c.

◆ XPATH_MAX_NODESET_LENGTH

#define XPATH_MAX_NODESET_LENGTH   10000000

Definition at line 136 of file xpath.c.

◆ XPATH_MAX_RECURSION_DEPTH

#define XPATH_MAX_RECURSION_DEPTH   5000

Definition at line 146 of file xpath.c.

◆ XPATH_MAX_STACK_DEPTH

#define XPATH_MAX_STACK_DEPTH   1000000

Definition at line 126 of file xpath.c.

◆ XPATH_MAX_STEPS

#define XPATH_MAX_STEPS   1000000

Definition at line 117 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 467 of file xpath.c.

468  {
469  int res = xmlXPathCmpNodesExt(x, y);
470  return res == -2 ? res : -res;
471  }
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
static int xmlXPathCmpNodesExt(xmlNodePtr node1, xmlNodePtr node2)
Definition: xpath.c:169
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLuint res
Definition: glext.h:9613

◆ 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 169 of file xpath.c.

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

Referenced by wrap_cmp().