GNUnet  0.11.x
Typedefs | Functions
Container library: Bloom filter

Probabilistic set tests. More...

Typedefs

typedef int(* GNUNET_CONTAINER_HashCodeIterator) (void *cls, struct GNUNET_HashCode *next)
 Iterator over struct GNUNET_HashCode. More...
 

Functions

struct GNUNET_CONTAINER_BloomFilterGNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size, unsigned int k)
 Load a Bloom filter from a file. More...
 
struct GNUNET_CONTAINER_BloomFilterGNUNET_CONTAINER_bloomfilter_init (const char *data, size_t size, unsigned int k)
 Create a Bloom filter from raw bits. More...
 
int GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFilter *bf, char *data, size_t size)
 Copy the raw data of this Bloom filter into the given data array. More...
 
int GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
 Test if an element is in the filter. More...
 
void GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
 Add an element to the filter. More...
 
void GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
 Remove an element from the filter. More...
 
struct GNUNET_CONTAINER_BloomFilterGNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf)
 Create a copy of a bloomfilter. More...
 
void GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf)
 Free the space associcated with a filter in memory, flush to drive if needed (do not free the space on the drive). More...
 
size_t GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter *bf)
 Get size of the bloom filter. More...
 
void GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf)
 Reset a Bloom filter to empty. More...
 
int GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, const char *data, size_t size)
 "or" the entries of the given raw data array with the data of the given Bloom filter. More...
 
int GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_CONTAINER_BloomFilter *to_or)
 "or" the entries of the given raw data array with the data of the given Bloom filter. More...
 
void GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf, GNUNET_CONTAINER_HashCodeIterator iterator, void *iterator_cls, size_t size, unsigned int k)
 Resize a bloom filter. More...
 

Detailed Description

Probabilistic set tests.

Typedef Documentation

◆ GNUNET_CONTAINER_HashCodeIterator

typedef int(* GNUNET_CONTAINER_HashCodeIterator) (void *cls, struct GNUNET_HashCode *next)

Iterator over struct GNUNET_HashCode.

Parameters
clsclosure
nextset to the next hash code
Returns
GNUNET_YES if next was updated GNUNET_NO if there are no more entries

Definition at line 216 of file gnunet_container_lib.h.

Function Documentation

◆ GNUNET_CONTAINER_bloomfilter_load()

struct GNUNET_CONTAINER_BloomFilter* GNUNET_CONTAINER_bloomfilter_load ( const char *  filename,
size_t  size,
unsigned int  k 
)

Load a Bloom filter from a file.

Parameters
filenamethe name of the file (or the prefix)
sizethe size of the bloom-filter (number of bytes of storage space to use); will be rounded up to next power of 2
kthe number of GNUNET_CRYPTO_hash-functions to apply per element (number of bits set per element in the set)
Returns
the bloomfilter

Load a Bloom filter from a file.

Parameters
filenamethe name of the file (or the prefix)
sizethe size of the bloom-filter (number of bytes of storage space to use); will be rounded up to next power of 2
kthe number of GNUNET_CRYPTO_hash-functions to apply per element (number of bits set per element in the set)
Returns
the bloomfilter

Definition at line 498 of file container_bloomfilter.c.

References _, GNUNET_CONTAINER_BloomFilter::addressesPerElement, GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, BUFFSIZE, GNUNET_CONTAINER_BloomFilter::fh, GNUNET_CONTAINER_BloomFilter::filename, GNUNET_assert, GNUNET_DISK_file_close(), GNUNET_DISK_file_handle_size(), GNUNET_DISK_file_open(), GNUNET_DISK_file_read(), GNUNET_DISK_file_test(), GNUNET_DISK_OPEN_CREATE, GNUNET_DISK_OPEN_READWRITE, GNUNET_DISK_PERM_USER_READ, GNUNET_DISK_PERM_USER_WRITE, GNUNET_ERROR_TYPE_ERROR, GNUNET_ERROR_TYPE_WARNING, GNUNET_free, GNUNET_log, GNUNET_log_strerror, GNUNET_malloc, GNUNET_malloc_large, GNUNET_new, GNUNET_NO, GNUNET_OK, GNUNET_strdup, GNUNET_YES, LOG_STRERROR_FILE, make_empty_file(), res, setBit(), and size.

