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_tunnel_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;
65 * Tree to reach all peers in the tunnel
67 struct MeshTunnelTree;
70 /******************************************************************************/
71 /************************* FUNCTIONS *****************************/
72 /******************************************************************************/
77 * @param length How many hops will the path have.
79 * @return A newly allocated path with a peer array of the specified length.
82 path_new (unsigned int length);
88 * @param path The path to invert.
91 path_invert (struct MeshPeerPath *path);
95 * Duplicate a path, incrementing short peer's rc.
97 * @param path The path to duplicate.
100 path_duplicate (struct MeshPeerPath *path);
104 * Get the length of a path.
106 * @param path The path to measure, with the local peer at any point of it.
108 * @return Number of hops to reach destination.
109 * UINT_MAX in case the peer is not in the path.
112 path_get_length (struct MeshPeerPath *path);
116 * Destroy the path and free any allocated resources linked to it
118 * @param p the path to destroy
120 * @return GNUNET_OK on success
123 path_destroy (struct MeshPeerPath *p);
126 /******************************************************************************/
129 * Iterator over all children of a node.
131 * @param cls Closure.
132 * @param peer_id Short ID of the peer.
134 typedef void (*MeshTreeCallback) (void *cls, GNUNET_PEER_Id peer_id);
138 * Iterator over all nodes in a tree.
140 * @param cls Closure.
141 * @param peer_id Short ID of the peer.
142 * @param peer_id Short ID of the parent of the peer.
144 typedef void (*MeshWholeTreeCallback) (void *cls,
145 GNUNET_PEER_Id peer_id,
146 GNUNET_PEER_Id parent_id);
149 * Create a new tunnel tree associated to a tunnel
151 * @param peer A short peer id of the root of the tree
153 * @return A newly allocated and initialized tunnel tree
155 struct MeshTunnelTree *
156 tree_new (GNUNET_PEER_Id peer);
160 * Set the status of a node.
163 * @param peer A short peer id of the node.
164 * @param status New status to set.
167 tree_set_status (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer,
168 enum MeshPeerState status);
172 * Get the status of a node.
174 * @param tree Tree whose local id we want to now.
175 * @param peer A short peer id of the node.
177 * @return Short peer id of local peer.
180 tree_get_status (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer);
184 * Get the id of the predecessor of the local node.
186 * @param tree Tree whose local id we want to now.
188 * @return Short peer id of local peer.
191 tree_get_predecessor (struct MeshTunnelTree *tree);
195 * Find the first peer whom to send a packet to go down this path
197 * @param t The tunnel tree to use
198 * @param peer The peerinfo of the peer we are trying to reach
200 * @return peerinfo of the peer who is the first hop in the tunnel
203 struct GNUNET_PeerIdentity *
204 tree_get_first_hop (struct MeshTunnelTree *t, GNUNET_PEER_Id peer);
208 * Find the given peer in the tree.
210 * @param tree Tree where to look for the peer.
211 * @param peer_id Peer to find.
213 * @return Pointer to the node of the peer. NULL if not found.
215 struct MeshTunnelTreeNode *
216 tree_find_peer (struct MeshTunnelTree *tree, GNUNET_PEER_Id peer_id);
220 * Iterate over all children of the local node.
222 * @param tree Tree to use. Must have "me" set.
223 * @param cb Callback to call over each child.
224 * @param cb_cls Closure for @c cb.
227 tree_iterate_children (struct MeshTunnelTree *tree,
233 * Iterate over all nodes in the tree.
235 * @param tree Tree to use..
236 * @param cb Callback to call over each child.
237 * @param cb_cls Closure for @c cb.
239 * TODO: recursive implementation? (s/heap/stack/g)
242 tree_iterate_all (struct MeshTunnelTree *tree,
243 MeshWholeTreeCallback cb,
248 * Recusively update the info about what is the first hop to reach the node
250 * @param tree Tree this nodes belongs to.
251 * @param parent_id Short ID from node form which to start updating.
252 * @param hop If known, ID of the first hop.
253 * If not known, NULL to find out and pass on children.
256 tree_update_first_hops (struct MeshTunnelTree *tree, GNUNET_PEER_Id parent_id,
257 struct GNUNET_PeerIdentity *hop);
260 * Delete the current path to the peer, including all now unused relays.
261 * The destination peer is NOT destroyed, it is returned in order to either set
262 * a new path to it or destroy it explicitly, taking care of it's child nodes.
264 * @param t Tunnel tree where to delete the path from.
265 * @param peer_id Short ID of the destination peer whose path we want to remove.
266 * @param cb Callback to use to notify about which peers are going to be
268 * @param cbcls Closure for cb.
270 * @return pointer to the pathless node.
271 * NULL when not found
273 struct MeshTunnelTreeNode *
274 tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id,
275 MeshTreeCallback cb, void *cbcls);
279 * Return a newly allocated individual path to reach a peer from the local peer,
280 * according to the path tree of some tunnel.
282 * @param t Tunnel from which to read the path tree
283 * @param peer Destination peer to whom we want a path
285 * @return A newly allocated individual path to reach the destination peer.
286 * Path must be destroyed afterwards.
288 struct MeshPeerPath *
289 tree_get_path_to_peer (struct MeshTunnelTree *t, GNUNET_PEER_Id peer);
293 * Integrate a stand alone path into the tunnel tree.
295 * @param t Tunnel where to add the new path.
296 * @param p Path to be integrated.
297 * @param cb Callback to use to notify about peers temporarily disconnecting.
298 * @param cbcls Closure for cb.
300 * @return GNUNET_OK in case of success.
301 * GNUNET_SYSERR in case of error.
304 tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p,
305 MeshTreeCallback cb, void *cbcls);
309 * Notifies a tree that a connection it might be using is broken.
310 * Marks all peers down the paths as disconnected and notifies the client.
312 * @param t Tree to use.
313 * @param p1 Short id of one of the peers (order unimportant)
314 * @param p2 Short id of one of the peers (order unimportant)
315 * @param cb Function to call for every peer that is marked as disconnected.
316 * @param cbcls Closure for cb.
318 * @return Short ID of the first disconnected peer in the tree.
321 tree_notify_connection_broken (struct MeshTunnelTree *t, GNUNET_PEER_Id p1,
322 GNUNET_PEER_Id p2, MeshTreeCallback cb,
327 * Deletes a peer from a tunnel, liberating all unused resources on the path to
328 * it. It shouldn't have children, if it has they will be destroyed as well.
329 * If the tree is not local and no longer has any paths, the root node will be
330 * destroyed and marked as NULL.
332 * @param t Tunnel tree to use.
333 * @param peer Short ID of the peer to remove from the tunnel tree.
334 * @param cb Callback to notify client of disconnected peers.
335 * @param cbcls Closure for cb.
337 * @return GNUNET_YES if the tunnel still has nodes
340 tree_del_peer (struct MeshTunnelTree *t, GNUNET_PEER_Id peer,
341 MeshTreeCallback cb, void *cbcls);
345 * Get the cost of the path relative to the already built tunnel tree
347 * @param t The tunnel tree to which compare
348 * @param path The individual path to reach a peer
350 * @return Number of hops to reach destination, UINT_MAX in case the peer is not
354 tree_get_path_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path);
358 * Print the tree on stderr
363 tree_debug (struct MeshTunnelTree *t);
367 * Destroy the whole tree and free all used memory and Peer_Ids
369 * @param t Tree to be destroyed
372 tree_destroy (struct MeshTunnelTree *t);