[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