Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- struct route {
- short interface;
- short ip1;
- short ip2;
- short ip3;
- };
- int binary_search(struct route* routes, short ip1temp, short ip2temp, short ip3temp, int inicio, int fim) {
- if (fim >= inicio) {
- int mid = inicio + (fim - 1) / 2;
- if (routes[mid].ip1 == ip1temp) {
- if (routes[mid].ip2 == ip2temp) {
- if (routes[mid].ip3 == ip3temp) {
- return routes[mid].interface;
- }
- }
- }
- if (routes[mid].ip1 > ip1temp) {
- return binary_search(routes, ip1temp, ip2temp, ip3temp, inicio, mid - 1);
- }
- if (routes[mid].ip1 == ip1temp && routes[mid].ip2 > ip2temp) {
- return binary_search(routes, ip1temp, ip2temp, ip3temp, inicio, mid - 1);
- }
- if (routes[mid].ip1 == ip1temp && routes[mid].ip2 == ip2temp && routes[mid].ip3 > ip3temp) {
- return binary_search(routes, ip1temp, ip2temp, ip3temp, inicio, mid - 1);
- }
- return binary_search(routes, ip1temp, ip2temp, ip3temp, mid + 1, fim);
- }
- else{
- if (routes[0].ip1 == 0 && routes[0].ip2 == 0 && routes[0].ip3 == 0) {
- return routes[0].interface;
- }else{
- // no route
- return -1;
- }
- }
- }
- int comparator(const void *p, const void *q)
- {
- const struct route *a = p;
- const struct route *b = q;
- if (a->ip1 > b->ip1){
- return 1;
- }
- else if (a->ip1 < b->ip1){
- return -1;
- }
- else if (a->ip2 > b->ip2 && a->ip1 == b->ip1){
- return 1;
- }
- else if (a->ip2 < b->ip2 && a->ip1 == b->ip1){
- return -1;
- }
- else if (a->ip3 > b->ip3 && a->ip2 == b->ip2 && a->ip1 == b->ip1){
- return 1;
- }
- else if (a->ip3 < b->ip3 && a->ip2 == b->ip2 && a->ip1 == b->ip1){
- return -1;
- }
- else{
- return 0;
- }
- }
- int main() {
- struct route routes[100000];
- int n, i;
- short ip1temp, ip2temp, ip3temp, ip4temp;
- scanf("%d", &n);
- for (i = 0; i < n; i++) {
- scanf("%hd.%hd.%hd.0 %hd", &routes[i].ip1, &routes[i].ip2, &routes[i].ip3, &routes[i].interface);
- }
- qsort(routes, n, sizeof(*routes), comparator);
- while(scanf("%hd.%hd.%hd.%hd", &ip1temp, &ip2temp, &ip3temp, &ip4temp) != EOF){
- short result = binary_search(routes, ip1temp, ip2temp, ip3temp, 0, n-1);
- if(result==-1){
- printf("no route\n");
- }else{
- printf("%hd\n", result);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement