From 9dccfed7fc149542bb836da4243f105dec485114 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 11 Jan 2011 10:28:07 +0000 Subject: [PATCH] trying to fix SVN 1640 --- src/fs/fs.h | 6 +- src/fs/fs_namespace.c | 127 +++++++++++++++++++++++------------------- 2 files changed, 72 insertions(+), 61 deletions(-) diff --git a/src/fs/fs.h b/src/fs/fs.h index e655a3e57..0ba1d08a1 100644 --- a/src/fs/fs.h +++ b/src/fs/fs.h @@ -1925,14 +1925,14 @@ struct NamespaceUpdateNode /** * Namespace update generation ID. Used to ensure - * freshness of the scc_id. + * freshness of the tree_id. */ unsigned int nug; /** - * SCC this entry belongs to (if nug is current). + * TREE this entry belongs to (if nug is current). */ - unsigned int scc_id; + unsigned int tree_id; }; diff --git a/src/fs/fs_namespace.c b/src/fs/fs_namespace.c index 91502e1de..bc66bb21f 100644 --- a/src/fs/fs_namespace.c +++ b/src/fs/fs_namespace.c @@ -1032,9 +1032,9 @@ process_update_node (void *cls, /** - * Closure for 'find_sccs'. + * Closure for 'find_trees'. */ -struct FindSccClosure +struct FindTreeClosure { /** * Namespace we are operating on. @@ -1042,14 +1042,14 @@ struct FindSccClosure struct GNUNET_FS_Namespace *namespace; /** - * Array with 'head's of SCCs. + * Array with 'head's of TREEs. */ - struct NamespaceUpdateNode **scc_array; + struct NamespaceUpdateNode **tree_array; /** - * Size of 'scc_array' + * Size of 'tree_array' */ - unsigned int scc_array_size; + unsigned int tree_array_size; /** * Current generational ID used. @@ -1057,7 +1057,7 @@ struct FindSccClosure unsigned int nug; /** - * Identifier for the current SCC, or UINT_MAX for none yet. + * Identifier for the current TREE, or UINT_MAX for none yet. */ unsigned int id; }; @@ -1065,15 +1065,18 @@ struct FindSccClosure /** * Find all nodes reachable from the current node (including the - * current node itself). If they are in no SCC, add them to the - * current one. If they are the head of another SCC, merge the - * SCCs. If they are in the middle of another SCC, let them be. - * We can tell that a node is already in an SCC by checking if + * current node itself). If they are in no tree, add them to the + * current one. If they are the head of another tree, merge the + * trees. If they are in the middle of another tree, let them be. + * We can tell that a node is already in an tree by checking if * its 'nug' field is set to the current 'nug' value. It is the - * head of an SCC if it is in the 'scc_array' under its respective - * 'scc_id'. + * head of an tree if it is in the 'tree_array' under its respective + * 'tree_id'. * - * @param cls closure (of type 'struct FindSccClosure') + * In short, we're trying to find the smallest number of tree to + * cover a directed graph. + * + * @param cls closure (of type 'struct FindTreeClosure') * @param key current key code * @param value value in the hash map * @return GNUNET_YES if we should continue to @@ -1081,34 +1084,40 @@ struct FindSccClosure * GNUNET_NO if not. */ static int -find_sccs (void *cls, +find_trees (void *cls, const GNUNET_HashCode * key, void *value) { - struct FindSccClosure *fc = cls; + struct FindTreeClosure *fc = cls; struct NamespaceUpdateNode *nsn = value; GNUNET_HashCode hc; if (nsn->nug == fc->nug) { - if (fc->scc_array[nsn->scc_id] != nsn) - return GNUNET_YES; /* part of another SCC, end trace */ - if (nsn->scc_id == fc->id) - return GNUNET_YES; /* that's us */ - fc->scc_array[nsn->scc_id] = NULL; + if (nsn->tree_id == UINT_MAX) + return GNUNET_YES; /* circular */ + GNUNET_assert (nsn->tree_id < fc->tree_array_size); + if (fc->tree_array[nsn->tree_id] != nsn) + return GNUNET_YES; /* part of "another" (directed) TREE, + and not root of it, end trace */ + if (nsn->tree_id == fc->id) + return GNUNET_YES; /* that's our own root (can this be?) */ + /* merge existing TREE, we have a root for both */ + fc->tree_array[nsn->tree_id] = NULL; if (fc->id == UINT_MAX) - fc->id = nsn->scc_id; /* take over ID */ + fc->id = nsn->tree_id; /* take over ID */ } else { nsn->nug = fc->nug; + nsn->tree_id = UINT_MAX; /* mark as undef */ /* trace */ GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc); GNUNET_CONTAINER_multihashmap_get_multiple (fc->namespace->update_map, &hc, - &find_sccs, + &find_trees, fc); } return GNUNET_YES; @@ -1123,15 +1132,17 @@ find_sccs (void *cls, * * Calling this function with "next_id" NULL will cause the library to * call "ip" with a root for each strongly connected component of the - * graph (a root being a node from which all other nodes in the Scc + * graph (a root being a node from which all other nodes in the Tree * are reachable). * * Calling this function with "next_id" being the name of a node will * cause the library to call "ip" with all children of the node. Note - * that cycles within an SCC are possible (including self-loops). + * that cycles within the final tree are possible (including self-loops). + * I know, odd definition of a tree, but the GUI will display an actual + * tree (GtkTreeView), so that's what counts for the term here. * * @param namespace namespace to inspect for updateable content - * @param next_id ID to look for; use NULL to look for SCC roots + * @param next_id ID to look for; use NULL to look for tree roots * @param ip function to call on each updateable identifier * @param ip_cls closure for ip */ @@ -1146,7 +1157,7 @@ GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Namespace *namespace, GNUNET_HashCode hc; struct NamespaceUpdateNode *nsn; struct ProcessUpdateClosure pc; - struct FindSccClosure fc; + struct FindTreeClosure fc; if (namespace->update_nodes == NULL) read_update_information_graph (namespace); @@ -1190,12 +1201,12 @@ GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Namespace *namespace, } #if DEBUG_NAMESPACE GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "Calculating SCCs to find roots of update trees\n"); + "Calculating TREEs to find roots of update trees\n"); #endif - /* Find heads of SCCs in update graph */ + /* Find heads of TREEs in update graph */ nug = ++namespace->nug_gen; - fc.scc_array = NULL; - fc.scc_array_size = 0; + fc.tree_array = NULL; + fc.tree_array_size = 0; for (i=0;iupdate_node_count;i++) { @@ -1204,11 +1215,11 @@ GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Namespace *namespace, { #if DEBUG_NAMESPACE GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "SCC of node `%s' is %u\n", + "TREE of node `%s' is %u\n", nsn->id, nsn->nug); #endif - continue; /* already placed in SCC */ + continue; /* already placed in TREE */ } GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), @@ -1219,66 +1230,66 @@ GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Namespace *namespace, fc.namespace = namespace; GNUNET_CONTAINER_multihashmap_get_multiple (namespace->update_map, &hc, - &find_sccs, + &find_trees, &fc); if (fc.id == UINT_MAX) { - /* start new SCC */ - for (fc.id=0;fc.idscc_id = fc.id; + fc.tree_array[fc.id] = nsn; + nsn->tree_id = fc.id; break; } } - if (fc.id == fc.scc_array_size) + if (fc.id == fc.tree_array_size) { - GNUNET_array_append (fc.scc_array, - fc.scc_array_size, + GNUNET_array_append (fc.tree_array, + fc.tree_array_size, nsn); - nsn->scc_id = fc.id; + nsn->tree_id = fc.id; } #if DEBUG_NAMESPACE GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "Starting new SCC %u with node `%s'\n", - nsn->scc_id, + "Starting new TREE %u with node `%s'\n", + nsn->tree_id, nsn->id); #endif - /* put all nodes with same identifier into this SCC */ + /* put all nodes with same identifier into this TREE */ GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc); - fc.id = nsn->scc_id; + fc.id = nsn->tree_id; fc.nug = nug; fc.namespace = namespace; GNUNET_CONTAINER_multihashmap_get_multiple (namespace->update_map, &hc, - &find_sccs, + &find_trees, &fc); } else { - /* make head of SCC "id" */ - fc.scc_array[fc.id] = nsn; - nsn->scc_id = fc.id; + /* make head of TREE "id" */ + fc.tree_array[fc.id] = nsn; + nsn->tree_id = fc.id; } #if DEBUG_NAMESPACE GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "SCC of node `%s' is %u\n", + "TREE of node `%s' is %u\n", nsn->id, fc.id); #endif } - for (i=0;iid); #endif @@ -1290,12 +1301,12 @@ GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Namespace *namespace, nsn->update); } } - GNUNET_array_grow (fc.scc_array, - fc.scc_array_size, + GNUNET_array_grow (fc.tree_array, + fc.tree_array_size, 0); #if DEBUG_NAMESPACE GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "Done processing SCCs\n"); + "Done processing TREEs\n"); #endif } -- 2.25.1