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