X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/eae159a7a056450dfec373f559f38ea0b942d158..3e6c7cad2fecb20fc9e694e63cd915f097bf2b99:/src/surf/surf_routing.c

diff --git a/src/surf/surf_routing.c b/src/surf/surf_routing.c
index 0a1c209282..50504869e5 100644
--- a/src/surf/surf_routing.c
+++ b/src/surf/surf_routing.c
@@ -582,11 +582,12 @@ static void elements_father(const char *src, const char *dst,
                             routing_component_t *res_dst)
 {
   xbt_assert(src && dst, "bad parameters for \"elements_father\" method");
-
+#define ELEMENTS_FATHER_MAXDEPTH 16 /* increase if it is not enough */
   routing_component_t src_as, dst_as;
-  int index_src, index_dst;
-  xbt_dynar_t path_src;
-  xbt_dynar_t path_dst;
+  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;
@@ -608,200 +609,170 @@ static void elements_father(const char *src, const char *dst,
              "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);
-  for (current = src_as ; current != NULL ; current = current->routing_father)
-    xbt_dynar_push_as(path_src, routing_component_t, current);
-  path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
-  for (current = dst_as ; current != NULL ; current = current->routing_father)
-    xbt_dynar_push_as(path_dst, routing_component_t, current);
+  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");
+  }
+  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 = xbt_dynar_length(path_src) - 1;
-  index_dst = xbt_dynar_length(path_dst) - 1;
-  current_src = xbt_dynar_get_as(path_src, index_src, routing_component_t);
-  current_dst = xbt_dynar_get_as(path_dst, index_dst, routing_component_t);
-  while (index_src > 0 && index_dst > 0 && current_src == current_dst) {
-    index_src--;
-    index_dst--;
-    current_src = xbt_dynar_get_as(path_src, index_src, routing_component_t);
-    current_dst = xbt_dynar_get_as(path_dst, index_dst, routing_component_t);
-  }
+  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 */
   if (current_src == current_dst)
     father = current_src;
   else
-    father = xbt_dynar_get_as(path_src, index_src + 1, routing_component_t);
+    father = path_src[index_src + 1];
 
   /* (5) result generation */
   *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 */
 
-  xbt_dynar_free(&path_src);
-  xbt_dynar_free(&path_dst);
+#undef ELEMENTS_FATHER_MAXDEPTH
 }
 
 /* Global Business methods */
 
 /**
- * \brief Recursive function for get_route
+ * \brief Recursive function for get_route and get_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 void _get_route(const char *src, const char *dst,route_extended_t *e_route)
+static void _get_route_latency(const char *src, const char *dst,
+                               xbt_dynar_t *route, double *latency)
 {
-  XBT_DEBUG("Solve route  \"%s\" to \"%s\"", src, dst);
-  xbt_assert(src && dst, "bad parameters for \"_get_route\" method");
+  XBT_DEBUG("Solve route/latency  \"%s\" to \"%s\"", src, dst);
+  xbt_assert(src && dst, "bad parameters for \"_get_route_latency\" method");
 
   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);
 
-  if (src_father == dst_father) {       /* SURF_ROUTING_BASE */
+  if (src_father == dst_father) { /* SURF_ROUTING_BASE */
 
-	(*e_route) =
-	  (*(common_father->get_route)) (common_father, src, dst);
-	xbt_assert((*e_route), "no route between \"%s\" and \"%s\"", src,
-			  dst);
+    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 */
 
-	void *link;
-	unsigned int cpt = 0;
-
-	route_extended_t e_route_cnt = NULL;
-	route_extended_t e_route_src = NULL;
-	route_extended_t e_route_dst = NULL;
     route_extended_t e_route_bypass = NULL;
-
-    (*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 (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)) {
-      _get_route(src, e_route_cnt->src_gateway, &e_route_src);
-      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)) {
-      _get_route(e_route_cnt->dst_gateway, dst, &e_route_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);
-  }
-}
-
-static double _get_latency(const char *src, const char *dst)
-{
-  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;
-
-  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);
-
-  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;
-    }
-	
   }
-
-  return latency;
 }
 
 /**
@@ -817,23 +788,15 @@ static double _get_latency(const char *src, const char *dst)
 static xbt_dynar_t get_route(const char *src, const char *dst)
 {
 
-  route_extended_t e_route = NULL;
-
-  _get_route(src, dst, &e_route);
-  xbt_assert(e_route, "no route between \"%s\" and \"%s\"", src, dst);
+  xbt_dynar_t route = NULL;
 
-  if (global_routing->last_route)
-    xbt_dynar_free(&(global_routing->last_route));
-  global_routing->last_route = e_route->generic_route.link_list;
+  _get_route_latency(src, dst, &route, NULL);
+  xbt_assert(route, "no route between \"%s\" and \"%s\"", src, dst);
 
-  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);
+  xbt_dynar_free(&global_routing->last_route);
+  global_routing->last_route = route;
 
-  return global_routing->last_route;
+  return route;
 }
 
 /**
@@ -858,7 +821,7 @@ static double get_latency(const char *src, const char *dst)
 {
 
   double latency = -1.0;
-  latency = _get_latency(src, dst);
+  _get_route_latency(src, dst, NULL, &latency);
   xbt_assert(latency>=0.0, "no route between \"%s\" and \"%s\"", src, dst);
   return latency;
 }