Logo AND Algorithmique Numérique Distribuée

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