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