Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
632b1405410218fcff89a11c4d41fc28ca887434
[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
8
9 #include <float.h>
10 #include "gras_config.h"
11
12 #ifdef HAVE_PCRE_LIB
13 #include <pcre.h>               /* regular expresion library */
14 #endif
15 #include "surf_private.h"
16 #include "xbt/dynar.h"
17 #include "xbt/str.h"
18 #include "xbt/config.h"
19 #include "xbt/graph.h"
20 #include "xbt/set.h"
21
22 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route, surf, "Routing part of surf");
23
24 /* Global vars */
25 routing_global_t global_routing = NULL;
26 routing_component_t current_routing = NULL;
27 model_type_t current_routing_model = NULL;
28 static double_f_cpvoid_t get_link_latency = NULL;
29
30 /* Prototypes of each model */
31 static void *model_full_create(void);   /* create structures for full routing model */
32 static void model_full_load(void);      /* load parse functions for full routing model */
33 static void model_full_unload(void);    /* unload parse functions for full routing model */
34 static void model_full_end(void);       /* finalize the creation of full routing model */
35 static void model_full_set_route(               /* Set the route and ASroute between src and dst */
36                 routing_component_t rc, const char *src, const char *dst, name_route_extended_t route);
37
38 static void *model_floyd_create(void);  /* create structures for floyd routing model */
39 static void model_floyd_load(void);     /* load parse functions for floyd routing model */
40 static void model_floyd_unload(void);   /* unload parse functions for floyd routing model */
41 static void model_floyd_end(void);      /* finalize the creation of floyd routing model */
42 static void model_floyd_set_route(routing_component_t rc, const char *src,
43         const char *dst, name_route_extended_t route);
44
45 static void *model_dijkstra_both_create(int cached);    /* create by calling dijkstra or dijkstracache */
46 static void *model_dijkstra_create(void);       /* create structures for dijkstra routing model */
47 static void *model_dijkstracache_create(void);  /* create structures for dijkstracache routing model */
48 static void model_dijkstra_both_load(void);     /* load parse functions for dijkstra routing model */
49 static void model_dijkstra_both_unload(void);   /* unload parse functions for dijkstra routing model */
50 static void model_dijkstra_both_end(void);      /* finalize the creation of dijkstra routing model */
51 static void model_dijkstra_both_set_route (routing_component_t rc, const char *src,
52                      const char *dst, name_route_extended_t route);
53
54 static void *model_rulebased_create(void);      /* create structures for rulebased routing model */
55 static void model_rulebased_load(void); /* load parse functions for rulebased routing model */
56 static void model_rulebased_unload(void);       /* unload parse functions for rulebased routing model */
57 static void model_rulebased_end(void);  /* finalize the creation of rulebased 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 static void routing_parse_Scluster(void);  /*cluster bypass */
65 static void routing_parse_Speer(void);          /*peer bypass */
66
67 static void routing_parse_Sconfig(void);        /*config Tag */
68 static void routing_parse_Econfig(void);        /*config Tag */
69
70 /* this lines are only for replace use like index in the model table */
71 typedef enum {
72   SURF_MODEL_FULL = 0,
73   SURF_MODEL_FLOYD,
74   SURF_MODEL_DIJKSTRA,
75   SURF_MODEL_DIJKSTRACACHE,
76   SURF_MODEL_NONE,
77 #ifdef HAVE_PCRE_LIB
78   SURF_MODEL_RULEBASED
79 #endif
80 } e_routing_types;
81
82
83 /* must be finish with null and carefull if change de order */
84 struct s_model_type routing_models[] = { {"Full",
85                                           "Full routing data (fast, large memory requirements, fully expressive)",
86                                           model_full_create,
87                                           model_full_load,
88                                           model_full_unload,
89                                           model_full_end},
90 {"Floyd",
91  "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)",
92  model_floyd_create, model_floyd_load, model_floyd_unload,
93  model_floyd_end},
94 {"Dijkstra",
95  "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)",
96  model_dijkstra_create, model_dijkstra_both_load,
97  model_dijkstra_both_unload, model_dijkstra_both_end},
98 {"DijkstraCache",
99  "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)",
100  model_dijkstracache_create, model_dijkstra_both_load,
101  model_dijkstra_both_unload, model_dijkstra_both_end},
102 {"none", "No routing (usable with Constant network only)",
103  model_none_create, model_none_load, model_none_unload, model_none_end},
104 #ifdef HAVE_PCRE_LIB
105 {"RuleBased", "Rule-Based routing data (...)", model_rulebased_create,
106  model_rulebased_load, model_rulebased_unload, model_rulebased_end},
107 {"Vivaldi", "Vivaldi routing", model_rulebased_create,
108   model_rulebased_load, model_rulebased_unload, model_rulebased_end},
109 #endif
110 {NULL, NULL, NULL, NULL, NULL, NULL}
111 };
112
113 /* ************************************************************************** */
114 /* ***************** GENERIC PARSE FUNCTIONS (declarations) ***************** */
115
116 static void generic_set_processing_unit(routing_component_t rc,
117                                         const char *name);
118 static void generic_set_autonomous_system(routing_component_t rc,
119                                           const char *name);
120 static void generic_set_bypassroute(routing_component_t rc,
121                                     const char *src, const char *dst,
122                                     route_extended_t e_route);
123
124 static int surf_link_resource_cmp(const void *a, const void *b);
125 static int surf_pointer_resource_cmp(const void *a, const void *b);
126
127 /* ************************************************************************** */
128 /* *************** GENERIC BUSINESS METHODS (declarations) ****************** */
129
130 static double generic_get_link_latency(routing_component_t rc, const char *src, const char *dst);
131 static xbt_dynar_t generic_get_onelink_routes(routing_component_t rc);
132 static route_extended_t generic_get_bypassroute(routing_component_t rc,
133                                                 const char *src,
134                                                 const char *dst);
135
136 /* ************************************************************************** */
137 /* ****************** GENERIC AUX FUNCTIONS (declarations) ****************** */
138
139 static route_extended_t
140 generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy,
141                            void *data, int order);
142 static route_t
143 generic_new_route(e_surf_routing_hierarchy_t hierarchy,
144                            void *data, int order);
145 static void generic_free_route(route_t route);
146 static void generic_free_extended_route(route_extended_t e_route);
147 static routing_component_t
148 generic_autonomous_system_exist(routing_component_t rc, char *element);
149 static routing_component_t
150 generic_processing_units_exist(routing_component_t rc, char *element);
151 static void generic_src_dst_check(routing_component_t rc, const char *src,
152                                   const char *dst);
153
154 /* ************************************************************************** */
155 /* **************************** GLOBAL FUNCTIONS **************************** */
156
157 /* global parse functions */
158 static const char *src = NULL;        /* temporary store the source name of a route */
159 static const char *dst = NULL;        /* temporary store the destination name of a route */
160 static char *gw_src = NULL;     /* temporary store the gateway source name of a route */
161 static char *gw_dst = NULL;     /* temporary store the gateway destination name of a route */
162 static xbt_dynar_t link_list = NULL;    /* temporary store of current list link of a route */
163
164 static xbt_dict_t coordinates = NULL;
165
166
167 static double eculidean_dist_comp(int index, xbt_dynar_t src, xbt_dynar_t dst)
168 {
169         double src_coord, dst_coord;
170
171         src_coord = atof(xbt_dynar_get_as(src, index, char *));
172         dst_coord = atof(xbt_dynar_get_as(dst, index, char *));
173
174         return (src_coord-dst_coord)*(src_coord-dst_coord);
175
176 }
177
178 static double vivaldi_get_link_latency (routing_component_t rc,
179                                                                                                                                                                 const char *src, const char *dst)
180 {
181   double euclidean_dist;
182   xbt_dynar_t src_ctn, dst_ctn;
183   src_ctn = xbt_dict_get(coordinates, src);
184   dst_ctn = xbt_dict_get(coordinates, dst);
185
186   euclidean_dist = sqrt (eculidean_dist_comp(0,src_ctn,dst_ctn)+eculidean_dist_comp(1,src_ctn,dst_ctn))
187                                                                 +fabs(atof(xbt_dynar_get_as(src_ctn, 2, char *)))+fabs(atof(xbt_dynar_get_as(dst_ctn, 2, char *)));
188
189   xbt_assert2(euclidean_dist>=0, "Euclidean Dist is less than 0\"%s\" and \"%.2f\"", src, euclidean_dist);
190
191   return euclidean_dist;
192
193   /*
194   x = atof(xbt_dynar_get_as(src_ctn, 0, char *))-atof(xbt_dynar_get_as(dst_ctn, 0, char *));
195   y = atof(xbt_dynar_get_as(src_ctn, 1, char *));
196   h = atof(xbt_dynar_get_as(ctn, 2, char *));
197   sqrt((c1->x - c2->x) * (c1->x - c2->x) + (c1->y - c2->y) * (c1->y - c2->y)) + fabs(c1->h) + fabs(c2->h);
198
199           if (strcmp(coord,"")) {
200         xbt_dynar_t ctn = xbt_str_split_str(coord, " ");
201         xbt_dynar_shrink(ctn,0);
202         xbt_dict_set (coordinates,host_id,ctn,NULL);
203   }
204         */
205 }
206
207 /**
208  * \brief Add a "host" to the network element list
209  */
210 static void parse_S_host(const char *host_id, const char* coord)
211 {
212   network_element_info_t info = NULL;
213   if (current_routing->hierarchy == SURF_ROUTING_NULL)
214     current_routing->hierarchy = SURF_ROUTING_BASE;
215   xbt_assert1(!xbt_dict_get_or_null
216               (global_routing->where_network_elements, host_id),
217               "Reading a host, processing unit \"%s\" already exists",
218               host_id);
219   xbt_assert1(current_routing->set_processing_unit,
220               "no defined method \"set_processing_unit\" in \"%s\"",
221               current_routing->name);
222   (*(current_routing->set_processing_unit)) (current_routing, host_id);
223   info = xbt_new0(s_network_element_info_t, 1);
224   info->rc_component = current_routing;
225   info->rc_type = SURF_NETWORK_ELEMENT_HOST;
226   xbt_dict_set(global_routing->where_network_elements, host_id,
227                (void *) info, xbt_free);
228
229   if (strcmp(coord,"")) {
230         xbt_dynar_t ctn = xbt_str_split_str(coord, " ");
231         xbt_dynar_shrink(ctn,0);
232         xbt_dict_set (coordinates,host_id,ctn,NULL);
233   }
234 }
235
236 static void parse_E_host(void)
237 {
238          xbt_dict_cursor_t cursor = NULL;
239           char *key;
240           char *elem;
241
242           xbt_dict_foreach(current_property_set, cursor, key, elem) {
243                   DEBUG2("property : %s = %s",key,elem);
244                 }
245 }
246
247 /*
248  * \brief Add a host to the network element list from XML
249  */
250 static void parse_S_host_XML(void)
251 {
252         parse_S_host(A_surfxml_host_id, A_surfxml_host_coordinates);
253 }
254 static void parse_E_host_XML(void)
255 {
256         parse_E_host();
257 }
258
259 /*
260  * \brief Add a host to the network element list from lua script
261  */
262 static void parse_S_host_lua(const char *host_id, const char *coord)
263 {
264   parse_S_host(host_id, coord);
265 }
266
267
268 /**
269  * \brief Add a "router" to the network element list
270  */
271 static void parse_S_router(void)
272 {
273   network_element_info_t info = NULL;
274
275   if (current_routing->hierarchy == SURF_ROUTING_NULL)
276     current_routing->hierarchy = SURF_ROUTING_BASE;
277   xbt_assert1(!xbt_dict_get_or_null
278               (global_routing->where_network_elements,
279                A_surfxml_router_id),
280               "Reading a router, processing unit \"%s\" already exists",
281               A_surfxml_router_id);
282   xbt_assert1(current_routing->set_processing_unit,
283               "no defined method \"set_processing_unit\" in \"%s\"",
284               current_routing->name);
285   (*(current_routing->set_processing_unit)) (current_routing,
286                                              A_surfxml_router_id);
287   info = xbt_new0(s_network_element_info_t, 1);
288   info->rc_component = current_routing;
289   info->rc_type = SURF_NETWORK_ELEMENT_ROUTER;
290   xbt_dict_set(global_routing->where_network_elements, A_surfxml_router_id,
291                (void *) info, xbt_free);
292   if (strcmp(A_surfxml_router_coordinates,"")) {
293         xbt_dynar_t ctn = xbt_str_split_str(A_surfxml_router_coordinates, " ");
294         xbt_dynar_shrink(ctn,0);
295         xbt_dict_set (coordinates,A_surfxml_router_id,ctn,NULL);
296   }
297 }
298
299 /**
300  * \brief Set the endponints for a route
301  */
302 static void parse_S_route_new_and_endpoints(const char *src_id, const char *dst_id)
303 {
304   if (src != NULL && dst != NULL && link_list != NULL)
305     THROW2(arg_error, 0, "Route between %s to %s can not be defined",
306            src_id, dst_id);
307   src = src_id;
308   dst = dst_id;
309   xbt_assert2(strlen(src) > 0 || strlen(dst) > 0,
310               "Some limits are null in the route between \"%s\" and \"%s\"",
311               src, dst);
312   link_list = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
313 }
314
315 /**
316  * \brief Set the endpoints for a route from XML
317  */
318 static void parse_S_route_new_and_endpoints_XML(void)
319 {
320   parse_S_route_new_and_endpoints(A_surfxml_route_src,
321                                   A_surfxml_route_dst);
322 }
323
324 /**
325  * \brief Set the endpoints for a route from lua
326  */
327 static void parse_S_route_new_and_endpoints_lua(const char *id_src, const char *id_dst)
328 {
329   parse_S_route_new_and_endpoints(id_src, id_dst);
330 }
331
332 /**
333  * \brief Set the endponints and gateways for a ASroute
334  */
335 static void parse_S_ASroute_new_and_endpoints(void)
336 {
337   if (src != NULL && dst != NULL && link_list != NULL)
338     THROW2(arg_error, 0, "Route between %s to %s can not be defined",
339            A_surfxml_ASroute_src, A_surfxml_ASroute_dst);
340   src = A_surfxml_ASroute_src;
341   dst = A_surfxml_ASroute_dst;
342   gw_src = A_surfxml_ASroute_gw_src;
343   gw_dst = A_surfxml_ASroute_gw_dst;
344   xbt_assert2(strlen(src) > 0 || strlen(dst) > 0 || strlen(gw_src) > 0
345               || strlen(gw_dst) > 0,
346               "Some limits are null in the route between \"%s\" and \"%s\"",
347               src, dst);
348   link_list = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
349 }
350
351 /**
352  * \brief Set the endponints for a bypassRoute
353  */
354 static void parse_S_bypassRoute_new_and_endpoints(void)
355 {
356   if (src != NULL && dst != NULL && link_list != NULL)
357     THROW2(arg_error, 0,
358            "Bypass Route between %s to %s can not be defined",
359            A_surfxml_bypassRoute_src, A_surfxml_bypassRoute_dst);
360   src = A_surfxml_bypassRoute_src;
361   dst = A_surfxml_bypassRoute_dst;
362   gw_src = A_surfxml_bypassRoute_gw_src;
363   gw_dst = A_surfxml_bypassRoute_gw_dst;
364   xbt_assert2(strlen(src) > 0 || strlen(dst) > 0 || strlen(gw_src) > 0
365               || strlen(gw_dst) > 0,
366               "Some limits are null in the route between \"%s\" and \"%s\"",
367               src, dst);
368   link_list = xbt_dynar_new(sizeof(char *), &xbt_free_ref);
369 }
370
371 /**
372  * \brief Set a new link on the actual list of link for a route or ASroute
373  */
374 static void parse_E_link_ctn_new_elem(const char *link_id)
375 {
376   char *val;
377   val = xbt_strdup(link_id);
378   xbt_dynar_push(link_list, &val);
379 }
380
381 /**
382  * \brief Set a new link on the actual list of link for a route or ASroute from XML
383  */
384
385 static void parse_E_link_ctn_new_elem_XML(void)
386 {
387   if (A_surfxml_link_ctn_direction == A_surfxml_link_ctn_direction_NONE)
388     parse_E_link_ctn_new_elem(A_surfxml_link_ctn_id);
389   if (A_surfxml_link_ctn_direction == A_surfxml_link_ctn_direction_UP) {
390     char *link_id = bprintf("%s_UP", A_surfxml_link_ctn_id);
391     parse_E_link_ctn_new_elem(link_id);
392     free(link_id);
393   }
394   if (A_surfxml_link_ctn_direction == A_surfxml_link_ctn_direction_DOWN) {
395     char *link_id = bprintf("%s_DOWN", A_surfxml_link_ctn_id);
396     parse_E_link_ctn_new_elem(link_id);
397     free(link_id);
398   }
399 }
400
401 /**
402  * \brief Set a new link on the actual list of link for a route or ASroute from lua
403  */
404 static void parse_E_link_c_ctn_new_elem_lua(const char *link_id)
405 {
406   parse_E_link_ctn_new_elem(link_id);
407 }
408
409 /**
410  * \brief Store the route by calling the set_route function of the current routing component
411  */
412 static void parse_E_route_store_route(void)
413 {
414   name_route_extended_t route = xbt_new0(s_name_route_extended_t, 1);
415   route->generic_route.link_list = link_list;
416   xbt_assert1(current_routing->set_route,
417               "no defined method \"set_route\" in \"%s\"",
418               current_routing->name);
419   (*(current_routing->set_route)) (current_routing, src, dst, route);
420   link_list = NULL;
421   src = NULL;
422   dst = NULL;
423 }
424
425 /**
426  * \brief Store the ASroute by calling the set_ASroute function of the current routing component
427  */
428 static void parse_E_ASroute_store_route(void)
429 {
430   name_route_extended_t e_route = xbt_new0(s_name_route_extended_t, 1);
431   e_route->generic_route.link_list = link_list;
432   e_route->src_gateway = xbt_strdup(gw_src);
433   e_route->dst_gateway = xbt_strdup(gw_dst);
434   xbt_assert1(current_routing->set_ASroute,
435               "no defined method \"set_ASroute\" in \"%s\"",
436               current_routing->name);
437   (*(current_routing->set_ASroute)) (current_routing, src, dst, e_route);
438   link_list = NULL;
439   src = NULL;
440   dst = NULL;
441   gw_src = NULL;
442   gw_dst = NULL;
443 }
444
445 /**
446  * \brief Store the bypass route by calling the set_bypassroute function of the current routing component
447  */
448 static void parse_E_bypassRoute_store_route(void)
449 {
450   route_extended_t e_route = xbt_new0(s_route_extended_t, 1);
451   e_route->generic_route.link_list = link_list;
452   e_route->src_gateway = xbt_strdup(gw_src);
453   e_route->dst_gateway = xbt_strdup(gw_dst);
454   xbt_assert1(current_routing->set_bypassroute,
455               "no defined method \"set_bypassroute\" in \"%s\"",
456               current_routing->name);
457   (*(current_routing->set_bypassroute)) (current_routing, src, dst,
458                                          e_route);
459   link_list = NULL;
460   src = NULL;
461   dst = NULL;
462   gw_src = NULL;
463   gw_dst = NULL;
464 }
465
466 /**
467  * \brief Make a new routing component
468  *
469  * make the new structure and
470  * set the parsing functions to allows parsing the part of the routing tree
471  */
472 static void parse_S_AS(char *AS_id, char *AS_routing)
473 {
474   routing_component_t new_routing;
475   model_type_t model = NULL;
476   char *wanted = AS_routing;
477   int cpt;
478   /* seach the routing model */
479   for (cpt = 0; routing_models[cpt].name; cpt++)
480     if (!strcmp(wanted, routing_models[cpt].name))
481       model = &routing_models[cpt];
482   /* if its not exist, error */
483   if (model == NULL) {
484     fprintf(stderr, "Routing model %s not found. Existing models:\n",
485             wanted);
486     for (cpt = 0; routing_models[cpt].name; cpt++)
487       if (!strcmp(wanted, routing_models[cpt].name))
488         fprintf(stderr, "   %s: %s\n", routing_models[cpt].name,
489                 routing_models[cpt].desc);
490     xbt_die(NULL);
491   }
492
493   /* make a new routing component */
494   new_routing = (routing_component_t) (*(model->create)) ();
495   new_routing->routing = model;
496   new_routing->hierarchy = SURF_ROUTING_NULL;
497   new_routing->name = xbt_strdup(AS_id);
498   new_routing->routing_sons = xbt_dict_new();
499
500   /* Hack for Vivaldi */
501   if(!strcmp(model->name,"Vivaldi"))
502         new_routing->get_latency = vivaldi_get_link_latency;
503
504   if (current_routing == NULL && global_routing->root == NULL) {
505
506     /* it is the first one */
507     new_routing->routing_father = NULL;
508     global_routing->root = new_routing;
509
510   } else if (current_routing != NULL && global_routing->root != NULL) {
511
512     xbt_assert1(!xbt_dict_get_or_null
513                 (current_routing->routing_sons, AS_id),
514                 "The AS \"%s\" already exists", AS_id);
515     /* it is a part of the tree */
516     new_routing->routing_father = current_routing;
517     /* set the father behavior */
518     if (current_routing->hierarchy == SURF_ROUTING_NULL)
519       current_routing->hierarchy = SURF_ROUTING_RECURSIVE;
520     /* add to the sons dictionary */
521     xbt_dict_set(current_routing->routing_sons, AS_id,
522                  (void *) new_routing, NULL);
523     /* add to the father element list */
524     (*(current_routing->set_autonomous_system)) (current_routing, AS_id);
525     /* unload the prev parse rules */
526     (*(current_routing->routing->unload)) ();
527
528   } else {
529     THROW0(arg_error, 0, "All defined components must be belong to a AS");
530   }
531   /* set the new parse rules */
532   (*(new_routing->routing->load)) ();
533   /* set the new current component of the tree */
534   current_routing = new_routing;
535 }
536
537 /*
538  * Detect the routing model type of the routing component from XML platforms
539  */
540 static void parse_S_AS_XML(void)
541 {
542   parse_S_AS(A_surfxml_AS_id, A_surfxml_AS_routing);
543 }
544
545 /*
546  * define the routing model type of routing component from lua script
547  */
548 static void parse_S_AS_lua(char *id, char *mode)
549 {
550   parse_S_AS(id, mode);
551 }
552
553
554 /**
555  * \brief Finish the creation of a new routing component
556  *
557  * When you finish to read the routing component, other structures must be created. 
558  * the "end" method allow to do that for any routing model type
559  */
560 static void parse_E_AS(const char *AS_id)
561 {
562
563   if (current_routing == NULL) {
564     THROW1(arg_error, 0, "Close AS(%s), that never open", AS_id);
565   } else {
566     network_element_info_t info = NULL;
567     xbt_assert1(!xbt_dict_get_or_null
568                 (global_routing->where_network_elements,
569                  current_routing->name), "The AS \"%s\" already exists",
570                 current_routing->name);
571     info = xbt_new0(s_network_element_info_t, 1);
572     info->rc_component = current_routing->routing_father;
573     info->rc_type = SURF_NETWORK_ELEMENT_AS;
574     xbt_dict_set(global_routing->where_network_elements,
575                  current_routing->name, info, xbt_free);
576     (*(current_routing->routing->unload)) ();
577     (*(current_routing->routing->end)) ();
578     current_routing = current_routing->routing_father;
579     if (current_routing != NULL)
580       (*(current_routing->routing->load)) ();
581   }
582 }
583
584 /*
585  * \brief Finish the creation of a new routing component from XML
586  */
587 static void parse_E_AS_XML(void)
588 {
589   parse_E_AS(A_surfxml_AS_id);
590 }
591
592 /*
593  * \brief Finish the creation of a new routing component from lua
594  */
595 static void parse_E_AS_lua(const char *id)
596 {
597   parse_E_AS(id);
598 }
599
600 /* Aux Business methods */
601
602 /**
603  * \brief Get the AS father and the first elements of the chain
604  *
605  * \param src the source host name 
606  * \param dst the destination host name
607  * 
608  * Get the common father of the to processing units, and the first different 
609  * father in the chain
610  */
611 static xbt_dynar_t elements_father(const char *src, const char *dst)
612 {
613
614   xbt_assert0(src && dst, "bad parameters for \"elements_father\" method");
615
616   xbt_dynar_t result = xbt_dynar_new(sizeof(char *), NULL);
617
618   routing_component_t src_as, dst_as;
619   int index_src, index_dst, index_father_src, index_father_dst;
620   xbt_dynar_t path_src = NULL;
621   xbt_dynar_t path_dst = NULL;
622   routing_component_t current = NULL;
623   routing_component_t *current_src = NULL;
624   routing_component_t *current_dst = NULL;
625   routing_component_t *father = NULL;
626
627   /* (1) find the as where the src and dst are located */
628   src_as = ((network_element_info_t)
629             xbt_dict_get_or_null(global_routing->where_network_elements,
630                                  src))->rc_component;
631   dst_as = ((network_element_info_t)
632             xbt_dict_get_or_null(global_routing->where_network_elements,
633                                  dst))->rc_component;
634   xbt_assert2(src_as
635               && dst_as,
636               "Ask for route \"from\"(%s) or \"to\"(%s) no found", src,
637               dst);
638
639   /* (2) find the path to the root routing component */
640   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
641   current = src_as;
642   while (current != NULL) {
643     xbt_dynar_push(path_src, &current);
644     current = current->routing_father;
645   }
646   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
647   current = dst_as;
648   while (current != NULL) {
649     xbt_dynar_push(path_dst, &current);
650     current = current->routing_father;
651   }
652
653   /* (3) find the common father */
654   index_src = path_src->used - 1;
655   index_dst = path_dst->used - 1;
656   current_src = xbt_dynar_get_ptr(path_src, index_src);
657   current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
658   while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
659     current_src = xbt_dynar_get_ptr(path_src, index_src);
660     current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
661     index_src--;
662     index_dst--;
663   }
664   index_src++;
665   index_dst++;
666   current_src = xbt_dynar_get_ptr(path_src, index_src);
667   current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
668
669   /* (4) they are not in the same routing component, make the path */
670   index_father_src = index_src + 1;
671   index_father_dst = index_dst + 1;
672
673   if (*current_src == *current_dst)
674     father = current_src;
675   else
676     father = xbt_dynar_get_ptr(path_src, index_father_src);
677
678   /* (5) result generation */
679   xbt_dynar_push(result, father);       /* first same the father of src and dst */
680   xbt_dynar_push(result, current_src);  /* second the first different father of src */
681   xbt_dynar_push(result, current_dst);  /* three  the first different father of dst */
682
683   xbt_dynar_free(&path_src);
684   xbt_dynar_free(&path_dst);
685
686   return result;
687 }
688
689 /* Global Business methods */
690
691 /**
692  * \brief Recursive function for get_route
693  *
694  * \param src the source host name 
695  * \param dst the destination host name
696  * 
697  * This fuction is call by "get_route". It allow to walk through the 
698  * routing components tree.
699  */
700 static route_extended_t _get_route(const char *src, const char *dst)
701 {
702
703   void *link;
704   unsigned int cpt = 0;
705
706   DEBUG2("Solve route  \"%s\" to \"%s\"", src, dst);
707
708   xbt_assert0(src && dst, "bad parameters for \"_get_route\" method");
709
710   route_extended_t e_route, e_route_cnt, e_route_src = NULL, e_route_dst =
711       NULL;
712
713   xbt_dynar_t elem_father_list = elements_father(src, dst);
714
715   routing_component_t common_father =
716       xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
717   routing_component_t src_father =
718       xbt_dynar_get_as(elem_father_list, 1, routing_component_t);
719   routing_component_t dst_father =
720       xbt_dynar_get_as(elem_father_list, 2, routing_component_t);
721
722   e_route = xbt_new0(s_route_extended_t, 1);
723   e_route->src_gateway = NULL;
724   e_route->dst_gateway = NULL;
725   e_route->generic_route.link_list =
726       xbt_dynar_new(global_routing->size_of_link, NULL);
727
728   if (src_father == dst_father) {       /* SURF_ROUTING_BASE */
729
730     if (strcmp(src, dst)) {
731       e_route_cnt =
732           (*(common_father->get_route)) (common_father, src, dst);
733       xbt_assert2(e_route_cnt, "no route between \"%s\" and \"%s\"", src,
734                   dst);
735       xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
736         xbt_dynar_push(e_route->generic_route.link_list, &link);
737       }
738       generic_free_extended_route(e_route_cnt);
739     }
740
741   } else {                      /* SURF_ROUTING_RECURSIVE */
742
743     route_extended_t e_route_bypass = NULL;
744
745     if (common_father->get_bypass_route)
746       e_route_bypass =
747           (*(common_father->get_bypass_route)) (common_father, src, dst);
748
749     if (e_route_bypass)
750       e_route_cnt = e_route_bypass;
751     else
752       e_route_cnt =
753           (*(common_father->get_route)) (common_father, src_father->name,
754                                          dst_father->name);
755
756     xbt_assert2(e_route_cnt, "no route between \"%s\" and \"%s\"",
757                 src_father->name, dst_father->name);
758
759     xbt_assert2((e_route_cnt->src_gateway == NULL) ==
760                 (e_route_cnt->dst_gateway == NULL),
761                 "bad gateway for route between \"%s\" and \"%s\"", src,
762                 dst);
763
764     if (strcmp(src, e_route_cnt->src_gateway)) {
765       e_route_src = _get_route(src, e_route_cnt->src_gateway);
766       xbt_assert2(e_route_src, "no route between \"%s\" and \"%s\"", src,
767                   e_route_cnt->src_gateway);
768       xbt_dynar_foreach(e_route_src->generic_route.link_list, cpt, link) {
769         xbt_dynar_push(e_route->generic_route.link_list, &link);
770       }
771     }
772
773     xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
774       xbt_dynar_push(e_route->generic_route.link_list, &link);
775     }
776
777     if (strcmp(e_route_cnt->dst_gateway, dst)) {
778       e_route_dst = _get_route(e_route_cnt->dst_gateway, dst);
779       xbt_assert2(e_route_dst, "no route between \"%s\" and \"%s\"",
780                   e_route_cnt->dst_gateway, dst);
781       xbt_dynar_foreach(e_route_dst->generic_route.link_list, cpt, link) {
782         xbt_dynar_push(e_route->generic_route.link_list, &link);
783       }
784     }
785
786     e_route->src_gateway = xbt_strdup(e_route_cnt->src_gateway);
787     e_route->dst_gateway = xbt_strdup(e_route_cnt->dst_gateway);
788
789     generic_free_extended_route(e_route_src);
790     generic_free_extended_route(e_route_cnt);
791     generic_free_extended_route(e_route_dst);
792   }
793
794   xbt_dynar_free(&elem_father_list);
795
796   return e_route;
797 }
798
799 static double _get_latency(const char *src, const char *dst)
800 {
801   double latency, latency_src, latency_dst = 0.0;
802
803   DEBUG2("Solve route  \"%s\" to \"%s\"", src, dst);
804
805   xbt_assert0(src && dst, "bad parameters for \"_get_route\" method");
806
807   route_extended_t e_route_cnt;
808
809   xbt_dynar_t elem_father_list = elements_father(src, dst);
810
811   routing_component_t common_father =
812       xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
813   routing_component_t src_father =
814       xbt_dynar_get_as(elem_father_list, 1, routing_component_t);
815   routing_component_t dst_father =
816       xbt_dynar_get_as(elem_father_list, 2, routing_component_t);
817
818   if (src_father == dst_father) {       /* SURF_ROUTING_BASE */
819
820     if (strcmp(src, dst)) {
821       latency =
822           (*(common_father->get_latency)) (common_father, src, dst);
823       xbt_assert2(latency>=0, "no route between \"%s\" and \"%s\"", src,
824                   dst);
825      } else latency = 0;
826   } else {                      /* SURF_ROUTING_RECURSIVE */
827      route_extended_t e_route_bypass = NULL;
828
829     if (common_father->get_bypass_route)
830       e_route_bypass =
831           (*(common_father->get_bypass_route)) (common_father, src, dst);
832
833     xbt_assert0(!e_route_bypass,"Bypass cannot work yet with get_latency"); 
834                                                  
835     e_route_cnt =
836           (*(common_father->get_route)) (common_father, src_father->name,
837                                          dst_father->name);
838
839     xbt_assert2(e_route_cnt, "no route between \"%s\" and \"%s\"",
840                 src_father->name, dst_father->name);
841
842     xbt_assert2((e_route_cnt->src_gateway == NULL) ==
843                 (e_route_cnt->dst_gateway == NULL),
844                 "bad gateway for route between \"%s\" and \"%s\"", src,
845                 dst);            
846     latency =
847           (*(common_father->get_latency)) (common_father, e_route_cnt->src_gateway,
848                                          e_route_cnt->src_gateway);
849     xbt_assert2(latency>=0, "no route between \"%s\" and \"%s\"",
850                 src_father->name, dst_father->name);
851     
852
853     if (src != e_route_cnt->src_gateway) {
854
855       latency_src = _get_latency(src, e_route_cnt->src_gateway);
856       xbt_assert2(latency_src>=0, "no route between \"%s\" and \"%s\"", src,
857                   e_route_cnt->src_gateway);
858       latency += latency_src;
859     }
860
861     if (e_route_cnt->dst_gateway != dst) {
862     
863       latency_dst = _get_latency(e_route_cnt->dst_gateway, dst);
864       xbt_assert2(latency_dst>=0, "no route between \"%s\" and \"%s\"",
865                   e_route_cnt->dst_gateway, dst);
866       latency += latency_dst;
867     }
868         
869   }
870
871   xbt_dynar_free(&elem_father_list);
872
873   return latency;
874 }
875
876 /**
877  * \brief Generic method: find a route between hosts
878  *
879  * \param src the source host name 
880  * \param dst the destination host name
881  * 
882  * walk through the routing components tree and find a route between hosts
883  * by calling the differents "get_route" functions in each routing component.
884  * No need to free the returned dynar. It will be freed at the next call.
885  */
886 static xbt_dynar_t get_route(const char *src, const char *dst)
887 {
888
889   route_extended_t e_route;
890   xbt_dynar_t elem_father_list = NULL;
891   routing_component_t common_father = NULL;
892
893   if (strcmp(src, dst))
894     e_route = _get_route(src, dst);
895   else {
896     elem_father_list = elements_father(src, dst);
897     common_father =
898         xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
899
900     e_route = (*(common_father->get_route)) (common_father, src, dst);
901     xbt_dynar_free(&elem_father_list);
902   }
903
904   xbt_assert2(e_route, "no route between \"%s\" and \"%s\"", src, dst);
905
906   if (global_routing->last_route)
907     xbt_dynar_free(&(global_routing->last_route));
908   global_routing->last_route = e_route->generic_route.link_list;
909
910   if (e_route->src_gateway)
911     xbt_free(e_route->src_gateway);
912   if (e_route->dst_gateway)
913     xbt_free(e_route->dst_gateway);
914
915   xbt_free(e_route);
916
917 /*
918   if (xbt_dynar_length(global_routing->last_route) == 0)
919     return NULL;
920   else
921 */
922     return global_routing->last_route;
923 }
924
925 /**
926  * \brief Generic method: find a route between hosts
927  *
928  * \param src the source host name
929  * \param dst the destination host name
930  *
931  * walk through the routing components tree and find a route between hosts
932  * by calling the differents "get_route" functions in each routing component.
933  * Leaves the caller the responsability to clean the returned dynar.
934  */
935 static xbt_dynar_t get_route_no_cleanup(const char *src, const char *dst)
936 {
937         xbt_dynar_t d = get_route(src,dst);
938         global_routing->last_route = NULL;
939         return d;
940 }
941
942 /*Get Latency*/
943 static double get_latency(const char *src, const char *dst)
944 {
945
946   double latency = -1.0;
947   xbt_dynar_t elem_father_list = elements_father(src, dst);
948   routing_component_t common_father =
949       xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
950
951   if (strcmp(src, dst))
952     latency = _get_latency(src, dst);
953   else
954     latency = (*(common_father->get_latency)) (common_father, src, dst);
955
956   xbt_assert2(latency>=0.0, "no route between \"%s\" and \"%s\"", src, dst);
957   xbt_dynar_free(&elem_father_list);
958
959   return latency;
960 }
961
962 /**
963  * \brief Recursive function for finalize
964  *
965  * \param rc the source host name 
966  * 
967  * This fuction is call by "finalize". It allow to finalize the 
968  * AS or routing components. It delete all the structures.
969  */
970 static void _finalize(routing_component_t rc)
971 {
972   if (rc) {
973     xbt_dict_cursor_t cursor = NULL;
974     char *key;
975     routing_component_t elem;
976     xbt_dict_foreach(rc->routing_sons, cursor, key, elem) {
977       _finalize(elem);
978     }
979     xbt_dict_t tmp_sons = rc->routing_sons;
980     char *tmp_name = rc->name;
981     xbt_dict_free(&tmp_sons);
982     xbt_free(tmp_name);
983     xbt_assert1(rc->finalize, "no defined method \"finalize\" in \"%s\"",
984                 current_routing->name);
985     (*(rc->finalize)) (rc);
986   }
987 }
988
989 /**
990  * \brief Generic method: delete all the routing structures
991  * 
992  * walk through the routing components tree and delete the structures
993  * by calling the differents "finalize" functions in each routing component
994  */
995 static void finalize(void)
996 {
997   /* delete recursibly all the tree */
998   _finalize(global_routing->root);
999   /* delete "where" dict */
1000   xbt_dict_free(&(global_routing->where_network_elements));
1001   xbt_dict_free(&(coordinates));
1002   /* delete last_route */
1003   xbt_dynar_free(&(global_routing->last_route));
1004   /* delete global routing structure */
1005   xbt_free(global_routing);
1006 }
1007
1008 static xbt_dynar_t recursive_get_onelink_routes(routing_component_t rc)
1009 {
1010   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
1011
1012   //adding my one link routes
1013   unsigned int cpt;
1014   void *link;
1015   xbt_dynar_t onelink_mine = rc->get_onelink_routes(rc);
1016   if (onelink_mine) {
1017     xbt_dynar_foreach(onelink_mine, cpt, link) {
1018       xbt_dynar_push(ret, &link);
1019     }
1020   }
1021   //recursing
1022   char *key;
1023   xbt_dict_cursor_t cursor = NULL;
1024   routing_component_t rc_child;
1025   xbt_dict_foreach(rc->routing_sons, cursor, key, rc_child) {
1026     xbt_dynar_t onelink_child = recursive_get_onelink_routes(rc_child);
1027     if (onelink_child) {
1028       xbt_dynar_foreach(onelink_child, cpt, link) {
1029         xbt_dynar_push(ret, &link);
1030       }
1031     }
1032   }
1033   return ret;
1034 }
1035
1036 static xbt_dynar_t get_onelink_routes(void)
1037 {
1038   return recursive_get_onelink_routes(global_routing->root);
1039 }
1040
1041 static e_surf_network_element_type_t get_network_element_type(const char
1042                                                               *name)
1043 {
1044   network_element_info_t rc = NULL;
1045   rc = xbt_dict_get(global_routing->where_network_elements, name);
1046   return rc->rc_type;
1047 }
1048
1049 /**
1050  * \brief Generic method: create the global routing schema
1051  * 
1052  * Make a global routing structure and set all the parsing functions.
1053  */
1054 void routing_model_create(size_t size_of_links, void *loopback, double_f_cpvoid_t get_link_latency_fun)
1055 {
1056   /* config the uniq global routing */
1057   global_routing = xbt_new0(s_routing_global_t, 1);
1058   global_routing->where_network_elements = xbt_dict_new();
1059   global_routing->root = NULL;
1060   global_routing->get_route = get_route;
1061   global_routing->get_latency = get_latency;
1062   global_routing->get_route_no_cleanup = get_route_no_cleanup;
1063   global_routing->get_onelink_routes = get_onelink_routes;
1064   global_routing->get_network_element_type = get_network_element_type;
1065   global_routing->finalize = finalize;
1066   global_routing->loopback = loopback;
1067   global_routing->size_of_link = size_of_links;
1068   global_routing->last_route = NULL;
1069   get_link_latency = get_link_latency_fun;
1070   /* no current routing at moment */
1071   current_routing = NULL;
1072
1073   coordinates = xbt_dict_new();
1074
1075   /* parse generic elements */
1076   surfxml_add_callback(STag_surfxml_host_cb_list, &parse_S_host_XML);
1077   surfxml_add_callback(ETag_surfxml_host_cb_list, &parse_E_host_XML);
1078   surfxml_add_callback(STag_surfxml_router_cb_list, &parse_S_router);
1079
1080   surfxml_add_callback(STag_surfxml_route_cb_list,
1081                        &parse_S_route_new_and_endpoints_XML);
1082   surfxml_add_callback(STag_surfxml_ASroute_cb_list,
1083                        &parse_S_ASroute_new_and_endpoints);
1084   surfxml_add_callback(STag_surfxml_bypassRoute_cb_list,
1085                        &parse_S_bypassRoute_new_and_endpoints);
1086
1087   surfxml_add_callback(ETag_surfxml_link_ctn_cb_list,
1088                        &parse_E_link_ctn_new_elem_XML);
1089
1090   surfxml_add_callback(ETag_surfxml_route_cb_list,
1091                        &parse_E_route_store_route);
1092   surfxml_add_callback(ETag_surfxml_ASroute_cb_list,
1093                        &parse_E_ASroute_store_route);
1094   surfxml_add_callback(ETag_surfxml_bypassRoute_cb_list,
1095                        &parse_E_bypassRoute_store_route);
1096
1097   surfxml_add_callback(STag_surfxml_AS_cb_list, &parse_S_AS_XML);
1098   surfxml_add_callback(ETag_surfxml_AS_cb_list, &parse_E_AS_XML);
1099
1100   surfxml_add_callback(STag_surfxml_cluster_cb_list,
1101                        &routing_parse_Scluster);
1102
1103   surfxml_add_callback(STag_surfxml_peer_cb_list,
1104                          &routing_parse_Speer);
1105
1106 #ifdef HAVE_TRACING
1107   instr_routing_define_callbacks();
1108 #endif
1109 }
1110
1111 void surf_config_add_callback(void)
1112 {
1113         surf_parse_reset_parser();
1114         surfxml_add_callback(STag_surfxml_config_cb_list, &routing_parse_Sconfig);
1115         surfxml_add_callback(ETag_surfxml_config_cb_list, &routing_parse_Econfig);
1116         surfxml_add_callback(STag_surfxml_prop_cb_list, &parse_properties);
1117 }
1118
1119 /* ************************************************************************** */
1120 /* *************************** FULL ROUTING ********************************* */
1121
1122 #define TO_ROUTE_FULL(i,j) routing->routing_table[(i)+(j)*table_size]
1123
1124 /* Routing model structure */
1125
1126 typedef struct {
1127   s_routing_component_t generic_routing;
1128   route_extended_t *routing_table;
1129 } s_routing_component_full_t, *routing_component_full_t;
1130
1131 /* Business methods */
1132 static xbt_dynar_t full_get_onelink_routes(routing_component_t rc)
1133 {
1134   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
1135
1136   routing_component_full_t routing = (routing_component_full_t) rc;
1137   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1138   xbt_dict_cursor_t c1 = NULL, c2 = NULL;
1139   char *k1, *d1, *k2, *d2;
1140   xbt_dict_foreach(routing->generic_routing.to_index, c1, k1, d1) {
1141     xbt_dict_foreach(routing->generic_routing.to_index, c2, k2, d2) {
1142       int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, k1);
1143       int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, k2);
1144       xbt_assert2(src_id
1145                   && dst_id,
1146                   "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1147                   src, dst);
1148       route_extended_t route = TO_ROUTE_FULL(*src_id, *dst_id);
1149       if (route) {
1150         if (xbt_dynar_length(route->generic_route.link_list) == 1) {
1151           void *link =
1152               *(void **) xbt_dynar_get_ptr(route->generic_route.link_list,
1153                                            0);
1154           onelink_t onelink = xbt_new0(s_onelink_t, 1);
1155           onelink->link_ptr = link;
1156           if (routing->generic_routing.hierarchy == SURF_ROUTING_BASE) {
1157             onelink->src = xbt_strdup(k1);
1158             onelink->dst = xbt_strdup(k2);
1159           } else if (routing->generic_routing.hierarchy ==
1160                      SURF_ROUTING_RECURSIVE) {
1161             onelink->src = xbt_strdup(route->src_gateway);
1162             onelink->dst = xbt_strdup(route->dst_gateway);
1163           }
1164           xbt_dynar_push(ret, &onelink);
1165         }
1166       }
1167     }
1168   }
1169   return ret;
1170 }
1171
1172 static route_extended_t full_get_route(routing_component_t rc,
1173                                        const char *src, const char *dst)
1174 {
1175   xbt_assert1(rc && src
1176               && dst,
1177               "Invalid params for \"get_route\" function at AS \"%s\"",
1178               rc->name);
1179
1180   /* set utils vars */
1181   routing_component_full_t routing = (routing_component_full_t) rc;
1182   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1183
1184   generic_src_dst_check(rc, src, dst);
1185   int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, src);
1186   int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, dst);
1187   xbt_assert2(src_id
1188               && dst_id,
1189               "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1190               src, dst);
1191
1192   route_extended_t e_route = NULL;
1193   route_extended_t new_e_route = NULL;
1194   void *link;
1195   unsigned int cpt = 0;
1196
1197   e_route = TO_ROUTE_FULL(*src_id, *dst_id);
1198
1199   if (e_route) {
1200     new_e_route = xbt_new0(s_route_extended_t, 1);
1201     new_e_route->src_gateway = xbt_strdup(e_route->src_gateway);
1202     new_e_route->dst_gateway = xbt_strdup(e_route->dst_gateway);
1203     new_e_route->generic_route.link_list =
1204         xbt_dynar_new(global_routing->size_of_link, NULL);
1205     xbt_dynar_foreach(e_route->generic_route.link_list, cpt, link) {
1206       xbt_dynar_push(new_e_route->generic_route.link_list, &link);
1207     }
1208   }
1209   return new_e_route;
1210 }
1211
1212 static void full_finalize(routing_component_t rc)
1213 {
1214   routing_component_full_t routing = (routing_component_full_t) rc;
1215   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1216   int i, j;
1217   if (routing) {
1218     /* Delete routing table */
1219     for (i = 0; i < table_size; i++)
1220       for (j = 0; j < table_size; j++)
1221         generic_free_extended_route(TO_ROUTE_FULL(i, j));
1222     xbt_free(routing->routing_table);
1223     /* Delete bypass dict */
1224     xbt_dict_free(&rc->bypassRoutes);
1225     /* Delete index dict */
1226     xbt_dict_free(&rc->to_index);
1227     /* Delete structure */
1228     xbt_free(rc);
1229   }
1230 }
1231
1232 /* Creation routing model functions */
1233
1234 static void *model_full_create(void)
1235 {
1236   routing_component_full_t new_component =
1237       xbt_new0(s_routing_component_full_t, 1);
1238   new_component->generic_routing.set_processing_unit =
1239       generic_set_processing_unit;
1240   new_component->generic_routing.set_autonomous_system =
1241       generic_set_autonomous_system;
1242   new_component->generic_routing.set_route = model_full_set_route;
1243   new_component->generic_routing.set_ASroute = model_full_set_route;
1244   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
1245   new_component->generic_routing.get_route = full_get_route;
1246   new_component->generic_routing.get_latency = generic_get_link_latency;
1247   new_component->generic_routing.get_onelink_routes =
1248       full_get_onelink_routes;
1249   new_component->generic_routing.get_bypass_route =
1250       generic_get_bypassroute;
1251   new_component->generic_routing.finalize = full_finalize;
1252   new_component->generic_routing.to_index = xbt_dict_new();
1253   new_component->generic_routing.bypassRoutes = xbt_dict_new();
1254   return new_component;
1255 }
1256
1257 static void model_full_load(void)
1258 {
1259   /* use "surfxml_add_callback" to add a parse function call */
1260 }
1261
1262 static void model_full_unload(void)
1263 {
1264   /* use "surfxml_del_callback" to remove a parse function call */
1265 }
1266
1267 static void model_full_end(void)
1268 {
1269   unsigned int i;
1270   route_extended_t e_route;
1271
1272   /* set utils vars */
1273   routing_component_full_t routing =
1274       ((routing_component_full_t) current_routing);
1275   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1276
1277   /* Create table if necessary */
1278   if(!routing->routing_table)
1279           routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
1280
1281   /* Add the loopback if needed */
1282   if (current_routing->hierarchy == SURF_ROUTING_BASE) {
1283     for (i = 0; i < table_size; i++) {
1284       e_route = TO_ROUTE_FULL(i, i);
1285       if (!e_route) {
1286         e_route = xbt_new0(s_route_extended_t, 1);
1287         e_route->src_gateway = NULL;
1288         e_route->dst_gateway = NULL;
1289         e_route->generic_route.link_list =
1290             xbt_dynar_new(global_routing->size_of_link, NULL);
1291         xbt_dynar_push(e_route->generic_route.link_list,
1292                        &global_routing->loopback);
1293         TO_ROUTE_FULL(i, i) = e_route;
1294       }
1295     }
1296   }
1297 }
1298
1299 static void model_full_set_route(routing_component_t rc, const char *src,
1300                 const char *dst, name_route_extended_t route)
1301 {
1302         int *src_id, *dst_id;
1303         src_id = xbt_dict_get_or_null(rc->to_index, src);
1304         dst_id = xbt_dict_get_or_null(rc->to_index, dst);
1305         routing_component_full_t routing = ((routing_component_full_t) rc);
1306         size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1307
1308         xbt_assert2(src_id
1309                           && dst_id, "Network elements %s or %s not found", src, dst);
1310
1311         xbt_assert2(xbt_dynar_length(route->generic_route.link_list) > 0,
1312                           "Invalid count of links, must be greater than zero (%s,%s)",
1313                           src, dst);
1314
1315         if(!routing->routing_table)
1316                 routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
1317
1318         if(TO_ROUTE_FULL(*src_id, *dst_id))
1319         {
1320                 char * link_name;
1321                 unsigned int i;
1322                 xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1323                 xbt_dynar_foreach(route->generic_route.link_list,i,link_name)
1324                 {
1325                         void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1326                         xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1327                         xbt_dynar_push(link_route_to_test,&link);
1328                 }
1329                 xbt_assert2(!xbt_dynar_compare(
1330                           (void*)TO_ROUTE_FULL(*src_id, *dst_id)->generic_route.link_list,
1331                           (void*)link_route_to_test,
1332                           (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1333                           "The route between \"%s\" and \"%s\" already exists. If you are trying to define a reverse route, you must set the symmetrical=no attribute to your routes tags.", src,dst);
1334                 xbt_dynar_free(&link_route_to_test);
1335         }
1336         else
1337         {
1338                   if(!route->dst_gateway && !route->src_gateway)
1339                           DEBUG2("Load Route from \"%s\" to \"%s\"", src, dst);
1340                   else
1341                           DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
1342                                  route->src_gateway, dst, route->dst_gateway);
1343               TO_ROUTE_FULL(*src_id, *dst_id) = generic_new_extended_route(rc->hierarchy,route,1);
1344               xbt_dynar_shrink(TO_ROUTE_FULL(*src_id, *dst_id)->generic_route.link_list, 0);
1345         }
1346
1347         if( A_surfxml_route_symmetrical == A_surfxml_route_symmetrical_YES
1348                 || A_surfxml_ASroute_symmetrical == A_surfxml_ASroute_symmetrical_YES )
1349         {
1350                 if(route->dst_gateway && route->src_gateway)
1351                 {
1352                   char *gw_src = xbt_strdup(route->src_gateway);
1353                   char *gw_dst = xbt_strdup(route->dst_gateway);
1354                   route->src_gateway = gw_dst;
1355                   route->dst_gateway = gw_src;
1356                 }
1357                 if(TO_ROUTE_FULL(*dst_id, *src_id))
1358                 {
1359                         char * link_name;
1360                         unsigned int i;
1361                         xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1362                         for(i=xbt_dynar_length(route->generic_route.link_list) ;i>0 ;i--)
1363                         {
1364                                 link_name = xbt_dynar_get_as(route->generic_route.link_list,i-1,void *);
1365                                 void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1366                                 xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1367                                 xbt_dynar_push(link_route_to_test,&link);
1368                         }
1369                         xbt_assert2(!xbt_dynar_compare(
1370                                   (void*)TO_ROUTE_FULL(*dst_id, *src_id)->generic_route.link_list,
1371                               (void*)link_route_to_test,
1372                                   (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1373                                   "The route between \"%s\" and \"%s\" already exists", src,dst);
1374                         xbt_dynar_free(&link_route_to_test);
1375                 }
1376                 else
1377                 {
1378                           if(!route->dst_gateway && !route->src_gateway)
1379                                   DEBUG2("Load Route from \"%s\" to \"%s\"", dst, src);
1380                           else
1381                                   DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
1382                                          route->src_gateway, src, route->dst_gateway);
1383                       TO_ROUTE_FULL(*dst_id, *src_id) = generic_new_extended_route(rc->hierarchy,route,0);
1384                       xbt_dynar_shrink(TO_ROUTE_FULL(*dst_id, *src_id)->generic_route.link_list, 0);
1385                 }
1386
1387         }
1388 }
1389
1390 /* ************************************************************************** */
1391 /* *************************** FLOYD ROUTING ******************************** */
1392
1393 #define TO_FLOYD_COST(i,j) (routing->cost_table)[(i)+(j)*table_size]
1394 #define TO_FLOYD_PRED(i,j) (routing->predecessor_table)[(i)+(j)*table_size]
1395 #define TO_FLOYD_LINK(i,j) (routing->link_table)[(i)+(j)*table_size]
1396
1397 /* Routing model structure */
1398
1399 typedef struct {
1400   s_routing_component_t generic_routing;
1401   /* vars for calculate the floyd algorith. */
1402   int *predecessor_table;
1403   double *cost_table;
1404   route_extended_t *link_table; /* char* -> int* */
1405 } s_routing_component_floyd_t, *routing_component_floyd_t;
1406
1407 static route_extended_t floyd_get_route(routing_component_t rc,
1408                                         const char *src, const char *dst);
1409
1410 /* Business methods */
1411 static xbt_dynar_t floyd_get_onelink_routes(routing_component_t rc)
1412 {
1413   xbt_dynar_t ret = xbt_dynar_new(sizeof(onelink_t), xbt_free);
1414
1415   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1416   //size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1417   xbt_dict_cursor_t c1 = NULL, c2 = NULL;
1418   char *k1, *d1, *k2, *d2;
1419   xbt_dict_foreach(routing->generic_routing.to_index, c1, k1, d1) {
1420     xbt_dict_foreach(routing->generic_routing.to_index, c2, k2, d2) {
1421       route_extended_t route = floyd_get_route(rc, k1, k2);
1422       if (route) {
1423         if (xbt_dynar_length(route->generic_route.link_list) == 1) {
1424           void *link =
1425               *(void **) xbt_dynar_get_ptr(route->generic_route.link_list,
1426                                            0);
1427           onelink_t onelink = xbt_new0(s_onelink_t, 1);
1428           onelink->link_ptr = link;
1429           if (routing->generic_routing.hierarchy == SURF_ROUTING_BASE) {
1430             onelink->src = xbt_strdup(k1);
1431             onelink->dst = xbt_strdup(k2);
1432           } else if (routing->generic_routing.hierarchy ==
1433                      SURF_ROUTING_RECURSIVE) {
1434             onelink->src = xbt_strdup(route->src_gateway);
1435             onelink->dst = xbt_strdup(route->dst_gateway);
1436           }
1437           xbt_dynar_push(ret, &onelink);
1438         }
1439       }
1440     }
1441   }
1442   return ret;
1443 }
1444
1445 static route_extended_t floyd_get_route(routing_component_t rc,
1446                                         const char *src, const char *dst)
1447 {
1448   xbt_assert1(rc && src
1449               && dst,
1450               "Invalid params for \"get_route\" function at AS \"%s\"",
1451               rc->name);
1452
1453   /* set utils vars */
1454   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1455   size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1456
1457   generic_src_dst_check(rc, src, dst);
1458   int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, src);
1459   int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, dst);
1460   xbt_assert2(src_id
1461               && dst_id,
1462               "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1463               src, dst);
1464
1465   /* create a result route */
1466   route_extended_t new_e_route = xbt_new0(s_route_extended_t, 1);
1467   new_e_route->generic_route.link_list =
1468       xbt_dynar_new(global_routing->size_of_link, NULL);
1469   new_e_route->src_gateway = NULL;
1470   new_e_route->dst_gateway = NULL;
1471
1472   int first = 1;
1473   int pred = *dst_id;
1474   int prev_pred = 0;
1475   char *gw_src = NULL, *gw_dst =
1476       NULL, *prev_gw_src, *prev_gw_dst, *first_gw = NULL;
1477   unsigned int cpt;
1478   void *link;
1479   xbt_dynar_t links;
1480
1481   do {
1482     prev_pred = pred;
1483     pred = TO_FLOYD_PRED(*src_id, pred);
1484     if (pred == -1)             /* if no pred in route -> no route to host */
1485       break;
1486     xbt_assert2(TO_FLOYD_LINK(pred, prev_pred),
1487                 "Invalid link for the route between \"%s\" or \"%s\"", src,
1488                 dst);
1489
1490     prev_gw_src = gw_src;
1491     prev_gw_dst = gw_dst;
1492
1493     route_extended_t e_route = TO_FLOYD_LINK(pred, prev_pred);
1494     gw_src = e_route->src_gateway;
1495     gw_dst = e_route->dst_gateway;
1496
1497     if (first)
1498       first_gw = gw_dst;
1499
1500     if (rc->hierarchy == SURF_ROUTING_RECURSIVE && !first
1501         && strcmp(gw_dst, prev_gw_src)) {
1502       xbt_dynar_t e_route_as_to_as =
1503           (*(global_routing->get_route)) (gw_dst, prev_gw_src);
1504       xbt_assert2(e_route_as_to_as, "no route between \"%s\" and \"%s\"",
1505                   gw_dst, prev_gw_src);
1506       links = e_route_as_to_as;
1507       int pos = 0;
1508       xbt_dynar_foreach(links, cpt, link) {
1509         xbt_dynar_insert_at(new_e_route->generic_route.link_list, pos,
1510                             &link);
1511         pos++;
1512       }
1513     }
1514
1515     links = e_route->generic_route.link_list;
1516     xbt_dynar_foreach(links, cpt, link) {
1517       xbt_dynar_unshift(new_e_route->generic_route.link_list, &link);
1518     }
1519     first = 0;
1520
1521   } while (pred != *src_id);
1522   xbt_assert4(pred != -1, "no route from host %d to %d (\"%s\" to \"%s\")",
1523               *src_id, *dst_id, src, dst);
1524
1525   if (rc->hierarchy == SURF_ROUTING_RECURSIVE) {
1526     new_e_route->src_gateway = xbt_strdup(gw_src);
1527     new_e_route->dst_gateway = xbt_strdup(first_gw);
1528   }
1529
1530   return new_e_route;
1531 }
1532
1533 static void floyd_finalize(routing_component_t rc)
1534 {
1535   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1536   int i, j;
1537   size_t table_size;
1538   if (routing) {
1539     table_size = xbt_dict_length(routing->generic_routing.to_index);
1540     /* Delete link_table */
1541     for (i = 0; i < table_size; i++)
1542       for (j = 0; j < table_size; j++)
1543         generic_free_extended_route(TO_FLOYD_LINK(i, j));
1544     xbt_free(routing->link_table);
1545     /* Delete bypass dict */
1546     xbt_dict_free(&routing->generic_routing.bypassRoutes);
1547     /* Delete index dict */
1548     xbt_dict_free(&(routing->generic_routing.to_index));
1549     /* Delete dictionary index dict, predecessor and links table */
1550     xbt_free(routing->predecessor_table);
1551     /* Delete structure */
1552     xbt_free(rc);
1553   }
1554 }
1555
1556 static void *model_floyd_create(void)
1557 {
1558   routing_component_floyd_t new_component =
1559       xbt_new0(s_routing_component_floyd_t, 1);
1560   new_component->generic_routing.set_processing_unit =
1561       generic_set_processing_unit;
1562   new_component->generic_routing.set_autonomous_system =
1563       generic_set_autonomous_system;
1564   new_component->generic_routing.set_route = model_floyd_set_route;
1565   new_component->generic_routing.set_ASroute = model_floyd_set_route;
1566   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
1567   new_component->generic_routing.get_route = floyd_get_route;
1568   new_component->generic_routing.get_latency = generic_get_link_latency;
1569   new_component->generic_routing.get_onelink_routes =
1570       floyd_get_onelink_routes;
1571   new_component->generic_routing.get_bypass_route =
1572       generic_get_bypassroute;
1573   new_component->generic_routing.finalize = floyd_finalize;
1574   new_component->generic_routing.to_index = xbt_dict_new();
1575   new_component->generic_routing.bypassRoutes = xbt_dict_new();
1576   return new_component;
1577 }
1578
1579 static void model_floyd_load(void)
1580 {
1581   /* use "surfxml_add_callback" to add a parse function call */
1582 }
1583
1584 static void model_floyd_unload(void)
1585 {
1586   /* use "surfxml_del_callback" to remove a parse function call */
1587 }
1588
1589 static void model_floyd_end(void)
1590 {
1591
1592         routing_component_floyd_t routing =
1593           ((routing_component_floyd_t) current_routing);
1594
1595         unsigned int i, j, a, b, c;
1596
1597         /* set the size of table routing */
1598         size_t table_size = xbt_dict_length(routing->generic_routing.to_index);
1599
1600         if(!routing->link_table)
1601         {
1602                 /* Create Cost, Predecessor and Link tables */
1603                 routing->cost_table = xbt_new0(double, table_size * table_size);       /* link cost from host to host */
1604                 routing->predecessor_table = xbt_new0(int, table_size * table_size);  /* predecessor host numbers */
1605                 routing->link_table = xbt_new0(route_extended_t, table_size * table_size);    /* actual link between src and dst */
1606
1607                 /* Initialize costs and predecessors */
1608                 for (i = 0; i < table_size; i++)
1609                 for (j = 0; j < table_size; j++) {
1610                   TO_FLOYD_COST(i, j) = DBL_MAX;
1611                   TO_FLOYD_PRED(i, j) = -1;
1612                   TO_FLOYD_LINK(i, j) = NULL;       /* fixed, missing in the previous version */
1613                 }
1614         }
1615
1616         /* Add the loopback if needed */
1617         if (current_routing->hierarchy == SURF_ROUTING_BASE) {
1618                 for (i = 0; i < table_size; i++) {
1619                   route_extended_t e_route = TO_FLOYD_LINK(i, i);
1620                   if (!e_route) {
1621                         e_route = xbt_new0(s_route_extended_t, 1);
1622                         e_route->src_gateway = NULL;
1623                         e_route->dst_gateway = NULL;
1624                         e_route->generic_route.link_list =
1625                                 xbt_dynar_new(global_routing->size_of_link, NULL);
1626                         xbt_dynar_push(e_route->generic_route.link_list,
1627                                                    &global_routing->loopback);
1628                         TO_FLOYD_LINK(i, i) = e_route;
1629                         TO_FLOYD_PRED(i, i) = i;
1630                         TO_FLOYD_COST(i, i) = 1;
1631                   }
1632                 }
1633         }
1634         /* Calculate path costs */
1635         for (c = 0; c < table_size; c++) {
1636                 for (a = 0; a < table_size; a++) {
1637                   for (b = 0; b < table_size; b++) {
1638                         if (TO_FLOYD_COST(a, c) < DBL_MAX && TO_FLOYD_COST(c, b) < DBL_MAX) {
1639                           if (TO_FLOYD_COST(a, b) == DBL_MAX ||
1640                                   (TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b) <
1641                                    TO_FLOYD_COST(a, b))) {
1642                                 TO_FLOYD_COST(a, b) =
1643                                         TO_FLOYD_COST(a, c) + TO_FLOYD_COST(c, b);
1644                                 TO_FLOYD_PRED(a, b) = TO_FLOYD_PRED(c, b);
1645                           }
1646                         }
1647                   }
1648                 }
1649         }
1650 }
1651
1652 static void model_floyd_set_route(routing_component_t rc, const char *src,
1653         const char *dst, name_route_extended_t route)
1654 {
1655         routing_component_floyd_t routing = (routing_component_floyd_t) rc;
1656
1657         /* set the size of table routing */
1658         size_t table_size = xbt_dict_length(rc->to_index);
1659         int *src_id, *dst_id;
1660         int i,j;
1661
1662         src_id = xbt_dict_get_or_null(rc->to_index, src);
1663         dst_id = xbt_dict_get_or_null(rc->to_index, dst);
1664
1665         if(!routing->link_table)
1666         {
1667                 /* Create Cost, Predecessor and Link tables */
1668                 routing->cost_table = xbt_new0(double, table_size * table_size);       /* link cost from host to host */
1669                 routing->predecessor_table = xbt_new0(int, table_size * table_size);  /* predecessor host numbers */
1670                 routing->link_table = xbt_new0(route_extended_t, table_size * table_size);    /* actual link between src and dst */
1671
1672                 /* Initialize costs and predecessors */
1673                 for (i = 0; i < table_size; i++)
1674                 for (j = 0; j < table_size; j++) {
1675                   TO_FLOYD_COST(i, j) = DBL_MAX;
1676                   TO_FLOYD_PRED(i, j) = -1;
1677                   TO_FLOYD_LINK(i, j) = NULL;       /* fixed, missing in the previous version */
1678                 }
1679         }
1680
1681         if(TO_FLOYD_LINK(*src_id, *dst_id))
1682         {
1683                 if(!route->dst_gateway && !route->src_gateway)
1684                         DEBUG2("See Route from \"%s\" to \"%s\"", src, dst);
1685                 else
1686                         DEBUG4("See ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
1687                                  route->src_gateway, dst, route->dst_gateway);
1688                 char * link_name;
1689                 unsigned int cpt;
1690                 xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1691                 xbt_dynar_foreach(route->generic_route.link_list,cpt,link_name)
1692                 {
1693                         void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1694                         xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1695                         xbt_dynar_push(link_route_to_test,&link);
1696                 }
1697                 xbt_assert2(!xbt_dynar_compare(
1698                           (void*)TO_FLOYD_LINK(*src_id, *dst_id)->generic_route.link_list,
1699                           (void*)link_route_to_test,
1700                           (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1701                           "The route between \"%s\" and \"%s\" already exists", src,dst);
1702                 xbt_free(link_route_to_test);
1703         }
1704         else
1705         {
1706                 if(!route->dst_gateway && !route->src_gateway)
1707                   DEBUG2("Load Route from \"%s\" to \"%s\"", src, dst);
1708                 else
1709                   DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
1710                                  route->src_gateway, dst, route->dst_gateway);
1711
1712             TO_FLOYD_LINK(*src_id, *dst_id) =
1713                         generic_new_extended_route(rc->hierarchy, route, 1);
1714             TO_FLOYD_PRED(*src_id, *dst_id) = *src_id;
1715             TO_FLOYD_COST(*src_id, *dst_id) =
1716                         ((TO_FLOYD_LINK(*src_id, *dst_id))->generic_route.link_list)->used;   /* count of links, old model assume 1 */
1717         }
1718
1719         if( A_surfxml_route_symmetrical == A_surfxml_route_symmetrical_YES
1720                 || A_surfxml_ASroute_symmetrical == A_surfxml_ASroute_symmetrical_YES )
1721         {
1722                 if(TO_FLOYD_LINK(*dst_id, *src_id))
1723                 {
1724                         if(!route->dst_gateway && !route->src_gateway)
1725                           DEBUG2("See Route from \"%s\" to \"%s\"", dst, src);
1726                         else
1727                           DEBUG4("See ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
1728                                          route->src_gateway, src, route->dst_gateway);
1729                         char * link_name;
1730                         unsigned int i;
1731                         xbt_dynar_t link_route_to_test = xbt_dynar_new(global_routing->size_of_link, NULL);
1732                         for(i=xbt_dynar_length(route->generic_route.link_list) ;i>0 ;i--)
1733                         {
1734                                 link_name = xbt_dynar_get_as(route->generic_route.link_list,i-1,void *);
1735                                 void *link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1736                                 xbt_assert1(link,"Link : '%s' doesn't exists.",link_name);
1737                                 xbt_dynar_push(link_route_to_test,&link);
1738                         }
1739                         xbt_assert2(!xbt_dynar_compare(
1740                                   (void*)TO_FLOYD_LINK(*dst_id, *src_id)->generic_route.link_list,
1741                               (void*)link_route_to_test,
1742                                   (int_f_cpvoid_cpvoid_t) surf_pointer_resource_cmp),
1743                                   "The route between \"%s\" and \"%s\" already exists", src,dst);
1744                         xbt_free(link_route_to_test);
1745                 }
1746                 else
1747                 {
1748                         if(route->dst_gateway && route->src_gateway)
1749                         {
1750                           char *gw_src = xbt_strdup(route->src_gateway);
1751                           char *gw_dst = xbt_strdup(route->dst_gateway);
1752                           route->src_gateway = gw_dst;
1753                           route->dst_gateway = gw_src;
1754                         }
1755
1756                         if(!route->dst_gateway && !route->src_gateway)
1757                           DEBUG2("Load Route from \"%s\" to \"%s\"", dst, src);
1758                         else
1759                           DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", dst,
1760                                          route->src_gateway, src, route->dst_gateway);
1761
1762                     TO_FLOYD_LINK(*dst_id, *src_id) =
1763                                 generic_new_extended_route(rc->hierarchy, route, 0);
1764                     TO_FLOYD_PRED(*dst_id, *src_id) = *dst_id;
1765                     TO_FLOYD_COST(*dst_id, *src_id) =
1766                                 ((TO_FLOYD_LINK(*dst_id, *src_id))->generic_route.link_list)->used;   /* count of links, old model assume 1 */
1767                 }
1768         }
1769 }
1770
1771 /* ************************************************************************** */
1772 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
1773
1774 typedef struct {
1775   s_routing_component_t generic_routing;
1776   xbt_graph_t route_graph;      /* xbt_graph */
1777   xbt_dict_t graph_node_map;    /* map */
1778   xbt_dict_t route_cache;       /* use in cache mode */
1779   int cached;
1780 } s_routing_component_dijkstra_t, *routing_component_dijkstra_t;
1781
1782
1783 typedef struct graph_node_data {
1784   int id;
1785   int graph_id;                 /* used for caching internal graph id's */
1786 } s_graph_node_data_t, *graph_node_data_t;
1787
1788 typedef struct graph_node_map_element {
1789   xbt_node_t node;
1790 } s_graph_node_map_element_t, *graph_node_map_element_t;
1791
1792 typedef struct route_cache_element {
1793   int *pred_arr;
1794   int size;
1795 } s_route_cache_element_t, *route_cache_element_t;
1796
1797 /* Free functions */
1798
1799 static void route_cache_elem_free(void *e)
1800 {
1801   route_cache_element_t elm = (route_cache_element_t) e;
1802   if (elm) {
1803     xbt_free(elm->pred_arr);
1804     xbt_free(elm);
1805   }
1806 }
1807
1808 static void graph_node_map_elem_free(void *e)
1809 {
1810   graph_node_map_element_t elm = (graph_node_map_element_t) e;
1811   if (elm) {
1812     xbt_free(elm);
1813   }
1814 }
1815
1816 static void graph_edge_data_free(void *e)
1817 {
1818   route_extended_t e_route = (route_extended_t) e;
1819   if (e_route) {
1820     xbt_dynar_free(&(e_route->generic_route.link_list));
1821     if (e_route->src_gateway)
1822       xbt_free(e_route->src_gateway);
1823     if (e_route->dst_gateway)
1824       xbt_free(e_route->dst_gateway);
1825     xbt_free(e_route);
1826   }
1827 }
1828
1829 /* Utility functions */
1830
1831 static xbt_node_t route_graph_new_node(routing_component_dijkstra_t rc,
1832                                        int id, int graph_id)
1833 {
1834   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1835   xbt_node_t node = NULL;
1836   graph_node_data_t data = NULL;
1837   graph_node_map_element_t elm = NULL;
1838
1839   data = xbt_new0(struct graph_node_data, 1);
1840   data->id = id;
1841   data->graph_id = graph_id;
1842   node = xbt_graph_new_node(routing->route_graph, data);
1843
1844   elm = xbt_new0(struct graph_node_map_element, 1);
1845   elm->node = node;
1846   xbt_dict_set_ext(routing->graph_node_map, (char *) (&id), sizeof(int),
1847                    (xbt_set_elm_t) elm, &graph_node_map_elem_free);
1848
1849   return node;
1850 }
1851
1852 static graph_node_map_element_t
1853 graph_node_map_search(routing_component_dijkstra_t rc, int id)
1854 {
1855   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1856   graph_node_map_element_t elm = (graph_node_map_element_t)
1857       xbt_dict_get_or_null_ext(routing->graph_node_map,
1858                                (char *) (&id),
1859                                sizeof(int));
1860   return elm;
1861 }
1862
1863 /* Parsing */
1864
1865 static void route_new_dijkstra(routing_component_dijkstra_t rc, int src_id,
1866                                int dst_id, route_extended_t e_route)
1867 {
1868   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1869   DEBUG2("Load Route from \"%d\" to \"%d\"", src_id, dst_id);
1870   xbt_node_t src = NULL;
1871   xbt_node_t dst = NULL;
1872
1873   graph_node_map_element_t src_elm = (graph_node_map_element_t)
1874       xbt_dict_get_or_null_ext(routing->graph_node_map,
1875                                (char *) (&src_id),
1876                                sizeof(int));
1877   graph_node_map_element_t dst_elm = (graph_node_map_element_t)
1878       xbt_dict_get_or_null_ext(routing->graph_node_map,
1879                                (char *) (&dst_id),
1880                                sizeof(int));
1881
1882
1883   if (src_elm)
1884     src = src_elm->node;
1885
1886   if (dst_elm)
1887     dst = dst_elm->node;
1888
1889   /* add nodes if they don't exist in the graph */
1890   if (src_id == dst_id && src == NULL && dst == NULL) {
1891     src = route_graph_new_node(rc, src_id, -1);
1892     dst = src;
1893   } else {
1894     if (src == NULL) {
1895       src = route_graph_new_node(rc, src_id, -1);
1896     }
1897     if (dst == NULL) {
1898       dst = route_graph_new_node(rc, dst_id, -1);
1899     }
1900   }
1901
1902   /* add link as edge to graph */
1903   xbt_graph_new_edge(routing->route_graph, src, dst, e_route);
1904 }
1905
1906 static void add_loopback_dijkstra(routing_component_dijkstra_t rc)
1907 {
1908   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1909
1910   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1911
1912   xbt_node_t node = NULL;
1913   unsigned int cursor2;
1914   xbt_dynar_foreach(nodes, cursor2, node) {
1915     xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
1916     xbt_edge_t edge = NULL;
1917     unsigned int cursor;
1918
1919     int found = 0;
1920     xbt_dynar_foreach(out_edges, cursor, edge) {
1921       xbt_node_t other_node = xbt_graph_edge_get_target(edge);
1922       if (other_node == node) {
1923         found = 1;
1924         break;
1925       }
1926     }
1927
1928     if (!found) {
1929       route_extended_t e_route = xbt_new0(s_route_extended_t, 1);
1930       e_route->src_gateway = NULL;
1931       e_route->dst_gateway = NULL;
1932       e_route->generic_route.link_list =
1933           xbt_dynar_new(global_routing->size_of_link, NULL);
1934       xbt_dynar_push(e_route->generic_route.link_list,
1935                      &global_routing->loopback);
1936       xbt_graph_new_edge(routing->route_graph, node, node, e_route);
1937     }
1938   }
1939 }
1940
1941 /* Business methods */
1942 static xbt_dynar_t dijkstra_get_onelink_routes(routing_component_t rc)
1943 {
1944   xbt_die("\"dijkstra_get_onelink_routes\" function not implemented yet");
1945 }
1946
1947 static route_extended_t dijkstra_get_route(routing_component_t rc,
1948                                            const char *src,
1949                                            const char *dst)
1950 {
1951   xbt_assert1(rc && src
1952               && dst,
1953               "Invalid params for \"get_route\" function at AS \"%s\"",
1954               rc->name);
1955
1956   /* set utils vars */
1957   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1958
1959   generic_src_dst_check(rc, src, dst);
1960   int *src_id = xbt_dict_get_or_null(routing->generic_routing.to_index, src);
1961   int *dst_id = xbt_dict_get_or_null(routing->generic_routing.to_index, dst);
1962   xbt_assert2(src_id
1963               && dst_id,
1964               "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
1965               src, dst);
1966
1967   /* create a result route */
1968   route_extended_t new_e_route = xbt_new0(s_route_extended_t, 1);
1969   new_e_route->generic_route.link_list =
1970       xbt_dynar_new(global_routing->size_of_link, NULL);
1971   new_e_route->src_gateway = NULL;
1972   new_e_route->dst_gateway = NULL;
1973
1974   int *pred_arr = NULL;
1975   int src_node_id = 0;
1976   int dst_node_id = 0;
1977   int *nodeid = NULL;
1978   int v;
1979   route_extended_t e_route;
1980   int size = 0;
1981   unsigned int cpt;
1982   void *link;
1983   xbt_dynar_t links = NULL;
1984   route_cache_element_t elm = NULL;
1985   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1986
1987   /* Use the graph_node id mapping set to quickly find the nodes */
1988   graph_node_map_element_t src_elm =
1989       graph_node_map_search(routing, *src_id);
1990   graph_node_map_element_t dst_elm =
1991       graph_node_map_search(routing, *dst_id);
1992   xbt_assert2(src_elm != NULL
1993               && dst_elm != NULL, "src %d or dst %d does not exist",
1994               *src_id, *dst_id);
1995   src_node_id = ((graph_node_data_t)
1996                  xbt_graph_node_get_data(src_elm->node))->graph_id;
1997   dst_node_id = ((graph_node_data_t)
1998                  xbt_graph_node_get_data(dst_elm->node))->graph_id;
1999
2000   /* if the src and dst are the same *//* fixed, missing in the previous version */
2001   if (src_node_id == dst_node_id) {
2002
2003     xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
2004     xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
2005     xbt_edge_t edge =
2006         xbt_graph_get_edge(routing->route_graph, node_s_v, node_e_v);
2007
2008     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id,
2009                 *dst_id);
2010
2011     e_route = (route_extended_t) xbt_graph_edge_get_data(edge);
2012
2013     links = e_route->generic_route.link_list;
2014     xbt_dynar_foreach(links, cpt, link) {
2015       xbt_dynar_unshift(new_e_route->generic_route.link_list, &link);
2016     }
2017
2018     return new_e_route;
2019   }
2020
2021   if (routing->cached) {
2022     /*check if there is a cached predecessor list avail */
2023     elm = (route_cache_element_t)
2024         xbt_dict_get_or_null_ext(routing->route_cache, (char *) (&src_id),
2025                                  sizeof(int));
2026   }
2027
2028   if (elm) {                    /* cached mode and cache hit */
2029     pred_arr = elm->pred_arr;
2030   } else {                      /* not cached mode or cache miss */
2031     double *cost_arr = NULL;
2032     xbt_heap_t pqueue = NULL;
2033     int i = 0;
2034
2035     int nr_nodes = xbt_dynar_length(nodes);
2036     cost_arr = xbt_new0(double, nr_nodes);      /* link cost from src to other hosts */
2037     pred_arr = xbt_new0(int, nr_nodes); /* predecessors in path from src */
2038     pqueue = xbt_heap_new(nr_nodes, xbt_free);
2039
2040     /* initialize */
2041     cost_arr[src_node_id] = 0.0;
2042
2043     for (i = 0; i < nr_nodes; i++) {
2044       if (i != src_node_id) {
2045         cost_arr[i] = DBL_MAX;
2046       }
2047
2048       pred_arr[i] = 0;
2049
2050       /* initialize priority queue */
2051       nodeid = xbt_new0(int, 1);
2052       *nodeid = i;
2053       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
2054
2055     }
2056
2057     /* apply dijkstra using the indexes from the graph's node array */
2058     while (xbt_heap_size(pqueue) > 0) {
2059       int *v_id = xbt_heap_pop(pqueue);
2060       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
2061       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
2062       xbt_edge_t edge = NULL;
2063       unsigned int cursor;
2064
2065       xbt_dynar_foreach(out_edges, cursor, edge) {
2066         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
2067         graph_node_data_t data = xbt_graph_node_get_data(u_node);
2068         int u_id = data->graph_id;
2069         route_extended_t tmp_e_route =
2070             (route_extended_t) xbt_graph_edge_get_data(edge);
2071         int cost_v_u = (tmp_e_route->generic_route.link_list)->used;    /* count of links, old model assume 1 */
2072
2073         if (cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
2074           pred_arr[u_id] = *v_id;
2075           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
2076           nodeid = xbt_new0(int, 1);
2077           *nodeid = u_id;
2078           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
2079         }
2080       }
2081
2082       /* free item popped from pqueue */
2083       xbt_free(v_id);
2084     }
2085
2086     xbt_free(cost_arr);
2087     xbt_heap_free(pqueue);
2088   }
2089
2090   /* compose route path with links */
2091   char *gw_src = NULL, *gw_dst =
2092       NULL, *prev_gw_src, *prev_gw_dst, *first_gw = NULL;
2093
2094   for (v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
2095     xbt_node_t node_pred_v =
2096         xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
2097     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
2098     xbt_edge_t edge =
2099         xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
2100
2101     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id,
2102                 *dst_id);
2103
2104     prev_gw_src = gw_src;
2105     prev_gw_dst = gw_dst;
2106
2107     e_route = (route_extended_t) xbt_graph_edge_get_data(edge);
2108     gw_src = e_route->src_gateway;
2109     gw_dst = e_route->dst_gateway;
2110
2111     if (v == dst_node_id)
2112       first_gw = gw_dst;
2113
2114     if (rc->hierarchy == SURF_ROUTING_RECURSIVE && v != dst_node_id
2115         && strcmp(gw_dst, prev_gw_src)) {
2116       xbt_dynar_t e_route_as_to_as =
2117           (*(global_routing->get_route)) (gw_dst, prev_gw_src);
2118       xbt_assert2(e_route_as_to_as, "no route between \"%s\" and \"%s\"",
2119                   gw_dst, prev_gw_src);
2120       links = e_route_as_to_as;
2121       int pos = 0;
2122       xbt_dynar_foreach(links, cpt, link) {
2123         xbt_dynar_insert_at(new_e_route->generic_route.link_list, pos,
2124                             &link);
2125         pos++;
2126       }
2127     }
2128
2129     links = e_route->generic_route.link_list;
2130     xbt_dynar_foreach(links, cpt, link) {
2131       xbt_dynar_unshift(new_e_route->generic_route.link_list, &link);
2132     }
2133     size++;
2134   }
2135
2136   if (rc->hierarchy == SURF_ROUTING_RECURSIVE) {
2137     new_e_route->src_gateway = xbt_strdup(gw_src);
2138     new_e_route->dst_gateway = xbt_strdup(first_gw);
2139   }
2140
2141   if (routing->cached && elm == NULL) {
2142     /* add to predecessor list of the current src-host to cache */
2143     elm = xbt_new0(struct route_cache_element, 1);
2144     elm->pred_arr = pred_arr;
2145     elm->size = size;
2146     xbt_dict_set_ext(routing->route_cache, (char *) (&src_id), sizeof(int),
2147                      (xbt_set_elm_t) elm, &route_cache_elem_free);
2148   }
2149
2150   if (!routing->cached)
2151     xbt_free(pred_arr);
2152
2153   return new_e_route;
2154 }
2155
2156 static void dijkstra_finalize(routing_component_t rc)
2157 {
2158   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
2159
2160   if (routing) {
2161     xbt_graph_free_graph(routing->route_graph, &xbt_free,
2162                          &graph_edge_data_free, &xbt_free);
2163     xbt_dict_free(&routing->graph_node_map);
2164     if (routing->cached)
2165       xbt_dict_free(&routing->route_cache);
2166     /* Delete bypass dict */
2167     xbt_dict_free(&routing->generic_routing.bypassRoutes);
2168     /* Delete index dict */
2169     xbt_dict_free(&(routing->generic_routing.to_index));
2170     /* Delete structure */
2171     xbt_free(routing);
2172   }
2173 }
2174
2175 /* Creation routing model functions */
2176
2177 static void *model_dijkstra_both_create(int cached)
2178 {
2179   routing_component_dijkstra_t new_component =
2180       xbt_new0(s_routing_component_dijkstra_t, 1);
2181   new_component->generic_routing.set_processing_unit =
2182       generic_set_processing_unit;
2183   new_component->generic_routing.set_autonomous_system =
2184       generic_set_autonomous_system;
2185   new_component->generic_routing.set_route = model_dijkstra_both_set_route;
2186   new_component->generic_routing.set_ASroute = model_dijkstra_both_set_route; //TODO
2187   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
2188   new_component->generic_routing.get_route = dijkstra_get_route;
2189   new_component->generic_routing.get_latency = generic_get_link_latency;
2190   new_component->generic_routing.get_onelink_routes =
2191       dijkstra_get_onelink_routes;
2192   new_component->generic_routing.get_bypass_route =
2193       generic_get_bypassroute;
2194   new_component->generic_routing.finalize = dijkstra_finalize;
2195   new_component->cached = cached;
2196   new_component->generic_routing.to_index = xbt_dict_new();
2197   new_component->generic_routing.bypassRoutes = xbt_dict_new();
2198   return new_component;
2199 }
2200
2201 static void *model_dijkstra_create(void)
2202 {
2203   return model_dijkstra_both_create(0);
2204 }
2205
2206 static void *model_dijkstracache_create(void)
2207 {
2208   return model_dijkstra_both_create(1);
2209 }
2210
2211 static void model_dijkstra_both_load(void)
2212 {
2213   /* use "surfxml_add_callback" to add a parse function call */
2214 }
2215
2216 static void model_dijkstra_both_unload(void)
2217 {
2218   /* use "surfxml_del_callback" to remove a parse function call */
2219 }
2220
2221 static void model_dijkstra_both_end(void)
2222 {
2223   routing_component_dijkstra_t routing =
2224       (routing_component_dijkstra_t) current_routing;
2225
2226   xbt_node_t node = NULL;
2227   unsigned int cursor2;
2228   xbt_dynar_t nodes = NULL;
2229
2230   /* Create the topology graph */
2231   if(!routing->route_graph)
2232   routing->route_graph = xbt_graph_new_graph(1, NULL);
2233   if(!routing->graph_node_map)
2234   routing->graph_node_map = xbt_dict_new();
2235
2236   if (routing->cached && !routing->route_cache)
2237   routing->route_cache = xbt_dict_new();
2238
2239   /* Add the loopback if needed */
2240   if (current_routing->hierarchy == SURF_ROUTING_BASE)
2241     add_loopback_dijkstra(routing);
2242
2243   /* initialize graph indexes in nodes after graph has been built */
2244   nodes = xbt_graph_get_nodes(routing->route_graph);
2245
2246   xbt_dynar_foreach(nodes, cursor2, node) {
2247     graph_node_data_t data = xbt_graph_node_get_data(node);
2248     data->graph_id = cursor2;
2249   }
2250
2251 }
2252 static void model_dijkstra_both_set_route (routing_component_t rc, const char *src,
2253                      const char *dst, name_route_extended_t route)
2254 {
2255         routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
2256         int *src_id, *dst_id;
2257         src_id = xbt_dict_get_or_null(rc->to_index, src);
2258         dst_id = xbt_dict_get_or_null(rc->to_index, dst);
2259
2260     /* Create the topology graph */
2261         if(!routing->route_graph)
2262         routing->route_graph = xbt_graph_new_graph(1, NULL);
2263         if(!routing->graph_node_map)
2264         routing->graph_node_map = xbt_dict_new();
2265
2266         if (routing->cached && !routing->route_cache)
2267         routing->route_cache = xbt_dict_new();
2268
2269         if( A_surfxml_route_symmetrical == A_surfxml_route_symmetrical_YES
2270                 || A_surfxml_ASroute_symmetrical == A_surfxml_ASroute_symmetrical_YES )
2271                 xbt_die("Route symmetrical not supported on model dijkstra");
2272
2273         if(!route->dst_gateway && !route->src_gateway)
2274           DEBUG2("Load Route from \"%s\" to \"%s\"", src, dst);
2275         else
2276           DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"", src,
2277                          route->src_gateway, dst, route->dst_gateway);
2278
2279         route_extended_t e_route =
2280                 generic_new_extended_route(current_routing->hierarchy, route, 1);
2281         route_new_dijkstra(routing, *src_id, *dst_id, e_route);
2282 }
2283
2284 #ifdef HAVE_PCRE_LIB
2285 /* ************************************************** */
2286 /* ************** RULE-BASED ROUTING **************** */
2287
2288 /* Routing model structure */
2289
2290 typedef struct {
2291   s_routing_component_t generic_routing;
2292   xbt_dict_t dict_processing_units;
2293   xbt_dict_t dict_autonomous_systems;
2294   xbt_dynar_t list_route;
2295   xbt_dynar_t list_ASroute;
2296 } s_routing_component_rulebased_t, *routing_component_rulebased_t;
2297
2298 typedef struct s_rule_route s_rule_route_t, *rule_route_t;
2299 typedef struct s_rule_route_extended s_rule_route_extended_t,
2300     *rule_route_extended_t;
2301
2302 struct s_rule_route {
2303   xbt_dynar_t re_str_link;      // dynar of char*
2304   pcre *re_src;
2305   pcre *re_dst;
2306 };
2307
2308 struct s_rule_route_extended {
2309   s_rule_route_t generic_rule_route;
2310   char *re_src_gateway;
2311   char *re_dst_gateway;
2312 };
2313
2314 static void rule_route_free(void *e)
2315 {
2316   rule_route_t *elem = (rule_route_t *) (e);
2317   if (*elem) {
2318     xbt_dynar_free(&(*elem)->re_str_link);
2319     pcre_free((*elem)->re_src);
2320     pcre_free((*elem)->re_dst);
2321     xbt_free(*elem);
2322   }
2323   *elem = NULL;
2324 }
2325
2326 static void rule_route_extended_free(void *e)
2327 {
2328   rule_route_extended_t *elem = (rule_route_extended_t *) e;
2329   if (*elem) {
2330     xbt_dynar_free(&(*elem)->generic_rule_route.re_str_link);
2331     pcre_free((*elem)->generic_rule_route.re_src);
2332     pcre_free((*elem)->generic_rule_route.re_dst);
2333     xbt_free((*elem)->re_src_gateway);
2334     xbt_free((*elem)->re_dst_gateway);
2335     xbt_free(*elem);
2336   }
2337 }
2338
2339 /* Parse routing model functions */
2340
2341 static void model_rulebased_set_processing_unit(routing_component_t rc,
2342                                                 const char *name)
2343 {
2344   routing_component_rulebased_t routing =
2345       (routing_component_rulebased_t) rc;
2346   xbt_dict_set(routing->dict_processing_units, name, (void *) (-1), NULL);
2347 }
2348
2349 static void model_rulebased_set_autonomous_system(routing_component_t rc,
2350                                                   const char *name)
2351 {
2352   routing_component_rulebased_t routing =
2353       (routing_component_rulebased_t) rc;
2354   xbt_dict_set(routing->dict_autonomous_systems, name, (void *) (-1),
2355                NULL);
2356 }
2357
2358 static void model_rulebased_set_route(routing_component_t rc,
2359                                       const char *src, const char *dst,
2360                                       name_route_extended_t route)
2361 {
2362   routing_component_rulebased_t routing =
2363       (routing_component_rulebased_t) rc;
2364   rule_route_t ruleroute = xbt_new0(s_rule_route_t, 1);
2365   const char *error;
2366   int erroffset;
2367   ruleroute->re_src = pcre_compile(src, 0, &error, &erroffset, NULL);
2368   xbt_assert3(ruleroute->re_src,
2369               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2370               erroffset, src, error);
2371   ruleroute->re_dst = pcre_compile(dst, 0, &error, &erroffset, NULL);
2372   xbt_assert3(ruleroute->re_src,
2373               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2374               erroffset, dst, error);
2375   ruleroute->re_str_link = route->generic_route.link_list;
2376   xbt_dynar_push(routing->list_route, &ruleroute);
2377   xbt_free(route);
2378 }
2379
2380 static void model_rulebased_set_ASroute(routing_component_t rc,
2381                                         const char *src, const char *dst,
2382                                         name_route_extended_t route)
2383 {
2384   routing_component_rulebased_t routing =
2385       (routing_component_rulebased_t) rc;
2386   rule_route_extended_t ruleroute_e = xbt_new0(s_rule_route_extended_t, 1);
2387   const char *error;
2388   int erroffset;
2389   ruleroute_e->generic_rule_route.re_src =
2390       pcre_compile(src, 0, &error, &erroffset, NULL);
2391   xbt_assert3(ruleroute_e->generic_rule_route.re_src,
2392               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2393               erroffset, src, error);
2394   ruleroute_e->generic_rule_route.re_dst =
2395       pcre_compile(dst, 0, &error, &erroffset, NULL);
2396   xbt_assert3(ruleroute_e->generic_rule_route.re_src,
2397               "PCRE compilation failed at offset %d (\"%s\"): %s\n",
2398               erroffset, dst, error);
2399   ruleroute_e->generic_rule_route.re_str_link =
2400       route->generic_route.link_list;
2401   ruleroute_e->re_src_gateway = route->src_gateway;
2402   ruleroute_e->re_dst_gateway = route->dst_gateway;
2403   xbt_dynar_push(routing->list_ASroute, &ruleroute_e);
2404 //  xbt_free(route->src_gateway);
2405 //  xbt_free(route->dst_gateway);
2406   xbt_free(route);
2407 }
2408
2409 static void model_rulebased_set_bypassroute(routing_component_t rc,
2410                                             const char *src,
2411                                             const char *dst,
2412                                             route_extended_t e_route)
2413 {
2414   xbt_die("bypass routing not supported for Route-Based model");
2415 }
2416
2417 #define BUFFER_SIZE 4096        /* result buffer size */
2418 #define OVECCOUNT 30            /* should be a multiple of 3 */
2419
2420 static char *remplace(char *value, const char **src_list, int src_size,
2421                       const char **dst_list, int dst_size)
2422 {
2423
2424   char result_result[BUFFER_SIZE];
2425   int i_result_buffer;
2426   int value_length = (int) strlen(value);
2427   int number = 0;
2428
2429   int i = 0;
2430   i_result_buffer = 0;
2431   do {
2432     if (value[i] == '$') {
2433       i++;                      // skip $
2434
2435       // find the number      
2436       int number_length = 0;
2437       while ('0' <= value[i + number_length]
2438              && value[i + number_length] <= '9') {
2439         number_length++;
2440       }
2441       xbt_assert2(number_length != 0,
2442                   "bad string parameter, no number indication, at offset: %d (\"%s\")",
2443                   i, value);
2444
2445       // solve number
2446       number = atoi(value + i);
2447       i = i + number_length;
2448       xbt_assert2(i + 2 < value_length,
2449                   "bad string parameter, too few chars, at offset: %d (\"%s\")",
2450                   i, value);
2451
2452       // solve the indication
2453       const char **param_list;
2454       int param_size;
2455       if (value[i] == 's' && value[i + 1] == 'r' && value[i + 2] == 'c') {
2456         param_list = src_list;
2457         param_size = src_size;
2458       } else if (value[i] == 'd' && value[i + 1] == 's'
2459                  && value[i + 2] == 't') {
2460         param_list = dst_list;
2461         param_size = dst_size;
2462       } else {
2463         xbt_assert2(0,
2464                     "bad string parameter, support only \"src\" and \"dst\", at offset: %d (\"%s\")",
2465                     i, value);
2466       }
2467       i = i + 3;
2468
2469       xbt_assert4(param_size >= number,
2470                   "bad string parameter, not enough length param_size, at offset: %d (\"%s\") %d %d",
2471                   i, value, param_size, number);
2472
2473       const char *param = param_list[number];
2474       int size = strlen(param);
2475       int cp;
2476       for (cp = 0; cp < size; cp++) {
2477         result_result[i_result_buffer] = param[cp];
2478         i_result_buffer++;
2479         if (i_result_buffer >= BUFFER_SIZE)
2480           break;
2481       }
2482     } else {
2483       result_result[i_result_buffer] = value[i];
2484       i_result_buffer++;
2485       i++;                      // next char
2486     }
2487
2488   } while (i < value_length && i_result_buffer < BUFFER_SIZE);
2489
2490   xbt_assert2(i_result_buffer < BUFFER_SIZE,
2491               "solving string \"%s\", small buffer size (%d)", value,
2492               BUFFER_SIZE);
2493   result_result[i_result_buffer] = 0;
2494   return xbt_strdup(result_result);
2495 }
2496
2497 static route_extended_t rulebased_get_route(routing_component_t rc,
2498                                             const char *src,
2499                                             const char *dst);
2500 static xbt_dynar_t rulebased_get_onelink_routes(routing_component_t rc)
2501 {
2502   xbt_dynar_t ret = xbt_dynar_new (sizeof(onelink_t), xbt_free);
2503   routing_component_rulebased_t routing = (routing_component_rulebased_t)rc;
2504
2505   xbt_dict_cursor_t c1 = NULL;
2506   char *k1, *d1;
2507
2508   //find router
2509   char *router = NULL;
2510   xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
2511     if (strstr (k1, "router")){
2512       router = k1;
2513     }
2514   }
2515   if (!router){
2516     xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
2517   }
2518
2519   xbt_dict_foreach(routing->dict_processing_units, c1, k1, d1) {
2520     route_extended_t route = rulebased_get_route (rc, router, k1);
2521
2522     int number_of_links = xbt_dynar_length(route->generic_route.link_list);
2523     if (number_of_links != 3) {
2524       xbt_die ("rulebased_get_onelink_routes works only if the AS is a cluster, sorry.");
2525     }
2526
2527     void *link_ptr;
2528     xbt_dynar_get_cpy (route->generic_route.link_list, 2, &link_ptr);
2529     onelink_t onelink = xbt_new0 (s_onelink_t, 1);
2530     onelink->src = xbt_strdup (k1);
2531     onelink->dst = xbt_strdup (router);
2532     onelink->link_ptr = link_ptr;
2533     xbt_dynar_push (ret, &onelink);
2534   }
2535   return ret;
2536 }
2537
2538 /* Business methods */
2539 static route_extended_t rulebased_get_route(routing_component_t rc,
2540                                             const char *src,
2541                                             const char *dst)
2542 {
2543   xbt_assert1(rc && src
2544               && dst,
2545               "Invalid params for \"get_route\" function at AS \"%s\"",
2546               rc->name);
2547
2548   /* set utils vars */
2549   routing_component_rulebased_t routing =
2550       (routing_component_rulebased_t) rc;
2551
2552   int are_processing_units;
2553   xbt_dynar_t rule_list;
2554   if (xbt_dict_get_or_null(routing->dict_processing_units, src)
2555       && xbt_dict_get_or_null(routing->dict_processing_units, dst)) {
2556     are_processing_units = 1;
2557     rule_list = routing->list_route;
2558   } else if (xbt_dict_get_or_null(routing->dict_autonomous_systems, src)
2559              && xbt_dict_get_or_null(routing->dict_autonomous_systems,
2560                                      dst)) {
2561     are_processing_units = 0;
2562     rule_list = routing->list_ASroute;
2563   } else
2564     xbt_assert2(NULL,
2565                 "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",
2566                 src, dst);
2567
2568   int rc_src = -1;
2569   int rc_dst = -1;
2570   int src_length = (int) strlen(src);
2571   int dst_length = (int) strlen(dst);
2572
2573   xbt_dynar_t links_list =
2574       xbt_dynar_new(global_routing->size_of_link, NULL);
2575
2576   rule_route_t ruleroute;
2577   unsigned int cpt;
2578   int ovector_src[OVECCOUNT];
2579   int ovector_dst[OVECCOUNT];
2580   const char **list_src = NULL;
2581   const char **list_dst = NULL;
2582   xbt_dynar_foreach(rule_list, cpt, ruleroute) {
2583     rc_src =
2584         pcre_exec(ruleroute->re_src, NULL, src, src_length, 0, 0,
2585                   ovector_src, OVECCOUNT);
2586     if (rc_src >= 0) {
2587       rc_dst =
2588           pcre_exec(ruleroute->re_dst, NULL, dst, dst_length, 0, 0,
2589                     ovector_dst, OVECCOUNT);
2590       if (rc_dst >= 0) {
2591         xbt_assert1(!pcre_get_substring_list
2592                     (src, ovector_src, rc_src, &list_src),
2593                     "error solving substring list for src \"%s\"", src);
2594         xbt_assert1(!pcre_get_substring_list
2595                     (dst, ovector_dst, rc_dst, &list_dst),
2596                     "error solving substring list for src \"%s\"", dst);
2597         char *link_name;
2598         xbt_dynar_foreach(ruleroute->re_str_link, cpt, link_name) {
2599           char *new_link_name =
2600               remplace(link_name, list_src, rc_src, list_dst, rc_dst);
2601           void *link =
2602               xbt_dict_get_or_null(surf_network_model->resource_set,
2603                                    new_link_name);
2604           if (link)
2605             xbt_dynar_push(links_list, &link);
2606           else
2607             THROW1(mismatch_error, 0, "Link %s not found", new_link_name);
2608           xbt_free(new_link_name);
2609         }
2610       }
2611     }
2612     if (rc_src >= 0 && rc_dst >= 0)
2613       break;
2614   }
2615
2616   route_extended_t new_e_route = NULL;
2617   if (rc_src >= 0 && rc_dst >= 0) {
2618     new_e_route = xbt_new0(s_route_extended_t, 1);
2619     new_e_route->generic_route.link_list = links_list;
2620   } else if (!strcmp(src, dst) && are_processing_units) {
2621     new_e_route = xbt_new0(s_route_extended_t, 1);
2622     xbt_dynar_push(links_list, &(global_routing->loopback));
2623     new_e_route->generic_route.link_list = links_list;
2624   } else {
2625     xbt_dynar_free(&link_list);
2626   }
2627
2628   if (!are_processing_units && new_e_route) {
2629     rule_route_extended_t ruleroute_extended =
2630         (rule_route_extended_t) ruleroute;
2631     new_e_route->src_gateway =
2632         remplace(ruleroute_extended->re_src_gateway, list_src, rc_src,
2633                  list_dst, rc_dst);
2634     new_e_route->dst_gateway =
2635         remplace(ruleroute_extended->re_dst_gateway, list_src, rc_src,
2636                  list_dst, rc_dst);
2637   }
2638
2639   if (list_src)
2640     pcre_free_substring_list(list_src);
2641   if (list_dst)
2642     pcre_free_substring_list(list_dst);
2643
2644   return new_e_route;
2645 }
2646
2647 static route_extended_t rulebased_get_bypass_route(routing_component_t rc,
2648                                                    const char *src,
2649                                                    const char *dst)
2650 {
2651   return NULL;
2652 }
2653
2654 static void rulebased_finalize(routing_component_t rc)
2655 {
2656   routing_component_rulebased_t routing =
2657       (routing_component_rulebased_t) rc;
2658   if (routing) {
2659     xbt_dict_free(&routing->dict_processing_units);
2660     xbt_dict_free(&routing->dict_autonomous_systems);
2661     xbt_dynar_free(&routing->list_route);
2662     xbt_dynar_free(&routing->list_ASroute);
2663     /* Delete structure */
2664     xbt_free(routing);
2665   }
2666 }
2667
2668 /* Creation routing model functions */
2669 static void *model_rulebased_create(void)
2670 {
2671   routing_component_rulebased_t new_component =
2672       xbt_new0(s_routing_component_rulebased_t, 1);
2673   new_component->generic_routing.set_processing_unit =
2674       model_rulebased_set_processing_unit;
2675   new_component->generic_routing.set_autonomous_system =
2676       model_rulebased_set_autonomous_system;
2677   new_component->generic_routing.set_route = model_rulebased_set_route;
2678   new_component->generic_routing.set_ASroute = model_rulebased_set_ASroute;
2679   new_component->generic_routing.set_bypassroute = model_rulebased_set_bypassroute;
2680   new_component->generic_routing.get_onelink_routes = rulebased_get_onelink_routes;
2681   new_component->generic_routing.get_route = rulebased_get_route;
2682   new_component->generic_routing.get_latency = generic_get_link_latency;
2683   new_component->generic_routing.get_bypass_route = rulebased_get_bypass_route;
2684   new_component->generic_routing.finalize = rulebased_finalize;
2685   /* initialization of internal structures */
2686   new_component->dict_processing_units = xbt_dict_new();
2687   new_component->dict_autonomous_systems = xbt_dict_new();
2688   new_component->list_route = xbt_dynar_new(sizeof(rule_route_t), &rule_route_free);
2689   new_component->list_ASroute =
2690       xbt_dynar_new(sizeof(rule_route_extended_t),
2691                     &rule_route_extended_free);
2692   return new_component;
2693 }
2694
2695 static void model_rulebased_load(void)
2696 {
2697   /* use "surfxml_add_callback" to add a parse function call */
2698 }
2699
2700 static void model_rulebased_unload(void)
2701 {
2702   /* use "surfxml_del_callback" to remove a parse function call */
2703 }
2704
2705 static void model_rulebased_end(void)
2706 {
2707 }
2708
2709 #endif                          /* HAVE_PCRE_LIB */
2710
2711 /* ************************************************************************** */
2712 /* ******************************* NO ROUTING ******************************* */
2713
2714 /* Routing model structure */
2715 typedef struct {
2716   s_routing_component_t generic_routing;
2717 } s_routing_component_none_t, *routing_component_none_t;
2718
2719 /* Business methods */
2720 static xbt_dynar_t none_get_onelink_routes(routing_component_t rc)
2721 {
2722   return NULL;
2723 }
2724
2725 static route_extended_t none_get_route(routing_component_t rc,
2726                                        const char *src, const char *dst)
2727 {
2728   return NULL;
2729 }
2730
2731 static route_extended_t none_get_bypass_route(routing_component_t rc,
2732                                               const char *src,
2733                                               const char *dst)
2734 {
2735   return NULL;
2736 }
2737
2738 static void none_finalize(routing_component_t rc)
2739 {
2740   xbt_free(rc);
2741 }
2742
2743 static void none_set_processing_unit(routing_component_t rc,
2744                                      const char *name)
2745 {
2746 }
2747
2748 static void none_set_autonomous_system(routing_component_t rc,
2749                                        const char *name)
2750 {
2751 }
2752
2753 /* Creation routing model functions */
2754 static void *model_none_create(void)
2755 {
2756   routing_component_none_t new_component =
2757       xbt_new0(s_routing_component_none_t, 1);
2758   new_component->generic_routing.set_processing_unit =
2759       none_set_processing_unit;
2760   new_component->generic_routing.set_autonomous_system =
2761       none_set_autonomous_system;
2762   new_component->generic_routing.set_route = NULL;
2763   new_component->generic_routing.set_ASroute = NULL;
2764   new_component->generic_routing.set_bypassroute = NULL;
2765   new_component->generic_routing.get_route = none_get_route;
2766   new_component->generic_routing.get_onelink_routes =
2767       none_get_onelink_routes;
2768   new_component->generic_routing.get_bypass_route = none_get_bypass_route;
2769   new_component->generic_routing.finalize = none_finalize;
2770   return new_component;
2771 }
2772
2773 static void model_none_load(void)
2774 {
2775 }
2776
2777 static void model_none_unload(void)
2778 {
2779 }
2780
2781 static void model_none_end(void)
2782 {
2783 }
2784
2785 /* ************************************************** */
2786 /* ********** PATERN FOR NEW ROUTING **************** */
2787
2788 /* The minimal configuration of a new routing model need the next functions,
2789  * also you need to set at the start of the file, the new model in the model
2790  * list. Remember keep the null ending of the list.
2791  */
2792 /*** Routing model structure ***/
2793 // typedef struct {
2794 //   s_routing_component_t generic_routing;
2795 //   /* things that your routing model need */
2796 // } s_routing_component_NEW_t,*routing_component_NEW_t;
2797
2798 /*** Parse routing model functions ***/
2799 // static void model_NEW_set_processing_unit(routing_component_t rc, const char* name) {}
2800 // static void model_NEW_set_autonomous_system(routing_component_t rc, const char* name) {}
2801 // static void model_NEW_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {}
2802 // static void model_NEW_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t route) {}
2803 // static void model_NEW_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {}
2804
2805 /*** Business methods ***/
2806 // static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
2807 // static route_extended_t NEW_get_bypass_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
2808 // static void NEW_finalize(routing_component_t rc) { xbt_free(rc);}
2809
2810 /*** Creation routing model functions ***/
2811 // static void* model_NEW_create(void) {
2812 //   routing_component_NEW_t new_component =  xbt_new0(s_routing_component_NEW_t,1);
2813 //   new_component->generic_routing.set_processing_unit = model_NEW_set_processing_unit;
2814 //   new_component->generic_routing.set_autonomous_system = model_NEW_set_autonomous_system;
2815 //   new_component->generic_routing.set_route = model_NEW_set_route;
2816 //   new_component->generic_routing.set_ASroute = model_NEW_set_ASroute;
2817 //   new_component->generic_routing.set_bypassroute = model_NEW_set_bypassroute;
2818 //   new_component->generic_routing.get_route = NEW_get_route;
2819 //   new_component->generic_routing.get_bypass_route = NEW_get_bypass_route;
2820 //   new_component->generic_routing.finalize = NEW_finalize;
2821 //   /* initialization of internal structures */
2822 //   return new_component;
2823 // } /* mandatory */
2824 // static void  model_NEW_load(void) {}   /* mandatory */
2825 // static void  model_NEW_unload(void) {} /* mandatory */
2826 // static void  model_NEW_end(void) {}    /* mandatory */
2827
2828 /* ************************************************************************** */
2829 /* ************************* GENERIC PARSE FUNCTIONS ************************ */
2830
2831 static void generic_set_processing_unit(routing_component_t rc,
2832                                         const char *name)
2833 {
2834   DEBUG1("Load process unit \"%s\"", name);
2835   int *id = xbt_new0(int, 1);
2836   xbt_dict_t _to_index;
2837   _to_index = current_routing->to_index;
2838   *id = xbt_dict_length(_to_index);
2839   xbt_dict_set(_to_index, name, id, xbt_free);
2840 }
2841
2842 static void generic_set_autonomous_system(routing_component_t rc,
2843                                           const char *name)
2844 {
2845   DEBUG1("Load Autonomous system \"%s\"", name);
2846   int *id = xbt_new0(int, 1);
2847   xbt_dict_t _to_index;
2848   _to_index = current_routing->to_index;
2849   *id = xbt_dict_length(_to_index);
2850   xbt_dict_set(_to_index, name, id, xbt_free);
2851 }
2852
2853 static int surf_pointer_resource_cmp(const void *a, const void *b)
2854 {
2855   return a != b;
2856 }
2857
2858 static int surf_link_resource_cmp(const void *a, const void *b)
2859 {
2860   return !!memcmp(a,b,global_routing->size_of_link);
2861 }
2862
2863 static void generic_set_bypassroute(routing_component_t rc,
2864                                     const char *src, const char *dst,
2865                                     route_extended_t e_route)
2866 {
2867   DEBUG2("Load bypassRoute from \"%s\" to \"%s\"", src, dst);
2868   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
2869   char *route_name;
2870
2871   route_name = bprintf("%s#%s", src, dst);
2872   xbt_assert2(xbt_dynar_length(e_route->generic_route.link_list) > 0,
2873               "Invalid count of links, must be greater than zero (%s,%s)",
2874               src, dst);
2875   xbt_assert4(!xbt_dict_get_or_null(dict_bypassRoutes, route_name),
2876               "The bypass route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exists",
2877               src, e_route->src_gateway, dst, e_route->dst_gateway);
2878
2879   route_extended_t new_e_route =
2880       generic_new_extended_route(SURF_ROUTING_RECURSIVE, e_route, 0);
2881   xbt_dynar_free(&(e_route->generic_route.link_list));
2882   xbt_free(e_route);
2883
2884   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route,
2885                (void (*)(void *)) generic_free_extended_route);
2886   xbt_free(route_name);
2887 }
2888
2889 /* ************************************************************************** */
2890 /* *********************** GENERIC BUSINESS METHODS ************************* */
2891
2892 static double generic_get_link_latency(routing_component_t rc,
2893                                        const char *src, const char *dst)
2894 {
2895         route_extended_t route = rc->get_route(rc,src,dst);
2896         void * link;
2897         unsigned int i;
2898         double latency = 0.0;
2899
2900         xbt_dynar_foreach(route->generic_route.link_list,i,link) {
2901                 latency += get_link_latency(link);
2902         }
2903         generic_free_extended_route(route);
2904   return latency;
2905 }
2906
2907 static xbt_dynar_t generic_get_onelink_routes(routing_component_t rc)
2908 {
2909   xbt_die("\"generic_get_onelink_routes\" not implemented yet");
2910 }
2911
2912 static route_extended_t generic_get_bypassroute(routing_component_t rc,
2913                                                 const char *src,
2914                                                 const char *dst)
2915 {
2916   xbt_dict_t dict_bypassRoutes = rc->bypassRoutes;
2917   routing_component_t src_as, dst_as;
2918   int index_src, index_dst;
2919   xbt_dynar_t path_src = NULL;
2920   xbt_dynar_t path_dst = NULL;
2921   routing_component_t current = NULL;
2922   routing_component_t *current_src = NULL;
2923   routing_component_t *current_dst = NULL;
2924
2925   /* (1) find the as where the src and dst are located */
2926   src_as = ((network_element_info_t)
2927             xbt_dict_get_or_null(global_routing->where_network_elements,
2928                                  src))->rc_component;
2929   dst_as = ((network_element_info_t)
2930             xbt_dict_get_or_null(global_routing->where_network_elements,
2931                                  dst))->rc_component;
2932   xbt_assert2(src_as
2933               && dst_as,
2934               "Ask for route \"from\"(%s) or \"to\"(%s) no found", src,
2935               dst);
2936
2937   /* (2) find the path to the root routing component */
2938   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
2939   current = src_as;
2940   while (current != NULL) {
2941     xbt_dynar_push(path_src, &current);
2942     current = current->routing_father;
2943   }
2944   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
2945   current = dst_as;
2946   while (current != NULL) {
2947     xbt_dynar_push(path_dst, &current);
2948     current = current->routing_father;
2949   }
2950
2951   /* (3) find the common father */
2952   index_src = path_src->used - 1;
2953   index_dst = path_dst->used - 1;
2954   current_src = xbt_dynar_get_ptr(path_src, index_src);
2955   current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
2956   while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
2957     routing_component_t *tmp_src, *tmp_dst;
2958     tmp_src = xbt_dynar_pop_ptr(path_src);
2959     tmp_dst = xbt_dynar_pop_ptr(path_dst);
2960     index_src--;
2961     index_dst--;
2962     current_src = xbt_dynar_get_ptr(path_src, index_src);
2963     current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
2964   }
2965
2966   int max_index_src = path_src->used - 1;
2967   int max_index_dst = path_dst->used - 1;
2968
2969   int max_index = max(max_index_src, max_index_dst);
2970   int i, max;
2971
2972   route_extended_t e_route_bypass = NULL;
2973
2974   for (max = 0; max <= max_index; max++) {
2975     for (i = 0; i < max; i++) {
2976       if (i <= max_index_src && max <= max_index_dst) {
2977         char *route_name = bprintf("%s#%s",
2978                                    (*(routing_component_t *)
2979                                     (xbt_dynar_get_ptr
2980                                      (path_src, i)))->name,
2981                                    (*(routing_component_t *)
2982                                     (xbt_dynar_get_ptr
2983                                      (path_dst, max)))->name);
2984         e_route_bypass =
2985             xbt_dict_get_or_null(dict_bypassRoutes, route_name);
2986         xbt_free(route_name);
2987       }
2988       if (e_route_bypass)
2989         break;
2990       if (max <= max_index_src && i <= max_index_dst) {
2991         char *route_name = bprintf("%s#%s",
2992                                    (*(routing_component_t *)
2993                                     (xbt_dynar_get_ptr
2994                                      (path_src, max)))->name,
2995                                    (*(routing_component_t *)
2996                                     (xbt_dynar_get_ptr
2997                                      (path_dst, i)))->name);
2998         e_route_bypass =
2999             xbt_dict_get_or_null(dict_bypassRoutes, route_name);
3000         xbt_free(route_name);
3001       }
3002       if (e_route_bypass)
3003         break;
3004     }
3005
3006     if (e_route_bypass)
3007       break;
3008
3009     if (max <= max_index_src && max <= max_index_dst) {
3010       char *route_name = bprintf("%s#%s",
3011                                  (*(routing_component_t *)
3012                                   (xbt_dynar_get_ptr
3013                                    (path_src, max)))->name,
3014                                  (*(routing_component_t *)
3015                                   (xbt_dynar_get_ptr
3016                                    (path_dst, max)))->name);
3017       e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes, route_name);
3018       xbt_free(route_name);
3019     }
3020     if (e_route_bypass)
3021       break;
3022   }
3023
3024   xbt_dynar_free(&path_src);
3025   xbt_dynar_free(&path_dst);
3026
3027   route_extended_t new_e_route = NULL;
3028
3029   if (e_route_bypass) {
3030     void *link;
3031     unsigned int cpt = 0;
3032     new_e_route = xbt_new0(s_route_extended_t, 1);
3033     new_e_route->src_gateway = xbt_strdup(e_route_bypass->src_gateway);
3034     new_e_route->dst_gateway = xbt_strdup(e_route_bypass->dst_gateway);
3035     new_e_route->generic_route.link_list =
3036         xbt_dynar_new(global_routing->size_of_link, NULL);
3037     xbt_dynar_foreach(e_route_bypass->generic_route.link_list, cpt, link) {
3038       xbt_dynar_push(new_e_route->generic_route.link_list, &link);
3039     }
3040   }
3041
3042   return new_e_route;
3043 }
3044
3045 /* ************************************************************************** */
3046 /* ************************* GENERIC AUX FUNCTIONS ************************** */
3047
3048 static route_t
3049 generic_new_route(e_surf_routing_hierarchy_t hierarchy,
3050                            void *data, int order)
3051 {
3052
3053   char *link_name;
3054   route_t new_route;
3055   unsigned int cpt;
3056   xbt_dynar_t links = NULL, links_id = NULL;
3057
3058   new_route = xbt_new0(s_route_t, 1);
3059   new_route->link_list =
3060       xbt_dynar_new(global_routing->size_of_link, NULL);
3061
3062   xbt_assert0(hierarchy == SURF_ROUTING_BASE,
3063               "the hierarchy type is not SURF_ROUTING_BASE");
3064
3065   links = ((route_t) data)->link_list;
3066
3067
3068   links_id = new_route->link_list;
3069
3070   xbt_dynar_foreach(links, cpt, link_name) {
3071
3072     void *link =
3073         xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
3074     if (link) {
3075       if (order)
3076         xbt_dynar_push(links_id, &link);
3077       else
3078         xbt_dynar_unshift(links_id, &link);
3079     } else
3080       THROW1(mismatch_error, 0, "Link %s not found", link_name);
3081   }
3082
3083   return new_route;
3084 }
3085
3086 static route_extended_t
3087 generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy,
3088                            void *data, int order)
3089 {
3090
3091   char *link_name;
3092   route_extended_t e_route, new_e_route;
3093   route_t route;
3094   unsigned int cpt;
3095   xbt_dynar_t links = NULL, links_id = NULL;
3096
3097   new_e_route = xbt_new0(s_route_extended_t, 1);
3098   new_e_route->generic_route.link_list =
3099       xbt_dynar_new(global_routing->size_of_link, NULL);
3100   new_e_route->src_gateway = NULL;
3101   new_e_route->dst_gateway = NULL;
3102
3103   xbt_assert0(hierarchy == SURF_ROUTING_BASE
3104               || hierarchy == SURF_ROUTING_RECURSIVE,
3105               "the hierarchy type is not defined");
3106
3107   if (hierarchy == SURF_ROUTING_BASE) {
3108
3109     route = (route_t) data;
3110     links = route->link_list;
3111
3112   } else if (hierarchy == SURF_ROUTING_RECURSIVE) {
3113
3114     e_route = (route_extended_t) data;
3115     xbt_assert0(e_route->src_gateway
3116                 && e_route->dst_gateway, "bad gateway, is null");
3117     links = e_route->generic_route.link_list;
3118
3119     /* remeber not erase the gateway names */
3120     new_e_route->src_gateway = e_route->src_gateway;
3121     new_e_route->dst_gateway = e_route->dst_gateway;
3122   }
3123
3124   links_id = new_e_route->generic_route.link_list;
3125
3126   xbt_dynar_foreach(links, cpt, link_name) {
3127
3128     void *link =
3129         xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
3130     if (link) {
3131       if (order)
3132         xbt_dynar_push(links_id, &link);
3133       else
3134         xbt_dynar_unshift(links_id, &link);
3135     } else
3136       THROW1(mismatch_error, 0, "Link %s not found", link_name);
3137   }
3138
3139   return new_e_route;
3140 }
3141
3142 static void generic_free_route(route_t route)
3143 {
3144   if (route) {
3145     xbt_dynar_free(&(route->link_list));
3146     xbt_free(route);
3147   }
3148 }
3149
3150 static void generic_free_extended_route(route_extended_t e_route)
3151 {
3152   if (e_route) {
3153     xbt_dynar_free(&(e_route->generic_route.link_list));
3154     if (e_route->src_gateway)
3155       xbt_free(e_route->src_gateway);
3156     if (e_route->dst_gateway)
3157       xbt_free(e_route->dst_gateway);
3158     xbt_free(e_route);
3159   }
3160 }
3161
3162 static routing_component_t generic_as_exist(routing_component_t find_from,
3163                                             routing_component_t to_find)
3164 {
3165   //return to_find; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
3166   xbt_dict_cursor_t cursor = NULL;
3167   char *key;
3168   int found = 0;
3169   routing_component_t elem;
3170   xbt_dict_foreach(find_from->routing_sons, cursor, key, elem) {
3171     if (to_find == elem || generic_as_exist(elem, to_find)) {
3172       found = 1;
3173       break;
3174     }
3175   }
3176   if (found)
3177     return to_find;
3178   return NULL;
3179 }
3180
3181 static routing_component_t
3182 generic_autonomous_system_exist(routing_component_t rc, char *element)
3183 {
3184   //return rc; // FIXME: BYPASSERROR OF FOREACH WITH BREAK
3185   routing_component_t element_as, result, elem;
3186   xbt_dict_cursor_t cursor = NULL;
3187   char *key;
3188   element_as = ((network_element_info_t)
3189                 xbt_dict_get_or_null
3190                 (global_routing->where_network_elements,
3191                  element))->rc_component;
3192   result = ((routing_component_t) - 1);
3193   if (element_as != rc)
3194     result = generic_as_exist(rc, element_as);
3195
3196   int found = 0;
3197   if (result) {
3198     xbt_dict_foreach(element_as->routing_sons, cursor, key, elem) {
3199       found = !strcmp(elem->name, element);
3200       if (found)
3201         break;
3202     }
3203     if (found)
3204       return element_as;
3205   }
3206   return NULL;
3207 }
3208
3209 static routing_component_t
3210 generic_processing_units_exist(routing_component_t rc, char *element)
3211 {
3212   routing_component_t element_as;
3213   element_as = ((network_element_info_t)
3214                 xbt_dict_get_or_null
3215                 (global_routing->where_network_elements,
3216                  element))->rc_component;
3217   if (element_as == rc)
3218     return element_as;
3219   return generic_as_exist(rc, element_as);
3220 }
3221
3222 static void generic_src_dst_check(routing_component_t rc, const char *src,
3223                                   const char *dst)
3224 {
3225
3226   routing_component_t src_as = ((network_element_info_t)
3227                                 xbt_dict_get_or_null
3228                                 (global_routing->where_network_elements,
3229                                  src))->rc_component;
3230   routing_component_t dst_as = ((network_element_info_t)
3231                                 xbt_dict_get_or_null
3232                                 (global_routing->where_network_elements,
3233                                  dst))->rc_component;
3234
3235   xbt_assert3(src_as != NULL && dst_as != NULL,
3236               "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",
3237               src, dst, rc->name);
3238   xbt_assert4(src_as == dst_as,
3239               "The src(%s in %s) and dst(%s in %s) are in differents AS",
3240               src, src_as->name, dst, dst_as->name);
3241   xbt_assert2(rc == dst_as,
3242               "The routing component of src and dst is not the same as the network elements belong (%s==%s)",
3243               rc->name, dst_as->name);
3244 }
3245
3246 static void routing_parse_Sconfig(void)
3247 {
3248   DEBUG1("START configuration name = %s",A_surfxml_config_id);
3249 }
3250
3251 static void routing_parse_Econfig(void)
3252 {
3253   xbt_dict_cursor_t cursor = NULL;
3254   char *key;
3255   char *elem;
3256   char *cfg;
3257   xbt_dict_foreach(current_property_set, cursor, key, elem) {
3258           cfg = bprintf("%s:%s",key,elem);
3259           xbt_cfg_set_parse(_surf_cfg_set, cfg);
3260         }
3261   DEBUG1("End configuration name = %s",A_surfxml_config_id);
3262 }
3263
3264 static void routing_parse_Scluster(void)
3265 {
3266   static int AX_ptr = 0;
3267
3268   char *cluster_id = A_surfxml_cluster_id;
3269   char *cluster_prefix = A_surfxml_cluster_prefix;
3270   char *cluster_suffix = A_surfxml_cluster_suffix;
3271   char *cluster_radical = A_surfxml_cluster_radical;
3272   char *cluster_power = A_surfxml_cluster_power;
3273   char *cluster_core = A_surfxml_cluster_core;
3274   char *cluster_bw = A_surfxml_cluster_bw;
3275   char *cluster_lat = A_surfxml_cluster_lat;
3276   char *cluster_bb_bw = A_surfxml_cluster_bb_bw;
3277   char *cluster_bb_lat = A_surfxml_cluster_bb_lat;
3278   char *cluster_availability_file = A_surfxml_cluster_availability_file;
3279   char *cluster_state_file = A_surfxml_cluster_state_file;
3280   char *host_id, *groups, *link_id = NULL;
3281   char *router_id, *link_router, *link_backbone;
3282   char *availability_file = bprintf("%s",cluster_availability_file);
3283   char *state_file = bprintf("%s",cluster_state_file);
3284
3285   xbt_dict_t patterns = xbt_dict_new();
3286   xbt_dict_set(patterns,"id",cluster_id,NULL);
3287   xbt_dict_set(patterns,"prefix",cluster_prefix,NULL);
3288   xbt_dict_set(patterns,"suffix",cluster_suffix,NULL);
3289
3290
3291 #ifdef HAVE_PCRE_LIB
3292   char *route_src_dst;
3293 #endif
3294   unsigned int iter;
3295   int start, end, i;
3296   xbt_dynar_t radical_elements;
3297   xbt_dynar_t radical_ends;
3298   int cluster_sharing_policy = AX_surfxml_cluster_sharing_policy;
3299   int cluster_bb_sharing_policy = AX_surfxml_cluster_bb_sharing_policy;
3300
3301 #ifndef HAVE_PCRE_LIB
3302   xbt_dynar_t tab_elements_num = xbt_dynar_new(sizeof(int), NULL);
3303   char *route_src, *route_dst;
3304   int j;
3305 #endif
3306
3307   static unsigned int surfxml_buffer_stack_stack_ptr = 1;
3308   static unsigned int surfxml_buffer_stack_stack[1024];
3309
3310   surfxml_buffer_stack_stack[0] = 0;
3311
3312   surfxml_bufferstack_push(1);
3313
3314   SURFXML_BUFFER_SET(AS_id, cluster_id);
3315 #ifdef HAVE_PCRE_LIB
3316   SURFXML_BUFFER_SET(AS_routing, "RuleBased");
3317   DEBUG1("<AS id=\"%s\"\trouting=\"RuleBased\">", cluster_id);
3318 #else
3319   SURFXML_BUFFER_SET(AS_routing, "Full");
3320   DEBUG1("<AS id=\"%s\"\trouting=\"Full\">", cluster_id);
3321 #endif
3322   SURFXML_START_TAG(AS);
3323
3324   radical_elements = xbt_str_split(cluster_radical, ",");
3325   xbt_dynar_foreach(radical_elements, iter, groups) {
3326     radical_ends = xbt_str_split(groups, "-");
3327     switch (xbt_dynar_length(radical_ends)) {
3328     case 1:
3329       surf_parse_get_int(&start,
3330                          xbt_dynar_get_as(radical_ends, 0, char *));
3331       host_id = bprintf("%s%d%s", cluster_prefix, start, cluster_suffix);
3332 #ifndef HAVE_PCRE_LIB
3333       xbt_dynar_push_as(tab_elements_num, int, start);
3334 #endif
3335       link_id = bprintf("%s_link_%d", cluster_id, start);
3336
3337       DEBUG2("<host\tid=\"%s\"\tpower=\"%s\">", host_id, cluster_power);
3338       A_surfxml_host_state = A_surfxml_host_state_ON;
3339       SURFXML_BUFFER_SET(host_id, host_id);
3340       SURFXML_BUFFER_SET(host_power, cluster_power);
3341       SURFXML_BUFFER_SET(host_core, cluster_core);
3342       SURFXML_BUFFER_SET(host_availability, "1.0");
3343           xbt_dict_set(patterns,"radical",bprintf("%d",start),NULL);
3344           availability_file = bprintf("%s",cluster_availability_file);
3345           state_file = bprintf("%s",cluster_state_file);
3346           DEBUG1("\tavailability_file=\"%s\"",xbt_str_varsubst(availability_file,patterns));
3347           DEBUG1("\tstate_file=\"%s\"",xbt_str_varsubst(state_file,patterns));
3348           SURFXML_BUFFER_SET(host_availability_file, xbt_str_varsubst(availability_file,patterns));
3349           SURFXML_BUFFER_SET(host_state_file, xbt_str_varsubst(state_file,patterns));
3350           DEBUG0("</host>");
3351       SURFXML_START_TAG(host);
3352       SURFXML_END_TAG(host);
3353
3354       DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id,cluster_bw, cluster_lat);
3355       A_surfxml_link_state = A_surfxml_link_state_ON;
3356       A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3357       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3358           {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3359       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
3360           {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3361       SURFXML_BUFFER_SET(link_id, link_id);
3362       SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
3363       SURFXML_BUFFER_SET(link_latency, cluster_lat);
3364       SURFXML_BUFFER_SET(link_bandwidth_file, "");
3365       SURFXML_BUFFER_SET(link_latency_file, "");
3366       SURFXML_BUFFER_SET(link_state_file, "");
3367       SURFXML_START_TAG(link);
3368       SURFXML_END_TAG(link);
3369
3370       free(link_id);
3371       free(host_id);
3372       break;
3373
3374     case 2:
3375
3376       surf_parse_get_int(&start,
3377                          xbt_dynar_get_as(radical_ends, 0, char *));
3378       surf_parse_get_int(&end, xbt_dynar_get_as(radical_ends, 1, char *));
3379       for (i = start; i <= end; i++) {
3380         host_id = bprintf("%s%d%s", cluster_prefix, i, cluster_suffix);
3381 #ifndef HAVE_PCRE_LIB
3382         xbt_dynar_push_as(tab_elements_num, int, i);
3383 #endif
3384         link_id = bprintf("%s_link_%d", cluster_id, i);
3385
3386         DEBUG2("<host\tid=\"%s\"\tpower=\"%s\"", host_id, cluster_power);
3387         A_surfxml_host_state = A_surfxml_host_state_ON;
3388         SURFXML_BUFFER_SET(host_id, host_id);
3389         SURFXML_BUFFER_SET(host_power, cluster_power);
3390         SURFXML_BUFFER_SET(host_core, cluster_core);
3391                 SURFXML_BUFFER_SET(host_availability, "1.0");
3392                 xbt_dict_set(patterns,"radical",bprintf("%d",i),NULL);
3393                 availability_file = bprintf("%s",cluster_availability_file);
3394                 state_file = bprintf("%s",cluster_state_file);
3395                 DEBUG1("\tavailability_file=\"%s\"",xbt_str_varsubst(availability_file,patterns));
3396                 DEBUG1("\tstate_file=\"%s\"",xbt_str_varsubst(state_file,patterns));
3397                 SURFXML_BUFFER_SET(host_availability_file, xbt_str_varsubst(availability_file,patterns));
3398                 SURFXML_BUFFER_SET(host_state_file, xbt_str_varsubst(state_file,patterns));
3399                 DEBUG0("</host>");
3400         SURFXML_START_TAG(host);
3401         SURFXML_END_TAG(host);
3402
3403         DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id,cluster_bw, cluster_lat);
3404         A_surfxml_link_state = A_surfxml_link_state_ON;
3405         A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3406         if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3407             {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3408         if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
3409             {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3410         SURFXML_BUFFER_SET(link_id, link_id);
3411         SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
3412         SURFXML_BUFFER_SET(link_latency, cluster_lat);
3413         SURFXML_BUFFER_SET(link_bandwidth_file, "");
3414         SURFXML_BUFFER_SET(link_latency_file, "");
3415         SURFXML_BUFFER_SET(link_state_file, "");
3416         SURFXML_START_TAG(link);
3417         SURFXML_END_TAG(link);
3418
3419         free(link_id);
3420         free(host_id);
3421       }
3422       break;
3423
3424     default:
3425       DEBUG0("Malformed radical");
3426     }
3427
3428     xbt_dynar_free(&radical_ends);
3429   }
3430   xbt_dynar_free(&radical_elements);
3431
3432   DEBUG0(" ");
3433   router_id =
3434       bprintf("%s%s_router%s", cluster_prefix, cluster_id,
3435               cluster_suffix);
3436   link_router = bprintf("%s_link_%s_router", cluster_id, cluster_id);
3437   link_backbone = bprintf("%s_backbone", cluster_id);
3438
3439   DEBUG1("<router id=\"%s\"/>", router_id);
3440   SURFXML_BUFFER_SET(router_id, router_id);;
3441   SURFXML_START_TAG(router);
3442   SURFXML_END_TAG(router);
3443
3444   DEBUG3("<link\tid=\"%s\" bw=\"%s\" lat=\"%s\"/>", link_router,cluster_bw, cluster_lat);
3445   A_surfxml_link_state = A_surfxml_link_state_ON;
3446   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3447   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3448   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3449   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FATPIPE)
3450   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3451   SURFXML_BUFFER_SET(link_id, link_router);
3452   SURFXML_BUFFER_SET(link_bandwidth, cluster_bw);
3453   SURFXML_BUFFER_SET(link_latency, cluster_lat);
3454   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3455   SURFXML_BUFFER_SET(link_latency_file, "");
3456   SURFXML_BUFFER_SET(link_state_file, "");
3457   SURFXML_START_TAG(link);
3458   SURFXML_END_TAG(link);
3459
3460   DEBUG3("<link\tid=\"%s\" bw=\"%s\" lat=\"%s\"/>", link_backbone,cluster_bb_bw, cluster_bb_lat);
3461   A_surfxml_link_state = A_surfxml_link_state_ON;
3462   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3463   if(cluster_bb_sharing_policy == A_surfxml_cluster_bb_sharing_policy_FATPIPE)
3464   {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FATPIPE;}
3465   SURFXML_BUFFER_SET(link_id, link_backbone);
3466   SURFXML_BUFFER_SET(link_bandwidth, cluster_bb_bw);
3467   SURFXML_BUFFER_SET(link_latency, cluster_bb_lat);
3468   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3469   SURFXML_BUFFER_SET(link_latency_file, "");
3470   SURFXML_BUFFER_SET(link_state_file, "");
3471   SURFXML_START_TAG(link);
3472   SURFXML_END_TAG(link);
3473
3474   DEBUG0(" ");
3475
3476 #ifdef HAVE_PCRE_LIB
3477   char *new_suffix = xbt_strdup("");
3478
3479   radical_elements = xbt_str_split(cluster_suffix, ".");
3480   xbt_dynar_foreach(radical_elements, iter, groups) {
3481     if (strcmp(groups, "")) {
3482       char *old_suffix = new_suffix;
3483       new_suffix = bprintf("%s\\.%s", old_suffix, groups);
3484       free(old_suffix);
3485     }
3486   }
3487   route_src_dst = bprintf("%s(.*)%s", cluster_prefix, new_suffix);
3488   xbt_dynar_free(&radical_elements);
3489   free(new_suffix);
3490
3491   char *pcre_link_src = bprintf("%s_link_$1src", cluster_id);
3492   char *pcre_link_backbone = bprintf("%s_backbone", cluster_id);
3493   char *pcre_link_dst = bprintf("%s_link_$1dst", cluster_id);
3494
3495   DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", route_src_dst, route_src_dst);
3496   DEBUG0("symmetrical=\"NO\">");
3497   SURFXML_BUFFER_SET(route_src, route_src_dst);
3498   SURFXML_BUFFER_SET(route_dst, route_src_dst);
3499   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3500   SURFXML_START_TAG(route);
3501
3502   DEBUG1("<link_ctn\tid=\"%s\"/>", pcre_link_src);
3503   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_src);
3504   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3505   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3506   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
3507   SURFXML_START_TAG(link_ctn);
3508   SURFXML_END_TAG(link_ctn);
3509
3510   DEBUG1("<link_ctn\tid=\"%s\"/>", pcre_link_backbone);
3511   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_backbone);
3512   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3513   SURFXML_START_TAG(link_ctn);
3514   SURFXML_END_TAG(link_ctn);
3515
3516   DEBUG1("<link_ctn\tid=\"%s\"/>", pcre_link_dst);
3517   SURFXML_BUFFER_SET(link_ctn_id, pcre_link_dst);
3518   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3519   if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3520   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_DOWN;}
3521   SURFXML_START_TAG(link_ctn);
3522   SURFXML_END_TAG(link_ctn);
3523
3524   DEBUG0("</route>");
3525   SURFXML_END_TAG(route);
3526
3527   free(pcre_link_dst);
3528   free(pcre_link_backbone);
3529   free(pcre_link_src);
3530   free(route_src_dst);
3531 #else
3532   for (i = 0; i <= xbt_dynar_length(tab_elements_num); i++) {
3533     for (j = 0; j <= xbt_dynar_length(tab_elements_num); j++) {
3534       if (i == xbt_dynar_length(tab_elements_num)) {
3535         route_src = router_id;
3536       } else {
3537         route_src =
3538             bprintf("%s%d%s", cluster_prefix,
3539                     xbt_dynar_get_as(tab_elements_num, i, int),
3540                     cluster_suffix);
3541       }
3542
3543       if (j == xbt_dynar_length(tab_elements_num)) {
3544         route_dst = router_id;
3545       } else {
3546         route_dst =
3547             bprintf("%s%d%s", cluster_prefix,
3548                     xbt_dynar_get_as(tab_elements_num, j, int),
3549                     cluster_suffix);
3550       }
3551
3552       DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", route_src, route_dst);
3553       DEBUG0("symmetrical=\"NO\">");
3554       SURFXML_BUFFER_SET(route_src, route_src);
3555       SURFXML_BUFFER_SET(route_dst, route_dst);
3556       A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3557       SURFXML_START_TAG(route);
3558
3559       if (i == xbt_dynar_length(tab_elements_num)) {
3560         route_src = link_router;
3561       } else {
3562         route_src =
3563             bprintf("%s_link_%d", cluster_id,
3564                     xbt_dynar_get_as(tab_elements_num, i, int));
3565       }
3566
3567       if (j == xbt_dynar_length(tab_elements_num)) {
3568         route_dst = link_router;
3569       } else {
3570         route_dst =
3571             bprintf("%s_link_%d", cluster_id,
3572                     xbt_dynar_get_as(tab_elements_num, j, int));
3573       }
3574
3575       DEBUG1("<link_ctn\tid=\"%s\"/>", route_src);
3576       SURFXML_BUFFER_SET(link_ctn_id, route_src);
3577       A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3578       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3579       {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
3580       SURFXML_START_TAG(link_ctn);
3581       SURFXML_END_TAG(link_ctn);
3582
3583       DEBUG1("<link_ctn\tid=\"%s_backbone\"/>", cluster_id);
3584       SURFXML_BUFFER_SET(link_ctn_id, bprintf("%s_backbone", cluster_id));
3585       A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3586       SURFXML_START_TAG(link_ctn);
3587       SURFXML_END_TAG(link_ctn);
3588
3589       DEBUG1("<link_ctn\tid=\"%s\"/>", route_dst);
3590       SURFXML_BUFFER_SET(link_ctn_id, route_dst);
3591       A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3592       if(cluster_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3593       {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_DOWN;}
3594       SURFXML_START_TAG(link_ctn);
3595       SURFXML_END_TAG(link_ctn);
3596
3597       DEBUG0("</route>");
3598       SURFXML_END_TAG(route);
3599     }
3600   }
3601   xbt_dynar_free(&tab_elements_num);
3602   free(router_id);
3603
3604 #endif
3605
3606   free(link_backbone);
3607   free(link_router);
3608   xbt_dict_free(&patterns);
3609   free(availability_file);
3610   free(state_file);
3611
3612   DEBUG0("</AS>");
3613   SURFXML_END_TAG(AS);
3614   DEBUG0(" ");
3615
3616   surfxml_bufferstack_pop(1);
3617 }
3618
3619 static void routing_parse_Speer(void)
3620 {
3621   static int AX_ptr = 0;
3622
3623   char *peer_id = A_surfxml_peer_id;
3624   char *peer_power = A_surfxml_peer_power;
3625   char *peer_bw_in = A_surfxml_peer_bw_in;
3626   char *peer_bw_out = A_surfxml_peer_bw_out;
3627   char *peer_lat = A_surfxml_peer_lat;
3628   char *peer_coord = A_surfxml_peer_coordinates;
3629   char *peer_state_file = A_surfxml_peer_state_file;
3630   char *peer_availability_file = A_surfxml_peer_availability_file;
3631
3632   char *host_id = NULL;
3633   char *router_id, *link_router, *link_backbone, *link_id_up, *link_id_down;
3634
3635 #ifdef HAVE_PCRE_LIB
3636
3637 #endif
3638
3639   int peer_sharing_policy = AX_surfxml_peer_sharing_policy;
3640
3641 #ifndef HAVE_PCRE_LIB
3642   //xbt_dynar_t tab_elements_num = xbt_dynar_new(sizeof(int), NULL);
3643   //char *route_src, *route_dst;
3644   //int j;
3645 #endif
3646
3647   static unsigned int surfxml_buffer_stack_stack_ptr = 1;
3648   static unsigned int surfxml_buffer_stack_stack[1024];
3649
3650   surfxml_buffer_stack_stack[0] = 0;
3651
3652   surfxml_bufferstack_push(1);
3653
3654   SURFXML_BUFFER_SET(AS_id, peer_id);
3655 #ifdef HAVE_PCRE_LIB
3656   SURFXML_BUFFER_SET(AS_routing, "RuleBased");
3657   DEBUG1("<AS id=\"%s\"\trouting=\"RuleBased\">", peer_id);
3658 #else
3659   SURFXML_BUFFER_SET(AS_routing, "Full");
3660   DEBUG1("<AS id=\"%s\"\trouting=\"Full\">", peer_id);
3661 #endif
3662   SURFXML_START_TAG(AS);
3663
3664   DEBUG0(" ");
3665   host_id = bprintf("peer_%s", peer_id);
3666   router_id = bprintf("router_%s", peer_id);
3667   link_id_up = bprintf("link_%s_up", peer_id);
3668   link_id_down = bprintf("link_%s_down", peer_id);
3669
3670   link_router = bprintf("%s_link_router", peer_id);
3671   link_backbone = bprintf("%s_backbone", peer_id);
3672
3673   DEBUG2("<host\tid=\"%s\"\tpower=\"%s\"/>", host_id, peer_power);
3674   A_surfxml_host_state = A_surfxml_host_state_ON;
3675   SURFXML_BUFFER_SET(host_id, host_id);
3676   SURFXML_BUFFER_SET(host_power, peer_power);
3677   SURFXML_BUFFER_SET(host_availability, "1.0");
3678   SURFXML_BUFFER_SET(host_availability_file, peer_availability_file);
3679   SURFXML_BUFFER_SET(host_state_file, peer_state_file);
3680   SURFXML_START_TAG(host);
3681   SURFXML_END_TAG(host);
3682
3683   DEBUG2("<router id=\"%s\"\tcoordinates=\"%s\"/>", router_id, peer_coord);
3684   SURFXML_BUFFER_SET(router_id, router_id);
3685   SURFXML_BUFFER_SET(router_coordinates, peer_coord);
3686   SURFXML_START_TAG(router);
3687   SURFXML_END_TAG(router);
3688
3689   DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id_up, peer_bw_in, peer_lat);
3690   A_surfxml_link_state = A_surfxml_link_state_ON;
3691   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3692   if(peer_sharing_policy == A_surfxml_peer_sharing_policy_FULLDUPLEX)
3693 {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3694   SURFXML_BUFFER_SET(link_id, link_id_up);
3695   SURFXML_BUFFER_SET(link_bandwidth, peer_bw_in);
3696   SURFXML_BUFFER_SET(link_latency, peer_lat);
3697   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3698   SURFXML_BUFFER_SET(link_latency_file, "");
3699   SURFXML_BUFFER_SET(link_state_file, "");
3700   SURFXML_START_TAG(link);
3701   SURFXML_END_TAG(link);
3702
3703   DEBUG3("<link\tid=\"%s\"\tbw=\"%s\"\tlat=\"%s\"/>", link_id_down, peer_bw_out, peer_lat);
3704   A_surfxml_link_state = A_surfxml_link_state_ON;
3705   A_surfxml_link_sharing_policy = A_surfxml_link_sharing_policy_SHARED;
3706   if(peer_sharing_policy == A_surfxml_cluster_sharing_policy_FULLDUPLEX)
3707 {A_surfxml_link_sharing_policy =  A_surfxml_link_sharing_policy_FULLDUPLEX;}
3708   SURFXML_BUFFER_SET(link_id, link_id_down);
3709   SURFXML_BUFFER_SET(link_bandwidth, peer_bw_out);
3710   SURFXML_BUFFER_SET(link_latency, peer_lat);
3711   SURFXML_BUFFER_SET(link_bandwidth_file, "");
3712   SURFXML_BUFFER_SET(link_latency_file, "");
3713   SURFXML_BUFFER_SET(link_state_file, "");
3714   SURFXML_START_TAG(link);
3715   SURFXML_END_TAG(link);
3716
3717   DEBUG0(" ");
3718
3719   // begin here
3720   DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", peer_id, router_id);
3721   DEBUG0("symmetrical=\"NO\">");
3722   SURFXML_BUFFER_SET(route_src, peer_id);
3723   SURFXML_BUFFER_SET(route_dst, router_id);
3724   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3725   SURFXML_START_TAG(route);
3726
3727   DEBUG1("<link_ctn\tid=\"%s\"/>", link_id_up);
3728   SURFXML_BUFFER_SET(link_ctn_id, link_id_up);
3729   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3730   if(peer_sharing_policy == A_surfxml_peer_sharing_policy_FULLDUPLEX)
3731   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_UP;}
3732   SURFXML_START_TAG(link_ctn);
3733   SURFXML_END_TAG(link_ctn);
3734
3735   DEBUG0("</route>");
3736   SURFXML_END_TAG(route);
3737
3738   //Opposite Route
3739   DEBUG2("<route\tsrc=\"%s\"\tdst=\"%s\"", router_id, peer_id);
3740   DEBUG0("symmetrical=\"NO\">");
3741   SURFXML_BUFFER_SET(route_src, router_id);
3742   SURFXML_BUFFER_SET(route_dst, peer_id);
3743   A_surfxml_route_symmetrical = A_surfxml_route_symmetrical_NO;
3744   SURFXML_START_TAG(route);
3745
3746   DEBUG1("<link_ctn\tid=\"%s\"/>", link_id_down);
3747   SURFXML_BUFFER_SET(link_ctn_id, link_id_down);
3748   A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_NONE;
3749   if(peer_sharing_policy == A_surfxml_peer_sharing_policy_FULLDUPLEX)
3750   {A_surfxml_link_ctn_direction = A_surfxml_link_ctn_direction_DOWN;}
3751   SURFXML_START_TAG(link_ctn);
3752   SURFXML_END_TAG(link_ctn);
3753
3754   DEBUG0("</route>");
3755   SURFXML_END_TAG(route);
3756
3757   DEBUG0("</AS>");
3758   SURFXML_END_TAG(AS);
3759   DEBUG0(" ");
3760
3761   //xbt_dynar_free(&tab_elements_num);
3762
3763   surfxml_bufferstack_pop(1);
3764 }
3765
3766
3767 /*
3768  * New methods to init the routing model component from the lua script
3769  */
3770
3771 /*
3772  * calling parse_S_AS_lua with lua values
3773  */
3774 void routing_AS_init(const char *AS_id, const char *AS_routing)
3775 {
3776   parse_S_AS_lua((char *) AS_id, (char *) AS_routing);
3777 }
3778
3779 /*
3780  * calling parse_E_AS_lua to fisnish the creation of routing component
3781  */
3782 void routing_AS_end(const char *AS_id)
3783 {
3784   parse_E_AS_lua((char *) AS_id);
3785 }
3786
3787 /*
3788  * add a host to the network element list
3789  */
3790
3791 void routing_add_host(const char *host_id)
3792 {
3793   parse_S_host_lua((char *) host_id, (char*)""); // FIXME propagate coordinate system to lua
3794 }
3795
3796 /*
3797  * Set a new link on the actual list of link for a route or ASroute
3798  */
3799 void routing_add_link(const char *link_id)
3800 {
3801   parse_E_link_c_ctn_new_elem_lua((char *) link_id);
3802 }
3803
3804 /*
3805  *Set the endpoints for a route
3806  */
3807 void routing_set_route(const char *src_id, const char *dst_id)
3808 {
3809   parse_S_route_new_and_endpoints_lua(src_id, dst_id);
3810 }
3811
3812 /*
3813  * Store the route by calling parse_E_route_store_route
3814  */
3815 void routing_store_route(void)
3816 {
3817   parse_E_route_store_route();
3818 }