[Mulgara-svn] r826 - projects/xa2/object-pool/src
andrae at mulgara.org
andrae at mulgara.org
Wed Apr 23 08:34:47 UTC 2008
Author: andrae
Date: 2008-04-23 01:34:46 -0700 (Wed, 23 Apr 2008)
New Revision: 826
Modified:
projects/xa2/object-pool/src/ByteMap.java
projects/xa2/object-pool/src/CompMemTrie.java
Log:
Doesn't compile, but it is a first cut at reading the serialized Tries from Blocks.
Modified: projects/xa2/object-pool/src/ByteMap.java
===================================================================
--- projects/xa2/object-pool/src/ByteMap.java 2008-04-23 06:53:28 UTC (rev 825)
+++ projects/xa2/object-pool/src/ByteMap.java 2008-04-23 08:34:46 UTC (rev 826)
@@ -27,6 +27,21 @@
data = (T[])new Object[0];
}
+ public ByteMap(ByteBuffer index, Map<Short, T> nodeMap) {
+ high = bb.getShort();
+ low = new short[ones(high)];
+ dataCount = 0;
+ for (int i = 0; i < low.length; i++) {
+ low[i] = bb.getShort();
+ dataCount += ones(low[i]);
+ }
+ data = (T[])new Object[dataCount];
+ for (int i = 0; i < data.length; i++) {
+ short t = index.getShort();
+ data[i] = nodeMap.get(t);
+ }
+ }
+
/**
* @param datum Value to be associated with key. Note: Must not be null.
* @return the old value associated with key, or null if this is a new mapping.
Modified: projects/xa2/object-pool/src/CompMemTrie.java
===================================================================
--- projects/xa2/object-pool/src/CompMemTrie.java 2008-04-23 06:53:28 UTC (rev 825)
+++ projects/xa2/object-pool/src/CompMemTrie.java 2008-04-23 08:34:46 UTC (rev 826)
@@ -18,13 +18,14 @@
public static class InsufficientSpace extends Exception
{ public InsufficientSpace(String s) { super(s); } };
- 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..
+ 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..
+ public final static int MAGIC = 0x00020001;
+ public final static int INVERT_MAGIC = 0x01000200;
+
protected TrieNode root;
- public static int MAGIC = 0x00010001;
-
public CompMemTrie() {
this.root = null;
}
@@ -66,7 +67,45 @@
index.putShort(index.limit() - 2, root.location);
}
+ public static CompMemTrie read(ByteBuffer index, FileChannel data) throws IOException {
+ index.rewind(); // Note sure if I should doing this here or delegating to the caller.
+ int magic = index.getInt();
+ if (magic != MAGIC) {
+ if (magic == INVERT_MAGIC) {
+ index.order(index.order().equals(ByteOrder.BIG_ENDIAN) ? ByteOrder.LITTLE_ENDIAN : ByteOrder.BIG_ENDIAN);
+ } else {
+ throw new IllegalArgumentException("Bad magic in index buffer: " + magic + ", MAGIC=" + MAGIC);
+ }
+ }
+ short rootLocation = index.getShort(index.limit() - 2);
+
+ // I should be able to replace this with a stack.
+ // The child->parent relationship is implicit in the ordering of the nodes in the file.
+ // The only thing we need to know is when to stop reading nodes and that is provided by rootLocation.
+ // If treated as a stack once we have read the root the stack should contain only a single element - the
+ // root node.
+ // For now I'm hoping the HashMap will help with debugging - but it is wasteful of memory in the long run.
+ HashMap<Short, TrieNode> nodeMap = new HashMap<Short, TrieNode>();
+ while (index.position() < rootLocation) {
+ short location = (short)index.position();
+ byte type = index.get();
+ switch (type) {
+ case TYPE_BRANCH_TERM:
+ nodeMap.put(location, TrieBranch.readTerm(index, true, nodeMap));
+ break;
+ case TYPE_BRANCH_NOTERM:
+ nodeMap.put(location, TrieBranch.readNoTerm(index, false, nodeMap));
+ break;
+ case TYPE_BRANCH_LEAF:
+ nodeMap.put(location, TrieLeaf.readLeaf(index, data));
+ break;
+ }
+ }
+
+ root = nodeMap.get(rootLocation);
+ }
+
protected abstract static class TrieNode {
@SuppressWarnings("serial")
protected static class InsertAbove extends Exception {} ;
@@ -160,7 +199,21 @@
return total;
}
+ protected TrieBranch(ByteBuffer index, Map<Short, TrieNode> nodeMap, boolean hasTerm) throws IOException {
+ location = (short)index.position() - 1;
+
+ index.get(); // skip padding.
+ offset = index.getInt();
+ if (hasTerm) {
+ term = (TrieLeaf)nodeMap.get(index.getShort());
+ }
+ children = new ByteMap<TrieNode>(index, nodeMap);
+ }
+
protected void write(ByteBuffer index, FileChannel data) throws IOException {
+ if (term != null) {
+ term.write(index, data);
+ }
for (TrieNode child : children) {
child.write(index, data);
}
@@ -256,6 +309,7 @@
protected long lookup(byte[] key, int parentLcd) throws NotFound {
if (!regionMatches(aLeaf.key, parentLcd, key, parentLcd, offset - parentLcd)) {
+ //FIXME: I need to migrate this to the end of the search to avoid needing access to the key at each level.
throw new NotFound();
} else {
// new node matches the lcp of this node.
@@ -298,6 +352,19 @@
this.aLeaf = this;
}
+ protected TrieLeaf(ByteBuffer index, FileChannel data) throws IOException {
+ location = (short)index.position() - 1;
+ index.get();
+ keyLocation = getLong();
+ data.position(keyLocation);
+ ByteBuffer bb = ByteBuffer.allocateDirect(14);
+ data.read(bb);
+ value = bb.getLong();
+ length = bb.getInt();
+ key = new byte[length]; // FIXME: I eventually need to replace this with a lazy load.
+ data.read(ByteBuffer.wrap(key));
+ }
+
protected void insert(TrieLeaf node, int parentLcp) throws InsertAbove {
if (key.length != node.key.length) {
throw cont;
More information about the Mulgara-svn
mailing list