fs_sharetree.c File Reference

code to manipulate the 'struct GNUNET_FS_ShareTreeItem' tree More...

#include "platform.h"
#include "gnunet_fs_service.h"
#include "gnunet_scheduler_lib.h"
#include <pthread.h>

Include dependency graph for fs_sharetree.c:

Go to the source code of this file.

Data Structures
struct	KeywordCounter
	Entry for each unique keyword to track how often it occurred. More...
struct	MetaCounter
	Aggregate information we keep for meta data in each directory. More...
struct	TrimContext
	A structure that forms a singly-linked list that serves as a stack for metadata-processing function. More...

Functions
static int	add_to_keyword_counter (void *cls, const char *keyword, int is_mandatory)
	Add the given keyword to the keyword statistics tracker. More...
static int	add_to_meta_counter (void *cls, const char *plugin_name, enum EXTRACTOR_MetaType type, enum EXTRACTOR_MetaFormat format, const char *data_mime_type, const char *data, size_t data_len)
	Function called on each meta data item. More...
static int	remove_high_frequency_keywords (void *cls, const char *keyword, int is_mandatory)
	Remove keywords above the threshold. More...
static int	migrate_and_drop_keywords (void *cls, const struct GNUNET_HashCode *key, void *value)
	Move "frequent" keywords over to the target ksk uri, free the counters. More...
static int	migrate_and_drop_metadata (void *cls, const struct GNUNET_HashCode *key, void *value)
	Copy "frequent" metadata items over to the target metadata container, free the counters. More...
static void	share_tree_trim (struct TrimContext *tc, struct GNUNET_FS_ShareTreeItem *tree)
	Process a share item tree, moving frequent keywords up and copying frequent metadata up. More...
void	GNUNET_FS_share_tree_trim (struct GNUNET_FS_ShareTreeItem *toplevel)
	Process a share item tree, moving frequent keywords up and copying frequent metadata up. More...
void	GNUNET_FS_share_tree_free (struct GNUNET_FS_ShareTreeItem *toplevel)
	Release memory of a share item tree. More...

Detailed Description

code to manipulate the 'struct GNUNET_FS_ShareTreeItem' tree

Author

LRN

Christian Grothoff

Definition in file fs_sharetree.c.

Function Documentation

add_to_keyword_counter()

static int add_to_keyword_counter ( void *  cls, const char *  keyword, int  is_mandatory  )

static

Add the given keyword to the keyword statistics tracker.

Parameters

cls	the multihashmap we store the keyword counters in
keyword	the keyword to count
is_mandatory	ignored

Returns

always GNUNET_OK

Definition at line 156 of file fs_sharetree.c.

