You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@labs.apache.org by ka...@apache.org on 2009/03/13 07:20:22 UTC
svn commit: r753136 - in /labs/bananadb/trunk: ./
src/main/java/org/apache/labs/bananadb/hashtable/
src/main/java/org/apache/labs/bananadb/hashtable/handlers/
src/test/java/org/apache/labs/bananadb/hashtable/
Author: kalle
Date: Fri Mar 13 06:20:21 2009
New Revision: 753136
URL: http://svn.apache.org/viewvc?rev=753136&view=rev
Log:
BananDB
Hashtable#containsKey
null value tests
tests refactor
name refactor
Added:
labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/ValueClassHandler.java
- copied, changed from r752987, labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/EntityClassHandler.java
Removed:
labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/EntityClassHandler.java
Modified:
labs/bananadb/trunk/FILES.txt
labs/bananadb/trunk/TODO.txt
labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java
labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/HashtableAccessor.java
labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/KeyClassHandler.java
labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/handlers/StringValueHandler.java
labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/Benchmark.java
labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestHashtable.java
Modified: labs/bananadb/trunk/FILES.txt
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/FILES.txt?rev=753136&r1=753135&r2=753136&view=diff
==============================================================================
--- labs/bananadb/trunk/FILES.txt (original)
+++ labs/bananadb/trunk/FILES.txt Fri Mar 13 06:20:21 2009
@@ -13,9 +13,9 @@
}}}
-== entities ==
+== key postings ==
-Hashtable key entity list, the serialized K part of the Hashtable<K, V>.
+Hashtable key postings list, the serialized K part of the Hashtable<K, V>.
If keys share the same hash code,
or if the capacity is not great enough for keys to get a unique posting the the hashtable
entities will be added to a list that must be iterated in order to find the correct posting.
Modified: labs/bananadb/trunk/TODO.txt
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/TODO.txt?rev=753136&r1=753135&r2=753136&view=diff
==============================================================================
--- labs/bananadb/trunk/TODO.txt (original)
+++ labs/bananadb/trunk/TODO.txt Fri Mar 13 06:20:21 2009
@@ -15,3 +15,7 @@
= Transactions =
= Annotation API =
+
+== Serialization handler annotations ==
+
+
Modified: labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java?rev=753136&r1=753135&r2=753136&view=diff
==============================================================================
--- labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java (original)
+++ labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/Hashtable.java Fri Mar 13 06:20:21 2009
@@ -44,40 +44,40 @@
/**
* the header contains meta data such as number of records, et c. todo factor out to new meta data file
*/
- private static final int ENTRIES_HEADER_BYTE_SIZE = 1024;
+ private static final int KEY_POSTINGS_HEADER_BYTE_SIZE = 1024;
private File path;
private List<Partition> partitions = new ArrayList<Partition>();
private File hashtableFile;
- private File entriesFile;
-
-// private Class<K> keyClass;
-// private Class<V> valueClass;
+ private File keyPostingsFile;
+ private static final String hashtableFileName = "hashtable";
+ private static final String keyPostingsFileName = "keys";
+ private static final String valuePostingsFileName = "values";
private static final int megaByte = 1024 * 1024;
private static final int partitionSize = 100 * megaByte;
private KeyClassHandler<K> keyClassHandler;
- /** size of an entity in the entity file */
- private int entityByteSize;
+ /** size of a key posting in the key postings file */
+ private int keyPostingByteSize;
- private EntityClassHandler<V> valueClassHandler;
+ private ValueClassHandler<V> valueClassHandler;
- private int hashtableSize;
+ private int capacity;
private int entityCount;
- private int nextEntityOffset;
+ private int nextKeyPostingOffset;
- private void setNextEntityOffset(int nextEntityOffset) {
- this.nextEntityOffset = nextEntityOffset;
+ private void setNextKeyPostingOffset(int nextKeyPostingOffset) {
+ this.nextKeyPostingOffset = nextKeyPostingOffset;
}
- private int getNextEntityOffset() {
- return nextEntityOffset;
+ private int getNextKeyPostingOffset() {
+ return nextKeyPostingOffset;
}
// // todo factor out RAF to new reader (transaction) class.
@@ -114,12 +114,12 @@
* @param valueClassHandler
* @throws IOException
*/
- public Hashtable(File path, int capacity, KeyClassHandler<K> keyClassHandler, EntityClassHandler<V> valueClassHandler) throws IOException {
+ public Hashtable(File path, int capacity, KeyClassHandler<K> keyClassHandler, ValueClassHandler<V> valueClassHandler) throws IOException {
this.keyClassHandler = keyClassHandler;
this.valueClassHandler = valueClassHandler;
- entityByteSize = 4 + 4 + 4 + 4 + 4 + keyClassHandler.getByteSize();
+ keyPostingByteSize = 4 + 4 + 4 + 4 + 4 + keyClassHandler.getByteSize();
this.path = path;
if (!path.exists()) {
@@ -127,44 +127,46 @@
path.mkdirs();
}
- hashtableFile = new File(path, "hashtable");
- entriesFile = new File(path, "entries");
+ hashtableFile = new File(path, hashtableFileName);
+ this.keyPostingsFile = new File(path, keyPostingsFileName);
// open
- File hashtableFile = new File(path, "hashtable");
+ File hashtableFile = new File(path, hashtableFileName);
if (!hashtableFile.exists()) {
format(hashtableFile, capacity * HASHTABLE_RECORD_BYTE_SIZE);
+ } else {
+ capacity = (int) (hashtableFile.length() / HASHTABLE_RECORD_BYTE_SIZE);
}
+ this.capacity = capacity;
- hashtableSize = (int) (hashtableFile.length() / HASHTABLE_RECORD_BYTE_SIZE);
- File entriesFile = new File(path, "entries");
- if (!entriesFile.exists()) {
+ File keyPostingsFile = new File(path, keyPostingsFileName);
+ if (!keyPostingsFile.exists()) {
- log.info("Creating a new entries file");
+ log.info("Creating a new key postings file");
- format(entriesFile, ENTRIES_HEADER_BYTE_SIZE + (capacity * entityByteSize));
- setNextEntityOffset(ENTRIES_HEADER_BYTE_SIZE);
+ format(keyPostingsFile, KEY_POSTINGS_HEADER_BYTE_SIZE + (capacity * keyPostingByteSize));
+ setNextKeyPostingOffset(KEY_POSTINGS_HEADER_BYTE_SIZE);
- RandomAccessFile entriesRAF = new RandomAccessFile(entriesFile, "rw");
- entriesRAF.seek(0);
- entriesRAF.writeInt(getNextEntityOffset());
- entriesRAF.close();
+ RandomAccessFile keyPostingsRAF = new RandomAccessFile(keyPostingsFile, "rw");
+ keyPostingsRAF.seek(0);
+ keyPostingsRAF.writeInt(getNextKeyPostingOffset());
+ keyPostingsRAF.close();
} else {
- RandomAccessFile entriesRAF = new RandomAccessFile(entriesFile, "r");
- entriesRAF.seek(0);
- setNextEntityOffset(entriesRAF.readInt());
- entityCount = entriesRAF.readInt();
- entriesRAF.close();
+ RandomAccessFile keyPostingsRAF = new RandomAccessFile(keyPostingsFile, "r");
+ keyPostingsRAF.seek(0);
+ setNextKeyPostingOffset(keyPostingsRAF.readInt());
+ entityCount = keyPostingsRAF.readInt();
+ keyPostingsRAF.close();
}
File[] valueFiles = path.listFiles(new FileFilter() {
public boolean accept(File file) {
- return file.isFile() && file.getName().matches("data\\.[0-9]+");
+ return file.isFile() && file.getName().matches(valuePostingsFileName+"\\.[0-9]+");
}
});
Arrays.sort(valueFiles, new Comparator<File>() {
@@ -177,7 +179,7 @@
if (valueFiles.length > 0) {
for (int i = 0; i < valueFiles.length; i++) {
if (!valueFiles[i].getName().endsWith("." + i)) {
- throw new FileNotFoundException("Expected partition data." + i + " but found " + valueFiles[i].getName());
+ throw new FileNotFoundException("Expected partition "+valuePostingsFileName+"." + i + " but found " + valueFiles[i].getName());
}
Partition partition = new Partition(i);
partition.open();
@@ -221,7 +223,7 @@
V oldValue = null;
int keyHash = key.hashCode();
- int index = keyHash & (hashtableSize - 1);
+ int index = keyHash & (capacity - 1);
byte[] hashtableRecordBuf = new byte[HASHTABLE_RECORD_BYTE_SIZE];
accessor.getHashtableRAF().seek(index * HASHTABLE_RECORD_BYTE_SIZE);
accessor.getHashtableRAF().read(hashtableRecordBuf);
@@ -230,18 +232,18 @@
if (in.readByte() == 0) {
// create inital posting for hash
- int entityOffset = getNextEntityOffset();
- setNextEntityOffset(getNextEntityOffset() + entityByteSize);
- accessor.getEntitiesRAF().seek(0);
- accessor.getEntitiesRAF().writeInt(getNextEntityOffset());
- accessor.getEntitiesRAF().writeInt(++entityCount);
+ int keyPostingOffset = getNextKeyPostingOffset();
+ setNextKeyPostingOffset(getNextKeyPostingOffset() + keyPostingByteSize);
+ accessor.getKeyPostingsRAF().seek(0);
+ accessor.getKeyPostingsRAF().writeInt(getNextKeyPostingOffset());
+ accessor.getKeyPostingsRAF().writeInt(++entityCount);
- accessor.getEntitiesRAF().seek(entityOffset);
- writeEntity(accessor, -1, keyBuf, valueBuf, keyHash);
+ accessor.getKeyPostingsRAF().seek(keyPostingOffset);
+ writePostings(accessor, -1, keyBuf, valueBuf, keyHash);
accessor.getHashtableRAF().seek(index * HASHTABLE_RECORD_BYTE_SIZE);
accessor.getHashtableRAF().writeByte(1);
- accessor.getHashtableRAF().writeInt(entityOffset);
+ accessor.getHashtableRAF().writeInt(keyPostingOffset);
return null;
@@ -249,24 +251,24 @@
// already contains a posting for the hash
- int firstEntityOffset = in.readInt();
+ int firstKeyPostingOffset = in.readInt();
K compareKey;
- int previousEntityOffset = -1;
- int nextEntityOffset = firstEntityOffset;
- while (nextEntityOffset != -1) {
- int entityOffset = nextEntityOffset;
-
- accessor.getEntitiesRAF().seek(entityOffset);
-
- nextEntityOffset = accessor.getEntitiesRAF().readInt();
- int partitionNumber = accessor.getEntitiesRAF().readInt();
- int partitionOffset = accessor.getEntitiesRAF().readInt();
- int keySize = accessor.getEntitiesRAF().readInt();
+ int previousKeyPostingOffset = -1;
+ int nextKeyPostingOffset = firstKeyPostingOffset;
+ while (nextKeyPostingOffset != -1) {
+ int keyPostingOffset = nextKeyPostingOffset;
+
+ accessor.getKeyPostingsRAF().seek(keyPostingOffset);
+
+ nextKeyPostingOffset = accessor.getKeyPostingsRAF().readInt();
+ int partitionNumber = accessor.getKeyPostingsRAF().readInt();
+ int partitionOffset = accessor.getKeyPostingsRAF().readInt();
+ int keySize = accessor.getKeyPostingsRAF().readInt();
if (keySize > 0) {
byte[] compareKeyBuf = new byte[keySize];
- accessor.getEntitiesRAF().read(compareKeyBuf);
+ accessor.getKeyPostingsRAF().read(compareKeyBuf);
compareKey = keyClassHandler.read(new DataInputStream(new ByteArrayInputStream(compareKeyBuf)));
if (key.equals(compareKey)) {
@@ -277,40 +279,40 @@
oldValue = partition.read(accessor, partitionOffset);
}
- // over write old entity posting
- accessor.getEntitiesRAF().seek(entityOffset);
- writeEntity(accessor, nextEntityOffset, keyBuf, valueBuf, keyHash);
+ // over write old key posting
+ accessor.getKeyPostingsRAF().seek(keyPostingOffset);
+ writePostings(accessor, nextKeyPostingOffset, keyBuf, valueBuf, keyHash);
return oldValue;
}
}
- previousEntityOffset = entityOffset;
+ previousKeyPostingOffset = keyPostingOffset;
}
// this key instance did not exist in entries
// although it shares hash with some other keys in there.
- // create new entity and point at it from the previous entity
- int entityOffset = getNextEntityOffset();
- setNextEntityOffset(getNextEntityOffset() + entityByteSize);
+ // create new key posting and point at it from the previous key posting
+ int KeyPostingOffset = getNextKeyPostingOffset();
+ setNextKeyPostingOffset(getNextKeyPostingOffset() + keyPostingByteSize);
- accessor.getEntitiesRAF().seek(entityOffset);
- writeEntity(accessor, -1, keyBuf, valueBuf, keyHash);
+ accessor.getKeyPostingsRAF().seek(KeyPostingOffset);
+ writePostings(accessor, -1, keyBuf, valueBuf, keyHash);
- accessor.getEntitiesRAF().seek(previousEntityOffset);
- accessor.getEntitiesRAF().writeInt(entityOffset);
+ accessor.getKeyPostingsRAF().seek(previousKeyPostingOffset);
+ accessor.getKeyPostingsRAF().writeInt(KeyPostingOffset);
- accessor.getEntitiesRAF().seek(4);
- accessor.getEntitiesRAF().writeInt(++entityCount);
+ accessor.getKeyPostingsRAF().seek(4);
+ accessor.getKeyPostingsRAF().writeInt(++entityCount);
return null;
}
}
- private synchronized void writeEntity(HashtableAccessor accessor, int nextEntity, byte[] keyBuf, byte[] valueBuf, int keyHashCode) throws IOException {
+ private synchronized void writePostings(HashtableAccessor accessor, int nextKeyPostingOffset, byte[] keyBuf, byte[] valueBuf, int keyHashCode) throws IOException {
int partitionNumber = -1;
long offset = -1;
@@ -330,34 +332,89 @@
offset = partition.append(accessor, valueBuf);
}
- // int offset position in this file to the next entity with the same hash, -1 = null
- accessor.getEntitiesRAF().writeInt(nextEntity);
+ // int offset position in this file to the next key posting with the same hash, -1 = null
+ accessor.getKeyPostingsRAF().writeInt(nextKeyPostingOffset);
// int value partition number, -1 == null
- accessor.getEntitiesRAF().writeInt(partitionNumber);
+ accessor.getKeyPostingsRAF().writeInt(partitionNumber);
// int offset position in value partition, -1 == null
- accessor.getEntitiesRAF().writeInt((int) offset);
+ accessor.getKeyPostingsRAF().writeInt((int) offset);
// int key length in bytes, 0 = null
if (keyBuf == null || keyBuf.length == 0) {
- accessor.getEntitiesRAF().writeInt(0);
+ accessor.getKeyPostingsRAF().writeInt(0);
} else {
- accessor.getEntitiesRAF().writeInt(keyBuf.length);
+ accessor.getKeyPostingsRAF().writeInt(keyBuf.length);
// key writable key
- accessor.getEntitiesRAF().write(keyBuf);
+ accessor.getKeyPostingsRAF().write(keyBuf);
// key hash
- accessor.getEntitiesRAF().write(keyHashCode);
+ accessor.getKeyPostingsRAF().write(keyHashCode);
+ }
+
+ }
+
+ /**
+ *
+ * @param accessor
+ * @param key
+ * @return true if hashtable contains a posting for the given key.
+ * @throws IOException
+ */
+ public boolean containsKey(HashtableAccessor accessor, K key) throws IOException {
+ int keyHash = key.hashCode();
+ int index = keyHash & (capacity - 1);
+ byte[] hashtableRecordBuf = new byte[HASHTABLE_RECORD_BYTE_SIZE];
+ accessor.getHashtableRAF().seek(index * HASHTABLE_RECORD_BYTE_SIZE);
+ accessor.getHashtableRAF().read(hashtableRecordBuf);
+ DataInput in = new DataInputStream(new ByteArrayInputStream(hashtableRecordBuf));
+ byte isnull = in.readByte();
+ if (isnull == 0) {
+ return false;
+ }
+
+ int firstKeyPostingOffset = in.readInt();
+
+ K compareKey;
+
+ // there was some thought behind this attribute but I cant seem to recall what..
+ int previousKeyPostingOffset = -1;
+
+ int nextKeyPostingOffset = firstKeyPostingOffset;
+ while (nextKeyPostingOffset != -1) {
+ int keyPostingOffset = nextKeyPostingOffset;
+
+ accessor.getKeyPostingsRAF().seek(keyPostingOffset);
+ previousKeyPostingOffset = keyPostingOffset;
+
+ nextKeyPostingOffset = accessor.getKeyPostingsRAF().readInt();
+ int partitionNumber = accessor.getKeyPostingsRAF().readInt();
+
+// if (partitionNumber == -1) {
+// return false;
+// }
+ int partitionOffset = accessor.getKeyPostingsRAF().readInt();
+
+ int keySize = accessor.getKeyPostingsRAF().readInt();
+ if (keySize > 0) {
+ byte[] compareKeyBuf = new byte[keySize];
+ accessor.getKeyPostingsRAF().read(compareKeyBuf);
+ compareKey = keyClassHandler.read(new DataInputStream(new ByteArrayInputStream(compareKeyBuf)));
+ if (key.equals(compareKey)) {
+ return true;
+ }
+ }
}
+ return false;
}
public V get(HashtableAccessor accessor, K key) throws IOException {
int keyHash = key.hashCode();
- int index = keyHash & (hashtableSize - 1);
+ int index = keyHash & (capacity - 1);
byte[] hashtableRecordBuf = new byte[HASHTABLE_RECORD_BYTE_SIZE];
accessor.getHashtableRAF().seek(index * HASHTABLE_RECORD_BYTE_SIZE);
accessor.getHashtableRAF().read(hashtableRecordBuf);
@@ -367,32 +424,32 @@
return null;
}
- int firstEntityOffset = in.readInt();
+ int firstKeyPostingOffset = in.readInt();
K compareKey;
// there was some thought behind this attribute but I cant seem to recall what..
- int previousEntityOffset = -1;
+ int previousKeyPostingOffset = -1;
- int nextEntityOffset = firstEntityOffset;
- while (nextEntityOffset != -1) {
- int entityOffset = nextEntityOffset;
+ int nextKeyPostingOffset = firstKeyPostingOffset;
+ while (nextKeyPostingOffset != -1) {
+ int keyPostingOffset = nextKeyPostingOffset;
- accessor.getEntitiesRAF().seek(entityOffset);
- previousEntityOffset = entityOffset;
+ accessor.getKeyPostingsRAF().seek(keyPostingOffset);
+ previousKeyPostingOffset = keyPostingOffset;
- nextEntityOffset = accessor.getEntitiesRAF().readInt();
- int partitionNumber = accessor.getEntitiesRAF().readInt();
+ nextKeyPostingOffset = accessor.getKeyPostingsRAF().readInt();
+ int partitionNumber = accessor.getKeyPostingsRAF().readInt();
if (partitionNumber == -1) {
return null;
}
- int partitionOffset = accessor.getEntitiesRAF().readInt();
- int keySize = accessor.getEntitiesRAF().readInt();
+ int partitionOffset = accessor.getKeyPostingsRAF().readInt();
+ int keySize = accessor.getKeyPostingsRAF().readInt();
if (keySize > 0) {
byte[] compareKeyBuf = new byte[keySize];
- accessor.getEntitiesRAF().read(compareKeyBuf);
+ accessor.getKeyPostingsRAF().read(compareKeyBuf);
compareKey = keyClassHandler.read(new DataInputStream(new ByteArrayInputStream(compareKeyBuf)));
if (key.equals(compareKey)) {
@@ -417,7 +474,7 @@
int keyHash = key.hashCode();
- int index = keyHash & (hashtableSize - 1);
+ int index = keyHash & (capacity - 1);
byte[] hashtableRecordBuf = new byte[HASHTABLE_RECORD_BYTE_SIZE];
accessor.getHashtableRAF().seek(index * HASHTABLE_RECORD_BYTE_SIZE);
accessor.getHashtableRAF().read(hashtableRecordBuf);
@@ -425,24 +482,24 @@
byte isnull = in.readByte();
- int firstEntityOffset = in.readInt();
+ int firstKeyPostingOffset = in.readInt();
K compareKey;
- int previousEntityOffset = -1;
- int nextEntityOffset = firstEntityOffset;
- while (nextEntityOffset != -1) {
- int entityOffset = nextEntityOffset;
-
- accessor.getEntitiesRAF().seek(entityOffset);
-
- nextEntityOffset = accessor.getEntitiesRAF().readInt();
- int partitionNumber = accessor.getEntitiesRAF().readInt();
- int partitionOffset = accessor.getEntitiesRAF().readInt();
- int keySize = accessor.getEntitiesRAF().readInt();
+ int previousKeyPostingOffset = -1;
+ int nextKeyPostingOffset = firstKeyPostingOffset;
+ while (nextKeyPostingOffset != -1) {
+ int keyPostingOffset = nextKeyPostingOffset;
+
+ accessor.getKeyPostingsRAF().seek(keyPostingOffset);
+
+ nextKeyPostingOffset = accessor.getKeyPostingsRAF().readInt();
+ int partitionNumber = accessor.getKeyPostingsRAF().readInt();
+ int partitionOffset = accessor.getKeyPostingsRAF().readInt();
+ int keySize = accessor.getKeyPostingsRAF().readInt();
if (keySize > 0) {
byte[] compareKeyBuf = new byte[keySize];
- accessor.getEntitiesRAF().read(compareKeyBuf);
+ accessor.getKeyPostingsRAF().read(compareKeyBuf);
compareKey = keyClassHandler.read(new DataInputStream(new ByteArrayInputStream(compareKeyBuf)));
if (key.equals(compareKey)) {
@@ -455,24 +512,24 @@
oldValue = partition.read(accessor, partitionOffset);
}
- if (previousEntityOffset != -1) {
- // update offset in previous entity to point at next offset in removed entity
- accessor.getEntitiesRAF().seek(previousEntityOffset);
- accessor.getEntitiesRAF().writeInt(nextEntityOffset);
+ if (previousKeyPostingOffset != -1) {
+ // update offset in previous key posting to point at next offset in removed key posting
+ accessor.getKeyPostingsRAF().seek(previousKeyPostingOffset);
+ accessor.getKeyPostingsRAF().writeInt(nextKeyPostingOffset);
} else {
// remove posting in hashtable
accessor.getHashtableRAF().seek(index * HASHTABLE_RECORD_BYTE_SIZE);
accessor.getHashtableRAF().writeByte(0);
}
- accessor.getEntitiesRAF().seek(4);
- accessor.getEntitiesRAF().writeInt(--entityCount);
+ accessor.getKeyPostingsRAF().seek(4);
+ accessor.getKeyPostingsRAF().writeInt(--entityCount);
return oldValue;
}
}
- previousEntityOffset = entityOffset;
+ previousKeyPostingOffset = keyPostingOffset;
}
@@ -481,7 +538,7 @@
/**
- * Represents an entity value data partition file.
+ * Represents an hashtable value data partition file.
*/
public class Partition {
@@ -497,7 +554,7 @@
private Partition(int partitionNumber) {
this.partitionNumber = partitionNumber;
- file = new File(path, "data." + partitionNumber);
+ file = new File(path, valuePostingsFileName + "." + partitionNumber);
while (partitions.size() < partitionNumber) {
log.warn("Adding a null partition");
partitions.add(null);
@@ -681,7 +738,7 @@
* A Cursor iterates the entities in a Hashtable.
*
* It is NOT thread safe! I.e. you can not use multiple threads to iterate the
- * same cursor at the same time.
+ * same cursor at the same time. TODO: fix that. Multiple solutions available.
*
* The entities are returned close to the order of the hash code, but not always.
* The greater the capacity of a hashtable the more precise the order.
@@ -700,7 +757,7 @@
}
private long hashtableCursor = 0;
- private long entityCursor = -1;
+ private long keyPostingsCursor = -1;
private K key;
private V value;
@@ -711,22 +768,22 @@
* @throws IOException
*/
public boolean next() throws IOException {
- if (entityCursor != -1) {
- accessor.getEntitiesRAF().seek(entityCursor);
- entityCursor = accessor.getEntitiesRAF().readInt(); // next entity
- if (entityCursor != -1) {
- accessor.getEntitiesRAF().seek(entityCursor + 4);
+ if (keyPostingsCursor != -1) {
+ accessor.getKeyPostingsRAF().seek(keyPostingsCursor);
+ keyPostingsCursor = accessor.getKeyPostingsRAF().readInt(); // next entity
+ if (keyPostingsCursor != -1) {
+ accessor.getKeyPostingsRAF().seek(keyPostingsCursor + 4);
set();
return true;
}
}
- while (hashtableCursor < (hashtableSize * HASHTABLE_RECORD_BYTE_SIZE)) {
+ while (hashtableCursor < (capacity * HASHTABLE_RECORD_BYTE_SIZE)) {
accessor.getHashtableRAF().seek(hashtableCursor);
hashtableCursor += HASHTABLE_RECORD_BYTE_SIZE;
byte isnull = accessor.getHashtableRAF().readByte();
if (isnull != 0) {
- entityCursor = accessor.getHashtableRAF().readInt();
- accessor.getEntitiesRAF().seek(entityCursor + 4);
+ keyPostingsCursor = accessor.getHashtableRAF().readInt();
+ accessor.getKeyPostingsRAF().seek(keyPostingsCursor + 4);
set();
return true;
@@ -737,10 +794,10 @@
}
private void set() throws IOException {
- int partitionNumber = accessor.getEntitiesRAF().readInt();
- int partitionOffset = accessor.getEntitiesRAF().readInt();
- byte[] keyBuf = new byte[accessor.getEntitiesRAF().readInt()];
- accessor.getEntitiesRAF().read(keyBuf);
+ int partitionNumber = accessor.getKeyPostingsRAF().readInt();
+ int partitionOffset = accessor.getKeyPostingsRAF().readInt();
+ byte[] keyBuf = new byte[accessor.getKeyPostingsRAF().readInt()];
+ accessor.getKeyPostingsRAF().read(keyBuf);
K key;
key = keyClassHandler.read(new DataInputStream(new ByteArrayInputStream(keyBuf)));
this.key = key;
@@ -751,12 +808,12 @@
}
public K key() {
- // todo lazy load key
+ // todo lazy load key?
return key;
}
public V value() {
- // todo lazy load value
+ // todo lazy load value?
return value;
}
}
@@ -769,7 +826,7 @@
return keyClassHandler;
}
- public EntityClassHandler<V> getValueClassHandler() {
+ public ValueClassHandler<V> getValueClassHandler() {
return valueClassHandler;
}
@@ -781,8 +838,8 @@
return hashtableFile;
}
- public File getEntriesFile() {
- return entriesFile;
+ public File getKeyPostingsFile() {
+ return keyPostingsFile;
}
List<Partition> getPartitions() {
Modified: labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/HashtableAccessor.java
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/HashtableAccessor.java?rev=753136&r1=753135&r2=753136&view=diff
==============================================================================
--- labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/HashtableAccessor.java (original)
+++ labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/HashtableAccessor.java Fri Mar 13 06:20:21 2009
@@ -24,24 +24,31 @@
import java.util.HashMap;
/**
- * User: kalle
- * Date: 2009-jan-03
- * Time: 04:37:42
+ * RandomAccessFile placeholder for accessing hashtable files.
+ *
+ * Allows for multiple threads to read and write the hashtable files at the same time.
*/
public class HashtableAccessor {
private String access;
private RandomAccessFile hashtableRAF;
- private RandomAccessFile entitiesRAF;
+ private RandomAccessFile keyPostingsRAF;
private Map<Hashtable.Partition, RandomAccessFile> partitionRAFs = new HashMap<Hashtable.Partition, RandomAccessFile>();
- public HashtableAccessor(Hashtable<?, ?> hashtable, boolean readOnly) throws IOException {
+ /**
+ * @see org.apache.labs.bananadb.hashtable.Hashtable#createAccessor(boolean)
+ *
+ * @param hashtable
+ * @param readOnly
+ * @throws IOException
+ */
+ HashtableAccessor(Hashtable<?, ?> hashtable, boolean readOnly) throws IOException {
// todo open hashtableRAF, entriesRAF and all partitionRAFs
access = readOnly ? "r" : "rw";
hashtableRAF = new RandomAccessFile(hashtable.getHashtableFile(), access);
- entitiesRAF = new RandomAccessFile(hashtable.getEntriesFile(), access);
+ keyPostingsRAF = new RandomAccessFile(hashtable.getKeyPostingsFile(), access);
for (Hashtable.Partition partition : hashtable.getPartitions()) {
registerPartition(partition);
@@ -56,8 +63,8 @@
return hashtableRAF;
}
- RandomAccessFile getEntitiesRAF() {
- return entitiesRAF;
+ RandomAccessFile getKeyPostingsRAF() {
+ return keyPostingsRAF;
}
RandomAccessFile getPartitionRAF(Hashtable.Partition partition) {
@@ -72,9 +79,10 @@
public void close() throws IOException {
getHashtableRAF().close();
- getEntitiesRAF().close();
+ getKeyPostingsRAF().close();
for (RandomAccessFile partitionRAF : partitionRAFs.values()) {
partitionRAF.close();
}
}
+
}
Modified: labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/KeyClassHandler.java
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/KeyClassHandler.java?rev=753136&r1=753135&r2=753136&view=diff
==============================================================================
--- labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/KeyClassHandler.java (original)
+++ labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/KeyClassHandler.java Fri Mar 13 06:20:21 2009
@@ -19,13 +19,13 @@
/**
- * User: kalle
- * Date: 2009-jan-03
- * Time: 04:18:04
+ * Serialization interface for keys in the hashtable,
+ * producing a serialized value of static length
+ * for fast seeking in the key postings file.
*/
-public interface KeyClassHandler<C> extends EntityClassHandler<C> {
+public interface KeyClassHandler<C> extends ValueClassHandler<C> {
/** A primary key needs to be of a static size for fast seeking in the hash table */
- public int getByteSize();
+ public abstract int getByteSize();
}
Copied: labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/ValueClassHandler.java (from r752987, labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/EntityClassHandler.java)
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/ValueClassHandler.java?p2=labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/ValueClassHandler.java&p1=labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/EntityClassHandler.java&r1=752987&r2=753136&rev=753136&view=diff
==============================================================================
--- labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/EntityClassHandler.java (original)
+++ labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/ValueClassHandler.java Fri Mar 13 06:20:21 2009
@@ -21,11 +21,9 @@
import java.io.*;
/**
- * User: kalle
- * Date: 2009-jan-03
- * Time: 04:13:29
+ * Serialization interface for values in the hashtable.
*/
-public interface EntityClassHandler<C> {
+public interface ValueClassHandler<C> {
public abstract Class<C> getEntityClass();
public abstract void write(C entity, DataOutputStream out) throws IOException;
Modified: labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/handlers/StringValueHandler.java
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/handlers/StringValueHandler.java?rev=753136&r1=753135&r2=753136&view=diff
==============================================================================
--- labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/handlers/StringValueHandler.java (original)
+++ labs/bananadb/trunk/src/main/java/org/apache/labs/bananadb/hashtable/handlers/StringValueHandler.java Fri Mar 13 06:20:21 2009
@@ -17,7 +17,7 @@
* limitations under the License.
*/
-import org.apache.labs.bananadb.hashtable.EntityClassHandler;
+import org.apache.labs.bananadb.hashtable.ValueClassHandler;
import java.io.DataOutputStream;
import java.io.IOException;
@@ -28,7 +28,7 @@
* Date: 2009-jan-03
* Time: 05:52:33
*/
-public class StringValueHandler implements EntityClassHandler<String> {
+public class StringValueHandler implements ValueClassHandler<String> {
public Class<String> getEntityClass() {
return String.class;
Modified: labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/Benchmark.java
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/Benchmark.java?rev=753136&r1=753135&r2=753136&view=diff
==============================================================================
--- labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/Benchmark.java (original)
+++ labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/Benchmark.java Fri Mar 13 06:20:21 2009
@@ -1,12 +1,9 @@
package org.apache.labs.bananadb.hashtable;
-import junit.framework.TestCase;
-
import java.io.IOException;
import java.io.File;
import java.util.*;
-import org.junit.Test;
import org.apache.labs.bananadb.hashtable.handlers.IntegerHandler;
import org.apache.labs.bananadb.hashtable.handlers.StringValueHandler;
@@ -19,7 +16,7 @@
private Hashtable hashtable;
private int capacity;
private KeyClassHandler keyClassHandler;
- private EntityClassHandler entityClassHandler;
+ private ValueClassHandler valueClassHandler;
public static void main(String[] args) throws Exception {
@@ -52,8 +49,8 @@
csv.append(String.valueOf(items));
keyClassHandler = new IntegerHandler();
- entityClassHandler = new StringValueHandler();
- hashtable = new Hashtable(new File("target/benchmark/" + System.currentTimeMillis()), capacity, keyClassHandler, entityClassHandler);
+ valueClassHandler = new StringValueHandler();
+ hashtable = new Hashtable(new File("target/benchmark/" + System.currentTimeMillis()), capacity, keyClassHandler, valueClassHandler);
List<Integer> keys = new ArrayList<Integer>(items);
Modified: labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestHashtable.java
URL: http://svn.apache.org/viewvc/labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestHashtable.java?rev=753136&r1=753135&r2=753136&view=diff
==============================================================================
--- labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestHashtable.java (original)
+++ labs/bananadb/trunk/src/test/java/org/apache/labs/bananadb/hashtable/TestHashtable.java Fri Mar 13 06:20:21 2009
@@ -20,8 +20,10 @@
import junit.framework.TestCase;
import org.apache.labs.bananadb.hashtable.handlers.IntegerHandler;
import org.apache.labs.bananadb.hashtable.handlers.StringValueHandler;
+import org.junit.Test;
import java.io.File;
+import java.io.IOException;
/**
* User: kalle
@@ -30,14 +32,41 @@
*/
public class TestHashtable extends TestCase {
- public void test() throws Exception {
+ private File path;
- File path = new File("target/" + Hashtable.class.getSimpleName() + "/" + System.currentTimeMillis());
- path.mkdirs();
+ public TestHashtable() {
+ path = new File("target/" + Hashtable.class.getSimpleName() + "/" + System.currentTimeMillis());
+ if (!path.exists() && !path.mkdirs()) {
+ throw new RuntimeException("Could not create path " + path);
+ }
+ }
+
+ @Test
+ public void testNull() throws Exception {
+
+ File path = new File(this.path, "testNull");
+
+ Hashtable<Integer, String> map = new Hashtable<Integer, String>(path, 100, new IntegerHandler(), new StringValueHandler());
+ HashtableAccessor accessor = map.createAccessor(false);
- Hashtable<Integer, String> map;
+ assertFalse(map.containsKey(accessor, 0));
+ map.put(accessor, 0, "hello world");
+ assertEquals("hello world", map.get(accessor, 0));
+ String oldValue = map.put(accessor, 0, null);
+ assertEquals("hello world", oldValue);
+ assertNull(map.get(accessor, 0));
+ assertEquals(1, map.size());
+ assertTrue(map.containsKey(accessor, 0));
+
+ accessor.close();
+ }
- map = new Hashtable<Integer, String>(path, 1000000, new IntegerHandler(), new StringValueHandler());
+ @Test
+ public void testSimple() throws Exception {
+
+ File path = new File(this.path, "testSimple");
+
+ Hashtable<Integer, String> map = new Hashtable<Integer, String>(path, 100, new IntegerHandler(), new StringValueHandler());
assertEquals(0, map.size());
@@ -57,6 +86,19 @@
String v2 = map.get(accessor, 1);
assertEquals(v, v2);
+ // test cursor
+ accessor = map.createAccessor(false);
+ Hashtable<Integer, String>.Cursor cursor = map.new Cursor(accessor);
+
+ assertTrue(cursor.next());
+ assertEquals(0, (int) cursor.key());
+ assertEquals(v, cursor.value());
+
+ assertTrue(cursor.next());
+ assertEquals(1, (int) cursor.key());
+ assertEquals(v, cursor.value());
+
+ assertFalse(cursor.next());
accessor.close();
@@ -67,7 +109,7 @@
assertEquals(2, map.size());
accessor = map.createAccessor(false);
- Hashtable<Integer, String>.Cursor cursor = map.new Cursor(accessor);
+ cursor = map.new Cursor(accessor);
assertTrue(cursor.next());
assertEquals(0, (int) cursor.key());
@@ -105,8 +147,21 @@
accessor.close();
- // load lots of data to it in order to make sure it produce more than one partition
- accessor = map.createAccessor(false);
+
+
+ }
+
+
+ @Test
+ public void testPartitions() throws Exception {
+
+ // load lots of data to it in order to make sure it produce more than one partition but not too many.
+
+ File path = new File(this.path, "testPartitions");
+
+ Hashtable<Integer, String> map = new Hashtable<Integer, String>(path, 10000, new IntegerHandler(), new StringValueHandler());
+
+ HashtableAccessor accessor = map.createAccessor(false);
StringBuilder sb = new StringBuilder(10000);
for (int i = 0; i < 1000; i++) {
@@ -122,8 +177,8 @@
assertEquals(str + String.valueOf(i), map.get(accessor, i));
}
-
accessor.close();
-
}
+
+
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@labs.apache.org
For additional commands, e-mail: commits-help@labs.apache.org