src/util/test_container_bloomfilter.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2004, 2009 GNUnet e.V.
   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., 51 Franklin Street, Fifth Floor,
  18      Boston, MA 02110-1301, USA.
  19 */
  20 /**
  21  * @file util/test_container_bloomfilter.c
  22  * @brief Testcase for the bloomfilter.
  23  * @author Christian Grothoff
  24  * @author Igor Wronsky
  25  */
  26
  27 #include "platform.h"
  28 #include "gnunet_util_lib.h"
  29
  30 #define K 4
  31 #define SIZE 65536
  32 #define TESTFILE "/tmp/bloomtest.dat"
  33
  34 /**
  35  * Generate a random hashcode.
  36  */
  37 static void
  38 nextHC (struct GNUNET_HashCode * hc)
  39 {
  40   GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_WEAK, hc);
  41 }
  42
  43 static int
  44 add_iterator (void *cls, struct GNUNET_HashCode * next)
  45 {
  46   int *ret = cls;
  47   struct GNUNET_HashCode pos;
  48
  49   if (0 == (*ret)--)
  50     return GNUNET_NO;
  51   nextHC (&pos);
  52   *next = pos;
  53   return GNUNET_YES;
  54 }
  55
  56 int
  57 main (int argc, char *argv[])
  58 {
  59   struct GNUNET_CONTAINER_BloomFilter *bf;
  60   struct GNUNET_CONTAINER_BloomFilter *bfi;
  61   struct GNUNET_HashCode tmp;
  62   int i;
  63   int ok1;
  64   int ok2;
  65   int falseok;
  66   char buf[SIZE];
  67   struct stat sbuf;
  68
  69   GNUNET_log_setup ("test-container-bloomfilter", "WARNING", NULL);
  70   GNUNET_CRYPTO_seed_weak_random (1);
  71   if (0 == STAT (TESTFILE, &sbuf))
  72     if (0 != UNLINK (TESTFILE))
  73       GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_ERROR, "unlink", TESTFILE);
  74   bf = GNUNET_CONTAINER_bloomfilter_load (TESTFILE, SIZE, K);
  75
  76   for (i = 0; i < 200; i++)
  77   {
  78     nextHC (&tmp);
  79     GNUNET_CONTAINER_bloomfilter_add (bf, &tmp);
  80   }
  81   GNUNET_CRYPTO_seed_weak_random (1);
  82   ok1 = 0;
  83   for (i = 0; i < 200; i++)
  84   {
  85     nextHC (&tmp);
  86     if (GNUNET_CONTAINER_bloomfilter_test (bf, &tmp) == GNUNET_YES)
  87       ok1++;
  88   }
  89   if (ok1 != 200)
  90   {
  91     printf ("Got %d elements out of" "200 expected after insertion.\n", ok1);
  92     GNUNET_CONTAINER_bloomfilter_free (bf);
  93     return -1;
  94   }
  95   if (GNUNET_OK != GNUNET_CONTAINER_bloomfilter_get_raw_data (bf, buf, SIZE))
  96   {
  97     GNUNET_CONTAINER_bloomfilter_free (bf);
  98     return -1;
  99   }
 100
 101   GNUNET_CONTAINER_bloomfilter_free (bf);
 102
 103   bf = GNUNET_CONTAINER_bloomfilter_load (TESTFILE, SIZE, K);
 104   GNUNET_assert (bf != NULL);
 105   bfi = GNUNET_CONTAINER_bloomfilter_init (buf, SIZE, K);
 106   GNUNET_assert (bfi != NULL);
 107
 108   GNUNET_CRYPTO_seed_weak_random (1);
 109   ok1 = 0;
 110   ok2 = 0;
 111   for (i = 0; i < 200; i++)
 112   {
 113     nextHC (&tmp);
 114     if (GNUNET_CONTAINER_bloomfilter_test (bf, &tmp) == GNUNET_YES)
 115       ok1++;
 116     if (GNUNET_CONTAINER_bloomfilter_test (bfi, &tmp) == GNUNET_YES)
 117       ok2++;
 118   }
 119   if (ok1 != 200)
 120   {
 121     printf ("Got %d elements out of 200 " "expected after reloading.\n", ok1);
 122     GNUNET_CONTAINER_bloomfilter_free (bf);
 123     GNUNET_CONTAINER_bloomfilter_free (bfi);
 124     return -1;
 125   }
 126
 127   if (ok2 != 200)
 128   {
 129     printf ("Got %d elements out of 200 " "expected after initialization.\n",
 130             ok2);
 131     GNUNET_CONTAINER_bloomfilter_free (bf);
 132     GNUNET_CONTAINER_bloomfilter_free (bfi);
 133     return -1;
 134   }
 135
 136   GNUNET_CRYPTO_seed_weak_random (1);
 137   for (i = 0; i < 100; i++)
 138   {
 139     nextHC (&tmp);
 140     GNUNET_CONTAINER_bloomfilter_remove (bf, &tmp);
 141     GNUNET_CONTAINER_bloomfilter_remove (bfi, &tmp);
 142   }
 143
 144   GNUNET_CRYPTO_seed_weak_random (1);
 145
 146   ok1 = 0;
 147   ok2 = 0;
 148   for (i = 0; i < 200; i++)
 149   {
 150     nextHC (&tmp);
 151     if (GNUNET_CONTAINER_bloomfilter_test (bf, &tmp) == GNUNET_YES)
 152       ok1++;
 153     if (GNUNET_CONTAINER_bloomfilter_test (bfi, &tmp) == GNUNET_YES)
 154       ok2++;
 155   }
 156
 157   if (ok1 != 100)
 158   {
 159     printf ("Expected 100 elements in loaded filter"
 160             " after adding 200 and deleting 100, got %d\n", ok1);
 161     GNUNET_CONTAINER_bloomfilter_free (bf);
 162     GNUNET_CONTAINER_bloomfilter_free (bfi);
 163     return -1;
 164   }
 165   if (ok2 != 200)
 166   {
 167     printf ("Expected 200 elements in initialized filter"
 168             " after adding 200 and deleting 100 "
 169             "(which should do nothing for a filter not backed by a file), got %d\n",
 170             ok2);
 171     GNUNET_CONTAINER_bloomfilter_free (bf);
 172     GNUNET_CONTAINER_bloomfilter_free (bfi);
 173     return -1;
 174   }
 175
 176   GNUNET_CRYPTO_seed_weak_random (3);
 177
 178   GNUNET_CONTAINER_bloomfilter_clear (bf);
 179   falseok = 0;
 180   for (i = 0; i < 1000; i++)
 181   {
 182     nextHC (&tmp);
 183     if (GNUNET_CONTAINER_bloomfilter_test (bf, &tmp) == GNUNET_YES)
 184       falseok++;
 185   }
 186   if (falseok > 0)
 187   {
 188     GNUNET_CONTAINER_bloomfilter_free (bf);
 189     GNUNET_CONTAINER_bloomfilter_free (bfi);
 190     return -1;
 191   }
 192
 193   if (GNUNET_OK != GNUNET_CONTAINER_bloomfilter_or (bf, buf, SIZE))
 194   {
 195     GNUNET_CONTAINER_bloomfilter_free (bf);
 196     GNUNET_CONTAINER_bloomfilter_free (bfi);
 197     return -1;
 198   }
 199
 200   GNUNET_CRYPTO_seed_weak_random (2);
 201   i = 20;
 202   GNUNET_CONTAINER_bloomfilter_resize (bfi, &add_iterator, &i, SIZE * 2, K);
 203
 204   GNUNET_CRYPTO_seed_weak_random (2);
 205   i = 20;
 206   GNUNET_CONTAINER_bloomfilter_resize (bf, &add_iterator, &i, SIZE * 2, K);
 207   GNUNET_CRYPTO_seed_weak_random (2);
 208
 209   ok1 = 0;
 210   ok2 = 0;
 211   for (i = 0; i < 20; i++)
 212   {
 213     nextHC (&tmp);
 214     if (GNUNET_CONTAINER_bloomfilter_test (bf, &tmp) == GNUNET_YES)
 215       ok1++;
 216     if (GNUNET_CONTAINER_bloomfilter_test (bfi, &tmp) == GNUNET_YES)
 217       ok2++;
 218   }
 219
 220   if (ok1 != 20)
 221   {
 222     printf ("Expected 20 elements in resized file-backed filter"
 223             " after adding 20, got %d\n", ok1);
 224     GNUNET_CONTAINER_bloomfilter_free (bf);
 225     GNUNET_CONTAINER_bloomfilter_free (bfi);
 226     return -1;
 227   }
 228   if (ok2 != 20)
 229   {
 230     printf ("Expected 20 elements in resized filter"
 231             " after adding 20, got %d\n", ok2);
 232     GNUNET_CONTAINER_bloomfilter_free (bf);
 233     GNUNET_CONTAINER_bloomfilter_free (bfi);
 234     return -1;
 235   }
 236
 237
 238   GNUNET_CONTAINER_bloomfilter_free (bf);
 239   GNUNET_CONTAINER_bloomfilter_free (bfi);
 240
 241   GNUNET_break (0 == UNLINK (TESTFILE));
 242   return 0;
 243 }