src/surf/surf_routing.c

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