bloomfilter.c

GNUnet是一个安全的点对点网络框架

          round++;
          slot = 0;
        }
    }
}

/**
 * Callback: increment bit
 *
 * @param bf the filter to manipulate
 * @param bit the bit to increment
 * @param arg not used
 */
static void
incrementBitCallback (Bloomfilter * bf, unsigned int bit, void *arg)
{
  incrementBit (bf->bitArray, bit, bf->fd);
}

/**
 * Callback: decrement bit
 *
 * @param bf the filter to manipulate
 * @param bit the bit to decrement
 * @param arg not used
 */
static void
decrementBitCallback (Bloomfilter * bf, unsigned int bit, void *arg)
{
  decrementBit (bf->bitArray, bit, bf->fd);
}

/**
 * Callback: test if all bits are set
 *
 * @param bf the filter
 * @param bit the bit to test
 * @param arg pointer set to GNUNET_NO if bit is not set
 */
static void
testBitCallback (Bloomfilter * bf, unsigned int bit, void *cls)
{
  int *arg = cls;
  if (GNUNET_NO == testBit (bf->bitArray, bit))
    *arg = GNUNET_NO;
}

/* *********************** INTERFACE **************** */

/**
 * Load a bloom-filter from a file.
 *
 * @param filename the name of the file (or the prefix)
 * @param size the size of the bloom-filter (number of
 *        bytes of storage space to use)
 * @param k the number of GNUNET_hash-functions to apply per
 *        element (number of bits set per element in the set)
 * @return the bloomfilter
 */
Bloomfilter *
GNUNET_bloomfilter_load (struct GNUNET_GE_Context *ectx,
                         const char *filename, unsigned int size,
                         unsigned int k)
{
  Bloomfilter *bf;
  char *rbuff;
  unsigned int pos;
  int i;
  unsigned int ui;

  if ((k == 0) || (size == 0))
    return NULL;
  if (size < BUFFSIZE)
    size = BUFFSIZE;
  ui = 1;
  while (ui < size)
    ui *= 2;
  size = ui;                    /* make sure it's a power of 2 */

  bf = GNUNET_malloc (sizeof (Bloomfilter));
  bf->ectx = ectx;
  /* Try to open a bloomfilter file */
  if (filename != NULL)
    {
#ifndef _MSC_VER
      bf->fd = GNUNET_disk_file_open (ectx,
                                      filename, O_RDWR | O_CREAT,
                                      S_IRUSR | S_IWUSR);
#else
      bf->fd = GNUNET_disk_file_open (ectx,
                                      filename,
                                      O_WRONLY | O_CREAT, S_IREAD | S_IWRITE);
#endif
      if (-1 == bf->fd)
        {
          GNUNET_free (bf);
          return NULL;
        }
      bf->filename = GNUNET_strdup (filename);
    }
  else
    {
      bf->fd = -1;
      bf->filename = NULL;
    }
  /* Alloc block */
  bf->lock = GNUNET_mutex_create (GNUNET_YES);
  bf->bitArray = GNUNET_malloc_large (size);
  bf->bitArraySize = size;
  bf->addressesPerElement = k;
  memset (bf->bitArray, 0, bf->bitArraySize);

  if (bf->fd != -1)
    {
      /* Read from the file what bits we can */
      rbuff = GNUNET_malloc (BUFFSIZE);
      pos = 0;
      while (pos < size * 8)
        {
          int res;

          res = READ (bf->fd, rbuff, BUFFSIZE);
          if (res == 0)
            break;              /* is ok! we just did not use that many bits yet */
          for (i = 0; i < res; i++)
            {
              if ((rbuff[i] & 0x0F) != 0)
                setBit (bf->bitArray, pos + i * 2);
              if ((rbuff[i] & 0xF0) != 0)
                setBit (bf->bitArray, pos + i * 2 + 1);
            }
          if (res < BUFFSIZE)
            break;
          pos += BUFFSIZE * 2;  /* 2 bits per byte in the buffer */
        }
      GNUNET_free (rbuff);
    }
  return bf;
}


/**
 * Create a bloom filter from raw bits.
 *
 * @param data the raw bits in memory (maybe NULL,
 *        in which case all bits should be considered
 *        to be zero).
 * @param size the size of the bloom-filter (number of
 *        bytes of storage space to use); also size of data
 *        -- unless data is NULL
 * @param k the number of GNUNET_hash-functions to apply per
 *        element (number of bits set per element in the set)
 * @return the bloomfilter
 */
struct GNUNET_BloomFilter *
GNUNET_bloomfilter_init (struct GNUNET_GE_Context
                         *ectx,
                         const char *data, unsigned int size, unsigned int k)
{
  Bloomfilter *bf;
  unsigned int ui;

  if ((k == 0) || (size == 0))
    return NULL;
  ui = 1;
  while (ui < size)
    ui *= 2;
  size = ui;                    /* make sure it's a power of 2 */

  bf = GNUNET_malloc (sizeof (Bloomfilter));
  bf->ectx = ectx;
  bf->fd = -1;
  bf->filename = NULL;
  bf->lock = GNUNET_mutex_create (GNUNET_YES);
  bf->bitArray = GNUNET_malloc_large (size);
  bf->bitArraySize = size;
  bf->addressesPerElement = k;
  memset (bf->bitArray, 0, bf->bitArraySize);
  return bf;
}


