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