[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r17001 - gnunet/src/mesh
From: |
gnunet |
Subject: |
[GNUnet-SVN] r17001 - gnunet/src/mesh |
Date: |
Thu, 22 Sep 2011 20:12:27 +0200 |
Author: bartpolot
Date: 2011-09-22 20:12:27 +0200 (Thu, 22 Sep 2011)
New Revision: 17001
Modified:
gnunet/src/mesh/gnunet-service-mesh.c
gnunet/src/mesh/mesh_tunnel_tree.c
gnunet/src/mesh/mesh_tunnel_tree.h
gnunet/src/mesh/test_mesh_path_api.c
Log:
Changed tree children magement from array to DLL, fixed bugs, extended testcase.
Modified: gnunet/src/mesh/gnunet-service-mesh.c
===================================================================
--- gnunet/src/mesh/gnunet-service-mesh.c 2011-09-21 22:39:11 UTC (rev
17000)
+++ gnunet/src/mesh/gnunet-service-mesh.c 2011-09-22 18:12:27 UTC (rev
17001)
@@ -1084,28 +1084,6 @@
/**
- * Recursively destory the path tree of a tunnel.
- * Note: it does not liberate memory for itself, parent must do it!
- *
- * @param n The node to destroy, along with children.
- *
- * @return GNUNET_OK on success
- */
-static void
-tunnel_destroy_tree_node (struct MeshTunnelTreeNode *n)
-{
- unsigned int i;
-
- for (i = 0; i < n->nchildren; i++)
- {
- tunnel_destroy_tree_node(&n->children[i]);
- }
- if (NULL != n->children)
- GNUNET_free (n->children);
-}
-
-
-/**
* Destroy the tunnel and free any allocated resources linked to it
*
* @param t the tunnel to destroy
@@ -1155,9 +1133,7 @@
GNUNET_CONTAINER_multihashmap_iterate(t->tree->first_hops, &iterate_free, t);
GNUNET_CONTAINER_multihashmap_destroy(t->tree->first_hops);
- tunnel_destroy_tree_node(t->tree->root);
- GNUNET_free(t->tree->root);
- GNUNET_free (t->tree);
+ tree_destroy(t->tree);
GNUNET_free (t);
return r;
}
Modified: gnunet/src/mesh/mesh_tunnel_tree.c
===================================================================
--- gnunet/src/mesh/mesh_tunnel_tree.c 2011-09-21 22:39:11 UTC (rev 17000)
+++ gnunet/src/mesh/mesh_tunnel_tree.c 2011-09-22 18:12:27 UTC (rev 17001)
@@ -31,13 +31,27 @@
static void
debug_node(struct MeshTunnelTreeNode *n, uint16_t level)
{
+ struct MeshTunnelTreeNode *c;
uint16_t i;
for (i = 0; i < level; i++)
- fprintf(stderr, " ");
- fprintf(stderr, "%u\n", n->peer);
- for (i = 0; i < n->nchildren; i++)
- debug_node(&n->children[i], level + 1);
+ fprintf(stderr, " ");
+ if (n->status == MESH_PEER_READY)
+ fprintf(stderr, "#");
+ if (n->status == MESH_PEER_SEARCHING)
+ fprintf(stderr, "+");
+ if (n->status == MESH_PEER_RELAY)
+ fprintf(stderr, "-");
+ if (n->status == MESH_PEER_RECONNECTING)
+ fprintf(stderr, "*");
+
+ fprintf(stderr, "%u [%p] ", n->peer, n);
+ if (NULL != n->parent)
+ fprintf(stderr, "(-> %u)\n", n->parent->peer);
+ else
+ fprintf(stderr, "(root)\n");
+ for (c = n->children_head; NULL != c; c = c->next)
+ debug_node(c, level + 1);
}
@@ -151,18 +165,18 @@
* @return Pointer to the node of the peer. NULL if not found.
*/
struct MeshTunnelTreeNode *
-tree_find_peer (struct MeshTunnelTreeNode *root, GNUNET_PEER_Id peer_id)
+tree_find_peer (struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id peer_id)
{
struct MeshTunnelTreeNode *n;
- unsigned int i;
+ struct MeshTunnelTreeNode *r;
- if (root->peer == peer_id)
- return root;
- for (i = 0; i < root->nchildren; i++)
+ if (parent->peer == peer_id)
+ return parent;
+ for (n = parent->children_head; NULL != n; n = n->next)
{
- n = tree_find_peer (&root->children[i], peer_id);
- if (NULL != n)
- return n;
+ r = tree_find_peer (n, peer_id);
+ if (NULL != r)
+ return r;
}
return NULL;
}
@@ -182,36 +196,24 @@
{
struct GNUNET_PeerIdentity *pi;
struct GNUNET_PeerIdentity id;
- unsigned int i;
+ struct MeshTunnelTreeNode *n;
- for (i = 0; i < parent->nchildren; i++)
+ for (n = parent->children_head; NULL != n; n = n->next)
{
- tree_mark_peers_disconnected (tree, &parent->children[i], cb);
+ tree_mark_peers_disconnected (tree, n, cb);
}
if (MESH_PEER_READY == parent->status)
{
cb (parent);
}
parent->status = MESH_PEER_RECONNECTING;
-
+
/* Remove and free info about first hop */
GNUNET_PEER_resolve(parent->peer, &id);
pi = GNUNET_CONTAINER_multihashmap_get(tree->first_hops, &id.hashPubKey);
GNUNET_CONTAINER_multihashmap_remove_all(tree->first_hops, &id.hashPubKey);
if (NULL != pi)
GNUNET_free(pi);
-// FIXME: add to service code on callback
-// struct GNUNET_MESH_PeerControl msg;
-// if (NULL == parent->t->client)
-// return;
-// msg.header.size = htons (sizeof (msg));
-// msg.header.type = htons (GNUNET_MESSAGE_TYPE_MESH_LOCAL_PEER_DEL);
-// msg.tunnel_id = htonl (parent->t->local_tid);
-// GNUNET_PEER_resolve (parent->peer, &msg.peer);
-// if (NULL == nc)
-// return;
-// GNUNET_SERVER_notification_context_unicast (nc, parent->t->client->handle,
-// &msg.header, GNUNET_NO);
}
@@ -231,7 +233,7 @@
struct GNUNET_PeerIdentity pi;
struct GNUNET_PeerIdentity *copy;
struct GNUNET_PeerIdentity id;
- unsigned int i;
+ struct MeshTunnelTreeNode *n;
GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
"tree: Finding first hop for %u.\n",
@@ -264,9 +266,9 @@
GNUNET_CONTAINER_multihashmap_put(tree->first_hops, &id.hashPubKey, copy,
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
- for (i = 0; i < parent->nchildren; i++)
+ for (n = parent->children_head; NULL != n; n = n->next)
{
- tree_update_first_hops (tree, &parent->children[i], hop);
+ tree_update_first_hops (tree, n, hop);
}
}
@@ -280,7 +282,8 @@
* @param peer Destination peer whose path we want to remove.
* @param cb Callback to use to notify about disconnected peers.
*
- * @return pointer to the pathless node, NULL on error
+ * @return pointer to the pathless node.
+ * NULL when not found
*/
struct MeshTunnelTreeNode *
tree_del_path (struct MeshTunnelTree *t, GNUNET_PEER_Id peer_id,
@@ -296,23 +299,25 @@
n = tree_find_peer (t->me, peer_id);
if (NULL == n)
return NULL;
- node = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode));
- *node = *n;
+ node = n;
+
parent = n->parent;
- parent->nchildren--;
+ GNUNET_CONTAINER_DLL_remove(parent->children_head, parent->children_tail, n);
n->parent = NULL;
- *n = parent->children[parent->nchildren];
- parent->children = GNUNET_realloc(parent->children,
- parent->nchildren
- * sizeof(struct MeshTunnelTreeNode));
+
while (t->root != parent && MESH_PEER_RELAY == parent->status &&
- 0 == parent->nchildren)
+ NULL == parent->children_head)
{
- GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Deleting node %u.\n",
parent->peer);
+ GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
+ "tree: Deleting node %u.\n",
+ parent->peer);
n = parent->parent;
tree_node_destroy(parent);
parent = n;
}
+ GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
+ "tree: Not deleted peer %u.\n",
+ parent->peer);
tree_mark_peers_disconnected (t, node, cb);
@@ -378,12 +383,12 @@
struct MeshTunnelTreeNode *parent;
struct MeshTunnelTreeNode *oldnode;
struct MeshTunnelTreeNode *n;
+ struct MeshTunnelTreeNode *c;
struct GNUNET_PeerIdentity id;
struct GNUNET_PeerIdentity *hop;
GNUNET_PEER_Id myid = t->me->peer;
int me;
unsigned int i;
- unsigned int j;
GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
"tree: Adding path [%u] towards peer %u to peer %u.\n",
@@ -415,11 +420,14 @@
parent = n;
if (p->peers[i] == myid)
me = i;
- for (j = 0; j < n->nchildren; j++)
+ for (c = n->children_head; NULL != c; c = c->next)
{
- if (n->children[j].peer == p->peers[i])
+ if (c->peer == p->peers[i])
{
- n = &n->children[j];
+ GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
+ "tree: Found in children of %u.\n",
+ parent->peer);
+ n = c;
break;
}
}
@@ -443,33 +451,23 @@
"tree: Adding peer %u, to %u.\n",
p->peers[i],
parent->peer);
- parent->nchildren++;
- parent->children = GNUNET_realloc (parent->children,
- parent->nchildren *
- sizeof(struct MeshTunnelTreeNode));
- n = &parent->children[parent->nchildren - 1];
- n->parent = parent;
+
if (i == p->length - 1 && NULL != oldnode)
{
GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Putting old node into
place.\n");
- /* Assignation and free can be misleading, using explicit mempcy */
- memcpy (n, oldnode, sizeof (struct MeshTunnelTreeNode));
- n->parent = parent;
- GNUNET_free (oldnode);
- for (j = 0; j < n->nchildren; j++)
- {
- n->children[j].parent = n;
- tree_update_first_hops (t, &n->children[j], NULL);
- }
+ oldnode->parent = parent;
+ GNUNET_CONTAINER_DLL_insert(parent->children_head,
+ parent->children_tail,
+ oldnode);
+ tree_update_first_hops (t, oldnode, NULL);
+ n = oldnode;
}
else
{
GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Creating new node.\n");
+ n = tree_node_new(parent, p->peers[i]);
n->t = t->t;
n->status = MESH_PEER_RELAY;
- n->peer = p->peers[i];
- n->nchildren = 0;
- n->children = NULL;
}
i++;
parent = n;
@@ -482,7 +480,10 @@
GNUNET_PEER_resolve (p->peers[p->length - 1], &id);
hop = GNUNET_CONTAINER_multihashmap_get(t->first_hops, &id.hashPubKey);
if (NULL != hop)
+ {
+ GNUNET_CONTAINER_multihashmap_remove_all(t->first_hops, &id.hashPubKey);
GNUNET_free(hop);
+ }
hop = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
GNUNET_PEER_resolve (p->peers[me + 1], hop);
GNUNET_CONTAINER_multihashmap_put (t->first_hops, &id.hashPubKey,
@@ -495,36 +496,56 @@
/**
- * Destroy the node and all children
+ * Allocates and initializes a new node.
+ * Sets ID and parent of the new node and inserts it in the DLL of the parent
+ *
+ * @param parent Node that will be the parent from the new node, NULL for root
+ * @param id Short Id of the new node
+ *
+ * @return Newly allocated node
+ */
+struct MeshTunnelTreeNode *
+tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id id)
+{
+ struct MeshTunnelTreeNode *node;
+
+ node = GNUNET_malloc(sizeof(struct MeshTunnelTreeNode));
+ node->peer = id;
+ GNUNET_PEER_change_rc(id, 1);
+ node->parent = parent;
+ if (NULL != parent)
+ GNUNET_CONTAINER_DLL_insert(parent->children_head,
+ parent->children_tail,
+ node);
+
+ return node;
+}
+
+
+/**
+ * Destroys and frees the node and all children
*
* @param n Parent node to be destroyed
*/
void
-tree_node_destroy (struct MeshTunnelTreeNode *n)
+tree_node_destroy (struct MeshTunnelTreeNode *parent)
{
- struct MeshTunnelTreeNode *parent;
- unsigned int i;
+ struct MeshTunnelTreeNode *n;
+ struct MeshTunnelTreeNode *next;
- if (n->nchildren != 0)
+ n = parent->children_head;
+ while (NULL != n)
{
- for (i = 0; i < n->nchildren; i++)
- {
- tree_node_destroy(&n->children[i]);
- }
- if (n->children != NULL)
- GNUNET_free(n->children);
+ next = n->next;
+ tree_node_destroy(n);
+ n = next;
}
- GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Destroying node %u.\n",
n->peer);
- if (NULL == (parent = n->parent))
- return;
- i = (n - parent->children) / sizeof(struct MeshTunnelTreeNode);
- parent->children[i] = parent->children[parent->nchildren - 1];
- parent->nchildren--;
- parent->children = realloc(parent->children,
- parent->nchildren
- * sizeof(struct MeshTunnelTreeNode));
-
- GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "tree: Destroyed.\n");
+ GNUNET_PEER_change_rc(parent->peer, -1);
+ if (NULL != parent->parent)
+ GNUNET_CONTAINER_DLL_remove(parent->parent->children_head,
+ parent->parent->children_tail,
+ parent);
+ GNUNET_free(parent);
}
@@ -554,7 +575,7 @@
tree_destroy (struct MeshTunnelTree *t)
{
tree_node_destroy(t->root);
- GNUNET_free(t->root);
GNUNET_CONTAINER_multihashmap_iterate(t->first_hops, &iterate_free, NULL);
GNUNET_CONTAINER_multihashmap_destroy(t->first_hops);
+ GNUNET_free(t);
}
\ No newline at end of file
Modified: gnunet/src/mesh/mesh_tunnel_tree.h
===================================================================
--- gnunet/src/mesh/mesh_tunnel_tree.h 2011-09-21 22:39:11 UTC (rev 17000)
+++ gnunet/src/mesh/mesh_tunnel_tree.h 2011-09-22 18:12:27 UTC (rev 17001)
@@ -76,15 +76,25 @@
struct MeshTunnelTreeNode *parent;
/**
- * Array of children
+ * DLL of siblings
*/
- struct MeshTunnelTreeNode *children;
+ struct MeshTunnelTreeNode *next;
/**
- * Number of children
+ * DLL of siblings
*/
- unsigned int nchildren;
+ struct MeshTunnelTreeNode *prev;
+ /**
+ * DLL of children
+ */
+ struct MeshTunnelTreeNode *children_head;
+
+ /**
+ * DLL of children
+ */
+ struct MeshTunnelTreeNode *children_tail;
+
/**
* Status of the peer in the tunnel
*/
@@ -257,6 +267,19 @@
/**
+ * Allocates and initializes a new node.
+ * Sets ID and parent of the new node and inserts it in the DLL of the parent
+ *
+ * @param parent Node that will be the parent from the new node, NULL for root
+ * @param id Short Id of the new node
+ *
+ * @return Newly allocated node
+ */
+struct MeshTunnelTreeNode *
+tree_node_new(struct MeshTunnelTreeNode *parent, GNUNET_PEER_Id id);
+
+
+/**
* Destroy the node and all children
*
* @param n Parent node to be destroyed
Modified: gnunet/src/mesh/test_mesh_path_api.c
===================================================================
--- gnunet/src/mesh/test_mesh_path_api.c 2011-09-21 22:39:11 UTC (rev
17000)
+++ gnunet/src/mesh/test_mesh_path_api.c 2011-09-22 18:12:27 UTC (rev
17001)
@@ -42,10 +42,10 @@
void
cb (const struct MeshTunnelTreeNode *n)
{
- GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Disconnected %u\n", n->peer);
+ GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: CB: Disconnected %u\n", n->peer);
if(0 == cb_call)
{
- GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: and it shouldn't!\n");
+ GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: and it shouldn't!\n");
failed++;
}
cb_call--;
@@ -120,6 +120,7 @@
GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding first path: 0 1 2 3\n");
tree_add_path(tree, path, &cb);
+ tree_debug(tree);
path1 = tree_get_path_to_peer(tree, 3);
if (path->length != path1->length ||
memcmp(path->peers, path1->peers, path->length) != 0)
@@ -156,7 +157,7 @@
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n");
failed++;
}
- if (node->nchildren != 1)
+ if (node->children_head != node->children_tail)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n");
failed++;
@@ -178,7 +179,7 @@
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n");
failed++;
}
- if (node->nchildren != 1)
+ if (node->children_head != node->children_tail)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n");
failed++;
@@ -187,7 +188,8 @@
GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding second path: 0 1 2\n");
path->length--;
tree_add_path(tree, path, &cb);
-
+ tree_debug(tree);
+
node = tree_find_peer(tree->root, 2);
if (node->peer != 2)
{
@@ -199,7 +201,7 @@
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n");
failed++;
}
- if (node->nchildren != 1)
+ if (node->children_head != node->children_tail)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n");
failed++;
@@ -228,7 +230,7 @@
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n");
failed++;
}
- if (node->nchildren != 1)
+ if (node->children_head != node->children_tail)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n");
failed++;
@@ -238,10 +240,7 @@
path->length++;
path->peers[3] = 4;
tree_add_path(tree, path, &cb);
-
- path_destroy(path);
tree_debug(tree);
- finish();
node = tree_find_peer(tree->root, 2);
if (node->peer != 2)
@@ -254,7 +253,7 @@
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n");
failed++;
}
- if (node->nchildren != 2)
+ if (node->children_head->next != node->children_tail)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n");
failed++;
@@ -281,7 +280,7 @@
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n");
failed++;
}
- if (node->nchildren != 1)
+ if (node->children_head != node->children_tail)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n");
failed++;
@@ -293,11 +292,12 @@
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer != original\n");
failed++;
}
-
+
GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Deleting third path...\n");
node->status = MESH_PEER_READY;
cb_call = 1;
node2 = tree_del_path(tree, 4, &cb);
+ tree_debug(tree);
if (cb_call != 0)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "%u callbacks missed!\n", cb_call);
@@ -320,25 +320,31 @@
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n");
failed++;
}
- if (node->nchildren != 1)
+ if (node->children_head != node->children_tail)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n");
failed++;
}
GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Destroying node copy...\n");
- tree_node_destroy(node2);
+ GNUNET_free (node2);
GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "test: Adding new shorter first
path...\n");
path->length = 2;
path->peers[1] = 3;
cb_call = 1;
+ tree_find_peer(tree->root, 3)->status = MESH_PEER_READY;
tree_add_path(tree, path, cb);
+ tree_debug(tree);
if (cb_call != 0)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "%u callbacks missed!\n", cb_call);
failed++;
}
+
+ path_destroy(path);
+ finish();
+
node = tree_find_peer(tree->root, 2);
if (node->peer != 2)
{
@@ -350,7 +356,7 @@
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n");
failed++;
}
- if (node->nchildren != 0)
+ if (node->children_head != NULL)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n");
failed++;
@@ -366,7 +372,7 @@
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong status!\n");
failed++;
}
- if (node->nchildren != 0)
+ if (node->children_head != NULL)
{
GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "Retrieved peer wrong nchildren!\n");
failed++;
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r17001 - gnunet/src/mesh,
gnunet <=