[Mulgara-svn] r801 - projects/xa2/object-pool/src
andrae at mulgara.org
andrae at mulgara.org
Mon Apr 21 08:05:47 UTC 2008
Author: andrae
Date: 2008-04-21 01:05:47 -0700 (Mon, 21 Apr 2008)
New Revision: 801
Modified:
projects/xa2/object-pool/src/ByteMap.java
projects/xa2/object-pool/src/CompMemTrie.java
Log:
Adds the ability to write out a trie-map - currently untested.
Modified: projects/xa2/object-pool/src/ByteMap.java
===================================================================
--- projects/xa2/object-pool/src/ByteMap.java 2008-04-18 08:44:31 UTC (rev 800)
+++ projects/xa2/object-pool/src/ByteMap.java 2008-04-21 08:05:47 UTC (rev 801)
@@ -13,7 +13,7 @@
* Represents a map from a byte to data.
* ie. a compressed 256 element array.
*/
-public class ByteMap<T> {
+public class ByteMap<T> implements Iterable<T> {
short high;
short[] low;
ArrayList<T> data;
@@ -21,7 +21,7 @@
public ByteMap() {
high = 0;
low = new short[0];
- data = new ArrayList<T>(0);
+ data = new ArrayList<T>(2);
}
/**
@@ -105,6 +105,10 @@
}
}
+ public Iterator<T> iterator() {
+ return children.iterator();
+ }
+
public int size() {
return data.size();
}
@@ -112,4 +116,15 @@
public int memSize() {
return 2 + 2 * low.length + 2 * data.size();
}
+
+ public int headerSize() {
+ return 2 + 2 * low.length;
+ }
+
+ public void writeHeader(ByteBuffer bb) {
+ bb.putByte(high);
+ for (int i = 0; i < low.length; i++) {
+ bb.putByte(low[i]);
+ }
+ }
}
Modified: projects/xa2/object-pool/src/CompMemTrie.java
===================================================================
--- projects/xa2/object-pool/src/CompMemTrie.java 2008-04-18 08:44:31 UTC (rev 800)
+++ projects/xa2/object-pool/src/CompMemTrie.java 2008-04-21 08:05:47 UTC (rev 801)
@@ -11,9 +11,16 @@
*/
public class CompMemTrie {
@SuppressWarnings("serial")
- public static class NotFound extends Exception {};
+ public static class CompMemTrieException extends Exception {};
+ public static class NotFound extends CompMemTrieException {};
+ public static class InsufficientSpace extends CompMemTrieException {};
+ static byte TYPE_BRANCH_TERM = 0x01; // Indicates a trie branch with a termination entry..
+ static byte TYPE_BRANCH_NOTERM = 0x02; // Indicates a trie branch without a termination entry..
+ static byte TYPE_LEAF = 0x03; // Indicates a trie branch without a termination entry..
+
private TrieNode root;
+ public static int MAGIC = 0x00010001;
public CompMemTrie() {
this.root = null;
@@ -39,12 +46,39 @@
return root.lookup(key);
}
+ public void write(ByteBuffer index, ByteBuffer data) {
+ if (root == null) {
+ throw new IllegalStateException("Attempt to write empty trie");
+ }
+ int indexreq = root.totalIndexSize() + 4 + 2; // + sizeof(MAGIC) + sizeof(ptr_to_root)
+ if (indexreq > index.hasRemaining()) {
+ throw new InsufficientSpaceException("Attempt to write trie index to bytebuffer with insufficient space");
+ }
+ if (indexreq > 0x00010000) {
+ throw new InsufficientSpaceException("Attempt to write trie index larger than 64K");
+ }
+ int datareq = root.totalDataSize();
+ if (datareq > data.hasRemaining()) {
+ throw new InsufficientSpaceException("Attempt to write trie data to bytebuffer with insufficient space");
+ }
+
+ index.putInt(MAGIC);
+ root.write(index, data);
+ index.putShort(index.limit() - 2, root.location);
+ }
+
+
private abstract static class TrieNode {
@SuppressWarnings("serial")
protected static class InsertAbove extends Exception {} ;
protected static final InsertAbove cont = new InsertAbove();
protected TrieLeaf aLeaf;
+ /**
+ * Offset into block of this TrieNode.
+ * 0 if uninitialized. Measured in bytes.
+ */
+ protected short location = 0;
public void insert(byte[] key, long value) throws InsertAbove {
insert(new TrieLeaf(key, value), 0);
@@ -54,6 +88,16 @@
return lookup(key, 0);
}
+ /**
+ * This method *must* update location with the position in the index buffer it was written to.
+ * This allows parents to obtain a physical reference to this node in their write methods.
+ * The index buffer is the target of the Trie index itself.
+ * The data buffer is the target of the byte[]/value pairs stored in the leaves. We want to keep these
+ * separate for caching purposes.
+ */
+ protected abstract void write(ByteBuffer index, ByteBuffer data);
+ protected abstract int totalIndexSize();
+ protected abstract int totalDataSize();
protected abstract void insert(TrieLeaf node, int parentLcd) throws InsertAbove;
protected abstract long lookup(byte[] key, int parentLcd) throws NotFound;
@@ -89,10 +133,53 @@
this(oldRoot, new TrieLeaf(key, value));
}
- public int memSize() {
- return 4 + children.memSize() + (term == null ? 0 : 2);
+ protected int memSize() {
+ return 4 + 1 + 1 + children.memSize() + (term == null ? 0 : 2);
}
+ protected int totalIndexSize() {
+ int total = memSize();
+ if (term != null) {
+ total += term.totalIndexSize();
+ }
+ for (TrieNode child : children) {
+ total += child.totalIndexSize();
+ }
+
+ return total;
+ }
+
+ protected int totalDataSize() {
+ int total = 0;
+ if (term != null) {
+ total += term.totalDataSize();
+ }
+ for (TrieNode child : children) {
+ total += child.totalDataSize();
+ }
+
+ return total;
+ }
+
+ protected void write(ByteBuffer index, ByteBuffer data) {
+ for (TrieNode child : children) {
+ child.write(index, data);
+ }
+
+ location = (short)bb.position();
+
+ index.putByte((term == null) ? TYPE_BRANCH_NOTERM : TYPE_BRANCH_TERM);
+ index.putByte(aLeaf.key[offset]);
+ index.putInt(offset);
+ if (term != null) {
+ index.putShort(term.location);
+ }
+ children.writeHeader(index);
+ for (TrieNode child : children) {
+ index.putShort(child.location);
+ }
+ }
+
private TrieBranch(TrieNode oldNode, TrieLeaf newNode) {
super();
assert oldNode != null;
@@ -202,6 +289,8 @@
final byte[] key;
final long value;
+ private long keyLocation = 0;
+
public TrieLeaf(byte[] key, long value) {
super();
this.key = new byte[key.length];
@@ -227,6 +316,26 @@
return value;
}
+ protected int totalIndexSize() {
+ return 1 + 1 + 8;
+ }
+
+ protected int totalDataSize() {
+ return 8 + 4 + key.length;
+ }
+
+ protected void write(ByteBuffer index, ByteBuffer data) {
+ keyLocation = data.position();
+ data.putLong(value);
+ data.putInt(key.length);
+ data.put(key);
+
+ location = (short)index.position;
+ index.putByte(TYPE_LEAF);
+ index.putByte(0x00); // Pad to 16-bit aligned.
+ index.putLong(keyLocation);
+ }
+
public String toString() {
return "Trie-LEAF: " + Arrays.toString(key) + " -> " + value;
}
More information about the Mulgara-svn
mailing list