ReactOS  0.4.14-dev-52-g6116262
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 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 15131 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 468 of file xpath.c.

◆ SORT_NAME

#define SORT_NAME   libxml_domnode

Definition at line 441 of file xpath.c.

◆ SORT_TYPE

#define SORT_TYPE   xmlNodePtr

Definition at line 442 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_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 456 of file xpath.c.

457  {
458  int res = xmlXPathCmpNodesExt(x, y);
459  return res == -2 ? res : -res;
460  }
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
static int xmlXPathCmpNodesExt(xmlNodePtr node1, xmlNodePtr node2)
Definition: xpath.c:158
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 158 of file xpath.c.

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

Referenced by wrap_cmp().