Logo Search packages:      
Sourcecode: aggregate version File versions

cidr_net_list.c

/**********************************************************************
 * cidr_net_list.c                                           March 2001
 * Horms                                             horms@verge.net.au
 *
 * aggregate
 * CIDR network aggregation and filtering
 * Copyright (C) 1999-2002  Horms
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
 * 02111-1307  USA
 *
 **********************************************************************/


#include "cidr_net_list.h"
#include "log.h"
#include <stdlib.h>
#include <errno.h>


/**********************************************************************
 * cidr_net_list_create
 * Create a new, empty list
 * pre: norecent: number of elements for recent list.
 *                If negative DEFAULT_NORECENT is used
 * post: list structure is alocated, and values initialised to NULL
 * return: pointer to list
 *         NULL on error
 **********************************************************************/

cidr_net_list_t *cidr_net_list_create(int norecent){
  cidr_net_list_t *l;
  size_t i;

  extern int errno;

  if((l=(cidr_net_list_t *)malloc(sizeof(cidr_net_list_t)))==NULL){
    AGGREGATE_DEBUG_ERRNO("cidr_net_list_create: malloc 1", errno);
    return(NULL);
  }

  l->norecent=(size_t)((norecent<0)?DEFAULT_NORECENT:norecent);
  if(norecent==0){
    l->recent=NULL;
  }
  else{
    if((l->recent=(cidr_net_list_elem_t **)malloc(
      sizeof(cidr_net_list_elem_t *)*l->norecent
    ))==NULL){
      AGGREGATE_DEBUG_ERRNO("cidr_net_list_create: malloc 2", errno);
      free(l);
      return(NULL);
    }
    for(i=0;i<l->norecent;i++){
      *(l->recent+i)=NULL;
    }
  }
    
  l->recent_offset=0;
  l->first=NULL;
  l->last=NULL;

  return(l);
}


/**********************************************************************
 * cidr_net_list_destroy
 * Destroy a list and all the data contained in the list
 * pre: l: list
 * post: all elements of l are destroyed
 **********************************************************************/

void cidr_net_list_destroy(cidr_net_list_t *l){
  cidr_net_list_elem_t *next;

  if(l==NULL){
    return;
  }

  while(l->first!=NULL){
    next=l->first->next;
    cidr_net_list_elem_destroy(l->first);
    l->first=next;
  }

  free(l);
  return;
}


/**********************************************************************
 * cidr_net_list_display
 * Print to stdout  all the elements in a list, in the order they are 
 * stored elemetns are printed as per cidr_net_display()
 * pre: l: list to display
 *      minimim_prefix: Don't display networks with a prefix less than
 *                      this value. Valid values 0-32. 
 *                      -1 for no mimimium prefix.
 *      maximim_prefix: Don't display networks with a prefix greater than
 *                      this value. Valid values 0-32. 
 *                      -1 for no maximium prefix.
 *      flag: passed tp cidr_net_display
 * post: networks in list displayed to stdout
 **********************************************************************/

int cidr_net_list_display(
  cidr_net_list_t *l, 
  prefix_t minimum_prefix,
  prefix_t maximum_prefix,
  cidr_flag_t flag
){
  cidr_net_list_elem_t *e;
  char *str;

  extern int errno;

  if(l==NULL){ return(-1); }
  if((e=l->first)==NULL){ return(-1); }
  do{
    if((str=cidr_net_to_a(e->net, minimum_prefix, maximum_prefix, flag))==NULL){
      AGGREGATE_DEBUG_ERRNO("cidr_net_list_to_a: cidr_net_display", errno);
      return(-1);
    }
    if(*str != '\0') {
      printf("%s\n", str);
    }
    e=e->next;
  }while(e!=NULL);

  return(0);
}
  

/**********************************************************************
 * cidr_net_list_insert
 * Insert element into a list
 * pre: l: list to insert value into
 *      n: network to insert
 * post: network is inserted into the list in order
 *       NULL if l is NULL
 *       l, unchanged if n is null
 **********************************************************************/

