src/mesh/mesh_tunnel_tree.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001 - 2011 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file mesh/mesh_tunnel_tree.c
  23  * @brief Tunnel tree handling functions
  24  * @author Bartlomiej Polot
  25  */
  26
  27 #include "mesh.h"
  28 #include "mesh_tunnel_tree.h"
  29
  30
  31 /**
  32  * Create a new path
  33  *
  34  * @param lenght How many hops will the path have.
  35  *
  36  * @return A newly allocated path with a peer array of the specified length.
  37  */
  38 struct MeshPeerPath *
  39 path_new (unsigned int length)
  40 {
  41   struct MeshPeerPath *p;
  42
  43   p = GNUNET_malloc (sizeof(struct MeshPeerPath));
  44   if (length > 0)
  45   {
  46     p->length = length;
  47     p->peers = GNUNET_malloc (length * sizeof(GNUNET_PEER_Id));
  48   }
  49   return p;
  50 }
  51
  52
  53 /**
  54  * Invert the path
  55  *
  56  * @param p the path to invert
  57  */
  58 void
  59 path_invert (struct MeshPeerPath *path)
  60 {
  61   GNUNET_PEER_Id aux;
  62   unsigned int i;
  63
  64   for (i = 0; i < path->length / 2; i++)
  65   {
  66     aux = path->peers[i];
  67     path->peers[i] = path->peers[path->length - i - 1];
  68     path->peers[path->length - i - 1] = aux;
  69   }
  70 }
  71
  72
  73
  74 /**
  75  * Find the first peer whom to send a packet to go down this path
  76  *
  77  * @param t The tunnel tree to use
  78  * @param peer The peerinfo of the peer we are trying to reach
  79  *
  80  * @return peerinfo of the peer who is the first hop in the tunnel
  81  *         NULL on error
  82  */
  83 struct GNUNET_PeerIdentity *
  84 path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
  85 {
  86   struct GNUNET_PeerIdentity id;
  87
  88   GNUNET_PEER_resolve (peer, &id);
  89   return GNUNET_CONTAINER_multihashmap_get (t->first_hops,
  90                                             &id.hashPubKey);
  91 }
  92
  93
  94 /**
  95  * Get the length of a path
  96  *
  97  * @param path The path to measure, with the local peer at any point of it
  98  *
  99  * @return Number of hops to reach destination
 100  *         UINT_MAX in case the peer is not in the path
 101  */
 102 unsigned int
 103 path_get_length (struct MeshPeerPath *path)
 104 {
 105   if (NULL == path)
 106     return UINT_MAX;
 107   return path->length;
 108 }
 109
 110
 111 /**
 112  * Get the cost of the path relative to the already built tunnel tree
 113  *
 114  * @param t The tunnel tree to which compare
 115  * @param path The individual path to reach a peer
 116  *
 117  * @return Number of hops to reach destination, UINT_MAX in case the peer is not
 118  * in the path
 119  *
 120  * TODO: remove dummy implementation, look into the tunnel tree
 121  */
 122 unsigned int
 123 path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path)
 124 {
 125   return path_get_length (path);
 126 }
 127
 128
 129 /**
 130  * Destroy the path and free any allocated resources linked to it
 131  *
 132  * @param p the path to destroy
 133  *
 134  * @return GNUNET_OK on success
 135  */
 136 int
 137 path_destroy (struct MeshPeerPath *p)
 138 {
 139   GNUNET_PEER_decrement_rcs (p->peers, p->length);
 140   GNUNET_free (p->peers);
 141   GNUNET_free (p);
 142   return GNUNET_OK;
 143 }
 144
 145
 146
 147 /**
 148  * Allocates and initializes a new node.
 149  * Sets ID and parent of the new node and inserts it in the DLL of the parent
 150  *
 151  * @param parent Node that will be the parent from the new node, NULL for root
 152  * @param peer Short Id of the new node
 153  *
 154  * @return Newly allocated node
 155  */
 156 static struct MeshTunnelTreeNode *
 157 tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer)
 158 {
 159   struct MeshTunnelTreeNode *node;
 160
 161   node = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode));
 162   node->peer = peer;
 163   GNUNET_PEER_change_rc(peer, 1);
 164   node->parent = parent;
 165   if (NULL != parent)
 166     GNUNET_CONTAINER_DLL_insert(parent->children_head,
 167                                 parent->children_tail,
 168                                 node);
 169
 170   return node;
 171 }
 172
 173
 174 static void
 175 tree_node_debug(struct MeshTunnelTreeNode *n, uint16_t level)
 176 {
 177   struct MeshTunnelTreeNode *c;
 178   uint16_t i;
 179
 180   for (i = 0; i < level; i++)
 181     fprintf(stderr, "  ");
 182   if (n->status == MESH_PEER_READY)
 183     fprintf(stderr, "#");
 184   if (n->status == MESH_PEER_SEARCHING)
 185     fprintf(stderr, "+");
 186   if (n->status == MESH_PEER_RELAY)
 187     fprintf(stderr, "-");
 188   if (n->status == MESH_PEER_RECONNECTING)
 189     fprintf(stderr, "*");
 190
 191   fprintf(stderr, "%u [%p] ", n->peer, n);
 192   if (NULL != n->parent)
 193     fprintf(stderr, "(-> %u)\n", n->parent->peer);
 194   else
 195     fprintf(stderr, "(root)\n");
 196   for (c = n->children_head; NULL != c; c = c->next)
 197     tree_node_debug(c, level + 1);
 198 }
 199
 200
 201 /**
 202  * Destroys and frees the node and all children
 203  *
 204  * @param n Parent node to be destroyed
 205  */
 206 static void
 207 tree_node_destroy (struct MeshTunnelTreeNode *parent)
 208 {
 209   struct MeshTunnelTreeNode *n;
 210   struct MeshTunnelTreeNode *next;
 211
 212   n = parent->children_head;
 213   while (NULL != n)
 214   {
 215     next = n->next;
 216     tree_node_destroy(n);
 217     n = next;
 218   }
 219   GNUNET_PEER_change_rc(parent->peer, -1);
 220   if (NULL != parent->parent)
 221     GNUNET_CONTAINER_DLL_remove(parent->parent->children_head,
 222                                 parent->parent->children_tail,
 223                                 parent);
 224   GNUNET_free(parent);
 225 }
 226
 227
 228
 229 /**
 230  * Create a new tunnel tree associated to a tunnel
 231  *
 232  * @param t Tunnel this tree will represent
 233  * @param peer A short peer id of the root of the tree
 234  *
 235  * @return A newly allocated and initialized tunnel tree
 236  */
 237 struct MeshTunnelTree *
 238 tree_new (struct MeshTunnel *t, GNUNET_PEER_Id peer)
 239 {
 240   struct MeshTunnelTree *tree;
 241
 242   tree = GNUNET_malloc(sizeof (struct MeshTunnelTree));
 243   tree->first_hops = GNUNET_CONTAINER_multihashmap_create(32);
 244   tree->root = tree_node_new(NULL, peer);
 245   tree->t = t;
 246   tree->root->t = t;
 247
 248   return tree;
 249 }
 250
 251
 252 /**
 253  * Recursively find the given peer in the tree.
 254  *
 255  * @param t Tunnel where to look for the peer.
 256  * @param peer Peer to find
 257  *
 258  * @return Pointer to the node of the peer. NULL if not found.
 259  */
 260 struct MeshTunnelTreeNode *
 261 tree_find_peer (struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer_id)
 262 {
 263   struct MeshTunnelTreeNode *n;
 264   struct MeshTunnelTreeNode *r;
 265
 266   if (parent->peer == peer_id)
 267     return parent;
 268   for (n = parent->children_head; NULL != n; n = n->next)
 269   {
 270     r = tree_find_peer (n, peer_id);
 271     if (NULL != r)
 272       return r;
 273   }
 274   return NULL;
 275 }
 276
 277
 278 /**
 279  * Recusively mark peer and children as disconnected, notify client
 280  *
 281  * @param tree Tree this node belongs to
 282  * @param parent Node to be clean, potentially with children
 283  * @param cb Callback to use to notify about disconnected peers.
 284  */
 285 static void
 286 tree_mark_peers_disconnected (struct MeshTunnelTree *tree,
 287                               struct MeshTunnelTreeNode *parent,
 288                               MeshNodeDisconnectCB cb)
 289 {
 290   struct GNUNET_PeerIdentity *pi;
 291   struct GNUNET_PeerIdentity id;
 292   struct MeshTunnelTreeNode *n;
 293
 294   for (n = parent->children_head; NULL != n; n = n->next)
 295   {
 296     tree_mark_peers_disconnected (tree, n, cb);
 297   }
 298   if (MESH_PEER_READY == parent->status)
 299   {
 300     cb (parent);
 301   }
 302   parent->status = MESH_PEER_RECONNECTING;
 303
 304   /* Remove and free info about first hop */
 305   GNUNET_PEER_resolve(parent->peer, &id);
 306   pi = GNUNET_CONTAINER_multihashmap_get(tree->first_hops, &id.hashPubKey);
 307   GNUNET_CONTAINER_multihashmap_remove_all(tree->first_hops, &id.hashPubKey);
 308   if (NULL != pi)
 309     GNUNET_free(pi);
 310 }
 311
 312
 313 /**
 314  * Recusively update the info about what is the first hop to reach the node
 315  *
 316  * @param tree Tree this nodes belongs to
 317  * @param parent Node to be start updating
 318  * @param hop If known, ID of the first hop.
 319  *            If not known, NULL to find out and pass on children.
 320  */
 321 static void
 322 tree_update_first_hops (struct MeshTunnelTree *tree,
 323                         struct MeshTunnelTreeNode *parent,
 324                         struct GNUNET_PeerIdentity *hop)
 325 {
 326   struct GNUNET_PeerIdentity pi;
 327   struct GNUNET_PeerIdentity *copy;
 328   struct GNUNET_PeerIdentity id;
 329   struct MeshTunnelTreeNode *n;
 330
 331   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 332              "tree:   Finding first hop for %u.\n",
 333              parent->peer);
 334   if (NULL == hop)
 335   {
 336     struct MeshTunnelTreeNode *aux;
 337     struct MeshTunnelTreeNode *old;
 338
 339     old = parent;
 340     aux = old->parent;
 341     while (aux != tree->me)
 342     {
 343       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 344              "tree:   ... its not %u.\n",
 345              old->peer);
 346       old = aux;
 347       aux = aux->parent;
 348       GNUNET_assert(NULL != aux);
 349     }
 350     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 351              "tree:   It's %u!!\n",
 352              old->peer);
 353     hop = &pi;
 354     GNUNET_PEER_resolve(old->peer, hop);
 355   }
 356   copy = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
 357   *copy = *hop;
 358   GNUNET_PEER_resolve(parent->peer, &id);
 359   GNUNET_CONTAINER_multihashmap_put(tree->first_hops, &id.hashPubKey, copy,
 360                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 361
 362   for (n = parent->children_head; NULL != n; n = n->next)
 363   {
 364     tree_update_first_hops (tree, n, hop);
 365   }
 366 }
 367
 368
 369 /**
 370  * Delete the current path to the peer, including all now unused relays.
 371  * The destination peer is NOT destroyed, it is returned in order to either set
 372  * a new path to it or destroy it explicitly, taking care of it's child nodes.
 373  *
 374  * @param t Tunnel tree where to delete the path from.
 375  * @param peer Destination peer whose path we want to remove.
 376  * @param cb Callback to use to notify about disconnected peers.
 377  *
 378  * @return pointer to the pathless node.
 379  *         NULL when not found
 380  */
 381 struct MeshTunnelTreeNode *
 382 tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id,
 383                  MeshNodeDisconnectCB cb)
 384 {
 385   struct MeshTunnelTreeNode *parent;
 386   struct MeshTunnelTreeNode *node;
 387   struct MeshTunnelTreeNode *n;
 388
 389   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 390              "tree:   Deleting path to %u.\n", peer_id);
 391   if (peer_id == t->root->peer)
 392     return NULL;
 393
 394   for (n = t->disconnected_head; NULL != n; n = n->next)
 395   {
 396     if (n->peer == peer_id)
 397     {
 398       /* Was already pathless, waiting for reconnection */
 399       GNUNET_CONTAINER_DLL_remove (t->disconnected_head,
 400                                    t->disconnected_tail,
 401                                    n);
 402       return n;
 403     }
 404   }
 405   n = tree_find_peer (t->me, peer_id);
 406   if (NULL == n)
 407     return NULL;
 408   node = n;
 409
 410   parent = n->parent;
 411   GNUNET_CONTAINER_DLL_remove(parent->children_head, parent->children_tail, n);
 412   n->parent = NULL;
 413
 414   while (t->root != parent && MESH_PEER_RELAY == parent->status &&
 415          NULL == parent->children_head)
 416   {
 417     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 418                "tree:   Deleting node %u.\n",
 419                parent->peer);
 420     n = parent->parent;
 421     tree_node_destroy(parent);
 422     parent = n;
 423   }
 424   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 425              "tree:   Not deleted peer %u.\n",
 426              parent->peer);
 427
 428   tree_mark_peers_disconnected (t, node, cb);
 429
 430   return node;
 431 }
 432
 433
 434 /**
 435  * Return a newly allocated individual path to reach a peer from the local peer,
 436  * according to the path tree of some tunnel.
 437  *
 438  * @param t Tunnel from which to read the path tree
 439  * @param peer_info Destination peer to whom we want a path
 440  *
 441  * @return A newly allocated individual path to reach the destination peer.
 442  *         Path must be destroyed afterwards.
 443  */
 444 struct MeshPeerPath *
 445 tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer)
 446 {
 447   struct MeshTunnelTreeNode *n;
 448   struct MeshPeerPath *p;
 449   GNUNET_PEER_Id myid = t->me->peer;
 450
 451   n = tree_find_peer(t->me, peer);
 452   p = path_new(0);
 453
 454   /* Building the path (inverted!) */
 455   while (n->peer != myid)
 456   {
 457     GNUNET_array_append(p->peers, p->length, n->peer);
 458     GNUNET_PEER_change_rc(n->peer, 1);
 459     n = n->parent;
 460     GNUNET_assert(NULL != n);
 461   }
 462   GNUNET_array_append(p->peers, p->length, myid);
 463   GNUNET_PEER_change_rc(myid, 1);
 464
 465   path_invert(p);
 466
 467   return p;
 468 }
 469
 470
 471 /**
 472  * Integrate a stand alone path into the tunnel tree.
 473  *
 474  * @param t Tunnel where to add the new path.
 475  * @param p Path to be integrated.
 476  * @param cb Callback to use to notify about peers temporarily disconnecting
 477  *
 478  * @return GNUNET_OK in case of success.
 479  *         GNUNET_SYSERR in case of error.
 480  *
 481  * TODO: optimize
 482  * - go backwards on path looking for each peer in the present tree
 483  * - do not disconnect peers until new path is created & connected
 484  */
 485 int
 486 tree_add_path (struct MeshTunnelTree *t,
 487                const struct MeshPeerPath *p,
 488                MeshNodeDisconnectCB cb)
 489 {
 490   struct MeshTunnelTreeNode *parent;
 491   struct MeshTunnelTreeNode *oldnode;
 492   struct MeshTunnelTreeNode *n;
 493   struct MeshTunnelTreeNode *c;
 494   struct GNUNET_PeerIdentity id;
 495   struct GNUNET_PeerIdentity *hop;
 496   GNUNET_PEER_Id myid = t->me->peer;
 497   int me;
 498   unsigned int i;
 499
 500   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 501              "tree:   Adding path [%u] towards peer %u to peer %u.\n",
 502              p->length,
 503              p->peers[p->length - 1],
 504              t->me->peer);
 505   GNUNET_assert(0 != p->length);
 506   parent = n = t->root;
 507   if (n->peer != p->peers[0])
 508   {
 509     GNUNET_break (0);
 510     return GNUNET_SYSERR;
 511   }
 512   if (1 == p->length)
 513     return GNUNET_OK;
 514   oldnode = tree_del_path (t, p->peers[p->length - 1], cb);
 515   /* Look for the first node that is not already present in the tree
 516    *
 517    * Assuming that the tree is somewhat balanced, O(log n * log N).
 518    * - Length of the path is expected to be log N (size of whole network).
 519    * - Each level of the tree is expected to have log n children (size of tree).
 520    */
 521   me = t->root->peer == myid ? 0 : -1;
 522   for (i = 1; i < p->length; i++)
 523   {
 524     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 525              "tree:   Looking for peer %u.\n",
 526              p->peers[i]);
 527     parent = n;
 528     if (p->peers[i] == myid)
 529       me = i;
 530     for (c = n->children_head; NULL != c; c = c->next)
 531     {
 532       if (c->peer == p->peers[i])
 533       {
 534         GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 535              "tree:   Found in children of %u.\n",
 536              parent->peer);
 537         n = c;
 538         break;
 539       }
 540     }
 541     /*  If we couldn't find a child equal to path[i], we have reached the end
 542      * of the common path. */
 543     if (parent == n)
 544       break;
 545   }
 546   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 547              "tree:   All childen visited.\n");
 548   if (-1 == me)
 549   {
 550     /* New path deviates from tree before reaching us. What happened? */
 551     GNUNET_break (0);
 552     return GNUNET_SYSERR;
 553   }
 554   /* Add the rest of the path as a branch from parent. */
 555   while (i < p->length)
 556   {
 557     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 558                "tree:   Adding  peer %u, to %u.\n",
 559                p->peers[i],
 560                parent->peer);
 561
 562     if (i == p->length - 1 && NULL != oldnode)
 563     {
 564       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree:   Putting old node into place.\n");
 565       oldnode->parent = parent;
 566       GNUNET_CONTAINER_DLL_insert(parent->children_head,
 567                                   parent->children_tail,
 568                                   oldnode);
 569       tree_update_first_hops (t, oldnode, NULL);
 570       n = oldnode;
 571     }
 572     else
 573     {
 574       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree:   Creating new node.\n");
 575       n = tree_node_new(parent, p->peers[i]);
 576       n->t = t->t;
 577       n->status = MESH_PEER_RELAY;
 578     }
 579     i++;
 580     parent = n;
 581   }
 582   n->status = MESH_PEER_SEARCHING;
 583
 584   /* Add info about first hop into hashmap. */
 585   if (me < p->length - 1)
 586   {
 587     GNUNET_PEER_resolve (p->peers[p->length - 1], &id);
 588     hop = GNUNET_CONTAINER_multihashmap_get(t->first_hops, &id.hashPubKey);
 589     if (NULL != hop)
 590     {
 591       GNUNET_CONTAINER_multihashmap_remove_all(t->first_hops, &id.hashPubKey);
 592       GNUNET_free(hop);
 593     }
 594     hop = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
 595     GNUNET_PEER_resolve (p->peers[me + 1], hop);
 596     GNUNET_CONTAINER_multihashmap_put (t->first_hops, &id.hashPubKey,
 597                                        hop,
 598                                        GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 599   }
 600   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree:   New node added.\n");
 601   return GNUNET_OK;
 602 }
 603
 604
 605 /**
 606  * Notifies a tree that a connection it might be using is broken.
 607  * Marks all peers down the paths as disconnected and notifies the client.
 608  *
 609  * @param t Tree to use.
 610  * @param p1 Short id of one of the peers (order unimportant)
 611  * @param p2 Short id of one of the peers (order unimportant)
 612  * @param cb Function to call for every peer that is marked as disconnected.
 613  *
 614  * @return Short ID of the first disconnected peer in the tree.
 615  */
 616 GNUNET_PEER_Id
 617 tree_notify_connection_broken (struct MeshTunnelTree *t,
 618                                GNUNET_PEER_Id p1,
 619                                GNUNET_PEER_Id p2,
 620                                MeshNodeDisconnectCB cb)
 621 {
 622   struct MeshTunnelTreeNode *n;
 623   struct MeshTunnelTreeNode *c;
 624
 625   n = tree_find_peer(t->me, p1);
 626   if (NULL == n)
 627     return 0;
 628   if (NULL != n->parent && n->parent->peer == p2)
 629   {
 630     tree_mark_peers_disconnected(t, n, cb);
 631     GNUNET_CONTAINER_DLL_remove(n->parent->children_head,
 632                                 n->parent->children_tail,
 633                                 n);
 634     GNUNET_CONTAINER_DLL_insert(t->disconnected_head,
 635                                 t->disconnected_tail,
 636                                 n);
 637     return p1;
 638   }
 639   for (c = n->children_head; NULL != c; c = c->next)
 640   {
 641     if (c->peer == p2)
 642     {
 643       tree_mark_peers_disconnected(t, c, cb);
 644       GNUNET_CONTAINER_DLL_remove(n->children_head,
 645                                   n->children_tail,
 646                                   c);
 647       GNUNET_CONTAINER_DLL_insert(t->disconnected_head,
 648                                   t->disconnected_tail,
 649                                   c);
 650       return p2;
 651     }
 652   }
 653   return 0;
 654 }
 655
 656
 657 /**
 658  * Deletes a peer from a tunnel, marking its children as disconnected.
 659  *
 660  * @param t Tunnel tree to use.
 661  * @param peer Short ID of the peer to remove from the tunnel tree.
 662  * @param cb Callback to notify client of disconnected peers.
 663  *
 664  * @return GNUNET_OK or GNUNET_SYSERR
 665  */
 666 int
 667 tree_del_peer (struct MeshTunnelTree *t,
 668                GNUNET_PEER_Id peer,
 669                MeshNodeDisconnectCB cb)
 670 {
 671   struct MeshTunnelTreeNode *n;
 672   struct MeshTunnelTreeNode *c;
 673   struct MeshTunnelTreeNode *aux;
 674
 675   n = tree_del_path(t, peer, cb);
 676   c = n->children_head;
 677   while (NULL != c)
 678   {
 679     aux = c->next;
 680     GNUNET_CONTAINER_DLL_remove(n->children_head,
 681                                 n->children_tail,
 682                                 c);
 683     GNUNET_CONTAINER_DLL_insert(t->disconnected_head,
 684                                 t->disconnected_tail,
 685                                 c);
 686     cb (c);
 687     c = aux;
 688   }
 689   tree_node_destroy(n);
 690   return GNUNET_OK;
 691 }
 692
 693
 694 /**
 695  * Print the tree on stderr
 696  *
 697  * @param t The tree
 698  */
 699 void
 700 tree_debug(struct MeshTunnelTree *t)
 701 {
 702   tree_node_debug(t->root, 0);
 703 }
 704
 705
 706 /**
 707  * Iterator over hash map peer entries and frees all data in it.
 708  * Used prior to destroying a hashmap. Makes you miss anonymous functions in C.
 709  *
 710  * @param cls closure
 711  * @param key current key code (will no longer contain valid data!!)
 712  * @param value value in the hash map (treated as void *)
 713  * @return GNUNET_YES if we should continue to iterate, GNUNET_NO if not.
 714  */
 715 static int
 716 iterate_free (void *cls, const GNUNET_HashCode * key, void *value)
 717 {
 718   GNUNET_free(value);
 719   return GNUNET_YES;
 720 }
 721
 722
 723 /**
 724  * Destroy the whole tree and free all used memory and Peer_Ids
 725  *
 726  * @param t Tree to be destroyed
 727  */
 728 void
 729 tree_destroy (struct MeshTunnelTree *t)
 730 {
 731   tree_node_destroy(t->root);
 732   GNUNET_CONTAINER_multihashmap_iterate(t->first_hops, &iterate_free, NULL);
 733   GNUNET_CONTAINER_multihashmap_destroy(t->first_hops);
 734   GNUNET_free(t);
 735 }