From 1a0de0017f7b2061bad0b695a98963ca0f274e21 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Sat, 20 Nov 2021 13:42:07 +0100 Subject: grid: add grid_row_uri_range_erase() This function handles erasing of an URI range. That is, a range of the row is being either erased, or overwritten (from the URI perspective, these two are the same thing). We handle both partial overwrites (split up, or truncate URI), as well as complete overwrites (remove URI). --- grid.c | 156 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 151 insertions(+), 5 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index 733d8ded..d98c4696 100644 --- a/grid.c +++ b/grid.c @@ -236,7 +236,7 @@ grid_resize_without_reflow( .id = it->item.id, .uri = xstrdup(it->item.uri), }; - grid_row_add_uri_range(new_row, range); + grid_row_uri_range_add(new_row, range); } } @@ -303,7 +303,7 @@ reflow_uri_range_start(struct row_uri_range *range, struct row *new_row, .uri = range->uri, }; range->uri = NULL; - grid_row_add_uri_range(new_row, new_range); + grid_row_uri_range_add(new_row, new_range); } static void @@ -366,7 +366,7 @@ _line_wrap(struct grid *old_grid, struct row **new_grid, struct row *row, .id = range->id, .uri = xstrdup(range->uri), }; - grid_row_add_uri_range(new_row, new_range); + grid_row_uri_range_add(new_row, new_range); } } @@ -845,14 +845,160 @@ ensure_row_has_extra_data(struct row *row) } void -grid_row_add_uri_range(struct row *row, struct row_uri_range range) +grid_row_uri_range_add(struct row *row, struct row_uri_range range) { ensure_row_has_extra_data(row); tll_rforeach(row->extra->uri_ranges, it) { if (it->item.end < range.start) { tll_insert_after(row->extra->uri_ranges, it, range); - return; + goto out; } } + tll_push_front(row->extra->uri_ranges, range); + +out: + ; +#if defined(_DEBUG) + tll_foreach(row->extra->uri_ranges, it1) { + tll_foreach(row->extra->uri_ranges, it2) { + if (&it1->item == &it2->item) + continue; + + xassert(it1->item.start != it2->item.start); + xassert(it1->item.start != it2->item.end); + xassert(it1->item.end != it2->item.start); + xassert(it1->item.end != it2->item.end); + } + } +#endif +} + +void +grid_row_uri_range_erase(struct row *row, int start, int end) +{ + if (likely(row->extra == NULL)) + return; + + /* Split up, or remove, URI ranges affected by the erase */ + tll_foreach(row->extra->uri_ranges, it) { + if (it->item.start > end) { + /* This range, and all subsequent ranges, start *after* + * the erase range */ + break; + } + + if (it->item.start < start && it->item.end >= start) { + /* + * URI crosses the erase *start* point. + * + * Create a new range for the URI part *before* the erased + * cells. + * + * Also modify this URI range’s start point so that we can + * remove it below. + */ + struct row_uri_range range_before = { + .start = it->item.start, + .end = start - 1, + .id = it->item.id, + .uri = it->item.uri != NULL ? xstrdup(it->item.uri) : NULL, + }; + tll_insert_before(row->extra->uri_ranges, it, range_before); + it->item.start = start; + } + + if (it->item.start <= end && it->item.end > end) { + /* + * URI crosses the erase *end* point. + * + * Create a new range for the URI part *after* the erased + * cells. + * + * Also modify the URI range’s end point so that we can + * remove it below. + */ + struct row_uri_range range_after = { + .start = end + 1, + .end = it->item.end, + .id = it->item.id, + .uri = it->item.uri != NULL ? xstrdup(it->item.uri) : NULL, + }; + tll_insert_before(row->extra->uri_ranges, it, range_after); + it->item.end = end; + } + + if (it->item.start >= start && it->item.end <= end) { + /* URI range completey covered by the erase - remove it */ + free(it->item.uri); + tll_remove(row->extra->uri_ranges, it); + } + } +} + +UNITTEST +{ + struct row_data row_data = {.uri_ranges = tll_init()}; + struct row row = {.extra = &row_data}; + +#define row_has_no_overlapping_uris(row) \ + do { \ + tll_foreach((row)->extra->uri_ranges, it1) { \ + tll_foreach((row)->extra->uri_ranges, it2) { \ + if (&it1->item == &it2->item) \ + continue; \ + xassert(it1->item.start != it2->item.start); \ + xassert(it1->item.start != it2->item.end); \ + xassert(it1->item.end != it2->item.start); \ + xassert(it1->item.end != it2->item.end); \ + } \ + } \ + } while (0) + + grid_row_uri_range_add(&row, (struct row_uri_range){1, 10}); + xassert(tll_length(row_data.uri_ranges) == 1); + xassert(tll_front(row_data.uri_ranges).start == 1); + xassert(tll_front(row_data.uri_ranges).end == 10); + row_has_no_overlapping_uris(&row); + + grid_row_uri_range_add(&row, (struct row_uri_range){11, 20}); + xassert(tll_length(row_data.uri_ranges) == 2); + xassert(tll_back(row_data.uri_ranges).start == 11); + xassert(tll_back(row_data.uri_ranges).end == 20); + row_has_no_overlapping_uris(&row); + + /* Erase both URis */ + grid_row_uri_range_erase(&row, 1, 20); + xassert(tll_length(row_data.uri_ranges) == 0); + row_has_no_overlapping_uris(&row); + + /* Two URIs, then erase second half of the first, first half of + the second */ + grid_row_uri_range_add(&row, (struct row_uri_range){1, 10}); + grid_row_uri_range_add(&row, (struct row_uri_range){11, 20}); + grid_row_uri_range_erase(&row, 5, 15); + xassert(tll_length(row_data.uri_ranges) == 2); + xassert(tll_front(row_data.uri_ranges).start == 1); + xassert(tll_front(row_data.uri_ranges).end == 4); + xassert(tll_back(row_data.uri_ranges).start == 16); + xassert(tll_back(row_data.uri_ranges).end == 20); + row_has_no_overlapping_uris(&row); + + tll_pop_back(row_data.uri_ranges); + tll_pop_back(row_data.uri_ranges); + xassert(tll_length(row_data.uri_ranges) == 0); + + /* One URI, erase middle part of it */ + grid_row_uri_range_add(&row, (struct row_uri_range){1, 10}); + grid_row_uri_range_erase(&row, 5, 6); + xassert(tll_length(row_data.uri_ranges) == 2); + xassert(tll_front(row_data.uri_ranges).start == 1); + xassert(tll_front(row_data.uri_ranges).end == 4); + xassert(tll_back(row_data.uri_ranges).start == 7); + xassert(tll_back(row_data.uri_ranges).end == 10); + row_has_no_overlapping_uris(&row); + +#undef row_has_no_overlapping_uris + + tll_free(row_data.uri_ranges); } -- cgit v1.3 From 503c2ebd50caaf1d50b57c42d319973277a583e0 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Sat, 20 Nov 2021 14:40:16 +0100 Subject: grid: row_uri_range_erase(): assume caller has checked row->extra != NULL --- grid.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index d98c4696..22405356 100644 --- a/grid.c +++ b/grid.c @@ -877,8 +877,7 @@ out: void grid_row_uri_range_erase(struct row *row, int start, int end) { - if (likely(row->extra == NULL)) - return; + xassert(row->extra != NULL); /* Split up, or remove, URI ranges affected by the erase */ tll_foreach(row->extra->uri_ranges, it) { -- cgit v1.3 From f27ccd999ef6fcf10f99aed9f6aec449fe071551 Mon Sep 17 00:00:00 2001 From: Daniel Eklöf Date: Sat, 20 Nov 2021 15:46:20 +0100 Subject: grid: refactor grid_row_uri_range_erase() MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit The old algorithm always created a new URI, followed by (maybe) removing the existing URI, when an URI needed to be modified. That is, if e.g. the tail of an URI was being erased, the old algorithm would create a new URI for the part of the URI that should remain, and then removed the old URI. This isn’t very effective. The new algorithm instead identifies all possible overlap cases, and handles each one differently: * URI ends *before* erase range starts - continue with the next URI without further checks * URI starts *after* the erase range ends - return, we’re done * Erase range erases the entire URI - remove the URI * Erase range erases a part in the middle - split the URI * Erase range erases the head of the URI - adjust the URI’s start * Erase range erases the tail of the URI - adjust the URI’s end --- grid.c | 75 ++++++++++++++++++++++++++++-------------------------------------- 1 file changed, 32 insertions(+), 43 deletions(-) (limited to 'grid.c') diff --git a/grid.c b/grid.c index 22405356..459fa369 100644 --- a/grid.c +++ b/grid.c @@ -878,59 +878,48 @@ void grid_row_uri_range_erase(struct row *row, int start, int end) { xassert(row->extra != NULL); + xassert(start <= end); /* Split up, or remove, URI ranges affected by the erase */ tll_foreach(row->extra->uri_ranges, it) { - if (it->item.start > end) { - /* This range, and all subsequent ranges, start *after* - * the erase range */ - break; - } + struct row_uri_range *old = &it->item; - if (it->item.start < start && it->item.end >= start) { - /* - * URI crosses the erase *start* point. - * - * Create a new range for the URI part *before* the erased - * cells. - * - * Also modify this URI range’s start point so that we can - * remove it below. - */ - struct row_uri_range range_before = { - .start = it->item.start, - .end = start - 1, - .id = it->item.id, - .uri = it->item.uri != NULL ? xstrdup(it->item.uri) : NULL, - }; - tll_insert_before(row->extra->uri_ranges, it, range_before); - it->item.start = start; + if (old->end < start) + continue; + + if (old->start > end) + return; + + if (start <= old->start && end >= old->end) { + /* Erase range covers URI completely - remove it */ + grid_row_uri_range_destroy(old); + tll_remove(row->extra->uri_ranges, it); } - if (it->item.start <= end && it->item.end > end) { - /* - * URI crosses the erase *end* point. - * - * Create a new range for the URI part *after* the erased - * cells. - * - * Also modify the URI range’s end point so that we can - * remove it below. - */ - struct row_uri_range range_after = { + else if (start > old->start && end < old->end) { + /* Erase range erases a part in the middle of the URI */ + struct row_uri_range old_tail = { .start = end + 1, - .end = it->item.end, - .id = it->item.id, - .uri = it->item.uri != NULL ? xstrdup(it->item.uri) : NULL, + .end = old->end, + .id = old->id, + .uri = old->uri != NULL ? xstrdup(old->uri) : NULL, }; - tll_insert_before(row->extra->uri_ranges, it, range_after); - it->item.end = end; + tll_insert_after(row->extra->uri_ranges, it, old_tail); + old->end = start - 1; + return; /* There can be no more URIs affected by the erase range */ } - if (it->item.start >= start && it->item.end <= end) { - /* URI range completey covered by the erase - remove it */ - free(it->item.uri); - tll_remove(row->extra->uri_ranges, it); + else if (start <= old->start && end >= old->start) { + /* Erase range erases the head of the URI */ + xassert(start <= old->start); + old->start = end + 1; + return; /* There can be no more overlapping URIs */ + } + + else if (start <= old->end && end >= old->end) { + /* Erase range erases the tail of the URI */ + xassert(end >= old->end); + old->end = start - 1; } } } -- cgit v1.3