From 41323384c6bc36f5713cce594258110144d261ef Mon Sep 17 00:00:00 2001 From: Bart Polot Date: Mon, 14 Nov 2011 17:06:42 +0000 Subject: Real implementation for getting cost of a path compared to an existing tunnel tree (additional hops) --- src/mesh/gnunet-service-mesh.c | 11 +++----- src/mesh/mesh_tunnel_tree.c | 64 ++++++++++++++++++++++++++++++------------ src/mesh/mesh_tunnel_tree.h | 27 +++++++++--------- src/mesh/test_mesh_tree_api.c | 37 ++++++++++++++++++++++++ 4 files changed, 101 insertions(+), 38 deletions(-) (limited to 'src') diff --git a/src/mesh/gnunet-service-mesh.c b/src/mesh/gnunet-service-mesh.c index 14dd5d1fd..bcf6a400b 100644 --- a/src/mesh/gnunet-service-mesh.c +++ b/src/mesh/gnunet-service-mesh.c @@ -1477,7 +1477,7 @@ peer_info_remove_path (struct MeshPeerInfo *peer, GNUNET_PEER_Id p1, aux = NULL; for (p = peer_d->path_head; NULL != p; p = p->next) { - if ((cost = path_get_cost (peer->tunnels[i]->tree, p)) < best) + if ((cost = tree_get_path_cost (peer->tunnels[i]->tree, p)) < best) { best = cost; aux = p; @@ -1848,10 +1848,10 @@ tunnel_add_peer (struct MeshTunnel *t, struct MeshPeerInfo *peer) if (NULL != (p = peer->path_head)) { best_p = p; - best_cost = path_get_cost (t->tree, p); + best_cost = tree_get_path_cost (t->tree, p); while (NULL != p) { - if ((cost = path_get_cost (t->tree, p)) < best_cost) + if ((cost = tree_get_path_cost (t->tree, p)) < best_cost) { best_cost = cost; best_p = p; @@ -1865,7 +1865,7 @@ tunnel_add_peer (struct MeshTunnel *t, struct MeshPeerInfo *peer) } else { - /* Start a DHT get if necessary */ + /* Start a DHT get */ peer_info_connect (peer, t); } } @@ -3253,8 +3253,6 @@ dht_get_id_handler (void *cls, struct GNUNET_TIME_Absolute exp, GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MESH: Got results from DHT!\n"); GNUNET_PEER_resolve (path_info->peer->id, &pi); GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "MESH: for %s\n", GNUNET_i2s (&pi)); -// GNUNET_DHT_get_stop(path_info->peer->dhtget); -// path_info->peer->dhtget = NULL; p = path_build_from_dht (get_path, get_path_length, put_path, put_path_length); @@ -3264,7 +3262,6 @@ dht_get_id_handler (void *cls, struct GNUNET_TIME_Absolute exp, tunnel_add_peer (path_info->peer->tunnels[i], path_info->peer); peer_info_connect (path_info->peer, path_info->t); } -// GNUNET_free (path_info); return; } diff --git a/src/mesh/mesh_tunnel_tree.c b/src/mesh/mesh_tunnel_tree.c index b43fb2534..2b2e460b5 100644 --- a/src/mesh/mesh_tunnel_tree.c +++ b/src/mesh/mesh_tunnel_tree.c @@ -199,24 +199,6 @@ path_get_length (struct MeshPeerPath *path) } -/** - * Get the cost of the path relative to the already built tunnel tree - * - * @param t The tunnel tree to which compare - * @param path The individual path to reach a peer - * - * @return Number of hops to reach destination, UINT_MAX in case the peer is not - * in the path - * - * TODO: remove dummy implementation, look into the tunnel tree - */ -unsigned int -path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path) -{ - return path_get_length (path); -} - - /** * Destroy the path and free any allocated resources linked to it * @@ -989,6 +971,52 @@ tree_del_peer (struct MeshTunnelTree *t, GNUNET_PEER_Id peer, } + +/** + * Get the cost of the path relative to the already built tunnel tree. + * + * @param t The tunnel tree to which compare. + * @param path The individual path to reach a peer. It has to start at the + * root of the tree to be comparable. + * + * @return Number of hops to reach destination, UINT_MAX in case the peer is not + * in the path. + * + * TODO: adapt to allow any start / root combination + * TODO: take in account state of the nodes + */ +unsigned int +tree_get_path_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path) +{ + struct MeshTunnelTreeNode *n; + struct MeshTunnelTreeNode *p; + unsigned int i; + unsigned int l; + + l = path_get_length (path); + p = t->root; + if (t->root->peer != path->peers[0]) + { + GNUNET_break (0); + return UINT_MAX; + } + for (i = 1; i < l; i++) + { + for (n = p->children_head; NULL != n; n = n->next) + { + if (path->peers[i] == n->peer) + { + break; + } + } + if (NULL == n) + return l - i; + p = n; + } + return l - i; +} + + /** * Print the tree on stderr * diff --git a/src/mesh/mesh_tunnel_tree.h b/src/mesh/mesh_tunnel_tree.h index 5060fa1a7..dd31661ac 100644 --- a/src/mesh/mesh_tunnel_tree.h +++ b/src/mesh/mesh_tunnel_tree.h @@ -112,19 +112,6 @@ unsigned int path_get_length (struct MeshPeerPath *p); -/** - * Get the cost of the path relative to the already built tunnel tree - * - * @param t The tunnel tree to which compare - * @param path The individual path to reach a peer - * - * @return Number of hops to reach destination, UINT_MAX in case the peer is not - * in the path - */ -unsigned int -path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path); - - /** * Destroy the path and free any allocated resources linked to it * @@ -324,6 +311,20 @@ int tree_del_peer (struct MeshTunnelTree *t, GNUNET_PEER_Id peer, MeshTreeCallback cb, void *cbcls); + +/** + * Get the cost of the path relative to the already built tunnel tree + * + * @param t The tunnel tree to which compare + * @param path The individual path to reach a peer + * + * @return Number of hops to reach destination, UINT_MAX in case the peer is not + * in the path + */ +unsigned int +tree_get_path_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path); + + /** * Print the tree on stderr * diff --git a/src/mesh/test_mesh_tree_api.c b/src/mesh/test_mesh_tree_api.c index 77fd799bd..6ad5e9189 100644 --- a/src/mesh/test_mesh_tree_api.c +++ b/src/mesh/test_mesh_tree_api.c @@ -215,6 +215,43 @@ main (int argc, char *argv[]) test_assert (2, MESH_PEER_RELAY, 1, 0); test_assert (1, MESH_PEER_ROOT, 1, 0); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Calculating costs...\n"); + for (i = 1; i < 5; i++) + { + path->length = i; + if (tree_get_path_cost(tree, path) != 0) + { + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, + "test: length %u cost failed!\n", + i); + failed++; + } + } + path->length++; + path->peers[4] = 6; + if (tree_get_path_cost(tree, path) != 1) + { + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, + "test: length %u cost failed!\n", + i); + failed++; + } + path->peers[3] = 7; + if (tree_get_path_cost(tree, path) != 2) + { + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, + "test: length %u cost failed!\n", + i); + failed++; + } + path->length--; + if (tree_get_path_cost(tree, path) != 1) + { + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, + "test: length %u cost failed!\n", + i); + failed++; + } GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "test: Deleting third path (5)\n"); tree_set_status(tree, 5, MESH_PEER_READY); cb_call = 1; -- cgit v1.2.3