Referenced by GNUNET_DATACACHE_create(), and run().

501 {
502  struct GNUNET_CONTAINER_BloomFilter *bf;
503  char *rbuff;
504  off_t pos;
505  int i;
506  size_t ui;
507  off_t fsize;
508  int must_read;
509 
510  GNUNET_assert (NULL != filename);
511  if ((k == 0) || (size == 0))
512  return NULL;
513  if (size < BUFFSIZE)
514  size = BUFFSIZE;
515  ui = 1;
516  while ((ui < size) && (ui * 2 > ui))
517  ui *= 2;
518  size = ui; /* make sure it's a power of 2 */
519 
521  /* Try to open a bloomfilter file */
527  if (NULL != bf->fh)
528  {
529  /* file existed, try to read it! */
530  must_read = GNUNET_YES;
531  if (GNUNET_OK != GNUNET_DISK_file_handle_size (bf->fh, &fsize))
532  {
534  GNUNET_free (bf);
535  return NULL;
536  }
537  if (0 == fsize)
538  {
539  /* found existing empty file, just overwrite */
540  if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL))
541  {
544  GNUNET_free (bf);
545  return NULL;
546  }
547  }
548  else if (fsize != ((off_t) size) * 4LL)
549  {
550  GNUNET_log (
552  _ (
553  "Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"),
554  (unsigned long long) (size * 4LL),
555  (unsigned long long) fsize);
557  GNUNET_free (bf);
558  return NULL;
559  }
560  }
561  else
562  {
563  /* file did not exist, don't read, just create */
564  must_read = GNUNET_NO;
570  if (NULL == bf->fh)
571  {
572  GNUNET_free (bf);
573  return NULL;
574  }
575  if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL))
576  {
579  GNUNET_free (bf);
580  return NULL;
581  }
582  }
584  /* Alloc block */
585  bf->bitArray = GNUNET_malloc_large (size);
586  if (NULL == bf->bitArray)
587  {
588  if (NULL != bf->fh)
590  GNUNET_free (bf->filename);
591  GNUNET_free (bf);
592  return NULL;
593  }
594  bf->bitArraySize = size;
595  bf->addressesPerElement = k;
596  if (GNUNET_YES != must_read)
597  return bf; /* already done! */
598  /* Read from the file what bits we can */
599  rbuff = GNUNET_malloc (BUFFSIZE);
600  pos = 0;
601  while (pos < ((off_t) size) * 8LL)
602  {
603  int res;
604 
605  res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE);
606  if (res == -1)
607  {
609  GNUNET_free (rbuff);
610  GNUNET_free (bf->filename);
612  GNUNET_free (bf);
613  return NULL;
614  }
615  if (res == 0)
616  break; /* is ok! we just did not use that many bits yet */
617  for (i = 0; i < res; i++)
618  {
619  if ((rbuff[i] & 0x0F) != 0)
620  setBit (bf->bitArray, pos + i * 2);
621  if ((rbuff[i] & 0xF0) != 0)
622  setBit (bf->bitArray, pos + i * 2 + 1);
623  }
624  if (res < BUFFSIZE)
625  break;
626  pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */
627  }
628  GNUNET_free (rbuff);
629  return bf;
630 }
int GNUNET_DISK_file_test(const char *fil)
Check that fil corresponds to a filename (of a file that exists and that is not a directory)...
Definition: disk.c:544
Create file if it doesn&#39;t exist.
int GNUNET_DISK_file_close(struct GNUNET_DISK_FileHandle *h)
Close an open file.
Definition: disk.c:1345
ssize_t GNUNET_DISK_file_read(const struct GNUNET_DISK_FileHandle *h, void *result, size_t len)
Read the contents of a binary file into a buffer.
Definition: disk.c:732
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static int make_empty_file(const struct GNUNET_DISK_FileHandle *fh, size_t size)
Creates a file filled with zeroes.
unsigned int addressesPerElement
How many bits we set for each stored element.
#define LOG_STRERROR_FILE(kind, syscall, filename)
#define GNUNET_NO
Definition: gnunet_common.h:78
char * filename
Filename of the filter.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_strdup(a)
Wrapper around GNUNET_xstrdup_.
#define _(String)
GNU gettext support macro.
Definition: platform.h:181
#define GNUNET_log_strerror(level, cmd)
Log an error message at log-level &#39;level&#39; that indicates a failure of the command &#39;cmd&#39; with the mess...
size_t bitArraySize
Size of bitArray in bytes.
static char * filename
static int res
static unsigned int size
Size of the "table".
Definition: peer.c:67
char * bitArray
The actual bloomfilter bit array.
struct GNUNET_DISK_FileHandle * fh
The bit counter file on disk.
static void setBit(char *bitArray, unsigned int bitIdx)
Sets a bit active in the bitArray.
int GNUNET_DISK_file_handle_size(struct GNUNET_DISK_FileHandle *fh, off_t *size)
Get the size of an open file.
Definition: disk.c:206
#define GNUNET_log(kind,...)
Open the file for both reading and writing.
#define GNUNET_YES
Definition: gnunet_common.h:77
#define BUFFSIZE
struct GNUNET_DISK_FileHandle * GNUNET_DISK_file_open(const char *fn, enum GNUNET_DISK_OpenFlags flags, enum GNUNET_DISK_AccessPermissions perm)
Open a file.
Definition: disk.c:1268
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_bloomfilter_init()

