src/util/container_bloomfilter.c

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