src/fs/fs_namespace.c

   1 /*
   2      This file is part of GNUnet
   3      (C) 2003-2013 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file fs/fs_namespace.c
  23  * @brief publishing to namespaces, and tracking updateable entries
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_constants.h"
  28 #include "gnunet_signatures.h"
  29 #include "gnunet_util_lib.h"
  30 #include "gnunet_fs_service.h"
  31 #include "fs_api.h"
  32 #include "fs_publish_ublock.h"
  33
  34
  35 /**
  36  * Information about an (updateable) node in the
  37  * namespace.
  38  */
  39 struct NamespaceUpdateNode
  40 {
  41   /**
  42    * Identifier for this node.
  43    */
  44   char *id;
  45
  46   /**
  47    * Identifier of children of this node.
  48    */
  49   char *update;
  50
  51   /**
  52    * Metadata for this entry.
  53    */
  54   struct GNUNET_CONTAINER_MetaData *md;
  55
  56   /**
  57    * URI of this entry in the namespace.
  58    */
  59   struct GNUNET_FS_Uri *uri;
  60
  61   /**
  62    * Namespace update generation ID.  Used to ensure
  63    * freshness of the tree_id.
  64    */
  65   unsigned int nug;
  66
  67   /**
  68    * TREE this entry belongs to (if nug is current).
  69    */
  70   unsigned int tree_id;
  71
  72 };
  73
  74
  75 /**
  76  * Handle to update information for a namespace.
  77  */
  78 struct GNUNET_FS_UpdateInformationGraph
  79 {
  80
  81   /**
  82    * Handle to the FS service context.
  83    */
  84   struct GNUNET_FS_Handle *h;
  85
  86   /**
  87    * Array with information about nodes in the namespace.
  88    */
  89   struct NamespaceUpdateNode **update_nodes;
  90
  91   /**
  92    * Private key for the namespace.
  93    */
  94   struct GNUNET_CRYPTO_EccPrivateKey ns;
  95
  96   /**
  97    * Hash map mapping identifiers of update nodes
  98    * to the update nodes (initialized on-demand).
  99    */
 100   struct GNUNET_CONTAINER_MultiHashMap *update_map;
 101
 102   /**
 103    * Size of the update nodes array.
 104    */
 105   unsigned int update_node_count;
 106
 107   /**
 108    * Reference counter.
 109    */
 110   unsigned int rc;
 111
 112   /**
 113    * Generator for unique nug numbers.
 114    */
 115   unsigned int nug_gen;
 116 };
 117
 118
 119 /**
 120  * Return the name of the directory in which we store
 121  * the update information graph for the given local namespace.
 122  *
 123  * @param h file-sharing handle
 124  * @param ns namespace handle
 125  * @return NULL on error, otherwise the name of the directory
 126  */
 127 static char *
 128 get_update_information_directory (struct GNUNET_FS_Handle *h,
 129                                   const struct GNUNET_CRYPTO_EccPrivateKey *ns)
 130 {
 131   char *dn;
 132   char *ret;
 133   struct GNUNET_CRYPTO_EccPublicKey pub;
 134   struct GNUNET_CRYPTO_ShortHashCode hc;
 135   struct GNUNET_CRYPTO_ShortHashAsciiEncoded enc;
 136
 137   if (GNUNET_OK !=
 138       GNUNET_CONFIGURATION_get_value_filename (h->cfg, "FS", "UPDATE_DIR",
 139                                                &dn))
 140   {
 141     GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR,
 142                                "fs", "UPDATE_DIR");
 143     return NULL;
 144   }
 145   GNUNET_CRYPTO_ecc_key_get_public (ns, &pub);
 146   GNUNET_CRYPTO_short_hash (&pub, sizeof (pub), &hc);
 147   GNUNET_CRYPTO_short_hash_to_enc (&hc,
 148                                    &enc);
 149   GNUNET_asprintf (&ret, "%s%s%s",
 150                    dn,
 151                    DIR_SEPARATOR_STR,
 152                    (const char *) enc.short_encoding);
 153   GNUNET_free (dn);
 154   return ret;
 155 }
 156
 157
 158 /**
 159  * Release memory occupied by UIG datastructure.
 160  *
 161  * @param uig data structure to free
 162  */
 163 static void
 164 free_update_information_graph (struct GNUNET_FS_UpdateInformationGraph *uig)
 165 {
 166   unsigned int i;
 167   struct NamespaceUpdateNode *nsn;
 168
 169   for (i = 0; i < uig->update_node_count; i++)
 170   {
 171     nsn = uig->update_nodes[i];
 172     GNUNET_CONTAINER_meta_data_destroy (nsn->md);
 173     GNUNET_FS_uri_destroy (nsn->uri);
 174     GNUNET_free (nsn->id);
 175     GNUNET_free (nsn->update);
 176     GNUNET_free (nsn);
 177   }
 178   GNUNET_array_grow (uig->update_nodes, uig->update_node_count,
 179                      0);
 180   if (NULL != uig->update_map)
 181     GNUNET_CONTAINER_multihashmap_destroy (uig->update_map);
 182   GNUNET_free (uig);
 183 }
 184
 185
 186 /**
 187  * Write a namespace's update node graph to a file.
 188  *
 189  * @param uig update information graph to dump
 190  */
 191 static void
 192 write_update_information_graph (struct GNUNET_FS_UpdateInformationGraph *uig)
 193 {
 194   char *fn;
 195   struct GNUNET_BIO_WriteHandle *wh;
 196   unsigned int i;
 197   struct NamespaceUpdateNode *n;
 198   char *uris;
 199
 200   fn = get_update_information_directory (uig->h,
 201                                          &uig->ns);
 202   wh = GNUNET_BIO_write_open (fn);
 203   if (NULL == wh)
 204   {
 205     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 206                 _("Failed to open `%s' for writing: %s\n"), STRERROR (errno));
 207     GNUNET_free (fn);
 208     return;
 209   }
 210   if (GNUNET_OK != GNUNET_BIO_write_int32 (wh, uig->update_node_count))
 211     goto END;
 212   for (i = 0; i < uig->update_node_count; i++)
 213   {
 214     n = uig->update_nodes[i];
 215     uris = GNUNET_FS_uri_to_string (n->uri);
 216     if ((GNUNET_OK != GNUNET_BIO_write_string (wh, n->id)) ||
 217         (GNUNET_OK != GNUNET_BIO_write_meta_data (wh, n->md)) ||
 218         (GNUNET_OK != GNUNET_BIO_write_string (wh, n->update)) ||
 219         (GNUNET_OK != GNUNET_BIO_write_string (wh, uris)))
 220     {
 221       GNUNET_free (uris);
 222       break;
 223     }
 224     GNUNET_free (uris);
 225   }
 226 END:
 227   if (GNUNET_OK != GNUNET_BIO_write_close (wh))
 228     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to write `%s': %s\n"),
 229                 STRERROR (errno));
 230   GNUNET_free (fn);
 231 }
 232
 233
 234 /**
 235  * Read the namespace update node graph from a file.
 236  *
 237  * @param h FS handle to use
 238  * @param ns namespace to read
 239  * @return update graph, never NULL
 240  */
 241 static struct GNUNET_FS_UpdateInformationGraph *
 242 read_update_information_graph (struct GNUNET_FS_Handle *h,
 243                                const struct GNUNET_CRYPTO_EccPrivateKey *ns)
 244 {
 245   struct GNUNET_FS_UpdateInformationGraph *uig;
 246   char *fn;
 247   struct GNUNET_BIO_ReadHandle *rh;
 248   unsigned int i;
 249   struct NamespaceUpdateNode *n;
 250   char *uris;
 251   uint32_t count;
 252   char *emsg;
 253
 254   uig = GNUNET_new (struct GNUNET_FS_UpdateInformationGraph);
 255   uig->h = h;
 256   uig->ns = *ns;
 257   fn = get_update_information_directory (h, ns);
 258   if (GNUNET_YES != GNUNET_DISK_file_test (fn))
 259   {
 260     GNUNET_free (fn);
 261     return uig;
 262   }
 263   rh = GNUNET_BIO_read_open (fn);
 264   if (NULL == rh)
 265   {
 266     GNUNET_free (fn);
 267     return uig;
 268   }
 269   if (GNUNET_OK != GNUNET_BIO_read_int32 (rh, &count))
 270   {
 271     GNUNET_break (0);
 272     goto END;
 273   }
 274   if (count > 1024 * 1024)
 275   {
 276     GNUNET_break (0);
 277     goto END;
 278   }
 279   if (0 == count)
 280     goto END;
 281   uig->update_nodes =
 282     GNUNET_malloc (count * sizeof (struct NamespaceUpdateNode *));
 283
 284   for (i = 0; i < count; i++)
 285   {
 286     n = GNUNET_new (struct NamespaceUpdateNode);
 287     if ((GNUNET_OK != GNUNET_BIO_read_string (rh, "identifier", &n->id, 1024))
 288         || (GNUNET_OK != GNUNET_BIO_read_meta_data (rh, "meta", &n->md)) ||
 289         (GNUNET_OK !=
 290          GNUNET_BIO_read_string (rh, "update-id", &n->update, 1024)) ||
 291         (GNUNET_OK != GNUNET_BIO_read_string (rh, "uri", &uris, 1024 * 2)))
 292     {
 293       GNUNET_break (0);
 294       GNUNET_free_non_null (n->id);
 295       GNUNET_free_non_null (n->update);
 296       if (n->md != NULL)
 297         GNUNET_CONTAINER_meta_data_destroy (n->md);
 298       GNUNET_free (n);
 299       break;
 300     }
 301     n->uri = GNUNET_FS_uri_parse (uris, &emsg);
 302     GNUNET_free (uris);
 303     if (n->uri == NULL)
 304     {
 305       GNUNET_break (0);
 306       GNUNET_free (emsg);
 307       GNUNET_free (n->id);
 308       GNUNET_free_non_null (n->update);
 309       GNUNET_CONTAINER_meta_data_destroy (n->md);
 310       GNUNET_free (n);
 311       break;
 312     }
 313     uig->update_nodes[i] = n;
 314   }
 315   uig->update_node_count = i;
 316  END:
 317   if (GNUNET_OK != GNUNET_BIO_read_close (rh, &emsg))
 318   {
 319     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to read `%s': %s\n"),
 320                 fn, emsg);
 321     GNUNET_free (emsg);
 322   }
 323   GNUNET_free (fn);
 324   return uig;
 325 }
 326
 327
 328 /**
 329  * Context for the SKS publication.
 330  */
 331 struct GNUNET_FS_PublishSksContext
 332 {
 333
 334   /**
 335    * URI of the new entry in the namespace.
 336    */
 337   struct GNUNET_FS_Uri *uri;
 338
 339   /**
 340    * Namespace update node to add to namespace on success (or to be
 341    * deleted if publishing failed).
 342    */
 343   struct NamespaceUpdateNode *nsn;
 344
 345   /**
 346    * Namespace we're publishing to.
 347    */
 348   struct GNUNET_CRYPTO_EccPrivateKey ns;
 349
 350   /**
 351    * Handle to the datastore.
 352    */
 353   struct GNUNET_DATASTORE_Handle *dsh;
 354
 355   /**
 356    * Handle to FS.
 357    */
 358   struct GNUNET_FS_Handle *h;
 359
 360   /**
 361    * Function to call once we're done.
 362    */
 363   GNUNET_FS_PublishContinuation cont;
 364
 365   /**
 366    * Closure for cont.
 367    */
 368   void *cont_cls;
 369
 370   /**
 371    * Handle for our UBlock operation request.
 372    */
 373   struct GNUNET_FS_PublishUblockContext *uc;
 374 };
 375
 376
 377 /**
 378  * Function called by the UBlock construction with
 379  * the result from the PUT (UBlock) request.
 380  *
 381  * @param cls closure of type "struct GNUNET_FS_PublishSksContext*"
 382  * @param msg error message (or NULL)
 383  */
 384 static void
 385 sks_publish_cont (void *cls,
 386                   const char *msg)
 387 {
 388   struct GNUNET_FS_PublishSksContext *psc = cls;
 389   struct GNUNET_FS_UpdateInformationGraph *uig;
 390
 391   psc->uc = NULL;
 392   if (NULL != msg)
 393   {
 394     if (NULL != psc->cont)
 395       psc->cont (psc->cont_cls, NULL, msg);
 396     GNUNET_FS_publish_sks_cancel (psc);
 397     return;
 398   }
 399   if (NULL != psc->nsn)
 400   {
 401     /* FIXME: this can be done much more
 402      * efficiently by simply appending to the
 403      * file and overwriting the 4-byte header */
 404     uig = read_update_information_graph (psc->h,
 405                                          &psc->ns);
 406     GNUNET_array_append (uig->update_nodes,
 407                          uig->update_node_count,
 408                          psc->nsn);
 409     psc->nsn = NULL;
 410     write_update_information_graph (uig);
 411     free_update_information_graph (uig);
 412   }
 413   if (NULL != psc->cont)
 414     psc->cont (psc->cont_cls, psc->uri, NULL);
 415   GNUNET_FS_publish_sks_cancel (psc);
 416 }
 417
 418
 419 /**
 420  * Publish an SBlock on GNUnet.
 421  *
 422  * @param h handle to the file sharing subsystem
 423  * @param ns namespace to publish in
 424  * @param identifier identifier to use
 425  * @param update update identifier to use
 426  * @param meta metadata to use
 427  * @param uri URI to refer to in the SBlock
 428  * @param bo block options
 429  * @param options publication options
 430  * @param cont continuation
 431  * @param cont_cls closure for cont
 432  * @return NULL on error ('cont' will still be called)
 433  */
 434 struct GNUNET_FS_PublishSksContext *
 435 GNUNET_FS_publish_sks (struct GNUNET_FS_Handle *h,
 436                        const struct GNUNET_CRYPTO_EccPrivateKey *ns,
 437                        const char *identifier, const char *update,
 438                        const struct GNUNET_CONTAINER_MetaData *meta,
 439                        const struct GNUNET_FS_Uri *uri,
 440                        const struct GNUNET_FS_BlockOptions *bo,
 441                        enum GNUNET_FS_PublishOptions options,
 442                        GNUNET_FS_PublishContinuation cont, void *cont_cls)
 443 {
 444   struct GNUNET_FS_PublishSksContext *psc;
 445   struct GNUNET_FS_Uri *sks_uri;
 446
 447   sks_uri = GNUNET_new (struct GNUNET_FS_Uri);
 448   sks_uri->type = GNUNET_FS_URI_SKS;
 449   sks_uri->data.sks.identifier = GNUNET_strdup (identifier);
 450   GNUNET_CRYPTO_ecc_key_get_public (ns,
 451                                     &sks_uri->data.sks.ns);
 452
 453   psc = GNUNET_new (struct GNUNET_FS_PublishSksContext);
 454   psc->h = h;
 455   psc->uri = sks_uri;
 456   psc->cont = cont;
 457   psc->cont_cls = cont_cls;
 458   psc->ns = *ns;
 459   if (0 == (options & GNUNET_FS_PUBLISH_OPTION_SIMULATE_ONLY))
 460   {
 461     psc->dsh = GNUNET_DATASTORE_connect (h->cfg);
 462     if (NULL == psc->dsh)
 463     {
 464       sks_publish_cont (psc,
 465                         _("Failed to connect to datastore."));
 466       return NULL;
 467     }
 468   }
 469   if (NULL != update)
 470   {
 471     psc->nsn = GNUNET_new (struct NamespaceUpdateNode);
 472     psc->nsn->id = GNUNET_strdup (identifier);
 473     psc->nsn->update = GNUNET_strdup (update);
 474     psc->nsn->md = GNUNET_CONTAINER_meta_data_duplicate (meta);
 475     psc->nsn->uri = GNUNET_FS_uri_dup (uri);
 476   }
 477   psc->uc = GNUNET_FS_publish_ublock_ (h,
 478                                        psc->dsh,
 479                                        identifier,
 480                                        update,
 481                                        ns,
 482                                        meta,
 483                                        uri,
 484                                        bo,
 485                                        options,
 486                                        &sks_publish_cont,
 487                                        psc);
 488   return psc;
 489 }
 490
 491
 492 /**
 493  * Abort the SKS publishing operation.
 494  *
 495  * @param psc context of the operation to abort.
 496  */
 497 void
 498 GNUNET_FS_publish_sks_cancel (struct GNUNET_FS_PublishSksContext *psc)
 499 {
 500   if (NULL != psc->uc)
 501   {
 502     GNUNET_FS_publish_ublock_cancel_ (psc->uc);
 503     psc->uc = NULL;
 504   }
 505   if (NULL != psc->dsh)
 506   {
 507     GNUNET_DATASTORE_disconnect (psc->dsh, GNUNET_NO);
 508     psc->dsh = NULL;
 509   }
 510   GNUNET_FS_uri_destroy (psc->uri);
 511   if (NULL != psc->nsn)
 512   {
 513     GNUNET_CONTAINER_meta_data_destroy (psc->nsn->md);
 514     GNUNET_FS_uri_destroy (psc->nsn->uri);
 515     GNUNET_free (psc->nsn->id);
 516     GNUNET_free (psc->nsn->update);
 517     GNUNET_free (psc->nsn);
 518   }
 519   GNUNET_free (psc);
 520 }
 521
 522
 523 /**
 524  * Closure for 'process_update_node'.
 525  */
 526 struct ProcessUpdateClosure
 527 {
 528   /**
 529    * Function to call for each node.
 530    */
 531   GNUNET_FS_IdentifierProcessor ip;
 532
 533   /**
 534    * Closure for 'ip'.
 535    */
 536   void *ip_cls;
 537 };
 538
 539
 540 /**
 541  * Call the iterator in the closure for each node.
 542  *
 543  * @param cls closure (of type 'struct ProcessUpdateClosure *')
 544  * @param key current key code
 545  * @param value value in the hash map (of type 'struct NamespaceUpdateNode *')
 546  * @return GNUNET_YES if we should continue to
 547  *         iterate,
 548  *         GNUNET_NO if not.
 549  */
 550 static int
 551 process_update_node (void *cls,
 552                      const struct GNUNET_HashCode *key,
 553                      void *value)
 554 {
 555   struct ProcessUpdateClosure *pc = cls;
 556   struct NamespaceUpdateNode *nsn = value;
 557
 558   pc->ip (pc->ip_cls,
 559           nsn->id,
 560           nsn->uri,
 561           nsn->md,
 562           nsn->update);
 563   return GNUNET_YES;
 564 }
 565
 566
 567 /**
 568  * Closure for 'find_trees'.
 569  */
 570 struct FindTreeClosure
 571 {
 572   /**
 573    * UIG we are operating on.
 574    */
 575   struct GNUNET_FS_UpdateInformationGraph *uig;
 576
 577   /**
 578    * Array with 'head's of TREEs.
 579    */
 580   struct NamespaceUpdateNode **tree_array;
 581
 582   /**
 583    * Size of 'tree_array'
 584    */
 585   unsigned int tree_array_size;
 586
 587   /**
 588    * Current generational ID used.
 589    */
 590   unsigned int nug;
 591
 592   /**
 593    * Identifier for the current TREE, or UINT_MAX for none yet.
 594    */
 595   unsigned int id;
 596 };
 597
 598
 599 /**
 600  * Find all nodes reachable from the current node (including the
 601  * current node itself).  If they are in no tree, add them to the
 602  * current one.   If they are the head of another tree, merge the
 603  * trees.  If they are in the middle of another tree, let them be.
 604  * We can tell that a node is already in an tree by checking if
 605  * its 'nug' field is set to the current 'nug' value.  It is the
 606  * head of an tree if it is in the 'tree_array' under its respective
 607  * 'tree_id'.
 608  *
 609  * In short, we're trying to find the smallest number of tree to
 610  * cover a directed graph.
 611  *
 612  * @param cls closure (of type 'struct FindTreeClosure')
 613  * @param key current key code
 614  * @param value value in the hash map
 615  * @return GNUNET_YES if we should continue to
 616  *         iterate,
 617  *         GNUNET_NO if not.
 618  */
 619 static int
 620 find_trees (void *cls,
 621             const struct GNUNET_HashCode *key,
 622             void *value)
 623 {
 624   struct FindTreeClosure *fc = cls;
 625   struct NamespaceUpdateNode *nsn = value;
 626   struct GNUNET_HashCode hc;
 627
 628   if (nsn->nug == fc->nug)
 629   {
 630     if (UINT_MAX == nsn->tree_id)
 631       return GNUNET_YES;        /* circular */
 632     GNUNET_assert (nsn->tree_id < fc->tree_array_size);
 633     if (fc->tree_array[nsn->tree_id] != nsn)
 634       return GNUNET_YES;        /* part of "another" (directed) TREE,
 635                                  * and not root of it, end trace */
 636     if (nsn->tree_id == fc->id)
 637       return GNUNET_YES;        /* that's our own root (can this be?) */
 638     /* merge existing TREE, we have a root for both */
 639     fc->tree_array[nsn->tree_id] = NULL;
 640     if (UINT_MAX == fc->id)
 641       fc->id = nsn->tree_id;    /* take over ID */
 642   }
 643   else
 644   {
 645     nsn->nug = fc->nug;
 646     nsn->tree_id = UINT_MAX;    /* mark as undef */
 647     /* trace */
 648     GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
 649     GNUNET_CONTAINER_multihashmap_get_multiple (fc->uig->update_map, &hc,
 650                                                 &find_trees, fc);
 651   }
 652   return GNUNET_YES;
 653 }
 654
 655
 656 /**
 657  * List all of the identifiers in the namespace for which we could
 658  * produce an update.  Namespace updates form a graph where each node
 659  * has a name.  Each node can have any number of URI/meta-data entries
 660  * which can each be linked to other nodes.  Cycles are possible.
 661  *
 662  * Calling this function with "next_id" NULL will cause the library to
 663  * call "ip" with a root for each strongly connected component of the
 664  * graph (a root being a node from which all other nodes in the Tree
 665  * are reachable).
 666  *
 667  * Calling this function with "next_id" being the name of a node will
 668  * cause the library to call "ip" with all children of the node.  Note
 669  * that cycles within the final tree are possible (including self-loops).
 670  * I know, odd definition of a tree, but the GUI will display an actual
 671  * tree (GtkTreeView), so that's what counts for the term here.
 672  *
 673  * @param h fs handle to use
 674  * @param ns namespace to inspect for updateable content
 675  * @param next_id ID to look for; use NULL to look for tree roots
 676  * @param ip function to call on each updateable identifier
 677  * @param ip_cls closure for ip
 678  */
 679 void
 680 GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Handle *h,
 681                                      const struct GNUNET_CRYPTO_EccPrivateKey *ns,
 682                                      const char *next_id,
 683                                      GNUNET_FS_IdentifierProcessor ip,
 684                                      void *ip_cls)
 685 {
 686   unsigned int i;
 687   unsigned int nug;
 688   struct GNUNET_HashCode hc;
 689   struct NamespaceUpdateNode *nsn;
 690   struct ProcessUpdateClosure pc;
 691   struct FindTreeClosure fc;
 692   struct GNUNET_FS_UpdateInformationGraph *uig;
 693
 694   uig = read_update_information_graph (h, ns);
 695   if (NULL == uig->update_nodes)
 696   {
 697     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 698                 "No updateable nodes found for ID `%s'\n", next_id);
 699     free_update_information_graph (uig);
 700     return;                     /* no nodes */
 701   }
 702   uig->update_map =
 703     GNUNET_CONTAINER_multihashmap_create (2 +
 704                                           3 * uig->update_node_count /
 705                                           4,
 706                                           GNUNET_NO);
 707   for (i = 0; i < uig->update_node_count; i++)
 708   {
 709     nsn = uig->update_nodes[i];
 710     GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc);
 711     GNUNET_CONTAINER_multihashmap_put (uig->update_map, &hc, nsn,
 712                                        GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
 713   }
 714   if (NULL != next_id)
 715   {
 716     GNUNET_CRYPTO_hash (next_id, strlen (next_id), &hc);
 717     pc.ip = ip;
 718     pc.ip_cls = ip_cls;
 719     GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
 720                                                 &process_update_node, &pc);
 721     free_update_information_graph (uig);
 722     return;
 723   }
 724   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 725               "Calculating TREEs to find roots of update trees\n");
 726   /* Find heads of TREEs in update graph */
 727   nug = ++uig->nug_gen;
 728   fc.tree_array = NULL;
 729   fc.tree_array_size = 0;
 730
 731   for (i = 0; i < uig->update_node_count; i++)
 732   {
 733     nsn = uig->update_nodes[i];
 734     if (nsn->nug == nug)
 735     {
 736       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TREE of node `%s' is %u\n", nsn->id,
 737                   nsn->nug);
 738       continue;                 /* already placed in TREE */
 739     }
 740     GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
 741     nsn->nug = nug;
 742     nsn->tree_id = UINT_MAX;
 743     fc.id = UINT_MAX;
 744     fc.nug = nug;
 745     fc.uig = uig;
 746     GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
 747                                                 &find_trees, &fc);
 748     if (UINT_MAX == fc.id)
 749     {
 750       /* start new TREE */
 751       for (fc.id = 0; fc.id < fc.tree_array_size; fc.id++)
 752       {
 753         if (NULL == fc.tree_array[fc.id])
 754         {
 755           fc.tree_array[fc.id] = nsn;
 756           nsn->tree_id = fc.id;
 757           break;
 758         }
 759       }
 760       if (fc.id == fc.tree_array_size)
 761       {
 762         GNUNET_array_append (fc.tree_array, fc.tree_array_size, nsn);
 763         nsn->tree_id = fc.id;
 764       }
 765       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 766                   "Starting new TREE %u with node `%s'\n", nsn->tree_id,
 767                   nsn->id);
 768       /* put all nodes with same identifier into this TREE */
 769       GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc);
 770       fc.id = nsn->tree_id;
 771       fc.nug = nug;
 772       fc.uig = uig;
 773       GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
 774                                                   &find_trees, &fc);
 775     }
 776     else
 777     {
 778       /* make head of TREE "id" */
 779       fc.tree_array[fc.id] = nsn;
 780       nsn->tree_id = fc.id;
 781     }
 782     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 783                 "TREE of node `%s' is %u\n", nsn->id,
 784                 fc.id);
 785   }
 786   for (i = 0; i < fc.tree_array_size; i++)
 787   {
 788     nsn = fc.tree_array[i];
 789     if (NULL != nsn)
 790     {
 791       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Root of TREE %u is node `%s'\n", i,
 792                   nsn->id);
 793       ip (ip_cls, nsn->id, nsn->uri, nsn->md, nsn->update);
 794     }
 795   }
 796   GNUNET_array_grow (fc.tree_array, fc.tree_array_size, 0);
 797   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Done processing TREEs\n");
 798   free_update_information_graph (uig);
 799 }
 800
 801
 802 /* end of fs_namespace.c */