path: root/src/mesh/mesh_tunnel_tree.c

/*
     This file is part of GNUnet.
     (C) 2001 - 2011 Christian Grothoff (and other contributing authors)

     GNUnet is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published
     by the Free Software Foundation; either version 3, or (at your
     option) any later version.

     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with GNUnet; see the file COPYING.  If not, write to the
     Free Software Foundation, Inc., 59 Temple Place - Suite 330,
     Boston, MA 02111-1307, USA.
*/

/**
 * @file mesh/mesh_tunnel_tree.c
 * @brief Tunnel tree handling functions
 * @author Bartlomiej Polot
 */

#include "mesh.h"
#include "mesh_tunnel_tree.h"

#define MESH_TREE_DEBUG GNUNET_YES


/**
 * Node of path tree for a tunnel
 */
struct MeshTunnelTreeNode
{
  /**
   * Peer this node describes
   */
  GNUNET_PEER_Id peer;

  /**
   * Parent node in the tree
   */
  struct MeshTunnelTreeNode *parent;

  /**
   * DLL of siblings
   */
  struct MeshTunnelTreeNode *next;

  /**
   * DLL of siblings
   */
  struct MeshTunnelTreeNode *prev;

  /**
   * DLL of children
   */
  struct MeshTunnelTreeNode *children_head;

  /**
   * DLL of children
   */
  struct MeshTunnelTreeNode *children_tail;

    /**
     * Status of the peer in the tunnel
     */
  enum MeshPeerState status;
};


/**
 * Tree to reach all peers in the tunnel
 */
struct MeshTunnelTree
{
  /**
   * Root node of peer tree
   */
  struct MeshTunnelTreeNode *root;

  /**
   * Node that represents our position in the tree (for non local tunnels)
   */
  struct MeshTunnelTreeNode *me;

  /**
   * DLL of disconneted nodes
   */
  struct MeshTunnelTreeNode *disconnected_head;

  /**
   * DLL of disconneted nodes
   */
  struct MeshTunnelTreeNode *disconnected_tail;

  /**
   * Cache of all peers and the first hop to them.
   * Indexed by PeerIdentity, contains a pointer to the PeerIdentity
   * of 1st hop.
   */
  struct GNUNET_CONTAINER_MultiHashMap *first_hops;

};


/**
 * Create a new path
 *
 * @param length How many hops will the path have.
 *
 * @return A newly allocated path with a peer array of the specified length.
 */
struct MeshPeerPath *
path_new (unsigned int length)
{
  struct MeshPeerPath *p;

  p = GNUNET_malloc (sizeof (struct MeshPeerPath));
  if (length > 0)
  {
    p->length = length;
    p->peers = GNUNET_malloc (length * sizeof (GNUNET_PEER_Id));
  }
  return p;
}


/**
 * Invert the path
 *
 * @param path the path to invert
 */
void
path_invert (struct MeshPeerPath *path)
{
  GNUNET_PEER_Id aux;
  unsigned int i;

  for (i = 0; i < path->length / 2; i++)
  {
    aux = path->peers[i];
    path->peers[i] = path->peers[path->length - i - 1];
    path->peers[path->length - i - 1] = aux;
  }
}


/**
 * Duplicate a path, incrementing short peer's rc.
 *
 * @param path The path to duplicate.
 */
struct MeshPeerPath *
path_duplicate (struct MeshPeerPath *path)
{
  struct MeshPeerPath *aux;
  unsigned int i;

  aux = path_new (path->length);
  memcpy (aux->peers, path->peers, path->length * sizeof (GNUNET_PEER_Id));
  for (i = 0; i < path->length; i++)
    GNUNET_PEER_change_rc (path->peers[i], 1);
  return aux;
}


/**
 * Recusively update the info about what is the first hop to reach the node
 *
 * @param tree Tree this nodes belongs to.
 * @param parent The node form which to start updating.
 * @param hop If known, ID of the first hop.
 *            If not known, NULL to find out and pass on children.
 */
static void
tree_node_update_first_hops (struct MeshTunnelTree *tree,
                             struct MeshTunnelTreeNode *parent,
                             struct GNUNET_PeerIdentity *hop);


/**
 * Get the length of a path.
 *
 * @param path The path to measure, with the local peer at any point of it.
 *
 * @return Number of hops to reach destination.
 *         UINT_MAX in case the peer is not in the path.
 */
unsigned int
path_get_length (struct MeshPeerPath