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