-static route_extended_t floyd_get_route(routing_component_t rc, const char* src,const char* dst) {
- xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
-
- /* set utils vars */
- routing_component_floyd_t routing = (routing_component_floyd_t) rc;
- int table_size = xbt_dict_length(routing->to_index);
-
- generic_src_dst_check(rc,src,dst);
- int *src_id = xbt_dict_get_or_null(routing->to_index,src);
- int *dst_id = xbt_dict_get_or_null(routing->to_index,dst);
- xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s) or \"to\"(%s) no found in the local table",src,dst);
-
- /* create a result route */
- route_extended_t new_e_route = xbt_new0(s_route_extended_t,1);
- new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
- new_e_route->src_gateway = NULL;
- new_e_route->dst_gateway = NULL;
-
- int first = 1;
- int pred = *dst_id;
- int prev_pred = 0;
- char *gw_src=NULL,*gw_dst=NULL, *prev_gw_src,*prev_gw_dst, *first_gw=NULL;
- unsigned int cpt;
- void* link;
- xbt_dynar_t links;
-
- do {
- prev_pred = pred;
- pred = TO_FLOYD_PRED(*src_id, pred);
- if(pred == -1) /* if no pred in route -> no route to host */
- break;
- xbt_assert2(TO_FLOYD_LINK(pred,prev_pred),"Invalid link for the route between \"%s\" or \"%s\"", src, dst);
-
- prev_gw_src = gw_src;
- prev_gw_dst = gw_dst;
-
- route_extended_t e_route = TO_FLOYD_LINK(pred,prev_pred);
- gw_src = e_route->src_gateway;
- gw_dst = e_route->dst_gateway;
-
- if(first) first_gw = gw_dst;
-
- if(rc->hierarchy == SURF_ROUTING_RECURSIVE && !first && strcmp(gw_dst,prev_gw_src)) {
- xbt_dynar_t e_route_as_to_as = (*(global_routing->get_route))(gw_dst,prev_gw_src);
- xbt_assert2(e_route_as_to_as,"no route between \"%s\" and \"%s\"",gw_dst,prev_gw_src);
- links = e_route_as_to_as;
- int pos = 0;
- xbt_dynar_foreach(links, cpt, link) {
- xbt_dynar_insert_at(new_e_route->generic_route.link_list,pos,&link);
- pos++;
- }
- }
-
- links = e_route->generic_route.link_list;
- xbt_dynar_foreach(links, cpt, link) {
- xbt_dynar_unshift(new_e_route->generic_route.link_list,&link);
- }
- first=0;
-
- } while(pred != *src_id);
- xbt_assert4(pred != -1, "no route from host %d to %d (\"%s\" to \"%s\")", *src_id, *dst_id,src,dst);
-
- if(rc->hierarchy == SURF_ROUTING_RECURSIVE) {
- new_e_route->src_gateway = xbt_strdup(gw_src);
- new_e_route->dst_gateway = xbt_strdup(first_gw);
- }
-
- return new_e_route;
-}
-
-static void floyd_finalize(routing_component_t rc) {
- routing_component_floyd_t routing = (routing_component_floyd_t)rc;
- int i,j,table_size;
- if (routing) {
- table_size = xbt_dict_length(routing->to_index);
- /* Delete link_table */
- for (i=0;i<table_size;i++)
- for (j=0;j<table_size;j++)
- generic_free_extended_route(TO_FLOYD_LINK(i,j));
- xbt_free(routing->link_table);
- /* Delete bypass dict */
- xbt_dict_free(&routing->bypassRoutes);
- /* Delete index dict */
- xbt_dict_free(&(routing->to_index));
- /* Delete dictionary index dict, predecessor and links table */
- xbt_free(routing->predecessor_table);
- /* Delete structure */
- xbt_free(rc);
- }
-}
-
-static void* model_floyd_create(void) {
- routing_component_floyd_t new_component = xbt_new0(s_routing_component_floyd_t,1);
- new_component->generic_routing.set_processing_unit = generic_set_processing_unit;
- new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
- new_component->generic_routing.set_route = generic_set_route;
- new_component->generic_routing.set_ASroute = generic_set_ASroute;
- new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
- new_component->generic_routing.get_route = floyd_get_route;
- new_component->generic_routing.get_onelink_routes = floyd_get_onelink_routes;
- new_component->generic_routing.get_bypass_route = generic_get_bypassroute;
- new_component->generic_routing.finalize = floyd_finalize;
- new_component->to_index = xbt_dict_new();
- new_component->bypassRoutes = xbt_dict_new();
- new_component->parse_routes = xbt_dict_new();
- return new_component;
-}
-
-static void model_floyd_load(void) {
- /* use "surfxml_add_callback" to add a parse function call */
-}
-
-static void model_floyd_unload(void) {
- /* use "surfxml_del_callback" to remove a parse function call */
-}
-
-static void model_floyd_end(void) {
-
- routing_component_floyd_t routing = ((routing_component_floyd_t)current_routing);
- xbt_dict_cursor_t cursor = NULL;
- double * cost_table;
- char *key,*data, *end;
- const char *sep = "#";
- xbt_dynar_t keys;
- int src_id, dst_id;
- unsigned int i,j,a,b,c;
-
- /* set the size of inicial table */
- int table_size = xbt_dict_length(routing->to_index);
-
- /* Create Cost, Predecessor and Link tables */
- cost_table = xbt_new0(double, table_size*table_size); /* link cost from host to host */
- routing->predecessor_table = xbt_new0(int, table_size*table_size); /* predecessor host numbers */
- routing->link_table = xbt_new0(route_extended_t, table_size*table_size); /* actual link between src and dst */
-
- /* Initialize costs and predecessors*/
- for(i = 0; i<table_size;i++)
- for(j = 0; j<table_size;j++) {
- TO_FLOYD_COST(i,j) = DBL_MAX;
- TO_FLOYD_PRED(i,j) = -1;
- TO_FLOYD_LINK(i,j) = NULL; /* fixed, missing in the previous version */
- }
-
- /* Put the routes in position */
- xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
- keys = xbt_str_split_str(key, sep);
- src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 10);
- dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 10);
- TO_FLOYD_LINK(src_id,dst_id) = generic_new_extended_route(current_routing->hierarchy,data,0);
- TO_FLOYD_PRED(src_id,dst_id) = src_id;
- /* set link cost */
- TO_FLOYD_COST(src_id,dst_id) = ((TO_FLOYD_LINK(src_id,dst_id))->generic_route.link_list)->used; /* count of links, old model assume 1 */
- xbt_dynar_free(&keys);
- }
-
- /* Add the loopback if needed */
- if(current_routing->hierarchy == SURF_ROUTING_BASE) {
- for (i = 0; i < table_size; i++) {
- route_extended_t e_route = TO_FLOYD_LINK(i, i);
- if(!e_route) {
- e_route = xbt_new0(s_route_extended_t,1);
- e_route->src_gateway = NULL;
- e_route->dst_gateway = NULL;
- e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
- xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
- TO_FLOYD_LINK(i,i) = e_route;
- TO_FLOYD_PRED(i,i) = i;
- TO_FLOYD_COST(i,i) = 1;
- }
- }
- }
- /* Calculate path costs */
- for(c=0;c<table_size;c++) {
- for(a=0;a<table_size;a++) {
- for(b=0;b<table_size;b++) {
- if(TO_FLOYD_COST(a,c) < DBL_MAX && TO_FLOYD_COST(c,b) < DBL_MAX) {
- if(TO_FLOYD_COST(a,b) == DBL_MAX ||
- (TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b) < TO_FLOYD_COST(a,b))) {
- TO_FLOYD_COST(a,b) = TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b);
- TO_FLOYD_PRED(a,b) = TO_FLOYD_PRED(c,b);
- }
- }
- }
- }
- }
-
- /* delete the parse table */
- xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
- route_t route = (route_t)data;
- xbt_dynar_free(&(route->link_list));
- xbt_free(data);
- }
-
- /* delete parse dict */
- xbt_dict_free(&(routing->parse_routes));
-
- /* cleanup */
- xbt_free(cost_table);
-}
-
-/* ************************************************************************** */
-/* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
-
-typedef struct {
- s_routing_component_t generic_routing;
- xbt_dict_t to_index;
- xbt_dict_t bypassRoutes;
- xbt_graph_t route_graph; /* xbt_graph */
- xbt_dict_t graph_node_map; /* map */
- xbt_dict_t route_cache; /* use in cache mode */
- int cached;
- xbt_dict_t parse_routes;
-} s_routing_component_dijkstra_t,*routing_component_dijkstra_t;
-
-
-typedef struct graph_node_data {
- int id;
- int graph_id; /* used for caching internal graph id's */
-} s_graph_node_data_t, * graph_node_data_t;
-
-typedef struct graph_node_map_element {
- xbt_node_t node;
-} s_graph_node_map_element_t, * graph_node_map_element_t;
-
-typedef struct route_cache_element {
- int * pred_arr;
- int size;
-} s_route_cache_element_t, * route_cache_element_t;
-
-/* Free functions */
-
-static void route_cache_elem_free(void *e) {
- route_cache_element_t elm=(route_cache_element_t)e;
- if (elm) {
- xbt_free(elm->pred_arr);
- xbt_free(elm);
- }
-}
-
-static void graph_node_map_elem_free(void *e) {
- graph_node_map_element_t elm = (graph_node_map_element_t)e;
- if(elm) {
- xbt_free(elm);
- }
-}
-
-static void graph_edge_data_free(void *e) {
- route_extended_t e_route = (route_extended_t)e;
- if(e_route) {
- xbt_dynar_free(&(e_route->generic_route.link_list));
- if(e_route->src_gateway) xbt_free(e_route->src_gateway);
- if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
- xbt_free(e_route);
- }
-}
-
-/* Utility functions */
-
-static xbt_node_t route_graph_new_node(routing_component_dijkstra_t rc, int id, int graph_id) {
- routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
- xbt_node_t node = NULL;
- graph_node_data_t data = NULL;
- graph_node_map_element_t elm = NULL;
-
- data = xbt_new0(struct graph_node_data, 1);
- data->id = id;
- data->graph_id = graph_id;
- node = xbt_graph_new_node(routing->route_graph, data);
-
- elm = xbt_new0(struct graph_node_map_element, 1);
- elm->node = node;
- xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);
-
- return node;
-}
-
-static graph_node_map_element_t graph_node_map_search(routing_component_dijkstra_t rc, int id) {
- routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
- graph_node_map_element_t elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&id), sizeof(int));
- return elm;
-}
-
-/* Parsing */
-
-static void route_new_dijkstra(routing_component_dijkstra_t rc, int src_id, int dst_id, route_extended_t e_route ) {
- routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
-
- xbt_node_t src = NULL;
- xbt_node_t dst = NULL;
- graph_node_map_element_t src_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&src_id), sizeof(int));
- graph_node_map_element_t dst_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&dst_id), sizeof(int));
-
- if(src_elm)
- src = src_elm->node;
-
- if(dst_elm)
- dst = dst_elm->node;
-
- /* add nodes if they don't exist in the graph */
- if(src_id == dst_id && src == NULL && dst == NULL) {
- src = route_graph_new_node(rc,src_id, -1);
- dst = src;
- } else {
- if(src == NULL) {
- src = route_graph_new_node(rc,src_id, -1);
- }
- if(dst == NULL) {
- dst = route_graph_new_node(rc,dst_id, -1);
- }
- }
-
- /* add link as edge to graph */
- xbt_graph_new_edge(routing->route_graph, src, dst, e_route);
-}
-
-static void add_loopback_dijkstra(routing_component_dijkstra_t rc) {
- routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
-
- xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
-
- xbt_node_t node = NULL;
- unsigned int cursor2;
- xbt_dynar_foreach(nodes, cursor2, node) {
- xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
- xbt_edge_t edge = NULL;
- unsigned int cursor;
-
- int found = 0;
- xbt_dynar_foreach(out_edges, cursor, edge) {
- xbt_node_t other_node = xbt_graph_edge_get_target(edge);
- if(other_node == node) {
- found = 1;
- break;
- }
- }
-
- if(!found) {
- route_extended_t e_route = xbt_new0(s_route_extended_t,1);
- e_route->src_gateway = NULL;
- e_route->dst_gateway = NULL;
- e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
- xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
- xbt_graph_new_edge(routing->route_graph, node, node, e_route);
- }
- }
-}
-
-/* Business methods */
-static xbt_dynar_t dijkstra_get_onelink_routes(routing_component_t rc)