Skip to content

Instantly share code, notes, and snippets.

@fabware
Forked from chenshuo/iprange.cc
Created September 21, 2011 23:08
Show Gist options
  • Save fabware/1233586 to your computer and use it in GitHub Desktop.
Save fabware/1233586 to your computer and use it in GitHub Desktop.
从一组 IP range --> value 的数据中查找单个 IP
#include <assert.h>
#include <stdint.h>
#include <algorithm>
#include <vector>
using namespace std;
struct IPrange
{
uint32_t startIp;
uint32_t endIp;
int value;
};
bool operator<(const IPrange& lhs, const IPrange& rhs)
{
return lhs.startIp < rhs.startIp;
}
bool operator==(const IPrange& lhs, const IPrange& rhs)
{
return lhs.startIp == rhs.startIp;
}
int findIpValue(const vector<IPrange>& ranges, uint32_t ip)
{
int result = -1;
if (!ranges.empty())
{
IPrange needle = { ip, 0, 0 };
vector<IPrange>::const_iterator it = lower_bound(ranges.begin(), ranges.end(), needle);
if (it == ranges.end())
{
--it;
}
else if (it != ranges.begin() && it->startIp > ip)
{
--it;
}
if (it->startIp <= ip && it->endIp >= ip)
{
result = it->value;
}
}
return result;
}
int main()
{
vector<IPrange> ranges;
IPrange r1 = { 123, 234, 999 };
ranges.push_back(r1);
sort(ranges.begin(), ranges.end());
assert(adjacent_find(ranges.begin(), ranges.end()) == ranges.end());
int v = findIpValue(ranges, 0);
assert(v == -1);
v = findIpValue(ranges, 122);
assert(v == -1);
v = findIpValue(ranges, 123);
assert(v == 999);
v = findIpValue(ranges, 234);
assert(v == 999);
v = findIpValue(ranges, 235);
assert(v == -1);
IPrange r2 = { 1000, 2000, 7777 };
ranges.push_back(r2);
sort(ranges.begin(), ranges.end());
assert(adjacent_find(ranges.begin(), ranges.end()) == ranges.end());
v = findIpValue(ranges, 0);
assert(v == -1);
v = findIpValue(ranges, 122);
assert(v == -1);
v = findIpValue(ranges, 123);
assert(v == 999);
v = findIpValue(ranges, 234);
assert(v == 999);
v = findIpValue(ranges, 235);
assert(v == -1);
v = findIpValue(ranges, 999);
assert(v == -1);
v = findIpValue(ranges, 1000);
assert(v == 7777);
v = findIpValue(ranges, 1500);
assert(v == 7777);
v = findIpValue(ranges, 2000);
assert(v == 7777);
v = findIpValue(ranges, 2001);
assert(v == -1);
v = findIpValue(ranges, 1073741824);
assert(v == -1);
IPrange r3 = { 1073741824U*3, 1073741824U*3+1073741823U, 5555 };
ranges.push_back(r3);
v = findIpValue(ranges, 1073741824U*2);
assert(v == -1);
v = findIpValue(ranges, 1073741824U*3);
assert(v == 5555);
v = findIpValue(ranges, 1073741824U*3+1073741822U);
assert(v == 5555);
v = findIpValue(ranges, 1073741824U*3+1073741823U);
assert(v == 5555);
v = findIpValue(ranges, 1073741824U*3+1073741824U);
assert(v == -1);
IPrange r4 = { 1073741824U*3+1073741823U, 1073741824U*3+1073741823U, 3333 };
ranges.push_back(r4);
v = findIpValue(ranges, 1073741824U*3+1073741822U);
assert(v == 5555);
v = findIpValue(ranges, 1073741824U*3+1073741823U);
assert(v == 3333);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment