src/surf/surf_routing.c

   1 /* Copyright (c) 2009, 2010. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 #include <float.h>
   8 #include <pcre.h> /* regular expresion library */
   9 #include "surf_private.h"
  10 #include "xbt/dynar.h"
  11 #include "xbt/str.h"
  12 #include "xbt/config.h"
  13 #include "xbt/graph.h"
  14 #include "xbt/set.h"
  15
  16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf");
  17
  18 /* Global vars */
  19 routing_global_t global_routing = NULL;
  20 routing_component_t current_routing = NULL;
  21 model_type_t current_routing_model = NULL;
  22
  23 /* Prototypes of each model */
  24 static void* model_full_create(void); /* create structures for full routing model */
  25 static void  model_full_load(void);   /* load parse functions for full routing model */
  26 static void  model_full_unload(void); /* unload parse functions for full routing model */
  27 static void  model_full_end(void);    /* finalize the creation of full routing model */
  28
  29 static void* model_floyd_create(void); /* create structures for floyd routing model */
  30 static void  model_floyd_load(void);   /* load parse functions for floyd routing model */
  31 static void  model_floyd_unload(void); /* unload parse functions for floyd routing model */
  32 static void  model_floyd_end(void);    /* finalize the creation of floyd routing model */
  33
  34 static void* model_dijkstra_both_create(int cached); /* create by calling dijkstra or dijkstracache */
  35 static void* model_dijkstra_create(void);      /* create structures for dijkstra routing model */
  36 static void* model_dijkstracache_create(void); /* create structures for dijkstracache routing model */
  37 static void  model_dijkstra_both_load(void);   /* load parse functions for dijkstra routing model */
  38 static void  model_dijkstra_both_unload(void); /* unload parse functions for dijkstra routing model */
  39 static void  model_dijkstra_both_end(void);    /* finalize the creation of dijkstra routing model */
  40
  41 static void* model_rulebased_create(void); /* create structures for rulebased routing model */
  42 static void  model_rulebased_load(void);   /* load parse functions for rulebased routing model */
  43 static void  model_rulebased_unload(void); /* unload parse functions for rulebased routing model */
  44 static void  model_rulebased_end(void);    /* finalize the creation of rulebased routing model */
  45
  46 static void* model_none_create(void); /* none routing model */
  47 static void  model_none_load(void);   /* none routing model */
  48 static void  model_none_unload(void); /* none routing model */
  49 static void  model_none_end(void);    /* none routing model */
  50
  51 /* this lines are olny for replace use like index in the model table */
  52 #define SURF_MODEL_FULL           0
  53 #define SURF_MODEL_FLOYD          1
  54 #define SURF_MODEL_DIJKSTRA       2
  55 #define SURF_MODEL_DIJKSTRACACHE  3
  56 #define SURF_MODEL_RULEBASED      4
  57 #define SURF_MODEL_NONE           5
  58
  59 /* must be finish with null and carefull if change de order */
  60 struct s_model_type routing_models[] =
  61 { {"Full", "Full routing data (fast, large memory requirements, fully expressive)",
  62   model_full_create, model_full_load, model_full_unload, model_full_end },
  63   {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)",
  64   model_floyd_create, model_floyd_load, model_floyd_unload, model_floyd_end },
  65   {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)",
  66   model_dijkstra_create ,model_dijkstra_both_load, model_dijkstra_both_unload, model_dijkstra_both_end },
  67   {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)",
  68   model_dijkstracache_create, model_dijkstra_both_load, model_dijkstra_both_unload, model_dijkstra_both_end },
  69   {"RuleBased", "Rule-Based routing data (...)",
  70   model_rulebased_create, model_rulebased_load, model_rulebased_unload, model_rulebased_end },
  71   {"none", "No routing (usable with Constant network only)",
  72   model_none_create, model_none_load, model_none_unload, model_none_end },
  73   {NULL,NULL,NULL,NULL,NULL,NULL}};
  74
  75 /* ************************************************************************** */
  76 /* ***************** GENERIC PARSE FUNCTIONS (declarations) ***************** */
  77
  78 static void generic_set_processing_unit(routing_component_t rc, const char* name);
  79 static void generic_set_autonomous_system(routing_component_t rc, const char* name);
  80 static void generic_set_route(routing_component_t rc, const char* src, const char* dst, route_t route);
  81 static void generic_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route);
  82 static void generic_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route);
  83
  84 /* ************************************************************************** */
  85 /* *************** GENERIC BUSINESS METHODS (declarations) ****************** */
  86
  87 static route_extended_t generic_get_bypassroute(routing_component_t rc, const char* src, const char* dst);
  88
  89 /* ************************************************************************** */
  90 /* ****************** GENERIC AUX FUNCTIONS (declarations) ****************** */
  91
  92 static route_extended_t generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy, void* data, int order);
  93 static void generic_free_route(route_t route);
  94 static void generic_free_extended_route(route_extended_t e_route);
  95 static routing_component_t generic_autonomous_system_exist(routing_component_t rc, char* element);
  96 static routing_component_t generic_processing_units_exist(routing_component_t rc, char* element);
  97 static void generic_src_dst_check(routing_component_t rc, const char* src, const char* dst);
  98
  99 /* ************************************************************************** */
 100 /* **************************** GLOBAL FUNCTIONS **************************** */
 101
 102 /* global parse functions */
 103 static char* src = NULL;    /* temporary store the source name of a route */
 104 static char* dst = NULL;    /* temporary store the destination name of a route */
 105 static char* gw_src = NULL; /* temporary store the gateway source name of a route */
 106 static char* gw_dst = NULL; /* temporary store the gateway destination name of a route */
 107 static xbt_dynar_t link_list = NULL; /* temporary store of current list link of a route */
 108
 109 /**
 110  * \brief Add a "host" to the network element list
 111  */
 112 static void  parse_S_host(void) {
 113   if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_BASE;
 114   xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,A_surfxml_host_id),
 115       "Reading a host, processing unit \"%s\" already exist",A_surfxml_host_id);
 116   xbt_assert1(current_routing->set_processing_unit,
 117       "no defined method \"set_processing_unit\" in \"%s\"",current_routing->name);
 118   (*(current_routing->set_processing_unit))(current_routing,A_surfxml_host_id);
 119   xbt_dict_set(global_routing->where_network_elements,A_surfxml_host_id,(void*)current_routing,NULL);
 120 }
 121
 122 /**
 123  * \brief Add a "router" to the network element list
 124  */
 125 static void parse_S_router(void) {
 126   if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_BASE;
 127   xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,A_surfxml_router_id),
 128       "Reading a router, processing unit \"%s\" already exist",A_surfxml_router_id);
 129   xbt_assert1(current_routing->set_processing_unit,
 130       "no defined method \"set_processing_unit\" in \"%s\"",current_routing->name);
 131   (*(current_routing->set_processing_unit))(current_routing,A_surfxml_router_id);
 132   xbt_dict_set(global_routing->where_network_elements,A_surfxml_router_id,(void*)current_routing,NULL);
 133 }
 134
 135 /**
 136  * \brief Set the endponints for a route
 137  */
 138 static void parse_S_route_new_and_endpoints(void) {
 139   if( src != NULL && dst != NULL && link_list != NULL )
 140     THROW2(arg_error,0,"Route between %s to %s can not be defined",A_surfxml_route_src,A_surfxml_route_dst);
 141   src = A_surfxml_route_src;
 142   dst = A_surfxml_route_dst;
 143   xbt_assert2(strlen(src)>0||strlen(dst)>0,
 144       "Some limits are null in the route between \"%s\" and \"%s\"",src,dst);
 145   link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 146 }
 147
 148 /**
 149  * \brief Set the endponints and gateways for a ASroute
 150  */
 151 static void parse_S_ASroute_new_and_endpoints(void) {
 152   if( src != NULL && dst != NULL && link_list != NULL )
 153     THROW2(arg_error,0,"Route between %s to %s can not be defined",A_surfxml_ASroute_src,A_surfxml_ASroute_dst);
 154   src = A_surfxml_ASroute_src;
 155   dst = A_surfxml_ASroute_dst;
 156   gw_src = A_surfxml_ASroute_gw_src;
 157   gw_dst = A_surfxml_ASroute_gw_dst;
 158   xbt_assert2(strlen(src)>0||strlen(dst)>0||strlen(gw_src)>0||strlen(gw_dst)>0,
 159       "Some limits are null in the route between \"%s\" and \"%s\"",src,dst);
 160   link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 161 }
 162
 163 /**
 164  * \brief Set the endponints for a bypassRoute
 165  */
 166 static void parse_S_bypassRoute_new_and_endpoints(void) {
 167   if( src != NULL && dst != NULL && link_list != NULL )
 168     THROW2(arg_error,0,"Bypass Route between %s to %s can not be defined",A_surfxml_bypassRoute_src,A_surfxml_bypassRoute_dst);
 169   src = A_surfxml_bypassRoute_src;
 170   dst = A_surfxml_bypassRoute_dst;
 171   gw_src = A_surfxml_bypassRoute_gw_src;
 172   gw_dst = A_surfxml_bypassRoute_gw_dst;
 173   xbt_assert2(strlen(src)>0||strlen(dst)>0||strlen(gw_src)>0||strlen(gw_dst)>0,
 174       "Some limits are null in the route between \"%s\" and \"%s\"",src,dst);
 175   link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 176 }
 177
 178 /**
 179  * \brief Set a new link on the actual list of link for a route or ASroute
 180  */
 181 static void parse_E_link_c_ctn_new_elem(void) {
 182   char *val;
 183   val = xbt_strdup(A_surfxml_link_c_ctn_id);
 184   xbt_dynar_push(link_list, &val);
 185 }
 186
 187 /**
 188  * \brief Store the route by calling the set_route function of the current routing component
 189  */
 190 static void parse_E_route_store_route(void) {
 191   route_t route = xbt_new0(s_route_t,1);
 192   route->link_list = link_list;
 193 //   xbt_assert1(generic_processing_units_exist(current_routing,src),"the \"%s\" processing units gateway does not exist",src);
 194 //   xbt_assert1(generic_processing_units_exist(current_routing,dst),"the \"%s\" processing units gateway does not exist",dst);
 195     xbt_assert1(current_routing->set_route,"no defined method \"set_route\" in \"%s\"",current_routing->name);
 196   (*(current_routing->set_route))(current_routing,src,dst,route);
 197   link_list = NULL;
 198   src = NULL;
 199   dst = NULL;
 200 }
 201
 202 /**
 203  * \brief Store the ASroute by calling the set_ASroute function of the current routing component
 204  */
 205 static void parse_E_ASroute_store_route(void) {
 206   route_extended_t e_route = xbt_new0(s_route_extended_t,1);
 207   e_route->generic_route.link_list = link_list;
 208   e_route->src_gateway = xbt_strdup(gw_src);
 209   e_route->dst_gateway = xbt_strdup(gw_dst);
 210 //   xbt_assert1(generic_autonomous_system_exist(current_routing,src),"the \"%s\" autonomous system does not exist",src);
 211 //   xbt_assert1(generic_autonomous_system_exist(current_routing,dst),"the \"%s\" autonomous system does not exist",dst);
 212 //   xbt_assert1(generic_processing_units_exist(current_routing,gw_src),"the \"%s\" processing units gateway does not exist",gw_src);
 213 //   xbt_assert1(generic_processing_units_exist(current_routing,gw_dst),"the \"%s\" processing units gateway does not exist",gw_dst);
 214   xbt_assert1(current_routing->set_ASroute,"no defined method \"set_ASroute\" in \"%s\"",current_routing->name);
 215   (*(current_routing->set_ASroute))(current_routing,src,dst,e_route);
 216   link_list = NULL;
 217   src = NULL;
 218   dst = NULL;
 219   gw_src = NULL;
 220   gw_dst = NULL;
 221 }
 222
 223 /**
 224  * \brief Store the bypass route by calling the set_bypassroute function of the current routing component
 225  */
 226 static void parse_E_bypassRoute_store_route(void) {
 227   route_extended_t e_route = xbt_new0(s_route_extended_t,1);
 228   e_route->generic_route.link_list = link_list;
 229   e_route->src_gateway = xbt_strdup(gw_src);
 230   e_route->dst_gateway = xbt_strdup(gw_dst);
 231 //   xbt_assert1(generic_autonomous_system_exist(current_routing,src),"the \"%s\" autonomous system does not exist",src);
 232 //   xbt_assert1(generic_autonomous_system_exist(current_routing,dst),"the \"%s\" autonomous system does not exist",dst);
 233 //   xbt_assert1(generic_processing_units_exist(current_routing,gw_src),"the \"%s\" processing units gateway does not exist",gw_src);
 234 //   xbt_assert1(generic_processing_units_exist(current_routing,gw_dst),"the \"%s\" processing units gateway does not exist",gw_dst);
 235   xbt_assert1(current_routing->set_bypassroute,"no defined method \"set_bypassroute\" in \"%s\"",current_routing->name);
 236   (*(current_routing->set_bypassroute))(current_routing,src,dst,e_route);
 237   link_list = NULL;
 238   src = NULL;
 239   dst = NULL;
 240   gw_src = NULL;
 241   gw_dst = NULL;
 242 }
 243
 244 /**
 245  * \brief Make a new routing component
 246  *
 247  * Detect the routing model type of the routing component, make the new structure and
 248  * set the parsing functions to allows parsing the part of the routing tree
 249  */
 250 static void parse_S_AS(void) {
 251   routing_component_t new_routing;
 252   model_type_t model = NULL;
 253   char* wanted = A_surfxml_AS_routing;
 254   int cpt;
 255   /* seach the routing model */
 256   for (cpt=0;routing_models[cpt].name;cpt++)
 257     if (!strcmp(wanted,routing_models[cpt].name))
 258           model = &routing_models[cpt];
 259   /* if its not exist, error */
 260   if( model == NULL ) {
 261     fprintf(stderr,"Routing model %s not found. Existing models:\n",wanted);
 262     for (cpt=0;routing_models[cpt].name;cpt++)
 263       if (!strcmp(wanted,routing_models[cpt].name))
 264         fprintf(stderr,"   %s: %s\n",routing_models[cpt].name,routing_models[cpt].desc);
 265     xbt_die(NULL);
 266   }
 267
 268   /* make a new routing component */
 269   new_routing = (routing_component_t)(*(model->create))();
 270   new_routing->routing = model;
 271   new_routing->hierarchy = SURF_ROUTING_NULL;
 272   new_routing->name = xbt_strdup(A_surfxml_AS_id);
 273   new_routing->routing_sons = xbt_dict_new();
 274   //INFO2("Routing %s for AS %s",A_surfxml_AS_routing,A_surfxml_AS_id);
 275
 276   if( current_routing == NULL && global_routing->root == NULL ){
 277
 278     /* it is the first one */
 279     new_routing->routing_father = NULL;
 280     global_routing->root = new_routing;
 281
 282   } else if( current_routing != NULL && global_routing->root != NULL ) {
 283
 284     xbt_assert1(!xbt_dict_get_or_null(current_routing->routing_sons,A_surfxml_AS_id),
 285            "The AS \"%s\" already exist",A_surfxml_AS_id);
 286      /* it is a part of the tree */
 287     new_routing->routing_father = current_routing;
 288     /* set the father behavior */
 289     if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_RECURSIVE;
 290     /* add to the sons dictionary */
 291     xbt_dict_set(current_routing->routing_sons,A_surfxml_AS_id,(void*)new_routing,NULL);
 292     /* add to the father element list */
 293     (*(current_routing->set_autonomous_system))(current_routing,A_surfxml_AS_id);
 294     /* unload the prev parse rules */
 295     (*(current_routing->routing->unload))();
 296
 297   } else {
 298     THROW0(arg_error,0,"All defined components must be belong to a AS");
 299   }
 300   /* set the new parse rules */
 301   (*(new_routing->routing->load))();
 302   /* set the new current component of the tree */
 303   current_routing = new_routing;
 304 }
 305
 306 /**
 307  * \brief Finish the creation of a new routing component
 308  *
 309  * When you finish to read the routing component, other structures must be created.
 310  * the "end" method allow to do that for any routing model type
 311  */
 312 static void parse_E_AS(void) {
 313
 314   if( current_routing == NULL ) {
 315     THROW1(arg_error,0,"Close AS(%s), that never open",A_surfxml_AS_id);
 316   } else {
 317       xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,current_routing->name),
 318           "The AS \"%s\" already exist",current_routing->name);
 319       xbt_dict_set(global_routing->where_network_elements,current_routing->name,current_routing->routing_father,NULL);
 320       (*(current_routing->routing->unload))();
 321       (*(current_routing->routing->end))();
 322       current_routing = current_routing->routing_father;
 323       if( current_routing != NULL )
 324         (*(current_routing->routing->load))();
 325   }
 326 }
 327
 328 /* Aux Business methods */
 329
 330 /**
 331  * \brief Get the AS father and the first elements of the chain
 332  *
 333  * \param src the source host name
 334  * \param dst the destination host name
 335  *
 336  * Get the common father of the to processing units, and the first different
 337  * father in the chain
 338  */
 339 static xbt_dynar_t elements_father(const char* src,const char* dst) {
 340
 341   xbt_assert0(src&&dst,"bad parameters for \"elements_father\" method");
 342
 343   xbt_dynar_t result = xbt_dynar_new(sizeof(char*), NULL);
 344
 345   routing_component_t src_as, dst_as;
 346   int index_src, index_dst, index_father_src, index_father_dst;
 347   xbt_dynar_t path_src = NULL;
 348   xbt_dynar_t path_dst = NULL;
 349   routing_component_t current = NULL;
 350   routing_component_t* current_src = NULL;
 351   routing_component_t* current_dst = NULL;
 352   routing_component_t* father = NULL;
 353
 354   /* (1) find the as where the src and dst are located */
 355   src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
 356   dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
 357   xbt_assert2(src_as&&dst_as, "Ask for route \"from\"(%s) or \"to\"(%s) no found",src,dst);
 358
 359   /* (2) find the path to the root routing component */
 360   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
 361   current = src_as;
 362   while( current != NULL ) {
 363     xbt_dynar_push(path_src,&current);
 364     current = current->routing_father;
 365   }
 366   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
 367   current = dst_as;
 368   while( current != NULL ) {
 369     xbt_dynar_push(path_dst,&current);
 370     current = current->routing_father;
 371   }
 372
 373   /* (3) find the common father */
 374   index_src  = (path_src->used)-1;
 375   index_dst  = (path_dst->used)-1;
 376   current_src = xbt_dynar_get_ptr(path_src,index_src);
 377   current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
 378   while( index_src >= 0 && index_dst >= 0 && *current_src == *current_dst ) {
 379     current_src = xbt_dynar_get_ptr(path_src,index_src);
 380     current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
 381     index_src--;
 382     index_dst--;
 383   }
 384   index_src++;
 385   index_dst++;
 386   current_src = xbt_dynar_get_ptr(path_src,index_src);
 387   current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
 388
 389   /* (4) they are not in the same routing component, make the path */
 390   index_father_src = index_src+1;
 391   index_father_dst = index_dst+1;
 392
 393   if(*current_src==*current_dst)
 394     father = current_src;
 395   else
 396     father = xbt_dynar_get_ptr(path_src,index_father_src);
 397
 398   /* (5) result generation */
 399   xbt_dynar_push(result,father); /* first same the father of src and dst */
 400   xbt_dynar_push(result,current_src); /* second the first different father of src */
 401   xbt_dynar_push(result,current_dst); /* three  the first different father of dst */
 402
 403   xbt_dynar_free(&path_src);
 404   xbt_dynar_free(&path_dst);
 405
 406   return result;
 407 }
 408
 409 /* Global Business methods */
 410
 411 /**
 412  * \brief Recursive function for get_route
 413  *
 414  * \param src the source host name
 415  * \param dst the destination host name
 416  *
 417  * This fuction is call by "get_route". It allow to walk through the
 418  * routing components tree.
 419  */
 420 static route_extended_t _get_route(const char* src,const char* dst) {
 421
 422   void* link;
 423   unsigned int cpt=0;
 424
 425   DEBUG2("Solve route  \"%s\" to \"%s\"",src,dst);
 426
 427   xbt_assert0(src&&dst,"bad parameters for \"_get_route\" method");
 428
 429   route_extended_t e_route, e_route_cnt, e_route_src, e_route_dst;
 430
 431   xbt_dynar_t elem_father_list = elements_father(src,dst);
 432
 433   routing_component_t common_father = xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 434   routing_component_t src_father    = xbt_dynar_get_as(elem_father_list, 1, routing_component_t);
 435   routing_component_t dst_father    = xbt_dynar_get_as(elem_father_list, 2, routing_component_t);
 436
 437   e_route = xbt_new0(s_route_extended_t,1);
 438   e_route->src_gateway = NULL;
 439   e_route->dst_gateway = NULL;
 440   e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 441
 442   if(src_father==dst_father) { /* SURF_ROUTING_BASE */
 443
 444     if( strcmp(src,dst) ){
 445       e_route_cnt = (*(common_father->get_route))(common_father,src,dst);
 446       xbt_assert2(e_route_cnt,"no route between \"%s\" and \"%s\"",src,dst);
 447       xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
 448         xbt_dynar_push(e_route->generic_route.link_list,&link);
 449       }
 450       generic_free_extended_route(e_route_cnt);
 451     }
 452
 453   } else { /* SURF_ROUTING_RECURSIVE */
 454
 455     route_extended_t e_route_bypass = NULL;
 456
 457     if(common_father->get_bypass_route)
 458       e_route_bypass = (*(common_father->get_bypass_route))(common_father,src,dst);
 459
 460     if(e_route_bypass)
 461       e_route_cnt = e_route_bypass;
 462     else
 463       e_route_cnt = (*(common_father->get_route))(common_father,src_father->name,dst_father->name);
 464
 465     xbt_assert2(e_route_cnt,"no route between \"%s\" and \"%s\"",src_father->name,dst_father->name);
 466
 467     xbt_assert2( (e_route_cnt->src_gateway==NULL) == (e_route_cnt->dst_gateway==NULL) ,
 468       "bad gateway for route between \"%s\" and \"%s\"",src,dst);
 469
 470     if( src != e_route_cnt->src_gateway ) {
 471       e_route_src = _get_route(src,e_route_cnt->src_gateway);
 472       xbt_assert2(e_route_src,"no route between \"%s\" and \"%s\"",src,e_route_cnt->src_gateway);
 473       xbt_dynar_foreach(e_route_src->generic_route.link_list, cpt, link) {
 474         xbt_dynar_push(e_route->generic_route.link_list,&link);
 475       }
 476     }
 477
 478     xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
 479       xbt_dynar_push(e_route->generic_route.link_list,&link);
 480     }
 481
 482     if( e_route_cnt->dst_gateway != dst ) {
 483       e_route_dst = _get_route(e_route_cnt->dst_gateway,dst);
 484       xbt_assert2(e_route_dst,"no route between \"%s\" and \"%s\"",e_route_cnt->dst_gateway,dst);
 485       xbt_dynar_foreach(e_route_dst->generic_route.link_list, cpt, link) {
 486         xbt_dynar_push(e_route->generic_route.link_list,&link);
 487       }
 488     }
 489
 490     e_route->src_gateway = xbt_strdup(e_route_cnt->src_gateway);
 491     e_route->dst_gateway = xbt_strdup(e_route_cnt->dst_gateway);
 492
 493     generic_free_extended_route(e_route_src);
 494     generic_free_extended_route(e_route_cnt);
 495     generic_free_extended_route(e_route_dst);
 496   }
 497
 498   xbt_dynar_free(&elem_father_list);
 499
 500   return e_route;
 501 }
 502
 503 /**
 504  * \brief Generic method: find a route between hosts
 505  *
 506  * \param src the source host name
 507  * \param dst the destination host name
 508  *
 509  * walk through the routing components tree and find a route between hosts
 510  * by calling the differents "get_route" functions in each routing component
 511  */
 512 static xbt_dynar_t get_route(const char* src,const char* dst) {
 513
 514   route_extended_t e_route;
 515   xbt_dynar_t elem_father_list = elements_father(src,dst);
 516   routing_component_t common_father = xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 517
 518   if(strcmp(src,dst))
 519     e_route = _get_route(src,dst);
 520   else
 521     e_route = (*(common_father->get_route))(common_father,src,dst);
 522
 523   xbt_assert2(e_route,"no route between \"%s\" and \"%s\"",src,dst);
 524
 525   if(global_routing->last_route) xbt_dynar_free( &(global_routing->last_route) );
 526   global_routing->last_route = e_route->generic_route.link_list;
 527
 528   if(e_route->src_gateway) xbt_free(e_route->src_gateway);
 529   if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
 530
 531   xbt_free(e_route);
 532   xbt_dynar_free(&elem_father_list);
 533
 534   if( xbt_dynar_length(global_routing->last_route)==0 )
 535     return NULL;
 536   else
 537     return global_routing->last_route;
 538 }
 539
 540 /**
 541  * \brief Recursive function for finalize
 542  *
 543  * \param rc the source host name
 544  *
 545  * This fuction is call by "finalize". It allow to finalize the
 546  * AS or routing components. It delete all the structures.
 547  */
 548 static void _finalize(routing_component_t rc) {
 549   if(rc) {
 550     xbt_dict_cursor_t cursor = NULL;
 551     char *key;
 552     routing_component_t elem;
 553     xbt_dict_foreach(rc->routing_sons, cursor, key, elem) {
 554       _finalize(elem);
 555     }
 556     xbt_dict_t tmp_sons = rc->routing_sons;
 557     char* tmp_name = rc->name;
 558     xbt_dict_free(&tmp_sons);
 559     xbt_free(tmp_name);
 560     xbt_assert1(rc->finalize,"no defined method \"finalize\" in \"%s\"",current_routing->name);
 561     (*(rc->finalize))(rc);
 562   }
 563 }
 564
 565 /**
 566  * \brief Generic method: delete all the routing structures
 567  *
 568  * walk through the routing components tree and delete the structures
 569  * by calling the differents "finalize" functions in each routing component
 570  */
 571 static void finalize(void) {
 572   /* delete recursibly all the tree */
 573   _finalize(global_routing->root);
 574   /* delete "where" dict */
 575   xbt_dict_free(&(global_routing->where_network_elements));
 576   /* delete last_route */
 577   xbt_dynar_free(&(global_routing->last_route));
 578   /* delete global routing structure */
 579   xbt_free(global_routing);
 580 }
 581
 582 /**
 583  * \brief Generic method: create the global routing schema
 584  *
 585  * Make a global routing structure and set all the parsing functions.
 586  */
 587 void routing_model_create(size_t size_of_links, void* loopback) {
 588
 589   /* config the uniq global routing */
 590   global_routing = xbt_new0(s_routing_global_t,1);
 591   global_routing->where_network_elements = xbt_dict_new();
 592   global_routing->root = NULL;
 593   global_routing->get_route = get_route;
 594   global_routing->finalize = finalize;
 595   global_routing->loopback = loopback;
 596   global_routing->size_of_link = size_of_links;
 597   global_routing->last_route = xbt_dynar_new(size_of_links, NULL);
 598
 599   /* no current routing at moment */
 600   current_routing = NULL;
 601
 602   /* parse generic elements */
 603   surfxml_add_callback(STag_surfxml_host_cb_list, &parse_S_host);
 604   surfxml_add_callback(STag_surfxml_router_cb_list, &parse_S_router);
 605
 606   surfxml_add_callback(STag_surfxml_route_cb_list, &parse_S_route_new_and_endpoints);
 607   surfxml_add_callback(STag_surfxml_ASroute_cb_list, &parse_S_ASroute_new_and_endpoints);
 608   surfxml_add_callback(STag_surfxml_bypassRoute_cb_list, &parse_S_bypassRoute_new_and_endpoints);
 609
 610   surfxml_add_callback(ETag_surfxml_link_c_ctn_cb_list, &parse_E_link_c_ctn_new_elem);
 611
 612   surfxml_add_callback(ETag_surfxml_route_cb_list, &parse_E_route_store_route);
 613   surfxml_add_callback(ETag_surfxml_ASroute_cb_list, &parse_E_ASroute_store_route);
 614   surfxml_add_callback(ETag_surfxml_bypassRoute_cb_list, &parse_E_bypassRoute_store_route);
 615
 616   surfxml_add_callback(STag_surfxml_AS_cb_list, &parse_S_AS);
 617   surfxml_add_callback(ETag_surfxml_AS_cb_list, &parse_E_AS);
 618
 619 //   /* DEBUG ONLY */
 620 //   surfxml_add_callback(ETag_surfxml_platform_cb_list, &DEBUG_exit);
 621 }
 622
 623 /* ************************************************************************** */
 624 /* *************************** FULL ROUTING ********************************* */
 625
 626 #define TO_ROUTE_FULL(i,j) routing->routing_table[(i)+(j)*table_size]
 627
 628 /* Routing model structure */
 629
 630 typedef struct {
 631   s_routing_component_t generic_routing;
 632   xbt_dict_t parse_routes; /* store data during the parse process */
 633   xbt_dict_t to_index; /* char* -> network_element_t */
 634   xbt_dict_t bypassRoutes;
 635   route_extended_t *routing_table;
 636 } s_routing_component_full_t,*routing_component_full_t;
 637
 638 /* Business methods */
 639
 640 static route_extended_t full_get_route(routing_component_t rc, const char* src,const char* dst) {
 641   xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
 642
 643   /* set utils vars */
 644   routing_component_full_t routing = (routing_component_full_t)rc;
 645   int table_size = xbt_dict_length(routing->to_index);
 646
 647   generic_src_dst_check(rc,src,dst);
 648   int *src_id = xbt_dict_get_or_null(routing->to_index,src);
 649   int *dst_id = xbt_dict_get_or_null(routing->to_index,dst);
 650   xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",src,dst);
 651
 652   route_extended_t e_route = NULL;
 653   route_extended_t new_e_route = NULL;
 654   void* link;
 655   unsigned int cpt=0;
 656
 657   e_route = TO_ROUTE_FULL(*src_id,*dst_id);
 658
 659   if(e_route) {
 660     new_e_route = xbt_new0(s_route_extended_t,1);
 661     new_e_route->src_gateway = xbt_strdup(e_route->src_gateway);
 662     new_e_route->dst_gateway = xbt_strdup(e_route->dst_gateway);
 663     new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 664     xbt_dynar_foreach(e_route->generic_route.link_list, cpt, link) {
 665       xbt_dynar_push(new_e_route->generic_route.link_list,&link);
 666     }
 667   }
 668   return new_e_route;
 669 }
 670
 671 static void full_finalize(routing_component_t rc) {
 672   routing_component_full_t routing = (routing_component_full_t)rc;
 673   int table_size = xbt_dict_length(routing->to_index);
 674   int i,j;
 675   if (routing) {
 676     /* Delete routing table */
 677     for (i=0;i<table_size;i++)
 678       for (j=0;j<table_size;j++)
 679         generic_free_extended_route(TO_ROUTE_FULL(i,j));
 680     xbt_free(routing->routing_table);
 681     /* Delete bypass dict */
 682     xbt_dict_free(&routing->bypassRoutes);
 683     /* Delete index dict */
 684     xbt_dict_free(&(routing->to_index));
 685     /* Delete structure */
 686     xbt_free(rc);
 687   }
 688 }
 689
 690 /* Creation routing model functions */
 691
 692 static void* model_full_create(void) {
 693   routing_component_full_t new_component =  xbt_new0(s_routing_component_full_t,1);
 694   new_component->generic_routing.set_processing_unit = generic_set_processing_unit;
 695   new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
 696   new_component->generic_routing.set_route = generic_set_route;
 697   new_component->generic_routing.set_ASroute = generic_set_ASroute;
 698   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
 699   new_component->generic_routing.get_route = full_get_route;
 700   new_component->generic_routing.get_bypass_route = generic_get_bypassroute;
 701   new_component->generic_routing.finalize = full_finalize;
 702   new_component->to_index = xbt_dict_new();
 703   new_component->bypassRoutes = xbt_dict_new();
 704   new_component->parse_routes = xbt_dict_new();
 705   return new_component;
 706 }
 707
 708 static void model_full_load(void) {
 709  /* use "surfxml_add_callback" to add a parse function call */
 710 }
 711
 712 static void model_full_unload(void) {
 713  /* use "surfxml_del_callback" to remove a parse function call */
 714 }
 715
 716 static void  model_full_end(void) {
 717
 718   char *key, *end;
 719   const char* sep = "#";
 720   int src_id, dst_id;
 721   unsigned int i, j;
 722   route_t route;
 723   route_extended_t e_route;
 724   void* data;
 725
 726   xbt_dict_cursor_t cursor = NULL;
 727   xbt_dynar_t keys = NULL;
 728
 729   /* set utils vars */
 730   routing_component_full_t routing = ((routing_component_full_t)current_routing);
 731   int table_size = xbt_dict_length(routing->to_index);
 732
 733   /* Create the routing table */
 734   routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
 735
 736   /* Put the routes in position */
 737   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 738     keys = xbt_str_split_str(key, sep);
 739     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 10);
 740     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 10);
 741     TO_ROUTE_FULL(src_id,dst_id) = generic_new_extended_route(current_routing->hierarchy,data,1);
 742      xbt_dynar_free(&keys);
 743    }
 744
 745    /* delete the parse table */
 746   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 747     route = (route_t)data;
 748     xbt_dynar_free(&(route->link_list));
 749     xbt_free(data);
 750   }
 751
 752   /* delete parse dict */
 753   xbt_dict_free(&(routing->parse_routes));
 754
 755   /* Add the loopback if needed */
 756   if(current_routing->hierarchy == SURF_ROUTING_BASE) {
 757     for (i = 0; i < table_size; i++) {
 758       e_route = TO_ROUTE_FULL(i, i);
 759       if(!e_route) {
 760         e_route = xbt_new0(s_route_extended_t,1);
 761         e_route->src_gateway = NULL;
 762         e_route->dst_gateway = NULL;
 763         e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 764         xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
 765         TO_ROUTE_FULL(i, i) = e_route;
 766       }
 767     }
 768   }
 769
 770   /* Shrink the dynar routes (save unused slots) */
 771   for (i=0;i<table_size;i++)
 772     for (j=0;j<table_size;j++)
 773       if(TO_ROUTE_FULL(i,j))
 774         xbt_dynar_shrink(TO_ROUTE_FULL(i,j)->generic_route.link_list,0);
 775 }
 776
 777 /* ************************************************************************** */
 778 /* *************************** FLOYD ROUTING ******************************** */
 779
 780 #define TO_FLOYD_COST(i,j) cost_table[(i)+(j)*table_size]
 781 #define TO_FLOYD_PRED(i,j) (routing->predecessor_table)[(i)+(j)*table_size]
 782 #define TO_FLOYD_LINK(i,j) (routing->link_table)[(i)+(j)*table_size]
 783
 784 /* Routing model structure */
 785
 786 typedef struct {
 787   s_routing_component_t generic_routing;
 788   /* vars for calculate the floyd algorith. */
 789   int *predecessor_table;
 790   route_extended_t *link_table; /* char* -> int* */
 791   xbt_dict_t to_index;
 792   xbt_dict_t bypassRoutes;
 793   /* store data during the parse process */
 794   xbt_dict_t parse_routes;
 795 } s_routing_component_floyd_t,*routing_component_floyd_t;
 796
 797 /* Business methods */
 798
 799 static route_extended_t floyd_get_route(routing_component_t rc, const char* src,const char* dst) {
 800   xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
 801
 802   /* set utils vars */
 803   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
 804   int table_size = xbt_dict_length(routing->to_index);
 805
 806   generic_src_dst_check(rc,src,dst);
 807   int *src_id = xbt_dict_get_or_null(routing->to_index,src);
 808   int *dst_id = xbt_dict_get_or_null(routing->to_index,dst);
 809   xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",src,dst);
 810
 811   /* create a result route */
 812   route_extended_t new_e_route = xbt_new0(s_route_extended_t,1);
 813   new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 814   new_e_route->src_gateway = NULL;
 815   new_e_route->dst_gateway = NULL;
 816
 817   int first = 1;
 818   int pred = *dst_id;
 819   int prev_pred = 0;
 820   char *gw_src,*gw_dst, *prev_gw_src,*prev_gw_dst, *first_gw;
 821   unsigned int cpt;
 822   void* link;
 823   xbt_dynar_t links;
 824
 825   do {
 826     prev_pred = pred;
 827     pred = TO_FLOYD_PRED(*src_id, pred);
 828     if(pred == -1) /* if no pred in route -> no route to host */
 829       break;
 830     xbt_assert2(TO_FLOYD_LINK(pred,prev_pred),"Invalid link for the route between \"%s\" or \"%s\"", src, dst);
 831
 832     prev_gw_src = gw_src;
 833     prev_gw_dst = gw_dst;
 834
 835     route_extended_t e_route = TO_FLOYD_LINK(pred,prev_pred);
 836     gw_src = e_route->src_gateway;
 837     gw_dst = e_route->dst_gateway;
 838
 839     if(first) first_gw = gw_dst;
 840
 841     if(rc->hierarchy == SURF_ROUTING_RECURSIVE && !first && strcmp(gw_dst,prev_gw_src)) {
 842       xbt_dynar_t e_route_as_to_as = (*(global_routing->get_route))(gw_dst,prev_gw_src);
 843       xbt_assert2(e_route_as_to_as,"no route between \"%s\" and \"%s\"",gw_dst,prev_gw_src);
 844       links = e_route_as_to_as;
 845       int pos = 0;
 846       xbt_dynar_foreach(links, cpt, link) {
 847         xbt_dynar_insert_at(new_e_route->generic_route.link_list,pos,&link);
 848         pos++;
 849       }
 850     }
 851
 852     links = e_route->generic_route.link_list;
 853     xbt_dynar_foreach(links, cpt, link) {
 854       xbt_dynar_unshift(new_e_route->generic_route.link_list,&link);
 855     }
 856     first=0;
 857
 858   } while(pred != *src_id);
 859   xbt_assert4(pred != -1, "no route from host %d to %d (\"%s\" to \"%s\")", *src_id, *dst_id,src,dst);
 860
 861   if(rc->hierarchy == SURF_ROUTING_RECURSIVE) {
 862     new_e_route->src_gateway = xbt_strdup(gw_src);
 863     new_e_route->dst_gateway = xbt_strdup(first_gw);
 864   }
 865
 866   return new_e_route;
 867 }
 868
 869 static void floyd_finalize(routing_component_t rc) {
 870    routing_component_floyd_t routing = (routing_component_floyd_t)rc;
 871   int i,j,table_size;
 872   if (routing) {
 873     table_size = xbt_dict_length(routing->to_index);
 874     /* Delete link_table */
 875     for (i=0;i<table_size;i++)
 876       for (j=0;j<table_size;j++)
 877         generic_free_extended_route(TO_FLOYD_LINK(i,j));
 878     xbt_free(routing->link_table);
 879     /* Delete bypass dict */
 880     xbt_dict_free(&routing->bypassRoutes);
 881     /* Delete index dict */
 882     xbt_dict_free(&(routing->to_index));
 883     /* Delete dictionary index dict, predecessor and links table */
 884     xbt_free(routing->predecessor_table);
 885     /* Delete structure */
 886     xbt_free(rc);
 887   }
 888 }
 889
 890 static void* model_floyd_create(void) {
 891   routing_component_floyd_t new_component = xbt_new0(s_routing_component_floyd_t,1);
 892   new_component->generic_routing.set_processing_unit = generic_set_processing_unit;
 893   new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
 894   new_component->generic_routing.set_route = generic_set_route;
 895   new_component->generic_routing.set_ASroute = generic_set_ASroute;
 896   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
 897   new_component->generic_routing.get_route = floyd_get_route;
 898   new_component->generic_routing.get_bypass_route = generic_get_bypassroute;
 899   new_component->generic_routing.finalize = floyd_finalize;
 900   new_component->to_index = xbt_dict_new();
 901   new_component->bypassRoutes = xbt_dict_new();
 902   new_component->parse_routes = xbt_dict_new();
 903   return new_component;
 904 }
 905
 906 static void  model_floyd_load(void) {
 907  /* use "surfxml_add_callback" to add a parse function call */
 908 }
 909
 910 static void  model_floyd_unload(void) {
 911  /* use "surfxml_del_callback" to remove a parse function call */
 912 }
 913
 914 static void  model_floyd_end(void) {
 915
 916   routing_component_floyd_t routing = ((routing_component_floyd_t)current_routing);
 917   xbt_dict_cursor_t cursor = NULL;
 918   double * cost_table;
 919   char *key,*data, *end;
 920   const char *sep = "#";
 921   xbt_dynar_t keys;
 922   int src_id, dst_id;
 923   unsigned int i,j,a,b,c;
 924
 925   /* set the size of inicial table */
 926   int table_size = xbt_dict_length(routing->to_index);
 927
 928   /* Create Cost, Predecessor and Link tables */
 929   cost_table = xbt_new0(double, table_size*table_size); /* link cost from host to host */
 930   routing->predecessor_table = xbt_new0(int, table_size*table_size); /* predecessor host numbers */
 931   routing->link_table = xbt_new0(route_extended_t, table_size*table_size); /* actual link between src and dst */
 932
 933   /* Initialize costs and predecessors*/
 934   for(i = 0; i<table_size;i++)
 935     for(j = 0; j<table_size;j++) {
 936         TO_FLOYD_COST(i,j) = DBL_MAX;
 937         TO_FLOYD_PRED(i,j) = -1;
 938         TO_FLOYD_LINK(i,j) = NULL; /* fixed, missing in the previous version */
 939     }
 940
 941    /* Put the routes in position */
 942   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 943     keys = xbt_str_split_str(key, sep);
 944     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 10);
 945     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 10);
 946     TO_FLOYD_LINK(src_id,dst_id) = generic_new_extended_route(current_routing->hierarchy,data,0);
 947     TO_FLOYD_PRED(src_id,dst_id) = src_id;
 948     /* set link cost */
 949     TO_FLOYD_COST(src_id,dst_id) = ((TO_FLOYD_LINK(src_id,dst_id))->generic_route.link_list)->used; /* count of links, old model assume 1 */
 950     xbt_dynar_free(&keys);
 951   }
 952
 953   /* Add the loopback if needed */
 954   if(current_routing->hierarchy == SURF_ROUTING_BASE) {
 955     for (i = 0; i < table_size; i++) {
 956       route_extended_t e_route = TO_FLOYD_LINK(i, i);
 957       if(!e_route) {
 958         e_route = xbt_new0(s_route_extended_t,1);
 959         e_route->src_gateway = NULL;
 960         e_route->dst_gateway = NULL;
 961         e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 962         xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
 963         TO_FLOYD_LINK(i,i) = e_route;
 964         TO_FLOYD_PRED(i,i) = i;
 965         TO_FLOYD_COST(i,i) = 1;
 966       }
 967     }
 968   }
 969   /* Calculate path costs */
 970   for(c=0;c<table_size;c++) {
 971     for(a=0;a<table_size;a++) {
 972       for(b=0;b<table_size;b++) {
 973         if(TO_FLOYD_COST(a,c) < DBL_MAX && TO_FLOYD_COST(c,b) < DBL_MAX) {
 974           if(TO_FLOYD_COST(a,b) == DBL_MAX ||
 975             (TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b) < TO_FLOYD_COST(a,b))) {
 976             TO_FLOYD_COST(a,b) = TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b);
 977             TO_FLOYD_PRED(a,b) = TO_FLOYD_PRED(c,b);
 978           }
 979         }
 980       }
 981     }
 982   }
 983
 984    /* delete the parse table */
 985   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 986     route_t route = (route_t)data;
 987     xbt_dynar_free(&(route->link_list));
 988     xbt_free(data);
 989   }
 990
 991   /* delete parse dict */
 992   xbt_dict_free(&(routing->parse_routes));
 993
 994   /* cleanup */
 995   xbt_free(cost_table);
 996 }
 997
 998 /* ************************************************************************** */
 999 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
1000
1001 typedef struct {
1002   s_routing_component_t generic_routing;
1003   xbt_dict_t to_index;
1004   xbt_dict_t bypassRoutes;
1005   xbt_graph_t route_graph;   /* xbt_graph */
1006   xbt_dict_t graph_node_map; /* map */
1007   xbt_dict_t route_cache;    /* use in cache mode */
1008   int cached;
1009   xbt_dict_t parse_routes;
1010 } s_routing_component_dijkstra_t,*routing_component_dijkstra_t;
1011
1012
1013 typedef struct graph_node_data {
1014   int id;
1015   int graph_id; /* used for caching internal graph id's */
1016 } s_graph_node_data_t, * graph_node_data_t;
1017
1018 typedef struct graph_node_map_element {
1019   xbt_node_t node;
1020 } s_graph_node_map_element_t, * graph_node_map_element_t;
1021
1022 typedef struct route_cache_element {
1023   int * pred_arr;
1024   int size;
1025 } s_route_cache_element_t, * route_cache_element_t;
1026
1027 /* Free functions */
1028
1029 static void route_cache_elem_free(void *e) {
1030   route_cache_element_t elm=(route_cache_element_t)e;
1031   if (elm) {
1032     xbt_free(elm->pred_arr);
1033     xbt_free(elm);
1034   }
1035 }
1036
1037 static void graph_node_map_elem_free(void *e) {
1038   graph_node_map_element_t elm = (graph_node_map_element_t)e;
1039   if(elm) {
1040     xbt_free(elm);
1041   }
1042 }
1043
1044 static void graph_edge_data_free(void *e) {
1045   route_extended_t e_route = (route_extended_t)e;
1046   if(e_route) {
1047     xbt_dynar_free(&(e_route->generic_route.link_list));
1048     if(e_route->src_gateway) xbt_free(e_route->src_gateway);
1049     if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
1050     xbt_free(e_route);
1051   }
1052 }
1053
1054 /* Utility functions */
1055
1056 static xbt_node_t route_graph_new_node(routing_component_dijkstra_t rc, int id, int graph_id) {
1057   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1058   xbt_node_t node = NULL;
1059   graph_node_data_t data = NULL;
1060   graph_node_map_element_t elm = NULL;
1061
1062   data = xbt_new0(struct graph_node_data, 1);
1063   data->id = id;
1064   data->graph_id = graph_id;
1065   node = xbt_graph_new_node(routing->route_graph, data);
1066
1067   elm = xbt_new0(struct graph_node_map_element, 1);
1068   elm->node = node;
1069   xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);
1070
1071   return node;
1072 }
1073
1074 static graph_node_map_element_t graph_node_map_search(routing_component_dijkstra_t rc, int id) {
1075   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1076   graph_node_map_element_t elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&id), sizeof(int));
1077   return elm;
1078 }
1079
1080 /* Parsing */
1081
1082 static void route_new_dijkstra(routing_component_dijkstra_t rc, int src_id, int dst_id, route_extended_t e_route ) {
1083   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1084
1085   xbt_node_t src = NULL;
1086   xbt_node_t dst = NULL;
1087   graph_node_map_element_t src_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&src_id), sizeof(int));
1088   graph_node_map_element_t dst_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&dst_id), sizeof(int));
1089
1090   if(src_elm)
1091     src = src_elm->node;
1092
1093   if(dst_elm)
1094     dst = dst_elm->node;
1095
1096   /* add nodes if they don't exist in the graph */
1097   if(src_id == dst_id && src == NULL && dst == NULL) {
1098     src = route_graph_new_node(rc,src_id, -1);
1099     dst = src;
1100   } else {
1101     if(src == NULL) {
1102       src = route_graph_new_node(rc,src_id, -1);
1103     }
1104     if(dst == NULL) {
1105       dst = route_graph_new_node(rc,dst_id, -1);
1106     }
1107   }
1108
1109   /* add link as edge to graph */
1110   xbt_graph_new_edge(routing->route_graph, src, dst, e_route);
1111 }
1112
1113 static void add_loopback_dijkstra(routing_component_dijkstra_t rc) {
1114   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1115
1116   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1117
1118   xbt_node_t node = NULL;
1119   unsigned int cursor2;
1120   xbt_dynar_foreach(nodes, cursor2, node) {
1121     xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
1122     xbt_edge_t edge = NULL;
1123     unsigned int cursor;
1124
1125     int found = 0;
1126     xbt_dynar_foreach(out_edges, cursor, edge) {
1127       xbt_node_t other_node = xbt_graph_edge_get_target(edge);
1128       if(other_node == node) {
1129         found = 1;
1130         break;
1131       }
1132     }
1133
1134     if(!found) {
1135       route_extended_t e_route = xbt_new0(s_route_extended_t,1);
1136       e_route->src_gateway = NULL;
1137       e_route->dst_gateway = NULL;
1138       e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1139       xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
1140       xbt_graph_new_edge(routing->route_graph, node, node, e_route);
1141     }
1142   }
1143 }
1144
1145 /* Business methods */
1146
1147 static route_extended_t dijkstra_get_route(routing_component_t rc, const char* src,const char* dst) {
1148   xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
1149
1150   /* set utils vars */
1151   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1152
1153   generic_src_dst_check(rc,src,dst);
1154   int *src_id = xbt_dict_get_or_null(routing->to_index,src);
1155   int *dst_id = xbt_dict_get_or_null(routing->to_index,dst);
1156   xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",src,dst);
1157
1158   /* create a result route */
1159   route_extended_t new_e_route = xbt_new0(s_route_extended_t,1);
1160   new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1161   new_e_route->src_gateway = NULL;
1162   new_e_route->dst_gateway = NULL;
1163
1164   int *pred_arr = NULL;
1165   int src_node_id = 0;
1166   int dst_node_id = 0;
1167   int * nodeid = NULL;
1168   int v;
1169   route_extended_t e_route;
1170   int size = 0;
1171   unsigned int cpt;
1172   void* link;
1173   xbt_dynar_t links = NULL;
1174   route_cache_element_t elm = NULL;
1175   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1176
1177   /* Use the graph_node id mapping set to quickly find the nodes */
1178   graph_node_map_element_t src_elm = graph_node_map_search(routing,*src_id);
1179   graph_node_map_element_t dst_elm = graph_node_map_search(routing,*dst_id);
1180   xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", *src_id, *dst_id);
1181   src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id;
1182   dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id;
1183
1184   /* if the src and dst are the same */  /* fixed, missing in the previous version */
1185   if( src_node_id == dst_node_id ) {
1186
1187     xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
1188     xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
1189     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_s_v, node_e_v);
1190
1191     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id, *dst_id);
1192
1193     e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1194
1195     links = e_route->generic_route.link_list;
1196     xbt_dynar_foreach(links, cpt, link) {
1197       xbt_dynar_unshift(new_e_route->generic_route.link_list,&link);
1198     }
1199
1200     return new_e_route;
1201   }
1202
1203   if(routing->cached) {
1204     /*check if there is a cached predecessor list avail */
1205     elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int));
1206   }
1207
1208   if(elm) { /* cached mode and cache hit */
1209     pred_arr = elm->pred_arr;
1210   } else { /* not cached mode or cache miss */
1211     double * cost_arr = NULL;
1212     xbt_heap_t pqueue = NULL;
1213     int i = 0;
1214
1215     int nr_nodes = xbt_dynar_length(nodes);
1216     cost_arr = xbt_new0(double, nr_nodes); /* link cost from src to other hosts */
1217     pred_arr = xbt_new0(int, nr_nodes);    /* predecessors in path from src */
1218     pqueue = xbt_heap_new(nr_nodes, xbt_free);
1219
1220     /* initialize */
1221     cost_arr[src_node_id] = 0.0;
1222
1223     for(i = 0; i < nr_nodes; i++) {
1224       if(i != src_node_id) {
1225         cost_arr[i] = DBL_MAX;
1226       }
1227
1228       pred_arr[i] = 0;
1229
1230       /* initialize priority queue */
1231       nodeid = xbt_new0(int, 1);
1232       *nodeid = i;
1233       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
1234
1235     }
1236
1237     /* apply dijkstra using the indexes from the graph's node array */
1238     while(xbt_heap_size(pqueue) > 0) {
1239       int * v_id = xbt_heap_pop(pqueue);
1240       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
1241       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
1242       xbt_edge_t edge = NULL;
1243       unsigned int cursor;
1244
1245       xbt_dynar_foreach(out_edges, cursor, edge) {
1246         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
1247         graph_node_data_t data = xbt_graph_node_get_data(u_node);
1248         int u_id = data->graph_id;
1249         route_extended_t tmp_e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1250         int cost_v_u = (tmp_e_route->generic_route.link_list)->used;  /* count of links, old model assume 1 */
1251
1252         if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
1253           pred_arr[u_id] = *v_id;
1254           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
1255           nodeid = xbt_new0(int, 1);
1256           *nodeid = u_id;
1257           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
1258         }
1259       }
1260
1261       /* free item popped from pqueue */
1262       xbt_free(v_id);
1263     }
1264
1265     xbt_free(cost_arr);
1266     xbt_heap_free(pqueue);
1267   }
1268
1269   /* compose route path with links */
1270   char *gw_src,*gw_dst, *prev_gw_src,*prev_gw_dst, *first_gw;
1271
1272   for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
1273     xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
1274     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
1275     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
1276
1277     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id, *dst_id);
1278
1279     prev_gw_src = gw_src;
1280     prev_gw_dst = gw_dst;
1281
1282     e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1283     gw_src = e_route->src_gateway;
1284     gw_dst = e_route->dst_gateway;
1285
1286     if(v==dst_node_id) first_gw = gw_dst;
1287
1288     if(rc->hierarchy == SURF_ROUTING_RECURSIVE && v!=dst_node_id && strcmp(gw_dst,prev_gw_src)) {
1289       xbt_dynar_t e_route_as_to_as = (*(global_routing->get_route))(gw_dst,prev_gw_src);
1290       xbt_assert2(e_route_as_to_as,"no route between \"%s\" and \"%s\"",gw_dst,prev_gw_src);
1291       links = e_route_as_to_as;
1292       int pos = 0;
1293       xbt_dynar_foreach(links, cpt, link) {
1294         xbt_dynar_insert_at(new_e_route->generic_route.link_list,pos,&link);
1295         pos++;
1296       }
1297     }
1298
1299     links = e_route->generic_route.link_list;
1300     xbt_dynar_foreach(links, cpt, link) {
1301       xbt_dynar_unshift(new_e_route->generic_route.link_list,&link);
1302     }
1303     size++;
1304   }
1305
1306   if(rc->hierarchy == SURF_ROUTING_RECURSIVE) {
1307     new_e_route->src_gateway = xbt_strdup(gw_src);
1308     new_e_route->dst_gateway = xbt_strdup(first_gw);
1309   }
1310
1311   if(routing->cached && elm == NULL) {
1312     /* add to predecessor list of the current src-host to cache */
1313     elm = xbt_new0(struct route_cache_element, 1);
1314     elm->pred_arr = pred_arr;
1315     elm->size = size;
1316     xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free);
1317   }
1318
1319   if(!routing->cached)
1320     xbt_free(pred_arr);
1321
1322   return new_e_route;
1323 }
1324
1325 static void dijkstra_finalize(routing_component_t rc) {
1326   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1327
1328   if (routing) {
1329     xbt_graph_free_graph(routing->route_graph, &xbt_free, &graph_edge_data_free, &xbt_free);
1330     xbt_dict_free(&routing->graph_node_map);
1331     if(routing->cached)
1332       xbt_dict_free(&routing->route_cache);
1333     /* Delete bypass dict */
1334     xbt_dict_free(&routing->bypassRoutes);
1335     /* Delete index dict */
1336     xbt_dict_free(&(routing->to_index));
1337     /* Delete structure */
1338     xbt_free(routing);
1339   }
1340 }
1341
1342 /* Creation routing model functions */
1343
1344 static void* model_dijkstra_both_create(int cached) {
1345   routing_component_dijkstra_t new_component = xbt_new0(s_routing_component_dijkstra_t,1);
1346   new_component->generic_routing.set_processing_unit = generic_set_processing_unit;
1347   new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
1348   new_component->generic_routing.set_route = generic_set_route;
1349   new_component->generic_routing.set_ASroute = generic_set_ASroute;
1350   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
1351   new_component->generic_routing.get_route = dijkstra_get_route;
1352   new_component->generic_routing.get_bypass_route = generic_get_bypassroute;
1353   new_component->generic_routing.finalize = dijkstra_finalize;
1354   new_component->cached = cached;
1355   new_component->to_index = xbt_dict_new();
1356   new_component->bypassRoutes = xbt_dict_new();
1357   new_component->parse_routes = xbt_dict_new();
1358   return new_component;
1359 }
1360
1361 static void* model_dijkstra_create(void) {
1362   return model_dijkstra_both_create(0);
1363 }
1364
1365 static void* model_dijkstracache_create(void) {
1366   return model_dijkstra_both_create(1);
1367 }
1368
1369 static void  model_dijkstra_both_load(void) {
1370  /* use "surfxml_add_callback" to add a parse function call */
1371 }
1372
1373 static void  model_dijkstra_both_unload(void) {
1374  /* use "surfxml_del_callback" to remove a parse function call */
1375 }
1376
1377 static void  model_dijkstra_both_end(void) {
1378   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) current_routing;
1379    xbt_dict_cursor_t cursor = NULL;
1380    char *key, *data, *end;
1381    const char *sep = "#";
1382    xbt_dynar_t keys;
1383   xbt_node_t node = NULL;
1384   unsigned int cursor2;
1385   xbt_dynar_t nodes = NULL;
1386   int src_id, dst_id;
1387   route_t route;
1388
1389   /* Create the topology graph */
1390   routing->route_graph = xbt_graph_new_graph(1, NULL);
1391   routing->graph_node_map = xbt_dict_new();
1392
1393   if(routing->cached)
1394     routing->route_cache = xbt_dict_new();
1395
1396   /* Put the routes in position */
1397   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1398     keys = xbt_str_split_str(key, sep);
1399     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 10);
1400     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 10);
1401     route_extended_t e_route = generic_new_extended_route(current_routing->hierarchy,data,0);
1402     route_new_dijkstra(routing,src_id,dst_id,e_route);
1403     xbt_dynar_free(&keys);
1404   }
1405
1406   /* delete the parse table */
1407   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1408     route = (route_t)data;
1409     xbt_dynar_free(&(route->link_list));
1410     xbt_free(data);
1411   }
1412
1413   /* delete parse dict */
1414   xbt_dict_free(&(routing->parse_routes));
1415
1416   /* Add the loopback if needed */
1417   if(current_routing->hierarchy == SURF_ROUTING_BASE)
1418     add_loopback_dijkstra(routing);
1419
1420   /* initialize graph indexes in nodes after graph has been built */
1421   nodes = xbt_graph_get_nodes(routing->route_graph);
1422
1423   xbt_dynar_foreach(nodes, cursor2, node) {
1424     graph_node_data_t data = xbt_graph_node_get_data(node);
1425     data->graph_id = cursor2;
1426   }
1427
1428 }
1429
1430 /* ************************************************** */
1431 /* ************** RULE-BASED ROUTING **************** */
1432
1433 /* Routing model structure */
1434
1435 typedef struct {
1436   s_routing_component_t generic_routing;
1437   xbt_dict_t  dict_processing_units;
1438   xbt_dict_t  dict_autonomous_systems;
1439   xbt_dynar_t list_route;
1440   xbt_dynar_t list_ASroute;
1441 } s_routing_component_rulebased_t,*routing_component_rulebased_t;
1442
1443 typedef struct s_rule_route s_rule_route_t, *rule_route_t;
1444 typedef struct s_rule_route_extended s_rule_route_extended_t, *rule_route_extended_t;
1445
1446 struct s_rule_route {
1447   xbt_dynar_t re_str_link; // dynar of char*
1448   pcre* re_src;
1449   pcre* re_dst;
1450 };
1451
1452 struct s_rule_route_extended {
1453   s_rule_route_t generic_rule_route;
1454   char* re_src_gateway;
1455   char* re_dst_gateway;
1456 };
1457
1458 static void rule_route_free(void *e) {
1459   rule_route_t* elem = (rule_route_t*)(e);
1460   if (*elem) {
1461     xbt_dynar_free(&(*elem)->re_str_link);
1462     pcre_free((*elem)->re_src);
1463     pcre_free((*elem)->re_dst);
1464     xbt_free((*elem));
1465   }
1466   (*elem) = NULL;
1467 }
1468
1469 static void rule_route_extended_free(void *e) {
1470   rule_route_extended_t* elem = (rule_route_extended_t*)e;
1471   if (*elem) {
1472     xbt_dynar_free(&(*elem)->generic_rule_route.re_str_link);
1473     pcre_free((*elem)->generic_rule_route.re_src);
1474     pcre_free((*elem)->generic_rule_route.re_dst);
1475     xbt_free((*elem)->re_src_gateway);
1476     xbt_free((*elem)->re_dst_gateway);
1477     xbt_free((*elem));
1478   }
1479 }
1480
1481 /* Parse routing model functions */
1482
1483 static void model_rulebased_set_processing_unit(routing_component_t rc, const char* name) {
1484   routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1485   xbt_dict_set(routing->dict_processing_units, name, (void*)(-1), NULL);
1486 }
1487
1488 static void model_rulebased_set_autonomous_system(routing_component_t rc, const char* name) {
1489   routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1490   xbt_dict_set(routing->dict_autonomous_systems, name, (void*)(-1), NULL);
1491 }
1492
1493 static void model_rulebased_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {
1494   routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1495   rule_route_t ruleroute = xbt_new0(s_rule_route_t,1);
1496   const char *error;
1497   int erroffset;
1498   ruleroute->re_src = pcre_compile(src,0,&error,&erroffset,NULL);
1499   xbt_assert3(ruleroute->re_src,"PCRE compilation failed at offset %d (\"%s\"): %s\n", erroffset, src, error);
1500   ruleroute->re_dst = pcre_compile(dst,0,&error,&erroffset,NULL);
1501   xbt_assert3(ruleroute->re_src,"PCRE compilation failed at offset %d (\"%s\"): %s\n", erroffset, dst, error);
1502   ruleroute->re_str_link = route->link_list;
1503   xbt_dynar_push(routing->list_route,&ruleroute);
1504   xbt_free(route);
1505 }
1506
1507 static void model_rulebased_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t route) {
1508   routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1509   rule_route_extended_t ruleroute_e = xbt_new0(s_rule_route_extended_t,1);
1510   const char *error;
1511   int erroffset;
1512   ruleroute_e->generic_rule_route.re_src = pcre_compile(src,0,&error,&erroffset,NULL);
1513   xbt_assert3(ruleroute_e->generic_rule_route.re_src,"PCRE compilation failed at offset %d (\"%s\"): %s\n", erroffset, src, error);
1514   ruleroute_e->generic_rule_route.re_dst = pcre_compile(dst,0,&error,&erroffset,NULL);
1515   xbt_assert3(ruleroute_e->generic_rule_route.re_src,"PCRE compilation failed at offset %d (\"%s\"): %s\n", erroffset, dst, error);
1516   ruleroute_e->generic_rule_route.re_str_link = route->generic_route.link_list;
1517   ruleroute_e->re_src_gateway = route->src_gateway;
1518   ruleroute_e->re_dst_gateway = route->dst_gateway;
1519   xbt_dynar_push(routing->list_ASroute,&ruleroute_e);
1520   xbt_free(route->src_gateway);
1521   xbt_free(route->dst_gateway);
1522   xbt_free(route);
1523 }
1524
1525 static void model_rulebased_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {
1526   xbt_die("bypass routing not support for Route-Based model");
1527 }
1528
1529 #define BUFFER_SIZE 4096  /* result buffer size */
1530 #define OVECCOUNT 30      /* should be a multiple of 3 */
1531
1532 static char* remplace(char* value, const char** src_list, int src_size, const char** dst_list, int dst_size ) {
1533
1534   char result_result[BUFFER_SIZE];
1535   int i_result_buffer;
1536   int value_length = (int)strlen(value);
1537   int number=0;
1538
1539   int i=0;
1540   i_result_buffer = 0;
1541   do {
1542     if( value[i] == '$' ) {
1543       i++; // skip $
1544
1545       // find the number
1546       int number_length = 0;
1547       while( '0' <= value[i+number_length] && value[i+number_length] <= '9' ) {
1548         number_length++;
1549       }
1550       xbt_assert2( number_length!=0, "bad string parameter, no number indication, at offset: %d (\"%s\")",i,value);
1551
1552       // solve number
1553       number = atoi(value+i);
1554       i=i+number_length;
1555       xbt_assert2(i+2<value_length,"bad string parameter, too few chars, at offset: %d (\"%s\")",i,value);
1556
1557       // solve the indication
1558       const char** param_list;
1559       int param_size;
1560       if( value[i] == 's' && value[i+1] == 'r' && value[i+2] == 'c' ) {
1561         param_list = src_list;
1562         param_size = src_size;
1563       } else  if( value[i] == 'd' && value[i+1] == 's' && value[i+2] == 't' ) {
1564         param_list = dst_list;
1565         param_size = dst_size;
1566       } else {
1567         xbt_assert2(0,"bad string parameter, support only \"src\" and \"dst\", at offset: %d (\"%s\")",i,value);
1568       }
1569       i=i+3;
1570
1571       xbt_assert4( param_size >= number, "bad string parameter, not enough length param_size, at offset: %d (\"%s\") %d %d",i,value,param_size,number);
1572
1573       const char* param = param_list[number];
1574       int size = strlen(param);
1575       int cp;
1576       for(cp = 0; cp < size; cp++ ) {
1577         result_result[i_result_buffer] = param[cp];
1578         i_result_buffer++;
1579         if( i_result_buffer >= BUFFER_SIZE ) break;
1580       }
1581     } else {
1582       result_result[i_result_buffer] = value[i];
1583       i_result_buffer++;
1584       i++; // next char
1585     }
1586
1587   } while(i<value_length && i_result_buffer < BUFFER_SIZE);
1588
1589   xbt_assert2( i_result_buffer < BUFFER_SIZE, "solving string \"%s\", small buffer size (%d)",value,BUFFER_SIZE);
1590   result_result[i_result_buffer] = 0;
1591   return xbt_strdup(result_result);
1592 }
1593
1594 /* Business methods */
1595 static route_extended_t rulebased_get_route(routing_component_t rc, const char* src,const char* dst) {
1596   xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
1597
1598   /* set utils vars */
1599   routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1600
1601   int are_processing_units;
1602   xbt_dynar_t rule_list;
1603   if( xbt_dict_get_or_null(routing->dict_processing_units,src) && xbt_dict_get_or_null(routing->dict_processing_units,dst) ) {
1604     are_processing_units = 1;
1605     rule_list = routing->list_route;
1606   } else if( xbt_dict_get_or_null(routing->dict_autonomous_systems,src) && xbt_dict_get_or_null(routing->dict_autonomous_systems,dst) ) {
1607     are_processing_units = 0;
1608     rule_list = routing->list_ASroute;
1609   } else
1610      xbt_assert2(NULL, "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",src,dst);
1611
1612   int rc_src,rc_dst;
1613   int src_length = (int)strlen(src);
1614   int dst_length = (int)strlen(dst);
1615
1616   xbt_dynar_t links_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1617
1618   rule_route_t ruleroute;
1619   unsigned int cpt;
1620   int ovector_src[OVECCOUNT];
1621   int ovector_dst[OVECCOUNT];
1622   const char** list_src = NULL;
1623   const char** list_dst = NULL;
1624   xbt_dynar_foreach(rule_list, cpt, ruleroute) {
1625     rc_src = pcre_exec(ruleroute->re_src,NULL,src,src_length,0,0,ovector_src,OVECCOUNT);
1626     if( rc_src >= 0 ) {
1627       rc_dst = pcre_exec(ruleroute->re_dst,NULL,dst,dst_length,0,0,ovector_dst,OVECCOUNT);
1628       if( rc_dst >= 0 ) {
1629         xbt_assert1(!pcre_get_substring_list(src,ovector_src,rc_src,&list_src),"error solving substring list for src \"%s\"",src);
1630         xbt_assert1(!pcre_get_substring_list(dst,ovector_dst,rc_dst,&list_dst),"error solving substring list for src \"%s\"",dst);
1631         char* link_name;
1632         xbt_dynar_foreach(ruleroute->re_str_link, cpt, link_name) {
1633           char* new_link_name = remplace(link_name,list_src,rc_src,list_dst,rc_dst);
1634           void* link = xbt_dict_get_or_null(surf_network_model->resource_set, new_link_name);
1635           if (link)
1636             xbt_dynar_push(links_list,&link);
1637           else
1638             THROW1(mismatch_error,0,"Link %s not found", new_link_name);
1639           xbt_free(new_link_name);
1640         }
1641       }
1642     }
1643     if( rc_src >= 0 && rc_dst >= 0 ) break;
1644   }
1645
1646   route_extended_t new_e_route = NULL;
1647   if(rc_src >= 0 && rc_dst >= 0) {
1648     new_e_route = xbt_new0(s_route_extended_t,1);
1649     new_e_route->generic_route.link_list = links_list;
1650   }
1651
1652   if(!are_processing_units && new_e_route)
1653   {
1654     rule_route_extended_t ruleroute_extended = (rule_route_extended_t)ruleroute;
1655     new_e_route->src_gateway = remplace(ruleroute_extended->re_src_gateway,list_src,rc_src,list_dst,rc_dst);
1656     new_e_route->dst_gateway = remplace(ruleroute_extended->re_dst_gateway,list_src,rc_src,list_dst,rc_dst);
1657   }
1658
1659   if(list_src) pcre_free_substring_list(list_src);
1660   if(list_dst) pcre_free_substring_list(list_dst);
1661
1662   return new_e_route;
1663 }
1664
1665 static route_extended_t rulebased_get_bypass_route(routing_component_t rc, const char* src,const char* dst) {
1666   return NULL;
1667 }
1668
1669 static void rulebased_finalize(routing_component_t rc) {
1670   routing_component_rulebased_t routing = (routing_component_rulebased_t) rc;
1671   if (routing) {
1672     xbt_dict_free(&routing->dict_processing_units);
1673     xbt_dict_free(&routing->dict_autonomous_systems);
1674     xbt_dynar_free(&routing->list_route);
1675     xbt_dynar_free(&routing->list_ASroute);
1676     /* Delete structure */
1677     xbt_free(routing);
1678   }
1679 }
1680
1681 /* Creation routing model functions */
1682 static void* model_rulebased_create(void) {
1683   routing_component_rulebased_t new_component =  xbt_new0(s_routing_component_rulebased_t,1);
1684   new_component->generic_routing.set_processing_unit = model_rulebased_set_processing_unit;
1685   new_component->generic_routing.set_autonomous_system = model_rulebased_set_autonomous_system;
1686   new_component->generic_routing.set_route = model_rulebased_set_route;
1687   new_component->generic_routing.set_ASroute = model_rulebased_set_ASroute;
1688   new_component->generic_routing.set_bypassroute = model_rulebased_set_bypassroute;
1689   new_component->generic_routing.get_route = rulebased_get_route;
1690   new_component->generic_routing.get_bypass_route = NULL; //rulebased_get_bypass_route;
1691   new_component->generic_routing.finalize = rulebased_finalize;
1692   /* initialization of internal structures */
1693   new_component->dict_processing_units = xbt_dict_new();
1694   new_component->dict_autonomous_systems = xbt_dict_new();
1695   new_component->list_route = xbt_dynar_new(sizeof(rule_route_t), &rule_route_free);
1696   new_component->list_ASroute = xbt_dynar_new(sizeof(rule_route_extended_t), &rule_route_extended_free);
1697   return new_component;
1698 }
1699
1700 static void  model_rulebased_load(void) {
1701  /* use "surfxml_add_callback" to add a parse function call */
1702 }
1703
1704 static void  model_rulebased_unload(void) {
1705  /* use "surfxml_del_callback" to remove a parse function call */
1706 }
1707
1708 static void  model_rulebased_end(void) {
1709 }
1710
1711 /* ************************************************************************** */
1712 /* ******************************* NO ROUTING ******************************* */
1713
1714 /* Routing model structure */
1715 typedef struct {
1716   s_routing_component_t generic_routing;
1717 } s_routing_component_none_t,*routing_component_none_t;
1718
1719 /* Business methods */
1720 static route_extended_t none_get_route(routing_component_t rc, const char* src,const char* dst){
1721   return NULL;
1722 }
1723 static route_extended_t none_get_bypass_route(routing_component_t rc, const char* src,const char* dst){
1724   return NULL;
1725 }
1726 static void none_finalize(routing_component_t rc) {
1727   xbt_free(rc);
1728 }
1729
1730 static void none_set_processing_unit(routing_component_t rc, const char* name) {}
1731 static void none_set_autonomous_system(routing_component_t rc, const char* name) {}
1732
1733 /* Creation routing model functions */
1734 static void* model_none_create(void) {
1735   routing_component_none_t new_component =  xbt_new0(s_routing_component_none_t,1);
1736   new_component->generic_routing.set_processing_unit = none_set_processing_unit;
1737   new_component->generic_routing.set_autonomous_system = none_set_autonomous_system;
1738   new_component->generic_routing.set_route = NULL;
1739   new_component->generic_routing.set_ASroute = NULL;
1740   new_component->generic_routing.set_bypassroute = NULL;
1741   new_component->generic_routing.get_route = none_get_route;
1742   new_component->generic_routing.get_bypass_route = none_get_bypass_route;
1743   new_component->generic_routing.finalize = none_finalize;
1744   return new_component;
1745 }
1746
1747 static void  model_none_load(void) {}
1748 static void  model_none_unload(void) {}
1749 static void  model_none_end(void) {}
1750
1751 /* ************************************************** */
1752 /* ********** PATERN FOR NEW ROUTING **************** */
1753
1754 /* The minimal configuration of a new routing model need the next functions,
1755  * also you need to set at the start of the file, the new model in the model
1756  * list. Remember keep the null ending of the list.
1757  */
1758 /*** Routing model structure ***/
1759 // typedef struct {
1760 //   s_routing_component_t generic_routing;
1761 //   /* things that your routing model need */
1762 // } s_routing_component_NEW_t,*routing_component_NEW_t;
1763
1764 /*** Parse routing model functions ***/
1765 // static void model_NEW_set_processing_unit(routing_component_t rc, const char* name) {}
1766 // static void model_NEW_set_autonomous_system(routing_component_t rc, const char* name) {}
1767 // static void model_NEW_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {}
1768 // static void model_NEW_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t route) {}
1769 // static void model_NEW_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {}
1770
1771 /*** Business methods ***/
1772 // static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
1773 // static route_extended_t NEW_get_bypass_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
1774 // static void NEW_finalize(routing_component_t rc) { xbt_free(rc);}
1775
1776 /*** Creation routing model functions ***/
1777 // static void* model_NEW_create(void) {
1778 //   routing_component_NEW_t new_component =  xbt_new0(s_routing_component_NEW_t,1);
1779 //   new_component->generic_routing.set_processing_unit = model_NEW_set_processing_unit;
1780 //   new_component->generic_routing.set_autonomous_system = model_NEW_set_autonomous_system;
1781 //   new_component->generic_routing.set_route = model_NEW_set_route;
1782 //   new_component->generic_routing.set_ASroute = model_NEW_set_ASroute;
1783 //   new_component->generic_routing.set_bypassroute = model_NEW_set_bypassroute;
1784 //   new_component->generic_routing.get_route = NEW_get_route;
1785 //   new_component->generic_routing.get_bypass_route = NEW_get_bypass_route;
1786 //   new_component->generic_routing.finalize = NEW_finalize;
1787 //   /* initialization of internal structures */
1788 //   return new_component;
1789 // } /* mandatory */
1790 // static void  model_NEW_load(void) {}   /* mandatory */
1791 // static void  model_NEW_unload(void) {} /* mandatory */
1792 // static void  model_NEW_end(void) {}    /* mandatory */
1793
1794 /* ************************************************************************** */
1795 /* ************************* GENERIC PARSE FUNCTIONS ************************ */
1796
1797 static void generic_set_processing_unit(routing_component_t rc, const char* name) {
1798   DEBUG1("Load process unit \"%s\"",name);
1799   model_type_t modeltype = rc->routing;
1800   int *id = xbt_new0(int,1);
1801   xbt_dict_t _to_index;
1802   if(modeltype==&routing_models[SURF_MODEL_FULL])
1803     _to_index = ((routing_component_full_t)rc)->to_index;
1804
1805   else if(modeltype==&routing_models[SURF_MODEL_FLOYD])
1806     _to_index = ((routing_component_floyd_t)rc)->to_index;
1807
1808   else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1809           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE])
1810     _to_index = ((routing_component_dijkstra_t)rc)->to_index;
1811
1812   else xbt_die("\"generic_set_processing_unit\" not support");
1813   *id = xbt_dict_length(_to_index);
1814   xbt_dict_set(_to_index,name,id,xbt_free);
1815 }
1816
1817 static void generic_set_autonomous_system(routing_component_t rc, const char* name) {
1818   DEBUG1("Load Autonomous system \"%s\"",name);
1819   model_type_t modeltype = rc->routing;
1820   int *id = xbt_new0(int,1);
1821   xbt_dict_t _to_index;
1822   if(modeltype==&routing_models[SURF_MODEL_FULL])
1823     _to_index = ((routing_component_full_t)rc)->to_index;
1824
1825   else if(modeltype==&routing_models[SURF_MODEL_FLOYD])
1826     _to_index = ((routing_component_floyd_t)rc)->to_index;
1827
1828   else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1829           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE])
1830     _to_index = ((routing_component_dijkstra_t)rc)->to_index;
1831
1832   else xbt_die("\"generic_set_autonomous_system\" not support");
1833   *id = xbt_dict_length(_to_index);
1834   xbt_dict_set(_to_index,name,id,xbt_free);
1835 }
1836
1837 static void generic_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {
1838   DEBUG2("Load Route from \"%s\" to \"%s\"",src,dst);
1839   model_type_t modeltype = rc->routing;
1840   xbt_dict_t _parse_routes;
1841   xbt_dict_t _to_index;
1842   char *route_name;
1843   int *src_id, *dst_id;
1844
1845   if(modeltype==&routing_models[SURF_MODEL_FULL]) {
1846     _parse_routes = ((routing_component_full_t)rc)->parse_routes;
1847     _to_index = ((routing_component_full_t)rc)->to_index;
1848
1849   } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
1850     _parse_routes = ((routing_component_floyd_t)rc)->parse_routes;
1851     _to_index = ((routing_component_floyd_t)rc)->to_index;
1852
1853   } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1854           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
1855     _parse_routes = ((routing_component_dijkstra_t)rc)->parse_routes;
1856     _to_index = ((routing_component_dijkstra_t)rc)->to_index;
1857
1858   } else xbt_die("\"generic_set_route\" not support");
1859
1860   src_id = xbt_dict_get_or_null(_to_index, src);
1861   dst_id = xbt_dict_get_or_null(_to_index, dst);
1862
1863   xbt_assert2(src_id&&dst_id,"Network elements %s or %s not found", src, dst);
1864   route_name = bprintf("%d#%d",*src_id,*dst_id);
1865
1866   xbt_assert2(xbt_dynar_length(route->link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
1867   xbt_assert2(!xbt_dict_get_or_null(_parse_routes,route_name),
1868     "The route between \"%s\" and \"%s\" already exist",src,dst);
1869
1870   xbt_dict_set(_parse_routes, route_name, route, NULL);
1871   xbt_free(route_name);
1872 }
1873
1874 static void generic_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {
1875   DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"",src,e_route->src_gateway,dst,e_route->dst_gateway);
1876   model_type_t modeltype = rc->routing;
1877   xbt_dict_t _parse_routes;
1878   xbt_dict_t _to_index;
1879   char *route_name;
1880   int *src_id, *dst_id;
1881
1882   if(modeltype==&routing_models[SURF_MODEL_FULL]) {
1883     _parse_routes = ((routing_component_full_t)rc)->parse_routes;
1884     _to_index = ((routing_component_full_t)rc)->to_index;
1885
1886   } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
1887     _parse_routes = ((routing_component_floyd_t)rc)->parse_routes;
1888     _to_index = ((routing_component_floyd_t)rc)->to_index;
1889
1890   } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1891           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
1892     _parse_routes = ((routing_component_dijkstra_t)rc)->parse_routes;
1893     _to_index = ((routing_component_dijkstra_t)rc)->to_index;
1894
1895   } else xbt_die("\"generic_set_route\" not support");
1896
1897   src_id = xbt_dict_get_or_null(_to_index, src);
1898   dst_id = xbt_dict_get_or_null(_to_index, dst);
1899
1900   xbt_assert2(src_id&&dst_id,"Network elements %s or %s not found", src, dst);
1901   route_name = bprintf("%d#%d",*src_id,*dst_id);
1902
1903   xbt_assert2(xbt_dynar_length(e_route->generic_route.link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
1904   xbt_assert4(!xbt_dict_get_or_null(_parse_routes,route_name),
1905     "The route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exist",src,e_route->src_gateway,dst,e_route->dst_gateway);
1906
1907   xbt_dict_set(_parse_routes, route_name, e_route, NULL);
1908   xbt_free(route_name);
1909 }
1910
1911 static void generic_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {
1912   DEBUG2("Load bypassRoute from \"%s\" to \"%s\"",src,dst);
1913   model_type_t modeltype = rc->routing;
1914   xbt_dict_t dict_bypassRoutes;
1915   char *route_name;
1916   if(modeltype==&routing_models[SURF_MODEL_FULL]) {
1917     dict_bypassRoutes = ((routing_component_full_t)rc)->bypassRoutes;
1918   } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
1919     dict_bypassRoutes = ((routing_component_floyd_t)rc)->bypassRoutes;
1920   } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1921           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
1922     dict_bypassRoutes = ((routing_component_dijkstra_t)rc)->bypassRoutes;
1923   } else xbt_die("\"generic_set_bypassroute\" not support");
1924   route_name = bprintf("%s#%s",src,dst);
1925   xbt_assert2(xbt_dynar_length(e_route->generic_route.link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
1926   xbt_assert4(!xbt_dict_get_or_null(dict_bypassRoutes,route_name),
1927     "The bypass route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exist",src,e_route->src_gateway,dst,e_route->dst_gateway);
1928
1929   route_extended_t new_e_route = generic_new_extended_route(SURF_ROUTING_RECURSIVE,e_route,0);
1930   xbt_dynar_free( &(e_route->generic_route.link_list) );
1931   xbt_free(e_route);
1932
1933   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route, (void(*)(void*))generic_free_extended_route );
1934   xbt_free(route_name);
1935 }
1936
1937 /* ************************************************************************** */
1938 /* *********************** GENERIC BUSINESS METHODS ************************* */
1939
1940 static route_extended_t generic_get_bypassroute(routing_component_t rc, const char* src, const char* dst) {
1941   model_type_t modeltype = rc->routing;
1942   xbt_dict_t dict_bypassRoutes;
1943
1944   if(modeltype==&routing_models[SURF_MODEL_FULL]) {
1945     dict_bypassRoutes = ((routing_component_full_t)rc)->bypassRoutes;
1946   } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
1947     dict_bypassRoutes = ((routing_component_floyd_t)rc)->bypassRoutes;
1948   } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1949           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
1950     dict_bypassRoutes = ((routing_component_dijkstra_t)rc)->bypassRoutes;
1951   } else xbt_die("\"generic_set_bypassroute\" not support");
1952
1953
1954   routing_component_t src_as, dst_as;
1955   int index_src, index_dst;
1956   xbt_dynar_t path_src = NULL;
1957   xbt_dynar_t path_dst = NULL;
1958   routing_component_t current = NULL;
1959   routing_component_t* current_src = NULL;
1960   routing_component_t* current_dst = NULL;
1961
1962   /* (1) find the as where the src and dst are located */
1963   src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
1964   dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
1965   xbt_assert2(src_as&&dst_as, "Ask for route \"from\"(%s) or \"to\"(%s) no found",src,dst);
1966
1967   /* (2) find the path to the root routing component */
1968   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
1969   current = src_as;
1970   while( current != NULL ) {
1971     xbt_dynar_push(path_src,&current);
1972     current = current->routing_father;
1973   }
1974   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
1975   current = dst_as;
1976   while( current != NULL ) {
1977     xbt_dynar_push(path_dst,&current);
1978     current = current->routing_father;
1979   }
1980
1981   /* (3) find the common father */
1982   index_src  = (path_src->used)-1;
1983   index_dst  = (path_dst->used)-1;
1984   current_src = xbt_dynar_get_ptr(path_src,index_src);
1985   current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
1986   while( index_src >= 0 && index_dst >= 0 && *current_src == *current_dst ) {
1987     routing_component_t *tmp_src,*tmp_dst;
1988     tmp_src = xbt_dynar_pop_ptr(path_src);
1989     tmp_dst = xbt_dynar_pop_ptr(path_dst);
1990     index_src--;
1991     index_dst--;
1992     current_src = xbt_dynar_get_ptr(path_src,index_src);
1993     current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
1994   }
1995
1996   int max_index_src = (path_src->used)-1;
1997   int max_index_dst = (path_dst->used)-1;
1998
1999   int max_index = max(max_index_src,max_index_dst);
2000   int i, max;
2001
2002  route_extended_t e_route_bypass = NULL;
2003
2004   for( max=0;max<=max_index;max++)
2005   {
2006     for(i=0;i<max;i++)
2007     {
2008       if( i <= max_index_src  && max <= max_index_dst ) {
2009         char* route_name = bprintf("%s#%s",
2010           (*(routing_component_t*)(xbt_dynar_get_ptr(path_src,i)))->name,
2011           (*(routing_component_t*)(xbt_dynar_get_ptr(path_dst,max)))->name);
2012         e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes,route_name);
2013         xbt_free(route_name);
2014       }
2015       if( e_route_bypass ) break;
2016       if( max <= max_index_src  && i <= max_index_dst ) {
2017         char* route_name = bprintf("%s#%s",
2018           (*(routing_component_t*)(xbt_dynar_get_ptr(path_src,max)))->name,
2019           (*(routing_component_t*)(xbt_dynar_get_ptr(path_dst,i)))->name);
2020         e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes,route_name);
2021         xbt_free(route_name);
2022       }
2023       if( e_route_bypass ) break;
2024     }
2025
2026     if( e_route_bypass ) break;
2027
2028     if( max <= max_index_src  && max <= max_index_dst ) {
2029       char* route_name = bprintf("%s#%s",
2030         (*(routing_component_t*)(xbt_dynar_get_ptr(path_src,max)))->name,
2031         (*(routing_component_t*)(xbt_dynar_get_ptr(path_dst,max)))->name);
2032       e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes,route_name);
2033       xbt_free(route_name);
2034     }
2035     if( e_route_bypass ) break;
2036   }
2037
2038   xbt_dynar_free(&path_src);
2039   xbt_dynar_free(&path_dst);
2040
2041   route_extended_t new_e_route = NULL;
2042
2043   if(e_route_bypass) {
2044     void* link;
2045     unsigned int cpt=0;
2046     new_e_route = xbt_new0(s_route_extended_t,1);
2047     new_e_route->src_gateway = xbt_strdup(e_route_bypass->src_gateway);
2048     new_e_route->dst_gateway = xbt_strdup(e_route_bypass->dst_gateway);
2049     new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
2050     xbt_dynar_foreach(e_route_bypass->generic_route.link_list, cpt, link) {
2051       xbt_dynar_push(new_e_route->generic_route.link_list,&link);
2052     }
2053   }
2054
2055   return new_e_route;
2056 }
2057
2058 /* ************************************************************************** */
2059 /* ************************* GENERIC AUX FUNCTIONS ************************** */
2060
2061 static route_extended_t generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy, void* data, int order) {
2062
2063   char *link_name;
2064   route_extended_t e_route, new_e_route;
2065   route_t route;
2066   unsigned int cpt;
2067   xbt_dynar_t links, links_id;
2068
2069   new_e_route = xbt_new0(s_route_extended_t,1);
2070   new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
2071   new_e_route->src_gateway = NULL;
2072   new_e_route->dst_gateway = NULL;
2073
2074   xbt_assert0(hierarchy == SURF_ROUTING_BASE || hierarchy == SURF_ROUTING_RECURSIVE,
2075       "the hierarchy type is not defined");
2076
2077   if(hierarchy == SURF_ROUTING_BASE ) {
2078
2079     route = (route_t)data;
2080     links = route->link_list;
2081
2082   } else if(hierarchy == SURF_ROUTING_RECURSIVE ) {
2083
2084     e_route = (route_extended_t)data;
2085     xbt_assert0(e_route->src_gateway&&e_route->dst_gateway,"bad gateway, is null");
2086     links = e_route->generic_route.link_list;
2087
2088     /* remeber not erase the gateway names */
2089     new_e_route->src_gateway = e_route->src_gateway;
2090     new_e_route->dst_gateway = e_route->dst_gateway;
2091   }
2092
2093   links_id = new_e_route->generic_route.link_list;
2094
2095   xbt_dynar_foreach(links, cpt, link_name) {
2096
2097     void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
2098     if (link)
2099     {
2100       if( order )
2101         xbt_dynar_push(links_id,&link);
2102       else
2103         xbt_dynar_unshift(links_id,&link);
2104     }
2105     else
2106       THROW1(mismatch_error,0,"Link %s not found", link_name);
2107   }
2108
2109   return new_e_route;
2110 }
2111
2112 static void generic_free_route(route_t route) {
2113   if(route) {
2114     xbt_dynar_free(&(route->link_list));
2115     xbt_free(route);
2116   }
2117 }
2118
2119 static void generic_free_extended_route(route_extended_t e_route) {
2120   if(e_route) {
2121     xbt_dynar_free(&(e_route->generic_route.link_list));
2122     if(e_route->src_gateway) xbt_free(e_route->src_gateway);
2123     if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
2124     xbt_free(e_route);
2125   }
2126 }
2127
2128 static routing_component_t generic_as_exist(routing_component_t find_from, routing_component_t to_find) {
2129   //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
2130   xbt_dict_cursor_t cursor = NULL;
2131   char *key;
2132   int found=0;
2133   routing_component_t elem;
2134   xbt_dict_foreach(find_from->routing_sons, cursor, key, elem) {
2135     if( to_find == elem || generic_as_exist(elem,to_find) ){
2136       found=1;
2137       break;
2138     }
2139   }
2140   if(found) return to_find;
2141   return NULL;
2142 }
2143
2144 static routing_component_t generic_autonomous_system_exist(routing_component_t rc, char* element) {
2145   //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
2146   routing_component_t element_as, result, elem;
2147   xbt_dict_cursor_t cursor = NULL;
2148   char *key;
2149   element_as = xbt_dict_get_or_null(global_routing->where_network_elements,element);
2150   result = ((routing_component_t)-1);
2151   if(element_as!=rc)
2152     result = generic_as_exist(rc,element_as);
2153
2154   int found=0;
2155   if(result)
2156   {
2157     xbt_dict_foreach(element_as->routing_sons, cursor, key, elem) {
2158       found = !strcmp(elem->name,element);
2159       if( found ) break;
2160     }
2161     if( found ) return element_as;
2162   }
2163   return NULL;
2164 }
2165
2166 static routing_component_t generic_processing_units_exist(routing_component_t rc, char* element) {
2167   routing_component_t element_as;
2168   element_as = xbt_dict_get_or_null(global_routing->where_network_elements,element);
2169   if(element_as==rc) return element_as;
2170   return generic_as_exist(rc,element_as);
2171 }
2172
2173 static void generic_src_dst_check(routing_component_t rc, const char* src, const char* dst) {
2174
2175   routing_component_t src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
2176   routing_component_t dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
2177
2178   xbt_assert3(src_as != NULL && dst_as  != NULL,
2179       "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",src,dst,rc->name);
2180   xbt_assert4(src_as == dst_as,
2181       "The src(%s in %s) and dst(%s in %s) are in differents AS",src,src_as->name,dst,dst_as->name);
2182   xbt_assert2(rc == dst_as,
2183       "The routing component of src and dst is not the same as the network elements belong (%s==%s)",rc->name,dst_as->name);
2184 }