TopCoder challenge: SimpleRouter

feipigwang

浏览: 775332 次
性别:
来自: 北京

最近访客更多访客>>

mchong

米糠杰

leon916

bxjgood66

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1207)

社区版块

存档分类

This implementation is by no means elegant: it does not handle error well; it uses the same space for a forward table with a rule table; it uses hand-coded parsing, which is hard to read and modify...

But it has to comply with some constraints: it has to use ONLY the standard library, it must be completed in a short time.

Then I post it here, after some polishing, for a reference.

SimpleRouter.cpp:

#include <vector>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

class SimpleRouter
{
public:
typedef unsigned short num_type;
typedef pair<num_type, num_type> range_type;
typedef vector<range_type> ip_type;
typedef vector<ip_type> forward_table_type;
typedef pair<string, ip_type> rule_type;
typedef vector<rule_type> rule_table_type;

// This method & its signature is required by the problem.
vector<string> route(vector<string> rules, vector<string> packets);

private:
string route(ip_type& packet);

bool range_any(const range_type& ip_seg);
bool match(const ip_type& rule_ip, const ip_type& packet);

range_type parse_ip_seg(string& seg);
ip_type parse_ip(const string& ip);

string ip_seg_to_string(const range_type& ip_seg);
string ip_to_string(const ip_type& ip, char port_seperator);

string get_forward(const ip_type& rule, ip_type packet);

private:
const static num_type min_num = 0;
const static num_type max_num = static_cast<num_type>(-1);

rule_table_type rule_table;
forward_table_type forward_table;

void build_table(vector<string>& rules);

public:
// For debug
void print_table();
void print_ip(const ip_type& ip);

};

void SimpleRouter::build_table(vector<string>& rules)
{
rule_table.reserve(rules.size());
forward_table.reserve(rules.size());

string action, ip_str, port_str;
for(vector<string>::const_iterator iter = rules.begin();
iter != rules.end(); ++iter)
{
string::size_type end_action = iter->find_first_of(' ');
action = iter->substr(0, end_action);
ip_str = iter->substr(end_action + 1);

if(action == "FORWARD")
{
// get position of forward target
string::size_type temp = ip_str.find_first_of(' ') + 1;
string::size_type start_fwdip = ip_str.find_first_of(' ', temp) + 1;

rule_table.push_back(make_pair(action, parse_ip(ip_str.substr(0, start_fwdip - 1))));
forward_table.push_back(parse_ip(ip_str.substr(start_fwdip)));
}
else
{
rule_table.push_back(make_pair(action, parse_ip(ip_str)));
// push a placeholder to forward table
forward_table.push_back(ip_type());
}
}
}

vector <string> SimpleRouter::route(vector<string> rules, vector<string> packets)
{
build_table(rules);

vector<string> ret;
for(vector<string>::iterator iter = packets.begin();
iter != packets.end(); ++iter)
{
ret.push_back(route(parse_ip(*iter)));
}
return ret;
}

string SimpleRouter::route(ip_type& packet)
{
// check rules one-by-one reversely, as the last matched rule counts
forward_table_type::const_reverse_iterator fwd_iter = forward_table.rbegin();
rule_table_type::const_reverse_iterator rule_iter = rule_table.rbegin();
// workaround for a VC7.1 bug
rule_table_type::const_reverse_iterator rule_rend = rule_table.rend();

for(; rule_iter != rule_rend; ++rule_iter, ++fwd_iter)
{
string action = rule_iter->first;

if(action == "FORWARD")
{
if(match(rule_iter->second, packet))
{
return get_forward(*fwd_iter, packet);
}
}
else
{
if(match(rule_iter->second, packet))
return action;
}
}

// match no rules
return "REJECT";
}

string SimpleRouter::get_forward(const ip_type& fwd, ip_type packet)
{
// if fwd port is specified, replace packet port with fwd port
if(fwd.size() > 4 && !range_any(fwd[4]))
packet[4] = fwd[4];

return ip_to_string(packet, ':');
}

bool inline SimpleRouter::range_any(const range_type& ip_seg)
{
return ip_seg.first == min_num && ip_seg.second == max_num;
}

