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