src/surf/surf_routing.c

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