/*
This file is part of GNUnet
- (C) 2012 Christian Grothoff (and other contributing authors)
+ Copyright (C) 2012 GNUnet e.V.
GNUnet is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published
- by the Free Software Foundation; either version 2, or (at your
+ by the Free Software Foundation; either version 3, or (at your
option) any later version.
GNUnet is distributed in the hope that it will be useful, but
You should have received a copy of the GNU General Public License
along with GNUnet; see the file COPYING. If not, write to the
- Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA.
+ Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
*/
/**
#define GNUNET_CONSENSUS_IBF_H
#include "platform.h"
-#include "gnunet_common.h"
#include "gnunet_util_lib.h"
#ifdef __cplusplus
#endif
+/**
+ * Keys that can be inserted into and removed from an IBF.
+ */
struct IBF_Key
{
uint64_t key_val;
};
+
+/**
+ * Hash of an IBF key.
+ */
struct IBF_KeyHash
{
uint32_t key_hash_val;
};
+
+/**
+ * Type of the count field of IBF buckets.
+ */
struct IBF_Count
{
int8_t count_val;
};
+
/**
* Size of one ibf bucket in bytes
*/
#define IBF_BUCKET_SIZE (sizeof (struct IBF_Count) + sizeof (struct IBF_Key) + \
sizeof (struct IBF_KeyHash))
+
/**
* Invertible bloom filter (IBF).
*
/**
* Write buckets from an ibf to a buffer.
* Exactly (IBF_BUCKET_SIZE*ibf->size) bytes are written to buf.
- *
+ *
* @param ibf the ibf to write
* @param start with which bucket to start
* @param count how many buckets to write
* @param buf buffer to write the data to
*/
void
-ibf_write_slice (const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf);
+ibf_write_slice (const struct InvertibleBloomFilter *ibf,
+ uint32_t start,
+ uint32_t count,
+ void *buf);
/**
* @param buf pointer to the buffer to read from
* @param start which bucket to start at
* @param count how many buckets to read
- * @param ibf the ibf to read from
+ * @param ibf the ibf to write to
*/
void
-ibf_read_slice (const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf);
+ibf_read_slice (const void *buf,
+ uint32_t start,
+ uint32_t count,
+ struct InvertibleBloomFilter *ibf);
/**
*
* @param size number of IBF buckets
* @param hash_num number of buckets one element is hashed in, usually 3 or 4
- * @return the newly created invertible bloom filter
+ * @return the newly created invertible bloom filter, NULL on error
*/
struct InvertibleBloomFilter *
ibf_create (uint32_t size, uint8_t hash_num);
/**
- * Insert an element into an IBF.
+ * Insert a key into an IBF.
*
* @param ibf the IBF
* @param key the element's hash code
ibf_insert (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
+/**
+ * Remove a key from an IBF.
+ *
+ * @param ibf the IBF
+ * @param key the element's hash code
+ */
+void
+ibf_remove (struct InvertibleBloomFilter *ibf, struct IBF_Key key);
+
+
/**
* Subtract ibf2 from ibf1, storing the result in ibf1.
* The two IBF's must have the same parameters size and hash_num.
* @param ibf2 IBF that will be subtracted from ibf1
*/
void
-ibf_subtract (struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2);
+ibf_subtract (struct InvertibleBloomFilter *ibf1,
+ const struct InvertibleBloomFilter *ibf2);
/**
* A negative sign indicates that the element was recovered
* resides in an IBF that was previously subtracted from.
* @param ret_id receives the hash code of the decoded element, if successful
- * @return GNUNET_YES if decoding an element was successful,
- * GNUNET_NO if the IBF is empty,
- * GNUNET_SYSERR if the decoding has failed
+ * @return #GNUNET_YES if decoding an element was successful,
+ * #GNUNET_NO if the IBF is empty,
+ * #GNUNET_SYSERR if the decoding has failed
*/
int
-ibf_decode (struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id);
+ibf_decode (struct InvertibleBloomFilter *ibf,
+ int *ret_side,
+ struct IBF_Key *ret_id);
/**
struct InvertibleBloomFilter *
ibf_dup (const struct InvertibleBloomFilter *ibf);
+
/**
* Destroy all resources associated with the invertible bloom filter.
* No more ibf_*-functions may be called on ibf after calling destroy.
#endif
#endif
-