前綴匹配
網絡層的數據報網絡，在路由器轉發功能實現中會用到前綴匹配，即是對 IP 地址與路由表中的目的地址范圍的公共部分進行前綴匹配。
由于有的前綴存在包含的問題，對有些 IP 地址會造成多重匹配，短的匹配會造成 IP 的轉發錯誤。
所以可以遵循 最長前綴匹配原則 進行匹配。
首先做一個 ip 轉換的實現
從 unsigned int 32 位整型數到 ip 字符串的轉換
從 ip 字符串到 unsigned int 32 位整型數的轉換
1 #include <cstdio>
2 #include <iostream>
3 #include <string>
4 using namespace std;
5
6 string uintToIp(unsigned nip)
7 {
8 int t[4];
9 for (int i = 3; i >= 0; --i)
10 {
11 t[i] = nip % 256;
12 nip /= 256;
13 }
14 string ret;
15 char s[4];
16 for (int i = 0; i < 3; ++i)
17 {
18 ret += itoa(t[i], s, 10);
19 ret += '.';
20 }
21 return ret += itoa(t[3], s, 10);
22 }
23
24 unsigned ipToUint(const string& ip)
25 {
26 unsigned ret = 0;
27 string::size_type st1 = 0, st2 = 0;
28 string t;
29 while ((st2 = ip.find('.', st1)) != string::npos)
30 {
31 t = ip.substr(st1, st2 - st1);
32 ret = ret * 256 + atoi(t.c_str());
33 st1 = st2 + 1;
34 }
35 t = ip.substr(st1, ip.size() - st2);
36 return ret = ret * 256 + atoi(t.c_str());
37 }
38
39 int main()
40 {
41 unsigned nip;
42 string ip;
43 while (cin >> nip)
44 {
45 cout << uintToIp(nip) << endl;
46
47 cin >> ip;
48 cout << ipToUint(ip) << endl;
49 }
50 return 0;
51 }
ip 的形式有三種
·點式十進制
·二進制
·unsigned
它們之間的轉換以 unsigned 為橋梁
前綴匹配的實現
利用異或，與前綴進行異或，如果得到的結果的相應位都為 0 則說明匹配成功，否則沒有匹配成功。
------------------------------
前綴匹配 鏈路接口
xxxxxxxxxxx 0
xxxxxxxxxxxxxx 1
xxxxxxxxxxx 2
其他 3
------------------------------
前綴匹配也可以直接尋找在轉發表里的排序前綴中，第一個大于待匹配的 ip 的那個前綴即是前綴匹配成功的。
1 #include <cstdio>
2 #include <iostream>
3 #include <string>
4 #include <map>
5 using namespace std;
6
7 string uintToIp(unsigned nip)
8 {
9 int t[4];
10 for (int i = 3; i >= 0; --i)
11 {
12 t[i] = nip % 256;
13 nip /= 256;
14 }
15 string ret;
16 char s[4];
17 for (int i = 0; i < 3; ++i)
18 {
19 ret += itoa(t[i], s, 10);
20 ret += '.';
21 }
22 return ret += itoa(t[3], s, 10);
23 }
24
25 unsigned ipToUint(const string& ip)
26 {
27 unsigned ret = 0;
28 string::size_type st1 = 0, st2 = 0;
29 string t;
30 while ((st2 = ip.find('.', st1)) != string::npos)
31 {
32 t = ip.substr(st1, st2 - st1);
33 ret = ret * 256 + atoi(t.c_str());
34 st1 = st2 + 1;
35 }
36 t = ip.substr(st1, ip.size() - st2);
37 return ret = ret * 256 + atoi(t.c_str());
38 }
39
40 unsigned binaryIpToUint(const string& bip)
41 {
42 unsigned ret = 0;
43 for (string::size_type i = 0; i != bip.size(); ++i)
44 {
45 ret = ret * 2 + (bip[i] - '0');
46 }
47 return ret;
48 }
49
50 string uintToBinaryIp(unsigned uip)
51 {
52 string ret;
53 for (int i = 0; i != 32; ++i)
54 {
55 if (uip >= (1 << 31))
56 {
57 ret += '1';
58 }
59 else
60 {
61 ret += '0';
62 }
63 uip <<= 1;
64 }
65 return ret;
66 }
67
68 string binaryIpToIp(const string& bip)
69 {
70 return uintToIp(binaryIpToUint(bip));
71 }
72
73 string ipToBinaryIp(const string& ip)
74 {
75 return uintToBinaryIp(ipToUint(ip));
76 }
77
78 //unsigned findNonZeroBitNo(unsigned prefix)
79 //{
80 // unsigned ret = 0;
81 // unsigned mask = 1 << 31;
82 // while ((prefix & mask) == 0)
83 // {
84 // ++ret;
85 // prefix <<= 1;
86 // }
87 // return ret;
88 //}
89
90 bool marchPrefix(unsigned nip, const string& prefix)
91 {
92 string ip = uintToBinaryIp(nip);
93 return ip.substr(0, prefix.size()) == prefix;
94 }
95
96 struct Prefix
97 {
98 string bip;
99 Prefix(const string& s) : bip(s) {}
100 };
101
102 bool operator < (const Prefix& lhs, const Prefix& rhs)
103 {
104 if (lhs.bip < rhs.bip)
105 {
106 if (rhs.bip.find(lhs.bip) != string::npos)
107 {
108 return false;
109 }
110 else
111 {
112 return true;
113 }
114 }
115 else if (lhs.bip > rhs.bip)
116 {
117 if (lhs.bip.find(rhs.bip) != string::npos)
118 {
119 return true;
120 }
121 else
122 {
123 return false;
124 }
125 }
126 else
127 {
128 return false;
129 }
130 }
131
132 bool operator == (const Prefix& lhs, const Prefix& rhs)
133 {
134 return lhs.bip == rhs.bip;
135 }
136
137 int main()
138 {
139 map<Prefix, unsigned> forwardingtable;
140 forwardingtable[Prefix("110010000001011100010")] = 0;
141 forwardingtable[Prefix("110010000001011100011000")] = 1;
142 forwardingtable[Prefix("110010000001011100011")] = 2;
143
144 for (map<Prefix, unsigned>::const_iterator cit = forwardingtable.begin(); cit != forwardingtable.end(); ++cit)
145 {
146 cout << cit->first.bip << '\t' << cit->second << endl;
147 }
148
149 unsigned nip;
150 string ip;
151 while (cin >> ip)
152 {
153 nip = ipToUint(ip);
154 //cout << nip << endl;
155 unsigned linkinterface = 3;
156 for (map<Prefix, unsigned>::const_iterator cit = forwardingtable.begin(); cit != forwardingtable.end(); ++cit)
157 {
158 if (marchPrefix(nip, cit->first.bip) == true)
159 {
160 linkinterface = cit->second;
161 break;
162 }
163 }
164 cout << linkinterface << endl;
165 }
166 return 0;
167 }
posted on 2011-06-17 14:36
unixfy 閱讀(795)
評論(0) 編輯 收藏 引用