struct GNUNET_CONTAINER_BloomFilter* GNUNET_CONTAINER_bloomfilter_init ( const char *  data,
size_t  size,
unsigned int  k 
)

Create a Bloom filter from raw bits.

Parameters
datathe raw bits in memory (maybe NULL, in which case all bits should be considered to be zero).
sizethe size of the bloom-filter (number of bytes of storage space to use); also size of data – unless data is NULL. Must be a power of 2.
kthe number of GNUNET_CRYPTO_hash-functions to apply per element (number of bits set per element in the set)
Returns
the bloomfilter

Create a Bloom filter from raw bits.

Parameters
datathe raw bits in memory (maybe NULL, in which case all bits should be considered to be zero).
sizethe size of the bloom-filter (number of bytes of storage space to use); also size of data – unless data is NULL
kthe number of GNUNET_CRYPTO_hash-functions to apply per element (number of bits set per element in the set)
Returns
the bloomfilter

Definition at line 647 of file container_bloomfilter.c.

References GNUNET_CONTAINER_BloomFilter::addressesPerElement, GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, GNUNET_CONTAINER_BloomFilter::fh, GNUNET_CONTAINER_BloomFilter::filename, GNUNET_free, GNUNET_malloc_large, GNUNET_memcpy, GNUNET_new, and size.

Referenced by GNUNET_BLOCK_GROUP_bf_create(), GNUNET_CONTAINER_bloomfilter_copy(), GNUNET_DATACACHE_create(), handle_dht_local_put(), handle_dht_p2p_get(), handle_dht_p2p_put(), handle_intersection_p2p_bf(), run(), send_bloomfilter(), send_find_peer_message(), setup_filter(), and transmit_request().

650 {
651  struct GNUNET_CONTAINER_BloomFilter *bf;
652 
653  if ((0 == k) || (0 == size))
654  return NULL;
656  bf->filename = NULL;
657  bf->fh = NULL;
659  if (NULL == bf->bitArray)
660  {
661  GNUNET_free (bf);
662  return NULL;
663  }
664  bf->bitArraySize = size;
665  bf->addressesPerElement = k;
666  if (NULL != data)
668  return bf;
669 }
unsigned int addressesPerElement
How many bits we set for each stored element.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
char * filename
Filename of the filter.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
size_t bitArraySize
Size of bitArray in bytes.
static unsigned int size
Size of the "table".
Definition: peer.c:67
char * bitArray
The actual bloomfilter bit array.
struct GNUNET_DISK_FileHandle * fh
The bit counter file on disk.
uint32_t data
The data value.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_bloomfilter_get_raw_data()

