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