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 routing_t used_routing = NULL;
  18 xbt_dict_t onelink_routes = NULL;
  19
  20 /* Prototypes of each model */
  21 static void routing_model_full_create(size_t size_of_link,void *loopback);
  22 static void routing_model_floyd_create(size_t size_of_link, void*loopback);
  23 static void routing_model_dijkstra_create(size_t size_of_link, void*loopback);
  24 static void routing_model_dijkstracache_create(size_t size_of_link, void*loopback);
  25 static void routing_model_hierarchical_create(size_t size_of_link, void*loopback); // added by DAVID
  26 static void routing_model_none_create(size_t size_of_link, void*loopback);
  27
  28 /* Definition of each model */
  29 struct model_type {
  30   const char *name;
  31   const char *desc;
  32   void (*fun)(size_t,void*);
  33 };
  34 struct model_type models[] =
  35 { {"Full", "Full routing data (fast, large memory requirements, fully expressive)", routing_model_full_create },
  36   {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)", routing_model_floyd_create },
  37   {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)", routing_model_dijkstra_create },
  38   {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)", routing_model_dijkstracache_create },
  39   {"Hierarchical", "Hierarchical routing", routing_model_hierarchical_create }, // added by DAVID
  40   {"none", "No routing (usable with Constant network only)", routing_model_none_create },
  41   {NULL,NULL,NULL}};
  42
  43
  44 void routing_model_create(size_t size_of_links, void* loopback) {
  45 //
  46   char * wanted=xbt_cfg_get_string(_surf_cfg_set,"routing");
  47   int cpt;
  48   for (cpt=0;models[cpt].name;cpt++) {
  49     if (!strcmp(wanted,models[cpt].name)) {
  50       (*(models[cpt].fun))(size_of_links,loopback);
  51       return;
  52     }
  53   }
  54   fprintf(stderr,"Routing model %s not found. Existing models:\n",wanted);
  55   for (cpt=0;models[cpt].name;cpt++)
  56     fprintf(stderr,"   %s: %s\n",models[cpt].name,models[cpt].desc);
  57   xbt_die("Invalid model.");
  58 }
  59 //
  60 /* ************************************************************************** */
  61 /* *************************** FULL ROUTING ********************************* */
  62 typedef struct {
  63   s_routing_t generic_routing;
  64   xbt_dynar_t *routing_table;
  65   void *loopback;
  66   size_t size_of_link;
  67 } s_routing_full_t,*routing_full_t;
  68
  69 #define ROUTE_FULL(i,j) ((routing_full_t)used_routing)->routing_table[(i)+(j)*(used_routing)->host_count]
  70 #define HOST2ROUTER(id) ((id)+(2<<29))
  71 #define ROUTER2HOST(id) ((id)-(2<<29))
  72 #define ISROUTER(id) ((id)>=(2<<29))
  73
  74 /*
  75  * Free the onelink routes
  76  */
  77 static void onelink_route_elem_free(void *e) {
  78   s_onelink_t tmp = (s_onelink_t)e;
  79   if(tmp) {
  80     free(tmp);
  81   }
  82 }
  83
  84
  85 /*
  86  * Parsing
  87  */
  88 static void routing_full_parse_Shost(void) {
  89   int *val = xbt_malloc(sizeof(int));
  90   DEBUG2("Seen host %s (#%d)",A_surfxml_host_id,used_routing->host_count);
  91   *val = used_routing->host_count++;
  92   xbt_dict_set(used_routing->host_id,A_surfxml_host_id,val,xbt_free);
  93 #ifdef HAVE_TRACING
  94   TRACE_surf_host_define_id (A_surfxml_host_id, *val);
  95 #endif
  96 }
  97
  98 static void routing_full_parse_Srouter(void) {
  99         int *val = xbt_malloc(sizeof(int));
 100   DEBUG3("Seen router %s (%d -> #%d)",A_surfxml_router_id,used_routing->router_count,
 101                 HOST2ROUTER(used_routing->router_count));
 102   *val = HOST2ROUTER(used_routing->router_count++);
 103   xbt_dict_set(used_routing->host_id,A_surfxml_router_id,val,xbt_free);
 104 #ifdef HAVE_TRACING
 105   TRACE_surf_host_define_id (A_surfxml_router_id, *val);
 106   TRACE_surf_host_declaration (A_surfxml_router_id, 0);
 107 #endif
 108 }
 109
 110 static int src_id = -1;
 111 static int dst_id = -1;
 112 static void routing_full_parse_Sroute_set_endpoints(void)
 113 {
 114   src_id = *(int*)xbt_dict_get(used_routing->host_id,A_surfxml_route_src);
 115   dst_id = *(int*)xbt_dict_get(used_routing->host_id,A_surfxml_route_dst);
 116   DEBUG4("Route %s %d -> %s %d",A_surfxml_route_src,src_id,A_surfxml_route_dst,dst_id);
 117   route_action = A_surfxml_route_action;
 118 }
 119 static void routing_full_parse_Eroute(void)
 120 {
 121   char *name;
 122   if (src_id != -1 && dst_id != -1) {
 123     name = bprintf("%x#%x", src_id, dst_id);
 124     manage_route(route_table, name, route_action, 0);
 125     free(name);
 126   }
 127 }
 128
 129 /* Cluster tag functions */
 130
 131 static void routing_full_parse_change_cpu_data(const char *hostName,
 132                                   const char *surfxml_host_power,
 133                                   const char *surfxml_host_availability,
 134                                   const char *surfxml_host_availability_file,
 135                                   const char *surfxml_host_state_file)
 136 {
 137   int AX_ptr = 0;
 138
 139   SURFXML_BUFFER_SET(host_id, hostName);
 140   SURFXML_BUFFER_SET(host_power, surfxml_host_power /*hostPower */ );
 141   SURFXML_BUFFER_SET(host_availability, surfxml_host_availability);
 142   SURFXML_BUFFER_SET(host_availability_file, surfxml_host_availability_file);
 143   SURFXML_BUFFER_SET(host_state_file, surfxml_host_state_file);
 144 }
 145
 146 static void routing_full_parse_change_link_data(const char *linkName,
 147                                    const char *surfxml_link_bandwidth,
 148                                    const char *surfxml_link_bandwidth_file,
 149                                    const char *surfxml_link_latency,
 150                                    const char *surfxml_link_latency_file,
 151                                    const char *surfxml_link_state_file)
 152 {
 153   int AX_ptr = 0;
 154
 155   SURFXML_BUFFER_SET(link_id, linkName);
 156   SURFXML_BUFFER_SET(link_bandwidth, surfxml_link_bandwidth);
 157   SURFXML_BUFFER_SET(link_bandwidth_file, surfxml_link_bandwidth_file);
 158   SURFXML_BUFFER_SET(link_latency, surfxml_link_latency);
 159   SURFXML_BUFFER_SET(link_latency_file, surfxml_link_latency_file);
 160   SURFXML_BUFFER_SET(link_state_file, surfxml_link_state_file);
 161 }
 162
 163 static void routing_full_parse_Scluster(void)
 164 {
 165   static int AX_ptr = 0;
 166
 167   char *cluster_id = A_surfxml_cluster_id;
 168   char *cluster_prefix = A_surfxml_cluster_prefix;
 169   char *cluster_suffix = A_surfxml_cluster_suffix;
 170   char *cluster_radical = A_surfxml_cluster_radical;
 171   char *cluster_power = A_surfxml_cluster_power;
 172   char *cluster_bw = A_surfxml_cluster_bw;
 173   char *cluster_lat = A_surfxml_cluster_lat;
 174   char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
 175   char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
 176   char *backbone_name;
 177   unsigned int it1,it2;
 178   char *name1,*name2;
 179   xbt_dynar_t names = NULL;
 180   surfxml_bufferstack_push(1);
 181
 182   /* Make set a set to parse the prefix/suffix/radical into a neat list of names */
 183   DEBUG4("Make <set id='%s' prefix='%s' suffix='%s' radical='%s'>",
 184       cluster_id,cluster_prefix,cluster_suffix,cluster_radical);
 185   SURFXML_BUFFER_SET(set_id, cluster_id);
 186   SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
 187   SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
 188   SURFXML_BUFFER_SET(set_radical, cluster_radical);
 189
 190   SURFXML_START_TAG(set);
 191   SURFXML_END_TAG(set);
 192
 193   names = xbt_dict_get(set_list,cluster_id);
 194
 195   xbt_dynar_foreach(names,it1,name1) {
 196     /* create the host */
 197     routing_full_parse_change_cpu_data(name1, cluster_power, "1.0", "", "");
 198     A_surfxml_host_state = A_surfxml_host_state_ON;
 199
 200     SURFXML_START_TAG(host);
 201     SURFXML_END_TAG(host);
 202
 203     /* Here comes the link */
 204     routing_full_parse_change_link_data(name1, cluster_bw, "", cluster_lat, "", "");
 205     A_surfxml_link_state = A_surfxml_link_state_ON;
 206     A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
 207
 208     SURFXML_START_TAG(link);
 209     SURFXML_END_TAG(link);
 210   }
 211
 212   /* Make backbone link */
 213   backbone_name = bprintf("%s_bb", cluster_id);
 214   routing_full_parse_change_link_data(backbone_name, cluster_bb_bw, "", cluster_bb_lat, "",
 215                          "");
 216   A_surfxml_link_state = A_surfxml_link_state_ON;
 217   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_FATPIPE;
 218
 219   SURFXML_START_TAG(link);
 220   SURFXML_END_TAG(link);
 221
 222   /* And now the internal routes */
 223   xbt_dynar_foreach(names,it1,name1) {
 224     xbt_dynar_foreach(names,it2,name2) {
 225       if (strcmp(name1,name2)) {
 226         A_surfxml_route_action = A_surfxml_route_action_POSTPEND;
 227         SURFXML_BUFFER_SET(route_src,name1);
 228         SURFXML_BUFFER_SET(route_dst,name2);
 229         SURFXML_START_TAG(route); {
 230           /* FIXME: name1 link is added by error about 20 lines below, so don't add it here
 231           SURFXML_BUFFER_SET(link_c_ctn_id, name1);
 232           SURFXML_START_TAG(link_c_ctn);
 233           SURFXML_END_TAG(link_c_ctn);
 234            */
 235           SURFXML_BUFFER_SET(link_c_ctn_id, backbone_name);
 236           SURFXML_START_TAG(link_c_ctn);
 237           SURFXML_END_TAG(link_c_ctn);
 238
 239           SURFXML_BUFFER_SET(link_c_ctn_id, name2);
 240           SURFXML_START_TAG(link_c_ctn);
 241           SURFXML_END_TAG(link_c_ctn);
 242
 243         } SURFXML_END_TAG(route);
 244       }
 245     }
 246   }
 247
 248   /* Make route multi with the outside world, i.e. cluster->$* */
 249
 250   /* FIXME
 251    * This also adds an elements to the routes within the cluster,
 252    * and I guess it's wrong, but since this element is commented out in the above
 253    * code creating the internal routes, we're good.
 254    * To fix it, I'd say that we need a way to understand "$*-${cluster_id}" as "whole world, but the guys in that cluster"
 255    * But for that, we need to install a real expression parser for src/dst attributes
 256    *
 257    * FIXME
 258    * This also adds a dumb element (the private link) in place of the loopback. Then, since
 259    * the loopback is added only if no link to self already exist, this fails.
 260    * That's really dumb.
 261    *
 262    * FIXME
 263    * It seems to me that it does not add the backbone to the path to outside world...
 264    */
 265   SURFXML_BUFFER_SET(route_c_multi_src, cluster_id);
 266   SURFXML_BUFFER_SET(route_c_multi_dst, "$*");
 267   A_surfxml_route_c_multi_symmetric = A_surfxml_route_c_multi_symmetric_NO;
 268   A_surfxml_route_c_multi_action = A_surfxml_route_c_multi_action_PREPEND;
 269
 270   SURFXML_START_TAG(route_c_multi);
 271
 272   SURFXML_BUFFER_SET(link_c_ctn_id, "$src");
 273
 274   SURFXML_START_TAG(link_c_ctn);
 275   SURFXML_END_TAG(link_c_ctn);
 276
 277   SURFXML_END_TAG(route_c_multi);
 278
 279   free(backbone_name);
 280
 281   /* Restore buff */
 282   surfxml_bufferstack_pop(1);
 283 }
 284
 285
 286 static void routing_full_parse_end(void) {
 287   routing_full_t routing = (routing_full_t) used_routing;
 288   int nb_link = 0;
 289   unsigned int cpt = 0;
 290   xbt_dict_cursor_t cursor = NULL;
 291   char *key, *data, *end;
 292   const char *sep = "#";
 293   xbt_dynar_t links, keys;
 294   char *link_name = NULL;
 295   int i,j;
 296
 297   int host_count = routing->generic_routing.host_count;
 298
 299   /* Create the routing table */
 300   routing->routing_table = xbt_new0(xbt_dynar_t, host_count * host_count);
 301   for (i=0;i<host_count;i++)
 302     for (j=0;j<host_count;j++)
 303       ROUTE_FULL(i,j) = xbt_dynar_new(routing->size_of_link,NULL);
 304
 305   /* Put the routes in position */
 306   xbt_dict_foreach(route_table, cursor, key, data) {
 307     nb_link = 0;
 308     links = (xbt_dynar_t) data;
 309     keys = xbt_str_split_str(key, sep);
 310
 311     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
 312     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
 313     xbt_dynar_free(&keys);
 314
 315     if(xbt_dynar_length(links) == 1){
 316       s_onelink_t new_link = (s_onelink_t) xbt_malloc0(sizeof(s_onelink));
 317       new_link->src_id = src_id;
 318       new_link->dst_id = dst_id;
 319       link_name = xbt_dynar_getfirst_as(links, char*);
 320       new_link->link_ptr = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
 321       DEBUG3("Adding onelink route from (#%d) to (#%d), link_name %s",src_id, dst_id, link_name);
 322       xbt_dict_set(onelink_routes, link_name, (void *)new_link, onelink_route_elem_free);
 323 #ifdef HAVE_TRACING
 324       TRACE_surf_link_save_endpoints (link_name, src_id, dst_id);
 325 #endif
 326     }
 327
 328     if(ISROUTER(src_id) || ISROUTER(dst_id)) {
 329                                 DEBUG2("There is route with a router here: (%d ,%d)",src_id,dst_id);
 330                                 /* Check there is only one link in the route and store the information */
 331                                 continue;
 332     }
 333
 334     DEBUG4("Handle %d %d (from %d hosts): %ld links",
 335         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
 336     xbt_dynar_foreach(links, cpt, link_name) {
 337       void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
 338       if (link)
 339         xbt_dynar_push(ROUTE_FULL(src_id,dst_id),&link);
 340       else
 341         THROW1(mismatch_error,0,"Link %s not found", link_name);
 342     }
 343   }
 344
 345   /* Add the loopback if needed */
 346   for (i = 0; i < host_count; i++)
 347     if (!xbt_dynar_length(ROUTE_FULL(i, i)))
 348       xbt_dynar_push(ROUTE_FULL(i,i),&routing->loopback);
 349
 350   /* Shrink the dynar routes (save unused slots) */
 351   for (i=0;i<host_count;i++)
 352     for (j=0;j<host_count;j++)
 353       xbt_dynar_shrink(ROUTE_FULL(i,j),0);
 354 }
 355
 356 /*
 357  * Business methods
 358  */
 359 static xbt_dynar_t routing_full_get_route(int src,int dst) {
 360   xbt_assert0(!(ISROUTER(src) || ISROUTER(dst)), "Ask for route \"from\" or \"to\" a router node");
 361   return ROUTE_FULL(src,dst);
 362 }
 363
 364 static xbt_dict_t routing_full_get_onelink_routes(void){
 365   return onelink_routes;
 366 }
 367
 368 static int routing_full_is_router(int id){
 369         return ISROUTER(id);
 370 }
 371
 372 static void routing_full_finalize(void) {
 373   routing_full_t routing = (routing_full_t)used_routing;
 374   int i,j;
 375
 376   if (routing) {
 377     for (i = 0; i < used_routing->host_count; i++)
 378       for (j = 0; j < used_routing->host_count; j++)
 379         xbt_dynar_free(&ROUTE_FULL(i, j));
 380     free(routing->routing_table);
 381     xbt_dict_free(&used_routing->host_id);
 382     xbt_dict_free(&onelink_routes);
 383     free(routing);
 384     routing=NULL;
 385   }
 386 }
 387
 388 static void routing_model_full_create(size_t size_of_link,void *loopback) {
 389   /* initialize our structure */
 390   routing_full_t routing = xbt_new0(s_routing_full_t,1);
 391   routing->generic_routing.name = "Full";
 392   routing->generic_routing.host_count = 0;
 393   routing->generic_routing.get_route = routing_full_get_route;
 394   routing->generic_routing.get_onelink_routes = routing_full_get_onelink_routes;
 395   routing->generic_routing.is_router = routing_full_is_router;
 396   routing->generic_routing.finalize = routing_full_finalize;
 397
 398   routing->size_of_link = size_of_link;
 399   routing->loopback = loopback;
 400
 401   /* Set it in position */
 402   used_routing = (routing_t) routing;
 403
 404   /* Set the dict for onehop routes */
 405   onelink_routes =  xbt_dict_new();
 406
 407   /* Setup the parsing callbacks we need */
 408   routing->generic_routing.host_id = xbt_dict_new();
 409   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
 410   surfxml_add_callback(STag_surfxml_router_cb_list, &routing_full_parse_Srouter);
 411   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_full_parse_end);
 412   surfxml_add_callback(STag_surfxml_route_cb_list,
 413       &routing_full_parse_Sroute_set_endpoints);
 414   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
 415   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_full_parse_Scluster);
 416 }
 417
 418 /* ************************************************************************** */
 419
 420 static void routing_shortest_path_parse_Scluster(void)
 421 {
 422   static int AX_ptr = 0;
 423
 424   char *cluster_id = A_surfxml_cluster_id;
 425   char *cluster_prefix = A_surfxml_cluster_prefix;
 426   char *cluster_suffix = A_surfxml_cluster_suffix;
 427   char *cluster_radical = A_surfxml_cluster_radical;
 428   char *cluster_power = A_surfxml_cluster_power;
 429   char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
 430   char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
 431   char *backbone_name;
 432
 433   surfxml_bufferstack_push(1);
 434
 435   /* Make set */
 436   SURFXML_BUFFER_SET(set_id, cluster_id);
 437   SURFXML_BUFFER_SET(set_prefix, cluster_prefix);
 438   SURFXML_BUFFER_SET(set_suffix, cluster_suffix);
 439   SURFXML_BUFFER_SET(set_radical, cluster_radical);
 440
 441   SURFXML_START_TAG(set);
 442   SURFXML_END_TAG(set);
 443
 444   /* Make foreach */
 445   SURFXML_BUFFER_SET(foreach_set_id, cluster_id);
 446
 447   SURFXML_START_TAG(foreach);
 448
 449   /* Make host for the foreach */
 450   routing_full_parse_change_cpu_data("$1", cluster_power, "1.0", "", "");
 451   A_surfxml_host_state = A_surfxml_host_state_ON;
 452
 453   SURFXML_START_TAG(host);
 454   SURFXML_END_TAG(host);
 455
 456   SURFXML_END_TAG(foreach);
 457
 458   /* Make backbone link */
 459   backbone_name = bprintf("%s_bb", cluster_id);
 460   routing_full_parse_change_link_data(backbone_name, cluster_bb_bw, "", cluster_bb_lat, "",
 461                          "");
 462   A_surfxml_link_state = A_surfxml_link_state_ON;
 463   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_FATPIPE;
 464
 465   SURFXML_START_TAG(link);
 466   SURFXML_END_TAG(link);
 467
 468   free(backbone_name);
 469
 470   /* Restore buff */
 471   surfxml_bufferstack_pop(1);
 472 }
 473
 474 /* ************************************************************************** */
 475 /* *************************** FLOYD ROUTING ********************************* */
 476 typedef struct {
 477   s_routing_t generic_routing;
 478   int *predecessor_table;
 479   void** link_table;
 480   xbt_dynar_t last_route;
 481   void *loopback;
 482   size_t size_of_link;
 483 } s_routing_floyd_t,*routing_floyd_t;
 484
 485 #define FLOYD_COST(i,j) cost_table[(i)+(j)*(used_routing)->host_count]
 486 #define FLOYD_PRED(i,j) ((routing_floyd_t)used_routing)->predecessor_table[(i)+(j)*(used_routing)->host_count]
 487 #define FLOYD_LINK(i,j) ((routing_floyd_t)used_routing)->link_table[(i)+(j)*(used_routing)->host_count]
 488
 489 static void routing_floyd_parse_end(void) {
 490
 491   routing_floyd_t routing = (routing_floyd_t) used_routing;
 492   int nb_link = 0;
 493   void* link_list = NULL;
 494   double * cost_table;
 495   xbt_dict_cursor_t cursor = NULL;
 496   char *key,*data, *end;
 497   const char *sep = "#";
 498   xbt_dynar_t links, keys;
 499
 500   unsigned int i,j;
 501   unsigned int a,b,c;
 502   int host_count = routing->generic_routing.host_count;
 503   char * link_name = NULL;
 504   void * link = NULL;
 505
 506   /* Create Cost, Predecessor and Link tables */
 507   cost_table = xbt_new0(double, host_count * host_count); //link cost from host to host
 508   routing->predecessor_table = xbt_new0(int, host_count*host_count); //predecessor host numbers
 509   routing->link_table = xbt_new0(void*,host_count*host_count); //actual link between src and dst
 510   routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
 511
 512   /* Initialize costs and predecessors*/
 513   for(i = 0; i<host_count;i++)
 514     for(j = 0; j<host_count;j++) {
 515         FLOYD_COST(i,j) = DBL_MAX;
 516         FLOYD_PRED(i,j) = -1;
 517     }
 518
 519    /* Put the routes in position */
 520   xbt_dict_foreach(route_table, cursor, key, data) {
 521     nb_link = 0;
 522     links = (xbt_dynar_t)data;
 523     keys = xbt_str_split_str(key, sep);
 524
 525
 526     src_id = strtol(xbt_dynar_get_as(keys, 0, char*), &end, 16);
 527     dst_id = strtol(xbt_dynar_get_as(keys, 1, char*), &end, 16);
 528     xbt_dynar_free(&keys);
 529
 530     DEBUG4("Handle %d %d (from %d hosts): %ld links",
 531         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
 532     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);
 533
 534     link_name = xbt_dynar_getfirst_as(links, char*);
 535     link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
 536
 537     if (link)
 538       link_list = link;
 539     else
 540       THROW1(mismatch_error,0,"Link %s not found", link_name);
 541
 542
 543     FLOYD_LINK(src_id,dst_id) = link_list;
 544     FLOYD_PRED(src_id, dst_id) = src_id;
 545
 546     //link cost
 547     FLOYD_COST(src_id, dst_id) = 1; // assume 1 for now
 548
 549   }
 550
 551     /* Add the loopback if needed */
 552   for (i = 0; i < host_count; i++)
 553     if (!FLOYD_PRED(i, i)) {
 554       FLOYD_PRED(i, i) = i;
 555       FLOYD_COST(i, i) = 1;
 556       FLOYD_LINK(i, i) = routing->loopback;
 557     }
 558
 559
 560   //Calculate path costs
 561
 562   for(c=0;c<host_count;c++) {
 563     for(a=0;a<host_count;a++) {
 564       for(b=0;b<host_count;b++) {
 565         if(FLOYD_COST(a,c) < DBL_MAX && FLOYD_COST(c,b) < DBL_MAX) {
 566           if(FLOYD_COST(a,b) == DBL_MAX || (FLOYD_COST(a,c)+FLOYD_COST(c,b) < FLOYD_COST(a,b))) {
 567             FLOYD_COST(a,b) = FLOYD_COST(a,c)+FLOYD_COST(c,b);
 568             FLOYD_PRED(a,b) = FLOYD_PRED(c,b);
 569           }
 570         }
 571       }
 572     }
 573   }
 574
 575   //cleanup
 576   free(cost_table);
 577 }
 578
 579 /*
 580  * Business methods
 581  */
 582 static xbt_dynar_t routing_floyd_get_route(int src_id,int dst_id) {
 583
 584   routing_floyd_t routing = (routing_floyd_t) used_routing;
 585
 586   int pred = dst_id;
 587   int prev_pred = 0;
 588
 589   xbt_dynar_reset(routing->last_route);
 590
 591   do {
 592     prev_pred = pred;
 593     pred = FLOYD_PRED(src_id, pred);
 594
 595     if(pred == -1) // if no pred in route -> no route to host
 596         break;
 597
 598     xbt_dynar_unshift(routing->last_route, &FLOYD_LINK(pred,prev_pred));
 599
 600   } while(pred != src_id);
 601
 602   xbt_assert2(pred != -1, "no route from host %d to %d", src_id, dst_id);
 603
 604   return routing->last_route;
 605 }
 606
 607 static void routing_floyd_finalize(void) {
 608   routing_floyd_t routing = (routing_floyd_t)used_routing;
 609
 610   if (routing) {
 611     free(routing->link_table);
 612     free(routing->predecessor_table);
 613     xbt_dynar_free(&routing->last_route);
 614     xbt_dict_free(&used_routing->host_id);
 615     free(routing);
 616     routing=NULL;
 617   }
 618 }
 619
 620 static xbt_dict_t routing_floyd_get_onelink_routes(void){
 621   xbt_assert0(0,"The get_onelink_routes feature is not supported in routing model Floyd");
 622 }
 623
 624 static int routing_floyd_is_router(int id){
 625   xbt_assert0(0,"The get_is_router feature is not supported in routing model Floyd");
 626 }
 627
 628 static void routing_model_floyd_create(size_t size_of_link,void *loopback) {
 629   /* initialize our structure */
 630   routing_floyd_t routing = xbt_new0(s_routing_floyd_t,1);
 631   routing->generic_routing.name = "Floyd";
 632   routing->generic_routing.host_count = 0;
 633   routing->generic_routing.host_id = xbt_dict_new();
 634   routing->generic_routing.get_route = routing_floyd_get_route;
 635   routing->generic_routing.get_onelink_routes = routing_floyd_get_onelink_routes;
 636   routing->generic_routing.is_router = routing_floyd_is_router;
 637   routing->generic_routing.finalize = routing_floyd_finalize;
 638   routing->size_of_link = size_of_link;
 639   routing->loopback = loopback;
 640
 641   /* Set it in position */
 642   used_routing = (routing_t) routing;
 643
 644   /* Setup the parsing callbacks we need */
 645   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
 646   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_floyd_parse_end);
 647   surfxml_add_callback(STag_surfxml_route_cb_list,
 648       &routing_full_parse_Sroute_set_endpoints);
 649   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
 650   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);
 651
 652 }
 653
 654 /* ************************************************************************** */
 655 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
 656 typedef struct {
 657   s_routing_t generic_routing;
 658   xbt_graph_t route_graph;
 659   xbt_dict_t graph_node_map;
 660   xbt_dict_t route_cache;
 661   xbt_dynar_t last_route;
 662   int cached;
 663   void *loopback;
 664   size_t size_of_link;
 665 } s_routing_dijkstra_t,*routing_dijkstra_t;
 666
 667
 668 typedef struct graph_node_data {
 669   int id;
 670   int graph_id; //used for caching internal graph id's
 671 } s_graph_node_data_t, * graph_node_data_t;
 672
 673 typedef struct graph_node_map_element {
 674   xbt_node_t node;
 675 } s_graph_node_map_element_t, * graph_node_map_element_t;
 676
 677 typedef struct route_cache_element {
 678   int * pred_arr;
 679   int size;
 680 } s_route_cache_element_t, * route_cache_element_t;
 681
 682 /*
 683  * Free functions
 684  */
 685 static void route_cache_elem_free(void *e) {
 686   route_cache_element_t elm=(route_cache_element_t)e;
 687
 688   if (elm) {
 689     free(elm->pred_arr);
 690     free(elm);
 691   }
 692 }
 693
 694 static void graph_node_map_elem_free(void *e) {
 695   graph_node_map_element_t elm = (graph_node_map_element_t)e;
 696
 697   if(elm) {
 698     free(elm);
 699   }
 700 }
 701
 702 /*
 703  * Utility functions
 704 */
 705 static xbt_node_t route_graph_new_node(int id, int graph_id) {
 706   xbt_node_t node = NULL;
 707   graph_node_data_t data = NULL;
 708   graph_node_map_element_t elm = NULL;
 709   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 710
 711   data = xbt_new0(struct graph_node_data, sizeof(struct graph_node_data));
 712   data->id = id;
 713   data->graph_id = graph_id;
 714   node = xbt_graph_new_node(routing->route_graph, data);
 715
 716   elm = xbt_new0(struct graph_node_map_element, sizeof(struct graph_node_map_element));
 717   elm->node = node;
 718   xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);
 719
 720   return node;
 721 }
 722
 723 static graph_node_map_element_t graph_node_map_search(int id) {
 724   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 725
 726   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));
 727
 728   return elm;
 729 }
 730
 731 /*
 732  * Parsing
 733  */
 734 static void route_new_dijkstra(int src_id, int dst_id, void* link) {
 735   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 736
 737   xbt_node_t src = NULL;
 738   xbt_node_t dst = NULL;
 739   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));
 740   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));
 741
 742   if(src_elm)
 743     src = src_elm->node;
 744
 745   if(dst_elm)
 746     dst = dst_elm->node;
 747
 748   //add nodes if they don't exist in the graph
 749   if(src_id == dst_id && src == NULL && dst == NULL) {
 750     src = route_graph_new_node(src_id, -1);
 751     dst = src;
 752   } else {
 753     if(src == NULL) {
 754       src = route_graph_new_node(src_id, -1);
 755     }
 756
 757     if(dst == NULL) {
 758       dst = route_graph_new_node(dst_id, -1);
 759     }
 760   }
 761
 762   //add link as edge to graph
 763   xbt_graph_new_edge(routing->route_graph, src, dst, link);
 764
 765 }
 766
 767 static void add_loopback_dijkstra(void) {
 768   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 769
 770         xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
 771
 772         xbt_node_t node = NULL;
 773         unsigned int cursor2;
 774         xbt_dynar_foreach(nodes, cursor2, node) {
 775                 xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
 776                 xbt_edge_t edge = NULL;
 777                 unsigned int cursor;
 778
 779                 int found = 0;
 780                 xbt_dynar_foreach(out_edges, cursor, edge) {
 781                         xbt_node_t other_node = xbt_graph_edge_get_target(edge);
 782                         if(other_node == node) {
 783                                 found = 1;
 784                                 break;
 785                         }
 786                 }
 787
 788                 if(!found)
 789                         xbt_graph_new_edge(routing->route_graph, node, node, &routing->loopback);
 790         }
 791 }
 792
 793 static void routing_dijkstra_parse_end(void) {
 794   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 795   int nb_link = 0;
 796   xbt_dict_cursor_t cursor = NULL;
 797   char *key, *data, *end;
 798   const char *sep = "#";
 799   xbt_dynar_t links, keys;
 800   char* link_name = NULL;
 801   void* link = NULL;
 802   xbt_node_t node = NULL;
 803   unsigned int cursor2;
 804   xbt_dynar_t nodes = NULL;
 805   /* Create the topology graph */
 806   routing->route_graph = xbt_graph_new_graph(1, NULL);
 807   routing->graph_node_map = xbt_dict_new();
 808   routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
 809   if(routing->cached)
 810     routing->route_cache = xbt_dict_new();
 811
 812
 813   /* Put the routes in position */
 814   xbt_dict_foreach(route_table, cursor, key, data) {
 815     nb_link = 0;
 816     links = (xbt_dynar_t) data;
 817     keys = xbt_str_split_str(key, sep);
 818
 819     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
 820     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
 821     xbt_dynar_free(&keys);
 822
 823     DEBUG4("Handle %d %d (from %d hosts): %ld links",
 824         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
 825
 826     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);
 827
 828     link_name = xbt_dynar_getfirst_as(links, char*);
 829     link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
 830     if (link)
 831       route_new_dijkstra(src_id,dst_id,link);
 832     else
 833       THROW1(mismatch_error,0,"Link %s not found", link_name);
 834
 835   }
 836
 837   /* Add the loopback if needed */
 838   add_loopback_dijkstra();
 839
 840   /* initialize graph indexes in nodes after graph has been built */
 841   nodes = xbt_graph_get_nodes(routing->route_graph);
 842
 843   xbt_dynar_foreach(nodes, cursor2, node) {
 844     graph_node_data_t data = xbt_graph_node_get_data(node);
 845     data->graph_id = cursor2;
 846   }
 847
 848 }
 849
 850 /*
 851  * Business methods
 852  */
 853 static xbt_dynar_t routing_dijkstra_get_route(int src_id,int dst_id) {
 854
 855   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 856   int * pred_arr = NULL;
 857   int src_node_id = 0;
 858   int dst_node_id = 0;
 859   int * nodeid = NULL;
 860   int v;
 861   int size = 0;
 862   void * link = NULL;
 863   route_cache_element_t elm = NULL;
 864   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
 865
 866   /*Use the graph_node id mapping set to quickly find the nodes */
 867   graph_node_map_element_t src_elm = graph_node_map_search(src_id);
 868   graph_node_map_element_t dst_elm = graph_node_map_search(dst_id);
 869   xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", src_id, dst_id);
 870   src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id;
 871   dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id;
 872
 873   if(routing->cached) {
 874     /*check if there is a cached predecessor list avail */
 875     elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int));
 876   }
 877
 878   if(elm) { //cached mode and cache hit
 879     pred_arr = elm->pred_arr;
 880   } else { //not cached mode or cache miss
 881     double * cost_arr = NULL;
 882     xbt_heap_t pqueue = NULL;
 883     int i = 0;
 884
 885     int nr_nodes = xbt_dynar_length(nodes);
 886     cost_arr = xbt_new0(double, nr_nodes); //link cost from src to other hosts
 887     pred_arr = xbt_new0(int, nr_nodes); //predecessors in path from src
 888     pqueue = xbt_heap_new(nr_nodes, free);
 889
 890     //initialize
 891     cost_arr[src_node_id] = 0.0;
 892
 893     for(i = 0; i < nr_nodes; i++) {
 894       if(i != src_node_id) {
 895         cost_arr[i] = DBL_MAX;
 896       }
 897
 898       pred_arr[i] = 0;
 899
 900       //initialize priority queue
 901       nodeid = xbt_new0(int, 1);
 902       *nodeid = i;
 903       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
 904
 905     }
 906
 907     // apply dijkstra using the indexes from the graph's node array
 908     while(xbt_heap_size(pqueue) > 0) {
 909       int * v_id = xbt_heap_pop(pqueue);
 910       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
 911       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
 912       xbt_edge_t edge = NULL;
 913       unsigned int cursor;
 914
 915       xbt_dynar_foreach(out_edges, cursor, edge) {
 916         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
 917         graph_node_data_t data = xbt_graph_node_get_data(u_node);
 918         int u_id = data->graph_id;
 919         int cost_v_u = 1; //fixed link cost for now
 920
 921         if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
 922           pred_arr[u_id] = *v_id;
 923           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
 924           nodeid = xbt_new0(int, 1);
 925           *nodeid = u_id;
 926           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
 927         }
 928       }
 929
 930       //free item popped from pqueue
 931       free(v_id);
 932     }
 933
 934     free(cost_arr);
 935     xbt_heap_free(pqueue);
 936
 937   }
 938
 939   //compose route path with links
 940   xbt_dynar_reset(routing->last_route);
 941
 942   for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
 943     xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
 944     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
 945     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
 946
 947     xbt_assert2(edge != NULL, "no route between host %d and %d", src_id, dst_id);
 948
 949     link = xbt_graph_edge_get_data(edge);
 950     xbt_dynar_unshift(routing->last_route, &link);
 951     size++;
 952   }
 953
 954
 955   if(routing->cached && elm == NULL) {
 956     //add to predecessor list of the current src-host to cache
 957     elm = xbt_new0(struct route_cache_element, sizeof(struct route_cache_element));
 958     elm->pred_arr = pred_arr;
 959     elm->size = size;
 960     xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free);
 961   }
 962
 963   if(!routing->cached)
 964     free(pred_arr);
 965
 966   return routing->last_route;
 967 }
 968
 969
 970 static void routing_dijkstra_finalize(void) {
 971   routing_dijkstra_t routing = (routing_dijkstra_t)used_routing;
 972
 973   if (routing) {
 974     xbt_graph_free_graph(routing->route_graph, &free, NULL, &free);
 975     xbt_dict_free(&routing->graph_node_map);
 976     if(routing->cached)
 977       xbt_dict_free(&routing->route_cache);
 978     xbt_dynar_free(&routing->last_route);
 979     xbt_dict_free(&used_routing->host_id);
 980     free(routing);
 981     routing=NULL;
 982   }
 983 }
 984
 985 static xbt_dict_t routing_dijkstraboth_get_onelink_routes(void){
 986   xbt_assert0(0,"The get_onelink_routes feature is not supported in routing model dijkstraboth");
 987 }
 988
 989 static int routing_dijkstraboth_is_router(int id){
 990   xbt_assert0(0,"The get_is_router feature is not supported in routing model dijkstraboth");
 991 }
 992
 993 /*
 994  *
 995  */
 996 static void routing_model_dijkstraboth_create(size_t size_of_link,void *loopback, int cached) {
 997   /* initialize our structure */
 998   routing_dijkstra_t routing = xbt_new0(s_routing_dijkstra_t,1);
 999   routing->generic_routing.name = "Dijkstra";
1000   routing->generic_routing.host_count = 0;
1001   routing->generic_routing.get_route = routing_dijkstra_get_route;
1002   routing->generic_routing.get_onelink_routes = routing_dijkstraboth_get_onelink_routes;
1003   routing->generic_routing.is_router = routing_dijkstraboth_is_router;
1004   routing->generic_routing.finalize = routing_dijkstra_finalize;
1005   routing->size_of_link = size_of_link;
1006   routing->loopback = loopback;
1007   routing->cached = cached;
1008
1009   /* Set it in position */
1010   used_routing = (routing_t) routing;
1011
1012   /* Setup the parsing callbacks we need */
1013   routing->generic_routing.host_id = xbt_dict_new();
1014   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
1015   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_dijkstra_parse_end);
1016   surfxml_add_callback(STag_surfxml_route_cb_list,
1017       &routing_full_parse_Sroute_set_endpoints);
1018   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
1019   surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_shortest_path_parse_Scluster);
1020 }
1021
1022 static void routing_model_dijkstra_create(size_t size_of_link,void *loopback) {
1023   routing_model_dijkstraboth_create(size_of_link, loopback, 0);
1024 }
1025
1026 static void routing_model_dijkstracache_create(size_t size_of_link,void *loopback) {
1027   routing_model_dijkstraboth_create(size_of_link, loopback, 1);
1028 }
1029
1030 /* ************************************************** */
1031 /* ********** NO ROUTING **************************** */
1032
1033
1034 static void routing_none_finalize(void) {
1035   if (used_routing) {
1036     xbt_dict_free(&used_routing->host_id);
1037     free(used_routing);
1038     used_routing=NULL;
1039   }
1040 }
1041
1042 static void routing_model_none_create(size_t size_of_link,void *loopback) {
1043   routing_t routing = xbt_new0(s_routing_t,1);
1044   routing->name = "none";
1045   routing->host_count = 0;
1046   routing->host_id = xbt_dict_new();
1047   routing->get_onelink_routes = NULL;
1048   routing->is_router = NULL;
1049   routing->get_route = NULL;
1050   routing->finalize = routing_none_finalize;
1051
1052   /* Set it in position */
1053   used_routing = (routing_t) routing;
1054 }
1055
1056 /* ************************************************************************** */
1057 /* *********************** HIERARCHICAL ROUTING ***************************** */
1058
1059 #define ROUTE_TABLE_HOST(dest,i,j)     (((*dest)->routing_table)[(i)+(j)*((*dest)->host_count)])
1060 #define ROUTE_H_TABLE_HOST(dest,i,j) (((*dest)->h_routing_table)[(i)+(j)*((*dest)->host_count)])
1061 #define ROUTE_V_TABLE_HOST(dest,i,j) (((*dest)->v_routing_table)[(i)+(j)*((*dest)->router_count)])
1062 #define ROUTE_TABLE_AS(dest,i,j)       (((*dest)->routing_table)[(i)+(j)*((*dest)->routetree_list->used)])
1063 #define ROUTE_H_TABLE_AS(dest,i,j)   (((*dest)->h_routing_table)[(i)+(j)*((*dest)->routetree_list->used)])
1064 #define ROUTE_V_TABLE_AS(dest,i,j)   (((*dest)->v_routing_table)[(i)+(j)*((*dest)->router_count)])
1065
1066 #define H2ID(rt,val)  (val-((*rt)->host_offset))
1067 #define R2ID(rt,val)  (val-((*rt)->router_offset))
1068 #define A2ID(val)     ((*val)->id_father)
1069
1070 #define HVALID(rt,val)  (          ((*rt)->host_count)>H2ID(rt,val) && H2ID(rt,val)=>0)
1071 #define RVALID(rt,val)  (        ((*rt)->router_count)>R2ID(rt,val) && R2ID(rt,val)=>0)
1072 #define AVALID(rt,val)  (((*rt)->routetree_list->used)>A2ID(val)    &&    A2ID(val)=>0)
1073
1074 #define ROUTE_HIERARCHICAL_HH(src,dst,rt)   (((*rt)->routing_table)[H2ID(rt,src)+H2ID(rt,dst)*((*rt)->host_count)])
1075 #define ROUTE_HIERARCHICAL_HR(src,dst,rt) (((*rt)->h_routing_table)[H2ID(rt,src)+R2ID(rt,dst)*((*rt)->host_count)])
1076 #define ROUTE_HIERARCHICAL_RH(src,dst,rt) (((*rt)->v_routing_table)[R2ID(rt,src)+H2ID(rt,dst)*((*rt)->router_count)])
1077 #define ROUTE_HIERARCHICAL_AA(src,dst,rt)   (((*rt)->routing_table)[A2ID(   src)+A2ID(   dst)*((*rt)->routetree_list->used)])
1078 #define ROUTE_HIERARCHICAL_AR(src,dst,rt) (((*rt)->h_routing_table)[A2ID(   src)+R2ID(rt,dst)*((*rt)->routetree_list->used)])
1079 #define ROUTE_HIERARCHICAL_RA(src,dst,rt) (((*rt)->v_routing_table)[R2ID(rt,src)+A2ID(   dst)*((*rt)->router_count)])
1080
1081 #define SRC_DST_HIERARCHICAL_AA(src,dst,rt)   ((routelimits_t)&(((*rt)->src_dst_table)[A2ID(   src)+A2ID(   dst)*((*rt)->routetree_list->used)]))
1082 #define SRC_DST_HIERARCHICAL_AR(src,dst,rt) ((routelimits_t)&(((*rt)->h_src_dst_table)[A2ID(   src)+R2ID(rt,dst)*((*rt)->routetree_list->used)]))
1083 #define SRC_DST_HIERARCHICAL_RA(src,dst,rt) ((routelimits_t)&(((*rt)->v_src_dst_table)[R2ID(rt,src)+A2ID(   dst)*((*rt)->router_count)]))
1084
1085 /* for the calculus of locals ids */
1086 int local_host_count;
1087 int local_router_count;
1088
1089 /*####[ Type definition ]####################################################*/
1090
1091 typedef struct routelimits_ {
1092     int src_id;         /* source router  */
1093     int dst_id;         /* destine router */
1094 } s_routelimits_t, *routelimits_t;
1095
1096 typedef struct routetree_ {
1097     const char* name;              /* name of the set */
1098     struct routetree_* father;     /* father set */
1099     int id_father;                 /* id in the father set */
1100     int host_count;                /* count of host in the set */
1101     int router_count;              /* count of router in the set */
1102     int host_offset;               /* offset for the host id */
1103     int router_offset;             /* offset for the router id */
1104     xbt_dynar_t routetree_list;    /* other sets in the set */
1105     xbt_dynar_t *routing_table;    /* host-host or AS-AS */
1106     xbt_dynar_t *h_routing_table;  /* host-router or AS-router */
1107     xbt_dynar_t *v_routing_table;  /* router-host or router-AS */
1108     routelimits_t src_dst_table;   /* src and dst for routing table */
1109     routelimits_t h_src_dst_table; /* src and dst for h routing table */
1110     routelimits_t v_src_dst_table; /* src and dst for v routing table */
1111 } s_routetree_t, *routetree_t;
1112
1113 typedef struct routing_hierarchical_t {
1114   s_routing_t generic_routing;
1115   routetree_t routetree;
1116   xbt_dynar_t host_routetree; /* routetree_t* */
1117   xbt_dynar_t last_route;     /* store the last routing path */
1118   void *loopback;
1119   size_t size_of_link;
1120 } s_routing_hierarchical_t,*routing_hierarchical_t;
1121
1122 /*####[ routetree functions ]################################################*/
1123
1124 /* @brief Constructor */
1125 routetree_t routetree_new(void) {
1126   routetree_t res = xbt_new(s_routetree_t, 1);
1127   res->name             = NULL;
1128   res->father           = NULL;
1129   res->id_father        = 0;
1130   res->host_count       = 0;
1131   res->router_count     = 0;
1132   res->host_offset      = 0;
1133   res->router_offset    = 0;
1134   res->routetree_list   = NULL;
1135   res->routing_table    = NULL;
1136   res->h_routing_table  = NULL;
1137   res->v_routing_table  = NULL;
1138   res->src_dst_table   = NULL;
1139   res->v_src_dst_table = NULL;
1140   res->h_src_dst_table = NULL;
1141   return res;
1142 }
1143
1144 /* @brief Destructor */
1145 void routetree_free(routetree_t* routetree) {
1146   unsigned int it;
1147   int i,j,ni,nj;
1148   int size_host_list = 0, size_router_list = 0, size_routetree_list = 0;
1149   int size_of_link = ((routing_hierarchical_t)used_routing)->size_of_link;
1150   routetree_t elem;
1151
1152   if (*routetree) {
1153     size_host_list = (*routetree)->host_count;
1154     size_router_list = (*routetree)->router_count;
1155     if( (*routetree)->routetree_list ) size_routetree_list = ((*routetree)->routetree_list)->used;
1156
1157     if( size_host_list == 0 && size_routetree_list == 0 ) {
1158       return;
1159     }
1160     else if( size_host_list > 0 && size_routetree_list == 0 ) {
1161       /* create a host table */
1162       ni = size_host_list;
1163       nj = size_host_list;
1164       if(ni*nj > 1) {
1165        for (i=0;i<ni;i++)
1166          for (j=0;j<nj;j++)
1167              if( &ROUTE_TABLE_HOST(routetree,i,j) )
1168                xbt_dynar_free( &ROUTE_TABLE_HOST(routetree,i,j) );
1169       xbt_free( (*routetree)->routing_table );
1170       }
1171       /* create a host vs router table */
1172       ni = size_host_list;
1173       nj = size_router_list;
1174       if(ni*nj) {
1175       for (i=0;i<ni;i++)
1176         for (j=0;j<nj;j++)
1177              if( &ROUTE_H_TABLE_HOST(routetree,i,j) )
1178                xbt_dynar_free( &ROUTE_H_TABLE_HOST(routetree,i,j) );
1179       xbt_free( (*routetree)->h_routing_table );
1180       }
1181       /* create a router vs host table */
1182       ni = size_router_list;
1183       nj = size_host_list;
1184       if(ni*nj) {
1185       for (i=0;i<ni;i++)
1186         for (j=0;j<nj;j++)
1187              if( &ROUTE_V_TABLE_HOST(routetree,i,j) )
1188                xbt_dynar_free( &ROUTE_V_TABLE_HOST(routetree,i,j) );
1189       xbt_free( (*routetree)->v_routing_table );
1190       }
1191     }
1192     else if( size_host_list == 0 && size_routetree_list > 0 ) {
1193       /* create a host table */
1194       ni = size_routetree_list;
1195       nj = size_routetree_list;
1196       if(ni*nj > 1) {
1197       for (i=0;i<ni;i++)
1198         for (j=0;j<nj;j++)
1199              if( &ROUTE_TABLE_AS(routetree,i,j) )
1200                xbt_dynar_free( &ROUTE_TABLE_AS(routetree,i,j) );
1201       xbt_free( (*routetree)->src_dst_table );
1202       xbt_free( (*routetree)->routing_table );
1203       }
1204       /* create a host vs router table */
1205       ni = size_routetree_list;
1206       nj = size_router_list;
1207       if(ni*nj) {
1208       for (i=0;i<ni;i++)
1209         for (j=0;j<nj;j++)
1210              if( &ROUTE_H_TABLE_AS(routetree,i,j) )
1211                xbt_dynar_free( &ROUTE_H_TABLE_AS(routetree,i,j) );
1212       xbt_free( (*routetree)->h_src_dst_table );
1213       xbt_free( (*routetree)->h_routing_table );
1214       }
1215       /* create a router vs host table */
1216       ni = size_router_list;
1217       nj = size_routetree_list;
1218       if(ni*nj) {
1219       for (i=0;i<ni;i++)
1220         for (j=0;j<nj;j++)
1221              if( &ROUTE_V_TABLE_AS(routetree,i,j) )
1222                xbt_dynar_free( &ROUTE_V_TABLE_AS(routetree,i,j) );
1223       xbt_free( (*routetree)->v_src_dst_table );
1224       xbt_free( (*routetree)->v_routing_table );
1225       }
1226     }
1227     else {
1228       xbt_assert0(0,"The autonomous system must have hosts or autonomous systems, not the both");
1229     }
1230
1231     if ((*routetree)->routetree_list) {
1232       xbt_dynar_foreach((*routetree)->routetree_list,it,elem) {
1233          routetree_free(&elem);}
1234       xbt_dynar_free(&((*routetree)->routetree_list));
1235     }
1236     free(*routetree);
1237     *routetree = NULL;
1238
1239   }
1240 }
1241
1242 /* @brief Add a host to routetree */
1243 void routetree_add_host(const char* name, routetree_t* dest) {
1244   int* val;
1245   val = xbt_malloc(sizeof(int));
1246   /* count the new host */
1247   //*val = used_routing->host_count++;
1248   *val = local_host_count++;
1249   /* add the host to the dictonary */
1250   xbt_dict_set(used_routing->host_id,name,val,xbt_free);
1251   /* add the host to the routetree traduction vector */
1252   xbt_dynar_push(((routing_hierarchical_t)used_routing)->host_routetree,dest);
1253   /* add a local count for the routetree */
1254   (*dest)->host_count++;
1255 }
1256
1257 /* @brief Add a router to routetree */
1258 void routetree_add_router(const char* name, routetree_t* dest) {
1259   int* val;
1260   val = xbt_malloc(sizeof(int));
1261   /* count the new host */
1262   //*val = HOST2ROUTER(used_routing->router_count++);
1263   *val = HOST2ROUTER(local_router_count++);
1264   /* add the host to the dictonary */
1265   xbt_dict_set(used_routing->host_id,name,val,xbt_free);
1266   /* add a local count for the routetree */
1267   (*dest)->router_count++;
1268 }
1269
1270 /* @brief Add a child routetree to routetree father */
1271 void routetree_add(routetree_t* dest, routetree_t* elem) {
1272   xbt_dynar_push((*dest)->routetree_list, elem);
1273 }
1274
1275 void routetree_fill(routetree_t* dest, const char* name, routetree_t father, int id_father) {
1276   (*dest)->name             = name;
1277   (*dest)->father           = father;
1278   (*dest)->id_father        = id_father;
1279   (*dest)->host_count       = 0;
1280   (*dest)->router_count     = 0;
1281   (*dest)->host_offset      = local_host_count;
1282   (*dest)->router_offset    = local_router_count;
1283   (*dest)->routetree_list   = xbt_dynar_new(sizeof(routetree_t), NULL);
1284   (*dest)->routing_table    = NULL;
1285   (*dest)->v_routing_table  = NULL;
1286   (*dest)->h_routing_table  = NULL;
1287   (*dest)->src_dst_table    = NULL;
1288   (*dest)->v_src_dst_table  = NULL;
1289   (*dest)->h_src_dst_table  = NULL;
1290 }
1291
1292 /* @brief Make the routing tables for a empty routetree */
1293 void routetree_fill_routing_table(routetree_t* dest) {
1294
1295   int i,j,ni,nj;
1296   int size_host_list = 0, size_router_list = 0, size_routetree_list = 0;
1297   int size_of_link = ((routing_hierarchical_t)used_routing)->size_of_link;
1298   size_host_list = (*dest)->host_count;
1299   size_router_list = (*dest)->router_count;
1300   if( (*dest)->routetree_list ) size_routetree_list = ((*dest)->routetree_list)->used;
1301
1302   if( size_host_list == 0 && size_routetree_list == 0 ) {
1303     return;
1304   }
1305   else if( size_host_list > 0 && size_routetree_list == 0 ) {
1306     /* create a host table */
1307     ni = size_host_list;
1308     nj = size_host_list;
1309     if(ni*nj) {
1310     (*dest)->routing_table = xbt_new0(xbt_dynar_t, ni * nj);
1311     for (i=0;i<ni;i++)
1312       for (j=0;j<nj;j++)
1313           ROUTE_TABLE_HOST(dest,i,j) = xbt_dynar_new(size_of_link,NULL);
1314     }
1315     /* create a host vs router table */
1316     ni = size_host_list;
1317     nj = size_router_list;
1318     if(ni*nj) {
1319     (*dest)->h_routing_table = xbt_new0(xbt_dynar_t, ni * nj);
1320     for (i=0;i<ni;i++)
1321       for (j=0;j<nj;j++)
1322           ROUTE_H_TABLE_HOST(dest,i,j) = xbt_dynar_new(size_of_link,NULL);
1323     }
1324     /* create a router vs host table */
1325     ni = size_router_list;
1326     nj = size_host_list;
1327     if(ni*nj) {
1328     (*dest)->v_routing_table = xbt_new0(xbt_dynar_t, ni * nj);
1329     for (i=0;i<ni;i++)
1330       for (j=0;j<nj;j++)
1331           ROUTE_V_TABLE_HOST(dest,i,j) = xbt_dynar_new(size_of_link,NULL);
1332     }
1333   }
1334   else if( size_host_list == 0 && size_routetree_list > 0 ) {
1335     /* create a host table */
1336     ni = size_routetree_list;
1337     nj = size_routetree_list;
1338     if(ni*nj > 1) {
1339     (*dest)->src_dst_table = xbt_new0(s_routelimits_t, ni * nj);
1340     (*dest)->routing_table = xbt_new0(xbt_dynar_t, ni * nj);
1341     for (i=0;i<ni;i++)
1342       for (j=0;j<nj;j++)
1343         ROUTE_TABLE_AS(dest,i,j) = xbt_dynar_new(size_of_link,NULL);
1344     }
1345     /* create a host vs router table */
1346     ni = size_routetree_list;
1347     nj = size_router_list;
1348     if(ni*nj) {
1349     (*dest)->h_src_dst_table = xbt_new0(s_routelimits_t, ni * nj);
1350     (*dest)->h_routing_table = xbt_new0(xbt_dynar_t, ni * nj);
1351     for (i=0;i<ni;i++)
1352       for (j=0;j<nj;j++)
1353           ROUTE_H_TABLE_AS(dest,i,j) = xbt_dynar_new(size_of_link,NULL);
1354     }
1355     /* create a router vs host table */
1356     ni = size_router_list;
1357     nj = size_routetree_list;
1358     if(ni*nj) {
1359     (*dest)->v_src_dst_table = xbt_new0(s_routelimits_t, ni * nj);
1360     (*dest)->v_routing_table = xbt_new0(xbt_dynar_t, ni * nj);
1361     for (i=0;i<ni;i++)
1362       for (j=0;j<nj;j++)
1363           ROUTE_V_TABLE_AS(dest,i,j) = xbt_dynar_new(size_of_link,NULL);
1364     }
1365   }
1366   else {
1367     xbt_assert0(0,"The autonomous system must have hosts or autonomous systems, not the both");
1368   }
1369 }
1370
1371 ////////////////////////////
1372 // PARSER CODE HERE
1373 ////////////////////////////
1374
1375
1376 /////////////
1377 // is coming ...
1378 /////////////
1379
1380
1381 /*
1382  * Business methods
1383  */
1384 static xbt_dynar_t routing_hierarchical_get_route(int src,int dst) {
1385
1386   routing_hierarchical_t routing = (routing_hierarchical_t)used_routing;
1387   routetree_t* rt_src = NULL;
1388   routetree_t* rt_dst = NULL;
1389   routetree_t* actual = NULL;
1390   xbt_dynar_t path_src = NULL;
1391   xbt_dynar_t path_dst = NULL;
1392   xbt_dynar_t path_first = NULL;
1393   xbt_dynar_t path_last = NULL;
1394   int cpt = 0;
1395   int *val;
1396   int index_src;
1397   int index_dst;
1398   int index_father_src;
1399   int index_father_dst;
1400   int actual_router_src;
1401   int actual_router_dst;
1402   routetree_t* actual_src;
1403   routetree_t* actual_dst;
1404   routetree_t* actual_src_father;
1405   routetree_t* actual_dst_father;
1406   routetree_t* father;
1407   xbt_dynar_t result;
1408   xbt_dynar_t path_tmp_links;
1409   xbt_dynar_t path_center_links;
1410   xbt_dynar_t path_src_links;
1411   xbt_dynar_t path_dst_links;
1412   void* link;
1413
1414   xbt_dynar_reset(routing->last_route);
1415
1416   // (0) test for routers ids
1417   xbt_assert0(!(ISROUTER(src) || ISROUTER(dst)), "Ask for route \"from\" or \"to\" a router node");
1418
1419   // (1) find the as-routetree where the src and dst are located
1420   rt_src = xbt_dynar_get_ptr(routing->host_routetree,src);
1421   rt_dst = xbt_dynar_get_ptr(routing->host_routetree,dst);
1422
1423   // (2) find the path to the root routetree
1424   path_src = xbt_dynar_new(sizeof(routetree_t), NULL);
1425   actual = rt_src;
1426   while( *actual != NULL ) {
1427     xbt_dynar_push(path_src,actual);
1428     actual = &((*actual)->father);
1429   }
1430   path_dst = xbt_dynar_new(sizeof(routetree_t), NULL);
1431   actual = rt_dst;
1432   while( *actual != NULL ) {
1433     xbt_dynar_push(path_dst,actual);
1434     actual = &((*actual)->father);
1435   }
1436
1437   // (3) find the common father
1438   index_src  = (path_src->used)-1;
1439   index_dst  = (path_dst->used)-1;
1440   actual_src = xbt_dynar_get_ptr(path_src,index_src);
1441   actual_dst = xbt_dynar_get_ptr(path_dst,index_dst);
1442   while( index_src >= 0 && index_dst >= 0 && *actual_src == *actual_dst ) {
1443     actual_src = xbt_dynar_get_ptr(path_src,index_src);
1444     actual_dst = xbt_dynar_get_ptr(path_dst,index_dst);
1445     index_src--;
1446     index_dst--;
1447   }
1448   index_src++;
1449   index_dst++;
1450   actual_src = xbt_dynar_get_ptr(path_src,index_src);
1451   actual_dst = xbt_dynar_get_ptr(path_dst,index_dst);
1452
1453   // (4) if they are in the same routetree?
1454   if( *actual_src == *actual_dst ) {
1455
1456     // (5.1) belong to the same routetree, are in the same routing table
1457     // even if are the same host, src and dst
1458     path_tmp_links = ROUTE_HIERARCHICAL_HH(src,dst,actual_src);
1459     cpt = 0;
1460     xbt_dynar_foreach(path_tmp_links, cpt, link) {
1461       xbt_dynar_push(routing->last_route,&link);
1462     }
1463
1464   }
1465   else {
1466
1467     // (5.2) they are not in the same routetree, make the path
1468     index_father_src = index_src+1;
1469     index_father_dst = index_dst+1;
1470     father = xbt_dynar_get_ptr(path_src,index_father_src);
1471     path_center_links = ROUTE_HIERARCHICAL_AA(actual_src,actual_dst,father);
1472     routelimits_t limits = SRC_DST_HIERARCHICAL_AA(actual_src,actual_dst,father);
1473
1474     // (5.2.1) make the source path
1475      path_src_links = xbt_dynar_new(routing->size_of_link, NULL);
1476      actual_router_dst = ROUTER2HOST(limits->src_id); /* first router in the reverse path */
1477      actual_src_father = xbt_dynar_get_ptr(path_src,index_src);
1478      index_src--;
1479      for(index_src;index_src>=0;index_src--) {
1480        actual_src = xbt_dynar_get_ptr(path_src,index_src);
1481        path_tmp_links = ROUTE_HIERARCHICAL_AR(actual_src,actual_router_dst,actual_src_father);
1482        cpt = 0;
1483        xbt_dynar_foreach(path_tmp_links, cpt, link) {
1484          xbt_assert2(link!=NULL,"NULL link in the route from src %d to dst %d (5.2.1)", src, dst);
1485          xbt_dynar_push(path_src_links,&link);
1486        }
1487        actual_router_dst = ROUTER2HOST(SRC_DST_HIERARCHICAL_AR(actual_src,actual_router_dst,actual_src_father)->src_id);
1488        actual_src_father = actual_src;
1489      }
1490
1491     // (5.2.2) make the destination path
1492      path_dst_links = xbt_dynar_new(routing->size_of_link, NULL);
1493      actual_router_src = ROUTER2HOST(limits->dst_id); /* first router for the path */
1494      actual_dst_father = xbt_dynar_get_ptr(path_dst,index_dst);
1495      index_dst--;
1496      for(index_dst;index_dst>=0;index_dst--) {
1497        actual_dst = xbt_dynar_get_ptr(path_dst,index_dst);
1498        path_tmp_links = ROUTE_HIERARCHICAL_RA(actual_router_src,actual_dst,actual_dst_father);
1499        cpt = 0;
1500        xbt_dynar_foreach(path_tmp_links, cpt, link) {
1501          xbt_assert2(link!=NULL,"NULL link in the route from src %d to dst %d (5.2.2)", src, dst);
1502          xbt_dynar_push(path_dst_links,&link);
1503        }
1504        actual_router_src = ROUTER2HOST(SRC_DST_HIERARCHICAL_RA(actual_router_src,actual_dst,actual_dst_father)->dst_id);
1505        actual_dst_father = actual_dst;
1506      }
1507
1508     // (5.2.3) the first part of the route
1509     path_first = ROUTE_HIERARCHICAL_HR(src,actual_router_dst,actual_src);
1510
1511     // (5.2.4) the last part of the route
1512     path_last = ROUTE_HIERARCHICAL_RH(actual_router_src,dst,actual_dst);
1513
1514     // (5.2.5) make all paths together
1515     // FIXME: the paths non respect the right order
1516
1517     cpt = 0;
1518     xbt_dynar_foreach(path_first, cpt, link) {
1519       xbt_assert2(link!=NULL,"NULL link in the route from src %d to dst %d", src, dst);
1520       xbt_dynar_push(routing->last_route,&link);
1521     }
1522     cpt = 0;
1523     xbt_dynar_foreach(path_src_links, cpt, link) {
1524       xbt_assert2(link!=NULL,"NULL link in the route from src %d to dst %d", src, dst);
1525       xbt_dynar_push(routing->last_route,&link);
1526     }
1527     cpt = 0;
1528     xbt_dynar_foreach(path_center_links, cpt, link) {
1529       xbt_assert2(link!=NULL,"NULL link in the route from src %d to dst %d", src, dst);
1530       xbt_dynar_push(routing->last_route,&link);
1531     }
1532     cpt = 0;
1533     xbt_dynar_foreach(path_dst_links, cpt, link) {
1534       xbt_assert2(link!=NULL,"NULL link in the route from src %d to dst %d", src, dst);
1535       xbt_dynar_push(routing->last_route,&link);
1536     }
1537     cpt = 0;
1538     xbt_dynar_foreach(path_last, cpt, link) {
1539       xbt_assert2(link!=NULL,"NULL link in the route from src %d to dst %d", src, dst);
1540       xbt_dynar_push(routing->last_route,&link);
1541     }
1542
1543     xbt_dynar_free(&path_src_links);
1544     xbt_dynar_free(&path_dst_links);
1545   }
1546
1547   xbt_dynar_free(&path_src);
1548   xbt_dynar_free(&path_dst);
1549
1550 //   cpt=0;
1551 //   xbt_dynar_foreach(routing->last_route, cpt, link)
1552 //   { s_surf_resource_t* generic_resource = link;
1553 //   printf("< LINK > link %s\n",generic_resource->name); }
1554
1555   return(routing->last_route);
1556 }
1557
1558 static xbt_dict_t routing_hierarchical_get_onelink_routes(void){
1559   xbt_assert0(0,"The get_onelink_routes feature is not supported in routing model Hierarchical");
1560 }
1561
1562 static int routing_hierarchical_is_router(int id){
1563    return ISROUTER(id);
1564 }
1565
1566 static void routing_hierarchical_finalize(void) {
1567   routing_hierarchical_t routing = (routing_hierarchical_t)used_routing;
1568   if(routing) {
1569     xbt_dict_free(&used_routing->host_id);
1570     routetree_free(&(routing->routetree));
1571     xbt_dynar_free(&(routing->host_routetree));
1572     xbt_dynar_free(&routing->last_route);
1573     xbt_free(routing);
1574     routing=NULL;
1575   }
1576 }
1577
1578 // void print_tree(routetree_t start)
1579 // {
1580 //   int data;
1581 //   unsigned int it;
1582 //   routetree_t elem;
1583 //
1584 //   printf("Nombre %s - hosts %i - routers %i - as %i\n",
1585 //       start->name,
1586 //       (int)start->host_count,
1587 //       (int)start->router_count,
1588 //       (int)start->routetree_list->used);
1589 // /*
1590 //   printf("hosts:");
1591 //   xbt_dynar_foreach(start->host_list,it,data) {
1592 //     printf(" %i",data);
1593 //   }
1594 //   printf("\n");
1595 //
1596 //   printf("routers:");
1597 //   xbt_dynar_foreach(start->router_list,it,data) {
1598 //     printf(" %i",ROUTER2HOST(data));
1599 //   }
1600 //   printf("\n");
1601 //   */
1602 //   xbt_dynar_foreach(start->routetree_list,it,elem) {
1603 //     print_tree(elem);
1604 //   }
1605 // }
1606
1607 /* erase me */
1608 // The following function makes a example as if a paser program would do it.
1609 static void example() {
1610
1611   int nb_link = 0;
1612   unsigned int cpt = 0;
1613   xbt_dict_cursor_t cursor = NULL;
1614   char *key, *data, *end;
1615   const char *sep = "#";
1616   xbt_dynar_t links, keys;
1617   char *link_name = NULL;
1618
1619   routetree_t tmp1,tmp2,tmp3,tmp4,tmp5; // erase me
1620   int *val;                             // erase me
1621   int i,j,n;                            // erase me
1622   void* link;                           // erase me
1623
1624 routing_hierarchical_t routing = (routing_hierarchical_t)used_routing;
1625
1626 /////////// fixed network /////////////
1627
1628 /////////// make the routetree tree /////////////
1629
1630         routing->routetree = routetree_new();
1631         routetree_fill(&(routing->routetree),"as1",NULL,0);
1632
1633                 tmp2 = routetree_new();
1634                 routetree_fill(&(tmp2),"as2",(routing->routetree),0);
1635                 //hosts
1636                 //router
1637                 routetree_add_router("R21",&tmp2);
1638                 routetree_add_router("R22",&tmp2);
1639                 // add
1640                 routetree_add(&(routing->routetree),&tmp2);
1641
1642                         tmp3 = routetree_new();
1643                         routetree_fill(&(tmp3),"as3",(tmp2),0);
1644                         //hosts
1645                         routetree_add_host("A",&tmp3);
1646                         routetree_add_host("B",&tmp3);
1647                         //router
1648                         routetree_add_router("R31",&tmp3);
1649                         routetree_add_router("R32",&tmp3);
1650                         // add
1651                         routetree_add(&(tmp2),&tmp3);
1652
1653                 tmp4 = routetree_new();
1654                 routetree_fill(&(tmp4),"as4",(routing->routetree),1);
1655                 //hosts
1656                 routetree_add_host("C",&tmp4);
1657                 routetree_add_host("D",&tmp4);
1658                 routetree_add_host("E",&tmp4);
1659                 //router
1660                 routetree_add_router("R41",&tmp4);
1661                 routetree_add_router("R42",&tmp4);
1662                 // add
1663                 routetree_add(&(routing->routetree),&tmp4);
1664
1665                 tmp5 = routetree_new();
1666                 routetree_fill(&(tmp5),"as5",(routing->routetree),2);
1667                 //hosts
1668                 routetree_add_host("F",&tmp5);
1669                 //router
1670                 routetree_add_router("R51",&tmp5);
1671                 // add
1672                 routetree_add(&(routing->routetree),&tmp5);
1673
1674 /////////// fill the routing tables /////////////
1675
1676   routetree_fill_routing_table(&(routing->routetree));
1677   routetree_fill_routing_table(&(tmp2));
1678   routetree_fill_routing_table(&(tmp3));
1679   routetree_fill_routing_table(&(tmp4));
1680   routetree_fill_routing_table(&(tmp5));
1681
1682 /////////// fill the routing tables with the routes /////////////
1683
1684   // as2 - as4
1685   link = xbt_dict_get_or_null(surf_network_model->resource_set, "0"); xbt_assert0(link!=NULL,"NULL");
1686   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp2,&tmp4,&(routing->routetree)),&link);
1687   link = xbt_dict_get_or_null(surf_network_model->resource_set, "1"); xbt_assert0(link!=NULL,"NULL");
1688   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp2,&tmp4,&(routing->routetree)),&link);
1689   SRC_DST_HIERARCHICAL_AA(&tmp2,&tmp4,&(routing->routetree))->src_id = HOST2ROUTER(0); //r21
1690   SRC_DST_HIERARCHICAL_AA(&tmp2,&tmp4,&(routing->routetree))->dst_id = HOST2ROUTER(4); //r41
1691   // as4 - as2
1692   link = xbt_dict_get_or_null(surf_network_model->resource_set, "0"); xbt_assert0(link!=NULL,"NULL");
1693   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp4,&tmp2,&(routing->routetree)),&link);
1694   link = xbt_dict_get_or_null(surf_network_model->resource_set, "1"); xbt_assert0(link!=NULL,"NULL");
1695   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp4,&tmp2,&(routing->routetree)),&link);
1696   SRC_DST_HIERARCHICAL_AA(&tmp4,&tmp2,&(routing->routetree))->src_id = HOST2ROUTER(4); //r41
1697   SRC_DST_HIERARCHICAL_AA(&tmp4,&tmp2,&(routing->routetree))->dst_id = HOST2ROUTER(0); //r21
1698
1699   // as2 - as5
1700   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1701   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp2,&tmp5,&(routing->routetree)),&link);
1702   link = xbt_dict_get_or_null(surf_network_model->resource_set, "3"); xbt_assert0(link!=NULL,"NULL");
1703   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp2,&tmp5,&(routing->routetree)),&link);
1704   SRC_DST_HIERARCHICAL_AA(&tmp2,&tmp5,&(routing->routetree))->src_id = HOST2ROUTER(1); //r22
1705   SRC_DST_HIERARCHICAL_AA(&tmp2,&tmp5,&(routing->routetree))->dst_id = HOST2ROUTER(6); //r51
1706   // as5 - as2
1707   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1708   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp5,&tmp2,&(routing->routetree)),&link);
1709   link = xbt_dict_get_or_null(surf_network_model->resource_set, "3"); xbt_assert0(link!=NULL,"NULL");
1710   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp5,&tmp2,&(routing->routetree)),&link);
1711   SRC_DST_HIERARCHICAL_AA(&tmp5,&tmp2,&(routing->routetree))->src_id = HOST2ROUTER(6); //r51
1712   SRC_DST_HIERARCHICAL_AA(&tmp5,&tmp2,&(routing->routetree))->dst_id = HOST2ROUTER(1); //r22
1713
1714   // as4 - as5
1715   link = xbt_dict_get_or_null(surf_network_model->resource_set, "4"); xbt_assert0(link!=NULL,"NULL");
1716   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp4,&tmp5,&(routing->routetree)),&link);
1717   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1718   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp4,&tmp5,&(routing->routetree)),&link);
1719   SRC_DST_HIERARCHICAL_AA(&tmp4,&tmp5,&(routing->routetree))->src_id = HOST2ROUTER(5); //r42
1720   SRC_DST_HIERARCHICAL_AA(&tmp4,&tmp5,&(routing->routetree))->dst_id = HOST2ROUTER(6); //r51
1721   // as5 - as4
1722   link = xbt_dict_get_or_null(surf_network_model->resource_set, "4"); xbt_assert0(link!=NULL,"NULL");
1723   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp5,&tmp4,&(routing->routetree)),&link);
1724   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1725   xbt_dynar_push(ROUTE_HIERARCHICAL_AA(&tmp5,&tmp4,&(routing->routetree)),&link);
1726   SRC_DST_HIERARCHICAL_AA(&tmp5,&tmp4,&(routing->routetree))->src_id = HOST2ROUTER(6); //r51
1727   SRC_DST_HIERARCHICAL_AA(&tmp5,&tmp4,&(routing->routetree))->dst_id = HOST2ROUTER(5); //r42
1728
1729 // tmp2
1730
1731   // as3 - r21
1732   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1733   xbt_dynar_push(ROUTE_HIERARCHICAL_AR(&tmp3,0,&tmp2),&link);
1734   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1735   xbt_dynar_push(ROUTE_HIERARCHICAL_AR(&tmp3,0,&tmp2),&link);
1736   SRC_DST_HIERARCHICAL_AR(&tmp3,0,&tmp2)->src_id = HOST2ROUTER(2); //r31
1737   SRC_DST_HIERARCHICAL_AR(&tmp3,0,&tmp2)->dst_id = HOST2ROUTER(0); //r21
1738   // r21 - as3
1739   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1740   xbt_dynar_push(ROUTE_HIERARCHICAL_RA(0,&tmp3,&tmp2),&link);
1741   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1742   xbt_dynar_push(ROUTE_HIERARCHICAL_RA(0,&tmp3,&tmp2),&link);
1743   SRC_DST_HIERARCHICAL_RA(0,&tmp3,&tmp2)->src_id = HOST2ROUTER(0); //r21
1744   SRC_DST_HIERARCHICAL_RA(0,&tmp3,&tmp2)->dst_id = HOST2ROUTER(2); //r31
1745
1746   // as3 - r22
1747   link = xbt_dict_get_or_null(surf_network_model->resource_set, "3"); xbt_assert0(link!=NULL,"NULL");
1748   xbt_dynar_push(ROUTE_HIERARCHICAL_AR(&tmp3,1,&tmp2),&link);
1749   link = xbt_dict_get_or_null(surf_network_model->resource_set, "1"); xbt_assert0(link!=NULL,"NULL");
1750   xbt_dynar_push(ROUTE_HIERARCHICAL_AR(&tmp3,1,&tmp2),&link);
1751   SRC_DST_HIERARCHICAL_AR(&tmp3,1,&tmp2)->src_id = HOST2ROUTER(3); //r32
1752   SRC_DST_HIERARCHICAL_AR(&tmp3,1,&tmp2)->dst_id = HOST2ROUTER(1); //r22
1753   // r22 - as3
1754   link = xbt_dict_get_or_null(surf_network_model->resource_set, "3"); xbt_assert0(link!=NULL,"NULL");
1755   xbt_dynar_push(ROUTE_HIERARCHICAL_RA(1,&tmp3,&tmp2),&link);
1756   link = xbt_dict_get_or_null(surf_network_model->resource_set, "1"); xbt_assert0(link!=NULL,"NULL");
1757   xbt_dynar_push(ROUTE_HIERARCHICAL_RA(1,&tmp3,&tmp2),&link);
1758   SRC_DST_HIERARCHICAL_RA(1,&tmp3,&tmp2)->src_id = HOST2ROUTER(1); //r22
1759   SRC_DST_HIERARCHICAL_RA(1,&tmp3,&tmp2)->dst_id = HOST2ROUTER(3); //r32
1760
1761 // tmp3
1762
1763   // a - b
1764   link = xbt_dict_get_or_null(surf_network_model->resource_set, "7"); xbt_assert0(link!=NULL,"NULL");
1765   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(0,1,&tmp3),&link);
1766   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1767   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(0,1,&tmp3),&link);
1768   // b - a
1769   link = xbt_dict_get_or_null(surf_network_model->resource_set, "7"); xbt_assert0(link!=NULL,"NULL");
1770   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(1,0,&tmp3),&link);
1771   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1772   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(1,0,&tmp3),&link);
1773
1774   // a - r31
1775   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1776   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(0,2,&tmp3),&link);
1777   link = xbt_dict_get_or_null(surf_network_model->resource_set, "1"); xbt_assert0(link!=NULL,"NULL");
1778   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(0,2,&tmp3),&link);
1779   // a - r32
1780   link = xbt_dict_get_or_null(surf_network_model->resource_set, "8"); xbt_assert0(link!=NULL,"NULL");
1781   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(0,3,&tmp3),&link);
1782   link = xbt_dict_get_or_null(surf_network_model->resource_set, "7"); xbt_assert0(link!=NULL,"NULL");
1783   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(0,3,&tmp3),&link);
1784   // b - r31
1785   link = xbt_dict_get_or_null(surf_network_model->resource_set, "3"); xbt_assert0(link!=NULL,"NULL");
1786   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(1,2,&tmp3),&link);
1787   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1788   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(1,2,&tmp3),&link);
1789   // b - r32
1790   link = xbt_dict_get_or_null(surf_network_model->resource_set, "9"); xbt_assert0(link!=NULL,"NULL");
1791   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(1,3,&tmp3),&link);
1792   link = xbt_dict_get_or_null(surf_network_model->resource_set, "3"); xbt_assert0(link!=NULL,"NULL");
1793   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(1,3,&tmp3),&link);
1794
1795    // r31 - a
1796   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1797   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(2,0,&tmp3),&link);
1798   link = xbt_dict_get_or_null(surf_network_model->resource_set, "1"); xbt_assert0(link!=NULL,"NULL");
1799   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(2,0,&tmp3),&link);
1800   // r32 - a
1801   link = xbt_dict_get_or_null(surf_network_model->resource_set, "8"); xbt_assert0(link!=NULL,"NULL");
1802   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(3,1,&tmp3),&link);
1803   link = xbt_dict_get_or_null(surf_network_model->resource_set, "7"); xbt_assert0(link!=NULL,"NULL");
1804   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(3,1,&tmp3),&link);
1805   // r31 - b
1806   link = xbt_dict_get_or_null(surf_network_model->resource_set, "3"); xbt_assert0(link!=NULL,"NULL");
1807   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(2,0,&tmp3),&link);
1808   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1809   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(2,0,&tmp3),&link);
1810   // r32 - b
1811   link = xbt_dict_get_or_null(surf_network_model->resource_set, "9"); xbt_assert0(link!=NULL,"NULL");
1812   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(3,1,&tmp3),&link);
1813   link = xbt_dict_get_or_null(surf_network_model->resource_set, "3"); xbt_assert0(link!=NULL,"NULL");
1814   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(3,1,&tmp3),&link);
1815
1816 // tmp4
1817
1818   // c - d
1819   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1820   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(2,3,&tmp4),&link);
1821   link = xbt_dict_get_or_null(surf_network_model->resource_set, "7"); xbt_assert0(link!=NULL,"NULL");
1822   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(2,3,&tmp4),&link);
1823   // d - c
1824   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1825   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(3,2,&tmp4),&link);
1826   link = xbt_dict_get_or_null(surf_network_model->resource_set, "7"); xbt_assert0(link!=NULL,"NULL");
1827   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(3,2,&tmp4),&link);
1828   // c - e
1829   link = xbt_dict_get_or_null(surf_network_model->resource_set, "6"); xbt_assert0(link!=NULL,"NULL");
1830   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(2,4,&tmp4),&link);
1831   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1832   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(2,4,&tmp4),&link);
1833   // e - c
1834   link = xbt_dict_get_or_null(surf_network_model->resource_set, "6"); xbt_assert0(link!=NULL,"NULL");
1835   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(4,2,&tmp4),&link);
1836   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1837   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(4,2,&tmp4),&link);
1838   // d - e
1839   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1840   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(3,4,&tmp4),&link);
1841   link = xbt_dict_get_or_null(surf_network_model->resource_set, "3"); xbt_assert0(link!=NULL,"NULL");
1842   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(3,4,&tmp4),&link);
1843   // e - d
1844   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1845   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(4,3,&tmp4),&link);
1846   link = xbt_dict_get_or_null(surf_network_model->resource_set, "3"); xbt_assert0(link!=NULL,"NULL");
1847   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(4,3,&tmp4),&link);
1848
1849   // c - r41
1850   link = xbt_dict_get_or_null(surf_network_model->resource_set, "7"); xbt_assert0(link!=NULL,"NULL");
1851   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(2,4,&tmp4),&link);
1852   link = xbt_dict_get_or_null(surf_network_model->resource_set, "9"); xbt_assert0(link!=NULL,"NULL");
1853   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(2,4,&tmp4),&link);
1854   // d - r41
1855   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1856   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(3,4,&tmp4),&link);
1857   link = xbt_dict_get_or_null(surf_network_model->resource_set, "8"); xbt_assert0(link!=NULL,"NULL");
1858   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(3,4,&tmp4),&link);
1859   // e - r41
1860   link = xbt_dict_get_or_null(surf_network_model->resource_set, "8"); xbt_assert0(link!=NULL,"NULL");
1861   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(4,4,&tmp4),&link);
1862   link = xbt_dict_get_or_null(surf_network_model->resource_set, "0"); xbt_assert0(link!=NULL,"NULL");
1863   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(4,4,&tmp4),&link);
1864   // c - r42
1865   link = xbt_dict_get_or_null(surf_network_model->resource_set, "6"); xbt_assert0(link!=NULL,"NULL");
1866   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(2,5,&tmp4),&link);
1867   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1868   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(2,5,&tmp4),&link);
1869   // d - r42
1870   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1871   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(3,5,&tmp4),&link);
1872   link = xbt_dict_get_or_null(surf_network_model->resource_set, "1"); xbt_assert0(link!=NULL,"NULL");
1873   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(3,5,&tmp4),&link);
1874   // e - r42
1875   link = xbt_dict_get_or_null(surf_network_model->resource_set, "9"); xbt_assert0(link!=NULL,"NULL");
1876   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(4,5,&tmp4),&link);
1877   link = xbt_dict_get_or_null(surf_network_model->resource_set, "4"); xbt_assert0(link!=NULL,"NULL");
1878   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(4,5,&tmp4),&link);
1879
1880   // r41 - c
1881   link = xbt_dict_get_or_null(surf_network_model->resource_set, "7"); xbt_assert0(link!=NULL,"NULL");
1882   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(4,2,&tmp4),&link);
1883   link = xbt_dict_get_or_null(surf_network_model->resource_set, "9"); xbt_assert0(link!=NULL,"NULL");
1884   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(4,2,&tmp4),&link);
1885   // r41 - d
1886   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1887   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(4,3,&tmp4),&link);
1888   link = xbt_dict_get_or_null(surf_network_model->resource_set, "8"); xbt_assert0(link!=NULL,"NULL");
1889   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(4,3,&tmp4),&link);
1890   // r41 - e
1891   link = xbt_dict_get_or_null(surf_network_model->resource_set, "8"); xbt_assert0(link!=NULL,"NULL");
1892   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(4,4,&tmp4),&link);
1893   link = xbt_dict_get_or_null(surf_network_model->resource_set, "0"); xbt_assert0(link!=NULL,"NULL");
1894   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(4,4,&tmp4),&link);
1895   // r42 - c
1896   link = xbt_dict_get_or_null(surf_network_model->resource_set, "6"); xbt_assert0(link!=NULL,"NULL");
1897   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(5,2,&tmp4),&link);
1898   link = xbt_dict_get_or_null(surf_network_model->resource_set, "5"); xbt_assert0(link!=NULL,"NULL");
1899   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(5,2,&tmp4),&link);
1900   // r42 - d
1901   link = xbt_dict_get_or_null(surf_network_model->resource_set, "2"); xbt_assert0(link!=NULL,"NULL");
1902   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(5,3,&tmp4),&link);
1903   link = xbt_dict_get_or_null(surf_network_model->resource_set, "1"); xbt_assert0(link!=NULL,"NULL");
1904   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(5,3,&tmp4),&link);
1905   // r42 - e
1906   link = xbt_dict_get_or_null(surf_network_model->resource_set, "9"); xbt_assert0(link!=NULL,"NULL");
1907   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(5,4,&tmp4),&link);
1908   link = xbt_dict_get_or_null(surf_network_model->resource_set, "4"); xbt_assert0(link!=NULL,"NULL");
1909   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(5,4,&tmp4),&link);
1910
1911 // tmp5
1912
1913   // f - r51
1914   link = xbt_dict_get_or_null(surf_network_model->resource_set, "6"); xbt_assert0(link!=NULL,"NULL");
1915   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(5,6,&tmp5),&link);
1916   link = xbt_dict_get_or_null(surf_network_model->resource_set, "8"); xbt_assert0(link!=NULL,"NULL");
1917   xbt_dynar_push(ROUTE_HIERARCHICAL_HR(5,6,&tmp5),&link);
1918
1919   // r51 - f
1920   link = xbt_dict_get_or_null(surf_network_model->resource_set, "6"); xbt_assert0(link!=NULL,"NULL");
1921   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(6,5,&tmp5),&link);
1922   link = xbt_dict_get_or_null(surf_network_model->resource_set, "8"); xbt_assert0(link!=NULL,"NULL");
1923   xbt_dynar_push(ROUTE_HIERARCHICAL_RH(6,5,&tmp5),&link);
1924
1925 // loopback
1926
1927   link = xbt_dict_get_or_null(surf_network_model->resource_set, "loopback"); xbt_assert0(link!=NULL,"NULL loopback");
1928   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(0,0,&tmp3),&link);
1929   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(1,1,&tmp3),&link);
1930   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(2,2,&tmp4),&link);
1931   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(3,3,&tmp4),&link);
1932   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(4,4,&tmp4),&link);
1933   xbt_dynar_push(ROUTE_HIERARCHICAL_HH(5,5,&tmp5),&link);
1934
1935 //   for(i=0;i<=5;i++) {
1936 //     for(j=0;j<=5;j++) {
1937 //       links = routing_hierarchical_get_route(i,j);
1938 //       printf("route from %d to %d",i,j);
1939 //       cpt=0;
1940 //       xbt_dynar_foreach(links, cpt, link) {
1941 //      s_surf_resource_t* generic_resource = link;
1942 //      printf(" l%s,",generic_resource->name);
1943 //       }
1944 //       printf("\n");
1945 //     }
1946 //   }
1947 //
1948 //     exit(0);
1949
1950 }
1951
1952 static void routing_model_hierarchical_create(size_t size_of_link,void *loopback) {
1953
1954   /* initialize the id counters */
1955   local_host_count = 0;
1956   local_router_count = 0;
1957
1958   /* initialize our structure */
1959   routing_hierarchical_t routing = xbt_new0(s_routing_hierarchical_t,1);
1960   routing->generic_routing.name = "Hierarchical";
1961   routing->generic_routing.host_count = 0;
1962   routing->generic_routing.get_route = routing_hierarchical_get_route;
1963   routing->generic_routing.get_onelink_routes = routing_hierarchical_get_onelink_routes;
1964   routing->generic_routing.is_router = routing_hierarchical_is_router;
1965   routing->generic_routing.finalize = routing_hierarchical_finalize;
1966
1967   routing->size_of_link = size_of_link;
1968   routing->loopback = loopback;
1969
1970   /* Set it in position */
1971   used_routing = (routing_t) routing;
1972
1973   /* Set the dict for host ids */
1974   routing->generic_routing.host_id = xbt_dict_new();
1975
1976   /* Set the host */
1977   routing->host_routetree = xbt_dynar_new(sizeof(routetree_t), NULL);
1978
1979   /* Create the last route array */
1980   routing->last_route = xbt_dynar_new(routing->size_of_link, NULL);
1981
1982   /* Setup the parsing callbacks we need */
1983
1984   // DAVID - only for parse the hosts
1985   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
1986
1987   // surfxml_add_callback(STag_surfxml_router_cb_list, &routing_full_parse_Srouter);
1988   // surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_full_parse_end);
1989   // surfxml_add_callback(STag_surfxml_route_cb_list, &routing_full_parse_Sroute_set_endpoints);
1990   // surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
1991   // surfxml_add_callback(STag_surfxml_cluster_cb_list, &routing_full_parse_Scluster);
1992
1993   // DAVID - make a fix example
1994   surfxml_add_callback(ETag_surfxml_platform_cb_list, &example);
1995
1996 }