src/fs/fs_namespace.c

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