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