[datastore] Fix #3743

This change adds support for key == NULL to the datastore plugins
and replaces the offset argument with a next_uid and random arguments to
increase performance in the key == NULL case.

With the offset argument a datastore plugin would have to count all
matching keys before fetching the key at the right offset, which would
iterate over the entire database in the case of key == NULL.

The offset argument was used in two ways: to iterate over a set of
matching values and to start iteration at a random matching value. The new API
seperates these into two arguments: if random is true it will return a
random matching value, otherwise next_uid can be set to uid + 1 to return the
next matching value.

The random argument was not added to get_zero_anonymity. This function
is used to periodically insert zero anonymity values into the DHT. I
don't think it's necessary to randomize this.

3 files changed, 26 insertions, 36 deletions

diff --git a/src/include/gnunet_datastore_plugin.h b/src/include/gnunet_datastore_plugin.h
index 2295d4e72..b1c9cb7c3 100644
--- a/src/include/gnunet_datastore_plugin.h
+++ b/src/include/gnunet_datastore_plugin.h
@@ -204,9 +204,9 @@ typedef void
  * Get one of the results for a particular key in the datastore.
  *
  * @param cls closure
- * @param offset offset of the result (modulo num-results);
- *               specific ordering does not matter for the offset
- * @param key key to match, never NULL
+ * @param next_uid return the result with lowest uid >= next_uid
+ * @param random if true, return a random result instead of using next_uid
+ * @param key maybe NULL (to match all entries)
  * @param vhash hash of the value, maybe NULL (to
  *        match all values that have the right key).
  *        Note that for DBlocks there is no difference
@@ -215,17 +215,18 @@ typedef void
  * @param type entries of which type are relevant?
  *     Use 0 for any type.
  * @param proc function to call on the matching value;
- *        proc should be called with NULL if there is no result
+ *        will be called with NULL if nothing matches
  * @param proc_cls closure for @a proc
  */
 typedef void
 (*PluginGetKey) (void *cls,
-                 uint64_t offset,
-                 const struct GNUNET_HashCode *key,
-                 const struct GNUNET_HashCode *vhash,
-                 enum GNUNET_BLOCK_Type type,
-                 PluginDatumProcessor proc,
-                 void *proc_cls);
+                 uint64_t next_uid,
+                 bool random,
+                 const struct GNUNET_HashCode *key,
+                 const struct GNUNET_HashCode *vhash,
+                 enum GNUNET_BLOCK_Type type,
+                 PluginDatumProcessor proc,
+                 void *proc_cls);
 
 
 /**
@@ -285,23 +286,22 @@ typedef void
 
 
 /**
- * Select a single item from the datastore at the specified offset
- * (among those applicable).
+ * Select a single item from the datastore (among those applicable).
  *
  * @param cls closure
- * @param offset offset of the result (modulo num-results);
- *               specific ordering does not matter for the offset
+ * @param next_uid return the result with lowest uid >= next_uid
  * @param type entries of which type should be considered?
  *        Must not be zero (ANY).
- * @param proc function to call on the matching value
+ * @param proc function to call on the matching value;
+ *        will be called with NULL if no value matches
  * @param proc_cls closure for @a proc
  */
 typedef void
 (*PluginGetType) (void *cls,
-                  uint64_t offset,
-                  enum GNUNET_BLOCK_Type type,
-                  PluginDatumProcessor proc,
-                  void *proc_cls);
+                  uint64_t next_uid,
+                  enum GNUNET_BLOCK_Type type,
+                  PluginDatumProcessor proc,
+                  void *proc_cls);
 
 
 /**
@@ -354,9 +354,6 @@ struct GNUNET_DATASTORE_PluginFunctions
 
   /**
    * Get datum (of the specified type) with anonymity level zero.
-   * This function is allowed to ignore the 'offset' argument
-   * and instead return a random result (with zero anonymity of
-   * the correct type) if implementing an offset is expensive.
    */
   PluginGetType get_zero_anonymity;
 
diff --git a/src/include/gnunet_datastore_service.h b/src/include/gnunet_datastore_service.h
index 233598667..830e7da86 100644
--- a/src/include/gnunet_datastore_service.h
+++ b/src/include/gnunet_datastore_service.h
@@ -261,10 +261,8 @@ typedef void
  * will only be called once.
  *
  * @param h handle to the datastore
- * @param offset offset of the result (modulo num-results); set to
- *               a random 64-bit value initially; then increment by
- *               one each time; detect that all results have been found by uid
- *               being again the first uid ever returned.
+ * @param next_uid return the result with lowest uid >= next_uid
+ * @param random if true, return a random result instead of using next_uid
  * @param key maybe NULL (to match all entries)
  * @param type desired type, 0 for any
  * @param queue_priority ranking of this request in the priority queue
@@ -278,7 +276,8 @@ typedef void
  */
 struct GNUNET_DATASTORE_QueueEntry *
 GNUNET_DATASTORE_get_key (struct GNUNET_DATASTORE_Handle *h,
-                          uint64_t offset,
+                          uint64_t next_uid,
+                          bool random,
                           const struct GNUNET_HashCode *key,
                           enum GNUNET_BLOCK_Type type,
                           unsigned int queue_priority,
@@ -289,16 +288,9 @@ GNUNET_DATASTORE_get_key (struct GNUNET_DATASTORE_Handle *h,
 
 /**
  * Get a single zero-anonymity value from the datastore.
- * Note that some implementations can ignore the 'offset' and
- * instead return a random zero-anonymity value.  In that case,
- * detecting the wrap-around based on a repeating UID is at best
- * probabilistic.
  *
  * @param h handle to the datastore
- * @param offset offset of the result (modulo num-results); set to
- *               a random 64-bit value initially; then increment by
- *               one each time; detect that all results have been found by uid
- *               being again the first uid ever returned.
+ * @param next_uid return the result with lowest uid >= next_uid
  * @param queue_priority ranking of this request in the priority queue
  * @param max_queue_size at what queue size should this request be dropped
  *        (if other requests of higher priority are in the queue)
@@ -312,7 +304,7 @@ GNUNET_DATASTORE_get_key (struct GNUNET_DATASTORE_Handle *h,
  */
 struct GNUNET_DATASTORE_QueueEntry *
 GNUNET_DATASTORE_get_zero_anonymity (struct GNUNET_DATASTORE_Handle *h,
-                                     uint64_t offset,
+                                     uint64_t next_uid,
                                      unsigned int queue_priority,
                                      unsigned int max_queue_size,
                                      enum GNUNET_BLOCK_Type type,
diff --git a/src/include/platform.h b/src/include/platform.h
index add58821f..6095d0258 100644
--- a/src/include/platform.h
+++ b/src/include/platform.h
@@ -110,6 +110,7 @@
 #include <stdlib.h>
 #include <stdint.h>
 #include <stdarg.h>
+#include <stdbool.h>
 #include <errno.h>
 #include <signal.h>
 #include <libgen.h>