SimpleRouter.cpp:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
using namespace boost;
using namespace boost::lambda;
typedef unsigned char ip_seg_type;
typedef unsigned short port_type;
typedef pair
typedef pair
typedef array
typedef array
typedef tokenizer
struct Addr
{
Addr(const string& addr)
{ from_string(addr); }
ip_type ip;
port_type port;
bool has_port;
void from_string(const string& str);
string to_string();
};
void Addr::from_string(const string& str)
{
char_separator
token tok_addr(str, sep_ip_port);
token::const_iterator tok_addr_iter = tok_addr.begin();
string ip_str = *tok_addr_iter;
has_port = ++tok_addr_iter != tok_addr.end();
token tok_ip(ip_str, sep_ip_seg);
transform(tok_ip.begin(), tok_ip.end(), ip.begin(),
bind(&atoi, bind(&string::c_str, _1))
);
if(has_port) port = atoi(tok_addr_iter->c_str());
}
string Addr::to_string()
{
string ret;
ret.reserve(22); //xxx.xxx.xxx.xxx xxxxx
for(ip_type::const_iterator iter = ip.begin();
iter != ip.end(); ++iter)
{
char buf[5];
sprintf(buf, "%d.", *iter);
ret.append(buf);
}
// remove last '.'
ret.erase(--ret.end());
if(has_port)
{
char buf[7];
sprintf(buf, " %d", port);
ret.append(buf);
}
return ret;
}
template
T parse_seg_range(const string& str)
{
if(str == "*")
{
return make_pair(numeric_limits<:first_type>::min(),
numeric_limits<:second_type>::max());
}
else
{
char_separator
token tok(str, sep);
token::const_iterator tok_iter = tok.begin();
T::first_type first = static_cast<:first_type>(atoi(tok_iter->c_str()));
T::second_type second = ++tok_iter == tok.end() ? first :
static_cast<:second_type>(atoi(tok_iter->c_str()));
return make_pair(first, second);
}
}
template
string seg_range_to_string(T& seg_range)
{
if(seg_range.first == numeric_limits<:first_type>::min() &&
seg_range.second == numeric_limits<:second_type>::max())
{
return "*";
}
else
{
char buf[12];
int len = sprintf(buf, "%d", seg_range.first);
if(seg_range.second != seg_range.first)
{
buf[len] = '-';
sprintf(buf + len + 1, "%d", seg_range.second);
}
return buf;
}
}
template
bool inline seg_covers(const Range& seg_range, const Seg& seg)
{
return seg_range.first = seg;
}
struct AddrRange
{
AddrRange(const string& str)
{ from_string(str); }
ip_range_type ip_range;
port_range_type port_range;
void from_string(const string& str);
string to_string();
bool covers(const Addr& addr);
};
void AddrRange::from_string(const string& str)
{
char_separator
token tok_addr(str, sep_ip_port);
string ip_range_str = *tok_addr.begin();
token tok_ip_range(ip_range_str, sep_ip_seg);
ip_seg_range_type (*parser)(const string&) = &parse_seg_range
transform(tok_ip_range.begin(), tok_ip_range.end(), ip_range.begin(),
bind(parser, _1)
);
port_range = parse_seg_range
}
string AddrRange::to_string()
{
string ret;
ret.reserve(44);
for(ip_range_type::const_iterator ip_range_iter = ip_range.begin();
ip_range_iter != ip_range.end(); ++ip_range_iter)
{
ret.append(seg_range_to_string(*ip_range_iter));
ret.append(1, '.');
}
// replace the last '.' with a ' '
*--ret.end() = ' ';
ret.append(seg_range_to_string(port_range));
return ret;
}
bool AddrRange::covers(const Addr& addr)
{
ip_type::const_iterator ip_iter = addr.ip.begin();
// function pointer to seg_covers.
// neither bind or boost.function can be used without a concern here.
bool (*range_covers_ip)(const ip_seg_range_type&, const ip_seg_type&) =
&seg_covers
bool ip_covered = find_if(ip_range.begin(), ip_range.end(),
!bind(range_covers_ip, _1, *var(ip_iter)++)
) == ip_range.end();
return ip_covered && seg_covers(port_range, addr.port);
}
class rule
{
public:
virtual string validate(const Addr& packet) = 0;
virtual string to_string() const = 0;
};
class accept_rule : public rule
{
public:
accept_rule(const string& str)
{ range_.reset(new AddrRange(str)); }
virtual string validate(const Addr& packet)
{ return range_->covers(packet) ? "ACCEPT" : ""; }
virtual string to_string() const
{ return string("ACCEPT ").append(range_->to_string()); }
private:
auto_ptr
};
class reject_rule : public rule
{
public:
reject_rule(const string& str)
{ range_.reset(new AddrRange(str)); }
virtual string validate(const Addr& packet)
{ return range_->covers(packet) ? "REJECT" : ""; }
virtual string to_string() const
{ return string("REJECT ").append(range_->to_string()); }
private:
auto_ptr
};
class forward_rule : public rule
{
public:
forward_rule(const string& str);
virtual string validate(const Addr& packet)
{ return range_->covers(packet) ? make_forward(packet) : ""; }
virtual string to_string() const
{ return string("FORWARD ").append(range_->to_string())
.append(" ").append(fwd_->to_string()); }
string make_forward(const Addr& packet);
private:
auto_ptr
auto_ptr
};
forward_rule::forward_rule(const string& str)
{
string::size_type pos = str.find_first_of(' ');
pos = str.find_first_of(' ', pos + 1);
range_.reset(new AddrRange(str.substr(0, pos)));
fwd_.reset(new Addr(str.substr(++pos)));
}
string forward_rule::make_forward(const Addr& packet)
{
bool fwd_has_port = fwd_->has_port;
if(!fwd_has_port)
{
fwd_->has_port = true;
fwd_->port = packet.port;
}
string ret = fwd_->to_string();
fwd_->has_port = fwd_has_port;
return ret;
}
auto_ptr
{
string::size_type pos = str.find_first_of(' ');
string action = str.substr(0, pos);
auto_ptr
if(action == "ACCEPT")
ret.reset(new accept_rule(str.substr(++pos)));
else if(action == "REJECT")
ret.reset(new reject_rule(str.substr(++pos)));
else if(action == "FORWARD")
ret.reset(new forward_rule(str.substr(++pos)));
else
throw "Unexpected rule";
return ret;
}
class SimpleRouter
{
public:
// This method & its signature is required by the problem.
vector
typedef vector
private:
string route_packet(const Addr& packet);
void build_rule_table(const svect_type& rules);
void print_rule_table();
private:
typedef ptr_vector
rule_table_type rule_table_;
};
vector
{
build_rule_table(rules);
svect_type ret;
for(svect_type::const_iterator iter = packets.begin();
iter != packets.end(); ++iter)
{
ret.push_back(route_packet(Addr(*iter)));
}
return ret;
}
string SimpleRouter::route_packet(const Addr& packet)
{
for(rule_table_type::reverse_iterator iter = rule_table_.rbegin();
iter != rule_table_.rend(); ++iter)
{
string ret = iter->validate(packet);
if(!ret.empty())
return ret;
}
return "REJECT";
}
void SimpleRouter::build_rule_table(const svect_type& rules)
{
rule_table_.reserve(rules.size());
for(svect_type::const_iterator iter = rules.begin();
iter != rules.end(); ++iter)
rule_table_.push_back(make_rule(*iter).release());
}
void SimpleRouter::print_rule_table()
{
for(rule_table_type::const_iterator iter = rule_table_.begin();
iter != rule_table_.end(); ++iter)
cout to_string()
}
//========================== Test ===========================
#include
#include
template
struct ArraySize
{};
template
struct ArraySize
{
static const int value = D;
};
template
void InitWith(vector
{
int size = ArraySize
vect.reserve(size);
vect.insert(vect.begin(), ary, ary + size);
}
int main()
{
string rule_ary[] =
{
"REJECT *.20-252.114-157.36-91 13171-54085",
"ACCEPT *.*.73-180.* *",
"FORWARD 55.63.173.239 * 168.154.33.25",
"REJECT *.72-73.*.48-191 *",
"REJECT 20.51.*.* 4579",
"ACCEPT 70-166.*.*.86-182 *",
"REJECT 88-190.*.119-157.* 3316-27844",
"FORWARD *.52-221.134-250.66-207 * 116.94.120.82"
};
string packet_ary[] =
{
"203.11.104.45 44072",
"154.92.128.87 30085",
"20.51.68.55 4579",
"177.73.138.69 14319",
"112.65.145.82 26287",
"55.63.173.239 45899"
};
vector
InitWith(rules, rule_ary);
InitWith(packets, packet_ary);
SimpleRouter router;
vector
for_each(ret.begin(), ret.end(), cout
}
=================================================================================
cl /EHsc SimpleRouter.cpp
SimpleRouter
ACCEPT
ACCEPT
REJECT
116.94.120.82 14319
116.94.120.82 26287
168.154.33.25 45899
There are still numerous places to improve. I'll come back to this some day later.