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