[Mulgara-svn] r866 - projects/xa2/object-pool/src
andrae at mulgara.org
andrae at mulgara.org
Tue Apr 29 04:27:51 UTC 2008
Author: andrae
Date: 2008-04-28 21:27:51 -0700 (Mon, 28 Apr 2008)
New Revision: 866
Modified:
projects/xa2/object-pool/src/CompBlockTrie.java
projects/xa2/object-pool/src/CompMemTrie.java
Log:
The only IO code left in the memory-trie is the location field. Final step will be to migrate that to a map
internal to the block-trie write-function.
Modified: projects/xa2/object-pool/src/CompBlockTrie.java
===================================================================
--- projects/xa2/object-pool/src/CompBlockTrie.java 2008-04-29 03:59:02 UTC (rev 865)
+++ projects/xa2/object-pool/src/CompBlockTrie.java 2008-04-29 04:27:51 UTC (rev 866)
@@ -12,13 +12,23 @@
import java.util.Map;
/**
- * Extends CompMemTrie to guarantee the trie will fit within a single block.
+ * Extends CompMemTrie to provide IO functionality.
+ *
+ * Guarantees Trie will fit within a single block, refuses to accept insert() if it would make the
+ * serialized size of the node greater than the blocksize.
*/
public class CompBlockTrie extends CompMemTrie {
@SuppressWarnings("serial")
public static class InsufficientSpace extends Exception
{ public InsufficientSpace(String s) { super(s); } };
+ static final byte TYPE_BRANCH_TERM = 0x01; // Indicates a trie branch with a termination entry..
+ static final byte TYPE_BRANCH_NOTERM = 0x02; // Indicates a trie branch without a termination entry..
+ static final byte TYPE_LEAF = 0x03; // Indicates a trie branch without a termination entry..
+ static final byte TYPE_ROOT_LOC = 0x04; // Indicates the following short indicates a branch.
+ public final static int MAGIC = 0x00020001;
+ public final static int INVERT_MAGIC = 0x01000200;
+
// Calculated as the worst case size per entry.
// Assumes a full leaf and branch per entry.
// Block: 2-byte type-header
@@ -106,7 +116,7 @@
// Space was calculated on the basis of worst-case - if we were worst case we have now filled the
// trie-block, but if we haven't we should recalculate the space available.
if (space == 0) {
- int size = root.totalIndexSize();
+ int size = totalIndexSize(root);
space = (short)((blockSize - size - 8) / WORST_CASE_ENTRY_SIZE);
if (space < 0) {
throw new IllegalStateException("Overfilled CompBlockTrie");
@@ -134,7 +144,7 @@
throw new IllegalStateException("Attempt to write empty trie");
}
- int indexreq = (root == null) ? 8 : root.totalIndexSize() + 4 + 4; // + sizeof(MAGIC) + sizeof(root_loc_type + root_loc)
+ int indexreq = (root == null) ? 8 : totalIndexSize(root) + 4 + 4; // + sizeof(MAGIC) + sizeof(root_loc_type + root_loc)
if (indexreq > index.remaining()) {
System.err.printf("Index-Req:%d ; remaining:%d ; capacity:%d ; limit:%d ; position:%d\n", indexreq,
index.remaining(), index.capacity(), index.limit(), index.position());
@@ -209,7 +219,7 @@
TrieLeaf leaf = (TrieLeaf)node;
ByteBuffer dataBuf = ByteBuffer.allocateDirect(8 + 4 + leaf.key.length);
- leaf.keyLocation = data.position();
+ long keyLocation = data.position();
dataBuf.putLong(leaf.value);
dataBuf.putInt(leaf.key.length);
dataBuf.put(leaf.key);
@@ -218,7 +228,7 @@
leaf.location = (short)index.position();
index.put(TYPE_LEAF);
index.put((byte)0xFF); // Pad to 16-bit aligned.
- index.putLong(leaf.keyLocation);
+ index.putLong(keyLocation);
}
}
@@ -261,6 +271,68 @@
byte[] key = new byte[length]; // FIXME: I eventually need to replace this with a lazy load.
data.read(ByteBuffer.wrap(key));
- return new TrieLeaf(key, value, location, keyLocation);
+ return new TrieLeaf(key, value, location);
}
+
+ private static Map<Class, TrieNodeSizer> sizerMap = new HashMap<Class, TrieNodeSizer>();
+ static {
+ sizerMap.put(TrieBranch.class, new TrieBranchSizer());
+ sizerMap.put(TrieLeaf.class, new TrieLeafSizer());
+ }
+
+ protected static int totalIndexSize(TrieNode node) {
+ return sizerMap.get(node.getClass()).indexSize(node);
+ }
+
+ protected static int totalDataSize(TrieNode node) {
+ return sizerMap.get(node.getClass()).dataSize(node);
+ }
+
+ private static interface TrieNodeSizer {
+ public int indexSize(TrieNode node);
+ public int dataSize(TrieNode node);
+ }
+
+ private static class TrieBranchSizer implements TrieNodeSizer {
+ protected int memSize(TrieBranch branch) {
+ return 4 + 1 + 1 + branch.children.memSize() + (branch.term == null ? 0 : 2);
+ }
+
+ public int indexSize(TrieNode node) {
+ TrieBranch branch = (TrieBranch)node;
+ int total = memSize(branch);
+ if (branch.term != null) {
+ total += totalIndexSize(branch.term);
+ }
+ for (TrieNode child : branch.children) {
+ total += totalIndexSize(child);
+ }
+
+ return total;
+ }
+
+ public int dataSize(TrieNode node) {
+ TrieBranch branch = (TrieBranch)node;
+ int total = 0;
+ if (branch.term != null) {
+ total += totalDataSize(branch.term);
+ }
+ for (TrieNode child : branch.children) {
+ total += totalDataSize(child);
+ }
+
+ return total;
+ }
+ }
+
+ private static class TrieLeafSizer implements TrieNodeSizer {
+ public int indexSize(TrieNode node) {
+ return 1 + 1 + 8;
+ }
+
+ public int dataSize(TrieNode node) {
+ TrieLeaf leaf = (TrieLeaf)node;
+ return 8 + 4 + leaf.key.length;
+ }
+ }
}
Modified: projects/xa2/object-pool/src/CompMemTrie.java
===================================================================
--- projects/xa2/object-pool/src/CompMemTrie.java 2008-04-29 03:59:02 UTC (rev 865)
+++ projects/xa2/object-pool/src/CompMemTrie.java 2008-04-29 04:27:51 UTC (rev 866)
@@ -14,13 +14,6 @@
public static class NotFound extends Exception {};
private static NotFound notfound = new NotFound();
- static final byte TYPE_BRANCH_TERM = 0x01; // Indicates a trie branch with a termination entry..
- static final byte TYPE_BRANCH_NOTERM = 0x02; // Indicates a trie branch without a termination entry..
- static final byte TYPE_LEAF = 0x03; // Indicates a trie branch without a termination entry..
- static final byte TYPE_ROOT_LOC = 0x04; // Indicates the following short indicates a branch.
- public final static int MAGIC = 0x00020001;
- public final static int INVERT_MAGIC = 0x01000200;
-
protected TrieNode root;
public CompMemTrie() {
this.root = null;
@@ -77,8 +70,6 @@
return lookup(key, 0, valid);
}
- protected abstract int totalIndexSize();
- protected abstract int totalDataSize();
protected abstract boolean insert(TrieLeaf node, int parentLcd);
protected abstract long lookup(byte[] key, int parentLcd, boolean[] valid);
@@ -115,34 +106,6 @@
this(oldRoot, new TrieLeaf(key, value));
}
- 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;
- }
-
private TrieBranch(TrieNode oldNode, TrieLeaf newNode) {
super();
assert oldNode != null;
@@ -257,13 +220,10 @@
final byte[] key;
final long value;
- protected long keyLocation = 0;
-
- protected TrieLeaf(byte[] key, long value, short location, long keyLocation) {
+ protected TrieLeaf(byte[] key, long value, short location) {
this.key = key;
this.value = value;
this.location = location;
- this.keyLocation = keyLocation;
this.aLeaf = this;
}
@@ -292,14 +252,6 @@
return value;
}
- protected int totalIndexSize() {
- return 1 + 1 + 8;
- }
-
- protected int totalDataSize() {
- return 8 + 4 + key.length;
- }
-
public String toString() {
return "Trie-LEAF: " + Arrays.toString(key) + " -> " + value;
}
More information about the Mulgara-svn
mailing list