src/util/container_bloomfilter.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2001, 2002, 2003, 2004, 2006, 2008, 2011, 2012, 2018 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your 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      Affero General Public License for more details.
  14 */
  15 /**
  16  * @file util/container_bloomfilter.c
  17  * @brief data structure used to reduce disk accesses.
  18  *
  19  * The idea basically: Create a signature for each element in the
  20  * database. Add those signatures to a bit array. When doing a lookup,
  21  * check if the bit array matches the signature of the requested
  22  * element. If yes, address the disk, otherwise return 'not found'.
  23  *
  24  * A property of the bloom filter is that sometimes we will have
  25  * a match even if the element is not on the disk (then we do
  26  * an unnecessary disk access), but what's most important is that
  27  * we never get a single "false negative".
  28  *
  29  * To be able to delete entries from the bloom filter, we maintain
  30  * a 4 bit counter in the file on the drive (we still use only one
  31  * bit in memory).
  32  *
  33  * @author Igor Wronsky
  34  * @author Christian Grothoff
  35  */
  36
  37 #include "platform.h"
  38 #include "gnunet_util_lib.h"
  39
  40 #define LOG(kind,...) GNUNET_log_from (kind, "util-container-bloomfilter", __VA_ARGS__)
  41
  42 #define LOG_STRERROR(kind,syscall) GNUNET_log_from_strerror (kind, "util-container-bloomfilter", syscall)
  43
  44 #define LOG_STRERROR_FILE(kind,syscall,filename) GNUNET_log_from_strerror_file (kind, "util-container-bloomfilter", syscall, filename)
  45
  46 struct GNUNET_CONTAINER_BloomFilter
  47 {
  48
  49   /**
  50    * The actual bloomfilter bit array
  51    */
  52   char *bitArray;
  53
  54   /**
  55    * Filename of the filter
  56    */
  57   char *filename;
  58
  59   /**
  60    * The bit counter file on disk
  61    */
  62   struct GNUNET_DISK_FileHandle *fh;
  63
  64   /**
  65    * How many bits we set for each stored element
  66    */
  67   unsigned int addressesPerElement;
  68
  69   /**
  70    * Size of bitArray in bytes
  71    */
  72   size_t bitArraySize;
  73
  74 };
  75
  76
  77 /**
  78  * Get the number of the addresses set per element in the bloom filter.
  79  *
  80  * @param bf the filter
  81  * @return addresses set per element in the bf
  82  */
  83 size_t
  84 GNUNET_CONTAINER_bloomfilter_get_element_addresses (const struct GNUNET_CONTAINER_BloomFilter
  85                                        *bf)
  86 {
  87   if (bf == NULL)
  88     return 0;
  89   return bf->addressesPerElement;
  90 }
  91
  92
  93 /**
  94  * Get size of the bloom filter.
  95  *
  96  * @param bf the filter
  97  * @return number of bytes used for the data of the bloom filter
  98  */
  99 size_t
 100 GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter
 101                                        *bf)
 102 {
 103   if (bf == NULL)
 104     return 0;
 105   return bf->bitArraySize;
 106 }
 107
 108
 109 /**
 110  * Copy an existing memory.  Any association with a file
 111  * on-disk will be lost in the process.
 112  * @param bf the filter to copy
 113  * @return copy of the bf
 114  */
 115 struct GNUNET_CONTAINER_BloomFilter *
 116 GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter
 117                                    *bf)
 118 {
 119   return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray, bf->bitArraySize,
 120                                             bf->addressesPerElement);
 121 }
 122
 123
 124 /**
 125  * Sets a bit active in the bitArray. Increment bit-specific
 126  * usage counter on disk only if below 4bit max (==15).
 127  *
 128  * @param bitArray memory area to set the bit in
 129  * @param bitIdx which bit to set
 130  */
 131 static void
 132 setBit (char *bitArray, unsigned int bitIdx)
 133 {
 134   size_t arraySlot;
 135   unsigned int targetBit;
 136
 137   arraySlot = bitIdx / 8;
 138   targetBit = (1L << (bitIdx % 8));
 139   bitArray[arraySlot] |= targetBit;
 140 }
 141
 142 /**
 143  * Clears a bit from bitArray. Bit is cleared from the array
 144  * only if the respective usage counter on the disk hits/is zero.
 145  *
 146  * @param bitArray memory area to set the bit in
 147  * @param bitIdx which bit to unset
 148  */
 149 static void
 150 clearBit (char *bitArray, unsigned int bitIdx)
 151 {
 152   size_t slot;
 153   unsigned int targetBit;
 154
 155   slot = bitIdx / 8;
 156   targetBit = (1L << (bitIdx % 8));
 157   bitArray[slot] = bitArray[slot] & (~targetBit);
 158 }
 159
 160 /**
 161  * Checks if a bit is active in the bitArray
 162  *
 163  * @param bitArray memory area to set the bit in
 164  * @param bitIdx which bit to test
 165  * @return GNUNET_YES if the bit is set, GNUNET_NO if not.
 166  */
 167 static int
 168 testBit (char *bitArray, unsigned int bitIdx)
 169 {
 170   size_t slot;
 171   unsigned int targetBit;
 172
 173   slot = bitIdx / 8;
 174   targetBit = (1L << (bitIdx % 8));
 175   if (bitArray[slot] & targetBit)
 176     return GNUNET_YES;
 177   else
 178     return GNUNET_NO;
 179 }
 180
 181 /**
 182  * Sets a bit active in the bitArray and increments
 183  * bit-specific usage counter on disk (but only if
 184  * the counter was below 4 bit max (==15)).
 185  *
 186  * @param bitArray memory area to set the bit in
 187  * @param bitIdx which bit to test
 188  * @param fh A file to keep the 4 bit address usage counters in
 189  */
 190 static void
 191 incrementBit (char *bitArray, unsigned int bitIdx,
 192               const struct GNUNET_DISK_FileHandle *fh)
 193 {
 194   off_t fileSlot;
 195   unsigned char value;
 196   unsigned int high;
 197   unsigned int low;
 198   unsigned int targetLoc;
 199
 200   setBit (bitArray, bitIdx);
 201   if (GNUNET_DISK_handle_invalid (fh))
 202     return;
 203   /* Update the counter file on disk */
 204   fileSlot = bitIdx / 2;
 205   targetLoc = bitIdx % 2;
 206
 207   GNUNET_assert (fileSlot ==
 208                  GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET));
 209   if (1 != GNUNET_DISK_file_read (fh, &value, 1))
 210     value = 0;
 211   low = value & 0xF;
 212   high = (value & (~0xF)) >> 4;
 213
 214   if (targetLoc == 0)
 215   {
 216     if (low < 0xF)
 217       low++;
 218   }
 219   else
 220   {
 221     if (high < 0xF)
 222       high++;
 223   }
 224   value = ((high << 4) | low);
 225   GNUNET_assert (fileSlot ==
 226                  GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET));
 227   GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1));
 228 }
 229
 230 /**
 231  * Clears a bit from bitArray if the respective usage
 232  * counter on the disk hits/is zero.
 233  *
 234  * @param bitArray memory area to set the bit in
 235  * @param bitIdx which bit to test
 236  * @param fh A file to keep the 4bit address usage counters in
 237  */
 238 static void
 239 decrementBit (char *bitArray, unsigned int bitIdx,
 240               const struct GNUNET_DISK_FileHandle *fh)
 241 {
 242   off_t fileslot;
 243   unsigned char value;
 244   unsigned int high;
 245   unsigned int low;
 246   unsigned int targetLoc;
 247
 248   if (GNUNET_DISK_handle_invalid (fh))
 249     return;                     /* cannot decrement! */
 250   /* Each char slot in the counter file holds two 4 bit counters */
 251   fileslot = bitIdx / 2;
 252   targetLoc = bitIdx % 2;
 253   if (GNUNET_SYSERR == GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET))
 254     {
 255       GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek");
 256       return;
 257     }
 258   if (1 != GNUNET_DISK_file_read (fh, &value, 1))
 259     value = 0;
 260   low = value & 0xF;
 261   high = (value & 0xF0) >> 4;
 262
 263   /* decrement, but once we have reached the max, never go back! */
 264   if (targetLoc == 0)
 265   {
 266     if ((low > 0) && (low < 0xF))
 267       low--;
 268     if (low == 0)
 269     {
 270       clearBit (bitArray, bitIdx);
 271     }
 272   }
 273   else
 274   {
 275     if ((high > 0) && (high < 0xF))
 276       high--;
 277     if (high == 0)
 278     {
 279       clearBit (bitArray, bitIdx);
 280     }
 281   }
 282   value = ((high << 4) | low);
 283   if (GNUNET_SYSERR == GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET))
 284     {
 285       GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek");
 286       return;
 287     }
 288   GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1));
 289 }
 290
 291 #define BUFFSIZE 65536
 292
 293 /**
 294  * Creates a file filled with zeroes
 295  *
 296  * @param fh the file handle
 297  * @param size the size of the file
 298  * @return GNUNET_OK if created ok, GNUNET_SYSERR otherwise
 299  */
 300 static int
 301 make_empty_file (const struct GNUNET_DISK_FileHandle *fh, size_t size)
 302 {
 303   char buffer[BUFFSIZE];
 304   size_t bytesleft = size;
 305   int res = 0;
 306
 307   if (GNUNET_DISK_handle_invalid (fh))
 308     return GNUNET_SYSERR;
 309   memset (buffer, 0, sizeof (buffer));
 310   GNUNET_DISK_file_seek (fh, 0, GNUNET_DISK_SEEK_SET);
 311   while (bytesleft > 0)
 312   {
 313     if (bytesleft > sizeof (buffer))
 314     {
 315       res = GNUNET_DISK_file_write (fh, buffer, sizeof (buffer));
 316       if (res >= 0)
 317         bytesleft -= res;
 318     }
 319     else
 320     {
 321       res = GNUNET_DISK_file_write (fh, buffer, bytesleft);
 322       if (res >= 0)
 323         bytesleft -= res;
 324     }
 325     if (GNUNET_SYSERR == res)
 326       return GNUNET_SYSERR;
 327   }
 328   return GNUNET_OK;
 329 }
 330
 331 /* ************** GNUNET_CONTAINER_BloomFilter iterator ********* */
 332
 333 /**
 334  * Iterator (callback) method to be called by the
 335  * bloomfilter iterator on each bit that is to be
 336  * set or tested for the key.
 337  *
 338  * @param cls closure
 339  * @param bf the filter to manipulate
 340  * @param bit the current bit
 341  * @return GNUNET_YES to continue, GNUNET_NO to stop early
 342  */
 343 typedef int (*BitIterator) (void *cls,
 344                             const struct GNUNET_CONTAINER_BloomFilter * bf,
 345                             unsigned int bit);
 346
 347
 348 /**
 349  * Call an iterator for each bit that the bloomfilter
 350  * must test or set for this element.
 351  *
 352  * @param bf the filter
 353  * @param callback the method to call
 354  * @param arg extra argument to callback
 355  * @param key the key for which we iterate over the BF bits
 356  */
 357 static void
 358 iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf,
 359              BitIterator callback, void *arg, const struct GNUNET_HashCode *key)
 360 {
 361   struct GNUNET_HashCode tmp[2];
 362   int bitCount;
 363   unsigned int round;
 364   unsigned int slot = 0;
 365
 366   bitCount = bf->addressesPerElement;
 367   tmp[0] = *key;
 368   round = 0;
 369   GNUNET_assert (bf->bitArraySize > 0);
 370   GNUNET_assert (bf->bitArraySize * 8LL > bf->bitArraySize);
 371   while (bitCount > 0)
 372   {
 373     while (slot < (sizeof (struct GNUNET_HashCode) / sizeof (uint32_t)))
 374     {
 375       if (GNUNET_YES !=
 376           callback (arg, bf,
 377                     ntohl ((((uint32_t *) & tmp[round & 1])[slot])) %
 378                     ((bf->bitArraySize * 8LL))))
 379         return;
 380       slot++;
 381       bitCount--;
 382       if (bitCount == 0)
 383         break;
 384     }
 385     if (bitCount > 0)
 386     {
 387       GNUNET_CRYPTO_hash (&tmp[round & 1], sizeof (struct GNUNET_HashCode),
 388                           &tmp[(round + 1) & 1]);
 389       round++;
 390       slot = 0;
 391     }
 392   }
 393 }
 394
 395
 396 /**
 397  * Callback: increment bit
 398  *
 399  * @param cls pointer to writeable form of bf
 400  * @param bf the filter to manipulate
 401  * @param bit the bit to increment
 402  * @return GNUNET_YES
 403  */
 404 static int
 405 incrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 406                       unsigned int bit)
 407 {
 408   struct GNUNET_CONTAINER_BloomFilter *b = cls;
 409
 410   incrementBit (b->bitArray, bit, bf->fh);
 411   return GNUNET_YES;
 412 }
 413
 414
 415 /**
 416  * Callback: decrement bit
 417  *
 418  * @param cls pointer to writeable form of bf
 419  * @param bf the filter to manipulate
 420  * @param bit the bit to decrement
 421  * @return GNUNET_YES
 422  */
 423 static int
 424 decrementBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 425                       unsigned int bit)
 426 {
 427   struct GNUNET_CONTAINER_BloomFilter *b = cls;
 428
 429   decrementBit (b->bitArray, bit, bf->fh);
 430   return GNUNET_YES;
 431 }
 432
 433
 434 /**
 435  * Callback: test if all bits are set
 436  *
 437  * @param cls pointer set to GNUNET_NO if bit is not set
 438  * @param bf the filter
 439  * @param bit the bit to test
 440  * @return YES if the bit is set, NO if not
 441  */
 442 static int
 443 testBitCallback (void *cls, const struct GNUNET_CONTAINER_BloomFilter *bf,
 444                  unsigned int bit)
 445 {
 446   int *arg = cls;
 447
 448   if (GNUNET_NO == testBit (bf->bitArray, bit))
 449   {
 450     *arg = GNUNET_NO;
 451     return GNUNET_NO;
 452   }
 453   return GNUNET_YES;
 454 }
 455
 456 /* *********************** INTERFACE **************** */
 457
 458 /**
 459  * Load a bloom-filter from a file.
 460  *
 461  * @param filename the name of the file (or the prefix)
 462  * @param size the size of the bloom-filter (number of
 463  *        bytes of storage space to use); will be rounded up
 464  *        to next power of 2
 465  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
 466  *        element (number of bits set per element in the set)
 467  * @return the bloomfilter
 468  */
 469 struct GNUNET_CONTAINER_BloomFilter *
 470 GNUNET_CONTAINER_bloomfilter_load (const char *filename, size_t size,
 471                                    unsigned int k)
 472 {
 473   struct GNUNET_CONTAINER_BloomFilter *bf;
 474   char *rbuff;
 475   off_t pos;
 476   int i;
 477   size_t ui;
 478   off_t fsize;
 479   int must_read;
 480
 481   GNUNET_assert (NULL != filename);
 482   if ((k == 0) || (size == 0))
 483     return NULL;
 484   if (size < BUFFSIZE)
 485     size = BUFFSIZE;
 486   ui = 1;
 487   while ( (ui < size) &&
 488           (ui * 2 > ui) )
 489     ui *= 2;
 490   size = ui;                    /* make sure it's a power of 2 */
 491
 492   bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter);
 493   /* Try to open a bloomfilter file */
 494   if (GNUNET_YES == GNUNET_DISK_file_test (filename))
 495     bf->fh =
 496       GNUNET_DISK_file_open (filename,
 497                              GNUNET_DISK_OPEN_READWRITE,
 498                              GNUNET_DISK_PERM_USER_READ |
 499                              GNUNET_DISK_PERM_USER_WRITE);
 500   if (NULL != bf->fh)
 501   {
 502     /* file existed, try to read it! */
 503     must_read = GNUNET_YES;
 504     if (GNUNET_OK !=
 505         GNUNET_DISK_file_handle_size (bf->fh, &fsize))
 506     {
 507       GNUNET_DISK_file_close (bf->fh);
 508       GNUNET_free (bf);
 509       return NULL;
 510     }
 511     if (0 == fsize)
 512     {
 513       /* found existing empty file, just overwrite */
 514       if (GNUNET_OK !=
 515           make_empty_file (bf->fh, size * 4LL))
 516       {
 517         GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING,
 518                              "write");
 519         GNUNET_DISK_file_close (bf->fh);
 520         GNUNET_free (bf);
 521         return NULL;
 522       }
 523     }
 524     else if (fsize != ((off_t) size) * 4LL)
 525     {
 526       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 527                   _("Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"),
 528                   (unsigned long long) (size * 4LL),
 529                   (unsigned long long) fsize);
 530       GNUNET_DISK_file_close (bf->fh);
 531       GNUNET_free (bf);
 532       return NULL;
 533     }
 534   }
 535   else
 536   {
 537     /* file did not exist, don't read, just create */
 538     must_read = GNUNET_NO;
 539     bf->fh =
 540       GNUNET_DISK_file_open (filename,
 541                              GNUNET_DISK_OPEN_CREATE |
 542                              GNUNET_DISK_OPEN_READWRITE,
 543                              GNUNET_DISK_PERM_USER_READ |
 544                              GNUNET_DISK_PERM_USER_WRITE);
 545     if (NULL == bf->fh)
 546       {
 547         GNUNET_free (bf);
 548         return NULL;
 549       }
 550     if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL))
 551     {
 552       GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING,
 553                            "write");
 554       GNUNET_DISK_file_close (bf->fh);
 555       GNUNET_free (bf);
 556       return NULL;
 557     }
 558   }
 559   bf->filename = GNUNET_strdup (filename);
 560   /* Alloc block */
 561   bf->bitArray = GNUNET_malloc_large (size);
 562   if (NULL == bf->bitArray)
 563   {
 564     if (NULL != bf->fh)
 565       GNUNET_DISK_file_close (bf->fh);
 566     GNUNET_free (bf->filename);
 567     GNUNET_free (bf);
 568     return NULL;
 569   }
 570   bf->bitArraySize = size;
 571   bf->addressesPerElement = k;
 572   if (GNUNET_YES != must_read)
 573     return bf; /* already done! */
 574   /* Read from the file what bits we can */
 575   rbuff = GNUNET_malloc (BUFFSIZE);
 576   pos = 0;
 577   while (pos < ((off_t) size) * 8LL)
 578   {
 579     int res;
 580
 581     res = GNUNET_DISK_file_read (bf->fh,
 582                                  rbuff,
 583                                  BUFFSIZE);
 584     if (res == -1)
 585     {
 586       LOG_STRERROR_FILE (GNUNET_ERROR_TYPE_WARNING,
 587                          "read",
 588                          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 *bf,
 720                                    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,
 761                                  size_t size)
 762 {
 763   unsigned int i;
 764   unsigned int n;
 765   unsigned long long *fc;
 766   const unsigned long long *dc;
 767
 768   if (NULL == bf)
 769     return GNUNET_YES;
 770   if (bf->bitArraySize != size)
 771     return GNUNET_SYSERR;
 772   fc = (unsigned long long *) bf->bitArray;
 773   dc = (const unsigned long long *) data;
 774   n = size / sizeof (unsigned long long);
 775
 776   for (i = 0; i < n; i++)
 777     fc[i] |= dc[i];
 778   for (i = n * sizeof (unsigned long long); i < size; i++)
 779     bf->bitArray[i] |= data[i];
 780   return GNUNET_OK;
 781 }
 782
 783 /**
 784  * Or the entries of the given raw data array with the
 785  * data of the given bloom filter.  Assumes that
 786  * the size of the data array and the current filter
 787  * match.
 788  *
 789  * @param bf the filter
 790  * @param to_or the bloomfilter to or-in
 791  * @return #GNUNET_OK on success
 792  */
 793 int
 794 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
 795                                   const struct GNUNET_CONTAINER_BloomFilter *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 (NULL == bf->filename)
 836     return;
 837   iterateBits (bf,
 838                &decrementBitCallback,
 839                bf,
 840                e);
 841 }
 842
 843 /**
 844  * Resize a bloom filter.  Note that this operation
 845  * is pretty costly.  Essentially, the bloom filter
 846  * needs to be completely re-build.
 847  *
 848  * @param bf the filter
 849  * @param iterator an iterator over all elements stored in the BF
 850  * @param iterator_cls argument to the iterator function
 851  * @param size the new size for the filter
 852  * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
 853  */
 854 void
 855 GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
 856                                      GNUNET_CONTAINER_HashCodeIterator iterator,
 857                                      void *iterator_cls,
 858                                      size_t size,
 859                                      unsigned int k)
 860 {
 861   struct GNUNET_HashCode hc;
 862   unsigned int i;
 863
 864   GNUNET_free (bf->bitArray);
 865   i = 1;
 866   while (i < size)
 867     i *= 2;
 868   size = i;                     /* make sure it's a power of 2 */
 869   bf->addressesPerElement = k;
 870   bf->bitArraySize = size;
 871   bf->bitArray = GNUNET_malloc (size);
 872   if (NULL != bf->filename)
 873     make_empty_file (bf->fh,
 874                      bf->bitArraySize * 4LL);
 875   while (GNUNET_YES == iterator (iterator_cls,
 876                                  &hc))
 877     GNUNET_CONTAINER_bloomfilter_add (bf,
 878                                       &hc);
 879 }
 880
 881 /* end of container_bloomfilter.c */