rice.p2p.util
Class IdBloomFilter

java.lang.Object
  rice.p2p.util.IdBloomFilter

All Implemented Interfaces:

java.io.Serializable

public class IdBloomFilter
extends java.lang.Object
implements java.io.Serializable

Version:

$Id: IdBloomFilter.java 3558 2007-01-24 16:16:57Z jeffh $

Author:

Alan Mislove

See Also:

Serialized Form

Field Summary

protected byte[]	array An internal byte[] for managing ids in a memory-efficent manner The deal with this is that we will be creating a ton of arrays in addId/check.
protected BloomFilter	filter The parameters to the hash functions for this bloom filter
static int	NUM_BITS_PER_KEY The number of bits per key in bloom filters
static int	NUM_HASH_FUNCTIONS The number of different hash functions to use in bloom filters

Constructor Summary

IdBloomFilter(IdSet set)
Constructor which takes the number of hash functions to use and the length of the set to use.

IdBloomFilter(InputBuffer buf)

Method Summary

protected void	addId(Id id) Method which adds an Id to the underlying bloom filter
boolean	check(Id id) Method which returns whether or not an Id *may* be in the set.
void	check(IdSet set, IdSet result, int max) Method which checks an entire IdSet to see if they exist in this bloom filter, and returns the response by adding elements to the other provided id set.
protected void	checkArray(Id id) Internal method for checking to see if the array exists, and if not, instanciating it.
void	serialize(OutputBuffer buf)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

NUM_BITS_PER_KEY

public static int NUM_BITS_PER_KEY

The number of bits per key in bloom filters

NUM_HASH_FUNCTIONS

public static int NUM_HASH_FUNCTIONS

The number of different hash functions to use in bloom filters

array

protected transient byte[] array

An internal byte[] for managing ids in a memory-efficent manner The deal with this is that we will be creating a ton of arrays in addId/check. So, what we do is allocate only 1 on a lazy basis. The call to checkArray() will construct a new array if there isn't one yet, then it will encode the id into the array.

filter

protected BloomFilter filter

The parameters to the hash functions for this bloom filter

Constructor Detail

IdBloomFilter

public IdBloomFilter(IdSet set)

Constructor which takes the number of hash functions to use and the length of the set to use.

Parameters:

num - The number of hash functions to use

length - The length of the underlying bit set

IdBloomFilter

public IdBloomFilter(InputBuffer buf)
              throws java.io.IOException

Throws:

java.io.IOException

Method Detail

checkArray

protected void checkArray(Id id)

Internal method for checking to see if the array exists, and if not, instanciating it. It also places the given Id into the array. See the documentation of the member variable array for more info.

Parameters:

id - An id to build the array from

addId

protected void addId(Id id)

Method which adds an Id to the underlying bloom filter

Parameters:

id - The id to add

check

public boolean check(Id id)

Method which returns whether or not an Id *may* be in the set. Specifically, if this method returns false, the element is definately not in the set. Otherwise, if true is returned, the element may be in the set, but it is not guaranteed.

Parameters:

id - The id to check for

check

public void check(IdSet set,
                  IdSet result,
                  int max)

Method which checks an entire IdSet to see if they exist in this bloom filter, and returns the response by adding elements to the other provided id set.

Parameters:

set - THe set to check for

result - The set to put the non-existing objects into

max - The maximum number of keys to return

serialize

public void serialize(OutputBuffer buf)
               throws java.io.IOException

Throws:

java.io.IOException