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