src/set/strata_estimator.c

   1 /*
   2       This file is part of GNUnet
   3       (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., 59 Temple Place - Suite 330,
  18       Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file set/ibf.h
  23  * @brief invertible bloom filter
  24  * @author Florian Dold
  25  */
  26
  27 #include "platform.h"
  28 #include "gnunet_util_lib.h"
  29 #include "ibf.h"
  30 #include "strata_estimator.h"
  31
  32 void
  33 strata_estimator_write (const struct StrataEstimator *se, void *buf)
  34 {
  35   int i;
  36
  37   GNUNET_assert (NULL != se);
  38   for (i = 0; i < se->strata_count; i++)
  39   {
  40     ibf_write_slice (se->strata[i], 0, se->ibf_size, buf);
  41     buf += se->ibf_size * IBF_BUCKET_SIZE;
  42   }
  43 }
  44
  45 void
  46 strata_estimator_read (const void *buf, struct StrataEstimator *se)
  47 {
  48   int i;
  49   for (i = 0; i < se->strata_count; i++)
  50   {
  51     ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
  52     buf += se->ibf_size * IBF_BUCKET_SIZE;
  53   }
  54 }
  55
  56
  57 void
  58 strata_estimator_insert (struct StrataEstimator *se, struct IBF_Key key)
  59 {
  60   uint64_t v;
  61   int i;
  62   v = key.key_val;
  63   /* count trailing '1'-bits of v */
  64   for (i = 0; v & 1; v>>=1, i++)
  65     /* empty */;
  66   ibf_insert (se->strata[i], key);
  67 }
  68
  69
  70 void
  71 strata_estimator_remove (struct StrataEstimator *se, struct IBF_Key key)
  72 {
  73   uint64_t v;
  74   int i;
  75   v = key.key_val;
  76   /* count trailing '1'-bits of v */
  77   for (i = 0; v & 1; v>>=1, i++)
  78     /* empty */;
  79   ibf_remove (se->strata[i], key);
  80 }
  81
  82
  83
  84 struct StrataEstimator *
  85 strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
  86 {
  87   struct StrataEstimator *se;
  88   int i;
  89
  90   /* fixme: allocate everything in one chunk */
  91
  92   se = GNUNET_malloc (sizeof (struct StrataEstimator));
  93   se->strata_count = strata_count;
  94   se->ibf_size = ibf_size;
  95   se->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * strata_count);
  96   for (i = 0; i < strata_count; i++)
  97     se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
  98   return se;
  99 }
 100
 101
 102 /**
 103  * Estimate set difference with two strata estimators,
 104  * i.e. arrays of IBFs.
 105  * Does not not modify its arguments.
 106  *
 107  * @param se1 first strata estimator
 108  * @param se2 second strata estimator
 109  * @return the estimated difference
 110  */
 111 unsigned int
 112 strata_estimator_difference (const struct StrataEstimator *se1,
 113                              const struct StrataEstimator *se2)
 114 {
 115   int i;
 116   int count;
 117
 118   GNUNET_assert (se1->strata_count == se2->strata_count);
 119   count = 0;
 120   for (i = se1->strata_count - 1; i >= 0; i--)
 121   {
 122     struct InvertibleBloomFilter *diff;
 123     /* number of keys decoded from the ibf */
 124     int ibf_count;
 125     /* FIXME: implement this without always allocating new IBFs */
 126     diff = ibf_dup (se1->strata[i]);
 127     ibf_subtract (diff, se2->strata[i]);
 128     for (ibf_count = 0; GNUNET_YES; ibf_count++)
 129     {
 130       int more;
 131
 132       more = ibf_decode (diff, NULL, NULL);
 133       if (GNUNET_NO == more)
 134       {
 135         count += ibf_count;
 136         break;
 137       }
 138       /* Estimate if decoding fails or would not terminate */
 139       if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
 140       {
 141         ibf_destroy (diff);
 142         return count * (1 << (i + 1));
 143       }
 144     }
 145     ibf_destroy (diff);
 146   }
 147   return count;
 148 }
 149
 150 /**
 151  * Make a copy of a strata estimator.
 152  *
 153  * @param se the strata estimator to copy
 154  * @return the copy
 155  */
 156 struct StrataEstimator *
 157 strata_estimator_dup (struct StrataEstimator *se)
 158 {
 159   struct StrataEstimator *c;
 160   int i;
 161
 162   c = GNUNET_malloc (sizeof (struct StrataEstimator));
 163   c->strata_count = se->strata_count;
 164   c->ibf_size = se->ibf_size;
 165   c->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * se->strata_count);
 166   for (i = 0; i < se->strata_count; i++)
 167     c->strata[i] = ibf_dup (se->strata[i]);
 168   return c;
 169 }
 170
 171
 172 void
 173 strata_estimator_destroy (struct StrataEstimator *se)
 174 {
 175   int i;
 176   for (i = 0; i < se->strata_count; i++)
 177     ibf_destroy (se->strata[i]);
 178   GNUNET_free (se->strata);
 179   GNUNET_free (se);
 180 }
 181