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
  71 struct StrataEstimator *
  72 strata_estimator_create (unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
  73 {
  74   struct StrataEstimator *se;
  75   int i;
  76
  77   /* fixme: allocate everything in one chunk */
  78
  79   se = GNUNET_malloc (sizeof (struct StrataEstimator));
  80   se->strata_count = strata_count;
  81   se->ibf_size = ibf_size;
  82   se->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * strata_count);
  83   for (i = 0; i < strata_count; i++)
  84     se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
  85   return se;
  86 }
  87
  88
  89 /**
  90  * Estimate set difference with two strata estimators,
  91  * i.e. arrays of IBFs.
  92  * Does not not modify its arguments.
  93  *
  94  * @param se1 first strata estimator
  95  * @param se2 second strata estimator
  96  * @return the estimated difference
  97  */
  98 unsigned int
  99 strata_estimator_difference (const struct StrataEstimator *se1,
 100                              const struct StrataEstimator *se2)
 101 {
 102   int i;
 103   int count;
 104
 105   GNUNET_assert (se1->strata_count == se2->strata_count);
 106   count = 0;
 107   for (i = se1->strata_count - 1; i >= 0; i--)
 108   {
 109     struct InvertibleBloomFilter *diff;
 110     /* number of keys decoded from the ibf */
 111     int ibf_count;
 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 (ibf_count = 0; GNUNET_YES; ibf_count++)
 116     {
 117       int more;
 118
 119       more = ibf_decode (diff, NULL, NULL);
 120       if (GNUNET_NO == more)
 121       {
 122         count += ibf_count;
 123         break;
 124       }
 125       /* Estimate if decoding fails or would not terminate */
 126       if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
 127       {
 128         ibf_destroy (diff);
 129         return count * (1 << (i + 1));
 130       }
 131     }
 132     ibf_destroy (diff);
 133   }
 134   return count;
 135 }
 136
 137 /**
 138  * Make a copy of a strata estimator.
 139  *
 140  * @param se the strata estimator to copy
 141  * @return the copy
 142  */
 143 struct StrataEstimator *
 144 strata_estimator_dup (struct StrataEstimator *se)
 145 {
 146   struct StrataEstimator *c;
 147   int i;
 148
 149   c = GNUNET_malloc (sizeof (struct StrataEstimator));
 150   c->strata_count = se->strata_count;
 151   c->ibf_size = se->ibf_size;
 152   c->strata = GNUNET_malloc (sizeof (struct InvertibleBloomFilter *) * se->strata_count);
 153   for (i = 0; i < se->strata_count; i++)
 154     c->strata[i] = ibf_dup (se->strata[i]);
 155   return c;
 156 }
 157
 158
 159 void
 160 strata_estimator_destroy (struct StrataEstimator *se)
 161 {
 162   int i;
 163   for (i = 0; i < se->strata_count; i++)
 164     ibf_destroy (se->strata[i]);
 165   GNUNET_free (se->strata);
 166   GNUNET_free (se);
 167 }
 168