src/surf/surf_routing.c

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