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