From: Václav Slavík Date: Sun, 30 Mar 2008 10:27:19 +0000 (+0000) Subject: added wxXmlNode::InsertChildAfter and use it for (much) faster XML parsing (based... X-Git-Url: https://git.saurik.com/wxWidgets.git/commitdiff_plain/43a302f200f1e9f5f21380bbc7ba74ad8c22d6d6 added wxXmlNode::InsertChildAfter and use it for (much) faster XML parsing (based on patch by Francesco Montorsi) git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@52919 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775 --- diff --git a/include/wx/xml/xml.h b/include/wx/xml/xml.h index 77c88ef74c..939e526098 100644 --- a/include/wx/xml/xml.h +++ b/include/wx/xml/xml.h @@ -128,6 +128,7 @@ public: int lineNo = -1); virtual void AddChild(wxXmlNode *child); virtual bool InsertChild(wxXmlNode *child, wxXmlNode *followingNode); + virtual bool InsertChildAfter(wxXmlNode *child, wxXmlNode *precedingNode); virtual bool RemoveChild(wxXmlNode *child); virtual void AddAttribute(const wxString& name, const wxString& value); virtual bool DeleteAttribute(const wxString& name); diff --git a/interface/xml/xml.h b/interface/xml/xml.h index cc1fd7fef7..604daaa0ca 100644 --- a/interface/xml/xml.h +++ b/interface/xml/xml.h @@ -58,9 +58,16 @@ public: //@} /** - Adds the given node as child of this node. To attach a second children to this - node, use the - SetNext() function of the @a child node. + Adds node @a child as the last child of this node. + + @note + Note that this function works in O(n) time where @e n is the number + of existing children. Consequently, adding large number of child + nodes using this method can be expensive, because it has O(n^2) time + complexity in number of nodes to be added. Use InsertChildAfter() to + populate XML tree in linear time. + + @see InsertChild(), InsertChildAfter() */ void AddChild(wxXmlNode* child); @@ -168,9 +175,29 @@ public: then @a child is prepended to the list of children and becomes the first child of this node, i.e. it behaves identically to using the first children (as returned by GetChildren()) for @a followingNode). + + @see AddChild(), InsertChildAfter() */ bool InsertChild(wxXmlNode* child, wxXmlNode* followingNode); + /** + Inserts the @a child node immediately after @a precedingNode in the + children list. + + @return @true if @a precedingNode has been found and the @a child + node has been inserted. + + @param precedingNode + The node to insert @a child after. As a special case, this can be + @NULL if this node has no children yet -- in that case, @a child + will become this node's only child node. + + @since 2.8.8 + + @see InsertChild(), AddChild() + */ + bool InsertChildAfter(wxXmlNode* child, wxXmlNode* precedingNode); + /** Returns @true if the content of this node is a string containing only whitespaces (spaces, diff --git a/src/xml/xml.cpp b/src/xml/xml.cpp index 37467fc122..4941e6104b 100644 --- a/src/xml/xml.cpp +++ b/src/xml/xml.cpp @@ -226,6 +226,33 @@ bool wxXmlNode::InsertChild(wxXmlNode *child, wxXmlNode *followingNode) return true; } +// inserts a new node right after 'precedingNode' +bool wxXmlNode::InsertChildAfter(wxXmlNode *child, wxXmlNode *precedingNode) +{ + wxCHECK_MSG( child, false, "cannot insert a NULL node!" ); + wxCHECK_MSG( child->m_parent == NULL, false, "node already has a parent" ); + wxCHECK_MSG( child->m_next == NULL, false, "node already has m_next" ); + wxCHECK_MSG( precedingNode == NULL || precedingNode->m_parent == this, false, + "precedingNode has wrong parent" ); + + if ( precedingNode ) + { + child->m_next = precedingNode->m_next; + precedingNode->m_next = child; + } + else // precedingNode == NULL + { + wxCHECK_MSG( m_children == NULL, false, + "NULL precedingNode only makes sense when there are no children" ); + + child->m_next = m_children; + m_children = child; + } + + child->m_parent = this; + return true; +} + bool wxXmlNode::RemoveChild(wxXmlNode *child) { if (m_children == NULL) @@ -476,16 +503,33 @@ bool wxIsWhiteOnly(const wxString& buf) struct wxXmlParsingContext { + wxXmlParsingContext() + : conv(NULL), + root(NULL), + node(NULL), + lastChild(NULL), + lastAsText(NULL), + removeWhiteOnlyNodes(false) + {} + XML_Parser parser; wxMBConv *conv; wxXmlNode *root; - wxXmlNode *node; - wxXmlNode *lastAsText; + wxXmlNode *node; // the node being parsed + wxXmlNode *lastChild; // the last child of "node" + wxXmlNode *lastAsText; // the last _text_ child of "node" wxString encoding; wxString version; bool removeWhiteOnlyNodes; }; +// checks that ctx->lastChild is in consistent state +#define ASSERT_LAST_CHILD_OK(ctx) \ + wxASSERT( ctx->lastChild == NULL || \ + ctx->lastChild->GetNext() == NULL ); \ + wxASSERT( ctx->lastChild == NULL || \ + ctx->lastChild->GetParent() == ctx->node ) + extern "C" { static void StartElementHnd(void *userData, const char *name, const char **atts) { @@ -496,23 +540,38 @@ static void StartElementHnd(void *userData, const char *name, const char **atts) XML_GetCurrentLineNumber(ctx->parser)); const char **a = atts; + // add node attributes while (*a) { node->AddAttribute(CharToString(ctx->conv, a[0]), CharToString(ctx->conv, a[1])); a += 2; } + if (ctx->root == NULL) + { ctx->root = node; + } else - ctx->node->AddChild(node); - ctx->node = node; + { + ASSERT_LAST_CHILD_OK(ctx); + ctx->node->InsertChildAfter(node, ctx->lastChild); + } + ctx->lastAsText = NULL; + ctx->lastChild = NULL; // our new node "node" has no children yet + + ctx->node = node; } static void EndElementHnd(void *userData, const char* WXUNUSED(name)) { wxXmlParsingContext *ctx = (wxXmlParsingContext*)userData; + // we're exiting the last children of ctx->node->GetParent() and going + // back one level up, so current value of ctx->node points to the last + // child of ctx->node->GetParent() + ctx->lastChild = ctx->node; + ctx->node = ctx->node->GetParent(); ctx->lastAsText = NULL; } @@ -534,10 +593,13 @@ static void TextHnd(void *userData, const char *s, int len) if (!whiteOnly) { - ctx->lastAsText = + wxXmlNode *textnode = new wxXmlNode(wxXML_TEXT_NODE, wxT("text"), str, XML_GetCurrentLineNumber(ctx->parser)); - ctx->node->AddChild(ctx->lastAsText); + + ASSERT_LAST_CHILD_OK(ctx); + ctx->node->InsertChildAfter(textnode, ctx->lastChild); + ctx->lastChild= ctx->lastAsText = textnode; } } } @@ -546,10 +608,13 @@ static void StartCdataHnd(void *userData) { wxXmlParsingContext *ctx = (wxXmlParsingContext*)userData; - ctx->lastAsText = + wxXmlNode *textnode = new wxXmlNode(wxXML_CDATA_SECTION_NODE, wxT("cdata"), wxT(""), XML_GetCurrentLineNumber(ctx->parser)); - ctx->node->AddChild(ctx->lastAsText); + + ASSERT_LAST_CHILD_OK(ctx); + ctx->node->InsertChildAfter(textnode, ctx->lastChild); + ctx->lastChild= ctx->lastAsText = textnode; } static void CommentHnd(void *userData, const char *data) @@ -558,14 +623,19 @@ static void CommentHnd(void *userData, const char *data) if (ctx->node) { - // VS: ctx->node == NULL happens if there is a comment before - // the root element (e.g. wxDesigner's output). We ignore such - // comments, no big deal... - ctx->node->AddChild( + wxXmlNode *commentnode = new wxXmlNode(wxXML_COMMENT_NODE, wxT("comment"), CharToString(ctx->conv, data), - XML_GetCurrentLineNumber(ctx->parser))); + XML_GetCurrentLineNumber(ctx->parser)); + + ASSERT_LAST_CHILD_OK(ctx); + ctx->node->InsertChildAfter(commentnode, ctx->lastChild); + ctx->lastChild = commentnode; } + //else: ctx->node == NULL happens if there is a comment before + // the root element. We current don't have a way to represent + // these in wxXmlDocument (FIXME). + ctx->lastAsText = NULL; } @@ -634,7 +704,6 @@ bool wxXmlDocument::Load(wxInputStream& stream, const wxString& encoding, int fl bool done; XML_Parser parser = XML_ParserCreate(NULL); - ctx.root = ctx.node = NULL; ctx.encoding = wxT("UTF-8"); // default in absence of encoding="" ctx.conv = NULL; #if !wxUSE_UNICODE diff --git a/tests/xml/xmltest.cpp b/tests/xml/xmltest.cpp index 1f354224f1..09bc9598d4 100644 --- a/tests/xml/xmltest.cpp +++ b/tests/xml/xmltest.cpp @@ -72,9 +72,11 @@ public: private: CPPUNIT_TEST_SUITE( XmlTestCase ); CPPUNIT_TEST( InsertChild ); + CPPUNIT_TEST( InsertChildAfter ); CPPUNIT_TEST_SUITE_END(); void InsertChild(); + void InsertChildAfter(); DECLARE_NO_COPY_CLASS(XmlTestCase) }; @@ -104,3 +106,27 @@ void XmlTestCase::InsertChild() root->InsertChild(new wxXmlNode(wxXML_ELEMENT_NODE, "C"), two); CheckXml(root, "B", "A", "1", "C", "2", "3", NULL); } + +void XmlTestCase::InsertChildAfter() +{ + wxXmlNode *root = new wxXmlNode(wxXML_ELEMENT_NODE, "root"); + + root->InsertChildAfter(new wxXmlNode(wxXML_ELEMENT_NODE, "1"), NULL); + CheckXml(root, "1", NULL); + + wxXmlNode *two = new wxXmlNode(wxXML_ELEMENT_NODE, "2"); + root->AddChild(two); + wxXmlNode *three = new wxXmlNode(wxXML_ELEMENT_NODE, "3"); + root->AddChild(three); + CheckXml(root, "1", "2", "3", NULL); + + // check inserting in the middle: + root->InsertChildAfter(new wxXmlNode(wxXML_ELEMENT_NODE, "A"), root->GetChildren()); + CheckXml(root, "1", "A", "2", "3", NULL); + root->InsertChildAfter(new wxXmlNode(wxXML_ELEMENT_NODE, "B"), two); + CheckXml(root, "1", "A", "2", "B", "3", NULL); + + // and at the end: + root->InsertChildAfter(new wxXmlNode(wxXML_ELEMENT_NODE, "C"), three); + CheckXml(root, "1", "A", "2", "B", "3", "C", NULL); +}