gnunet-service-set_union_strata_estimator.c

Go to the documentation of this file.

/*
      This file is part of GNUnet
      Copyright (C) 2012 GNUnet e.V.
 
      GNUnet is free software: you can redistribute it and/or modify it
      under the terms of the GNU Affero General Public License as published
      by the Free Software Foundation, either version 3 of the License,
      or (at your option) any later version.
 
      GNUnet is distributed in the hope that it will be useful, but
      WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      Affero General Public License for more details.
 
      You should have received a copy of the GNU Affero General Public License
      along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
     SPDX-License-Identifier: AGPL3.0-or-later
 */
#include "platform.h"
#include "gnunet_util_lib.h"
#include "ibf.h"
#include "gnunet-service-set_union_strata_estimator.h"
 
 
#define FAIL_10_1_COMPATIBILTIY 1
 
 
size_t
strata_estimator_write (const struct StrataEstimator *se,
                        void *buf)
{
  char *sbuf = buf;
  unsigned int i;
  size_t osize;
 
  GNUNET_assert (NULL != se);
  for (i = 0; i < se->strata_count; i++)
  {
    ibf_write_slice (se->strata[i],
                     0,
                     se->ibf_size,
                     &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]);
  }
  osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
#if FAIL_10_1_COMPATIBILTIY
  {
    char *cbuf;
    size_t nsize;
 
    if (GNUNET_YES ==
        GNUNET_try_compression (buf,
                                osize,
                                &cbuf,
                                &nsize))
    {
      GNUNET_memcpy (buf, cbuf, nsize);
      osize = nsize;
      GNUNET_free (cbuf);
    }
  }
#endif
  return osize;
}
 
 
int
strata_estimator_read (const void *buf,
                       size_t buf_len,
                       int is_compressed,
                       struct StrataEstimator *se)
{
  unsigned int i;
  size_t osize;
  char *dbuf;
 
  dbuf = NULL;
  if (GNUNET_YES == is_compressed)
  {
    osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
    dbuf = GNUNET_decompress (buf,
                              buf_len,
                              osize);
    if (NULL == dbuf)
    {
      GNUNET_break_op (0);    /* bad compressed input data */
      return GNUNET_SYSERR;
    }
    buf = dbuf;
    buf_len = osize;
  }
 
  if (buf_len != se->strata_count * se->ibf_size * IBF_BUCKET_SIZE)
  {
    GNUNET_break (0);  /* very odd error */
    GNUNET_free (dbuf);
    return GNUNET_SYSERR;
  }
 
  for (i = 0; i < se->strata_count; i++)
  {
    ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
    buf += se->ibf_size * IBF_BUCKET_SIZE;
  }
  GNUNET_free (dbuf);
  return GNUNET_OK;
}
 
 
void
strata_estimator_insert (struct StrataEstimator *se,
                         struct IBF_Key key)
{
  uint64_t v;
  unsigned int i;
 
  v = key.key_val;
  /* count trailing '1'-bits of v */
  for (i = 0; v & 1; v >>= 1, i++)
    /* empty */;
  ibf_insert (se->strata[i], key);
}
 
 
void
strata_estimator_remove (struct StrataEstimator *se,
                         struct IBF_Key key)
{
  uint64_t v;
  unsigned int i;
 
  v = key.key_val;
  /* count trailing '1'-bits of v */
  for (i = 0; v & 1; v >>= 1, i++)
    /* empty */;
  ibf_remove (se->strata[i], key);
}
 
 
struct StrataEstimator *
strata_estimator_create (unsigned int strata_count,
                         uint32_t ibf_size,
                         uint8_t ibf_hashnum)
{
  struct StrataEstimator *se;
  unsigned int i;
  unsigned int j;
 
  se = GNUNET_new (struct StrataEstimator);
  se->strata_count = strata_count;
  se->ibf_size = ibf_size;
  se->strata = GNUNET_new_array (strata_count,
                                 struct InvertibleBloomFilter *);
  for (i = 0; i < strata_count; i++)
  {
    se->strata[i] = ibf_create (ibf_size, ibf_hashnum);
    if (NULL == se->strata[i])
    {
      GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                  "Failed to allocate memory for strata estimator\n");
      for (j = 0; j < i; j++)
        ibf_destroy (se->strata[i]);
      GNUNET_free (se);
      return NULL;
    }
  }
  return se;
}
 
 
unsigned int
strata_estimator_difference (const struct StrataEstimator *se1,
                             const struct StrataEstimator *se2)
{
  unsigned int count;
 
  GNUNET_assert (se1->strata_count == se2->strata_count);
  count = 0;
  for (int i = se1->strata_count - 1; i >= 0; i--)
  {
    struct InvertibleBloomFilter *diff;
    /* number of keys decoded from the ibf */
 
    /* FIXME: implement this without always allocating new IBFs */
    diff = ibf_dup (se1->strata[i]);
    ibf_subtract (diff, se2->strata[i]);
    for (int ibf_count = 0; GNUNET_YES; ibf_count++)
    {
      int more;
 
      more = ibf_decode (diff, NULL, NULL);
      if (GNUNET_NO == more)
      {
        count += ibf_count;
        break;
      }
      /* Estimate if decoding fails or would not terminate */
      if ((GNUNET_SYSERR == more) || (ibf_count > diff->size))
      {
        ibf_destroy (diff);
        return count * (1 << (i + 1));
      }
    }
    ibf_destroy (diff);
  }
  return count;
}
 
 
struct StrataEstimator *
strata_estimator_dup (struct StrataEstimator *se)
{
  struct StrataEstimator *c;
  unsigned int i;
 
  c = GNUNET_new (struct StrataEstimator);
  c->strata_count = se->strata_count;
  c->ibf_size = se->ibf_size;
  c->strata = GNUNET_new_array (se->strata_count,
                                struct InvertibleBloomFilter *);
  for (i = 0; i < se->strata_count; i++)
    c->strata[i] = ibf_dup (se->strata[i]);
  return c;
}
 
 
void
strata_estimator_destroy (struct StrataEstimator *se)
{
  unsigned int i;
 
  for (i = 0; i < se->strata_count; i++)
    ibf_destroy (se->strata[i]);
  GNUNET_free (se->strata);
  GNUNET_free (se);
}