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