src/surf/surf_routing.c

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