src/set/gnunet-service-set_union_strata_estimator.c

   1 /*
   2       This file is part of GNUnet
   3       Copyright (C) 2012 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., 51 Franklin Street, Fifth Floor,
  18       Boston, MA 02110-1301, USA.
  19 */
  20 /**
  21  * @file set/gnunet-service-set_union_strata_estimator.c
  22  * @brief invertible bloom filter
  23  * @author Florian Dold
  24  */
  25 #include "platform.h"
  26 #include "gnunet_util_lib.h"
  27 #include "ibf.h"
  28 #include "gnunet-service-set_union_strata_estimator.h"
  29
  30
  31 /**
  32  * Write the given strata estimator to the buffer.
  33  *
  34  * @param se strata estimator to serialize
  35  * @param buf buffer to write to, must be of appropriate size
  36  */
  37 void
  38 strata_estimator_write (const struct StrataEstimator *se,
  39                         void *buf)
  40 {
  41   unsigned int i;
  42
  43   GNUNET_assert (NULL != se);
  44   for (i = 0; i < se->strata_count; i++)
  45   {
  46     ibf_write_slice (se->strata[i], 0, se->ibf_size, buf);
  47     buf += se->ibf_size * IBF_BUCKET_SIZE;
  48   }
  49 }
  50
  51
  52 /**
  53  * Read strata from the buffer into the given strata
  54  * estimator.  The strata estimator must already be allocated.
  55  *
  56  * @param buf buffer to read from
  57  * @param se strata estimator to write to
  58  */
  59 void
  60 strata_estimator_read (const void *buf,
  61                        struct StrataEstimator *se)
  62 {
  63   unsigned int i;
  64
  65   for (i = 0; i < se->strata_count; i++)
  66   {
  67     ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
  68     buf += se->ibf_size * IBF_BUCKET_SIZE;
  69   }
  70 }
  71
  72
  73 /**
  74  * Add a key to the strata estimator.
  75  *
  76  * @param se strata estimator to add the key to
  77  * @param key key to add
  78  */
  79 void
  80 strata_estimator_insert (struct StrataEstimator *se,
  81                          struct IBF_Key key)
  82 {
  83   uint64_t v;
  84   unsigned int i;
  85
  86   v = key.key_val;
  87   /* count trailing '1'-bits of v */
  88   for (i = 0; v & 1; v>>=1, i++)
  89     /* empty */;
  90   ibf_insert (se->strata[i], key);
  91 }
  92
  93
  94 /**
  95  * Remove a key from the strata estimator.
  96  *
  97  * @param se strata estimator to remove the key from
  98  * @param key key to remove
  99  */
 100 void
 101 strata_estimator_remove (struct StrataEstimator *se,
 102                          struct IBF_Key key)
 103 {
 104   uint64_t v;
 105   unsigned int i;
 106
 107   v = key.key_val;
 108   /* count trailing '1'-bits of v */
 109   for (i = 0; v & 1; v>>=1, i++)
 110     /* empty */;
 111   ibf_remove (se->strata[i], key);
 112 }
 113
 114
 115 /**
 116  * Create a new strata estimator with the given parameters.
 117  *
 118  * @param strata_count number of stratas, that is, number of ibfs in the estimator
 119  * @param ibf_size size of each ibf stratum
 120  * @param ibf_hashnum hashnum parameter of each ibf
 121  * @return a freshly allocated, empty strata estimator
 122  */
 123 struct StrataEstimator *
 124 strata_estimator_create (unsigned int strata_count,
 125                          uint32_t ibf_size,
 126                          uint8_t ibf_hashnum)
 127 {
 128   struct StrataEstimator *se;
 129   unsigned int i;
 130
 131   /* fixme: allocate everything in one chunk */
 132   se = GNUNET_new (struct StrataEstimator);
 133   se->strata_count = strata_count;
 134   se->ibf_size = ibf_size;
 135   se->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * strata_count);
 136   for (i = 0; i < strata_count; i++)
 137     se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
 138   return se;
 139 }
 140
 141
 142 /**
 143  * Estimate set difference with two strata estimators,
 144  * i.e. arrays of IBFs.
 145  * Does not not modify its arguments.
 146  *
 147  * @param se1 first strata estimator
 148  * @param se2 second strata estimator
 149  * @return the estimated difference
 150  */
 151 unsigned int
 152 strata_estimator_difference (const struct StrataEstimator *se1,
 153                              const struct StrataEstimator *se2)
 154 {
 155   int i;
 156   unsigned int count;
 157
 158   GNUNET_assert (se1->strata_count == se2->strata_count);
 159   count = 0;
 160   for (i = se1->strata_count - 1; i >= 0; i--)
 161   {
 162     struct InvertibleBloomFilter *diff;
 163     /* number of keys decoded from the ibf */
 164     int ibf_count;
 165
 166     /* FIXME: implement this without always allocating new IBFs */
 167     diff = ibf_dup (se1->strata[i]);
 168     ibf_subtract (diff, se2->strata[i]);
 169     for (ibf_count = 0; GNUNET_YES; ibf_count++)
 170     {
 171       int more;
 172
 173       more = ibf_decode (diff, NULL, NULL);
 174       if (GNUNET_NO == more)
 175       {
 176         count += ibf_count;
 177         break;
 178       }
 179       /* Estimate if decoding fails or would not terminate */
 180       if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
 181       {
 182         ibf_destroy (diff);
 183         return count * (1 << (i + 1));
 184       }
 185     }
 186     ibf_destroy (diff);
 187   }
 188   return count;
 189 }
 190
 191
 192 /**
 193  * Make a copy of a strata estimator.
 194  *
 195  * @param se the strata estimator to copy
 196  * @return the copy
 197  */
 198 struct StrataEstimator *
 199 strata_estimator_dup (struct StrataEstimator *se)
 200 {
 201   struct StrataEstimator *c;
 202   unsigned int i;
 203
 204   c = GNUNET_new (struct StrataEstimator);
 205   c->strata_count = se->strata_count;
 206   c->ibf_size = se->ibf_size;
 207   c->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * se->strata_count);
 208   for (i = 0; i < se->strata_count; i++)
 209     c->strata[i] = ibf_dup (se->strata[i]);
 210   return c;
 211 }
 212
 213
 214 /**
 215  * Destroy a strata estimator, free all of its resources.
 216  *
 217  * @param se strata estimator to destroy.
 218  */
 219 void
 220 strata_estimator_destroy (struct StrataEstimator *se)
 221 {
 222   unsigned int i;
 223
 224   for (i = 0; i < se->strata_count; i++)
 225     ibf_destroy (se->strata[i]);
 226   GNUNET_free (se->strata);
 227   GNUNET_free (se);
 228 }
 229