TopCoder challenge: SimpleRouter

阿尔萨斯

浏览: 4170334 次

最近访客更多访客>>

snower_tt

iams13

u012363178

wangyy

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2014-10 ( 581)
2014-09 ( 572)
2014-08 ( 545)
更多存档...

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 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 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 { 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 } 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 first print_ip(rule_iter->second); if(!fwd_iter->empty()) { cout print_ip(*fwd_iter); } cout } } //========================== Test =========================== #include <iostream> #include <algorithm> template <class t> struct ArraySize {}; template <class t int d> struct ArraySize<t> { 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 //============ debug ============= cout 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 </string></string></string></ary></string></class></t></class></class></algorithm></iostream></string></string></string></string></string></string></string></string></num_type></string></string></string></rule_type></string></ip_type></range_type></num_type></sstream></iostream></string></vector>

分享到：