diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/mesh/gnunet-service-mesh.c | 26 | ||||
-rw-r--r-- | src/mesh/mesh_tunnel_tree.c | 193 | ||||
-rw-r--r-- | src/mesh/mesh_tunnel_tree.h | 31 | ||||
-rw-r--r-- | src/mesh/test_mesh_path_api.c | 40 |
4 files changed, 158 insertions, 132 deletions
diff --git a/src/mesh/gnunet-service-mesh.c b/src/mesh/gnunet-service-mesh.c index f39040851..77986f90c 100644 --- a/src/mesh/gnunet-service-mesh.c +++ b/src/mesh/gnunet-service-mesh.c | |||
@@ -1084,28 +1084,6 @@ tunnel_notify_connection_broken (struct MeshTunnel *t, | |||
1084 | 1084 | ||
1085 | 1085 | ||
1086 | /** | 1086 | /** |
1087 | * Recursively destory the path tree of a tunnel. | ||
1088 | * Note: it does not liberate memory for itself, parent must do it! | ||
1089 | * | ||
1090 | * @param n The node to destroy, along with children. | ||
1091 | * | ||
1092 | * @return GNUNET_OK on success | ||
1093 | */ | ||
1094 | static void | ||
1095 | tunnel_destroy_tree_node (struct MeshTunnelTreeNode *n) | ||
1096 | { | ||
1097 | unsigned int i; | ||
1098 | |||
1099 | for (i = 0; i < n->nchildren; i++) | ||
1100 | { | ||
1101 | tunnel_destroy_tree_node(&n->children[i]); | ||
1102 | } | ||
1103 | if (NULL != n->children) | ||
1104 | GNUNET_free (n->children); | ||
1105 | } | ||
1106 | |||
1107 | |||
1108 | /** | ||
1109 | * Destroy the tunnel and free any allocated resources linked to it | 1087 | * Destroy the tunnel and free any allocated resources linked to it |
1110 | * | 1088 | * |
1111 | * @param t the tunnel to destroy | 1089 | * @param t the tunnel to destroy |
@@ -1155,9 +1133,7 @@ tunnel_destroy (struct MeshTunnel *t) | |||
1155 | 1133 | ||
1156 | GNUNET_CONTAINER_multihashmap_iterate(t->tree->first_hops, &iterate_free, t); | 1134 | GNUNET_CONTAINER_multihashmap_iterate(t->tree->first_hops, &iterate_free, t); |
1157 | GNUNET_CONTAINER_multihashmap_destroy(t->tree->first_hops); | 1135 | GNUNET_CONTAINER_multihashmap_destroy(t->tree->first_hops); |
1158 | tunnel_destroy_tree_node(t->tree->root); | 1136 | tree_destroy(t->tree); |
1159 | GNUNET_free(t->tree->root); | ||
1160 | GNUNET_free (t->tree); | ||
1161 | GNUNET_free (t); | 1137 | GNUNET_free (t); |
1162 | return r; | 1138 | return r; |
1163 | } | 1139 | } |
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 |
diff --git a/src/mesh/mesh_tunnel_tree.h b/src/mesh/mesh_tunnel_tree.h index 6573a85bd..a929f7a6d 100644 --- a/src/mesh/mesh_tunnel_tree.h +++ b/src/mesh/mesh_tunnel_tree.h | |||
@@ -76,14 +76,24 @@ struct MeshTunnelTreeNode | |||
76 | struct MeshTunnelTreeNode *parent; | 76 | struct MeshTunnelTreeNode *parent; |
77 | 77 | ||
78 | /** | 78 | /** |
79 | * Array of children | 79 | * DLL of siblings |
80 | */ | 80 | */ |
81 | struct MeshTunnelTreeNode *children; | 81 | struct MeshTunnelTreeNode *next; |
82 | 82 | ||
83 | /** | 83 | /** |
84 | * Number of children | 84 | * DLL of siblings |
85 | */ | 85 | */ |
86 | unsigned int nchildren; | 86 | struct MeshTunnelTreeNode *prev; |
87 | |||
88 | /** | ||
89 | * DLL of children | ||
90 | */ | ||
91 | struct MeshTunnelTreeNode *children_head; | ||
92 | |||
93 | /** | ||
94 | * DLL of children | ||
95 | */ | ||
96 | struct MeshTunnelTreeNode *children_tail; | ||
87 | 97 | ||
88 | /** | 98 | /** |
89 | * Status of the peer in the tunnel | 99 | * Status of the peer in the tunnel |
@@ -257,6 +267,19 @@ tree_add_path (struct MeshTunnelTree *t, const struct MeshPeerPath *p, | |||
257 | 267 | ||
258 | 268 | ||
259 | /** | 269 | /** |
270 | * Allocates and initializes a new node. | ||
271 | * Sets ID and parent of the new node and inserts it in the DLL of the parent | ||
272 | * | ||
273 | * @param parent Node that will be the parent from the new node, NULL for root | ||
274 | * @param id Short Id of the new node | ||
275 | * | ||
276 | * @return Newly allocated node | ||
277 | */ | ||
278 | struct MeshTunnelTreeNode * | ||
279 | tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id id); | ||
280 | |||
281 | |||
282 | /** | ||
260 | * Destroy the node and all children | 283 | * Destroy the node and all children |
261 | * | 284 | * |
262 | * @param n Parent node to be destroyed | 285 | * @param n Parent node to be destroyed |
diff --git a/src/mesh/test_mesh_path_api.c b/src/mesh/test_mesh_path_api.c index 3d6a06857..a397752e9 100644 --- a/src/mesh/test_mesh_path_api.c +++ b/src/mesh/test_mesh_path_api.c | |||
@@ -42,10 +42,10 @@ struct MeshTunnelTree *tree; | |||
42 | void | 42 | void |
43 | cb (const struct MeshTunnelTreeNode *n) | 43 | cb (const struct MeshTunnelTreeNode *n) |
44 | { | 44 | { |
45 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Disconnected %u\n", n->peer); | 45 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: CB: Disconnected %u\n", n->peer); |
46 | if(0 == cb_call) | 46 | if(0 == cb_call) |
47 | { | 47 | { |
48 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: and it shouldn't!\n"); | 48 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: and it shouldn't!\n"); |
49 | failed++; | 49 | failed++; |
50 | } | 50 | } |
51 | cb_call--; | 51 | cb_call--; |
@@ -120,6 +120,7 @@ main (int argc, char *argv[]) | |||
120 | 120 | ||
121 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding first path: 0 1 2 3\n"); | 121 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding first path: 0 1 2 3\n"); |
122 | tree_add_path(tree, path, &cb); | 122 | tree_add_path(tree, path, &cb); |
123 | tree_debug(tree); | ||
123 | path1 = tree_get_path_to_peer(tree, 3); | 124 | path1 = tree_get_path_to_peer(tree, 3); |
124 | if (path->length != path1->length || | 125 | if (path->length != path1->length || |
125 | memcmp(path->peers, path1->peers, path->length) != 0) | 126 | memcmp(path->peers, path1->peers, path->length) != 0) |
@@ -156,7 +157,7 @@ main (int argc, char *argv[]) | |||
156 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); | 157 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); |
157 | failed++; | 158 | failed++; |
158 | } | 159 | } |
159 | if (node->nchildren != 1) | 160 | if (node->children_head != node->children_tail) |
160 | { | 161 | { |
161 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); | 162 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); |
162 | failed++; | 163 | failed++; |
@@ -178,7 +179,7 @@ main (int argc, char *argv[]) | |||
178 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); | 179 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); |
179 | failed++; | 180 | failed++; |
180 | } | 181 | } |
181 | if (node->nchildren != 1) | 182 | if (node->children_head != node->children_tail) |
182 | { | 183 | { |
183 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); | 184 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); |
184 | failed++; | 185 | failed++; |
@@ -187,7 +188,8 @@ main (int argc, char *argv[]) | |||
187 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding second path: 0 1 2\n"); | 188 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding second path: 0 1 2\n"); |
188 | path->length--; | 189 | path->length--; |
189 | tree_add_path(tree, path, &cb); | 190 | tree_add_path(tree, path, &cb); |
190 | 191 | tree_debug(tree); | |
192 | |||
191 | node = tree_find_peer(tree->root, 2); | 193 | node = tree_find_peer(tree->root, 2); |
192 | if (node->peer != 2) | 194 | if (node->peer != 2) |
193 | { | 195 | { |
@@ -199,7 +201,7 @@ main (int argc, char *argv[]) | |||
199 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); | 201 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); |
200 | failed++; | 202 | failed++; |
201 | } | 203 | } |
202 | if (node->nchildren != 1) | 204 | if (node->children_head != node->children_tail) |
203 | { | 205 | { |
204 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); | 206 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); |
205 | failed++; | 207 | failed++; |
@@ -228,7 +230,7 @@ main (int argc, char *argv[]) | |||
228 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); | 230 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); |
229 | failed++; | 231 | failed++; |
230 | } | 232 | } |
231 | if (node->nchildren != 1) | 233 | if (node->children_head != node->children_tail) |
232 | { | 234 | { |
233 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); | 235 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); |
234 | failed++; | 236 | failed++; |
@@ -238,10 +240,7 @@ main (int argc, char *argv[]) | |||
238 | path->length++; | 240 | path->length++; |
239 | path->peers[3] = 4; | 241 | path->peers[3] = 4; |
240 | tree_add_path(tree, path, &cb); | 242 | tree_add_path(tree, path, &cb); |
241 | |||
242 | path_destroy(path); | ||
243 | tree_debug(tree); | 243 | tree_debug(tree); |
244 | finish(); | ||
245 | 244 | ||
246 | node = tree_find_peer(tree->root, 2); | 245 | node = tree_find_peer(tree->root, 2); |
247 | if (node->peer != 2) | 246 | if (node->peer != 2) |
@@ -254,7 +253,7 @@ main (int argc, char *argv[]) | |||
254 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); | 253 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); |
255 | failed++; | 254 | failed++; |
256 | } | 255 | } |
257 | if (node->nchildren != 2) | 256 | if (node->children_head->next != node->children_tail) |
258 | { | 257 | { |
259 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); | 258 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); |
260 | failed++; | 259 | failed++; |
@@ -281,7 +280,7 @@ main (int argc, char *argv[]) | |||
281 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); | 280 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); |
282 | failed++; | 281 | failed++; |
283 | } | 282 | } |
284 | if (node->nchildren != 1) | 283 | if (node->children_head != node->children_tail) |
285 | { | 284 | { |
286 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); | 285 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); |
287 | failed++; | 286 | failed++; |
@@ -293,11 +292,12 @@ main (int argc, char *argv[]) | |||
293 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer != original\n"); | 292 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer != original\n"); |
294 | failed++; | 293 | failed++; |
295 | } | 294 | } |
296 | 295 | ||
297 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Deleting third path...\n"); | 296 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Deleting third path...\n"); |
298 | node->status = MESH_PEER_READY; | 297 | node->status = MESH_PEER_READY; |
299 | cb_call = 1; | 298 | cb_call = 1; |
300 | node2 = tree_del_path(tree, 4, &cb); | 299 | node2 = tree_del_path(tree, 4, &cb); |
300 | tree_debug(tree); | ||
301 | if (cb_call != 0) | 301 | if (cb_call != 0) |
302 | { | 302 | { |
303 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "%u callbacks missed!\n", cb_call); | 303 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "%u callbacks missed!\n", cb_call); |
@@ -320,25 +320,31 @@ main (int argc, char *argv[]) | |||
320 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); | 320 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); |
321 | failed++; | 321 | failed++; |
322 | } | 322 | } |
323 | if (node->nchildren != 1) | 323 | if (node->children_head != node->children_tail) |
324 | { | 324 | { |
325 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); | 325 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); |
326 | failed++; | 326 | failed++; |
327 | } | 327 | } |
328 | 328 | ||
329 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Destroying node copy...\n"); | 329 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Destroying node copy...\n"); |
330 | tree_node_destroy(node2); | 330 | GNUNET_free (node2); |
331 | 331 | ||
332 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding new shorter first path...\n"); | 332 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding new shorter first path...\n"); |
333 | path->length = 2; | 333 | path->length = 2; |
334 | path->peers[1] = 3; | 334 | path->peers[1] = 3; |
335 | cb_call = 1; | 335 | cb_call = 1; |
336 | tree_find_peer(tree->root, 3)->status = MESH_PEER_READY; | ||
336 | tree_add_path(tree, path, cb); | 337 | tree_add_path(tree, path, cb); |
338 | tree_debug(tree); | ||
337 | if (cb_call != 0) | 339 | if (cb_call != 0) |
338 | { | 340 | { |
339 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "%u callbacks missed!\n", cb_call); | 341 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "%u callbacks missed!\n", cb_call); |
340 | failed++; | 342 | failed++; |
341 | } | 343 | } |
344 | |||
345 | path_destroy(path); | ||
346 | finish(); | ||
347 | |||
342 | node = tree_find_peer(tree->root, 2); | 348 | node = tree_find_peer(tree->root, 2); |
343 | if (node->peer != 2) | 349 | if (node->peer != 2) |
344 | { | 350 | { |
@@ -350,7 +356,7 @@ main (int argc, char *argv[]) | |||
350 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); | 356 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); |
351 | failed++; | 357 | failed++; |
352 | } | 358 | } |
353 | if (node->nchildren != 0) | 359 | if (node->children_head != NULL) |
354 | { | 360 | { |
355 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); | 361 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); |
356 | failed++; | 362 | failed++; |
@@ -366,7 +372,7 @@ main (int argc, char *argv[]) | |||
366 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); | 372 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n"); |
367 | failed++; | 373 | failed++; |
368 | } | 374 | } |
369 | if (node->nchildren != 0) | 375 | if (node->children_head != NULL) |
370 | { | 376 | { |
371 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); | 377 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n"); |
372 | failed++; | 378 | failed++; |