Make destroy_node() function non-recursive
@@ -2566,13 +2566,52 @@ static bool handle_after_head(GumboParser* parser, GumboToken* token) {
}
}
-static void destroy_node(GumboNode* node) {
+typedef void (*TreeTraversalCallback)(GumboNode* node);
+
+static void tree_traverse(GumboNode* node, TreeTraversalCallback callback) {
+ GumboNode* current_node = node;
+ unsigned int offset = 0;
+
+tailcall:
+ switch (current_node->type) {
+ case GUMBO_NODE_DOCUMENT:
+ case GUMBO_NODE_TEMPLATE:
+ case GUMBO_NODE_ELEMENT: {
+ GumboVector* children = (current_node->type == GUMBO_NODE_DOCUMENT)
+ ? &current_node->v.document.children
+ : &current_node->v.element.children
+ ;
+ if (offset >= children->length) {
+ assert(offset == children->length);
+ break;
+ } else {
+ current_node = children->data[offset];
+ offset = 0;
+ goto tailcall;
+ }
+ }
+ case GUMBO_NODE_TEXT:
+ case GUMBO_NODE_CDATA:
+ case GUMBO_NODE_COMMENT:
+ case GUMBO_NODE_WHITESPACE:
+ assert(offset == 0);
+ break;
+ }
+
+ offset = current_node->index_within_parent + 1;
+ GumboNode* next_node = current_node->parent;
+ callback(current_node);
+ if (current_node == node) {
+ return;
+ }
+ current_node = next_node;
+ goto tailcall;
+}
+
+static void destroy_node_callback(GumboNode* node) {
switch (node->type) {
case GUMBO_NODE_DOCUMENT: {
GumboDocument* doc = &node->v.document;
- for (unsigned int i = 0; i < doc->children.length; ++i) {
- destroy_node(doc->children.data[i]);
- }
gumbo_free((void*) doc->children.data);
gumbo_free((void*) doc->name);
gumbo_free((void*) doc->public_identifier);
@@ -2584,9 +2623,6 @@ static void destroy_node(GumboNode* node) {
gumbo_destroy_attribute(node->v.element.attributes.data[i]);
}
gumbo_free(node->v.element.attributes.data);
- for (unsigned int i = 0; i < node->v.element.children.length; ++i) {
- destroy_node(node->v.element.children.data[i]);
- }
gumbo_free(node->v.element.children.data);
break;
case GUMBO_NODE_TEXT:
@@ -2599,6 +2635,10 @@ static void destroy_node(GumboNode* node) {
gumbo_free(node);
}
+static void destroy_node(GumboNode* node) {
+ tree_traverse(node, &destroy_node_callback);
+}
+
// https://html.spec.whatwg.org/multipage/parsing.html#parsing-main-inbody
static bool handle_in_body(GumboParser* parser, GumboToken* token) {
GumboParserState* state = parser->_parser_state;
