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