cidr_net_list_t *cidr_net_list_insert(cidr_net_list_t *l, cidr_net_t *n){
  cidr_net_list_elem_t *e;
  cidr_net_list_elem_t *current;
  cidr_net_list_elem_t *next;
  cidr_net_list_elem_t *prev;
  size_t i;
  int direction;
  int new_direction;
  int skips=0;

  extern int errno;

  e=NULL;
  if(l==NULL||n==NULL){ return(l); }

  if(
    cidr_net_distance(n, (l->last==NULL)?NULL:l->last->net) <
    cidr_net_distance(n, (l->first==NULL)?NULL:l->first->net)
  ){
    current=l->last;
  }
  else{
    current=l->first;
  }
  for(i=0;i<l->norecent;i++){
    if(
      cidr_net_distance(n, (*(l->recent+i)==NULL)?NULL:(*(l->recent+i))->net) <
      cidr_net_distance(n, (current==NULL)?NULL:current->net)
    ){
      current=*(l->recent+i);
    }
  }
  direction=0;
  new_direction=0;
  while(current!=NULL){
    skips++;
    if(current->net->address>n->address){
      current=current->prev;
      new_direction=-1;
    }
    else if(current->net->address<n->address){
      current=current->next;
      new_direction=1;
    }
    else if(current->net->address==n->address){
      direction=0;
      break;
    }
    if(direction+new_direction==0){
      break;
    }
    direction=new_direction;
  }

  next=NULL;
  prev=NULL;
  if(current==NULL){
    switch(direction){
      case -1:
        next=l->first;
        break;
      case 1:
        prev=l->last;
        break;
    }
  }
  else{
    switch(direction){
      case -1:
        next=current;
        prev=current->prev;
        break;
      case 1:
        next=current->next;
        prev=current;
        break;
      default:
        /*If the network addresses are the same*/
        /*Take network with smallest prefix, discard the other network*/
        if(n->prefix<current->net->prefix){
          cidr_net_assign(current->net, n->address, n->prefix);
        }
        cidr_net_destroy(n);
        return(l);
      break;
    }
  }

  if((e=cidr_net_list_elem_create(prev, next, n))==NULL){
    AGGREGATE_DEBUG_ERRNO(
      "cidr_net_list_insert: cidr_net_list_elem_create", 
      errno
    );
    cidr_net_list_destroy(l);
    return(NULL);
  }
  if(next!=NULL){ next->prev=e; }
  if(prev!=NULL){ prev->next=e; }
  if(l->first==NULL||(current==NULL&&direction==-1)){ l->first=e; }
  if(l->last==NULL||(current==NULL&&direction==1)){ l->last=e; }
  l->recent_offset=(l->recent_offset+1)%l->norecent;
  *(l->recent+l->recent_offset)=e;

  return(l);
}


/**********************************************************************
 * cidr_net_list_elem_remove
 * remove an element from a list
 * pre: l: list to remove elment from
 *      e: element to remove
 * post: element is removed from list
 *       If this was the last element of the list then l->recent is
 *       set to the previous (now last) elemet of the list.
 *       Otherwise l->recent is set to the next element in the list
 *       No change is made to the list if l or e are NULL
 * return: l
 *         NULL if l or e are NULL
 **********************************************************************/

cidr_net_list_t *cidr_net_list_elem_remove(
  cidr_net_list_t *l,
  cidr_net_list_elem_t *e
){
  size_t i;

  if(l==NULL||e==NULL){ return(NULL); }
  for(i=0;i<l->norecent;i++){
     if(*(l->recent+i)==e){
        *(l->recent+i)=NULL;
    }
  }

  l->recent_offset=(l->recent_offset+1)%l->norecent;
  if(e->prev!=NULL){ 
    e->prev->next=e->next;
    *(l->recent+l->recent_offset)=e->prev;
  }
  if(e->next!=NULL){ 
    e->next->prev=e->prev; 
    *(l->recent+l->recent_offset)=e->next;
  }
  if(l->first==e){ l->first=e->next; }
  if(l->last==e){ l->last=e->prev; }

  return(l);
}


