Advertisement
Guest User

Untitled

a guest
Mar 21st, 2019
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.61 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4.  
  5. struct route {
  6. short interface;
  7. short ip1;
  8. short ip2;
  9. short ip3;
  10. };
  11.  
  12. int binary_search(struct route* routes, short ip1temp, short ip2temp, short ip3temp, int inicio, int fim) {
  13.  
  14. if (fim >= inicio) {
  15. int mid = inicio + (fim - 1) / 2;
  16.  
  17. if (routes[mid].ip1 == ip1temp) {
  18. if (routes[mid].ip2 == ip2temp) {
  19. if (routes[mid].ip3 == ip3temp) {
  20. return routes[mid].interface;
  21. }
  22. }
  23. }
  24.  
  25. if (routes[mid].ip1 > ip1temp) {
  26. return binary_search(routes, ip1temp, ip2temp, ip3temp, inicio, mid - 1);
  27. }
  28. if (routes[mid].ip1 == ip1temp && routes[mid].ip2 > ip2temp) {
  29. return binary_search(routes, ip1temp, ip2temp, ip3temp, inicio, mid - 1);
  30. }
  31. if (routes[mid].ip1 == ip1temp && routes[mid].ip2 == ip2temp && routes[mid].ip3 > ip3temp) {
  32. return binary_search(routes, ip1temp, ip2temp, ip3temp, inicio, mid - 1);
  33. }
  34.  
  35. return binary_search(routes, ip1temp, ip2temp, ip3temp, mid + 1, fim);
  36. }
  37. else{
  38. if (routes[0].ip1 == 0 && routes[0].ip2 == 0 && routes[0].ip3 == 0) {
  39. return routes[0].interface;
  40. }else{
  41. // no route
  42. return -1;
  43. }
  44. }
  45. }
  46.  
  47.  
  48. int comparator(const void *p, const void *q)
  49. {
  50.  
  51. const struct route *a = p;
  52. const struct route *b = q;
  53.  
  54. if (a->ip1 > b->ip1){
  55. return 1;
  56. }
  57. else if (a->ip1 < b->ip1){
  58. return -1;
  59. }
  60. else if (a->ip2 > b->ip2 && a->ip1 == b->ip1){
  61. return 1;
  62. }
  63. else if (a->ip2 < b->ip2 && a->ip1 == b->ip1){
  64. return -1;
  65. }
  66. else if (a->ip3 > b->ip3 && a->ip2 == b->ip2 && a->ip1 == b->ip1){
  67. return 1;
  68. }
  69. else if (a->ip3 < b->ip3 && a->ip2 == b->ip2 && a->ip1 == b->ip1){
  70. return -1;
  71. }
  72. else{
  73. return 0;
  74. }
  75. }
  76.  
  77. int main() {
  78. struct route routes[100000];
  79. int n, i;
  80. short ip1temp, ip2temp, ip3temp, ip4temp;
  81.  
  82. scanf("%d", &n);
  83.  
  84. for (i = 0; i < n; i++) {
  85. scanf("%hd.%hd.%hd.0 %hd", &routes[i].ip1, &routes[i].ip2, &routes[i].ip3, &routes[i].interface);
  86. }
  87.  
  88. qsort(routes, n, sizeof(*routes), comparator);
  89.  
  90. while(scanf("%hd.%hd.%hd.%hd", &ip1temp, &ip2temp, &ip3temp, &ip4temp) != EOF){
  91.  
  92. short result = binary_search(routes, ip1temp, ip2temp, ip3temp, 0, n-1);
  93. if(result==-1){
  94. printf("no route\n");
  95. }else{
  96. printf("%hd\n", result);
  97. }
  98. }
  99. return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement