IP trie树接口

自己实现了一个IP trie树接口.

在这里保存一下，方便备份以后使用，同时欢迎纠错和交流，希望有大神能指教更高效的算法.

1.头文件如下(iptrie.h)

 #ifndef _IP_TRIE_H_

 #define _IP_TIRE_H_

 #define SPLIT_SIGN "."

 #define IP_BINARY_LEN 32

 typedef struct ip_trie_node

 {

     struct ip_trie_node *child[]; //two child node

 }ip_trie_node;

 ip_trie_node *create_iptrie_node();

 void insert_iptrie_node(ip_trie_node *root,char ip[]);

 int select_iptrie_node(ip_trie_node *root,char ip[]);

 #endif

2.c文件如下(iptrie.c)

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #include "iptrie.h"

 /*

  *name: itobinary

  *

  *param:

  * num: orignal number; binary_str: dest string; index: the binary str copy index

  *

  *return:

  * void

  */

 void itobinary(int num,char binary_str[],int index)

 {

     if(binary_str == NULL)

     {

         return;

     }

     int i,bit = 0x01;

     for(i = ; i < ; i++)

     {//conver integer to 8 bit binary str

         if((num & bit) != )

         {//oprater & is lower than !=

             binary_str[index +  - i] = '';

         }

         else

         {

             binary_str[index +  - i] = '';

         }

         bit <<= ; //bit * 2

     }

 }

 /*

  *name: convert_ip_binary

  *

  *param:

  * ip:orign ip string; binary_str:dest binary string

  *

  *return:

  * void

  */

 void convert_ip_binary(char ip[],char binary_str[])

 {

     if(ip == NULL || binary_str == NULL)

     {

         return;

     }

     /*为确保正确性在进行转换之前可以进一步进行IP格式校验*/

     char *ip_sub = NULL;

     int i,index =;

     ip_sub = strtok(ip,SPLIT_SIGN); //slit ip by .

     itobinary(atoi(ip_sub),binary_str,index);

     for(i = ; i < ; i++)

     {//need to ip legal detect to pretend error

         ip_sub = strtok(NULL,SPLIT_SIGN);

         index += ;

         itobinary(atoi(ip_sub),binary_str,index);

     }

 }

 /*

  *name: create_iptrie_node

  *

  *return:

  * new ip trie node

  */

 ip_trie_node *create_iptrie_node()

 {

     ip_trie_node *node = (ip_trie_node *)calloc(,sizeof(ip_trie_node));

     if(node == NULL)

     {

         perror("create ip trie node error -- calloc");

     }

     else

     {

         node->child[] = NULL;

         node->child[] = NULL;

     }

     return node;

 }

 /*

  *name: insert_iptrie_node

  *

  *param:

  * root: trie root; ip: orignal ip string

  *

  *return:

  * void

  *

  *notice:

  * this function call strtok it will change input ip

  * so if input ip need to use at other position

  * you shold input a copy of ip

  */

 void insert_iptrie_node(ip_trie_node *root,char ip[])

 {

     if(root == NULL)

     {

         printf("trie have not init\n");

         return;

     }

     if(ip == NULL)

     {

         return;

     }

     char binary_str[IP_BINARY_LEN + ];

     int i,child_index;

     memset(binary_str,,IP_BINARY_LEN + );

     convert_ip_binary(ip,binary_str); //to binary string

     for(i = ; i < IP_BINARY_LEN; i++)

     {

         child_index = binary_str[i] - ''; //child is 0 or 1

         if(root->child[child_index] == NULL)

         {

             root->child[child_index] = create_iptrie_node();

         }

         root = root->child[child_index];

     }

 }

 /*

  *name: select_iptrie_node

  *

  *param:

  * root: trie root; ip: orignal ip string

  *

  *return:

  * 0 :not find; 1:find

  *

  *notice:

  * this function call strtok it will change input ip

  * so if input ip need to use at other position

  * you shold input a copy of ip

  */

 int select_iptrie_node(ip_trie_node *root,char ip[])

 {

     if(root == NULL)

     {

         printf("trie have not init\n");

         return ;

     }

     if(ip == NULL)

     {

         return ;

     }

     int i;

     char binary_str[IP_BINARY_LEN + ];

     memset(binary_str,,IP_BINARY_LEN + );

     convert_ip_binary(ip,binary_str); //to binary string

     int child_index;

     for(i = ; i < IP_BINARY_LEN; i++)

     {

         child_index = binary_str[i] - '';

         if(root->child[child_index] == NULL)

         {

             return ;

         }

         root = root->child[child_index];

     }

     return ;

 }

3.main.c如下(测试程序)

 #include <stdio.h>

 #include <stdlib.h>

 #include "iptrie.h"

 int main()

 {

     char sip[];

     char dip[];

     int i = ;

     int isfind = ;

     ip_trie_node *root = create_iptrie_node();

     while()

     {

         printf("insert a ip:\n");

         scanf("%s",sip);

         insert_iptrie_node(root,sip);

         printf("query a ip:\n");

         scanf("%s",dip);

         isfind = select_iptrie_node(root,dip);

         if(isfind == )

         {

             printf("find\n");

         }

         else

         {

             printf("not find\n");

         }

     }

 }

4.Makefile (linux下编译)

CC = gcc

CFLAG = -g

INC = -I./

target:Iptrie

Iptrie:iptrie.o main.c

    $(CC) $(CFLAG) $(INC) -o $@  $^

iptrie.o:iptrie.c

    $(CC) -c $<

clean:

    rm *.o Iptrie

巴特西

IP trie树接口

最新文章

热门文章