快速比較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的例子。