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