int GNUNET_CONTAINER_bloomfilter_get_raw_data ( const struct GNUNET_CONTAINER_BloomFilter bf,
char *  data,
size_t  size 
)

Copy the raw data of this Bloom filter into the given data array.

Parameters
datawhere to write the data
sizethe size of the given data array
Returns
GNUNET_SYSERR if the data array of the wrong size

Copy the raw data of this Bloom filter into the given data array.

Parameters
bfbloomfilter to take the raw data from
datawhere to write the data
sizethe size of the given data array
Returns
GNUNET_SYSERR if the data array is not big enough

Definition at line 682 of file container_bloomfilter.c.

References GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, GNUNET_memcpy, GNUNET_OK, and GNUNET_SYSERR.

Referenced by bf_group_serialize_cb(), GDS_NEIGHBOURS_handle_get(), GDS_NEIGHBOURS_handle_put(), and send_bloomfilter().

686 {
687  if (NULL == bf)
688  return GNUNET_SYSERR;
689  if (bf->bitArraySize != size)
690  return GNUNET_SYSERR;
692  return GNUNET_OK;
693 }
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
size_t bitArraySize
Size of bitArray in bytes.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
static unsigned int size
Size of the "table".
Definition: peer.c:67
char * bitArray
The actual bloomfilter bit array.
uint32_t data
The data value.
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_bloomfilter_test()

int GNUNET_CONTAINER_bloomfilter_test ( const struct GNUNET_CONTAINER_BloomFilter bf,
const struct GNUNET_HashCode e 
)

Test if an element is in the filter.

Parameters
ethe element
bfthe filter
Returns
GNUNET_YES if the element is in the filter, GNUNET_NO if not

Definition at line 741 of file container_bloomfilter.c.

References GNUNET_YES, iterateBits(), res, and testBitCallback().

Referenced by filtered_map_initialization(), find_advertisable_hello(), GDS_am_closest_peer(), GDS_NEIGHBOURS_handle_get(), GDS_NEIGHBOURS_handle_put(), get_target_peers(), GNUNET_BLOCK_GROUP_bf_test_and_set(), GNUNET_DATACACHE_get(), handle_dht_p2p_get(), handle_dht_p2p_put(), handle_get_key(), handle_put(), iterator_bf_reduce(), and select_peer().

744 {
745  int res;
746 
747  if (NULL == bf)
748  return GNUNET_YES;
749  res = GNUNET_YES;
750  iterateBits (bf, &testBitCallback, &res, e);
751  return res;
752 }
static int testBitCallback(void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit)
Callback: test if all bits are set.
static void iterateBits(const struct GNUNET_CONTAINER_BloomFilter *bf, BitIterator callback, void *arg, const struct GNUNET_HashCode *key)
Call an iterator for each bit that the bloomfilter must test or set for this element.
static int res
#define GNUNET_YES
Definition: gnunet_common.h:77
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_bloomfilter_add()

void GNUNET_CONTAINER_bloomfilter_add ( struct GNUNET_CONTAINER_BloomFilter bf,
const struct GNUNET_HashCode e 
)

Add an element to the filter.

Parameters
bfthe filter
ethe element

Definition at line 762 of file container_bloomfilter.c.

References incrementBitCallback(), and iterateBits().

Referenced by add_key_to_bloomfilter(), bf_group_mark_seen_cb(), GDS_NEIGHBOURS_handle_get(), GDS_NEIGHBOURS_handle_put(), get_target_peers(), GNUNET_BLOCK_GROUP_bf_test_and_set(), GNUNET_CONTAINER_bloomfilter_resize(), GNUNET_DATACACHE_put(), iterator_bf_create(), put_continuation(), schedule_next_hello(), and setup_filter().

764 {
765  if (NULL == bf)
766  return;
767  iterateBits (bf, &incrementBitCallback, bf, e);
768 }
static int incrementBitCallback(void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit)
Callback: increment bit.
static void iterateBits(const struct GNUNET_CONTAINER_BloomFilter *bf, BitIterator callback, void *arg, const struct GNUNET_HashCode *key)
Call an iterator for each bit that the bloomfilter must test or set for this element.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_bloomfilter_remove()

