src/util/container_bloomfilter.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2001, 2002, 2003, 2004, 2006, 2008, 2011, 2012 GNUnet e.V.
   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 3, 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., 51 Franklin Street, Fifth Floor,
  18      Boston, MA 02110-1301, 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_util_lib.h"
  44
  45 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
  46
  47 #define LOG_STRERROR(kind,syscall) GNUNET_log_from_strerror (kind, "util", syscall)
  48
  49 #define LOG_STRERROR_FILE(kind,syscall,filename) GNUNET_log_from_strerror_file (kind, "util", syscall, filename)
  50
  51 struct GNUNET_CONTAINER_BloomFilter
  52 {
  53
  54   /**
  55    * The actual bloomfilter bit array
  56    */
  57   char *bitArray;
  58
  59   /**
  60    * Filename of the filter
  61    */
  62   char *filename;
  63
  64   /**
  65    * The bit counter file on disk
  66    */
  67   struct GNUNET_DISK_FileHandle *fh;
  68
  69   /**
  70    * How many bits we set for each stored element
  71    */
  72   unsigned int addressesPerElement;
  73
  74   /**
  75    * Size of bitArray in bytes
  76    */
  77   size_t bitArraySize;
  78
  79 };
  80
  81
  82 /**
  83  * Get the number of the addresses set per element in the bloom filter.
  84  *
  85  * @param bf the filter
  86  * @return addresses set per element in the bf
  87  */
  88 size_t
  89 GNUNET_CONTAINER_bloomfilter_get_element_addresses (const struct GNUNET_CONTAINER_BloomFilter
  90                                        *bf)
  91 {
  92   if (bf == NULL)
  93     return 0;
  94   return bf->addressesPerElement;
  95 }
  96
  97
  98 /**
  99  * Get size of the bloom filter.
 100  *
 101  * @param bf the filter
 102  * @return number of bytes used for the data of the bloom filter
 103  */
 104 size_t
 105 GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter
 106                                        *bf)
 107 {
 108   if (bf == NULL)
 109     return 0;
 110   return bf->bitArraySize;
 111 }
 112
 113
 114 /**
 115  * Copy an existing memory.  Any association with a file
 116  * on-disk will be lost in the process.
 117  * @param bf the filter to copy
 118  * @return copy of the bf
 119  */
 120 struct GNUNET_CONTAINER_BloomFilter *
 121 GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter
 122                                    *bf)
 123 {
 124   return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray, bf->bitArraySize,
 125                                             bf->addressesPerElement);
 126 }
 127
 128
 129 /**
 130  * Sets a bit active in the bitArray. Increment bit-specific
 131  * usage counter on disk only if below 4bit max (==15).
 132  *
 133  * @param bitArray memory area to set the bit in
 134  * @param bitIdx which bit to set
 135  */
 136 static void
 137 setBit (char *bitArray, unsigned int bitIdx)
 138 {
 139   size_t arraySlot;
 140   unsigned int targetBit;
 141
 142   arraySlot = bitIdx / 8;
 143   targetBit = (1L << (bitIdx % 8));
 144   bitArray[arraySlot] |= targetBit;
 145 }
 146
 147 /**
 148  * Clears a bit from bitArray. Bit is cleared from the array
 149  * only if the respective usage counter on the disk hits/is zero.
 150  *
 151  * @param bitArray memory area to set the bit in
 152  * @param bitIdx which bit to unset
 153  */
 154 static void
 155 clearBit (char *bitArray, unsigned int bitIdx)
 156 {
 157   size_t slot;
 158   unsigned int targetBit;
 159
 160   slot = bitIdx / 8;
 161   targetBit = (1L << (bitIdx % 8));
 162   bitArray[slot] = bitArray[slot] & (~targetBit);
 163 }
 164
 165 /**
 166  * Checks if a bit is active in the bitArray
 167  *
 168  * @param bitArray memory area to set the bit in
 169  * @param bitIdx which bit to test
 170  * @return GNUNET_YES if the bit is set, GNUNET_NO if not.
 171  */
 172 static int
 173 testBit (char *bitArray, unsigned int bitIdx)
 174 {
 175   size_t slot;
 176   unsigned int targetBit;
 177
 178   slot = bitIdx / 8;
 179   targetBit = (1L << (bitIdx % 8));
 180   if (bitArray[slot] & targetBit)
 181     return GNUNET_YES;
 182   else
 183     return GNUNET_NO;
 184 }
 185
 186 /**
 187  * Sets a bit active in the bitArray and increments
 188  * bit-specific usage counter on disk (but only if
 189  * the counter was below 4 bit max (==15)).
 190  *
 191  * @param bitArray memory area to set the bit in
 192  * @param bitIdx which bit to test
 193  * @param fh A file to keep the 4 bit address usage counters in
 194  */
 195 static void
 196 incrementBit (char *bitArray, unsigned int bitIdx,
 197               const struct GNUNET_DISK_FileHandle *fh)
 198 {
 199   off_t fileSlot;
 200   unsigned char value;
 201   unsigned int high;
 202   unsigned int low;
 203   unsigned int targetLoc;
 204
 205   setBit (bitArray, bitIdx);
 206   if (GNUNET_DISK_handle_invalid (fh))
 207     return;
 208   /* Update the counter file on disk */
 209   fileSlot = bitIdx / 2;
 210   targetLoc = bitIdx % 2;
 211
 212   GNUNET_assert (fileSlot ==
 213                  GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET));
 214   if (1 != GNUNET_DISK_file_read (fh, &value, 1))
 215     value = 0;
 216   low = value & 0xF;
 217   high = (value & (~0xF)) >> 4;
 218
 219   if (targetLoc == 0)
 220   {
 221     if (low < 0xF)
 222       low++;
 223   }
 224   else
 225   {
 226     if (high < 0xF)
 227       high++;
 228   }
 229   value = ((high << 4) | low);
 230   GNUNET_assert (fileSlot ==
 231                  GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET));
 232   GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1));
 233 }
 234
 235 /**
 236  * Clears a bit from bitArray if the respective usage
 237  * counter on the disk hits/is zero.
 238  *
 239  * @param bitArray memory area to set the bit in
 240  * @param bitIdx which bit to test
 241  * @param fh A file to keep the 4bit address usage counters in
 242  */
 243 static void
 244 decrementBit (char *bitArray, unsigned int bitIdx,
 245               const struct GNUNET_DISK_FileHandle *fh)
 246 {
 247   off_t fileslot;
 248   unsigned char value;
 249   unsigned int high;
 250   unsigned int low;
 251   unsigned int targetLoc;
 252
 253   if (GNUNET_DISK_handle_invalid (fh))
 254     return;                     /* cannot decrement! */
 255   /* Each char slot in the counter file holds two 4 bit counters */
 256   fileslot = bitIdx / 2;
 257   targetLoc = bitIdx % 2;
 258   if (GNUNET_SYSERR == GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET))
 259     {
 260       GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek");
 261       return;
 262     }
 263   if (1 != GNUNET_DISK_file_read (fh, &value, 1))
 264     value = 0;
 265   low = value & 0xF;
 266   high = (value & 0xF0) >> 4;
 267
 268   /* decrement, but once we have reached the max, never go back! */
 269   if (targetLoc == 0)
 270   {
 271     if ((low > 0) && (low < 0xF))
 272       low--;
 273     if (low == 0)
 274     {
 275       clearBit (bitArray, bitIdx);
 276     }
 277   }
 278   else
 279   {
 280     if ((high > 0) && (high < 0xF))
 281       high--;
 282     if (high == 0)
 283     {
 284       clearBit (bitArray, bitIdx);
 285     }
 286   }
 287   value = ((high << 4) | low);
 288   if (GNUNET_SYSERR == GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET))
 289     {
 290       GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek");
 291       return;
 292     }
 293   GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1));
 294 }
 295
 296 #define BUFFSIZE 65536
 297
 298 /**
 299  * Creates a file filled with zeroes
 300  *
 301  * @param fh the file handle
 302  * @param size the size of the file
 303  * @return GNUNET_OK if created ok, GNUNET_SYSERR otherwise
 304  */
 305 static int
 306 make_empty_file (const struct GNUNET_DISK_FileHandle *fh, size_t size)
 307 {
 308   char buffer[BUFFSIZE];
 309   size_t bytesleft = size;
 310   int res = 0;
 311
 312   if (GNUNET_DISK_handle_invalid (fh))
 313     return GNUNET_SYSERR;
 314   memset (buffer, 0, sizeof (buffer));
 315   GNUNET_DISK_file_seek (fh, 0, GNUNET_DISK_SEEK_SET);
 316   while (bytesleft > 0)
 317   {
 318     if (bytesleft > sizeof (buffer))
 319     {
 320       res = GNUNET_DISK_file_write (fh, buffer, sizeof (buffer));
 321       if (res >= 0)
 322         bytesleft -= res;
 323     }
 324     else
 325     {
 326       res = GNUNET_DISK_file_write (fh, buffer, bytesleft);
 327       if (res >= 0)
 328         bytesleft -= res;
 329     }
 330     if (GNUNET_SYSERR == res)
 331       return GNUNET_SYSERR;
 332   }
 333   return GNUNET_OK;
 334 }
 335
 336 /* ************** GNUNET_CONTAINER_BloomFilter iterator ********* */
 337
 338 /**
 339  * Iterator (callback) method to be called by the
 340  * bloomfilter iterator on each bit that is to be
 341  * set or tested for the key.
 342  *
 343  * @param cls closure
 344  * @param bf the filter to manipulate
 345  * @param bit the current bit
 346  * @return GNUNET_YES to continue, GNUNET_NO to stop early
 347  */
 348 typedef int (*BitIterator) (void *cls,
 349                             const struct GNUNET_CONTAINER_BloomFilter * bf,
 350                             unsigned int bit);
 351
 352
 353 /**
 354  * Call an iterator for each bit that the bloomfilter
 355  * must test or set for this element.
 356  *
 357  * @param bf the filter
 358  * @param callback the method to call
 359  * @param arg extra argument to callback
 360  * @param key the key for which we iterate over the BF bits
 361  */
 362 static void
 363 iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf,
 364              BitIterator callback, void *arg, const struct GNUNET_HashCode *key)
 365 {
 366   struct GNUNET_HashCode tmp[2];
 367   int bitCount;
 368   unsigned int round;
 369   unsigned int slot = 0;
 370
 371   bitCount = bf->addressesPerElement;
 372   tmp[0] = *key;
 373   round = 0;
 374   GNUNET_assert (bf->bitArraySize > 0);
 375   GNUNET_assert (bf->bitArraySize * 8LL > bf->bitArraySize);
 376   while (bitCount > 0)
 377   {
 378     while (slot < (sizeof (struct GNUNET_HashCode) / sizeof (uint32_t)))
 379     {
 380       if (GNUNET_YES !=
 381           callback (arg, bf,
 382                     ntohl ((((uint32_t *) & tmp[round & 1])[slot])) %
 383                     ((bf->bitArraySize * 8LL))))
 384         return;
 385       slot++;
 386       bitCount--;
 387       if (bitCount == 0)
 388         break;
 389     }
 390     if (bitCount > 0)
 391     {
 392       GNUNET_CRYPTO_hash (&tmp[round & 1], sizeof (struct GNUNET_HashCode),
 393                           &tmp[(round + 1) & 1]);
 394       round++;
 395       slot = 0;
 396     }
 397   }
 398 }
 399
 400
 401 /**
 402  * Callback: increment bit
 403  *
 404  * @param cls pointer to writeable form of bf
 405  * @param bf the filter to manipulate
 406  * @param bit the bit to increment
 407  * @return GNUNET_YES
 408  */
 409 static int
 410 incrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 411                       unsigned int bit)
 412 {
 413   struct GNUNET_CONTAINER_BloomFilter *b = cls;
 414
 415   incrementBit (b->bitArray, bit, bf->fh);
 416   return GNUNET_YES;
 417 }
 418
 419
 420 /**
 421  * Callback: decrement bit
 422  *
 423  * @param cls pointer to writeable form of bf
 424  * @param bf the filter to manipulate
 425  * @param bit the bit to decrement
 426  * @return GNUNET_YES
 427  */
 428 static int
 429 decrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 430                       unsigned int bit)
 431 {
 432   struct GNUNET_CONTAINER_BloomFilter *b = cls;
 433
 434   decrementBit (b->bitArray, bit, bf->fh);
 435   return GNUNET_YES;
 436 }
 437
 438
 439 /**
 440  * Callback: test if all bits are set
 441  *
 442  * @param cls pointer set to GNUNET_NO if bit is not set
 443  * @param bf the filter
 444  * @param bit the bit to test
 445  * @return YES if the bit is set, NO if not
 446  */
 447 static int
 448 testBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 449                  unsigned int bit)
 450 {
 451   int *arg = cls;
 452
 453   if (GNUNET_NO == testBit (bf->bitArray, bit))
 454   {
 455     *arg = GNUNET_NO;
 456     return GNUNET_NO;
 457   }
 458   return GNUNET_YES;
 459 }
 460
 461 /* *********************** INTERFACE **************** */
 462
 463 /**
 464  * Load a bloom-filter from a file.
 465  *
 466  * @param filename the name of the file (or the prefix)
 467  * @param size the size of the bloom-filter (number of
 468  *        bytes of storage space to use); will be rounded up
 469  *        to next power of 2
 470  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
 471  *        element (number of bits set per element in the set)
 472  * @return the bloomfilter
 473  */
 474 struct GNUNET_CONTAINER_BloomFilter *
 475 GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size,
 476                                    unsigned int k)
 477 {
 478   struct GNUNET_CONTAINER_BloomFilter *bf;
 479   char *rbuff;
 480   off_t pos;
 481   int i;
 482   size_t ui;
 483   off_t fsize;
 484   int must_read;
 485
 486   GNUNET_assert (NULL != filename);
 487   if ((k == 0) || (size == 0))
 488     return NULL;
 489   if (size < BUFFSIZE)
 490     size = BUFFSIZE;
 491   ui = 1;
 492   while ( (ui < size) &&
 493           (ui * 2 > ui) )
 494     ui *= 2;
 495   size = ui;                    /* make sure it's a power of 2 */
 496
 497   bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter);
 498   /* Try to open a bloomfilter file */
 499   if (GNUNET_YES == GNUNET_DISK_file_test (filename))
 500     bf->fh =
 501       GNUNET_DISK_file_open (filename,
 502                              GNUNET_DISK_OPEN_READWRITE,
 503                              GNUNET_DISK_PERM_USER_READ |
 504                              GNUNET_DISK_PERM_USER_WRITE);
 505   if (NULL != bf->fh)
 506   {
 507     /* file existed, try to read it! */
 508     must_read = GNUNET_YES;
 509     if (GNUNET_OK !=
 510         GNUNET_DISK_file_handle_size (bf->fh, &fsize))
 511     {
 512       GNUNET_DISK_file_close (bf->fh);
 513       GNUNET_free (bf);
 514       return NULL;
 515     }
 516     if (fsize == 0)
 517     {
 518       /* found existing empty file, just overwrite */
 519       if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL))
 520       {
 521         GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING,
 522                              "write");
 523         GNUNET_DISK_file_close (bf->fh);
 524         GNUNET_free (bf);
 525         return NULL;
 526       }
 527     }
 528     else if (fsize != size * 4LL)
 529     {
 530       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 531                   _("Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"),
 532                   (unsigned long long) (size * 4LL),
 533                   (unsigned long long) fsize);
 534       GNUNET_DISK_file_close (bf->fh);
 535       GNUNET_free (bf);
 536       return NULL;
 537     }
 538   }
 539   else
 540   {
 541     /* file did not exist, don't read, just create */
 542     must_read = GNUNET_NO;
 543     bf->fh =
 544       GNUNET_DISK_file_open (filename,
 545                              GNUNET_DISK_OPEN_CREATE |
 546                              GNUNET_DISK_OPEN_READWRITE,
 547                              GNUNET_DISK_PERM_USER_READ |
 548                              GNUNET_DISK_PERM_USER_WRITE);
 549     if (NULL == bf->fh)
 550       {
 551         GNUNET_free (bf);
 552         return NULL;
 553       }
 554     if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL))
 555     {
 556       GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING,
 557                            "write");
 558       GNUNET_DISK_file_close (bf->fh);
 559       GNUNET_free (bf);
 560       return NULL;
 561     }
 562   }
 563   bf->filename = GNUNET_strdup (filename);
 564   /* Alloc block */
 565   bf->bitArray = GNUNET_malloc_large (size);
 566   if (bf->bitArray == NULL)
 567   {
 568     if (bf->fh != NULL)
 569       GNUNET_DISK_file_close (bf->fh);
 570     GNUNET_free (bf->filename);
 571     GNUNET_free (bf);
 572     return NULL;
 573   }
 574   bf->bitArraySize = size;
 575   bf->addressesPerElement = k;
 576   if (GNUNET_YES != must_read)
 577     return bf; /* already done! */
 578   /* Read from the file what bits we can */
 579   rbuff = GNUNET_malloc (BUFFSIZE);
 580   pos = 0;
 581   while (pos < size * 8LL)
 582   {
 583     int res;
 584
 585     res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE);
 586     if (res == -1)
 587     {
 588       LOG_STRERROR_FILE (GNUNET_ERROR_TYPE_WARNING, "read", bf->filename);
 589       GNUNET_free (rbuff);
 590       GNUNET_free (bf->filename);
 591       GNUNET_DISK_file_close (bf->fh);
 592       GNUNET_free (bf);
 593       return NULL;
 594     }
 595     if (res == 0)
 596       break;                    /* is ok! we just did not use that many bits yet */
 597     for (i = 0; i < res; i++)
 598     {
 599       if ((rbuff[i] & 0x0F) != 0)
 600         setBit (bf->bitArray, pos + i * 2);
 601       if ((rbuff[i] & 0xF0) != 0)
 602         setBit (bf->bitArray, pos + i * 2 + 1);
 603     }
 604     if (res < BUFFSIZE)
 605       break;
 606     pos += BUFFSIZE * 2;        /* 2 bits per byte in the buffer */
 607   }
 608   GNUNET_free (rbuff);
 609   return bf;
 610 }
 611
 612
 613 /**
 614  * Create a bloom filter from raw bits.
 615  *
 616  * @param data the raw bits in memory (maybe NULL,
 617  *        in which case all bits should be considered
 618  *        to be zero).
 619  * @param size the size of the bloom-filter (number of
 620  *        bytes of storage space to use); also size of data
 621  *        -- unless data is NULL
 622  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
 623  *        element (number of bits set per element in the set)
 624  * @return the bloomfilter
 625  */
 626 struct GNUNET_CONTAINER_BloomFilter *
 627 GNUNET_CONTAINER_bloomfilter_init (const char *data, size_t size,
 628                                    unsigned int k)
 629 {
 630   struct GNUNET_CONTAINER_BloomFilter *bf;
 631
 632   if ((0 == k) || (0 == size))
 633     return NULL;
 634   bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter);
 635   bf->filename = NULL;
 636   bf->fh = NULL;
 637   bf->bitArray = GNUNET_malloc_large (size);
 638   if (NULL == bf->bitArray)
 639   {
 640     GNUNET_free (bf);
 641     return NULL;
 642   }
 643   bf->bitArraySize = size;
 644   bf->addressesPerElement = k;
 645   if (NULL != data)
 646     GNUNET_memcpy (bf->bitArray, data, size);
 647   return bf;
 648 }
 649
 650
 651 /**
 652  * Copy the raw data of this bloomfilter into
 653  * the given data array.
 654  *
 655  * @param bf bloomfilter to take the raw data from
 656  * @param data where to write the data
 657  * @param size the size of the given data array
 658  * @return GNUNET_SYSERR if the data array is not big enough
 659  */
 660 int
 661 GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct
 662                                            GNUNET_CONTAINER_BloomFilter *bf,
 663                                            char *data, size_t size)
 664 {
 665   if (NULL == bf)
 666     return GNUNET_SYSERR;
 667   if (bf->bitArraySize != size)
 668     return GNUNET_SYSERR;
 669   GNUNET_memcpy (data, bf->bitArray, size);
 670   return GNUNET_OK;
 671 }
 672
 673
 674 /**
 675  * Free the space associated with a filter
 676  * in memory, flush to drive if needed (do not
 677  * free the space on the drive)
 678  *
 679  * @param bf the filter
 680  */
 681 void
 682 GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf)
 683 {
 684   if (NULL == bf)
 685     return;
 686   if (bf->fh != NULL)
 687     GNUNET_DISK_file_close (bf->fh);
 688   GNUNET_free_non_null (bf->filename);
 689   GNUNET_free (bf->bitArray);
 690   GNUNET_free (bf);
 691 }
 692
 693
 694 /**
 695  * Reset a bloom filter to empty. Clears the file on disk.
 696  *
 697  * @param bf the filter
 698  */
 699 void
 700 GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf)
 701 {
 702   if (NULL == bf)
 703     return;
 704
 705   memset (bf->bitArray, 0, bf->bitArraySize);
 706   if (bf->filename != NULL)
 707     make_empty_file (bf->fh, bf->bitArraySize * 4LL);
 708 }
 709
 710
 711 /**
 712  * Test if an element is in the filter.
 713  *
 714  * @param e the element
 715  * @param bf the filter
 716  * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not
 717  */
 718 int
 719 GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter
 720                                    *bf, const struct GNUNET_HashCode * e)
 721 {
 722   int res;
 723
 724   if (NULL == bf)
 725     return GNUNET_YES;
 726   res = GNUNET_YES;
 727   iterateBits (bf, &testBitCallback, &res, e);
 728   return res;
 729 }
 730
 731
 732 /**
 733  * Add an element to the filter
 734  *
 735  * @param bf the filter
 736  * @param e the element
 737  */
 738 void
 739 GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
 740                                   const struct GNUNET_HashCode * e)
 741 {
 742   if (NULL == bf)
 743     return;
 744   iterateBits (bf, &incrementBitCallback, bf, e);
 745 }
 746
 747
 748 /**
 749  * Or the entries of the given raw data array with the
 750  * data of the given bloom filter.  Assumes that
 751  * the size of the data array and the current filter
 752  * match.
 753  *
 754  * @param bf the filter
 755  * @param data the data to or-in
 756  * @param size number of bytes in data
 757  */
 758 int
 759 GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
 760                                  const char *data, size_t size)
 761 {
 762   unsigned int i;
 763   unsigned int n;
 764   unsigned long long *fc;
 765   const unsigned long long *dc;
 766
 767   if (NULL == bf)
 768     return GNUNET_YES;
 769   if (bf->bitArraySize != size)
 770     return GNUNET_SYSERR;
 771   fc = (unsigned long long *) bf->bitArray;
 772   dc = (const unsigned long long *) data;
 773   n = size / sizeof (unsigned long long);
 774
 775   for (i = 0; i < n; i++)
 776     fc[i] |= dc[i];
 777   for (i = n * sizeof (unsigned long long); i < size; i++)
 778     bf->bitArray[i] |= data[i];
 779   return GNUNET_OK;
 780 }
 781
 782 /**
 783  * Or the entries of the given raw data array with the
 784  * data of the given bloom filter.  Assumes that
 785  * the size of the data array and the current filter
 786  * match.
 787  *
 788  * @param bf the filter
 789  * @param to_or the bloomfilter to or-in
 790  * @return #GNUNET_OK on success
 791  */
 792 int
 793 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
 794                                   const struct GNUNET_CONTAINER_BloomFilter
 795                                   *to_or)
 796 {
 797   unsigned int i;
 798   unsigned int n;
 799   unsigned long long *fc;
 800   const unsigned long long *dc;
 801   size_t size;
 802
 803   if (NULL == bf)
 804     return GNUNET_OK;
 805   if (bf->bitArraySize != to_or->bitArraySize)
 806   {
 807     GNUNET_break (0);
 808     return GNUNET_SYSERR;
 809   }
 810   size = bf->bitArraySize;
 811   fc = (unsigned long long *) bf->bitArray;
 812   dc = (const unsigned long long *) to_or->bitArray;
 813   n = size / sizeof (unsigned long long);
 814
 815   for (i = 0; i < n; i++)
 816     fc[i] |= dc[i];
 817   for (i = n * sizeof (unsigned long long); i < size; i++)
 818     bf->bitArray[i] |= to_or->bitArray[i];
 819   return GNUNET_OK;
 820 }
 821
 822
 823 /**
 824  * Remove an element from the filter.
 825  *
 826  * @param bf the filter
 827  * @param e the element to remove
 828  */
 829 void
 830 GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
 831                                      const struct GNUNET_HashCode * e)
 832 {
 833   if (NULL == bf)
 834     return;
 835   if (bf->filename == NULL)
 836     return;
 837   iterateBits (bf, &decrementBitCallback, bf, e);
 838 }
 839
 840 /**
 841  * Resize a bloom filter.  Note that this operation
 842  * is pretty costly.  Essentially, the bloom filter
 843  * needs to be completely re-build.
 844  *
 845  * @param bf the filter
 846  * @param iterator an iterator over all elements stored in the BF
 847  * @param iterator_cls argument to the iterator function
 848  * @param size the new size for the filter
 849  * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
 850  */
 851 void
 852 GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
 853                                      GNUNET_CONTAINER_HashCodeIterator iterator,
 854                                      void *iterator_cls, size_t size,
 855                                      unsigned int k)
 856 {
 857   struct GNUNET_HashCode hc;
 858   unsigned int i;
 859
 860   GNUNET_free (bf->bitArray);
 861   i = 1;
 862   while (i < size)
 863     i *= 2;
 864   size = i;                     /* make sure it's a power of 2 */
 865
 866   bf->bitArraySize = size;
 867   bf->bitArray = GNUNET_malloc (size);
 868   if (bf->filename != NULL)
 869     make_empty_file (bf->fh, bf->bitArraySize * 4LL);
 870   while (GNUNET_YES == iterator (iterator_cls, &hc))
 871     GNUNET_CONTAINER_bloomfilter_add (bf, &hc);
 872 }
 873
 874 /* end of container_bloomfilter.c */