* Get the common father of the to processing units, and the first different
* father in the chain
*/
-static xbt_dynar_t elements_father(const char *src, const char *dst)
+static void elements_father(const char *src, const char *dst,
+ routing_component_t *res_father,
+ routing_component_t *res_src,
+ routing_component_t *res_dst)
{
-
xbt_assert(src && dst, "bad parameters for \"elements_father\" method");
-
- xbt_dynar_t result = xbt_dynar_new(sizeof(char *), NULL);
-
+#define ELEMENTS_FATHER_MAXDEPTH 16 /* increase if it is not enough */
routing_component_t src_as, dst_as;
- int index_src, index_dst, index_father_src, index_father_dst;
- xbt_dynar_t path_src = NULL;
- xbt_dynar_t path_dst = NULL;
- routing_component_t current = NULL;
- routing_component_t *current_src = NULL;
- routing_component_t *current_dst = NULL;
- routing_component_t *father = NULL;
+ routing_component_t path_src[ELEMENTS_FATHER_MAXDEPTH];
+ routing_component_t path_dst[ELEMENTS_FATHER_MAXDEPTH];
+ int index_src = 0;
+ int index_dst = 0;
+ routing_component_t current;
+ routing_component_t current_src;
+ routing_component_t current_dst;
+ routing_component_t father;
/* (1) find the as where the src and dst are located */
- void * src_data = xbt_lib_get_or_null(host_lib,src, ROUTING_HOST_LEVEL);
- void * dst_data = xbt_lib_get_or_null(host_lib,dst, ROUTING_HOST_LEVEL);
- if(!src_data) src_data = xbt_lib_get_or_null(as_router_lib,src, ROUTING_ASR_LEVEL);
- if(!dst_data) dst_data = xbt_lib_get_or_null(as_router_lib,dst, ROUTING_ASR_LEVEL);
- src_as = ((network_element_info_t)src_data)->rc_component;
- dst_as = ((network_element_info_t)dst_data)->rc_component;
-
- xbt_assert(src_as
- && dst_as,
- "Ask for route \"from\"(%s) or \"to\"(%s) no found", src,
- dst);
+ network_element_info_t src_data = xbt_lib_get_or_null(host_lib, src,
+ ROUTING_HOST_LEVEL);
+ network_element_info_t dst_data = xbt_lib_get_or_null(host_lib, dst,
+ ROUTING_HOST_LEVEL);
+ if (!src_data)
+ src_data = xbt_lib_get_or_null(as_router_lib, src, ROUTING_ASR_LEVEL);
+ if (!dst_data)
+ dst_data = xbt_lib_get_or_null(as_router_lib, dst, ROUTING_ASR_LEVEL);
+ src_as = src_data->rc_component;
+ dst_as = dst_data->rc_component;
+
+ xbt_assert(src_as && dst_as,
+ "Ask for route \"from\"(%s) or \"to\"(%s) no found", src, dst);
/* (2) find the path to the root routing component */
- path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
- current = src_as;
- while (current != NULL) {
- xbt_dynar_push(path_src, ¤t);
- current = current->routing_father;
+ for (current = src_as ; current != NULL ; current = current->routing_father) {
+ path_src[index_src++] = current;
+ xbt_assert(index_src <= ELEMENTS_FATHER_MAXDEPTH,
+ "ELEMENTS_FATHER_MAXDEPTH should be increased for path_src");
}
- path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
- current = dst_as;
- while (current != NULL) {
- xbt_dynar_push(path_dst, ¤t);
- current = current->routing_father;
+ for (current = dst_as ; current != NULL ; current = current->routing_father) {
+ path_dst[index_dst++] = current;
+ xbt_assert(index_dst <= ELEMENTS_FATHER_MAXDEPTH,
+ "ELEMENTS_FATHER_MAXDEPTH should be increased for path_dst");
}
/* (3) find the common father */
- index_src = path_src->used - 1;
- index_dst = path_dst->used - 1;
- current_src = xbt_dynar_get_ptr(path_src, index_src);
- current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
- while (index_src >= 0 && index_dst >= 0 && *current_src == *current_dst) {
- current_src = xbt_dynar_get_ptr(path_src, index_src);
- current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
- index_src--;
- index_dst--;
- }
- index_src++;
- index_dst++;
- current_src = xbt_dynar_get_ptr(path_src, index_src);
- current_dst = xbt_dynar_get_ptr(path_dst, index_dst);
+ do {
+ current_src = path_src[--index_src];
+ current_dst = path_dst[--index_dst];
+ } while (index_src > 0 && index_dst > 0 && current_src == current_dst);
/* (4) they are not in the same routing component, make the path */
- index_father_src = index_src + 1;
- index_father_dst = index_dst + 1;
-
- if (*current_src == *current_dst)
+ if (current_src == current_dst)
father = current_src;
else
- father = xbt_dynar_get_ptr(path_src, index_father_src);
+ father = path_src[index_src + 1];
/* (5) result generation */
- xbt_dynar_push(result, father); /* first same the father of src and dst */
- xbt_dynar_push(result, current_src); /* second the first different father of src */
- xbt_dynar_push(result, current_dst); /* three the first different father of dst */
-
- xbt_dynar_free(&path_src);
- xbt_dynar_free(&path_dst);
+ *res_father = father; /* first the common father of src and dst */
+ *res_src = current_src; /* second the first different father of src */
+ *res_dst = current_dst; /* three the first different father of dst */
- return result;
+#undef ELEMENTS_FATHER_MAXDEPTH
}
/* Global Business methods */
/**
- * \brief Recursive function for get_route
+ * \brief Recursive function for get_route_latency
*
* \param src the source host name
* \param dst the destination host name
+ * \param *e_route the route where the links are stored
+ * \param *latency the latency, if needed
*
- * This function is called by "get_route". It allows to walk recursively
- * through the routing components tree.
+ * This function is called by "get_route" and "get_latency". It allows to walk
+ * recursively through the routing components tree.
*/
-static route_extended_t _get_route(const char *src, const char *dst)
+static void _get_route_latency(const char *src, const char *dst,
+ xbt_dynar_t *route, double *latency)
{
+ XBT_DEBUG("Solve route/latency \"%s\" to \"%s\"", src, dst);
+ xbt_assert(src && dst, "bad parameters for \"_get_route_latency\" method");
- void *link;
- unsigned int cpt = 0;
-
- XBT_DEBUG("Solve route \"%s\" to \"%s\"", src, dst);
-
- xbt_assert(src && dst, "bad parameters for \"_get_route\" method");
-
- route_extended_t e_route, e_route_cnt, e_route_src = NULL, e_route_dst =
- NULL;
-
- xbt_dynar_t elem_father_list = elements_father(src, dst);
+ routing_component_t common_father;
+ routing_component_t src_father;
+ routing_component_t dst_father;
+ elements_father(src, dst, &common_father, &src_father, &dst_father);
- routing_component_t common_father =
- xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
- routing_component_t src_father =
- xbt_dynar_get_as(elem_father_list, 1, routing_component_t);
- routing_component_t dst_father =
- xbt_dynar_get_as(elem_father_list, 2, routing_component_t);
+ if (src_father == dst_father) { /* SURF_ROUTING_BASE */
- 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);
-
- if (src_father == dst_father) { /* SURF_ROUTING_BASE */
-
- e_route_cnt =
- (*(common_father->get_route)) (common_father, src, dst);
- xbt_assert(e_route_cnt, "no route between \"%s\" and \"%s\"", src,
- dst);
- // FIXME (optim): faire une copie et pas une série de push
- xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
- xbt_dynar_push(e_route->generic_route.link_list, &link);
- }
- generic_free_extended_route(e_route_cnt);
+ route_extended_t e_route = NULL;
+ if (route) {
+ e_route = common_father->get_route(common_father, src, dst);
+ xbt_assert(e_route, "no route between \"%s\" and \"%s\"", src, dst);
+ *route = e_route->generic_route.link_list;
+ }
+ if (latency) {
+ *latency = common_father->get_latency(common_father, src, dst, e_route);
+ xbt_assert(*latency >= 0.0,
+ "latency error on route between \"%s\" and \"%s\"", src, dst);
+ }
+ if (e_route) {
+ xbt_free(e_route->src_gateway);
+ xbt_free(e_route->dst_gateway);
+ xbt_free(e_route);
+ }
} else { /* SURF_ROUTING_RECURSIVE */
route_extended_t e_route_bypass = NULL;
-
if (common_father->get_bypass_route)
- e_route_bypass =
- (*(common_father->get_bypass_route)) (common_father, src, dst);
+ e_route_bypass = common_father->get_bypass_route(common_father, src, dst);
- if (e_route_bypass)
- e_route_cnt = e_route_bypass;
- else
- e_route_cnt =
- (*(common_father->get_route)) (common_father, src_father->name,
- dst_father->name);
+ xbt_assert(!latency || !e_route_bypass,
+ "Bypass cannot work yet with get_latency");
+
+ route_extended_t e_route_cnt = e_route_bypass
+ ? e_route_bypass
+ : common_father->get_route(common_father,
+ src_father->name, dst_father->name);
xbt_assert(e_route_cnt, "no route between \"%s\" and \"%s\"",
- src_father->name, dst_father->name);
+ src_father->name, dst_father->name);
xbt_assert((e_route_cnt->src_gateway == NULL) ==
- (e_route_cnt->dst_gateway == NULL),
- "bad gateway for route between \"%s\" and \"%s\"", src,
- dst);
+ (e_route_cnt->dst_gateway == NULL),
+ "bad gateway for route between \"%s\" and \"%s\"", src, dst);
+
+ if (route) {
+ *route = xbt_dynar_new(global_routing->size_of_link, NULL);
+ }
+ if (latency) {
+ *latency = common_father->get_latency(common_father,
+ src_father->name, dst_father->name,
+ e_route_cnt);
+ xbt_assert(*latency >= 0.0,
+ "latency error on route between \"%s\" and \"%s\"",
+ src_father->name, dst_father->name);
+ }
+
+ void *link;
+ unsigned int cpt;
if (strcmp(src, e_route_cnt->src_gateway)) {
- e_route_src = _get_route(src, e_route_cnt->src_gateway);
- xbt_assert(e_route_src, "no route between \"%s\" and \"%s\"", src,
- e_route_cnt->src_gateway);
- xbt_dynar_foreach(e_route_src->generic_route.link_list, cpt, link) {
- xbt_dynar_push(e_route->generic_route.link_list, &link);
+ double latency_src;
+ xbt_dynar_t route_src;
+
+ _get_route_latency(src, e_route_cnt->src_gateway,
+ (route ? &route_src : NULL),
+ (latency ? &latency_src : NULL));
+ if (route) {
+ xbt_assert(route_src, "no route between \"%s\" and \"%s\"",
+ src, e_route_cnt->src_gateway);
+ xbt_dynar_foreach(route_src, cpt, link) {
+ xbt_dynar_push(*route, &link);
+ }
+ xbt_dynar_free(&route_src);
+ }
+ if (latency) {
+ xbt_assert(latency_src >= 0.0,
+ "latency error on route between \"%s\" and \"%s\"",
+ src, e_route_cnt->src_gateway);
+ *latency += latency_src;
}
}
- xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
- xbt_dynar_push(e_route->generic_route.link_list, &link);
+ if (route) {
+ xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
+ xbt_dynar_push(*route, &link);
+ }
}
if (strcmp(e_route_cnt->dst_gateway, dst)) {
- e_route_dst = _get_route(e_route_cnt->dst_gateway, dst);
- xbt_assert(e_route_dst, "no route between \"%s\" and \"%s\"",
- e_route_cnt->dst_gateway, dst);
- xbt_dynar_foreach(e_route_dst->generic_route.link_list, cpt, link) {
- xbt_dynar_push(e_route->generic_route.link_list, &link);
+ double latency_dst;
+ xbt_dynar_t route_dst;
+
+ _get_route_latency(e_route_cnt->dst_gateway, dst,
+ (route ? &route_dst : NULL),
+ (latency ? &latency_dst : NULL));
+ if (route) {
+ xbt_assert(route_dst, "no route between \"%s\" and \"%s\"",
+ e_route_cnt->dst_gateway, dst);
+ xbt_dynar_foreach(route_dst, cpt, link) {
+ xbt_dynar_push(*route, &link);
+ }
+ xbt_dynar_free(&route_dst);
+ }
+ if (latency) {
+ xbt_assert(latency_dst >= 0.0,
+ "latency error on route between \"%s\" and \"%s\"",
+ e_route_cnt->dst_gateway, dst);
+ *latency += latency_dst;
}
}
- e_route->src_gateway = xbt_strdup(e_route_cnt->src_gateway);
- e_route->dst_gateway = xbt_strdup(e_route_cnt->dst_gateway);
-
- generic_free_extended_route(e_route_src);
generic_free_extended_route(e_route_cnt);
- generic_free_extended_route(e_route_dst);
}
-
- xbt_dynar_free(&elem_father_list);
-
- return e_route;
}
-static double _get_latency(const char *src, const char *dst)
+/**
+ * \brief Generic function for get_route, get_route_no_cleanup, and get_latency
+ */
+static void get_route_latency(const char *src, const char *dst,
+ xbt_dynar_t *route, double *latency, int cleanup)
{
- double latency, latency_src, latency_dst = 0.0;
-
- XBT_DEBUG("Solve route \"%s\" to \"%s\"", src, dst);
- xbt_assert(src && dst, "bad parameters for \"_get_route\" method");
-
- route_extended_t e_route_cnt;
-
- xbt_dynar_t elem_father_list = elements_father(src, dst);
-
- routing_component_t common_father =
- xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
- routing_component_t src_father =
- xbt_dynar_get_as(elem_father_list, 1, routing_component_t);
- routing_component_t dst_father =
- xbt_dynar_get_as(elem_father_list, 2, routing_component_t);
-
- if (src_father == dst_father) { /* SURF_ROUTING_BASE */
-
- latency =
- (*(common_father->get_latency)) (common_father, src, dst, NULL);
- xbt_assert(latency>=0, "no route between \"%s\" and \"%s\"", src,
- dst);
-
- } else { /* SURF_ROUTING_RECURSIVE */
- route_extended_t e_route_bypass = NULL;
- if (common_father->get_bypass_route)
- e_route_bypass =
- (*(common_father->get_bypass_route)) (common_father, src, dst);
-
- xbt_assert(!e_route_bypass,"Bypass cannot work yet with get_latency");
-
- e_route_cnt =
- (*(common_father->get_route)) (common_father, src_father->name,
- dst_father->name);
-
- xbt_assert(e_route_cnt, "no route between \"%s\" and \"%s\"",
- src_father->name, dst_father->name);
-
- xbt_assert((e_route_cnt->src_gateway == NULL) ==
- (e_route_cnt->dst_gateway == NULL),
- "bad gateway for route between \"%s\" and \"%s\"", src,
- dst);
-
- latency = (*(common_father->get_latency)) (common_father, src_father->name, dst_father->name, e_route_cnt);
-
- xbt_assert(latency>=0, "no route between \"%s\" and \"%s\"",
- src_father->name, dst_father->name);
-
- if (strcmp(src,e_route_cnt->src_gateway)) {
-
- latency_src = _get_latency(src, e_route_cnt->src_gateway);
- xbt_assert(latency_src>=0, "no route between \"%s\" and \"%s\"", src,
- e_route_cnt->src_gateway);
- latency += latency_src;
- }
-
- if (strcmp(e_route_cnt->dst_gateway,dst)) {
-
- latency_dst = _get_latency(e_route_cnt->dst_gateway, dst);
- xbt_assert(latency_dst>=0, "no route between \"%s\" and \"%s\"",
- e_route_cnt->dst_gateway, dst);
- latency += latency_dst;
- }
-
+ _get_route_latency(src, dst, route, latency);
+ xbt_assert(!route || *route, "no route between \"%s\" and \"%s\"", src, dst);
+ xbt_assert(!latency || *latency >= 0.0,
+ "latency error on route between \"%s\" and \"%s\"", src, dst);
+ if (route) {
+ xbt_dynar_free(&global_routing->last_route);
+ global_routing->last_route = cleanup ? *route : NULL;
}
-
- xbt_dynar_free(&elem_father_list);
-
- return latency;
}
/**
*/
static xbt_dynar_t get_route(const char *src, const char *dst)
{
-
- route_extended_t e_route;
-
- e_route = _get_route(src, dst);
- xbt_assert(e_route, "no route between \"%s\" and \"%s\"", src, dst);
-
- if (global_routing->last_route)
- xbt_dynar_free(&(global_routing->last_route));
- global_routing->last_route = 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);
-
- return global_routing->last_route;
+ xbt_dynar_t route = NULL;
+ get_route_latency(src, dst, &route, NULL, 1);
+ return route;
}
/**
*/
static xbt_dynar_t get_route_no_cleanup(const char *src, const char *dst)
{
- xbt_dynar_t d = get_route(src,dst);
- global_routing->last_route = NULL;
- return d;
+ xbt_dynar_t route = NULL;
+ get_route_latency(src, dst, &route, NULL, 0);
+ return route;
}
/*Get Latency*/
static double get_latency(const char *src, const char *dst)
{
-
double latency = -1.0;
- latency = _get_latency(src, dst);
- xbt_assert(latency>=0.0, "no route between \"%s\" and \"%s\"", src, dst);
+ get_route_latency(src, dst, NULL, &latency, 0);
return latency;
}
global_routing->get_latency = get_latency;
global_routing->get_route_no_cleanup = get_route_no_cleanup;
global_routing->get_onelink_routes = get_onelink_routes;
+ global_routing->get_route_latency = get_route_latency;
global_routing->get_network_element_type = get_network_element_type;
global_routing->finalize = finalize;
global_routing->loopback = loopback;