bool SimpleRouter::match(const ip_type& rule_ip, const ip_type& packet)
{
ip_type::const_iterator rule_iter = rule_ip.begin();
ip_type::const_iterator pk_iter = packet.begin();

for( ; rule_iter != rule_ip.end(); ++rule_iter, ++pk_iter)
{
// see if packet ip is within the range of rule
if(!(rule_iter->first <= pk_iter->first) ||
!(rule_iter->second >= pk_iter->second))
return false;
}
return true;
}

string SimpleRouter::ip_seg_to_string(const range_type& ip_seg)
{
char ret[12] = "*"; //the longest possible segment is 11 chars:
//xxxxx-xxxxx

if(!range_any(ip_seg))
{
int len = sprintf(ret, "%d", ip_seg.first);
if(ip_seg.first != ip_seg.second)
{
ret[len] = '-';
sprintf(ret + len + 1, "%d", ip_seg.second);
}
}

return ret;
}

string SimpleRouter::ip_to_string(const ip_type& ip, char port_seperator)
{
string ret;
ret.reserve(44); //the longest possible ip string is 43 chars:
//xxx-xxx.xxx-xxx.xxx-xxx.xxx-xxx xxxxx-xxxxx

ip_type::const_iterator iter = ip.begin();
for(int i = 0; iter != ip.end(); ++iter, ++i)
{
ret.append(ip_seg_to_string(*iter));
if(i < 3)
ret.append(".");
else if(i == 3)
ret.append(1, port_seperator);
}

return ret;
}

SimpleRouter::range_type SimpleRouter::parse_ip_seg(string& seg)
{
if(seg == "*")
{
return make_pair(min_num, max_num);
}
else
{
string::size_type dash_pos = seg.find_first_of('-');

num_type start, end;
if(dash_pos == string::npos)
{
stringstream(seg) >> start;
end = start;
}
else
{
stringstream(seg.substr(0, dash_pos)) >> start;
stringstream(seg.substr(++dash_pos)) >> end;
}

return make_pair(start, end);
}
}

SimpleRouter::ip_type SimpleRouter::parse_ip(const string& ip)
{
ip_type ret;

// break string ip into ip & port
string::size_type end_ip, start_port;

end_ip = ip.find_first_of(' ');
start_port = (end_ip == string::npos) ? string::npos : end_ip + 1;

// parse the 4 segment of ip
string::size_type start_seg = 0, end_seg;
for(int i = 0; i < 4; ++i)
{
end_seg = (i == 3) ? end_ip : ip.find_first_of('.', start_seg);
ret.push_back(parse_ip_seg(ip.substr(start_seg, end_seg - start_seg)));
start_seg = end_seg + 1;
}

// parse port(optional)
if(start_port != string::npos)
ret.push_back(parse_ip_seg(ip.substr(start_port)));

return ret;
}

//===================== For debug ======================
void SimpleRouter::print_ip(const ip_type& ip)
{
cout << ip_to_string(ip, ' ');
}

void SimpleRouter::print_table()
{
rule_table_type::iterator rule_iter = rule_table.begin();
forward_table_type::iterator fwd_iter = forward_table.begin();

for(; rule_iter != rule_table.end(); ++rule_iter, ++fwd_iter)
{
cout << rule_iter->first << " ";

print_ip(rule_iter->second);
if(!fwd_iter->empty())
{
cout << " ";
print_ip(*fwd_iter);
}

cout << endl;
}
}

//========================== Test ===========================
#include <iostream>
#include <algorithm>

template <class T>
struct ArraySize
{};

template <class T, int D>
struct ArraySize<T[D]>
{
static const int value = D;
};

template <class ARY>
void InitWith(vector<string>& vect, const ARY& ary)
{
int size = ArraySize<ARY>::value;

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<string> rules, packets;
InitWith(rules, rule_ary);
InitWith(packets, packet_ary);

SimpleRouter router;
vector<string> ret = router.route(rules, packets);

for(vector<string>::iterator i = ret.begin(); i != ret.end(); ++i)
cout << *i << endl;

//============ debug =============
cout << endl << "Rule table, with forwards: " << endl;
router.print_table();
//================================
}

=================================================================================
cl /EHsc SimpleRouter.cpp

SimpleRouter

OUTPUT:

ACCEPT
ACCEPT
REJECT
177.73.138.69:14319
112.65.145.82:26287
55.63.173.239:45899

Rule table, with forwards:
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

分享到：