From d548d56d604193e4eebb4ab81c347887763b7d69 Mon Sep 17 00:00:00 2001 From: Nick Wellnhofer Date: Sat, 10 Jan 2015 16:10:22 +0100 Subject: Optimize S_is_leaf --- src/iterator.c | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-) diff --git a/src/iterator.c b/src/iterator.c index a3ae415..0354eff 100644 --- a/src/iterator.c +++ b/src/iterator.c @@ -5,6 +5,16 @@ #include "cmark.h" #include "iterator.h" +static const int S_leaf_mask = + (1 << CMARK_NODE_HTML) | + (1 << CMARK_NODE_HRULE) | + (1 << CMARK_NODE_CODE_BLOCK) | + (1 << CMARK_NODE_TEXT) | + (1 << CMARK_NODE_SOFTBREAK) | + (1 << CMARK_NODE_LINEBREAK) | + (1 << CMARK_NODE_CODE) | + (1 << CMARK_NODE_INLINE_HTML); + cmark_iter* cmark_iter_new(cmark_node *root) { @@ -31,21 +41,10 @@ cmark_iter_next(cmark_iter *iter) return iter->event_type; } -int S_is_leaf(cmark_node *node) +static bool +S_is_leaf(cmark_node *node) { - switch (cmark_node_get_type(node)) { - case CMARK_NODE_HTML: - case CMARK_NODE_HRULE: - case CMARK_NODE_CODE_BLOCK: - case CMARK_NODE_TEXT: - case CMARK_NODE_SOFTBREAK: - case CMARK_NODE_LINEBREAK: - case CMARK_NODE_CODE: - case CMARK_NODE_INLINE_HTML: - return 1; - default: - return 0; - } + return (1 << node->type) & S_leaf_mask; } void -- cgit v1.2.3 From 009c3847f004fda437dd5376a9452973b1cb913e Mon Sep 17 00:00:00 2001 From: Nick Wellnhofer Date: Sat, 10 Jan 2015 16:10:35 +0100 Subject: Rework iterators * Advance to the next node when calling 'cmark_iter_next', not when calling 'cmark_iter_get_node'. * Add 'cmark_iter_get_event_type' accessor. * Allow deletion of nodes after an 'EXIT' event, or an 'ENTER' event for leaf nodes. --- api_test/main.c | 41 ++++++++++++++++++++++++ src/cmark.h | 7 +++++ src/iterator.c | 98 +++++++++++++++++++++++++++++++++------------------------ src/iterator.h | 10 ++++-- 4 files changed, 112 insertions(+), 44 deletions(-) diff --git a/api_test/main.c b/api_test/main.c index d2e41d3..af40a9f 100644 --- a/api_test/main.c +++ b/api_test/main.c @@ -319,6 +319,46 @@ iterator(test_batch_runner *runner) { cmark_node_free(doc); } +static void +iterator_delete(test_batch_runner *runner) { + static const char md[] = + "a *b* c\n" + "\n" + "* item1\n" + "* item2\n" + "\n" + "a `b` c\n" + "\n" + "* item1\n" + "* item2\n"; + cmark_node *doc = cmark_parse_document(md, sizeof(md) - 1); + cmark_iter *iter = cmark_iter_new(doc); + cmark_event_type ev_type; + + while ((ev_type = cmark_iter_next(iter)) != CMARK_EVENT_DONE) { + cmark_node *node = cmark_iter_get_node(iter); + // Delete list, emph, and code nodes. + if ((ev_type == CMARK_EVENT_EXIT && + node->type == CMARK_NODE_LIST) || + (ev_type == CMARK_EVENT_EXIT && + node->type == CMARK_NODE_EMPH) || + (ev_type == CMARK_EVENT_ENTER && + node->type == CMARK_NODE_CODE)) { + cmark_node_free(node); + } + } + + char *html = cmark_render_html(doc, CMARK_OPT_DEFAULT); + static const char expected[] = + "

a c

\n" + "

a c

