Logo AND Algorithmique Numérique Distribuée

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