快速比较IP地址的最佳方法？

Question

我有IP地址的列表，存储的是这样的：

char IP_addresses_list[] = { 
    "157.55.130", /* 157.55.130.0/24 */ 
    "157.56.52", /* 157.56.52.0/24 */ 
    "157.12.53", /* 157.12.53.0/24 */ 
    ... 
}; 

我从嗅探到的数据包中的IP地址（铸造struct iphdr *iph = (struct iphdr *)(packet + sizeof(struct ether_header));我把它转换使用inet_ntop的字符串;最后，我比较从列表中的那些用下面的代码数据包的IP地址：

/* 
* input: IP address to search in the list 
* output: 1 if IP address is found in the list, 0 otherwise 
*/ 
int find_IP_addr(char *server) { 
    int ret = 0; 
    int i, string_size1, string_size2; 
    char *copied_server, *copied_const_char; 
    char *save_ptr1, *save_ptr2; 
    char dot[2] = "."; 
    /* Here I store the IP address from the packet */ 
    char first_IPaddr_pkt[4], second_IPaddr_pkt[4], third_IPaddr_pkt[4]; 
    /* Here I store the IP address from the list */ 
    char first_IPaddr_list[4], second_IPaddr_list[4], third_IPaddr_list[4]; 

    string_size1 = strlen(server)+1; 
    copied_server = (char *)malloc(string_size1 * sizeof(char)); 
    strcpy(copied_server, server); 

    /* I store and compare the first three bits of the IP address */ 
    strcpy(first_IPaddr_pkt, strtok_r(copied_server, dot, &save_ptr1)); 
    strcpy(second_IPaddr_pkt, strtok_r(NULL, dot, &save_ptr1)); 
    strcpy(third_IPaddr_pkt, strtok_r(NULL, dot, &save_ptr1)); 
    printf("tokenized %s, %s and %s\n", first_IPaddr_pkt, second_IPaddr_pkt, third_IPaddr_pkt); 

    /* Now I scan the list */ 
    for (i=0; i<LIST_LENGTH; i++) { 
     /* I copy an address from the list */ 
     string_size2 = strlen(IP_addresses_list[i])+1; // +1 for null character 
     copied_const_char = (char *)malloc(string_size2 * sizeof(char)); 
     strcpy(copied_const_char, IP_addresses_list[i]); 
     /* Let's split the address from the list */ 
     strcpy(first_IPaddr_list, strtok_r(copied_const_char, dot, &save_ptr2)); 
     strcpy(second_IPaddr_list, strtok_r(NULL, dot, &save_ptr2)); 
     strcpy(third_IPaddr_list, strtok_r(NULL, dot, &save_ptr2)); 
     printf("tokenized %s, %s and %s\n", first_IPaddr_list, second_IPaddr_list, third_IPaddr_list); 
     /* I compare the first byte of the address from the packet I got and 
     the first byte of the address from the list: 
     if they are different, there's no reason to continue comparing 
     the other bytes of the addresses */ 
     if (strcmp(first_IPaddr_pkt, first_IPaddr_list) != 0) { 
      continue; 
     } 
     else { 
      if (strcmp(second_IPaddr_pkt, second_IPaddr_list) != 0) { 
       continue; 
     } 
     else { 
      if (strcmp(third_IPaddr_pkt, third_IPaddr_list) != 0) { 
       continue; 
      } 
      else 
       /* All the bytes are the same! */ 
       ret = 1; 
      } 
     } 
     free(copied_const_char); 
    } 
    free(copied_server); 
    return ret; 
} 

我想使这更快捷，无需使用strtok，strcmp，malloc或free 在/usr/include/netinet/ip.h我看到地址是

u_int32_t saddr; 
u_int32_t daddr; 

是否有可能甚至不需要使用inet_ntop第一，也许仅仅比较这两个地址，但他们仍然是u_int32_t比较？

编辑：这里有一个解决方案的例子，谁会读这个问题。

#include <stdio.h> 
#include <sys/types.h> 

int main() { 

    // In the list I have: 104.40.0.0./13 
    int cidr = 13; 
    u_int32_t ipaddr_from_pkt = 1747488105;  // pkt coming from 104.40.141.105 
    u_int32_t ipaddr_from_list = 1747451904; // 104.40.0.0 
    int mask = (-1) << (32 - cidr); 

    if ((ipaddr_from_pkt & mask) == ipaddr_from_list) 
     printf("IP address belongs to the given range!!!\n"); 
    else printf ("failure\n"); 

    return 0; 
} 

感谢iharob也为bsearch提示。

Answer 1

我会避免将二进制数据转换为字符串。如果将它们保留为二进制，则很容易比较：

match = (ip & listed_mask) == listed_ip; 

“/ 24”是一个掩码。意味着最高24位是相关的。将其转换为二进制掩码如下：

listed_mask = (-1) << (32 - 24); 

Answer 2

性能问题与strcmp()无关，malloc()是不必要的。

如果您只使用IPv4地址，则只需要个字符来存储它，以便您可以删除malloc()并将临时存储声明为数组。

但是如果在列表中会有很多的IP地址，这会有一个重要的改进。

首先，您需要对IP地址列表进行排序，然后使用bsearch()来搜索正确的IP。这样的代码将在O（日志（2N））时间比O（N）快得多运行，专为大型N

Answer 3

最快的方法是将存储地址在字典中，看到this link

Answer 4

我在这里的做法是：

1. 只需使用strncat与".0"建立有效的IPv4地址。
2. 使用getaddrinfo与插座等类型的常数值打造addrinfo结构
3. 比较addrinfo的相关领域。

基本上，从man getaddrinfo does all this的例子。