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