/**
 * Copy the raw data of this bloomfilter into
 * the given data array.
 *
 * @param data where to write the data
 * @param size the size of the given data array
 * @return GNUNET_SYSERR if the data array is not big enough
 */
int
GNUNET_bloomfilter_get_raw_data (struct GNUNET_BloomFilter *bf,
                                 char *data, unsigned int size)
{
  if (bf->bitArraySize != size)
    return GNUNET_SYSERR;
  memcpy (data, bf->bitArray, size);
  return GNUNET_OK;
}

/**
 * Free the space associated with a filter
 * in memory, flush to drive if needed (do not
 * free the space on the drive)
 *
 * @param bf the filter
 */
void
GNUNET_bloomfilter_free (Bloomfilter * bf)
{
  if (NULL == bf)
    return;
  GNUNET_mutex_destroy (bf->lock);
  if (bf->fd != -1)
    GNUNET_disk_file_close (bf->ectx, bf->filename, bf->fd);
  GNUNET_free_non_null (bf->filename);
  GNUNET_free (bf->bitArray);
  GNUNET_free (bf);
}

/**
 * Reset a bloom filter to empty. Clears the file on disk.
 *
 * @param bf the filter
 */
void
GNUNET_bloomfilter_clear (Bloomfilter * bf)
{
  if (NULL == bf)
    return;

  GNUNET_mutex_lock (bf->lock);
  memset (bf->bitArray, 0, bf->bitArraySize);
  if (bf->fd != -1)
    makeEmptyFile (bf->fd, bf->bitArraySize * 4);
  GNUNET_mutex_unlock (bf->lock);
}


/**
 * Test if an element is in the filter.
 *
 * @param e the element
 * @param bf the filter
 * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not
 */
int
GNUNET_bloomfilter_test (Bloomfilter * bf, const GNUNET_HashCode * e)
{
  int res;

  if (NULL == bf)
    return GNUNET_YES;
  GNUNET_mutex_lock (bf->lock);
  res = GNUNET_YES;
  iterateBits (bf, &testBitCallback, &res, e);
  GNUNET_mutex_unlock (bf->lock);
  return res;
}

/**
 * Add an element to the filter
 *
 * @param bf the filter
 * @param e the element
 */
void
GNUNET_bloomfilter_add (Bloomfilter * bf, const GNUNET_HashCode * e)
{

  if (NULL == bf)
    return;
  GNUNET_mutex_lock (bf->lock);
  iterateBits (bf, &incrementBitCallback, NULL, e);
  GNUNET_mutex_unlock (bf->lock);
}


/**
 * Or the entries of the given raw data array with the
 * data of the given bloom filter.  Assumes that
 * the size of the data array and the current filter
 * match.
 * @param bf the filter
 */
int
GNUNET_bloomfilter_or (struct GNUNET_BloomFilter *bf,
                       const char *data, unsigned int size)
{
  unsigned int i;

  if (bf->bitArraySize != size)
    return GNUNET_SYSERR;
  /* FIXME: we could do this 4-8x faster by
     going over int/long arrays */
  for (i = 0; i < size; i++)
    bf->bitArray[i] |= data[i];
  return GNUNET_OK;
}

/**
 * Remove an element from the filter.
 *
 * @param bf the filter
 * @param e the element to remove
 */
void
GNUNET_bloomfilter_remove (Bloomfilter * bf, const GNUNET_HashCode * e)
{
  if (NULL == bf)
    return;
  GNUNET_mutex_lock (bf->lock);
  iterateBits (bf, &decrementBitCallback, NULL, e);
  GNUNET_mutex_unlock (bf->lock);
}

/**
 * Resize a bloom filter.  Note that this operation
 * is pretty costly.  Essentially, the bloom filter
 * needs to be completely re-build.
 *
 * @param bf the filter
 * @param iterator an iterator over all elements stored in the BF
 * @param iterator_arg argument to the iterator function
 * @param size the new size for the filter
 * @param k the new number of GNUNET_hash-function to apply per element
 */
void
GNUNET_bloomfilter_resize (Bloomfilter * bf,
                           GNUNET_HashCodeIterator iterator,
                           void *iterator_arg, unsigned int size,
                           unsigned int k)
{
  GNUNET_HashCode hc;
  unsigned int i;

  GNUNET_mutex_lock (bf->lock);
  GNUNET_free (bf->bitArray);
  i = 1;
  while (i < size)
    i *= 2;
  size = i;                     /* make sure it's a power of 2 */

  bf->bitArraySize = size;
  bf->bitArray = GNUNET_malloc (size);
  memset (bf->bitArray, 0, bf->bitArraySize);
  if (bf->fd != -1)
    makeEmptyFile (bf->fd, bf->bitArraySize * 4);
  while (GNUNET_YES == iterator (&hc, iterator_arg))
    GNUNET_bloomfilter_add (bf, &hc);
  GNUNET_mutex_unlock (bf->lock);
}

/* ******************** end of bloomfilter.c *********** */