aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Eklöf <daniel@ekloef.se>2021-11-20 14:46:20 +0000
committerDaniel Eklöf <daniel@ekloef.se>2021-11-21 17:09:27 +0000
commitf27ccd999ef6fcf10f99aed9f6aec449fe071551 (patch)
tree9337dbc8c2daa3effd1d34bfdf3a86d41985b8a0
parentgrid: row_uri_range_erase(): assume caller has checked row->extra != NULL (diff)
grid: refactor grid_row_uri_range_erase()
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
-rw-r--r--grid.c75
1 files changed, 32 insertions, 43 deletions
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;
}
}
}