void GNUNET_CONTAINER_bloomfilter_remove ( struct GNUNET_CONTAINER_BloomFilter bf,
const struct GNUNET_HashCode e 
)

Remove an element from the filter.

Parameters
bfthe filter
ethe element to remove

Definition at line 855 of file container_bloomfilter.c.

References decrementBitCallback(), GNUNET_CONTAINER_BloomFilter::filename, and iterateBits().

Referenced by env_delete_notify(), expired_processor(), quota_processor(), and remove_continuation().

857 {
858  if (NULL == bf)
859  return;
860  if (NULL == bf->filename)
861  return;
862  iterateBits (bf, &decrementBitCallback, bf, e);
863 }
char * filename
Filename of the filter.
static void iterateBits(const struct GNUNET_CONTAINER_BloomFilter *bf, BitIterator callback, void *arg, const struct GNUNET_HashCode *key)
Call an iterator for each bit that the bloomfilter must test or set for this element.
static int decrementBitCallback(void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf, unsigned int bit)
Callback: decrement bit.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_bloomfilter_copy()

struct GNUNET_CONTAINER_BloomFilter* GNUNET_CONTAINER_bloomfilter_copy ( const struct GNUNET_CONTAINER_BloomFilter bf)

Create a copy of a bloomfilter.

Parameters
bfthe filter
Returns
copy of bf

Create a copy of a bloomfilter.

Any association with a file on-disk will be lost in the process.

Parameters
bfthe filter to copy
Returns
copy of the bf

Definition at line 125 of file container_bloomfilter.c.

References GNUNET_CONTAINER_BloomFilter::addressesPerElement, GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, and GNUNET_CONTAINER_bloomfilter_init().

127 {
129  bf->bitArraySize,
130  bf->addressesPerElement);
131 }
struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_init(const char *data, size_t size, unsigned int k)
Create a bloom filter from raw bits.
unsigned int addressesPerElement
How many bits we set for each stored element.
size_t bitArraySize
Size of bitArray in bytes.
char * bitArray
The actual bloomfilter bit array.
Here is the call graph for this function:

◆ GNUNET_CONTAINER_bloomfilter_free()

void GNUNET_CONTAINER_bloomfilter_free ( struct GNUNET_CONTAINER_BloomFilter bf)

Free the space associcated with a filter in memory, flush to drive if needed (do not free the space on the drive).

Parameters
bfthe filter

Free the space associcated with a filter in memory, flush to drive if needed (do not free the space on the drive).

Parameters
bfthe filter

Definition at line 704 of file container_bloomfilter.c.

References GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::fh, GNUNET_CONTAINER_BloomFilter::filename, GNUNET_DISK_file_close(), GNUNET_free, and GNUNET_free_non_null.

Referenced by bf_group_destroy_cb(), cleaning_task(), consider_for_advertising(), find_advertisable_hello(), free_peer(), GNUNET_DATACACHE_destroy(), handle_dht_local_put(), handle_dht_p2p_get(), handle_dht_p2p_put(), intersection_op_cancel(), process_bf(), process_peer(), process_stat_done(), send_bloomfilter(), send_find_peer_message(), and transmit_request().

705 {
706  if (NULL == bf)
707  return;
708  if (bf->fh != NULL)
711  GNUNET_free (bf->bitArray);
712  GNUNET_free (bf);
713 }
int GNUNET_DISK_file_close(struct GNUNET_DISK_FileHandle *h)
Close an open file.
Definition: disk.c:1345
char * filename
Filename of the filter.
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
char * bitArray
The actual bloomfilter bit array.
struct GNUNET_DISK_FileHandle * fh
The bit counter file on disk.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_bloomfilter_get_size()

size_t GNUNET_CONTAINER_bloomfilter_get_size ( const struct GNUNET_CONTAINER_BloomFilter bf)

Get size of the bloom filter.

