[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