You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by bn...@apache.org on 2024/01/30 16:26:46 UTC
(trafficserver-libswoc) 02/04: Fix for blending bug introduced in 1.1.2.
This is an automated email from the ASF dual-hosted git repository.
bneradt pushed a commit to branch dev-1-1-4
in repository https://gitbox.apache.org/repos/asf/trafficserver-libswoc.git
commit 5b543a2c8c5af7d44c2e1fad7936bf3e12cea1ab
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Tue Mar 31 17:57:59 2020 -0500
Fix for blending bug introduced in 1.1.2.
---
swoc++/include/swoc/DiscreteRange.h | 53 +++++++++++++++++--------------------
unit_tests/test_ip.cc | 26 ++++++++++++++++++
2 files changed, 50 insertions(+), 29 deletions(-)
diff --git a/swoc++/include/swoc/DiscreteRange.h b/swoc++/include/swoc/DiscreteRange.h
index d6f933e..4ab78fb 100644
--- a/swoc++/include/swoc/DiscreteRange.h
+++ b/swoc++/include/swoc/DiscreteRange.h
@@ -472,12 +472,7 @@ DiscreteRange<T>::is_left_adjacent_to(DiscreteRange::self_type const &that) cons
* T has a modulus and not depend on ++t > t always being true. However, we know that if t1 >
* t0 then ++t0 > t0.
*/
-
- if (_max < that._min) {
- T x(_max);
- return ++x == that._min;
- }
- return false;
+ return _max < that._min && ++metric_type(_max) == that._min;
}
template <typename T>
@@ -836,16 +831,16 @@ DiscreteSpace<METRIC, PAYLOAD>::Node::assign(PAYLOAD const &payload) -> self_typ
template<typename METRIC, typename PAYLOAD>
void DiscreteSpace<METRIC, PAYLOAD>::Node::structure_fixup() {
- if (_left) {
- if (_right) {
- _hull = this->left()->_hull.hull(this->right()->_hull);
- } else {
- _hull = this->left()->_hull;
- }
+ // Invariant: The hulls of all children are correct.
+ if (_left && _right) {
+ // If both children, local range must be inside the hull of the children and irrelevant.
+ _hull.assign(this->left()->_hull.min(), this->right()->_hull.max());
+ } else if (_left) {
+ _hull.assign(this->left()->_hull.min(), _range.max());
} else if (_right) {
- _hull = this->right()->_hull;
+ _hull.assign(_range.min(), this->right()->_hull.max());
} else {
- _hull = _range; // always contain at least self in the hull.
+ _hull = _range;
}
}
@@ -951,8 +946,7 @@ DiscreteSpace<METRIC, PAYLOAD>::insert_before(DiscreteSpace::Node *spot, Discret
template <typename METRIC, typename PAYLOAD>
void
DiscreteSpace<METRIC, PAYLOAD>::insert_after(DiscreteSpace::Node *spot, DiscreteSpace::Node *node) {
- Node *c = right(spot);
- if (!c) {
+ if (right(spot) == nullptr) {
spot->set_child(node, Direction::RIGHT);
} else {
// If there's a right child, there's a successor node, and therefore @a _next is valid.
@@ -1259,25 +1253,25 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const&range, U c
if (same_color_p && n->max() >= remaining.max()) {
return *this; // incoming range is completely covered by @a n in the same color, done.
}
- remaining.assign_min(++METRIC(n->max())); // going to fill up n->max(), clip target.
+ remaining.assign_min(++metric_type(n->max())); // going to fill up n->max(), clip target.
if (! same_color_p) {
- n->assign_max(--METRIC(remaining.min())); // clip @a n down.
+ n->assign_max(--metric_type(remaining.min())); // clip @a n down.
this->insert_after(n, fill.get()); // add intersection node in different color.
- n = fill.release();
+ n = fill.release(); // skip to use new node as current node.
}
} else { // clear, don't fill.
- auto max = n->max(); // cache this before reassigning.
- if (max > remaining.max()) { // overhang on the right, must split.
- fill.release();
- this->insert_before(n, _fa.make(n->min(), --METRIC(remaining.min()), n->payload()));
- n->assign_min(++METRIC(remaining.max()));
+ auto n_r = n->range(); // cache to avoid ordering requirements.
+ if (n_r.max() > remaining.max()) { // overhang on the right, must split.
+ fill.release(); // not going to use it,
+ n->assign_min(++metric_type(remaining.max()));
+ this->insert_before(n, _fa.make(n_r.min(), --metric_type(remaining.min()), n->payload()));
return *this;
}
- n->assign_max(--METRIC(remaining.min())); // clip @a n down.
- if (max == remaining.max()) {
+ n->assign_max(--metric_type(remaining.min())); // clip @a n down.
+ if (n_r.max() == remaining.max()) {
return *this;
}
- remaining.assign_min(++METRIC(max));
+ remaining.assign_min(++metric_type(n_r.max()));
}
continue;
}
@@ -1308,8 +1302,9 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const&range, U c
if (right_adj_p && n_plain_colored_p) { // can pull @a n left to cover
n->assign_min(remaining.min());
if (pred_plain_colored_p) { // if that touches @a pred with same color, collapse.
- n->assign_min(pred->min());
+ auto pred_min = pred->min();
this->remove(pred);
+ n->assign_min(pred_min);
}
} else if (pred_plain_colored_p) { // can pull @a pred right to cover.
pred->assign_max(remaining.max());
@@ -1389,7 +1384,7 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const&range, U c
// Check if the last node can be extended to cover because it's left adjacent.
// Can decrement @a range_min because if there's a range to the left, @a range_min is not minimal.
n = _list.tail();
- if (n && n->max() >= --METRIC{remaining.min()} && n->payload() == plain_color) {
+ if (n && n->max() >= --metric_type{remaining.min()} && n->payload() == plain_color) {
n->assign_max(range.max());
} else {
this->append(_fa.make(remaining.min(), remaining.max(), plain_color));
diff --git a/unit_tests/test_ip.cc b/unit_tests/test_ip.cc
index f1c8d05..f0f39c3 100644
--- a/unit_tests/test_ip.cc
+++ b/unit_tests/test_ip.cc
@@ -673,16 +673,42 @@ TEST_CASE("IP Space Int", "[libswoc][ip][ipspace]") {
for (auto &&[text, value] : r2) {
IPRange range{text};
space.blend(IPRange{text}, value, b2);
+ REQUIRE(space.end() != space.find(range.min()));
+ REQUIRE(space.end() != space.find(range.max()));
}
CHECK(6 == space.count());
for (auto &&[text, value] : r2) {
IPRange range{text};
space.blend(IPRange{text}, value, b2);
+ REQUIRE(space.end() != space.find(range.min()));
+ REQUIRE(space.end() != space.find(range.max()));
}
CHECK(6 == space.count());
+ for (auto &&[text, value] : r2) {
+ IPRange range{text};
+ REQUIRE(space.end() != space.find(range.min()));
+ REQUIRE(space.end() != space.find(range.max()));
+ }
// Drop a non-intersecting range between existing ranges 1 and 2, make sure both sides coalesce.
space.blend(IPRange{"2001:4998:58:400::C/126"_tv}, 1, b2);
CHECK(5 == space.count());
+ // Verify all the data is in the ranges.
+ for (auto &&[text, value] : r2) {
+ IPRange range{text};
+ REQUIRE(space.end() != space.find(range.min()));
+ REQUIRE(space.end() != space.find(range.max()));
+ }
+
+ // Check some syntax.
+ {
+ auto && [ r, p ] = *space.find(IPAddr{"2001:4998:58:400::1E"});
+ REQUIRE(false == r.empty());
+ REQUIRE(p == 1);
+ }
+ {
+ auto && [ r, p ] = *space.find(IPAddr{"2001:4997:58:400::1E"});
+ REQUIRE(true == r.empty());
+ }
}
TEST_CASE("IPSpace bitset", "[libswoc][ipspace][bitset]") {