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:

    xmlGenericError(xmlGenericErrorContext,             \
        "Unimplemented block at %s:%d\n",               \
            __FILE__, __LINE__);

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.

    {
        int res = xmlXPathCmpNodesExt(x, y);
        return res == -2 ? res : -res;
    }

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.

                                                        {
    int depth1, depth2;
    int misc = 0, precedence1 = 0, precedence2 = 0;
    xmlNodePtr miscNode1 = NULL, miscNode2 = NULL;
    xmlNodePtr cur, root;
    ptrdiff_t l1, l2;
 
    if ((node1 == NULL) || (node2 == NULL))
    return(-2);
 
    if (node1 == node2)
    return(0);
 
    /*
     * a couple of optimizations which will avoid computations in most cases
     */
    switch (node1->type) {
    case XML_ELEMENT_NODE:
        if (node2->type == XML_ELEMENT_NODE) {
        if ((0 > (ptrdiff_t) node1->content) &&
            (0 > (ptrdiff_t) node2->content) &&
            (node1->doc == node2->doc))
        {
            l1 = -((ptrdiff_t) node1->content);
            l2 = -((ptrdiff_t) node2->content);
            if (l1 < l2)
            return(1);
            if (l1 > l2)
            return(-1);
        } else
            goto turtle_comparison;
        }
        break;
    case XML_ATTRIBUTE_NODE:
        precedence1 = 1; /* element is owner */
        miscNode1 = node1;
        node1 = node1->parent;
        misc = 1;
        break;
    case XML_TEXT_NODE:
    case XML_CDATA_SECTION_NODE:
    case XML_COMMENT_NODE:
    case XML_PI_NODE: {
        miscNode1 = node1;
        /*
        * Find nearest element node.
        */
        if (node1->prev != NULL) {
        do {
            node1 = node1->prev;
            if (node1->type == XML_ELEMENT_NODE) {
            precedence1 = 3; /* element in prev-sibl axis */
            break;
            }
            if (node1->prev == NULL) {
            precedence1 = 2; /* element is parent */
            /*
            * URGENT TODO: Are there any cases, where the
            * parent of such a node is not an element node?
            */
            node1 = node1->parent;
            break;
            }
        } while (1);
        } else {
        precedence1 = 2; /* element is parent */
        node1 = node1->parent;
        }
        if ((node1 == NULL) || (node1->type != XML_ELEMENT_NODE) ||
        (0 <= (ptrdiff_t) node1->content)) {
        /*
        * Fallback for whatever case.
        */
        node1 = miscNode1;
        precedence1 = 0;
        } else
        misc = 1;
    }
        break;
    case XML_NAMESPACE_DECL:
        /*
        * TODO: why do we return 1 for namespace nodes?
        */
        return(1);
    default:
        break;
    }
    switch (node2->type) {
    case XML_ELEMENT_NODE:
        break;
    case XML_ATTRIBUTE_NODE:
        precedence2 = 1; /* element is owner */
        miscNode2 = node2;
        node2 = node2->parent;
        misc = 1;
        break;
    case XML_TEXT_NODE:
    case XML_CDATA_SECTION_NODE:
    case XML_COMMENT_NODE:
    case XML_PI_NODE: {
        miscNode2 = node2;
        if (node2->prev != NULL) {
        do {
            node2 = node2->prev;
            if (node2->type == XML_ELEMENT_NODE) {
            precedence2 = 3; /* element in prev-sibl axis */
            break;
            }
            if (node2->prev == NULL) {
            precedence2 = 2; /* element is parent */
            node2 = node2->parent;
            break;
            }
        } while (1);
        } else {
        precedence2 = 2; /* element is parent */
        node2 = node2->parent;
        }
        if ((node2 == NULL) || (node2->type != XML_ELEMENT_NODE) ||
        (0 <= (ptrdiff_t) node2->content))
        {
        node2 = miscNode2;
        precedence2 = 0;
        } else
        misc = 1;
    }
        break;
    case XML_NAMESPACE_DECL:
        return(1);
    default:
        break;
    }
    if (misc) {
    if (node1 == node2) {
        if (precedence1 == precedence2) {
        /*
        * The ugly case; but normally there aren't many
        * adjacent non-element nodes around.
        */
        cur = miscNode2->prev;
        while (cur != NULL) {
            if (cur == miscNode1)
            return(1);
            if (cur->type == XML_ELEMENT_NODE)
            return(-1);
            cur = cur->prev;
        }
        return (-1);
        } else {
        /*
        * Evaluate based on higher precedence wrt to the element.
        * TODO: This assumes attributes are sorted before content.
        *   Is this 100% correct?
        */
        if (precedence1 < precedence2)
            return(1);
        else
            return(-1);
        }
    }
    /*
    * Special case: One of the helper-elements is contained by the other.
    * <foo>
    *   <node2>
    *     <node1>Text-1(precedence1 == 2)</node1>
    *   </node2>
    *   Text-6(precedence2 == 3)
    * </foo>
    */
    if ((precedence2 == 3) && (precedence1 > 1)) {
        cur = node1->parent;
        while (cur) {
        if (cur == node2)
            return(1);
        cur = cur->parent;
        }
    }
    if ((precedence1 == 3) && (precedence2 > 1)) {
        cur = node2->parent;
        while (cur) {
        if (cur == node1)
            return(-1);
        cur = cur->parent;
        }
    }
    }
 
    /*
     * Speedup using document order if available.
     */
    if ((node1->type == XML_ELEMENT_NODE) &&
    (node2->type == XML_ELEMENT_NODE) &&
    (0 > (ptrdiff_t) node1->content) &&
    (0 > (ptrdiff_t) node2->content) &&
    (node1->doc == node2->doc)) {
 
    l1 = -((ptrdiff_t) node1->content);
    l2 = -((ptrdiff_t) node2->content);
    if (l1 < l2)
        return(1);
    if (l1 > l2)
        return(-1);
    }
 
turtle_comparison:
 
    if (node1 == node2->prev)
    return(1);
    if (node1 == node2->next)
    return(-1);
    /*
     * compute depth to root
     */
    for (depth2 = 0, cur = node2; cur->parent != NULL; cur = cur->parent) {
    if (cur->parent == node1)
        return(1);
    depth2++;
    }
    root = cur;
    for (depth1 = 0, cur = node1; cur->parent != NULL; cur = cur->parent) {
    if (cur->parent == node2)
        return(-1);
    depth1++;
    }
    /*
     * Distinct document (or distinct entities :-( ) case.
     */
    if (root != cur) {
    return(-2);
    }
    /*
     * get the nearest common ancestor.
     */
    while (depth1 > depth2) {
    depth1--;
    node1 = node1->parent;
    }
    while (depth2 > depth1) {
    depth2--;
    node2 = node2->parent;
    }
    while (node1->parent != node2->parent) {
    node1 = node1->parent;
    node2 = node2->parent;
    /* should not happen but just in case ... */
    if ((node1 == NULL) || (node2 == NULL))
        return(-2);
    }
    /*
     * Find who's first.
     */
    if (node1 == node2->prev)
    return(1);
    if (node1 == node2->next)
    return(-1);
    /*
     * Speedup using document order if available.
     */
    if ((node1->type == XML_ELEMENT_NODE) &&
    (node2->type == XML_ELEMENT_NODE) &&
    (0 > (ptrdiff_t) node1->content) &&
    (0 > (ptrdiff_t) node2->content) &&
    (node1->doc == node2->doc)) {
 
    l1 = -((ptrdiff_t) node1->content);
    l2 = -((ptrdiff_t) node2->content);
    if (l1 < l2)
        return(1);
    if (l1 > l2)
        return(-1);
    }
 
    for (cur = node1->next;cur != NULL;cur = cur->next)
    if (cur == node2)
        return(1);
    return(-1); /* assume there is no sibling list corruption */
}

Referenced by wrap_cmp().