GNUnet  0.10.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 214 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 490 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().

493 {
494  struct GNUNET_CONTAINER_BloomFilter *bf;
495  char *rbuff;
496  off_t pos;
497  int i;
498  size_t ui;
499  off_t fsize;
500  int must_read;
501 
502  GNUNET_assert(NULL != filename);
503  if ((k == 0) || (size == 0))
504  return NULL;
505  if (size < BUFFSIZE)
506  size = BUFFSIZE;
507  ui = 1;
508  while ((ui < size) && (ui * 2 > ui))
509  ui *= 2;
510  size = ui; /* make sure it's a power of 2 */
511 
513  /* Try to open a bloomfilter file */
519  if (NULL != bf->fh)
520  {
521  /* file existed, try to read it! */
522  must_read = GNUNET_YES;
523  if (GNUNET_OK != GNUNET_DISK_file_handle_size(bf->fh, &fsize))
524  {
526  GNUNET_free(bf);
527  return NULL;
528  }
529  if (0 == fsize)
530  {
531  /* found existing empty file, just overwrite */
532  if (GNUNET_OK != make_empty_file(bf->fh, size * 4LL))
533  {
536  GNUNET_free(bf);
537  return NULL;
538  }
539  }
540  else if (fsize != ((off_t)size) * 4LL)
541  {
542  GNUNET_log(
544  _(
545  "Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"),
546  (unsigned long long)(size * 4LL),
547  (unsigned long long)fsize);
549  GNUNET_free(bf);
550  return NULL;
551  }
552  }
553  else
554  {
555  /* file did not exist, don't read, just create */
556  must_read = GNUNET_NO;
562  if (NULL == bf->fh)
563  {
564  GNUNET_free(bf);
565  return NULL;
566  }
567  if (GNUNET_OK != make_empty_file(bf->fh, size * 4LL))
568  {
571  GNUNET_free(bf);
572  return NULL;
573  }
574  }
576  /* Alloc block */
577  bf->bitArray = GNUNET_malloc_large(size);
578  if (NULL == bf->bitArray)
579  {
580  if (NULL != bf->fh)
582  GNUNET_free(bf->filename);
583  GNUNET_free(bf);
584  return NULL;
585  }
586  bf->bitArraySize = size;
587  bf->addressesPerElement = k;
588  if (GNUNET_YES != must_read)
589  return bf; /* already done! */
590  /* Read from the file what bits we can */
591  rbuff = GNUNET_malloc(BUFFSIZE);
592  pos = 0;
593  while (pos < ((off_t)size) * 8LL)
594  {
595  int res;
596 
597  res = GNUNET_DISK_file_read(bf->fh, rbuff, BUFFSIZE);
598  if (res == -1)
599  {
601  GNUNET_free(rbuff);
602  GNUNET_free(bf->filename);
604  GNUNET_free(bf);
605  return NULL;
606  }
607  if (res == 0)
608  break; /* is ok! we just did not use that many bits yet */
609  for (i = 0; i < res; i++)
610  {
611  if ((rbuff[i] & 0x0F) != 0)
612  setBit(bf->bitArray, pos + i * 2);
613  if ((rbuff[i] & 0xF0) != 0)
614  setBit(bf->bitArray, pos + i * 2 + 1);
615  }
616  if (res < BUFFSIZE)
617  break;
618  pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */
619  }
620  GNUNET_free(rbuff);
621  return bf;
622 }
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:541
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:1339
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:729
#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:66
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:203
#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:1262
#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 639 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().

642 {
643  struct GNUNET_CONTAINER_BloomFilter *bf;
644 
645  if ((0 == k) || (0 == size))
646  return NULL;
648  bf->filename = NULL;
649  bf->fh = NULL;
651  if (NULL == bf->bitArray)
652  {
653  GNUNET_free(bf);
654  return NULL;
655  }
656  bf->bitArraySize = size;
657  bf->addressesPerElement = k;
658  if (NULL != data)
660  return bf;
661 }
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:66
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 674 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().

