src/surf/surf_routing.c

   1 /* Copyright (c) 2009 The SimGrid team. All rights reserved.                */
   2
   3 /* This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the license (GNU LGPL) which comes with this package. */
   5
   6 #include <float.h>
   7 #include "surf_private.h"
   8 #include "xbt/dynar.h"
   9 #include "xbt/str.h"
  10 #include "xbt/config.h"
  11 #include "xbt/graph.h"
  12 #include "xbt/set.h"
  13
  14 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf");// FIXME: connect this under windows
  15
  16 routing_t used_routing = NULL;
  17
  18 /* Prototypes of each model */
  19 static void routing_model_full_create(size_t size_of_link,void *loopback);
  20 static void routing_model_floyd_create(size_t size_of_link, void*loopback);
  21 static void routing_model_dijkstra_create(size_t size_of_link, void*loopback);
  22 static void routing_model_dijkstracache_create(size_t size_of_link, void*loopback);
  23
  24 /* Definition of each model */
  25 struct model_type {
  26   const char *name;
  27   const char *desc;
  28   void (*fun)(size_t,void*);
  29 };
  30 struct model_type models[] =
  31 { {"Full", "Full routing data (fast, large memory requirements, fully expressive)", routing_model_full_create },
  32   {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)", routing_model_floyd_create },
  33   {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)", routing_model_dijkstra_create },
  34   {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)", routing_model_dijkstracache_create },
  35     {NULL,NULL,NULL}};
  36
  37
  38 void routing_model_create(size_t size_of_links, void* loopback) {
  39
  40   char * wanted=xbt_cfg_get_string(_surf_cfg_set,"routing");
  41   int cpt;
  42   for (cpt=0;models[cpt].name;cpt++) {
  43     if (!strcmp(wanted,models[cpt].name)) {
  44       (*(models[cpt].fun))(size_of_links,loopback);
  45       return;
  46     }
  47   }
  48   fprintf(stderr,"Routing model %s not found. Existing models:\n",wanted);
  49   for (cpt=0;models[cpt].name;cpt++)
  50     if (!strcmp(wanted,models[cpt].name))
  51       fprintf(stderr,"   %s: %s\n",models[cpt].name,models[cpt].desc);
  52   exit(1);
  53 }
  54
  55 /* ************************************************************************** */
  56 /* *************************** FULL ROUTING ********************************* */
  57 typedef struct {
  58   s_routing_t generic_routing;
  59   xbt_dynar_t *routing_table;
  60   void *loopback;
  61   size_t size_of_link;
  62 } s_routing_full_t,*routing_full_t;
  63
  64 #define ROUTE_FULL(i,j) ((routing_full_t)used_routing)->routing_table[(i)+(j)*(used_routing)->host_count]
  65
  66 /*
  67  * Parsing
  68  */
  69 static void routing_full_parse_Shost(void) {
  70   int *val = xbt_malloc(sizeof(int));
  71   DEBUG2("Seen host %s (#%d)",A_surfxml_host_id,used_routing->host_count);
  72   *val = used_routing->host_count++;
  73   xbt_dict_set(used_routing->host_id,A_surfxml_host_id,val,xbt_free);
  74 }
  75 static int src_id = -1;
  76 static int dst_id = -1;
  77 static void routing_full_parse_Sroute_set_endpoints(void)
  78 {
  79   src_id = *(int*)xbt_dict_get(used_routing->host_id,A_surfxml_route_src);
  80   dst_id = *(int*)xbt_dict_get(used_routing->host_id,A_surfxml_route_dst);
  81   DEBUG4("Route %s %d -> %s %d",A_surfxml_route_src,src_id,A_surfxml_route_dst,dst_id);
  82   route_action = A_surfxml_route_action;
  83 }
  84 static void routing_full_parse_Eroute(void)
  85 {
  86   char *name;
  87   if (src_id != -1 && dst_id != -1) {
  88     name = bprintf("%x#%x", src_id, dst_id);
  89     manage_route(route_table, name, route_action, 0);
  90     free(name);
  91   }
  92 }
  93
  94
  95 static void routing_full_parse_end(void) {
  96   routing_full_t routing = (routing_full_t) used_routing;
  97   int nb_link = 0;
  98   unsigned int cpt = 0;
  99   xbt_dict_cursor_t cursor = NULL;
 100   char *key, *data, *end;
 101   const char *sep = "#";
 102   xbt_dynar_t links, keys;
 103   char *link_name = NULL;
 104   int i,j;
 105
 106   int host_count = routing->generic_routing.host_count;
 107
 108   /* Create the routing table */
 109   routing->routing_table = xbt_new0(xbt_dynar_t, host_count * host_count);
 110   for (i=0;i<host_count;i++)
 111     for (j=0;j<host_count;j++)
 112       ROUTE_FULL(i,j) = xbt_dynar_new(routing->size_of_link,NULL);
 113
 114   /* Put the routes in position */
 115   xbt_dict_foreach(route_table, cursor, key, data) {
 116     nb_link = 0;
 117     links = (xbt_dynar_t) data;
 118     keys = xbt_str_split_str(key, sep);
 119
 120     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
 121     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
 122     xbt_dynar_free(&keys);
 123
 124     DEBUG4("Handle %d %d (from %d hosts): %ld links",
 125         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
 126     xbt_dynar_foreach(links, cpt, link_name) {
 127       void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
 128       if (link)
 129         xbt_dynar_push(ROUTE_FULL(src_id,dst_id),&link);
 130       else
 131         THROW1(mismatch_error,0,"Link %s not found", link_name);
 132     }
 133   }
 134
 135   /* Add the loopback if needed */
 136   for (i = 0; i < host_count; i++)
 137     if (!xbt_dynar_length(ROUTE_FULL(i, i)))
 138       xbt_dynar_push(ROUTE_FULL(i,i),&routing->loopback);
 139
 140   /* Shrink the dynar routes (save unused slots) */
 141   for (i=0;i<host_count;i++)
 142     for (j=0;j<host_count;j++)
 143       xbt_dynar_shrink(ROUTE_FULL(i,j),0);
 144 }
 145
 146 /*
 147  * Business methods
 148  */
 149 static xbt_dynar_t routing_full_get_route(int src,int dst) {
 150   return ROUTE_FULL(src,dst);
 151 }
 152
 153 static void routing_full_finalize(void) {
 154   routing_full_t routing = (routing_full_t)used_routing;
 155   int i,j;
 156
 157   if (routing) {
 158     for (i = 0; i < used_routing->host_count; i++)
 159       for (j = 0; j < used_routing->host_count; j++)
 160         xbt_dynar_free(&ROUTE_FULL(i, j));
 161     free(routing->routing_table);
 162     xbt_dict_free(&used_routing->host_id);
 163     free(routing);
 164     routing=NULL;
 165   }
 166 }
 167
 168 static void routing_model_full_create(size_t size_of_link,void *loopback) {
 169   /* initialize our structure */
 170   routing_full_t routing = xbt_new0(s_routing_full_t,1);
 171   routing->generic_routing.name = "Full";
 172   routing->generic_routing.host_count = 0;
 173   routing->generic_routing.get_route = routing_full_get_route;
 174   routing->generic_routing.finalize = routing_full_finalize;
 175   routing->size_of_link = size_of_link;
 176   routing->loopback = loopback;
 177
 178   /* Set it in position */
 179   used_routing = (routing_t) routing;
 180
 181   /* Setup the parsing callbacks we need */
 182   routing->generic_routing.host_id = xbt_dict_new();
 183   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
 184   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_full_parse_end);
 185   surfxml_add_callback(STag_surfxml_route_cb_list,
 186       &routing_full_parse_Sroute_set_endpoints);
 187   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
 188 }
 189
 190 /* ************************************************************************** */
 191 /* *************************** FLOYD ROUTING ********************************* */
 192 typedef struct {
 193   s_routing_t generic_routing;
 194   double *cost_table;
 195   int *predecessor_table;
 196   void** link_table;
 197
 198   void *loopback;
 199   size_t size_of_link;
 200 } s_routing_floyd_t,*routing_floyd_t;
 201
 202
 203
 204 #define FLOYD_COST(i,j) ((routing_floyd_t)used_routing)->cost_table[(i)+(j)*(used_routing)->host_count]
 205 #define FLOYD_PRED(i,j) ((routing_floyd_t)used_routing)->predecessor_table[(i)+(j)*(used_routing)->host_count]
 206 #define FLOYD_LINK(i,j) ((routing_floyd_t)used_routing)->link_table[(i)+(j)*(used_routing)->host_count]
 207
 208 static void routing_floyd_parse_end(void) {
 209
 210   routing_floyd_t routing = (routing_floyd_t) used_routing;
 211   int nb_link = 0;
 212   unsigned int cpt = 0;
 213   void* link_list = NULL;
 214   xbt_dict_cursor_t cursor = NULL;
 215   char *key,*data, *end;
 216   const char *sep = "#";
 217   xbt_dynar_t links, keys;
 218   char *link_name = NULL;
 219
 220   unsigned int i,j;
 221
 222   int host_count = routing->generic_routing.host_count;
 223
 224   /* Create Cost, Predecessor and Link tables */
 225   routing->cost_table = xbt_new0(double, host_count * host_count); //link cost from host to host
 226   routing->predecessor_table = xbt_new0(int, host_count*host_count); //predecessor host numbers
 227   routing->link_table = xbt_new0(void*,host_count*host_count); //actual link between src and dst
 228
 229   /* Initialize costs and predecessors*/
 230   for(i = 0; i<host_count;i++)
 231     for(j = 0; j<host_count;j++) {
 232         FLOYD_COST(i,j) = DBL_MAX;
 233         FLOYD_PRED(i,j) = -1;
 234     }
 235
 236    /* Put the routes in position */
 237   xbt_dict_foreach(route_table, cursor, key, data) {
 238     nb_link = 0;
 239     links = (xbt_dynar_t)data;
 240     keys = xbt_str_split_str(key, sep);
 241
 242
 243     src_id = strtol(xbt_dynar_get_as(keys, 0, char*), &end, 16);
 244     dst_id = strtol(xbt_dynar_get_as(keys, 1, char*), &end, 16);
 245     xbt_dynar_free(&keys);
 246
 247     DEBUG4("Handle %d %d (from %d hosts): %ld links",
 248         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
 249     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);
 250
 251     xbt_dynar_foreach (links, cpt, link_name) {
 252       void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
 253       if (link)
 254         link_list = link;
 255       else
 256         THROW1(mismatch_error,0,"Link %s not found", link_name);
 257
 258     }
 259
 260     FLOYD_LINK(src_id,dst_id) = link_list;
 261     FLOYD_PRED(src_id, dst_id) = src_id;
 262
 263     //link cost
 264     FLOYD_COST(src_id, dst_id) = 1; // assume 1 for now
 265
 266   }
 267
 268     /* Add the loopback if needed */
 269   for (i = 0; i < host_count; i++)
 270     if (!FLOYD_PRED(i, i)) {
 271       FLOYD_PRED(i, i) = i;
 272       FLOYD_COST(i, i) = 1;
 273       FLOYD_LINK(i, i) = routing->loopback;
 274     }
 275
 276
 277   //Calculate path costs
 278   unsigned int a,b,c;
 279   for(c=0;c<host_count;c++) {
 280     for(a=0;a<host_count;a++) {
 281       for(b=0;b<host_count;b++) {
 282         if(FLOYD_COST(a,c) < DBL_MAX && FLOYD_COST(c,b) < DBL_MAX) {
 283           if(FLOYD_COST(a,b) == DBL_MAX || (FLOYD_COST(a,c)+FLOYD_COST(c,b) < FLOYD_COST(a,b))) {
 284             FLOYD_COST(a,b) = FLOYD_COST(a,c)+FLOYD_COST(c,b);
 285             FLOYD_PRED(a,b) = FLOYD_PRED(c,b);
 286           }
 287         }
 288       }
 289     }
 290   }
 291 }
 292
 293 /*
 294  * Business methods
 295  */
 296 static xbt_dynar_t routing_floyd_get_route(int src_id,int dst_id) {
 297
 298   routing_floyd_t routing = (routing_floyd_t) used_routing;
 299
 300   int pred = dst_id;
 301   int prev_pred = 0;
 302
 303   xbt_dynar_t link_list = xbt_dynar_new(routing->size_of_link, NULL);
 304
 305   do {
 306     prev_pred = pred;
 307     pred = FLOYD_PRED(src_id, pred);
 308
 309     if(pred == -1) // if no pred in route -> no route to host
 310         break;
 311
 312     xbt_dynar_unshift(link_list, &FLOYD_LINK(pred,prev_pred));
 313
 314   } while(pred != src_id);
 315
 316   xbt_assert2(pred != -1, "no route from host %d to %d", src_id, dst_id);
 317
 318   return link_list;
 319 }
 320
 321 static void routing_floyd_finalize_route(xbt_dynar_t route) {
 322   xbt_dynar_free(&route);
 323 }
 324
 325 static void routing_floyd_finalize(void) {
 326   routing_floyd_t routing = (routing_floyd_t)used_routing;
 327
 328   if (routing) {
 329     free(routing->link_table);
 330     free(routing->cost_table);
 331     free(routing->predecessor_table);
 332     xbt_dict_free(&used_routing->host_id);
 333     free(routing);
 334     routing=NULL;
 335   }
 336 }
 337
 338 static void routing_model_floyd_create(size_t size_of_link,void *loopback) {
 339   /* initialize our structure */
 340   routing_floyd_t routing = xbt_new0(s_routing_floyd_t,1);
 341   routing->generic_routing.name = "Floyd";
 342   routing->generic_routing.host_count = 0;
 343   routing->generic_routing.get_route = routing_floyd_get_route;
 344   routing->generic_routing.finalize = routing_floyd_finalize;
 345   routing->generic_routing.finalize_route = routing_floyd_finalize_route;
 346   routing->size_of_link = size_of_link;
 347   routing->loopback = loopback;
 348
 349   /* Set it in position */
 350   used_routing = (routing_t) routing;
 351
 352   /* Setup the parsing callbacks we need */
 353   routing->generic_routing.host_id = xbt_dict_new();
 354   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
 355   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_floyd_parse_end);
 356   surfxml_add_callback(STag_surfxml_route_cb_list,
 357       &routing_full_parse_Sroute_set_endpoints);
 358   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
 359
 360 }
 361
 362 /* ************************************************************************** */
 363 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
 364 typedef struct {
 365   s_routing_t generic_routing;
 366   xbt_graph_t route_graph;
 367   xbt_set_t graph_node_map;
 368   xbt_set_t route_cache;
 369   int cached;
 370   void *loopback;
 371   size_t size_of_link;
 372 } s_routing_dijkstra_t,*routing_dijkstra_t;
 373
 374
 375 typedef struct graph_node_data {
 376   int id;
 377   int graph_id; //used for caching internal id's
 378 } s_graph_node_data_t, * graph_node_data_t;
 379
 380 typedef struct graph_node_map_element {
 381   XBT_SET_HEADERS;
 382
 383   xbt_node_t node;
 384 } s_graph_node_map_element_t, * graph_node_map_element_t;
 385
 386 typedef struct route_cache_element {
 387   XBT_SET_HEADERS;
 388
 389   int * pred_arr;
 390   int size;
 391 } s_route_cache_element_t, * route_cache_element_t;
 392
 393 /*
 394  * Free functions
 395  */
 396 static void route_cache_elem_free(void *e) {
 397   route_cache_element_t elm=(route_cache_element_t)e;
 398
 399   if (elm) {
 400     free(elm->name);
 401     free(elm->pred_arr);
 402     free(elm);
 403   }
 404 }
 405
 406 static void graph_node_map_elem_free(void *e) {
 407   graph_node_map_element_t elm = (graph_node_map_element_t)e;
 408
 409   if(elm) {
 410     free(elm->name);
 411     free(elm);
 412   }
 413 }
 414
 415 /*
 416  * Utility functions
 417 */
 418 static xbt_node_t route_graph_new_node(int id, int graph_id) {
 419   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 420
 421   graph_node_data_t data = xbt_new0(struct graph_node_data, sizeof(struct graph_node_data));
 422   data->id = id;
 423   data->graph_id = graph_id;
 424   xbt_node_t node = xbt_graph_new_node(routing->route_graph, data);
 425
 426   graph_node_map_element_t elm = xbt_new0(struct graph_node_map_element, sizeof(struct graph_node_map_element));
 427   elm->name_len = 0;
 428   elm->name = bprintf("%d",id);
 429   elm->node = node;
 430
 431   xbt_set_add(routing->graph_node_map, (xbt_set_elm_t)elm, &graph_node_map_elem_free);
 432
 433   return node;
 434 }
 435
 436 static graph_node_map_element_t graph_node_map_search(int id) {
 437   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 438
 439   char * id_str = bprintf("%d",id);
 440   graph_node_map_element_t elm = (graph_node_map_element_t)xbt_set_get_by_name_or_null(routing->graph_node_map, id_str);
 441   free(id_str);
 442
 443   return elm;
 444 }
 445
 446 /*
 447  * Parsing
 448  */
 449 static void route_new_dijkstra(int src_id, int dst_id, void* link) {
 450   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 451
 452   xbt_node_t src = NULL;
 453   xbt_node_t dst = NULL;
 454   char * src_id_str = bprintf("%d",src_id);
 455   char * dst_id_str = bprintf("%d",dst_id);
 456   graph_node_map_element_t src_elm = (graph_node_map_element_t)xbt_set_get_by_name_or_null(routing->graph_node_map, src_id_str);
 457   graph_node_map_element_t dst_elm = (graph_node_map_element_t)xbt_set_get_by_name_or_null(routing->graph_node_map, dst_id_str);
 458   free(src_id_str);
 459   free(dst_id_str);
 460
 461   if(src_elm)
 462     src = src_elm->node;
 463
 464   if(dst_elm)
 465     dst = dst_elm->node;
 466
 467   //add nodes if they don't exist in the graph
 468   if(src_id == dst_id && src == NULL && dst == NULL) {
 469     src = route_graph_new_node(src_id, -1);
 470     dst = src;
 471   } else {
 472     if(src == NULL) {
 473       src = route_graph_new_node(src_id, -1);
 474     }
 475
 476     if(dst == NULL) {
 477       dst = route_graph_new_node(dst_id, -1);
 478     }
 479   }
 480
 481   //add link as edge to graph
 482   xbt_graph_new_edge(routing->route_graph, src, dst, link);
 483
 484 }
 485
 486 static void add_loopback_dijkstra(void) {
 487   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 488
 489         xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
 490
 491         xbt_node_t node = NULL;
 492         unsigned int cursor2;
 493         xbt_dynar_foreach(nodes, cursor2, node) {
 494                 xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
 495                 xbt_edge_t edge = NULL;
 496                 unsigned int cursor;
 497
 498                 int found = 0;
 499                 xbt_dynar_foreach(out_edges, cursor, edge) {
 500                         xbt_node_t other_node = xbt_graph_edge_get_target(edge);
 501                         if(other_node == node) {
 502                                 found = 1;
 503                                 break;
 504                         }
 505                 }
 506
 507                 if(!found)
 508                         xbt_graph_new_edge(routing->route_graph, node, node, &routing->loopback);
 509         }
 510 }
 511
 512 static void routing_dijkstra_parse_end(void) {
 513   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 514   int nb_link = 0;
 515   unsigned int cpt = 0;
 516   xbt_dict_cursor_t cursor = NULL;
 517   char *key, *data, *end;
 518   const char *sep = "#";
 519   xbt_dynar_t links, keys;
 520   char *link_name = NULL;
 521
 522   /* Create the topology graph */
 523   routing->route_graph = xbt_graph_new_graph(1, NULL);
 524   routing->graph_node_map = xbt_set_new();
 525   if(routing->cached)
 526     routing->route_cache = xbt_set_new();
 527
 528
 529   /* Put the routes in position */
 530   xbt_dict_foreach(route_table, cursor, key, data) {
 531     nb_link = 0;
 532     links = (xbt_dynar_t) data;
 533     keys = xbt_str_split_str(key, sep);
 534
 535     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 16);
 536     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 16);
 537     xbt_dynar_free(&keys);
 538
 539     DEBUG4("Handle %d %d (from %d hosts): %ld links",
 540         src_id,dst_id,routing->generic_routing.host_count,xbt_dynar_length(links));
 541
 542     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);
 543
 544     xbt_dynar_foreach(links, cpt, link_name) {
 545       void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
 546       if (link)
 547         route_new_dijkstra(src_id,dst_id,link);
 548       else
 549         THROW1(mismatch_error,0,"Link %s not found", link_name);
 550     }
 551
 552   }
 553
 554   /* Add the loopback if needed */
 555   add_loopback_dijkstra();
 556
 557   /* initialize graph indexes in nodes after graph has been built */
 558   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
 559
 560   xbt_node_t node = NULL;
 561   unsigned int cursor2;
 562   xbt_dynar_foreach(nodes, cursor2, node) {
 563     graph_node_data_t data = xbt_graph_node_get_data(node);
 564     data->graph_id = cursor2;
 565   }
 566
 567 }
 568
 569 /*
 570  * Business methods
 571  */
 572 static xbt_dynar_t routing_dijkstra_get_route(int src_id,int dst_id) {
 573
 574   routing_dijkstra_t routing = (routing_dijkstra_t) used_routing;
 575   int * pred_arr = NULL;
 576
 577   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
 578
 579   /*Use the graph_node id mapping set to quickly find the nodes */
 580   graph_node_map_element_t src_elm = graph_node_map_search(src_id);
 581   graph_node_map_element_t dst_elm = graph_node_map_search(dst_id);
 582   xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", src_id, dst_id);
 583   int src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id;
 584   int dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id;
 585
 586   route_cache_element_t elm = NULL;
 587   if(routing->cached) {
 588     /*check if there is a cached predecessor list avail */
 589     char * src_id_str = bprintf("%d",src_id);
 590     elm = (route_cache_element_t)xbt_set_get_by_name_or_null(routing->route_cache, src_id_str);
 591     free(src_id_str);
 592   }
 593
 594   if(elm) { //cached mode and cache hit
 595     pred_arr = elm->pred_arr;
 596   } else { //not cached mode or cache miss
 597     double * cost_arr = NULL;
 598     xbt_heap_t pqueue = NULL;
 599     int i = 0;
 600
 601     int nr_nodes = xbt_dynar_length(nodes);
 602     cost_arr = xbt_new0(double, nr_nodes); //link cost from src to other hosts
 603     pred_arr = xbt_new0(int, nr_nodes); //predecessors in path from src
 604     pqueue = xbt_heap_new(nr_nodes, free);
 605
 606     //initialize
 607     cost_arr[src_node_id] = 0.0;
 608
 609     for(i = 0; i < nr_nodes; i++) {
 610       if(i != src_node_id) {
 611         cost_arr[i] = DBL_MAX;
 612       }
 613
 614       pred_arr[i] = 0;
 615
 616       //initialize priority queue
 617       int * nodeid = xbt_new0(int, 1);
 618       *nodeid = i;
 619       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
 620
 621     }
 622
 623     // apply dijkstra using the indexes from the graph's node array
 624     while(xbt_heap_size(pqueue) > 0) {
 625       int * v_id = xbt_heap_pop(pqueue);
 626       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
 627       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
 628       xbt_edge_t edge = NULL;
 629       unsigned int cursor;
 630
 631       xbt_dynar_foreach(out_edges, cursor, edge) {
 632         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
 633         graph_node_data_t data = xbt_graph_node_get_data(u_node);
 634         int u_id = data->graph_id;
 635         int cost_v_u = 1; //fixed link cost for now
 636
 637         if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
 638           pred_arr[u_id] = *v_id;
 639           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
 640           int * nodeid = xbt_new0(int, 1);
 641           *nodeid = u_id;
 642           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
 643         }
 644       }
 645
 646       //free item popped from pqueue
 647       free(v_id);
 648     }
 649
 650     free(cost_arr);
 651     xbt_heap_free(pqueue);
 652
 653   }
 654
 655   //compose route path with links
 656   xbt_dynar_t link_list = xbt_dynar_new(routing->size_of_link, NULL);
 657
 658   int v;
 659   int size = 0;
 660   for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
 661     xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
 662     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
 663     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
 664
 665     xbt_assert2(edge != NULL, "no route between host %d and %d", src_id, dst_id);
 666
 667     void * link = xbt_graph_edge_get_data(edge);
 668     xbt_dynar_unshift(link_list, &link);
 669     size++;
 670   }
 671
 672
 673   if(routing->cached && elm == NULL) {
 674     //add to predecessor list of the current src-host to cache
 675     elm = xbt_new0(struct route_cache_element, sizeof(struct route_cache_element));
 676     elm->name = bprintf("%d",src_id);
 677     elm->name_len = 0;
 678     elm->pred_arr = pred_arr;
 679     elm->size = size;
 680     xbt_set_add(routing->route_cache, (xbt_set_elm_t)elm, &route_cache_elem_free);
 681   }
 682
 683   if(!routing->cached)
 684     free(pred_arr);
 685
 686   return link_list;
 687 }
 688
 689 static void routing_dijkstra_finalize_route(xbt_dynar_t route) {
 690   xbt_dynar_free(&route);
 691 }
 692
 693 static void routing_dijkstra_finalize(void) {
 694   routing_dijkstra_t routing = (routing_dijkstra_t)used_routing;
 695
 696   if (routing) {
 697     xbt_graph_free_graph(routing->route_graph, &free, NULL, &free);
 698     xbt_set_free(&routing->graph_node_map);
 699     if(routing->cached)
 700       xbt_set_free(&routing->route_cache);
 701     xbt_dict_free(&used_routing->host_id);
 702     free(routing);
 703     routing=NULL;
 704   }
 705 }
 706
 707 /*
 708  *
 709  */
 710 static void routing_model_dijkstraboth_create(size_t size_of_link,void *loopback, int cached) {
 711   /* initialize our structure */
 712   routing_dijkstra_t routing = xbt_new0(s_routing_dijkstra_t,1);
 713   routing->generic_routing.name = "Dijkstra";
 714   routing->generic_routing.host_count = 0;
 715   routing->generic_routing.get_route = routing_dijkstra_get_route;
 716   routing->generic_routing.finalize = routing_dijkstra_finalize;
 717   routing->generic_routing.finalize_route = routing_dijkstra_finalize_route;
 718   routing->size_of_link = size_of_link;
 719   routing->loopback = loopback;
 720   routing->cached = cached;
 721
 722   /* Set it in position */
 723   used_routing = (routing_t) routing;
 724
 725   /* Setup the parsing callbacks we need */
 726   routing->generic_routing.host_id = xbt_dict_new();
 727   surfxml_add_callback(STag_surfxml_host_cb_list, &routing_full_parse_Shost);
 728   surfxml_add_callback(ETag_surfxml_platform_cb_list, &routing_dijkstra_parse_end);
 729   surfxml_add_callback(STag_surfxml_route_cb_list,
 730       &routing_full_parse_Sroute_set_endpoints);
 731   surfxml_add_callback(ETag_surfxml_route_cb_list, &routing_full_parse_Eroute);
 732 }
 733
 734 static void routing_model_dijkstra_create(size_t size_of_link,void *loopback) {
 735   routing_model_dijkstraboth_create(size_of_link, loopback, 0);
 736 }
 737
 738 static void routing_model_dijkstracache_create(size_t size_of_link,void *loopback) {
 739   routing_model_dijkstraboth_create(size_of_link, loopback, 1);
 740 }