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
   8
   9 #include <float.h>
  10 #include "gras_config.h"
  11
  12 #ifdef HAVE_PCRE_LIB
  13 #include <pcre.h>               /* regular expresion library */
  14 #endif
  15 #include "surf_private.h"
  16 #include "xbt/dynar.h"
  17 #include "xbt/str.h"
  18 #include "xbt/config.h"
  19 #include "xbt/graph.h"
  20 #include "xbt/set.h"
  21
  22 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route, surf, "Routing part of surf");
  23
  24 /* Global vars */
  25 routing_global_t global_routing = NULL;
  26 routing_component_t current_routing = NULL;
  27 model_type_t current_routing_model = NULL;
  28 static double_f_cpvoid_t get_link_latency = NULL;
  29
  30 /* Prototypes of each model */
  31 static void *model_full_create(void);   /* create structures for full routing model */
  32 static void model_full_load(void);      /* load parse functions for full routing model */
  33 static void model_full_unload(void);    /* unload parse functions for full routing model */
  34 static void model_full_end(void);       /* finalize the creation of full routing model */
  35 static void model_full_set_route(               /* Set the route and ASroute between src and dst */
  36                 routing_component_t rc, const char *src, const char *dst, name_route_extended_t route);
  37
  38 static void *model_floyd_create(void);  /* create structures for floyd routing model */
  39 static void model_floyd_load(void);     /* load parse functions for floyd routing model */
  40 static void model_floyd_unload(void);   /* unload parse functions for floyd routing model */
  41 static void model_floyd_end(void);      /* finalize the creation of floyd routing model */
  42 static void model_floyd_set_route(routing_component_t rc, const char *src,
  43         const char *dst, name_route_extended_t route);
  44
  45 static void *model_dijkstra_both_create(int cached);    /* create by calling dijkstra or dijkstracache */
  46 static void *model_dijkstra_create(void);       /* create structures for dijkstra routing model */
  47 static void *model_dijkstracache_create(void);  /* create structures for dijkstracache routing model */
  48 static void model_dijkstra_both_load(void);     /* load parse functions for dijkstra routing model */
  49 static void model_dijkstra_both_unload(void);   /* unload parse functions for dijkstra routing model */
  50 static void model_dijkstra_both_end(void);      /* finalize the creation of dijkstra routing model */
  51 static void model_dijkstra_both_set_route (routing_component_t rc, const char *src,
  52                      const char *dst, name_route_extended_t route);
  53
  54 static void *model_rulebased_create(void);      /* create structures for rulebased routing model */
  55 static void model_rulebased_load(void); /* load parse functions for rulebased routing model */
  56 static void model_rulebased_unload(void);       /* unload parse functions for rulebased routing model */
  57 static void model_rulebased_end(void);  /* finalize the creation of rulebased routing model */
  58
  59 static void *model_none_create(void);   /* none routing model */
  60 static void model_none_load(void);      /* none routing model */
  61 static void model_none_unload(void);    /* none routing model */
  62 static void model_none_end(void);       /* none routing model */
  63
  64 static void routing_parse_Scluster(void);  /*cluster bypass */
  65 static void routing_parse_Speer(void);          /*peer bypass */
  66
  67 static void routing_parse_Sconfig(void);        /*config Tag */
  68 static void routing_parse_Econfig(void);        /*config Tag */
  69
  70 /* this lines are only for replace use like index in the model table */
  71 typedef enum {
  72   SURF_MODEL_FULL = 0,
  73   SURF_MODEL_FLOYD,
  74   SURF_MODEL_DIJKSTRA,
  75   SURF_MODEL_DIJKSTRACACHE,
  76   SURF_MODEL_NONE,
  77 #ifdef HAVE_PCRE_LIB
  78   SURF_MODEL_RULEBASED
  79 #endif
  80 } e_routing_types;
  81
  82
  83 /* must be finish with null and carefull if change de order */
  84 struct s_model_type routing_models[] = { {"Full",
  85                                           "Full routing data (fast, large memory requirements, fully expressive)",
  86                                           model_full_create,
  87                                           model_full_load,
  88                                           model_full_unload,
  89                                           model_full_end},
  90 {"Floyd",
  91  "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)",
  92  model_floyd_create, model_floyd_load, model_floyd_unload,
  93  model_floyd_end},
  94 {"Dijkstra",
  95  "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)",
  96  model_dijkstra_create, model_dijkstra_both_load,
  97  model_dijkstra_both_unload, model_dijkstra_both_end},
  98 {"DijkstraCache",
  99  "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)",
 100  model_dijkstracache_create, model_dijkstra_both_load,
 101  model_dijkstra_both_unload, model_dijkstra_both_end},
 102 {"none", "No routing (usable with Constant network only)",
 103  model_none_create, model_none_load, model_none_unload, model_none_end},
 104 #ifdef HAVE_PCRE_LIB
 105 {"RuleBased", "Rule-Based routing data (...)", model_rulebased_create,
 106  model_rulebased_load, model_rulebased_unload, model_rulebased_end},
 107 {"Vivaldi", "Vivaldi routing", model_rulebased_create,
 108   model_rulebased_load, model_rulebased_unload, model_rulebased_end},
 109 #endif
 110 {NULL, NULL, NULL, NULL, NULL, NULL}
 111 };
 112
 113 /* ************************************************************************** */
 114 /* ***************** GENERIC PARSE FUNCTIONS (declarations) ***************** */
 115
 116 static void generic_set_processing_unit(routing_component_t rc,
 117                                         const char *name);
 118 static void generic_set_autonomous_system(routing_component_t rc,
 119                                           const char *name);
 120 static void generic_set_bypassroute(routing_component_t rc,
 121                                     const char *src, const char *dst,
 122                                     route_extended_t e_route);
 123
 124 static int surf_link_resource_cmp(const void *a, const void *b);
 125 static int surf_pointer_resource_cmp(const void *a, const void *b);
 126
 127 /* ************************************************************************** */
 128 /* *************** GENERIC BUSINESS METHODS (declarations) ****************** */
 129
 130 static double generic_get_link_latency(routing_component_t rc, const char *src, const char *dst);
 131 static xbt_dynar_t generic_get_onelink_routes(routing_component_t rc);
 132 static route_extended_t generic_get_bypassroute(routing_component_t rc,
 133                                                 const char *src,
 134                                                 const char *dst);
 135
 136 /* ************************************************************************** */
 137 /* ****************** GENERIC AUX FUNCTIONS (declarations) ****************** */
 138
 139 static route_extended_t
 140 generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy,
 141                            void *data, int order);
 142 static route_t
 143 generic_new_route(e_surf_routing_hierarchy_t hierarchy,
 144                            void *data, int order);
 145 static void generic_free_route(route_t route);
 146 static void generic_free_extended_route(route_extended_t e_route);
 147 static routing_component_t
 148 generic_autonomous_system_exist(routing_component_t rc, char *element);
 149 static routing_component_t
 150 generic_processing_units_exist(routing_component_t rc, char *element);
 151 static void generic_src_dst_check(routing_component_t rc, const char *src,
 152                                   const char *dst);
 153
 154 /* ************************************************************************** */
 155 /* **************************** GLOBAL FUNCTIONS **************************** */
 156
 157 /* global parse functions */
 158 static const char *src = NULL;        /* temporary store the source name of a route */
 159 static const char *dst = NULL;        /* temporary store the destination name of a route */
 160 static char *gw_src = NULL;     /* temporary store the gateway source name of a route */
 161 static char *gw_dst = NULL;     /* temporary store the gateway destination name of a route */
 162 static xbt_dynar_t link_list = NULL;    /* temporary store of current list link of a route */
 163
 164 static xbt_dict_t coordinates = NULL;
 165
 166
 167 static double eculidean_dist_comp(int index, xbt_dynar_t src, xbt_dynar_t dst)
 168 {
 169         double src_coord, dst_coord;
 170
 171         src_coord = atof(xbt_dynar_get_as(src, index, char *));
 172         dst_coord = atof(xbt_dynar_get_as(dst, index, char *));
 173
 174         return (src_coord-dst_coord)*(src_coord-dst_coord);
 175
 176 }
 177
 178 static double vivaldi_get_link_latency (routing_component_t rc,
 179                                                                                                                                                                 const char *src, const char *dst)
 180 {
 181   double euclidean_dist;
 182   xbt_dynar_t src_ctn, dst_ctn;
 183   src_ctn = xbt_dict_get(coordinates, src);
 184   dst_ctn = xbt_dict_get(coordinates, dst);
 185
 186   euclidean_dist = sqrt (eculidean_dist_comp(0,src_ctn,dst_ctn)+eculidean_dist_comp(1,src_ctn,dst_ctn))
 187                                                                 +fabs(atof(xbt_dynar_get_as(src_ctn, 2, char *)))+fabs(atof(xbt_dynar_get_as(dst_ctn, 2, char *)));
 188
 189   xbt_assert2(euclidean_dist>=0, "Euclidean Dist is less than 0\"%s\" and \"%.2f\"", src, euclidean_dist);
 190
 191   return euclidean_dist;
 192
 193   /*
 194   x = atof(xbt_dynar_get_as(src_ctn, 0, char *))-atof(xbt_dynar_get_as(dst_ctn, 0, char *));
 195   y = atof(xbt_dynar_get_as(src_ctn, 1, char *));
 196   h = atof(xbt_dynar_get_as(ctn, 2, char *));
 197   sqrt((c1->x - c2->x) * (c1->x - c2->x) + (c1->y - c2->y) * (c1->y - c2->y)) + fabs(c1->h) + fabs(c2->h);
 198
 199           if (strcmp(coord,"")) {
 200         xbt_dynar_t ctn = xbt_str_split_str(coord, " ");
 201         xbt_dynar_shrink(ctn,0);
 202         xbt_dict_set (coordinates,host_id,ctn,NULL);
 203   }
 204         */
 205 }
 206
 207 /**
 208  * \brief Add a "host" to the network element list
 209  */
 210 static void parse_S_host(const char *host_id, const char* coord)
 211 {
 212   network_element_info_t info = NULL;
 213   if (current_routing->hierarchy == SURF_ROUTING_NULL)
 214     current_routing->hierarchy = SURF_ROUTING_BASE;
 215   xbt_assert1(!xbt_dict_get_or_null
 216               (global_routing->where_network_elements, host_id),
 217               "Reading a host, processing unit \"%s\" already exists",
 218               host_id);
 219   xbt_assert1(current_routing->set_processing_unit,
 220               "no defined method \"set_processing_unit\" in \"%s\"",
 221               current_routing->name);
 222   (*(current_routing->set_processing_unit)) (current_routing, host_id);
 223   info = xbt_new0(s_network_element_info_t, 1);
 224   info->rc_component = current_routing;
 225   info->rc_type = SURF_NETWORK_ELEMENT_HOST;
 226   xbt_dict_set(global_routing->where_network_elements, host_id,
 227                (void *) info, xbt_free);
 228
 229   if (strcmp(coord,"")) {
 230         xbt_dynar_t ctn = xbt_str_split_str(coord, " ");
 231         xbt_dynar_shrink(ctn,0);
 232         xbt_dict_set (coordinates,host_id,ctn,NULL);
 233   }
 234 }
 235
 236 /*
 237  * \brief Add a host to the network element list from XML
 238  */
 239 static void parse_S_host_XML(void)
 240 {
 241         parse_S_host(A_surfxml_host_id, A_surfxml_host_coordinates);
 242 }
 243
 244 /*
 245  * \brief Add a host to the network element list from lua script
 246  */
 247 static void parse_S_host_lua(const char *host_id, const char *coord)
 248 {
 249   parse_S_host(host_id, coord);
 250 }
 251
 252
 253 /**
 254  * \brief Add a "router" to the network element list
 255  */
 256 static void parse_S_router(void)
 257 {
 258   network_element_info_t info = NULL;
 259
 260   if (current_routing->hierarchy == SURF_ROUTING_NULL)
 261     current_routing->hierarchy = SURF_ROUTING_BASE;
 262   xbt_assert1(!xbt_dict_get_or_null
 263               (global_routing->where_network_elements,
 264                A_surfxml_router_id),
 265               "Reading a router, processing unit \"%s\" already exists",
 266               A_surfxml_router_id);
 267   xbt_assert1(current_routing->set_processing_unit,
 268               "no defined method \"set_processing_unit\" in \"%s\"",
 269               current_routing->name);
 270   (*(current_routing->set_processing_unit)) (current_routing,
 271                                              A_surfxml_router_id);
 272   info = xbt_new0(s_network_element_info_t, 1);
 273   info->rc_component = current_routing;
 274   info->rc_type = SURF_NETWORK_ELEMENT_ROUTER;
 275   xbt_dict_set(global_routing->where_network_elements, A_surfxml_router_id,
 276                (void *) info, xbt_free);
 277 #ifdef HAVE_TRACING
 278   TRACE_surf_host_declaration(A_surfxml_router_id, 0);
 279 #endif
 280   if (strcmp(A_surfxml_router_coordinates,"")) {
 281         xbt_dynar_t ctn = xbt_str_split_str(A_surfxml_router_coordinates, " ");
 282         xbt_dynar_shrink(ctn,0);
 283         xbt_dict_set (coordinates,A_surfxml_router_id,ctn,NULL);
 284   }
 285 }
 286
 287 /**
 288  * \brief Set the endponints for a route
 289  */
 290 static void parse_S_route_new_and_endpoints(const char *src_id, const char *dst_id)
 291 {
 292   if (src != NULL && dst != NULL && link_list != NULL)
 293     THROW2(arg_error, 0, "Route between %s to %s can not be defined",
 294            src_id, dst_id);
 295   src = src_id;
 296   dst = dst_id;
 297   xbt_assert2(strlen(src) > 0 || strlen(dst) > 0,
 298               "Some limits are null in the route between \"%s\" and \"%s\"",
 299               src, dst);
 300   link_list = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
 301 }
 302
 303 /**
 304  * \brief Set the endpoints for a route from XML
 305  */
 306 static void parse_S_route_new_and_endpoints_XML(void)
 307 {
 308   parse_S_route_new_and_endpoints(A_surfxml_route_src,
 309                                   A_surfxml_route_dst);
 310 }
 311
 312 /**
 313  * \brief Set the endpoints for a route from lua
 314  */
 315 static void parse_S_route_new_and_endpoints_lua(const char *id_src, const char *id_dst)
 316 {
 317   parse_S_route_new_and_endpoints(id_src, id_dst);
 318 }
 319
 320 /**
 321  * \brief Set the endponints and gateways for a ASroute
 322  */
 323 static void parse_S_ASroute_new_and_endpoints(void)
 324 {
 325   if (src != NULL && dst != NULL && link_list != NULL)
 326     THROW2(arg_error, 0, "Route between %s to %s can not be defined",
 327            A_surfxml_ASroute_src, A_surfxml_ASroute_dst);
 328   src = A_surfxml_ASroute_src;
 329   dst = A_surfxml_ASroute_dst;
 330   gw_src = A_surfxml_ASroute_gw_src;
 331   gw_dst = A_surfxml_ASroute_gw_dst;
 332   xbt_assert2(strlen(src) > 0 || strlen(dst) > 0 || strlen(gw_src) > 0
 333               || strlen(gw_dst) > 0,
 334               "Some limits are null in the route between \"%s\" and \"%s\"",
 335               src, dst);
 336   link_list = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
 337 }
 338
 339 /**
 340  * \brief Set the endponints for a bypassRoute
 341  */
 342 static void parse_S_bypassRoute_new_and_endpoints(void)
 343 {
 344   if (src != NULL && dst != NULL && link_list != NULL)
 345     THROW2(arg_error, 0,
 346            "Bypass Route between %s to %s can not be defined",
 347            A_surfxml_bypassRoute_src, A_surfxml_bypassRoute_dst);
 348   src = A_surfxml_bypassRoute_src;
 349   dst = A_surfxml_bypassRoute_dst;
 350   gw_src = A_surfxml_bypassRoute_gw_src;
 351   gw_dst = A_surfxml_bypassRoute_gw_dst;
 352   xbt_assert2(strlen(src) > 0 || strlen(dst) > 0 || strlen(gw_src) > 0
 353               || strlen(gw_dst) > 0,
 354               "Some limits are null in the route between \"%s\" and \"%s\"",
 355               src, dst);
 356   link_list = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
 357 }
 358
 359 /**
 360  * \brief Set a new link on the actual list of link for a route or ASroute
 361  */
 362 static void parse_E_link_ctn_new_elem(const char *link_id)
 363 {
 364   char *val;
 365   val = xbt_strdup(link_id);
 366   xbt_dynar_push(link_list, &val);
 367 }
 368
 369 /**
 370  * \brief Set a new link on the actual list of link for a route or ASroute from XML
 371  */
 372
 373 static void parse_E_link_ctn_new_elem_XML(void)
 374 {
 375   if (A_surfxml_link_ctn_direction == A_surfxml_link_ctn_direction_NONE)
 376     parse_E_link_ctn_new_elem(A_surfxml_link_ctn_id);
 377   if (A_surfxml_link_ctn_direction == A_surfxml_link_ctn_direction_UP) {
 378     char *link_id = bprintf("%s_UP", A_surfxml_link_ctn_id);
 379     parse_E_link_ctn_new_elem(link_id);
 380     free(link_id);
 381   }
 382   if (A_surfxml_link_ctn_direction == A_surfxml_link_ctn_direction_DOWN) {
 383     char *link_id = bprintf("%s_DOWN", A_surfxml_link_ctn_id);
 384     parse_E_link_ctn_new_elem(link_id);
 385     free(link_id);
 386   }
 387 }
 388
 389 /**
 390  * \brief Set a new link on the actual list of link for a route or ASroute from lua
 391  */
 392 static void parse_E_link_c_ctn_new_elem_lua(const char *link_id)
 393 {
 394   parse_E_link_ctn_new_elem(link_id);
 395 }
 396
 397 /**
 398  * \brief Store the route by calling the set_route function of the current routing component
 399  */
 400 static void parse_E_route_store_route(void)
 401 {
 402   name_route_extended_t route = xbt_new0(s_name_route_extended_t, 1);
 403   route->generic_route.link_list = link_list;
 404   xbt_assert1(current_routing->set_route,
 405               "no defined method \"set_route\" in \"%s\"",
 406               current_routing->name);
 407   (*(current_routing->set_route)) (current_routing, src, dst, route);
 408   link_list = NULL;
 409   src = NULL;
 410   dst = NULL;
 411 }
 412
 413 /**
 414  * \brief Store the ASroute by calling the set_ASroute function of the current routing component
 415  */
 416 static void parse_E_ASroute_store_route(void)
 417 {
 418   name_route_extended_t e_route = xbt_new0(s_name_route_extended_t, 1);
 419   e_route->generic_route.link_list = link_list;
 420   e_route->src_gateway = xbt_strdup(gw_src);
 421   e_route->dst_gateway = xbt_strdup(gw_dst);
 422   xbt_assert1(current_routing->set_ASroute,
 423               "no defined method \"set_ASroute\" in \"%s\"",
 424               current_routing->name);
 425   (*(current_routing->set_ASroute)) (current_routing, src, dst, e_route);
 426   link_list = NULL;
 427   src = NULL;
 428   dst = NULL;
 429   gw_src = NULL;
 430   gw_dst = NULL;
 431 }
 432
 433 /**
 434  * \brief Store the bypass route by calling the set_bypassroute function of the current routing component
 435  */
 436 static void parse_E_bypassRoute_store_route(void)
 437 {
 438   route_extended_t e_route = xbt_new0(s_route_extended_t, 1);
 439   e_route->generic_route.link_list = link_list;
 440   e_route->src_gateway = xbt_strdup(gw_src);
 441   e_route->dst_gateway = xbt_strdup(gw_dst);
 442   xbt_assert1(current_routing->set_bypassroute,
 443               "no defined method \"set_bypassroute\" in \"%s\"",
 444               current_routing->name);
 445   (*(current_routing->set_bypassroute)) (current_routing, src, dst,
 446                                          e_route);
 447   link_list = NULL;
 448   src = NULL;
 449   dst = NULL;
 450   gw_src = NULL;
 451   gw_dst = NULL;
 452 }
 453
 454 /**
 455  * \brief Make a new routing component
 456  *
 457  * make the new structure and
 458  * set the parsing functions to allows parsing the part of the routing tree
 459  */
 460 static void parse_S_AS(char *AS_id, char *AS_routing)
 461 {
 462   routing_component_t new_routing;
 463   model_type_t model = NULL;
 464   char *wanted = AS_routing;
 465   int cpt;
 466   /* seach the routing model */
 467   for (cpt = 0; routing_models[cpt].name; cpt++)
 468     if (!strcmp(wanted, routing_models[cpt].name))
 469       model = &routing_models[cpt];
 470   /* if its not exist, error */
 471   if (model == NULL) {
 472     fprintf(stderr, "Routing model %s not found. Existing models:\n",
 473             wanted);
 474     for (cpt = 0; routing_models[cpt].name; cpt++)
 475       if (!strcmp(wanted, routing_models[cpt].name))
 476         fprintf(stderr, "   %s: %s\n", routing_models[cpt].name,
 477                 routing_models[cpt].desc);
 478     xbt_die(NULL);
 479   }
 480
 481   /* make a new routing component */
 482   new_routing = (routing_component_t) (*(model->create)) ();
 483   new_routing->routing = model;
 484   new_routing->hierarchy = SURF_ROUTING_NULL;
 485   new_routing->name = xbt_strdup(AS_id);
 486   new_routing->routing_sons = xbt_dict_new();
 487
 488   /* Hack for Vivaldi */
 489   if(!strcmp(model->name,"Vivaldi"))
 490         new_routing->get_latency = vivaldi_get_link_latency;
 491
 492   if (current_routing == NULL && global_routing->root == NULL) {
 493
 494     /* it is the first one */
 495     new_routing->routing_father = NULL;
 496     global_routing->root = new_routing;
 497
 498   } else if (current_routing != NULL && global_routing->root != NULL) {
 499
 500     xbt_assert1(!xbt_dict_get_or_null
 501                 (current_routing->routing_sons, AS_id),
 502                 "The AS \"%s\" already exists", AS_id);
 503     /* it is a part of the tree */
 504     new_routing->routing_father = current_routing;
 505     /* set the father behavior */
 506     if (current_routing->hierarchy == SURF_ROUTING_NULL)
 507       current_routing->hierarchy = SURF_ROUTING_RECURSIVE;
 508     /* add to the sons dictionary */
 509     xbt_dict_set(current_routing->routing_sons, AS_id,
 510                  (void *) new_routing, NULL);
 511     /* add to the father element list */
 512     (*(current_routing->set_autonomous_system)) (current_routing, AS_id);
 513     /* unload the prev parse rules */
 514     (*(current_routing->routing->unload)) ();
 515
 516   } else {
 517     THROW0(arg_error, 0, "All defined components must be belong to a AS");
 518   }
 519   /* set the new parse rules */
 520   (*(new_routing->routing->load)) ();
 521   /* set the new current component of the tree */
 522   current_routing = new_routing;
 523 }
 524
 525 /*
 526  * Detect the routing model type of the routing component from XML platforms
 527  */
 528 static void parse_S_AS_XML(void)
 529 {
 530   parse_S_AS(A_surfxml_AS_id, A_surfxml_AS_routing);
 531 }
 532
 533 /*
 534  * define the routing model type of routing component from lua script
 535  */
 536 static void parse_S_AS_lua(char *id, char *mode)
 537 {
 538   parse_S_AS(id, mode);
 539 }
 540
 541
 542 /**
 543  * \brief Finish the creation of a new routing component
 544  *
 545  * When you finish to read the routing component, other structures must be created.
 546  * the "end" method allow to do that for any routing model type
 547  */
 548 static void parse_E_AS(const char *AS_id)
 549 {
 550
 551   if (current_routing == NULL) {
 552     THROW1(arg_error, 0, "Close AS(%s), that never open", AS_id);
 553   } else {
 554     network_element_info_t info = NULL;
 555     xbt_assert1(!xbt_dict_get_or_null
 556                 (global_routing->where_network_elements,
 557                  current_routing->name), "The AS \"%s\" already exists",
 558                 current_routing->name);
 559     info = xbt_new0(s_network_element_info_t, 1);
 560     info->rc_component = current_routing->routing_father;
 561     info->rc_type = SURF_NETWORK_ELEMENT_AS;
 562     xbt_dict_set(global_routing->where_network_elements,
 563                  current_routing->name, info, xbt_free);
 564     (*(current_routing->routing->unload)) ();
 565     (*(current_routing->routing->end)) ();
 566     current_routing = current_routing->routing_father;
 567     if (current_routing != NULL)
 568       (*(current_routing->routing->load)) ();
 569   }
 570 }
 571
 572 /*
 573  * \brief Finish the creation of a new routing component from XML
 574  */
 575 static void parse_E_AS_XML(void)
 576 {
 577   parse_E_AS(A_surfxml_AS_id);
 578 }
 579
 580 /*
 581  * \brief Finish the creation of a new routing component from lua
 582  */
 583 static void parse_E_AS_lua(const char *id)
 584 {
 585   parse_E_AS(id);
 586 }
 587
 588 /* Aux Business methods */
 589
 590 /**
 591  * \brief Get the AS father and the first elements of the chain
 592  *
 593  * \param src the source host name
 594  * \param dst the destination host name
 595  *
 596  * Get the common father of the to processing units, and the first different
 597  * father in the chain
 598  */
 599 static xbt_dynar_t elements_father(const char *src, const char *dst)
 600 {
 601
 602   xbt_assert0(src && dst, "bad parameters for \"elements_father\" method");
 603
 604   xbt_dynar_t result = xbt_dynar_new(sizeof(char *), NULL);
 605
 606   routing_component_t src_as, dst_as;
 607   int index_src, index_dst, index_father_src, index_father_dst;
 608   xbt_dynar_t path_src = NULL;
 609   xbt_dynar_t path_dst = NULL;
 610   routing_component_t current = NULL;
 611   routing_component_t *current_src = NULL;
 612   routing_component_t *current_dst = NULL;
 613   routing_component_t *father = NULL;
 614
 615   /* (1) find the as where the src and dst are located */
 616   src_as = ((network_element_info_t)
 617             xbt_dict_get_or_null(global_routing->where_network_elements,
 618                                  src))->rc_component;
 619   dst_as = ((network_element_info_t)
 620             xbt_dict_get_or_null(global_routing->where_network_elements,
 621                                  dst))->rc_component;
 622   xbt_assert2(src_as
 623               && dst_as,
 624               "Ask for route \"from\"(%s) or \"to\"(%s) no found", src,
 625               dst);
 626
 627   /* (2) find the path to the root routing component */
 628   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
 629   current = src_as;
 630   while (current != NULL) {
 631     xbt_dynar_push(path_src, &current);
 632     current = current->routing_father;
 633   }
 634   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
 635   current = dst_as;
 636   while (current != NULL) {
 637     xbt_dynar_push(path_dst, &current);
 638     current = current->routing_father;
 639   }
 640
 641   /* (3) find the common father */
 642   index_src = path_src->used - 1;
 643   index_dst = path_dst->used - 1;
 644   current_src = xbt_dynar_get_ptr(path_src, index_src);
 645   current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
 646   while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
 647     current_src = xbt_dynar_get_ptr(path_src, index_src);
 648     current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
 649     index_src--;
 650     index_dst--;
 651   }
 652   index_src++;
 653   index_dst++;
 654   current_src = xbt_dynar_get_ptr(path_src, index_src);
 655   current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
 656
 657   /* (4) they are not in the same routing component, make the path */
 658   index_father_src = index_src + 1;
 659   index_father_dst = index_dst + 1;
 660
 661   if (*current_src == *current_dst)
 662     father = current_src;
 663   else
 664     father = xbt_dynar_get_ptr(path_src, index_father_src);
 665
 666   /* (5) result generation */
 667   xbt_dynar_push(result, father);       /* first same the father of src and dst */
 668   xbt_dynar_push(result, current_src);  /* second the first different father of src */
 669   xbt_dynar_push(result, current_dst);  /* three  the first different father of dst */
 670
 671   xbt_dynar_free(&path_src);
 672   xbt_dynar_free(&path_dst);
 673
 674   return result;
 675 }
 676
 677 /* Global Business methods */
 678
 679 /**
 680  * \brief Recursive function for get_route
 681  *
 682  * \param src the source host name
 683  * \param dst the destination host name
 684  *
 685  * This fuction is call by "get_route". It allow to walk through the
 686  * routing components tree.
 687  */
 688 static route_extended_t _get_route(const char *src, const char *dst)
 689 {
 690
 691   void *link;
 692   unsigned int cpt = 0;
 693
 694   DEBUG2("Solve route  \"%s\" to \"%s\"", src, dst);
 695
 696   xbt_assert0(src && dst, "bad parameters for \"_get_route\" method");
 697
 698   route_extended_t e_route, e_route_cnt, e_route_src = NULL, e_route_dst =
 699       NULL;
 700
 701   xbt_dynar_t elem_father_list = elements_father(src, dst);
 702
 703   routing_component_t common_father =
 704       xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 705   routing_component_t src_father =
 706       xbt_dynar_get_as(elem_father_list, 1, routing_component_t);
 707   routing_component_t dst_father =
 708       xbt_dynar_get_as(elem_father_list, 2, routing_component_t);
 709
 710   e_route = xbt_new0(s_route_extended_t, 1);
 711   e_route->src_gateway = NULL;
 712   e_route->dst_gateway = NULL;
 713   e_route->generic_route.link_list =
 714       xbt_dynar_new(global_routing->size_of_link, NULL);
 715
 716   if (src_father == dst_father) {       /* SURF_ROUTING_BASE */
 717
 718     if (strcmp(src, dst)) {
 719       e_route_cnt =
 720           (*(common_father->get_route)) (common_father, src, dst);
 721       xbt_assert2(e_route_cnt, "no route between \"%s\" and \"%s\"", src,
 722                   dst);
 723       xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
 724         xbt_dynar_push(e_route->generic_route.link_list, &link);
 725       }
 726       generic_free_extended_route(e_route_cnt);
 727     }
 728
 729   } else {                      /* SURF_ROUTING_RECURSIVE */
 730
 731     route_extended_t e_route_bypass = NULL;
 732
 733     if (common_father->get_bypass_route)
 734       e_route_bypass =
 735           (*(common_father->get_bypass_route)) (common_father, src, dst);
 736
 737     if (e_route_bypass)
 738       e_route_cnt = e_route_bypass;
 739     else
 740       e_route_cnt =
 741           (*(common_father->get_route)) (common_father, src_father->name,
 742                                          dst_father->name);
 743
 744     xbt_assert2(e_route_cnt, "no route between \"%s\" and \"%s\"",
 745                 src_father->name, dst_father->name);
 746
 747     xbt_assert2((e_route_cnt->src_gateway == NULL) ==
 748                 (e_route_cnt->dst_gateway == NULL),
 749                 "bad gateway for route between \"%s\" and \"%s\"", src,
 750                 dst);
 751
 752     if (strcmp(src, e_route_cnt->src_gateway)) {
 753       e_route_src = _get_route(src, e_route_cnt->src_gateway);
 754       xbt_assert2(e_route_src, "no route between \"%s\" and \"%s\"", src,
 755                   e_route_cnt->src_gateway);
 756       xbt_dynar_foreach(e_route_src->generic_route.link_list, cpt, link) {
 757         xbt_dynar_push(e_route->generic_route.link_list, &link);
 758       }
 759     }
 760
 761     xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
 762       xbt_dynar_push(e_route->generic_route.link_list, &link);
 763     }
 764
 765     if (strcmp(e_route_cnt->dst_gateway, dst)) {
 766       e_route_dst = _get_route(e_route_cnt->dst_gateway, dst);
 767       xbt_assert2(e_route_dst, "no route between \"%s\" and \"%s\"",
 768                   e_route_cnt->dst_gateway, dst);
 769       xbt_dynar_foreach(e_route_dst->generic_route.link_list, cpt, link) {
 770         xbt_dynar_push(e_route->generic_route.link_list, &link);
 771       }
 772     }
 773
 774     e_route->src_gateway = xbt_strdup(e_route_cnt->src_gateway);
 775     e_route->dst_gateway = xbt_strdup(e_route_cnt->dst_gateway);
 776
 777     generic_free_extended_route(e_route_src);
 778     generic_free_extended_route(e_route_cnt);
 779     generic_free_extended_route(e_route_dst);
 780   }
 781
 782   xbt_dynar_free(&elem_father_list);
 783
 784   return e_route;
 785 }
 786
 787 static double _get_latency(const char *src, const char *dst)
 788 {
 789   double latency, latency_src, latency_dst = 0.0;
 790
 791   DEBUG2("Solve route  \"%s\" to \"%s\"", src, dst);
 792
 793   xbt_assert0(src && dst, "bad parameters for \"_get_route\" method");
 794
 795   route_extended_t e_route_cnt;
 796
 797   xbt_dynar_t elem_father_list = elements_father(src, dst);
 798
 799   routing_component_t common_father =
 800       xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 801   routing_component_t src_father =
 802       xbt_dynar_get_as(elem_father_list, 1, routing_component_t);
 803   routing_component_t dst_father =
 804       xbt_dynar_get_as(elem_father_list, 2, routing_component_t);
 805
 806   if (src_father == dst_father) {       /* SURF_ROUTING_BASE */
 807
 808     if (strcmp(src, dst)) {
 809       latency =
 810           (*(common_father->get_latency)) (common_father, src, dst);
 811       xbt_assert2(latency>=0, "no route between \"%s\" and \"%s\"", src,
 812                   dst);
 813      } else latency = 0;
 814   } else {                      /* SURF_ROUTING_RECURSIVE */
 815      route_extended_t e_route_bypass = NULL;
 816
 817     if (common_father->get_bypass_route)
 818       e_route_bypass =
 819           (*(common_father->get_bypass_route)) (common_father, src, dst);
 820
 821     xbt_assert0(!e_route_bypass,"Bypass cannot work yet with get_latency");
 822
 823     e_route_cnt =
 824           (*(common_father->get_route)) (common_father, src_father->name,
 825                                          dst_father->name);
 826
 827     xbt_assert2(e_route_cnt, "no route between \"%s\" and \"%s\"",
 828                 src_father->name, dst_father->name);
 829
 830     xbt_assert2((e_route_cnt->src_gateway == NULL) ==
 831                 (e_route_cnt->dst_gateway == NULL),
 832                 "bad gateway for route between \"%s\" and \"%s\"", src,
 833                 dst);
 834     latency =
 835           (*(common_father->get_latency)) (common_father, e_route_cnt->src_gateway,
 836                                          e_route_cnt->src_gateway);
 837     xbt_assert2(latency>=0, "no route between \"%s\" and \"%s\"",
 838                 src_father->name, dst_father->name);
 839
 840
 841     if (src != e_route_cnt->src_gateway) {
 842
 843       latency_src = _get_latency(src, e_route_cnt->src_gateway);
 844       xbt_assert2(latency_src>=0, "no route between \"%s\" and \"%s\"", src,
 845                   e_route_cnt->src_gateway);
 846       latency += latency_src;
 847     }
 848
 849     if (e_route_cnt->dst_gateway != dst) {
 850
 851       latency_dst = _get_latency(e_route_cnt->dst_gateway, dst);
 852       xbt_assert2(latency_dst>=0, "no route between \"%s\" and \"%s\"",
 853                   e_route_cnt->dst_gateway, dst);
 854       latency += latency_dst;
 855     }
 856
 857   }
 858
 859   xbt_dynar_free(&elem_father_list);
 860
 861   return latency;
 862 }
 863
 864 /**
 865  * \brief Generic method: find a route between hosts
 866  *
 867  * \param src the source host name
 868  * \param dst the destination host name
 869  *
 870  * walk through the routing components tree and find a route between hosts
 871  * by calling the differents "get_route" functions in each routing component.
 872  * No need to free the returned dynar. It will be freed at the next call.
 873  */
 874 static xbt_dynar_t get_route(const char *src, const char *dst)
 875 {
 876
 877   route_extended_t e_route;
 878   xbt_dynar_t elem_father_list = NULL;
 879   routing_component_t common_father = NULL;
 880
 881   if (strcmp(src, dst))
 882     e_route = _get_route(src, dst);
 883   else {
 884     elem_father_list = elements_father(src, dst);
 885     common_father =
 886         xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 887
 888     e_route = (*(common_father->get_route)) (common_father, src, dst);
 889     xbt_dynar_free(&elem_father_list);
 890   }
 891
 892   xbt_assert2(e_route, "no route between \"%s\" and \"%s\"", src, dst);
 893
 894   if (global_routing->last_route)
 895     xbt_dynar_free(&(global_routing->last_route));
 896   global_routing->last_route = e_route->generic_route.link_list;
 897
 898   if (e_route->src_gateway)
 899     xbt_free(e_route->src_gateway);
 900   if (e_route->dst_gateway)
 901     xbt_free(e_route->dst_gateway);
 902
 903   xbt_free(e_route);
 904
 905 /*
 906   if (xbt_dynar_length(global_routing->last_route) == 0)
 907     return NULL;
 908   else
 909 */
 910     return global_routing->last_route;
 911 }
 912
 913 /**
 914  * \brief Generic method: find a route between hosts
 915  *
 916  * \param src the source host name
 917  * \param dst the destination host name
 918  *
 919  * walk through the routing components tree and find a route between hosts
 920  * by calling the differents "get_route" functions in each routing component.
 921  * Leaves the caller the responsability to clean the returned dynar.
 922  */
 923 static xbt_dynar_t get_route_no_cleanup(const char *src, const char *dst)
 924 {
 925         xbt_dynar_t d = get_route(src,dst);
 926         global_routing->last_route = NULL;
 927         return d;
 928 }
 929
 930 /*Get Latency*/
 931 static double get_latency(const char *src, const char *dst)
 932 {
 933
 934   double latency = -1.0;
 935   xbt_dynar_t elem_father_list = elements_father(src, dst);
 936   routing_component_t common_father =
 937       xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 938
 939   if (strcmp(src, dst))
 940     latency = _get_latency(src, dst);
 941   else
 942     latency = (*(common_father->get_latency)) (common_father, src, dst);
 943
 944   xbt_assert2(latency>=0.0, "no route between \"%s\" and \"%s\"", src, dst);
 945   xbt_dynar_free(&elem_father_list);
 946
 947   return latency;
 948 }
 949
 950 /**
 951  * \brief Recursive function for finalize
 952  *
 953  * \param rc the source host name
 954  *
 955  * This fuction is call by "finalize". It allow to finalize the
 956  * AS or routing components. It delete all the structures.
 957  */
 958 static void _finalize(routing_component_t rc)
 959 {
 960   if (rc) {
 961     xbt_dict_cursor_t cursor = NULL;
 962     char *key;
 963     routing_component_t elem;
 964     xbt_dict_foreach(rc->routing_sons, cursor, key, elem) {
 965       _finalize(elem);
 966     }
 967     xbt_dict_t tmp_sons = rc->routing_sons;
 968     char *tmp_name = rc->name;
 969     xbt_dict_free(&tmp_sons);
 970     xbt_free(tmp_name);
 971     xbt_assert1(rc->finalize, "no defined method \"finalize\" in \"%s\"",
 972                 current_routing->name);
 973     (*(rc->finalize)) (rc);
 974   }
 975 }
 976
 977 /**
 978  * \brief Generic method: delete all the routing structures
 979  *
 980  * walk through the routing components tree and delete the structures
 981  * by calling the differents "finalize" functions in each routing component
 982  */
 983 static void finalize(void)
 984 {
 985   /* delete recursibly all the tree */
 986   _finalize(global_routing->root);
 987   /* delete "where" dict */
 988   xbt_dict_free(&(global_routing->where_network_elements));
 989   xbt_dict_free(&(coordinates));
 990   /* delete last_route */
 991   xbt_dynar_free(&(global_routing->last_route));
 992   /* delete global routing structure */
 993   xbt_free(global_routing);
 994 }
 995
 996 static xbt_dynar_t recursive_get_onelink_routes(routing_component_t rc)
 997 {
 998   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
 999
1000   //adding my one link routes
1001   unsigned int cpt;
1002   void *link;
1003   xbt_dynar_t onelink_mine = rc->get_onelink_routes(rc);
1004   if (onelink_mine) {
1005     xbt_dynar_foreach(onelink_mine, cpt, link) {
1006       xbt_dynar_push(ret, &link);
1007     }
1008   }
1009   //recursing
1010   char *key;
1011   xbt_dict_cursor_t cursor = NULL;
1012   routing_component_t rc_child;
1013   xbt_dict_foreach(rc->routing_sons, cursor, key, rc_child) {
1014     xbt_dynar_t onelink_child = recursive_get_onelink_routes(rc_child);
1015     if (onelink_child) {
1016       xbt_dynar_foreach(onelink_child, cpt, link) {
1017         xbt_dynar_push(ret, &link);
1018       }
1019     }
1020   }
1021   return ret;
1022 }
1023
1024 static xbt_dynar_t get_onelink_routes(void)
1025 {
1026   return recursive_get_onelink_routes(global_routing->root);
1027 }
1028
1029 static e_surf_network_element_type_t get_network_element_type(const char
1030                                                               *name)
1031 {
1032   network_element_info_t rc = NULL;
1033   rc = xbt_dict_get(global_routing->where_network_elements, name);
1034   return rc->rc_type;
1035 }
1036
1037 /**
1038  * \brief Generic method: create the global routing schema
1039  *
1040  * Make a global routing structure and set all the parsing functions.
1041  */
1042 void routing_model_create(size_t size_of_links, void *loopback, double_f_cpvoid_t get_link_latency_fun)
1043 {
1044
1045   /* config the uniq global routing */
1046   global_routing = xbt_new0(s_routing_global_t, 1);
1047   global_routing->where_network_elements = xbt_dict_new();
1048   global_routing->root = NULL;
1049   global_routing->get_route = get_route;
1050   global_routing->get_latency = get_latency;
1051   global_routing->get_route_no_cleanup = get_route_no_cleanup;
1052   global_routing->get_onelink_routes = get_onelink_routes;
1053   global_routing->get_network_element_type = get_network_element_type;
1054   global_routing->finalize = finalize;
1055   global_routing->loopback = loopback;
1056   global_routing->size_of_link = size_of_links;
1057   global_routing->last_route = NULL;
1058   get_link_latency = get_link_latency_fun;
1059   /* no current routing at moment */
1060   current_routing = NULL;
1061
1062   coordinates = xbt_dict_new();
1063
1064   /* parse generic elements */
1065   surfxml_add_callback(STag_surfxml_host_cb_list, &parse_S_host_XML);
1066   surfxml_add_callback(STag_surfxml_router_cb_list, &parse_S_router);
1067
1068   surfxml_add_callback(STag_surfxml_route_cb_list,
1069                        &parse_S_route_new_and_endpoints_XML);
1070   surfxml_add_callback(STag_surfxml_ASroute_cb_list,
1071                        &parse_S_ASroute_new_and_endpoints);
1072   surfxml_add_callback(STag_surfxml_bypassRoute_cb_list,
1073                        &parse_S_bypassRoute_new_and_endpoints);
1074
1075   surfxml_add_callback(ETag_surfxml_link_ctn_cb_list,
1076                        &parse_E_link_ctn_new_elem_XML);
1077
1078   surfxml_add_callback(ETag_surfxml_route_cb_list,
1079                        &parse_E_route_store_route);
1080   surfxml_add_callback(ETag_surfxml_ASroute_cb_list,
1081                        &parse_E_ASroute_store_route);
1082   surfxml_add_callback(ETag_surfxml_bypassRoute_cb_list,
1083                        &parse_E_bypassRoute_store_route);
1084
1085   surfxml_add_callback(STag_surfxml_AS_cb_list, &parse_S_AS_XML);
1086   surfxml_add_callback(ETag_surfxml_AS_cb_list, &parse_E_AS_XML);
1087
1088   surfxml_add_callback(STag_surfxml_cluster_cb_list,
1089                        &routing_parse_Scluster);
1090
1091   surfxml_add_callback(STag_surfxml_peer_cb_list,
1092                          &routing_parse_Speer);
1093
1094   surfxml_add_callback(STag_surfxml_config_cb_list,
1095                                            &routing_parse_Sconfig);
1096   surfxml_add_callback(ETag_surfxml_config_cb_list,
1097                                            &routing_parse_Econfig);
1098 }
1099
1100 /* ************************************************************************** */
1101 /* *************************** FULL ROUTING ********************************* */
1102
1103 #define TO_ROUTE_FULL(i,j) routing->routing_table[(i)+(j)*table_size]
1104
1105 /* Routing model structure */
1106
1107 typedef struct {
1108   s_routing_component_t generic_routing;
1109   route_extended_t *routing_table;
1110 } s_routing_component_full_t, *routing_component_full_t;
1111
1112 /* Business methods */
1113 static xbt_dynar_t full_get_onelink_routes(routing_component_t rc)
1114 {
1115   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
1116
1117   routing_component_full_t routing = (routing_component_full_t) rc;
1118   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1119   xbt_dict_cursor_t c1 = NULL, c2 = NULL;
1120   char *k1, *d1, *k2, *d2;
1121   xbt_dict_foreach(routing->generic_routing.to_index, c1, k1, d1) {
1122     xbt_dict_foreach(routing->generic_routing.to_index, c2, k2, d2) {
1123       int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, k1);
1124       int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, k2);
1125       xbt_assert2(src_id
1126                   && dst_id,
1127                   "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1128                   src, dst);
1129       route_extended_t route = TO_ROUTE_FULL(*src_id, *dst_id);
1130       if (route) {
1131         if (xbt_dynar_length(route->generic_route.link_list) == 1) {
1132           void *link =
1133               *(void **) xbt_dynar_get_ptr(route->generic_route.link_list,
1134                                            0);
1135           onelink_t onelink = xbt_new0(s_onelink_t, 1);
1136           onelink->link_ptr = link;
1137           if (routing->generic_routing.hierarchy == SURF_ROUTING_BASE) {
1138             onelink->src = xbt_strdup(k1);
1139             onelink->dst = xbt_strdup(k2);
1140           } else if (routing->generic_routing.hierarchy ==
1141                      SURF_ROUTING_RECURSIVE) {
1142             onelink->src = xbt_strdup(route->src_gateway);
1143             onelink->dst = xbt_strdup(route->dst_gateway);
1144           }
1145           xbt_dynar_push(ret, &onelink);
1146         }
1147       }
1148     }
1149   }
1150   return ret;
1151 }
1152
1153 static route_extended_t full_get_route(routing_component_t rc,
1154                                        const char *src, const char *dst)
1155 {
1156   xbt_assert1(rc && src
1157               && dst,
1158               "Invalid params for \"get_route\" function at AS \"%s\"",
1159               rc->name);
1160
1161   /* set utils vars */
1162   routing_component_full_t routing = (routing_component_full_t) rc;
1163   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1164
1165   generic_src_dst_check(rc, src, dst);
1166   int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, src);
1167   int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, dst);
1168   xbt_assert2(src_id
1169               && dst_id,
1170               "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1171               src, dst);
1172
1173   route_extended_t e_route = NULL;
1174   route_extended_t new_e_route = NULL;
1175   void *link;
1176   unsigned int cpt = 0;
1177
1178   e_route = TO_ROUTE_FULL(*src_id, *dst_id);
1179
1180   if (e_route) {
1181     new_e_route = xbt_new0(s_route_extended_t, 1);
1182     new_e_route->src_gateway = xbt_strdup(e_route->src_gateway);
1183     new_e_route->dst_gateway = xbt_strdup(e_route->dst_gateway);
1184     new_e_route->generic_route.link_list =
1185         xbt_dynar_new(global_routing->size_of_link, NULL);
1186     xbt_dynar_foreach(e_route->generic_route.link_list, cpt, link) {
1187       xbt_dynar_push(new_e_route->generic_route.link_list, &link);
1188     }
1189   }
1190   return new_e_route;
1191 }
1192
1193 static void full_finalize(routing_component_t rc)
1194 {
1195   routing_component_full_t routing = (routing_component_full_t) rc;
1196   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1197   int i, j;
1198   if (routing) {
1199     /* Delete routing table */
1200     for (i = 0; i < table_size; i++)
1201       for (j = 0; j < table_size; j++)
1202         generic_free_extended_route(TO_ROUTE_FULL(i, j));
1203     xbt_free(routing->routing_table);
1204     /* Delete bypass dict */
1205     xbt_dict_free(&rc->bypassRoutes);
1206     /* Delete index dict */
1207     xbt_dict_free(&rc->to_index);
1208     /* Delete structure */
1209     xbt_free(rc);
1210   }
1211 }
1212
1213 /* Creation routing model functions */
1214
1215 static void *model_full_create(void)
1216 {
1217   routing_component_full_t new_component =
1218       xbt_new0(s_routing_component_full_t, 1);
1219   new_component->generic_routing.set_processing_unit =
1220       generic_set_processing_unit;
1221   new_component->generic_routing.set_autonomous_system =
1222       generic_set_autonomous_system;
1223   new_component->generic_routing.set_route = model_full_set_route;
1224   new_component->generic_routing.set_ASroute = model_full_set_route;
1225   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
1226   new_component->generic_routing.get_route = full_get_route;
1227   new_component->generic_routing.get_latency = generic_get_link_latency;
1228   new_component->generic_routing.get_onelink_routes =
1229       full_get_onelink_routes;
1230   new_component->generic_routing.get_bypass_route =
1231       generic_get_bypassroute;
1232   new_component->generic_routing.finalize = full_finalize;
1233   new_component->generic_routing.to_index = xbt_dict_new();
1234   new_component->generic_routing.bypassRoutes = xbt_dict_new();
1235   return new_component;
1236 }
1237
1238 static void model_full_load(void)
1239 {
1240   /* use "surfxml_add_callback" to add a parse function call */
1241 }
1242
1243 static void model_full_unload(void)
1244 {
1245   /* use "surfxml_del_callback" to remove a parse function call */
1246 }
1247
1248 static void model_full_end(void)
1249 {
1250   unsigned int i;
1251   route_extended_t e_route;
1252
1253   /* set utils vars */
1254   routing_component_full_t routing =
1255       ((routing_component_full_t) current_routing);
1256   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1257
1258   /* Create table if necessary */
1259   if(!routing->routing_table)
1260           routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
1261
1262   /* Add the loopback if needed */
1263   if (current_routing->hierarchy == SURF_ROUTING_BASE) {
1264     for (i = 0; i < table_size; i++) {
1265       e_route = TO_ROUTE_FULL(i, i);
1266       if (!e_route) {
1267         e_route = xbt_new0(s_route_extended_t, 1);
1268         e_route->src_gateway = NULL;
1269         e_route->dst_gateway = NULL;
1270         e_route->generic_route.link_list =
1271             xbt_dynar_new(global_routing->size_of_link, NULL);
1272         xbt_dynar_push(e_route->generic_route.link_list,
1273                        &global_routing->loopback);
1274         TO_ROUTE_FULL(i, i) = e_route;
1275       }
1276     }
1277   }
1278 }
1279
1280 static void model_full_set_route(routing_component_t rc, const char *src,
1281                 const char *dst, name_route_extended_t route)
1282 {
1283         int *src_id, *dst_id;
1284         src_id = xbt_dict_get_or_null(rc->to_index, src);
1285         dst_id = xbt_dict_get_or_null(rc->to_index, dst);
1286         routing_component_full_t routing = ((routing_component_full_t) rc);
1287         size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1288
1289         xbt_assert2(src_id
1290                           && dst_id, "Network elements %s or %s not found", src, dst);
1291
1292         xbt_assert2(xbt_dynar_length(route->generic_route.link_list) > 0,
1293                           "Invalid count of links, must be greater than zero (%s,%s)",
1294                           src, dst);
1295
1296         if(!routing->routing_table)
1297                 routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
1298
1299         if(TO_ROUTE_FULL(*src_id, *dst_id))
1300         {
1301                 char * link_name;
1302                 unsigned int i;
1303                 xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1304                 xbt_dynar_foreach(route->generic_route.link_list,i,link_name)
1305                 {
1306                         void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1307                         xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1308                         xbt_dynar_push(link_route_to_test,&link);
1309                 }
1310                 xbt_assert2(!xbt_dynar_compare(
1311                           (void*)TO_ROUTE_FULL(*src_id, *dst_id)->generic_route.link_list,
1312                           (void*)link_route_to_test,
1313                           (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1314                           "The route between \"%s\" and \"%s\" already exists", src,dst);
1315                 xbt_dynar_free(&link_route_to_test);
1316         }
1317         else
1318         {
1319                   if(!route->dst_gateway && !route->src_gateway)
1320                           DEBUG2("Load Route from \"%s\" to \"%s\"", src, dst);
1321                   else
1322                           DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
1323                                  route->src_gateway, dst, route->dst_gateway);
1324               TO_ROUTE_FULL(*src_id, *dst_id) = generic_new_extended_route(rc->hierarchy,route,1);
1325               xbt_dynar_shrink(TO_ROUTE_FULL(*src_id, *dst_id)->generic_route.link_list, 0);
1326         }
1327
1328         if( A_surfxml_route_symmetrical == A_surfxml_route_symmetrical_YES
1329                 || A_surfxml_ASroute_symmetrical == A_surfxml_ASroute_symmetrical_YES )
1330         {
1331                 if(route->dst_gateway && route->src_gateway)
1332                 {
1333                   char *gw_src = xbt_strdup(route->src_gateway);
1334                   char *gw_dst = xbt_strdup(route->dst_gateway);
1335                   route->src_gateway = gw_dst;
1336                   route->dst_gateway = gw_src;
1337                 }
1338                 if(TO_ROUTE_FULL(*dst_id, *src_id))
1339                 {
1340                         char * link_name;
1341                         unsigned int i;
1342                         xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1343                         for(i=xbt_dynar_length(route->generic_route.link_list) ;i>0 ;i--)
1344                         {
1345                                 link_name = xbt_dynar_get_as(route->generic_route.link_list,i-1,void *);
1346                                 void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1347                                 xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1348                                 xbt_dynar_push(link_route_to_test,&link);
1349                         }
1350                         xbt_assert2(!xbt_dynar_compare(
1351                                   (void*)TO_ROUTE_FULL(*dst_id, *src_id)->generic_route.link_list,
1352                               (void*)link_route_to_test,
1353                                   (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1354                                   "The route between \"%s\" and \"%s\" already exists", src,dst);
1355                         xbt_dynar_free(&link_route_to_test);
1356                 }
1357                 else
1358                 {
1359                           if(!route->dst_gateway && !route->src_gateway)
1360                                   DEBUG2("Load Route from \"%s\" to \"%s\"", dst, src);
1361                           else
1362                                   DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
1363                                          route->src_gateway, src, route->dst_gateway);
1364                       TO_ROUTE_FULL(*dst_id, *src_id) = generic_new_extended_route(rc->hierarchy,route,0);
1365                       xbt_dynar_shrink(TO_ROUTE_FULL(*dst_id, *src_id)->generic_route.link_list, 0);
1366                 }
1367
1368         }
1369 }
1370
1371 /* ************************************************************************** */
1372 /* *************************** FLOYD ROUTING ******************************** */
1373
1374 #define TO_FLOYD_COST(i,j) (routing->cost_table)[(i)+(j)*table_size]
1375 #define TO_FLOYD_PRED(i,j) (routing->predecessor_table)[(i)+(j)*table_size]
1376 #define TO_FLOYD_LINK(i,j) (routing->link_table)[(i)+(j)*table_size]
1377
1378 /* Routing model structure */
1379
1380 typedef struct {
1381   s_routing_component_t generic_routing;
1382   /* vars for calculate the floyd algorith. */
1383   int *predecessor_table;
1384   double *cost_table;
1385   route_extended_t *link_table; /* char* -> int* */
1386 } s_routing_component_floyd_t, *routing_component_floyd_t;
1387
1388 static route_extended_t floyd_get_route(routing_component_t rc,
1389                                         const char *src, const char *dst);
1390
1391 /* Business methods */
1392 static xbt_dynar_t floyd_get_onelink_routes(routing_component_t rc)
1393 {
1394   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
1395
1396   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1397   //size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1398   xbt_dict_cursor_t c1 = NULL, c2 = NULL;
1399   char *k1, *d1, *k2, *d2;
1400   xbt_dict_foreach(routing->generic_routing.to_index, c1, k1, d1) {
1401     xbt_dict_foreach(routing->generic_routing.to_index, c2, k2, d2) {
1402       route_extended_t route = floyd_get_route(rc, k1, k2);
1403       if (route) {
1404         if (xbt_dynar_length(route->generic_route.link_list) == 1) {
1405           void *link =
1406               *(void **) xbt_dynar_get_ptr(route->generic_route.link_list,
1407                                            0);
1408           onelink_t onelink = xbt_new0(s_onelink_t, 1);
1409           onelink->link_ptr = link;
1410           if (routing->generic_routing.hierarchy == SURF_ROUTING_BASE) {
1411             onelink->src = xbt_strdup(k1);
1412             onelink->dst = xbt_strdup(k2);
1413           } else if (routing->generic_routing.hierarchy ==
1414                      SURF_ROUTING_RECURSIVE) {
1415             onelink->src = xbt_strdup(route->src_gateway);
1416             onelink->dst = xbt_strdup(route->dst_gateway);
1417           }
1418           xbt_dynar_push(ret, &onelink);
1419         }
1420       }
1421     }
1422   }
1423   return ret;
1424 }
1425
1426 static route_extended_t floyd_get_route(routing_component_t rc,
1427                                         const char *src, const char *dst)
1428 {
1429   xbt_assert1(rc && src
1430               && dst,
1431               "Invalid params for \"get_route\" function at AS \"%s\"",
1432               rc->name);
1433
1434   /* set utils vars */
1435   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1436   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1437
1438   generic_src_dst_check(rc, src, dst);
1439   int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, src);
1440   int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, dst);
1441   xbt_assert2(src_id
1442               && dst_id,
1443               "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1444               src, dst);
1445
1446   /* create a result route */
1447   route_extended_t new_e_route = xbt_new0(s_route_extended_t, 1);
1448   new_e_route->generic_route.link_list =
1449       xbt_dynar_new(global_routing->size_of_link, NULL);
1450   new_e_route->src_gateway = NULL;
1451   new_e_route->dst_gateway = NULL;
1452
1453   int first = 1;
1454   int pred = *dst_id;
1455   int prev_pred = 0;
1456   char *gw_src = NULL, *gw_dst =
1457       NULL, *prev_gw_src, *prev_gw_dst, *first_gw = NULL;
1458   unsigned int cpt;
1459   void *link;
1460   xbt_dynar_t links;
1461
1462   do {
1463     prev_pred = pred;
1464     pred = TO_FLOYD_PRED(*src_id, pred);
1465     if (pred == -1)             /* if no pred in route -> no route to host */
1466       break;
1467     xbt_assert2(TO_FLOYD_LINK(pred, prev_pred),
1468                 "Invalid link for the route between \"%s\" or \"%s\"", src,
1469                 dst);
1470
1471     prev_gw_src = gw_src;
1472     prev_gw_dst = gw_dst;
1473
1474     route_extended_t e_route = TO_FLOYD_LINK(pred, prev_pred);
1475     gw_src = e_route->src_gateway;
1476     gw_dst = e_route->dst_gateway;
1477
1478     if (first)
1479       first_gw = gw_dst;
1480
1481     if (rc->hierarchy == SURF_ROUTING_RECURSIVE && !first
1482         && strcmp(gw_dst, prev_gw_src)) {
1483       xbt_dynar_t e_route_as_to_as =
1484           (*(global_routing->get_route)) (gw_dst, prev_gw_src);
1485       xbt_assert2(e_route_as_to_as, "no route between \"%s\" and \"%s\"",
1486                   gw_dst, prev_gw_src);
1487       links = e_route_as_to_as;
1488       int pos = 0;
1489       xbt_dynar_foreach(links, cpt, link) {
1490         xbt_dynar_insert_at(new_e_route->generic_route.link_list, pos,
1491                             &link);
1492         pos++;
1493       }
1494     }
1495
1496     links = e_route->generic_route.link_list;
1497     xbt_dynar_foreach(links, cpt, link) {
1498       xbt_dynar_unshift(new_e_route->generic_route.link_list, &link);
1499     }
1500     first = 0;
1501
1502   } while (pred != *src_id);
1503   xbt_assert4(pred != -1, "no route from host %d to %d (\"%s\" to \"%s\")",
1504               *src_id, *dst_id, src, dst);
1505
1506   if (rc->hierarchy == SURF_ROUTING_RECURSIVE) {
1507     new_e_route->src_gateway = xbt_strdup(gw_src);
1508     new_e_route->dst_gateway = xbt_strdup(first_gw);
1509   }
1510
1511   return new_e_route;
1512 }
1513
1514 static void floyd_finalize(routing_component_t rc)
1515 {
1516   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1517   int i, j;
1518   size_t table_size;
1519   if (routing) {
1520     table_size = xbt_dict_length(routing->generic_routing.to_index);
1521     /* Delete link_table */
1522     for (i = 0; i < table_size; i++)
1523       for (j = 0; j < table_size; j++)
1524         generic_free_extended_route(TO_FLOYD_LINK(i, j));
1525     xbt_free(routing->link_table);
1526     /* Delete bypass dict */
1527     xbt_dict_free(&routing->generic_routing.bypassRoutes);
1528     /* Delete index dict */
1529     xbt_dict_free(&(routing->generic_routing.to_index));
1530     /* Delete dictionary index dict, predecessor and links table */
1531     xbt_free(routing->predecessor_table);
1532     /* Delete structure */
1533     xbt_free(rc);
1534   }
1535 }
1536
1537 static void *model_floyd_create(void)
1538 {
1539   routing_component_floyd_t new_component =
1540       xbt_new0(s_routing_component_floyd_t, 1);
1541   new_component->generic_routing.set_processing_unit =
1542       generic_set_processing_unit;
1543   new_component->generic_routing.set_autonomous_system =
1544       generic_set_autonomous_system;
1545   new_component->generic_routing.set_route = model_floyd_set_route;
1546   new_component->generic_routing.set_ASroute = model_floyd_set_route;
1547   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
1548   new_component->generic_routing.get_route = floyd_get_route;
1549   new_component->generic_routing.get_latency = generic_get_link_latency;
1550   new_component->generic_routing.get_onelink_routes =
1551       floyd_get_onelink_routes;
1552   new_component->generic_routing.get_bypass_route =
1553       generic_get_bypassroute;
1554   new_component->generic_routing.finalize = floyd_finalize;
1555   new_component->generic_routing.to_index = xbt_dict_new();
1556   new_component->generic_routing.bypassRoutes = xbt_dict_new();
1557   return new_component;
1558 }
1559
1560 static void model_floyd_load(void)
1561 {
1562   /* use "surfxml_add_callback" to add a parse function call */
1563 }
1564
1565 static void model_floyd_unload(void)
1566 {
1567   /* use "surfxml_del_callback" to remove a parse function call */
1568 }
1569
1570 static void model_floyd_end(void)
1571 {
1572
1573         routing_component_floyd_t routing =
1574           ((routing_component_floyd_t) current_routing);
1575
1576         unsigned int i, j, a, b, c;
1577
1578         /* set the size of table routing */
1579         size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1580
1581         if(!routing->link_table)
1582         {
1583                 /* Create Cost, Predecessor and Link tables */
1584                 routing->cost_table = xbt_new0(double, table_size * table_size);       /* link cost from host to host */
1585                 routing->predecessor_table = xbt_new0(int, table_size * table_size);  /* predecessor host numbers */
1586                 routing->link_table = xbt_new0(route_extended_t, table_size * table_size);    /* actual link between src and dst */
1587
1588                 /* Initialize costs and predecessors */
1589                 for (i = 0; i < table_size; i++)
1590                 for (j = 0; j < table_size; j++) {
1591                   TO_FLOYD_COST(i, j) = DBL_MAX;
1592                   TO_FLOYD_PRED(i, j) = -1;
1593                   TO_FLOYD_LINK(i, j) = NULL;       /* fixed, missing in the previous version */
1594                 }
1595         }
1596
1597         /* Add the loopback if needed */
1598         if (current_routing->hierarchy == SURF_ROUTING_BASE) {
1599                 for (i = 0; i < table_size; i++) {
1600                   route_extended_t e_route = TO_FLOYD_LINK(i, i);
1601                   if (!e_route) {
1602                         e_route = xbt_new0(s_route_extended_t, 1);
1603                         e_route->src_gateway = NULL;
1604                         e_route->dst_gateway = NULL;
1605                         e_route->generic_route.link_list =
1606                                 xbt_dynar_new(global_routing->size_of_link, NULL);
1607                         xbt_dynar_push(e_route->generic_route.link_list,
1608                                                    &global_routing->loopback);
1609                         TO_FLOYD_LINK(i, i) = e_route;
1610                         TO_FLOYD_PRED(i, i) = i;
1611                         TO_FLOYD_COST(i, i) = 1;
1612                   }
1613                 }
1614         }
1615         /* Calculate path costs */
1616         for (c = 0; c < table_size; c++) {
1617                 for (a = 0; a < table_size; a++) {
1618                   for (b = 0; b < table_size; b++) {
1619                         if (TO_FLOYD_COST(a, c) < DBL_MAX && TO_FLOYD_COST(c, b) < DBL_MAX) {
1620                           if (TO_FLOYD_COST(a, b) == DBL_MAX ||
1621                                   (TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b) <
1622                                    TO_FLOYD_COST(a, b))) {
1623                                 TO_FLOYD_COST(a, b) =
1624                                         TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b);
1625                                 TO_FLOYD_PRED(a, b) = TO_FLOYD_PRED(c, b);
1626                           }
1627                         }
1628                   }
1629                 }
1630         }
1631 }
1632
1633 static void model_floyd_set_route(routing_component_t rc, const char *src,
1634         const char *dst, name_route_extended_t route)
1635 {
1636         routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1637
1638         /* set the size of table routing */
1639         size_t table_size = xbt_dict_length(rc->to_index);
1640         int *src_id, *dst_id;
1641         int i,j;
1642
1643         src_id = xbt_dict_get_or_null(rc->to_index, src);
1644         dst_id = xbt_dict_get_or_null(rc->to_index, dst);
1645
1646         if(!routing->link_table)
1647         {
1648                 /* Create Cost, Predecessor and Link tables */
1649                 routing->cost_table = xbt_new0(double, table_size * table_size);       /* link cost from host to host */
1650                 routing->predecessor_table = xbt_new0(int, table_size * table_size);  /* predecessor host numbers */
1651                 routing->link_table = xbt_new0(route_extended_t, table_size * table_size);    /* actual link between src and dst */
1652
1653                 /* Initialize costs and predecessors */
1654                 for (i = 0; i < table_size; i++)
1655                 for (j = 0; j < table_size; j++) {
1656                   TO_FLOYD_COST(i, j) = DBL_MAX;
1657                   TO_FLOYD_PRED(i, j) = -1;
1658                   TO_FLOYD_LINK(i, j) = NULL;       /* fixed, missing in the previous version */
1659                 }
1660         }
1661
1662         if(TO_FLOYD_LINK(*src_id, *dst_id))
1663         {
1664                 if(!route->dst_gateway && !route->src_gateway)
1665                         DEBUG2("See Route from \"%s\" to \"%s\"", src, dst);
1666                 else
1667                         DEBUG4("See ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
1668                                  route->src_gateway, dst, route->dst_gateway);
1669                 char * link_name;
1670                 unsigned int cpt;
1671                 xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1672                 xbt_dynar_foreach(route->generic_route.link_list,cpt,link_name)
1673                 {
1674                         void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1675                         xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1676                         xbt_dynar_push(link_route_to_test,&link);
1677                 }
1678                 xbt_assert2(!xbt_dynar_compare(
1679                           (void*)TO_FLOYD_LINK(*src_id, *dst_id)->generic_route.link_list,
1680                           (void*)link_route_to_test,
1681                           (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1682                           "The route between \"%s\" and \"%s\" already exists", src,dst);
1683                 xbt_free(link_route_to_test);
1684         }
1685         else
1686         {
1687                 if(!route->dst_gateway && !route->src_gateway)
1688                   DEBUG2("Load Route from \"%s\" to \"%s\"", src, dst);
1689                 else
1690                   DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
1691                                  route->src_gateway, dst, route->dst_gateway);
1692
1693             TO_FLOYD_LINK(*src_id, *dst_id) =
1694                         generic_new_extended_route(rc->hierarchy, route, 1);
1695             TO_FLOYD_PRED(*src_id, *dst_id) = *src_id;
1696             TO_FLOYD_COST(*src_id, *dst_id) =
1697                         ((TO_FLOYD_LINK(*src_id, *dst_id))->generic_route.link_list)->used;   /* count of links, old model assume 1 */
1698         }
1699
1700         if( A_surfxml_route_symmetrical == A_surfxml_route_symmetrical_YES
1701                 || A_surfxml_ASroute_symmetrical == A_surfxml_ASroute_symmetrical_YES )
1702         {
1703                 if(TO_FLOYD_LINK(*dst_id, *src_id))
1704                 {
1705                         if(!route->dst_gateway && !route->src_gateway)
1706                           DEBUG2("See Route from \"%s\" to \"%s\"", dst, src);
1707                         else
1708                           DEBUG4("See ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
1709                                          route->src_gateway, src, route->dst_gateway);
1710                         char * link_name;
1711                         unsigned int i;
1712                         xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1713                         for(i=xbt_dynar_length(route->generic_route.link_list) ;i>0 ;i--)
1714                         {
1715                                 link_name = xbt_dynar_get_as(route->generic_route.link_list,i-1,void *);
1716                                 void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1717                                 xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1718                                 xbt_dynar_push(link_route_to_test,&link);
1719                         }
1720                         xbt_assert2(!xbt_dynar_compare(
1721                                   (void*)TO_FLOYD_LINK(*dst_id, *src_id)->generic_route.link_list,
1722                               (void*)link_route_to_test,
1723                                   (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1724                                   "The route between \"%s\" and \"%s\" already exists", src,dst);
1725                         xbt_free(link_route_to_test);
1726                 }
1727                 else
1728                 {
1729                         if(route->dst_gateway && route->src_gateway)
1730                         {
1731                           char *gw_src = xbt_strdup(route->src_gateway);
1732                           char *gw_dst = xbt_strdup(route->dst_gateway);
1733                           route->src_gateway = gw_dst;
1734                           route->dst_gateway = gw_src;
1735                         }
1736
1737                         if(!route->dst_gateway && !route->src_gateway)
1738                           DEBUG2("Load Route from \"%s\" to \"%s\"", dst, src);
1739                         else
1740                           DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
1741                                          route->src_gateway, src, route->dst_gateway);
1742
1743                     TO_FLOYD_LINK(*dst_id, *src_id) =
1744                                 generic_new_extended_route(rc->hierarchy, route, 0);
1745                     TO_FLOYD_PRED(*dst_id, *src_id) = *dst_id;
1746                     TO_FLOYD_COST(*dst_id, *src_id) =
1747                                 ((TO_FLOYD_LINK(*dst_id, *src_id))->generic_route.link_list)->used;   /* count of links, old model assume 1 */
1748                 }
1749         }
1750 }
1751
1752 /* ************************************************************************** */
1753 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
1754
1755 typedef struct {
1756   s_routing_component_t generic_routing;
1757   xbt_graph_t route_graph;      /* xbt_graph */
1758   xbt_dict_t graph_node_map;    /* map */
1759   xbt_dict_t route_cache;       /* use in cache mode */
1760   int cached;
1761 } s_routing_component_dijkstra_t, *routing_component_dijkstra_t;
1762
1763
1764 typedef struct graph_node_data {
1765   int id;
1766   int graph_id;                 /* used for caching internal graph id's */
1767 } s_graph_node_data_t, *graph_node_data_t;
1768
1769 typedef struct graph_node_map_element {
1770   xbt_node_t node;
1771 } s_graph_node_map_element_t, *graph_node_map_element_t;
1772
1773 typedef struct route_cache_element {
1774   int *pred_arr;
1775   int size;
1776 } s_route_cache_element_t, *route_cache_element_t;
1777
1778 /* Free functions */
1779
1780 static void route_cache_elem_free(void *e)
1781 {
1782   route_cache_element_t elm = (route_cache_element_t) e;
1783   if (elm) {
1784     xbt_free(elm->pred_arr);
1785     xbt_free(elm);
1786   }
1787 }
1788
1789 static void graph_node_map_elem_free(void *e)
1790 {
1791   graph_node_map_element_t elm = (graph_node_map_element_t) e;
1792   if (elm) {
1793     xbt_free(elm);
1794   }
1795 }
1796
1797 static void graph_edge_data_free(void *e)
1798 {
1799   route_extended_t e_route = (route_extended_t) e;
1800   if (e_route) {
1801     xbt_dynar_free(&(e_route->generic_route.link_list));
1802     if (e_route->src_gateway)
1803       xbt_free(e_route->src_gateway);
1804     if (e_route->dst_gateway)
1805       xbt_free(e_route->dst_gateway);
1806     xbt_free(e_route);
1807   }
1808 }
1809
1810 /* Utility functions */
1811
1812 static xbt_node_t route_graph_new_node(routing_component_dijkstra_t rc,
1813                                        int id, int graph_id)
1814 {
1815   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1816   xbt_node_t node = NULL;
1817   graph_node_data_t data = NULL;
1818   graph_node_map_element_t elm = NULL;
1819
1820   data = xbt_new0(struct graph_node_data, 1);
1821   data->id = id;
1822   data->graph_id = graph_id;
1823   node = xbt_graph_new_node(routing->route_graph, data);
1824
1825   elm = xbt_new0(struct graph_node_map_element, 1);
1826   elm->node = node;
1827   xbt_dict_set_ext(routing->graph_node_map, (char *) (&id), sizeof(int),
1828                    (xbt_set_elm_t) elm, &graph_node_map_elem_free);
1829
1830   return node;
1831 }
1832
1833 static graph_node_map_element_t
1834 graph_node_map_search(routing_component_dijkstra_t rc, int id)
1835 {
1836   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1837   graph_node_map_element_t elm = (graph_node_map_element_t)
1838       xbt_dict_get_or_null_ext(routing->graph_node_map,
1839                                (char *) (&id),
1840                                sizeof(int));
1841   return elm;
1842 }
1843
1844 /* Parsing */
1845
1846 static void route_new_dijkstra(routing_component_dijkstra_t rc, int src_id,
1847                                int dst_id, route_extended_t e_route)
1848 {
1849   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1850
1851   xbt_node_t src = NULL;
1852   xbt_node_t dst = NULL;
1853   graph_node_map_element_t src_elm = (graph_node_map_element_t)
1854       xbt_dict_get_or_null_ext(routing->graph_node_map,
1855                                (char *) (&src_id),
1856                                sizeof(int));
1857   graph_node_map_element_t dst_elm = (graph_node_map_element_t)
1858       xbt_dict_get_or_null_ext(routing->graph_node_map,
1859                                (char *) (&dst_id),
1860                                sizeof(int));
1861
1862   if (src_elm)
1863     src = src_elm->node;
1864
1865   if (dst_elm)
1866     dst = dst_elm->node;
1867
1868   /* add nodes if they don't exist in the graph */
1869   if (src_id == dst_id && src == NULL && dst == NULL) {
1870     src = route_graph_new_node(rc, src_id, -1);
1871     dst = src;
1872   } else {
1873     if (src == NULL) {
1874       src = route_graph_new_node(rc, src_id, -1);
1875     }
1876     if (dst == NULL) {
1877       dst = route_graph_new_node(rc, dst_id, -1);
1878     }
1879   }
1880
1881   /* add link as edge to graph */
1882   xbt_graph_new_edge(routing->route_graph, src, dst, e_route);
1883 }
1884
1885 static void add_loopback_dijkstra(routing_component_dijkstra_t rc)
1886 {
1887   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1888
1889   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1890
1891   xbt_node_t node = NULL;
1892   unsigned int cursor2;
1893   xbt_dynar_foreach(nodes, cursor2, node) {
1894     xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
1895     xbt_edge_t edge = NULL;
1896     unsigned int cursor;
1897
1898     int found = 0;
1899     xbt_dynar_foreach(out_edges, cursor, edge) {
1900       xbt_node_t other_node = xbt_graph_edge_get_target(edge);
1901       if (other_node == node) {
1902         found = 1;
1903         break;
1904       }
1905     }
1906
1907     if (!found) {
1908       route_extended_t e_route = xbt_new0(s_route_extended_t, 1);
1909       e_route->src_gateway = NULL;
1910       e_route->dst_gateway = NULL;
1911       e_route->generic_route.link_list =
1912           xbt_dynar_new(global_routing->size_of_link, NULL);
1913       xbt_dynar_push(e_route->generic_route.link_list,
1914                      &global_routing->loopback);
1915       xbt_graph_new_edge(routing->route_graph, node, node, e_route);
1916     }
1917   }
1918 }
1919
1920 /* Business methods */
1921 static xbt_dynar_t dijkstra_get_onelink_routes(routing_component_t rc)
1922 {
1923   xbt_die("\"dijkstra_get_onelink_routes\" function not implemented yet");
1924 }
1925
1926 static route_extended_t dijkstra_get_route(routing_component_t rc,
1927                                            const char *src,
1928                                            const char *dst)
1929 {
1930   xbt_assert1(rc && src
1931               && dst,
1932               "Invalid params for \"get_route\" function at AS \"%s\"",
1933               rc->name);
1934
1935   /* set utils vars */
1936   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1937
1938   generic_src_dst_check(rc, src, dst);
1939   int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, src);
1940   int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, dst);
1941   xbt_assert2(src_id
1942               && dst_id,
1943               "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1944               src, dst);
1945
1946   /* create a result route */
1947   route_extended_t new_e_route = xbt_new0(s_route_extended_t, 1);
1948   new_e_route->generic_route.link_list =
1949       xbt_dynar_new(global_routing->size_of_link, NULL);
1950   new_e_route->src_gateway = NULL;
1951   new_e_route->dst_gateway = NULL;
1952
1953   int *pred_arr = NULL;
1954   int src_node_id = 0;
1955   int dst_node_id = 0;
1956   int *nodeid = NULL;
1957   int v;
1958   route_extended_t e_route;
1959   int size = 0;
1960   unsigned int cpt;
1961   void *link;
1962   xbt_dynar_t links = NULL;
1963   route_cache_element_t elm = NULL;
1964   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1965
1966   /* Use the graph_node id mapping set to quickly find the nodes */
1967   graph_node_map_element_t src_elm =
1968       graph_node_map_search(routing, *src_id);
1969   graph_node_map_element_t dst_elm =
1970       graph_node_map_search(routing, *dst_id);
1971   xbt_assert2(src_elm != NULL
1972               && dst_elm != NULL, "src %d or dst %d does not exist",
1973               *src_id, *dst_id);
1974   src_node_id = ((graph_node_data_t)
1975                  xbt_graph_node_get_data(src_elm->node))->graph_id;
1976   dst_node_id = ((graph_node_data_t)
1977                  xbt_graph_node_get_data(dst_elm->node))->graph_id;
1978
1979   /* if the src and dst are the same *//* fixed, missing in the previous version */
1980   if (src_node_id == dst_node_id) {
1981
1982     xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
1983     xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
1984     xbt_edge_t edge =
1985         xbt_graph_get_edge(routing->route_graph, node_s_v, node_e_v);
1986
1987     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id,
1988                 *dst_id);
1989
1990     e_route = (route_extended_t) xbt_graph_edge_get_data(edge);
1991
1992     links = e_route->generic_route.link_list;
1993     xbt_dynar_foreach(links, cpt, link) {
1994       xbt_dynar_unshift(new_e_route->generic_route.link_list, &link);
1995     }
1996
1997     return new_e_route;
1998   }
1999
2000   if (routing->cached) {
2001     /*check if there is a cached predecessor list avail */
2002     elm = (route_cache_element_t)
2003         xbt_dict_get_or_null_ext(routing->route_cache, (char *) (&src_id),
2004                                  sizeof(int));
2005   }
2006
2007   if (elm) {                    /* cached mode and cache hit */
2008     pred_arr = elm->pred_arr;
2009   } else {                      /* not cached mode or cache miss */
2010     double *cost_arr = NULL;
2011     xbt_heap_t pqueue = NULL;
2012     int i = 0;
2013
2014     int nr_nodes = xbt_dynar_length(nodes);
2015     cost_arr = xbt_new0(double, nr_nodes);      /* link cost from src to other hosts */
2016     pred_arr = xbt_new0(int, nr_nodes); /* predecessors in path from src */
2017     pqueue = xbt_heap_new(nr_nodes, xbt_free);
2018
2019     /* initialize */
2020     cost_arr[src_node_id] = 0.0;
2021
2022     for (i = 0; i < nr_nodes; i++) {
2023       if (i != src_node_id) {
2024         cost_arr[i] = DBL_MAX;
2025       }
2026
2027       pred_arr[i] = 0;
2028
2029       /* initialize priority queue */
2030       nodeid = xbt_new0(int, 1);
2031       *nodeid = i;
2032       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
2033
2034     }
2035
2036     /* apply dijkstra using the indexes from the graph's node array */
2037     while (xbt_heap_size(pqueue) > 0) {
2038       int *v_id = xbt_heap_pop(pqueue);
2039       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
2040       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
2041       xbt_edge_t edge = NULL;
2042       unsigned int cursor;
2043
2044       xbt_dynar_foreach(out_edges, cursor, edge) {
2045         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
2046         graph_node_data_t data = xbt_graph_node_get_data(u_node);
2047         int u_id = data->graph_id;
2048         route_extended_t tmp_e_route =
2049             (route_extended_t) xbt_graph_edge_get_data(edge);
2050         int cost_v_u = (tmp_e_route->generic_route.link_list)->used;    /* count of links, old model assume 1 */
2051
2052         if (cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
2053           pred_arr[u_id] = *v_id;
2054           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
2055           nodeid = xbt_new0(int, 1);
2056           *nodeid = u_id;
2057           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
2058         }
2059       }
2060
2061       /* free item popped from pqueue */
2062       xbt_free(v_id);
2063     }
2064
2065     xbt_free(cost_arr);
2066     xbt_heap_free(pqueue);
2067   }
2068
2069   /* compose route path with links */
2070   char *gw_src = NULL, *gw_dst =
2071       NULL, *prev_gw_src, *prev_gw_dst, *first_gw = NULL;
2072
2073   for (v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
2074     xbt_node_t node_pred_v =
2075         xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
2076     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
2077     xbt_edge_t edge =
2078         xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
2079
2080     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id,
2081                 *dst_id);
2082
2083     prev_gw_src = gw_src;
2084     prev_gw_dst = gw_dst;
2085
2086     e_route = (route_extended_t) xbt_graph_edge_get_data(edge);
2087     gw_src = e_route->src_gateway;
2088     gw_dst = e_route->dst_gateway;
2089
2090     if (v == dst_node_id)
2091       first_gw = gw_dst;
2092
2093     if (rc->hierarchy == SURF_ROUTING_RECURSIVE && v != dst_node_id
2094         && strcmp(gw_dst, prev_gw_src)) {
2095       xbt_dynar_t e_route_as_to_as =
2096           (*(global_routing->get_route)) (gw_dst, prev_gw_src);
2097       xbt_assert2(e_route_as_to_as, "no route between \"%s\" and \"%s\"",
2098                   gw_dst, prev_gw_src);
2099       links = e_route_as_to_as;
2100       int pos = 0;
2101       xbt_dynar_foreach(links, cpt, link) {
2102         xbt_dynar_insert_at(new_e_route->generic_route.link_list, pos,
2103                             &link);
2104         pos++;
2105       }
2106     }
2107
2108     links = e_route->generic_route.link_list;
2109     xbt_dynar_foreach(links, cpt, link) {
2110       xbt_dynar_unshift(new_e_route->generic_route.link_list, &link);
2111     }
2112     size++;
2113   }
2114
2115   if (rc->hierarchy == SURF_ROUTING_RECURSIVE) {
2116     new_e_route->src_gateway = xbt_strdup(gw_src);
2117     new_e_route->dst_gateway = xbt_strdup(first_gw);
2118   }
2119
2120   if (routing->cached && elm == NULL) {
2121     /* add to predecessor list of the current src-host to cache */
2122     elm = xbt_new0(struct route_cache_element, 1);
2123     elm->pred_arr = pred_arr;
2124     elm->size = size;
2125     xbt_dict_set_ext(routing->route_cache, (char *) (&src_id), sizeof(int),
2126                      (xbt_set_elm_t) elm, &route_cache_elem_free);
2127   }
2128
2129   if (!routing->cached)
2130     xbt_free(pred_arr);
2131
2132   return new_e_route;
2133 }
2134
2135 static void dijkstra_finalize(routing_component_t rc)
2136 {
2137   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
2138
2139   if (routing) {
2140     xbt_graph_free_graph(routing->route_graph, &xbt_free,
2141                          &graph_edge_data_free, &xbt_free);
2142     xbt_dict_free(&routing->graph_node_map);
2143     if (routing->cached)
2144       xbt_dict_free(&routing->route_cache);
2145     /* Delete bypass dict */
2146     xbt_dict_free(&routing->generic_routing.bypassRoutes);
2147     /* Delete index dict */
2148     xbt_dict_free(&(routing->generic_routing.to_index));
2149     /* Delete structure */
2150     xbt_free(routing);
2151   }
2152 }
2153
2154 /* Creation routing model functions */
2155
2156 static void *model_dijkstra_both_create(int cached)
2157 {
2158   routing_component_dijkstra_t new_component =
2159       xbt_new0(s_routing_component_dijkstra_t, 1);
2160   new_component->generic_routing.set_processing_unit =
2161       generic_set_processing_unit;
2162   new_component->generic_routing.set_autonomous_system =
2163       generic_set_autonomous_system;
2164   new_component->generic_routing.set_route = model_dijkstra_both_set_route;
2165   new_component->generic_routing.set_ASroute = model_dijkstra_both_set_route; //TODO
2166   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
2167   new_component->generic_routing.get_route = dijkstra_get_route;
2168   new_component->generic_routing.get_latency = generic_get_link_latency;
2169   new_component->generic_routing.get_onelink_routes =
2170       dijkstra_get_onelink_routes;
2171   new_component->generic_routing.get_bypass_route =
2172       generic_get_bypassroute;
2173   new_component->generic_routing.finalize = dijkstra_finalize;
2174   new_component->cached = cached;
2175   new_component->generic_routing.to_index = xbt_dict_new();
2176   new_component->generic_routing.bypassRoutes = xbt_dict_new();
2177   return new_component;
2178 }
2179
2180 static void *model_dijkstra_create(void)
2181 {
2182   return model_dijkstra_both_create(0);
2183 }
2184
2185 static void *model_dijkstracache_create(void)
2186 {
2187   return model_dijkstra_both_create(1);
2188 }
2189
2190 static void model_dijkstra_both_load(void)
2191 {
2192   /* use "surfxml_add_callback" to add a parse function call */
2193 }
2194
2195 static void model_dijkstra_both_unload(void)
2196 {
2197   /* use "surfxml_del_callback" to remove a parse function call */
2198 }
2199
2200 static void model_dijkstra_both_end(void)
2201 {
2202   routing_component_dijkstra_t routing =
2203       (routing_component_dijkstra_t) current_routing;
2204
2205   xbt_node_t node = NULL;
2206   unsigned int cursor2;
2207   xbt_dynar_t nodes = NULL;
2208
2209   /* Create the topology graph */
2210   routing->route_graph = xbt_graph_new_graph(1, NULL);
2211   routing->graph_node_map = xbt_dict_new();
2212
2213   if (routing->cached && !routing->route_cache)
2214     routing->route_cache = xbt_dict_new();
2215
2216   /* Add the loopback if needed */
2217   if (current_routing->hierarchy == SURF_ROUTING_BASE)
2218     add_loopback_dijkstra(routing);
2219
2220   /* initialize graph indexes in nodes after graph has been built */
2221   nodes = xbt_graph_get_nodes(routing->route_graph);
2222
2223   xbt_dynar_foreach(nodes, cursor2, node) {
2224     graph_node_data_t data = xbt_graph_node_get_data(node);
2225     data->graph_id = cursor2;
2226   }
2227
2228 }
2229 static void model_dijkstra_both_set_route (routing_component_t rc, const char *src,
2230                      const char *dst, name_route_extended_t route)
2231 {
2232         routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
2233         int *src_id, *dst_id;
2234         src_id = xbt_dict_get_or_null(rc->to_index, src);
2235         dst_id = xbt_dict_get_or_null(rc->to_index, dst);
2236
2237         if (routing->cached && !routing->route_cache)
2238         routing->route_cache = xbt_dict_new();
2239
2240         if( A_surfxml_route_symmetrical == A_surfxml_route_symmetrical_YES
2241                 || A_surfxml_ASroute_symmetrical == A_surfxml_ASroute_symmetrical_YES )
2242                 xbt_die("Route symmetrical not supported on model dijkstra");
2243
2244         if(!route->dst_gateway && !route->src_gateway)
2245           DEBUG2("Load Route from \"%s\" to \"%s\"", src, dst);
2246         else
2247           DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
2248                          route->src_gateway, dst, route->dst_gateway);
2249
2250         route_extended_t e_route =
2251                 generic_new_extended_route(current_routing->hierarchy, route, 1);
2252         route_new_dijkstra(routing, *src_id, *dst_id, e_route);
2253 }
2254
2255 #ifdef HAVE_PCRE_LIB
2256 /* ************************************************** */
2257 /* ************** RULE-BASED ROUTING **************** */
2258
2259 /* Routing model structure */
2260
2261 typedef struct {
2262   s_routing_component_t generic_routing;
2263   xbt_dict_t dict_processing_units;
2264   xbt_dict_t dict_autonomous_systems;
2265   xbt_dynar_t list_route;
2266   xbt_dynar_t list_ASroute;
2267 } s_routing_component_rulebased_t, *routing_component_rulebased_t;
2268
2269 typedef struct s_rule_route s_rule_route_t, *rule_route_t;
2270 typedef struct s_rule_route_extended s_rule_route_extended_t,
2271     *rule_route_extended_t;
2272
2273 struct s_rule_route {
2274   xbt_dynar_t re_str_link;      // dynar of char*
2275   pcre *re_src;
2276   pcre *re_dst;
2277 };
2278
2279 struct s_rule_route_extended {
2280   s_rule_route_t generic_rule_route;
2281   char *re_src_gateway;
2282   char *re_dst_gateway;
2283 };
2284
2285 static void rule_route_free(void *e)
2286 {
2287   rule_route_t *elem = (rule_route_t *) (e);
2288   if (*elem) {
2289     xbt_dynar_free(&(*elem)->re_str_link);
2290     pcre_free((*elem)->re_src);
2291     pcre_free((*elem)->re_dst);
2292     xbt_free(*elem);
2293   }
2294   *elem = NULL;
2295 }
2296
2297 static void rule_route_extended_free(void *e)
2298 {
2299   rule_route_extended_t *elem = (rule_route_extended_t *) e;
2300   if (*elem) {
2301     xbt_dynar_free(&(*elem)->generic_rule_route.re_str_link);
2302     pcre_free((*elem)->generic_rule_route.re_src);
2303     pcre_free((*elem)->generic_rule_route.re_dst);
2304     xbt_free((*elem)->re_src_gateway);
2305     xbt_free((*elem)->re_dst_gateway);
2306     xbt_free(*elem);
2307   }
2308 }
2309
2310 /* Parse routing model functions */
2311
2312 static void model_rulebased_set_processing_unit(routing_component_t rc,
2313                                                 const char *name)
2314 {
2315   routing_component_rulebased_t routing =
2316       (routing_component_rulebased_t) rc;
2317   xbt_dict_set(routing->dict_processing_units, name, (void *) (-1), NULL);
2318 }
2319
2320 static void model_rulebased_set_autonomous_system(routing_component_t rc,
2321                                                   const char *name)
2322 {
2323   routing_component_rulebased_t routing =
2324       (routing_component_rulebased_t) rc;
2325   xbt_dict_set(routing->dict_autonomous_systems, name, (void *) (-1),
2326                NULL);
2327 }
2328
2329 static void model_rulebased_set_route(routing_component_t rc,
2330                                       const char *src, const char *dst,
2331                                       name_route_extended_t route)
2332 {
2333   routing_component_rulebased_t routing =
2334       (routing_component_rulebased_t) rc;
2335   rule_route_t ruleroute = xbt_new0(s_rule_route_t, 1);
2336   const char *error;
2337   int erroffset;
2338   ruleroute->re_src = pcre_compile(src, 0, &error, &erroffset, NULL);
2339   xbt_assert3(ruleroute->re_src,
2340               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2341               erroffset, src, error);
2342   ruleroute->re_dst = pcre_compile(dst, 0, &error, &erroffset, NULL);
2343   xbt_assert3(ruleroute->re_src,
2344               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2345               erroffset, dst, error);
2346   ruleroute->re_str_link = route->generic_route.link_list;
2347   xbt_dynar_push(routing->list_route, &ruleroute);
2348   xbt_free(route);
2349 }
2350
2351 static void model_rulebased_set_ASroute(routing_component_t rc,
2352                                         const char *src, const char *dst,
2353                                         name_route_extended_t route)
2354 {
2355   routing_component_rulebased_t routing =
2356       (routing_component_rulebased_t) rc;
2357   rule_route_extended_t ruleroute_e = xbt_new0(s_rule_route_extended_t, 1);
2358   const char *error;
2359   int erroffset;
2360   ruleroute_e->generic_rule_route.re_src =
2361       pcre_compile(src, 0, &error, &erroffset, NULL);
2362   xbt_assert3(ruleroute_e->generic_rule_route.re_src,
2363               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2364               erroffset, src, error);
2365   ruleroute_e->generic_rule_route.re_dst =
2366       pcre_compile(dst, 0, &error, &erroffset, NULL);
2367   xbt_assert3(ruleroute_e->generic_rule_route.re_src,
2368               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2369               erroffset, dst, error);
2370   ruleroute_e->generic_rule_route.re_str_link =
2371       route->generic_route.link_list;
2372   ruleroute_e->re_src_gateway = route->src_gateway;
2373   ruleroute_e->re_dst_gateway = route->dst_gateway;
2374   xbt_dynar_push(routing->list_ASroute, &ruleroute_e);
2375 //  xbt_free(route->src_gateway);
2376 //  xbt_free(route->dst_gateway);
2377   xbt_free(route);
2378 }
2379
2380 static void model_rulebased_set_bypassroute(routing_component_t rc,
2381                                             const char *src,
2382                                             const char *dst,
2383                                             route_extended_t e_route)
2384 {
2385   xbt_die("bypass routing not supported for Route-Based model");
2386 }
2387
2388 #define BUFFER_SIZE 4096        /* result buffer size */
2389 #define OVECCOUNT 30            /* should be a multiple of 3 */
2390
2391 static char *remplace(char *value, const char **src_list, int src_size,
2392                       const char **dst_list, int dst_size)
2393 {
2394
2395   char result_result[BUFFER_SIZE];
2396   int i_result_buffer;
2397   int value_length = (int) strlen(value);
2398   int number = 0;
2399
2400   int i = 0;
2401   i_result_buffer = 0;
2402   do {
2403     if (value[i] == '$') {
2404       i++;                      // skip $
2405
2406       // find the number
2407       int number_length = 0;
2408       while ('0' <= value[i + number_length]
2409              && value[i + number_length] <= '9') {
2410         number_length++;
2411       }
2412       xbt_assert2(number_length != 0,
2413                   "bad string parameter, no number indication, at offset: %d (\"%s\")",
2414                   i, value);
2415
2416       // solve number
2417       number = atoi(value + i);
2418       i = i + number_length;
2419       xbt_assert2(i + 2 < value_length,
2420                   "bad string parameter, too few chars, at offset: %d (\"%s\")",
2421                   i, value);
2422
2423       // solve the indication
2424       const char **param_list;
2425       int param_size;
2426       if (value[i] == 's' && value[i + 1] == 'r' && value[i + 2] == 'c') {
2427         param_list = src_list;
2428         param_size = src_size;
2429       } else if (value[i] == 'd' && value[i + 1] == 's'
2430                  && value[i + 2] == 't') {
2431         param_list = dst_list;
2432         param_size = dst_size;
2433       } else {
2434         xbt_assert2(0,
2435                     "bad string parameter, support only \"src\" and \"dst\", at offset: %d (\"%s\")",
2436                     i, value);
2437       }
2438       i = i + 3;
2439
2440       xbt_assert4(param_size >= number,
2441                   "bad string parameter, not enough length param_size, at offset: %d (\"%s\") %d %d",
2442                   i, value, param_size, number);
2443
2444       const char *param = param_list[number];
2445       int size = strlen(param);
2446       int cp;
2447       for (cp = 0; cp < size; cp++) {
2448         result_result[i_result_buffer] = param[cp];
2449         i_result_buffer++;
2450         if (i_result_buffer >= BUFFER_SIZE)
2451           break;
2452       }
2453     } else {
2454       result_result[i_result_buffer] = value[i];
2455       i_result_buffer++;
2456       i++;                      // next char
2457     }
2458
2459   } while (i < value_length && i_result_buffer < BUFFER_SIZE);
2460
2461   xbt_assert2(i_result_buffer < BUFFER_SIZE,
2462               "solving string \"%s\", small buffer size (%d)", value,
2463               BUFFER_SIZE);
2464   result_result[i_result_buffer] = 0;
2465   return xbt_strdup(result_result);
2466 }
2467
2468 static route_extended_t rulebased_get_route(routing_component_t rc,
2469                                             const char *src,
2470                                             const char *dst);
2471 static xbt_dynar_t rulebased_get_onelink_routes(routing_component_t rc)
2472 {
2473   xbt_dynar_t ret = xbt_dynar_new (sizeof(onelink_t), xbt_free);
2474   routing_component_rulebased_t routing = (routing_component_rulebased_t)rc;
2475
2476   xbt_dict_cursor_t c1 = NULL;
2477   char *k1, *d1;
2478
2479   //find router
2480   char *router = NULL;
2481   xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
2482     if (strstr (k1, "router")){
2483       router = k1;
2484     }
2485   }
2486   if (!router){
2487     xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
2488   }
2489
2490   xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
2491     route_extended_t route = rulebased_get_route (rc, router, k1);
2492
2493     int number_of_links = xbt_dynar_length(route->generic_route.link_list);
2494     if (number_of_links != 3) {
2495       xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
2496     }
2497
2498     void *link_ptr;
2499     xbt_dynar_get_cpy (route->generic_route.link_list, 2, &link_ptr);
2500     onelink_t onelink = xbt_new0 (s_onelink_t, 1);
2501     onelink->src = xbt_strdup (k1);
2502     onelink->dst = xbt_strdup (router);
2503     onelink->link_ptr = link_ptr;
2504     xbt_dynar_push (ret, &onelink);
2505   }
2506   return ret;
2507 }
2508
2509 /* Business methods */
2510 static route_extended_t rulebased_get_route(routing_component_t rc,
2511                                             const char *src,
2512                                             const char *dst)
2513 {
2514   xbt_assert1(rc && src
2515               && dst,
2516               "Invalid params for \"get_route\" function at AS \"%s\"",
2517               rc->name);
2518
2519   /* set utils vars */
2520   routing_component_rulebased_t routing =
2521       (routing_component_rulebased_t) rc;
2522
2523   int are_processing_units;
2524   xbt_dynar_t rule_list;
2525   if (xbt_dict_get_or_null(routing->dict_processing_units, src)
2526       && xbt_dict_get_or_null(routing->dict_processing_units, dst)) {
2527     are_processing_units = 1;
2528     rule_list = routing->list_route;
2529   } else if (xbt_dict_get_or_null(routing->dict_autonomous_systems, src)
2530              && xbt_dict_get_or_null(routing->dict_autonomous_systems,
2531                                      dst)) {
2532     are_processing_units = 0;
2533     rule_list = routing->list_ASroute;
2534   } else
2535     xbt_assert2(NULL,
2536                 "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
2537                 src, dst);
2538
2539   int rc_src = -1;
2540   int rc_dst = -1;
2541   int src_length = (int) strlen(src);
2542   int dst_length = (int) strlen(dst);
2543
2544   xbt_dynar_t links_list =
2545       xbt_dynar_new(global_routing->size_of_link, NULL);
2546
2547   rule_route_t ruleroute;
2548   unsigned int cpt;
2549   int ovector_src[OVECCOUNT];
2550   int ovector_dst[OVECCOUNT];
2551   const char **list_src = NULL;
2552   const char **list_dst = NULL;
2553   xbt_dynar_foreach(rule_list, cpt, ruleroute) {
2554     rc_src =
2555         pcre_exec(ruleroute->re_src, NULL, src, src_length, 0, 0,
2556                   ovector_src, OVECCOUNT);
2557     if (rc_src >= 0) {
2558       rc_dst =
2559           pcre_exec(ruleroute->re_dst, NULL, dst, dst_length, 0, 0,
2560                     ovector_dst, OVECCOUNT);
2561       if (rc_dst >= 0) {
2562         xbt_assert1(!pcre_get_substring_list
2563                     (src, ovector_src, rc_src, &list_src),
2564                     "error solving substring list for src \"%s\"", src);
2565         xbt_assert1(!pcre_get_substring_list
2566                     (dst, ovector_dst, rc_dst, &list_dst),
2567                     "error solving substring list for src \"%s\"", dst);
2568         char *link_name;
2569         xbt_dynar_foreach(ruleroute->re_str_link, cpt, link_name) {
2570           char *new_link_name =
2571               remplace(link_name, list_src, rc_src, list_dst, rc_dst);
2572           void *link =
2573               xbt_dict_get_or_null(surf_network_model->resource_set,
2574                                    new_link_name);
2575           if (link)
2576             xbt_dynar_push(links_list, &link);
2577           else
2578             THROW1(mismatch_error, 0, "Link %s not found", new_link_name);
2579           xbt_free(new_link_name);
2580         }
2581       }
2582     }
2583     if (rc_src >= 0 && rc_dst >= 0)
2584       break;
2585   }
2586
2587   route_extended_t new_e_route = NULL;
2588   if (rc_src >= 0 && rc_dst >= 0) {
2589     new_e_route = xbt_new0(s_route_extended_t, 1);
2590     new_e_route->generic_route.link_list = links_list;
2591   } else if (!strcmp(src, dst) && are_processing_units) {
2592     new_e_route = xbt_new0(s_route_extended_t, 1);
2593     xbt_dynar_push(links_list, &(global_routing->loopback));
2594     new_e_route->generic_route.link_list = links_list;
2595   } else {
2596     xbt_dynar_free(&link_list);
2597   }
2598
2599   if (!are_processing_units && new_e_route) {
2600     rule_route_extended_t ruleroute_extended =
2601         (rule_route_extended_t) ruleroute;
2602     new_e_route->src_gateway =
2603         remplace(ruleroute_extended->re_src_gateway, list_src, rc_src,
2604                  list_dst, rc_dst);
2605     new_e_route->dst_gateway =
2606         remplace(ruleroute_extended->re_dst_gateway, list_src, rc_src,
2607                  list_dst, rc_dst);
2608   }
2609
2610   if (list_src)
2611     pcre_free_substring_list(list_src);
2612   if (list_dst)
2613     pcre_free_substring_list(list_dst);
2614
2615   return new_e_route;
2616 }
2617
2618 static route_extended_t rulebased_get_bypass_route(routing_component_t rc,
2619                                                    const char *src,
2620                                                    const char *dst)
2621 {
2622   return NULL;
2623 }
2624
2625 static void rulebased_finalize(routing_component_t rc)
2626 {
2627   routing_component_rulebased_t routing =
2628       (routing_component_rulebased_t) rc;
2629   if (routing) {
2630     xbt_dict_free(&routing->dict_processing_units);
2631     xbt_dict_free(&routing->dict_autonomous_systems);
2632     xbt_dynar_free(&routing->list_route);
2633     xbt_dynar_free(&routing->list_ASroute);
2634     /* Delete structure */
2635     xbt_free(routing);
2636   }
2637 }
2638
2639 /* Creation routing model functions */
2640 static void *model_rulebased_create(void)
2641 {
2642   routing_component_rulebased_t new_component =
2643       xbt_new0(s_routing_component_rulebased_t, 1);
2644   new_component->generic_routing.set_processing_unit =
2645       model_rulebased_set_processing_unit;
2646   new_component->generic_routing.set_autonomous_system =
2647       model_rulebased_set_autonomous_system;
2648   new_component->generic_routing.set_route = model_rulebased_set_route;
2649   new_component->generic_routing.set_ASroute = model_rulebased_set_ASroute;
2650   new_component->generic_routing.set_bypassroute = model_rulebased_set_bypassroute;
2651   new_component->generic_routing.get_onelink_routes = rulebased_get_onelink_routes;
2652   new_component->generic_routing.get_route = rulebased_get_route;
2653   new_component->generic_routing.get_latency = generic_get_link_latency;
2654   new_component->generic_routing.get_bypass_route = rulebased_get_bypass_route;
2655   new_component->generic_routing.finalize = rulebased_finalize;
2656   /* initialization of internal structures */
2657   new_component->dict_processing_units = xbt_dict_new();
2658   new_component->dict_autonomous_systems = xbt_dict_new();
2659   new_component->list_route = xbt_dynar_new(sizeof(rule_route_t), &rule_route_free);
2660   new_component->list_ASroute =
2661       xbt_dynar_new(sizeof(rule_route_extended_t),
2662                     &rule_route_extended_free);
2663   return new_component;
2664 }
2665
2666 static void model_rulebased_load(void)
2667 {
2668   /* use "surfxml_add_callback" to add a parse function call */
2669 }
2670
2671 static void model_rulebased_unload(void)
2672 {
2673   /* use "surfxml_del_callback" to remove a parse function call */
2674 }
2675
2676 static void model_rulebased_end(void)
2677 {
2678 }
2679
2680 #endif                          /* HAVE_PCRE_LIB */
2681
2682 /* ************************************************************************** */
2683 /* ******************************* NO ROUTING ******************************* */
2684
2685 /* Routing model structure */
2686 typedef struct {
2687   s_routing_component_t generic_routing;
2688 } s_routing_component_none_t, *routing_component_none_t;
2689
2690 /* Business methods */
2691 static xbt_dynar_t none_get_onelink_routes(routing_component_t rc)
2692 {
2693   return NULL;
2694 }
2695
2696 static route_extended_t none_get_route(routing_component_t rc,
2697                                        const char *src, const char *dst)
2698 {
2699   return NULL;
2700 }
2701
2702 static route_extended_t none_get_bypass_route(routing_component_t rc,
2703                                               const char *src,
2704                                               const char *dst)
2705 {
2706   return NULL;
2707 }
2708
2709 static void none_finalize(routing_component_t rc)
2710 {
2711   xbt_free(rc);
2712 }
2713
2714 static void none_set_processing_unit(routing_component_t rc,
2715                                      const char *name)
2716 {
2717 }
2718
2719 static void none_set_autonomous_system(routing_component_t rc,
2720                                        const char *name)
2721 {
2722 }
2723
2724 /* Creation routing model functions */
2725 static void *model_none_create(void)
2726 {
2727   routing_component_none_t new_component =
2728       xbt_new0(s_routing_component_none_t, 1);
2729   new_component->generic_routing.set_processing_unit =
2730       none_set_processing_unit;
2731   new_component->generic_routing.set_autonomous_system =
2732       none_set_autonomous_system;
2733   new_component->generic_routing.set_route = NULL;
2734   new_component->generic_routing.set_ASroute = NULL;
2735   new_component->generic_routing.set_bypassroute = NULL;
2736   new_component->generic_routing.get_route = none_get_route;
2737   new_component->generic_routing.get_onelink_routes =
2738       none_get_onelink_routes;
2739   new_component->generic_routing.get_bypass_route = none_get_bypass_route;
2740   new_component->generic_routing.finalize = none_finalize;
2741   return new_component;
2742 }
2743
2744 static void model_none_load(void)
2745 {
2746 }
2747
2748 static void model_none_unload(void)
2749 {
2750 }
2751
2752 static void model_none_end(void)
2753 {
2754 }
2755
2756 /* ************************************************** */
2757 /* ********** PATERN FOR NEW ROUTING **************** */
2758
2759 /* The minimal configuration of a new routing model need the next functions,
2760  * also you need to set at the start of the file, the new model in the model
2761  * list. Remember keep the null ending of the list.
2762  */
2763 /*** Routing model structure ***/
2764 // typedef struct {
2765 //   s_routing_component_t generic_routing;
2766 //   /* things that your routing model need */
2767 // } s_routing_component_NEW_t,*routing_component_NEW_t;
2768
2769 /*** Parse routing model functions ***/
2770 // static void model_NEW_set_processing_unit(routing_component_t rc, const char* name) {}
2771 // static void model_NEW_set_autonomous_system(routing_component_t rc, const char* name) {}
2772 // static void model_NEW_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {}
2773 // static void model_NEW_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t route) {}
2774 // static void model_NEW_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {}
2775
2776 /*** Business methods ***/
2777 // static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
2778 // static route_extended_t NEW_get_bypass_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
2779 // static void NEW_finalize(routing_component_t rc) { xbt_free(rc);}
2780
2781 /*** Creation routing model functions ***/
2782 // static void* model_NEW_create(void) {
2783 //   routing_component_NEW_t new_component =  xbt_new0(s_routing_component_NEW_t,1);
2784 //   new_component->generic_routing.set_processing_unit = model_NEW_set_processing_unit;
2785 //   new_component->generic_routing.set_autonomous_system = model_NEW_set_autonomous_system;
2786 //   new_component->generic_routing.set_route = model_NEW_set_route;
2787 //   new_component->generic_routing.set_ASroute = model_NEW_set_ASroute;
2788 //   new_component->generic_routing.set_bypassroute = model_NEW_set_bypassroute;
2789 //   new_component->generic_routing.get_route = NEW_get_route;
2790 //   new_component->generic_routing.get_bypass_route = NEW_get_bypass_route;
2791 //   new_component->generic_routing.finalize = NEW_finalize;
2792 //   /* initialization of internal structures */
2793 //   return new_component;
2794 // } /* mandatory */
2795 // static void  model_NEW_load(void) {}   /* mandatory */
2796 // static void  model_NEW_unload(void) {} /* mandatory */
2797 // static void  model_NEW_end(void) {}    /* mandatory */
2798
2799 /* ************************************************************************** */
2800 /* ************************* GENERIC PARSE FUNCTIONS ************************ */
2801
2802 static void generic_set_processing_unit(routing_component_t rc,
2803                                         const char *name)
2804 {
2805   DEBUG1("Load process unit \"%s\"", name);
2806   int *id = xbt_new0(int, 1);
2807   xbt_dict_t _to_index;
2808   _to_index = current_routing->to_index;
2809   *id = xbt_dict_length(_to_index);
2810   xbt_dict_set(_to_index, name, id, xbt_free);
2811 }
2812
2813 static void generic_set_autonomous_system(routing_component_t rc,
2814                                           const char *name)
2815 {
2816   DEBUG1("Load Autonomous system \"%s\"", name);
2817   int *id = xbt_new0(int, 1);
2818   xbt_dict_t _to_index;
2819   _to_index = current_routing->to_index;
2820   *id = xbt_dict_length(_to_index);
2821   xbt_dict_set(_to_index, name, id, xbt_free);
2822 }
2823
2824 static int surf_pointer_resource_cmp(const void *a, const void *b)
2825 {
2826   return a != b;
2827 }
2828
2829 static int surf_link_resource_cmp(const void *a, const void *b)
2830 {
2831   return !!memcmp(a,b,global_routing->size_of_link);
2832 }
2833
2834 static void generic_set_bypassroute(routing_component_t rc,
2835                                     const char *src, const char *dst,
2836                                     route_extended_t e_route)
2837 {
2838   DEBUG2("Load bypassRoute from \"%s\" to \"%s\"", src, dst);
2839   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
2840   char *route_name;
2841
2842   route_name = bprintf("%s#%s", src, dst);
2843   xbt_assert2(xbt_dynar_length(e_route->generic_route.link_list) > 0,
2844               "Invalid count of links, must be greater than zero (%s,%s)",
2845               src, dst);
2846   xbt_assert4(!xbt_dict_get_or_null(dict_bypassRoutes, route_name),
2847               "The bypass route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exists",
2848               src, e_route->src_gateway, dst, e_route->dst_gateway);
2849
2850   route_extended_t new_e_route =
2851       generic_new_extended_route(SURF_ROUTING_RECURSIVE, e_route, 0);
2852   xbt_dynar_free(&(e_route->generic_route.link_list));
2853   xbt_free(e_route);
2854
2855   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route,
2856                (void (*)(void *)) generic_free_extended_route);
2857   xbt_free(route_name);
2858 }
2859
2860 /* ************************************************************************** */
2861 /* *********************** GENERIC BUSINESS METHODS ************************* */
2862
2863 static double generic_get_link_latency(routing_component_t rc,
2864                                        const char *src, const char *dst)
2865 {
2866         route_extended_t route = rc->get_route(rc,src,dst);
2867         void * link;
2868         unsigned int i;
2869         double latency = 0.0;
2870
2871         xbt_dynar_foreach(route->generic_route.link_list,i,link) {
2872                 latency += get_link_latency(link);
2873         }
2874         generic_free_extended_route(route);
2875   return latency;
2876 }
2877
2878 static xbt_dynar_t generic_get_onelink_routes(routing_component_t rc)
2879 {
2880   xbt_die("\"generic_get_onelink_routes\" not implemented yet");
2881 }
2882
2883 static route_extended_t generic_get_bypassroute(routing_component_t rc,
2884                                                 const char *src,
2885                                                 const char *dst)
2886 {
2887   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
2888   routing_component_t src_as, dst_as;
2889   int index_src, index_dst;
2890   xbt_dynar_t path_src = NULL;
2891   xbt_dynar_t path_dst = NULL;
2892   routing_component_t current = NULL;
2893   routing_component_t *current_src = NULL;
2894   routing_component_t *current_dst = NULL;
2895
2896   /* (1) find the as where the src and dst are located */
2897   src_as = ((network_element_info_t)
2898             xbt_dict_get_or_null(global_routing->where_network_elements,
2899                                  src))->rc_component;
2900   dst_as = ((network_element_info_t)
2901             xbt_dict_get_or_null(global_routing->where_network_elements,
2902                                  dst))->rc_component;
2903   xbt_assert2(src_as
2904               && dst_as,
2905               "Ask for route \"from\"(%s) or \"to\"(%s) no found", src,
2906               dst);
2907
2908   /* (2) find the path to the root routing component */
2909   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
2910   current = src_as;
2911   while (current != NULL) {
2912     xbt_dynar_push(path_src, &current);
2913     current = current->routing_father;
2914   }
2915   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
2916   current = dst_as;
2917   while (current != NULL) {
2918     xbt_dynar_push(path_dst, &current);
2919     current = current->routing_father;
2920   }
2921
2922   /* (3) find the common father */
2923   index_src = path_src->used - 1;
2924   index_dst = path_dst->used - 1;
2925   current_src = xbt_dynar_get_ptr(path_src, index_src);
2926   current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
2927   while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
2928     routing_component_t *tmp_src, *tmp_dst;
2929     tmp_src = xbt_dynar_pop_ptr(path_src);
2930     tmp_dst = xbt_dynar_pop_ptr(path_dst);
2931     index_src--;
2932     index_dst--;
2933     current_src = xbt_dynar_get_ptr(path_src, index_src);
2934     current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
2935   }
2936
2937   int max_index_src = path_src->used - 1;
2938   int max_index_dst = path_dst->used - 1;
2939
2940   int max_index = max(max_index_src, max_index_dst);
2941   int i, max;
2942
2943   route_extended_t e_route_bypass = NULL;
2944
2945   for (max = 0; max <= max_index; max++) {
2946     for (i = 0; i < max; i++) {
2947       if (i <= max_index_src && max <= max_index_dst) {
2948         char *route_name = bprintf("%s#%s",
2949                                    (*(routing_component_t *)
2950                                     (xbt_dynar_get_ptr
2951                                      (path_src, i)))->name,
2952                                    (*(routing_component_t *)
2953                                     (xbt_dynar_get_ptr
2954                                      (path_dst, max)))->name);
2955         e_route_bypass =
2956             xbt_dict_get_or_null(dict_bypassRoutes, route_name);
2957         xbt_free(route_name);
2958       }
2959       if (e_route_bypass)
2960         break;
2961       if (max <= max_index_src && i <= max_index_dst) {
2962         char *route_name = bprintf("%s#%s",
2963                                    (*(routing_component_t *)
2964                                     (xbt_dynar_get_ptr
2965                                      (path_src, max)))->name,
2966                                    (*(routing_component_t *)
2967                                     (xbt_dynar_get_ptr
2968                                      (path_dst, i)))->name);
2969         e_route_bypass =
2970             xbt_dict_get_or_null(dict_bypassRoutes, route_name);
2971         xbt_free(route_name);
2972       }
2973       if (e_route_bypass)
2974         break;
2975     }
2976
2977     if (e_route_bypass)
2978       break;
2979
2980     if (max <= max_index_src && max <= max_index_dst) {
2981       char *route_name = bprintf("%s#%s",
2982                                  (*(routing_component_t *)
2983                                   (xbt_dynar_get_ptr
2984                                    (path_src, max)))->name,
2985                                  (*(routing_component_t *)
2986                                   (xbt_dynar_get_ptr
2987                                    (path_dst, max)))->name);
2988       e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
2989       xbt_free(route_name);
2990     }
2991     if (e_route_bypass)
2992       break;
2993   }
2994
2995   xbt_dynar_free(&path_src);
2996   xbt_dynar_free(&path_dst);
2997
2998   route_extended_t new_e_route = NULL;
2999
3000   if (e_route_bypass) {
3001     void *link;
3002     unsigned int cpt = 0;
3003     new_e_route = xbt_new0(s_route_extended_t, 1);
3004     new_e_route->src_gateway = xbt_strdup(e_route_bypass->src_gateway);
3005     new_e_route->dst_gateway = xbt_strdup(e_route_bypass->dst_gateway);
3006     new_e_route->generic_route.link_list =
3007         xbt_dynar_new(global_routing->size_of_link, NULL);
3008     xbt_dynar_foreach(e_route_bypass->generic_route.link_list, cpt, link) {
3009       xbt_dynar_push(new_e_route->generic_route.link_list, &link);
3010     }
3011   }
3012
3013   return new_e_route;
3014 }
3015
3016 /* ************************************************************************** */
3017 /* ************************* GENERIC AUX FUNCTIONS ************************** */
3018
3019 static route_t
3020 generic_new_route(e_surf_routing_hierarchy_t hierarchy,
3021                            void *data, int order)
3022 {
3023
3024   char *link_name;
3025   route_t new_route;
3026   unsigned int cpt;
3027   xbt_dynar_t links = NULL, links_id = NULL;
3028
3029   new_route = xbt_new0(s_route_t, 1);
3030   new_route->link_list =
3031       xbt_dynar_new(global_routing->size_of_link, NULL);
3032
3033   xbt_assert0(hierarchy == SURF_ROUTING_BASE,
3034               "the hierarchy type is not SURF_ROUTING_BASE");
3035
3036   links = ((route_t) data)->link_list;
3037
3038
3039   links_id = new_route->link_list;
3040
3041   xbt_dynar_foreach(links, cpt, link_name) {
3042
3043     void *link =
3044         xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
3045     if (link) {
3046       if (order)
3047         xbt_dynar_push(links_id, &link);
3048       else
3049         xbt_dynar_unshift(links_id, &link);
3050     } else
3051       THROW1(mismatch_error, 0, "Link %s not found", link_name);
3052   }
3053
3054   return new_route;
3055 }
3056
3057 static route_extended_t
3058 generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy,
3059                            void *data, int order)
3060 {
3061
3062   char *link_name;
3063   route_extended_t e_route, new_e_route;
3064   route_t route;
3065   unsigned int cpt;
3066   xbt_dynar_t links = NULL, links_id = NULL;
3067
3068   new_e_route = xbt_new0(s_route_extended_t, 1);
3069   new_e_route->generic_route.link_list =
3070       xbt_dynar_new(global_routing->size_of_link, NULL);
3071   new_e_route->src_gateway = NULL;
3072   new_e_route->dst_gateway = NULL;
3073
3074   xbt_assert0(hierarchy == SURF_ROUTING_BASE
3075               || hierarchy == SURF_ROUTING_RECURSIVE,
3076               "the hierarchy type is not defined");
3077
3078   if (hierarchy == SURF_ROUTING_BASE) {
3079
3080     route = (route_t) data;
3081     links = route->link_list;
3082
3083   } else if (hierarchy == SURF_ROUTING_RECURSIVE) {
3084
3085     e_route = (route_extended_t) data;
3086     xbt_assert0(e_route->src_gateway
3087                 && e_route->dst_gateway, "bad gateway, is null");
3088     links = e_route->generic_route.link_list;
3089
3090     /* remeber not erase the gateway names */
3091     new_e_route->src_gateway = e_route->src_gateway;
3092     new_e_route->dst_gateway = e_route->dst_gateway;
3093   }
3094
3095   links_id = new_e_route->generic_route.link_list;
3096
3097   xbt_dynar_foreach(links, cpt, link_name) {
3098
3099     void *link =
3100         xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
3101     if (link) {
3102       if (order)
3103         xbt_dynar_push(links_id, &link);
3104       else
3105         xbt_dynar_unshift(links_id, &link);
3106     } else
3107       THROW1(mismatch_error, 0, "Link %s not found", link_name);
3108   }
3109
3110   return new_e_route;
3111 }
3112
3113 static void generic_free_route(route_t route)
3114 {
3115   if (route) {
3116     xbt_dynar_free(&(route->link_list));
3117     xbt_free(route);
3118   }
3119 }
3120
3121 static void generic_free_extended_route(route_extended_t e_route)
3122 {
3123   if (e_route) {
3124     xbt_dynar_free(&(e_route->generic_route.link_list));
3125     if (e_route->src_gateway)
3126       xbt_free(e_route->src_gateway);
3127     if (e_route->dst_gateway)
3128       xbt_free(e_route->dst_gateway);
3129     xbt_free(e_route);
3130   }
3131 }
3132
3133 static routing_component_t generic_as_exist(routing_component_t find_from,
3134                                             routing_component_t to_find)
3135 {
3136   //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
3137   xbt_dict_cursor_t cursor = NULL;
3138   char *key;
3139   int found = 0;
3140   routing_component_t elem;
3141   xbt_dict_foreach(find_from->routing_sons, cursor, key, elem) {
3142     if (to_find == elem || generic_as_exist(elem, to_find)) {
3143       found = 1;
3144       break;
3145     }
3146   }
3147   if (found)
3148     return to_find;
3149   return NULL;
3150 }
3151
3152 static routing_component_t
3153 generic_autonomous_system_exist(routing_component_t rc, char *element)
3154 {
3155   //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
3156   routing_component_t element_as, result, elem;
3157   xbt_dict_cursor_t cursor = NULL;
3158   char *key;
3159   element_as = ((network_element_info_t)
3160                 xbt_dict_get_or_null
3161                 (global_routing->where_network_elements,
3162                  element))->rc_component;
3163   result = ((routing_component_t) - 1);
3164   if (element_as != rc)
3165     result = generic_as_exist(rc, element_as);
3166
3167   int found = 0;
3168   if (result) {
3169     xbt_dict_foreach(element_as->routing_sons, cursor, key, elem) {
3170       found = !strcmp(elem->name, element);
3171       if (found)
3172         break;
3173     }
3174     if (found)
3175       return element_as;
3176   }
3177   return NULL;
3178 }
3179
3180 static routing_component_t
3181 generic_processing_units_exist(routing_component_t rc, char *element)
3182 {
3183   routing_component_t element_as;
3184   element_as = ((network_element_info_t)
3185                 xbt_dict_get_or_null
3186                 (global_routing->where_network_elements,
3187                  element))->rc_component;
3188   if (element_as == rc)
3189     return element_as;
3190   return generic_as_exist(rc, element_as);
3191 }
3192
3193 static void generic_src_dst_check(routing_component_t rc, const char *src,
3194                                   const char *dst)
3195 {
3196
3197   routing_component_t src_as = ((network_element_info_t)
3198                                 xbt_dict_get_or_null
3199                                 (global_routing->where_network_elements,
3200                                  src))->rc_component;
3201   routing_component_t dst_as = ((network_element_info_t)
3202                                 xbt_dict_get_or_null
3203                                 (global_routing->where_network_elements,
3204                                  dst))->rc_component;
3205
3206   xbt_assert3(src_as != NULL && dst_as != NULL,
3207               "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
3208               src, dst, rc->name);
3209   xbt_assert4(src_as == dst_as,
3210               "The src(%s in %s) and dst(%s in %s) are in differents AS",
3211               src, src_as->name, dst, dst_as->name);
3212   xbt_assert2(rc == dst_as,
3213               "The routing component of src and dst is not the same as the network elements belong (%s==%s)",
3214               rc->name, dst_as->name);
3215 }
3216
3217 static void routing_parse_Sconfig(void)
3218 {
3219   //TODO
3220   DEBUG0("WARNING tag config not yet implemented.");
3221   DEBUG1("Configuration name = %s",A_surfxml_config_id);
3222 }
3223
3224 static void routing_parse_Econfig(void)
3225 {
3226   //TODO
3227   xbt_dict_cursor_t cursor = NULL;
3228   char *key;
3229   char *elem;
3230   xbt_dict_foreach(current_property_set, cursor, key, elem) {
3231           DEBUG2("property : %s = %s",key,elem);
3232         }
3233 }
3234
3235 static void routing_parse_Scluster(void)
3236 {
3237   static int AX_ptr = 0;
3238
3239   char *cluster_id = A_surfxml_cluster_id;
3240   char *cluster_prefix = A_surfxml_cluster_prefix;
3241   char *cluster_suffix = A_surfxml_cluster_suffix;
3242   char *cluster_radical = A_surfxml_cluster_radical;
3243   char *cluster_power = A_surfxml_cluster_power;
3244   char *cluster_core = A_surfxml_cluster_core;
3245   char *cluster_bw = A_surfxml_cluster_bw;
3246   char *cluster_lat = A_surfxml_cluster_lat;
3247   char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
3248   char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
3249   char *host_id, *groups, *link_id = NULL;
3250   char *router_id, *link_router, *link_backbone;
3251 #ifdef HAVE_PCRE_LIB
3252   char *route_src_dst;
3253 #endif
3254   unsigned int iter;
3255   int start, end, i;
3256   xbt_dynar_t radical_elements;
3257   xbt_dynar_t radical_ends;
3258   int cluster_sharing_policy = AX_surfxml_cluster_sharing_policy;
3259   int cluster_bb_sharing_policy = AX_surfxml_cluster_bb_sharing_policy;
3260
3261 #ifndef HAVE_PCRE_LIB
3262   xbt_dynar_t tab_elements_num = xbt_dynar_new(sizeof(int), NULL);
3263   char *route_src, *route_dst;
3264   int j;
3265 #endif
3266
3267   static unsigned int surfxml_buffer_stack_stack_ptr = 1;
3268   static unsigned int surfxml_buffer_stack_stack[1024];
3269
3270   surfxml_buffer_stack_stack[0] = 0;
3271
3272   surfxml_bufferstack_push(1);
3273
3274   SURFXML_BUFFER_SET(AS_id, cluster_id);
3275 #ifdef HAVE_PCRE_LIB
3276   SURFXML_BUFFER_SET(AS_routing, "RuleBased");
3277   DEBUG1("<AS id=\"%s\"\trouting=\"RuleBased\">", cluster_id);
3278 #else
3279   SURFXML_BUFFER_SET(AS_routing, "Full");
3280   DEBUG1("<AS id=\"%s\"\trouting=\"Full\">", cluster_id);
3281 #endif
3282   SURFXML_START_TAG(AS);
3283
3284   radical_elements = xbt_str_split(cluster_radical, ",");
3285   xbt_dynar_foreach(radical_elements, iter, groups) {
3286     radical_ends = xbt_str_split(groups, "-");
3287     switch (xbt_dynar_length(radical_ends)) {
3288     case 1:
3289       surf_parse_get_int(&start,
3290                          xbt_dynar_get_as(radical_ends, 0, char *));
3291       host_id = bprintf("%s%d%s", cluster_prefix, start, cluster_suffix);
3292 #ifndef HAVE_PCRE_LIB
3293       xbt_dynar_push_as(tab_elements_num, int, start);
3294 #endif
3295       link_id = bprintf("%s_link_%d", cluster_id, start);
3296
3297       DEBUG2("<host\tid=\"%s\"\tpower=\"%s\"/>", host_id, cluster_power);
3298       A_surfxml_host_state = A_surfxml_host_state_ON;
3299       SURFXML_BUFFER_SET(host_id, host_id);
3300       SURFXML_BUFFER_SET(host_power, cluster_power);
3301       SURFXML_BUFFER_SET(host_core, cluster_core);
3302       SURFXML_BUFFER_SET(host_availability, "1.0");
3303       SURFXML_BUFFER_SET(host_availability_file, "");
3304       SURFXML_BUFFER_SET(host_state_file, "");
3305       SURFXML_START_TAG(host);
3306       SURFXML_END_TAG(host);
3307
3308       DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id,cluster_bw, cluster_lat);
3309       A_surfxml_link_state = A_surfxml_link_state_ON;
3310       A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3311       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3312           {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3313       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
3314           {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3315       SURFXML_BUFFER_SET(link_id, link_id);
3316       SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
3317       SURFXML_BUFFER_SET(link_latency, cluster_lat);
3318       SURFXML_BUFFER_SET(link_bandwidth_file, "");
3319       SURFXML_BUFFER_SET(link_latency_file, "");
3320       SURFXML_BUFFER_SET(link_state_file, "");
3321       SURFXML_START_TAG(link);
3322       SURFXML_END_TAG(link);
3323
3324       free(link_id);
3325       free(host_id);
3326       break;
3327
3328     case 2:
3329
3330       surf_parse_get_int(&start,
3331                          xbt_dynar_get_as(radical_ends, 0, char *));
3332       surf_parse_get_int(&end, xbt_dynar_get_as(radical_ends, 1, char *));
3333       DEBUG2("Create hosts and links from %d to %d", start, end);
3334       for (i = start; i <= end; i++) {
3335         host_id = bprintf("%s%d%s", cluster_prefix, i, cluster_suffix);
3336 #ifndef HAVE_PCRE_LIB
3337         xbt_dynar_push_as(tab_elements_num, int, i);
3338 #endif
3339         link_id = bprintf("%s_link_%d", cluster_id, i);
3340
3341         DEBUG2("<host\tid=\"%s\"\tpower=\"%s\"/>", host_id, cluster_power);
3342         A_surfxml_host_state = A_surfxml_host_state_ON;
3343         SURFXML_BUFFER_SET(host_id, host_id);
3344         SURFXML_BUFFER_SET(host_power, cluster_power);
3345         SURFXML_BUFFER_SET(host_core, cluster_core);
3346         SURFXML_BUFFER_SET(host_availability, "1.0");
3347         SURFXML_BUFFER_SET(host_availability_file, "");
3348         SURFXML_BUFFER_SET(host_state_file, "");
3349         SURFXML_START_TAG(host);
3350         SURFXML_END_TAG(host);
3351
3352         DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id,cluster_bw, cluster_lat);
3353         A_surfxml_link_state = A_surfxml_link_state_ON;
3354         A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3355         if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3356             {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3357         if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
3358             {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3359         SURFXML_BUFFER_SET(link_id, link_id);
3360         SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
3361         SURFXML_BUFFER_SET(link_latency, cluster_lat);
3362         SURFXML_BUFFER_SET(link_bandwidth_file, "");
3363         SURFXML_BUFFER_SET(link_latency_file, "");
3364         SURFXML_BUFFER_SET(link_state_file, "");
3365         SURFXML_START_TAG(link);
3366         SURFXML_END_TAG(link);
3367
3368         free(link_id);
3369         free(host_id);
3370       }
3371       break;
3372
3373     default:
3374       DEBUG0("Malformed radical");
3375     }
3376
3377     xbt_dynar_free(&radical_ends);
3378   }
3379   xbt_dynar_free(&radical_elements);
3380
3381   DEBUG0(" ");
3382   router_id =
3383       bprintf("%s%s_router%s", cluster_prefix, cluster_id,
3384               cluster_suffix);
3385   link_router = bprintf("%s_link_%s_router", cluster_id, cluster_id);
3386   link_backbone = bprintf("%s_backbone", cluster_id);
3387
3388   DEBUG1("<router id=\"%s\"/>", router_id);
3389   SURFXML_BUFFER_SET(router_id, router_id);;
3390   SURFXML_START_TAG(router);
3391   SURFXML_END_TAG(router);
3392
3393   DEBUG3("<link\tid=\"%s\" bw=\"%s\" lat=\"%s\"/>", link_router,cluster_bw, cluster_lat);
3394   A_surfxml_link_state = A_surfxml_link_state_ON;
3395   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3396   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3397   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3398   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
3399   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3400   SURFXML_BUFFER_SET(link_id, link_router);
3401   SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
3402   SURFXML_BUFFER_SET(link_latency, cluster_lat);
3403   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3404   SURFXML_BUFFER_SET(link_latency_file, "");
3405   SURFXML_BUFFER_SET(link_state_file, "");
3406   SURFXML_START_TAG(link);
3407   SURFXML_END_TAG(link);
3408
3409   DEBUG3("<link\tid=\"%s\" bw=\"%s\" lat=\"%s\"/>", link_backbone,cluster_bw, cluster_lat);
3410   A_surfxml_link_state = A_surfxml_link_state_ON;
3411   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3412   if(cluster_bb_sharing_policy == A_surfxml_cluster_bb_sharing_policy_FATPIPE)
3413   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3414   SURFXML_BUFFER_SET(link_id, link_backbone);
3415   SURFXML_BUFFER_SET(link_bandwidth, cluster_bb_bw);
3416   SURFXML_BUFFER_SET(link_latency, cluster_bb_lat);
3417   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3418   SURFXML_BUFFER_SET(link_latency_file, "");
3419   SURFXML_BUFFER_SET(link_state_file, "");
3420   SURFXML_START_TAG(link);
3421   SURFXML_END_TAG(link);
3422
3423   DEBUG0(" ");
3424
3425 #ifdef HAVE_PCRE_LIB
3426   char *new_suffix = xbt_strdup("");
3427
3428   radical_elements = xbt_str_split(cluster_suffix, ".");
3429   xbt_dynar_foreach(radical_elements, iter, groups) {
3430     if (strcmp(groups, "")) {
3431       char *old_suffix = new_suffix;
3432       new_suffix = bprintf("%s\\.%s", old_suffix, groups);
3433       free(old_suffix);
3434     }
3435   }
3436   route_src_dst = bprintf("%s(.*)%s", cluster_prefix, new_suffix);
3437   xbt_dynar_free(&radical_elements);
3438   free(new_suffix);
3439
3440   char *pcre_link_src = bprintf("%s_link_$1src", cluster_id);
3441   char *pcre_link_backbone = bprintf("%s_backbone", cluster_id);
3442   char *pcre_link_dst = bprintf("%s_link_$1dst", cluster_id);
3443
3444   DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", route_src_dst, route_src_dst);
3445   DEBUG0("symmetrical=\"NO\">");
3446   SURFXML_BUFFER_SET(route_src, route_src_dst);
3447   SURFXML_BUFFER_SET(route_dst, route_src_dst);
3448   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3449   SURFXML_START_TAG(route);
3450
3451   DEBUG1("<link_ctn\tid=\"%s\"/>", pcre_link_src);
3452   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_src);
3453   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3454   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3455   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
3456   SURFXML_START_TAG(link_ctn);
3457   SURFXML_END_TAG(link_ctn);
3458
3459   DEBUG1("<link_ctn\tid=\"%s\"/>", pcre_link_backbone);
3460   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_backbone);
3461   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3462   SURFXML_START_TAG(link_ctn);
3463   SURFXML_END_TAG(link_ctn);
3464
3465   DEBUG1("<link_ctn\tid=\"%s\"/>", pcre_link_dst);
3466   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_dst);
3467   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3468   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3469   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_DOWN;}
3470   SURFXML_START_TAG(link_ctn);
3471   SURFXML_END_TAG(link_ctn);
3472
3473   DEBUG0("</route>");
3474   SURFXML_END_TAG(route);
3475
3476   free(pcre_link_dst);
3477   free(pcre_link_backbone);
3478   free(pcre_link_src);
3479   free(route_src_dst);
3480 #else
3481   for (i = 0; i <= xbt_dynar_length(tab_elements_num); i++) {
3482     for (j = 0; j <= xbt_dynar_length(tab_elements_num); j++) {
3483       if (i == xbt_dynar_length(tab_elements_num)) {
3484         route_src = router_id;
3485       } else {
3486         route_src =
3487             bprintf("%s%d%s", cluster_prefix,
3488                     xbt_dynar_get_as(tab_elements_num, i, int),
3489                     cluster_suffix);
3490       }
3491
3492       if (j == xbt_dynar_length(tab_elements_num)) {
3493         route_dst = router_id;
3494       } else {
3495         route_dst =
3496             bprintf("%s%d%s", cluster_prefix,
3497                     xbt_dynar_get_as(tab_elements_num, j, int),
3498                     cluster_suffix);
3499       }
3500
3501       DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", route_src, route_dst);
3502       DEBUG0("symmetrical=\"NO\">");
3503       SURFXML_BUFFER_SET(route_src, route_src);
3504       SURFXML_BUFFER_SET(route_dst, route_dst);
3505       A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3506       SURFXML_START_TAG(route);
3507
3508       if (i == xbt_dynar_length(tab_elements_num)) {
3509         route_src = link_router;
3510       } else {
3511         route_src =
3512             bprintf("%s_link_%d", cluster_id,
3513                     xbt_dynar_get_as(tab_elements_num, i, int));
3514       }
3515
3516       if (j == xbt_dynar_length(tab_elements_num)) {
3517         route_dst = link_router;
3518       } else {
3519         route_dst =
3520             bprintf("%s_link_%d", cluster_id,
3521                     xbt_dynar_get_as(tab_elements_num, j, int));
3522       }
3523
3524       DEBUG1("<link_ctn\tid=\"%s\"/>", route_src);
3525       SURFXML_BUFFER_SET(link_ctn_id, route_src);
3526       A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3527       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3528       {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
3529       SURFXML_START_TAG(link_ctn);
3530       SURFXML_END_TAG(link_ctn);
3531
3532       DEBUG1("<link_ctn\tid=\"%s_backbone\"/>", cluster_id);
3533       SURFXML_BUFFER_SET(link_ctn_id, bprintf("%s_backbone", cluster_id));
3534       A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3535       SURFXML_START_TAG(link_ctn);
3536       SURFXML_END_TAG(link_ctn);
3537
3538       DEBUG1("<link_ctn\tid=\"%s\"/>", route_dst);
3539       SURFXML_BUFFER_SET(link_ctn_id, route_dst);
3540       A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3541       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3542       {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_DOWN;}
3543       SURFXML_START_TAG(link_ctn);
3544       SURFXML_END_TAG(link_ctn);
3545
3546       DEBUG0("</route>");
3547       SURFXML_END_TAG(route);
3548     }
3549   }
3550   xbt_dynar_free(&tab_elements_num);
3551   free(router_id);
3552
3553 #endif
3554
3555   free(link_backbone);
3556   free(link_router);
3557
3558   DEBUG0("</AS>");
3559   SURFXML_END_TAG(AS);
3560   DEBUG0(" ");
3561
3562   surfxml_bufferstack_pop(1);
3563 }
3564
3565 static void routing_parse_Speer(void)
3566 {
3567   static int AX_ptr = 0;
3568
3569   char *peer_id = A_surfxml_peer_id;
3570   char *peer_power = A_surfxml_peer_power;
3571   char *peer_bw_in = A_surfxml_peer_bw_in;
3572   char *peer_bw_out = A_surfxml_peer_bw_out;
3573   char *peer_lat = A_surfxml_peer_lat;
3574   char *peer_coord = A_surfxml_peer_coordinates;
3575
3576   char *host_id = NULL;
3577   char *router_id, *link_router, *link_backbone, *link_id_up, *link_id_down;
3578
3579 #ifdef HAVE_PCRE_LIB
3580
3581 #endif
3582
3583   int peer_sharing_policy = AX_surfxml_peer_sharing_policy;
3584
3585 #ifndef HAVE_PCRE_LIB
3586   //xbt_dynar_t tab_elements_num = xbt_dynar_new(sizeof(int), NULL);
3587   //char *route_src, *route_dst;
3588   //int j;
3589 #endif
3590
3591   static unsigned int surfxml_buffer_stack_stack_ptr = 1;
3592   static unsigned int surfxml_buffer_stack_stack[1024];
3593
3594   surfxml_buffer_stack_stack[0] = 0;
3595
3596   surfxml_bufferstack_push(1);
3597
3598   SURFXML_BUFFER_SET(AS_id, peer_id);
3599 #ifdef HAVE_PCRE_LIB
3600   SURFXML_BUFFER_SET(AS_routing, "RuleBased");
3601   DEBUG1("<AS id=\"%s\"\trouting=\"RuleBased\">", peer_id);
3602 #else
3603   SURFXML_BUFFER_SET(AS_routing, "Full");
3604   DEBUG1("<AS id=\"%s\"\trouting=\"Full\">", peer_id);
3605 #endif
3606   SURFXML_START_TAG(AS);
3607
3608   DEBUG0(" ");
3609   host_id = bprintf("peer_%s", peer_id);
3610   router_id = bprintf("router_%s", peer_id);
3611   link_id_up = bprintf("link_%s_up", peer_id);
3612   link_id_down = bprintf("link_%s_down", peer_id);
3613
3614   link_router = bprintf("%s_link_router", peer_id);
3615   link_backbone = bprintf("%s_backbone", peer_id);
3616
3617   DEBUG2("<host\tid=\"%s\"\tpower=\"%s\"/>", host_id, peer_power);
3618   A_surfxml_host_state = A_surfxml_host_state_ON;
3619   SURFXML_BUFFER_SET(host_id, host_id);
3620   SURFXML_BUFFER_SET(host_power, peer_power);
3621   SURFXML_BUFFER_SET(host_availability, "1.0");
3622   SURFXML_BUFFER_SET(host_availability_file, "");
3623   SURFXML_BUFFER_SET(host_state_file, "");
3624   SURFXML_START_TAG(host);
3625   SURFXML_END_TAG(host);
3626
3627   DEBUG2("<router id=\"%s\"\tcoordinates=\"%s\"/>", router_id, peer_coord);
3628   SURFXML_BUFFER_SET(router_id, router_id);
3629   SURFXML_BUFFER_SET(router_coordinates, peer_coord);
3630   SURFXML_START_TAG(router);
3631   SURFXML_END_TAG(router);
3632
3633   DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id_up, peer_bw_in, peer_lat);
3634   A_surfxml_link_state = A_surfxml_link_state_ON;
3635   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3636   if(peer_sharing_policy == A_surfxml_peer_sharing_policy_FULLDUPLEX)
3637 {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3638   SURFXML_BUFFER_SET(link_id, link_id_up);
3639   SURFXML_BUFFER_SET(link_bandwidth, peer_bw_in);
3640   SURFXML_BUFFER_SET(link_latency, peer_lat);
3641   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3642   SURFXML_BUFFER_SET(link_latency_file, "");
3643   SURFXML_BUFFER_SET(link_state_file, "");
3644   SURFXML_START_TAG(link);
3645   SURFXML_END_TAG(link);
3646
3647   DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id_down, peer_bw_out, peer_lat);
3648   A_surfxml_link_state = A_surfxml_link_state_ON;
3649   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3650   if(peer_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3651 {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3652   SURFXML_BUFFER_SET(link_id, link_id_down);
3653   SURFXML_BUFFER_SET(link_bandwidth, peer_bw_out);
3654   SURFXML_BUFFER_SET(link_latency, peer_lat);
3655   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3656   SURFXML_BUFFER_SET(link_latency_file, "");
3657   SURFXML_BUFFER_SET(link_state_file, "");
3658   SURFXML_START_TAG(link);
3659   SURFXML_END_TAG(link);
3660
3661   DEBUG0(" ");
3662
3663   // begin here
3664   DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", peer_id, router_id);
3665   DEBUG0("symmetrical=\"NO\">");
3666   SURFXML_BUFFER_SET(route_src, peer_id);
3667   SURFXML_BUFFER_SET(route_dst, router_id);
3668   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3669   SURFXML_START_TAG(route);
3670
3671   DEBUG1("<link_ctn\tid=\"%s\"/>", link_id_up);
3672   SURFXML_BUFFER_SET(link_ctn_id, link_id_up);
3673   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3674   if(peer_sharing_policy == A_surfxml_peer_sharing_policy_FULLDUPLEX)
3675   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
3676   SURFXML_START_TAG(link_ctn);
3677   SURFXML_END_TAG(link_ctn);
3678
3679   DEBUG0("</route>");
3680   SURFXML_END_TAG(route);
3681
3682   //Opposite Route
3683   DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", router_id, peer_id);
3684   DEBUG0("symmetrical=\"NO\">");
3685   SURFXML_BUFFER_SET(route_src, router_id);
3686   SURFXML_BUFFER_SET(route_dst, peer_id);
3687   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3688   SURFXML_START_TAG(route);
3689
3690   DEBUG1("<link_ctn\tid=\"%s\"/>", link_id_down);
3691   SURFXML_BUFFER_SET(link_ctn_id, link_id_down);
3692   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3693   if(peer_sharing_policy == A_surfxml_peer_sharing_policy_FULLDUPLEX)
3694   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_DOWN;}
3695   SURFXML_START_TAG(link_ctn);
3696   SURFXML_END_TAG(link_ctn);
3697
3698   DEBUG0("</route>");
3699   SURFXML_END_TAG(route);
3700
3701   DEBUG0("</AS>");
3702   SURFXML_END_TAG(AS);
3703   DEBUG0(" ");
3704
3705   //xbt_dynar_free(&tab_elements_num);
3706
3707   surfxml_bufferstack_pop(1);
3708 }
3709
3710
3711 /*
3712  * New methods to init the routing model component from the lua script
3713  */
3714
3715 /*
3716  * calling parse_S_AS_lua with lua values
3717  */
3718 void routing_AS_init(const char *AS_id, const char *AS_routing)
3719 {
3720   parse_S_AS_lua((char *) AS_id, (char *) AS_routing);
3721 }
3722
3723 /*
3724  * calling parse_E_AS_lua to fisnish the creation of routing component
3725  */
3726 void routing_AS_end(const char *AS_id)
3727 {
3728   parse_E_AS_lua((char *) AS_id);
3729 }
3730
3731 /*
3732  * add a host to the network element list
3733  */
3734
3735 void routing_add_host(const char *host_id)
3736 {
3737   parse_S_host_lua((char *) host_id, (char*)""); // FIXME propagate coordinate system to lua
3738 }
3739
3740 /*
3741  * Set a new link on the actual list of link for a route or ASroute
3742  */
3743 void routing_add_link(const char *link_id)
3744 {
3745   parse_E_link_c_ctn_new_elem_lua((char *) link_id);
3746 }
3747
3748 /*
3749  *Set the endpoints for a route
3750  */
3751 void routing_set_route(const char *src_id, const char *dst_id)
3752 {
3753   parse_S_route_new_and_endpoints_lua(src_id, dst_id);
3754 }
3755
3756 /*
3757  * Store the route by calling parse_E_route_store_route
3758  */
3759 void routing_store_route(void)
3760 {
3761   parse_E_route_store_route();
3762 }