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 #include <float.h>
   8 #include "surf_private.h"
   9 #include "xbt/dynar.h"
  10 #include "xbt/str.h"
  11 #include "xbt/config.h"
  12 #include "xbt/graph.h"
  13 #include "xbt/set.h"
  14
  15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf");
  16
  17 ////////////////////////////////////////////////////////////////////////////////
  18 // HERE START THE NEW CODE
  19 ////////////////////////////////////////////////////////////////////////////////
  20
  21 //...... DEBUG ONLY .... //
  22 static void print_tree(routing_component_t rc);
  23 static void print_global(void);
  24 static void print_AS_start(void);
  25 static void print_AS_end(void);
  26 static void print_host(void);
  27 static void print_link(void);
  28 static void print_route(void);
  29 static void print_ctn(void);
  30 static void DEBUG_exit(void);
  31
  32 ////////////////////////////////////////////////////////////////////////////////
  33 // HERE START THE NEW CODE
  34 ////////////////////////////////////////////////////////////////////////////////
  35
  36 /* Global vars */
  37 routing_global_t global_routing = NULL;
  38 routing_component_t current_routing = NULL;
  39 model_type_t current_routing_model = NULL;
  40
  41 /* Prototypes of each model */
  42 static void* model_full_create(void); /* create structures for full routing model */
  43 static void  model_full_load(void);   /* load parse functions for full routing model */
  44 static void  model_full_unload(void); /* unload parse functions for full routing model */
  45 static void  model_full_end(void);    /* finalize the creation of full routing model */
  46
  47 static void* model_floyd_create(void); /* create structures for floyd routing model */
  48 static void  model_floyd_load(void);   /* load parse functions for floyd routing model */
  49 static void  model_floyd_unload(void); /* unload parse functions for floyd routing model */
  50 static void  model_floyd_end(void);    /* finalize the creation of floyd routing model */
  51
  52 static void* model_dijkstra_both_create(int cached); /* create by calling dijkstra or dijkstracache */
  53 static void* model_dijkstra_create(void);      /* create structures for dijkstra routing model */
  54 static void* model_dijkstracache_create(void); /* create structures for dijkstracache routing model */
  55 static void  model_dijkstra_both_load(void);   /* load parse functions for dijkstra routing model */
  56 static void  model_dijkstra_both_unload(void); /* unload parse functions for dijkstra routing model */
  57 static void  model_dijkstra_both_end(void);    /* finalize the creation of dijkstra routing model */
  58
  59 static void* model_none_create(void); /* none routing model */
  60 static void  model_none_load(void);   /* none routing model */
  61 static void  model_none_unload(void); /* none routing model */
  62 static void  model_none_end(void);    /* none routing model */
  63
  64 /* Table of routing models */
  65 // typedef enum {
  66 //   SURF_MODEL_FULL = 0,
  67 //   SURF_MODEL_FLOYD,
  68 //   SURF_MODEL_DIJKSTRA,
  69 //   SURF_MODEL_DIJKSTRACACHE,
  70 //   SURF_MODEL_NONE
  71 // } e_surf_model_type_t;
  72
  73 /* this lines are olny for replace use like index in the model table */
  74 #define SURF_MODEL_FULL           0
  75 #define SURF_MODEL_FLOYD          1
  76 #define SURF_MODEL_DIJKSTRA       2
  77 #define SURF_MODEL_DIJKSTRACACHE  3
  78 #define SURF_MODEL_NONE           4
  79
  80 /* must be finish with null and carefull if change de order */
  81 struct s_model_type routing_models[] =
  82 { {"Full", "Full routing data (fast, large memory requirements, fully expressive)",
  83   model_full_create, model_full_load, model_full_unload, model_full_end },
  84   {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)",
  85   model_floyd_create, model_floyd_load, model_floyd_unload, model_floyd_end },
  86   {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)",
  87   model_dijkstra_create ,model_dijkstra_both_load, model_dijkstra_both_unload, model_dijkstra_both_end },
  88   {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)",
  89   model_dijkstracache_create, model_dijkstra_both_load, model_dijkstra_both_unload, model_dijkstra_both_end },
  90   {"none", "No routing (usable with Constant network only)",
  91   model_none_create, model_none_load, model_none_unload, model_none_end },
  92   {NULL,NULL,NULL,NULL,NULL,NULL}};
  93
  94 /* global parse functions */
  95
  96 static char* src = NULL;    /* temporary store the source name of a route */
  97 static char* dst = NULL;    /* temporary store the destination name of a route */
  98 static char* gw_src = NULL; /* temporary store the gateway source name of a route */
  99 static char* gw_dst = NULL; /* temporary store the gateway destination name of a route */
 100 static xbt_dynar_t link_list = NULL; /* temporary store of current list link of a route */
 101
 102 /**
 103  * \brief Add a "host" to the network element list
 104  */
 105 static void  parse_S_host(void) {
 106   if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_BASE;
 107   xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,A_surfxml_host_id),
 108       "Reading a host, processing unit \"%s\" already exist",A_surfxml_host_id);
 109 // FIXME: checked by parser
 110 //   xbt_assert1(current_routing->hierarchy==SURF_ROUTING_BASE,
 111 //       "Bad declaration of processing unit \"%s\"",A_surfxml_host_id);
 112   (*(current_routing->set_processing_units))(current_routing,A_surfxml_host_id);
 113   xbt_dict_set(global_routing->where_network_elements,A_surfxml_host_id,(void*)current_routing,NULL);
 114 }
 115
 116 /**
 117  * \brief Add a "router" to the network element list
 118  */
 119 static void parse_S_router(void) {
 120   if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_BASE;
 121   xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,A_surfxml_router_id),
 122       "Reading a router, processing unit \"%s\" already exist",A_surfxml_router_id);
 123 // FIXME: checked by parser
 124 //   xbt_assert1(current_routing->hierarchy==SURF_ROUTING_BASE,
 125 //       "Bad declaration of processing unit \"%s\"",A_surfxml_host_id);
 126   (*(current_routing->set_processing_units))(current_routing,A_surfxml_router_id);
 127   xbt_dict_set(global_routing->where_network_elements,A_surfxml_router_id,(void*)current_routing,NULL);
 128 }
 129
 130 /**
 131  * \brief Set the endponints for a route
 132  */
 133 static void parse_S_route_new_and_endpoints(void) {
 134   // FIXME: checked by parser
 135 //   xbt_assert1(current_routing->hierarchy==SURF_ROUTING_BASE,
 136 //     "Bad declaration of route in \"%s\"",current_routing->name);
 137   if( src != NULL && dst != NULL && link_list != NULL )
 138     THROW2(arg_error,0,"Route between %s to %s can not be defined",A_surfxml_route_src,A_surfxml_route_dst);
 139   src = A_surfxml_route_src;
 140   dst = A_surfxml_route_dst;
 141   link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 142 }
 143
 144 /**
 145  * \brief Set the endponints and gateways for a ASroute
 146  */
 147 static void parse_S_ASroute_new_and_endpoints(void) {
 148 // FIXME: checked by parser
 149 //   xbt_assert1(current_routing->hierarchy==SURF_ROUTING_RECURSIVE,
 150 //     "Bad declaration of ASroute in \"%s\"",current_routing->name);
 151   if( src != NULL && dst != NULL && link_list != NULL )
 152     THROW2(arg_error,0,"Route between %s to %s can not be defined",A_surfxml_ASroute_src,A_surfxml_ASroute_dst);
 153   src = A_surfxml_ASroute_src;
 154   dst = A_surfxml_ASroute_dst;
 155   gw_src = A_surfxml_ASroute_gw_src;
 156   gw_dst = A_surfxml_ASroute_gw_dst;
 157   link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 158 }
 159
 160 /**
 161  * \brief Set a new link on the actual list of link for a route or ASroute
 162  */
 163 static void parse_E_link_c_ctn_new_elem(void) {
 164   char *val;
 165   val = xbt_strdup(A_surfxml_link_c_ctn_id);
 166   xbt_dynar_push(link_list, &val);
 167 }
 168
 169 /**
 170  * \brief Store de route by calling the set_route function of the current routing component
 171  */
 172 static void parse_E_route_store_route(void) {
 173 // FIXME: checked by parser
 174 //   xbt_assert1(current_routing->hierarchy==SURF_ROUTING_BASE,
 175 //     "Bad declaration of route in \"%s\"",current_routing->name);
 176   route_t route = xbt_new0(s_route_t,1);
 177   route->link_list = link_list;
 178   // TODO check if are correct
 179   (*(current_routing->set_route))(current_routing,src,dst,route);
 180   link_list = NULL;
 181   src = NULL;
 182   dst = NULL;
 183 }
 184
 185 /**
 186  * \brief Store de ASroute by calling the set_ASroute function of the current routing component
 187  */
 188 static void parse_E_ASroute_store_route(void) {
 189 // FIXME: checked by parser
 190 //   xbt_assert1(current_routing->hierarchy==SURF_ROUTING_RECURSIVE,
 191 //     "Bad declaration of ASroute in \"%s\"",current_routing->name);
 192   route_extended_t e_route = xbt_new0(s_route_extended_t,1);
 193   e_route->generic_route.link_list = link_list;
 194   e_route->src_gateway = xbt_strdup(gw_src);
 195   e_route->dst_gateway = xbt_strdup(gw_dst);
 196   // TODO check if are correct
 197   (*(current_routing->set_ASroute))(current_routing,src,dst,e_route);
 198   link_list = NULL;
 199   src = NULL;
 200   dst = NULL;
 201   gw_src = NULL;
 202   gw_dst = NULL;
 203 }
 204
 205 /**
 206  * \brief Make a new routing component
 207  *
 208  * Detect the routing model type of the routing component, make the new structure and
 209  * set the parsing functions to allows parsing the part of the routing tree
 210  */
 211 static void parse_S_AS(void) {
 212   routing_component_t new_routing;
 213   model_type_t model = NULL;
 214   char* wanted = A_surfxml_AS_routing;
 215   int cpt;
 216   /* seach the routing model */
 217   for (cpt=0;routing_models[cpt].name;cpt++)
 218     if (!strcmp(wanted,routing_models[cpt].name))
 219           model = &routing_models[cpt];
 220   /* if its not exist, error */
 221   if( model == NULL ) {
 222     fprintf(stderr,"Routing model %s not found. Existing models:\n",wanted);
 223     for (cpt=0;routing_models[cpt].name;cpt++)
 224       if (!strcmp(wanted,routing_models[cpt].name))
 225         fprintf(stderr,"   %s: %s\n",routing_models[cpt].name,routing_models[cpt].desc);
 226     xbt_die(NULL);
 227   }
 228
 229   /* make a new routing component */
 230   new_routing = (routing_component_t)(*(model->create))();
 231
 232   /* FIXME: for now, if I forget to declare */
 233   xbt_assert1( new_routing->set_processing_units,
 234        "Bad routing type, \"set_processing_units\" is not declared for \"%s\"",A_surfxml_AS_id);
 235   xbt_assert1( new_routing->set_autonomous_system,
 236        "Bad routing type, \"set_autonomous_system\" is not declared for \"%s\"",A_surfxml_AS_id);
 237   xbt_assert1( new_routing->set_route,
 238        "Bad routing type, \"set_route\" is not declared for \"%s\"",A_surfxml_AS_id);
 239   xbt_assert1( new_routing->set_ASroute,
 240        "Bad routing type, \"set_ASroute\" is not declared for \"%s\"",A_surfxml_AS_id);
 241   xbt_assert1( new_routing->finalize,
 242        "Bad routing type, \"finalize\" is not declared for \"%s\"",A_surfxml_AS_id);
 243
 244   new_routing->routing = model;
 245   new_routing->hierarchy = SURF_ROUTING_NULL;
 246   new_routing->name = xbt_strdup(A_surfxml_AS_id);
 247   new_routing->routing_sons = xbt_dict_new();
 248   INFO2("Routing %s for AS %s",A_surfxml_AS_routing,A_surfxml_AS_id);
 249
 250   if( current_routing == NULL && global_routing->root == NULL ){
 251
 252     /* it is the first one */
 253     new_routing->routing_father = NULL;
 254     global_routing->root = new_routing;
 255
 256   } else if( current_routing != NULL && global_routing->root != NULL ) {
 257
 258     xbt_assert1(!xbt_dict_get_or_null(current_routing->routing_sons,A_surfxml_AS_id),
 259            "The AS \"%s\" already exist",A_surfxml_AS_id);
 260      /* it is a part of the tree */
 261     new_routing->routing_father = current_routing;
 262     /* set the father behavior */
 263     if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_RECURSIVE;
 264 // FIXME: checked by parser
 265 //     xbt_assert1(current_routing->hierarchy==SURF_ROUTING_RECURSIVE,
 266 //       "Bad declaration of AS \"%s\"",A_surfxml_AS_id);
 267     /* add to the sons dictionary */
 268     xbt_dict_set(current_routing->routing_sons,A_surfxml_AS_id,(void*)new_routing,NULL);
 269     /* add to the father element list */
 270     (*(current_routing->set_autonomous_system))(current_routing,A_surfxml_AS_id);
 271     /* unload the prev parse rules */
 272     (*(current_routing->routing->unload))();
 273
 274   } else {
 275     THROW0(arg_error,0,"All defined components must be belong to a AS");
 276   }
 277   /* set the new parse rules */
 278   (*(new_routing->routing->load))();
 279   /* set the new current component of the tree */
 280   current_routing = new_routing;
 281 }
 282
 283 /**
 284  * \brief Finish the creation of a new routing component
 285  *
 286  * When you finish to read the routing component, other structures must be created.
 287  * the "end" method allow to do that for any routing model type
 288  */
 289 static void parse_E_AS(void) {
 290
 291   if( current_routing == NULL ) {
 292     THROW1(arg_error,0,"Close AS(%s), that never open",A_surfxml_AS_id);
 293   } else {
 294       (*(current_routing->routing->unload))();
 295       (*(current_routing->routing->end))();
 296       current_routing = current_routing->routing_father;
 297       if( current_routing != NULL )
 298         (*(current_routing->routing->load))();
 299   }
 300 }
 301
 302 /**
 303  * \brief Recursive function for add the differents AS to global dict of network element
 304  *
 305  * This fuction is call by "parse_E_platform_add_parse_AS". It allow to add the
 306  * AS or routing components, to the where_network_elements dictionary. In the same
 307  * way as "parse_S_host", "parse_S_router" and "parse_S_gateway" do.
 308  */
 309 static void _add_parse_AS(routing_component_t rc) {
 310   xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,rc->name),
 311      "The AS \"%s\" already exist",rc->name);
 312   xbt_dict_set(global_routing->where_network_elements,rc->name,rc->routing_father,NULL);
 313   xbt_dict_cursor_t cursor = NULL;
 314   char *key;
 315   routing_component_t elem;
 316   xbt_dict_foreach(rc->routing_sons, cursor, key, elem) {
 317     _add_parse_AS(elem);
 318   }
 319 }
 320
 321 /**
 322  * \brief Add all "AS" to the global dict of network element
 323  *
 324  * Allows find a "AS" in any routing component
 325  */
 326 static void parse_E_platform_add_parse_AS(void) {
 327   _add_parse_AS(global_routing->root);
 328 }
 329
 330 /* Aux Business methods */
 331
 332 /**
 333  * \brief Get the AS father and the first elements of the chain
 334  *
 335  * \param src the source host name
 336  * \param dst the destination host name
 337  *
 338  * Get the common father of the to processing units, and the first different
 339  * father in the chain
 340  */
 341 static xbt_dynar_t elements_father(const char* src,const char* dst) {
 342
 343   xbt_assert0(src&&dst,"bad parameters for \"elements_father\" method");
 344
 345   xbt_dynar_t result = xbt_dynar_new(sizeof(char*), NULL); // &xbt_free_ref
 346
 347   routing_component_t src_as, dst_as;
 348   int index_src, index_dst, index_father_src, index_father_dst;
 349   xbt_dynar_t path_src = NULL;
 350   xbt_dynar_t path_dst = NULL;
 351   routing_component_t current = NULL;
 352   routing_component_t* current_src = NULL;
 353   routing_component_t* current_dst = NULL;
 354   routing_component_t* father = NULL;
 355
 356   /* (1) find the as where the src and dst are located */
 357   src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
 358   dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
 359   xbt_assert2(src_as&&dst_as, "Ask for route \"from\"(%s) or \"to\"(%s) no found",src,dst);
 360
 361   /* (2) find the path to the root routing component */
 362   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
 363   current = src_as;
 364   while( current != NULL ) {
 365     xbt_dynar_push(path_src,&current);
 366     current = current->routing_father;
 367   }
 368   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
 369   current = dst_as;
 370   while( current != NULL ) {
 371     xbt_dynar_push(path_dst,&current);
 372     current = current->routing_father;
 373   }
 374
 375   /* (3) find the common father */
 376   index_src  = (path_src->used)-1;
 377   index_dst  = (path_dst->used)-1;
 378   current_src = xbt_dynar_get_ptr(path_src,index_src);
 379   current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
 380   while( index_src >= 0 && index_dst >= 0 && *current_src == *current_dst ) {
 381     current_src = xbt_dynar_get_ptr(path_src,index_src);
 382     current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
 383     index_src--;
 384     index_dst--;
 385   }
 386   index_src++;
 387   index_dst++;
 388   current_src = xbt_dynar_get_ptr(path_src,index_src);
 389   current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
 390
 391   /* (4) they are not in the same routing component, make the path */
 392   index_father_src = index_src+1;
 393   index_father_dst = index_dst+1;
 394
 395   if(*current_src==*current_dst)
 396     father = current_src;
 397   else
 398     father = xbt_dynar_get_ptr(path_src,index_father_src);
 399
 400   /* (5) result generation */
 401   xbt_dynar_push(result,father); // first same the father of src and dst
 402   xbt_dynar_push(result,current_src); // second the first different father of src
 403   xbt_dynar_push(result,current_dst); // three  the first different father of dst
 404
 405   xbt_dynar_free(&path_src);
 406   xbt_dynar_free(&path_dst);
 407
 408   return result;
 409 }
 410
 411 /* Global Business methods */
 412
 413 /**
 414  * \brief Recursive function for get_route
 415  *
 416  * \param src the source host name
 417  * \param dst the destination host name
 418  *
 419  * This fuction is call by "get_route". It allow to walk through the
 420  * routing components tree.
 421  */
 422 static route_extended_t _get_route(const char* src,const char* dst) {
 423
 424   void* link;
 425   unsigned int cpt=0;
 426
 427   DEBUG2("Solve route  \"%s\" to \"%s\"",src,dst);
 428
 429   xbt_assert0(src&&dst,"bad parameters for \"_get_route\" method");
 430
 431   route_extended_t e_route, e_route_cnt, e_route_src, e_route_dst;
 432
 433   xbt_dynar_t elem_father_list = elements_father(src,dst);
 434
 435   routing_component_t common_father = xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 436   routing_component_t src_father    = xbt_dynar_get_as(elem_father_list, 1, routing_component_t);
 437   routing_component_t dst_father    = xbt_dynar_get_as(elem_father_list, 2, routing_component_t);
 438
 439   e_route = xbt_new0(s_route_extended_t,1);
 440   e_route->src_gateway = NULL;
 441   e_route->dst_gateway = NULL;
 442   e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 443
 444   if(src_father==dst_father) { /* SURF_ROUTING_BASE */
 445
 446     if( strcmp(src,dst) ){
 447       e_route_cnt = (*(common_father->get_route))(common_father,src,dst);
 448       xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
 449         xbt_dynar_push(e_route->generic_route.link_list,&link);
 450       }
 451       xbt_dynar_free( &(e_route_cnt->generic_route.link_list) );
 452       xbt_free(e_route_cnt);
 453     }
 454
 455   } else { /* SURF_ROUTING_RECURSIVE */
 456
 457       e_route_cnt = (*(common_father->get_route))(common_father,src_father->name,dst_father->name);
 458
 459       xbt_assert2( (e_route_cnt->src_gateway==NULL) == (e_route_cnt->dst_gateway==NULL) ,
 460         "bad gateway for route between \"%s\" and \"%s\"",src,dst);
 461
 462       if( src != e_route_cnt->src_gateway ) {
 463         e_route_src = _get_route(src,e_route_cnt->src_gateway);
 464         xbt_dynar_foreach(e_route_src->generic_route.link_list, cpt, link) {
 465           xbt_dynar_push(e_route->generic_route.link_list,&link);
 466         }
 467       }
 468
 469       xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
 470         xbt_dynar_push(e_route->generic_route.link_list,&link);
 471       }
 472
 473       if( e_route_cnt->dst_gateway != dst ) {
 474         e_route_dst = _get_route(e_route_cnt->dst_gateway,dst);
 475         xbt_dynar_foreach(e_route_dst->generic_route.link_list, cpt, link) {
 476           xbt_dynar_push(e_route->generic_route.link_list,&link);
 477         }
 478       }
 479
 480       e_route->src_gateway = e_route_cnt->src_gateway;
 481       e_route->dst_gateway = e_route_cnt->dst_gateway;
 482
 483       xbt_dynar_free( &(e_route_src->generic_route.link_list) );
 484       xbt_free(e_route_src);
 485       xbt_dynar_free( &(e_route_cnt->generic_route.link_list) );
 486       xbt_free(e_route_cnt);
 487       xbt_dynar_free( &(e_route_dst->generic_route.link_list) );
 488       xbt_free(e_route_dst);
 489   }
 490
 491   xbt_dynar_free(&elem_father_list);
 492
 493   return e_route;
 494 }
 495
 496 /**
 497  * \brief Generic method: find a route between hosts
 498  *
 499  * \param src the source host name
 500  * \param dst the destination host name
 501  *
 502  * walk through the routing components tree and find a route between hosts
 503  * by calling the differents "get_route" functions in each routing component
 504  */
 505 static xbt_dynar_t get_route(const char* src,const char* dst) {
 506
 507   if(global_routing->last_route) xbt_dynar_free( &(global_routing->last_route) );
 508
 509   route_extended_t e_route;
 510   xbt_dynar_t elem_father_list = elements_father(src,dst);
 511   routing_component_t common_father = xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 512
 513   if(strcmp(src,dst))
 514     e_route = _get_route(src,dst);
 515   else
 516     e_route = (*(common_father->get_route))(common_father,src,dst);
 517
 518   global_routing->last_route = e_route->generic_route.link_list;
 519
 520   xbt_free(e_route);
 521   xbt_dynar_free(&elem_father_list);
 522
 523   if( xbt_dynar_length(global_routing->last_route)==0 )
 524     return NULL;
 525   else
 526     return global_routing->last_route;
 527 }
 528
 529 /**
 530  * \brief Recursive function for finalize
 531  *
 532  * \param rc the source host name
 533  *
 534  * This fuction is call by "finalize". It allow to finalize the
 535  * AS or routing components. It delete all the structures.
 536  */
 537 static void _finalize(routing_component_t rc) {
 538   if(rc) {
 539     xbt_dict_cursor_t cursor = NULL;
 540     char *key;
 541     routing_component_t elem;
 542     xbt_dict_foreach(rc->routing_sons, cursor, key, elem) {
 543       _finalize(elem);
 544     }
 545     xbt_dict_t tmp_sons = rc->routing_sons;
 546     char* tmp_name = rc->name;
 547     xbt_dict_free(&tmp_sons);
 548     xbt_free(tmp_name);
 549     (*(rc->finalize))(rc);
 550   }
 551 }
 552
 553 /**
 554  * \brief Generic method: delete all the routing structures
 555  *
 556  * walk through the routing components tree and delete the structures
 557  * by calling the differents "finalize" functions in each routing component
 558  */
 559 static void finalize(void) {
 560   /* delete recursibly all the tree */
 561   _finalize(global_routing->root);
 562   /* delete "where" dict */
 563   xbt_dict_free(&(global_routing->where_network_elements));
 564   /* delete last_route */
 565   xbt_dynar_free(&(global_routing->last_route));
 566   /* delete global routing structure */
 567   xbt_free(global_routing);
 568 }
 569
 570 /**
 571  * \brief Generic method: create the global routing schema
 572  *
 573  * Make a global routing structure and set all the parsing functions.
 574  */
 575 void routing_model_create(size_t size_of_links, void* loopback) {
 576
 577   /* config the uniq global routing */
 578   global_routing = xbt_new0(s_routing_global_t,1);
 579   global_routing->where_network_elements = xbt_dict_new();
 580   global_routing->root = NULL;
 581   global_routing->get_route = get_route;
 582   global_routing->finalize = finalize;
 583   global_routing->loopback = loopback;
 584   global_routing->size_of_link = size_of_links;
 585   global_routing->last_route = xbt_dynar_new(size_of_links, NULL);
 586
 587   /* no current routing at moment */
 588   current_routing = NULL;
 589
 590   /* parse generic elements */
 591   surfxml_add_callback(STag_surfxml_host_cb_list, &parse_S_host);
 592   surfxml_add_callback(STag_surfxml_router_cb_list, &parse_S_router);
 593
 594   surfxml_add_callback(STag_surfxml_route_cb_list, &parse_S_route_new_and_endpoints);
 595   surfxml_add_callback(STag_surfxml_ASroute_cb_list, &parse_S_ASroute_new_and_endpoints);
 596
 597   surfxml_add_callback(ETag_surfxml_link_c_ctn_cb_list, &parse_E_link_c_ctn_new_elem);
 598
 599   surfxml_add_callback(ETag_surfxml_route_cb_list, &parse_E_route_store_route);
 600   surfxml_add_callback(ETag_surfxml_ASroute_cb_list, &parse_E_ASroute_store_route);
 601
 602   surfxml_add_callback(STag_surfxml_AS_cb_list, &parse_S_AS);
 603   surfxml_add_callback(ETag_surfxml_AS_cb_list, &parse_E_AS);
 604
 605   /* set all the as in the global where table (recursive fuction) */
 606   surfxml_add_callback(ETag_surfxml_platform_cb_list, &parse_E_platform_add_parse_AS);
 607
 608   /* DEBUG ONLY */
 609   //surfxml_add_callback(ETag_surfxml_platform_cb_list, &DEBUG_exit);
 610 }
 611
 612 /* ************************************************************************** */
 613 /* ***************** GENERIC PARSE FUNCTIONS (declarations) ***************** */
 614
 615 static void generic_set_processing_units(routing_component_t rc, const char* name);
 616 static void generic_set_autonomous_system(routing_component_t rc, const char* name);
 617 static void generic_set_route(routing_component_t rc, const char* src, const char* dst, route_t route);
 618 static void generic_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route);
 619
 620 /* ************************************************************************** */
 621 /* ****************** GENERIC AUX FUNCTIONS (declarations) ****************** */
 622
 623 static route_extended_t generic_new_extended_route(routing_component_t rc, void* data);
 624
 625 /* ************************************************************************** */
 626 /* *************************** FULL ROUTING ********************************* */
 627
 628 #define TO_ROUTE_FULL(i,j) routing->routing_table[(i)+(j)*table_size]
 629
 630 /* Routing model structure */
 631
 632 typedef struct {
 633   s_routing_component_t generic_routing;
 634   xbt_dict_t parse_routes; /* store data during the parse process */
 635   xbt_dict_t to_index; /* char* -> network_element_t */
 636   route_extended_t *routing_table;
 637 } s_routing_component_full_t,*routing_component_full_t;
 638
 639 /* Business methods */
 640
 641 static route_extended_t full_get_route(routing_component_t rc, const char* src,const char* dst) {
 642
 643   routing_component_full_t routing = (routing_component_full_t)rc;
 644   int table_size = xbt_dict_length(routing->to_index);
 645
 646   xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
 647
 648   routing_component_t src_as, dst_as;
 649   int *src_id,*dst_id;
 650
 651   // TODO: MAKE A FUNCTION FOR GENERIC CHECK
 652   src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
 653   dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
 654
 655   xbt_assert3(src_as != NULL && dst_as  != NULL, "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",src,dst,rc->name);
 656   xbt_assert4(src_as == dst_as, "The src(%s in %s) and dst(%s in %s) are in differents AS",src,src_as->name,dst,dst_as->name);
 657   xbt_assert2(rc == dst_as, "The routing component of src and dst is not the same as the network elements belong (%s==%s)",rc->name,dst_as->name);
 658
 659   src_id = xbt_dict_get(routing->to_index,src);
 660   dst_id = xbt_dict_get(routing->to_index,dst);
 661   xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",src,dst);
 662
 663   void* link;
 664   unsigned int cpt=0;
 665   route_extended_t new_e_route;
 666   route_extended_t e_route = TO_ROUTE_FULL(*src_id,*dst_id);
 667   if(e_route) {
 668     new_e_route = xbt_new0(s_route_extended_t,1);
 669     new_e_route->src_gateway = e_route->src_gateway;
 670     new_e_route->dst_gateway = e_route->dst_gateway;
 671     new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 672     xbt_dynar_foreach(e_route->generic_route.link_list, cpt, link) {
 673       xbt_dynar_push(new_e_route->generic_route.link_list,&link);
 674     }
 675   } else {
 676     new_e_route = NULL;
 677   }
 678     return new_e_route;
 679 }
 680
 681 static void full_finalize(routing_component_t rc) {
 682   routing_component_full_t routing = (routing_component_full_t)rc;
 683   int table_size = xbt_dict_length(routing->to_index);
 684   int i,j;
 685   if (routing) {
 686     /* Delete routing table */
 687     for (i=0;i<table_size;i++) {
 688       for (j=0;j<table_size;j++) {
 689         route_extended_t e_route = TO_ROUTE_FULL(i,j);
 690         if(e_route) {
 691           xbt_dynar_free(&(e_route->generic_route.link_list));
 692           if(e_route->src_gateway) xbt_free(e_route->src_gateway);
 693           if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
 694           xbt_free(e_route);
 695         }
 696       }
 697     }
 698     xbt_free(routing->routing_table);
 699     /* Delete index dict */
 700     xbt_dict_free(&(routing->to_index));
 701     /* Delete structure */
 702     xbt_free(rc);
 703   }
 704 }
 705
 706 /* Creation routing model functions */
 707
 708 static void* model_full_create(void) {
 709   routing_component_full_t new_component =  xbt_new0(s_routing_component_full_t,1);
 710   new_component->generic_routing.set_processing_units = generic_set_processing_units;
 711   new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
 712   new_component->generic_routing.set_route = generic_set_route;
 713   new_component->generic_routing.set_ASroute = generic_set_ASroute;
 714   new_component->generic_routing.get_route = full_get_route;
 715   new_component->generic_routing.finalize = full_finalize;
 716   new_component->to_index = xbt_dict_new();
 717   new_component->parse_routes = xbt_dict_new();
 718   return new_component;
 719 }
 720
 721 static void model_full_load(void) {
 722  /* use "surfxml_add_callback" to add a parse function call */
 723 }
 724
 725 static void model_full_unload(void) {
 726  /* use "surfxml_del_callback" to remove a parse function call */
 727 }
 728
 729 static void  model_full_end(void) {
 730
 731   char *key, *src_name, *dst_name;
 732   const char* sep = "#";
 733   int *src_id, *dst_id;
 734   unsigned int i, j;
 735   route_t route;
 736   route_extended_t e_route;
 737   void* data;
 738
 739   xbt_dict_cursor_t cursor = NULL;
 740   xbt_dynar_t keys = NULL;
 741
 742   /* set utils vars */
 743   routing_component_full_t routing = ((routing_component_full_t)current_routing);
 744   int table_size = xbt_dict_length(routing->to_index);
 745
 746   /* Create the routing table */
 747   routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
 748
 749   /* Put the routes in position */
 750   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 751
 752     // FIXME: there are a misstake, is nesesary to use a different way to save the src_name and dst_name.
 753     // or use a restricted char for separator (maybe space)
 754     keys = xbt_str_split_str(key, sep);
 755
 756     src_name = xbt_dynar_get_as(keys, 0, char*);
 757     dst_name = xbt_dynar_get_as(keys, 1, char*);
 758
 759     src_id = xbt_dict_get_or_null(routing->to_index, src_name);
 760     dst_id = xbt_dict_get_or_null(routing->to_index, dst_name);
 761
 762     if (src_id == NULL || dst_id == NULL )
 763       THROW2(mismatch_error,0,"Network elements %s or %s not found", src_name, dst_name);
 764
 765     TO_ROUTE_FULL(*src_id,*dst_id) = generic_new_extended_route(current_routing,data);
 766
 767      xbt_dynar_free(&keys);
 768    }
 769
 770    /* delete the parse table */
 771   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 772     route = (route_t)data;
 773     xbt_dynar_free(&(route->link_list));
 774     xbt_free(data);
 775   }
 776
 777   /* delete parse dict */
 778   xbt_dict_free(&(routing->parse_routes));
 779
 780   /* Add the loopback if needed */
 781   if(current_routing->hierarchy == SURF_ROUTING_BASE) {
 782     for (i = 0; i < table_size; i++) {
 783       e_route = TO_ROUTE_FULL(i, i);
 784       if(!e_route) { // && !xbt_dynar_length(e_route->generic_route.link_list)
 785         e_route = xbt_new0(s_route_extended_t,1);
 786         e_route->src_gateway = NULL;
 787         e_route->dst_gateway = NULL;
 788         e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 789         xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
 790         TO_ROUTE_FULL(i, i) = e_route;
 791       }
 792     }
 793   }
 794
 795   /* Shrink the dynar routes (save unused slots) */
 796   for (i=0;i<table_size;i++)
 797     for (j=0;j<table_size;j++)
 798       if(TO_ROUTE_FULL(i,j))
 799         xbt_dynar_shrink(TO_ROUTE_FULL(i,j)->generic_route.link_list,0);
 800 }
 801
 802 /* ************************************************************************** */
 803 /* *************************** FLOYD ROUTING ******************************** */
 804
 805 #define TO_FLOYD_COST(i,j) cost_table[(i)+(j)*table_size]
 806 #define TO_FLOYD_PRED(i,j) (routing->predecessor_table)[(i)+(j)*table_size]
 807 #define TO_FLOYD_LINK(i,j) (routing->link_table)[(i)+(j)*table_size]
 808
 809 /* Routing model structure */
 810
 811 typedef struct {
 812   s_routing_component_t generic_routing;
 813   /* vars for calculate the floyd algorith. */
 814   int *predecessor_table;
 815   route_extended_t *link_table; /* char* -> int* */
 816   xbt_dict_t to_index;
 817   /* store data during the parse process */
 818   xbt_dict_t parse_routes;
 819 } s_routing_component_floyd_t,*routing_component_floyd_t;
 820
 821 /* Business methods */
 822
 823 static route_extended_t floyd_get_route(routing_component_t rc, const char* src,const char* dst) {
 824
 825   xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
 826
 827   /* set utils vars */
 828   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
 829   int table_size = xbt_dict_length(routing->to_index);
 830
 831   route_extended_t new_e_route = xbt_new0(s_route_extended_t,1);
 832   new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 833   new_e_route->src_gateway = NULL;
 834   new_e_route->dst_gateway = NULL;
 835
 836   routing_component_t src_as, dst_as;
 837
 838   // TODO: MAKE A FUNCTION FOR GENERIC CHECK
 839   src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
 840   dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
 841
 842   xbt_assert3(src_as != NULL && dst_as  != NULL, "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",src,dst,rc->name);
 843   xbt_assert4(src_as == dst_as, "The src(%s in %s) and dst(%s in %s) are in differents AS",src,src_as->name,dst,dst_as->name);
 844   xbt_assert2(rc == dst_as, "The routing component of src and dst is not the same as the network elements belong (%s==%s)",rc->name,dst_as->name);
 845
 846   int *src_id = xbt_dict_get(routing->to_index,src);
 847   int *dst_id = xbt_dict_get(routing->to_index,dst);
 848   xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",src,dst);
 849
 850   int first = 1;
 851   int pred = *dst_id;
 852   int prev_pred = 0;
 853   char *gw_src,*gw_dst, *prev_gw_src,*prev_gw_dst, *first_gw;
 854   unsigned int cpt;
 855   void* link;
 856   xbt_dynar_t links;
 857   route_extended_t e_route_as_to_as;
 858   do {
 859     prev_pred = pred;
 860     pred = TO_FLOYD_PRED(*src_id, pred);
 861     if(pred == -1) // if no pred in route -> no route to host
 862       break;
 863     xbt_assert2(TO_FLOYD_LINK(pred,prev_pred),"Invalid link for the route between \"%s\" or \"%s\"", src, dst);
 864
 865     prev_gw_src = gw_src;
 866     prev_gw_dst = gw_dst;
 867
 868     route_extended_t e_route = TO_FLOYD_LINK(pred,prev_pred);
 869     gw_src = e_route->src_gateway;
 870     gw_dst = e_route->dst_gateway;
 871
 872     if(first) first_gw = gw_src;
 873
 874     if(rc->hierarchy == SURF_ROUTING_RECURSIVE && !first && strcmp(prev_gw_dst,gw_src)) {
 875
 876       routing_component_t src_as = xbt_dict_get_or_null(global_routing->where_network_elements,prev_gw_dst);
 877       routing_component_t dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,gw_src);
 878       xbt_assert2(src_as==dst_as,"bad routing, differents AS gateways in route \"%s\" to \"%s\"",src,dst);
 879       e_route_as_to_as = (*(src_as->get_route))(src_as,prev_gw_dst,gw_src);
 880       links = e_route_as_to_as->generic_route.link_list;
 881       xbt_dynar_foreach(links, cpt, link) {
 882         xbt_dynar_push(new_e_route->generic_route.link_list,&link);
 883       }
 884     }
 885
 886     links = e_route->generic_route.link_list;
 887     xbt_dynar_foreach(links, cpt, link) {
 888       xbt_dynar_push(new_e_route->generic_route.link_list,&link);
 889     }
 890     first=0;
 891
 892   } while(pred != *src_id);
 893   xbt_assert4(pred != -1, "no route from host %d to %d (\"%s\" to \"%s\")", *src_id, *dst_id,src,dst);
 894
 895   if(rc->hierarchy == SURF_ROUTING_RECURSIVE) {
 896     new_e_route->src_gateway = first_gw;
 897     new_e_route->dst_gateway = gw_dst;
 898   }
 899
 900   return new_e_route;
 901 }
 902
 903 static void floyd_finalize(routing_component_t rc) {
 904    routing_component_floyd_t routing = (routing_component_floyd_t)rc;
 905   int i,j,table_size;
 906   if (routing) {
 907     table_size = xbt_dict_length(routing->to_index);
 908     /* Delete link_table */
 909     for (i=0;i<table_size;i++) {
 910       for (j=0;j<table_size;j++) {
 911         route_extended_t e_route = TO_FLOYD_LINK(i,j);
 912         if(e_route) {
 913           xbt_dynar_free(&(e_route->generic_route.link_list));
 914           if(e_route->src_gateway) xbt_free(e_route->src_gateway);
 915           if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
 916           xbt_free(e_route);
 917         }
 918       }
 919     }
 920     xbt_free(routing->link_table);
 921     /* Delete index dict */
 922     xbt_dict_free(&(routing->to_index));
 923     /* Delete dictionary index dict, predecessor and links table */
 924     xbt_free(routing->predecessor_table);
 925     /* Delete structure */
 926     xbt_free(rc);
 927   }
 928 }
 929
 930 static void* model_floyd_create(void) {
 931   routing_component_floyd_t new_component = xbt_new0(s_routing_component_floyd_t,1);
 932   new_component->generic_routing.set_processing_units = generic_set_processing_units;
 933   new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
 934   new_component->generic_routing.set_route = generic_set_route;
 935   new_component->generic_routing.set_ASroute = generic_set_ASroute;
 936   new_component->generic_routing.get_route = floyd_get_route;
 937   new_component->generic_routing.finalize = floyd_finalize;
 938   new_component->to_index = xbt_dict_new();
 939   new_component->parse_routes = xbt_dict_new();
 940   return new_component;
 941 }
 942
 943 static void  model_floyd_load(void) {
 944  /* use "surfxml_add_callback" to add a parse function call */
 945 }
 946
 947 static void  model_floyd_unload(void) {
 948  /* use "surfxml_del_callback" to remove a parse function call */
 949 }
 950
 951 static void  model_floyd_end(void) {
 952
 953   routing_component_floyd_t routing = ((routing_component_floyd_t)current_routing);
 954   xbt_dict_cursor_t cursor = NULL;
 955   double * cost_table;
 956   char *key,*data, *src_name, *dst_name;
 957   const char *sep = "#";
 958   xbt_dynar_t keys;
 959   int *src_id, *dst_id;
 960   unsigned int i,j,a,b,c;
 961
 962   /* set the size of inicial table */
 963   int table_size = xbt_dict_length(routing->to_index);
 964
 965   /* Create Cost, Predecessor and Link tables */
 966   cost_table = xbt_new0(double, table_size*table_size); //link cost from host to host
 967   routing->predecessor_table = xbt_new0(int, table_size*table_size); //predecessor host numbers
 968   routing->link_table = xbt_new0(route_extended_t, table_size*table_size); //actual link between src and dst
 969
 970   /* Initialize costs and predecessors*/
 971   for(i = 0; i<table_size;i++)
 972     for(j = 0; j<table_size;j++) {
 973         TO_FLOYD_COST(i,j) = DBL_MAX;
 974         TO_FLOYD_PRED(i,j) = -1;
 975         TO_FLOYD_LINK(i,j) = NULL; // FIXED DAVID
 976     }
 977
 978    /* Put the routes in position */
 979   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 980
 981     // FIXME: there are a misstake, is nesesary to use a different way to save the src_name and dst_name.
 982     // or use a restricted char for separator (maybe space)
 983     keys = xbt_str_split_str(key, sep);
 984
 985     src_name = xbt_dynar_get_as(keys, 0, char*);
 986     dst_name = xbt_dynar_get_as(keys, 1, char*);
 987
 988     src_id = xbt_dict_get_or_null(routing->to_index, src_name);
 989     dst_id = xbt_dict_get_or_null(routing->to_index, dst_name);
 990
 991     if (src_id == NULL || dst_id == NULL )
 992       THROW2(mismatch_error,0,"Network elements %s or %s not found", src_name, dst_name);
 993
 994     TO_FLOYD_LINK(*src_id,*dst_id) = generic_new_extended_route(current_routing,data);
 995     TO_FLOYD_PRED(*src_id,*dst_id) = *src_id;
 996
 997     //link cost
 998     TO_FLOYD_COST(*src_id,*dst_id) = 1; // assume 1 for now // TODO DAVID REDO
 999
1000     xbt_dynar_free(&keys);
1001   }
1002
1003   /* Add the loopback if needed */
1004   if(current_routing->hierarchy == SURF_ROUTING_BASE) {
1005     for (i = 0; i < table_size; i++) {
1006       route_extended_t e_route = TO_FLOYD_LINK(i, i);
1007       if(!e_route) { // && !xbt_dynar_length(e_route->generic_route.link_list)
1008         e_route = xbt_new0(s_route_extended_t,1);
1009         e_route->src_gateway = NULL;
1010         e_route->dst_gateway = NULL;
1011         e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1012         xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
1013         TO_FLOYD_LINK(i,i) = e_route;
1014         TO_FLOYD_PRED(i,i) = i;
1015         TO_FLOYD_COST(i,i) = 1;
1016       }
1017     }
1018   }
1019   //Calculate path costs
1020   for(c=0;c<table_size;c++) {
1021     for(a=0;a<table_size;a++) {
1022       for(b=0;b<table_size;b++) {
1023         if(TO_FLOYD_COST(a,c) < DBL_MAX && TO_FLOYD_COST(c,b) < DBL_MAX) {
1024           if(TO_FLOYD_COST(a,b) == DBL_MAX ||
1025             (TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b) < TO_FLOYD_COST(a,b))) {
1026             TO_FLOYD_COST(a,b) = TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b);
1027             TO_FLOYD_PRED(a,b) = TO_FLOYD_PRED(c,b);
1028           }
1029         }
1030       }
1031     }
1032   }
1033
1034    /* delete the parse table */
1035   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1036     route_t route = (route_t)data;
1037     xbt_dynar_free(&(route->link_list));
1038     xbt_free(data);
1039   }
1040
1041   /* delete parse dict */
1042   xbt_dict_free(&(routing->parse_routes));
1043
1044   //cleanup
1045   xbt_free(cost_table);
1046 }
1047
1048 /* ************************************************************************** */
1049 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
1050
1051 typedef struct {
1052   s_routing_component_t generic_routing;
1053   xbt_dict_t  parse_routes;
1054   xbt_dict_t  to_index;
1055   xbt_graph_t route_graph;   /* xbt_graph */
1056   xbt_dict_t  graph_node_map; /* map */
1057   xbt_dict_t  route_cache;    /* use in cache mode */
1058   int cached;
1059 } s_routing_component_dijkstra_t,*routing_component_dijkstra_t;
1060
1061
1062 typedef struct graph_node_data {
1063   int id;
1064   int graph_id; //used for caching internal graph id's
1065 } s_graph_node_data_t, * graph_node_data_t;
1066
1067 typedef struct graph_node_map_element {
1068   xbt_node_t node;
1069 } s_graph_node_map_element_t, * graph_node_map_element_t;
1070
1071 typedef struct route_cache_element {
1072   int * pred_arr;
1073   int size;
1074 } s_route_cache_element_t, * route_cache_element_t;
1075
1076 /* Free functions */
1077
1078 static void route_cache_elem_free(void *e) {
1079   route_cache_element_t elm=(route_cache_element_t)e;
1080   if (elm) {
1081     xbt_free(elm->pred_arr);
1082     xbt_free(elm);
1083   }
1084 }
1085
1086 static void graph_node_map_elem_free(void *e) {
1087   graph_node_map_element_t elm = (graph_node_map_element_t)e;
1088   if(elm) {
1089     xbt_free(elm);
1090   }
1091 }
1092
1093 static void graph_edge_data_free(void *e) {
1094   route_extended_t e_route = (route_extended_t)e;
1095   if(e_route) {
1096     xbt_dynar_free(&(e_route->generic_route.link_list));
1097     if(e_route->src_gateway) xbt_free(e_route->src_gateway);
1098     if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
1099     xbt_free(e_route);
1100   }
1101 }
1102
1103 /* Utility functions */
1104
1105 static xbt_node_t route_graph_new_node(routing_component_dijkstra_t rc, int id, int graph_id) {
1106   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1107   xbt_node_t node = NULL;
1108   graph_node_data_t data = NULL;
1109   graph_node_map_element_t elm = NULL;
1110
1111   data = xbt_new0(struct graph_node_data, 1); // FIXED by david
1112   data->id = id;
1113   data->graph_id = graph_id;
1114   node = xbt_graph_new_node(routing->route_graph, data);
1115
1116   elm = xbt_new0(struct graph_node_map_element, 1); // FIXED by david
1117   elm->node = node;
1118   xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);
1119
1120   return node;
1121 }
1122
1123 static graph_node_map_element_t graph_node_map_search(routing_component_dijkstra_t rc, int id) {
1124   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1125   graph_node_map_element_t elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&id), sizeof(int));
1126   return elm;
1127 }
1128
1129 /* Parsing */
1130
1131 static void route_new_dijkstra(routing_component_dijkstra_t rc, int src_id, int dst_id, route_extended_t e_route        ) {
1132   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1133
1134   xbt_node_t src = NULL;
1135   xbt_node_t dst = NULL;
1136   graph_node_map_element_t src_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&src_id), sizeof(int));
1137   graph_node_map_element_t dst_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&dst_id), sizeof(int));
1138
1139   if(src_elm)
1140     src = src_elm->node;
1141
1142   if(dst_elm)
1143     dst = dst_elm->node;
1144
1145   //add nodes if they don't exist in the graph
1146   if(src_id == dst_id && src == NULL && dst == NULL) {
1147     src = route_graph_new_node(rc,src_id, -1);
1148     dst = src;
1149   } else {
1150     if(src == NULL) {
1151       src = route_graph_new_node(rc,src_id, -1);
1152     }
1153     if(dst == NULL) {
1154       dst = route_graph_new_node(rc,dst_id, -1);
1155     }
1156   }
1157
1158   //add link as edge to graph
1159   xbt_graph_new_edge(routing->route_graph, src, dst, e_route);
1160 }
1161
1162 static void add_loopback_dijkstra(routing_component_dijkstra_t rc) {
1163   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1164
1165   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1166
1167   xbt_node_t node = NULL;
1168   unsigned int cursor2;
1169   xbt_dynar_foreach(nodes, cursor2, node) {
1170     xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
1171     xbt_edge_t edge = NULL;
1172     unsigned int cursor;
1173
1174     int found = 0;
1175     xbt_dynar_foreach(out_edges, cursor, edge) {
1176       xbt_node_t other_node = xbt_graph_edge_get_target(edge);
1177       if(other_node == node) {
1178         found = 1;
1179         break;
1180       }
1181     }
1182
1183     if(!found) {
1184       route_extended_t e_route = xbt_new0(s_route_extended_t,1);
1185       e_route->src_gateway = NULL;
1186       e_route->dst_gateway = NULL;
1187       e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1188       xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
1189       xbt_graph_new_edge(routing->route_graph, node, node, e_route);
1190     }
1191   }
1192 }
1193
1194 /* Business methods */
1195
1196 static route_extended_t dijkstra_get_route(routing_component_t rc, const char* src,const char* dst) {
1197
1198   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1199
1200   xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
1201
1202   int * pred_arr = NULL;
1203   int src_node_id = 0;
1204   int dst_node_id = 0;
1205   int * nodeid = NULL;
1206   int v;
1207   routing_component_t src_as, dst_as;
1208   int *src_id,*dst_id;
1209   route_extended_t e_route;
1210   int size = 0;
1211   unsigned int cpt;
1212   void* link;
1213   xbt_dynar_t links = NULL;
1214   route_cache_element_t elm = NULL;
1215   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1216
1217   route_extended_t new_e_route = xbt_new0(s_route_extended_t,1);
1218   new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1219   new_e_route->src_gateway = NULL;
1220   new_e_route->dst_gateway = NULL;
1221
1222   // TODO: MAKE A FUNCTION FOR GENERIC CHECK
1223   src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
1224   dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
1225
1226   xbt_assert3(src_as != NULL && dst_as  != NULL, "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",src,dst,rc->name);
1227   xbt_assert4(src_as == dst_as, "The src(%s in %s) and dst(%s in %s) are in differents AS",src,src_as->name,dst,dst_as->name);
1228   xbt_assert2(rc == dst_as, "The routing component of src and dst is not the same as the network elements belong (%s==%s)",rc->name,dst_as->name);
1229
1230   src_id = xbt_dict_get_or_null(routing->to_index,src);
1231   dst_id = xbt_dict_get_or_null(routing->to_index,dst);
1232   xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",src,dst);
1233
1234   /*Use the graph_node id mapping set to quickly find the nodes */
1235   graph_node_map_element_t src_elm = graph_node_map_search(routing,*src_id);
1236   graph_node_map_element_t dst_elm = graph_node_map_search(routing,*dst_id);
1237   xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", *src_id, *dst_id);
1238   src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id;
1239   dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id;
1240
1241   /* if the src and dst are the same */ // FIXED by david
1242   if( src_node_id == dst_node_id ) {
1243
1244     xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
1245     xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
1246     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_s_v, node_e_v);
1247
1248     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id, *dst_id);
1249
1250     e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1251
1252     links = e_route->generic_route.link_list;
1253     xbt_dynar_foreach(links, cpt, link) {
1254       xbt_dynar_push(new_e_route->generic_route.link_list,&link);
1255     }
1256
1257     return new_e_route;
1258   }
1259
1260   if(routing->cached) {
1261     /*check if there is a cached predecessor list avail */
1262     elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int));
1263   }
1264
1265   if(elm) { //cached mode and cache hit
1266     pred_arr = elm->pred_arr;
1267   } else { //not cached mode or cache miss
1268     double * cost_arr = NULL;
1269     xbt_heap_t pqueue = NULL;
1270     int i = 0;
1271
1272     int nr_nodes = xbt_dynar_length(nodes);
1273     cost_arr = xbt_new0(double, nr_nodes); // link cost from src to other hosts
1274     pred_arr = xbt_new0(int, nr_nodes);    // predecessors in path from src
1275     pqueue = xbt_heap_new(nr_nodes, xbt_free);
1276
1277     //initialize
1278     cost_arr[src_node_id] = 0.0;
1279
1280     for(i = 0; i < nr_nodes; i++) {
1281       if(i != src_node_id) {
1282         cost_arr[i] = DBL_MAX;
1283       }
1284
1285       pred_arr[i] = 0;
1286
1287       //initialize priority queue
1288       nodeid = xbt_new0(int, 1);
1289       *nodeid = i;
1290       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
1291
1292     }
1293
1294     // apply dijkstra using the indexes from the graph's node array
1295     while(xbt_heap_size(pqueue) > 0) {
1296       int * v_id = xbt_heap_pop(pqueue);
1297       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
1298       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
1299       xbt_edge_t edge = NULL;
1300       unsigned int cursor;
1301
1302       xbt_dynar_foreach(out_edges, cursor, edge) {
1303         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
1304         graph_node_data_t data = xbt_graph_node_get_data(u_node);
1305         int u_id = data->graph_id;
1306         int cost_v_u = 1; //fixed link cost for now // TODO DAVID REDO
1307
1308         if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
1309           pred_arr[u_id] = *v_id;
1310           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
1311           nodeid = xbt_new0(int, 1);
1312           *nodeid = u_id;
1313           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
1314         }
1315       }
1316
1317       //free item popped from pqueue
1318       xbt_free(v_id);
1319     }
1320
1321     xbt_free(cost_arr);
1322     xbt_heap_free(pqueue);
1323
1324   }
1325
1326   //compose route path with links
1327   for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
1328     xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
1329     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
1330     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
1331
1332     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id, *dst_id);
1333
1334     e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1335
1336     if(v==dst_node_id)
1337       new_e_route->src_gateway=e_route->src_gateway;
1338     new_e_route->dst_gateway=e_route->dst_gateway;
1339
1340     links = e_route->generic_route.link_list;
1341     xbt_dynar_foreach(links, cpt, link) {
1342       xbt_dynar_push(new_e_route->generic_route.link_list,&link);
1343     }
1344     size++;
1345   }
1346
1347   if(routing->cached && elm == NULL) {
1348     //add to predecessor list of the current src-host to cache
1349     elm = xbt_new0(struct route_cache_element, 1); // FIXED by david
1350     elm->pred_arr = pred_arr;
1351     elm->size = size;
1352     xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free);
1353   }
1354
1355   if(!routing->cached)
1356     xbt_free(pred_arr);
1357
1358   return new_e_route;
1359 }
1360
1361 static void dijkstra_finalize(routing_component_t rc) {
1362   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1363
1364   if (routing) {
1365     xbt_graph_free_graph(routing->route_graph, &xbt_free, &graph_edge_data_free, &xbt_free);
1366     xbt_dict_free(&routing->graph_node_map);
1367     if(routing->cached)
1368       xbt_dict_free(&routing->route_cache);
1369     xbt_dict_free(&routing->to_index);
1370     xbt_free(routing);
1371   }
1372 }
1373
1374 /* Creation routing model functions */
1375
1376 static void* model_dijkstra_both_create(int cached) {
1377   routing_component_dijkstra_t new_component = xbt_new0(s_routing_component_dijkstra_t,1);
1378   new_component->generic_routing.set_processing_units = generic_set_processing_units;
1379   new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
1380   new_component->generic_routing.set_route = generic_set_route;
1381   new_component->generic_routing.set_ASroute = generic_set_ASroute;
1382   new_component->generic_routing.get_route = dijkstra_get_route;
1383   new_component->generic_routing.finalize = dijkstra_finalize;
1384   new_component->cached = cached;
1385   new_component->to_index = xbt_dict_new();
1386   new_component->parse_routes = xbt_dict_new();
1387   return new_component;
1388 }
1389
1390 static void* model_dijkstra_create(void) {
1391   return model_dijkstra_both_create(0);
1392 }
1393
1394 static void* model_dijkstracache_create(void) {
1395   return model_dijkstra_both_create(1);
1396 }
1397
1398 static void  model_dijkstra_both_load(void) {
1399  /* use "surfxml_add_callback" to add a parse function call */
1400 }
1401
1402 static void  model_dijkstra_both_unload(void) {
1403  /* use "surfxml_del_callback" to remove a parse function call */
1404 }
1405
1406 static void  model_dijkstra_both_end(void) {
1407   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) current_routing;
1408    xbt_dict_cursor_t cursor = NULL;
1409    char *key, *data;
1410    const char *sep = "#";
1411    xbt_dynar_t keys;
1412   xbt_node_t node = NULL;
1413   unsigned int cursor2;
1414   xbt_dynar_t nodes = NULL;
1415   char *src_name, *dst_name;
1416   int *src_id, *dst_id;
1417   route_t route;
1418
1419   /* Create the topology graph */
1420   routing->route_graph = xbt_graph_new_graph(1, NULL);
1421   routing->graph_node_map = xbt_dict_new();
1422
1423   if(routing->cached)
1424     routing->route_cache = xbt_dict_new();
1425
1426   /* Put the routes in position */
1427   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1428
1429     // FIXME: there are a misstake, is nesesary to use a different way to save the src_name and dst_name.
1430     // or use a restricted char for separator (maybe space)
1431     keys = xbt_str_split_str(key, sep);
1432
1433     src_name = xbt_dynar_get_as(keys, 0, char*);
1434     dst_name = xbt_dynar_get_as(keys, 1, char*);
1435
1436     src_id = xbt_dict_get_or_null(routing->to_index, src_name);
1437     dst_id = xbt_dict_get_or_null(routing->to_index, dst_name);
1438
1439     if (src_id == NULL || dst_id == NULL )
1440       THROW2(mismatch_error,0,"Network elements %s or %s not found", src_name, dst_name);
1441
1442     route_extended_t e_route = generic_new_extended_route(current_routing,data);
1443
1444     route_new_dijkstra(routing,*src_id,*dst_id,e_route);
1445
1446     xbt_dynar_free(&keys);
1447   }
1448
1449   /* delete the parse table */
1450   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1451     route = (route_t)data;
1452     xbt_dynar_free(&(route->link_list));
1453     xbt_free(data);
1454   }
1455
1456   /* delete parse dict */
1457   xbt_dict_free(&(routing->parse_routes));
1458
1459   /* Add the loopback if needed */
1460   if(current_routing->hierarchy == SURF_ROUTING_BASE)
1461     add_loopback_dijkstra(routing);
1462
1463   /* initialize graph indexes in nodes after graph has been built */
1464   nodes = xbt_graph_get_nodes(routing->route_graph);
1465
1466   xbt_dynar_foreach(nodes, cursor2, node) {
1467     graph_node_data_t data = xbt_graph_node_get_data(node);
1468     data->graph_id = cursor2;
1469   }
1470
1471 }
1472
1473
1474 /* ************************************************************************** */
1475 /* ******************************* NO ROUTING ******************************* */
1476
1477 /* Routing model structure */
1478 typedef struct {
1479   s_routing_component_t generic_routing;
1480 } s_routing_component_none_t,*routing_component_none_t;
1481
1482 /* Business methods */
1483 static route_extended_t none_get_route(routing_component_t rc, const char* src,const char* dst){
1484   return NULL;
1485 }
1486 static void none_finalize(routing_component_t rc) {
1487   xbt_free(rc);
1488 }
1489
1490 /* Creation routing model functions */
1491 static void* model_none_create(void) {
1492   routing_component_none_t new_component =  xbt_new0(s_routing_component_none_t,1);
1493   new_component->generic_routing.set_processing_units = NULL;
1494   new_component->generic_routing.set_autonomous_system = NULL;
1495   new_component->generic_routing.set_route = NULL;
1496   new_component->generic_routing.set_ASroute = NULL;
1497   new_component->generic_routing.get_route = none_get_route;
1498   new_component->generic_routing.finalize = none_finalize;
1499   return new_component;
1500 }
1501
1502 static void  model_none_load(void) {}
1503 static void  model_none_unload(void) {}
1504 static void  model_none_end(void) {}
1505
1506 // /* ************************************************** */
1507 // /* ********** PATERN FOR NEW ROUTING **************** */
1508 //
1509 // /* The minimal configuration of a new routing model need the next functions,
1510 //  * also you need to set at the start of the file, the new model in the model
1511 //  * list. Remember keep the null ending of the list.
1512 //  */
1513 // /* Routing model structure */
1514 // typedef struct {
1515 //   s_routing_component_t generic_routing;
1516 //   /* things that your routing model need */
1517 // } s_routing_component_NEW_t,*routing_component_NEW_t;
1518 //
1519 // /* Parse routing model functions */
1520 // static void NEW_parse_S_host(void) {} /* example*/
1521 //
1522 // /* Business methods */
1523 // static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {return NULL;} /* mandatory */
1524 // static void NEW_finalize(routing_component_t rc) {} /* mandatory */
1525 //
1526 // /* Creation routing model functions */
1527 // static void* model_NEW_create(void) {return NULL;} /* mandatory */
1528 // static void  model_NEW_load(void) {}   /* mandatory */
1529 // static void  model_NEW_unload(void) {} /* mandatory */
1530 // static void  model_NEW_end(void) {}    /* mandatory */
1531
1532 /* ************************************************************************** */
1533 /* ************************* GENERIC PARSE FUNCTIONS ************************ */
1534
1535 static void generic_set_processing_units(routing_component_t rc, const char* name) {
1536   DEBUG1("Full - Load process unit \"%s\"",name);
1537   model_type_t modeltype = rc->routing;
1538   int *id = xbt_new0(int,1); // xbt_malloc(sizeof(int)); ?
1539   xbt_dict_t index;
1540   if(modeltype==&routing_models[SURF_MODEL_FULL])
1541     index = ((routing_component_full_t)current_routing)->to_index;
1542   else if(modeltype==&routing_models[SURF_MODEL_FLOYD])
1543     index = ((routing_component_floyd_t)current_routing)->to_index;
1544   else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1545           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE])
1546     index = ((routing_component_dijkstra_t)current_routing)->to_index;
1547   else xbt_die("\"generic_set_processing_units\" not support");
1548   *id = xbt_dict_length(index);
1549   xbt_dict_set(index,name,id,xbt_free);
1550 }
1551
1552 static void generic_set_autonomous_system(routing_component_t rc, const char* name) {
1553   DEBUG1("Full - Load Autonomous system \"%s\"",name);
1554   model_type_t modeltype = rc->routing;
1555   int *id = xbt_new0(int,1); // xbt_malloc(sizeof(int)); ?
1556   xbt_dict_t index;
1557   if(modeltype==&routing_models[SURF_MODEL_FULL])
1558     index = ((routing_component_full_t)current_routing)->to_index;
1559   else if(modeltype==&routing_models[SURF_MODEL_FLOYD])
1560     index = ((routing_component_floyd_t)current_routing)->to_index;
1561   else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1562           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE])
1563     index = ((routing_component_dijkstra_t)current_routing)->to_index;
1564   else xbt_die("\"generic_set_autonomous_system\" not support");
1565   *id = xbt_dict_length(index);
1566   xbt_dict_set(index,name,id,xbt_free);
1567 }
1568
1569 static void generic_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {
1570   DEBUG2("Full - Load Route from \"%s\" to \"%s\"",src,dst);
1571   model_type_t modeltype = rc->routing;
1572   xbt_dict_t parseroutes;
1573   if(modeltype==&routing_models[SURF_MODEL_FULL])
1574     parseroutes = ((routing_component_full_t)current_routing)->parse_routes;
1575   else if(modeltype==&routing_models[SURF_MODEL_FLOYD])
1576     parseroutes = ((routing_component_floyd_t)current_routing)->parse_routes;
1577   else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1578           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE])
1579     parseroutes = ((routing_component_dijkstra_t)current_routing)->parse_routes;
1580   else xbt_die("\"generic_set_autonomous_system\" not support");
1581   char *route_name;
1582   route_name = bprintf("%s#%s",src,dst);
1583   xbt_assert2(xbt_dynar_length(link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
1584   xbt_assert2(!xbt_dict_get_or_null(parseroutes,route_name),
1585     "The route between \"%s\" and \"%s\" already exist",src,dst);
1586   xbt_dict_set(parseroutes, route_name, route, NULL);
1587   xbt_free(route_name);
1588 }
1589
1590 static void generic_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {
1591   DEBUG4("Full - Load ASroute from \"%s(%s)\" to \"%s(%s)\"",src,e_route->src_gateway,dst,e_route->dst_gateway);
1592   model_type_t modeltype = rc->routing;
1593   xbt_dict_t parseroutes;
1594   if(modeltype==&routing_models[SURF_MODEL_FULL])
1595     parseroutes = ((routing_component_full_t)current_routing)->parse_routes;
1596   else if(modeltype==&routing_models[SURF_MODEL_FLOYD])
1597     parseroutes = ((routing_component_floyd_t)current_routing)->parse_routes;
1598   else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1599           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE])
1600     parseroutes = ((routing_component_dijkstra_t)current_routing)->parse_routes;
1601   else xbt_die("\"generic_set_autonomous_system\" not support");
1602   char *route_name;
1603   route_name = bprintf("%s#%s",src,dst);
1604   xbt_assert2(xbt_dynar_length(link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
1605   xbt_assert4(!xbt_dict_get_or_null(parseroutes,route_name),
1606     "The route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exist",src,e_route->src_gateway,dst,e_route->dst_gateway);
1607   xbt_dict_set(parseroutes, route_name, e_route, NULL);
1608   xbt_free(route_name);
1609 }
1610
1611 /* ************************************************************************** */
1612 /* ************************* GENERIC AUX FUNCTIONS ************************** */
1613
1614 static route_extended_t generic_new_extended_route(routing_component_t rc, void* data) {
1615
1616   char *link_name;
1617   route_extended_t e_route, new_e_route;
1618   route_t route;
1619   unsigned int cpt;
1620   xbt_dynar_t links, links_id;
1621
1622   new_e_route = xbt_new0(s_route_extended_t,1);
1623   new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1624   new_e_route->src_gateway = NULL;
1625   new_e_route->dst_gateway = NULL;
1626
1627   xbt_assert0(rc->hierarchy == SURF_ROUTING_BASE || rc->hierarchy == SURF_ROUTING_RECURSIVE,
1628       "the hierarchy type is not defined");
1629
1630   if(rc->hierarchy == SURF_ROUTING_BASE ) {
1631
1632     route = (route_t)data;
1633     links = route->link_list;
1634
1635   } else if(rc->hierarchy == SURF_ROUTING_RECURSIVE ) {
1636
1637     e_route = (route_extended_t)data;
1638
1639     // FIXME: HERE CHECK THE GATEWAY!!!!!!!!!
1640     xbt_assert0(e_route->src_gateway&&e_route->dst_gateway,"bad gateway, is null");
1641
1642     links = e_route->generic_route.link_list;
1643
1644     /* remeber not erase the gateway names */
1645     new_e_route->src_gateway = e_route->src_gateway;
1646     new_e_route->dst_gateway = e_route->dst_gateway;
1647   }
1648
1649   links_id = new_e_route->generic_route.link_list;
1650
1651   xbt_dynar_foreach(links, cpt, link_name) {
1652
1653     void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1654     if (link)
1655       xbt_dynar_push(links_id,&link);
1656     else
1657       THROW1(mismatch_error,0,"Link %s not found", link_name);
1658   }
1659
1660   return new_e_route;
1661 }
1662
1663 ////////////////////////////////////////////////////////////////////////////////
1664 // HERE FINISH THE NEW CODE
1665 ////////////////////////////////////////////////////////////////////////////////
1666
1667 //...... DEBUG ONLY .... //
1668 static void print_tree(routing_component_t rc) {
1669   printf("(%s %s)\n",rc->name,rc->routing->name);
1670   printf("  ");
1671   xbt_dict_cursor_t cursor = NULL;
1672   char *key;
1673   int *val;
1674   if( rc->routing == &(routing_models[SURF_MODEL_FULL]) )
1675   { xbt_dict_foreach(((routing_component_full_t)rc)->to_index, cursor, key, val) { printf("<%s-%d> ",key,*val); } }
1676   else if( rc->routing == &(routing_models[SURF_MODEL_FLOYD]) )
1677   { xbt_dict_foreach(((routing_component_floyd_t)rc)->to_index, cursor, key, val) { printf("<%s-%d> ",key,*val); }
1678   }
1679   else
1680       xbt_assert0(0, "Invalid model for call \"print_tree\"");
1681   printf("\n");
1682   routing_component_t elem;
1683   xbt_dict_foreach(rc->routing_sons, cursor, key, elem) {
1684     printf("<--\n");
1685     print_tree(elem);
1686     printf("-->\n");
1687   }
1688 }
1689
1690 //...... DEBUG ONLY .... //
1691 static void print_global() {
1692   xbt_dict_cursor_t cursor = NULL;
1693   char *key;
1694   routing_component_t elem;
1695   xbt_dict_foreach(global_routing->where_network_elements, cursor, key, elem) { printf("<%s>\n",key); }
1696 }
1697
1698 //...... DEBUG ONLY .... //
1699 static void print_AS_start(void) { printf("AS!!! %s y se rutea \"%s\"\n",A_surfxml_AS_id,A_surfxml_AS_routing); }
1700 static void print_AS_end(void)   { printf("AS!!! %s\n",A_surfxml_AS_id); }
1701 static void print_host(void)     { printf("host!!! %s\n",A_surfxml_host_id); }
1702 static void print_link(void)     { printf("link!!! %s\n",A_surfxml_link_id); }
1703 static void print_route(void)    { printf("route!!! %s a %s\n",A_surfxml_route_src,A_surfxml_route_dst); }
1704 static void print_ctn(void)      { printf("ctn!!! %s\n",A_surfxml_link_c_ctn_id); }
1705
1706 //...... DEBUG ONLY .... //
1707 static void DEBUG_exit(void) {
1708
1709 //   printf("-------- print tree elements -----\n");
1710 //   print_tree(global_routing->root);
1711 //   printf("----------------------------------\n\n");
1712 //
1713 //   printf("-------- network_elements --------\n");
1714 //   print_global();
1715 //   printf("----------------------------------\n\n");
1716
1717 //   const char* names[] = { "11.A","11.B","11.C","121.A","121.B","122.A","13.A","13.B"};
1718 //   int i,j,total = 8;
1719
1720 //   printf("-- print all the example routes --\n");
1721 //   const char* names[] = { "11.A","11.B","11.C"};
1722 //   int i,j,total = 3;
1723
1724 //   const char* names[] = { "141.A","141.B","143.A","143.B"};
1725 //   int i,j,total = 4;
1726
1727 //   const char* names[] = { "15.A","15.B","15.C" };
1728 //   int i,j,total = 3;
1729
1730 //   const char* names[] = { "142.A","142.B","142.C", "11.A","11.B","11.C","141.A","141.B","143.A","143.B","11.A","11.B","11.C","121.A","121.B","122.A","13.A","13.B"};
1731 //   int i,j,total = 3+4+8+3;
1732
1733 //   const char* names[] = { "142.A","142.B","142.C" };
1734 //   int i,j,total = 3;
1735
1736    const char* names[] = { "11.A","11.B","11.C",
1737                            "121.A","121.B",
1738                            "122.A",
1739                            "13.A","13.B",
1740                            "141.A","141.B",
1741                            "142.A","142.B","142.C",
1742                            "143.A","143.B",
1743                            "15.A","15.B","15.C"};
1744    unsigned int i,j,total = 3+2+1+2+2+3+2+3;
1745
1746   printf("-- print all the example routes --\n");
1747   xbt_dynar_t links;
1748   void* link;
1749   for(i=0;i<total;i++) {
1750     for(j=0;j<total;j++) {
1751       printf("route from %s to %s >>> ",names[i],names[j]);
1752       links = (*(global_routing->get_route))(names[i],names[j]);
1753       unsigned int cpt=0;
1754       xbt_dynar_foreach(links, cpt, link) {
1755         s_surf_resource_t* generic_resource = link;
1756         printf(" %s",generic_resource->name);
1757       }
1758       printf("\n");
1759     }
1760   }
1761
1762   printf("----------------------------------\n\n");
1763
1764   printf("---------- call finalize ---------\n");
1765   (*(global_routing->finalize))();
1766   printf("----------------------------------\n");
1767
1768   exit(0);
1769 }
1770
1771 ////////////////////////////////////////////////////////////////////////////////
1772 // HERE END THE NEW CODE
1773 ////////////////////////////////////////////////////////////////////////////////
1774
1775 // /* ************************************************************************** */
1776 // /* *************************** FULL ROUTING ********************************* */
1777 // typedef struct {
1778 //   s_routing_t generic_routing;
1779 //   xbt_dynar_t *routing_table;
1780 //   void *loopback;
1781 //   size_t size_of_link;
1782 // } s_routing_full_t,*routing_full_t;
1783 //
1784 // #define ROUTE_FULL(i,j) ((routing_full_t)used_routing)->routing_table[(i)+(j)*(used_routing)->host_count]
1785 // #define HOST2ROUTER(id) ((id)+(2<<29))
1786 // #define ROUTER2HOST(id) ((id)-(2>>29))
1787 // #define ISROUTER(id) ((id)>=(2<<29))
1788 //
1789 // /*
1790 //  * Free the onelink routes
1791 //  */
1792 // static void onelink_route_elem_free(void *e) {
1793 //   s_onelink_t tmp = (s_onelink_t)e;
1794 //   if(tmp) {
1795 //     free(tmp);
1796 //   }
1797 // }
1798 //
1799 // /*
1800 //  * Parsing
1801 //  */
1802 // static void routing_full_parse_Shost(void) {
1803 //   int *val = xbt_malloc(sizeof(int));
1804 //   DEBUG2("Seen host %s (#%d)",A_surfxml_host_id,used_routing->host_count);
1805 //   *val = used_routing->host_count++;
1806 //   xbt_dict_set(used_routing->host_id,A_surfxml_host_id,val,xbt_free);
1807 // #ifdef HAVE_TRACING
1808 //   TRACE_surf_host_define_id (A_surfxml_host_id, *val);
1809 // #endif
1810 // }
1811 //
1812 // static void routing_full_parse_Srouter(void) {
1813 //      int *val = xbt_malloc(sizeof(int));
1814 //   DEBUG3("Seen router %s (%d -> #%d)",A_surfxml_router_id,used_routing->router_count,
1815 //              HOST2ROUTER(used_routing->router_count));
1816 //   *val = HOST2ROUTER(used_routing->router_count++);
1817 //   xbt_dict_set(used_routing->host_id,A_surfxml_router_id,val,xbt_free);
1818 // #ifdef HAVE_TRACING
1819 //   TRACE_surf_host_define_id (A_surfxml_host_id, *val);
1820 //   TRACE_surf_host_declaration (A_surfxml_host_id, 0);
1821 // #endif
1822 // }
1823 //
1824 // static int src_id = -1;
1825 // static int dst_id = -1;
1826 // static void routing_full_parse_Sroute_set_endpoints(void)
1827 // {
1828 //   src_id = *(int*)xbt_dict_get(used_routing->host_id,A_surfxml_route_src);
1829 //   dst_id = *(int*)xbt_dict_get(used_routing->host_id,A_surfxml_route_dst);
1830 //   DEBUG4("Route %s %d -> %s %d",A_surfxml_route_src,src_id,A_surfxml_route_dst,dst_id);
1831 //   route_action = A_surfxml_route_action;
1832 // }
1833 //
1834 // static void routing_full_parse_Eroute(void)
1835 // {
1836 //   char *name;
1837 //   if (src_id != -1 && dst_id != -1) {
1838 //     name = bprintf("%x#%x", src_id, dst_id);
1839 //     manage_route(route_table, name, route_action, 0);
1840 //     free(name);
1841 //   }
1842 // }
1843 //
1844 // /* Cluster tag functions */
1845 //
1846 // static void routing_full_parse_change_cpu_data(const char *hostName,
1847 //                                   const char *surfxml_host_power,
1848 //                                   const char *surfxml_host_availability,
1849 //                                   const char *surfxml_host_availability_file,
1850 //                                   const char *surfxml_host_state_file)
1851 // {
1852 //   int AX_ptr = 0;
1853 //
1854 //   SURFXML_BUFFER_SET(host_id, hostName);
1855 //   SURFXML_BUFFER_SET(host_power, surfxml_host_power /*hostPower */ );
1856 //   SURFXML_BUFFER_SET(host_availability, surfxml_host_availability);
1857 //   SURFXML_BUFFER_SET(host_availability_file, surfxml_host_availability_file);
1858 //   SURFXML_BUFFER_SET(host_state_file, surfxml_host_state_file);
1859 // }
1860 //
1861 // static void routing_full_parse_change_link_data(const char *linkName,
1862 //                                    const char *surfxml_link_bandwidth,
1863 //                                    const char *surfxml_link_bandwidth_file,
1864 //                                    const char *surfxml_link_latency,
1865 //                                    const char *surfxml_link_latency_file,
1866 //                                    const char *surfxml_link_state_file)
1867 // {
1868 //   int AX_ptr = 0;
1869 //
1870 //   SURFXML_BUFFER_SET(link_id, linkName);
1871 //   SURFXML_BUFFER_SET(link_bandwidth, surfxml_link_bandwidth);
1872 //   SURFXML_BUFFER_SET(link_bandwidth_file, surfxml_link_bandwidth_file);
1873 //   SURFXML_BUFFER_SET(link_latency, surfxml_link_latency);
1874 //   SURFXML_BUFFER_SET(link_latency_file, surfxml_link_latency_file);
1875 //   SURFXML_BUFFER_SET(link_state_file, surfxml_link_state_file);
1876 // }
1877 //
1878 // static void routing_full_parse_Scluster(void)
1879 // {
1880 //   static int AX_ptr = 0;
1881 //
1882 //   char *cluster_id = A_surfxml_cluster_id;
1883 //   char *cluster_prefix = A_surfxml_cluster_prefix;
1884 //   char *cluster_suffix = A_surfxml_cluster_suffix;
1885 //   char *cluster_radical = A_surfxml_cluster_radical;
1886 //   char *cluster_power = A_surfxml_cluster_power;
1887 //   char *cluster_bw = A_surfxml_cluster_bw;
1888 //   char *cluster_lat = A_surfxml_cluster_lat;
1889 //   char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
1890 //   char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
1891 //   char *backbone_name;
1892 //   unsigned int it1,it2;
1893 //   char *name1,*name2;
1894 //   xbt_dynar_t names = NULL;
1895 //   surfxml_bufferstack_push(1);
1896 //
1897 //   /* Make set a set to parse the prefix/suffix/radical into a neat list of names */
1898 //   DEBUG4("Make <set id='%s' prefix='%s' suffix='%s' radical='%s'>",
1899 //       cluster_id,cluster_prefix,cluster_suffix,cluster_radical);
1900 //   SURFXML_BUFFER_SET(set_id, cluster_id);
1901 //   SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
1902 //   SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
1903 //   SURFXML_BUFFER_SET(set_radical, cluster_radical);
1904 //
1905 //   SURFXML_START_TAG(set);
1906 //   SURFXML_END_TAG(set);
1907 //
1908 //   names = xbt_dict_get(set_list,cluster_id);
1909 //
1910 //   xbt_dynar_foreach(names,it1,name1) {
1911 //     /* create the host */
1912 //     routing_full_parse_change_cpu_data(name1, cluster_power, "1.0", "", "");
1913 //     A_surfxml_host_state = A_surfxml_host_state_ON;
1914 //
1915 //     SURFXML_START_TAG(host);
1916 //     SURFXML_END_TAG(host);
1917 //
1918 //     /* Here comes the link */
1919 //     routing_full_parse_change_link_data(name1, cluster_bw, "", cluster_lat, "", "");
1920 //     A_surfxml_link_state = A_surfxml_link_state_ON;
1921 //     A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
1922 //
1923 //     SURFXML_START_TAG(link);
1924 //     SURFXML_END_TAG(link);
1925 //   }
1926 //
1927 //   /* Make backbone link */
1928 //   backbone_name = bprintf("%s_bb", cluster_id);
1929 //   routing_full_parse_change_link_data(backbone_name, cluster_bb_bw, "", cluster_bb_lat, "",
1930 //                          "");
1931 //   A_surfxml_link_state = A_surfxml_link_state_ON;
1932 //   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_FATPIPE;
1933 //
1934 //   SURFXML_START_TAG(link);
1935 //   SURFXML_END_TAG(link);
1936 //
1937 //   /* And now the internal routes */
1938 //   xbt_dynar_foreach(names,it1,name1) {
1939 //     xbt_dynar_foreach(names,it2,name2) {
1940 //       if (strcmp(name1,name2)) {
1941 //         A_surfxml_route_action = A_surfxml_route_action_POSTPEND;
1942 //         SURFXML_BUFFER_SET(route_src,name1);
1943 //         SURFXML_BUFFER_SET(route_dst,name2);
1944 //         SURFXML_START_TAG(route); {
1945 //           /* FIXME: name1 link is added by error about 20 lines below, so don't add it here
1946 //           SURFXML_BUFFER_SET(link_c_ctn_id, name1);
1947 //           SURFXML_START_TAG(link_c_ctn);
1948 //           SURFXML_END_TAG(link_c_ctn);
1949 //            */
1950 //           SURFXML_BUFFER_SET(link_c_ctn_id, backbone_name);
1951 //           SURFXML_START_TAG(link_c_ctn);
1952 //           SURFXML_END_TAG(link_c_ctn);
1953 //
1954 //           SURFXML_BUFFER_SET(link_c_ctn_id, name2);
1955 //           SURFXML_START_TAG(link_c_ctn);
1956 //           SURFXML_END_TAG(link_c_ctn);
1957 //
1958 //         } SURFXML_END_TAG(route);
1959 //       }
1960 //     }
1961 //   }
1962 //
1963 //   /* Make route multi with the outside world, i.e. cluster->$* */
1964 //
1965 //   /* FIXME
1966 //    * This also adds an elements to the routes within the cluster,
1967 //    * and I guess it's wrong, but since this element is commented out in the above
1968 //    * code creating the internal routes, we're good.
1969 //    * To fix it, I'd say that we need a way to understand "$*-${cluster_id}" as "whole world, but the guys in that cluster"
1970 //    * But for that, we need to install a real expression parser for src/dst attributes
1971 //    *
1972 //    * FIXME
1973 //    * This also adds a dumb element (the private link) in place of the loopback. Then, since
1974 //    * the loopback is added only if no link to self already exist, this fails.
1975 //    * That's really dumb.
1976 //    *
1977 //    * FIXME
1978 //    * It seems to me that it does not add the backbone to the path to outside world...
1979 //    */
1980 //   SURFXML_BUFFER_SET(route_c_multi_src, cluster_id);
1981 //   SURFXML_BUFFER_SET(route_c_multi_dst, "$*");
1982 //   A_surfxml_route_c_multi_symmetric = A_surfxml_route_c_multi_symmetric_NO;
1983 //   A_surfxml_route_c_multi_action = A_surfxml_route_c_multi_action_PREPEND;
1984 //
1985 //   SURFXML_START_TAG(route_c_multi);
1986 //
1987 //   SURFXML_BUFFER_SET(link_c_ctn_id, "$src");
1988 //
1989 //   SURFXML_START_TAG(link_c_ctn);
1990 //   SURFXML_END_TAG(link_c_ctn);
1991 //
1992 //   SURFXML_END_TAG(route_c_multi);
1993 //
1994 //   free(backbone_name);
1995 //
1996 //   /* Restore buff */
1997 //   surfxml_bufferstack_pop(1);
1998 // }
1999 //
2000 //
2001 // static void routing_full_parse_end(void) {
2002 //   routing_full_t routing = (routing_full_t) used_routing;
2003 //   int nb_link = 0;
2004 //   unsigned int cpt = 0;
2005 //   xbt_dict_cursor_t cursor = NULL;
2006 //   char *key, *data, *end;
2007 //   const char *sep = "#";
2008 //   xbt_dynar_t links, keys;
2009 //   char *link_name = NULL;
2010 //   int i,j;
2011 //
2012 //   int host_count = routing->generic_routing.host_count;
2013 //
2014 //   /* Create the routing table */
2015 //   routing->routing_table = xbt_new0(xbt_dynar_t, host_count * host_count);
2016 //   for (i=0;i<host_count;i++)
2017 //     for (j=0;j<host_count;j++)
2018 //       ROUTE_FULL(i,j) = xbt_dynar_new(routing->size_of_link,NULL);
2019 //
2020 //   /* Put the routes in position */
2021 //   xbt_dict_foreach(route_table, cursor, key, data) {
2022 //     nb_link = 0;
2023 //     links = (xbt_dynar_t) data;
2024 //     keys = xbt_str_split_str(key, sep);
2025 //
2026 //     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
2027 //     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
2028 //     xbt_dynar_free(&keys);
2029 //
2030 //     if(xbt_dynar_length(links) == 1){
2031 //       s_onelink_t new_link = (s_onelink_t) xbt_malloc0(sizeof(s_onelink));
2032 //       new_link->src_id = src_id;
2033 //       new_link->dst_id = dst_id;
2034 //       link_name = xbt_dynar_getfirst_as(links, char*);
2035 //       new_link->link_ptr = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
2036 //       DEBUG3("Adding onelink route from (#%d) to (#%d), link_name %s",src_id, dst_id, link_name);
2037 //       xbt_dict_set(onelink_routes, link_name, (void *)new_link, onelink_route_elem_free);
2038 // #ifdef HAVE_TRACING
2039 //       TRACE_surf_link_save_endpoints (link_name, src_id, dst_id);
2040 // #endif
2041 //     }
2042 //
2043 //     if(ISROUTER(src_id) || ISROUTER(dst_id)) {
2044 //                              DEBUG2("There is route with a router here: (%d ,%d)",src_id,dst_id);
2045 //                              /* Check there is only one link in the route and store the information */
2046 //                              continue;
2047 //     }
2048 //
2049 //     DEBUG4("Handle %d %d (from %d hosts): %ld links",
2050 //         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
2051 //     xbt_dynar_foreach(links, cpt, link_name) {
2052 //       void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
2053 //       if (link)
2054 //         xbt_dynar_push(ROUTE_FULL(src_id,dst_id),&link);
2055 //       else
2056 //         THROW1(mismatch_error,0,"Link %s not found", link_name);
2057 //     }
2058 //   }
2059 //
2060 //   /* Add the loopback if needed */
2061 //   for (i = 0; i < host_count; i++)
2062 //     if (!xbt_dynar_length(ROUTE_FULL(i, i)))
2063 //       xbt_dynar_push(ROUTE_FULL(i,i),&routing->loopback);
2064 //
2065 //   /* Shrink the dynar routes (save unused slots) */
2066 //   for (i=0;i<host_count;i++)
2067 //     for (j=0;j<host_count;j++)
2068 //       xbt_dynar_shrink(ROUTE_FULL(i,j),0);
2069 // }
2070 //
2071 // /*
2072 //  * Business methods
2073 //  */
2074 // static xbt_dynar_t routing_full_get_route(int src,int dst) {
2075 //   xbt_assert0(!(ISROUTER(src) || ISROUTER(dst)), "Ask for route \"from\" or \"to\" a router node");
2076 //   return ROUTE_FULL(src,dst);
2077 // }
2078 //
2079 // static xbt_dict_t routing_full_get_onelink_routes(void){
2080 //   return onelink_routes;
2081 // }
2082 //
2083 // static int routing_full_is_router(int id){
2084 //      return ISROUTER(id);
2085 // }
2086 //
2087 // static void routing_full_finalize(void) {
2088 //   routing_full_t routing = (routing_full_t)used_routing;
2089 //   int i,j;
2090 //
2091 //   if (routing) {
2092 //     for (i = 0; i < used_routing->host_count; i++)
2093 //       for (j = 0; j < used_routing->host_count; j++)
2094 //         xbt_dynar_free(&ROUTE_FULL(i, j));
2095 //     free(routing->routing_table);
2096 //     xbt_dict_free(&used_routing->host_id);
2097 //     xbt_dict_free(&onelink_routes);
2098 //     free(routing);
2099 //     routing=NULL;
2100 //   }
2101 // }
2102 //
2103 // static void routing_model_full_create(size_t size_of_link,void *loopback) {
2104 //   /* initialize our structure */
2105 //   routing_full_t routing = xbt_new0(s_routing_full_t,1);
2106 //   routing->generic_routing.name = "Full";
2107 //   routing->generic_routing.host_count = 0;
2108 //   routing->generic_routing.get_route = routing_full_get_route;
2109 //   routing->generic_routing.get_onelink_routes = routing_full_get_onelink_routes;
2110 //   routing->generic_routing.is_router = routing_full_is_router;
2111 //   routing->generic_routing.finalize = routing_full_finalize;
2112 //
2113 //   routing->size_of_link = size_of_link;
2114 //   routing->loopback = loopback;
2115 //
2116 //   /* Set it in position */
2117 //   used_routing = (routing_t) routing;
2118 //
2119 //   /* Set the dict for onehop routes */
2120 //   onelink_routes =  xbt_dict_new();
2121 //
2122 //   routing->generic_routing.host_id = xbt_dict_new();
2123 //
2124 //   /* Setup the parsing callbacks we need */
2125 // //   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
2126 // //   surfxml_add_callback(STag_surfxml_router_cb_list, &routing_full_parse_Srouter);
2127 // //   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_full_parse_end);
2128 // //   surfxml_add_callback(STag_surfxml_route_cb_list, &routing_full_parse_Sroute_set_endpoints);
2129 // //   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
2130 // //   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_full_parse_Scluster);
2131 //
2132 // //   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
2133 // //   surfxml_add_callback(STag_surfxml_router_cb_list, &routing_full_parse_Srouter);
2134 //
2135 // }
2136
2137 /* ************************************************************************** */
2138
2139 // static void routing_shortest_path_parse_Scluster(void)
2140 // {
2141 //   static int AX_ptr = 0;
2142 //
2143 //   char *cluster_id = A_surfxml_cluster_id;
2144 //   char *cluster_prefix = A_surfxml_cluster_prefix;
2145 //   char *cluster_suffix = A_surfxml_cluster_suffix;
2146 //   char *cluster_radical = A_surfxml_cluster_radical;
2147 //   char *cluster_power = A_surfxml_cluster_power;
2148 //   char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
2149 //   char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
2150 //   char *backbone_name;
2151 //
2152 //   surfxml_bufferstack_push(1);
2153 //
2154 //   /* Make set */
2155 //   SURFXML_BUFFER_SET(set_id, cluster_id);
2156 //   SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
2157 //   SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
2158 //   SURFXML_BUFFER_SET(set_radical, cluster_radical);
2159 //
2160 //   SURFXML_START_TAG(set);
2161 //   SURFXML_END_TAG(set);
2162 //
2163 //   /* Make foreach */
2164 //   SURFXML_BUFFER_SET(foreach_set_id, cluster_id);
2165 //
2166 //   SURFXML_START_TAG(foreach);
2167 //
2168 //   /* Make host for the foreach */
2169 //   routing_full_parse_change_cpu_data("$1", cluster_power, "1.0", "", "");
2170 //   A_surfxml_host_state = A_surfxml_host_state_ON;
2171 //
2172 //   SURFXML_START_TAG(host);
2173 //   SURFXML_END_TAG(host);
2174 //
2175 //   SURFXML_END_TAG(foreach);
2176 //
2177 //   /* Make backbone link */
2178 //   backbone_name = bprintf("%s_bb", cluster_id);
2179 //   routing_full_parse_change_link_data(backbone_name, cluster_bb_bw, "", cluster_bb_lat, "",
2180 //                          "");
2181 //   A_surfxml_link_state = A_surfxml_link_state_ON;
2182 //   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_FATPIPE;
2183 //
2184 //   SURFXML_START_TAG(link);
2185 //   SURFXML_END_TAG(link);
2186 //
2187 //   free(backbone_name);
2188 //
2189 //   /* Restore buff */
2190 //   surfxml_bufferstack_pop(1);
2191 // }
2192 //
2193 // /* ************************************************************************** */
2194 // /* *************************** FLOYD ROUTING ********************************* */
2195 // typedef struct {
2196 //   s_routing_t generic_routing;
2197 //   int *predecessor_table;
2198 //   void** link_table;
2199 //   xbt_dynar_t last_route;
2200 //   void *loopback;
2201 //   size_t size_of_link;
2202 // } s_routing_floyd_t,*routing_floyd_t;
2203 //
2204 // #define FLOYD_COST(i,j) cost_table[(i)+(j)*(used_routing)->host_count]
2205 // #define FLOYD_PRED(i,j) ((routing_floyd_t)used_routing)->predecessor_table[(i)+(j)*(used_routing)->host_count]
2206 // #define FLOYD_LINK(i,j) ((routing_floyd_t)used_routing)->link_table[(i)+(j)*(used_routing)->host_count]
2207 //
2208 // static void routing_floyd_parse_end(void) {
2209 //
2210 //   routing_floyd_t routing = (routing_floyd_t) used_routing;
2211 //   int nb_link = 0;
2212 //   void* link_list = NULL;
2213 //   double * cost_table;
2214 //   xbt_dict_cursor_t cursor = NULL;
2215 //   char *key,*data, *end;
2216 //   const char *sep = "#";
2217 //   xbt_dynar_t links, keys;
2218 //
2219 //   unsigned int i,j;
2220 //   unsigned int a,b,c;
2221 //   int host_count = routing->generic_routing.host_count;
2222 //   char * link_name = NULL;
2223 //   void * link = NULL;
2224 //
2225 //   /* Create Cost, Predecessor and Link tables */
2226 //   cost_table = xbt_new0(double, host_count * host_count); //link cost from host to host
2227 //   routing->predecessor_table = xbt_new0(int, host_count*host_count); //predecessor host numbers
2228 //   routing->link_table = xbt_new0(void*,host_count*host_count); //actual link between src and dst
2229 //   routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
2230 //
2231 //   /* Initialize costs and predecessors*/
2232 //   for(i = 0; i<host_count;i++)
2233 //     for(j = 0; j<host_count;j++) {
2234 //         FLOYD_COST(i,j) = DBL_MAX;
2235 //         FLOYD_PRED(i,j) = -1;
2236 //     }
2237 //
2238 //    /* Put the routes in position */
2239 //   xbt_dict_foreach(route_table, cursor, key, data) {
2240 //     nb_link = 0;
2241 //     links = (xbt_dynar_t)data;
2242 //     keys = xbt_str_split_str(key, sep);
2243 //
2244 //
2245 //     src_id = strtol(xbt_dynar_get_as(keys, 0, char*), &end, 16);
2246 //     dst_id = strtol(xbt_dynar_get_as(keys, 1, char*), &end, 16);
2247 //     xbt_dynar_free(&keys);
2248 //
2249 //     DEBUG4("Handle %d %d (from %d hosts): %ld links",
2250 //         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
2251 //     xbt_assert3(xbt_dynar_length(links) == 1, "%ld links in route between host %d and %d, should be 1", xbt_dynar_length(links), src_id, dst_id);
2252 //
2253 //     link_name = xbt_dynar_getfirst_as(links, char*);
2254 //     link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
2255 //
2256 //     if (link)
2257 //       link_list = link;
2258 //     else
2259 //       THROW1(mismatch_error,0,"Link %s not found", link_name);
2260 //
2261 //
2262 //     FLOYD_LINK(src_id,dst_id) = link_list;
2263 //     FLOYD_PRED(src_id, dst_id) = src_id;
2264 //
2265 //     //link cost
2266 //     FLOYD_COST(src_id, dst_id) = 1; // assume 1 for now
2267 //
2268 //   }
2269 //
2270 //     /* Add the loopback if needed */
2271 //   for (i = 0; i < host_count; i++)
2272 //     if (!FLOYD_PRED(i, i)) {
2273 //       FLOYD_PRED(i, i) = i;
2274 //       FLOYD_COST(i, i) = 1;
2275 //       FLOYD_LINK(i, i) = routing->loopback;
2276 //     }
2277 //
2278 //
2279 //   //Calculate path costs
2280 //
2281 //   for(c=0;c<host_count;c++) {
2282 //     for(a=0;a<host_count;a++) {
2283 //       for(b=0;b<host_count;b++) {
2284 //         if(FLOYD_COST(a,c) < DBL_MAX && FLOYD_COST(c,b) < DBL_MAX) {
2285 //           if(FLOYD_COST(a,b) == DBL_MAX || (FLOYD_COST(a,c)+FLOYD_COST(c,b) < FLOYD_COST(a,b))) {
2286 //             FLOYD_COST(a,b) = FLOYD_COST(a,c)+FLOYD_COST(c,b);
2287 //             FLOYD_PRED(a,b) = FLOYD_PRED(c,b);
2288 //           }
2289 //         }
2290 //       }
2291 //     }
2292 //   }
2293 //
2294 //   //cleanup
2295 //   free(cost_table);
2296 // }
2297 //
2298 // /*
2299 //  * Business methods
2300 //  */
2301 // static xbt_dynar_t routing_floyd_get_route(int src_id,int dst_id) {
2302 //
2303 //   routing_floyd_t routing = (routing_floyd_t) used_routing;
2304 //
2305 //   int pred = dst_id;
2306 //   int prev_pred = 0;
2307 //
2308 //   xbt_dynar_reset(routing->last_route);
2309 //
2310 //   do {
2311 //     prev_pred = pred;
2312 //     pred = FLOYD_PRED(src_id, pred);
2313 //
2314 //     if(pred == -1) // if no pred in route -> no route to host
2315 //         break;
2316 //
2317 //     xbt_dynar_unshift(routing->last_route, &FLOYD_LINK(pred,prev_pred));
2318 //
2319 //   } while(pred != src_id);
2320 //
2321 //   xbt_assert2(pred != -1, "no route from host %d to %d", src_id, dst_id);
2322 //
2323 //   return routing->last_route;
2324 // }
2325 //
2326 // static void routing_floyd_finalize(void) {
2327 //   routing_floyd_t routing = (routing_floyd_t)used_routing;
2328 //
2329 //   if (routing) {
2330 //     free(routing->link_table);
2331 //     free(routing->predecessor_table);
2332 //     xbt_dynar_free(&routing->last_route);
2333 //     xbt_dict_free(&used_routing->host_id);
2334 //     free(routing);
2335 //     routing=NULL;
2336 //   }
2337 // }
2338 //
2339 // static xbt_dict_t routing_floyd_get_onelink_routes(void){
2340 //   xbt_assert0(0,"The get_onelink_routes feature is not supported in routing model Floyd");
2341 // }
2342 //
2343 // static int routing_floyd_is_router(int id){
2344 //   xbt_assert0(0,"The get_is_router feature is not supported in routing model Floyd");
2345 // }
2346 //
2347 // static void routing_model_floyd_create(size_t size_of_link,void *loopback) {
2348 //   /* initialize our structure */
2349 //   routing_floyd_t routing = xbt_new0(s_routing_floyd_t,1);
2350 //   routing->generic_routing.name = "Floyd";
2351 //   routing->generic_routing.host_count = 0;
2352 //   routing->generic_routing.host_id = xbt_dict_new();
2353 //   routing->generic_routing.get_route = routing_floyd_get_route;
2354 //   routing->generic_routing.get_onelink_routes = routing_floyd_get_onelink_routes;
2355 //   routing->generic_routing.is_router = routing_floyd_is_router;
2356 //   routing->generic_routing.finalize = routing_floyd_finalize;
2357 //   routing->size_of_link = size_of_link;
2358 //   routing->loopback = loopback;
2359 //
2360 //   /* Set it in position */
2361 //   used_routing = (routing_t) routing;
2362 //
2363 //   /* Setup the parsing callbacks we need */
2364 //   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
2365 //   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_floyd_parse_end);
2366 //   surfxml_add_callback(STag_surfxml_route_cb_list,
2367 //       &routing_full_parse_Sroute_set_endpoints);
2368 //   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
2369 //   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);
2370 //
2371 // }
2372 //
2373 // /* ************************************************************************** */
2374 // /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
2375 // typedef struct {
2376 //   s_routing_t generic_routing;
2377 //   xbt_graph_t route_graph;
2378 //   xbt_dict_t graph_node_map;
2379 //   xbt_dict_t route_cache;
2380 //   xbt_dynar_t last_route;
2381 //   int cached;
2382 //   void *loopback;
2383 //   size_t size_of_link;
2384 // } s_routing_dijkstra_t,*routing_dijkstra_t;
2385 //
2386 //
2387 // typedef struct graph_node_data {
2388 //   int id;
2389 //   int graph_id; //used for caching internal graph id's
2390 // } s_graph_node_data_t, * graph_node_data_t;
2391 //
2392 // typedef struct graph_node_map_element {
2393 //   xbt_node_t node;
2394 // } s_graph_node_map_element_t, * graph_node_map_element_t;
2395 //
2396 // typedef struct route_cache_element {
2397 //   int * pred_arr;
2398 //   int size;
2399 // } s_route_cache_element_t, * route_cache_element_t;
2400 //
2401 // /*
2402 //  * Free functions
2403 //  */
2404 // static void route_cache_elem_free(void *e) {
2405 //   route_cache_element_t elm=(route_cache_element_t)e;
2406 //
2407 //   if (elm) {
2408 //     free(elm->pred_arr);
2409 //     free(elm);
2410 //   }
2411 // }
2412 //
2413 // static void graph_node_map_elem_free(void *e) {
2414 //   graph_node_map_element_t elm = (graph_node_map_element_t)e;
2415 //
2416 //   if(elm) {
2417 //     free(elm);
2418 //   }
2419 // }
2420 //
2421 // /*
2422 //  * Utility functions
2423 // */
2424 // static xbt_node_t route_graph_new_node(int id, int graph_id) {
2425 //   xbt_node_t node = NULL;
2426 //   graph_node_data_t data = NULL;
2427 //   graph_node_map_element_t elm = NULL;
2428 //   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
2429 //
2430 //   data = xbt_new0(struct graph_node_data, sizeof(struct graph_node_data));
2431 //   data->id = id;
2432 //   data->graph_id = graph_id;
2433 //   node = xbt_graph_new_node(routing->route_graph, data);
2434 //
2435 //   elm = xbt_new0(struct graph_node_map_element, sizeof(struct graph_node_map_element));
2436 //   elm->node = node;
2437 //   xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);
2438 //
2439 //   return node;
2440 // }
2441 //
2442 // static graph_node_map_element_t graph_node_map_search(int id) {
2443 //   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
2444 //
2445 //   graph_node_map_element_t elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&id), sizeof(int));
2446 //
2447 //   return elm;
2448 // }
2449 //
2450 // /*
2451 //  * Parsing
2452 //  */
2453 // static void route_new_dijkstra(int src_id, int dst_id, void* link) {
2454 //   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
2455 //
2456 //   xbt_node_t src = NULL;
2457 //   xbt_node_t dst = NULL;
2458 //   graph_node_map_element_t src_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&src_id), sizeof(int));
2459 //   graph_node_map_element_t dst_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&dst_id), sizeof(int));
2460 //
2461 //   if(src_elm)
2462 //     src = src_elm->node;
2463 //
2464 //   if(dst_elm)
2465 //     dst = dst_elm->node;
2466 //
2467 //   //add nodes if they don't exist in the graph
2468 //   if(src_id == dst_id && src == NULL && dst == NULL) {
2469 //     src = route_graph_new_node(src_id, -1);
2470 //     dst = src;
2471 //   } else {
2472 //     if(src == NULL) {
2473 //       src = route_graph_new_node(src_id, -1);
2474 //     }
2475 //
2476 //     if(dst == NULL) {
2477 //       dst = route_graph_new_node(dst_id, -1);
2478 //     }
2479 //   }
2480 //
2481 //   //add link as edge to graph
2482 //   xbt_graph_new_edge(routing->route_graph, src, dst, link);
2483 //
2484 // }
2485 //
2486 // static void add_loopback_dijkstra(void) {
2487 //   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
2488 //
2489 //      xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
2490 //
2491 //      xbt_node_t node = NULL;
2492 //      unsigned int cursor2;
2493 //      xbt_dynar_foreach(nodes, cursor2, node) {
2494 //              xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
2495 //              xbt_edge_t edge = NULL;
2496 //              unsigned int cursor;
2497 //
2498 //              int found = 0;
2499 //              xbt_dynar_foreach(out_edges, cursor, edge) {
2500 //                      xbt_node_t other_node = xbt_graph_edge_get_target(edge);
2501 //                      if(other_node == node) {
2502 //                              found = 1;
2503 //                              break;
2504 //                      }
2505 //              }
2506 //
2507 //              if(!found)
2508 //                      xbt_graph_new_edge(routing->route_graph, node, node, &routing->loopback);
2509 //      }
2510 // }
2511 //
2512 // static void routing_dijkstra_parse_end(void) {
2513 //   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
2514 //   int nb_link = 0;
2515 //   xbt_dict_cursor_t cursor = NULL;
2516 //   char *key, *data, *end;
2517 //   const char *sep = "#";
2518 //   xbt_dynar_t links, keys;
2519 //   char* link_name = NULL;
2520 //   void* link = NULL;
2521 //   xbt_node_t node = NULL;
2522 //   unsigned int cursor2;
2523 //   xbt_dynar_t nodes = NULL;
2524 //   /* Create the topology graph */
2525 //   routing->route_graph = xbt_graph_new_graph(1, NULL);
2526 //   routing->graph_node_map = xbt_dict_new();
2527 //   routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
2528 //   if(routing->cached)
2529 //     routing->route_cache = xbt_dict_new();
2530 //
2531 //
2532 //   /* Put the routes in position */
2533 //   xbt_dict_foreach(route_table, cursor, key, data) {
2534 //     nb_link = 0;
2535 //     links = (xbt_dynar_t) data;
2536 //     keys = xbt_str_split_str(key, sep);
2537 //
2538 //     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
2539 //     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
2540 //     xbt_dynar_free(&keys);
2541 //
2542 //     DEBUG4("Handle %d %d (from %d hosts): %ld links",
2543 //         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
2544 //
2545 //     xbt_assert3(xbt_dynar_length(links) == 1, "%ld links in route between host %d and %d, should be 1", xbt_dynar_length(links), src_id, dst_id);
2546 //
2547 //     link_name = xbt_dynar_getfirst_as(links, char*);
2548 //     link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
2549 //     if (link)
2550 //       route_new_dijkstra(src_id,dst_id,link);
2551 //     else
2552 //       THROW1(mismatch_error,0,"Link %s not found", link_name);
2553 //
2554 //   }
2555 //
2556 //   /* Add the loopback if needed */
2557 //   add_loopback_dijkstra();
2558 //
2559 //   /* initialize graph indexes in nodes after graph has been built */
2560 //   nodes = xbt_graph_get_nodes(routing->route_graph);
2561 //
2562 //   xbt_dynar_foreach(nodes, cursor2, node) {
2563 //     graph_node_data_t data = xbt_graph_node_get_data(node);
2564 //     data->graph_id = cursor2;
2565 //   }
2566 //
2567 // }
2568 //
2569 // /*
2570 //  * Business methods
2571 //  */
2572 // static xbt_dynar_t routing_dijkstra_get_route(int src_id,int dst_id) {
2573 //
2574 //   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
2575 //   int * pred_arr = NULL;
2576 //   int src_node_id = 0;
2577 //   int dst_node_id = 0;
2578 //   int * nodeid = NULL;
2579 //   int v;
2580 //   int size = 0;
2581 //   void * link = NULL;
2582 //   route_cache_element_t elm = NULL;
2583 //   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
2584 //
2585 //   /*Use the graph_node id mapping set to quickly find the nodes */
2586 //   graph_node_map_element_t src_elm = graph_node_map_search(src_id);
2587 //   graph_node_map_element_t dst_elm = graph_node_map_search(dst_id);
2588 //   xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", src_id, dst_id);
2589 //   src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id;
2590 //   dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id;
2591 //
2592 //   if(routing->cached) {
2593 //     /*check if there is a cached predecessor list avail */
2594 //     elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int));
2595 //   }
2596 //
2597 //   if(elm) { //cached mode and cache hit
2598 //     pred_arr = elm->pred_arr;
2599 //   } else { //not cached mode or cache miss
2600 //     double * cost_arr = NULL;
2601 //     xbt_heap_t pqueue = NULL;
2602 //     int i = 0;
2603 //
2604 //     int nr_nodes = xbt_dynar_length(nodes);
2605 //     cost_arr = xbt_new0(double, nr_nodes); //link cost from src to other hosts
2606 //     pred_arr = xbt_new0(int, nr_nodes); //predecessors in path from src
2607 //     pqueue = xbt_heap_new(nr_nodes, free);
2608 //
2609 //     //initialize
2610 //     cost_arr[src_node_id] = 0.0;
2611 //
2612 //     for(i = 0; i < nr_nodes; i++) {
2613 //       if(i != src_node_id) {
2614 //         cost_arr[i] = DBL_MAX;
2615 //       }
2616 //
2617 //       pred_arr[i] = 0;
2618 //
2619 //       //initialize priority queue
2620 //       nodeid = xbt_new0(int, 1);
2621 //       *nodeid = i;
2622 //       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
2623 //
2624 //     }
2625 //
2626 //     // apply dijkstra using the indexes from the graph's node array
2627 //     while(xbt_heap_size(pqueue) > 0) {
2628 //       int * v_id = xbt_heap_pop(pqueue);
2629 //       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
2630 //       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
2631 //       xbt_edge_t edge = NULL;
2632 //       unsigned int cursor;
2633 //
2634 //       xbt_dynar_foreach(out_edges, cursor, edge) {
2635 //         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
2636 //         graph_node_data_t data = xbt_graph_node_get_data(u_node);
2637 //         int u_id = data->graph_id;
2638 //         int cost_v_u = 1; //fixed link cost for now
2639 //
2640 //         if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
2641 //           pred_arr[u_id] = *v_id;
2642 //           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
2643 //           nodeid = xbt_new0(int, 1);
2644 //           *nodeid = u_id;
2645 //           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
2646 //         }
2647 //       }
2648 //
2649 //       //free item popped from pqueue
2650 //       free(v_id);
2651 //     }
2652 //
2653 //     free(cost_arr);
2654 //     xbt_heap_free(pqueue);
2655 //
2656 //   }
2657 //
2658 //   //compose route path with links
2659 //   xbt_dynar_reset(routing->last_route);
2660 //
2661 //   for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
2662 //     xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
2663 //     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
2664 //     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
2665 //
2666 //     xbt_assert2(edge != NULL, "no route between host %d and %d", src_id, dst_id);
2667 //
2668 //     link = xbt_graph_edge_get_data(edge);
2669 //     xbt_dynar_unshift(routing->last_route, &link);
2670 //     size++;
2671 //   }
2672 //
2673 //
2674 //   if(routing->cached && elm == NULL) {
2675 //     //add to predecessor list of the current src-host to cache
2676 //     elm = xbt_new0(struct route_cache_element, sizeof(struct route_cache_element));
2677 //     elm->pred_arr = pred_arr;
2678 //     elm->size = size;
2679 //     xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free);
2680 //   }
2681 //
2682 //   if(!routing->cached)
2683 //     free(pred_arr);
2684 //
2685 //   return routing->last_route;
2686 // }
2687 //
2688 //
2689 // static void routing_dijkstra_finalize(void) {
2690 //   routing_dijkstra_t routing = (routing_dijkstra_t)used_routing;
2691 //
2692 //   if (routing) {
2693 //     xbt_graph_free_graph(routing->route_graph, &free, NULL, &free);
2694 //     xbt_dict_free(&routing->graph_node_map);
2695 //     if(routing->cached)
2696 //       xbt_dict_free(&routing->route_cache);
2697 //     xbt_dynar_free(&routing->last_route);
2698 //     xbt_dict_free(&used_routing->host_id);
2699 //     free(routing);
2700 //     routing=NULL;
2701 //   }
2702 // }
2703 //
2704 // static xbt_dict_t routing_dijkstraboth_get_onelink_routes(void){
2705 //   xbt_assert0(0,"The get_onelink_routes feature is not supported in routing model dijkstraboth");
2706 // }
2707 //
2708 // static int routing_dijkstraboth_is_router(int id){
2709 //   xbt_assert0(0,"The get_is_router feature is not supported in routing model dijkstraboth");
2710 // }
2711 //
2712 // /*
2713 //  *
2714 //  */
2715 // static void routing_model_dijkstraboth_create(size_t size_of_link,void *loopback, int cached) {
2716 //   /* initialize our structure */
2717 //   routing_dijkstra_t routing = xbt_new0(s_routing_dijkstra_t,1);
2718 //   routing->generic_routing.name = "Dijkstra";
2719 //   routing->generic_routing.host_count = 0;
2720 //   routing->generic_routing.get_route = routing_dijkstra_get_route;
2721 //   routing->generic_routing.get_onelink_routes = routing_dijkstraboth_get_onelink_routes;
2722 //   routing->generic_routing.is_router = routing_dijkstraboth_is_router;
2723 //   routing->generic_routing.finalize = routing_dijkstra_finalize;
2724 //   routing->size_of_link = size_of_link;
2725 //   routing->loopback = loopback;
2726 //   routing->cached = cached;
2727 //
2728 //   /* Set it in position */
2729 //   used_routing = (routing_t) routing;
2730 //
2731 //   /* Setup the parsing callbacks we need */
2732 //   routing->generic_routing.host_id = xbt_dict_new();
2733 //   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
2734 //   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_dijkstra_parse_end);
2735 //   surfxml_add_callback(STag_surfxml_route_cb_list,
2736 //       &routing_full_parse_Sroute_set_endpoints);
2737 //   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
2738 //   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);
2739 // }
2740 //
2741 // static void routing_model_dijkstra_create(size_t size_of_link,void *loopback) {
2742 //   routing_model_dijkstraboth_create(size_of_link, loopback, 0);
2743 // }
2744 //
2745 // static void routing_model_dijkstracache_create(size_t size_of_link,void *loopback) {
2746 //   routing_model_dijkstraboth_create(size_of_link, loopback, 1);
2747 // }
2748
2749 /* ************************************************** */
2750 /* ********** NO ROUTING **************************** */
2751
2752
2753 // static void routing_none_finalize(void) {
2754 //   if (used_routing) {
2755 //     xbt_dict_free(&used_routing->host_id);
2756 //     free(used_routing);
2757 //     used_routing=NULL;
2758 //   }
2759 // }
2760 //
2761 // static void routing_model_none_create(size_t size_of_link,void *loopback) {
2762 //   routing_t routing = xbt_new0(s_routing_t,1);
2763 //   INFO0("Null routing");
2764 //   routing->name = "none";
2765 //   routing->host_count = 0;
2766 //   routing->host_id = xbt_dict_new();
2767 //   routing->get_onelink_routes = NULL;
2768 //   routing->is_router = NULL;
2769 //   routing->get_route = NULL;
2770 //
2771 //   routing->finalize = routing_none_finalize;
2772 //
2773 //   /* Set it in position */
2774 //   used_routing = (routing_t) routing;
2775 // }