summaryrefslogtreecommitdiff
path: root/src/pugixml.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/pugixml.cpp')
-rw-r--r--src/pugixml.cpp88
1 files changed, 57 insertions, 31 deletions
diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index 94073f3..8417c44 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -6808,44 +6808,71 @@ PUGI__NS_BEGIN
}
}
- PUGI__FN unsigned int node_height(xml_node n)
+ PUGI__FN bool node_is_before_sibling(xml_node_struct* ln, xml_node_struct* rn)
{
- unsigned int result = 0;
-
- while (n)
+ assert(ln->parent == rn->parent);
+
+ // there is no common ancestor (the shared parent is null), nodes are from different documents
+ if (!ln->parent) return ln < rn;
+
+ // determine sibling order
+ xml_node_struct* ls = ln;
+ xml_node_struct* rs = rn;
+
+ while (ls && rs)
{
- ++result;
- n = n.parent();
+ if (ls == rn) return true;
+ if (rs == ln) return false;
+
+ ls = ls->next_sibling;
+ rs = rs->next_sibling;
}
-
- return result;
+
+ // if rn sibling chain ended ln must be before rn
+ return !rs;
}
- PUGI__FN bool node_is_before(xml_node ln, unsigned int lh, xml_node rn, unsigned int rh)
+ PUGI__FN bool node_is_before(xml_node_struct* ln, xml_node_struct* rn)
{
- // normalize heights
- for (unsigned int i = rh; i < lh; i++) ln = ln.parent();
- for (unsigned int j = lh; j < rh; j++) rn = rn.parent();
-
- // one node is the ancestor of the other
- if (ln == rn) return lh < rh;
-
- // find common ancestor
- while (ln.parent() != rn.parent())
+ // find common ancestor at the same depth, if any
+ xml_node_struct* lp = ln;
+ xml_node_struct* rp = rn;
+
+ while (lp && rp && lp->parent != rp->parent)
{
- ln = ln.parent();
- rn = rn.parent();
+ lp = lp->parent;
+ rp = rp->parent;
}
- // there is no common ancestor (the shared parent is null), nodes are from different documents
- if (!ln.parent()) return ln < rn;
+ // parents are the same!
+ if (lp && rp) return node_is_before_sibling(lp, rp);
- // determine sibling order
- for (; ln; ln = ln.next_sibling())
- if (ln == rn)
- return true;
+ // nodes are at different depths, need to normalize heights
+ bool left_higher = !lp;
- return false;
+ while (lp)
+ {
+ lp = lp->parent;
+ ln = ln->parent;
+ }
+
+ while (rp)
+ {
+ rp = rp->parent;
+ rn = rn->parent;
+ }
+
+ // one node is the ancestor of the other
+ if (ln == rn) return left_higher;
+
+ // find common ancestor... again
+ while (ln->parent != rn->parent)
+ {
+ ln = ln->parent;
+ rn = rn->parent;
+ }
+
+ return node_is_before_sibling(ln, rn);
}
PUGI__FN bool node_is_ancestor(xml_node parent, xml_node node)
@@ -6933,11 +6960,10 @@ PUGI__NS_BEGIN
}
if (ln == rn) return false;
+
+ if (!ln || !rn) return ln < rn;
- unsigned int lh = node_height(ln);
- unsigned int rh = node_height(rn);
-
- return node_is_before(ln, lh, rn, rh);
+ return node_is_before(ln.internal_object(), rn.internal_object());
}
};