/**********************************************************************
 * cidr_net_list_insert_raw
 * Insert raw network and prefix information into a list
 * Puts this data into a cidr_net structure and then inserts
 * this structure into the list, as per cidr_net_list_insert
 * pre: l: list to add network to
 *      a: base address of network
 *      p: prefix of network
 **********************************************************************/

cidr_net_list_t *cidr_net_list_insert_raw(
  cidr_net_list_t *l, 
  ip_address_t a,
  prefix_t p
){
  cidr_net_t *n;

  extern int errno;

  n=NULL;
  if((n=cidr_net_create(a, p))==NULL){
    AGGREGATE_DEBUG("cidr_net_list_insert_raw: cidr_net_create");
    return(l);
  }
  if((l=cidr_net_list_insert(l, n))==NULL){
    AGGREGATE_DEBUG("cidr_net_list_insert_raw: cidr_net_list_insert");
    cidr_net_list_destroy(l);
    return(NULL);
  }

  return(l);
}


/**********************************************************************
 * cidr_net_list_elem_create
 * Create a new element, and seed it
 * pre: prev: previous element in list
 *      next: next element in list
 *      net: net to store
 * post: e is initialised and values are seeded
 * return: pointer to e
 *         NULL on error
 **********************************************************************/

cidr_net_list_elem_t *cidr_net_list_elem_create(
  cidr_net_list_elem_t *prev,
  cidr_net_list_elem_t *next,
  cidr_net_t *net
){
  cidr_net_list_elem_t *e;

  extern int errno;

  if((e=(cidr_net_list_elem_t *)malloc(sizeof(cidr_net_list_elem_t)))==NULL){
    AGGREGATE_DEBUG_ERRNO("new_cidr_list_elem", errno);
    return(NULL);
  }
  e=cidr_net_list_elem_assign(e, prev, next, net);
  
  return(e);
}


/**********************************************************************
 * cidr_net_list_elem_create_empty
 * Create a new element, and seed it with NULL values
 * pre: none
 * post: e is initialised and values are seeded with NULL
 * return: pointer to e
 *         NULL on error
 **********************************************************************/

cidr_net_list_elem_t *cidr_net_list_elem_create_empty(void){
  return(cidr_net_list_elem_create(NULL, NULL, NULL));
}


/**********************************************************************
 * cidr_net_list_elem_assign
 * Assign values to a list element
 * pre: e: alocated pointer to elelemt to seed
 *      prev: previous element in list
 *      next: next element in list
 *      net: network to store in element
 * post: values are assigned to e
 * return: pointer to e
 *         NULL if e was NULL
 **********************************************************************/

cidr_net_list_elem_t *cidr_net_list_elem_assign(
  cidr_net_list_elem_t *e,
  cidr_net_list_elem_t *prev,
  cidr_net_list_elem_t *next,
  cidr_net_t *net
){
  if(e==NULL){ return(NULL); }
  e->next=next;
  e->prev=prev;
  e->net=net;
 
  return(e);
}


/**********************************************************************
 * cidr_net_list_elem_unassign
 * Assign NULL values to a list element.
 * As the name suggets this can be used to unasign values, possibly
 * so you can destroy the list element without freeing its contents.
 * pre: e: alocated pointer to elelemt to seed
 * post: values are assigned to e
 * return: pointer to e
 *         NULL if e was NULL
 **********************************************************************/

cidr_net_list_elem_t *cidr_net_list_elem_unassign(cidr_net_list_elem_t *e){
  return(cidr_net_list_elem_assign(e, NULL, NULL, NULL));
}


/**********************************************************************
 * cidr_net_list_elem_destroy
 * Assign values to a list element
 * pre: e: pointer to elelemt to destroy
 * post: e and values in e are dstroyed
 *       nothing if e is NULL
 **********************************************************************/

void cidr_net_list_elem_destroy(cidr_net_list_elem_t *e){
  if(e==NULL){ return; }
  cidr_net_destroy(e->net);
  free(e);
} 


