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