From e5a5469c5ea0df72c5e0bb6f742923ba692ea7f8 Mon Sep 17 00:00:00 2001 From: Jesper Jensen Date: Sat, 29 Mar 2025 23:28:17 +0100 Subject: Separate the tree expander out --- cmd/main.c | 155 +++++++++++++++++++---------------------------------------- src/tree.c | 77 +++++++++++++++++++++++++++++ src/tree.h | 23 +++++++++ test/parse.c | 30 ++++++++---- 4 files changed, 170 insertions(+), 115 deletions(-) create mode 100644 src/tree.c create mode 100644 src/tree.h diff --git a/cmd/main.c b/cmd/main.c index 5e72fea..dd95024 100644 --- a/cmd/main.c +++ b/cmd/main.c @@ -11,23 +11,11 @@ #include "leven.h" #include "parse.h" #include "log.h" +#include "tree.h" -#define ACTIONS(X) \ - X(ACTION_MATCH) \ - X(ACTION_DEL_A) \ - X(ACTION_ADD_B) \ - X(ACTION_ET) \ - -#define ENUM_VALUE(NAME) NAME, -#define STRING_ARRAY_VALUE(NAME) #NAME, - -enum Action { - ACTIONS(ENUM_VALUE) -}; - -static const char *ActionNames[] = { - ACTIONS(STRING_ARRAY_VALUE) -}; +size_t max(size_t a, size_t b) { + return a > b ? a : b; +} int main(int argc, char **argv) { int rc; @@ -74,18 +62,41 @@ int main(int argc, char **argv) { size_t *b_opens = malloc(b_tree.len * sizeof(size_t)); { - size_t *a_cursor = a_opens; - for(size_t i = 0; i < a_tree.len*2; i++) { - if(a_chunks[i] >= 0) { - *(a_cursor++) = a_chunks[i]; + size_t *stack_base = malloc(max(a_tree.len, b_tree.len) * sizeof(size_t)); + { + size_t *stack = stack_base; + size_t *write_cursor = a_opens; + ssize_t *read_cursor = a_chunks; + struct Tree tree = a_tree; + + for(size_t i = 0; i < tree.len; i++) { + *(write_cursor++) = *(read_cursor++); + + while(*stack < tree.adj.stride && *imat_nid(tree.adj, *stack, i) != 0) (*stack)++; + stack++; + // @CLEANUP: Maybe it would be nicer if we just added a fake + // element to the start of the array to abosrb the read + while(stack > stack_base && stack[-1] == 0) { + (stack--); + (*stack)--; + } } } - } - { - size_t *b_cursor = b_opens; - for(size_t i = 0; i < b_tree.len*2; i++) { - if(b_chunks[i] >= 0) { - *(b_cursor++) = b_chunks[i]; + { + size_t *stack = stack_base; + size_t *write_cursor = b_opens; + ssize_t *read_cursor = b_chunks; + struct Tree tree = b_tree; + + for(size_t i = 0; i < tree.len; i++) { + *(write_cursor++) = *(read_cursor++); + + while(*stack < tree.adj.stride && *imat_nid(tree.adj, *stack, i) != 0) (*stack)++; + stack++; + while(stack > stack_base && stack[-1] == 0) { + (stack--); + (*stack)--; + } } } } @@ -97,13 +108,13 @@ int main(int argc, char **argv) { *imat_uint32_t(cost, i+1, 0) = a_len; } for(size_t j = 0; j < 4; j++) { - size_t b_tag_end = b_chunks[j]; + size_t b_tag_end = b_opens[j]; while(b[b_tag_end] != '>') b_tag_end++; - size_t b_len = b_tag_end - b_chunks[j]; + size_t b_len = b_tag_end - b_opens[j]; *imat_uint32_t(cost, 0, j+1) = b_len; } for(size_t j = 0; j < 4; j++) { - size_t b_tag_end = b_chunks[j]; + size_t b_tag_end = b_opens[j]; while(b[b_tag_end] != '>') b_tag_end++; for(size_t i = 0; i < 4; i++) { size_t a_tag_end = a_opens[i]; @@ -111,11 +122,11 @@ int main(int argc, char **argv) { log("%ld, %ld", i, j); size_t a_len = a_tag_end - a_opens[i]; - size_t b_len = b_tag_end - b_chunks[j]; + size_t b_len = b_tag_end - b_opens[j]; log("B: %ld, A: %ld", b_len, a_len); - log("A: %.*s, B: %.*s", (int)a_len, a + a_opens[i], (int)b_len, b + b_chunks[j]); + log("A: %.*s, B: %.*s", (int)a_len, a + a_opens[i], (int)b_len, b + b_opens[j]); - *imat_uint32_t(cost, i+1, j+1) = !(a_len == b_len && memcmp(a + a_opens[i], b + b_chunks[j], a_len) == 0) * 1; + *imat_uint32_t(cost, i+1, j+1) = !(a_len == b_len && memcmp(a + a_opens[i], b + b_opens[j], a_len) == 0) * 1; } } printf("\n"); @@ -188,88 +199,20 @@ int main(int argc, char **argv) { // going to solve right now. I think we may have to lookup what decision // we made for the open tag // The worst case would be that we remove the whole A tree and the whole B tree - enum Action *emit_actions = malloc((a_tree.len + b_tree.len) * 2 * sizeof(*emit_actions)); - size_t current_action = 0; - size_t a_cursor = 0; - size_t b_cursor = 0; - size_t alignment_cursor = 0; - - size_t *a_close = malloc(a_tree.len * sizeof(size_t)); - size_t a_close_top = 0; - size_t *b_close = malloc(b_tree.len * sizeof(size_t)); - size_t b_close_top = 0; - - while(a_cursor < a_tree.len && b_cursor < b_tree.len) { - if(alignment[alignment_cursor] == 0) { - alignment_cursor++; - emit_actions[current_action++] = ACTION_ADD_B; - - b_close[b_close_top] = 0; - while(b_close[b_close_top] < b_tree.adj.stride && *imat_nid(b_tree.adj, b_close[b_close_top], b_cursor) != 0) - b_close[b_close_top]++; - b_close_top++; - - b_cursor++; - } else if(a_cursor + 1 < alignment[alignment_cursor]) { - emit_actions[current_action++] = ACTION_DEL_A; - - a_close[a_close_top] = 0; - while(a_close[a_close_top] < a_tree.adj.stride && *imat_nid(a_tree.adj, a_close[a_close_top], a_cursor) != 0) - a_close[a_close_top]++; - a_close_top++; - - a_cursor++; - } else { - alignment_cursor++; - emit_actions[current_action++] = ACTION_MATCH; - - b_close[b_close_top] = 0; - while(b_close[b_close_top] < b_tree.adj.stride && *imat_nid(b_tree.adj, b_close[b_close_top], b_cursor) != 0) - b_close[b_close_top]++; - b_close_top++; - - a_close[a_close_top] = 0; - while(a_close[a_close_top] < a_tree.adj.stride && *imat_nid(a_tree.adj, a_close[a_close_top], a_cursor) != 0) - a_close[a_close_top]++; - a_close_top++; - - a_cursor++; - b_cursor++; - } - - while(a_close[a_close_top-1] == 0 || b_close[b_close_top-1] == 0) { - if(a_close[a_close_top-1] == 0 && b_close[b_close_top-1] == 0) { - a_close_top--; - a_close[a_close_top-1]--; - b_close_top--; - b_close[b_close_top-1]--; - - emit_actions[current_action++] = ACTION_MATCH; - } else if(a_close[a_close_top-1] == 0) { - a_close_top--; - a_close[a_close_top-1]--; - - emit_actions[current_action++] = ACTION_DEL_A; - } else if(b_close[b_close_top-1] == 0) { - b_close_top--; - b_close[b_close_top-1]--; - - emit_actions[current_action++] = ACTION_ADD_B; - } - } - } + enum Action *emit_actions = malloc((a_tree.len + b_tree.len) * 2 * sizeof(*emit_actions) + 1); + expand_alignment(a_tree, b_tree, alignment, emit_actions); logb("Actions: "); - for(size_t i = 0; i < current_action; i++) { + for(size_t i = 0; emit_actions[i] != ACTION_END; i++) { lognl(); logc(" %s", ActionNames[emit_actions[i]]); } loge(); - b_cursor = 0; - a_cursor = 0; + size_t a_cursor = 0; + size_t b_cursor = 0; - for(size_t i = 0; i < current_action; i++) { + for(size_t i = 0; emit_actions[i] != ACTION_END; i++) { size_t bc_len = (b_cursor+1 >= b_tree.len*2 ? strlen(b) : b_chunks[b_cursor+1]) - b_chunks[b_cursor]; size_t ac_len = (a_cursor+1 >= a_tree.len*2 ? strlen(a) : a_chunks[a_cursor+1]) - a_chunks[a_cursor]; if(emit_actions[i] == ACTION_MATCH) { diff --git a/src/tree.c b/src/tree.c new file mode 100644 index 0000000..3bb2737 --- /dev/null +++ b/src/tree.c @@ -0,0 +1,77 @@ +#include "tree.h" + +#include + +void expand_alignment(struct Tree a_tree, struct Tree b_tree, uint32_t *alignment, enum Action *emit_actions) { + size_t current_action = 0; + size_t a_cursor = 0; + size_t b_cursor = 0; + size_t alignment_cursor = 0; + + size_t *a_close = malloc(a_tree.len * sizeof(size_t)); + size_t a_close_top = 0; + size_t *b_close = malloc(b_tree.len * sizeof(size_t)); + size_t b_close_top = 0; + + while(a_cursor < a_tree.len && b_cursor < b_tree.len) { + if(alignment[alignment_cursor] == 0) { + alignment_cursor++; + emit_actions[current_action++] = ACTION_ADD_B; + + b_close[b_close_top] = 0; + while(b_close[b_close_top] < b_tree.adj.stride && *imat_nid(b_tree.adj, b_close[b_close_top], b_cursor) != 0) + b_close[b_close_top]++; + b_close_top++; + + b_cursor++; + } else if(a_cursor + 1 < alignment[alignment_cursor]) { + emit_actions[current_action++] = ACTION_DEL_A; + + a_close[a_close_top] = 0; + while(a_close[a_close_top] < a_tree.adj.stride && *imat_nid(a_tree.adj, a_close[a_close_top], a_cursor) != 0) + a_close[a_close_top]++; + a_close_top++; + + a_cursor++; + } else { + alignment_cursor++; + emit_actions[current_action++] = ACTION_MATCH; + + b_close[b_close_top] = 0; + while(b_close[b_close_top] < b_tree.adj.stride && *imat_nid(b_tree.adj, b_close[b_close_top], b_cursor) != 0) + b_close[b_close_top]++; + b_close_top++; + + a_close[a_close_top] = 0; + while(a_close[a_close_top] < a_tree.adj.stride && *imat_nid(a_tree.adj, a_close[a_close_top], a_cursor) != 0) + a_close[a_close_top]++; + a_close_top++; + + a_cursor++; + b_cursor++; + } + + while(a_close[a_close_top-1] == 0 || b_close[b_close_top-1] == 0) { + if(a_close[a_close_top-1] == 0 && b_close[b_close_top-1] == 0) { + a_close_top--; + a_close[a_close_top-1]--; + b_close_top--; + b_close[b_close_top-1]--; + + emit_actions[current_action++] = ACTION_MATCH; + } else if(a_close[a_close_top-1] == 0) { + a_close_top--; + a_close[a_close_top-1]--; + + emit_actions[current_action++] = ACTION_DEL_A; + } else if(b_close[b_close_top-1] == 0) { + b_close_top--; + b_close[b_close_top-1]--; + + emit_actions[current_action++] = ACTION_ADD_B; + } + } + } + + emit_actions[current_action] = ACTION_END; +} diff --git a/src/tree.h b/src/tree.h new file mode 100644 index 0000000..e1dd424 --- /dev/null +++ b/src/tree.h @@ -0,0 +1,23 @@ +#pragma once + +#include "parse.h" +#include + +#define ACTIONS(X) \ + X(ACTION_MATCH) \ + X(ACTION_DEL_A) \ + X(ACTION_ADD_B) \ + X(ACTION_END) \ + +#define ENUM_VALUE(NAME) NAME, +#define STRING_ARRAY_VALUE(NAME) #NAME, + +enum Action { + ACTIONS(ENUM_VALUE) +}; + +static const char *ActionNames[] = { + ACTIONS(STRING_ARRAY_VALUE) +}; + +void expand_alignment(struct Tree a_tree, struct Tree b_tree, uint32_t *alignment, enum Action *emit_actions); diff --git a/test/parse.c b/test/parse.c index 328bfd3..e1474cd 100644 --- a/test/parse.c +++ b/test/parse.c @@ -17,7 +17,7 @@ int main(int argc, char **argv) { { struct Tree a; - size_t *chunks = NULL; + ssize_t *chunks = NULL; if(parse_string("", &a, &chunks) != 0) return fail(); if(a.adj.stride != 1) return fail(); if(a.len != 1) return fail(); @@ -28,6 +28,7 @@ int main(int argc, char **argv) { // Verify chunk offsets if(chunks[0] != 0) return fail(); + if(chunks[1] != 6) return fail(); free(chunks); free(a.adj.data); @@ -35,7 +36,7 @@ int main(int argc, char **argv) { { struct Tree a; - size_t *chunks = NULL; + ssize_t *chunks = NULL; if(parse_string(" ", &a, &chunks) != 0) return fail(); if(a.adj.stride != 1) return fail(); if(a.len != 1) return fail(); @@ -46,6 +47,7 @@ int main(int argc, char **argv) { // Verify chunk offsets if(chunks[0] != 0) return fail(); + if(chunks[1] != 7) return fail(); free(chunks); free(a.adj.data); @@ -53,7 +55,7 @@ int main(int argc, char **argv) { { struct Tree a; - size_t *chunks = NULL; + ssize_t *chunks = NULL; if(parse_string("\n", &a, &chunks) != 0) return fail(); if(a.adj.stride != 1) return fail(); if(a.len != 1) return fail(); @@ -64,6 +66,7 @@ int main(int argc, char **argv) { // Verify chunk offsets if(chunks[0] != 0) return fail(); + if(chunks[1] != 7) return fail(); free(chunks); free(a.adj.data); @@ -71,7 +74,7 @@ int main(int argc, char **argv) { { struct Tree a; - size_t *chunks = NULL; + ssize_t *chunks = NULL; if(parse_string("", &a, &chunks) != 0) return fail(); if(a.adj.stride != 2) return fail(); if(a.len != 3) return fail(); @@ -85,7 +88,10 @@ int main(int argc, char **argv) { // Verify chunk offsets if(chunks[0] != 0) return fail(); if(chunks[1] != 6) return fail(); - if(chunks[2] != 13) return fail(); + if(chunks[2] != 9) return fail(); + if(chunks[3] != 13) return fail(); + if(chunks[4] != 16) return fail(); + if(chunks[5] != 20) return fail(); free(chunks); free(a.adj.data); @@ -93,7 +99,7 @@ int main(int argc, char **argv) { { struct Tree a; - size_t *chunks = NULL; + ssize_t *chunks = NULL; if(parse_string("", &a, &chunks) != 0) return fail(); if(a.adj.stride != 2) return fail(); if(a.len != 4) return fail(); @@ -109,7 +115,11 @@ int main(int argc, char **argv) { if(chunks[0] != 0) return fail(); if(chunks[1] != 6) return fail(); if(chunks[2] != 9) return fail(); - if(chunks[3] != 20) return fail(); + if(chunks[3] != 12) return fail(); + if(chunks[4] != 16) return fail(); + if(chunks[5] != 20) return fail(); + if(chunks[6] != 23) return fail(); + if(chunks[7] != 27) return fail(); free(chunks); free(a.adj.data); @@ -118,7 +128,7 @@ int main(int argc, char **argv) { // We forgot to close the open tag { struct Tree a; - size_t *chunks = NULL; + ssize_t *chunks = NULL; fflush(stdout); if(parse_string("", &a, &chunks) != 1) return fail(); fflush(stdout); @@ -127,7 +137,7 @@ int main(int argc, char **argv) { // Test self-closing tag { struct Tree a; - size_t *chunks = NULL; + ssize_t *chunks = NULL; fflush(stdout); if(parse_string("", &a, &chunks) != 0) return fail(); if(a.adj.stride != 1) return fail(); @@ -141,6 +151,8 @@ int main(int argc, char **argv) { // Verify chunk offsets if(chunks[0] != 0) return fail(); if(chunks[1] != 6) return fail(); + if(chunks[2] != 9) return fail(); + if(chunks[3] != 11) return fail(); free(chunks); free(a.adj.data); -- cgit v1.2.3