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