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" "200 expected after insertion.\n", ok1);
  93     GNUNET_CONTAINER_bloomfilter_free (bf);
  94     return -1;
  95   }
  96   if (GNUNET_OK != GNUNET_CONTAINER_bloomfilter_get_raw_data (bf, buf, SIZE))
  97   {
  98     GNUNET_CONTAINER_bloomfilter_free (bf);
  99     return -1;
 100   }
 101
 102   GNUNET_CONTAINER_bloomfilter_free (bf);
 103
 104   bf = GNUNET_CONTAINER_bloomfilter_load (TESTFILE, SIZE, K);
 105   GNUNET_assert (bf != NULL);
 106   bfi = GNUNET_CONTAINER_bloomfilter_init (buf, SIZE, K);
 107   GNUNET_assert (bfi != NULL);
 108
 109   SRANDOM (1);
 110   ok1 = 0;
 111   ok2 = 0;
 112   for (i = 0; i < 200; i++)
 113   {
 114     nextHC (&tmp);
 115     if (GNUNET_CONTAINER_bloomfilter_test (bf, &tmp) == GNUNET_YES)
 116       ok1++;
 117     if (GNUNET_CONTAINER_bloomfilter_test (bfi, &tmp) == GNUNET_YES)
 118       ok2++;
 119   }
 120   if (ok1 != 200)
 121   {
 122     printf ("Got %d elements out of 200 " "expected after reloading.\n", ok1);
 123     GNUNET_CONTAINER_bloomfilter_free (bf);
 124     GNUNET_CONTAINER_bloomfilter_free (bfi);
 125     return -1;
 126   }
 127
 128   if (ok2 != 200)
 129   {
 130     printf ("Got %d elements out of 200 "
 131             "expected after initialization.\n", ok2);
 132     GNUNET_CONTAINER_bloomfilter_free (bf);
 133     GNUNET_CONTAINER_bloomfilter_free (bfi);
 134     return -1;
 135   }
 136
 137   SRANDOM (1);
 138   for (i = 0; i < 100; i++)
 139   {
 140     nextHC (&tmp);
 141     GNUNET_CONTAINER_bloomfilter_remove (bf, &tmp);
 142     GNUNET_CONTAINER_bloomfilter_remove (bfi, &tmp);
 143   }
 144
 145   SRANDOM (1);
 146
 147   ok1 = 0;
 148   ok2 = 0;
 149   for (i = 0; i < 200; i++)
 150   {
 151     nextHC (&tmp);
 152     if (GNUNET_CONTAINER_bloomfilter_test (bf, &tmp) == GNUNET_YES)
 153       ok1++;
 154     if (GNUNET_CONTAINER_bloomfilter_test (bfi, &tmp) == GNUNET_YES)
 155       ok2++;
 156   }
 157
 158   if (ok1 != 100)
 159   {
 160     printf ("Expected 100 elements in loaded filter"
 161             " after adding 200 and deleting 100, got %d\n", ok1);
 162     GNUNET_CONTAINER_bloomfilter_free (bf);
 163     GNUNET_CONTAINER_bloomfilter_free (bfi);
 164     return -1;
 165   }
 166   if (ok2 != 200)
 167   {
 168     printf ("Expected 200 elements in initialized filter"
 169             " after adding 200 and deleting 100 "
 170             "(which should do nothing for a filter not backed by a file), got %d\n",
 171             ok2);
 172     GNUNET_CONTAINER_bloomfilter_free (bf);
 173     GNUNET_CONTAINER_bloomfilter_free (bfi);
 174     return -1;
 175   }
 176
 177   SRANDOM (3);
 178
 179   GNUNET_CONTAINER_bloomfilter_clear (bf);
 180   falseok = 0;
 181   for (i = 0; i < 1000; i++)
 182   {
 183     nextHC (&tmp);
 184     if (GNUNET_CONTAINER_bloomfilter_test (bf, &tmp) == GNUNET_YES)
 185       falseok++;
 186   }
 187   if (falseok > 0)
 188   {
 189     GNUNET_CONTAINER_bloomfilter_free (bf);
 190     GNUNET_CONTAINER_bloomfilter_free (bfi);
 191     return -1;
 192   }
 193
 194   if (GNUNET_OK != GNUNET_CONTAINER_bloomfilter_or (bf, buf, SIZE))
 195   {
 196     GNUNET_CONTAINER_bloomfilter_free (bf);
 197     GNUNET_CONTAINER_bloomfilter_free (bfi);
 198     return -1;
 199   }
 200
 201   SRANDOM (2);
 202   i = 20;
 203   GNUNET_CONTAINER_bloomfilter_resize (bfi, &add_iterator, &i, SIZE * 2, K);
 204
 205   SRANDOM (2);
 206   i = 20;
 207   GNUNET_CONTAINER_bloomfilter_resize (bf, &add_iterator, &i, SIZE * 2, K);
 208   SRANDOM (2);
 209
 210   ok1 = 0;
 211   ok2 = 0;
 212   for (i = 0; i < 20; i++)
 213   {
 214     nextHC (&tmp);
 215     if (GNUNET_CONTAINER_bloomfilter_test (bf, &tmp) == GNUNET_YES)
 216       ok1++;
 217     if (GNUNET_CONTAINER_bloomfilter_test (bfi, &tmp) == GNUNET_YES)
 218       ok2++;
 219   }
 220
 221   if (ok1 != 20)
 222   {
 223     printf ("Expected 20 elements in resized file-backed filter"
 224             " after adding 20, got %d\n", ok1);
 225     GNUNET_CONTAINER_bloomfilter_free (bf);
 226     GNUNET_CONTAINER_bloomfilter_free (bfi);
 227     return -1;
 228   }
 229   if (ok2 != 20)
 230   {
 231     printf ("Expected 20 elements in resized filter"
 232             " after adding 20, got %d\n", ok2);
 233     GNUNET_CONTAINER_bloomfilter_free (bf);
 234     GNUNET_CONTAINER_bloomfilter_free (bfi);
 235     return -1;
 236   }
 237
 238
 239   GNUNET_CONTAINER_bloomfilter_free (bf);
 240   GNUNET_CONTAINER_bloomfilter_free (bfi);
 241
 242   GNUNET_break (0 == UNLINK (TESTFILE));
 243   return 0;
 244 }