[GNUnet-SVN] r14147 - gnunet/src/fs

[gnunet]

Author: grothoff
Date: 2011-01-11 11:28:07 +0100 (Tue, 11 Jan 2011)
New Revision: 14147

Modified:
   gnunet/src/fs/fs.h
   gnunet/src/fs/fs_namespace.c
Log:
trying to fix SVN 1640

Modified: gnunet/src/fs/fs.h
===================================================================
--- gnunet/src/fs/fs.h  2011-01-11 10:26:57 UTC (rev 14146)
+++ gnunet/src/fs/fs.h  2011-01-11 10:28:07 UTC (rev 14147)
@@ -1925,14 +1925,14 @@
 
   /**
    * 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;
 
 };
 

Modified: gnunet/src/fs/fs_namespace.c
===================================================================
--- gnunet/src/fs/fs_namespace.c        2011-01-11 10:26:57 UTC (rev 14146)
+++ gnunet/src/fs/fs_namespace.c        2011-01-11 10:28:07 UTC (rev 14147)
@@ -1032,9 +1032,9 @@
 
 
 /**
- * Closure for 'find_sccs'.
+ * Closure for 'find_trees'.
  */
-struct FindSccClosure 
+struct FindTreeClosure 
 {
   /**
    * Namespace we are operating on.
@@ -1042,14 +1042,14 @@
   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 @@
   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 @@
 
 /**
  * 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 @@
  *         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 @@
  * 
  * 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_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 @@
     }
 #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;i<namespace->update_node_count;i++)
     {
@@ -1204,11 +1215,11 @@
        {
 #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 @@
       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.id<fc.scc_array_size;fc.id++)
+         /* start new TREE */
+         for (fc.id=0;fc.id<fc.tree_array_size;fc.id++)
            {
-             if (fc.scc_array[fc.id] == NULL)
+             if (fc.tree_array[fc.id] == NULL)
                {
-                 fc.scc_array[fc.id] = nsn;
-                 nsn->scc_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;i<fc.scc_array_size;i++)
+  for (i=0;i<fc.tree_array_size;i++)
     {
-      nsn = fc.scc_array[i];
+      nsn = fc.tree_array[i];
       if (NULL != nsn)
        {
 #if DEBUG_NAMESPACE
          GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
-                     "Root of SCC %u is node `%s'\n",
+                     "Root of TREE %u is node `%s'\n",
                      i,
                      nsn->id);
 #endif
@@ -1290,12 +1301,12 @@
              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
 }