678 {
679  if (NULL == bf)
680  return GNUNET_SYSERR;
681  if (bf->bitArraySize != size)
682  return GNUNET_SYSERR;
684  return GNUNET_OK;
685 }
#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:66
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 733 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().

736 {
737  int res;
738 
739  if (NULL == bf)
740  return GNUNET_YES;
741  res = GNUNET_YES;
742  iterateBits(bf, &testBitCallback, &res, e);
743  return res;
744 }
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 754 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().

756 {
757  if (NULL == bf)
758  return;
759  iterateBits(bf, &incrementBitCallback, bf, e);
760 }
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 846 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().

848 {
849  if (NULL == bf)
850  return;
851  if (NULL == bf->filename)
852  return;
853  iterateBits(bf, &decrementBitCallback, bf, e);
854 }
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 124 of file container_bloomfilter.c.

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

126 {
128  bf->bitArraySize,
129  bf->addressesPerElement);
130 }
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 696 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().

697 {
698  if (NULL == bf)
699  return;
700  if (bf->fh != NULL)
703  GNUNET_free(bf->bitArray);
704  GNUNET_free(bf);
705 }
int GNUNET_DISK_file_close(struct GNUNET_DISK_FileHandle *h)
Close an open file.
Definition: disk.c:1339
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 108 of file container_bloomfilter.c.

References GNUNET_CONTAINER_BloomFilter::bitArraySize.

110 {
111  if (bf == NULL)
112  return 0;
113  return bf->bitArraySize;
114 }
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 714 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().

715 {
716  if (NULL == bf)
717  return;
718 
719  memset(bf->bitArray, 0, bf->bitArraySize);
720  if (bf->filename != NULL)
721  make_empty_file(bf->fh, bf->bitArraySize * 4LL);
722 }
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 774 of file container_bloomfilter.c.

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

777 {
778  unsigned int i;
779  unsigned int n;
780  unsigned long long *fc;
781  const unsigned long long *dc;
782 
783  if (NULL == bf)
784  return GNUNET_YES;
785  if (bf->bitArraySize != size)
786  return GNUNET_SYSERR;
787  fc = (unsigned long long *)bf->bitArray;
788  dc = (const unsigned long long *)data;
789  n = size / sizeof(unsigned long long);
790 
791  for (i = 0; i < n; i++)
792  fc[i] |= dc[i];
793  for (i = n * sizeof(unsigned long long); i < size; i++)
794  bf->bitArray[i] |= data[i];
795  return GNUNET_OK;
796 }
#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:66
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 809 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().

812 {
813  unsigned int i;
814  unsigned int n;
815  unsigned long long *fc;
816  const unsigned long long *dc;
817  size_t size;
818 
819  if (NULL == bf)
820  return GNUNET_OK;
821  if (bf->bitArraySize != to_or->bitArraySize)
822  {
823  GNUNET_break(0);
824  return GNUNET_SYSERR;
825  }
826  size = bf->bitArraySize;
827  fc = (unsigned long long *)bf->bitArray;
828  dc = (const unsigned long long *)to_or->bitArray;
829  n = size / sizeof(unsigned long long);
830 
831  for (i = 0; i < n; i++)
832  fc[i] |= dc[i];
833  for (i = n * sizeof(unsigned long long); i < size; i++)
834  bf->bitArray[i] |= to_or->bitArray[i];
835  return GNUNET_OK;
836 }
#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:66
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 868 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, iterator(), make_empty_file(), and size.

873 {
874  struct GNUNET_HashCode hc;
875  unsigned int i;
876 
877  GNUNET_free(bf->bitArray);
878  i = 1;
879  while (i < size)
880  i *= 2;
881  size = i; /* make sure it's a power of 2 */
882  bf->addressesPerElement = k;
883  bf->bitArraySize = size;
884  bf->bitArray = GNUNET_malloc(size);
885  if (NULL != bf->filename)
886  make_empty_file(bf->fh, bf->bitArraySize * 4LL);
887  while (GNUNET_YES == iterator(iterator_cls, &hc))
889 }
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:66
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: