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,...) GNUNET_log_from (kind, "util-container-bloomfilter", __VA_ARGS__)
  46
  47 #define LOG_STRERROR(kind,syscall) GNUNET_log_from_strerror (kind, "util-container-bloomfilter", syscall)
  48
  49 #define LOG_STRERROR_FILE(kind,syscall,filename) GNUNET_log_from_strerror_file (kind, "util-container-bloomfilter", 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 (0 == fsize)
 517     {
 518       /* found existing empty file, just overwrite */
 519       if (GNUNET_OK !=
 520           make_empty_file (bf->fh, size * 4LL))
 521       {
 522         GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING,
 523                              "write");
 524         GNUNET_DISK_file_close (bf->fh);
 525         GNUNET_free (bf);
 526         return NULL;
 527       }
 528     }
 529     else if (fsize != ((off_t) size) * 4LL)
 530     {
 531       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 532                   _("Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"),
 533                   (unsigned long long) (size * 4LL),
 534                   (unsigned long long) fsize);
 535       GNUNET_DISK_file_close (bf->fh);
 536       GNUNET_free (bf);
 537       return NULL;
 538     }
 539   }
 540   else
 541   {
 542     /* file did not exist, don't read, just create */
 543     must_read = GNUNET_NO;
 544     bf->fh =
 545       GNUNET_DISK_file_open (filename,
 546                              GNUNET_DISK_OPEN_CREATE |
 547                              GNUNET_DISK_OPEN_READWRITE,
 548                              GNUNET_DISK_PERM_USER_READ |
 549                              GNUNET_DISK_PERM_USER_WRITE);
 550     if (NULL == bf->fh)
 551       {
 552         GNUNET_free (bf);
 553         return NULL;
 554       }
 555     if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL))
 556     {
 557       GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING,
 558                            "write");
 559       GNUNET_DISK_file_close (bf->fh);
 560       GNUNET_free (bf);
 561       return NULL;
 562     }
 563   }
 564   bf->filename = GNUNET_strdup (filename);
 565   /* Alloc block */
 566   bf->bitArray = GNUNET_malloc_large (size);
 567   if (NULL == bf->bitArray)
 568   {
 569     if (NULL != bf->fh)
 570       GNUNET_DISK_file_close (bf->fh);
 571     GNUNET_free (bf->filename);
 572     GNUNET_free (bf);
 573     return NULL;
 574   }
 575   bf->bitArraySize = size;
 576   bf->addressesPerElement = k;
 577   if (GNUNET_YES != must_read)
 578     return bf; /* already done! */
 579   /* Read from the file what bits we can */
 580   rbuff = GNUNET_malloc (BUFFSIZE);
 581   pos = 0;
 582   while (pos < ((off_t) size) * 8LL)
 583   {
 584     int res;
 585
 586     res = GNUNET_DISK_file_read (bf->fh,
 587                                  rbuff,
 588                                  BUFFSIZE);
 589     if (res == -1)
 590     {
 591       LOG_STRERROR_FILE (GNUNET_ERROR_TYPE_WARNING,
 592                          "read",
 593                          bf->filename);
 594       GNUNET_free (rbuff);
 595       GNUNET_free (bf->filename);
 596       GNUNET_DISK_file_close (bf->fh);
 597       GNUNET_free (bf);
 598       return NULL;
 599     }
 600     if (res == 0)
 601       break;                    /* is ok! we just did not use that many bits yet */
 602     for (i = 0; i < res; i++)
 603     {
 604       if ((rbuff[i] & 0x0F) != 0)
 605         setBit (bf->bitArray, pos + i * 2);
 606       if ((rbuff[i] & 0xF0) != 0)
 607         setBit (bf->bitArray, pos + i * 2 + 1);
 608     }
 609     if (res < BUFFSIZE)
 610       break;
 611     pos += BUFFSIZE * 2;        /* 2 bits per byte in the buffer */
 612   }
 613   GNUNET_free (rbuff);
 614   return bf;
 615 }
 616
 617
 618 /**
 619  * Create a bloom filter from raw bits.
 620  *
 621  * @param data the raw bits in memory (maybe NULL,
 622  *        in which case all bits should be considered
 623  *        to be zero).
 624  * @param size the size of the bloom-filter (number of
 625  *        bytes of storage space to use); also size of data
 626  *        -- unless data is NULL
 627  * @param k the number of GNUNET_CRYPTO_hash-functions to apply per
 628  *        element (number of bits set per element in the set)
 629  * @return the bloomfilter
 630  */
 631 struct GNUNET_CONTAINER_BloomFilter *
 632 GNUNET_CONTAINER_bloomfilter_init (const char *data, size_t size,
 633                                    unsigned int k)
 634 {
 635   struct GNUNET_CONTAINER_BloomFilter *bf;
 636
 637   if ((0 == k) || (0 == size))
 638     return NULL;
 639   bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter);
 640   bf->filename = NULL;
 641   bf->fh = NULL;
 642   bf->bitArray = GNUNET_malloc_large (size);
 643   if (NULL == bf->bitArray)
 644   {
 645     GNUNET_free (bf);
 646     return NULL;
 647   }
 648   bf->bitArraySize = size;
 649   bf->addressesPerElement = k;
 650   if (NULL != data)
 651     GNUNET_memcpy (bf->bitArray, data, size);
 652   return bf;
 653 }
 654
 655
 656 /**
 657  * Copy the raw data of this bloomfilter into
 658  * the given data array.
 659  *
 660  * @param bf bloomfilter to take the raw data from
 661  * @param data where to write the data
 662  * @param size the size of the given data array
 663  * @return #GNUNET_SYSERR if the data array is not big enough
 664  */
 665 int
 666 GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct
 667                                            GNUNET_CONTAINER_BloomFilter *bf,
 668                                            char *data, size_t size)
 669 {
 670   if (NULL == bf)
 671     return GNUNET_SYSERR;
 672   if (bf->bitArraySize != size)
 673     return GNUNET_SYSERR;
 674   GNUNET_memcpy (data, bf->bitArray, size);
 675   return GNUNET_OK;
 676 }
 677
 678
 679 /**
 680  * Free the space associated with a filter
 681  * in memory, flush to drive if needed (do not
 682  * free the space on the drive)
 683  *
 684  * @param bf the filter
 685  */
 686 void
 687 GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf)
 688 {
 689   if (NULL == bf)
 690     return;
 691   if (bf->fh != NULL)
 692     GNUNET_DISK_file_close (bf->fh);
 693   GNUNET_free_non_null (bf->filename);
 694   GNUNET_free (bf->bitArray);
 695   GNUNET_free (bf);
 696 }
 697
 698
 699 /**
 700  * Reset a bloom filter to empty. Clears the file on disk.
 701  *
 702  * @param bf the filter
 703  */
 704 void
 705 GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf)
 706 {
 707   if (NULL == bf)
 708     return;
 709
 710   memset (bf->bitArray, 0, bf->bitArraySize);
 711   if (bf->filename != NULL)
 712     make_empty_file (bf->fh, bf->bitArraySize * 4LL);
 713 }
 714
 715
 716 /**
 717  * Test if an element is in the filter.
 718  *
 719  * @param e the element
 720  * @param bf the filter
 721  * @return #GNUNET_YES if the element is in the filter, #GNUNET_NO if not
 722  */
 723 int
 724 GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf,
 725                                    const struct GNUNET_HashCode * e)
 726 {
 727   int res;
 728
 729   if (NULL == bf)
 730     return GNUNET_YES;
 731   res = GNUNET_YES;
 732   iterateBits (bf, &testBitCallback, &res, e);
 733   return res;
 734 }
 735
 736
 737 /**
 738  * Add an element to the filter
 739  *
 740  * @param bf the filter
 741  * @param e the element
 742  */
 743 void
 744 GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf,
 745                                   const struct GNUNET_HashCode * e)
 746 {
 747   if (NULL == bf)
 748     return;
 749   iterateBits (bf, &incrementBitCallback, bf, e);
 750 }
 751
 752
 753 /**
 754  * Or the entries of the given raw data array with the
 755  * data of the given bloom filter.  Assumes that
 756  * the size of the data array and the current filter
 757  * match.
 758  *
 759  * @param bf the filter
 760  * @param data the data to or-in
 761  * @param size number of bytes in data
 762  */
 763 int
 764 GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
 765                                  const char *data,
 766                                  size_t size)
 767 {
 768   unsigned int i;
 769   unsigned int n;
 770   unsigned long long *fc;
 771   const unsigned long long *dc;
 772
 773   if (NULL == bf)
 774     return GNUNET_YES;
 775   if (bf->bitArraySize != size)
 776     return GNUNET_SYSERR;
 777   fc = (unsigned long long *) bf->bitArray;
 778   dc = (const unsigned long long *) data;
 779   n = size / sizeof (unsigned long long);
 780
 781   for (i = 0; i < n; i++)
 782     fc[i] |= dc[i];
 783   for (i = n * sizeof (unsigned long long); i < size; i++)
 784     bf->bitArray[i] |= data[i];
 785   return GNUNET_OK;
 786 }
 787
 788 /**
 789  * Or the entries of the given raw data array with the
 790  * data of the given bloom filter.  Assumes that
 791  * the size of the data array and the current filter
 792  * match.
 793  *
 794  * @param bf the filter
 795  * @param to_or the bloomfilter to or-in
 796  * @return #GNUNET_OK on success
 797  */
 798 int
 799 GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
 800                                   const struct GNUNET_CONTAINER_BloomFilter *to_or)
 801 {
 802   unsigned int i;
 803   unsigned int n;
 804   unsigned long long *fc;
 805   const unsigned long long *dc;
 806   size_t size;
 807
 808   if (NULL == bf)
 809     return GNUNET_OK;
 810   if (bf->bitArraySize != to_or->bitArraySize)
 811   {
 812     GNUNET_break (0);
 813     return GNUNET_SYSERR;
 814   }
 815   size = bf->bitArraySize;
 816   fc = (unsigned long long *) bf->bitArray;
 817   dc = (const unsigned long long *) to_or->bitArray;
 818   n = size / sizeof (unsigned long long);
 819
 820   for (i = 0; i < n; i++)
 821     fc[i] |= dc[i];
 822   for (i = n * sizeof (unsigned long long); i < size; i++)
 823     bf->bitArray[i] |= to_or->bitArray[i];
 824   return GNUNET_OK;
 825 }
 826
 827
 828 /**
 829  * Remove an element from the filter.
 830  *
 831  * @param bf the filter
 832  * @param e the element to remove
 833  */
 834 void
 835 GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf,
 836                                      const struct GNUNET_HashCode *e)
 837 {
 838   if (NULL == bf)
 839     return;
 840   if (NULL == bf->filename)
 841     return;
 842   iterateBits (bf,
 843                &decrementBitCallback,
 844                bf,
 845                e);
 846 }
 847
 848 /**
 849  * Resize a bloom filter.  Note that this operation
 850  * is pretty costly.  Essentially, the bloom filter
 851  * needs to be completely re-build.
 852  *
 853  * @param bf the filter
 854  * @param iterator an iterator over all elements stored in the BF
 855  * @param iterator_cls argument to the iterator function
 856  * @param size the new size for the filter
 857  * @param k the new number of GNUNET_CRYPTO_hash-function to apply per element
 858  */
 859 void
 860 GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf,
 861                                      GNUNET_CONTAINER_HashCodeIterator iterator,
 862                                      void *iterator_cls,
 863                                      size_t size,
 864                                      unsigned int k)
 865 {
 866   struct GNUNET_HashCode hc;
 867   unsigned int i;
 868
 869   GNUNET_free (bf->bitArray);
 870   i = 1;
 871   while (i < size)
 872     i *= 2;
 873   size = i;                     /* make sure it's a power of 2 */
 874   bf->addressesPerElement = k;
 875   bf->bitArraySize = size;
 876   bf->bitArray = GNUNET_malloc (size);
 877   if (NULL != bf->filename)
 878     make_empty_file (bf->fh,
 879                      bf->bitArraySize * 4LL);
 880   while (GNUNET_YES == iterator (iterator_cls,
 881                                  &hc))
 882     GNUNET_CONTAINER_bloomfilter_add (bf,
 883                                       &hc);
 884 }
 885
 886 /* end of container_bloomfilter.c */