This is an automated email from the ASF dual-hosted git repository. bneradt pushed a commit to branch dev-1-2-9 in repository https://gitbox.apache.org/repos/asf/trafficserver-libswoc.git
commit 9a46c899a9bfb800916998ba2294a35f9f3e6eeb Author: Alan M. Carroll <[email protected]> AuthorDate: Thu Jul 30 21:58:16 2020 -0500 Fix two logic errors in IPSpace::blend. Add tests to verify fix. --- code/include/swoc/DiscreteRange.h | 51 ++++++++++++++++++++++------------- unit_tests/test_ip.cc | 57 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 90 insertions(+), 18 deletions(-) diff --git a/code/include/swoc/DiscreteRange.h b/code/include/swoc/DiscreteRange.h index eba8bed..6e2494d 100644 --- a/code/include/swoc/DiscreteRange.h +++ b/code/include/swoc/DiscreteRange.h @@ -1267,8 +1267,8 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const& range, U , F&& blender) -> self_type& { // Do a base check for the color to use on unmapped values. If self blending on @a color // is @c false, then do not color currently unmapped values. - auto plain_color = PAYLOAD{}; - bool plain_color_p = blender(plain_color, color); + PAYLOAD plain_color; // color to paint uncolored metrics. + bool plain_color_p = blender(plain_color, color); // start with default and blend in @a color. auto node_cleaner = [&](Node *ptr) -> void { _fa.destroy(ptr); }; // Used to hold a temporary blended node - @c release if put in space, otherwise cleaned up. @@ -1298,8 +1298,6 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const& range, U } // Invariant - n->max() >= remaining.min(); - Node *pred = prev(n); - // Check for left extension. If found, clip that node to be adjacent and put in a // temporary that covers the overlap with the original payload. if (n->min() < remaining.min()) { @@ -1314,9 +1312,16 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const& range, U return *this; // incoming range is completely covered by @a n in the same color, done. } if (!same_color_p) { + auto fn = fill.release(); + auto n_max = n->max(); // save this so @a n can be clipped. 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(); // skip to use new node as current node. + this->insert_after(n, fn); // add intersection node in different color. + if (n_max > remaining.max()) { // right extent too - split and done. + fn->assign_max(remaining.max()); // fill node stops at end of target range. + this->insert_after(fn, _fa.make(++metric_type(remaining.max()), n_max, n->payload())); + return *this; + } + n = fn; // skip to use new node as current node. } remaining.assign_min(++metric_type(n->max())); // going to fill up n->max(), clip target. } else { // clear, don't fill. @@ -1336,7 +1341,10 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const& range, U continue; } - // invariant - pred->max() < remaining.min() + Node *pred = prev(n); + // invariant + // - remaining.min() <= n->max() + // - !pred || pred->max() < remaining.min() // Calculate and cache key relationships between @a n and @a remaining. @@ -1348,17 +1356,17 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const& range, U bool right_adj_p = !right_overlap_p && remaining.is_left_adjacent_to(n->range()); // @a n has the same color as would be used for unmapped values. bool n_plain_colored_p = plain_color_p && (n->payload() == plain_color); - // @a pred has the same color as would be used for unmapped values. - bool pred_plain_colored_p = - pred && - pred->max() < remaining.min() && - ++metric_type(pred->max()) == remaining.min() && - pred->payload() == plain_color; // Check for no right overlap - that means @a n is past the target range. // It may be possible to extend @a n or the previous range to cover // the target range. Regardless, all of @a range can be filled at this point. if (!right_overlap_p) { + // @a pred has the same color as would be used for unmapped values + // and is adjacent to @a remaining. + bool pred_plain_colored_p = pred && + ++metric_type(pred->max()) == remaining.min() && + pred->payload() == plain_color; + 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. @@ -1376,8 +1384,7 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const& range, U // Invariant: @n has right overlap with @a remaining - // If there's a gap on the left, fill from @a min to @a n.min - 1 - // Also see above - @a pred is set iff it is left overlapping or left adjacent. + // If there's a gap on the left, fill from @a r.min to @a n.min - 1 if (plain_color_p && remaining.min() < n->min()) { if (n->payload() == plain_color) { if (pred && pred->payload() == n->payload()) { @@ -1409,18 +1416,26 @@ DiscreteSpace<METRIC, PAYLOAD>::blend(DiscreteSpace::range_type const& range, U // Clean up the range for @a n if (fill_p) { + // Check if @a pred is suitable for extending right to cover the target range. + bool pred_adj_p = nullptr != (pred = prev(n)) && + pred->range().is_left_adjacent_to(fill->range()) && + pred->payload() == fill->payload(); + if (right_ext_p) { if (n->payload() == fill->payload()) { n->assign_min(fill->min()); } else { n->assign_min(range_max_plus_1); - this->insert_before(n, fill.release()); + if (pred_adj_p) { + pred->assign_max(fill->max()); + } else { + this->insert_before(n, fill.release()); + } } return *this; // @a n extends past @a remaining, -> all done. } else { // Collapse in to previous range if it's adjacent and the color matches. - if (nullptr != (pred = prev(n)) && pred->range().is_left_adjacent_to(fill->range()) && - pred->payload() == fill->payload()) { + if (pred_adj_p) { this->remove(n); pred->assign_max(fill->max()); } else { diff --git a/unit_tests/test_ip.cc b/unit_tests/test_ip.cc index c1f1480..7d50c91 100644 --- a/unit_tests/test_ip.cc +++ b/unit_tests/test_ip.cc @@ -14,6 +14,7 @@ #include "swoc/bwf_ip.h" #include "swoc/bwf_std.h" #include "swoc/swoc_file.h" +#include "swoc/Lexicon.h" using namespace std::literals; using namespace swoc::literals; @@ -1472,3 +1473,59 @@ TEST_CASE("IPSpace Uthira", "[libswoc][ipspace][uthira]") { } } +TEST_CASE("IPSpace skew overlap blend", "[libswoc][ipspace][blend][skew]") { + std::string buff; + enum class Pod { + INVALID, zio, zaz, zlz + }; + swoc::Lexicon<Pod> PodNames {{ { Pod::zio, "zio"}, { Pod::zaz, "zaz"} , { Pod::zlz, "zlz"} }, "-1"}; + + struct Data { + int _state = 0; + int _country = -1; + int _rack = 0; + Pod _pod = Pod::INVALID; + int _code = 0; + + bool operator==(Data const& that) const { + return _pod == that._pod && _rack == that._rack && _code == that._code && + _state == that._state && _country == that._country; + } + }; + + using Src_1 = std::tuple<int, Pod, int>; // rack, pod, code + using Src_2 = std::tuple<int, int>; // state, country. + auto blend_1 = [](Data& data, Src_1 const& src) { + std::tie(data._rack, data._pod, data._code) = src; + return true; + }; + [[maybe_unused]] auto blend_2 = [](Data& data, Src_2 const& src) { + std::tie(data._state, data._country) = src; + return true; + }; + swoc::IPSpace<Data> space; + space.blend(IPRange("14.6.128.0-14.6.191.255"), Src_2{32, 231}, blend_2); + space.blend(IPRange("14.6.192.0-14.6.223.255"), Src_2{32, 231}, blend_2); + REQUIRE(space.count() == 1); + space.blend(IPRange("14.6.160.0-14.6.160.1"), Src_1{1, Pod::zaz, 1}, blend_1); + REQUIRE(space.count() == 3); + space.blend(IPRange("14.6.160.64-14.6.160.95"), Src_1{1, Pod::zio, 1}, blend_1); + space.blend(IPRange("14.6.160.96-14.6.160.127"),Src_1{1, Pod::zlz, 1}, blend_1); + space.blend(IPRange("14.6.160.128-14.6.160.255"),Src_1{1, Pod::zlz, 1}, blend_1); + space.blend(IPRange("14.6.0.0-14.6.127.255"), Src_2{32, 231}, blend_2); + + std::array<std::tuple<IPRange, Data>, 6> results = { + {{IPRange("14.6.0.0-14.6.159.255"), Data{32,231,0,Pod::INVALID,0} } + , {IPRange("14.6.160.0-14.6.160.1"), Data{32,231,1,Pod::zaz,1}} + , {IPRange("14.6.160.2-14.6.160.63"), Data{32,231,0,Pod::INVALID,0}} + , {IPRange("14.6.160.64-14.6.160.95"), Data{32,231,1,Pod::zio,1}} + , {IPRange("14.6.160.96-14.6.160.255"), Data{32,231,1,Pod::zlz,1}} + , {IPRange("14.6.161.0-14.6.223.255"), Data{32,231,0,Pod::INVALID,0}} + }}; + REQUIRE(space.count() == results.size()); + unsigned idx = 0; + for ( auto const& v : space ) { + REQUIRE(v == results[idx]); + ++idx; + } +}
