ReactOS  0.4.15-dev-5496-g599ba9c
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 xmlGenericErrorFunc xmlGenericError
Definition: globals.h:337
XMLPUBVAR void * xmlGenericErrorContext
Definition: globals.h:353

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
static int xmlXPathCmpNodesExt(xmlNodePtr node1, xmlNodePtr node2)
Definition: xpath.c:156
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 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;
189  case XML_ATTRIBUTE_NODE:
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;
235  case XML_NAMESPACE_DECL:
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;
246  case XML_ATTRIBUTE_NODE:
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;
283  case XML_NAMESPACE_DECL:
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 
360 turtle_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 _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().