[Mulgara-svn] r786 - projects/xa2/object-pool/src
andrae at mulgara.org
andrae at mulgara.org
Tue Apr 15 05:57:18 UTC 2008
Author: andrae
Date: 2008-04-14 22:57:17 -0700 (Mon, 14 Apr 2008)
New Revision: 786
Added:
projects/xa2/object-pool/src/CompMemTrie.java
Log:
A Compressed Memory Trie. Uses the ByteMap to replace the existing HashMap byte->T map.
Copied: projects/xa2/object-pool/src/CompMemTrie.java (from rev 772, projects/xa2/object-pool/src/MemoryTrie.java)
===================================================================
--- projects/xa2/object-pool/src/CompMemTrie.java (rev 0)
+++ projects/xa2/object-pool/src/CompMemTrie.java 2008-04-15 05:57:17 UTC (rev 786)
@@ -0,0 +1,239 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 9th April 2008
+ */
+
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * Implements a basic in-memory trie - uses HashMaps to implement trie nodes.
+ */
+public class MemoryTrie {
+ @SuppressWarnings("serial")
+ public static class NotFound extends Exception {};
+
+ private TrieBranch root;
+
+ public MemoryTrie() {
+ this.root = null;
+ }
+
+ public void insert(byte[] key, long value) {
+// System.err.println("MemoryTrie # Inserting: " + Arrays.hashCode(key) + " :: " + value);
+ if (root == null) {
+ root = new TrieBranch(key, value);
+ } else {
+ try {
+ root.insert(key, value);
+ } catch (TrieNode.InsertAbove k) {
+ root = new TrieBranch(root, key, value);
+ }
+ }
+ }
+
+ public long lookup(byte[] key) throws NotFound {
+// System.err.println("MemoryTrie # Lookup: " + Arrays.hashCode(key));
+ if (root == null) {
+ throw new NotFound();
+ }
+
+ return root.lookup(key);
+ }
+
+ private abstract static class TrieNode {
+ @SuppressWarnings("serial")
+ protected static class InsertAbove extends Exception {} ;
+ protected static final InsertAbove cont = new InsertAbove();
+
+ protected TrieLeaf least;
+
+ protected abstract void insert(TrieLeaf node, int parentLcd) throws InsertAbove;
+ protected abstract long lookup(byte[] key, int parentLcd) throws NotFound;
+
+ protected static boolean regionMatches(byte[] lhs, int lhsOff, byte[] rhs, int rhsOff, int len) {
+ if (lhsOff < 0 || rhsOff < 0) {
+ return false;
+ }
+ if (lhs.length < lhsOff + len || rhs.length < rhsOff + len) {
+ return false;
+ }
+ for (int i = 0; i < len; i++) {
+ if (lhs[lhsOff + i] != rhs[rhsOff + i]) return false;
+ }
+
+ return true;
+ }
+ }
+
+ private static class TrieBranch extends TrieNode {
+ private int offset;
+ private Map<Byte, TrieNode> children;
+ private TrieLeaf term;
+
+ public TrieBranch(byte[] key, long value) {
+ super();
+ this.children = new HashMap<Byte, TrieNode>();
+ this.term = new TrieLeaf(key, value);
+ this.offset = term.key.length;
+ this.least = this.term;
+ }
+
+ public TrieBranch(TrieBranch oldRoot, byte[] key, long value) {
+ this(oldRoot, new TrieLeaf(key, value));
+ }
+
+ private TrieBranch(TrieNode oldNode, TrieLeaf newNode) {
+ super();
+ assert oldNode != null;
+ assert newNode != null;
+
+ offset = 0;
+ children = new HashMap<Byte, TrieNode>();
+ term = null;
+ least = null;
+
+ byte[] lhs = oldNode.least.key;
+ byte[] rhs = newNode.key;
+
+ int i = 0;
+ while (i < lhs.length && i < rhs.length) {
+ if (lhs[i] != rhs[i]) {
+ offset = i;
+ children.put(lhs[i], oldNode);
+ children.put(rhs[i], newNode);
+
+ least = lhs[i] < rhs[i] ? oldNode.least : newNode;
+
+ return; // Escape here.
+ }
+ i++;
+ }
+
+ if (i < lhs.length) {
+ offset = i;
+ children.put(lhs[i], oldNode);
+ term = newNode;
+ least = newNode;
+ } else if (i < rhs.length) {
+ if (oldNode instanceof TrieLeaf) {
+ offset = i;
+ children.put(rhs[i], newNode);
+ term = (TrieLeaf)oldNode;
+ least = (TrieLeaf)oldNode;
+ } else {
+ throw new IllegalStateException("Attempt to create new branch node with leaf > branch.");
+ }
+ } else {
+ throw new IllegalStateException("Attempt to create new branch node with equal children");
+ }
+ }
+
+ public void insert(byte[] key, long value) throws InsertAbove {
+ insert(new TrieLeaf(key, value), 0);
+ }
+
+ public long lookup(byte[] key) throws NotFound {
+ return lookup(key, 0);
+ }
+
+ protected void insert(TrieLeaf node, int parentLcp) throws InsertAbove {
+ if (!regionMatches(least.key, parentLcp, node.key, parentLcp, offset - parentLcp)) {
+ throw cont;
+ } else {
+ // new node matches the lcp of this node.
+ if (node.key.length == offset) {
+ // new node is expected to terminate here.
+ if (term == null) {
+ term = node;
+ least = node;
+ } else {
+ term.insert(node, offset);
+ }
+ } else {
+ // new node is expected to terminate in one of this nodes children.
+ TrieNode child = children.get(node.key[offset]);
+ if (child == null) {
+ // this is the first node to be inserted on this branching key.
+ children.put(node.key[offset], node);
+ } else {
+ try {
+ // there is an existing child node branching on this branching key.
+ child.insert(node, offset);
+ } catch (InsertAbove k) {
+ // as every child node shares a common lcp, any child will suffice when preparing the new
+ // lcp/offset of the new node. The least node is only required as the new parent's least node
+ // will be the smallest of the inserted node and this node's least node.
+ children.put(node.key[offset], new TrieBranch(child, node));
+ }
+ }
+ }
+ }
+ }
+
+ protected long lookup(byte[] key, int parentLcd) throws NotFound {
+ if (!regionMatches(least.key, parentLcd, key, parentLcd, offset - parentLcd)) {
+ throw new NotFound();
+ } else {
+ // new node matches the lcp of this node.
+ TrieNode child;
+ if (key.length == offset) {
+ // new node is expected to terminate here.
+ if (term != null) {
+ return term.value;
+ } else {
+ throw new NotFound();
+ }
+ } else {
+ // new node is expected to terminate in one of this nodes children.
+ child = children.get(key[offset]);
+ if (child != null) {
+ return child.lookup(key, offset);
+ } else {
+ throw new NotFound();
+ }
+ }
+ }
+ }
+
+ public String toString() {
+ return "Trie-BRANCH[" + (term != null) + " on " + offset + " with " + children.size() + " and least[" + least + "]";
+ }
+ }
+
+ private static class TrieLeaf extends TrieNode {
+ final byte[] key;
+ final long value;
+
+ public TrieLeaf(byte[] key, long value) {
+ super();
+ this.key = new byte[key.length];
+ System.arraycopy(key, 0, this.key, 0, key.length);
+ this.value = value;
+ this.least = this;
+ }
+
+ protected void insert(TrieLeaf node, int parentLcp) throws InsertAbove {
+ if (key.length != node.key.length) {
+ throw cont;
+ } else if (!regionMatches(key, parentLcp, node.key, parentLcp, key.length - parentLcp)) {
+ throw cont;
+ } else if (value == node.value) {
+ return; // Duplicate key/value pair.
+ } else {
+ throw new IllegalArgumentException("Attempt to insert multiple values for same key");
+ }
+ }
+
+ protected long lookup(byte[] key, int parentLcd) {
+ assert Arrays.equals(this.key, key);
+ return value;
+ }
+
+ public String toString() {
+ return "Trie-LEAF: " + Arrays.toString(key) + " -> " + value;
+ }
+ }
+}
More information about the Mulgara-svn
mailing list