\n"; + STR_EQ(runner, html, expected, "iterate and delete nodes"); + + free(html); + cmark_iter_free(iter); + cmark_node_free(doc); +} + static void create_tree(test_batch_runner *runner) { @@ -630,6 +670,7 @@ int main() { accessors(runner); node_check(runner); iterator(runner); + iterator_delete(runner); create_tree(runner); hierarchy(runner); parser(runner); diff --git a/src/cmark.h b/src/cmark.h index 72650c9..b153124 100644 --- a/src/cmark.h +++ b/src/cmark.h @@ -83,6 +83,7 @@ typedef struct cmark_parser cmark_parser; typedef struct cmark_iter cmark_iter; typedef enum { + CMARK_EVENT_NONE, CMARK_EVENT_DONE, CMARK_EVENT_ENTER, CMARK_EVENT_EXIT @@ -204,6 +205,12 @@ CMARK_EXPORT cmark_node* cmark_iter_get_node(cmark_iter *iter); +/** Returns the current event type. + */ +CMARK_EXPORT +cmark_event_type +cmark_iter_get_event_type(cmark_iter *iter); + /** * ## Accessors */ diff --git a/src/iterator.c b/src/iterator.c index 0354eff..7f90cc7 100644 --- a/src/iterator.c +++ b/src/iterator.c @@ -1,3 +1,4 @@ +#include #include #include "config.h" @@ -18,15 +19,19 @@ static const int S_leaf_mask = cmark_iter* cmark_iter_new(cmark_node *root) { + if (root == NULL) { + return NULL; + } cmark_iter *iter = (cmark_iter*)malloc(sizeof(cmark_iter)); if (iter == NULL) { return NULL; - } else { - iter->root = root; - iter->current = root; - iter->event_type = CMARK_EVENT_ENTER; - return iter; } + iter->root = root; + iter->cur.ev_type = CMARK_EVENT_NONE; + iter->cur.node = NULL; + iter->next.ev_type = CMARK_EVENT_ENTER; + iter->next.node = root; + return iter; } void @@ -35,61 +40,72 @@ cmark_iter_free(cmark_iter *iter) free(iter); } -cmark_event_type -cmark_iter_next(cmark_iter *iter) -{ - return iter->event_type; -} - static bool S_is_leaf(cmark_node *node) { return (1 << node->type) & S_leaf_mask; } -void -cmark_iter_reset(cmark_iter *iter, cmark_node *current, - cmark_event_type event_type) +cmark_event_type +cmark_iter_next(cmark_iter *iter) { - iter->event_type = event_type; - iter->current = current; -} + cmark_event_type ev_type = iter->next.ev_type; + cmark_node *node = iter->next.node; -cmark_node* -cmark_iter_get_node(cmark_iter *iter) -{ - /* we'll return current */ - cmark_node *cur = iter->current; + iter->cur.ev_type = ev_type; + iter->cur.node = node; - if (cur == NULL || iter->event_type == CMARK_EVENT_DONE) { - return NULL; + if (ev_type == CMARK_EVENT_DONE) { + return ev_type; } /* roll forward to next item, setting both fields */ - if (iter->event_type == CMARK_EVENT_ENTER && !S_is_leaf(cur)) { - if (cur->first_child == NULL) { + if (ev_type == CMARK_EVENT_ENTER && !S_is_leaf(node)) { + if (node->first_child == NULL) { /* stay on this node but exit */ - iter->event_type = CMARK_EVENT_EXIT; + iter->next.ev_type = CMARK_EVENT_EXIT; } else { - iter->current = cur->first_child; - iter->event_type = CMARK_EVENT_ENTER; + iter->next.ev_type = CMARK_EVENT_ENTER; + iter->next.node = node->first_child; } - } else if (cur == iter->root) { + } else if (node == iter->root) { /* don't move past root */ - iter->event_type = CMARK_EVENT_DONE; - iter->current = NULL; - } else if (cur->next) { - iter->event_type = CMARK_EVENT_ENTER; - iter->current = cur->next; - } else if (cur->parent) { - iter->event_type = CMARK_EVENT_EXIT; - iter->current = cur->parent; + iter->next.ev_type = CMARK_EVENT_DONE; + iter->next.node = NULL; + } else if (node->next) { + iter->next.ev_type = CMARK_EVENT_ENTER; + iter->next.node = node->next; + } else if (node->parent) { + iter->next.ev_type = CMARK_EVENT_EXIT; + iter->next.node = node->parent; } else { - iter->event_type = CMARK_EVENT_DONE; - iter->current = NULL; + assert(false); + iter->next.ev_type = CMARK_EVENT_DONE; + iter->next.node = NULL; } - return cur; + return ev_type; +} + +void +cmark_iter_reset(cmark_iter *iter, cmark_node *current, + cmark_event_type event_type) +{ + iter->next.ev_type = event_type; + iter->next.node = current; + cmark_iter_next(iter); +} + +cmark_node* +cmark_iter_get_node(cmark_iter *iter) +{ + return iter->cur.node; +} + +cmark_event_type +cmark_iter_get_event_type(cmark_iter *iter) +{ + return iter->cur.ev_type; } diff --git a/src/iterator.h b/src/iterator.h index bf53112..027b10b 100644 --- a/src/iterator.h +++ b/src/iterator.h @@ -6,12 +6,16 @@ extern "C" { #endif #include "cmark.h" -#include "node.h" + +typedef struct { + cmark_event_type ev_type; + cmark_node *node; +} cmark_iter_state; struct cmark_iter { - cmark_node *current; cmark_node *root; - cmark_event_type event_type; + cmark_iter_state cur; + cmark_iter_state next; }; #ifdef __cplusplus -- cgit v1.2.3 From fdfbe19d21822d30778a54a808b414dd280a8de6 Mon Sep 17 00:00:00 2001 From: Nick Wellnhofer Date: Sat, 10 Jan 2015 17:25:53 +0100 Subject: Update iterator documentation --- src/cmark.h | 45 ++++++++++++++++++++++++++++----------------- 1 file changed, 28 insertions(+), 17 deletions(-) diff --git a/src/cmark.h b/src/cmark.h index b153124..04ca6d7 100644 --- a/src/cmark.h +++ b/src/cmark.h @@ -165,13 +165,24 @@ cmark_node_last_child(cmark_node *node); * cmark_iter_free(iter); * } * - * Note that if you delete the current node, its first child, or its - * next sibling, the iterator may point to a nonexistent note. - * Use 'cmark_iter_reset' to set its pointer to the next node that - * should be traversed. + * Iterators will never return `EXIT` events for leaf nodes, which are nodes + * of type: + * + * * CMARK_NODE_HTML + * * CMARK_NODE_HRULE + * * CMARK_NODE_CODE_BLOCK + * * CMARK_NODE_TEXT + * * CMARK_NODE_SOFTBREAK + * * CMARK_NODE_LINEBREAK + * * CMARK_NODE_CODE + * * CMARK_NODE_INLINE_HTML + * + * Nodes must only be modified after an `EXIT` event, or an `ENTER` event for + * leaf nodes. */ -/** Creates a new iterator starting at 'root'. +/** Creates a new iterator starting at 'root'. The current node and event + * type are undefined until `cmark_iter_next` is called for the first time. */ CMARK_EXPORT cmark_iter* @@ -183,23 +194,14 @@ CMARK_EXPORT void cmark_iter_free(cmark_iter *iter); -/** Resets the iterator so that the current node is 'current' and - the event type is 'event_type'. Use this to resume after destructively - modifying the tree structure. - */ -CMARK_EXPORT -void -cmark_iter_reset(cmark_iter *iter, cmark_node *current, - cmark_event_type event_type); - -/** Returns the event type (`CMARK_EVENT_ENTER`, `CMARK_EVENT_EXIT`, - * or `CMARK_EVENT_DONE`) for the next node. +/** Advances to the next node and returns the event type (`CMARK_EVENT_ENTER`, + * `CMARK_EVENT_EXIT` or `CMARK_EVENT_DONE`). */ CMARK_EXPORT cmark_event_type cmark_iter_next(cmark_iter *iter); -/** Returns the next node in the sequence described above. +/** Returns the current node. */ CMARK_EXPORT cmark_node* @@ -211,6 +213,15 @@ CMARK_EXPORT cmark_event_type cmark_iter_get_event_type(cmark_iter *iter); +/** Resets the iterator so that the current node is 'current' and + * the event type is 'event_type'. The new current node must be a + * descendant of the root node or the root node itself. + */ +CMARK_EXPORT +void +cmark_iter_reset(cmark_iter *iter, cmark_node *current, + cmark_event_type event_type); + /** * ## Accessors */ -- cgit v1.2.3