2 This file is part of GNUnet.
3 (C) 2001 - 2011 Christian Grothoff (and other contributing authors)
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.
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.
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.
22 * @file mesh/mesh_tree_tree.h
23 * @brief Tunnel tree handling functions
24 * @author Bartlomiej Polot
29 /******************************************************************************/
30 /************************ DATA STRUCTURES ****************************/
31 /******************************************************************************/
34 * Information regarding a possible path to reach a single peer
42 struct MeshPeerPath *next;
43 struct MeshPeerPath *prev;
46 * List of all the peers that form the path from origin to target.
48 GNUNET_PEER_Id *peers;
51 * Number of peers (hops) in the path
59 * Node of path tree for a tunnel
61 struct MeshTunnelTreeNode
64 * Tunnel this node belongs to (and therefore tree)
69 * Peer this node describes
74 * Parent node in the tree
76 struct MeshTunnelTreeNode *parent;
81 struct MeshTunnelTreeNode *children;
86 unsigned int nchildren;
89 * Status of the peer in the tunnel
91 enum MeshPeerState status;
96 * Tree to reach all peers in the tunnel
101 * How often to refresh the path
103 struct GNUNET_TIME_Relative refresh;
106 * Tunnel this path belongs to
108 struct MeshTunnel *t;
111 * Root node of peer tree
113 struct MeshTunnelTreeNode *root;
116 * Node that represents our position in the tree (for non local tunnels)
118 struct MeshTunnelTreeNode *me;
121 * Cache of all peers and the first hop to them.
122 * Indexed by Peer_Identity, contains a pointer to the PeerIdentity
125 struct GNUNET_CONTAINER_MultiHashMap *first_hops;
130 /******************************************************************************/
131 /************************* FUNCTIONS *****************************/
132 /******************************************************************************/
136 * Method called whenever a node has been marked as disconnected.
138 * @param node peer identity the tunnel stopped working with
140 typedef void (*MeshNodeDisconnectCB) (const struct MeshTunnelTreeNode * node);
146 * @param p the path to invert
149 path_invert (struct MeshPeerPath *path);
154 * Destroy the path and free any allocated resources linked to it
156 * @param p the path to destroy
158 * @return GNUNET_OK on success
161 path_destroy (struct MeshPeerPath *p);
165 * Find the first peer whom to send a packet to go down this path
167 * @param t The tunnel to use
168 * @param peer The peerinfo of the peer we are trying to reach
170 * @return peerinfo of the peer who is the first hop in the tunnel
173 struct GNUNET_PeerIdentity *
174 path_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer);
178 * Get the length of a path
180 * @param path The path to measure, with the local peer at any point of it
182 * @return Number of hops to reach destination
183 * UINT_MAX in case the peer is not in the path
186 path_get_length (struct MeshPeerPath *path);
190 * Get the cost of the path relative to the already built tunnel tree
192 * @param t The tunnel to which compare
193 * @param path The individual path to reach a peer
195 * @return Number of hops to reach destination, UINT_MAX in case the peer is not
199 path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path);
203 * Recursively find the given peer in the tree.
205 * @param t Tunnel where to look for the peer.
206 * @param peer Peer to find
208 * @return Pointer to the node of the peer. NULL if not found.
210 struct MeshTunnelTreeNode *
211 tree_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id);
215 * Recusively mark peer and children as disconnected, notify client
217 * @param parent Node to be clean, potentially with children
218 * @param cb Callback to use to notify about disconnected peers
221 tree_mark_peers_disconnected (struct MeshTunnelTreeNode *parent,
222 MeshNodeDisconnectCB cb);
226 * Delete the current path to the peer, including all now unused relays.
227 * The destination peer is NOT destroyed, it is returned in order to either set
228 * a new path to it or destroy it explicitly, taking care of it's child nodes.
230 * @param t Tunnel where to delete the path from.
231 * @param peer Destination peer whose path we want to remove.
232 * @param cb Callback to use to notify about disconnected peers
234 * @return pointer to the pathless node, NULL on error
236 struct MeshTunnelTreeNode *
237 tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id,
238 MeshNodeDisconnectCB cb);
242 * Return a newly allocated individual path to reach a peer from the local peer,
243 * according to the path tree of some tunnel.
245 * @param t Tunnel from which to read the path tree
246 * @param peer_info Destination peer to whom we want a path
248 * @return A newly allocated individual path to reach the destination peer.
249 * Path must be destroyed afterwards.
251 struct MeshPeerPath *
252 tree_get_path_to_peer(struct MeshTunnelTree *t, GNUNET_PEER_Id peer);
256 * Integrate a stand alone path into the tunnel tree.
258 * @param t Tunnel where to add the new path.
259 * @param p Path to be integrated.
260 * @param cb Callback to use to notify about peers temporarily disconnecting
262 * @return GNUNET_OK in case of success.
263 * GNUNET_SYSERR in case of error.
266 tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p,
267 MeshNodeDisconnectCB cb);
271 * Destroy the node and all children
273 * @param n Parent node to be destroyed
276 tree_node_destroy (struct MeshTunnelTreeNode *n);
280 * Destroy the whole tree and free all used memory and Peer_Ids
282 * @param t Tree to be destroyed
285 tree_destroy (struct MeshTunnelTree *t);