Parameters
bfthe filter
Returns
number of bytes used for the data of the bloom filter

Definition at line 109 of file container_bloomfilter.c.

References GNUNET_CONTAINER_BloomFilter::bitArraySize.

111 {
112  if (bf == NULL)
113  return 0;
114  return bf->bitArraySize;
115 }
size_t bitArraySize
Size of bitArray in bytes.

◆ GNUNET_CONTAINER_bloomfilter_clear()

void GNUNET_CONTAINER_bloomfilter_clear ( struct GNUNET_CONTAINER_BloomFilter bf)

Reset a Bloom filter to empty.

Parameters
bfthe filter

Reset a Bloom filter to empty.

Clears the file on disk.

Parameters
bfthe filter

Definition at line 722 of file container_bloomfilter.c.

References GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, GNUNET_CONTAINER_BloomFilter::fh, GNUNET_CONTAINER_BloomFilter::filename, and make_empty_file().

723 {
724  if (NULL == bf)
725  return;
726 
727  memset (bf->bitArray, 0, bf->bitArraySize);
728  if (bf->filename != NULL)
729  make_empty_file (bf->fh, bf->bitArraySize * 4LL);
730 }
static int make_empty_file(const struct GNUNET_DISK_FileHandle *fh, size_t size)
Creates a file filled with zeroes.
char * filename
Filename of the filter.
size_t bitArraySize
Size of bitArray in bytes.
char * bitArray
The actual bloomfilter bit array.
struct GNUNET_DISK_FileHandle * fh
The bit counter file on disk.
Here is the call graph for this function:

◆ GNUNET_CONTAINER_bloomfilter_or()

int GNUNET_CONTAINER_bloomfilter_or ( struct GNUNET_CONTAINER_BloomFilter bf,
const char *  data,
size_t  size 
)

"or" the entries of the given raw data array with the data of the given Bloom filter.

Assumes that the size of the data array and the current filter match.

Parameters
bfthe filter
datadata to OR-in
sizesize of data
Returns
GNUNET_OK on success

"or" the entries of the given raw data array with the data of the given Bloom filter.

Assumes that the size of the data array and the current filter match.

Parameters
bfthe filter
datathe data to or-in
sizenumber of bytes in data

Definition at line 782 of file container_bloomfilter.c.

References GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, data, dc, GNUNET_OK, GNUNET_SYSERR, GNUNET_YES, and size.

785 {
786  unsigned int i;
787  unsigned int n;
788  unsigned long long *fc;
789  const unsigned long long *dc;
790 
791  if (NULL == bf)
792  return GNUNET_YES;
793  if (bf->bitArraySize != size)
794  return GNUNET_SYSERR;
795  fc = (unsigned long long *) bf->bitArray;
796  dc = (const unsigned long long *) data;
797  n = size / sizeof(unsigned long long);
798 
799  for (i = 0; i < n; i++)
800  fc[i] |= dc[i];
801  for (i = n * sizeof(unsigned long long); i < size; i++)
802  bf->bitArray[i] |= data[i];
803  return GNUNET_OK;
804 }
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
size_t bitArraySize
Size of bitArray in bytes.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
static unsigned int size
Size of the "table".
Definition: peer.c:67
char * bitArray
The actual bloomfilter bit array.
#define GNUNET_YES
Definition: gnunet_common.h:77
uint32_t data
The data value.
static struct GNUNET_FS_DownloadContext * dc

◆ GNUNET_CONTAINER_bloomfilter_or2()

int GNUNET_CONTAINER_bloomfilter_or2 ( struct GNUNET_CONTAINER_BloomFilter bf,
const struct GNUNET_CONTAINER_BloomFilter to_or 
)

"or" the entries of the given raw data array with the data of the given Bloom filter.

Assumes that the size of the two filters matches.

Parameters
bfthe filter
to_orthe bloomfilter to or-in
Returns
GNUNET_OK on success

"or" the entries of the given raw data array with the data of the given Bloom filter.

Assumes that the size of the data array and the current filter match.

Parameters
bfthe filter
to_orthe bloomfilter to or-in
Returns
GNUNET_OK on success

