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  * @return GNUNET_YES to continue, GNUNET_NO to stop early
 320  */
 321 typedef int (*BitIterator) (void *cls,
 322                             const struct GNUNET_CONTAINER_BloomFilter * bf,
 323                             unsigned int bit);
 324
 325 /**
 326  * Call an iterator for each bit that the bloomfilter
 327  * must test or set for this element.
 328  *
 329  * @param bf the filter
 330  * @param callback the method to call
 331  * @param arg extra argument to callback
 332  * @param key the key for which we iterate over the BF bits
 333  */
 334 static void
 335 iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf,
 336              BitIterator callback, void *arg, const GNUNET_HashCode * key)
 337 {
 338   GNUNET_HashCode tmp[2];
 339   int bitCount;
 340   unsigned int round;
 341   unsigned int slot = 0;
 342
 343   bitCount = bf->addressesPerElement;
 344   tmp[0] = *key;
 345   round = 0;
 346   while (bitCount > 0)
 347   {
 348     while (slot < (sizeof (GNUNET_HashCode) / sizeof (uint32_t)))
 349     {
 350       if (GNUNET_YES !=
 351           callback (arg, bf,
 352                     (((uint32_t *) & tmp[round & 1])[slot]) &
 353                     ((bf->bitArraySize * 8) - 1)))
 354         return;
 355       slot++;
 356       bitCount--;
 357       if (bitCount == 0)
 358         break;
 359     }
 360     if (bitCount > 0)
 361     {
 362       GNUNET_CRYPTO_hash (&tmp[round & 1], sizeof (GNUNET_HashCode),
 363                           &tmp[(round + 1) & 1]);
 364       round++;
 365       slot = 0;
 366     }
 367   }
 368 }
 369
 370 /**
 371  * Callback: increment bit
 372  *
 373  * @param cls pointer to writeable form of bf
 374  * @param bf the filter to manipulate
 375  * @param bit the bit to increment
 376  * @return GNUNET_YES
 377  */
 378 static int
 379 incrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 380                       unsigned int bit)
 381 {
 382   struct GNUNET_CONTAINER_BloomFilter *b = cls;
 383
 384   incrementBit (b->bitArray, bit, bf->fh);
 385   return GNUNET_YES;
 386 }
 387
 388 /**
 389  * Callback: decrement bit
 390  *
 391  * @param cls pointer to writeable form of bf
 392  * @param bf the filter to manipulate
 393  * @param bit the bit to decrement
 394  * @return GNUNET_YES
 395  */
 396 static int
 397 decrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 398                       unsigned int bit)
 399 {
 400   struct GNUNET_CONTAINER_BloomFilter *b = cls;
 401
 402   decrementBit (b->bitArray, bit, bf->fh);
 403   return GNUNET_YES;
 404 }
 405
 406 /**
 407  * Callback: test if all bits are set
 408  *
 409  * @param cls pointer set to GNUNET_NO if bit is not set
 410  * @param bf the filter
 411  * @param bit the bit to test
 412  * @return YES if the bit is set, NO if not
 413  */
 414 static int
 415 testBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 416                  unsigned int bit)
 417 {
 418   int *arg = cls;
 419
 420   if (GNUNET_NO == testBit (bf->bitArray, bit))
 421   {
 422     *arg = GNUNET_NO;
 423     return GNUNET_NO;
 424   }
 425   return GNUNET_YES;
 426 }
 427
 428 /* *********************** INTERFACE **************** */
 429
 430 /**
 431  * Load a bloom-filter from a file.
 432  *
 433  * @param filename the name of the file (or the prefix)
 434  * @param size the size of the bloom-filter (number of
 435  *        bytes of storage space to use)
 436  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
 437  *        element (number of bits set per element in the set)
 438  * @return the bloomfilter
 439  */
 440 struct GNUNET_CONTAINER_BloomFilter *
 441 GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size,
 442                                    unsigned int k)
 443 {
 444   struct GNUNET_CONTAINER_BloomFilter *bf;
 445   char *rbuff;
 446   off_t pos;
 447   int i;
 448   size_t ui;
 449
 450   GNUNET_assert (NULL != filename);
 451   if ((k == 0) || (size == 0))
 452     return NULL;
 453   if (size < BUFFSIZE)
 454     size = BUFFSIZE;
 455   ui = 1;
 456   while (ui < size)
 457     ui *= 2;
 458   size = ui;                    /* make sure it's a power of 2 */
 459
 460   bf = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_BloomFilter));
 461   /* Try to open a bloomfilter file */
 462   bf->fh =
 463       GNUNET_DISK_file_open (filename,
 464                              GNUNET_DISK_OPEN_READWRITE |
 465                              GNUNET_DISK_OPEN_CREATE,
 466                              GNUNET_DISK_PERM_USER_READ |
 467                              GNUNET_DISK_PERM_USER_WRITE);
 468   if (NULL == bf->fh)
 469   {
 470     GNUNET_free (bf);
 471     return NULL;
 472   }
 473   bf->filename = GNUNET_strdup (filename);
 474   /* Alloc block */
 475   bf->bitArray = GNUNET_malloc_large (size);
 476   if (bf->bitArray == NULL)
 477   {
 478     if (bf->fh != NULL)
 479       GNUNET_DISK_file_close (bf->fh);
 480     GNUNET_free (bf->filename);
 481     GNUNET_free (bf);
 482     return NULL;
 483   }
 484   bf->bitArraySize = size;
 485   bf->addressesPerElement = k;
 486   memset (bf->bitArray, 0, bf->bitArraySize);
 487
 488   /* Read from the file what bits we can */
 489   rbuff = GNUNET_malloc (BUFFSIZE);
 490   pos = 0;
 491   while (pos < size * 8)
 492   {
 493     int res;
 494
 495     res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE);
 496     if (res == -1)
 497     {
 498       GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING, "read",
 499                                 bf->filename);
 500     }
 501     if (res == 0)
 502       break;                    /* is ok! we just did not use that many bits yet */
 503     for (i = 0; i < res; i++)
 504     {
 505       if ((rbuff[i] & 0x0F) != 0)
 506         setBit (bf->bitArray, pos + i * 2);
 507       if ((rbuff[i] & 0xF0) != 0)
 508         setBit (bf->bitArray, pos + i * 2 + 1);
 509     }
 510     if (res < BUFFSIZE)
 511       break;
 512     pos += BUFFSIZE * 2;        /* 2 bits per byte in the buffer */
 513   }
 514   GNUNET_free (rbuff);
 515   return bf;
 516 }
 517
 518
 519 /**
 520  * Create a bloom filter from raw bits.
 521  *
 522  * @param data the raw bits in memory (maybe NULL,
 523  *        in which case all bits should be considered
 524  *        to be zero).
 525  * @param size the size of the bloom-filter (number of
 526  *        bytes of storage space to use); also size of data
 527  *        -- unless data is NULL
 528  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
 529  *        element (number of bits set per element in the set)
 530  * @return the bloomfilter
 531  */
 532 struct GNUNET_CONTAINER_BloomFilter *
 533 GNUNET_CONTAINER_bloomfilter_init (const char *data, size_t size,
 534                                    unsigned int k)
 535 {
 536   struct GNUNET_CONTAINER_BloomFilter *bf;
 537   size_t ui;
 538
 539   if ((k == 0) || (size == 0))
 540     return NULL;
 541   ui = 1;
 542   while (ui < size)
 543     ui *= 2;
 544   if (size != ui)
 545   {
 546     GNUNET_break (0);
 547     return NULL;
 548   }
 549   bf = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_BloomFilter));
 550   bf->filename = NULL;
 551   bf->fh = NULL;
 552   bf->bitArray = GNUNET_malloc_large (size);
 553   if (bf->bitArray == NULL)
 554   {
 555     GNUNET_free (bf);
 556     return NULL;
 557   }
 558   bf->bitArraySize = size;
 559   bf->addressesPerElement = k;
 560   if (data != NULL)
 561     memcpy (bf->bitArray, data, size);
 562   else
 563     memset (bf->bitArray, 0, bf->bitArraySize);
 564   return bf;
 565 }
 566
 567
 568 /**
 569  * Copy the raw data of this bloomfilter into
 570  * the given data array.
 571  *
 572  * @param bf bloomfilter to take the raw data from
 573  * @param data where to write the data
 574  * @param size the size of the given data array
 575  * @return GNUNET_SYSERR if the data array is not big enough
 576  */
 577 int
 578 GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct
 579                                            GNUNET_CONTAINER_BloomFilter *bf,
 580                                            char *data, size_t size)
 581 {
 582   if (NULL == bf)
 583     return GNUNET_SYSERR;
 584   if (bf->bitArraySize != size)
 585     return GNUNET_SYSERR;
 586   memcpy (data, bf->bitArray, size);
 587   return GNUNET_OK;
 588 }
 589
 590 /**
 591  * Free the space associated with a filter
 592  * in memory, flush to drive if needed (do not
 593  * free the space on the drive)
 594  *
 595  * @param bf the filter
 596  */
 597 void
 598 GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf)
 599 {
 600   if (NULL == bf)
 601     return;
 602   if (bf->fh != NULL)
 603     GNUNET_DISK_file_close (bf->fh);
 604   GNUNET_free_non_null (bf->filename);
 605   GNUNET_free (bf->bitArray);
 606   GNUNET_free (bf);
 607 }
 608
 609 /**
 610  * Reset a bloom filter to empty. Clears the file on disk.
 611  *
 612  * @param bf the filter
 613  */
 614 void
 615 GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf)
 616 {
 617   if (NULL == bf)
 618     return;
 619
 620   memset (bf->bitArray, 0, bf->bitArraySize);
 621   if (bf->filename != NULL)
 622     makeEmptyFile (bf->fh, bf->bitArraySize * 4);
 623 }
 624
 625
 626 /**
 627  * Test if an element is in the filter.
 628  *
 629  * @param e the element
 630  * @param bf the filter
 631  * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not
 632  */
 633 int
 634 GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter
 635                                    *bf, const GNUNET_HashCode * e)
 636 {
 637   int res;
 638
 639   if (NULL == bf)
 640     return GNUNET_YES;
 641   res = GNUNET_YES;
 642   iterateBits (bf, &testBitCallback, &res, e);
 643   return res;
 644 }
 645
 646 /**
 647  * Add an element to the filter
 648  *
 649  * @param bf the filter
 650  * @param e the element
 651  */
 652 void
 653 GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
 654                                   const GNUNET_HashCode * e)
 655 {
 656
 657   if (NULL == bf)
 658     return;
 659   iterateBits (bf, &incrementBitCallback, bf, e);
 660 }
 661
 662
 663 /**
 664  * Or the entries of the given raw data array with the
 665  * data of the given bloom filter.  Assumes that
 666  * the size of the data array and the current filter
 667  * match.
 668  *
 669  * @param bf the filter
 670  * @param data the data to or-in
 671  * @param size number of bytes in data
 672  */
 673 int
 674 GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
 675                                  const char *data, size_t size)
 676 {
 677   unsigned int i;
 678   unsigned int n;
 679   unsigned long long *fc;
 680   const unsigned long long *dc;
 681
 682   if (NULL == bf)
 683     return GNUNET_YES;
 684   if (bf->bitArraySize != size)
 685     return GNUNET_SYSERR;
 686   fc = (unsigned long long *) bf->bitArray;
 687   dc = (const unsigned long long *) data;
 688   n = size / sizeof (unsigned long long);
 689
 690   for (i = 0; i < n; i++)
 691     fc[i] |= dc[i];
 692   for (i = n * sizeof (unsigned long long); i < size; i++)
 693     bf->bitArray[i] |= data[i];
 694   return GNUNET_OK;
 695 }
 696
 697 /**
 698  * Or the entries of the given raw data array with the
 699  * data of the given bloom filter.  Assumes that
 700  * the size of the data array and the current filter
 701  * match.
 702  *
 703  * @param bf the filter
 704  * @param to_or the bloomfilter to or-in
 705  * @param size number of bytes in data
 706  */
 707 int
 708 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
 709                                   const struct GNUNET_CONTAINER_BloomFilter
 710                                   *to_or, size_t size)
 711 {
 712   unsigned int i;
 713   unsigned int n;
 714   unsigned long long *fc;
 715   const unsigned long long *dc;
 716
 717   if (NULL == bf)
 718     return GNUNET_YES;
 719   if (bf->bitArraySize != size)
 720     return GNUNET_SYSERR;
 721   fc = (unsigned long long *) bf->bitArray;
 722   dc = (const unsigned long long *) to_or->bitArray;
 723   n = size / sizeof (unsigned long long);
 724
 725   for (i = 0; i < n; i++)
 726     fc[i] |= dc[i];
 727   for (i = n * sizeof (unsigned long long); i < size; i++)
 728     bf->bitArray[i] |= to_or->bitArray[i];
 729   return GNUNET_OK;
 730 }
 731
 732 /**
 733  * Remove an element from the filter.
 734  *
 735  * @param bf the filter
 736  * @param e the element to remove
 737  */
 738 void
 739 GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
 740                                      const GNUNET_HashCode * e)
 741 {
 742   if (NULL == bf)
 743     return;
 744   if (bf->filename == NULL)
 745     return;
 746   iterateBits (bf, &decrementBitCallback, bf, e);
 747 }
 748
 749 /**
 750  * Resize a bloom filter.  Note that this operation
 751  * is pretty costly.  Essentially, the bloom filter
 752  * needs to be completely re-build.
 753  *
 754  * @param bf the filter
 755  * @param iterator an iterator over all elements stored in the BF
 756  * @param iterator_cls argument to the iterator function
 757  * @param size the new size for the filter
 758  * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
 759  */
 760 void
 761 GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
 762                                      GNUNET_HashCodeIterator iterator,
 763                                      void *iterator_cls, size_t size,
 764                                      unsigned int k)
 765 {
 766   GNUNET_HashCode hc;
 767   unsigned int i;
 768
 769   GNUNET_free (bf->bitArray);
 770   i = 1;
 771   while (i < size)
 772     i *= 2;
 773   size = i;                     /* make sure it's a power of 2 */
 774
 775   bf->bitArraySize = size;
 776   bf->bitArray = GNUNET_malloc (size);
 777   memset (bf->bitArray, 0, bf->bitArraySize);
 778   if (bf->filename != NULL)
 779     makeEmptyFile (bf->fh, bf->bitArraySize * 4);
 780   while (GNUNET_YES == iterator (iterator_cls, &hc))
 781     GNUNET_CONTAINER_bloomfilter_add (bf, &hc);
 782 }
 783
 784 /* end of container_bloomfilter.c */