From 4a2c65f233079d9cb070e4155ad1bfaebda56ed4 Mon Sep 17 00:00:00 2001 From: Geoffrey Allott Date: Wed, 24 Aug 2022 22:42:18 +0100 Subject: [PATCH] simplify some logic --- src/stree.c | 70 ++++++++++++++++++++++++++++------------------- test/test_stree.c | 2 +- 2 files changed, 43 insertions(+), 29 deletions(-) diff --git a/src/stree.c b/src/stree.c index 5b68bfe..37ec431 100644 --- a/src/stree.c +++ b/src/stree.c @@ -65,30 +65,49 @@ static void node_split_son(struct node *self, struct node *edge, struct node *br self->son = split; } +static void node_sort_sons(struct node *self) +{ + struct node *node, *brother, *tmp; + + for (brother = (struct node *) 0, node = self->son; node && node->brother; brother = node, node = node->brother) { + if (node->to > node->brother->to) { + if (brother) { + tmp = node->brother; + node->brother = node->brother->brother; + tmp->brother = node; + brother->brother = tmp; + } else { + tmp = node->brother; + node->brother = node->brother->brother; + tmp->brother = node; + self->son = tmp; + } + brother = (struct node *) 0; + node = self->son; + } + } +} + static struct node *node_edge_inv(struct node *self, uint8_t edge, const uint8_t *str, struct node **brother, bool seen[], uint8_t *code, bool record_seen) { struct node *node; if (record_seen) { - for (node = self->son; node; node = node->brother) { + node_sort_sons(self); + + for (*brother = (struct node *) 0, node = self->son; node; *brother = node, node = node->brother) { if (!seen[str[node->from]]) { seen[str[node->from]] = true; - if (*code == 0) { - edge = str[node->from]; - break; - } + if (*code == 0) return node; --*code; } } - if (!node) { - return (struct node *) 0; - } + } else { + for (*brother = (struct node *) 0, node = self->son; node; *brother = node, node = node->brother) + if (str[node->from] == edge) + return node; } - for (*brother = (struct node *) 0, node = self->son; node; *brother = node, node = node->brother) - if (str[node->from] == edge) - return node; - return (struct node *) 0; } @@ -97,20 +116,21 @@ static struct node *node_edge(struct node *self, uint8_t edge, const uint8_t *st struct node *node; if (record_seen) { - for (node = self->son; node; node = node->brother) { - if (str[node->from] == edge) - break; + node_sort_sons(self); + + for (*brother = (struct node *) 0, node = self->son; node; *brother = node, node = node->brother) { + if (str[node->from] == edge) return node; if (!seen[str[node->from]]) { seen[str[node->from]] = true; ++*code; } } + } else { + for (*brother = (struct node *) 0, node = self->son; node; *brother = node, node = node->brother) + if (str[node->from] == edge) + return node; } - for (*brother = (struct node *) 0, node = self->son; node; *brother = node, node = node->brother) - if (str[node->from] == edge) - return node; - return (struct node *) 0; } @@ -161,7 +181,6 @@ int stree_encode(size_t len, const uint8_t *in, uint8_t *out, size_t *aux) struct node *active_node; struct node *active_edge = (struct node *) 0; struct node *brother = (struct node *) 0; - struct node *new_leaf; size_t active_len = 0; size_t rem = 0; size_t i; @@ -193,7 +212,6 @@ int stree_encode(size_t len, const uint8_t *in, uint8_t *out, size_t *aux) if (!active_edge) { node_init(nodes + n, i); node_add_son(active_node, nodes + n); - new_leaf = nodes + n; ++n, --rem; } else { if (!seen[in[active_edge->from+active_len]]) { @@ -205,13 +223,12 @@ int stree_encode(size_t len, const uint8_t *in, uint8_t *out, size_t *aux) if (prev) prev->link = nodes + n; prev = nodes + n, n += 2, --rem; if (active_node == root) --active_len; - new_leaf = (struct node *) 0; } active_node = active_node->link ? active_node->link : (active_len = rem - 1, root); - if (active_len == 0 && active_node->son == new_leaf) + if (active_len == 0 && active_node->son == nodes + n - 1) brother = active_edge = (struct node *) 0; else - active_edge = node_edge(active_node, in[i-active_len], in, &brother, seen, &code, active_len == 0 && active_node->son != new_leaf); + active_edge = node_edge(active_node, in[i-active_len], in, &brother, seen, &code, active_len == 0); } while (active_edge && active_edge->from + active_len >= active_edge->to) { active_node = active_edge; @@ -250,7 +267,6 @@ int stree_decode(size_t len, const uint8_t *in, uint8_t *out, size_t *aux) struct node *active_node; struct node *active_edge = (struct node *) 0; struct node *brother = (struct node *) 0; - struct node *new_leaf; size_t active_len = 0; size_t rem = 0; size_t i, n; @@ -283,7 +299,6 @@ int stree_decode(size_t len, const uint8_t *in, uint8_t *out, size_t *aux) if (!active_edge) { node_init(nodes + n, i); node_add_son(active_node, nodes + n); - new_leaf = nodes + n; ++n, --rem; } else { if (!seen[out[active_edge->from+active_len]]) { @@ -295,10 +310,9 @@ int stree_decode(size_t len, const uint8_t *in, uint8_t *out, size_t *aux) if (prev) prev->link = nodes + n; prev = nodes + n, n += 2, --rem; if (active_node == root) --active_len; - new_leaf = (struct node *) 0; } active_node = active_node->link ? active_node->link : (active_len = rem - 1, root); - if (active_len == 0 && active_node->son == new_leaf) + if (active_len == 0 && active_node->son == nodes + n - 1) brother = active_edge = (struct node *) 0; else active_edge = node_edge_inv(active_node, out[i-active_len], out, &brother, seen, &code, active_len == 0); diff --git a/test/test_stree.c b/test/test_stree.c index 9047cd6..acae1ca 100644 --- a/test/test_stree.c +++ b/test/test_stree.c @@ -58,7 +58,7 @@ static enum test_result test_stree_encode_so_example(void) ASSERT_EQ(2, out[3]); ASSERT_EQ(0, out[4]); ASSERT_EQ('x', out[5]); - ASSERT_EQ(3, out[6]); + ASSERT_EQ(1, out[6]); ASSERT_EQ(0, out[7]); ASSERT_EQ(0, out[8]); ASSERT_EQ('e', out[9]); -- 2.34.1