SAX2: Fix quadratic behavior in xmlSAX2AttributeNs

The last missing piece to make parsing of attributes O(n).

1 files changed, 50 insertions, 41 deletions

diff --git a/SAX2.c b/SAX2.c
index e20ec886..2505f42a 100644
--- a/SAX2.c
+++ b/SAX2.c
@@ -1855,8 +1855,10 @@ decode:
  * The default handling is to convert the attribute into an
  * DOM subtree and past it in a new xmlAttr element added to
  * the element.
+ *
+ * Returns the new attribute or NULL in case of error.
  */
-static void
+static xmlAttrPtr
 xmlSAX2AttributeNs(xmlParserCtxtPtr ctxt,
                    const xmlChar * localname,
                    const xmlChar * prefix,
@@ -1884,42 +1886,28 @@ xmlSAX2AttributeNs(xmlParserCtxtPtr ctxt,
         ret = ctxt->freeAttrs;
 	ctxt->freeAttrs = ret->next;
 	ctxt->freeAttrsNr--;
-	memset(ret, 0, sizeof(xmlAttr));
-	ret->type = XML_ATTRIBUTE_NODE;
-
-	ret->parent = ctxt->node;
-	ret->doc = ctxt->myDoc;
-	ret->ns = namespace;
+    } else {
+        ret = xmlMalloc(sizeof(*ret));
+        if (ret == NULL) {
+            xmlSAX2ErrMemory(ctxt, NULL);
+            return(NULL);
+        }
+    }
 
-	if (ctxt->dictNames)
-	    ret->name = localname;
-	else
-	    ret->name = xmlStrdup(localname);
+    memset(ret, 0, sizeof(xmlAttr));
+    ret->type = XML_ATTRIBUTE_NODE;
 
-        /* link at the end to preserve order, TODO speed up with a last */
-	if (ctxt->node->properties == NULL) {
-	    ctxt->node->properties = ret;
-	} else {
-	    xmlAttrPtr prev = ctxt->node->properties;
+    ret->parent = ctxt->node;
+    ret->doc = ctxt->myDoc;
+    ret->ns = namespace;
 
-	    while (prev->next != NULL) prev = prev->next;
-	    prev->next = ret;
-	    ret->prev = prev;
-	}
+    if (ctxt->dictNames)
+        ret->name = localname;
+    else
+        ret->name = xmlStrdup(localname);
 
-	if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
-	    xmlRegisterNodeDefaultValue((xmlNodePtr)ret);
-    } else {
-	if (ctxt->dictNames)
-	    ret = xmlNewNsPropEatName(ctxt->node, namespace,
-	                              (xmlChar *) localname, NULL);
-	else
-	    ret = xmlNewNsProp(ctxt->node, namespace, localname, NULL);
-	if (ret == NULL) {
-	    xmlErrMemory(ctxt, "xmlSAX2AttributeNs");
-	    return;
-	}
-    }
+    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
+        xmlRegisterNodeDefaultValue((xmlNodePtr)ret);
 
     if ((ctxt->replaceEntities == 0) && (!ctxt->html)) {
 	xmlNodePtr tmp;
@@ -2065,6 +2053,8 @@ xmlSAX2AttributeNs(xmlParserCtxtPtr ctxt,
     }
     if (dup != NULL)
 	xmlFree(dup);
+
+    return(ret);
 }
 
 /**
@@ -2275,7 +2265,11 @@ xmlSAX2StartElementNs(void *ctx,
      * process all the other attributes
      */
     if (nb_attributes > 0) {
+        xmlAttrPtr prev = NULL;
+
         for (j = 0,i = 0;i < nb_attributes;i++,j+=5) {
+            xmlAttrPtr attr = NULL;
+
 	    /*
 	     * Handle the rare case of an undefined attribute prefix
 	     */
@@ -2286,23 +2280,38 @@ xmlSAX2StartElementNs(void *ctx,
 		    fullname = xmlDictQLookup(ctxt->dict, attributes[j+1],
 		                              attributes[j]);
 		    if (fullname != NULL) {
-			xmlSAX2AttributeNs(ctxt, fullname, NULL,
-			                   attributes[j+3], attributes[j+4]);
-		        continue;
+                        attr = xmlSAX2AttributeNs(ctxt, fullname, NULL,
+                                                  attributes[j+3],
+                                                  attributes[j+4]);
+                        goto have_attr;
 		    }
 		} else {
 		    lname = xmlBuildQName(attributes[j], attributes[j+1],
 		                          NULL, 0);
 		    if (lname != NULL) {
-			xmlSAX2AttributeNs(ctxt, lname, NULL,
-			                   attributes[j+3], attributes[j+4]);
+                        attr = xmlSAX2AttributeNs(ctxt, lname, NULL,
+                                                  attributes[j+3],
+                                                  attributes[j+4]);
 			xmlFree(lname);
-		        continue;
+                        goto have_attr;
 		    }
 		}
 	    }
-	    xmlSAX2AttributeNs(ctxt, attributes[j], attributes[j+1],
-			       attributes[j+3], attributes[j+4]);
+            attr = xmlSAX2AttributeNs(ctxt, attributes[j], attributes[j+1],
+                                      attributes[j+3], attributes[j+4]);
+have_attr:
+            if (attr == NULL)
+                continue;
+
+            /* link at the end to preserve order */
+            if (prev == NULL) {
+                ctxt->node->properties = attr;
+            } else {
+                prev->next = attr;
+                attr->prev = prev;
+            }
+
+            prev = attr;
 	}
     }