aboutsummaryrefslogtreecommitdiff
path: root/src/datacache/plugin_datacache_heap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/datacache/plugin_datacache_heap.c')
-rw-r--r--src/datacache/plugin_datacache_heap.c143
1 files changed, 115 insertions, 28 deletions
diff --git a/src/datacache/plugin_datacache_heap.c b/src/datacache/plugin_datacache_heap.c
index 49e60bca1d..ad5e7834d5 100644
--- a/src/datacache/plugin_datacache_heap.c
+++ b/src/datacache/plugin_datacache_heap.c
@@ -31,7 +31,7 @@
#define LOG_STRERROR_FILE(kind,op,fn) GNUNET_log_from_strerror_file (kind, "datacache-heap", op, fn)
-
+#define NUM_HEAPS 24
/**
* Context for all functions in this plugin.
@@ -49,9 +49,9 @@ struct Plugin
struct GNUNET_CONTAINER_MultiHashMap *map;
/**
- * Heap for expirations.
+ * Heaps sorted by distance.
*/
- struct GNUNET_CONTAINER_Heap *heap;
+ struct GNUNET_CONTAINER_Heap *heaps[NUM_HEAPS];
};
@@ -92,6 +92,11 @@ struct Value
unsigned int path_info_len;
/**
+ * How close is the hash to us? Determines which heap we are in!
+ */
+ uint32_t distance;
+
+ /**
* Type of the block.
*/
enum GNUNET_BLOCK_Type type;
@@ -118,11 +123,6 @@ struct PutContext
const char *data;
/**
- * Heap from the plugin.
- */
- struct GNUNET_CONTAINER_Heap *heap;
-
- /**
* Path information.
*/
const struct GNUNET_PeerIdentity *path_info;
@@ -168,7 +168,9 @@ put_cb (void *cls,
if ( (val->size == put_ctx->size) &&
(val->type == put_ctx->type) &&
- (0 == memcmp (&val[1], put_ctx->data, put_ctx->size)) )
+ (0 == memcmp (&val[1],
+ put_ctx->data,
+ put_ctx->size)) )
{
put_ctx->found = GNUNET_YES;
val->discard_time = GNUNET_TIME_absolute_max (val->discard_time,
@@ -178,8 +180,8 @@ put_cb (void *cls,
val->path_info_len,
put_ctx->path_info_len);
GNUNET_memcpy (val->path_info,
- put_ctx->path_info,
- put_ctx->path_info_len * sizeof (struct GNUNET_PeerIdentity));
+ put_ctx->path_info,
+ put_ctx->path_info_len * sizeof (struct GNUNET_PeerIdentity));
GNUNET_CONTAINER_heap_update_cost (val->hn,
val->discard_time.abs_value_us);
GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
@@ -199,6 +201,7 @@ put_cb (void *cls,
*
* @param cls closure (our `struct Plugin`)
* @param key key to store data under
+ * @param xor_distance how close is @a key to our PID?
* @param size number of bytes in @a data
* @param data data to store
* @param type type of the value
@@ -210,6 +213,7 @@ put_cb (void *cls,
static ssize_t
heap_plugin_put (void *cls,
const struct GNUNET_HashCode *key,
+ uint32_t xor_distance,
size_t size,
const char *data,
enum GNUNET_BLOCK_Type type,
@@ -222,7 +226,6 @@ heap_plugin_put (void *cls,
struct PutContext put_ctx;
put_ctx.found = GNUNET_NO;
- put_ctx.heap = plugin->heap;
put_ctx.data = data;
put_ctx.size = size;
put_ctx.path_info = path_info;
@@ -236,22 +239,28 @@ heap_plugin_put (void *cls,
if (GNUNET_YES == put_ctx.found)
return 0;
val = GNUNET_malloc (sizeof (struct Value) + size);
- GNUNET_memcpy (&val[1], data, size);
+ GNUNET_memcpy (&val[1],
+ data,
+ size);
val->key = *key;
val->type = type;
val->discard_time = discard_time;
val->size = size;
+ if (xor_distance >= NUM_HEAPS)
+ val->distance = NUM_HEAPS - 1;
+ else
+ val->distance = xor_distance;
GNUNET_array_grow (val->path_info,
val->path_info_len,
path_info_len);
GNUNET_memcpy (val->path_info,
- path_info,
- path_info_len * sizeof (struct GNUNET_PeerIdentity));
+ path_info,
+ path_info_len * sizeof (struct GNUNET_PeerIdentity));
(void) GNUNET_CONTAINER_multihashmap_put (plugin->map,
&val->key,
val,
GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
- val->hn = GNUNET_CONTAINER_heap_insert (plugin->heap,
+ val->hn = GNUNET_CONTAINER_heap_insert (plugin->heaps[val->distance],
val,
val->discard_time.abs_value_us);
return size + OVERHEAD;
@@ -369,7 +378,12 @@ heap_plugin_del (void *cls)
struct Plugin *plugin = cls;
struct Value *val;
- val = GNUNET_CONTAINER_heap_remove_root (plugin->heap);
+ for (unsigned int i=0;i<NUM_HEAPS;i++)
+ {
+ val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i]);
+ if (NULL != val)
+ break;
+ }
if (NULL == val)
return GNUNET_SYSERR;
GNUNET_assert (GNUNET_YES ==
@@ -413,6 +427,53 @@ heap_plugin_get_random (void *cls,
/**
+ * Closure for #find_closest().
+ */
+struct GetClosestContext
+{
+ struct Value **values;
+
+ unsigned int num_results;
+
+ const struct GNUNET_HashCode *key;
+};
+
+
+static int
+find_closest (void *cls,
+ const struct GNUNET_HashCode *key,
+ void *value)
+{
+ struct GetClosestContext *gcc = cls;
+ struct Value *val = value;
+ unsigned int j;
+
+ if (1 != GNUNET_CRYPTO_hash_cmp (key,
+ gcc->key))
+ return GNUNET_OK; /* useless */
+ j = gcc->num_results;
+ for (unsigned int i=0;i<gcc->num_results;i++)
+ {
+ if (NULL == gcc->values[i])
+ {
+ j = i;
+ break;
+ }
+ if (1 == GNUNET_CRYPTO_hash_cmp (&gcc->values[i]->key,
+ key))
+ {
+ j = i;
+ break;
+ }
+ }
+ if (j == gcc->num_results)
+ return GNUNET_OK;
+ gcc->values[j] = val;
+ return GNUNET_OK;
+}
+
+
+/**
* Iterate over the results that are "close" to a particular key in
* the datacache. "close" is defined as numerically larger than @a
* key (when interpreted as a circular address space), with small
@@ -432,8 +493,30 @@ heap_plugin_get_closest (void *cls,
GNUNET_DATACACHE_Iterator iter,
void *iter_cls)
{
- GNUNET_break (0); // not implemented!
- return 0;
+ struct Plugin *plugin = cls;
+ struct Value *values[num_results];
+ struct GetClosestContext gcc = {
+ .values = values,
+ .num_results = num_results,
+ .key = key
+ };
+ GNUNET_CONTAINER_multihashmap_iterate (plugin->map,
+ &find_closest,
+ &gcc);
+ for (unsigned int i=0;i<num_results;i++)
+ {
+ if (NULL == values[i])
+ return i;
+ iter (iter_cls,
+ &values[i]->key,
+ values[i]->size,
+ (void *) &values[i][1],
+ values[i]->type,
+ values[i]->discard_time,
+ values[i]->path_info_len,
+ values[i]->path_info);
+ }
+ return num_results;
}
@@ -453,7 +536,8 @@ libgnunet_plugin_datacache_heap_init (void *cls)
plugin = GNUNET_new (struct Plugin);
plugin->map = GNUNET_CONTAINER_multihashmap_create (1024, /* FIXME: base on quota! */
GNUNET_YES);
- plugin->heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
+ for (unsigned int i=0;i<NUM_HEAPS;i++)
+ plugin->heaps[i] = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
plugin->env = env;
api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions);
api->cls = plugin;
@@ -481,16 +565,19 @@ libgnunet_plugin_datacache_heap_done (void *cls)
struct Plugin *plugin = api->cls;
struct Value *val;
- while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heap)))
+ for (unsigned int i=0;i<NUM_HEAPS;i++)
{
- GNUNET_assert (GNUNET_YES ==
- GNUNET_CONTAINER_multihashmap_remove (plugin->map,
- &val->key,
- val));
- GNUNET_free_non_null (val->path_info);
- GNUNET_free (val);
+ while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i])))
+ {
+ GNUNET_assert (GNUNET_YES ==
+ GNUNET_CONTAINER_multihashmap_remove (plugin->map,
+ &val->key,
+ val));
+ GNUNET_free_non_null (val->path_info);
+ GNUNET_free (val);
+ }
+ GNUNET_CONTAINER_heap_destroy (plugin->heaps[i]);
}
- GNUNET_CONTAINER_heap_destroy (plugin->heap);
GNUNET_CONTAINER_multihashmap_destroy (plugin->map);
GNUNET_free (plugin);
GNUNET_free (api);
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-21 21:06:35 +0000