#include<stdio.h>
#include<stdlib.h>
struct prefix {
   unsigned int IP ;
   unsigned char len ;
  struct prefix *next ;
 };
typedef struct prefix Prefix ;
int cal(int d){
   int i , sum ;
   sum = 2 ;
   for( i = 0 ; i < d-1 ; i++)
     sum = sum * 2 ;
      return sum+1 ; }

Prefix *insert_a_node(Prefix *head,Prefix *node ){
    Prefix *cur ;
      cur = head ;
    if(head == NULL)
        return node ;
    if( node == NULL )
       return head ;
    if( node->IP < head->IP)
      { node->next = head ;
          return node ;  }
    while( cur->next != NULL && cur->next->IP <= node->IP)
        cur = cur->next ;
       node->next = cur->next ;
       cur->next = node ;
      return head ;
                       }

void insert_prefix(Prefix *group_head,Prefix *node,int index){
  int i = 0;
  Prefix *t;

  if(node == NULL) return;
  if(group_head->next == NULL)
        {
         group_head->next=node;
         t = group_head;
         return ;
        }
  if(node->IP <= group_head->next->IP)
        {
        node->next = group_head->next ;
        group_head->next=node;
        return ;
        }
 t = group_head->next ;
 if(t->next==NULL)
   {  t->next=node;
      return;}
  while(t->next!=NULL && t->next->IP < node->IP)
        t=t->next;
    node->next=t->next;
    t->next=node;
    return;
}
Prefix *build_list_no_order(Prefix *head,Prefix *node){

     if (head == NULL)
         return node ;
     if (node == NULL)
        return head ;
   Prefix *cur ;
     cur = head ;
   while ( cur->next != NULL)
    cur = cur->next ;
    cur->next = node ;
  return head ;

 }

Prefix *build_routing_table(){
    int a[5],i ;
   int ip = 0 ;
  Prefix *head ;
      head =  NULL ;
 FILE *ofp ;
 ofp = fopen("routing_table","r") ;
 while( fscanf(ofp,"%d.%d.%d.%d/%d",&a[0],&a[1],&a[2],&a[3],&a[4]) != EOF){
       Prefix *node = (Prefix*)malloc(sizeof(Prefix)) ;
   for ( i =0 ; i < 4 ; i++)
   {  ip = ip + a[i] ;
    if ( i != 3 )
      ip = ip<<8 ;  }
        node->IP = ip ;
        ip = 0 ;
        node->len=a[4];
      head = build_list_no_order(head,node);  }
    return head ;

    }

void segment(int d,Prefix *rout ,Prefix group[]){
   int index=0,i;

   for(i=31 ; i>31-d ; i--){
    if(rout->len<d)
         index=cal(d)-1;
    if( ( rout->IP & 1<<i ) && ( i!=32-d))
        {index++;
        index=index<<1;}
    if( (rout->IP & 1<<i) && i==32-d)
        index++;
    if( !(rout->IP & 1<<i) && i!=32-d)
        index=index<<1;
      }
   insert_prefix(&group[index],rout,index);

   }
int main ( int argc , char *argv[]){
  Prefix *head ;
  Prefix *routing_head;
  Prefix *trace_head;
  Prefix *temp_rout ;
  int d = 2 ; //need use argc finally
  int group_num;
  group_num = cal(d);
  Prefix group[group_num] ;
  trace_head = build_trace();
  routing_head = build_routing_table();

 while(routing_head != NULL ){
  segment(d,routing_head,group);
  routing_head = routing_head->next;
  }

     return 0 ;
}