C++: forwarding with longest-prefix match
A router holds a forwarding table of prefixes, each written as an address and a prefix length such as 10.1.0.0/16. An address matches a prefix if its first prefix-length bits are equal. Several prefixes can match one address, and the router must use the one with the longest prefix, which is the most specific.
C++
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
struct Route {
std::uint32_t network;
int prefix;
std::string next_hop;
};
std::uint32_t ip(int a, int b, int c, int d) {
return (static_cast<std::uint32_t>(a) << 24) | (b << 16) | (c << 8) | d;
}
std::string lookup(const std::vector<Route>& table, std::uint32_t dest) {
int best = -1;
std::string hop = "drop";
for (const Route& r : table) {
std::uint32_t mask = r.prefix == 0 ? 0 : 0xFFFFFFFFu << (32 - r.prefix);
if ((dest & mask) == r.network && r.prefix > best) {
best = r.prefix;
hop = r.next_hop;
}
}
return hop;
}
int main() {
std::vector<Route> table = {
{ip(10, 0, 0, 0), 8, "A"},
{ip(10, 1, 0, 0), 16, "B"},
{ip(10, 1, 2, 0), 24, "C"},
{ip(0, 0, 0, 0), 0, "default"},
};
std::cout << "10.1.2.9 -> " << lookup(table, ip(10, 1, 2, 9)) << "\n";
std::cout << "10.1.9.9 -> " << lookup(table, ip(10, 1, 9, 9)) << "\n";
std::cout << "10.9.9.9 -> " << lookup(table, ip(10, 9, 9, 9)) << "\n";
std::cout << "8.8.8.8 -> " << lookup(table, ip(8, 8, 8, 8)) << "\n";
}