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