/**********************************************************************
 * cidr_net_list_aggregate
 * Aggregate networks - join adjacent small networks to form larger networks
 * Resulting list will contain as few networks as possible
 * pre: l: list of networks to aggregate
 * post: l contains as few networks as possible
 * return: l
 **********************************************************************/

cidr_net_list_t *cidr_net_list_aggregate(cidr_net_list_t *l){
  cidr_net_list_elem_t *current;
  cidr_net_list_elem_t *next;

  if(l==NULL || l->first==NULL || l->first->next==NULL ){ return(NULL); }
  current=l->first;
  next=current->next;
 
  while(next!=NULL){
    if(
      current->net->top_address+1==next->net->address && 
      current->net->prefix==next->net->prefix && 
      cidr_prefix(current->net->address)<current->net->prefix
    ){
      cidr_net_list_elem_remove(l, next);
      cidr_net_list_elem_destroy(next);
      cidr_net_assign(
        current->net,
        current->net->address,
        current->net->prefix-1
      );
      if(current->prev!=NULL){
        next=current;
        current=current->prev;
     }
     else {
       next=current->next;
     }
     continue;
    }
    current=next;
    next=current->next;
  }

  return(l);
}
    

/**********************************************************************
 * cidr_net_list_assimilate
 * If a network is contrained in another network remove it
 * pre: l: list of networks
 * post: networks inside of networks are removed
 **********************************************************************/

cidr_net_list_t *cidr_net_list_assimilate(cidr_net_list_t *l){
  cidr_net_list_elem_t *current;
  cidr_net_list_elem_t *next;

  if(l==NULL || l->first==NULL || l->first->next==NULL ){ return(NULL); }
  current=l->first;
  next=current->next;
  
  while(next!=NULL){
    if(current->net->top_address>=next->net->top_address){
      cidr_net_list_elem_remove(l, next);
      cidr_net_list_elem_destroy(next); 
    }
    else{
      current=next;
    }
    next=current->next;
  }

  return(l);
}


/**********************************************************************
 * cidr_net_list_range
 * Insert a range of addresses, broken down into cidr networks into
 * a list of cidr networks
 * pre: ip1: first ip in range
 *      ip2: last ip in range
 * post: list of cidr networks 
 *       NULL list on error
 **********************************************************************/

cidr_net_list_t *cidr_net_list_insert_range(
  ip_address_t ip1, 
  ip_address_t ip2, 
  cidr_net_list_t *l
){
  ip_address_t difference;
  ip_address_t remove;
  prefix_t ip1_prefix; 
  prefix_t difference_prefix; 
  prefix_t use_prefix;
  cidr_net_t *net;

  extern unsigned int cidr_pow_2_lookup[];
  extern int errno;

  if(ip2<ip1){ return(NULL); }

  net=NULL;
  if((difference=ip2-ip1)==0){
    if((l=cidr_net_list_insert_raw(l, ip1, (prefix_t)32))==NULL){
      AGGREGATE_DEBUG_ERRNO("cidr_net_list_range: cidr_net_list_insert", errno);
      return(NULL);
    }
    return(l);
  }
  if(ip1==0 && ip2==0xffffffff){
    if((l=cidr_net_list_insert_raw(l, 0, 0))==NULL){
      AGGREGATE_DEBUG_ERRNO("cidr_net_list_range: cidr_net_list_insert", errno);
      return(NULL);
    }
    return(l);
  }

  while(ip1 <= ip2){
    ip1_prefix=cidr_prefix(ip1);
    difference_prefix=(prefix_t)(IP_BITS-cidr_log_2(difference+1));

    use_prefix=(difference_prefix>ip1_prefix)?difference_prefix:ip1_prefix;

    if((l=cidr_net_list_insert_raw(l, ip1, use_prefix))==NULL){
      AGGREGATE_DEBUG_ERRNO("cidr_net_list_range: cidr_net_list_insert", errno);
      return(NULL);
    }

    ip1+=cidr_pow_2_lookup[IP_BITS-use_prefix];
    difference-=(difference<(remove=cidr_pow_2_lookup[IP_BITS-use_prefix]))?
      difference:remove;
  }

  return(l);
}

Generated by  Doxygen 1.6.0   Back to index