Author: j16sdiz
Date: 2008-07-28 15:02:32 +0000 (Mon, 28 Jul 2008)
New Revision: 21448
Modified:
branches/saltedhashstore/freenet/src/freenet/support/BinaryBloomFilter.java
branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
Log:
move more methods to abstract class
Modified:
branches/saltedhashstore/freenet/src/freenet/support/BinaryBloomFilter.java
===================================================================
--- branches/saltedhashstore/freenet/src/freenet/support/BinaryBloomFilter.java
2008-07-28 14:27:21 UTC (rev 21447)
+++ branches/saltedhashstore/freenet/src/freenet/support/BinaryBloomFilter.java
2008-07-28 15:02:32 UTC (rev 21448)
@@ -7,25 +7,12 @@
import java.io.IOException;
import java.io.RandomAccessFile;
import java.nio.ByteBuffer;
-import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel.MapMode;
-import java.security.MessageDigest;
-import java.util.concurrent.locks.ReadWriteLock;
-import java.util.concurrent.locks.ReentrantReadWriteLock;
-import freenet.crypt.SHA256;
-
/**
* @author sdiz
*/
public class BinaryBloomFilter extends BloomFilter {
- protected ByteBuffer filter;
- protected final int length;
- /** Number of hash functions */
- protected final int k;
- private ReadWriteLock lock = new ReentrantReadWriteLock();
- private boolean needRebuild;
-
/**
* Constructor
*
@@ -33,12 +20,8 @@
* length in bits
*/
public BinaryBloomFilter(int length, int k) {
- if (length % 8 != 0)
- throw new IllegalArgumentException();
-
+ super(length, k);
filter = ByteBuffer.allocate(length / 8);
- this.length = length;
- this.k = k;
}
/**
@@ -51,80 +34,26 @@
* @throws IOException
*/
public BinaryBloomFilter(File file, int length, int k) throws
IOException {
- if (length % 8 != 0)
- throw new IllegalArgumentException();
+ super(length, k);
if (!file.exists() || file.length() != length / 8)
needRebuild = true;
RandomAccessFile raf = new RandomAccessFile(file, "rw");
raf.setLength(length / 8);
filter = raf.getChannel().map(MapMode.READ_WRITE, 0, length /
8).load();
-
- this.length = length;
- this.k = k;
}
@Override
- public void addKey(byte[] key) {
- int[] hashes = getHashes(key);
- lock.writeLock().lock();
- try {
- for (int i = 0; i < k; i++)
- setBit(hashes[i]);
- } finally {
- lock.writeLock().unlock();
- }
-
- if (forkedFilter != null)
- forkedFilter.addKey(key);
- }
-
- @Override
- public void removeKey(byte[] key) {
+ public void removeKey(byte[] key) {
// ignore
}
@Override
- public boolean checkFilter(byte[] key) {
- int[] hashes = getHashes(key);
- lock.readLock().lock();
- try {
- for (int i = 0; i < k; i++)
- if (!getBit(hashes[i]))
- return false;
- } finally {
- lock.readLock().unlock();
- }
- return true;
- }
-
- private int[] getHashes(byte[] key) {
- int[] hashes = new int[k];
-
- MessageDigest md = SHA256.getMessageDigest();
- try {
- byte[] lastDigest = key;
- ByteBuffer bf = ByteBuffer.wrap(lastDigest);
-
- for (int i = 0; i < k; i++) {
- if (bf.remaining() < 4) {
- lastDigest = md.digest(lastDigest);
- bf = ByteBuffer.wrap(lastDigest);
- }
-
- hashes[i] = (int) ((bf.getInt() &
Long.MAX_VALUE) % length);
- }
- } finally {
- SHA256.returnMessageDigest(md);
- }
-
- return hashes;
- }
-
protected boolean getBit(int offset) {
return (filter.get(offset / 8) & (1 << (offset % 8))) != 0;
}
+ @Override
protected void setBit(int offset) {
byte b = filter.get(offset / 8);
b |= 1 << (offset % 8);
@@ -132,20 +61,12 @@
}
@Override
- public void force() {
- if (filter instanceof MappedByteBuffer) {
- ((MappedByteBuffer) filter).force();
- }
+ protected void unsetBit(int offset) {
+ // NO-OP
}
- protected BinaryBloomFilter forkedFilter;
-
- /**
- * Create an empty, in-memory copy of bloom filter. New updates are
written to both filters.
- * This is written back to disk on #merge()
- */
@Override
- public void fork(int k) {
+ public void fork(int k) {
lock.writeLock().lock();
try {
forkedFilter = new BinaryBloomFilter(length, k);
@@ -153,55 +74,4 @@
lock.writeLock().unlock();
}
}
-
- @Override
- public void discard() {
- lock.writeLock().lock();
- try {
- forkedFilter = null;
- } finally {
- lock.writeLock().unlock();
- }
- }
-
- @Override
- public void merge() {
- lock.writeLock().lock();
- try {
- if (forkedFilter == null)
- return;
-
- filter.position(0);
- forkedFilter.filter.position(0);
-
- filter.put(forkedFilter.filter);
-
- filter.position(0);
- forkedFilter = null;
- } finally {
- lock.writeLock().unlock();
- }
- }
-
- @Override
- protected void finalize() {
- if (filter != null) {
- force();
- }
- filter = null;
- forkedFilter = null;
- }
-
- @Override
- public int getK() {
- return k;
- }
-
-
- @Override
- public boolean needRebuild() {
- boolean _needRebuild = needRebuild;
- needRebuild = false;
- return _needRebuild;
- }
}
Modified: branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
===================================================================
--- branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
2008-07-28 14:27:21 UTC (rev 21447)
+++ branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
2008-07-28 15:02:32 UTC (rev 21448)
@@ -1,7 +1,140 @@
package freenet.support;
+import java.nio.ByteBuffer;
+import java.nio.MappedByteBuffer;
+import java.security.MessageDigest;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+
+import freenet.crypt.SHA256;
+
public abstract class BloomFilter {
+ protected ByteBuffer filter;
+
+ /** Number of hash functions */
+ protected final int k;
+ protected final int length;
+
+ protected ReadWriteLock lock = new ReentrantReadWriteLock();
+
+ protected BloomFilter(int length, int k) {
+ if (length % 8 != 0)
+ throw new IllegalArgumentException();
+
+ this.length = length;
+ this.k = k;
+ }
+
+ //-- Core
+ public void addKey(byte[] key) {
+ int[] hashes = getHashes(key);
+ lock.writeLock().lock();
+ try {
+ for (int i = 0; i < hashes.length; i++)
+ setBit(hashes[i]);
+ } finally {
+ lock.writeLock().unlock();
+ }
+
+ if (forkedFilter != null)
+ forkedFilter.addKey(key);
+ }
+
+ public boolean checkFilter(byte[] key) {
+ int[] hashes = getHashes(key);
+ lock.readLock().lock();
+ try {
+ for (int i = 0; i < hashes.length; i++)
+ if (!getBit(hashes[i]))
+ return false;
+ } finally {
+ lock.readLock().unlock();
+ }
+ return true;
+ }
+
+ public void removeKey(byte[] key) {
+ int[] hashes = getHashes(key);
+ lock.writeLock().lock();
+ try {
+ for (int i = 0; i < hashes.length; i++)
+ unsetBit(hashes[i]);
+ } finally {
+ lock.writeLock().unlock();
+ }
+
+ if (forkedFilter != null)
+ forkedFilter.addKey(key);
+ }
+
+ //-- Bits and Hashes
+ protected abstract boolean getBit(int offset);
+
+ protected abstract void setBit(int offset);
+
+ protected abstract void unsetBit(int offset);
+
+ protected int[] getHashes(byte[] key) {
+ int[] hashes = new int[k];
+
+ MessageDigest md = SHA256.getMessageDigest();
+ try {
+ byte[] lastDigest = key;
+ ByteBuffer bf = ByteBuffer.wrap(lastDigest);
+
+ for (int i = 0; i < k; i++) {
+ if (bf.remaining() < 4) {
+ lastDigest = md.digest(lastDigest);
+ bf = ByteBuffer.wrap(lastDigest);
+ }
+
+ hashes[i] = (int) ((bf.getInt() &
Long.MAX_VALUE) % length);
+ }
+ } finally {
+ SHA256.returnMessageDigest(md);
+ }
+
+ return hashes;
+ }
+
+ //-- Fork & Merge
+ protected BloomFilter forkedFilter;
+
/**
+ * Create an empty, in-memory copy of bloom filter. New updates are
written to both filters.
+ * This is written back to disk on #merge()
+ */
+ public abstract void fork(int k);
+
+ public void merge() {
+ lock.writeLock().lock();
+ try {
+ if (forkedFilter == null)
+ return;
+
+ filter.position(0);
+ forkedFilter.filter.position(0);
+
+ filter.put(forkedFilter.filter);
+
+ filter.position(0);
+ forkedFilter = null;
+ } finally {
+ lock.writeLock().unlock();
+ }
+ }
+
+ public void discard() {
+ lock.writeLock().lock();
+ try {
+ forkedFilter = null;
+ } finally {
+ lock.writeLock().unlock();
+ }
+ }
+
+ //-- Misc.
+ /**
* Calculate optimal K value
*
* @param filterLength
@@ -20,26 +153,31 @@
return (int) k;
}
- public abstract void addKey(byte[] key);
+ public int getK() {
+ return k;
+ }
- public abstract void removeKey(byte[] key);
+ protected boolean needRebuild;
- public abstract boolean checkFilter(byte[] key);
+ public boolean needRebuild() {
+ boolean _needRebuild = needRebuild;
+ needRebuild = false;
+ return _needRebuild;
- public abstract void force();
+ }
- /**
- * Create an empty, in-memory copy of bloom filter. New updates are
written to both filters.
- * This is written back to disk on #merge()
- */
- public abstract void fork(int k);
+ public void force() {
+ if (filter instanceof MappedByteBuffer) {
+ ((MappedByteBuffer) filter).force();
+ }
+ }
- public abstract void discard();
-
- public abstract void merge();
-
- public abstract int getK();
-
- public abstract boolean needRebuild();
-
+ @Override
+ protected void finalize() {
+ if (filter != null) {
+ force();
+ }
+ filter = null;
+ forkedFilter = null;
+ }
}
\ No newline at end of file
