2 This file is part of GNUnet
3 (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 Christian Grothoff (and other contributing authors)
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.
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.
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.
22 * @file fs/fs_namespace.c
23 * @brief create and destroy namespaces
24 * @author Christian Grothoff
27 #include "gnunet_constants.h"
28 #include "gnunet_signatures.h"
29 #include "gnunet_util_lib.h"
30 #include "gnunet_fs_service.h"
35 * Maximum legal size for an sblock.
37 #define MAX_SBLOCK_SIZE (60 * 1024)
41 * Return the name of the directory in which we store
42 * our local namespaces (or rather, their public keys).
44 * @param h global fs handle
45 * @return NULL on error, otherwise the name of the directory
48 get_namespace_directory (struct GNUNET_FS_Handle *h)
53 GNUNET_CONFIGURATION_get_value_filename (h->cfg, "FS", "IDENTITY_DIR",
56 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
57 _("Configuration fails to specify `%s' in section `%s'\n"),
58 "IDENTITY_DIR", "fs");
66 * Return the name of the directory in which we store
67 * the update information graph for the given local namespace.
69 * @param ns namespace handle
70 * @return NULL on error, otherwise the name of the directory
73 get_update_information_directory (struct GNUNET_FS_Namespace *ns)
79 GNUNET_CONFIGURATION_get_value_filename (ns->h->cfg, "FS", "UPDATE_DIR",
82 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
83 _("Configuration fails to specify `%s' in section `%s'\n"),
87 GNUNET_asprintf (&ret, "%s%s%s", dn, DIR_SEPARATOR_STR, ns->name);
94 * Write the namespace update node graph to a file.
96 * @param ns namespace to dump
99 write_update_information_graph (struct GNUNET_FS_Namespace *ns)
102 struct GNUNET_BIO_WriteHandle *wh;
104 struct NamespaceUpdateNode *n;
107 fn = get_update_information_directory (ns);
108 wh = GNUNET_BIO_write_open (fn);
111 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
112 _("Failed to open `%s' for writing: %s\n"), STRERROR (errno));
116 if (GNUNET_OK != GNUNET_BIO_write_int32 (wh, ns->update_node_count))
118 for (i = 0; i < ns->update_node_count; i++)
120 n = ns->update_nodes[i];
121 uris = GNUNET_FS_uri_to_string (n->uri);
122 if ((GNUNET_OK != GNUNET_BIO_write_string (wh, n->id)) ||
123 (GNUNET_OK != GNUNET_BIO_write_meta_data (wh, n->md)) ||
124 (GNUNET_OK != GNUNET_BIO_write_string (wh, n->update)) ||
125 (GNUNET_OK != GNUNET_BIO_write_string (wh, uris)))
133 if (GNUNET_OK != GNUNET_BIO_write_close (wh))
134 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to write `%s': %s\n"),
141 * Read the namespace update node graph from a file.
143 * @param ns namespace to read
146 read_update_information_graph (struct GNUNET_FS_Namespace *ns)
149 struct GNUNET_BIO_ReadHandle *rh;
151 struct NamespaceUpdateNode *n;
156 fn = get_update_information_directory (ns);
157 if (GNUNET_YES != GNUNET_DISK_file_test (fn))
162 rh = GNUNET_BIO_read_open (fn);
168 if (GNUNET_OK != GNUNET_BIO_read_int32 (rh, &count))
173 if (count > 1024 * 1024)
180 GNUNET_break (GNUNET_OK == GNUNET_BIO_read_close (rh, NULL));
185 GNUNET_malloc (count * sizeof (struct NamespaceUpdateNode *));
187 for (i = 0; i < count; i++)
189 n = GNUNET_malloc (sizeof (struct NamespaceUpdateNode));
190 if ((GNUNET_OK != GNUNET_BIO_read_string (rh, "identifier", &n->id, 1024))
191 || (GNUNET_OK != GNUNET_BIO_read_meta_data (rh, "meta", &n->md)) ||
193 GNUNET_BIO_read_string (rh, "update-id", &n->update, 1024)) ||
194 (GNUNET_OK != GNUNET_BIO_read_string (rh, "uri", &uris, 1024 * 2)))
197 GNUNET_free_non_null (n->id);
198 GNUNET_free_non_null (n->update);
200 GNUNET_CONTAINER_meta_data_destroy (n->md);
204 n->uri = GNUNET_FS_uri_parse (uris, &emsg);
211 GNUNET_free_non_null (n->update);
212 GNUNET_CONTAINER_meta_data_destroy (n->md);
216 ns->update_nodes[i] = n;
218 ns->update_node_count = i;
220 if (GNUNET_OK != GNUNET_BIO_read_close (rh, &emsg))
222 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to write `%s': %s\n"), emsg);
230 * Create a namespace with the given name; if one already
231 * exists, return a handle to the existing namespace.
233 * @param h handle to the file sharing subsystem
234 * @param name name to use for the namespace
235 * @return handle to the namespace, NULL on error (i.e. invalid filename)
237 struct GNUNET_FS_Namespace *
238 GNUNET_FS_namespace_create (struct GNUNET_FS_Handle *h, const char *name)
242 struct GNUNET_FS_Namespace *ret;
244 dn = get_namespace_directory (h);
245 GNUNET_asprintf (&fn, "%s%s%s", dn, DIR_SEPARATOR_STR, name);
247 ret = GNUNET_malloc (sizeof (struct GNUNET_FS_Namespace));
250 ret->key = GNUNET_CRYPTO_rsa_key_create_from_file (fn);
251 if (NULL == ret->key)
253 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
254 _("Failed to create or read private key for namespace `%s'\n"),
260 ret->name = GNUNET_strdup (name);
267 * Duplicate a namespace handle.
269 * @param ns namespace handle
270 * @return duplicated handle to the namespace
272 struct GNUNET_FS_Namespace *
273 GNUNET_FS_namespace_dup (struct GNUNET_FS_Namespace *ns)
281 * Delete a namespace handle. Can be used for a clean shutdown (free
282 * memory) or also to freeze the namespace to prevent further
283 * insertions by anyone.
285 * @param namespace handle to the namespace that should be deleted / freed
286 * @param freeze prevents future insertions; creating a namespace
287 * with the same name again will create a fresh namespace instead
289 * @return GNUNET_OK on success, GNUNET_SYSERR on error
292 GNUNET_FS_namespace_delete (struct GNUNET_FS_Namespace *namespace, int freeze)
295 struct NamespaceUpdateNode *nsn;
300 if (0 != UNLINK (namespace->filename))
301 GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_ERROR, "unlink",
302 namespace->filename);
304 if (0 != namespace->rc)
306 GNUNET_CRYPTO_rsa_key_free (namespace->key);
307 GNUNET_free (namespace->filename);
308 GNUNET_free (namespace->name);
309 for (i = 0; i < namespace->update_node_count; i++)
311 nsn = namespace->update_nodes[i];
312 GNUNET_CONTAINER_meta_data_destroy (nsn->md);
313 GNUNET_FS_uri_destroy (nsn->uri);
314 GNUNET_free (nsn->id);
315 GNUNET_free (nsn->update);
318 GNUNET_array_grow (namespace->update_nodes, namespace->update_node_count,
320 if (namespace->update_map != NULL)
321 GNUNET_CONTAINER_multihashmap_destroy (namespace->update_map);
322 GNUNET_free (namespace);
328 * Context for the 'process_namespace' callback.
329 * Specifies a function to call on each namespace.
331 struct ProcessNamespaceContext
336 GNUNET_FS_NamespaceInfoProcessor cb;
346 * Function called with a filename of a namespace. Reads the key and
347 * calls the callback.
349 * @param cls closure (struct ProcessNamespaceContext)
350 * @param filename complete filename (absolute path)
351 * @return GNUNET_OK to continue to iterate,
352 * GNUNET_SYSERR to abort iteration with error!
355 process_namespace (void *cls, const char *filename)
357 struct ProcessNamespaceContext *pnc = cls;
358 struct GNUNET_CRYPTO_RsaPrivateKey *key;
359 struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded pk;
360 struct GNUNET_HashCode id;
364 key = GNUNET_CRYPTO_rsa_key_create_from_file (filename);
367 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
369 ("Failed to read namespace private key file `%s', deleting it!\n"),
371 if (0 != UNLINK (filename))
372 GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING, "unlink", filename);
375 GNUNET_CRYPTO_rsa_key_get_public (key, &pk);
376 GNUNET_CRYPTO_rsa_key_free (key);
377 GNUNET_CRYPTO_hash (&pk, sizeof (pk), &id);
379 while (NULL != (t = strstr (name, DIR_SEPARATOR_STR)))
381 pnc->cb (pnc->cb_cls, name, &id);
387 * Build a list of all available local (!) namespaces The returned
388 * names are only the nicknames since we only iterate over the local
391 * @param h handle to the file sharing subsystem
392 * @param cb function to call on each known namespace
393 * @param cb_cls closure for cb
396 GNUNET_FS_namespace_list (struct GNUNET_FS_Handle *h,
397 GNUNET_FS_NamespaceInfoProcessor cb, void *cb_cls)
400 struct ProcessNamespaceContext ctx;
402 dn = get_namespace_directory (h);
407 GNUNET_DISK_directory_scan (dn, &process_namespace, &ctx);
413 * Context for the SKS publication.
415 struct GNUNET_FS_PublishSksContext
419 * URI of the new entry in the namespace.
421 struct GNUNET_FS_Uri *uri;
424 * Namespace update node to add to namespace on success (or to be
425 * deleted if publishing failed).
427 struct NamespaceUpdateNode *nsn;
430 * Namespace we're publishing to.
432 struct GNUNET_FS_Namespace *namespace;
435 * Handle to the datastore.
437 struct GNUNET_DATASTORE_Handle *dsh;
440 * Function to call once we're done.
442 GNUNET_FS_PublishContinuation cont;
450 * Handle for our datastore request.
452 struct GNUNET_DATASTORE_QueueEntry *dqe;
457 * Function called by the datastore API with
458 * the result from the PUT (SBlock) request.
460 * @param cls closure of type "struct GNUNET_FS_PublishSksContext*"
461 * @param success GNUNET_OK on success
462 * @param min_expiration minimum expiration time required for content to be stored
463 * @param msg error message (or NULL)
466 sb_put_cont (void *cls, int success,
467 struct GNUNET_TIME_Absolute min_expiration,
470 struct GNUNET_FS_PublishSksContext *psc = cls;
471 struct GNUNET_HashCode hc;
474 if (GNUNET_OK != success)
476 if (NULL != psc->cont)
477 psc->cont (psc->cont_cls, NULL, msg);
478 GNUNET_FS_publish_sks_cancel (psc);
481 if (NULL != psc->nsn)
483 /* FIXME: this can be done much more
484 * efficiently by simply appending to the
485 * file and overwriting the 4-byte header */
486 if (psc->namespace->update_nodes == NULL)
487 read_update_information_graph (psc->namespace);
488 GNUNET_array_append (psc->namespace->update_nodes,
489 psc->namespace->update_node_count, psc->nsn);
490 if (psc->namespace->update_map != NULL)
492 GNUNET_CRYPTO_hash (psc->nsn->id, strlen (psc->nsn->id), &hc);
493 GNUNET_CONTAINER_multihashmap_put (psc->namespace->update_map, &hc,
495 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
498 write_update_information_graph (psc->namespace);
500 if (NULL != psc->cont)
501 psc->cont (psc->cont_cls, psc->uri, NULL);
502 GNUNET_FS_publish_sks_cancel (psc);
507 * Publish an SBlock on GNUnet.
509 * @param h handle to the file sharing subsystem
510 * @param namespace namespace to publish in
511 * @param identifier identifier to use
512 * @param update update identifier to use
513 * @param meta metadata to use
514 * @param uri URI to refer to in the SBlock
515 * @param bo block options
516 * @param options publication options
517 * @param cont continuation
518 * @param cont_cls closure for cont
519 * @return NULL on error ('cont' will still be called)
521 struct GNUNET_FS_PublishSksContext *
522 GNUNET_FS_publish_sks (struct GNUNET_FS_Handle *h,
523 struct GNUNET_FS_Namespace *namespace,
524 const char *identifier, const char *update,
525 const struct GNUNET_CONTAINER_MetaData *meta,
526 const struct GNUNET_FS_Uri *uri,
527 const struct GNUNET_FS_BlockOptions *bo,
528 enum GNUNET_FS_PublishOptions options,
529 GNUNET_FS_PublishContinuation cont, void *cont_cls)
531 struct GNUNET_FS_PublishSksContext *psc;
532 struct GNUNET_CRYPTO_AesSessionKey sk;
533 struct GNUNET_CRYPTO_AesInitializationVector iv;
534 struct GNUNET_FS_Uri *sks_uri;
542 struct SBlock *sb_enc;
544 struct GNUNET_CONTAINER_MetaData *mmeta;
545 struct GNUNET_HashCode key; /* hash of thisId = key */
546 struct GNUNET_HashCode id; /* hash of hc = identifier */
547 struct GNUNET_HashCode query; /* id ^ nsid = DB query */
550 mmeta = GNUNET_CONTAINER_meta_data_create ();
552 mmeta = GNUNET_CONTAINER_meta_data_duplicate (meta);
553 uris = GNUNET_FS_uri_to_string (uri);
554 slen = strlen (uris) + 1;
555 idlen = strlen (identifier);
557 nidlen = strlen (update) + 1;
560 mdsize = GNUNET_CONTAINER_meta_data_get_serialized_size (mmeta);
561 size = sizeof (struct SBlock) + slen + nidlen + mdsize;
562 if (size > MAX_SBLOCK_SIZE)
564 size = MAX_SBLOCK_SIZE;
565 mdsize = size - (sizeof (struct SBlock) + slen + nidlen);
567 sb = GNUNET_malloc (sizeof (struct SBlock) + size);
568 dest = (char *) &sb[1];
570 memcpy (dest, update, nidlen);
574 memcpy (dest, uris, slen);
578 GNUNET_CONTAINER_meta_data_serialize (mmeta, &dest, mdsize,
579 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART);
580 GNUNET_CONTAINER_meta_data_destroy (mmeta);
586 cont (cont_cls, NULL, _("Internal error."));
589 size = sizeof (struct SBlock) + mdsize + slen + nidlen;
590 sb_enc = GNUNET_malloc (size);
591 GNUNET_CRYPTO_hash (identifier, idlen, &key);
592 GNUNET_CRYPTO_hash (&key, sizeof (struct GNUNET_HashCode), &id);
593 sks_uri = GNUNET_malloc (sizeof (struct GNUNET_FS_Uri));
595 GNUNET_CRYPTO_rsa_key_get_public (namespace->key, &sb_enc->subspace);
596 GNUNET_CRYPTO_hash (&sb_enc->subspace,
597 sizeof (struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded),
598 &sks_uri->data.sks.namespace);
599 sks_uri->data.sks.identifier = GNUNET_strdup (identifier);
600 GNUNET_CRYPTO_hash_xor (&id, &sks_uri->data.sks.namespace,
601 &sb_enc->identifier);
602 GNUNET_CRYPTO_hash_to_aes_key (&key, &sk, &iv);
603 GNUNET_CRYPTO_aes_encrypt (&sb[1], size - sizeof (struct SBlock), &sk, &iv,
605 sb_enc->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_FS_SBLOCK);
606 sb_enc->purpose.size =
607 htonl (slen + mdsize + nidlen + sizeof (struct SBlock) -
608 sizeof (struct GNUNET_CRYPTO_RsaSignature));
609 GNUNET_assert (GNUNET_OK ==
610 GNUNET_CRYPTO_rsa_sign (namespace->key, &sb_enc->purpose,
611 &sb_enc->signature));
612 psc = GNUNET_malloc (sizeof (struct GNUNET_FS_PublishSksContext));
615 psc->namespace = GNUNET_FS_namespace_dup (namespace);
616 psc->cont_cls = cont_cls;
617 if (0 != (options & GNUNET_FS_PUBLISH_OPTION_SIMULATE_ONLY))
619 GNUNET_free (sb_enc);
621 sb_put_cont (psc, GNUNET_OK, GNUNET_TIME_UNIT_ZERO_ABS, NULL);
624 psc->dsh = GNUNET_DATASTORE_connect (h->cfg);
625 if (NULL == psc->dsh)
627 GNUNET_free (sb_enc);
629 sb_put_cont (psc, GNUNET_NO, GNUNET_TIME_UNIT_ZERO_ABS, _("Failed to connect to datastore."));
632 GNUNET_CRYPTO_hash_xor (&sks_uri->data.sks.namespace, &id, &query);
635 psc->nsn = GNUNET_malloc (sizeof (struct NamespaceUpdateNode));
636 psc->nsn->id = GNUNET_strdup (identifier);
637 psc->nsn->update = GNUNET_strdup (update);
638 psc->nsn->md = GNUNET_CONTAINER_meta_data_duplicate (meta);
639 psc->nsn->uri = GNUNET_FS_uri_dup (uri);
641 psc->dqe = GNUNET_DATASTORE_put (psc->dsh, 0, &sb_enc->identifier, size, sb_enc,
642 GNUNET_BLOCK_TYPE_FS_SBLOCK, bo->content_priority,
643 bo->anonymity_level, bo->replication_level,
644 bo->expiration_time, -2, 1,
645 GNUNET_CONSTANTS_SERVICE_TIMEOUT, &sb_put_cont, psc);
647 GNUNET_free (sb_enc);
653 * Abort the SKS publishing operation.
655 * @param psc context of the operation to abort.
658 GNUNET_FS_publish_sks_cancel (struct GNUNET_FS_PublishSksContext *psc)
660 if (NULL != psc->dqe)
662 GNUNET_DATASTORE_cancel (psc->dqe);
665 if (NULL != psc->dsh)
667 GNUNET_DATASTORE_disconnect (psc->dsh, GNUNET_NO);
670 GNUNET_FS_namespace_delete (psc->namespace, GNUNET_NO);
671 GNUNET_FS_uri_destroy (psc->uri);
672 if (NULL != psc->nsn)
674 GNUNET_CONTAINER_meta_data_destroy (psc->nsn->md);
675 GNUNET_FS_uri_destroy (psc->nsn->uri);
676 GNUNET_free (psc->nsn->id);
677 GNUNET_free (psc->nsn->update);
678 GNUNET_free (psc->nsn);
685 * Closure for 'process_update_node'.
687 struct ProcessUpdateClosure
690 * Function to call for each node.
692 GNUNET_FS_IdentifierProcessor ip;
702 * Call the iterator in the closure for each node.
704 * @param cls closure (of type 'struct ProcessUpdateClosure *')
705 * @param key current key code
706 * @param value value in the hash map (of type 'struct NamespaceUpdateNode *')
707 * @return GNUNET_YES if we should continue to
712 process_update_node (void *cls, const struct GNUNET_HashCode * key, void *value)
714 struct ProcessUpdateClosure *pc = cls;
715 struct NamespaceUpdateNode *nsn = value;
717 pc->ip (pc->ip_cls, nsn->id, nsn->uri, nsn->md, nsn->update);
723 * Closure for 'find_trees'.
725 struct FindTreeClosure
728 * Namespace we are operating on.
730 struct GNUNET_FS_Namespace *namespace;
733 * Array with 'head's of TREEs.
735 struct NamespaceUpdateNode **tree_array;
738 * Size of 'tree_array'
740 unsigned int tree_array_size;
743 * Current generational ID used.
748 * Identifier for the current TREE, or UINT_MAX for none yet.
755 * Find all nodes reachable from the current node (including the
756 * current node itself). If they are in no tree, add them to the
757 * current one. If they are the head of another tree, merge the
758 * trees. If they are in the middle of another tree, let them be.
759 * We can tell that a node is already in an tree by checking if
760 * its 'nug' field is set to the current 'nug' value. It is the
761 * head of an tree if it is in the 'tree_array' under its respective
764 * In short, we're trying to find the smallest number of tree to
765 * cover a directed graph.
767 * @param cls closure (of type 'struct FindTreeClosure')
768 * @param key current key code
769 * @param value value in the hash map
770 * @return GNUNET_YES if we should continue to
775 find_trees (void *cls, const struct GNUNET_HashCode * key, void *value)
777 struct FindTreeClosure *fc = cls;
778 struct NamespaceUpdateNode *nsn = value;
779 struct GNUNET_HashCode hc;
781 if (nsn->nug == fc->nug)
783 if (UINT_MAX == nsn->tree_id)
784 return GNUNET_YES; /* circular */
785 GNUNET_assert (nsn->tree_id < fc->tree_array_size);
786 if (fc->tree_array[nsn->tree_id] != nsn)
787 return GNUNET_YES; /* part of "another" (directed) TREE,
788 * and not root of it, end trace */
789 if (nsn->tree_id == fc->id)
790 return GNUNET_YES; /* that's our own root (can this be?) */
791 /* merge existing TREE, we have a root for both */
792 fc->tree_array[nsn->tree_id] = NULL;
793 if (UINT_MAX == fc->id)
794 fc->id = nsn->tree_id; /* take over ID */
799 nsn->tree_id = UINT_MAX; /* mark as undef */
801 GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
802 GNUNET_CONTAINER_multihashmap_get_multiple (fc->namespace->update_map, &hc,
810 * List all of the identifiers in the namespace for which we could
811 * produce an update. Namespace updates form a graph where each node
812 * has a name. Each node can have any number of URI/meta-data entries
813 * which can each be linked to other nodes. Cycles are possible.
815 * Calling this function with "next_id" NULL will cause the library to
816 * call "ip" with a root for each strongly connected component of the
817 * graph (a root being a node from which all other nodes in the Tree
820 * Calling this function with "next_id" being the name of a node will
821 * cause the library to call "ip" with all children of the node. Note
822 * that cycles within the final tree are possible (including self-loops).
823 * I know, odd definition of a tree, but the GUI will display an actual
824 * tree (GtkTreeView), so that's what counts for the term here.
826 * @param namespace namespace to inspect for updateable content
827 * @param next_id ID to look for; use NULL to look for tree roots
828 * @param ip function to call on each updateable identifier
829 * @param ip_cls closure for ip
832 GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Namespace *namespace,
834 GNUNET_FS_IdentifierProcessor ip,
839 struct GNUNET_HashCode hc;
840 struct NamespaceUpdateNode *nsn;
841 struct ProcessUpdateClosure pc;
842 struct FindTreeClosure fc;
844 if (NULL == namespace->update_nodes)
845 read_update_information_graph (namespace);
846 if (NULL == namespace->update_nodes)
848 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
849 "No updateable nodes found for ID `%s'\n", next_id);
850 return; /* no nodes */
852 if (NULL == namespace->update_map)
854 /* need to construct */
855 namespace->update_map =
856 GNUNET_CONTAINER_multihashmap_create (2 +
857 3 * namespace->update_node_count /
859 for (i = 0; i < namespace->update_node_count; i++)
861 nsn = namespace->update_nodes[i];
862 GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc);
863 GNUNET_CONTAINER_multihashmap_put (namespace->update_map, &hc, nsn,
864 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
869 GNUNET_CRYPTO_hash (next_id, strlen (next_id), &hc);
872 GNUNET_CONTAINER_multihashmap_get_multiple (namespace->update_map, &hc,
873 &process_update_node, &pc);
876 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
877 "Calculating TREEs to find roots of update trees\n");
878 /* Find heads of TREEs in update graph */
879 nug = ++namespace->nug_gen;
880 fc.tree_array = NULL;
881 fc.tree_array_size = 0;
883 for (i = 0; i < namespace->update_node_count; i++)
885 nsn = namespace->update_nodes[i];
888 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TREE of node `%s' is %u\n", nsn->id,
890 continue; /* already placed in TREE */
892 GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
894 nsn->tree_id = UINT_MAX;
897 fc.namespace = namespace;
898 GNUNET_CONTAINER_multihashmap_get_multiple (namespace->update_map, &hc,
900 if (UINT_MAX == fc.id)
903 for (fc.id = 0; fc.id < fc.tree_array_size; fc.id++)
905 if (fc.tree_array[fc.id] == NULL)
907 fc.tree_array[fc.id] = nsn;
908 nsn->tree_id = fc.id;
912 if (fc.id == fc.tree_array_size)
914 GNUNET_array_append (fc.tree_array, fc.tree_array_size, nsn);
915 nsn->tree_id = fc.id;
917 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
918 "Starting new TREE %u with node `%s'\n", nsn->tree_id,
920 /* put all nodes with same identifier into this TREE */
921 GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc);
922 fc.id = nsn->tree_id;
924 fc.namespace = namespace;
925 GNUNET_CONTAINER_multihashmap_get_multiple (namespace->update_map, &hc,
930 /* make head of TREE "id" */
931 fc.tree_array[fc.id] = nsn;
932 nsn->tree_id = fc.id;
934 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TREE of node `%s' is %u\n", nsn->id,
937 for (i = 0; i < fc.tree_array_size; i++)
939 nsn = fc.tree_array[i];
942 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Root of TREE %u is node `%s'\n", i,
944 ip (ip_cls, nsn->id, nsn->uri, nsn->md, nsn->update);
947 GNUNET_array_grow (fc.tree_array, fc.tree_array_size, 0);
948 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Done processing TREEs\n");
952 /* end of fs_namespace.c */