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 *next;
86 struct MeshTunnelTreeNode *prev;
91 struct MeshTunnelTreeNode *children_head;
96 struct MeshTunnelTreeNode *children_tail;
99 * Status of the peer in the tunnel
101 enum MeshPeerState status;
106 * Tree to reach all peers in the tunnel
108 struct MeshTunnelTree
111 * How often to refresh the path
113 struct GNUNET_TIME_Relative refresh;
116 * Tunnel this path belongs to
118 struct MeshTunnel *t;
121 * Root node of peer tree
123 struct MeshTunnelTreeNode *root;
126 * Node that represents our position in the tree (for non local tunnels)
128 struct MeshTunnelTreeNode *me;
131 * DLL of disconneted nodes
133 struct MeshTunnelTreeNode *disconnected_head;
136 * DLL of disconneted nodes
138 struct MeshTunnelTreeNode *disconnected_tail;
141 * Cache of all peers and the first hop to them.
142 * Indexed by PeerIdentity, contains a pointer to the PeerIdentity
145 struct GNUNET_CONTAINER_MultiHashMap *first_hops;
150 /******************************************************************************/
151 /************************* FUNCTIONS *****************************/
152 /******************************************************************************/
157 * @param lenght How many hops will the path have.
159 * @return A newly allocated path with a peer array of the specified length.
161 struct MeshPeerPath *
162 path_new (unsigned int length);
168 * @param p the path to invert
171 path_invert (struct MeshPeerPath *p);
175 * Duplicate a path, incrementing short peer's rc.
177 * @param p The path to duplicate.
179 struct MeshPeerPath *
180 path_duplicate (struct MeshPeerPath *path);
184 * Find the first peer whom to send a packet to go down this path
186 * @param t The tunnel tree to use
187 * @param peer The peerinfo of the peer we are trying to reach
189 * @return peerinfo of the peer who is the first hop in the tunnel
192 struct GNUNET_PeerIdentity *
193 path_get_first_hop (struct MeshTunnelTree *t,
194 GNUNET_PEER_Id peer);
198 * Get the length of a path
200 * @param p The path to measure, with the local peer at any point of it
202 * @return Number of hops to reach destination
203 * UINT_MAX in case the peer is not in the path
206 path_get_length (struct MeshPeerPath *p);
210 * Get the cost of the path relative to the already built tunnel tree
212 * @param t The tunnel tree to which compare
213 * @param path The individual path to reach a peer
215 * @return Number of hops to reach destination, UINT_MAX in case the peer is not
219 path_get_cost (struct MeshTunnelTree *t,
220 struct MeshPeerPath *path);
224 * Destroy the path and free any allocated resources linked to it
226 * @param p the path to destroy
228 * @return GNUNET_OK on success
231 path_destroy (struct MeshPeerPath *p);
234 /******************************************************************************/
237 * Method called whenever a node has been marked as disconnected.
239 * @param node peer identity the tunnel stopped working with
241 typedef void (*MeshNodeDisconnectCB) (const struct MeshTunnelTreeNode * node);
245 * Create a new tunnel tree associated to a tunnel
247 * @param t Tunnel this tree will represent
248 * @param peer A short peer id of the root of the tree
250 * @return A newly allocated and initialized tunnel tree
252 struct MeshTunnelTree *
253 tree_new (struct MeshTunnel *t, GNUNET_PEER_Id peer);
257 * Recursively find the given peer in the tree.
259 * @param parent Parent node where to start looking.
260 * @param peer Short ID of peer to find.
262 * @return Pointer to the node of the peer. NULL if not found.
264 struct MeshTunnelTreeNode *
265 tree_find_peer (struct MeshTunnelTreeNode *parent,
266 GNUNET_PEER_Id peer);
270 * Recusively update the info about what is the first hop to reach the node
272 * @param tree Tree this nodes belongs to
273 * @param parent Node to be start updating
274 * @param hop If known, ID of the first hop.
275 * If not known, NULL to find out and pass on children.
278 tree_update_first_hops (struct MeshTunnelTree *tree,
279 struct MeshTunnelTreeNode *parent,
280 struct GNUNET_PeerIdentity *hop);
283 * Delete the current path to the peer, including all now unused relays.
284 * The destination peer is NOT destroyed, it is returned in order to either set
285 * a new path to it or destroy it explicitly, taking care of it's child nodes.
287 * @param t Tunnel tree where to delete the path from.
288 * @param peer Destination peer whose path we want to remove.
289 * @param cb Callback to use to notify about which peers are going to be
292 * @return pointer to the pathless node.
293 * NULL when not found
295 struct MeshTunnelTreeNode *
296 tree_del_path (struct MeshTunnelTree *t,
298 MeshNodeDisconnectCB cb);
302 * Return a newly allocated individual path to reach a peer from the local peer,
303 * according to the path tree of some tunnel.
305 * @param t Tunnel from which to read the path tree
306 * @param peer Destination peer to whom we want a path
308 * @return A newly allocated individual path to reach the destination peer.
309 * Path must be destroyed afterwards.
311 struct MeshPeerPath *
312 tree_get_path_to_peer(struct MeshTunnelTree *t,
313 GNUNET_PEER_Id peer);
317 * Integrate a stand alone path into the tunnel tree.
319 * @param t Tunnel where to add the new path.
320 * @param p Path to be integrated.
321 * @param cb Callback to use to notify about peers temporarily disconnecting
323 * @return GNUNET_OK in case of success.
324 * GNUNET_SYSERR in case of error.
327 tree_add_path (struct MeshTunnelTree *t,
328 const struct MeshPeerPath *p,
329 MeshNodeDisconnectCB cb);
333 * Notifies a tree that a connection it might be using is broken.
334 * Marks all peers down the paths as disconnected and notifies the client.
336 * @param t Tree to use.
337 * @param p1 Short id of one of the peers (order unimportant)
338 * @param p2 Short id of one of the peers (order unimportant)
339 * @param cb Function to call for every peer that is marked as disconnected.
341 * @return Short ID of the first disconnected peer in the tree.
344 tree_notify_connection_broken (struct MeshTunnelTree *t,
347 MeshNodeDisconnectCB cb);
351 * Deletes a peer from a tunnel, liberating all unused resources on the path to
352 * it. It shouldn't have children, if it has they will be destroyed as well.
353 * If the tree is not local and no longer has any paths, the root node will be
354 * destroyed and marked as NULL.
356 * @param t Tunnel tree to use.
357 * @param peer Short ID of the peer to remove from the tunnel tree.
358 * @param cb Callback to notify client of disconnected peers.
360 * @return GNUNET_OK or GNUNET_SYSERR
363 tree_del_peer (struct MeshTunnelTree *t,
365 MeshNodeDisconnectCB cb);
368 * Print the tree on stderr
373 tree_debug(struct MeshTunnelTree *t);
377 * Destroy the whole tree and free all used memory and Peer_Ids
379 * @param t Tree to be destroyed
382 tree_destroy (struct MeshTunnelTree *t);