+ xbt_dict_cursor_t cursor = NULL;
+ xbt_dynar_t keys = NULL;
+
+ /* set utils vars */
+ routing_component_full_t routing = ((routing_component_full_t)current_routing);
+ int table_size = xbt_dict_length(routing->to_index);
+
+ /* Create the routing table */
+ routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
+
+ /* 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_ROUTE_FULL(src_id,dst_id) = generic_new_extended_route(current_routing->hierarchy,data,1);
+ xbt_dynar_free(&keys);
+ }
+
+ /* delete the parse table */
+ xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
+ route = (route_t)data;
+ xbt_dynar_free(&(route->link_list));
+ xbt_free(data);
+ }
+
+ /* delete parse dict */
+ xbt_dict_free(&(routing->parse_routes));
+
+ /* Add the loopback if needed */
+ if(current_routing->hierarchy == SURF_ROUTING_BASE) {
+ for (i = 0; i < table_size; i++) {
+ e_route = TO_ROUTE_FULL(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_ROUTE_FULL(i, i) = e_route;
+ }
+ }
+ }
+
+ /* Shrink the dynar routes (save unused slots) */
+ for (i=0;i<table_size;i++)
+ for (j=0;j<table_size;j++)
+ if(TO_ROUTE_FULL(i,j))
+ xbt_dynar_shrink(TO_ROUTE_FULL(i,j)->generic_route.link_list,0);
+}
+
+/* ************************************************************************** */
+/* *************************** FLOYD ROUTING ******************************** */
+
+#define TO_FLOYD_COST(i,j) cost_table[(i)+(j)*table_size]
+#define TO_FLOYD_PRED(i,j) (routing->predecessor_table)[(i)+(j)*table_size]
+#define TO_FLOYD_LINK(i,j) (routing->link_table)[(i)+(j)*table_size]
+
+/* Routing model structure */
+
+typedef struct {
+ s_routing_component_t generic_routing;
+ /* vars for calculate the floyd algorith. */
+ int *predecessor_table;
+ route_extended_t *link_table; /* char* -> int* */
+ xbt_dict_t to_index;
+ xbt_dict_t bypassRoutes;
+ /* store data during the parse process */
+ xbt_dict_t parse_routes;
+} s_routing_component_floyd_t,*routing_component_floyd_t;
+
+static route_extended_t floyd_get_route(routing_component_t rc, const char* src,const char* dst);
+
+/* Business methods */
+static xbt_dynar_t floyd_get_onelink_routes(routing_component_t rc)
+{
+ xbt_dynar_t ret = xbt_dynar_new (sizeof(onelink_t), xbt_free);
+
+ routing_component_floyd_t routing = (routing_component_floyd_t)rc;
+ //int table_size = xbt_dict_length(routing->to_index);
+ xbt_dict_cursor_t c1 = NULL, c2 = NULL;
+ char *k1, *d1, *k2, *d2;
+ xbt_dict_foreach(routing->to_index, c1, k1, d1) {
+ xbt_dict_foreach (routing->to_index, c2, k2, d2) {
+ route_extended_t route = floyd_get_route (rc, k1, k2);
+ if (route){
+ if (xbt_dynar_length(route->generic_route.link_list) == 1){
+ void *link = *(void**)xbt_dynar_get_ptr(route->generic_route.link_list,0);
+ onelink_t onelink = xbt_new0 (s_onelink_t, 1);
+ onelink->src = xbt_strdup (k1);
+ onelink->dst = xbt_strdup (k2);
+ onelink->link_ptr = link;
+ xbt_dynar_push (ret, &onelink);
+ }
+ }
+ }
+ }
+ return ret;
+}
+
+static int floyd_is_router(const char *name)
+{
+ xbt_die("\"floyd_is_router\" function not implemented yet");
+}
+
+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.is_router = floyd_is_router;
+ 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 **************************** */