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  * If the peer toward which the new path is already in the tree, the peer
 474  * and its children will be maked as disconnected and the callback
 475  * will be called on each one of them. They will be maked as online only after
 476  * receiving a PATH ACK for the new path for each one of them, so the caller
 477  * should take care of sending a new CREATE PATH message for each disconnected
 478  * peer.
 479  *
 480  * @param t Tunnel where to add the new path.
 481  * @param p Path to be integrated.
 482  * @param cb Callback to use to notify about peers temporarily disconnecting
 483  *
 484  * @return GNUNET_OK in case of success.
 485  *         GNUNET_SYSERR in case of error.
 486  *
 487  * TODO: optimize
 488  * - go backwards on path looking for each peer in the present tree
 489  * - do not disconnect peers until new path is created & connected
 490  */
 491 int
 492 tree_add_path (struct MeshTunnelTree *t,
 493                const struct MeshPeerPath *p,
 494                MeshNodeDisconnectCB cb)
 495 {
 496   struct MeshTunnelTreeNode *parent;
 497   struct MeshTunnelTreeNode *oldnode;
 498   struct MeshTunnelTreeNode *n;
 499   struct MeshTunnelTreeNode *c;
 500   struct GNUNET_PeerIdentity id;
 501   struct GNUNET_PeerIdentity *hop;
 502   GNUNET_PEER_Id myid = t->me->peer;
 503   int me;
 504   unsigned int i;
 505
 506   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 507              "tree:   Adding path [%u] towards peer %u to peer %u.\n",
 508              p->length,
 509              p->peers[p->length - 1],
 510              t->me->peer);
 511   GNUNET_assert(0 != p->length);
 512   parent = n = t->root;
 513   if (n->peer != p->peers[0])
 514   {
 515     GNUNET_break (0);
 516     return GNUNET_SYSERR;
 517   }
 518   if (1 == p->length)
 519     return GNUNET_OK;
 520   oldnode = tree_del_path (t, p->peers[p->length - 1], cb);
 521   /* Look for the first node that is not already present in the tree
 522    *
 523    * Assuming that the tree is somewhat balanced, O(log n * log N).
 524    * - Length of the path is expected to be log N (size of whole network).
 525    * - Each level of the tree is expected to have log n children (size of tree).
 526    */
 527   me = t->root->peer == myid ? 0 : -1;
 528   for (i = 1; i < p->length; i++)
 529   {
 530     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 531              "tree:   Looking for peer %u.\n",
 532              p->peers[i]);
 533     parent = n;
 534     if (p->peers[i] == myid)
 535       me = i;
 536     for (c = n->children_head; NULL != c; c = c->next)
 537     {
 538       if (c->peer == p->peers[i])
 539       {
 540         GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 541              "tree:   Found in children of %u.\n",
 542              parent->peer);
 543         n = c;
 544         break;
 545       }
 546     }
 547     /*  If we couldn't find a child equal to path[i], we have reached the end
 548      * of the common path. */
 549     if (parent == n)
 550       break;
 551   }
 552   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 553              "tree:   All childen visited.\n");
 554   if (-1 == me)
 555   {
 556     /* New path deviates from tree before reaching us. What happened? */
 557     GNUNET_break (0);
 558     return GNUNET_SYSERR;
 559   }
 560   /* Add the rest of the path as a branch from parent. */
 561   while (i < p->length)
 562   {
 563     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 564                "tree:   Adding  peer %u, to %u.\n",
 565                p->peers[i],
 566                parent->peer);
 567
 568     if (i == p->length - 1 && NULL != oldnode)
 569     {
 570       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree:   Putting old node into place.\n");
 571       oldnode->parent = parent;
 572       GNUNET_CONTAINER_DLL_insert(parent->children_head,
 573                                   parent->children_tail,
 574                                   oldnode);
 575       tree_update_first_hops (t, oldnode, NULL);
 576       n = oldnode;
 577     }
 578     else
 579     {
 580       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree:   Creating new node.\n");
 581       n = tree_node_new(parent, p->peers[i]);
 582       n->t = t->t;
 583       n->status = MESH_PEER_RELAY;
 584     }
 585     i++;
 586     parent = n;
 587   }
 588   n->status = MESH_PEER_SEARCHING;
 589
 590   /* Add info about first hop into hashmap. */
 591   if (me < p->length - 1)
 592   {
 593     GNUNET_PEER_resolve (p->peers[p->length - 1], &id);
 594     hop = GNUNET_CONTAINER_multihashmap_get(t->first_hops, &id.hashPubKey);
 595     if (NULL != hop)
 596     {
 597       GNUNET_CONTAINER_multihashmap_remove_all(t->first_hops, &id.hashPubKey);
 598       GNUNET_free(hop);
 599     }
 600     hop = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
 601     GNUNET_PEER_resolve (p->peers[me + 1], hop);
 602     GNUNET_CONTAINER_multihashmap_put (t->first_hops, &id.hashPubKey,
 603                                        hop,
 604                                        GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 605   }
 606   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree:   New node added.\n");
 607   return GNUNET_OK;
 608 }
 609
 610
 611 /**
 612  * Notifies a tree that a connection it might be using is broken.
 613  * Marks all peers down the paths as disconnected and notifies the client.
 614  *
 615  * @param t Tree to use.
 616  * @param p1 Short id of one of the peers (order unimportant)
 617  * @param p2 Short id of one of the peers (order unimportant)
 618  * @param cb Function to call for every peer that is marked as disconnected.
 619  *
 620  * @return Short ID of the first disconnected peer in the tree.
 621  */
 622 GNUNET_PEER_Id
 623 tree_notify_connection_broken (struct MeshTunnelTree *t,
 624                                GNUNET_PEER_Id p1,
 625                                GNUNET_PEER_Id p2,
 626                                MeshNodeDisconnectCB cb)
 627 {
 628   struct MeshTunnelTreeNode *n;
 629   struct MeshTunnelTreeNode *c;
 630
 631   n = tree_find_peer(t->me, p1);
 632   if (NULL == n)
 633     return 0;
 634   if (NULL != n->parent && n->parent->peer == p2)
 635   {
 636     tree_mark_peers_disconnected(t, n, cb);
 637     GNUNET_CONTAINER_DLL_remove(n->parent->children_head,
 638                                 n->parent->children_tail,
 639                                 n);
 640     GNUNET_CONTAINER_DLL_insert(t->disconnected_head,
 641                                 t->disconnected_tail,
 642                                 n);
 643     return p1;
 644   }
 645   for (c = n->children_head; NULL != c; c = c->next)
 646   {
 647     if (c->peer == p2)
 648     {
 649       tree_mark_peers_disconnected(t, c, cb);
 650       GNUNET_CONTAINER_DLL_remove(n->children_head,
 651                                   n->children_tail,
 652                                   c);
 653       GNUNET_CONTAINER_DLL_insert(t->disconnected_head,
 654                                   t->disconnected_tail,
 655                                   c);
 656       return p2;
 657     }
 658   }
 659   return 0;
 660 }
 661
 662
 663 /**
 664  * Deletes a peer from a tunnel, marking its children as disconnected.
 665  *
 666  * @param t Tunnel tree to use.
 667  * @param peer Short ID of the peer to remove from the tunnel tree.
 668  * @param cb Callback to notify client of disconnected peers.
 669  *
 670  * @return GNUNET_OK or GNUNET_SYSERR
 671  */
 672 int
 673 tree_del_peer (struct MeshTunnelTree *t,
 674                GNUNET_PEER_Id peer,
 675                MeshNodeDisconnectCB cb)
 676 {
 677   struct MeshTunnelTreeNode *n;
 678   struct MeshTunnelTreeNode *c;
 679   struct MeshTunnelTreeNode *aux;
 680
 681   n = tree_del_path(t, peer, cb);
 682   c = n->children_head;
 683   while (NULL != c)
 684   {
 685     aux = c->next;
 686     GNUNET_CONTAINER_DLL_remove(n->children_head,
 687                                 n->children_tail,
 688                                 c);
 689     GNUNET_CONTAINER_DLL_insert(t->disconnected_head,
 690                                 t->disconnected_tail,
 691                                 c);
 692     cb (c);
 693     c = aux;
 694   }
 695   tree_node_destroy(n);
 696   return GNUNET_OK;
 697 }
 698
 699
 700 /**
 701  * Print the tree on stderr
 702  *
 703  * @param t The tree
 704  */
 705 void
 706 tree_debug(struct MeshTunnelTree *t)
 707 {
 708   tree_node_debug(t->root, 0);
 709 }
 710
 711
 712 /**
 713  * Iterator over hash map peer entries and frees all data in it.
 714  * Used prior to destroying a hashmap. Makes you miss anonymous functions in C.
 715  *
 716  * @param cls closure
 717  * @param key current key code (will no longer contain valid data!!)
 718  * @param value value in the hash map (treated as void *)
 719  * @return GNUNET_YES if we should continue to iterate, GNUNET_NO if not.
 720  */
 721 static int
 722 iterate_free (void *cls, const GNUNET_HashCode * key, void *value)
 723 {
 724   GNUNET_free(value);
 725   return GNUNET_YES;
 726 }
 727
 728
 729 /**
 730  * Destroy the whole tree and free all used memory and Peer_Ids
 731  *
 732  * @param t Tree to be destroyed
 733  */
 734 void
 735 tree_destroy (struct MeshTunnelTree *t)
 736 {
 737   tree_node_destroy(t->root);
 738   GNUNET_CONTAINER_multihashmap_iterate(t->first_hops, &iterate_free, NULL);
 739   GNUNET_CONTAINER_multihashmap_destroy(t->first_hops);
 740   GNUNET_free(t);
 741 }