src/util/container_bloomfilter.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001, 2002, 2003, 2004, 2006, 2008 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 2, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20 /**
  21  * @file util/container_bloomfilter.c
  22  * @brief data structure used to reduce disk accesses.
  23  *
  24  * The idea basically: Create a signature for each element in the
  25  * database. Add those signatures to a bit array. When doing a lookup,
  26  * check if the bit array matches the signature of the requested
  27  * element. If yes, address the disk, otherwise return 'not found'.
  28  *
  29  * A property of the bloom filter is that sometimes we will have
  30  * a match even if the element is not on the disk (then we do
  31  * an unnecessary disk access), but what's most important is that
  32  * we never get a single "false negative".
  33  *
  34  * To be able to delete entries from the bloom filter, we maintain
  35  * a 4 bit counter in the file on the drive (we still use only one
  36  * bit in memory).
  37  *
  38  * @author Igor Wronsky
  39  * @author Christian Grothoff
  40  */
  41
  42 #include "platform.h"
  43 #include "gnunet_common.h"
  44 #include "gnunet_container_lib.h"
  45 #include "gnunet_disk_lib.h"
  46
  47 struct GNUNET_CONTAINER_BloomFilter
  48 {
  49
  50   /**
  51    * The actual bloomfilter bit array
  52    */
  53   char *bitArray;
  54
  55   /**
  56    * Filename of the filter
  57    */
  58   char *filename;
  59
  60   /**
  61    * The bit counter file on disk
  62    */
  63   struct GNUNET_DISK_FileHandle *fh;
  64
  65   /**
  66    * How many bits we set for each stored element
  67    */
  68   unsigned int addressesPerElement;
  69
  70   /**
  71    * Size of bitArray in bytes
  72    */
  73   size_t bitArraySize;
  74
  75 };
  76
  77
  78
  79 /**
  80  * Get size of the bloom filter.
  81  *
  82  * @param bf the filter
  83  * @return number of bytes used for the data of the bloom filter
  84  */
  85 size_t
  86 GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter
  87                                        *bf)
  88 {
  89   if (bf == NULL)
  90     return 0;
  91   return bf->bitArraySize;
  92 }
  93
  94
  95 /**
  96  * Copy an existing memory.  Any association with a file
  97  * on-disk will be lost in the process.
  98  * @param bf the filter to copy
  99  * @return copy of the bf
 100  */
 101 struct GNUNET_CONTAINER_BloomFilter *
 102 GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter
 103                                    *bf)
 104 {
 105   return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray, bf->bitArraySize,
 106                                             bf->addressesPerElement);
 107 }
 108
 109
 110 /**
 111  * Sets a bit active in the bitArray. Increment bit-specific
 112  * usage counter on disk only if below 4bit max (==15).
 113  *
 114  * @param bitArray memory area to set the bit in
 115  * @param bitIdx which bit to set
 116  */
 117 static void
 118 setBit (char *bitArray, unsigned int bitIdx)
 119 {
 120   size_t arraySlot;
 121   unsigned int targetBit;
 122
 123   arraySlot = bitIdx / 8;
 124   targetBit = (1L << (bitIdx % 8));
 125   bitArray[arraySlot] |= targetBit;
 126 }
 127
 128 /**
 129  * Clears a bit from bitArray. Bit is cleared from the array
 130  * only if the respective usage counter on the disk hits/is zero.
 131  *
 132  * @param bitArray memory area to set the bit in
 133  * @param bitIdx which bit to unset
 134  */
 135 static void
 136 clearBit (char *bitArray, unsigned int bitIdx)
 137 {
 138   size_t slot;
 139   unsigned int targetBit;
 140
 141   slot = bitIdx / 8;
 142   targetBit = (1L << (bitIdx % 8));
 143   bitArray[slot] = bitArray[slot] & (~targetBit);
 144 }
 145
 146 /**
 147  * Checks if a bit is active in the bitArray
 148  *
 149  * @param bitArray memory area to set the bit in
 150  * @param bitIdx which bit to test
 151  * @return GNUNET_YES if the bit is set, GNUNET_NO if not.
 152  */
 153 static int
 154 testBit (char *bitArray, unsigned int bitIdx)
 155 {
 156   size_t slot;
 157   unsigned int targetBit;
 158
 159   slot = bitIdx / 8;
 160   targetBit = (1L << (bitIdx % 8));
 161   if (bitArray[slot] & targetBit)
 162     return GNUNET_YES;
 163   else
 164     return GNUNET_NO;
 165 }
 166
 167 /**
 168  * Sets a bit active in the bitArray and increments
 169  * bit-specific usage counter on disk (but only if
 170  * the counter was below 4 bit max (==15)).
 171  *
 172  * @param bitArray memory area to set the bit in
 173  * @param bitIdx which bit to test
 174  * @param fh A file to keep the 4 bit address usage counters in
 175  */
 176 static void
 177 incrementBit (char *bitArray, unsigned int bitIdx,
 178               const struct GNUNET_DISK_FileHandle *fh)
 179 {
 180   off_t fileSlot;
 181   unsigned char value;
 182   unsigned int high;
 183   unsigned int low;
 184   unsigned int targetLoc;
 185
 186   setBit (bitArray, bitIdx);
 187   if (GNUNET_DISK_handle_invalid (fh))
 188     return;
 189   /* Update the counter file on disk */
 190   fileSlot = bitIdx / 2;
 191   targetLoc = bitIdx % 2;
 192
 193   GNUNET_assert (fileSlot ==
 194                  GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET));
 195   if (1 != GNUNET_DISK_file_read (fh, &value, 1))
 196     value = 0;
 197   low = value & 0xF;
 198   high = (value & (~0xF)) >> 4;
 199
 200   if (targetLoc == 0)
 201   {
 202     if (low < 0xF)
 203       low++;
 204   }
 205   else
 206   {
 207     if (high < 0xF)
 208       high++;
 209   }
 210   value = ((high << 4) | low);
 211   GNUNET_assert (fileSlot ==
 212                  GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET));
 213   GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1));
 214 }
 215
 216 /**
 217  * Clears a bit from bitArray if the respective usage
 218  * counter on the disk hits/is zero.
 219  *
 220  * @param bitArray memory area to set the bit in
 221  * @param bitIdx which bit to test
 222  * @param fh A file to keep the 4bit address usage counters in
 223  */
 224 static void
 225 decrementBit (char *bitArray, unsigned int bitIdx,
 226               const struct GNUNET_DISK_FileHandle *fh)
 227 {
 228   off_t fileSlot;
 229   unsigned char value;
 230   unsigned int high;
 231   unsigned int low;
 232   unsigned int targetLoc;
 233
 234   if (GNUNET_DISK_handle_invalid (fh))
 235     return;                     /* cannot decrement! */
 236   /* Each char slot in the counter file holds two 4 bit counters */
 237   fileSlot = bitIdx / 2;
 238   targetLoc = bitIdx % 2;
 239   GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET);
 240   if (1 != GNUNET_DISK_file_read (fh, &value, 1))
 241     value = 0;
 242   low = value & 0xF;
 243   high = (value & 0xF0) >> 4;
 244
 245   /* decrement, but once we have reached the max, never go back! */
 246   if (targetLoc == 0)
 247   {
 248     if ((low > 0) && (low < 0xF))
 249       low--;
 250     if (low == 0)
 251     {
 252       clearBit (bitArray, bitIdx);
 253     }
 254   }
 255   else
 256   {
 257     if ((high > 0) && (high < 0xF))
 258       high--;
 259     if (high == 0)
 260     {
 261       clearBit (bitArray, bitIdx);
 262     }
 263   }
 264   value = ((high << 4) | low);
 265   GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET);
 266   GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1));
 267 }
 268
 269 #define BUFFSIZE 65536
 270
 271 /**
 272  * Creates a file filled with zeroes
 273  *
 274  * @param fh the file handle
 275  * @param size the size of the file
 276  * @return GNUNET_OK if created ok, GNUNET_SYSERR otherwise
 277  */
 278 static int
 279 makeEmptyFile (const struct GNUNET_DISK_FileHandle *fh, size_t size)
 280 {
 281   char *buffer;
 282   size_t bytesleft = size;
 283   int res = 0;
 284
 285   if (GNUNET_DISK_handle_invalid (fh))
 286     return GNUNET_SYSERR;
 287   buffer = GNUNET_malloc (BUFFSIZE);
 288   memset (buffer, 0, BUFFSIZE);
 289   GNUNET_DISK_file_seek (fh, 0, GNUNET_DISK_SEEK_SET);
 290
 291   while (bytesleft > 0)
 292   {
 293     if (bytesleft > BUFFSIZE)
 294     {
 295       res = GNUNET_DISK_file_write (fh, buffer, BUFFSIZE);
 296       bytesleft -= BUFFSIZE;
 297     }
 298     else
 299     {
 300       res = GNUNET_DISK_file_write (fh, buffer, bytesleft);
 301       bytesleft = 0;
 302     }
 303     GNUNET_assert (res != GNUNET_SYSERR);
 304   }
 305   GNUNET_free (buffer);
 306   return GNUNET_OK;
 307 }
 308
 309 /* ************** GNUNET_CONTAINER_BloomFilter iterator ********* */
 310
 311 /**
 312  * Iterator (callback) method to be called by the
 313  * bloomfilter iterator on each bit that is to be
 314  * set or tested for the key.
 315  *
 316  * @param cls closure
 317  * @param bf the filter to manipulate
 318  * @param bit the current bit
 319  */
 320 typedef void (*BitIterator) (void *cls,
 321                              const struct GNUNET_CONTAINER_BloomFilter * bf,
 322                              unsigned int bit);
 323
 324 /**
 325  * Call an iterator for each bit that the bloomfilter
 326  * must test or set for this element.
 327  *
 328  * @param bf the filter
 329  * @param callback the method to call
 330  * @param arg extra argument to callback
 331  * @param key the key for which we iterate over the BF bits
 332  */
 333 static void
 334 iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf,
 335              BitIterator callback, void *arg, const GNUNET_HashCode * key)
 336 {
 337   GNUNET_HashCode tmp[2];
 338   int bitCount;
 339   int round;
 340   unsigned int slot = 0;
 341
 342   bitCount = bf->addressesPerElement;
 343   tmp[0] = *key;
 344   round = 0;
 345   while (bitCount > 0)
 346   {
 347     while (slot < (sizeof (GNUNET_HashCode) / sizeof (uint32_t)))
 348     {
 349       callback (arg, bf,
 350                 (((uint32_t *) & tmp[round & 1])[slot]) &
 351                 ((bf->bitArraySize * 8) - 1));
 352       slot++;
 353       bitCount--;
 354       if (bitCount == 0)
 355         break;
 356     }
 357     if (bitCount > 0)
 358     {
 359       GNUNET_CRYPTO_hash (&tmp[round & 1], sizeof (GNUNET_HashCode),
 360                           &tmp[(round + 1) & 1]);
 361       round++;
 362       slot = 0;
 363     }
 364   }
 365 }
 366
 367 /**
 368  * Callback: increment bit
 369  *
 370  * @param cls pointer to writeable form of bf
 371  * @param bf the filter to manipulate
 372  * @param bit the bit to increment
 373  */
 374 static void
 375 incrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 376                       unsigned int bit)
 377 {
 378   struct GNUNET_CONTAINER_BloomFilter *b = cls;
 379
 380   incrementBit (b->bitArray, bit, bf->fh);
 381 }
 382
 383 /**
 384  * Callback: decrement bit
 385  *
 386  * @param cls pointer to writeable form of bf
 387  * @param bf the filter to manipulate
 388  * @param bit the bit to decrement
 389  */
 390 static void
 391 decrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 392                       unsigned int bit)
 393 {
 394   struct GNUNET_CONTAINER_BloomFilter *b = cls;
 395
 396   decrementBit (b->bitArray, bit, bf->fh);
 397 }
 398
 399 /**
 400  * Callback: test if all bits are set
 401  *
 402  * @param cls pointer set to GNUNET_NO if bit is not set
 403  * @param bf the filter
 404  * @param bit the bit to test
 405  */
 406 static void
 407 testBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 408                  unsigned int bit)
 409 {
 410   int *arg = cls;
 411
 412   if (GNUNET_NO == testBit (bf->bitArray, bit))
 413     *arg = GNUNET_NO;
 414 }
 415
 416 /* *********************** INTERFACE **************** */
 417
 418 /**
 419  * Load a bloom-filter from a file.
 420  *
 421  * @param filename the name of the file (or the prefix)
 422  * @param size the size of the bloom-filter (number of
 423  *        bytes of storage space to use)
 424  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
 425  *        element (number of bits set per element in the set)
 426  * @return the bloomfilter
 427  */
 428 struct GNUNET_CONTAINER_BloomFilter *
 429 GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size,
 430                                    unsigned int k)
 431 {
 432   struct GNUNET_CONTAINER_BloomFilter *bf;
 433   char *rbuff;
 434   off_t pos;
 435   int i;
 436   size_t ui;
 437
 438   GNUNET_assert (NULL != filename);
 439   if ((k == 0) || (size == 0))
 440     return NULL;
 441   if (size < BUFFSIZE)
 442     size = BUFFSIZE;
 443   ui = 1;
 444   while (ui < size)
 445     ui *= 2;
 446   size = ui;                    /* make sure it's a power of 2 */
 447
 448   bf = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_BloomFilter));
 449   /* Try to open a bloomfilter file */
 450   bf->fh =
 451       GNUNET_DISK_file_open (filename,
 452                              GNUNET_DISK_OPEN_READWRITE |
 453                              GNUNET_DISK_OPEN_CREATE,
 454                              GNUNET_DISK_PERM_USER_READ |
 455                              GNUNET_DISK_PERM_USER_WRITE);
 456   if (NULL == bf->fh)
 457   {
 458     GNUNET_free (bf);
 459     return NULL;
 460   }
 461   bf->filename = GNUNET_strdup (filename);
 462   /* Alloc block */
 463   bf->bitArray = GNUNET_malloc_large (size);
 464   if (bf->bitArray == NULL)
 465   {
 466     if (bf->fh != NULL)
 467       GNUNET_DISK_file_close (bf->fh);
 468     GNUNET_free (bf->filename);
 469     GNUNET_free (bf);
 470     return NULL;
 471   }
 472   bf->bitArraySize = size;
 473   bf->addressesPerElement = k;
 474   memset (bf->bitArray, 0, bf->bitArraySize);
 475
 476   /* Read from the file what bits we can */
 477   rbuff = GNUNET_malloc (BUFFSIZE);
 478   pos = 0;
 479   while (pos < size * 8)
 480   {
 481     int res;
 482
 483     res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE);
 484     if (res == -1)
 485     {
 486       GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING, "read",
 487                                 bf->filename);
 488     }
 489     if (res == 0)
 490       break;                    /* is ok! we just did not use that many bits yet */
 491     for (i = 0; i < res; i++)
 492     {
 493       if ((rbuff[i] & 0x0F) != 0)
 494         setBit (bf->bitArray, pos + i * 2);
 495       if ((rbuff[i] & 0xF0) != 0)
 496         setBit (bf->bitArray, pos + i * 2 + 1);
 497     }
 498     if (res < BUFFSIZE)
 499       break;
 500     pos += BUFFSIZE * 2;        /* 2 bits per byte in the buffer */
 501   }
 502   GNUNET_free (rbuff);
 503   return bf;
 504 }
 505
 506
 507 /**
 508  * Create a bloom filter from raw bits.
 509  *
 510  * @param data the raw bits in memory (maybe NULL,
 511  *        in which case all bits should be considered
 512  *        to be zero).
 513  * @param size the size of the bloom-filter (number of
 514  *        bytes of storage space to use); also size of data
 515  *        -- unless data is NULL
 516  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
 517  *        element (number of bits set per element in the set)
 518  * @return the bloomfilter
 519  */
 520 struct GNUNET_CONTAINER_BloomFilter *
 521 GNUNET_CONTAINER_bloomfilter_init (const char *data, size_t size,
 522                                    unsigned int k)
 523 {
 524   struct GNUNET_CONTAINER_BloomFilter *bf;
 525   size_t ui;
 526
 527   if ((k == 0) || (size == 0))
 528     return NULL;
 529   ui = 1;
 530   while (ui < size)
 531     ui *= 2;
 532   if (size != ui)
 533   {
 534     GNUNET_break (0);
 535     return NULL;
 536   }
 537   bf = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_BloomFilter));
 538   bf->filename = NULL;
 539   bf->fh = NULL;
 540   bf->bitArray = GNUNET_malloc_large (size);
 541   if (bf->bitArray == NULL)
 542   {
 543     GNUNET_free (bf);
 544     return NULL;
 545   }
 546   bf->bitArraySize = size;
 547   bf->addressesPerElement = k;
 548   if (data != NULL)
 549     memcpy (bf->bitArray, data, size);
 550   else
 551     memset (bf->bitArray, 0, bf->bitArraySize);
 552   return bf;
 553 }
 554
 555
 556 /**
 557  * Copy the raw data of this bloomfilter into
 558  * the given data array.
 559  *
 560  * @param bf bloomfilter to take the raw data from
 561  * @param data where to write the data
 562  * @param size the size of the given data array
 563  * @return GNUNET_SYSERR if the data array is not big enough
 564  */
 565 int
 566 GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct
 567                                            GNUNET_CONTAINER_BloomFilter *bf,
 568                                            char *data, size_t size)
 569 {
 570   if (NULL == bf)
 571     return GNUNET_SYSERR;
 572   if (bf->bitArraySize != size)
 573     return GNUNET_SYSERR;
 574   memcpy (data, bf->bitArray, size);
 575   return GNUNET_OK;
 576 }
 577
 578 /**
 579  * Free the space associated with a filter
 580  * in memory, flush to drive if needed (do not
 581  * free the space on the drive)
 582  *
 583  * @param bf the filter
 584  */
 585 void
 586 GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf)
 587 {
 588   if (NULL == bf)
 589     return;
 590   if (bf->fh != NULL)
 591     GNUNET_DISK_file_close (bf->fh);
 592   GNUNET_free_non_null (bf->filename);
 593   GNUNET_free (bf->bitArray);
 594   GNUNET_free (bf);
 595 }
 596
 597 /**
 598  * Reset a bloom filter to empty. Clears the file on disk.
 599  *
 600  * @param bf the filter
 601  */
 602 void
 603 GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf)
 604 {
 605   if (NULL == bf)
 606     return;
 607
 608   memset (bf->bitArray, 0, bf->bitArraySize);
 609   if (bf->filename != NULL)
 610     makeEmptyFile (bf->fh, bf->bitArraySize * 4);
 611 }
 612
 613
 614 /**
 615  * Test if an element is in the filter.
 616  *
 617  * @param e the element
 618  * @param bf the filter
 619  * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not
 620  */
 621 int
 622 GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter
 623                                    *bf, const GNUNET_HashCode * e)
 624 {
 625   int res;
 626
 627   if (NULL == bf)
 628     return GNUNET_YES;
 629   res = GNUNET_YES;
 630   iterateBits (bf, &testBitCallback, &res, e);
 631   return res;
 632 }
 633
 634 /**
 635  * Add an element to the filter
 636  *
 637  * @param bf the filter
 638  * @param e the element
 639  */
 640 void
 641 GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
 642                                   const GNUNET_HashCode * e)
 643 {
 644
 645   if (NULL == bf)
 646     return;
 647   iterateBits (bf, &incrementBitCallback, bf, e);
 648 }
 649
 650
 651 /**
 652  * Or the entries of the given raw data array with the
 653  * data of the given bloom filter.  Assumes that
 654  * the size of the data array and the current filter
 655  * match.
 656  *
 657  * @param bf the filter
 658  * @param data the data to or-in
 659  * @param size number of bytes in data
 660  */
 661 int
 662 GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
 663                                  const char *data, size_t size)
 664 {
 665   unsigned int i;
 666   unsigned int n;
 667   unsigned long long *fc;
 668   const unsigned long long *dc;
 669
 670   if (NULL == bf)
 671     return GNUNET_YES;
 672   if (bf->bitArraySize != size)
 673     return GNUNET_SYSERR;
 674   fc = (unsigned long long *) bf->bitArray;
 675   dc = (const unsigned long long *) data;
 676   n = size / sizeof (unsigned long long);
 677
 678   for (i = 0; i < n; i++)
 679     fc[i] |= dc[i];
 680   for (i = n * sizeof (unsigned long long); i < size; i++)
 681     bf->bitArray[i] |= data[i];
 682   return GNUNET_OK;
 683 }
 684
 685 /**
 686  * Or the entries of the given raw data array with the
 687  * data of the given bloom filter.  Assumes that
 688  * the size of the data array and the current filter
 689  * match.
 690  *
 691  * @param bf the filter
 692  * @param to_or the bloomfilter to or-in
 693  * @param size number of bytes in data
 694  */
 695 int
 696 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
 697                                   const struct GNUNET_CONTAINER_BloomFilter
 698                                   *to_or, size_t size)
 699 {
 700   unsigned int i;
 701   unsigned int n;
 702   unsigned long long *fc;
 703   const unsigned long long *dc;
 704
 705   if (NULL == bf)
 706     return GNUNET_YES;
 707   if (bf->bitArraySize != size)
 708     return GNUNET_SYSERR;
 709   fc = (unsigned long long *) bf->bitArray;
 710   dc = (const unsigned long long *) to_or->bitArray;
 711   n = size / sizeof (unsigned long long);
 712
 713   for (i = 0; i < n; i++)
 714     fc[i] |= dc[i];
 715   for (i = n * sizeof (unsigned long long); i < size; i++)
 716     bf->bitArray[i] |= to_or->bitArray[i];
 717   return GNUNET_OK;
 718 }
 719
 720 /**
 721  * Remove an element from the filter.
 722  *
 723  * @param bf the filter
 724  * @param e the element to remove
 725  */
 726 void
 727 GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
 728                                      const GNUNET_HashCode * e)
 729 {
 730   if (NULL == bf)
 731     return;
 732   if (bf->filename == NULL)
 733     return;
 734   iterateBits (bf, &decrementBitCallback, bf, e);
 735 }
 736
 737 /**
 738  * Resize a bloom filter.  Note that this operation
 739  * is pretty costly.  Essentially, the bloom filter
 740  * needs to be completely re-build.
 741  *
 742  * @param bf the filter
 743  * @param iterator an iterator over all elements stored in the BF
 744  * @param iterator_cls argument to the iterator function
 745  * @param size the new size for the filter
 746  * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
 747  */
 748 void
 749 GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
 750                                      GNUNET_HashCodeIterator iterator,
 751                                      void *iterator_cls, size_t size,
 752                                      unsigned int k)
 753 {
 754   GNUNET_HashCode hc;
 755   unsigned int i;
 756
 757   GNUNET_free (bf->bitArray);
 758   i = 1;
 759   while (i < size)
 760     i *= 2;
 761   size = i;                     /* make sure it's a power of 2 */
 762
 763   bf->bitArraySize = size;
 764   bf->bitArray = GNUNET_malloc (size);
 765   memset (bf->bitArray, 0, bf->bitArraySize);
 766   if (bf->filename != NULL)
 767     makeEmptyFile (bf->fh, bf->bitArraySize * 4);
 768   while (GNUNET_YES == iterator (iterator_cls, &hc))
 769     GNUNET_CONTAINER_bloomfilter_add (bf, &hc);
 770 }
 771
 772 /* end of container_bloomfilter.c */