Definition at line 818 of file container_bloomfilter.c.

References GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, dc, GNUNET_break, GNUNET_OK, GNUNET_SYSERR, and size.

Referenced by bf_group_merge_cb().

821 {
822  unsigned int i;
823  unsigned int n;
824  unsigned long long *fc;
825  const unsigned long long *dc;
826  size_t size;
827 
828  if (NULL == bf)
829  return GNUNET_OK;
830  if (bf->bitArraySize != to_or->bitArraySize)
831  {
832  GNUNET_break (0);
833  return GNUNET_SYSERR;
834  }
835  size = bf->bitArraySize;
836  fc = (unsigned long long *) bf->bitArray;
837  dc = (const unsigned long long *) to_or->bitArray;
838  n = size / sizeof(unsigned long long);
839 
840  for (i = 0; i < n; i++)
841  fc[i] |= dc[i];
842  for (i = n * sizeof(unsigned long long); i < size; i++)
843  bf->bitArray[i] |= to_or->bitArray[i];
844  return GNUNET_OK;
845 }
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
size_t bitArraySize
Size of bitArray in bytes.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
static unsigned int size
Size of the "table".
Definition: peer.c:67
char * bitArray
The actual bloomfilter bit array.
static struct GNUNET_FS_DownloadContext * dc
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_bloomfilter_resize()

void GNUNET_CONTAINER_bloomfilter_resize ( struct GNUNET_CONTAINER_BloomFilter bf,
GNUNET_CONTAINER_HashCodeIterator  iterator,
void *  iterator_cls,
size_t  size,
unsigned int  k 
)

Resize a bloom filter.

Note that this operation is pretty costly. Essentially, the Bloom filter needs to be completely re-build.

Parameters
bfthe filter
iteratoran iterator over all elements stored in the BF
iterator_clsclosure for iterator
sizethe new size for the filter
kthe new number of GNUNET_CRYPTO_hash-function to apply per element

Note that this operation is pretty costly. Essentially, the bloom filter needs to be completely re-build.

Parameters
bfthe filter
iteratoran iterator over all elements stored in the BF
iterator_clsargument to the iterator function
sizethe new size for the filter
kthe new number of GNUNET_CRYPTO_hash-function to apply per element

Definition at line 878 of file container_bloomfilter.c.

References GNUNET_CONTAINER_BloomFilter::addressesPerElement, GNUNET_CONTAINER_BloomFilter::bitArray, GNUNET_CONTAINER_BloomFilter::bitArraySize, GNUNET_CONTAINER_BloomFilter::fh, GNUNET_CONTAINER_BloomFilter::filename, GNUNET_CONTAINER_bloomfilter_add(), GNUNET_free, GNUNET_malloc, GNUNET_YES, make_empty_file(), and size.

883 {
884  struct GNUNET_HashCode hc;
885  unsigned int i;
886 
887  GNUNET_free (bf->bitArray);
888  i = 1;
889  while (i < size)
890  i *= 2;
891  size = i; /* make sure it's a power of 2 */
892  bf->addressesPerElement = k;
893  bf->bitArraySize = size;
894  bf->bitArray = GNUNET_malloc (size);
895  if (NULL != bf->filename)
896  make_empty_file (bf->fh, bf->bitArraySize * 4LL);
897  while (GNUNET_YES == iterator (iterator_cls, &hc))
899 }
static int iterator(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.
void GNUNET_CONTAINER_bloomfilter_add(struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Add an element to the filter.
static int make_empty_file(const struct GNUNET_DISK_FileHandle *fh, size_t size)
Creates a file filled with zeroes.
unsigned int addressesPerElement
How many bits we set for each stored element.
char * filename
Filename of the filter.
size_t bitArraySize
Size of bitArray in bytes.
A 512-bit hashcode.
static unsigned int size
Size of the "table".
Definition: peer.c:67
char * bitArray
The actual bloomfilter bit array.
struct GNUNET_DISK_FileHandle * fh
The bit counter file on disk.
#define GNUNET_YES
Definition: gnunet_common.h:77
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function: