diff options
author | Bart Polot <bart@net.in.tum.de> | 2011-09-22 18:12:27 +0000 |
---|---|---|
committer | Bart Polot <bart@net.in.tum.de> | 2011-09-22 18:12:27 +0000 |
commit | 17e4c95ee4c555db7ab3ab9c57412b7866ee5411 (patch) | |
tree | 25a8e79563ba3a6890cba8de7015cae8f3a0d9ba /src/mesh/mesh_tunnel_tree.c | |
parent | 1e018e4e2e1d57cee223aa84f2ebd7e6c8160480 (diff) | |
download | gnunet-17e4c95ee4c555db7ab3ab9c57412b7866ee5411.tar.gz gnunet-17e4c95ee4c555db7ab3ab9c57412b7866ee5411.zip |
Changed tree children magement from array to DLL, fixed bugs, extended testcase.
Diffstat (limited to 'src/mesh/mesh_tunnel_tree.c')
-rw-r--r-- | src/mesh/mesh_tunnel_tree.c | 193 |
1 files changed, 107 insertions, 86 deletions
diff --git a/src/mesh/mesh_tunnel_tree.c b/src/mesh/mesh_tunnel_tree.c index 747789096..766960dd4 100644 --- a/src/mesh/mesh_tunnel_tree.c +++ b/src/mesh/mesh_tunnel_tree.c | |||
@@ -31,13 +31,27 @@ | |||
31 | static void | 31 | static void |
32 | debug_node(struct MeshTunnelTreeNode *n, uint16_t level) | 32 | debug_node(struct MeshTunnelTreeNode *n, uint16_t level) |
33 | { | 33 | { |
34 | struct MeshTunnelTreeNode *c; | ||
34 | uint16_t i; | 35 | uint16_t i; |
35 | 36 | ||
36 | for (i = 0; i < level; i++) | 37 | for (i = 0; i < level; i++) |
37 | fprintf(stderr, " "); | 38 | fprintf(stderr, " "); |
38 | fprintf(stderr, "%u\n", n->peer); | 39 | if (n->status == MESH_PEER_READY) |
39 | for (i = 0; i < n->nchildren; i++) | 40 | fprintf(stderr, "#"); |
40 | debug_node(&n->children[i], level + 1); | 41 | if (n->status == MESH_PEER_SEARCHING) |
42 | fprintf(stderr, "+"); | ||
43 | if (n->status == MESH_PEER_RELAY) | ||
44 | fprintf(stderr, "-"); | ||
45 | if (n->status == MESH_PEER_RECONNECTING) | ||
46 | fprintf(stderr, "*"); | ||
47 | |||
48 | fprintf(stderr, "%u [%p] ", n->peer, n); | ||
49 | if (NULL != n->parent) | ||
50 | fprintf(stderr, "(-> %u)\n", n->parent->peer); | ||
51 | else | ||
52 | fprintf(stderr, "(root)\n"); | ||
53 | for (c = n->children_head; NULL != c; c = c->next) | ||
54 | debug_node(c, level + 1); | ||
41 | } | 55 | } |
42 | 56 | ||
43 | 57 | ||
@@ -151,18 +165,18 @@ path_get_cost (struct MeshTunnelTree *t, struct MeshPeerPath *path) | |||
151 | * @return Pointer to the node of the peer. NULL if not found. | 165 | * @return Pointer to the node of the peer. NULL if not found. |
152 | */ | 166 | */ |
153 | struct MeshTunnelTreeNode * | 167 | struct MeshTunnelTreeNode * |
154 | tree_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id) | 168 | tree_find_peer (struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer_id) |
155 | { | 169 | { |
156 | struct MeshTunnelTreeNode *n; | 170 | struct MeshTunnelTreeNode *n; |
157 | unsigned int i; | 171 | struct MeshTunnelTreeNode *r; |
158 | 172 | ||
159 | if (root->peer == peer_id) | 173 | if (parent->peer == peer_id) |
160 | return root; | 174 | return parent; |
161 | for (i = 0; i < root->nchildren; i++) | 175 | for (n = parent->children_head; NULL != n; n = n->next) |
162 | { | 176 | { |
163 | n = tree_find_peer (&root->children[i], peer_id); | 177 | r = tree_find_peer (n, peer_id); |
164 | if (NULL != n) | 178 | if (NULL != r) |
165 | return n; | 179 | return r; |
166 | } | 180 | } |
167 | return NULL; | 181 | return NULL; |
168 | } | 182 | } |
@@ -182,36 +196,24 @@ tree_mark_peers_disconnected (struct MeshTunnelTree *tree, | |||
182 | { | 196 | { |
183 | struct GNUNET_PeerIdentity *pi; | 197 | struct GNUNET_PeerIdentity *pi; |
184 | struct GNUNET_PeerIdentity id; | 198 | struct GNUNET_PeerIdentity id; |
185 | unsigned int i; | 199 | struct MeshTunnelTreeNode *n; |
186 | 200 | ||
187 | for (i = 0; i < parent->nchildren; i++) | 201 | for (n = parent->children_head; NULL != n; n = n->next) |
188 | { | 202 | { |
189 | tree_mark_peers_disconnected (tree, &parent->children[i], cb); | 203 | tree_mark_peers_disconnected (tree, n, cb); |
190 | } | 204 | } |
191 | if (MESH_PEER_READY == parent->status) | 205 | if (MESH_PEER_READY == parent->status) |
192 | { | 206 | { |
193 | cb (parent); | 207 | cb (parent); |
194 | } | 208 | } |
195 | parent->status = MESH_PEER_RECONNECTING; | 209 | parent->status = MESH_PEER_RECONNECTING; |
196 | 210 | ||
197 | /* Remove and free info about first hop */ | 211 | /* Remove and free info about first hop */ |
198 | GNUNET_PEER_resolve(parent->peer, &id); | 212 | GNUNET_PEER_resolve(parent->peer, &id); |
199 | pi = GNUNET_CONTAINER_multihashmap_get(tree->first_hops, &id.hashPubKey); | 213 | pi = GNUNET_CONTAINER_multihashmap_get(tree->first_hops, &id.hashPubKey); |
200 | GNUNET_CONTAINER_multihashmap_remove_all(tree->first_hops, &id.hashPubKey); | 214 | GNUNET_CONTAINER_multihashmap_remove_all(tree->first_hops, &id.hashPubKey); |
201 | if (NULL != pi) | 215 | if (NULL != pi) |
202 | GNUNET_free(pi); | 216 | GNUNET_free(pi); |
203 | // FIXME: add to service code on callback | ||
204 | // struct GNUNET_MESH_PeerControl msg; | ||
205 | // if (NULL == parent->t->client) | ||
206 | // return; | ||
207 | // msg.header.size = htons (sizeof (msg)); | ||
208 | // msg.header.type = htons (GNUNET_MESSAGE_TYPE_MESH_LOCAL_PEER_DEL); | ||
209 | // msg.tunnel_id = htonl (parent->t->local_tid); | ||
210 | // GNUNET_PEER_resolve (parent->peer, &msg.peer); | ||
211 | // if (NULL == nc) | ||
212 | // return; | ||
213 | // GNUNET_SERVER_notification_context_unicast (nc, parent->t->client->handle, | ||
214 | // &msg.header, GNUNET_NO); | ||
215 | } | 217 | } |
216 | 218 | ||
217 | 219 | ||
@@ -231,7 +233,7 @@ tree_update_first_hops (struct MeshTunnelTree *tree, | |||
231 | struct GNUNET_PeerIdentity pi; | 233 | struct GNUNET_PeerIdentity pi; |
232 | struct GNUNET_PeerIdentity *copy; | 234 | struct GNUNET_PeerIdentity *copy; |
233 | struct GNUNET_PeerIdentity id; | 235 | struct GNUNET_PeerIdentity id; |
234 | unsigned int i; | 236 | struct MeshTunnelTreeNode *n; |
235 | 237 | ||
236 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, | 238 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, |
237 | "tree: Finding first hop for %u.\n", | 239 | "tree: Finding first hop for %u.\n", |
@@ -264,9 +266,9 @@ tree_update_first_hops (struct MeshTunnelTree *tree, | |||
264 | GNUNET_CONTAINER_multihashmap_put(tree->first_hops, &id.hashPubKey, copy, | 266 | GNUNET_CONTAINER_multihashmap_put(tree->first_hops, &id.hashPubKey, copy, |
265 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST); | 267 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST); |
266 | 268 | ||
267 | for (i = 0; i < parent->nchildren; i++) | 269 | for (n = parent->children_head; NULL != n; n = n->next) |
268 | { | 270 | { |
269 | tree_update_first_hops (tree, &parent->children[i], hop); | 271 | tree_update_first_hops (tree, n, hop); |
270 | } | 272 | } |
271 | } | 273 | } |
272 | 274 | ||
@@ -280,7 +282,8 @@ tree_update_first_hops (struct MeshTunnelTree *tree, | |||
280 | * @param peer Destination peer whose path we want to remove. | 282 | * @param peer Destination peer whose path we want to remove. |
281 | * @param cb Callback to use to notify about disconnected peers. | 283 | * @param cb Callback to use to notify about disconnected peers. |
282 | * | 284 | * |
283 | * @return pointer to the pathless node, NULL on error | 285 | * @return pointer to the pathless node. |
286 | * NULL when not found | ||
284 | */ | 287 | */ |
285 | struct MeshTunnelTreeNode * | 288 | struct MeshTunnelTreeNode * |
286 | tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id, | 289 | tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id, |
@@ -296,23 +299,25 @@ tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id, | |||
296 | n = tree_find_peer (t->me, peer_id); | 299 | n = tree_find_peer (t->me, peer_id); |
297 | if (NULL == n) | 300 | if (NULL == n) |
298 | return NULL; | 301 | return NULL; |
299 | node = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode)); | 302 | node = n; |
300 | *node = *n; | 303 | |
301 | parent = n->parent; | 304 | parent = n->parent; |
302 | parent->nchildren--; | 305 | GNUNET_CONTAINER_DLL_remove(parent->children_head, parent->children_tail, n); |
303 | n->parent = NULL; | 306 | n->parent = NULL; |
304 | *n = parent->children[parent->nchildren]; | 307 | |
305 | parent->children = GNUNET_realloc(parent->children, | ||
306 | parent->nchildren | ||
307 | * sizeof(struct MeshTunnelTreeNode)); | ||
308 | while (t->root != parent && MESH_PEER_RELAY == parent->status && | 308 | while (t->root != parent && MESH_PEER_RELAY == parent->status && |
309 | 0 == parent->nchildren) | 309 | NULL == parent->children_head) |
310 | { | 310 | { |
311 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Deleting node %u.\n", parent->peer); | 311 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, |
312 | "tree: Deleting node %u.\n", | ||
313 | parent->peer); | ||
312 | n = parent->parent; | 314 | n = parent->parent; |
313 | tree_node_destroy(parent); | 315 | tree_node_destroy(parent); |
314 | parent = n; | 316 | parent = n; |
315 | } | 317 | } |
318 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, | ||
319 | "tree: Not deleted peer %u.\n", | ||
320 | parent->peer); | ||
316 | 321 | ||
317 | tree_mark_peers_disconnected (t, node, cb); | 322 | tree_mark_peers_disconnected (t, node, cb); |
318 | 323 | ||
@@ -378,12 +383,12 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, | |||
378 | struct MeshTunnelTreeNode *parent; | 383 | struct MeshTunnelTreeNode *parent; |
379 | struct MeshTunnelTreeNode *oldnode; | 384 | struct MeshTunnelTreeNode *oldnode; |
380 | struct MeshTunnelTreeNode *n; | 385 | struct MeshTunnelTreeNode *n; |
386 | struct MeshTunnelTreeNode *c; | ||
381 | struct GNUNET_PeerIdentity id; | 387 | struct GNUNET_PeerIdentity id; |
382 | struct GNUNET_PeerIdentity *hop; | 388 | struct GNUNET_PeerIdentity *hop; |
383 | GNUNET_PEER_Id myid = t->me->peer; | 389 | GNUNET_PEER_Id myid = t->me->peer; |
384 | int me; | 390 | int me; |
385 | unsigned int i; | 391 | unsigned int i; |
386 | unsigned int j; | ||
387 | 392 | ||
388 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, | 393 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, |
389 | "tree: Adding path [%u] towards peer %u to peer %u.\n", | 394 | "tree: Adding path [%u] towards peer %u to peer %u.\n", |
@@ -415,11 +420,14 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, | |||
415 | parent = n; | 420 | parent = n; |
416 | if (p->peers[i] == myid) | 421 | if (p->peers[i] == myid) |
417 | me = i; | 422 | me = i; |
418 | for (j = 0; j < n->nchildren; j++) | 423 | for (c = n->children_head; NULL != c; c = c->next) |
419 | { | 424 | { |
420 | if (n->children[j].peer == p->peers[i]) | 425 | if (c->peer == p->peers[i]) |
421 | { | 426 | { |
422 | n = &n->children[j]; | 427 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, |
428 | "tree: Found in children of %u.\n", | ||
429 | parent->peer); | ||
430 | n = c; | ||
423 | break; | 431 | break; |
424 | } | 432 | } |
425 | } | 433 | } |
@@ -443,33 +451,23 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, | |||
443 | "tree: Adding peer %u, to %u.\n", | 451 | "tree: Adding peer %u, to %u.\n", |
444 | p->peers[i], | 452 | p->peers[i], |
445 | parent->peer); | 453 | parent->peer); |
446 | parent->nchildren++; | 454 | |
447 | parent->children = GNUNET_realloc (parent->children, | ||
448 | parent->nchildren * | ||
449 | sizeof(struct MeshTunnelTreeNode)); | ||
450 | n = &parent->children[parent->nchildren - 1]; | ||
451 | n->parent = parent; | ||
452 | if (i == p->length - 1 && NULL != oldnode) | 455 | if (i == p->length - 1 && NULL != oldnode) |
453 | { | 456 | { |
454 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Putting old node into place.\n"); | 457 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Putting old node into place.\n"); |
455 | /* Assignation and free can be misleading, using explicit mempcy */ | 458 | oldnode->parent = parent; |
456 | memcpy (n, oldnode, sizeof (struct MeshTunnelTreeNode)); | 459 | GNUNET_CONTAINER_DLL_insert(parent->children_head, |
457 | n->parent = parent; | 460 | parent->children_tail, |
458 | GNUNET_free (oldnode); | 461 | oldnode); |
459 | for (j = 0; j < n->nchildren; j++) | 462 | tree_update_first_hops (t, oldnode, NULL); |
460 | { | 463 | n = oldnode; |
461 | n->children[j].parent = n; | ||
462 | tree_update_first_hops (t, &n->children[j], NULL); | ||
463 | } | ||
464 | } | 464 | } |
465 | else | 465 | else |
466 | { | 466 | { |
467 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Creating new node.\n"); | 467 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Creating new node.\n"); |
468 | n = tree_node_new(parent, p->peers[i]); | ||
468 | n->t = t->t; | 469 | n->t = t->t; |
469 | n->status = MESH_PEER_RELAY; | 470 | n->status = MESH_PEER_RELAY; |
470 | n->peer = p->peers[i]; | ||
471 | n->nchildren = 0; | ||
472 | n->children = NULL; | ||
473 | } | 471 | } |
474 | i++; | 472 | i++; |
475 | parent = n; | 473 | parent = n; |
@@ -482,7 +480,10 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, | |||
482 | GNUNET_PEER_resolve (p->peers[p->length - 1], &id); | 480 | GNUNET_PEER_resolve (p->peers[p->length - 1], &id); |
483 | hop = GNUNET_CONTAINER_multihashmap_get(t->first_hops, &id.hashPubKey); | 481 | hop = GNUNET_CONTAINER_multihashmap_get(t->first_hops, &id.hashPubKey); |
484 | if (NULL != hop) | 482 | if (NULL != hop) |
483 | { | ||
484 | GNUNET_CONTAINER_multihashmap_remove_all(t->first_hops, &id.hashPubKey); | ||
485 | GNUNET_free(hop); | 485 | GNUNET_free(hop); |
486 | } | ||
486 | hop = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)); | 487 | hop = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)); |
487 | GNUNET_PEER_resolve (p->peers[me + 1], hop); | 488 | GNUNET_PEER_resolve (p->peers[me + 1], hop); |
488 | GNUNET_CONTAINER_multihashmap_put (t->first_hops, &id.hashPubKey, | 489 | GNUNET_CONTAINER_multihashmap_put (t->first_hops, &id.hashPubKey, |
@@ -495,36 +496,56 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, | |||
495 | 496 | ||
496 | 497 | ||
497 | /** | 498 | /** |
498 | * Destroy the node and all children | 499 | * Allocates and initializes a new node. |
500 | * Sets ID and parent of the new node and inserts it in the DLL of the parent | ||
501 | * | ||
502 | * @param parent Node that will be the parent from the new node, NULL for root | ||
503 | * @param id Short Id of the new node | ||
504 | * | ||
505 | * @return Newly allocated node | ||
506 | */ | ||
507 | struct MeshTunnelTreeNode * | ||
508 | tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id id) | ||
509 | { | ||
510 | struct MeshTunnelTreeNode *node; | ||
511 | |||
512 | node = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode)); | ||
513 | node->peer = id; | ||
514 | GNUNET_PEER_change_rc(id, 1); | ||
515 | node->parent = parent; | ||
516 | if (NULL != parent) | ||
517 | GNUNET_CONTAINER_DLL_insert(parent->children_head, | ||
518 | parent->children_tail, | ||
519 | node); | ||
520 | |||
521 | return node; | ||
522 | } | ||
523 | |||
524 | |||
525 | /** | ||
526 | * Destroys and frees the node and all children | ||
499 | * | 527 | * |
500 | * @param n Parent node to be destroyed | 528 | * @param n Parent node to be destroyed |
501 | */ | 529 | */ |
502 | void | 530 | void |
503 | tree_node_destroy (struct MeshTunnelTreeNode *n) | 531 | tree_node_destroy (struct MeshTunnelTreeNode *parent) |
504 | { | 532 | { |
505 | struct MeshTunnelTreeNode *parent; | 533 | struct MeshTunnelTreeNode *n; |
506 | unsigned int i; | 534 | struct MeshTunnelTreeNode *next; |
507 | 535 | ||
508 | if (n->nchildren != 0) | 536 | n = parent->children_head; |
537 | while (NULL != n) | ||
509 | { | 538 | { |
510 | for (i = 0; i < n->nchildren; i++) | 539 | next = n->next; |
511 | { | 540 | tree_node_destroy(n); |
512 | tree_node_destroy(&n->children[i]); | 541 | n = next; |
513 | } | ||
514 | if (n->children != NULL) | ||
515 | GNUNET_free(n->children); | ||
516 | } | 542 | } |
517 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Destroying node %u.\n", n->peer); | 543 | GNUNET_PEER_change_rc(parent->peer, -1); |
518 | if (NULL == (parent = n->parent)) | 544 | if (NULL != parent->parent) |
519 | return; | 545 | GNUNET_CONTAINER_DLL_remove(parent->parent->children_head, |
520 | i = (n - parent->children) / sizeof(struct MeshTunnelTreeNode); | 546 | parent->parent->children_tail, |
521 | parent->children[i] = parent->children[parent->nchildren - 1]; | 547 | parent); |
522 | parent->nchildren--; | 548 | GNUNET_free(parent); |
523 | parent->children = realloc(parent->children, | ||
524 | parent->nchildren | ||
525 | * sizeof(struct MeshTunnelTreeNode)); | ||
526 | |||
527 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Destroyed.\n"); | ||
528 | } | 549 | } |
529 | 550 | ||
530 | 551 | ||
@@ -554,7 +575,7 @@ void | |||
554 | tree_destroy (struct MeshTunnelTree *t) | 575 | tree_destroy (struct MeshTunnelTree *t) |
555 | { | 576 | { |
556 | tree_node_destroy(t->root); | 577 | tree_node_destroy(t->root); |
557 | GNUNET_free(t->root); | ||
558 | GNUNET_CONTAINER_multihashmap_iterate(t->first_hops, &iterate_free, NULL); | 578 | GNUNET_CONTAINER_multihashmap_iterate(t->first_hops, &iterate_free, NULL); |
559 | GNUNET_CONTAINER_multihashmap_destroy(t->first_hops); | 579 | GNUNET_CONTAINER_multihashmap_destroy(t->first_hops); |
580 | GNUNET_free(t); | ||
560 | } \ No newline at end of file | 581 | } \ No newline at end of file |