Rice Pastry API

rice.p2p.util
Class IdBloomFilter

java.lang.Object
  extended by 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

Rice Pastry API

Copyright © 2001-2005 - Rice Pastry.


Imprint-Dataprotection