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