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 * Return the name of the directory in which we store
36 * our local namespaces (or rather, their public keys).
38 * @param h global fs handle
39 * @return NULL on error, otherwise the name of the directory
42 get_namespace_directory (struct GNUNET_FS_Handle *h)
47 GNUNET_CONFIGURATION_get_value_filename (h->cfg, "FS", "IDENTITY_DIR",
50 GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR,
51 "fs", "IDENTITY_DIR");
59 * Return the name of the directory in which we store
60 * the update information graph for the given local namespace.
62 * @param ns namespace handle
63 * @return NULL on error, otherwise the name of the directory
66 get_update_information_directory (struct GNUNET_FS_Namespace *ns)
72 GNUNET_CONFIGURATION_get_value_filename (ns->h->cfg, "FS", "UPDATE_DIR",
75 GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR,
79 GNUNET_asprintf (&ret, "%s%s%s", dn, DIR_SEPARATOR_STR, ns->name);
86 * Write the namespace update node graph to a file.
88 * @param ns namespace to dump
91 write_update_information_graph (struct GNUNET_FS_Namespace *ns)
94 struct GNUNET_BIO_WriteHandle *wh;
96 struct NamespaceUpdateNode *n;
99 fn = get_update_information_directory (ns);
100 wh = GNUNET_BIO_write_open (fn);
103 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
104 _("Failed to open `%s' for writing: %s\n"), STRERROR (errno));
108 if (GNUNET_OK != GNUNET_BIO_write_int32 (wh, ns->update_node_count))
110 for (i = 0; i < ns->update_node_count; i++)
112 n = ns->update_nodes[i];
113 uris = GNUNET_FS_uri_to_string (n->uri);
114 if ((GNUNET_OK != GNUNET_BIO_write_string (wh, n->id)) ||
115 (GNUNET_OK != GNUNET_BIO_write_meta_data (wh, n->md)) ||
116 (GNUNET_OK != GNUNET_BIO_write_string (wh, n->update)) ||
117 (GNUNET_OK != GNUNET_BIO_write_string (wh, uris)))
125 if (GNUNET_OK != GNUNET_BIO_write_close (wh))
126 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to write `%s': %s\n"),
133 * Read the namespace update node graph from a file.
135 * @param ns namespace to read
138 read_update_information_graph (struct GNUNET_FS_Namespace *ns)
141 struct GNUNET_BIO_ReadHandle *rh;
143 struct NamespaceUpdateNode *n;
148 fn = get_update_information_directory (ns);
149 if (GNUNET_YES != GNUNET_DISK_file_test (fn))
154 rh = GNUNET_BIO_read_open (fn);
160 if (GNUNET_OK != GNUNET_BIO_read_int32 (rh, &count))
165 if (count > 1024 * 1024)
172 GNUNET_break (GNUNET_OK == GNUNET_BIO_read_close (rh, NULL));
177 GNUNET_malloc (count * sizeof (struct NamespaceUpdateNode *));
179 for (i = 0; i < count; i++)
181 n = GNUNET_malloc (sizeof (struct NamespaceUpdateNode));
182 if ((GNUNET_OK != GNUNET_BIO_read_string (rh, "identifier", &n->id, 1024))
183 || (GNUNET_OK != GNUNET_BIO_read_meta_data (rh, "meta", &n->md)) ||
185 GNUNET_BIO_read_string (rh, "update-id", &n->update, 1024)) ||
186 (GNUNET_OK != GNUNET_BIO_read_string (rh, "uri", &uris, 1024 * 2)))
189 GNUNET_free_non_null (n->id);
190 GNUNET_free_non_null (n->update);
192 GNUNET_CONTAINER_meta_data_destroy (n->md);
196 n->uri = GNUNET_FS_uri_parse (uris, &emsg);
203 GNUNET_free_non_null (n->update);
204 GNUNET_CONTAINER_meta_data_destroy (n->md);
208 ns->update_nodes[i] = n;
210 ns->update_node_count = i;
212 if (GNUNET_OK != GNUNET_BIO_read_close (rh, &emsg))
214 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to write `%s': %s\n"), emsg);
222 * Create a namespace with the given name; if one already
223 * exists, return a handle to the existing namespace.
225 * @param h handle to the file sharing subsystem
226 * @param name name to use for the namespace
227 * @return handle to the namespace, NULL on error (i.e. invalid filename)
229 struct GNUNET_FS_Namespace *
230 GNUNET_FS_namespace_create (struct GNUNET_FS_Handle *h, const char *name)
234 struct GNUNET_FS_Namespace *ret;
236 dn = get_namespace_directory (h);
239 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
240 _("Can't determine where namespace directory is\n"));
243 GNUNET_asprintf (&fn, "%s%s%s", dn, DIR_SEPARATOR_STR, name);
245 ret = GNUNET_malloc (sizeof (struct GNUNET_FS_Namespace));
248 ret->key = GNUNET_FS_pseudonym_create (fn);
249 if (NULL == ret->key)
251 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
252 _("Failed to create or read private key for namespace `%s'\n"),
258 ret->name = GNUNET_strdup (name);
265 * Open the namespace with the given name; if it does not exist,
266 * or the key file is corrupted, the function fails.
268 * @param h handle to the file sharing subsystem
269 * @param name name of the namespace
270 * @return handle to the namespace,
271 * NULL on error (i.e. invalid filename, non-existent filename)
273 struct GNUNET_FS_Namespace *
274 GNUNET_FS_namespace_open_existing (struct GNUNET_FS_Handle *h, const char *name)
278 struct GNUNET_FS_Namespace *ret;
280 dn = get_namespace_directory (h);
283 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
284 _("Can't determine where namespace directory is\n"));
287 GNUNET_asprintf (&fn, "%s%s%s", dn, DIR_SEPARATOR_STR, name);
289 ret = GNUNET_malloc (sizeof (struct GNUNET_FS_Namespace));
292 ret->key = GNUNET_FS_pseudonym_create_from_existing_file (fn);
293 if (NULL == ret->key)
295 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
296 _("Failed to read private key for namespace `%s'\n"), name);
301 ret->name = GNUNET_strdup (name);
308 * Rename a local namespace.
310 * @param h handle to the file sharing subsystem
311 * @param old_name old name of the namespace
312 * @param new_name new name of the namespace
313 * @return GNUNET_OK on success, GNUNET_SYSERR on error (see errno for details)
316 GNUNET_FS_namespace_rename (struct GNUNET_FS_Handle *h,
317 const char *old_name,
318 const char *new_name)
326 dn = get_namespace_directory (h);
329 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
330 _("Can't determine where namespace directory is\n"));
331 return GNUNET_SYSERR;
333 GNUNET_asprintf (&fn_old, "%s%s%s", dn, DIR_SEPARATOR_STR, old_name);
334 GNUNET_asprintf (&fn_new, "%s%s%s", dn, DIR_SEPARATOR_STR, new_name);
336 result = RENAME (fn_old, fn_new);
338 GNUNET_free (fn_old);
339 GNUNET_free (fn_new);
343 return GNUNET_SYSERR;
348 * Duplicate a namespace handle.
350 * @param ns namespace handle
351 * @return duplicated handle to the namespace
353 struct GNUNET_FS_Namespace *
354 GNUNET_FS_namespace_dup (struct GNUNET_FS_Namespace *ns)
362 * Delete a namespace handle. Can be used for a clean shutdown (free
363 * memory) or also to freeze the namespace to prevent further
364 * insertions by anyone.
366 * @param ns handle to the namespace that should be deleted / freed
367 * @param freeze prevents future insertions; creating a namespace
368 * with the same name again will create a fresh namespace instead
370 * @return GNUNET_OK on success, GNUNET_SYSERR on error
373 GNUNET_FS_namespace_delete (struct GNUNET_FS_Namespace *ns, int freeze)
376 struct NamespaceUpdateNode *nsn;
381 if (0 != UNLINK (ns->filename))
382 GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_ERROR, "unlink",
387 GNUNET_FS_pseudonym_destroy (ns->key);
388 GNUNET_free (ns->filename);
389 GNUNET_free (ns->name);
390 for (i = 0; i < ns->update_node_count; i++)
392 nsn = ns->update_nodes[i];
393 GNUNET_CONTAINER_meta_data_destroy (nsn->md);
394 GNUNET_FS_uri_destroy (nsn->uri);
395 GNUNET_free (nsn->id);
396 GNUNET_free (nsn->update);
399 GNUNET_array_grow (ns->update_nodes, ns->update_node_count,
401 if (ns->update_map != NULL)
402 GNUNET_CONTAINER_multihashmap_destroy (ns->update_map);
409 * Context for the 'process_namespace' callback.
410 * Specifies a function to call on each namespace.
412 struct ProcessNamespaceContext
417 GNUNET_FS_NamespaceInfoProcessor cb;
427 * Get hash of the public key of a namespace.
429 * @param ns namespace
430 * @param id buffer to store the key in
431 * @return GNUNET_OK on success
432 * GNUNET_SYSERR on failure (contents of id remain intact)
435 GNUNET_FS_namespace_get_public_identifier (struct GNUNET_FS_Namespace *ns,
436 struct GNUNET_FS_PseudonymIdentifier *id)
438 if ((NULL == ns) || (NULL == id))
439 return GNUNET_SYSERR;
440 GNUNET_FS_pseudonym_get_identifier (ns->key, id);
446 * Function called with a filename of a namespace. Reads the key and
447 * calls the callback.
449 * @param cls closure (struct ProcessNamespaceContext)
450 * @param filename complete filename (absolute path)
451 * @return GNUNET_OK to continue to iterate,
452 * GNUNET_SYSERR to abort iteration with error!
455 process_namespace (void *cls, const char *filename)
457 struct ProcessNamespaceContext *pnc = cls;
458 struct GNUNET_FS_PseudonymHandle *ph;
459 struct GNUNET_FS_PseudonymIdentifier id;
463 if (NULL == (ph = GNUNET_FS_pseudonym_create (filename)))
465 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
467 ("Failed to read namespace private key file `%s', deleting it!\n"),
469 if (0 != UNLINK (filename))
470 GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING, "unlink", filename);
473 GNUNET_FS_pseudonym_get_identifier (ph, &id);
474 GNUNET_FS_pseudonym_destroy (ph);
476 while (NULL != (t = strstr (name, DIR_SEPARATOR_STR)))
478 pnc->cb (pnc->cb_cls, name, &id);
484 * Build a list of all available local (!) namespaces The returned
485 * names are only the nicknames since we only iterate over the local
488 * @param h handle to the file sharing subsystem
489 * @param cb function to call on each known namespace
490 * @param cb_cls closure for cb
493 GNUNET_FS_namespace_list (struct GNUNET_FS_Handle *h,
494 GNUNET_FS_NamespaceInfoProcessor cb, void *cb_cls)
497 struct ProcessNamespaceContext ctx;
499 dn = get_namespace_directory (h);
504 GNUNET_DISK_directory_scan (dn, &process_namespace, &ctx);
510 * Context for the SKS publication.
512 struct GNUNET_FS_PublishSksContext
516 * URI of the new entry in the namespace.
518 struct GNUNET_FS_Uri *uri;
521 * Namespace update node to add to namespace on success (or to be
522 * deleted if publishing failed).
524 struct NamespaceUpdateNode *nsn;
527 * Namespace we're publishing to.
529 struct GNUNET_FS_Namespace *ns;
532 * Handle to the datastore.
534 struct GNUNET_DATASTORE_Handle *dsh;
537 * Function to call once we're done.
539 GNUNET_FS_PublishContinuation cont;
547 * Handle for our datastore request.
549 struct GNUNET_DATASTORE_QueueEntry *dqe;
554 * Function called by the datastore API with
555 * the result from the PUT (UBlock) request.
557 * @param cls closure of type "struct GNUNET_FS_PublishSksContext*"
558 * @param success GNUNET_OK on success
559 * @param min_expiration minimum expiration time required for content to be stored
560 * @param msg error message (or NULL)
563 sb_put_cont (void *cls, int success,
564 struct GNUNET_TIME_Absolute min_expiration,
567 struct GNUNET_FS_PublishSksContext *psc = cls;
568 struct GNUNET_HashCode hc;
571 if (GNUNET_OK != success)
573 if (NULL != psc->cont)
574 psc->cont (psc->cont_cls, NULL, msg);
575 GNUNET_FS_publish_sks_cancel (psc);
578 if (NULL != psc->nsn)
580 /* FIXME: this can be done much more
581 * efficiently by simply appending to the
582 * file and overwriting the 4-byte header */
583 if (psc->ns->update_nodes == NULL)
584 read_update_information_graph (psc->ns);
585 GNUNET_array_append (psc->ns->update_nodes,
586 psc->ns->update_node_count, psc->nsn);
587 if (NULL != psc->ns->update_map)
589 GNUNET_CRYPTO_hash (psc->nsn->id, strlen (psc->nsn->id), &hc);
590 GNUNET_CONTAINER_multihashmap_put (psc->ns->update_map, &hc,
592 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
595 write_update_information_graph (psc->ns);
597 if (NULL != psc->cont)
598 psc->cont (psc->cont_cls, psc->uri, NULL);
599 GNUNET_FS_publish_sks_cancel (psc);
604 * Publish an SBlock on GNUnet.
606 * @param h handle to the file sharing subsystem
607 * @param ns namespace to publish in
608 * @param identifier identifier to use
609 * @param update update identifier to use
610 * @param meta metadata to use
611 * @param uri URI to refer to in the SBlock
612 * @param bo block options
613 * @param options publication options
614 * @param cont continuation
615 * @param cont_cls closure for cont
616 * @return NULL on error ('cont' will still be called)
618 struct GNUNET_FS_PublishSksContext *
619 GNUNET_FS_publish_sks (struct GNUNET_FS_Handle *h,
620 struct GNUNET_FS_Namespace *ns,
621 const char *identifier, const char *update,
622 const struct GNUNET_CONTAINER_MetaData *meta,
623 const struct GNUNET_FS_Uri *uri,
624 const struct GNUNET_FS_BlockOptions *bo,
625 enum GNUNET_FS_PublishOptions options,
626 GNUNET_FS_PublishContinuation cont, void *cont_cls)
628 struct GNUNET_FS_PublishSksContext *psc;
629 struct GNUNET_CRYPTO_AesSessionKey sk;
630 struct GNUNET_CRYPTO_AesInitializationVector iv;
631 struct GNUNET_FS_Uri *sks_uri;
639 struct UBlock *ub_enc;
641 struct GNUNET_CONTAINER_MetaData *mmeta;
642 struct GNUNET_HashCode id_hash; /* hash of thisId */
643 struct GNUNET_HashCode ns_hash; /* hash of namespace public key */
644 struct GNUNET_HashCode key; /* id_hash ^ ns_hash, for AES key */
645 struct GNUNET_HashCode signing_key; /* H(key) = input for public key */
646 struct GNUNET_HashCode query; /* H(verification_key) = query */
648 idlen = strlen (identifier);
650 nidlen = strlen (update) + 1;
653 uris = GNUNET_FS_uri_to_string (uri);
654 slen = strlen (uris) + 1;
655 if ( (slen >= MAX_UBLOCK_SIZE - sizeof (struct UBlock)) ||
656 (nidlen >= MAX_UBLOCK_SIZE - sizeof (struct UBlock) - slen) )
658 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
659 _("Identifiers or URI too long to create UBlock"));
664 mmeta = GNUNET_CONTAINER_meta_data_create ();
666 mmeta = GNUNET_CONTAINER_meta_data_duplicate (meta);
667 mdsize = GNUNET_CONTAINER_meta_data_get_serialized_size (mmeta);
668 size = sizeof (struct UBlock) + slen + nidlen + mdsize;
669 if ( (size > MAX_UBLOCK_SIZE) ||
670 (size < sizeof (struct UBlock) + slen + nidlen) )
672 size = MAX_UBLOCK_SIZE;
673 mdsize = MAX_UBLOCK_SIZE - (sizeof (struct UBlock) + slen + nidlen);
675 ub = GNUNET_malloc (sizeof (struct UBlock) + size);
676 dest = (char *) &ub[1];
678 memcpy (dest, update, nidlen);
682 memcpy (dest, uris, slen);
686 GNUNET_CONTAINER_meta_data_serialize (mmeta, &dest, mdsize,
687 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART);
688 GNUNET_CONTAINER_meta_data_destroy (mmeta);
694 cont (cont_cls, NULL, _("Internal error."));
697 sks_uri = GNUNET_malloc (sizeof (struct GNUNET_FS_Uri));
698 sks_uri->type = GNUNET_FS_URI_SKS;
699 sks_uri->data.sks.identifier = GNUNET_strdup (identifier);
700 GNUNET_FS_namespace_get_public_identifier (ns,
701 &sks_uri->data.sks.ns);
703 size = sizeof (struct UBlock) + mdsize + slen + nidlen;
704 ub_enc = GNUNET_malloc (size);
705 GNUNET_CRYPTO_hash (identifier, idlen, &id_hash);
706 GNUNET_CRYPTO_hash (&sks_uri->data.sks.ns,
707 sizeof (sks_uri->data.sks.ns), &ns_hash);
708 GNUNET_CRYPTO_hash_xor (&id_hash, &ns_hash, &key);
709 GNUNET_CRYPTO_hash_to_aes_key (&key, &sk, &iv);
710 GNUNET_CRYPTO_hash (&key, sizeof (struct GNUNET_HashCode), &signing_key);
712 GNUNET_CRYPTO_aes_encrypt (&ub[1],
713 size - sizeof (struct UBlock),
716 ub_enc->purpose.size = htonl (nidlen + slen + mdsize + sizeof (struct UBlock)
717 - sizeof (struct GNUNET_FS_PseudonymSignature));
718 ub_enc->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_FS_UBLOCK);
719 GNUNET_FS_pseudonym_derive_verification_key (&sks_uri->data.sks.ns,
721 &ub_enc->verification_key);
722 GNUNET_CRYPTO_hash (&ub_enc->verification_key,
723 sizeof (ub_enc->verification_key),
725 GNUNET_FS_pseudonym_sign (ns->key,
730 psc = GNUNET_malloc (sizeof (struct GNUNET_FS_PublishSksContext));
733 psc->ns = GNUNET_FS_namespace_dup (ns);
734 psc->cont_cls = cont_cls;
735 if (0 != (options & GNUNET_FS_PUBLISH_OPTION_SIMULATE_ONLY))
737 GNUNET_free (ub_enc);
739 sb_put_cont (psc, GNUNET_OK, GNUNET_TIME_UNIT_ZERO_ABS, NULL);
742 psc->dsh = GNUNET_DATASTORE_connect (h->cfg);
743 if (NULL == psc->dsh)
745 GNUNET_free (ub_enc);
747 sb_put_cont (psc, GNUNET_NO, GNUNET_TIME_UNIT_ZERO_ABS, _("Failed to connect to datastore."));
753 psc->nsn = GNUNET_malloc (sizeof (struct NamespaceUpdateNode));
754 psc->nsn->id = GNUNET_strdup (identifier);
755 psc->nsn->update = GNUNET_strdup (update);
756 psc->nsn->md = GNUNET_CONTAINER_meta_data_duplicate (meta);
757 psc->nsn->uri = GNUNET_FS_uri_dup (uri);
760 psc->dqe = GNUNET_DATASTORE_put (psc->dsh, 0, &query, size, ub_enc,
761 GNUNET_BLOCK_TYPE_FS_UBLOCK, bo->content_priority,
762 bo->anonymity_level, bo->replication_level,
763 bo->expiration_time, -2, 1,
764 GNUNET_CONSTANTS_SERVICE_TIMEOUT, &sb_put_cont, psc);
766 GNUNET_free (ub_enc);
772 * Abort the SKS publishing operation.
774 * @param psc context of the operation to abort.
777 GNUNET_FS_publish_sks_cancel (struct GNUNET_FS_PublishSksContext *psc)
779 if (NULL != psc->dqe)
781 GNUNET_DATASTORE_cancel (psc->dqe);
784 if (NULL != psc->dsh)
786 GNUNET_DATASTORE_disconnect (psc->dsh, GNUNET_NO);
789 GNUNET_FS_namespace_delete (psc->ns, GNUNET_NO);
790 GNUNET_FS_uri_destroy (psc->uri);
791 if (NULL != psc->nsn)
793 GNUNET_CONTAINER_meta_data_destroy (psc->nsn->md);
794 GNUNET_FS_uri_destroy (psc->nsn->uri);
795 GNUNET_free (psc->nsn->id);
796 GNUNET_free (psc->nsn->update);
797 GNUNET_free (psc->nsn);
804 * Closure for 'process_update_node'.
806 struct ProcessUpdateClosure
809 * Function to call for each node.
811 GNUNET_FS_IdentifierProcessor ip;
821 * Call the iterator in the closure for each node.
823 * @param cls closure (of type 'struct ProcessUpdateClosure *')
824 * @param key current key code
825 * @param value value in the hash map (of type 'struct NamespaceUpdateNode *')
826 * @return GNUNET_YES if we should continue to
831 process_update_node (void *cls, const struct GNUNET_HashCode * key, void *value)
833 struct ProcessUpdateClosure *pc = cls;
834 struct NamespaceUpdateNode *nsn = value;
836 pc->ip (pc->ip_cls, nsn->id, nsn->uri, nsn->md, nsn->update);
842 * Closure for 'find_trees'.
844 struct FindTreeClosure
847 * Namespace we are operating on.
849 struct GNUNET_FS_Namespace *ns;
852 * Array with 'head's of TREEs.
854 struct NamespaceUpdateNode **tree_array;
857 * Size of 'tree_array'
859 unsigned int tree_array_size;
862 * Current generational ID used.
867 * Identifier for the current TREE, or UINT_MAX for none yet.
874 * Find all nodes reachable from the current node (including the
875 * current node itself). If they are in no tree, add them to the
876 * current one. If they are the head of another tree, merge the
877 * trees. If they are in the middle of another tree, let them be.
878 * We can tell that a node is already in an tree by checking if
879 * its 'nug' field is set to the current 'nug' value. It is the
880 * head of an tree if it is in the 'tree_array' under its respective
883 * In short, we're trying to find the smallest number of tree to
884 * cover a directed graph.
886 * @param cls closure (of type 'struct FindTreeClosure')
887 * @param key current key code
888 * @param value value in the hash map
889 * @return GNUNET_YES if we should continue to
894 find_trees (void *cls, const struct GNUNET_HashCode * key, void *value)
896 struct FindTreeClosure *fc = cls;
897 struct NamespaceUpdateNode *nsn = value;
898 struct GNUNET_HashCode hc;
900 if (nsn->nug == fc->nug)
902 if (UINT_MAX == nsn->tree_id)
903 return GNUNET_YES; /* circular */
904 GNUNET_assert (nsn->tree_id < fc->tree_array_size);
905 if (fc->tree_array[nsn->tree_id] != nsn)
906 return GNUNET_YES; /* part of "another" (directed) TREE,
907 * and not root of it, end trace */
908 if (nsn->tree_id == fc->id)
909 return GNUNET_YES; /* that's our own root (can this be?) */
910 /* merge existing TREE, we have a root for both */
911 fc->tree_array[nsn->tree_id] = NULL;
912 if (UINT_MAX == fc->id)
913 fc->id = nsn->tree_id; /* take over ID */
918 nsn->tree_id = UINT_MAX; /* mark as undef */
920 GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
921 GNUNET_CONTAINER_multihashmap_get_multiple (fc->ns->update_map, &hc,
929 * List all of the identifiers in the namespace for which we could
930 * produce an update. Namespace updates form a graph where each node
931 * has a name. Each node can have any number of URI/meta-data entries
932 * which can each be linked to other nodes. Cycles are possible.
934 * Calling this function with "next_id" NULL will cause the library to
935 * call "ip" with a root for each strongly connected component of the
936 * graph (a root being a node from which all other nodes in the Tree
939 * Calling this function with "next_id" being the name of a node will
940 * cause the library to call "ip" with all children of the node. Note
941 * that cycles within the final tree are possible (including self-loops).
942 * I know, odd definition of a tree, but the GUI will display an actual
943 * tree (GtkTreeView), so that's what counts for the term here.
945 * @param ns namespace to inspect for updateable content
946 * @param next_id ID to look for; use NULL to look for tree roots
947 * @param ip function to call on each updateable identifier
948 * @param ip_cls closure for ip
951 GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Namespace *ns,
953 GNUNET_FS_IdentifierProcessor ip,
958 struct GNUNET_HashCode hc;
959 struct NamespaceUpdateNode *nsn;
960 struct ProcessUpdateClosure pc;
961 struct FindTreeClosure fc;
963 if (NULL == ns->update_nodes)
964 read_update_information_graph (ns);
965 if (NULL == ns->update_nodes)
967 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
968 "No updateable nodes found for ID `%s'\n", next_id);
969 return; /* no nodes */
971 if (NULL == ns->update_map)
973 /* need to construct */
975 GNUNET_CONTAINER_multihashmap_create (2 +
976 3 * ns->update_node_count /
979 for (i = 0; i < ns->update_node_count; i++)
981 nsn = ns->update_nodes[i];
982 GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc);
983 GNUNET_CONTAINER_multihashmap_put (ns->update_map, &hc, nsn,
984 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
989 GNUNET_CRYPTO_hash (next_id, strlen (next_id), &hc);
992 GNUNET_CONTAINER_multihashmap_get_multiple (ns->update_map, &hc,
993 &process_update_node, &pc);
996 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
997 "Calculating TREEs to find roots of update trees\n");
998 /* Find heads of TREEs in update graph */
1000 fc.tree_array = NULL;
1001 fc.tree_array_size = 0;
1003 for (i = 0; i < ns->update_node_count; i++)
1005 nsn = ns->update_nodes[i];
1006 if (nsn->nug == nug)
1008 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TREE of node `%s' is %u\n", nsn->id,
1010 continue; /* already placed in TREE */
1012 GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
1014 nsn->tree_id = UINT_MAX;
1018 GNUNET_CONTAINER_multihashmap_get_multiple (ns->update_map, &hc,
1020 if (UINT_MAX == fc.id)
1022 /* start new TREE */
1023 for (fc.id = 0; fc.id < fc.tree_array_size; fc.id++)
1025 if (fc.tree_array[fc.id] == NULL)
1027 fc.tree_array[fc.id] = nsn;
1028 nsn->tree_id = fc.id;
1032 if (fc.id == fc.tree_array_size)
1034 GNUNET_array_append (fc.tree_array, fc.tree_array_size, nsn);
1035 nsn->tree_id = fc.id;
1037 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1038 "Starting new TREE %u with node `%s'\n", nsn->tree_id,
1040 /* put all nodes with same identifier into this TREE */
1041 GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc);
1042 fc.id = nsn->tree_id;
1045 GNUNET_CONTAINER_multihashmap_get_multiple (ns->update_map, &hc,
1050 /* make head of TREE "id" */
1051 fc.tree_array[fc.id] = nsn;
1052 nsn->tree_id = fc.id;
1054 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TREE of node `%s' is %u\n", nsn->id,
1057 for (i = 0; i < fc.tree_array_size; i++)
1059 nsn = fc.tree_array[i];
1062 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Root of TREE %u is node `%s'\n", i,
1064 ip (ip_cls, nsn->id, nsn->uri, nsn->md, nsn->update);
1067 GNUNET_array_grow (fc.tree_array, fc.tree_array_size, 0);
1068 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Done processing TREEs\n");
1072 /* end of fs_namespace.c */