| Methods Summary |
|---|
| public int | add(byte[] value)
return( add( bytesToInteger( value )));
|
| protected int | add(int value)
int count = 0xffff;
for (int i=0;i<HASH_NUM;i++){
int index = getHash( i, value );
// v = value BEFORE inc
int v = incValue( index );
if ( v < count ){
count = v;
}
}
if ( count == 0 ){
entry_count++;
}
// count is the smallest val found *before* incrementing
return( trimValue( count + 1 ));
|
| protected int | bytesToInteger(byte[] data)
int res = 0x51f7ac81;
for (int i=0;i<data.length;i++){
//res ^= (data[i]&0xff)<<((i%4)*8);
res = res * 191 + (data[i]&0xff);
}
return( res );
|
| protected boolean | contains(int value)
for (int i=0;i<HASH_NUM;i++){
int index = getHash( i, value );
int v = getValue( index );
if ( v == 0 ){
return( false );
}
}
return( true );
|
| public boolean | contains(byte[] value)
return( contains( bytesToInteger( value )));
|
| public int | count(byte[] value)
return( count( bytesToInteger( value )));
|
| protected int | count(int value)
int count = 0xffff;
for (int i=0;i<HASH_NUM;i++){
int index = getHash( i, value );
int v = getValue( index );
if ( v < count ){
count = v;
}
}
return( count );
|
| protected abstract int | decValue(int index)
|
| public int | getEntryCount()
return( entry_count );
|
| protected int | getHash(int function, int value)
long res;
switch( function ){
case 0:
{
// x mod p
res = value;
break;
}
case 1:
{
// x^2 mod p
res = value * value;
break;
}
case 2:
{
// bx + a mod p
res = value * a2 + b2;
break;
}
case 3:
{
// cx + d mod p
res = value * a3 + b3;
break;
}
case 4:
{
// ex + f mod p
res = value * a4 + b4;
break;
}
default:
{
System.out.println( "**** BloomFilter hash function doesn't exist ****" );
res = 0;
}
}
// System.out.println( "hash[" + function + "] " + value + "->" + r );
return( Math.abs( (int)res % max_entries ));
|
| protected int | getMaxEntries()
return( max_entries );
|
| protected static byte[] | getSerialization(byte[] address, int port)
//combine address and port bytes into one
byte[] full_address = new byte[ address.length +2 ];
System.arraycopy( address, 0, full_address, 0, address.length );
full_address[ address.length ] = (byte)(port >> 8);
full_address[ address.length +1 ] = (byte)(port & 0xff);
return full_address;
|
| public int | getSize()
return( max_entries );
|
| protected abstract int | getValue(int index)
|
| protected abstract int | incValue(int index)
|
| public static void | main(java.lang.String[] args)
Random rand = new Random();
/*
BloomFilter b1 = new BloomFilterAddRemove8Bit(10000);
for (int i=0;i<260;i++){
System.out.println( b1.add( "parp".getBytes()) + ", count = " + b1.count( "parp".getBytes()) + ", ent = " + b1.getEntryCount());
}
for (int i=0;i<260;i++){
System.out.println( b1.remove( "parp".getBytes())+ ", count = " + b1.count( "parp".getBytes()) + ", ent = " + b1.getEntryCount());
}
*/
/*
BloomFilter b1 = new BloomFilterAddOnly(90*10/3);
byte[] key1 = new byte[4];
for (int i=0;i<200;i++){
if ( i%2==0){
rand.nextBytes( key1 );
}
b1.add( key1 );
System.out.println( "entries = " + b1.getEntryCount() + ", act = " + i );
}
System.exit(0);
*/
int fp_count = 0;
for (int j=0;j<1000;j++){
long start = System.currentTimeMillis();
BloomFilter b = new BloomFilterAddRemove8Bit(10000);
//BloomFilter b = new BloomFilterAddOnly(10000);
int fp = 0;
for (int i=0;i<1000;i++){
//String key = "" + rand.nextInt();
byte[] key = new byte[6];
rand.nextBytes( key );
//key = getSerialization( key, 6881 );
if ( i%2 == 0 ){
b.add( key );
if ( !b.contains( key )){
System.out.println( "false negative on add!!!!" );
}
}else{
if ( b.contains( key )){
fp++;
}
}
/*
if ( i%2 == 0 ){
b.remove( key );
if ( b.contains( key )){
System.out.println( "false positive" );
}
}
*/
}
System.out.println( "" + (System.currentTimeMillis() - start + ", fp = " + fp ));
if ( fp > 0 ){
fp_count++;
}
}
System.out.println( fp_count );
|
| public int | remove(byte[] value)
return( remove( bytesToInteger( value )));
|
| protected int | remove(int value)
int count = 0xffff;
for (int i=0;i<HASH_NUM;i++){
int index = getHash( i, value );
// v = value BEFORE dec
int v = decValue( index );
if ( v < count ){
count = v;
}
}
if ( count == 1 && entry_count > 0 ){
entry_count--;
}
// count is the value BEFORE dec, decrease one further
return( trimValue( count - 1 ));
|
| protected abstract int | trimValue(int value)
|
