From 462dd712b987df83af2860e04937c67b414e89b2 Mon Sep 17 00:00:00 2001 From: Remi Gacogne Date: Wed, 12 Sep 2018 13:21:10 +0200 Subject: [PATCH] Store NetmaskTree nodes in a set for faster removal The insertion is a bit slower as a result (~ +25%) but removal is much, much more faster for large sets as it was O(n) previously. Walking all the entries might be a bit slower as well, but this change has no impact on the lookup speed, which is the critical point for the NMT. --- pdns/iputils.hh | 30 +++++++++--------------------- pdns/test-iputils_hh.cc | 24 ++++++++++++++++++++---- 2 files changed, 29 insertions(+), 25 deletions(-) diff --git a/pdns/iputils.hh b/pdns/iputils.hh index 4762c249e7..90ecdad281 100644 --- a/pdns/iputils.hh +++ b/pdns/iputils.hh @@ -632,11 +632,11 @@ public: return *this; } - const typename std::vector::const_iterator begin() const { return _nodes.begin(); } - const typename std::vector::const_iterator end() const { return _nodes.end(); } + const typename std::set::const_iterator begin() const { return _nodes.begin(); } + const typename std::set::const_iterator end() const { return _nodes.end(); } - typename std::vector::iterator begin() { return _nodes.begin(); } - typename std::vector::iterator end() { return _nodes.end(); } + typename std::set::iterator begin() { return _nodes.begin(); } + typename std::set::iterator end() { return _nodes.end(); } node_type& insert(const string &mask) { return insert(key_type(mask)); @@ -664,7 +664,7 @@ public: // only create node if not yet assigned if (!node->node4) { node->node4 = unique_ptr(new node_type()); - _nodes.push_back(node->node4.get()); + _nodes.insert(node->node4.get()); } value = node->node4.get(); } else { @@ -689,7 +689,7 @@ public: // only create node if not yet assigned if (!node->node6) { node->node6 = unique_ptr(new node_type()); - _nodes.push_back(node->node6.get()); + _nodes.insert(node->node6.get()); } value = node->node6.get(); } @@ -814,13 +814,7 @@ public: bits++; } if (node) { - for(auto it = _nodes.begin(); it != _nodes.end(); ) { - if (node->node4.get() == *it) - it = _nodes.erase(it); - else - it++; - } - + _nodes.erase(node->node4.get()); node->node4.reset(); if (d_cleanup_tree) @@ -843,13 +837,7 @@ public: bits++; } if (node) { - for(auto it = _nodes.begin(); it != _nodes.end(); ) { - if (node->node6.get() == *it) - it = _nodes.erase(it); - else - it++; - } - + _nodes.erase(node->node6.get()); node->node6.reset(); if (d_cleanup_tree) @@ -895,7 +883,7 @@ public: private: unique_ptr root; // _nodes; // _nodes; // vect; + stringtok(vect, str, ", "); + std::sort(vect.begin(), vect.end()); + std::string result; + for (const auto& entry : vect) { + if (!result.empty()) { + result += " "; + } + result += entry; + } + + return result; +} + BOOST_AUTO_TEST_CASE(test_NetmaskGroup) { { @@ -258,7 +274,7 @@ BOOST_AUTO_TEST_CASE(test_NetmaskGroup) { ng.addMask("fe80::/16"); BOOST_CHECK(ng.match(ComboAddress("fe80::1"))); BOOST_CHECK(!ng.match(ComboAddress("fe81::1"))); - BOOST_CHECK_EQUAL(ng.toString(), "10.0.1.0/32, 127.0.0.0/8, 10.0.0.0/24, ::1/128, fe80::/16"); + BOOST_CHECK_EQUAL(NMGOutputToSorted(ng.toString()), NMGOutputToSorted("10.0.1.0/32, 127.0.0.0/8, 10.0.0.0/24, ::1/128, fe80::/16")); /* negative entries using the explicit flag */ ng.addMask("172.16.0.0/16", true); @@ -283,7 +299,7 @@ BOOST_AUTO_TEST_CASE(test_NetmaskGroup) { /* not in 2001:db8::/64 but in 2001:db8::/32, should match */ BOOST_CHECK(ng.match(ComboAddress("2001:db8:1::1"))); - BOOST_CHECK_EQUAL(ng.toString(), "10.0.1.0/32, 127.0.0.0/8, 10.0.0.0/24, ::1/128, fe80::/16, 172.16.0.0/16, !172.16.4.0/24, !fe80::/24, !172.16.10.0/24, 2001:db8::/32, !2001:db8::/64"); + BOOST_CHECK_EQUAL(NMGOutputToSorted(ng.toString()), NMGOutputToSorted("10.0.1.0/32, 127.0.0.0/8, 10.0.0.0/24, ::1/128, fe80::/16, 172.16.0.0/16, !172.16.4.0/24, !fe80::/24, !172.16.10.0/24, 2001:db8::/32, !2001:db8::/64")); } { @@ -305,7 +321,7 @@ BOOST_AUTO_TEST_CASE(test_NetmaskGroup) { ng.addMask(Netmask("fe80::/16")); BOOST_CHECK(ng.match(ComboAddress("fe80::1"))); BOOST_CHECK(!ng.match(ComboAddress("fe81::1"))); - BOOST_CHECK_EQUAL(ng.toString(), "10.0.1.0/32, 127.0.0.0/8, 10.0.0.0/24, ::1/128, fe80::/16"); + BOOST_CHECK_EQUAL(NMGOutputToSorted(ng.toString()), NMGOutputToSorted("10.0.1.0/32, 127.0.0.0/8, 10.0.0.0/24, ::1/128, fe80::/16")); /* negative entries using the explicit flag */ ng.addMask(Netmask("172.16.0.0/16"), true); @@ -320,7 +336,7 @@ BOOST_AUTO_TEST_CASE(test_NetmaskGroup) { /* not in fe80::/24 but in fe80::/16, should match */ BOOST_CHECK(ng.match(ComboAddress("fe80:0100::1"))); - BOOST_CHECK_EQUAL(ng.toString(), "10.0.1.0/32, 127.0.0.0/8, 10.0.0.0/24, ::1/128, fe80::/16, 172.16.0.0/16, !172.16.4.0/24, !fe80::/24"); + BOOST_CHECK_EQUAL(NMGOutputToSorted(ng.toString()), NMGOutputToSorted("10.0.1.0/32, 127.0.0.0/8, 10.0.0.0/24, ::1/128, fe80::/16, 172.16.0.0/16, !172.16.4.0/24, !fe80::/24")); } } -- 2.47.2