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 (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 (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 = elements_father(src, dst);
 879   routing_component_t common_father =
 880       xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 881
 882   if (strcmp(src, dst))
 883     e_route = _get_route(src, dst);
 884   else
 885     e_route = (*(common_father->get_route)) (common_father, src, dst);
 886
 887   xbt_assert2(e_route, "no route between \"%s\" and \"%s\"", src, dst);
 888
 889   if (global_routing->last_route)
 890     xbt_dynar_free(&(global_routing->last_route));
 891   global_routing->last_route = e_route->generic_route.link_list;
 892
 893   if (e_route->src_gateway)
 894     xbt_free(e_route->src_gateway);
 895   if (e_route->dst_gateway)
 896     xbt_free(e_route->dst_gateway);
 897
 898   xbt_free(e_route);
 899   xbt_dynar_free(&elem_father_list);
 900
 901 /*
 902   if (xbt_dynar_length(global_routing->last_route) == 0)
 903     return NULL;
 904   else
 905 */
 906     return global_routing->last_route;
 907 }
 908
 909 /**
 910  * \brief Generic method: find a route between hosts
 911  *
 912  * \param src the source host name
 913  * \param dst the destination host name
 914  *
 915  * walk through the routing components tree and find a route between hosts
 916  * by calling the differents "get_route" functions in each routing component.
 917  * Leaves the caller the responsability to clean the returned dynar.
 918  */
 919 static xbt_dynar_t get_route_no_cleanup(const char *src, const char *dst)
 920 {
 921         xbt_dynar_t d = get_route(src,dst);
 922         global_routing->last_route = NULL;
 923         return d;
 924 }
 925
 926 /*Get Latency*/
 927 static double get_latency(const char *src, const char *dst)
 928 {
 929
 930   double latency = -1.0;
 931   xbt_dynar_t elem_father_list = elements_father(src, dst);
 932   routing_component_t common_father =
 933       xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 934
 935   if (strcmp(src, dst))
 936     latency = _get_latency(src, dst);
 937   else
 938     latency = (*(common_father->get_latency)) (common_father, src, dst);
 939
 940   xbt_assert2(latency>=0.0, "no route between \"%s\" and \"%s\"", src, dst);
 941   xbt_dynar_free(&elem_father_list);
 942
 943   return latency;
 944 }
 945
 946 /**
 947  * \brief Recursive function for finalize
 948  *
 949  * \param rc the source host name
 950  *
 951  * This fuction is call by "finalize". It allow to finalize the
 952  * AS or routing components. It delete all the structures.
 953  */
 954 static void _finalize(routing_component_t rc)
 955 {
 956   if (rc) {
 957     xbt_dict_cursor_t cursor = NULL;
 958     char *key;
 959     routing_component_t elem;
 960     xbt_dict_foreach(rc->routing_sons, cursor, key, elem) {
 961       _finalize(elem);
 962     }
 963     xbt_dict_t tmp_sons = rc->routing_sons;
 964     char *tmp_name = rc->name;
 965     xbt_dict_free(&tmp_sons);
 966     xbt_free(tmp_name);
 967     xbt_assert1(rc->finalize, "no defined method \"finalize\" in \"%s\"",
 968                 current_routing->name);
 969     (*(rc->finalize)) (rc);
 970   }
 971 }
 972
 973 /**
 974  * \brief Generic method: delete all the routing structures
 975  *
 976  * walk through the routing components tree and delete the structures
 977  * by calling the differents "finalize" functions in each routing component
 978  */
 979 static void finalize(void)
 980 {
 981   /* delete recursibly all the tree */
 982   _finalize(global_routing->root);
 983   /* delete "where" dict */
 984   xbt_dict_free(&(global_routing->where_network_elements));
 985   xbt_dict_free(&(coordinates));
 986   /* delete last_route */
 987   xbt_dynar_free(&(global_routing->last_route));
 988   /* delete global routing structure */
 989   xbt_free(global_routing);
 990 }
 991
 992 static xbt_dynar_t recursive_get_onelink_routes(routing_component_t rc)
 993 {
 994   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
 995
 996   //adding my one link routes
 997   unsigned int cpt;
 998   void *link;
 999   xbt_dynar_t onelink_mine = rc->get_onelink_routes(rc);
1000   if (onelink_mine) {
1001     xbt_dynar_foreach(onelink_mine, cpt, link) {
1002       xbt_dynar_push(ret, &link);
1003     }
1004   }
1005   //recursing
1006   char *key;
1007   xbt_dict_cursor_t cursor = NULL;
1008   routing_component_t rc_child;
1009   xbt_dict_foreach(rc->routing_sons, cursor, key, rc_child) {
1010     xbt_dynar_t onelink_child = recursive_get_onelink_routes(rc_child);
1011     if (onelink_child) {
1012       xbt_dynar_foreach(onelink_child, cpt, link) {
1013         xbt_dynar_push(ret, &link);
1014       }
1015     }
1016   }
1017   return ret;
1018 }
1019
1020 static xbt_dynar_t get_onelink_routes(void)
1021 {
1022   return recursive_get_onelink_routes(global_routing->root);
1023 }
1024
1025 static e_surf_network_element_type_t get_network_element_type(const char
1026                                                               *name)
1027 {
1028   network_element_info_t rc = NULL;
1029   rc = xbt_dict_get(global_routing->where_network_elements, name);
1030   return rc->rc_type;
1031 }
1032
1033 /**
1034  * \brief Generic method: create the global routing schema
1035  *
1036  * Make a global routing structure and set all the parsing functions.
1037  */
1038 void routing_model_create(size_t size_of_links, void *loopback, double_f_cpvoid_t get_link_latency_fun)
1039 {
1040
1041   /* config the uniq global routing */
1042   global_routing = xbt_new0(s_routing_global_t, 1);
1043   global_routing->where_network_elements = xbt_dict_new();
1044   global_routing->root = NULL;
1045   global_routing->get_route = get_route;
1046   global_routing->get_latency = get_latency;
1047   global_routing->get_route_no_cleanup = get_route_no_cleanup;
1048   global_routing->get_onelink_routes = get_onelink_routes;
1049   global_routing->get_network_element_type = get_network_element_type;
1050   global_routing->finalize = finalize;
1051   global_routing->loopback = loopback;
1052   global_routing->size_of_link = size_of_links;
1053   global_routing->last_route = NULL;
1054   get_link_latency = get_link_latency_fun;
1055   /* no current routing at moment */
1056   current_routing = NULL;
1057
1058   coordinates = xbt_dict_new();
1059
1060   /* parse generic elements */
1061   surfxml_add_callback(STag_surfxml_host_cb_list, &parse_S_host_XML);
1062   surfxml_add_callback(STag_surfxml_router_cb_list, &parse_S_router);
1063
1064   surfxml_add_callback(STag_surfxml_route_cb_list,
1065                        &parse_S_route_new_and_endpoints_XML);
1066   surfxml_add_callback(STag_surfxml_ASroute_cb_list,
1067                        &parse_S_ASroute_new_and_endpoints);
1068   surfxml_add_callback(STag_surfxml_bypassRoute_cb_list,
1069                        &parse_S_bypassRoute_new_and_endpoints);
1070
1071   surfxml_add_callback(ETag_surfxml_link_ctn_cb_list,
1072                        &parse_E_link_ctn_new_elem_XML);
1073
1074   surfxml_add_callback(ETag_surfxml_route_cb_list,
1075                        &parse_E_route_store_route);
1076   surfxml_add_callback(ETag_surfxml_ASroute_cb_list,
1077                        &parse_E_ASroute_store_route);
1078   surfxml_add_callback(ETag_surfxml_bypassRoute_cb_list,
1079                        &parse_E_bypassRoute_store_route);
1080
1081   surfxml_add_callback(STag_surfxml_AS_cb_list, &parse_S_AS_XML);
1082   surfxml_add_callback(ETag_surfxml_AS_cb_list, &parse_E_AS_XML);
1083
1084   surfxml_add_callback(STag_surfxml_cluster_cb_list,
1085                        &routing_parse_Scluster);
1086
1087   surfxml_add_callback(STag_surfxml_peer_cb_list,
1088                          &routing_parse_Speer);
1089
1090   surfxml_add_callback(STag_surfxml_config_cb_list,
1091                                            &routing_parse_Sconfig);
1092   surfxml_add_callback(ETag_surfxml_config_cb_list,
1093                                            &routing_parse_Econfig);
1094 }
1095
1096 /* ************************************************************************** */
1097 /* *************************** FULL ROUTING ********************************* */
1098
1099 #define TO_ROUTE_FULL(i,j) routing->routing_table[(i)+(j)*table_size]
1100
1101 /* Routing model structure */
1102
1103 typedef struct {
1104   s_routing_component_t generic_routing;
1105   route_extended_t *routing_table;
1106 } s_routing_component_full_t, *routing_component_full_t;
1107
1108 /* Business methods */
1109 static xbt_dynar_t full_get_onelink_routes(routing_component_t rc)
1110 {
1111   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
1112
1113   routing_component_full_t routing = (routing_component_full_t) rc;
1114   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1115   xbt_dict_cursor_t c1 = NULL, c2 = NULL;
1116   char *k1, *d1, *k2, *d2;
1117   xbt_dict_foreach(routing->generic_routing.to_index, c1, k1, d1) {
1118     xbt_dict_foreach(routing->generic_routing.to_index, c2, k2, d2) {
1119       int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, k1);
1120       int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, k2);
1121       xbt_assert2(src_id
1122                   && dst_id,
1123                   "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1124                   src, dst);
1125       route_extended_t route = TO_ROUTE_FULL(*src_id, *dst_id);
1126       if (route) {
1127         if (xbt_dynar_length(route->generic_route.link_list) == 1) {
1128           void *link =
1129               *(void **) xbt_dynar_get_ptr(route->generic_route.link_list,
1130                                            0);
1131           onelink_t onelink = xbt_new0(s_onelink_t, 1);
1132           onelink->link_ptr = link;
1133           if (routing->generic_routing.hierarchy == SURF_ROUTING_BASE) {
1134             onelink->src = xbt_strdup(k1);
1135             onelink->dst = xbt_strdup(k2);
1136           } else if (routing->generic_routing.hierarchy ==
1137                      SURF_ROUTING_RECURSIVE) {
1138             onelink->src = xbt_strdup(route->src_gateway);
1139             onelink->dst = xbt_strdup(route->dst_gateway);
1140           }
1141           xbt_dynar_push(ret, &onelink);
1142         }
1143       }
1144     }
1145   }
1146   return ret;
1147 }
1148
1149 static route_extended_t full_get_route(routing_component_t rc,
1150                                        const char *src, const char *dst)
1151 {
1152   xbt_assert1(rc && src
1153               && dst,
1154               "Invalid params for \"get_route\" function at AS \"%s\"",
1155               rc->name);
1156
1157   /* set utils vars */
1158   routing_component_full_t routing = (routing_component_full_t) rc;
1159   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1160
1161   generic_src_dst_check(rc, src, dst);
1162   int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, src);
1163   int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, dst);
1164   xbt_assert2(src_id
1165               && dst_id,
1166               "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1167               src, dst);
1168
1169   route_extended_t e_route = NULL;
1170   route_extended_t new_e_route = NULL;
1171   void *link;
1172   unsigned int cpt = 0;
1173
1174   e_route = TO_ROUTE_FULL(*src_id, *dst_id);
1175
1176   if (e_route) {
1177     new_e_route = xbt_new0(s_route_extended_t, 1);
1178     new_e_route->src_gateway = xbt_strdup(e_route->src_gateway);
1179     new_e_route->dst_gateway = xbt_strdup(e_route->dst_gateway);
1180     new_e_route->generic_route.link_list =
1181         xbt_dynar_new(global_routing->size_of_link, NULL);
1182     xbt_dynar_foreach(e_route->generic_route.link_list, cpt, link) {
1183       xbt_dynar_push(new_e_route->generic_route.link_list, &link);
1184     }
1185   }
1186   return new_e_route;
1187 }
1188
1189 static void full_finalize(routing_component_t rc)
1190 {
1191   routing_component_full_t routing = (routing_component_full_t) rc;
1192   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1193   int i, j;
1194   if (routing) {
1195     /* Delete routing table */
1196     for (i = 0; i < table_size; i++)
1197       for (j = 0; j < table_size; j++)
1198         generic_free_extended_route(TO_ROUTE_FULL(i, j));
1199     xbt_free(routing->routing_table);
1200     /* Delete bypass dict */
1201     xbt_dict_free(&rc->bypassRoutes);
1202     /* Delete index dict */
1203     xbt_dict_free(&rc->to_index);
1204     /* Delete structure */
1205     xbt_free(rc);
1206   }
1207 }
1208
1209 /* Creation routing model functions */
1210
1211 static void *model_full_create(void)
1212 {
1213   routing_component_full_t new_component =
1214       xbt_new0(s_routing_component_full_t, 1);
1215   new_component->generic_routing.set_processing_unit =
1216       generic_set_processing_unit;
1217   new_component->generic_routing.set_autonomous_system =
1218       generic_set_autonomous_system;
1219   new_component->generic_routing.set_route = model_full_set_route;
1220   new_component->generic_routing.set_ASroute = model_full_set_route;
1221   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
1222   new_component->generic_routing.get_route = full_get_route;
1223   new_component->generic_routing.get_latency = generic_get_link_latency;
1224   new_component->generic_routing.get_onelink_routes =
1225       full_get_onelink_routes;
1226   new_component->generic_routing.get_bypass_route =
1227       generic_get_bypassroute;
1228   new_component->generic_routing.finalize = full_finalize;
1229   new_component->generic_routing.to_index = xbt_dict_new();
1230   new_component->generic_routing.bypassRoutes = xbt_dict_new();
1231   return new_component;
1232 }
1233
1234 static void model_full_load(void)
1235 {
1236   /* use "surfxml_add_callback" to add a parse function call */
1237 }
1238
1239 static void model_full_unload(void)
1240 {
1241   /* use "surfxml_del_callback" to remove a parse function call */
1242 }
1243
1244 static void model_full_end(void)
1245 {
1246   unsigned int i;
1247   route_extended_t e_route;
1248
1249   /* set utils vars */
1250   routing_component_full_t routing =
1251       ((routing_component_full_t) current_routing);
1252   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1253
1254   /* Create table if necessary */
1255   if(!routing->routing_table)
1256           routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
1257
1258   /* Add the loopback if needed */
1259   if (current_routing->hierarchy == SURF_ROUTING_BASE) {
1260     for (i = 0; i < table_size; i++) {
1261       e_route = TO_ROUTE_FULL(i, i);
1262       if (!e_route) {
1263         e_route = xbt_new0(s_route_extended_t, 1);
1264         e_route->src_gateway = NULL;
1265         e_route->dst_gateway = NULL;
1266         e_route->generic_route.link_list =
1267             xbt_dynar_new(global_routing->size_of_link, NULL);
1268         xbt_dynar_push(e_route->generic_route.link_list,
1269                        &global_routing->loopback);
1270         TO_ROUTE_FULL(i, i) = e_route;
1271       }
1272     }
1273   }
1274 }
1275
1276 static void model_full_set_route(routing_component_t rc, const char *src,
1277                 const char *dst, name_route_extended_t route)
1278 {
1279         int *src_id, *dst_id;
1280         src_id = xbt_dict_get_or_null(rc->to_index, src);
1281         dst_id = xbt_dict_get_or_null(rc->to_index, dst);
1282         routing_component_full_t routing = ((routing_component_full_t) rc);
1283         size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1284
1285         xbt_assert2(src_id
1286                           && dst_id, "Network elements %s or %s not found", src, dst);
1287
1288         xbt_assert2(xbt_dynar_length(route->generic_route.link_list) > 0,
1289                           "Invalid count of links, must be greater than zero (%s,%s)",
1290                           src, dst);
1291
1292         if(!routing->routing_table)
1293                 routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
1294
1295         if(TO_ROUTE_FULL(*src_id, *dst_id))
1296         {
1297                 char * link_name;
1298                 unsigned int i;
1299                 xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1300                 xbt_dynar_foreach(route->generic_route.link_list,i,link_name)
1301                 {
1302                         void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1303                         xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1304                         xbt_dynar_push(link_route_to_test,&link);
1305                 }
1306                 xbt_assert2(!xbt_dynar_compare(
1307                           (void*)TO_ROUTE_FULL(*src_id, *dst_id)->generic_route.link_list,
1308                           (void*)link_route_to_test,
1309                           (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1310                           "The route between \"%s\" and \"%s\" already exists", src,dst);
1311                 xbt_dynar_free(&link_route_to_test);
1312         }
1313         else
1314         {
1315                   if(!route->dst_gateway && !route->src_gateway)
1316                           DEBUG2("Load Route from \"%s\" to \"%s\"", src, dst);
1317                   else
1318                           DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
1319                                  route->src_gateway, dst, route->dst_gateway);
1320               TO_ROUTE_FULL(*src_id, *dst_id) = generic_new_extended_route(rc->hierarchy,route,1);
1321               xbt_dynar_shrink(TO_ROUTE_FULL(*src_id, *dst_id)->generic_route.link_list, 0);
1322         }
1323
1324         if( A_surfxml_route_symmetrical == A_surfxml_route_symmetrical_YES
1325                 || A_surfxml_ASroute_symmetrical == A_surfxml_ASroute_symmetrical_YES )
1326         {
1327                 if(route->dst_gateway && route->src_gateway)
1328                 {
1329                   char *gw_src = xbt_strdup(route->src_gateway);
1330                   char *gw_dst = xbt_strdup(route->dst_gateway);
1331                   route->src_gateway = gw_dst;
1332                   route->dst_gateway = gw_src;
1333                 }
1334                 if(TO_ROUTE_FULL(*dst_id, *src_id))
1335                 {
1336                         char * link_name;
1337                         unsigned int i;
1338                         xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1339                         for(i=xbt_dynar_length(route->generic_route.link_list) ;i>0 ;i--)
1340                         {
1341                                 link_name = xbt_dynar_get_as(route->generic_route.link_list,i-1,void *);
1342                                 void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1343                                 xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1344                                 xbt_dynar_push(link_route_to_test,&link);
1345                         }
1346                         xbt_assert2(!xbt_dynar_compare(
1347                                   (void*)TO_ROUTE_FULL(*dst_id, *src_id)->generic_route.link_list,
1348                               (void*)link_route_to_test,
1349                                   (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1350                                   "The route between \"%s\" and \"%s\" already exists", src,dst);
1351                         xbt_dynar_free(&link_route_to_test);
1352                 }
1353                 else
1354                 {
1355                           if(!route->dst_gateway && !route->src_gateway)
1356                                   DEBUG2("Load Route from \"%s\" to \"%s\"", dst, src);
1357                           else
1358                                   DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
1359                                          route->src_gateway, src, route->dst_gateway);
1360                       TO_ROUTE_FULL(*dst_id, *src_id) = generic_new_extended_route(rc->hierarchy,route,0);
1361                       xbt_dynar_shrink(TO_ROUTE_FULL(*dst_id, *src_id)->generic_route.link_list, 0);
1362                 }
1363
1364         }
1365 }
1366
1367 /* ************************************************************************** */
1368 /* *************************** FLOYD ROUTING ******************************** */
1369
1370 #define TO_FLOYD_COST(i,j) (routing->cost_table)[(i)+(j)*table_size]
1371 #define TO_FLOYD_PRED(i,j) (routing->predecessor_table)[(i)+(j)*table_size]
1372 #define TO_FLOYD_LINK(i,j) (routing->link_table)[(i)+(j)*table_size]
1373
1374 /* Routing model structure */
1375
1376 typedef struct {
1377   s_routing_component_t generic_routing;
1378   /* vars for calculate the floyd algorith. */
1379   int *predecessor_table;
1380   double *cost_table;
1381   route_extended_t *link_table; /* char* -> int* */
1382 } s_routing_component_floyd_t, *routing_component_floyd_t;
1383
1384 static route_extended_t floyd_get_route(routing_component_t rc,
1385                                         const char *src, const char *dst);
1386
1387 /* Business methods */
1388 static xbt_dynar_t floyd_get_onelink_routes(routing_component_t rc)
1389 {
1390   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
1391
1392   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1393   //size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1394   xbt_dict_cursor_t c1 = NULL, c2 = NULL;
1395   char *k1, *d1, *k2, *d2;
1396   xbt_dict_foreach(routing->generic_routing.to_index, c1, k1, d1) {
1397     xbt_dict_foreach(routing->generic_routing.to_index, c2, k2, d2) {
1398       route_extended_t route = floyd_get_route(rc, k1, k2);
1399       if (route) {
1400         if (xbt_dynar_length(route->generic_route.link_list) == 1) {
1401           void *link =
1402               *(void **) xbt_dynar_get_ptr(route->generic_route.link_list,
1403                                            0);
1404           onelink_t onelink = xbt_new0(s_onelink_t, 1);
1405           onelink->link_ptr = link;
1406           if (routing->generic_routing.hierarchy == SURF_ROUTING_BASE) {
1407             onelink->src = xbt_strdup(k1);
1408             onelink->dst = xbt_strdup(k2);
1409           } else if (routing->generic_routing.hierarchy ==
1410                      SURF_ROUTING_RECURSIVE) {
1411             onelink->src = xbt_strdup(route->src_gateway);
1412             onelink->dst = xbt_strdup(route->dst_gateway);
1413           }
1414           xbt_dynar_push(ret, &onelink);
1415         }
1416       }
1417     }
1418   }
1419   return ret;
1420 }
1421
1422 static route_extended_t floyd_get_route(routing_component_t rc,
1423                                         const char *src, const char *dst)
1424 {
1425   xbt_assert1(rc && src
1426               && dst,
1427               "Invalid params for \"get_route\" function at AS \"%s\"",
1428               rc->name);
1429
1430   /* set utils vars */
1431   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1432   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1433
1434   generic_src_dst_check(rc, src, dst);
1435   int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, src);
1436   int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, dst);
1437   xbt_assert2(src_id
1438               && dst_id,
1439               "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1440               src, dst);
1441
1442   /* create a result route */
1443   route_extended_t new_e_route = xbt_new0(s_route_extended_t, 1);
1444   new_e_route->generic_route.link_list =
1445       xbt_dynar_new(global_routing->size_of_link, NULL);
1446   new_e_route->src_gateway = NULL;
1447   new_e_route->dst_gateway = NULL;
1448
1449   int first = 1;
1450   int pred = *dst_id;
1451   int prev_pred = 0;
1452   char *gw_src = NULL, *gw_dst =
1453       NULL, *prev_gw_src, *prev_gw_dst, *first_gw = NULL;
1454   unsigned int cpt;
1455   void *link;
1456   xbt_dynar_t links;
1457
1458   do {
1459     prev_pred = pred;
1460     pred = TO_FLOYD_PRED(*src_id, pred);
1461     if (pred == -1)             /* if no pred in route -> no route to host */
1462       break;
1463     xbt_assert2(TO_FLOYD_LINK(pred, prev_pred),
1464                 "Invalid link for the route between \"%s\" or \"%s\"", src,
1465                 dst);
1466
1467     prev_gw_src = gw_src;
1468     prev_gw_dst = gw_dst;
1469
1470     route_extended_t e_route = TO_FLOYD_LINK(pred, prev_pred);
1471     gw_src = e_route->src_gateway;
1472     gw_dst = e_route->dst_gateway;
1473
1474     if (first)
1475       first_gw = gw_dst;
1476
1477     if (rc->hierarchy == SURF_ROUTING_RECURSIVE && !first
1478         && strcmp(gw_dst, prev_gw_src)) {
1479       xbt_dynar_t e_route_as_to_as =
1480           (*(global_routing->get_route)) (gw_dst, prev_gw_src);
1481       xbt_assert2(e_route_as_to_as, "no route between \"%s\" and \"%s\"",
1482                   gw_dst, prev_gw_src);
1483       links = e_route_as_to_as;
1484       int pos = 0;
1485       xbt_dynar_foreach(links, cpt, link) {
1486         xbt_dynar_insert_at(new_e_route->generic_route.link_list, pos,
1487                             &link);
1488         pos++;
1489       }
1490     }
1491
1492     links = e_route->generic_route.link_list;
1493     xbt_dynar_foreach(links, cpt, link) {
1494       xbt_dynar_unshift(new_e_route->generic_route.link_list, &link);
1495     }
1496     first = 0;
1497
1498   } while (pred != *src_id);
1499   xbt_assert4(pred != -1, "no route from host %d to %d (\"%s\" to \"%s\")",
1500               *src_id, *dst_id, src, dst);
1501
1502   if (rc->hierarchy == SURF_ROUTING_RECURSIVE) {
1503     new_e_route->src_gateway = xbt_strdup(gw_src);
1504     new_e_route->dst_gateway = xbt_strdup(first_gw);
1505   }
1506
1507   return new_e_route;
1508 }
1509
1510 static void floyd_finalize(routing_component_t rc)
1511 {
1512   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1513   int i, j;
1514   size_t table_size;
1515   if (routing) {
1516     table_size = xbt_dict_length(routing->generic_routing.to_index);
1517     /* Delete link_table */
1518     for (i = 0; i < table_size; i++)
1519       for (j = 0; j < table_size; j++)
1520         generic_free_extended_route(TO_FLOYD_LINK(i, j));
1521     xbt_free(routing->link_table);
1522     /* Delete bypass dict */
1523     xbt_dict_free(&routing->generic_routing.bypassRoutes);
1524     /* Delete index dict */
1525     xbt_dict_free(&(routing->generic_routing.to_index));
1526     /* Delete dictionary index dict, predecessor and links table */
1527     xbt_free(routing->predecessor_table);
1528     /* Delete structure */
1529     xbt_free(rc);
1530   }
1531 }
1532
1533 static void *model_floyd_create(void)
1534 {
1535   routing_component_floyd_t new_component =
1536       xbt_new0(s_routing_component_floyd_t, 1);
1537   new_component->generic_routing.set_processing_unit =
1538       generic_set_processing_unit;
1539   new_component->generic_routing.set_autonomous_system =
1540       generic_set_autonomous_system;
1541   new_component->generic_routing.set_route = model_floyd_set_route;
1542   new_component->generic_routing.set_ASroute = model_floyd_set_route;
1543   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
1544   new_component->generic_routing.get_route = floyd_get_route;
1545   new_component->generic_routing.get_latency = generic_get_link_latency;
1546   new_component->generic_routing.get_onelink_routes =
1547       floyd_get_onelink_routes;
1548   new_component->generic_routing.get_bypass_route =
1549       generic_get_bypassroute;
1550   new_component->generic_routing.finalize = floyd_finalize;
1551   new_component->generic_routing.to_index = xbt_dict_new();
1552   new_component->generic_routing.bypassRoutes = xbt_dict_new();
1553   return new_component;
1554 }
1555
1556 static void model_floyd_load(void)
1557 {
1558   /* use "surfxml_add_callback" to add a parse function call */
1559 }
1560
1561 static void model_floyd_unload(void)
1562 {
1563   /* use "surfxml_del_callback" to remove a parse function call */
1564 }
1565
1566 static void model_floyd_end(void)
1567 {
1568
1569         routing_component_floyd_t routing =
1570           ((routing_component_floyd_t) current_routing);
1571
1572         unsigned int i, j, a, b, c;
1573
1574         /* set the size of table routing */
1575         size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1576
1577         if(!routing->link_table)
1578         {
1579                 /* Create Cost, Predecessor and Link tables */
1580                 routing->cost_table = xbt_new0(double, table_size * table_size);       /* link cost from host to host */
1581                 routing->predecessor_table = xbt_new0(int, table_size * table_size);  /* predecessor host numbers */
1582                 routing->link_table = xbt_new0(route_extended_t, table_size * table_size);    /* actual link between src and dst */
1583
1584                 /* Initialize costs and predecessors */
1585                 for (i = 0; i < table_size; i++)
1586                 for (j = 0; j < table_size; j++) {
1587                   TO_FLOYD_COST(i, j) = DBL_MAX;
1588                   TO_FLOYD_PRED(i, j) = -1;
1589                   TO_FLOYD_LINK(i, j) = NULL;       /* fixed, missing in the previous version */
1590                 }
1591         }
1592
1593         /* Add the loopback if needed */
1594         if (current_routing->hierarchy == SURF_ROUTING_BASE) {
1595                 for (i = 0; i < table_size; i++) {
1596                   route_extended_t e_route = TO_FLOYD_LINK(i, i);
1597                   if (!e_route) {
1598                         e_route = xbt_new0(s_route_extended_t, 1);
1599                         e_route->src_gateway = NULL;
1600                         e_route->dst_gateway = NULL;
1601                         e_route->generic_route.link_list =
1602                                 xbt_dynar_new(global_routing->size_of_link, NULL);
1603                         xbt_dynar_push(e_route->generic_route.link_list,
1604                                                    &global_routing->loopback);
1605                         TO_FLOYD_LINK(i, i) = e_route;
1606                         TO_FLOYD_PRED(i, i) = i;
1607                         TO_FLOYD_COST(i, i) = 1;
1608                   }
1609                 }
1610         }
1611         /* Calculate path costs */
1612         for (c = 0; c < table_size; c++) {
1613                 for (a = 0; a < table_size; a++) {
1614                   for (b = 0; b < table_size; b++) {
1615                         if (TO_FLOYD_COST(a, c) < DBL_MAX && TO_FLOYD_COST(c, b) < DBL_MAX) {
1616                           if (TO_FLOYD_COST(a, b) == DBL_MAX ||
1617                                   (TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b) <
1618                                    TO_FLOYD_COST(a, b))) {
1619                                 TO_FLOYD_COST(a, b) =
1620                                         TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b);
1621                                 TO_FLOYD_PRED(a, b) = TO_FLOYD_PRED(c, b);
1622                           }
1623                         }
1624                   }
1625                 }
1626         }
1627 }
1628
1629 static void model_floyd_set_route(routing_component_t rc, const char *src,
1630         const char *dst, name_route_extended_t route)
1631 {
1632         routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1633
1634         /* set the size of table routing */
1635         size_t table_size = xbt_dict_length(rc->to_index);
1636         int *src_id, *dst_id;
1637         int i,j;
1638
1639         src_id = xbt_dict_get_or_null(rc->to_index, src);
1640         dst_id = xbt_dict_get_or_null(rc->to_index, dst);
1641
1642         if(!routing->link_table)
1643         {
1644                 /* Create Cost, Predecessor and Link tables */
1645                 routing->cost_table = xbt_new0(double, table_size * table_size);       /* link cost from host to host */
1646                 routing->predecessor_table = xbt_new0(int, table_size * table_size);  /* predecessor host numbers */
1647                 routing->link_table = xbt_new0(route_extended_t, table_size * table_size);    /* actual link between src and dst */
1648
1649                 /* Initialize costs and predecessors */
1650                 for (i = 0; i < table_size; i++)
1651                 for (j = 0; j < table_size; j++) {
1652                   TO_FLOYD_COST(i, j) = DBL_MAX;
1653                   TO_FLOYD_PRED(i, j) = -1;
1654                   TO_FLOYD_LINK(i, j) = NULL;       /* fixed, missing in the previous version */
1655                 }
1656         }
1657
1658         if(TO_FLOYD_LINK(*src_id, *dst_id))
1659         {
1660                 if(!route->dst_gateway && !route->src_gateway)
1661                         DEBUG2("See Route from \"%s\" to \"%s\"", src, dst);
1662                 else
1663                         DEBUG4("See ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
1664                                  route->src_gateway, dst, route->dst_gateway);
1665                 char * link_name;
1666                 unsigned int cpt;
1667                 xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1668                 xbt_dynar_foreach(route->generic_route.link_list,cpt,link_name)
1669                 {
1670                         void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1671                         xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1672                         xbt_dynar_push(link_route_to_test,&link);
1673                 }
1674                 xbt_assert2(!xbt_dynar_compare(
1675                           (void*)TO_FLOYD_LINK(*src_id, *dst_id)->generic_route.link_list,
1676                           (void*)link_route_to_test,
1677                           (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1678                           "The route between \"%s\" and \"%s\" already exists", src,dst);
1679                 xbt_free(link_route_to_test);
1680         }
1681         else
1682         {
1683                 if(!route->dst_gateway && !route->src_gateway)
1684                   DEBUG2("Load Route from \"%s\" to \"%s\"", src, dst);
1685                 else
1686                   DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
1687                                  route->src_gateway, dst, route->dst_gateway);
1688
1689             TO_FLOYD_LINK(*src_id, *dst_id) =
1690                         generic_new_extended_route(rc->hierarchy, route, 1);
1691             TO_FLOYD_PRED(*src_id, *dst_id) = *src_id;
1692             TO_FLOYD_COST(*src_id, *dst_id) =
1693                         ((TO_FLOYD_LINK(*src_id, *dst_id))->generic_route.link_list)->used;   /* count of links, old model assume 1 */
1694         }
1695
1696         if( A_surfxml_route_symmetrical == A_surfxml_route_symmetrical_YES
1697                 || A_surfxml_ASroute_symmetrical == A_surfxml_ASroute_symmetrical_YES )
1698         {
1699                 if(TO_FLOYD_LINK(*dst_id, *src_id))
1700                 {
1701                         if(!route->dst_gateway && !route->src_gateway)
1702                           DEBUG2("See Route from \"%s\" to \"%s\"", dst, src);
1703                         else
1704                           DEBUG4("See ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
1705                                          route->src_gateway, src, route->dst_gateway);
1706                         char * link_name;
1707                         unsigned int i;
1708                         xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1709                         for(i=xbt_dynar_length(route->generic_route.link_list) ;i>0 ;i--)
1710                         {
1711                                 link_name = xbt_dynar_get_as(route->generic_route.link_list,i-1,void *);
1712                                 void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1713                                 xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1714                                 xbt_dynar_push(link_route_to_test,&link);
1715                         }
1716                         xbt_assert2(!xbt_dynar_compare(
1717                                   (void*)TO_FLOYD_LINK(*dst_id, *src_id)->generic_route.link_list,
1718                               (void*)link_route_to_test,
1719                                   (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1720                                   "The route between \"%s\" and \"%s\" already exists", src,dst);
1721                         xbt_free(link_route_to_test);
1722                 }
1723                 else
1724                 {
1725                         if(route->dst_gateway && route->src_gateway)
1726                         {
1727                           char *gw_src = xbt_strdup(route->src_gateway);
1728                           char *gw_dst = xbt_strdup(route->dst_gateway);
1729                           route->src_gateway = gw_dst;
1730                           route->dst_gateway = gw_src;
1731                         }
1732
1733                         if(!route->dst_gateway && !route->src_gateway)
1734                           DEBUG2("Load Route from \"%s\" to \"%s\"", dst, src);
1735                         else
1736                           DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
1737                                          route->src_gateway, src, route->dst_gateway);
1738
1739                     TO_FLOYD_LINK(*dst_id, *src_id) =
1740                                 generic_new_extended_route(rc->hierarchy, route, 0);
1741                     TO_FLOYD_PRED(*dst_id, *src_id) = *dst_id;
1742                     TO_FLOYD_COST(*dst_id, *src_id) =
1743                                 ((TO_FLOYD_LINK(*dst_id, *src_id))->generic_route.link_list)->used;   /* count of links, old model assume 1 */
1744                 }
1745         }
1746 }
1747
1748 /* ************************************************************************** */
1749 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
1750
1751 typedef struct {
1752   s_routing_component_t generic_routing;
1753   xbt_graph_t route_graph;      /* xbt_graph */
1754   xbt_dict_t graph_node_map;    /* map */
1755   xbt_dict_t route_cache;       /* use in cache mode */
1756   int cached;
1757 } s_routing_component_dijkstra_t, *routing_component_dijkstra_t;
1758
1759
1760 typedef struct graph_node_data {
1761   int id;
1762   int graph_id;                 /* used for caching internal graph id's */
1763 } s_graph_node_data_t, *graph_node_data_t;
1764
1765 typedef struct graph_node_map_element {
1766   xbt_node_t node;
1767 } s_graph_node_map_element_t, *graph_node_map_element_t;
1768
1769 typedef struct route_cache_element {
1770   int *pred_arr;
1771   int size;
1772 } s_route_cache_element_t, *route_cache_element_t;
1773
1774 /* Free functions */
1775
1776 static void route_cache_elem_free(void *e)
1777 {
1778   route_cache_element_t elm = (route_cache_element_t) e;
1779   if (elm) {
1780     xbt_free(elm->pred_arr);
1781     xbt_free(elm);
1782   }
1783 }
1784
1785 static void graph_node_map_elem_free(void *e)
1786 {
1787   graph_node_map_element_t elm = (graph_node_map_element_t) e;
1788   if (elm) {
1789     xbt_free(elm);
1790   }
1791 }
1792
1793 static void graph_edge_data_free(void *e)
1794 {
1795   route_extended_t e_route = (route_extended_t) e;
1796   if (e_route) {
1797     xbt_dynar_free(&(e_route->generic_route.link_list));
1798     if (e_route->src_gateway)
1799       xbt_free(e_route->src_gateway);
1800     if (e_route->dst_gateway)
1801       xbt_free(e_route->dst_gateway);
1802     xbt_free(e_route);
1803   }
1804 }
1805
1806 /* Utility functions */
1807
1808 static xbt_node_t route_graph_new_node(routing_component_dijkstra_t rc,
1809                                        int id, int graph_id)
1810 {
1811   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1812   xbt_node_t node = NULL;
1813   graph_node_data_t data = NULL;
1814   graph_node_map_element_t elm = NULL;
1815
1816   data = xbt_new0(struct graph_node_data, 1);
1817   data->id = id;
1818   data->graph_id = graph_id;
1819   node = xbt_graph_new_node(routing->route_graph, data);
1820
1821   elm = xbt_new0(struct graph_node_map_element, 1);
1822   elm->node = node;
1823   xbt_dict_set_ext(routing->graph_node_map, (char *) (&id), sizeof(int),
1824                    (xbt_set_elm_t) elm, &graph_node_map_elem_free);
1825
1826   return node;
1827 }
1828
1829 static graph_node_map_element_t
1830 graph_node_map_search(routing_component_dijkstra_t rc, int id)
1831 {
1832   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1833   graph_node_map_element_t elm = (graph_node_map_element_t)
1834       xbt_dict_get_or_null_ext(routing->graph_node_map,
1835                                (char *) (&id),
1836                                sizeof(int));
1837   return elm;
1838 }
1839
1840 /* Parsing */
1841
1842 static void route_new_dijkstra(routing_component_dijkstra_t rc, int src_id,
1843                                int dst_id, route_extended_t e_route)
1844 {
1845   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1846
1847   xbt_node_t src = NULL;
1848   xbt_node_t dst = NULL;
1849   graph_node_map_element_t src_elm = (graph_node_map_element_t)
1850       xbt_dict_get_or_null_ext(routing->graph_node_map,
1851                                (char *) (&src_id),
1852                                sizeof(int));
1853   graph_node_map_element_t dst_elm = (graph_node_map_element_t)
1854       xbt_dict_get_or_null_ext(routing->graph_node_map,
1855                                (char *) (&dst_id),
1856                                sizeof(int));
1857
1858   if (src_elm)
1859     src = src_elm->node;
1860
1861   if (dst_elm)
1862     dst = dst_elm->node;
1863
1864   /* add nodes if they don't exist in the graph */
1865   if (src_id == dst_id && src == NULL && dst == NULL) {
1866     src = route_graph_new_node(rc, src_id, -1);
1867     dst = src;
1868   } else {
1869     if (src == NULL) {
1870       src = route_graph_new_node(rc, src_id, -1);
1871     }
1872     if (dst == NULL) {
1873       dst = route_graph_new_node(rc, dst_id, -1);
1874     }
1875   }
1876
1877   /* add link as edge to graph */
1878   xbt_graph_new_edge(routing->route_graph, src, dst, e_route);
1879 }
1880
1881 static void add_loopback_dijkstra(routing_component_dijkstra_t rc)
1882 {
1883   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1884
1885   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1886
1887   xbt_node_t node = NULL;
1888   unsigned int cursor2;
1889   xbt_dynar_foreach(nodes, cursor2, node) {
1890     xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
1891     xbt_edge_t edge = NULL;
1892     unsigned int cursor;
1893
1894     int found = 0;
1895     xbt_dynar_foreach(out_edges, cursor, edge) {
1896       xbt_node_t other_node = xbt_graph_edge_get_target(edge);
1897       if (other_node == node) {
1898         found = 1;
1899         break;
1900       }
1901     }
1902
1903     if (!found) {
1904       route_extended_t e_route = xbt_new0(s_route_extended_t, 1);
1905       e_route->src_gateway = NULL;
1906       e_route->dst_gateway = NULL;
1907       e_route->generic_route.link_list =
1908           xbt_dynar_new(global_routing->size_of_link, NULL);
1909       xbt_dynar_push(e_route->generic_route.link_list,
1910                      &global_routing->loopback);
1911       xbt_graph_new_edge(routing->route_graph, node, node, e_route);
1912     }
1913   }
1914 }
1915
1916 /* Business methods */
1917 static xbt_dynar_t dijkstra_get_onelink_routes(routing_component_t rc)
1918 {
1919   xbt_die("\"dijkstra_get_onelink_routes\" function not implemented yet");
1920 }
1921
1922 static route_extended_t dijkstra_get_route(routing_component_t rc,
1923                                            const char *src,
1924                                            const char *dst)
1925 {
1926   xbt_assert1(rc && src
1927               && dst,
1928               "Invalid params for \"get_route\" function at AS \"%s\"",
1929               rc->name);
1930
1931   /* set utils vars */
1932   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1933
1934   generic_src_dst_check(rc, src, dst);
1935   int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, src);
1936   int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, dst);
1937   xbt_assert2(src_id
1938               && dst_id,
1939               "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1940               src, dst);
1941
1942   /* create a result route */
1943   route_extended_t new_e_route = xbt_new0(s_route_extended_t, 1);
1944   new_e_route->generic_route.link_list =
1945       xbt_dynar_new(global_routing->size_of_link, NULL);
1946   new_e_route->src_gateway = NULL;
1947   new_e_route->dst_gateway = NULL;
1948
1949   int *pred_arr = NULL;
1950   int src_node_id = 0;
1951   int dst_node_id = 0;
1952   int *nodeid = NULL;
1953   int v;
1954   route_extended_t e_route;
1955   int size = 0;
1956   unsigned int cpt;
1957   void *link;
1958   xbt_dynar_t links = NULL;
1959   route_cache_element_t elm = NULL;
1960   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1961
1962   /* Use the graph_node id mapping set to quickly find the nodes */
1963   graph_node_map_element_t src_elm =
1964       graph_node_map_search(routing, *src_id);
1965   graph_node_map_element_t dst_elm =
1966       graph_node_map_search(routing, *dst_id);
1967   xbt_assert2(src_elm != NULL
1968               && dst_elm != NULL, "src %d or dst %d does not exist",
1969               *src_id, *dst_id);
1970   src_node_id = ((graph_node_data_t)
1971                  xbt_graph_node_get_data(src_elm->node))->graph_id;
1972   dst_node_id = ((graph_node_data_t)
1973                  xbt_graph_node_get_data(dst_elm->node))->graph_id;
1974
1975   /* if the src and dst are the same *//* fixed, missing in the previous version */
1976   if (src_node_id == dst_node_id) {
1977
1978     xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
1979     xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
1980     xbt_edge_t edge =
1981         xbt_graph_get_edge(routing->route_graph, node_s_v, node_e_v);
1982
1983     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id,
1984                 *dst_id);
1985
1986     e_route = (route_extended_t) xbt_graph_edge_get_data(edge);
1987
1988     links = e_route->generic_route.link_list;
1989     xbt_dynar_foreach(links, cpt, link) {
1990       xbt_dynar_unshift(new_e_route->generic_route.link_list, &link);
1991     }
1992
1993     return new_e_route;
1994   }
1995
1996   if (routing->cached) {
1997     /*check if there is a cached predecessor list avail */
1998     elm = (route_cache_element_t)
1999         xbt_dict_get_or_null_ext(routing->route_cache, (char *) (&src_id),
2000                                  sizeof(int));
2001   }
2002
2003   if (elm) {                    /* cached mode and cache hit */
2004     pred_arr = elm->pred_arr;
2005   } else {                      /* not cached mode or cache miss */
2006     double *cost_arr = NULL;
2007     xbt_heap_t pqueue = NULL;
2008     int i = 0;
2009
2010     int nr_nodes = xbt_dynar_length(nodes);
2011     cost_arr = xbt_new0(double, nr_nodes);      /* link cost from src to other hosts */
2012     pred_arr = xbt_new0(int, nr_nodes); /* predecessors in path from src */
2013     pqueue = xbt_heap_new(nr_nodes, xbt_free);
2014
2015     /* initialize */
2016     cost_arr[src_node_id] = 0.0;
2017
2018     for (i = 0; i < nr_nodes; i++) {
2019       if (i != src_node_id) {
2020         cost_arr[i] = DBL_MAX;
2021       }
2022
2023       pred_arr[i] = 0;
2024
2025       /* initialize priority queue */
2026       nodeid = xbt_new0(int, 1);
2027       *nodeid = i;
2028       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
2029
2030     }
2031
2032     /* apply dijkstra using the indexes from the graph's node array */
2033     while (xbt_heap_size(pqueue) > 0) {
2034       int *v_id = xbt_heap_pop(pqueue);
2035       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
2036       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
2037       xbt_edge_t edge = NULL;
2038       unsigned int cursor;
2039
2040       xbt_dynar_foreach(out_edges, cursor, edge) {
2041         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
2042         graph_node_data_t data = xbt_graph_node_get_data(u_node);
2043         int u_id = data->graph_id;
2044         route_extended_t tmp_e_route =
2045             (route_extended_t) xbt_graph_edge_get_data(edge);
2046         int cost_v_u = (tmp_e_route->generic_route.link_list)->used;    /* count of links, old model assume 1 */
2047
2048         if (cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
2049           pred_arr[u_id] = *v_id;
2050           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
2051           nodeid = xbt_new0(int, 1);
2052           *nodeid = u_id;
2053           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
2054         }
2055       }
2056
2057       /* free item popped from pqueue */
2058       xbt_free(v_id);
2059     }
2060
2061     xbt_free(cost_arr);
2062     xbt_heap_free(pqueue);
2063   }
2064
2065   /* compose route path with links */
2066   char *gw_src = NULL, *gw_dst =
2067       NULL, *prev_gw_src, *prev_gw_dst, *first_gw = NULL;
2068
2069   for (v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
2070     xbt_node_t node_pred_v =
2071         xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
2072     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
2073     xbt_edge_t edge =
2074         xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
2075
2076     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id,
2077                 *dst_id);
2078
2079     prev_gw_src = gw_src;
2080     prev_gw_dst = gw_dst;
2081
2082     e_route = (route_extended_t) xbt_graph_edge_get_data(edge);
2083     gw_src = e_route->src_gateway;
2084     gw_dst = e_route->dst_gateway;
2085
2086     if (v == dst_node_id)
2087       first_gw = gw_dst;
2088
2089     if (rc->hierarchy == SURF_ROUTING_RECURSIVE && v != dst_node_id
2090         && strcmp(gw_dst, prev_gw_src)) {
2091       xbt_dynar_t e_route_as_to_as =
2092           (*(global_routing->get_route)) (gw_dst, prev_gw_src);
2093       xbt_assert2(e_route_as_to_as, "no route between \"%s\" and \"%s\"",
2094                   gw_dst, prev_gw_src);
2095       links = e_route_as_to_as;
2096       int pos = 0;
2097       xbt_dynar_foreach(links, cpt, link) {
2098         xbt_dynar_insert_at(new_e_route->generic_route.link_list, pos,
2099                             &link);
2100         pos++;
2101       }
2102     }
2103
2104     links = e_route->generic_route.link_list;
2105     xbt_dynar_foreach(links, cpt, link) {
2106       xbt_dynar_unshift(new_e_route->generic_route.link_list, &link);
2107     }
2108     size++;
2109   }
2110
2111   if (rc->hierarchy == SURF_ROUTING_RECURSIVE) {
2112     new_e_route->src_gateway = xbt_strdup(gw_src);
2113     new_e_route->dst_gateway = xbt_strdup(first_gw);
2114   }
2115
2116   if (routing->cached && elm == NULL) {
2117     /* add to predecessor list of the current src-host to cache */
2118     elm = xbt_new0(struct route_cache_element, 1);
2119     elm->pred_arr = pred_arr;
2120     elm->size = size;
2121     xbt_dict_set_ext(routing->route_cache, (char *) (&src_id), sizeof(int),
2122                      (xbt_set_elm_t) elm, &route_cache_elem_free);
2123   }
2124
2125   if (!routing->cached)
2126     xbt_free(pred_arr);
2127
2128   return new_e_route;
2129 }
2130
2131 static void dijkstra_finalize(routing_component_t rc)
2132 {
2133   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
2134
2135   if (routing) {
2136     xbt_graph_free_graph(routing->route_graph, &xbt_free,
2137                          &graph_edge_data_free, &xbt_free);
2138     xbt_dict_free(&routing->graph_node_map);
2139     if (routing->cached)
2140       xbt_dict_free(&routing->route_cache);
2141     /* Delete bypass dict */
2142     xbt_dict_free(&routing->generic_routing.bypassRoutes);
2143     /* Delete index dict */
2144     xbt_dict_free(&(routing->generic_routing.to_index));
2145     /* Delete structure */
2146     xbt_free(routing);
2147   }
2148 }
2149
2150 /* Creation routing model functions */
2151
2152 static void *model_dijkstra_both_create(int cached)
2153 {
2154   routing_component_dijkstra_t new_component =
2155       xbt_new0(s_routing_component_dijkstra_t, 1);
2156   new_component->generic_routing.set_processing_unit =
2157       generic_set_processing_unit;
2158   new_component->generic_routing.set_autonomous_system =
2159       generic_set_autonomous_system;
2160   new_component->generic_routing.set_route = model_dijkstra_both_set_route;
2161   new_component->generic_routing.set_ASroute = model_dijkstra_both_set_route; //TODO
2162   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
2163   new_component->generic_routing.get_route = dijkstra_get_route;
2164   new_component->generic_routing.get_latency = generic_get_link_latency;
2165   new_component->generic_routing.get_onelink_routes =
2166       dijkstra_get_onelink_routes;
2167   new_component->generic_routing.get_bypass_route =
2168       generic_get_bypassroute;
2169   new_component->generic_routing.finalize = dijkstra_finalize;
2170   new_component->cached = cached;
2171   new_component->generic_routing.to_index = xbt_dict_new();
2172   new_component->generic_routing.bypassRoutes = xbt_dict_new();
2173   return new_component;
2174 }
2175
2176 static void *model_dijkstra_create(void)
2177 {
2178   return model_dijkstra_both_create(0);
2179 }
2180
2181 static void *model_dijkstracache_create(void)
2182 {
2183   return model_dijkstra_both_create(1);
2184 }
2185
2186 static void model_dijkstra_both_load(void)
2187 {
2188   /* use "surfxml_add_callback" to add a parse function call */
2189 }
2190
2191 static void model_dijkstra_both_unload(void)
2192 {
2193   /* use "surfxml_del_callback" to remove a parse function call */
2194 }
2195
2196 static void model_dijkstra_both_end(void)
2197 {
2198   routing_component_dijkstra_t routing =
2199       (routing_component_dijkstra_t) current_routing;
2200
2201   xbt_node_t node = NULL;
2202   unsigned int cursor2;
2203   xbt_dynar_t nodes = NULL;
2204
2205   /* Create the topology graph */
2206   routing->route_graph = xbt_graph_new_graph(1, NULL);
2207   routing->graph_node_map = xbt_dict_new();
2208
2209   if (routing->cached && !routing->route_cache)
2210     routing->route_cache = xbt_dict_new();
2211
2212   /* Add the loopback if needed */
2213   if (current_routing->hierarchy == SURF_ROUTING_BASE)
2214     add_loopback_dijkstra(routing);
2215
2216   /* initialize graph indexes in nodes after graph has been built */
2217   nodes = xbt_graph_get_nodes(routing->route_graph);
2218
2219   xbt_dynar_foreach(nodes, cursor2, node) {
2220     graph_node_data_t data = xbt_graph_node_get_data(node);
2221     data->graph_id = cursor2;
2222   }
2223
2224 }
2225 static void model_dijkstra_both_set_route (routing_component_t rc, const char *src,
2226                      const char *dst, name_route_extended_t route)
2227 {
2228         routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
2229         int *src_id, *dst_id;
2230         src_id = xbt_dict_get_or_null(rc->to_index, src);
2231         dst_id = xbt_dict_get_or_null(rc->to_index, dst);
2232
2233         if (routing->cached && !routing->route_cache)
2234         routing->route_cache = xbt_dict_new();
2235
2236         if( A_surfxml_route_symmetrical == A_surfxml_route_symmetrical_YES
2237                 || A_surfxml_ASroute_symmetrical == A_surfxml_ASroute_symmetrical_YES )
2238                 xbt_die("Route symmetrical not supported on model dijkstra");
2239
2240         if(!route->dst_gateway && !route->src_gateway)
2241           DEBUG2("Load Route from \"%s\" to \"%s\"", src, dst);
2242         else
2243           DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
2244                          route->src_gateway, dst, route->dst_gateway);
2245
2246         route_extended_t e_route =
2247                 generic_new_extended_route(current_routing->hierarchy, route, 1);
2248         route_new_dijkstra(routing, *src_id, *dst_id, e_route);
2249 }
2250
2251 #ifdef HAVE_PCRE_LIB
2252 /* ************************************************** */
2253 /* ************** RULE-BASED ROUTING **************** */
2254
2255 /* Routing model structure */
2256
2257 typedef struct {
2258   s_routing_component_t generic_routing;
2259   xbt_dict_t dict_processing_units;
2260   xbt_dict_t dict_autonomous_systems;
2261   xbt_dynar_t list_route;
2262   xbt_dynar_t list_ASroute;
2263 } s_routing_component_rulebased_t, *routing_component_rulebased_t;
2264
2265 typedef struct s_rule_route s_rule_route_t, *rule_route_t;
2266 typedef struct s_rule_route_extended s_rule_route_extended_t,
2267     *rule_route_extended_t;
2268
2269 struct s_rule_route {
2270   xbt_dynar_t re_str_link;      // dynar of char*
2271   pcre *re_src;
2272   pcre *re_dst;
2273 };
2274
2275 struct s_rule_route_extended {
2276   s_rule_route_t generic_rule_route;
2277   char *re_src_gateway;
2278   char *re_dst_gateway;
2279 };
2280
2281 static void rule_route_free(void *e)
2282 {
2283   rule_route_t *elem = (rule_route_t *) (e);
2284   if (*elem) {
2285     xbt_dynar_free(&(*elem)->re_str_link);
2286     pcre_free((*elem)->re_src);
2287     pcre_free((*elem)->re_dst);
2288     xbt_free(*elem);
2289   }
2290   *elem = NULL;
2291 }
2292
2293 static void rule_route_extended_free(void *e)
2294 {
2295   rule_route_extended_t *elem = (rule_route_extended_t *) e;
2296   if (*elem) {
2297     xbt_dynar_free(&(*elem)->generic_rule_route.re_str_link);
2298     pcre_free((*elem)->generic_rule_route.re_src);
2299     pcre_free((*elem)->generic_rule_route.re_dst);
2300     xbt_free((*elem)->re_src_gateway);
2301     xbt_free((*elem)->re_dst_gateway);
2302     xbt_free(*elem);
2303   }
2304 }
2305
2306 /* Parse routing model functions */
2307
2308 static void model_rulebased_set_processing_unit(routing_component_t rc,
2309                                                 const char *name)
2310 {
2311   routing_component_rulebased_t routing =
2312       (routing_component_rulebased_t) rc;
2313   xbt_dict_set(routing->dict_processing_units, name, (void *) (-1), NULL);
2314 }
2315
2316 static void model_rulebased_set_autonomous_system(routing_component_t rc,
2317                                                   const char *name)
2318 {
2319   routing_component_rulebased_t routing =
2320       (routing_component_rulebased_t) rc;
2321   xbt_dict_set(routing->dict_autonomous_systems, name, (void *) (-1),
2322                NULL);
2323 }
2324
2325 static void model_rulebased_set_route(routing_component_t rc,
2326                                       const char *src, const char *dst,
2327                                       name_route_extended_t route)
2328 {
2329   routing_component_rulebased_t routing =
2330       (routing_component_rulebased_t) rc;
2331   rule_route_t ruleroute = xbt_new0(s_rule_route_t, 1);
2332   const char *error;
2333   int erroffset;
2334   ruleroute->re_src = pcre_compile(src, 0, &error, &erroffset, NULL);
2335   xbt_assert3(ruleroute->re_src,
2336               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2337               erroffset, src, error);
2338   ruleroute->re_dst = pcre_compile(dst, 0, &error, &erroffset, NULL);
2339   xbt_assert3(ruleroute->re_src,
2340               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2341               erroffset, dst, error);
2342   ruleroute->re_str_link = route->generic_route.link_list;
2343   xbt_dynar_push(routing->list_route, &ruleroute);
2344   xbt_free(route);
2345 }
2346
2347 static void model_rulebased_set_ASroute(routing_component_t rc,
2348                                         const char *src, const char *dst,
2349                                         name_route_extended_t route)
2350 {
2351   routing_component_rulebased_t routing =
2352       (routing_component_rulebased_t) rc;
2353   rule_route_extended_t ruleroute_e = xbt_new0(s_rule_route_extended_t, 1);
2354   const char *error;
2355   int erroffset;
2356   ruleroute_e->generic_rule_route.re_src =
2357       pcre_compile(src, 0, &error, &erroffset, NULL);
2358   xbt_assert3(ruleroute_e->generic_rule_route.re_src,
2359               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2360               erroffset, src, error);
2361   ruleroute_e->generic_rule_route.re_dst =
2362       pcre_compile(dst, 0, &error, &erroffset, NULL);
2363   xbt_assert3(ruleroute_e->generic_rule_route.re_src,
2364               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2365               erroffset, dst, error);
2366   ruleroute_e->generic_rule_route.re_str_link =
2367       route->generic_route.link_list;
2368   ruleroute_e->re_src_gateway = route->src_gateway;
2369   ruleroute_e->re_dst_gateway = route->dst_gateway;
2370   xbt_dynar_push(routing->list_ASroute, &ruleroute_e);
2371 //  xbt_free(route->src_gateway);
2372 //  xbt_free(route->dst_gateway);
2373   xbt_free(route);
2374 }
2375
2376 static void model_rulebased_set_bypassroute(routing_component_t rc,
2377                                             const char *src,
2378                                             const char *dst,
2379                                             route_extended_t e_route)
2380 {
2381   xbt_die("bypass routing not supported for Route-Based model");
2382 }
2383
2384 #define BUFFER_SIZE 4096        /* result buffer size */
2385 #define OVECCOUNT 30            /* should be a multiple of 3 */
2386
2387 static char *remplace(char *value, const char **src_list, int src_size,
2388                       const char **dst_list, int dst_size)
2389 {
2390
2391   char result_result[BUFFER_SIZE];
2392   int i_result_buffer;
2393   int value_length = (int) strlen(value);
2394   int number = 0;
2395
2396   int i = 0;
2397   i_result_buffer = 0;
2398   do {
2399     if (value[i] == '$') {
2400       i++;                      // skip $
2401
2402       // find the number
2403       int number_length = 0;
2404       while ('0' <= value[i + number_length]
2405              && value[i + number_length] <= '9') {
2406         number_length++;
2407       }
2408       xbt_assert2(number_length != 0,
2409                   "bad string parameter, no number indication, at offset: %d (\"%s\")",
2410                   i, value);
2411
2412       // solve number
2413       number = atoi(value + i);
2414       i = i + number_length;
2415       xbt_assert2(i + 2 < value_length,
2416                   "bad string parameter, too few chars, at offset: %d (\"%s\")",
2417                   i, value);
2418
2419       // solve the indication
2420       const char **param_list;
2421       int param_size;
2422       if (value[i] == 's' && value[i + 1] == 'r' && value[i + 2] == 'c') {
2423         param_list = src_list;
2424         param_size = src_size;
2425       } else if (value[i] == 'd' && value[i + 1] == 's'
2426                  && value[i + 2] == 't') {
2427         param_list = dst_list;
2428         param_size = dst_size;
2429       } else {
2430         xbt_assert2(0,
2431                     "bad string parameter, support only \"src\" and \"dst\", at offset: %d (\"%s\")",
2432                     i, value);
2433       }
2434       i = i + 3;
2435
2436       xbt_assert4(param_size >= number,
2437                   "bad string parameter, not enough length param_size, at offset: %d (\"%s\") %d %d",
2438                   i, value, param_size, number);
2439
2440       const char *param = param_list[number];
2441       int size = strlen(param);
2442       int cp;
2443       for (cp = 0; cp < size; cp++) {
2444         result_result[i_result_buffer] = param[cp];
2445         i_result_buffer++;
2446         if (i_result_buffer >= BUFFER_SIZE)
2447           break;
2448       }
2449     } else {
2450       result_result[i_result_buffer] = value[i];
2451       i_result_buffer++;
2452       i++;                      // next char
2453     }
2454
2455   } while (i < value_length && i_result_buffer < BUFFER_SIZE);
2456
2457   xbt_assert2(i_result_buffer < BUFFER_SIZE,
2458               "solving string \"%s\", small buffer size (%d)", value,
2459               BUFFER_SIZE);
2460   result_result[i_result_buffer] = 0;
2461   return xbt_strdup(result_result);
2462 }
2463
2464 static route_extended_t rulebased_get_route(routing_component_t rc,
2465                                             const char *src,
2466                                             const char *dst);
2467 static xbt_dynar_t rulebased_get_onelink_routes(routing_component_t rc)
2468 {
2469   xbt_dynar_t ret = xbt_dynar_new (sizeof(onelink_t), xbt_free);
2470   routing_component_rulebased_t routing = (routing_component_rulebased_t)rc;
2471
2472   xbt_dict_cursor_t c1 = NULL;
2473   char *k1, *d1;
2474
2475   //find router
2476   char *router = NULL;
2477   xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
2478     if (strstr (k1, "router")){
2479       router = k1;
2480     }
2481   }
2482   if (!router){
2483     xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
2484   }
2485
2486   xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
2487     route_extended_t route = rulebased_get_route (rc, router, k1);
2488
2489     int number_of_links = xbt_dynar_length(route->generic_route.link_list);
2490     if (number_of_links != 3) {
2491       xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
2492     }
2493
2494     void *link_ptr;
2495     xbt_dynar_get_cpy (route->generic_route.link_list, 2, &link_ptr);
2496     onelink_t onelink = xbt_new0 (s_onelink_t, 1);
2497     onelink->src = xbt_strdup (k1);
2498     onelink->dst = xbt_strdup (router);
2499     onelink->link_ptr = link_ptr;
2500     xbt_dynar_push (ret, &onelink);
2501   }
2502   return ret;
2503 }
2504
2505 /* Business methods */
2506 static route_extended_t rulebased_get_route(routing_component_t rc,
2507                                             const char *src,
2508                                             const char *dst)
2509 {
2510   xbt_assert1(rc && src
2511               && dst,
2512               "Invalid params for \"get_route\" function at AS \"%s\"",
2513               rc->name);
2514
2515   /* set utils vars */
2516   routing_component_rulebased_t routing =
2517       (routing_component_rulebased_t) rc;
2518
2519   int are_processing_units;
2520   xbt_dynar_t rule_list;
2521   if (xbt_dict_get_or_null(routing->dict_processing_units, src)
2522       && xbt_dict_get_or_null(routing->dict_processing_units, dst)) {
2523     are_processing_units = 1;
2524     rule_list = routing->list_route;
2525   } else if (xbt_dict_get_or_null(routing->dict_autonomous_systems, src)
2526              && xbt_dict_get_or_null(routing->dict_autonomous_systems,
2527                                      dst)) {
2528     are_processing_units = 0;
2529     rule_list = routing->list_ASroute;
2530   } else
2531     xbt_assert2(NULL,
2532                 "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
2533                 src, dst);
2534
2535   int rc_src = -1;
2536   int rc_dst = -1;
2537   int src_length = (int) strlen(src);
2538   int dst_length = (int) strlen(dst);
2539
2540   xbt_dynar_t links_list =
2541       xbt_dynar_new(global_routing->size_of_link, NULL);
2542
2543   rule_route_t ruleroute;
2544   unsigned int cpt;
2545   int ovector_src[OVECCOUNT];
2546   int ovector_dst[OVECCOUNT];
2547   const char **list_src = NULL;
2548   const char **list_dst = NULL;
2549   xbt_dynar_foreach(rule_list, cpt, ruleroute) {
2550     rc_src =
2551         pcre_exec(ruleroute->re_src, NULL, src, src_length, 0, 0,
2552                   ovector_src, OVECCOUNT);
2553     if (rc_src >= 0) {
2554       rc_dst =
2555           pcre_exec(ruleroute->re_dst, NULL, dst, dst_length, 0, 0,
2556                     ovector_dst, OVECCOUNT);
2557       if (rc_dst >= 0) {
2558         xbt_assert1(!pcre_get_substring_list
2559                     (src, ovector_src, rc_src, &list_src),
2560                     "error solving substring list for src \"%s\"", src);
2561         xbt_assert1(!pcre_get_substring_list
2562                     (dst, ovector_dst, rc_dst, &list_dst),
2563                     "error solving substring list for src \"%s\"", dst);
2564         char *link_name;
2565         xbt_dynar_foreach(ruleroute->re_str_link, cpt, link_name) {
2566           char *new_link_name =
2567               remplace(link_name, list_src, rc_src, list_dst, rc_dst);
2568           void *link =
2569               xbt_dict_get_or_null(surf_network_model->resource_set,
2570                                    new_link_name);
2571           if (link)
2572             xbt_dynar_push(links_list, &link);
2573           else
2574             THROW1(mismatch_error, 0, "Link %s not found", new_link_name);
2575           xbt_free(new_link_name);
2576         }
2577       }
2578     }
2579     if (rc_src >= 0 && rc_dst >= 0)
2580       break;
2581   }
2582
2583   route_extended_t new_e_route = NULL;
2584   if (rc_src >= 0 && rc_dst >= 0) {
2585     new_e_route = xbt_new0(s_route_extended_t, 1);
2586     new_e_route->generic_route.link_list = links_list;
2587   } else if (!strcmp(src, dst) && are_processing_units) {
2588     new_e_route = xbt_new0(s_route_extended_t, 1);
2589     xbt_dynar_push(links_list, &(global_routing->loopback));
2590     new_e_route->generic_route.link_list = links_list;
2591   } else {
2592     xbt_dynar_free(&link_list);
2593   }
2594
2595   if (!are_processing_units && new_e_route) {
2596     rule_route_extended_t ruleroute_extended =
2597         (rule_route_extended_t) ruleroute;
2598     new_e_route->src_gateway =
2599         remplace(ruleroute_extended->re_src_gateway, list_src, rc_src,
2600                  list_dst, rc_dst);
2601     new_e_route->dst_gateway =
2602         remplace(ruleroute_extended->re_dst_gateway, list_src, rc_src,
2603                  list_dst, rc_dst);
2604   }
2605
2606   if (list_src)
2607     pcre_free_substring_list(list_src);
2608   if (list_dst)
2609     pcre_free_substring_list(list_dst);
2610
2611   return new_e_route;
2612 }
2613
2614 static route_extended_t rulebased_get_bypass_route(routing_component_t rc,
2615                                                    const char *src,
2616                                                    const char *dst)
2617 {
2618   return NULL;
2619 }
2620
2621 static void rulebased_finalize(routing_component_t rc)
2622 {
2623   routing_component_rulebased_t routing =
2624       (routing_component_rulebased_t) rc;
2625   if (routing) {
2626     xbt_dict_free(&routing->dict_processing_units);
2627     xbt_dict_free(&routing->dict_autonomous_systems);
2628     xbt_dynar_free(&routing->list_route);
2629     xbt_dynar_free(&routing->list_ASroute);
2630     /* Delete structure */
2631     xbt_free(routing);
2632   }
2633 }
2634
2635 /* Creation routing model functions */
2636 static void *model_rulebased_create(void)
2637 {
2638   routing_component_rulebased_t new_component =
2639       xbt_new0(s_routing_component_rulebased_t, 1);
2640   new_component->generic_routing.set_processing_unit =
2641       model_rulebased_set_processing_unit;
2642   new_component->generic_routing.set_autonomous_system =
2643       model_rulebased_set_autonomous_system;
2644   new_component->generic_routing.set_route = model_rulebased_set_route;
2645   new_component->generic_routing.set_ASroute = model_rulebased_set_ASroute;
2646   new_component->generic_routing.set_bypassroute = model_rulebased_set_bypassroute;
2647   new_component->generic_routing.get_onelink_routes = rulebased_get_onelink_routes;
2648   new_component->generic_routing.get_route = rulebased_get_route;
2649   new_component->generic_routing.get_latency = generic_get_link_latency;
2650   new_component->generic_routing.get_bypass_route = rulebased_get_bypass_route;
2651   new_component->generic_routing.finalize = rulebased_finalize;
2652   /* initialization of internal structures */
2653   new_component->dict_processing_units = xbt_dict_new();
2654   new_component->dict_autonomous_systems = xbt_dict_new();
2655   new_component->list_route = xbt_dynar_new(sizeof(rule_route_t), &rule_route_free);
2656   new_component->list_ASroute =
2657       xbt_dynar_new(sizeof(rule_route_extended_t),
2658                     &rule_route_extended_free);
2659   return new_component;
2660 }
2661
2662 static void model_rulebased_load(void)
2663 {
2664   /* use "surfxml_add_callback" to add a parse function call */
2665 }
2666
2667 static void model_rulebased_unload(void)
2668 {
2669   /* use "surfxml_del_callback" to remove a parse function call */
2670 }
2671
2672 static void model_rulebased_end(void)
2673 {
2674 }
2675
2676 #endif                          /* HAVE_PCRE_LIB */
2677
2678 /* ************************************************************************** */
2679 /* ******************************* NO ROUTING ******************************* */
2680
2681 /* Routing model structure */
2682 typedef struct {
2683   s_routing_component_t generic_routing;
2684 } s_routing_component_none_t, *routing_component_none_t;
2685
2686 /* Business methods */
2687 static xbt_dynar_t none_get_onelink_routes(routing_component_t rc)
2688 {
2689   return NULL;
2690 }
2691
2692 static route_extended_t none_get_route(routing_component_t rc,
2693                                        const char *src, const char *dst)
2694 {
2695   return NULL;
2696 }
2697
2698 static route_extended_t none_get_bypass_route(routing_component_t rc,
2699                                               const char *src,
2700                                               const char *dst)
2701 {
2702   return NULL;
2703 }
2704
2705 static void none_finalize(routing_component_t rc)
2706 {
2707   xbt_free(rc);
2708 }
2709
2710 static void none_set_processing_unit(routing_component_t rc,
2711                                      const char *name)
2712 {
2713 }
2714
2715 static void none_set_autonomous_system(routing_component_t rc,
2716                                        const char *name)
2717 {
2718 }
2719
2720 /* Creation routing model functions */
2721 static void *model_none_create(void)
2722 {
2723   routing_component_none_t new_component =
2724       xbt_new0(s_routing_component_none_t, 1);
2725   new_component->generic_routing.set_processing_unit =
2726       none_set_processing_unit;
2727   new_component->generic_routing.set_autonomous_system =
2728       none_set_autonomous_system;
2729   new_component->generic_routing.set_route = NULL;
2730   new_component->generic_routing.set_ASroute = NULL;
2731   new_component->generic_routing.set_bypassroute = NULL;
2732   new_component->generic_routing.get_route = none_get_route;
2733   new_component->generic_routing.get_onelink_routes =
2734       none_get_onelink_routes;
2735   new_component->generic_routing.get_bypass_route = none_get_bypass_route;
2736   new_component->generic_routing.finalize = none_finalize;
2737   return new_component;
2738 }
2739
2740 static void model_none_load(void)
2741 {
2742 }
2743
2744 static void model_none_unload(void)
2745 {
2746 }
2747
2748 static void model_none_end(void)
2749 {
2750 }
2751
2752 /* ************************************************** */
2753 /* ********** PATERN FOR NEW ROUTING **************** */
2754
2755 /* The minimal configuration of a new routing model need the next functions,
2756  * also you need to set at the start of the file, the new model in the model
2757  * list. Remember keep the null ending of the list.
2758  */
2759 /*** Routing model structure ***/
2760 // typedef struct {
2761 //   s_routing_component_t generic_routing;
2762 //   /* things that your routing model need */
2763 // } s_routing_component_NEW_t,*routing_component_NEW_t;
2764
2765 /*** Parse routing model functions ***/
2766 // static void model_NEW_set_processing_unit(routing_component_t rc, const char* name) {}
2767 // static void model_NEW_set_autonomous_system(routing_component_t rc, const char* name) {}
2768 // static void model_NEW_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {}
2769 // static void model_NEW_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t route) {}
2770 // static void model_NEW_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {}
2771
2772 /*** Business methods ***/
2773 // static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
2774 // static route_extended_t NEW_get_bypass_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
2775 // static void NEW_finalize(routing_component_t rc) { xbt_free(rc);}
2776
2777 /*** Creation routing model functions ***/
2778 // static void* model_NEW_create(void) {
2779 //   routing_component_NEW_t new_component =  xbt_new0(s_routing_component_NEW_t,1);
2780 //   new_component->generic_routing.set_processing_unit = model_NEW_set_processing_unit;
2781 //   new_component->generic_routing.set_autonomous_system = model_NEW_set_autonomous_system;
2782 //   new_component->generic_routing.set_route = model_NEW_set_route;
2783 //   new_component->generic_routing.set_ASroute = model_NEW_set_ASroute;
2784 //   new_component->generic_routing.set_bypassroute = model_NEW_set_bypassroute;
2785 //   new_component->generic_routing.get_route = NEW_get_route;
2786 //   new_component->generic_routing.get_bypass_route = NEW_get_bypass_route;
2787 //   new_component->generic_routing.finalize = NEW_finalize;
2788 //   /* initialization of internal structures */
2789 //   return new_component;
2790 // } /* mandatory */
2791 // static void  model_NEW_load(void) {}   /* mandatory */
2792 // static void  model_NEW_unload(void) {} /* mandatory */
2793 // static void  model_NEW_end(void) {}    /* mandatory */
2794
2795 /* ************************************************************************** */
2796 /* ************************* GENERIC PARSE FUNCTIONS ************************ */
2797
2798 static void generic_set_processing_unit(routing_component_t rc,
2799                                         const char *name)
2800 {
2801   DEBUG1("Load process unit \"%s\"", name);
2802   int *id = xbt_new0(int, 1);
2803   xbt_dict_t _to_index;
2804   _to_index = current_routing->to_index;
2805   *id = xbt_dict_length(_to_index);
2806   xbt_dict_set(_to_index, name, id, xbt_free);
2807 }
2808
2809 static void generic_set_autonomous_system(routing_component_t rc,
2810                                           const char *name)
2811 {
2812   DEBUG1("Load Autonomous system \"%s\"", name);
2813   int *id = xbt_new0(int, 1);
2814   xbt_dict_t _to_index;
2815   _to_index = current_routing->to_index;
2816   *id = xbt_dict_length(_to_index);
2817   xbt_dict_set(_to_index, name, id, xbt_free);
2818 }
2819
2820 static int surf_pointer_resource_cmp(const void *a, const void *b)
2821 {
2822   return a != b;
2823 }
2824
2825 static int surf_link_resource_cmp(const void *a, const void *b)
2826 {
2827   return !!memcmp(a,b,global_routing->size_of_link);
2828 }
2829
2830 static void generic_set_bypassroute(routing_component_t rc,
2831                                     const char *src, const char *dst,
2832                                     route_extended_t e_route)
2833 {
2834   DEBUG2("Load bypassRoute from \"%s\" to \"%s\"", src, dst);
2835   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
2836   char *route_name;
2837
2838   route_name = bprintf("%s#%s", src, dst);
2839   xbt_assert2(xbt_dynar_length(e_route->generic_route.link_list) > 0,
2840               "Invalid count of links, must be greater than zero (%s,%s)",
2841               src, dst);
2842   xbt_assert4(!xbt_dict_get_or_null(dict_bypassRoutes, route_name),
2843               "The bypass route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exists",
2844               src, e_route->src_gateway, dst, e_route->dst_gateway);
2845
2846   route_extended_t new_e_route =
2847       generic_new_extended_route(SURF_ROUTING_RECURSIVE, e_route, 0);
2848   xbt_dynar_free(&(e_route->generic_route.link_list));
2849   xbt_free(e_route);
2850
2851   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route,
2852                (void (*)(void *)) generic_free_extended_route);
2853   xbt_free(route_name);
2854 }
2855
2856 /* ************************************************************************** */
2857 /* *********************** GENERIC BUSINESS METHODS ************************* */
2858
2859 static double generic_get_link_latency(routing_component_t rc,
2860                                        const char *src, const char *dst)
2861 {
2862         route_extended_t route = rc->get_route(rc,src,dst);
2863         void * link;
2864         unsigned int i;
2865         double latency = 0.0;
2866
2867         xbt_dynar_foreach(route->generic_route.link_list,i,link) {
2868                 latency += get_link_latency(link);
2869         }
2870         generic_free_extended_route(route);
2871   return latency;
2872 }
2873
2874 static xbt_dynar_t generic_get_onelink_routes(routing_component_t rc)
2875 {
2876   xbt_die("\"generic_get_onelink_routes\" not implemented yet");
2877 }
2878
2879 static route_extended_t generic_get_bypassroute(routing_component_t rc,
2880                                                 const char *src,
2881                                                 const char *dst)
2882 {
2883   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
2884   routing_component_t src_as, dst_as;
2885   int index_src, index_dst;
2886   xbt_dynar_t path_src = NULL;
2887   xbt_dynar_t path_dst = NULL;
2888   routing_component_t current = NULL;
2889   routing_component_t *current_src = NULL;
2890   routing_component_t *current_dst = NULL;
2891
2892   /* (1) find the as where the src and dst are located */
2893   src_as = ((network_element_info_t)
2894             xbt_dict_get_or_null(global_routing->where_network_elements,
2895                                  src))->rc_component;
2896   dst_as = ((network_element_info_t)
2897             xbt_dict_get_or_null(global_routing->where_network_elements,
2898                                  dst))->rc_component;
2899   xbt_assert2(src_as
2900               && dst_as,
2901               "Ask for route \"from\"(%s) or \"to\"(%s) no found", src,
2902               dst);
2903
2904   /* (2) find the path to the root routing component */
2905   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
2906   current = src_as;
2907   while (current != NULL) {
2908     xbt_dynar_push(path_src, &current);
2909     current = current->routing_father;
2910   }
2911   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
2912   current = dst_as;
2913   while (current != NULL) {
2914     xbt_dynar_push(path_dst, &current);
2915     current = current->routing_father;
2916   }
2917
2918   /* (3) find the common father */
2919   index_src = path_src->used - 1;
2920   index_dst = path_dst->used - 1;
2921   current_src = xbt_dynar_get_ptr(path_src, index_src);
2922   current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
2923   while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
2924     routing_component_t *tmp_src, *tmp_dst;
2925     tmp_src = xbt_dynar_pop_ptr(path_src);
2926     tmp_dst = xbt_dynar_pop_ptr(path_dst);
2927     index_src--;
2928     index_dst--;
2929     current_src = xbt_dynar_get_ptr(path_src, index_src);
2930     current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
2931   }
2932
2933   int max_index_src = path_src->used - 1;
2934   int max_index_dst = path_dst->used - 1;
2935
2936   int max_index = max(max_index_src, max_index_dst);
2937   int i, max;
2938
2939   route_extended_t e_route_bypass = NULL;
2940
2941   for (max = 0; max <= max_index; max++) {
2942     for (i = 0; i < max; i++) {
2943       if (i <= max_index_src && max <= max_index_dst) {
2944         char *route_name = bprintf("%s#%s",
2945                                    (*(routing_component_t *)
2946                                     (xbt_dynar_get_ptr
2947                                      (path_src, i)))->name,
2948                                    (*(routing_component_t *)
2949                                     (xbt_dynar_get_ptr
2950                                      (path_dst, max)))->name);
2951         e_route_bypass =
2952             xbt_dict_get_or_null(dict_bypassRoutes, route_name);
2953         xbt_free(route_name);
2954       }
2955       if (e_route_bypass)
2956         break;
2957       if (max <= max_index_src && i <= max_index_dst) {
2958         char *route_name = bprintf("%s#%s",
2959                                    (*(routing_component_t *)
2960                                     (xbt_dynar_get_ptr
2961                                      (path_src, max)))->name,
2962                                    (*(routing_component_t *)
2963                                     (xbt_dynar_get_ptr
2964                                      (path_dst, i)))->name);
2965         e_route_bypass =
2966             xbt_dict_get_or_null(dict_bypassRoutes, route_name);
2967         xbt_free(route_name);
2968       }
2969       if (e_route_bypass)
2970         break;
2971     }
2972
2973     if (e_route_bypass)
2974       break;
2975
2976     if (max <= max_index_src && max <= max_index_dst) {
2977       char *route_name = bprintf("%s#%s",
2978                                  (*(routing_component_t *)
2979                                   (xbt_dynar_get_ptr
2980                                    (path_src, max)))->name,
2981                                  (*(routing_component_t *)
2982                                   (xbt_dynar_get_ptr
2983                                    (path_dst, max)))->name);
2984       e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
2985       xbt_free(route_name);
2986     }
2987     if (e_route_bypass)
2988       break;
2989   }
2990
2991   xbt_dynar_free(&path_src);
2992   xbt_dynar_free(&path_dst);
2993
2994   route_extended_t new_e_route = NULL;
2995
2996   if (e_route_bypass) {
2997     void *link;
2998     unsigned int cpt = 0;
2999     new_e_route = xbt_new0(s_route_extended_t, 1);
3000     new_e_route->src_gateway = xbt_strdup(e_route_bypass->src_gateway);
3001     new_e_route->dst_gateway = xbt_strdup(e_route_bypass->dst_gateway);
3002     new_e_route->generic_route.link_list =
3003         xbt_dynar_new(global_routing->size_of_link, NULL);
3004     xbt_dynar_foreach(e_route_bypass->generic_route.link_list, cpt, link) {
3005       xbt_dynar_push(new_e_route->generic_route.link_list, &link);
3006     }
3007   }
3008
3009   return new_e_route;
3010 }
3011
3012 /* ************************************************************************** */
3013 /* ************************* GENERIC AUX FUNCTIONS ************************** */
3014
3015 static route_t
3016 generic_new_route(e_surf_routing_hierarchy_t hierarchy,
3017                            void *data, int order)
3018 {
3019
3020   char *link_name;
3021   route_t new_route;
3022   unsigned int cpt;
3023   xbt_dynar_t links = NULL, links_id = NULL;
3024
3025   new_route = xbt_new0(s_route_t, 1);
3026   new_route->link_list =
3027       xbt_dynar_new(global_routing->size_of_link, NULL);
3028
3029   xbt_assert0(hierarchy == SURF_ROUTING_BASE,
3030               "the hierarchy type is not SURF_ROUTING_BASE");
3031
3032   links = ((route_t) data)->link_list;
3033
3034
3035   links_id = new_route->link_list;
3036
3037   xbt_dynar_foreach(links, cpt, link_name) {
3038
3039     void *link =
3040         xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
3041     if (link) {
3042       if (order)
3043         xbt_dynar_push(links_id, &link);
3044       else
3045         xbt_dynar_unshift(links_id, &link);
3046     } else
3047       THROW1(mismatch_error, 0, "Link %s not found", link_name);
3048   }
3049
3050   return new_route;
3051 }
3052
3053 static route_extended_t
3054 generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy,
3055                            void *data, int order)
3056 {
3057
3058   char *link_name;
3059   route_extended_t e_route, new_e_route;
3060   route_t route;
3061   unsigned int cpt;
3062   xbt_dynar_t links = NULL, links_id = NULL;
3063
3064   new_e_route = xbt_new0(s_route_extended_t, 1);
3065   new_e_route->generic_route.link_list =
3066       xbt_dynar_new(global_routing->size_of_link, NULL);
3067   new_e_route->src_gateway = NULL;
3068   new_e_route->dst_gateway = NULL;
3069
3070   xbt_assert0(hierarchy == SURF_ROUTING_BASE
3071               || hierarchy == SURF_ROUTING_RECURSIVE,
3072               "the hierarchy type is not defined");
3073
3074   if (hierarchy == SURF_ROUTING_BASE) {
3075
3076     route = (route_t) data;
3077     links = route->link_list;
3078
3079   } else if (hierarchy == SURF_ROUTING_RECURSIVE) {
3080
3081     e_route = (route_extended_t) data;
3082     xbt_assert0(e_route->src_gateway
3083                 && e_route->dst_gateway, "bad gateway, is null");
3084     links = e_route->generic_route.link_list;
3085
3086     /* remeber not erase the gateway names */
3087     new_e_route->src_gateway = e_route->src_gateway;
3088     new_e_route->dst_gateway = e_route->dst_gateway;
3089   }
3090
3091   links_id = new_e_route->generic_route.link_list;
3092
3093   xbt_dynar_foreach(links, cpt, link_name) {
3094
3095     void *link =
3096         xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
3097     if (link) {
3098       if (order)
3099         xbt_dynar_push(links_id, &link);
3100       else
3101         xbt_dynar_unshift(links_id, &link);
3102     } else
3103       THROW1(mismatch_error, 0, "Link %s not found", link_name);
3104   }
3105
3106   return new_e_route;
3107 }
3108
3109 static void generic_free_route(route_t route)
3110 {
3111   if (route) {
3112     xbt_dynar_free(&(route->link_list));
3113     xbt_free(route);
3114   }
3115 }
3116
3117 static void generic_free_extended_route(route_extended_t e_route)
3118 {
3119   if (e_route) {
3120     xbt_dynar_free(&(e_route->generic_route.link_list));
3121     if (e_route->src_gateway)
3122       xbt_free(e_route->src_gateway);
3123     if (e_route->dst_gateway)
3124       xbt_free(e_route->dst_gateway);
3125     xbt_free(e_route);
3126   }
3127 }
3128
3129 static routing_component_t generic_as_exist(routing_component_t find_from,
3130                                             routing_component_t to_find)
3131 {
3132   //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
3133   xbt_dict_cursor_t cursor = NULL;
3134   char *key;
3135   int found = 0;
3136   routing_component_t elem;
3137   xbt_dict_foreach(find_from->routing_sons, cursor, key, elem) {
3138     if (to_find == elem || generic_as_exist(elem, to_find)) {
3139       found = 1;
3140       break;
3141     }
3142   }
3143   if (found)
3144     return to_find;
3145   return NULL;
3146 }
3147
3148 static routing_component_t
3149 generic_autonomous_system_exist(routing_component_t rc, char *element)
3150 {
3151   //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
3152   routing_component_t element_as, result, elem;
3153   xbt_dict_cursor_t cursor = NULL;
3154   char *key;
3155   element_as = ((network_element_info_t)
3156                 xbt_dict_get_or_null
3157                 (global_routing->where_network_elements,
3158                  element))->rc_component;
3159   result = ((routing_component_t) - 1);
3160   if (element_as != rc)
3161     result = generic_as_exist(rc, element_as);
3162
3163   int found = 0;
3164   if (result) {
3165     xbt_dict_foreach(element_as->routing_sons, cursor, key, elem) {
3166       found = !strcmp(elem->name, element);
3167       if (found)
3168         break;
3169     }
3170     if (found)
3171       return element_as;
3172   }
3173   return NULL;
3174 }
3175
3176 static routing_component_t
3177 generic_processing_units_exist(routing_component_t rc, char *element)
3178 {
3179   routing_component_t element_as;
3180   element_as = ((network_element_info_t)
3181                 xbt_dict_get_or_null
3182                 (global_routing->where_network_elements,
3183                  element))->rc_component;
3184   if (element_as == rc)
3185     return element_as;
3186   return generic_as_exist(rc, element_as);
3187 }
3188
3189 static void generic_src_dst_check(routing_component_t rc, const char *src,
3190                                   const char *dst)
3191 {
3192
3193   routing_component_t src_as = ((network_element_info_t)
3194                                 xbt_dict_get_or_null
3195                                 (global_routing->where_network_elements,
3196                                  src))->rc_component;
3197   routing_component_t dst_as = ((network_element_info_t)
3198                                 xbt_dict_get_or_null
3199                                 (global_routing->where_network_elements,
3200                                  dst))->rc_component;
3201
3202   xbt_assert3(src_as != NULL && dst_as != NULL,
3203               "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
3204               src, dst, rc->name);
3205   xbt_assert4(src_as == dst_as,
3206               "The src(%s in %s) and dst(%s in %s) are in differents AS",
3207               src, src_as->name, dst, dst_as->name);
3208   xbt_assert2(rc == dst_as,
3209               "The routing component of src and dst is not the same as the network elements belong (%s==%s)",
3210               rc->name, dst_as->name);
3211 }
3212
3213 static void routing_parse_Sconfig(void)
3214 {
3215   //TODO
3216   DEBUG0("WARNING tag config not yet implemented.");
3217   DEBUG1("Configuration name = %s",A_surfxml_config_id);
3218 }
3219
3220 static void routing_parse_Econfig(void)
3221 {
3222   //TODO
3223   xbt_dict_cursor_t cursor = NULL;
3224   char *key;
3225   char *elem;
3226   xbt_dict_foreach(current_property_set, cursor, key, elem) {
3227           DEBUG2("property : %s = %s",key,elem);
3228         }
3229 }
3230
3231 static void routing_parse_Scluster(void)
3232 {
3233   static int AX_ptr = 0;
3234
3235   char *cluster_id = A_surfxml_cluster_id;
3236   char *cluster_prefix = A_surfxml_cluster_prefix;
3237   char *cluster_suffix = A_surfxml_cluster_suffix;
3238   char *cluster_radical = A_surfxml_cluster_radical;
3239   char *cluster_power = A_surfxml_cluster_power;
3240   char *cluster_core = A_surfxml_cluster_core;
3241   char *cluster_bw = A_surfxml_cluster_bw;
3242   char *cluster_lat = A_surfxml_cluster_lat;
3243   char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
3244   char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
3245   char *host_id, *groups, *link_id = NULL;
3246   char *router_id, *link_router, *link_backbone;
3247 #ifdef HAVE_PCRE_LIB
3248   char *route_src_dst;
3249 #endif
3250   unsigned int iter;
3251   int start, end, i;
3252   xbt_dynar_t radical_elements;
3253   xbt_dynar_t radical_ends;
3254   int cluster_sharing_policy = AX_surfxml_cluster_sharing_policy;
3255   int cluster_bb_sharing_policy = AX_surfxml_cluster_bb_sharing_policy;
3256
3257 #ifndef HAVE_PCRE_LIB
3258   xbt_dynar_t tab_elements_num = xbt_dynar_new(sizeof(int), NULL);
3259   char *route_src, *route_dst;
3260   int j;
3261 #endif
3262
3263   static unsigned int surfxml_buffer_stack_stack_ptr = 1;
3264   static unsigned int surfxml_buffer_stack_stack[1024];
3265
3266   surfxml_buffer_stack_stack[0] = 0;
3267
3268   surfxml_bufferstack_push(1);
3269
3270   SURFXML_BUFFER_SET(AS_id, cluster_id);
3271 #ifdef HAVE_PCRE_LIB
3272   SURFXML_BUFFER_SET(AS_routing, "RuleBased");
3273   DEBUG1("<AS id=\"%s\"\trouting=\"RuleBased\">", cluster_id);
3274 #else
3275   SURFXML_BUFFER_SET(AS_routing, "Full");
3276   DEBUG1("<AS id=\"%s\"\trouting=\"Full\">", cluster_id);
3277 #endif
3278   SURFXML_START_TAG(AS);
3279
3280   radical_elements = xbt_str_split(cluster_radical, ",");
3281   xbt_dynar_foreach(radical_elements, iter, groups) {
3282     radical_ends = xbt_str_split(groups, "-");
3283     switch (xbt_dynar_length(radical_ends)) {
3284     case 1:
3285       surf_parse_get_int(&start,
3286                          xbt_dynar_get_as(radical_ends, 0, char *));
3287       host_id = bprintf("%s%d%s", cluster_prefix, start, cluster_suffix);
3288 #ifndef HAVE_PCRE_LIB
3289       xbt_dynar_push_as(tab_elements_num, int, start);
3290 #endif
3291       link_id = bprintf("%s_link_%d", cluster_id, start);
3292
3293       DEBUG2("<host\tid=\"%s\"\tpower=\"%s\"/>", host_id, cluster_power);
3294       A_surfxml_host_state = A_surfxml_host_state_ON;
3295       SURFXML_BUFFER_SET(host_id, host_id);
3296       SURFXML_BUFFER_SET(host_power, cluster_power);
3297       SURFXML_BUFFER_SET(host_core, cluster_core);
3298       SURFXML_BUFFER_SET(host_availability, "1.0");
3299       SURFXML_BUFFER_SET(host_availability_file, "");
3300       SURFXML_BUFFER_SET(host_state_file, "");
3301       SURFXML_START_TAG(host);
3302       SURFXML_END_TAG(host);
3303
3304       DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id,cluster_bw, cluster_lat);
3305       A_surfxml_link_state = A_surfxml_link_state_ON;
3306       A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3307       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3308           {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3309       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
3310           {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3311       SURFXML_BUFFER_SET(link_id, link_id);
3312       SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
3313       SURFXML_BUFFER_SET(link_latency, cluster_lat);
3314       SURFXML_BUFFER_SET(link_bandwidth_file, "");
3315       SURFXML_BUFFER_SET(link_latency_file, "");
3316       SURFXML_BUFFER_SET(link_state_file, "");
3317       SURFXML_START_TAG(link);
3318       SURFXML_END_TAG(link);
3319
3320       free(link_id);
3321       free(host_id);
3322       break;
3323
3324     case 2:
3325
3326       surf_parse_get_int(&start,
3327                          xbt_dynar_get_as(radical_ends, 0, char *));
3328       surf_parse_get_int(&end, xbt_dynar_get_as(radical_ends, 1, char *));
3329       DEBUG2("Create hosts and links from %d to %d", start, end);
3330       for (i = start; i <= end; i++) {
3331         host_id = bprintf("%s%d%s", cluster_prefix, i, cluster_suffix);
3332 #ifndef HAVE_PCRE_LIB
3333         xbt_dynar_push_as(tab_elements_num, int, i);
3334 #endif
3335         link_id = bprintf("%s_link_%d", cluster_id, i);
3336
3337         DEBUG2("<host\tid=\"%s\"\tpower=\"%s\"/>", host_id, cluster_power);
3338         A_surfxml_host_state = A_surfxml_host_state_ON;
3339         SURFXML_BUFFER_SET(host_id, host_id);
3340         SURFXML_BUFFER_SET(host_power, cluster_power);
3341         SURFXML_BUFFER_SET(host_core, cluster_core);
3342         SURFXML_BUFFER_SET(host_availability, "1.0");
3343         SURFXML_BUFFER_SET(host_availability_file, "");
3344         SURFXML_BUFFER_SET(host_state_file, "");
3345         SURFXML_START_TAG(host);
3346         SURFXML_END_TAG(host);
3347
3348         DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id,cluster_bw, cluster_lat);
3349         A_surfxml_link_state = A_surfxml_link_state_ON;
3350         A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3351         if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3352             {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3353         if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
3354             {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3355         SURFXML_BUFFER_SET(link_id, link_id);
3356         SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
3357         SURFXML_BUFFER_SET(link_latency, cluster_lat);
3358         SURFXML_BUFFER_SET(link_bandwidth_file, "");
3359         SURFXML_BUFFER_SET(link_latency_file, "");
3360         SURFXML_BUFFER_SET(link_state_file, "");
3361         SURFXML_START_TAG(link);
3362         SURFXML_END_TAG(link);
3363
3364         free(link_id);
3365         free(host_id);
3366       }
3367       break;
3368
3369     default:
3370       DEBUG0("Malformed radical");
3371     }
3372
3373     xbt_dynar_free(&radical_ends);
3374   }
3375   xbt_dynar_free(&radical_elements);
3376
3377   DEBUG0(" ");
3378   router_id =
3379       bprintf("%s%s_router%s", cluster_prefix, cluster_id,
3380               cluster_suffix);
3381   link_router = bprintf("%s_link_%s_router", cluster_id, cluster_id);
3382   link_backbone = bprintf("%s_backbone", cluster_id);
3383
3384   DEBUG1("<router id=\"%s\"/>", router_id);
3385   SURFXML_BUFFER_SET(router_id, router_id);;
3386   SURFXML_START_TAG(router);
3387   SURFXML_END_TAG(router);
3388
3389   DEBUG3("<link\tid=\"%s\" bw=\"%s\" lat=\"%s\"/>", link_router,cluster_bw, cluster_lat);
3390   A_surfxml_link_state = A_surfxml_link_state_ON;
3391   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3392   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3393   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3394   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
3395   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3396   SURFXML_BUFFER_SET(link_id, link_router);
3397   SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
3398   SURFXML_BUFFER_SET(link_latency, cluster_lat);
3399   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3400   SURFXML_BUFFER_SET(link_latency_file, "");
3401   SURFXML_BUFFER_SET(link_state_file, "");
3402   SURFXML_START_TAG(link);
3403   SURFXML_END_TAG(link);
3404
3405   DEBUG3("<link\tid=\"%s\" bw=\"%s\" lat=\"%s\"/>", link_backbone,cluster_bw, cluster_lat);
3406   A_surfxml_link_state = A_surfxml_link_state_ON;
3407   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3408   if(cluster_bb_sharing_policy == A_surfxml_cluster_bb_sharing_policy_FATPIPE)
3409   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3410   SURFXML_BUFFER_SET(link_id, link_backbone);
3411   SURFXML_BUFFER_SET(link_bandwidth, cluster_bb_bw);
3412   SURFXML_BUFFER_SET(link_latency, cluster_bb_lat);
3413   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3414   SURFXML_BUFFER_SET(link_latency_file, "");
3415   SURFXML_BUFFER_SET(link_state_file, "");
3416   SURFXML_START_TAG(link);
3417   SURFXML_END_TAG(link);
3418
3419   DEBUG0(" ");
3420
3421 #ifdef HAVE_PCRE_LIB
3422   char *new_suffix = xbt_strdup("");
3423
3424   radical_elements = xbt_str_split(cluster_suffix, ".");
3425   xbt_dynar_foreach(radical_elements, iter, groups) {
3426     if (strcmp(groups, "")) {
3427       char *old_suffix = new_suffix;
3428       new_suffix = bprintf("%s\\.%s", old_suffix, groups);
3429       free(old_suffix);
3430     }
3431   }
3432   route_src_dst = bprintf("%s(.*)%s", cluster_prefix, new_suffix);
3433   xbt_dynar_free(&radical_elements);
3434   free(new_suffix);
3435
3436   char *pcre_link_src = bprintf("%s_link_$1src", cluster_id);
3437   char *pcre_link_backbone = bprintf("%s_backbone", cluster_id);
3438   char *pcre_link_dst = bprintf("%s_link_$1dst", cluster_id);
3439
3440   DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", route_src_dst, route_src_dst);
3441   DEBUG0("symmetrical=\"NO\">");
3442   SURFXML_BUFFER_SET(route_src, route_src_dst);
3443   SURFXML_BUFFER_SET(route_dst, route_src_dst);
3444   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3445   SURFXML_START_TAG(route);
3446
3447   DEBUG1("<link_ctn\tid=\"%s\"/>", pcre_link_src);
3448   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_src);
3449   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3450   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3451   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
3452   SURFXML_START_TAG(link_ctn);
3453   SURFXML_END_TAG(link_ctn);
3454
3455   DEBUG1("<link_ctn\tid=\"%s\"/>", pcre_link_backbone);
3456   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_backbone);
3457   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3458   SURFXML_START_TAG(link_ctn);
3459   SURFXML_END_TAG(link_ctn);
3460
3461   DEBUG1("<link_ctn\tid=\"%s\"/>", pcre_link_dst);
3462   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_dst);
3463   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3464   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3465   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_DOWN;}
3466   SURFXML_START_TAG(link_ctn);
3467   SURFXML_END_TAG(link_ctn);
3468
3469   DEBUG0("</route>");
3470   SURFXML_END_TAG(route);
3471
3472   free(pcre_link_dst);
3473   free(pcre_link_backbone);
3474   free(pcre_link_src);
3475   free(route_src_dst);
3476 #else
3477   for (i = 0; i <= xbt_dynar_length(tab_elements_num); i++) {
3478     for (j = 0; j <= xbt_dynar_length(tab_elements_num); j++) {
3479       if (i == xbt_dynar_length(tab_elements_num)) {
3480         route_src = router_id;
3481       } else {
3482         route_src =
3483             bprintf("%s%d%s", cluster_prefix,
3484                     xbt_dynar_get_as(tab_elements_num, i, int),
3485                     cluster_suffix);
3486       }
3487
3488       if (j == xbt_dynar_length(tab_elements_num)) {
3489         route_dst = router_id;
3490       } else {
3491         route_dst =
3492             bprintf("%s%d%s", cluster_prefix,
3493                     xbt_dynar_get_as(tab_elements_num, j, int),
3494                     cluster_suffix);
3495       }
3496
3497       DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", route_src, route_dst);
3498       DEBUG0("symmetrical=\"NO\">");
3499       SURFXML_BUFFER_SET(route_src, route_src);
3500       SURFXML_BUFFER_SET(route_dst, route_dst);
3501       A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3502       SURFXML_START_TAG(route);
3503
3504       if (i == xbt_dynar_length(tab_elements_num)) {
3505         route_src = link_router;
3506       } else {
3507         route_src =
3508             bprintf("%s_link_%d", cluster_id,
3509                     xbt_dynar_get_as(tab_elements_num, i, int));
3510       }
3511
3512       if (j == xbt_dynar_length(tab_elements_num)) {
3513         route_dst = link_router;
3514       } else {
3515         route_dst =
3516             bprintf("%s_link_%d", cluster_id,
3517                     xbt_dynar_get_as(tab_elements_num, j, int));
3518       }
3519
3520       DEBUG1("<link_ctn\tid=\"%s\"/>", route_src);
3521       SURFXML_BUFFER_SET(link_ctn_id, route_src);
3522       A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3523       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3524       {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
3525       SURFXML_START_TAG(link_ctn);
3526       SURFXML_END_TAG(link_ctn);
3527
3528       DEBUG1("<link_ctn\tid=\"%s_backbone\"/>", cluster_id);
3529       SURFXML_BUFFER_SET(link_ctn_id, bprintf("%s_backbone", cluster_id));
3530       A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3531       SURFXML_START_TAG(link_ctn);
3532       SURFXML_END_TAG(link_ctn);
3533
3534       DEBUG1("<link_ctn\tid=\"%s\"/>", route_dst);
3535       SURFXML_BUFFER_SET(link_ctn_id, route_dst);
3536       A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3537       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3538       {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_DOWN;}
3539       SURFXML_START_TAG(link_ctn);
3540       SURFXML_END_TAG(link_ctn);
3541
3542       DEBUG0("</route>");
3543       SURFXML_END_TAG(route);
3544     }
3545   }
3546   xbt_dynar_free(&tab_elements_num);
3547   free(router_id);
3548
3549 #endif
3550
3551   free(link_backbone);
3552   free(link_router);
3553
3554   DEBUG0("</AS>");
3555   SURFXML_END_TAG(AS);
3556   DEBUG0(" ");
3557
3558   surfxml_bufferstack_pop(1);
3559 }
3560
3561 static void routing_parse_Speer(void)
3562 {
3563   static int AX_ptr = 0;
3564
3565   char *peer_id = A_surfxml_peer_id;
3566   char *peer_power = A_surfxml_peer_power;
3567   char *peer_bw_in = A_surfxml_peer_bw_in;
3568   char *peer_bw_out = A_surfxml_peer_bw_out;
3569   char *peer_lat = A_surfxml_peer_lat;
3570   char *peer_coord = A_surfxml_peer_coordinates;
3571
3572   char *host_id = NULL;
3573   char *router_id, *link_router, *link_backbone, *link_id_up, *link_id_down;
3574
3575 #ifdef HAVE_PCRE_LIB
3576
3577 #endif
3578
3579   int peer_sharing_policy = AX_surfxml_peer_sharing_policy;
3580
3581 #ifndef HAVE_PCRE_LIB
3582   //xbt_dynar_t tab_elements_num = xbt_dynar_new(sizeof(int), NULL);
3583   //char *route_src, *route_dst;
3584   //int j;
3585 #endif
3586
3587   static unsigned int surfxml_buffer_stack_stack_ptr = 1;
3588   static unsigned int surfxml_buffer_stack_stack[1024];
3589
3590   surfxml_buffer_stack_stack[0] = 0;
3591
3592   surfxml_bufferstack_push(1);
3593
3594   SURFXML_BUFFER_SET(AS_id, peer_id);
3595 #ifdef HAVE_PCRE_LIB
3596   SURFXML_BUFFER_SET(AS_routing, "RuleBased");
3597   DEBUG1("<AS id=\"%s\"\trouting=\"RuleBased\">", peer_id);
3598 #else
3599   SURFXML_BUFFER_SET(AS_routing, "Full");
3600   DEBUG1("<AS id=\"%s\"\trouting=\"Full\">", peer_id);
3601 #endif
3602   SURFXML_START_TAG(AS);
3603
3604   DEBUG0(" ");
3605   host_id = bprintf("peer_%s", peer_id);
3606   router_id = bprintf("router_%s", peer_id);
3607   link_id_up = bprintf("link_%s_up", peer_id);
3608   link_id_down = bprintf("link_%s_down", peer_id);
3609
3610   link_router = bprintf("%s_link_router", peer_id);
3611   link_backbone = bprintf("%s_backbone", peer_id);
3612
3613   DEBUG2("<host\tid=\"%s\"\tpower=\"%s\"/>", host_id, peer_power);
3614   A_surfxml_host_state = A_surfxml_host_state_ON;
3615   SURFXML_BUFFER_SET(host_id, host_id);
3616   SURFXML_BUFFER_SET(host_power, peer_power);
3617   SURFXML_BUFFER_SET(host_availability, "1.0");
3618   SURFXML_BUFFER_SET(host_availability_file, "");
3619   SURFXML_BUFFER_SET(host_state_file, "");
3620   SURFXML_START_TAG(host);
3621   SURFXML_END_TAG(host);
3622
3623   DEBUG2("<router id=\"%s\"\tcoordinates=\"%s\"/>", router_id, peer_coord);
3624   SURFXML_BUFFER_SET(router_id, router_id);
3625   SURFXML_BUFFER_SET(router_coordinates, peer_coord);
3626   SURFXML_START_TAG(router);
3627   SURFXML_END_TAG(router);
3628
3629   DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id_up, peer_bw_in, peer_lat);
3630   A_surfxml_link_state = A_surfxml_link_state_ON;
3631   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3632   if(peer_sharing_policy == A_surfxml_peer_sharing_policy_FULLDUPLEX)
3633 {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3634   SURFXML_BUFFER_SET(link_id, link_id_up);
3635   SURFXML_BUFFER_SET(link_bandwidth, peer_bw_in);
3636   SURFXML_BUFFER_SET(link_latency, peer_lat);
3637   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3638   SURFXML_BUFFER_SET(link_latency_file, "");
3639   SURFXML_BUFFER_SET(link_state_file, "");
3640   SURFXML_START_TAG(link);
3641   SURFXML_END_TAG(link);
3642
3643   DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id_down, peer_bw_out, peer_lat);
3644   A_surfxml_link_state = A_surfxml_link_state_ON;
3645   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3646   if(peer_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3647 {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3648   SURFXML_BUFFER_SET(link_id, link_id_down);
3649   SURFXML_BUFFER_SET(link_bandwidth, peer_bw_out);
3650   SURFXML_BUFFER_SET(link_latency, peer_lat);
3651   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3652   SURFXML_BUFFER_SET(link_latency_file, "");
3653   SURFXML_BUFFER_SET(link_state_file, "");
3654   SURFXML_START_TAG(link);
3655   SURFXML_END_TAG(link);
3656
3657   DEBUG0(" ");
3658
3659   // begin here
3660   DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", peer_id, router_id);
3661   DEBUG0("symmetrical=\"NO\">");
3662   SURFXML_BUFFER_SET(route_src, peer_id);
3663   SURFXML_BUFFER_SET(route_dst, router_id);
3664   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3665   SURFXML_START_TAG(route);
3666
3667   DEBUG1("<link_ctn\tid=\"%s\"/>", link_id_up);
3668   SURFXML_BUFFER_SET(link_ctn_id, link_id_up);
3669   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3670   if(peer_sharing_policy == A_surfxml_peer_sharing_policy_FULLDUPLEX)
3671   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
3672   SURFXML_START_TAG(link_ctn);
3673   SURFXML_END_TAG(link_ctn);
3674
3675   DEBUG0("</route>");
3676   SURFXML_END_TAG(route);
3677
3678   //Opposite Route
3679   DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", router_id, peer_id);
3680   DEBUG0("symmetrical=\"NO\">");
3681   SURFXML_BUFFER_SET(route_src, router_id);
3682   SURFXML_BUFFER_SET(route_dst, peer_id);
3683   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3684   SURFXML_START_TAG(route);
3685
3686   DEBUG1("<link_ctn\tid=\"%s\"/>", link_id_down);
3687   SURFXML_BUFFER_SET(link_ctn_id, link_id_down);
3688   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3689   if(peer_sharing_policy == A_surfxml_peer_sharing_policy_FULLDUPLEX)
3690   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_DOWN;}
3691   SURFXML_START_TAG(link_ctn);
3692   SURFXML_END_TAG(link_ctn);
3693
3694   DEBUG0("</route>");
3695   SURFXML_END_TAG(route);
3696
3697   DEBUG0("</AS>");
3698   SURFXML_END_TAG(AS);
3699   DEBUG0(" ");
3700
3701   //xbt_dynar_free(&tab_elements_num);
3702
3703   surfxml_bufferstack_pop(1);
3704 }
3705
3706
3707 /*
3708  * New methods to init the routing model component from the lua script
3709  */
3710
3711 /*
3712  * calling parse_S_AS_lua with lua values
3713  */
3714 void routing_AS_init(const char *AS_id, const char *AS_routing)
3715 {
3716   parse_S_AS_lua((char *) AS_id, (char *) AS_routing);
3717 }
3718
3719 /*
3720  * calling parse_E_AS_lua to fisnish the creation of routing component
3721  */
3722 void routing_AS_end(const char *AS_id)
3723 {
3724   parse_E_AS_lua((char *) AS_id);
3725 }
3726
3727 /*
3728  * add a host to the network element list
3729  */
3730
3731 void routing_add_host(const char *host_id)
3732 {
3733   parse_S_host_lua((char *) host_id, (char*)""); // FIXME propagate coordinate system to lua
3734 }
3735
3736 /*
3737  * Set a new link on the actual list of link for a route or ASroute
3738  */
3739 void routing_add_link(const char *link_id)
3740 {
3741   parse_E_link_c_ctn_new_elem_lua((char *) link_id);
3742 }
3743
3744 /*
3745  *Set the endpoints for a route
3746  */
3747 void routing_set_route(const char *src_id, const char *dst_id)
3748 {
3749   parse_S_route_new_and_endpoints_lua(src_id, dst_id);
3750 }
3751
3752 /*
3753  * Store the route by calling parse_E_route_store_route
3754  */
3755 void routing_store_route(void)
3756 {
3757   parse_E_route_store_route();
3758 }