pdns/test-iputils_hh.cc

   1 #define BOOST_TEST_DYN_LINK
   2 #define BOOST_TEST_NO_MAIN
   3 #ifdef HAVE_CONFIG_H
   4 #include "config.h"
   5 #endif
   6 #include <boost/test/unit_test.hpp>
   7 #include <bitset>
   8 #include "iputils.hh"
   9
  10 using namespace boost;
  11
  12 BOOST_AUTO_TEST_SUITE(test_iputils_hh)
  13
  14 BOOST_AUTO_TEST_CASE(test_ComboAddress) {
  15   ComboAddress local("127.0.0.1", 53);
  16   BOOST_CHECK(local==local);
  17   BOOST_CHECK_EQUAL(local.sin4.sin_family, AF_INET);
  18   BOOST_CHECK_EQUAL(local.sin4.sin_port, htons(53));
  19   BOOST_CHECK_EQUAL(local.sin4.sin_addr.s_addr, htonl(0x7f000001UL));
  20
  21   ComboAddress remote("130.161.33.15", 53);
  22   BOOST_CHECK(!(local == remote));
  23   BOOST_CHECK_EQUAL(remote.sin4.sin_port, htons(53));
  24
  25   ComboAddress withport("213.244.168.210:53");
  26   BOOST_CHECK_EQUAL(withport.sin4.sin_port, htons(53));
  27
  28   ComboAddress withportO("213.244.168.210:53", 5300);
  29   BOOST_CHECK_EQUAL(withportO.sin4.sin_port, htons(53));
  30
  31   withport = ComboAddress("[::]:53");
  32   BOOST_CHECK_EQUAL(withport.sin4.sin_port, htons(53));
  33
  34   withport = ComboAddress("[::]:5300", 53);
  35   BOOST_CHECK_EQUAL(withport.sin4.sin_port, htons(5300));
  36
  37   ComboAddress defaultport("213.244.168.210");
  38   BOOST_CHECK_EQUAL(defaultport.sin4.sin_port, htons(0));
  39
  40   defaultport = ComboAddress("[::1]");
  41   BOOST_CHECK_EQUAL(defaultport.sin4.sin_port, htons(0));
  42
  43   defaultport = ComboAddress("::1");
  44   BOOST_CHECK_EQUAL(defaultport.sin4.sin_port, htons(0));
  45
  46   // Verify that 2 'empty' ComboAddresses are equal, used in syncres.hh to
  47   // signal auth-zones
  48   ComboAddress a = ComboAddress();
  49   ComboAddress b = ComboAddress();
  50   BOOST_CHECK(a == b);
  51
  52   // Verify that 2 ComboAddresses are not the same
  53   ComboAddress c = ComboAddress("127.0.0.1:53");
  54   ComboAddress d = ComboAddress("127.0.0.1:52");
  55   ComboAddress e = ComboAddress("127.0.0.2:53");
  56
  57   BOOST_CHECK(a != c);
  58   BOOST_CHECK(c != d);
  59   BOOST_CHECK(c != e);
  60   BOOST_CHECK(d != e);
  61   BOOST_CHECK(!(a != b));
  62
  63   // Verify that we don't allow invalid port numbers
  64   BOOST_CHECK_THROW(ComboAddress("127.0.0.1:70000"), PDNSException); // Port no. too high
  65   BOOST_CHECK_THROW(ComboAddress("127.0.0.1:-6"), PDNSException); // Port no. too low
  66   BOOST_CHECK_THROW(ComboAddress("[::1]:70000"), PDNSException); // Port no. too high
  67   BOOST_CHECK_THROW(ComboAddress("[::1]:-6"), PDNSException); // Port no. too low
  68 }
  69
  70 BOOST_AUTO_TEST_CASE(test_ComboAddressCompare) {
  71   ComboAddress a, b;
  72   a.reset();
  73   b.reset();
  74   BOOST_CHECK(!(a<b));
  75   BOOST_CHECK(!(a>b));
  76 }
  77
  78 BOOST_AUTO_TEST_CASE(test_ComboAddressTruncate) {
  79   ComboAddress ca4("130.161.252.29");
  80   ca4.truncate(24);
  81   BOOST_CHECK_EQUAL(ca4.toString(), "130.161.252.0");
  82   ca4.truncate(16);
  83   BOOST_CHECK_EQUAL(ca4.toString(), "130.161.0.0");
  84
  85
  86
  87   ca4 = ComboAddress("130.161.252.29");
  88   ComboAddress orig(ca4);
  89   for(int n=32; n; --n) {
  90     ca4.truncate(n);
  91
  92     uint32_t p;
  93     memcpy(&p, (char*)&ca4.sin4.sin_addr.s_addr, 4);
  94     std::bitset<32> result(htonl(p));
  95
  96     memcpy(&p, (char*)&orig.sin4.sin_addr.s_addr, 4);
  97     std::bitset<32> manual(htonl(p));
  98
  99     auto tokill=32-n;
 100     for(int i =0; i< tokill; ++i)
 101       manual.set(i, 0);
 102
 103     BOOST_CHECK_EQUAL(result, manual);
 104   }
 105
 106   ca4 = ComboAddress("130.161.252.29");
 107   ca4.truncate(31);
 108   BOOST_CHECK_EQUAL(ca4.toString(), "130.161.252.28");
 109
 110   ca4.truncate(30);
 111   BOOST_CHECK_EQUAL(ca4.toString(), "130.161.252.28");
 112
 113   ca4.truncate(29);
 114   BOOST_CHECK_EQUAL(ca4.toString(), "130.161.252.24");
 115
 116   ca4.truncate(23);
 117   BOOST_CHECK_EQUAL(ca4.toString(), "130.161.252.0");
 118
 119   ca4.truncate(22);
 120   BOOST_CHECK_EQUAL(ca4.toString(), "130.161.252.0");
 121
 122   ca4.truncate(21);
 123   BOOST_CHECK_EQUAL(ca4.toString(), "130.161.248.0");
 124
 125   ComboAddress ca6("2001:888:2000:1d::2");
 126   ca6.truncate(120);
 127   BOOST_CHECK_EQUAL(ca6.toString(), "2001:888:2000:1d::");
 128   ca6.truncate(64);
 129   BOOST_CHECK_EQUAL(ca6.toString(), "2001:888:2000:1d::");
 130   ca6.truncate(72);                  // 0102 304 0506 78
 131   BOOST_CHECK_EQUAL(ca6.toString(), "2001:888:2000:1d::");
 132   ca6.truncate(56);
 133   BOOST_CHECK_EQUAL(ca6.toString(), "2001:888:2000::");
 134   ca6.truncate(48);
 135   BOOST_CHECK_EQUAL(ca6.toString(), "2001:888:2000::");
 136   ca6.truncate(32);
 137   BOOST_CHECK_EQUAL(ca6.toString(), "2001:888::");
 138   ca6.truncate(16);
 139   BOOST_CHECK_EQUAL(ca6.toString(), "2001::");
 140   ca6.truncate(8);
 141   BOOST_CHECK_EQUAL(ca6.toString(), "2000::");
 142
 143
 144   orig=ca6=ComboAddress("2001:888:2000:1d::2");
 145   for(int n=128; n; --n) {
 146     ca6.truncate(n);
 147
 148     std::bitset<128> result, manual;
 149     for(int i=0; i < 16; ++i) {
 150       result<<=8;
 151       result|= std::bitset<128>(*((unsigned char*)&ca6.sin6.sin6_addr.s6_addr + i));
 152
 153       manual<<=8;
 154       manual|= std::bitset<128>(*((unsigned char*)&orig.sin6.sin6_addr.s6_addr + i));
 155     }
 156
 157     auto tokill=128-n;
 158     for(int i =0; i< tokill; ++i)
 159       manual.set(i, 0);
 160
 161     BOOST_CHECK_EQUAL(result, manual);
 162   }
 163 }
 164
 165 BOOST_AUTO_TEST_CASE(test_Mapping)
 166 {
 167   ComboAddress lh("::1");
 168   BOOST_CHECK_EQUAL(lh.toString(), "::1");
 169 }
 170
 171 BOOST_AUTO_TEST_CASE(test_Netmask) {
 172   ComboAddress local("127.0.0.1", 53);
 173   ComboAddress remote("130.161.252.29", 53);
 174
 175   Netmask nm("127.0.0.1/24");
 176   BOOST_CHECK(nm.getBits() == 24);
 177   BOOST_CHECK(nm.match(local));
 178   BOOST_CHECK(!nm.match(remote));
 179   BOOST_CHECK(nm.isIPv4());
 180   BOOST_CHECK(!nm.isIPv6());
 181
 182   Netmask nm6("fe80::92fb:a6ff:fe4a:51da/64");
 183   BOOST_CHECK(nm6.getBits() == 64);
 184   BOOST_CHECK(nm6.match("fe80::92fb:a6ff:fe4a:51db"));
 185   BOOST_CHECK(!nm6.match("fe81::92fb:a6ff:fe4a:51db"));
 186   BOOST_CHECK(!nm6.isIPv4());
 187   BOOST_CHECK(nm6.isIPv6());
 188
 189   Netmask nmp("130.161.252.29/32");
 190   BOOST_CHECK(nmp.match(remote));
 191
 192   Netmask nmp6("fe80::92fb:a6ff:fe4a:51da/128");
 193   BOOST_CHECK(nmp6.match("fe80::92fb:a6ff:fe4a:51da"));
 194   BOOST_CHECK(!nmp6.match("fe81::92fb:a6ff:fe4a:51db"));
 195
 196   Netmask all("0.0.0.0/0");
 197   BOOST_CHECK(all.match(local) && all.match(remote));
 198
 199   Netmask all6("::/0");
 200   BOOST_CHECK(all6.match("::1") && all6.match("fe80::92fb:a6ff:fe4a:51da"));
 201
 202
 203   Netmask fromCombo1(ComboAddress("192.0.2.1:53"), 32);
 204   Netmask fromCombo2(ComboAddress("192.0.2.1:54"), 32);
 205   BOOST_CHECK(fromCombo1 == fromCombo2);
 206   BOOST_CHECK(fromCombo1.match("192.0.2.1"));
 207   BOOST_CHECK(fromCombo1.match(ComboAddress("192.0.2.1:80")));
 208   BOOST_CHECK(fromCombo1.getNetwork() == ComboAddress("192.0.2.1"));
 209   BOOST_CHECK(fromCombo1.getMaskedNetwork() == ComboAddress("192.0.2.1"));
 210
 211   Netmask nm25("192.0.2.255/25");
 212   BOOST_CHECK(nm25.getBits() == 25);
 213   BOOST_CHECK(nm25.getNetwork() == ComboAddress("192.0.2.255"));
 214   BOOST_CHECK(nm25.getMaskedNetwork() == ComboAddress("192.0.2.128"));
 215
 216   /* Make sure that more specific Netmasks are lesser than less specific ones,
 217      as this is very useful when matching. */
 218   Netmask specific32("192.0.0.0/32");
 219   Netmask specific24("192.0.0.0/24");
 220   Netmask specific16("192.0.0.0/16");
 221   BOOST_CHECK(specific32 < specific24);
 222   BOOST_CHECK(specific24 > specific32);
 223   BOOST_CHECK(specific24 < specific16);
 224   BOOST_CHECK(specific16 > specific24);
 225
 226   Netmask sameMask1("192.0.0.0/16");
 227   Netmask sameMask2("192.0.0.1/16");
 228   BOOST_CHECK(sameMask1 < sameMask2);
 229   BOOST_CHECK(sameMask2 > sameMask1);
 230
 231   /* An empty Netmask should be larger than
 232      every others. */
 233   Netmask empty = Netmask();
 234   Netmask full("255.255.255.255/32");
 235   BOOST_CHECK(empty > all);
 236   BOOST_CHECK(all < empty);
 237   BOOST_CHECK(empty > full);
 238   BOOST_CHECK(full < empty);
 239 }
 240
 241 static std::string NMGOutputToSorted(const std::string& str)
 242 {
 243   std::vector<std::string> vect;
 244   stringtok(vect, str, ", ");
 245   std::sort(vect.begin(), vect.end());
 246   std::string result;
 247   for (const auto& entry : vect) {
 248     if (!result.empty()) {
 249       result += " ";
 250     }
 251     result += entry;
 252   }
 253
 254   return result;
 255 }
 256
 257 BOOST_AUTO_TEST_CASE(test_NetmaskGroup) {
 258
 259   {
 260     NetmaskGroup ng;
 261     BOOST_CHECK_EQUAL(ng.empty(), true);
 262     BOOST_CHECK_EQUAL(ng.size(), 0);
 263     ng.addMask("10.0.1.0");
 264     BOOST_CHECK_EQUAL(ng.empty(), false);
 265     BOOST_CHECK_EQUAL(ng.size(), 1);
 266     BOOST_CHECK(ng.match(ComboAddress("10.0.1.0")));
 267     ng.toMasks("127.0.0.0/8, 10.0.0.0/24");
 268     BOOST_CHECK_EQUAL(ng.size(), 3);
 269     BOOST_CHECK(ng.match(ComboAddress("127.0.0.1")));
 270     BOOST_CHECK(ng.match(ComboAddress("10.0.0.3")));
 271     BOOST_CHECK(ng.match(ComboAddress("10.0.1.0")));
 272     BOOST_CHECK(!ng.match(ComboAddress("128.1.2.3")));
 273     BOOST_CHECK(!ng.match(ComboAddress("10.0.1.1")));
 274     BOOST_CHECK(!ng.match(ComboAddress("::1")));
 275     ng.addMask("::1");
 276     BOOST_CHECK_EQUAL(ng.size(), 4);
 277     BOOST_CHECK(ng.match(ComboAddress("::1")));
 278     BOOST_CHECK(!ng.match(ComboAddress("::2")));
 279     ng.addMask("fe80::/16");
 280     BOOST_CHECK_EQUAL(ng.size(), 5);
 281     BOOST_CHECK(ng.match(ComboAddress("fe80::1")));
 282     BOOST_CHECK(!ng.match(ComboAddress("fe81::1")));
 283     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"));
 284
 285     /* negative entries using the explicit flag */
 286     ng.addMask("172.16.0.0/16", true);
 287     BOOST_CHECK_EQUAL(ng.size(), 6);
 288     BOOST_CHECK(ng.match(ComboAddress("172.16.1.1")));
 289     BOOST_CHECK(ng.match(ComboAddress("172.16.4.50")));
 290     ng.addMask("172.16.4.0/24", false);
 291     BOOST_CHECK_EQUAL(ng.size(), 7);
 292     BOOST_CHECK(ng.match(ComboAddress("172.16.1.1")));
 293     BOOST_CHECK(!ng.match(ComboAddress("172.16.4.50")));
 294     ng.addMask("fe80::/24", false);
 295     BOOST_CHECK_EQUAL(ng.size(), 8);
 296     BOOST_CHECK(!ng.match(ComboAddress("fe80::1")));
 297     BOOST_CHECK(!ng.match(ComboAddress("fe81::1")));
 298     /* not in fe80::/24 but in fe80::/16, should match */
 299     BOOST_CHECK(ng.match(ComboAddress("fe80:0100::1")));
 300
 301     /* negative entries using '!' */
 302     BOOST_CHECK(ng.match(ComboAddress("172.16.10.80")));
 303     ng.addMask("!172.16.10.0/24");
 304     BOOST_CHECK_EQUAL(ng.size(), 9);
 305     BOOST_CHECK(!ng.match(ComboAddress("172.16.10.80")));
 306     ng.addMask("2001:db8::/32");
 307     BOOST_CHECK_EQUAL(ng.size(), 10);
 308     ng.addMask("!2001:db8::/64");
 309     BOOST_CHECK_EQUAL(ng.size(), 11);
 310     BOOST_CHECK(!ng.match(ComboAddress("2001:db8::1")));
 311     /* not in 2001:db8::/64 but in 2001:db8::/32, should match */
 312     BOOST_CHECK(ng.match(ComboAddress("2001:db8:1::1")));
 313
 314     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"));
 315   }
 316
 317   {
 318     /* this time using Netmask objects instead of strings */
 319     NetmaskGroup ng;
 320     BOOST_CHECK_EQUAL(ng.empty(), true);
 321     BOOST_CHECK_EQUAL(ng.size(), 0);
 322     ng.addMask(Netmask("10.0.1.0"));
 323     BOOST_CHECK_EQUAL(ng.empty(), false);
 324     BOOST_CHECK_EQUAL(ng.size(), 1);
 325     BOOST_CHECK(ng.match(ComboAddress("10.0.1.0")));
 326     ng.addMask(Netmask("127.0.0.0/8"));
 327     BOOST_CHECK_EQUAL(ng.size(), 2);
 328     ng.addMask(Netmask("10.0.0.0/24"));
 329     BOOST_CHECK_EQUAL(ng.size(), 3);
 330     BOOST_CHECK(ng.match(ComboAddress("127.0.0.1")));
 331     BOOST_CHECK(ng.match(ComboAddress("10.0.0.3")));
 332     BOOST_CHECK(ng.match(ComboAddress("10.0.1.0")));
 333     BOOST_CHECK(!ng.match(ComboAddress("128.1.2.3")));
 334     BOOST_CHECK(!ng.match(ComboAddress("10.0.1.1")));
 335     BOOST_CHECK(!ng.match(ComboAddress("::1")));
 336     ng.addMask(Netmask("::1"));
 337     BOOST_CHECK_EQUAL(ng.size(), 4);
 338     BOOST_CHECK(ng.match(ComboAddress("::1")));
 339     BOOST_CHECK(!ng.match(ComboAddress("::2")));
 340     ng.addMask(Netmask("fe80::/16"));
 341     BOOST_CHECK_EQUAL(ng.size(), 5);
 342     BOOST_CHECK(ng.match(ComboAddress("fe80::1")));
 343     BOOST_CHECK(!ng.match(ComboAddress("fe81::1")));
 344     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"));
 345
 346     /* negative entries using the explicit flag */
 347     ng.addMask(Netmask("172.16.0.0/16"), true);
 348     BOOST_CHECK_EQUAL(ng.size(), 6);
 349     BOOST_CHECK(ng.match(ComboAddress("172.16.1.1")));
 350     BOOST_CHECK(ng.match(ComboAddress("172.16.4.50")));
 351     ng.addMask(Netmask("172.16.4.0/24"), false);
 352     BOOST_CHECK_EQUAL(ng.size(), 7);
 353     BOOST_CHECK(ng.match(ComboAddress("172.16.1.1")));
 354     BOOST_CHECK(!ng.match(ComboAddress("172.16.4.50")));
 355     ng.addMask("fe80::/24", false);
 356     BOOST_CHECK_EQUAL(ng.size(), 8);
 357     BOOST_CHECK(!ng.match(ComboAddress("fe80::1")));
 358     BOOST_CHECK(!ng.match(ComboAddress("fe81::1")));
 359     /* not in fe80::/24 but in fe80::/16, should match */
 360     BOOST_CHECK(ng.match(ComboAddress("fe80:0100::1")));
 361
 362     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"));
 363   }
 364 }
 365
 366 BOOST_AUTO_TEST_CASE(test_NetmaskTree) {
 367   NetmaskTree<int> nmt;
 368   BOOST_CHECK_EQUAL(nmt.empty(), true);
 369   BOOST_CHECK_EQUAL(nmt.size(), 0);
 370   nmt.insert(Netmask("130.161.252.0/24")).second=0;
 371   BOOST_CHECK_EQUAL(nmt.empty(), false);
 372   BOOST_CHECK_EQUAL(nmt.size(), 1);
 373   nmt.insert(Netmask("130.161.0.0/16")).second=1;
 374   BOOST_CHECK_EQUAL(nmt.size(), 2);
 375   nmt.insert(Netmask("130.0.0.0/8")).second=2;
 376   BOOST_CHECK_EQUAL(nmt.size(), 3);
 377
 378   BOOST_CHECK_EQUAL(nmt.lookup(ComboAddress("213.244.168.210")), (void*)0);
 379   auto found=nmt.lookup(ComboAddress("130.161.252.29"));
 380   BOOST_CHECK(found);
 381   BOOST_CHECK_EQUAL(found->second, 0);
 382   found=nmt.lookup(ComboAddress("130.161.180.1"));
 383   BOOST_CHECK(found);
 384   BOOST_CHECK_EQUAL(found->second, 1);
 385
 386   BOOST_CHECK_EQUAL(nmt.lookup(ComboAddress("130.255.255.255"))->second, 2);
 387   BOOST_CHECK_EQUAL(nmt.lookup(ComboAddress("130.161.252.255"))->second, 0);
 388   BOOST_CHECK_EQUAL(nmt.lookup(ComboAddress("130.161.253.255"))->second, 1);
 389
 390   found=nmt.lookup(ComboAddress("130.145.180.1"));
 391   BOOST_CHECK(found);
 392   BOOST_CHECK_EQUAL(found->second, 2);
 393
 394   nmt.insert(Netmask("0.0.0.0/0")).second=3;
 395   BOOST_CHECK_EQUAL(nmt.size(), 4);
 396   nmt.insert(Netmask("0.0.0.0/7")).second=4;
 397   BOOST_CHECK_EQUAL(nmt.size(), 5);
 398   nmt.insert(Netmask("0.0.0.0/15")).second=5;
 399   BOOST_CHECK_EQUAL(nmt.size(), 6);
 400   BOOST_CHECK_EQUAL(nmt.lookup(Netmask("0.0.0.0/0"))->second, 3);
 401   BOOST_CHECK_EQUAL(nmt.lookup(Netmask("0.0.0.0/7"))->second, 4);
 402   BOOST_CHECK_EQUAL(nmt.lookup(Netmask("0.0.0.0/15"))->second, 5);
 403
 404   nmt.clear();
 405   BOOST_CHECK_EQUAL(nmt.empty(), true);
 406   BOOST_CHECK_EQUAL(nmt.size(), 0);
 407   BOOST_CHECK(!nmt.lookup(ComboAddress("130.161.180.1")));
 408
 409   nmt.insert(Netmask("::1")).second=1;
 410   BOOST_CHECK_EQUAL(nmt.empty(), false);
 411   BOOST_CHECK_EQUAL(nmt.size(), 1);
 412   nmt.insert(Netmask("::/0")).second=0;
 413   BOOST_CHECK_EQUAL(nmt.size(), 2);
 414   nmt.insert(Netmask("fe80::/16")).second=2;
 415   BOOST_CHECK_EQUAL(nmt.size(), 3);
 416   BOOST_CHECK_EQUAL(nmt.lookup(ComboAddress("130.161.253.255")), (void*)0);
 417   BOOST_CHECK_EQUAL(nmt.lookup(ComboAddress("::2"))->second, 0);
 418   BOOST_CHECK_EQUAL(nmt.lookup(ComboAddress("::ffff"))->second, 0);
 419   BOOST_CHECK_EQUAL(nmt.lookup(ComboAddress("::1"))->second, 1);
 420   BOOST_CHECK_EQUAL(nmt.lookup(ComboAddress("fe80::1"))->second, 2);
 421 }
 422
 423 BOOST_AUTO_TEST_CASE(test_single) {
 424   NetmaskTree<bool> nmt;
 425   BOOST_CHECK_EQUAL(nmt.empty(), true);
 426   BOOST_CHECK_EQUAL(nmt.size(), 0);
 427   nmt.insert(Netmask("127.0.0.0/8")).second=1;
 428   BOOST_CHECK_EQUAL(nmt.empty(), false);
 429   BOOST_CHECK_EQUAL(nmt.size(), 1);
 430   BOOST_CHECK_EQUAL(nmt.lookup(ComboAddress("127.0.0.1"))->second, 1);
 431 }
 432
 433 BOOST_AUTO_TEST_CASE(test_scale) {
 434   string start="192.168.";
 435   NetmaskTree<int> works;
 436   BOOST_CHECK_EQUAL(works.size(), 0);
 437   for(int i=0; i < 256; ++i) {
 438     for(int j=0; j < 256; ++j) {
 439       works.insert(Netmask(start+std::to_string(i)+"."+std::to_string(j))).second=i*j;
 440       BOOST_CHECK_EQUAL(works.size(), i*256 + j + 1);
 441     }
 442   }
 443
 444   for(int i=0; i < 256; ++i) {
 445     for(int j=0; j < 256; ++j) {
 446       BOOST_CHECK_EQUAL(works.lookup(ComboAddress(start+std::to_string(i)+"."+std::to_string(j)))->second, i*j);
 447     }
 448   }
 449
 450   start="130.161.";
 451   for(int i=0; i < 256; ++i) {
 452     for(int j=0; j < 256; ++j) {
 453       BOOST_CHECK_EQUAL(works.lookup(ComboAddress(start+std::to_string(i)+"."+std::to_string(j))), (void*)0);
 454     }
 455   }
 456
 457   start="2000:123:";
 458   for(int i=0; i < 256; ++i) {
 459     for(int j=0; j < 256; ++j) {
 460       works.insert(Netmask(start+std::to_string(i)+":"+std::to_string(j)+"::/64")).second=i*j;
 461       BOOST_CHECK_EQUAL(works.size(), (256*256) + i*256 + j + 1);
 462     }
 463   }
 464
 465   for(int i=0; i < 256; ++i) {
 466     for(int j=0; j < 256; ++j) {
 467       BOOST_CHECK_EQUAL(works.lookup(ComboAddress(start+std::to_string(i)+":"+std::to_string(j)+"::"+std::to_string(i)+":"+std::to_string(j)))->second, i*j);
 468     }
 469   }
 470
 471   start="2001:123:";
 472   for(int i=0; i < 256; ++i) {
 473     for(int j=0; j < 256; ++j) {
 474       BOOST_CHECK_EQUAL(works.lookup(ComboAddress(start+std::to_string(i)+":"+std::to_string(j)+"::"+std::to_string(i)+":"+std::to_string(j))), (void*)0);
 475     }
 476   }
 477 }
 478
 479 BOOST_AUTO_TEST_CASE(test_removal) {
 480   std::string prefix = "192.";
 481   NetmaskTree<int> nmt;
 482   BOOST_CHECK(nmt.empty());
 483   BOOST_CHECK_EQUAL(nmt.size(), 0);
 484
 485   size_t count = 0;
 486   for(unsigned int i = 0; i < 256; ++i) {
 487     for(unsigned int j = 16; j <= 32; ++j) {
 488       nmt.insert(Netmask(prefix + std::to_string(i) +".127.255/"+std::to_string(j))).second = j;
 489       count++;
 490       BOOST_CHECK_EQUAL(nmt.size(), count);
 491     }
 492   }
 493
 494   for(unsigned int i = 0; i < 256; ++i) {
 495     ComboAddress key(prefix + std::to_string(i) + ".127.255");
 496     const auto result = nmt.lookup(key);
 497     BOOST_CHECK_EQUAL(result->first.getBits(), 32);
 498     BOOST_CHECK_EQUAL(result->first.getMaskedNetwork().toString(), key.toString());
 499     BOOST_CHECK_EQUAL(result->second, 32);
 500   }
 501
 502   for(int i = 0; i < 256; ++i) {
 503     for(int j = 32; j >= 16; --j) {
 504       ComboAddress key(prefix + std::to_string(i) + ".127.255");
 505       nmt.erase(Netmask(key, j));
 506       count--;
 507       BOOST_CHECK_EQUAL(nmt.size(), count);
 508       const auto result = nmt.lookup(key);
 509
 510       if (j > 16) {
 511         BOOST_REQUIRE(result != nullptr);
 512         BOOST_CHECK_EQUAL(result->first.getBits(), j-1);
 513         BOOST_CHECK_EQUAL(result->first.getMaskedNetwork().toString(), Netmask(key, j-1).getMaskedNetwork().toString());
 514         BOOST_CHECK_EQUAL(result->second, j - 1);
 515       }
 516       else {
 517         BOOST_CHECK(result == nullptr);
 518       }
 519     }
 520   }
 521
 522   BOOST_CHECK_EQUAL(nmt.size(), 0U);
 523   BOOST_CHECK(nmt.empty());
 524 }
 525
 526 BOOST_AUTO_TEST_CASE(test_iterator) {
 527   NetmaskTree<int> masks_set1;
 528   std::set<Netmask> masks_set2;
 529
 530   // create sets. the std::set entries are normalized to match internal behavior
 531   // of NetmaskTree
 532   for(int i=0; i < 256; ++i) {
 533     std::stringstream ss;
 534     Netmask mask;
 535
 536     ss << i << "." << i << "." << i << "." << i;
 537     mask = Netmask(ss.str());
 538     masks_set1.insert(mask).second=i;
 539     masks_set2.insert(mask.getNormalized());
 540
 541     ss.str("");
 542     ss << (255-i) << "." << (i/2) << "." << (i/3) << "." << (i/5);
 543     mask = Netmask(ss.str());
 544     masks_set1.insert(mask).second=i;
 545     masks_set2.insert(mask.getNormalized());
 546
 547     ss.str("");
 548     ss << (i/5) << "." << (i/3) << "." << (i/2) << "." << (255-i);
 549     mask = Netmask(ss.str());
 550     masks_set1.insert(mask).second=i;
 551     masks_set2.insert(mask.getNormalized());
 552
 553     ss.str("");
 554     ss << (i/2) << "." << (i/4) << "." << (255-i) << ".0/" << (i%24);
 555     mask = Netmask(ss.str());
 556     masks_set1.insert(mask).second=i;
 557     masks_set2.insert(mask.getNormalized());
 558
 559     ss.str("");
 560     ss << std::hex << "2001:" << i << i << ":" << i << i << "::/64";
 561     mask = Netmask(ss.str());
 562     masks_set1.insert(mask).second=i;
 563     masks_set2.insert(mask.getNormalized());
 564
 565     ss.str("");
 566     ss << std::hex << "2001:" << (i/5) << (i/3) << ":" << (i/2) << (255-i) << "::/64";
 567     mask = Netmask(ss.str());
 568     masks_set1.insert(mask).second=i;
 569     masks_set2.insert(mask.getNormalized());
 570
 571     ss.str("");
 572     ss << std::hex << "2001:" << (255-i) << (i/2) << ":" << (i/3) << (i/5) << "::/64";
 573     mask = Netmask(ss.str());
 574     masks_set1.insert(mask).second=i;
 575     masks_set2.insert(mask.getNormalized());
 576
 577     ss.str("");
 578     ss << std::hex << "20" << i/2 << ":" << i/3 << i/7 << "::" << i << (i > 0 ? i-1 : i + 1);
 579     mask = Netmask(ss.str());
 580     masks_set1.insert(mask).second=i;
 581     masks_set2.insert(mask.getNormalized());
 582
 583     ss.str("");
 584     ss << std::hex << "20" << i << ":" << i << i << "::/" << std::dec << (i%48);
 585     mask = Netmask(ss.str());
 586     masks_set1.insert(mask).second=i;
 587     masks_set2.insert(mask.getNormalized());
 588   }
 589   for(int i=0; i <= 32; ++i) {
 590     std::stringstream ss;
 591     Netmask mask;
 592
 593     ss << "85.85.85.85/" << i;
 594     mask = Netmask(ss.str());
 595     masks_set1.insert(mask).second=i;
 596     masks_set2.insert(mask.getNormalized());
 597
 598     ss.str("");
 599     ss << "170.170.170.170/" << i;
 600     mask = Netmask(ss.str());
 601     masks_set1.insert(mask).second=i;
 602     masks_set2.insert(mask.getNormalized());
 603   }
 604   for(int i=0; i <= 128; ++i) {
 605     std::stringstream ss;
 606     Netmask mask;
 607
 608     ss << "5555:5555:5555:5555:5555:5555:5555:5555/" << i;
 609     mask = Netmask(ss.str());
 610     masks_set1.insert(mask).second=i;
 611     masks_set2.insert(mask.getNormalized());
 612
 613     ss.str("");
 614     ss << "aaaa:aaaa:aaaa:aaaa:aaaa:aaaa:aaaa:aaaa/" << i;
 615     mask = Netmask(ss.str());
 616     masks_set1.insert(mask).second=i;
 617     masks_set2.insert(mask.getNormalized());
 618   }
 619
 620
 621   // check set equality using iterators
 622   BOOST_CHECK_EQUAL(masks_set1.size(), masks_set2.size());
 623   BOOST_CHECK_EQUAL(std::distance(masks_set1.begin(), masks_set1.end()),
 624                     std::distance(masks_set2.begin(), masks_set2.end()));
 625   for (auto entry: masks_set1) {
 626     Netmask mask = entry.first.getNormalized();
 627
 628     BOOST_CHECK(masks_set2.find(mask) != masks_set2.end());
 629   }
 630   for (const Netmask& mask: masks_set2) {
 631     BOOST_CHECK(masks_set1.lookup(mask) != nullptr);
 632   }
 633
 634   // create a copy of the NetmaskTree (check copy by assignment)
 635   NetmaskTree<int> masks_set1_cp1 = masks_set1;
 636
 637   // taint the old version
 638   masks_set1.insert("1.2.3.4");
 639   masks_set1.erase("1.1.1.1");
 640
 641   // check set equality using iterators
 642   BOOST_CHECK_EQUAL(masks_set1_cp1.size(), masks_set2.size());
 643   BOOST_CHECK_EQUAL(std::distance(masks_set1_cp1.begin(), masks_set1_cp1.end()),
 644                     std::distance(masks_set2.begin(), masks_set2.end()));
 645   for (auto entry: masks_set1_cp1) {
 646     Netmask mask = entry.first.getNormalized();
 647
 648     BOOST_CHECK(masks_set2.find(mask) != masks_set2.end());
 649   }
 650   for (const Netmask& mask: masks_set2) {
 651     BOOST_CHECK(masks_set1_cp1.lookup(mask) != nullptr);
 652   }
 653
 654   // create a copy of the NetmaskTree (check copy constructor)
 655   NetmaskTree<int> masks_set1_cp2(masks_set1_cp1);
 656
 657   // taint the old version
 658   masks_set1_cp1.insert("2.3.4.5");
 659   masks_set1_cp1.erase("2.2.2.2");
 660
 661   // check set equality using iterators
 662   BOOST_CHECK_EQUAL(masks_set1_cp2.size(), masks_set2.size());
 663   BOOST_CHECK_EQUAL(std::distance(masks_set1_cp2.begin(), masks_set1_cp2.end()),
 664                     std::distance(masks_set2.begin(), masks_set2.end()));
 665   for (auto entry: masks_set1_cp2) {
 666     Netmask mask = entry.first.getNormalized();
 667
 668     BOOST_CHECK(masks_set2.find(mask) != masks_set2.end());
 669   }
 670   for (const Netmask& mask: masks_set2) {
 671     BOOST_CHECK(masks_set1_cp2.lookup(mask) != nullptr);
 672   }
 673
 674   // swap contents of the NetmaskTree
 675   NetmaskTree<int> masks_set1_cp3;
 676   masks_set1_cp3.swap(masks_set1_cp2);
 677
 678   // taint the old version
 679   masks_set1_cp2.insert("3.4.5.6");
 680   masks_set1_cp2.erase("3.3.3.3");
 681
 682   // check set equality using iterators
 683   BOOST_CHECK_EQUAL(masks_set1_cp3.size(), masks_set2.size());
 684   BOOST_CHECK_EQUAL(std::distance(masks_set1_cp3.begin(), masks_set1_cp3.end()),
 685                     std::distance(masks_set2.begin(), masks_set2.end()));
 686   for (auto entry: masks_set1_cp3) {
 687     Netmask mask = entry.first.getNormalized();
 688
 689     BOOST_CHECK(masks_set2.find(mask) != masks_set2.end());
 690   }
 691   for (const Netmask& mask: masks_set2) {
 692     BOOST_CHECK(masks_set1_cp3.lookup(mask) != nullptr);
 693   }
 694
 695   // copy contents to an std::set
 696   std::set<NetmaskTree<int>::node_type> masks_set1_cp4(masks_set1_cp3.begin(), masks_set1_cp3.end());
 697
 698   // check set equality
 699   BOOST_CHECK_EQUAL(masks_set1_cp4.size(), masks_set2.size());
 700   for (auto entry: masks_set1_cp4) {
 701     Netmask mask = entry.first.getNormalized();
 702
 703     BOOST_CHECK(masks_set2.find(mask) != masks_set2.end());
 704   }
 705   for (const Netmask& mask: masks_set2) {
 706     Netmask maskl = mask.getNormalized();
 707     bool found = false;
 708     for (auto entry: masks_set1_cp4) {
 709       Netmask maskr = entry.first.getNormalized();
 710
 711       if (maskl == maskr)
 712         found = true;
 713     }
 714     BOOST_CHECK(found);
 715   }
 716
 717   // create a copy of the NetmaskTree
 718   NetmaskTree<int> masks_set1_cp5(masks_set1_cp3);
 719
 720   // erase select values
 721   {
 722     Netmask mask;
 723
 724     mask = Netmask("16.16.16.16");
 725     masks_set1_cp5.erase(mask);
 726     masks_set2.erase(mask.getNormalized());
 727
 728     mask = Netmask("223.16.10.6");
 729     masks_set1_cp5.erase(mask);
 730     masks_set2.erase(mask.getNormalized());
 731
 732     mask = Netmask("12.21.32.191");
 733     masks_set1_cp5.erase(mask);
 734     masks_set2.erase(mask.getNormalized());
 735
 736     mask = Netmask("64.32.127.0/8");
 737     masks_set1_cp5.erase(mask);
 738     masks_set2.erase(mask.getNormalized());
 739
 740     mask = Netmask("2001:ffff:ffff::/64");
 741     masks_set1_cp5.erase(mask);
 742     masks_set2.erase(mask.getNormalized());
 743
 744     mask = Netmask("2001:192a:407f::/64");
 745     masks_set1_cp5.erase(mask);
 746     masks_set2.erase(mask.getNormalized());
 747
 748     mask = Netmask("2001:bf20:15c::/64");
 749     masks_set1_cp5.erase(mask);
 750     masks_set2.erase(mask.getNormalized());
 751
 752     mask = Netmask("2010:a4::201f");
 753     masks_set1_cp5.erase(mask);
 754     masks_set2.erase(mask.getNormalized());
 755
 756     mask = Netmask("2010:1010::/16");
 757     masks_set1_cp5.erase(mask);
 758     masks_set2.erase(mask.getNormalized());
 759
 760     mask = Netmask("85.85.85.85");
 761     masks_set1_cp5.erase(mask);
 762     masks_set2.erase(mask.getNormalized());
 763
 764     mask = Netmask("170.170.170.170");
 765     masks_set1_cp5.erase(mask);
 766     masks_set2.erase(mask.getNormalized());
 767
 768     mask = Netmask("5555:5555:5555:5555:5555:5555:5555:5555");
 769     masks_set1_cp5.erase(mask);
 770     masks_set2.erase(mask.getNormalized());
 771
 772     mask = Netmask("aaaa:aaaa:aaaa:aaaa:aaaa:aaaa:aaaa:aaaa");
 773     masks_set1_cp5.erase(mask);
 774     masks_set2.erase(mask.getNormalized());
 775   }
 776
 777   // check set equality using iterators
 778   BOOST_CHECK_EQUAL(masks_set1_cp5.size(), masks_set2.size());
 779   BOOST_CHECK_EQUAL(std::distance(masks_set1_cp5.begin(), masks_set1_cp5.end()),
 780                     std::distance(masks_set2.begin(), masks_set2.end()));
 781   for (auto entry: masks_set1_cp5) {
 782     Netmask mask = entry.first.getNormalized();
 783
 784     BOOST_CHECK(masks_set2.find(mask) != masks_set2.end());
 785   }
 786   for (const Netmask& mask: masks_set2) {
 787     BOOST_CHECK(masks_set1_cp5.lookup(mask) != nullptr);
 788   }
 789 }
 790
 791 BOOST_AUTO_TEST_SUITE_END()