{
  struct GNUNET_CONTAINER_MultiHashMap *mcm = cls;
  struct KeywordCounter *cnt;
  struct GNUNET_HashCode hc;
  size_t klen;
 
  klen = strlen (keyword) + 1;
  GNUNET_CRYPTO_hash (keyword, klen - 1, &hc);
  cnt = GNUNET_CONTAINER_multihashmap_get (mcm, &hc);
  if (cnt == NULL)
  {
    cnt = GNUNET_malloc (sizeof(struct KeywordCounter) + klen);
    cnt->value = (const char *) &cnt[1];
    GNUNET_memcpy (&cnt[1], keyword, klen);
    GNUNET_assert (GNUNET_OK ==
                   GNUNET_CONTAINER_multihashmap_put (mcm,
                                                      &hc, cnt,
                                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
  }
  cnt->count++;
  return GNUNET_OK;
}

References KeywordCounter::count, GNUNET_assert, GNUNET_CONTAINER_multihashmap_get(), GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY, GNUNET_CRYPTO_hash(), GNUNET_malloc, GNUNET_memcpy, GNUNET_OK, and KeywordCounter::value.

Referenced by share_tree_trim().

Here is the call graph for this function:

Here is the caller graph for this function:

add_to_meta_counter()

static int add_to_meta_counter ( void *  cls, const char *  plugin_name, enum EXTRACTOR_MetaType  type, enum EXTRACTOR_MetaFormat  format, const char *  data_mime_type, const char *  data, size_t  data_len  )

static

Function called on each meta data item.

Increments the respective counter.

Parameters

cls	the container multihashmap to update
plugin_name	name of the plugin that produced this value; special values can be used (e.g. '<zlib>' for zlib being used in the main libextractor library and yielding meta data).
type	libextractor-type describing the meta data
format	basic format information about data
data_mime_type	mime-type of data (not of the original file); can be NULL (if mime-type is not known)
data	actual meta-data found
data_len	number of bytes in data

Returns

0 to continue extracting / iterating

Definition at line 199 of file fs_sharetree.c.

{
  struct GNUNET_CONTAINER_MultiHashMap *map = cls;
  struct GNUNET_HashCode key;
  struct MetaCounter *cnt;
 
  GNUNET_CRYPTO_hash (data, data_len, &key);
  cnt = GNUNET_CONTAINER_multihashmap_get (map, &key);
  if (NULL == cnt)
  {
    cnt = GNUNET_new (struct MetaCounter);
    cnt->data = data;
    cnt->data_size = data_len;
    cnt->plugin_name = plugin_name;
    cnt->type = type;
    cnt->format = format;
    cnt->data_mime_type = data_mime_type;
    GNUNET_assert (GNUNET_OK ==
                   GNUNET_CONTAINER_multihashmap_put (map,
                                                      &key, cnt,
                                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
  }
  cnt->count++;
  return 0;
}

References MetaCounter::count, data, MetaCounter::data, MetaCounter::data_mime_type, MetaCounter::data_size, MetaCounter::format, GNUNET_assert, GNUNET_CONTAINER_multihashmap_get(), GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY, GNUNET_CRYPTO_hash(), GNUNET_new, GNUNET_OK, key, map, plugin_name, MetaCounter::plugin_name, type, and MetaCounter::type.

Referenced by share_tree_trim().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_high_frequency_keywords()

static int remove_high_frequency_keywords ( void *  cls, const char *  keyword, int  is_mandatory  )

static

Remove keywords above the threshold.

Parameters

cls	the 'struct TrimContext' with the pos to remove the keywords from
keyword	the keyword to check
is_mandatory	ignored

Returns

always GNUNET_OK

Definition at line 239 of file fs_sharetree.c.

{
  struct TrimContext *tc = cls;
  struct KeywordCounter *counter;
  struct GNUNET_HashCode hc;
  size_t klen;
 
  klen = strlen (keyword) + 1;
  GNUNET_CRYPTO_hash (keyword, klen - 1, &hc);
  counter = GNUNET_CONTAINER_multihashmap_get (tc->keywordcounter, &hc);
  GNUNET_assert (NULL != counter);
  if (counter->count < tc->move_threshold)
    return GNUNET_OK;
  GNUNET_FS_uri_ksk_remove_keyword (tc->pos->ksk_uri,
                                    counter->value);
  return GNUNET_OK;
}

References KeywordCounter::count, GNUNET_assert, GNUNET_CONTAINER_multihashmap_get(), GNUNET_CRYPTO_hash(), GNUNET_FS_uri_ksk_remove_keyword(), GNUNET_OK, tc, and KeywordCounter::value.

Referenced by share_tree_trim().

Here is the call graph for this function:

Here is the caller graph for this function:

migrate_and_drop_keywords()

static int migrate_and_drop_keywords ( void *  cls, const struct GNUNET_HashCode *  key, void *  value  )

static

Move "frequent" keywords over to the target ksk uri, free the counters.

Parameters

cls	the 'struct TrimContext'
key	key of the entry
value	the 'struct KeywordCounter'

Returns

GNUNET_YES (always)

Definition at line 269 of file fs_sharetree.c.

{
  struct TrimContext *tc = cls;
  struct KeywordCounter *counter = value;
 
  if (counter->count >= tc->move_threshold)
  {
    if (NULL == tc->pos->ksk_uri)
      tc->pos->ksk_uri = GNUNET_FS_uri_ksk_create_from_args (1,
                                                             &counter->value);
    else
      GNUNET_FS_uri_ksk_add_keyword (tc->pos->ksk_uri, counter->value,
                                     GNUNET_NO);
  }
  GNUNET_assert (GNUNET_YES ==
                 GNUNET_CONTAINER_multihashmap_remove (tc->keywordcounter,
                                                       key,
                                                       counter));
  GNUNET_free (counter);
  return GNUNET_YES;
}

References KeywordCounter::count, GNUNET_assert, GNUNET_CONTAINER_multihashmap_remove(), GNUNET_free, GNUNET_FS_uri_ksk_add_keyword(), GNUNET_FS_uri_ksk_create_from_args(), GNUNET_NO, GNUNET_YES, key, tc, value, and KeywordCounter::value.

Referenced by share_tree_trim().

Here is the call graph for this function:

Here is the caller graph for this function:

migrate_and_drop_metadata()

static int migrate_and_drop_metadata ( void *  cls, const struct GNUNET_HashCode *  key, void *  value  )

static

Copy "frequent" metadata items over to the target metadata container, free the counters.

Parameters

cls	the 'struct TrimContext'
key	key of the entry
value	the 'struct KeywordCounter'

Returns

GNUNET_YES (always)

Definition at line 303 of file fs_sharetree.c.

{
  struct TrimContext *tc = cls;
  struct MetaCounter *counter = value;
 
  if (counter->count >= tc->move_threshold)
  {
    if (NULL == tc->pos->meta)
      tc->pos->meta = GNUNET_FS_meta_data_create ();
    GNUNET_FS_meta_data_insert (tc->pos->meta,
                                counter->plugin_name,
                                counter->type,
                                counter->format,
                                counter->data_mime_type, counter->data,
                                counter->data_size);
  }
  GNUNET_assert (GNUNET_YES ==
                 GNUNET_CONTAINER_multihashmap_remove (tc->metacounter,
                                                       key,
                                                       counter));
  GNUNET_free (counter);
  return GNUNET_YES;
}

References MetaCounter::count, MetaCounter::data, MetaCounter::data_mime_type, MetaCounter::data_size, MetaCounter::format, GNUNET_assert, GNUNET_CONTAINER_multihashmap_remove(), GNUNET_free, GNUNET_FS_meta_data_create(), GNUNET_FS_meta_data_insert(), GNUNET_YES, key, MetaCounter::plugin_name, tc, MetaCounter::type, and value.

Referenced by share_tree_trim().

Here is the call graph for this function:

Here is the caller graph for this function:

share_tree_trim()

static void share_tree_trim ( struct TrimContext *  tc, struct GNUNET_FS_ShareTreeItem *  tree  )

static

Process a share item tree, moving frequent keywords up and copying frequent metadata up.

Parameters

tc	trim context with hash maps to use
tree	tree to trim

Definition at line 337 of file fs_sharetree.c.

{
  struct GNUNET_FS_ShareTreeItem *pos;
  unsigned int num_children;
 
  /* first, trim all children */
  num_children = 0;
  for (pos = tree->children_head; NULL != pos; pos = pos->next)
  {
    share_tree_trim (tc, pos);
    num_children++;
  }
 
  /* consider adding filename to directory meta data */
  if (tree->is_directory == GNUNET_YES)
  {
    const char *user = getenv ("USER");
    if ((user == NULL) ||
        (0 != strncasecmp (user, tree->short_filename, strlen (user))))
    {
      /* only use filename if it doesn't match $USER */
      if (NULL == tree->meta)
        tree->meta = GNUNET_FS_meta_data_create ();
      GNUNET_FS_meta_data_insert (tree->meta, "<libgnunetfs>",
                                  EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME,
                                  EXTRACTOR_METAFORMAT_UTF8,
                                  "text/plain", tree->short_filename,
                                  strlen (tree->short_filename) + 1);
    }
  }
 
  if (1 >= num_children)
    return; /* nothing to trim */
 
  /* now, count keywords and meta data in children */
  for (pos = tree->children_head; NULL != pos; pos = pos->next)
  {
    if (NULL != pos->meta)
      GNUNET_FS_meta_data_iterate (pos->meta, &add_to_meta_counter,
                                   tc->metacounter);
    if (NULL != pos->ksk_uri)
      GNUNET_FS_uri_ksk_get_keywords (pos->ksk_uri, &add_to_keyword_counter,
                                      tc->keywordcounter);
  }
 
  /* calculate threshold for moving keywords / meta data */
  tc->move_threshold = 1 + (num_children / 2);
 
  /* remove high-frequency keywords from children */
  for (pos = tree->children_head; NULL != pos; pos = pos->next)
  {
    tc->pos = pos;
    if (NULL != pos->ksk_uri)
    {
      struct GNUNET_FS_Uri *ksk_uri_copy = GNUNET_FS_uri_dup (pos->ksk_uri);
      GNUNET_FS_uri_ksk_get_keywords (ksk_uri_copy,
                                      &remove_high_frequency_keywords, tc);
      GNUNET_FS_uri_destroy (ksk_uri_copy);
    }
  }
 
  /* add high-frequency meta data and keywords to parent */
  tc->pos = tree;
  GNUNET_CONTAINER_multihashmap_iterate (tc->keywordcounter,
                                         &migrate_and_drop_keywords,
                                         tc);
  GNUNET_CONTAINER_multihashmap_iterate (tc->metacounter,
                                         &migrate_and_drop_metadata,
                                         tc);
}

References add_to_keyword_counter(), add_to_meta_counter(), GNUNET_FS_ShareTreeItem::children_head, EXTRACTOR_METAFORMAT_UTF8, EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME, getenv(), GNUNET_CONTAINER_multihashmap_iterate(), GNUNET_FS_meta_data_create(), GNUNET_FS_meta_data_insert(), GNUNET_FS_meta_data_iterate(), GNUNET_FS_uri_destroy(), GNUNET_FS_uri_dup(), GNUNET_FS_uri_ksk_get_keywords(), GNUNET_YES, GNUNET_FS_ShareTreeItem::is_directory, GNUNET_FS_ShareTreeItem::ksk_uri, GNUNET_FS_ShareTreeItem::meta, migrate_and_drop_keywords(), migrate_and_drop_metadata(), GNUNET_FS_ShareTreeItem::next, remove_high_frequency_keywords(), share_tree_trim(), GNUNET_FS_ShareTreeItem::short_filename, and tc.

Referenced by GNUNET_FS_share_tree_trim(), and share_tree_trim().

Here is the call graph for this function:

Here is the caller graph for this function: