src/util/test_container_bloomfilter.c

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