[Mulgara-svn] r1238 - in projects/xa2/object-pool: . lib src/data src/scheduler src/trie
andrae at mulgara.org
andrae at mulgara.org
Fri Sep 5 05:45:16 UTC 2008
Author: andrae
Date: 2008-09-04 22:45:15 -0700 (Thu, 04 Sep 2008)
New Revision: 1238
Added:
projects/xa2/object-pool/lib/ant-1.7.0.jar
projects/xa2/object-pool/lib/ant-apache-bsf-1.7.0.jar
projects/xa2/object-pool/lib/ant-junit-1.7.0.jar
projects/xa2/object-pool/lib/ant-launcher-1.7.0.jar
projects/xa2/object-pool/lib/ant-nodeps-1.7.0.jar
projects/xa2/object-pool/lib/ant-trax-1.7.0.jar
projects/xa2/object-pool/lib/bsf-2.3.0.jar
projects/xa2/object-pool/lib/js-1.5r3.jar
projects/xa2/object-pool/lib/junit-3.8.1.jar
projects/xa2/object-pool/src/data/DiskBackedDataEntry.java
projects/xa2/object-pool/src/data/DiskBackedDataEntryUnitTest.java
projects/xa2/object-pool/src/data/Entry.java
projects/xa2/object-pool/src/data/IndexEntry.java
projects/xa2/object-pool/src/data/Key.java
projects/xa2/object-pool/src/data/KeyUnitTest.java
projects/xa2/object-pool/src/data/MemoryBackedDataEntry.java
projects/xa2/object-pool/src/data/MemoryBackedDataEntryUnitTest.java
projects/xa2/object-pool/src/data/TestFileHandle.java
projects/xa2/object-pool/src/data/TestWritable.java
projects/xa2/object-pool/src/data/TrieEntry.java
projects/xa2/object-pool/src/scheduler/FileHandleImpl.java
projects/xa2/object-pool/src/scheduler/Writable.java
projects/xa2/object-pool/src/trie/TrieNode.java
Removed:
projects/xa2/object-pool/lib/ant
projects/xa2/object-pool/lib/ant-junit.jar
projects/xa2/object-pool/lib/ant-launcher.jar
projects/xa2/object-pool/lib/ant.jar
projects/xa2/object-pool/lib/junit-4.1.jar
Modified:
projects/xa2/object-pool/build.sh
projects/xa2/object-pool/build.xml
projects/xa2/object-pool/src/data/DataEntry.java
projects/xa2/object-pool/src/scheduler/Block.java
projects/xa2/object-pool/src/scheduler/FileHandle.java
projects/xa2/object-pool/src/scheduler/FileHandleFactory.java
projects/xa2/object-pool/src/scheduler/IOScheduler.java
projects/xa2/object-pool/src/trie/ByteMap.java
projects/xa2/object-pool/src/trie/DiskTrie.java
projects/xa2/object-pool/src/trie/DiskTrieTest.java
projects/xa2/object-pool/src/trie/MemoryTrie.java
projects/xa2/object-pool/src/trie/MemoryTrieUnitTest.java
projects/xa2/object-pool/src/trie/OnesTable.java
Log:
Bring subversion into synch with my own workspace.
Modified: projects/xa2/object-pool/build.sh
===================================================================
--- projects/xa2/object-pool/build.sh 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/build.sh 2008-09-05 05:45:15 UTC (rev 1238)
@@ -1,4 +1,7 @@
#!/bin/sh
unset ANT_HOME
-CLASSPATH=lib/ant.jar:lib/ant-junit.jar:lib/ant-launcher.jar:lib/junit-4.4.jar:$CLASSPATH lib/ant $@
+export ANT_HOME=./lib
+unset CLASSPATH
+export CLASSPATH="lib/ant-1.7.0.jar:lib/bsf-2.3.0.jar:lib/ant-launcher-1.7.0.jar:lib/junit-3.8.1.jar:lib/ant-junit-1.7.0.jar:lib/ant-apache-bsf-1.7.0.jar:lib/ant-trax-1.7.0.jar"
+java -Xmx768m org.apache.tools.ant.Main -buildfile "build.xml" $@
Modified: projects/xa2/object-pool/build.xml
===================================================================
--- projects/xa2/object-pool/build.xml 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/build.xml 2008-09-05 05:45:15 UTC (rev 1238)
@@ -35,7 +35,8 @@
<target name="test" depends="compile" description="Run the unit tests">
<delete dir="${test}"/>
<mkdir dir="${test}"/>
- <junit printsummary="yes" haltonfailure="no" showoutput="no" fork="yes" maxmemory="512m">
+ <junit printsummary="yes" haltonfailure="no" showoutput="no" fork="no" maxmemory="1024m">
+ <sysproperty key="org.mulgara.trie.OnesTable" value="src/trie/OnesTable.dat"/>
<classpath>
<pathelement path="${build}"/>
<pathelement location="/Developer/Java/Ant/lib/ant-junit.jar"/>
Deleted: projects/xa2/object-pool/lib/ant
===================================================================
--- projects/xa2/object-pool/lib/ant 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/lib/ant 2008-09-05 05:45:15 UTC (rev 1238)
@@ -1,326 +0,0 @@
-#! /bin/sh
-
-# Licensed to the Apache Software Foundation (ASF) under one or more
-# contributor license agreements. See the NOTICE file distributed with
-# this work for additional information regarding copyright ownership.
-# The ASF licenses this file to You under the Apache License, Version 2.0
-# (the "License"); you may not use this file except in compliance with
-# the License. You may obtain a copy of the License at
-#
-# http://www.apache.org/licenses/LICENSE-2.0
-#
-# Unless required by applicable law or agreed to in writing, software
-# distributed under the License is distributed on an "AS IS" BASIS,
-# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-# See the License for the specific language governing permissions and
-# limitations under the License.
-
-# Extract launch and ant arguments, (see details below).
-ant_exec_args=
-no_config=false
-use_jikes_default=false
-ant_exec_debug=false
-show_help=false
-for arg in "$@" ; do
- if [ "$arg" = "--noconfig" ] ; then
- no_config=true
- elif [ "$arg" = "--usejikes" ] ; then
- use_jikes_default=true
- elif [ "$arg" = "--execdebug" ] ; then
- ant_exec_debug=true
- elif [ my"$arg" = my"--h" -o my"$arg" = my"--help" ] ; then
- show_help=true
- ant_exec_args="$ant_exec_args -h"
- else
- if [ my"$arg" = my"-h" -o my"$arg" = my"-help" ] ; then
- show_help=true
- fi
- ant_exec_args="$ant_exec_args \"$arg\""
- fi
-done
-
-# Source/default ant configuration
-if $no_config ; then
- rpm_mode=false
- usejikes=$use_jikes_default
-else
- # load system-wide ant configuration (ONLY if ANT_HOME has NOT been set)
- if [ -z "$ANT_HOME" -o "$ANT_HOME" = "/usr/share/ant" ]; then
- if [ -f "/etc/ant.conf" ] ; then
- . /etc/ant.conf
- fi
- fi
-
- # load user ant configuration
- if [ -f "$HOME/.ant/ant.conf" ] ; then
- . $HOME/.ant/ant.conf
- fi
- if [ -f "$HOME/.antrc" ] ; then
- . "$HOME/.antrc"
- fi
-
- # provide default configuration values
- if [ -z "$rpm_mode" ] ; then
- rpm_mode=false
- fi
- if [ -z "$usejikes" ] ; then
- usejikes=$use_jikes_default
- fi
-fi
-
-# Setup Java environment in rpm mode
-if $rpm_mode ; then
- if [ -f /usr/share/java-utils/java-functions ] ; then
- . /usr/share/java-utils/java-functions
- set_jvm
- set_javacmd
- fi
-fi
-
-# OS specific support. $var _must_ be set to either true or false.
-cygwin=false;
-darwin=false;
-case "`uname`" in
- CYGWIN*) cygwin=true ;;
- Darwin*) darwin=true
- if [ -z "$JAVA_HOME" ] ; then
- JAVA_HOME=/System/Library/Frameworks/JavaVM.framework/Home
- fi
- ;;
-esac
-
-if [ -z "$ANT_HOME" -o ! -d "$ANT_HOME" ] ; then
- ## resolve links - $0 may be a link to ant's home
- PRG="$0"
- progname=`basename "$0"`
-
- # need this for relative symlinks
- while [ -h "$PRG" ] ; do
- ls=`ls -ld "$PRG"`
- link=`expr "$ls" : '.*-> \(.*\)$'`
- if expr "$link" : '/.*' > /dev/null; then
- PRG="$link"
- else
- PRG=`dirname "$PRG"`"/$link"
- fi
- done
-
- ANT_HOME=`dirname "$PRG"`/..
-
- # make it fully qualified
- ANT_HOME=`cd "$ANT_HOME" && pwd`
-fi
-
-# For Cygwin, ensure paths are in UNIX format before anything is touched
-if $cygwin ; then
- [ -n "$ANT_HOME" ] &&
- ANT_HOME=`cygpath --unix "$ANT_HOME"`
- [ -n "$JAVA_HOME" ] &&
- JAVA_HOME=`cygpath --unix "$JAVA_HOME"`
-fi
-
-# set ANT_LIB location
-ANT_LIB="${ANT_HOME}/lib"
-
-if [ -z "$JAVACMD" ] ; then
- if [ -n "$JAVA_HOME" ] ; then
- # IBM's JDK on AIX uses strange locations for the executables
- if [ -x "$JAVA_HOME/jre/sh/java" ] ; then
- JAVACMD="$JAVA_HOME/jre/sh/java"
- elif [ -x "$JAVA_HOME/jre/bin/java" ] ; then
- JAVACMD="$JAVA_HOME/jre/bin/java"
- else
- JAVACMD="$JAVA_HOME/bin/java"
- fi
- else
- JAVACMD=`which java 2> /dev/null `
- if [ -z "$JAVACMD" ] ; then
- JAVACMD=java
- fi
- fi
-fi
-
-if [ ! -x "$JAVACMD" ] ; then
- echo "Error: JAVA_HOME is not defined correctly."
- echo " We cannot execute $JAVACMD"
- exit 1
-fi
-
-# Build local classpath using just the launcher in non-rpm mode or
-# use the Jpackage helper in rpm mode with basic and default jars
-# specified in the ant.conf configuration. Because the launcher is
-# used, libraries linked in ANT_HOME/lib will also be included, but this
-# is discouraged as it is not java-version safe. A user should
-# request optional jars and their dependencies via the OPT_JAR_LIST
-# variable
-if $rpm_mode && [ -x /usr/bin/build-classpath ] ; then
- LOCALCLASSPATH="$(/usr/bin/build-classpath ant ant-launcher jaxp_parser_impl xml-commons-apis)"
-
- # If no optional jars have been specified then build the default list
- if [ -z "$OPT_JAR_LIST" ] ; then
- for file in /etc/ant.d/*; do
- if [ -f "$file" ]; then
- case "$file" in
- *~) ;;
- *#*) ;;
- *.rpmsave) ;;
- *.rpmnew) ;;
- *)
- for dep in `cat "$file"`; do
- case "$OPT_JAR_LIST" in
- *"$dep"*) ;;
- *) OPT_JAR_LIST="$OPT_JAR_LIST${OPT_JAR_LIST:+ }$dep"
- esac
- done
- esac
- fi
- done
- fi
-
- # If the user requested to try to add some other jars to the classpath
- if [ -n "$OPT_JAR_LIST" ] ; then
- _OPTCLASSPATH="$(/usr/bin/build-classpath $OPT_JAR_LIST 2> /dev/null)"
- if [ -n "$_OPTCLASSPATH" ] ; then
- LOCALCLASSPATH="$LOCALCLASSPATH:$_OPTCLASSPATH"
- fi
- fi
-
- # Explicitly add javac path to classpath, assume JAVA_HOME set
- # properly in rpm mode
- if [ -f "$JAVA_HOME/lib/tools.jar" ] ; then
- LOCALCLASSPATH="$LOCALCLASSPATH:$JAVA_HOME/lib/tools.jar"
- fi
- if [ -f "$JAVA_HOME/lib/classes.zip" ] ; then
- LOCALCLASSPATH="$LOCALCLASSPATH:$JAVA_HOME/lib/classes.zip"
- fi
-
- # if CLASSPATH_OVERRIDE env var is set, LOCALCLASSPATH will be
- # user CLASSPATH first and ant-found jars after.
- # In that case, the user CLASSPATH will override ant-found jars
- #
- # if CLASSPATH_OVERRIDE is not set, we'll have the normal behaviour
- # with ant-found jars first and user CLASSPATH after
- if [ -n "$CLASSPATH" ] ; then
- # merge local and specified classpath
- if [ -z "$LOCALCLASSPATH" ] ; then
- LOCALCLASSPATH="$CLASSPATH"
- elif [ -n "$CLASSPATH_OVERRIDE" ] ; then
- LOCALCLASSPATH="$CLASSPATH:$LOCALCLASSPATH"
- else
- LOCALCLASSPATH="$LOCALCLASSPATH:$CLASSPATH"
- fi
-
- # remove class path from launcher -cp option
- CLASSPATH=""
- fi
-else
- # not using rpm_mode; use launcher to determine classpaths
- if [ -z "$LOCALCLASSPATH" ] ; then
- LOCALCLASSPATH=$ANT_LIB/ant-launcher.jar
- else
- LOCALCLASSPATH=$ANT_LIB/ant-launcher.jar:$LOCALCLASSPATH
- fi
-fi
-
-if [ -n "$JAVA_HOME" ] ; then
- # OSX hack to make Ant work with jikes
- if $darwin ; then
- OSXHACK="${JAVA_HOME}/../Classes"
- if [ -d "${OSXHACK}" ] ; then
- for i in "${OSXHACK}"/*.jar
- do
- JIKESPATH="$JIKESPATH:$i"
- done
- fi
- fi
-fi
-
-# Allow Jikes support (off by default)
-if $usejikes; then
- ANT_OPTS="$ANT_OPTS -Dbuild.compiler=jikes"
-fi
-
-# For Cygwin, switch paths to appropriate format before running java
-# For PATHs convert to unix format first, then to windows format to ensure
-# both formats are supported. Probably this will fail on directories with ;
-# in the name in the path. Let's assume that paths containing ; are more
-# rare than windows style paths on cygwin.
-if $cygwin; then
- if [ "$OS" = "Windows_NT" ] && cygpath -m .>/dev/null 2>/dev/null ; then
- format=mixed
- else
- format=windows
- fi
- ANT_HOME=`cygpath --$format "$ANT_HOME"`
- ANT_LIB=`cygpath --$format "$ANT_LIB"`
- JAVA_HOME=`cygpath --$format "$JAVA_HOME"`
- LCP_TEMP=`cygpath --path --unix "$LOCALCLASSPATH"`
- LOCALCLASSPATH=`cygpath --path --$format "$LCP_TEMP"`
- if [ -n "$CLASSPATH" ] ; then
- CP_TEMP=`cygpath --path --unix "$CLASSPATH"`
- CLASSPATH=`cygpath --path --$format "$CP_TEMP"`
- fi
- CYGHOME=`cygpath --$format "$HOME"`
-fi
-
-# Show script help if requested
-if $show_help ; then
- echo $0 '[script options] [options] [target [target2 [target3] ..]]'
- echo 'Script Options:'
- echo ' --help, --h print this message and ant help'
- echo ' --noconfig suppress sourcing of /etc/ant.conf,'
- echo ' $HOME/.ant/ant.conf, and $HOME/.antrc'
- echo ' configuration files'
- echo ' --usejikes enable use of jikes by default, unless'
- echo ' set explicitly in configuration files'
- echo ' --execdebug print ant exec line generated by this'
- echo ' launch script'
- echo ' '
-fi
-# add a second backslash to variables terminated by a backslash under cygwin
-if $cygwin; then
- case "$ANT_HOME" in
- *\\ )
- ANT_HOME="$ANT_HOME\\"
- ;;
- esac
- case "$CYGHOME" in
- *\\ )
- CYGHOME="$CYGHOME\\"
- ;;
- esac
- case "$JIKESPATH" in
- *\\ )
- JIKESPATH="$JIKESPATH\\"
- ;;
- esac
- case "$LOCALCLASSPATH" in
- *\\ )
- LOCALCLASSPATH="$LOCALCLASSPATH\\"
- ;;
- esac
- case "$CLASSPATH" in
- *\\ )
- CLASSPATH="$CLASSPATH\\"
- ;;
- esac
-fi
-# Execute ant using eval/exec to preserve spaces in paths,
-# java options, and ant args
-ant_sys_opts=
-if [ -n "$CYGHOME" ]; then
- if [ -n "$JIKESPATH" ]; then
- ant_sys_opts="-Djikes.class.path=\"$JIKESPATH\" -Dcygwin.user.home=\"$CYGHOME\""
- else
- ant_sys_opts="-Dcygwin.user.home=\"$CYGHOME\""
- fi
-else
- if [ -n "$JIKESPATH" ]; then
- ant_sys_opts="-Djikes.class.path=\"$JIKESPATH\""
- fi
-fi
-ant_exec_command="exec \"$JAVACMD\" $ANT_OPTS -classpath \"$LOCALCLASSPATH\" -Dant.home=\"$ANT_HOME\" -Dant.library.dir=\"$ANT_LIB\" $ant_sys_opts org.apache.tools.ant.launch.Launcher $ANT_ARGS -cp \"$CLASSPATH\" $ant_exec_args"
-if $ant_exec_debug ; then
- echo $ant_exec_command
-fi
-eval $ant_exec_command
Added: projects/xa2/object-pool/lib/ant-1.7.0.jar
===================================================================
(Binary files differ)
Property changes on: projects/xa2/object-pool/lib/ant-1.7.0.jar
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: projects/xa2/object-pool/lib/ant-apache-bsf-1.7.0.jar
===================================================================
(Binary files differ)
Property changes on: projects/xa2/object-pool/lib/ant-apache-bsf-1.7.0.jar
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: projects/xa2/object-pool/lib/ant-junit-1.7.0.jar
===================================================================
(Binary files differ)
Property changes on: projects/xa2/object-pool/lib/ant-junit-1.7.0.jar
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Deleted: projects/xa2/object-pool/lib/ant-junit.jar
===================================================================
(Binary files differ)
Added: projects/xa2/object-pool/lib/ant-launcher-1.7.0.jar
===================================================================
(Binary files differ)
Property changes on: projects/xa2/object-pool/lib/ant-launcher-1.7.0.jar
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Deleted: projects/xa2/object-pool/lib/ant-launcher.jar
===================================================================
(Binary files differ)
Added: projects/xa2/object-pool/lib/ant-nodeps-1.7.0.jar
===================================================================
(Binary files differ)
Property changes on: projects/xa2/object-pool/lib/ant-nodeps-1.7.0.jar
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: projects/xa2/object-pool/lib/ant-trax-1.7.0.jar
===================================================================
(Binary files differ)
Property changes on: projects/xa2/object-pool/lib/ant-trax-1.7.0.jar
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Deleted: projects/xa2/object-pool/lib/ant.jar
===================================================================
(Binary files differ)
Added: projects/xa2/object-pool/lib/bsf-2.3.0.jar
===================================================================
(Binary files differ)
Property changes on: projects/xa2/object-pool/lib/bsf-2.3.0.jar
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: projects/xa2/object-pool/lib/js-1.5r3.jar
===================================================================
(Binary files differ)
Property changes on: projects/xa2/object-pool/lib/js-1.5r3.jar
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: projects/xa2/object-pool/lib/junit-3.8.1.jar
===================================================================
(Binary files differ)
Property changes on: projects/xa2/object-pool/lib/junit-3.8.1.jar
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Deleted: projects/xa2/object-pool/lib/junit-4.1.jar
===================================================================
(Binary files differ)
Modified: projects/xa2/object-pool/src/data/DataEntry.java
===================================================================
--- projects/xa2/object-pool/src/data/DataEntry.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/data/DataEntry.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -6,364 +6,65 @@
package data;
import java.io.IOException;
-import java.nio.BufferOverflowException;
-import java.nio.BufferUnderflowException;
-import java.nio.ByteBuffer;
-import java.nio.ByteOrder;
-import java.nio.channels.FileChannel;
-import java.util.HashMap;
-import java.util.Map;
-import scheduler.Block;
import scheduler.FileHandle;
+import scheduler.Writable;
/**
* Abstracts the concept of a data file entry.
*/
-public abstract class DataEntry {
- protected static final int HEADER_LENGTH = 12;
+public abstract class DataEntry implements TrieEntry {
+ protected static final int HEADER_LENGTH = (Long.SIZE + Integer.SIZE) / 8; // Node Value + Data Length
protected long value;
+ protected long location = -1;
- public abstract int dataSize();
-
- public abstract long write(FileHandle handle) throws IOException;
+ public abstract long write(Writable handle) throws IOException;
public abstract DataEntry canonicalize();
- public abstract DataEntry rewind();
- public abstract ByteBuffer slice(int offset, int length) throws IOException;
- public abstract byte get(int position) throws IOException;
- public abstract byte get() throws IOException;
+ public int entrySize() {
+// System.err.println("DataEntry:HEADER_LENGTH = " + HEADER_LENGTH + " / " + keySize());
+ return HEADER_LENGTH + keySize(); // VALUE + LENGTH + DATA
+ }
- public int totalSize() {
- return HEADER_LENGTH + dataSize(); // VALUE + LENGTH + DATA
+ public int referenceSize() {
+ return Long.SIZE / 8;
}
public long getValue() {
return value;
}
- public static DataEntry getEntry(byte[] data, long value) {
- return new MemoryBackedDataEntry(value, data, false);
+ public long getLocation() {
+ if (location != -1) {
+ return location;
+ } else {
+ throw new IllegalStateException("Attempt to obtain location of entry prior to serialization");
+ }
}
- public static DataEntry getEntry(byte[] data, long value, boolean copy) {
- return new MemoryBackedDataEntry(value, data, copy);
+ public TrieEntryType getTrieEntryType() {
+ return TrieEntryType.DATA;
}
- public static DataEntry getEntry(FileHandle handle, long position) throws IOException {
- return new DiskBackedDataEntry(handle, position).canonicalize();
+ public DataEntry asDataEntry() {
+ return this;
}
- public static DataEntry getKey(byte[] data) {
- return new MemoryBackedKey(data, false);
+ public IndexEntry asIndexEntry() {
+ throw new ClassCastException("Attempt to access DataEntry(" + this + ") as IndexEntry");
}
-
- protected static class DiskBackedDataEntry extends DataEntry {
- private FileHandle handle;
- private long position;
- private int length;
-
- // FIXME: Need to replace this with a background populated ConcurrentLinkedQueue.
- private Block[] blocks;
-
- // Note: In the case of the 0th buffer this is slice()'d to avoid having to deal with data.
- private ByteBuffer currBuffer;
- private int currBlock;
- private int currPosition;
- private int dataStart;
-
- DiskBackedDataEntry(FileHandle handle, long position) throws IOException {
- this.handle = handle;
- this.position = position;
-
- int blocksize = 0x01 << handle.getLog2BlockSize();
-
- System.err.println("Position: " + position + " blocksize: " + blocksize + " log2bs: " + handle.getLog2BlockSize());
- System.err.println("Reading block: " + (position >> handle.getLog2BlockSize()));
- Block block = handle.readBlock(position >> handle.getLog2BlockSize());
- if (block == null) {
- throw new IllegalArgumentException("Unable to read block for position");
- }
- this.currBlock = 0;
- System.err.println("Reading buffer: " + ((int)(position & (blocksize - 1))));
- this.currBuffer = block.offset((int)(position & (blocksize - 1)));
- this.currPosition = 0;
-
- this.value = currBuffer.getLong();
- this.length = currBuffer.getInt();
-
- System.err.printf("Value: %d, Length: %d\n", value, length);
-
- this.dataStart = currBuffer.position();
- currBuffer = currBuffer.slice();
-
- // Set the buffer to the entire block for length calculations.
- currBuffer.limit(currBuffer.capacity());
- int remaining = length - currBuffer.remaining();
- // If remaining <= 0 then this block contains all the data required for this entry.
- // Otherwise this entry is spread over multiple blocks, so we setup an array to support lazy-loading of
- // these blocks.
- System.err.printf("Setting totalBlocks to 1\n");
- int totalBlocks = 1;
- System.err.printf("remaining: %d, blocksize: %d\n", remaining, blocksize);
- if (remaining > 0) {
- System.err.printf("Calculating extra totalBlocks\n");
- totalBlocks += remaining / blocksize;
- System.err.printf("totalBlocks: %d\n", totalBlocks);
- if ((remaining % blocksize) > 0) {
- System.err.printf("Incrementing totalBlocks\n");
- totalBlocks++;
- System.err.printf("totalBlocks: %d\n", totalBlocks);
- }
- }
-
-// int totalBlocks = (remaining <= 0) ? 1 : remaining / blocksize + (((remaining % blocksize) > 0) ? 1 : 0);
- System.err.printf("remaining / blocksize: %d, remaining %% blocksize: %d\n", (remaining / blocksize), (remaining % blocksize));
- System.err.printf("remaining: %d, blocksize: %d, totalBlocks: %d\n", remaining, blocksize, totalBlocks);
- System.err.printf("currBuffer.capacity: %d, currBuffer.position: %d, currBuffer.limit: %d\n",
- currBuffer.capacity(), currBuffer.position(), currBuffer.limit());
- assert totalBlocks > 0;
-
- blocks = new Block[totalBlocks];
- blocks[0] = block;
- if (totalBlocks == 1) {
- // [dataStart,length] establishes the data covered by this entry.
- currBuffer.limit(length);
- }
- // FIXME: We eventually want to submit the remaining blocks to the scheduler for speculative background fetch.
- }
-
- /**
- * Convert 1 block entries into memory-backed entries.
- *
- * This makes the block's memory recoverable should we require it, and as the object-pool is subject to a
- * large number of stabbing-queries this is a good thing. Should we scan the pool, the block is likely to
- * still be cached so we shouldn't need to reload it; the only cost of canonicalizing in this case is an
- * unnecessary copy. However releasing a 32K-2M block in preference to a 20-30byte array is preferable if
- * we are doing a stabbing query.
- * Especially as a DiskBackedDataEntry requires 48-bytes anyway vs. 12 for a MemoryBackedDataEntry.
- */
- public DataEntry canonicalize() {
- if (blocks.length == 1) {
- System.err.println("dataStart = " + dataStart);
- System.err.println("currBuffer.capacity: " + currBuffer.capacity());
- System.err.println("currBuffer.limit: " + currBuffer.limit());
- byte[] data = new byte[currBuffer.position(0).remaining()];
- currBuffer.get(data);
- return new MemoryBackedDataEntry(value, data);
- } else {
- return this;
- }
- }
-
- public int dataSize() {
- return length;
- }
-
- public DataEntry rewind() {
- currBlock = 0;
- // block size is a power of 2 therefore mask is size - 1.
- currBuffer = blocks[0].offset(dataStart);
- if (blocks.length == 1) {
- // [mark,length] establishes the data covered by this entry.
- // Note: This should never occur as we expect DataEntries to be canonicalized, which would result in
- // a 1 block entry being replaced by a MemoryBackedDataEntry.
- // Note currBuffer has been slice()'d, so limit can be set to length directly.
- currBuffer.limit(length);
- } else {
- currBuffer.limit(currBuffer.capacity());
- }
-
- return this;
- }
-
- public byte get() throws IOException {
- if (currBuffer.hasRemaining()) {
- currPosition++;
- return currBuffer.get();
- } else {
- return get(currPosition);
- }
- }
-
- public byte get(int off) throws IOException {
- if (off < 0) throw new BufferUnderflowException();
- if (off >= length) throw new BufferOverflowException();
-
- int blocksize = (0x01 << handle.getLog2BlockSize());
- currBlock = (off + dataStart) / blocksize;
-
- if (blocks[currBlock] == null) {
- blocks[currBlock] = handle.readBlock(position + currBlock * blocksize);
- }
-
- if (currBlock == 0) {
- currBuffer = blocks[currBlock].offset(dataStart);
- currBuffer.position(off);
- } else {
- // Offset - (amount of data in 0th block) - (blocksize*number-of-skipped blocks).
- int blockOffset = off - (blocksize - dataStart) - (blocksize * (currBlock - 1));
- currBuffer = blocks[currBlock].offset(blockOffset);
- }
-
- // Allow for partial final block.
- if (currBlock == blocks.length - 1) {
- // if length fits within the first block:
- if (length - (blocksize - dataStart) <= 0) {
- currBuffer.limit(length);
- } else {
- int remaining = (length - (blocksize - dataStart));
- currBuffer.limit(remaining % blocksize);
-
- }
- }
-
- currPosition = off;
-
- return get();
- }
-
- public long write(FileHandle handle) throws IOException {
- handle.transferTo(handle, position, HEADER_LENGTH + length);
-
- return position;
- }
-
- /**
- * FIXME: We really need to return our own ByteBuffer implementation here that exploits lazy loading.
- *
- * Note this is a really really inefficient implementation.
- */
- public ByteBuffer slice(int offset, int length) throws IOException {
- ByteBuffer buffer = ByteBuffer.allocate(length);
- buffer.put(get(offset));
- for (int i = 1; i < length; i++) {
- buffer.put(get());
- }
-
- return buffer;
- }
+ // Static public constructors.
+ public static DataEntry getEntry(byte[] data, long value) {
+ return new MemoryBackedDataEntry(value, data, false);
}
-
- protected static class MemoryBackedDataEntry extends DataEntry {
- protected ByteBuffer data;
-
- MemoryBackedDataEntry(long value, byte[] data) {
- this(value, data, true);
- }
-
- MemoryBackedDataEntry(long value, byte[] data, boolean copyData) {
- this.value = value;
- if (copyData) {
- byte[] copy = new byte[data.length];
- System.arraycopy(data, 0, copy, 0, data.length);
- this.data = ByteBuffer.wrap(copy);
- } else {
- this.data = ByteBuffer.wrap(data);
- }
- }
-
- public byte get() throws BufferUnderflowException {
- return data.get();
- }
-
- public byte get(int offset) throws BufferUnderflowException {
- data.position(offset);
- return data.get(offset);
- }
-
- public DataEntry rewind() {
- data.rewind();
-
- return this;
- }
-
- public int dataSize() {
- return data.capacity();
- }
-
- public DataEntry canonicalize() {
- return this;
- }
-
- public long write(FileHandle handle) throws IOException {
- ByteBuffer bb = ByteBuffer.allocate(HEADER_LENGTH);
- bb.clear();
- bb.putLong(value);
- bb.putInt(data.capacity());
-// System.err.printf("Writing value %d, length %d\n", value, data.capacity());
- return handle.writeBuffers(new ByteBuffer[] { (ByteBuffer)bb.flip(), (ByteBuffer)data.duplicate().clear() }, HEADER_LENGTH);
- }
-
- public ByteBuffer slice(int offset, int length) {
- ByteBuffer bb = data.duplicate();
- bb.position(offset);
- bb = bb.slice();
- bb.limit(length);
-
- return bb;
- }
-
- public boolean equals(Object rhs) {
- if (rhs == this) {
- return true;
- }
- if (rhs.getClass().equals(getClass())) {
- MemoryBackedDataEntry mbde = (MemoryBackedDataEntry)rhs;
- return value == mbde.value && data.duplicate().clear().equals(mbde.data.duplicate().clear());
- } else {
- // FIXME: Do I need to consider comparing with DiskBackedDataEntry here?
- return false;
- }
- }
-
- public int hashCode() {
- // Note: If I do consider DBDE's equal to MBDE keeping it hashcode compatible will be all but
- // impossible. I doubt I want to do the linear hashCode computation required for a DBDE.
- return Long.valueOf(value).hashCode() ^ data.duplicate().clear().hashCode();
- }
+ public static DataEntry getEntry(byte[] data, long value, boolean copy) {
+ return new MemoryBackedDataEntry(value, data, copy);
}
- protected static class MemoryBackedKey extends MemoryBackedDataEntry {
- MemoryBackedKey(byte[] data) {
- this(data, true);
- }
-
- MemoryBackedKey(byte[] data, boolean copyData) {
- // Use dummy value.
- super(-1, data, copyData);
- }
-
- public boolean equals(Object rhs) {
- if (rhs == this) {
- return true;
- }
- if (rhs.getClass().equals(getClass())) {
- MemoryBackedKey mbde = (MemoryBackedKey)rhs;
- return data.duplicate().clear().equals(mbde.data.duplicate().clear());
- } else {
- return false;
- }
- }
-
- public int hashCode() {
- return data.duplicate().clear().hashCode();
- }
-
- public long write(FileHandle handle) throws IOException {
- throw new UnsupportedOperationException("Attempt to write Key without Value");
- }
-
- public long getValue() {
- throw new UnsupportedOperationException("Attempt to obtain value from naked Key");
- }
-
- public int totalSize() {
- throw new UnsupportedOperationException("Attempt to obtain materialization details from Key");
- }
+ public static DataEntry getEntry(FileHandle handle, long location) throws IOException {
+ return new DiskBackedDataEntry(handle, location).canonicalize();
}
-
}
Added: projects/xa2/object-pool/src/data/DiskBackedDataEntry.java
===================================================================
--- projects/xa2/object-pool/src/data/DiskBackedDataEntry.java (rev 0)
+++ projects/xa2/object-pool/src/data/DiskBackedDataEntry.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,226 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 4th September 2008
+ */
+package data;
+
+import java.io.IOException;
+import java.nio.BufferOverflowException;
+import java.nio.BufferUnderflowException;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+import java.nio.channels.FileChannel;
+import java.util.HashMap;
+import java.util.Map;
+
+import scheduler.Block;
+import scheduler.FileHandle;
+import scheduler.Writable;
+
+/**
+ * Abstracts the concept of a data file entry.
+ */
+class DiskBackedDataEntry extends DataEntry {
+ private FileHandle handle;
+
+ // Precalc'd points in the data entry.
+ // Note: superclass includes long location; the absolute offset of the DataEntry in the Handle.
+ /** Absolute offset of data in FileHandle */
+ private long dataAbsStartOffset;
+ /** Size of a block in this handle */
+ private int blocksize;
+ /** Log_2 of the blocksize */
+ private int log2bs;
+ /** BlockId of first block containing data in FileHandle */
+ private long dataAbsStartBlockId;
+ /** BlockId of first block containing this entry*/
+ private long entryAbsStartBlockId;
+ /** The number of data bytes in the entry. */
+ private int length;
+
+ // FIXME: Need to replace this with a background populated ConcurrentLinkedQueue.
+ private Block[] blocks;
+ private ByteBuffer currBuffer;
+ private int currBlock;
+ private int currPosition;
+
+ DiskBackedDataEntry(FileHandle handle, long location) throws IOException {
+// System.err.printf("DBDE::init(handle, location=%d)\n", location);
+ this.handle = handle;
+ this.location = location;
+
+ this.log2bs = handle.getLog2BlockSize();
+ this.blocksize = 0x01 << log2bs;
+ this.entryAbsStartBlockId = location >> log2bs;
+
+ Block block = handle.readBlock(entryAbsStartBlockId);
+ if (block == null) {
+ throw new IllegalArgumentException("Unable to read block for location");
+ }
+
+ ByteBuffer buff = block.offset((int)(location % blocksize));
+ this.value = buff.getLong();
+ this.length = buff.getInt();
+// System.err.printf("DataEntry:Value: %d, Length: %d\n", value, length);
+
+ this.dataAbsStartOffset = location + HEADER_LENGTH;
+ this.dataAbsStartBlockId = dataAbsStartOffset / blocksize;
+
+ // Set the buffer to the entire block for length calculations.
+ buff.limit(buff.capacity());
+ int remaining = length - buff.remaining();
+ // If remaining <= 0 then this block contains all the data required for this entry.
+ // Otherwise this entry is spread over multiple blocks, so we setup an array to support lazy-loading of
+ // these blocks.
+ int totalBlocks = 1;
+ if (remaining > 0) {
+ totalBlocks += remaining / blocksize;
+ if ((remaining % blocksize) > 0) {
+ totalBlocks++;
+ }
+ }
+ assert totalBlocks > 0;
+ this.blocks = new Block[totalBlocks];
+ this.blocks[0] = block;
+
+ // Having calculated all the necessary parameters, rewind buffer.
+ rewind();
+
+ // FIXME: We eventually want to submit the remaining blocks to the scheduler for speculative background fetch.
+
+ reportCurrBuffer("<init>");
+// System.err.printf("DataEntry:Leaving DBDE::<init> - length: %d, blocks.length: %d, currBlock: %d," +
+// " currPosition: %d, dataAbsStartOffset: %d, dataAbsStartBlockId: %d, entryAbsStartBlockId: %d, " +
+// " value: %d, location: %d, blocksize: %d, log2bs: %d\n",
+// length, blocks.length, currBlock, currPosition, dataAbsStartOffset, dataAbsStartBlockId,
+// entryAbsStartBlockId, value, location, blocksize, log2bs);
+ }
+
+ private void reportCurrBuffer(String method) {
+ if (currBuffer != null) {
+// System.err.printf("DataEntry:DBDE::%s - currBuffer: capacity: %d, position: %d, limit: %d\n",
+// method, currBuffer.capacity(), currBuffer.position(), currBuffer.limit());
+ } else {
+// System.err.printf("DataEntry:DBDE::%s with NULL currBuffer\n", method);
+ }
+ }
+
+ /**
+ * Convert 1 block entries into memory-backed entries.
+ *
+ * This makes the block's memory recoverable should we require it, and as the object-pool is subject to a
+ * large number of stabbing-queries this is a good thing. Should we scan the pool, the block is likely to
+ * still be cached so we shouldn't need to reload it; the only cost of canonicalizing in this case is an
+ * unnecessary copy. However releasing a 32K-2M block in preference to a 20-30byte array is preferable if
+ * we are doing a stabbing query.
+ * Especially as a DiskBackedDataEntry requires 48-bytes anyway vs. 12 for a MemoryBackedDataEntry.
+ */
+ public DataEntry canonicalize() {
+// System.err.println("DBDE::canonicalize()");
+ if (blocks.length == 1) {
+// System.err.println("DataEntry:currBuffer.capacity: " + currBuffer.capacity());
+// System.err.println("DataEntry:currBuffer.limit: " + currBuffer.limit());
+ byte[] data = new byte[currBuffer.position(0).remaining()];
+ currBuffer.get(data);
+ return new MemoryBackedDataEntry(value, data);
+ } else {
+ return this;
+ }
+ }
+
+ public int keySize() {
+// System.err.printf("DBDE::keySize()\n");
+ return length;
+ }
+
+ public Entry rewind() throws IOException {
+// System.err.printf("DBDE::rewind()\n");
+ reportCurrBuffer("rewind[start]");
+ currBuffer = obtainBuffer(0);
+ currPosition = 0;
+ reportCurrBuffer("rewind[end]");
+ return this;
+ }
+
+ public byte get() throws IOException {
+// System.err.printf("DBDE::get(); remaining: %d\n", currBuffer.remaining());
+ if (currBuffer.hasRemaining()) {
+ currPosition++;
+ return currBuffer.get();
+ } else if (currPosition >= length) {
+ throw new BufferUnderflowException();
+ } else {
+ currBuffer = obtainBuffer(currPosition);
+ return get();
+ }
+ }
+
+ private ByteBuffer obtainBuffer(int offset) throws IOException {
+ refreshCurrBlock(offset);
+
+ ByteBuffer buff;
+ int blockOffset;
+ // Note this allows for the posibility that block 1 may be the first block containing data.
+ if (currBlock == dataAbsStartBlockId - entryAbsStartBlockId) {
+ buff = blocks[currBlock].offset((int)(dataAbsStartOffset % blocksize));
+ blockOffset = offset;
+ } else {
+ buff = blocks[currBlock].offset(0);
+ // Offset - (amount of data in 0th block) - (blocksize*number-of-skipped blocks).
+ blockOffset = offset - (blocksize - (int)(dataAbsStartOffset % blocksize)) - (blocksize * (currBlock - 1));
+ }
+// System.err.printf("DBDE: setting blockOffset: %d\n", blockOffset);
+ buff.position(blockOffset);
+ if (length - offset <= buff.remaining()) {
+ buff.limit(blockOffset + length - offset);
+ } // else leave at capacity.
+
+ return buff;
+ }
+
+ private void refreshCurrBlock(int offset) throws IOException {
+// System.err.printf("DBDE::refreshCurrBlock(offset=%d)\n", offset);
+ currBlock = (int)((dataAbsStartOffset + offset) / blocksize - entryAbsStartBlockId);
+// System.err.printf("DBDE: calculated currBlock: %d\n", currBlock);
+
+ if (blocks[currBlock] == null) {
+ blocks[currBlock] = handle.readBlock(entryAbsStartBlockId + currBlock);
+ }
+ }
+
+ public byte get(int off) throws IOException {
+// System.err.printf("DBDE::get(off=%d)\n", off);
+ if (off < 0) throw new IndexOutOfBoundsException();
+ if (off >= length) throw new IndexOutOfBoundsException();
+
+ ByteBuffer buff = obtainBuffer(off);
+
+// System.err.printf("DBDE: buff: position: %d, limit: %d, capacity: %d\n", buff.position(), buff.limit(), buff.capacity());
+
+ return buff.get();
+ }
+
+ public long write(Writable handle) throws IOException {
+// System.err.printf("DBDE::write(handle)\n");
+ handle.transferTo(handle, getLocation(), HEADER_LENGTH + length);
+
+ return location;
+ }
+
+ /**
+ * FIXME: We need to return our own ByteBuffer implementation here that exploits lazy loading.
+ *
+ * Note this is a really really inefficient implementation.
+ */
+ public ByteBuffer keySlice(int offset, int length) throws IOException {
+// System.err.printf("DBDE::keySlice(offset=%d, length=%d)\n", offset, length);
+ ByteBuffer buffer = ByteBuffer.allocate(length);
+ buffer.put(get(offset));
+ for (int i = 1; i < length; i++) {
+ buffer.put(get());
+ }
+
+ return buffer;
+ }
+}
Added: projects/xa2/object-pool/src/data/DiskBackedDataEntryUnitTest.java
===================================================================
--- projects/xa2/object-pool/src/data/DiskBackedDataEntryUnitTest.java (rev 0)
+++ projects/xa2/object-pool/src/data/DiskBackedDataEntryUnitTest.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,262 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 3rd September 2008
+ */
+package data;
+
+import java.io.IOException;
+import java.nio.BufferUnderflowException;
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+
+import junit.framework.Test;
+import junit.framework.TestCase;
+import junit.framework.TestSuite;
+
+
+/**
+ * Basic tests of the MemoryTrie
+ */
+public class DiskBackedDataEntryUnitTest extends TestCase {
+ public static TestSuite suite() {
+ TestSuite suite = new TestSuite();
+ // Adapted from KeyUnitTest.java
+ suite.addTest(new DiskBackedDataEntryUnitTest("testConstructors"));
+ suite.addTest(new DiskBackedDataEntryUnitTest("testGet"));
+ suite.addTest(new DiskBackedDataEntryUnitTest("testGetOffset"));
+ suite.addTest(new DiskBackedDataEntryUnitTest("testRewind"));
+ suite.addTest(new DiskBackedDataEntryUnitTest("testKeySize"));
+ suite.addTest(new DiskBackedDataEntryUnitTest("testKeySlice"));
+
+ suite.addTest(new DiskBackedDataEntryUnitTest("testTrieEntryType"));
+ suite.addTest(new DiskBackedDataEntryUnitTest("testGetValue"));
+ suite.addTest(new DiskBackedDataEntryUnitTest("testCanonicalize"));
+
+ return suite;
+ }
+
+ public DiskBackedDataEntryUnitTest(String string) {
+ super(string);
+ }
+
+ byte[] sampledata = new byte[] { 0, 0, 0, 0, 0, 0, 0, 10, // 0:7 - 10L in BIG_ENDIAN (value) BLOCK0
+ 0, 0, 0, 8, // 8:11 - 8I in BIG_ENDIAN (length)
+ 0, 1, 2, 3, 4, 5, 6, 7, // 12:19 - byte array 1
+
+ 0, 0, 0, 0, 0, 0, 0, 11, // 20:27 - 11L in BIG_ENDIAN (value)
+ 0, 0, 0, 4, // 28:31 - 8I in BIG_ENDIAN (length)
+ 0, 1, 2, 3, // 32:35 - byte array 2 BLOCK1
+
+ 0, 0, 0, 0, 0, 0, 0, 12, // 36:43 - 12L in BIG_ENDIAN (value)
+ 0, 0, 0, 10, // 44:47 - 8I in BIG_ENDIAN (length)
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 8, 9, // 48:57 - byte array 3
+ 0, 0, 0, 0, 0, 0, // 58:63 - padding
+
+ 0, 0, 0, 0, 0, 0, 0, 13, // 64:71 - 13L in BIG_ENDIAN (value) BLOCK2
+ 0, 0, 0, 4, // 72:75 - 8I in BIG_ENDIAN (length)
+ 3, 2, 1, 0, // 76:79 - byte array 4
+ 0, 0, 0, 0, 0, 0, 0, 14, // 80:87 - 14L in BIG_ENDIAN (value)
+ 0, 0, 0, 70, // 88:91 - 70I in BIG_ENDIAN (length)
+ 0, 1, 2, 3, // 92:95 - first 4 bytes of byte array 5
+ 4, 5, 6, 7, // BLOCK3
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, // 96:127 - next 32 bytes of byte array 5
+ 4, 5, 6, 7, // BLOCK4
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, // 128:159 - next 32 bytes of byte array 5
+ 4, 5, // 160:161 - final 2 bytes of byte array 5 BLOCK5
+ 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, // 162:191 - padding
+ };
+
+ private byte[] bytes1 = new byte[] { 0, 1, 2, 3, 4, 5, 6, 7, };
+ private byte[] bytes2 = new byte[] { 0, 1, 2, 3, };
+ private byte[] bytes3 = new byte[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+ private byte[] bytes4 = new byte[] { 3, 2, 1, 0 };
+ private byte[] bytes5 = new byte[] { 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, 4, 5, };
+
+ public void testConstructors() throws Exception {
+ TestFileHandle handle = new TestFileHandle(sampledata);
+ DiskBackedDataEntry key1 = new DiskBackedDataEntry(handle, 0);
+ DiskBackedDataEntry key2 = new DiskBackedDataEntry(handle, 20);
+ DiskBackedDataEntry key3 = new DiskBackedDataEntry(handle, 36);
+ DiskBackedDataEntry key4 = new DiskBackedDataEntry(handle, 64);
+ DiskBackedDataEntry key5 = new DiskBackedDataEntry(handle, 80);
+ }
+
+ public void testGet() throws Exception {
+ TestFileHandle handle = new TestFileHandle(sampledata);
+ DiskBackedDataEntry key1 = new DiskBackedDataEntry(handle, 0);
+ DiskBackedDataEntry key2 = new DiskBackedDataEntry(handle, 20);
+ DiskBackedDataEntry key3 = new DiskBackedDataEntry(handle, 36);
+ DiskBackedDataEntry key4 = new DiskBackedDataEntry(handle, 64);
+ DiskBackedDataEntry key5 = new DiskBackedDataEntry(handle, 80);
+
+ assertCompare("1", key1, bytes1);
+ assertCompare("2", key2, bytes2);
+ assertCompare("3", key3, bytes3);
+ assertCompare("4", key4, bytes4);
+ assertCompare("5", key5, bytes5);
+ }
+
+ public void testGetOffset() throws Exception {
+ TestFileHandle handle = new TestFileHandle(sampledata);
+ DiskBackedDataEntry key2 = new DiskBackedDataEntry(handle, 20);
+
+ assertEquals("3", 3, key2.get(3));
+ assertEquals("3+", 0, key2.get());
+ assertEquals("2", 2, key2.get(2));
+ assertEquals("2+", 1, key2.get());
+ assertEquals("1", 1, key2.get(1));
+ assertEquals("0", 0, key2.get(0));
+ assertCompare("0+", key2, bytes2, 2, bytes2.length);
+
+ DiskBackedDataEntry key5 = new DiskBackedDataEntry(handle, 80);
+
+ assertEquals("3", 3, key5.get(3));
+ assertEquals("3+", 0, key5.get());
+ assertEquals("2", 2, key5.get(2));
+ assertEquals("2+", 1, key5.get());
+ assertEquals("1", 1, key5.get(1));
+ assertEquals("0", 0, key5.get(0));
+ assertEquals("33", 1, key5.get(33));
+ assertEquals("33+", 2, key5.get());
+ assertEquals("39", 7, key5.get(39));
+ assertEquals("39+", 3, key5.get());
+ assertEquals("42", 2, key5.get(42));
+ assertEquals("63", 7, key5.get(63));
+ assertEquals("64", 0, key5.get(64));
+ assertEquals("64+", 4, key5.get());
+ assertEquals("68", 4, key5.get(68));
+ assertEquals("68+", 5, key5.get());
+ assertEquals("69", 5, key5.get(69));
+ assertEquals("64", 0, key5.get(64));
+ assertEquals("63", 7, key5.get(63));
+ assertEquals("63+", 6, key5.get());
+ assertEquals("32", 0, key5.get(32));
+ assertEquals("32+", 7, key5.get());
+ assertEquals("31", 7, key5.get(31));
+ assertEquals("0", 0, key5.get(0));
+ assertCompare("0+", key5, bytes5, 8, bytes5.length);
+ }
+
+ public void testRewind() throws Exception {
+ TestFileHandle handle = new TestFileHandle(sampledata);
+ DiskBackedDataEntry key5 = new DiskBackedDataEntry(handle, 80);
+
+ assertEquals("0", 0, key5.get());
+ assertCompare("0+", key5, bytes5, 1, bytes5.length - 1);
+ assertEquals("f", 5, key5.get());
+ assertUnderflow("f+", key5);
+ key5.rewind();
+ assertCompare("r+", key5, bytes5);
+ }
+
+ public void testKeySize() throws Exception {
+ TestFileHandle handle = new TestFileHandle(sampledata);
+ DiskBackedDataEntry key1 = new DiskBackedDataEntry(handle, 0);
+ DiskBackedDataEntry key2 = new DiskBackedDataEntry(handle, 20);
+ DiskBackedDataEntry key3 = new DiskBackedDataEntry(handle, 36);
+ DiskBackedDataEntry key4 = new DiskBackedDataEntry(handle, 64);
+ DiskBackedDataEntry key5 = new DiskBackedDataEntry(handle, 80);
+
+ assertEquals("1", 8, key1.keySize());
+ assertEquals("2", 4, key2.keySize());
+ assertEquals("3", 10, key3.keySize());
+ assertEquals("4", 4, key4.keySize());
+ assertEquals("5", 70, key5.keySize());
+ }
+
+ public void testKeySlice() throws Exception {
+ TestFileHandle handle = new TestFileHandle(sampledata);
+ DiskBackedDataEntry key1 = new DiskBackedDataEntry(handle, 0);
+ DiskBackedDataEntry key2 = new DiskBackedDataEntry(handle, 20);
+ DiskBackedDataEntry key3 = new DiskBackedDataEntry(handle, 36);
+ DiskBackedDataEntry key4 = new DiskBackedDataEntry(handle, 64);
+ DiskBackedDataEntry key5 = new DiskBackedDataEntry(handle, 80);
+
+ // FIXME: Need to test this.
+ }
+
+ public void testTrieEntryType() throws Exception {
+ TestFileHandle handle = new TestFileHandle(sampledata);
+ DiskBackedDataEntry key1 = new DiskBackedDataEntry(handle, 0);
+
+ assertEquals("type", TrieEntry.TrieEntryType.DATA, key1.getTrieEntryType());
+ assertTrue("asDataEntry", key1.asDataEntry() == key1);
+ try {
+ key1.asIndexEntry();
+ fail("asIndexEntry");
+ } catch (ClassCastException ec) {}
+ }
+
+ public void testGetValue() throws Exception {
+ TestFileHandle handle = new TestFileHandle(sampledata);
+ DiskBackedDataEntry key1 = new DiskBackedDataEntry(handle, 0);
+ DiskBackedDataEntry key2 = new DiskBackedDataEntry(handle, 20);
+ DiskBackedDataEntry key3 = new DiskBackedDataEntry(handle, 36);
+ DiskBackedDataEntry key4 = new DiskBackedDataEntry(handle, 64);
+ DiskBackedDataEntry key5 = new DiskBackedDataEntry(handle, 80);
+
+ assertEquals("1", 10, key1.getValue());
+ assertEquals("2", 11, key2.getValue());
+ assertEquals("3", 12, key3.getValue());
+ assertEquals("4", 13, key4.getValue());
+ assertEquals("5", 14, key5.getValue());
+ }
+
+ public void testCanonicalize() throws Exception {
+ TestFileHandle handle = new TestFileHandle(sampledata);
+ DiskBackedDataEntry key1 = new DiskBackedDataEntry(handle, 0);
+ DiskBackedDataEntry key3 = new DiskBackedDataEntry(handle, 36);
+ DiskBackedDataEntry key4 = new DiskBackedDataEntry(handle, 64);
+ DiskBackedDataEntry key5 = new DiskBackedDataEntry(handle, 80);
+
+ assertTrue("1", key1 != key1.canonicalize());
+ // key2 can legitimately be canonicalized to either type.
+ assertTrue("3", key3 != key3.canonicalize());
+ assertTrue("4", key4 != key4.canonicalize());
+ assertTrue("5", key5 == key5.canonicalize());
+ }
+
+ public void assertNotEquals(String msg, Object o1, Object o2) {
+ assertFalse(msg, o1.equals(o2));
+ }
+
+ public void assertArrayEquals(String msg, byte[] a1, byte[] a2) {
+ if (!Arrays.equals(a1, a2)) {
+ fail(msg + "(" + Arrays.toString(a1) + ", " + Arrays.toString(a2) + ")");
+ }
+ }
+
+ public void assertCompare(String msg, DiskBackedDataEntry key, byte[] bytes) throws IOException {
+// System.err.printf("DBDEUT::assertCompare(msg=%s, key, bytes=%s)\n", msg, Arrays.toString(bytes));
+ assertCompare(msg, key, bytes, 0, bytes.length);
+ assertUnderflow(msg, key);
+ }
+
+ public void assertCompare(String msg, DiskBackedDataEntry key, byte[] bytes, int start, int end) throws IOException {
+ for (int i = start; i < end; i++) {
+// System.err.println("DBDEUT: calling key.get()");
+ assertEquals(msg + ":" + i, key.get(), bytes[i]);
+ }
+ }
+
+ public void assertUnderflow(String msg, DiskBackedDataEntry key) throws IOException {
+ try {
+ key.get();
+ fail(msg);
+ } catch (BufferUnderflowException eb) {}
+ }
+}
Added: projects/xa2/object-pool/src/data/Entry.java
===================================================================
--- projects/xa2/object-pool/src/data/Entry.java (rev 0)
+++ projects/xa2/object-pool/src/data/Entry.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,40 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 20th August 2008
+ */
+package data;
+
+import java.io.IOException;
+import java.nio.ByteBuffer;
+
+import scheduler.FileHandle;
+
+/**
+ * Abstracts the concept of a file entry.
+ *
+ * This can either be an unadorned key: used for interfacing with the lookup functions; a data-entry:
+ * consisting of a key/value pair; or an index-entry: containing a min-key-entry/index-ref pair pointing to the
+ * next trie node.
+ */
+public interface Entry {
+ /**
+ * Returns the size of the key associated with this entry.
+ *
+ * Measured in bytes.
+ */
+ public int keySize();
+
+ /**
+ * Returns a slice of the key as a ByteBuffer.
+ */
+ public ByteBuffer keySlice(int offset, int length) throws IOException;
+
+ public Entry rewind() throws IOException;
+
+ public byte get() throws IOException;
+
+ public byte get(int offset) throws IOException;
+}
+
+
Added: projects/xa2/object-pool/src/data/IndexEntry.java
===================================================================
--- projects/xa2/object-pool/src/data/IndexEntry.java (rev 0)
+++ projects/xa2/object-pool/src/data/IndexEntry.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,90 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 29th August 2008
+ */
+package data;
+
+import java.io.IOException;
+import java.nio.ByteBuffer;
+
+/**
+ * Abstracts the concept of an index entry.
+ */
+public class IndexEntry implements TrieEntry {
+ protected DataEntry value;
+ protected long indexOffset;
+
+ public IndexEntry(DataEntry value, long indexOffset) {
+ this.value = value;
+ this.indexOffset = indexOffset;
+ }
+
+ public int keySize() {
+ return value.keySize();
+ }
+
+ public long getDataLocation() {
+ return value.getLocation();
+ }
+
+ public long getIndexOffset() {
+ return indexOffset;
+ }
+
+ public ByteBuffer keySlice(int offset, int length) throws IOException {
+ return value.keySlice(offset, length);
+ }
+
+ public TrieEntryType getTrieEntryType() {
+ return TrieEntryType.INDEX;
+ }
+
+ public DataEntry asDataEntry() {
+ throw new ClassCastException("Attempt to access IndexEntry(" + this + ") as DataEntry");
+ }
+
+ public IndexEntry asIndexEntry() {
+ return this;
+ }
+
+ public int entrySize() {
+ return 0; // No data associated with an index-entry.
+ }
+
+ public int referenceSize() {
+ return Long.SIZE + // offset to next index.
+ value.referenceSize(); // reference to data-entry for min-key.
+ }
+
+ public Entry rewind() throws IOException {
+ value.rewind();
+ return this;
+ }
+
+ public byte get() throws IOException {
+ return value.get();
+ }
+
+ public byte get(int offset) throws IOException {
+ return value.get(offset);
+ }
+
+ public boolean equals(Object rhs) {
+ if (rhs == this) {
+ return true;
+ }
+ if (rhs.getClass().equals(getClass())) {
+ IndexEntry ie = (IndexEntry)rhs;
+ return indexOffset == ie.indexOffset && value.equals(ie.value);
+ } else {
+ return false;
+ }
+ }
+
+ public int hashCode() {
+ // Note: If I do consider DBDE's equal to MBDE keeping it hashcode compatible will be all but
+ // impossible. I doubt I want to do the linear hashCode computation required for a DBDE.
+ return Long.valueOf(indexOffset).hashCode() ^ value.hashCode();
+ }
+}
Added: projects/xa2/object-pool/src/data/Key.java
===================================================================
--- projects/xa2/object-pool/src/data/Key.java (rev 0)
+++ projects/xa2/object-pool/src/data/Key.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,73 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 22nd August 2008
+ */
+package data;
+
+import java.nio.BufferUnderflowException;
+import java.nio.ByteBuffer;
+
+/**
+ * Abstracts the concept of an unadorned key.
+ */
+public class Key implements Entry {
+ protected ByteBuffer data;
+
+ public Key(byte[] data) {
+ this(data, true);
+ }
+
+ public Key(byte[] data, boolean copyData) {
+ if (copyData) {
+ byte[] copy = new byte[data.length];
+ System.arraycopy(data, 0, copy, 0, data.length);
+ this.data = ByteBuffer.wrap(copy);
+ } else {
+ this.data = ByteBuffer.wrap(data);
+ }
+ }
+
+ public byte get(int offset) throws BufferUnderflowException {
+// data.position(offset);
+ return data.get(offset);
+ }
+
+ public ByteBuffer keySlice(int offset, int length) {
+ ByteBuffer bb = data.duplicate();
+ bb.position(offset);
+ bb = bb.slice();
+ bb.limit(length);
+
+ return bb;
+ }
+
+ public int keySize() {
+ return data.capacity();
+ }
+
+ public byte get() {
+ return data.get();
+ }
+
+ public Entry rewind() {
+ data.rewind();
+ return this;
+ }
+
+ public boolean equals(Object rhs) {
+ if (rhs == this) {
+ return true;
+ }
+ if (rhs.getClass().equals(getClass())) {
+ Key mbde = (Key)rhs;
+ return data.duplicate().clear().equals(mbde.data.duplicate().clear());
+ } else {
+ return false;
+ }
+ }
+
+ public int hashCode() {
+ return data.duplicate().clear().hashCode();
+ }
+}
Added: projects/xa2/object-pool/src/data/KeyUnitTest.java
===================================================================
--- projects/xa2/object-pool/src/data/KeyUnitTest.java (rev 0)
+++ projects/xa2/object-pool/src/data/KeyUnitTest.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,191 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 29th August 2008
+ */
+package data;
+
+import java.nio.BufferUnderflowException;
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+
+import junit.framework.Test;
+import junit.framework.TestCase;
+import junit.framework.TestSuite;
+
+
+/**
+ * Basic tests of the MemoryTrie.
+ *
+ * Note: Any changes here should be migrated into the other unit-tests.
+ */
+public class KeyUnitTest extends TestCase {
+ public static TestSuite suite() {
+ TestSuite suite = new TestSuite();
+ suite.addTest(new KeyUnitTest("testConstructors"));
+ suite.addTest(new KeyUnitTest("testEqualsHashCode"));
+ suite.addTest(new KeyUnitTest("testGet"));
+ suite.addTest(new KeyUnitTest("testGetOffset"));
+ suite.addTest(new KeyUnitTest("testRewind"));
+ suite.addTest(new KeyUnitTest("testKeySize"));
+ suite.addTest(new KeyUnitTest("testKeySlice"));
+
+ return suite;
+ }
+
+ public KeyUnitTest(String string) {
+ super(string);
+ }
+
+ private static byte[] bytesEmpty = new byte[] {};
+ private static byte[] bytes1 = new byte[] { 0, 1, 2, 3, 4, 5, 6, 7 };
+ private static byte[] bytes1eq = new byte[] { 0, 1, 2, 3, 4, 5, 6, 7 };
+ private static byte[] bytes2 = new byte[] { 1, 1, 2, 3, 4, 5, 6, 7 };
+ private static byte[] bytes2eq = new byte[] { 1, 1, 2, 3, 4, 5, 6, 7 };
+
+ public void testConstructors() throws Exception {
+ Key key1 = new Key(bytes1);
+ Key key1e = new Key(bytesEmpty);
+ Key key2 = new Key(bytes1, true);
+ Key key2e = new Key(bytesEmpty, true);
+ Key key3 = new Key(bytes1, false);
+ Key key3e = new Key(bytesEmpty, false);
+ }
+
+ public void testEqualsHashCode() throws Exception {
+ Key empty = new Key(bytesEmpty);
+ Key key1 = new Key(bytes1);
+ Key key1eq = new Key(bytes1eq);
+ Key key2 = new Key(bytes2);
+ Key key2eq = new Key(bytes2eq);
+
+ assertEquals("e.e", empty, empty);
+ assertEquals("1.1", key1, key1);
+ assertEquals("1e.1e", key1eq, key1eq);
+ assertEquals("2.2", key2, key2);
+ assertEquals("2e.2e", key2eq, key2eq);
+
+ assertEquals("1.1e", key1, key1eq);
+ assertEquals("1e.1", key1eq, key1);
+ assertEquals("2.2e", key2, key2eq);
+ assertEquals("2e.2", key2eq, key2);
+
+ assertNotEquals("1.2", key1, key2);
+ assertNotEquals("2.1", key2, key1);
+ assertNotEquals("1.2e", key1, key2eq);
+ assertNotEquals("2e.1", key2eq, key1);
+ assertNotEquals("1e.2", key1eq, key2);
+ assertNotEquals("2.1e", key2, key1eq);
+ assertNotEquals("1.e", key1, empty);
+ assertNotEquals("e.2", empty, key2);
+
+ assertEquals("he.e", empty.hashCode(), empty.hashCode());
+ assertEquals("h1.1", key1.hashCode(), key1.hashCode());
+ assertEquals("h1e.1e", key1eq.hashCode(), key1eq.hashCode());
+ assertEquals("h2.2", key2.hashCode(), key2.hashCode());
+ assertEquals("h2e.2e", key2eq.hashCode(), key2eq.hashCode());
+
+ assertEquals("h1.1e", key1.hashCode(), key1eq.hashCode());
+ assertEquals("h1e.1", key1eq.hashCode(), key1.hashCode());
+ assertEquals("h2.2e", key2.hashCode(), key2eq.hashCode());
+ assertEquals("h2e.2", key2eq.hashCode(), key2.hashCode());
+
+ assertNotEquals("h1.2", key1.hashCode(), key2.hashCode());
+ assertNotEquals("h2.1", key2.hashCode(), key1.hashCode());
+ assertNotEquals("h1.2e", key1.hashCode(), key2eq.hashCode());
+ assertNotEquals("h2e.1", key2eq.hashCode(), key1.hashCode());
+ assertNotEquals("h1e.2", key1eq.hashCode(), key2.hashCode());
+ assertNotEquals("h2.1e", key2.hashCode(), key1eq.hashCode());
+ assertNotEquals("h1.e", key1.hashCode(), empty.hashCode());
+ assertNotEquals("he.2", empty.hashCode(), key2.hashCode());
+ }
+
+ public void testGet() {
+ Key empty = new Key(bytesEmpty);
+ Key key1 = new Key(bytes1);
+ Key key1eq = new Key(bytes1eq);
+ Key key2 = new Key(bytes2);
+ Key key2eq = new Key(bytes2eq);
+
+ assertCompare("e", empty, bytesEmpty);
+ assertCompare("1", key1, bytes1);
+ assertCompare("1e", key1eq, bytes1eq);
+ assertCompare("2", key2, bytes2);
+ assertCompare("2e", key2eq, bytes2eq);
+ }
+
+ public void testGetOffset() {
+ Key key1 = new Key(bytes1);
+
+ assertEquals("4", 4, key1.get(4));
+ assertEquals("4+", 0, key1.get());
+ assertEquals("5", 5, key1.get(5));
+ assertEquals("7", 7, key1.get(7));
+ assertEquals("7+", 1, key1.get());
+ assertEquals("3", 3, key1.get(3));
+ assertEquals("2", 2, key1.get(2));
+ assertEquals("1", 1, key1.get(1));
+ assertEquals("6", 6, key1.get(6));
+ assertEquals("4.", 4, key1.get(4));
+ assertEquals("0", 0, key1.get(0));
+ assertCompare("0+", key1, bytes1, 2, bytes1.length);
+ }
+
+ public void testRewind() {
+ Key key1 = new Key(bytes1);
+
+ assertEquals("0", 0, key1.get());
+ assertCompare("0+", key1, bytes1, 1, bytes1.length - 1);
+ assertEquals("7", 7, key1.get());
+ assertUnderflow("7+", key1);
+ key1.rewind();
+ assertCompare("r+", key1, bytes1);
+ }
+
+ public void testKeySize() {
+ Key empty = new Key(bytesEmpty);
+ Key key1 = new Key(bytes1);
+ Key key1eq = new Key(bytes1eq);
+ Key key2 = new Key(bytes2);
+ Key key2eq = new Key(bytes2eq);
+
+ assertEquals("e", 0, empty.keySize());
+ assertEquals("1", 8, key1.keySize());
+ assertEquals("1e", 8, key1eq.keySize());
+ assertEquals("2", 8, key2.keySize());
+ assertEquals("2e", 8, key2eq.keySize());
+ }
+
+ public void testKeySlice() {
+ Key key1 = new Key(bytes1);
+ Key key1eq = new Key(bytes1eq);
+ Key key2 = new Key(bytes2);
+ Key key2eq = new Key(bytes2eq);
+
+ assertEquals("1.1", ByteBuffer.wrap(bytes1), key1eq.keySlice(0, bytes1.length));
+ assertEquals("1.2", ByteBuffer.wrap(bytes1, 1, bytes1.length - 2), key1.keySlice(1, bytes1.length - 2));
+ assertEquals("1.2", key2.keySlice(1, bytes2.length - 2), key1.keySlice(1, bytes1.length - 2));
+ }
+
+ public void assertNotEquals(String msg, Object o1, Object o2) {
+ assertFalse(msg, o1.equals(o2));
+ }
+
+ public void assertCompare(String msg, Key key, byte[] bytes) {
+ assertCompare(msg, key, bytes, 0, bytes.length);
+ assertUnderflow(msg, key);
+ }
+
+ public void assertCompare(String msg, Key key, byte[] bytes, int start, int end) {
+ for (int i = start; i < end; i++) {
+ assertEquals(msg + ":" + i, key.get(), bytes[i]);
+ }
+ }
+
+ public void assertUnderflow(String msg, Key key) {
+ try {
+ key.get();
+ fail(msg);
+ } catch (BufferUnderflowException eb) {}
+ }
+}
Added: projects/xa2/object-pool/src/data/MemoryBackedDataEntry.java
===================================================================
--- projects/xa2/object-pool/src/data/MemoryBackedDataEntry.java (rev 0)
+++ projects/xa2/object-pool/src/data/MemoryBackedDataEntry.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,96 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 4th September 2008
+ */
+package data;
+
+import java.io.IOException;
+import java.nio.BufferUnderflowException;
+import java.nio.ByteBuffer;
+
+import scheduler.Writable;
+
+/**
+ * A DataEntry backed by memory.
+ */
+class MemoryBackedDataEntry extends DataEntry {
+ protected ByteBuffer data;
+
+ MemoryBackedDataEntry(long value, byte[] data) {
+ this(value, data, true);
+ }
+
+ MemoryBackedDataEntry(long value, byte[] data, boolean copyData) {
+ this.value = value;
+ if (copyData) {
+ byte[] copy = new byte[data.length];
+ System.arraycopy(data, 0, copy, 0, data.length);
+ this.data = ByteBuffer.wrap(copy);
+ } else {
+ this.data = ByteBuffer.wrap(data);
+ }
+// System.err.println("DataEntry:MBDE::capacity = " + this.data.capacity() + "/" + data.length);
+ }
+
+ public byte get() throws BufferUnderflowException {
+ return data.get();
+ }
+
+ public byte get(int offset) throws BufferUnderflowException {
+ return data.get(offset);
+ }
+
+ public Entry rewind() {
+ data.rewind();
+
+ return this;
+ }
+
+ public int keySize() {
+// System.err.println("DataEntry:keysize = " + data.capacity());
+ return data.capacity();
+ }
+
+ public DataEntry canonicalize() {
+ return this;
+ }
+
+ public long write(Writable handle) throws IOException {
+ ByteBuffer bb = ByteBuffer.allocate(HEADER_LENGTH);
+ bb.clear();
+ bb.putLong(value);
+ bb.putInt(data.capacity());
+// System.err.printf("DataEntry:Writing value %d, length %d\n", value, data.capacity());
+ location = handle.writeBuffers(new ByteBuffer[] { (ByteBuffer)bb.flip(), (ByteBuffer)data.duplicate().clear() }, HEADER_LENGTH);
+ return location;
+ }
+
+ public ByteBuffer keySlice(int offset, int length) {
+ ByteBuffer bb = data.duplicate();
+ bb.position(offset);
+ bb = bb.slice();
+ bb.limit(length);
+
+ return bb;
+ }
+
+ public boolean equals(Object rhs) {
+ if (rhs == this) {
+ return true;
+ }
+ if (rhs.getClass().equals(getClass())) {
+ MemoryBackedDataEntry mbde = (MemoryBackedDataEntry)rhs;
+ return value == mbde.value && data.duplicate().clear().equals(mbde.data.duplicate().clear());
+ } else {
+ // FIXME: Do I need to consider comparing with DiskBackedDataEntry here?
+ return false;
+ }
+ }
+
+ public int hashCode() {
+ // Note: If I do consider DBDE's equal to MBDE keeping it hashcode compatible will be all but
+ // impossible. I doubt I want to do the linear hashCode computation required for a DBDE.
+ return Long.valueOf(value).hashCode() ^ data.duplicate().clear().hashCode();
+ }
+}
Added: projects/xa2/object-pool/src/data/MemoryBackedDataEntryUnitTest.java
===================================================================
--- projects/xa2/object-pool/src/data/MemoryBackedDataEntryUnitTest.java (rev 0)
+++ projects/xa2/object-pool/src/data/MemoryBackedDataEntryUnitTest.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,223 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 29th August 2008
+ */
+package data;
+
+import java.nio.BufferUnderflowException;
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+
+import junit.framework.Test;
+import junit.framework.TestCase;
+import junit.framework.TestSuite;
+
+
+/**
+ * Basic tests of the MemoryTrie
+ */
+public class MemoryBackedDataEntryUnitTest extends TestCase {
+ public static TestSuite suite() {
+ TestSuite suite = new TestSuite();
+ // Adapted from KeyUnitTest.java
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testConstructors"));
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testEqualsHashCode"));
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testGet"));
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testGetOffset"));
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testRewind"));
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testKeySize"));
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testKeySlice"));
+
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testTrieEntryType"));
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testGetValue"));
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testCanonicalize"));
+
+ suite.addTest(new MemoryBackedDataEntryUnitTest("testIO"));
+
+ return suite;
+ }
+
+ public MemoryBackedDataEntryUnitTest(String string) {
+ super(string);
+ }
+
+ private static byte[] bytes1 = new byte[] { 0, 1, 2, 3, 4, 5, 6, 7 };
+ private static byte[] bytes1eq = new byte[] { 0, 1, 2, 3, 4, 5, 6, 7 };
+ private static byte[] bytes2 = new byte[] { 1, 1, 2, 3, 4, 5, 6, 7 };
+ private static byte[] bytes2eq = new byte[] { 1, 1, 2, 3, 4, 5, 6, 7 };
+
+ public void testConstructors() throws Exception {
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+ MemoryBackedDataEntry key2 = new MemoryBackedDataEntry(10, bytes1, true);
+ MemoryBackedDataEntry key3 = new MemoryBackedDataEntry(10, bytes1, false);
+ }
+
+ public void testEqualsHashCode() throws Exception {
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+ MemoryBackedDataEntry key1eq = new MemoryBackedDataEntry(10, bytes1eq);
+ MemoryBackedDataEntry key2 = new MemoryBackedDataEntry(10, bytes2);
+ MemoryBackedDataEntry key2eq = new MemoryBackedDataEntry(10, bytes2eq);
+
+ assertEquals("1.1", key1, key1);
+ assertEquals("1e.1e", key1eq, key1eq);
+ assertEquals("2.2", key2, key2);
+ assertEquals("2e.2e", key2eq, key2eq);
+
+ assertEquals("1.1e", key1, key1eq);
+ assertEquals("1e.1", key1eq, key1);
+ assertEquals("2.2e", key2, key2eq);
+ assertEquals("2e.2", key2eq, key2);
+
+ assertNotEquals("1.2", key1, key2);
+ assertNotEquals("2.1", key2, key1);
+ assertNotEquals("1.2e", key1, key2eq);
+ assertNotEquals("2e.1", key2eq, key1);
+ assertNotEquals("1e.2", key1eq, key2);
+ assertNotEquals("2.1e", key2, key1eq);
+
+ assertEquals("h1.1", key1.hashCode(), key1.hashCode());
+ assertEquals("h1e.1e", key1eq.hashCode(), key1eq.hashCode());
+ assertEquals("h2.2", key2.hashCode(), key2.hashCode());
+ assertEquals("h2e.2e", key2eq.hashCode(), key2eq.hashCode());
+
+ assertEquals("h1.1e", key1.hashCode(), key1eq.hashCode());
+ assertEquals("h1e.1", key1eq.hashCode(), key1.hashCode());
+ assertEquals("h2.2e", key2.hashCode(), key2eq.hashCode());
+ assertEquals("h2e.2", key2eq.hashCode(), key2.hashCode());
+
+ assertNotEquals("h1.2", key1.hashCode(), key2.hashCode());
+ assertNotEquals("h2.1", key2.hashCode(), key1.hashCode());
+ assertNotEquals("h1.2e", key1.hashCode(), key2eq.hashCode());
+ assertNotEquals("h2e.1", key2eq.hashCode(), key1.hashCode());
+ assertNotEquals("h1e.2", key1eq.hashCode(), key2.hashCode());
+ assertNotEquals("h2.1e", key2.hashCode(), key1eq.hashCode());
+ }
+
+ public void testGet() {
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+ MemoryBackedDataEntry key1eq = new MemoryBackedDataEntry(10, bytes1eq);
+ MemoryBackedDataEntry key2 = new MemoryBackedDataEntry(10, bytes2);
+ MemoryBackedDataEntry key2eq = new MemoryBackedDataEntry(10, bytes2eq);
+
+ assertCompare("1", key1, bytes1);
+ assertCompare("1e", key1eq, bytes1eq);
+ assertCompare("2", key2, bytes2);
+ assertCompare("2e", key2eq, bytes2eq);
+ }
+
+ public void testGetOffset() {
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+
+ assertEquals("4", 4, key1.get(4));
+ assertEquals("4+", 0, key1.get());
+ assertEquals("5", 5, key1.get(5));
+ assertEquals("7", 7, key1.get(7));
+ assertEquals("7+", 1, key1.get());
+ assertEquals("3", 3, key1.get(3));
+ assertEquals("2", 2, key1.get(2));
+ assertEquals("1", 1, key1.get(1));
+ assertEquals("6", 6, key1.get(6));
+ assertEquals("4.", 4, key1.get(4));
+ assertEquals("0", 0, key1.get(0));
+ assertCompare("0+", key1, bytes1, 2, bytes1.length);
+ }
+
+ public void testRewind() {
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+
+ assertEquals("0", 0, key1.get());
+ assertCompare("0+", key1, bytes1, 1, bytes1.length - 1);
+ assertEquals("7", 7, key1.get());
+ assertUnderflow("7+", key1);
+ key1.rewind();
+ assertCompare("r+", key1, bytes1);
+ }
+
+ public void testKeySize() {
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+ MemoryBackedDataEntry key1eq = new MemoryBackedDataEntry(10, bytes1eq);
+ MemoryBackedDataEntry key2 = new MemoryBackedDataEntry(10, bytes2);
+ MemoryBackedDataEntry key2eq = new MemoryBackedDataEntry(10, bytes2eq);
+
+ assertEquals("1", 8, key1.keySize());
+ assertEquals("1e", 8, key1eq.keySize());
+ assertEquals("2", 8, key2.keySize());
+ assertEquals("2e", 8, key2eq.keySize());
+ }
+
+ public void testKeySlice() {
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+ MemoryBackedDataEntry key1eq = new MemoryBackedDataEntry(10, bytes1eq);
+ MemoryBackedDataEntry key2 = new MemoryBackedDataEntry(10, bytes2);
+ MemoryBackedDataEntry key2eq = new MemoryBackedDataEntry(10, bytes2eq);
+
+ assertEquals("1.1", ByteBuffer.wrap(bytes1), key1eq.keySlice(0, bytes1.length));
+ assertEquals("1.2", ByteBuffer.wrap(bytes1, 1, bytes1.length - 2), key1.keySlice(1, bytes1.length - 2));
+ assertEquals("1.2", key2.keySlice(1, bytes2.length - 2), key1.keySlice(1, bytes1.length - 2));
+ }
+
+ public void testTrieEntryType() throws Exception {
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+ assertEquals("type", TrieEntry.TrieEntryType.DATA, key1.getTrieEntryType());
+ assertTrue("asDataEntry", key1.asDataEntry() == key1);
+ try {
+ key1.asIndexEntry();
+ fail("asIndexEntry");
+ } catch (ClassCastException ec) {}
+ }
+
+ public void testGetValue() throws Exception {
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+ assertEquals("value", 10, key1.getValue());
+ }
+
+ public void testCanonicalize() throws Exception {
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+ assertEquals("value", key1, key1.canonicalize());
+ }
+
+ public void testIO() throws Exception {
+ byte[] key1serial = new byte[] { 0, 0, 0, 0, 0, 0, 0, 10, // 10L in BIG_ENDIAN (value)
+ 0, 0, 0, 8, // 8I in BIG_ENDIAN (length)
+ 0, 1, 2, 3, 4, 5, 6, 7, // bytes1 as byte array
+ };
+
+ TestWritable writable = new TestWritable();
+ MemoryBackedDataEntry key1 = new MemoryBackedDataEntry(10, bytes1);
+
+ long location = key1.write(writable);
+ assertEquals("1.loc", writable.getLocation(), location);
+ assertArrayEquals("1.buf", key1serial, writable.getBuffer().array());
+ assertEquals("1.rsize", 8, key1.referenceSize());
+ assertEquals("1.esize", key1serial.length, key1.entrySize());
+ }
+
+ public void assertNotEquals(String msg, Object o1, Object o2) {
+ assertFalse(msg, o1.equals(o2));
+ }
+
+ public void assertArrayEquals(String msg, byte[] a1, byte[] a2) {
+ if (!Arrays.equals(a1, a2)) {
+ fail(msg + "(" + Arrays.toString(a1) + ", " + Arrays.toString(a2) + ")");
+ }
+ }
+
+ public void assertCompare(String msg, MemoryBackedDataEntry key, byte[] bytes) {
+ assertCompare(msg, key, bytes, 0, bytes.length);
+ assertUnderflow(msg, key);
+ }
+
+ public void assertCompare(String msg, MemoryBackedDataEntry key, byte[] bytes, int start, int end) {
+ for (int i = start; i < end; i++) {
+ assertEquals(msg + ":" + i, key.get(), bytes[i]);
+ }
+ }
+
+ public void assertUnderflow(String msg, MemoryBackedDataEntry key) {
+ try {
+ key.get();
+ fail(msg);
+ } catch (BufferUnderflowException eb) {}
+ }
+}
Added: projects/xa2/object-pool/src/data/TestFileHandle.java
===================================================================
--- projects/xa2/object-pool/src/data/TestFileHandle.java (rev 0)
+++ projects/xa2/object-pool/src/data/TestFileHandle.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,73 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 3rd September 2008
+ */
+package data;
+
+import java.io.File;
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.nio.channels.FileChannel;
+
+import scheduler.Block;
+import scheduler.FileHandle;
+import scheduler.Writable;
+
+/**
+ * Used to test DiskBackedDataEntry.
+ */
+public class TestFileHandle implements FileHandle {
+ private static final int LOG2BS = 5; // Use a riduculously small blocksize for testing.
+
+ private ByteBuffer buffer;
+
+ public TestFileHandle(byte[] data) {
+ buffer = ByteBuffer.wrap(data);
+ }
+
+ public File getFile() {
+ return new File("TestFileHandle");
+ }
+
+ public int getLog2BlockSize() {
+ return LOG2BS;
+ }
+
+ public Block readBlock(long blockId) throws IOException {
+// System.err.printf("TestFileHandle::readBlock(blockId=%d)\n", blockId);
+ Block block = new Block(this, getLog2BlockSize());
+
+ block.prepare(blockId).put((ByteBuffer)(((ByteBuffer)(buffer.position((int)(blockId << LOG2BS)))).slice().limit(1 << LOG2BS)));
+
+ return block;
+ }
+
+ public Block readBlock() throws IOException {
+ throw new UnsupportedOperationException("readBlock/0");
+ }
+
+ public long writeBlock(Block block) throws IOException {
+ throw new UnsupportedOperationException("writeBlock");
+ }
+
+ public long writeBuffers(ByteBuffer[] buffers, int headerSize) throws IOException {
+ throw new UnsupportedOperationException("writeBuffers");
+ }
+
+ public void transferTo(Writable handle, long position, int length) throws IOException {
+ throw new UnsupportedOperationException("transferTo");
+ }
+
+ public void complete() throws IOException {
+ throw new UnsupportedOperationException("complete");
+ }
+
+ public void close() throws IOException {
+ throw new UnsupportedOperationException("close");
+ }
+
+ public FileChannel getChannel() {
+ throw new UnsupportedOperationException("getChannel");
+ }
+}
Added: projects/xa2/object-pool/src/data/TestWritable.java
===================================================================
--- projects/xa2/object-pool/src/data/TestWritable.java (rev 0)
+++ projects/xa2/object-pool/src/data/TestWritable.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,56 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 3rd September 2008
+ */
+package data;
+
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.nio.channels.FileChannel;
+
+import scheduler.Writable;
+
+/**
+ * A test Writable to allow testing DataEntries.
+ */
+public class TestWritable implements Writable {
+ ByteBuffer buffer;
+ long location;
+
+ public TestWritable() {
+ buffer = ByteBuffer.wrap(new byte[0]);
+ location = 1234567;
+ }
+
+ public long getLocation() {
+ return location;
+ }
+
+ public ByteBuffer getBuffer() {
+ return buffer;
+ }
+
+ public long writeBuffers(ByteBuffer[] buffers, int headerSize) throws IOException {
+ int size = 0;
+ for (int i = 0; i < buffers.length; i++) {
+ size += buffers[i].remaining();
+ }
+ buffer = ByteBuffer.wrap(new byte[size]);
+ for (int i = 0; i < buffers.length; i++) {
+ buffer.put(buffers[i]);
+ }
+
+ location += 1;
+
+ return location;
+ }
+
+ public void transferTo(Writable handle, long position, int length) throws IOException {
+ throw new UnsupportedOperationException("no transferTo in test-writable");
+ }
+
+ public FileChannel getChannel() {
+ throw new UnsupportedOperationException("no channel in test-writable");
+ }
+}
Added: projects/xa2/object-pool/src/data/TrieEntry.java
===================================================================
--- projects/xa2/object-pool/src/data/TrieEntry.java (rev 0)
+++ projects/xa2/object-pool/src/data/TrieEntry.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,42 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 26th August 2008
+ */
+package data;
+
+/**
+ * Abstracts the concept of an entry in a trie.
+ */
+public interface TrieEntry extends Entry {
+ enum TrieEntryType { DATA, INDEX };
+
+ /**
+ * Returns the type of trie-entry represented by this node.
+ */
+ public TrieEntryType getTrieEntryType();
+
+ /**
+ * Returns this node as a DataEntry; or throws ClassCastException.
+ */
+ public DataEntry asDataEntry();
+
+ /**
+ * Returns this node as an IndexEntry or throws ClassCastException.
+ */
+ public IndexEntry asIndexEntry();
+
+ /**
+ * Returns the serialized size (in bytes) of this entry.
+ *
+ * Note: This is the size taken in the _data_ file.
+ */
+ public int entrySize();
+
+ /**
+ * Returns the serialized size (in bytes) of a reference to this entry.
+ *
+ * Note: This is the size taken in the _index_ file.
+ */
+ public int referenceSize();
+}
Modified: projects/xa2/object-pool/src/scheduler/Block.java
===================================================================
--- projects/xa2/object-pool/src/scheduler/Block.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/scheduler/Block.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -20,8 +20,8 @@
this.handle = handle;
this.blockId = null;
this.buffer = ByteBuffer.allocateDirect(0x01 << log2bs);
- System.err.println("Allocating block with capacity: " + buffer.capacity() + " in file: " + handle.getFile());
- new Throwable().printStackTrace();
+// System.err.println("Block:Allocating block with capacity: " + buffer.capacity() + " in file: " + handle.getFile());
+// new Throwable().printStackTrace();
this.blockId = UNALLOCATED;
}
@@ -46,8 +46,8 @@
* Sets the Buffer's position = 0; limit = size; and stores the blockId.
*/
public ByteBuffer prepare(Long id) {
- System.err.println("Setting block-id to : " + id + " for file: " + handle.getFile());
- new Throwable().printStackTrace();
+// System.err.println("Block:Setting block-id to : " + id + " for file: " + handle.getFile());
+// new Throwable().printStackTrace();
blockId = id;
return (ByteBuffer)(buffer.clear());
}
@@ -89,9 +89,25 @@
}
public ByteBuffer offset(int position) {
- return (ByteBuffer)((ByteBuffer)buffer.position(position)).slice();
+// System.err.printf("Block:offset(position=%d)\n", position);
+ int pos = buffer.position();
+ buffer.position(position);
+ ByteBuffer tb = (ByteBuffer)buffer.slice();
+ buffer.position(pos);
+
+ reportBuffer("offset() result:", tb);
+ return tb;
}
+ private void reportBuffer(String buffer, ByteBuffer bb) {
+ if (bb != null) {
+// System.err.printf("Block::%s - buffer: capacity: %d, position: %d, limit: %d\n",
+// buffer, bb.capacity(), bb.position(), bb.limit());
+ } else {
+// System.err.printf("Block::%s with NULL buffer\n", buffer);
+ }
+ }
+
/**
* Prepare the Block to be written to/from memory.
* Sets the Buffer's position = 0; limit = size; and leaves the blockId unchanged.
Modified: projects/xa2/object-pool/src/scheduler/FileHandle.java
===================================================================
--- projects/xa2/object-pool/src/scheduler/FileHandle.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/scheduler/FileHandle.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -1,165 +1,34 @@
/*
* Copyright Topaz Foundation 2008
* Author Andrae Muys
- * Date 30th April 2008
+ * Date 3rd September 2008
*/
package scheduler;
import java.io.File;
-import java.io.FileInputStream;
-import java.io.FileOutputStream;
import java.io.IOException;
import java.nio.ByteBuffer;
-import java.nio.ByteOrder;
import java.nio.channels.FileChannel;
-public class FileHandle {
- private File file;
- private FileChannel channel;
- private int log2bs;
+/**
+ * This interface exists to permit test-harnesses to replace FileHandleImpl in UnitTests.
+ */
+public interface FileHandle extends Writable {
+ public File getFile();
- private final int blocksize;
- private long seeks;
+ public int getLog2BlockSize();
- FileHandle(File file, FileChannel channel, int magic, int log2bs) {
- this.file = file;
- this.channel = channel;
- this.log2bs = log2bs;
- this.blocksize = 0x01 << log2bs;
- this.seeks = 0;
- }
+ public Block readBlock(long blockId) throws IOException;
- FileHandle(File file, FileOutputStream stream, int magic, int log2bs) throws IOException {
- this(file, stream.getChannel(), magic, log2bs);
+ public Block readBlock() throws IOException;
- ByteBuffer bb = ByteBuffer.allocate(blocksize);
- System.err.println("Allocated header: " + bb.capacity());
- bb.putInt(magic);
- bb.putInt(log2bs);
- bb.position(0);
- bb.limit(bb.capacity());
+ long writeBlock(Block block) throws IOException;
- channel.write(bb);
- }
+ public long writeBuffers(ByteBuffer[] buffers, int headerSize) throws IOException;
- FileHandle(File file, FileInputStream stream, int magic, int log2bs) throws IOException {
- this(file, stream.getChannel(), magic, log2bs);
+ public void transferTo(Writable handle, long position, int length) throws IOException;
- if (log2bs < 10) throw new IllegalArgumentException("Attempt to open file with blocksize < 1KB");
+ public void complete() throws IOException;
- ByteBuffer bb = ByteBuffer.allocate(blocksize);
- this.channel.read(bb);
-
- bb.clear();
- int filemagic = bb.getInt();
- if (filemagic != magic) {
- bb.order(bb.order().equals(ByteOrder.BIG_ENDIAN) ? ByteOrder.LITTLE_ENDIAN : ByteOrder.BIG_ENDIAN);
- bb.clear();
- filemagic = bb.getInt();
- if (filemagic == magic) {
- throw new IllegalArgumentException("Attempt to read file using incorrect endian format");
- } else {
- throw new IllegalArgumentException("Bad magic in index buffer: " + filemagic + ", MAGIC=" + magic);
- }
- }
-
- int filebs = bb.getInt();
- if (filebs != log2bs) {
- throw new IllegalArgumentException("Attempt to read file(" + file + ") using incorrect log2bs: " + log2bs);
- }
- }
-
- public File getFile() {
- return file;
- }
-
- public int getLog2BlockSize() {
- return log2bs;
- }
-
- /**
- * FIXME: These should be package scope.
- */
- public Block readBlock(long blockId) throws IOException {
- // blockId + 1 allows higher levels to ignore the metadata stored in block-0.
- System.err.println("Reading block: " + blockId + " from File: " + file);
- if (channel.position() != ((blockId + 1) << log2bs)) {
- seeks++;
- channel.position((blockId + 1) << log2bs);
- }
-
- return readBlock();
- }
-
- public Block readBlock() throws IOException {
- Block block = new Block(this, log2bs);
-
- System.err.println("Reading block from position: " + channel.position());
- // Block::prepare takes a blockId, we can calculate this from the channel's position.
- int read = channel.read(block.prepare((channel.position() >> log2bs) - 1));
- if (read == blocksize) return block;
- if (read == -1) return null;
- throw new IllegalStateException("Partial block read");
- }
-
- long writeBlock(Block block) throws IOException {
- long position = channel.position() - blocksize;
-
- System.err.printf("Writing block to position: %d in file: %s\n", channel.position(), file.toString());
- channel.write(block.prepare(position >> log2bs));
-
- return position;
- }
-
- /**
- * FIXME: Should be package scope.
- */
- public long writeBuffers(ByteBuffer[] buffers, int headerSize) throws IOException {
- long currBlock = channel.position() / blocksize;
- long hEndBlock = (channel.position() + headerSize) / blocksize;
- if (currBlock != hEndBlock) {
- channel.write(ByteBuffer.wrap(new byte[(int)(channel.position() % blocksize)]));
- channel.position((currBlock + 1) * blocksize);
- }
-
- long position = channel.position() - blocksize;
-// System.err.printf("Writing %d buffers to position: %d in file: %s\n", buffers.length, channel.position(), file.toString());
-
- channel.write(buffers);
-
- return position;
- }
-
- /**
- * FIXME: Should be package scope.
- */
- public void transferTo(FileHandle handle, long position, int length) throws IOException {
- System.err.println("Transfering data");
- channel.transferTo(position + blocksize, length, handle.channel);
- }
-
- public void complete() throws IOException {
- if (channel.position() % blocksize != 0) {
- System.err.println("Writing data: " + (int)(blocksize - channel.position() % blocksize) + " to file: " + file);
- System.err.println(" to position: " + channel.position());
- System.err.println(" pos % blksz: " + (channel.position() % blocksize));
- System.err.println(" with blocksize: " + blocksize);
- channel.write(ByteBuffer.allocate((int)(blocksize - channel.position() % blocksize)));
- }
- channel.force(true);
- }
-
- public void close() throws IOException {
- System.err.println("Closing file: " + file);
- channel.close();
- }
-
- public String toString() {
- long position = -1;
- try {
- position = channel.position();
- } catch (Exception e) {}
-
- return file.toString() + ":" + position + ":" + log2bs + ":" + seeks;
- }
+ public void close() throws IOException;
}
Modified: projects/xa2/object-pool/src/scheduler/FileHandleFactory.java
===================================================================
--- projects/xa2/object-pool/src/scheduler/FileHandleFactory.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/scheduler/FileHandleFactory.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -21,7 +21,7 @@
throw new IllegalArgumentException("File already exists: " + file);
}
- return new FileHandle(file, new FileOutputStream(file), magic, blocksize);
+ return new FileHandleImpl(file, new FileOutputStream(file), magic, blocksize);
}
public FileHandle openExisting(File file, int magic, int blocksize) throws IOException {
@@ -29,7 +29,7 @@
throw new IllegalArgumentException("File does not exist: " + file);
}
- return new FileHandle(file, new FileInputStream(file), magic, blocksize);
+ return new FileHandleImpl(file, new FileInputStream(file), magic, blocksize);
}
public FileHandle open(File file, int magic, int blocksize) throws IOException {
Added: projects/xa2/object-pool/src/scheduler/FileHandleImpl.java
===================================================================
--- projects/xa2/object-pool/src/scheduler/FileHandleImpl.java (rev 0)
+++ projects/xa2/object-pool/src/scheduler/FileHandleImpl.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,169 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 30th April 2008
+ */
+package scheduler;
+
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+import java.nio.channels.FileChannel;
+
+public class FileHandleImpl implements FileHandle {
+ private File file;
+ private FileChannel channel;
+ private int log2bs;
+
+ private final int blocksize;
+ private long seeks;
+
+ FileHandleImpl(File file, FileChannel channel, int magic, int log2bs) {
+ this.file = file;
+ this.channel = channel;
+ this.log2bs = log2bs;
+ this.blocksize = 0x01 << log2bs;
+ this.seeks = 0;
+ }
+
+ FileHandleImpl(File file, FileOutputStream stream, int magic, int log2bs) throws IOException {
+ this(file, stream.getChannel(), magic, log2bs);
+
+ ByteBuffer bb = ByteBuffer.allocate(blocksize);
+// System.err.println("Allocated header: " + bb.capacity());
+ bb.putInt(magic);
+ bb.putInt(log2bs);
+ bb.position(0);
+ bb.limit(bb.capacity());
+
+ channel.write(bb);
+ }
+
+ FileHandleImpl(File file, FileInputStream stream, int magic, int log2bs) throws IOException {
+ this(file, stream.getChannel(), magic, log2bs);
+
+ if (log2bs < 10) throw new IllegalArgumentException("Attempt to open file with blocksize < 1KB");
+
+ ByteBuffer bb = ByteBuffer.allocate(blocksize);
+ this.channel.read(bb);
+
+ bb.clear();
+ int filemagic = bb.getInt();
+ if (filemagic != magic) {
+ bb.order(bb.order().equals(ByteOrder.BIG_ENDIAN) ? ByteOrder.LITTLE_ENDIAN : ByteOrder.BIG_ENDIAN);
+ bb.clear();
+ filemagic = bb.getInt();
+ if (filemagic == magic) {
+ throw new IllegalArgumentException("Attempt to read file using incorrect endian format");
+ } else {
+ throw new IllegalArgumentException("Bad magic in index buffer: " + filemagic + ", MAGIC=" + magic);
+ }
+ }
+
+ int filebs = bb.getInt();
+ if (filebs != log2bs) {
+ throw new IllegalArgumentException("Attempt to read file(" + file + ") using incorrect log2bs: " + log2bs);
+ }
+ }
+
+ public File getFile() {
+ return file;
+ }
+
+ public FileChannel getChannel() {
+ return channel;
+ }
+
+ public int getLog2BlockSize() {
+ return log2bs;
+ }
+
+ /**
+ * FIXME: These should be package scope.
+ */
+ public Block readBlock(long blockId) throws IOException {
+ // blockId + 1 allows higher levels to ignore the metadata stored in block-0.
+// System.err.printf("FileHandleImpl::readBlock(blockId=%d), file: %s\n", blockId, file.toString());
+ if (channel.position() != ((blockId + 1) << log2bs)) {
+ seeks++;
+ channel.position((blockId + 1) << log2bs);
+ }
+
+ return readBlock();
+ }
+
+ public Block readBlock() throws IOException {
+ Block block = new Block(this, log2bs);
+
+// System.err.println("Reading block from position: " + channel.position());
+ // Block::prepare takes a blockId, we can calculate this from the channel's position.
+ int read = channel.read(block.prepare((channel.position() >> log2bs) - 1));
+ if (read == blocksize) return block;
+ if (read == -1) return null;
+ throw new IllegalStateException("Partial block read");
+ }
+
+ public long writeBlock(Block block) throws IOException {
+ long position = channel.position() - blocksize;
+
+// System.err.printf("Writing block to position: %d in file: %s\n", channel.position(), file.toString());
+ channel.write(block.prepare(position >> log2bs));
+
+ return position;
+ }
+
+ /**
+ * FIXME: Should be package scope.
+ */
+ public long writeBuffers(ByteBuffer[] buffers, int headerSize) throws IOException {
+ long currBlock = channel.position() / blocksize;
+ long hEndBlock = (channel.position() + headerSize) / blocksize;
+ if (currBlock != hEndBlock) {
+ channel.write(ByteBuffer.wrap(new byte[(int)(channel.position() % blocksize)]));
+ channel.position((currBlock + 1) * blocksize);
+ }
+
+ long position = channel.position() - blocksize;
+// System.err.printf("Writing %d buffers to position: %d in file: %s\n", buffers.length, channel.position(), file.toString());
+
+ channel.write(buffers);
+
+ return position;
+ }
+
+ /**
+ * FIXME: Should be package scope.
+ */
+ public void transferTo(Writable handle, long position, int length) throws IOException {
+// System.err.println("Transfering data");
+ channel.transferTo(position + blocksize, length, handle.getChannel());
+ }
+
+ public void complete() throws IOException {
+ if (channel.position() % blocksize != 0) {
+// System.err.println("Writing data: " + (int)(blocksize - channel.position() % blocksize) + " to file: " + file);
+// System.err.println(" to position: " + channel.position());
+// System.err.println(" pos % blksz: " + (channel.position() % blocksize));
+// System.err.println(" with blocksize: " + blocksize);
+ channel.write(ByteBuffer.allocate((int)(blocksize - channel.position() % blocksize)));
+ }
+ channel.force(true);
+ }
+
+ public void close() throws IOException {
+// System.err.println("Closing file: " + file);
+ channel.close();
+ }
+
+ public String toString() {
+ long position = -1;
+ try {
+ position = channel.position();
+ } catch (Exception e) {}
+
+ return file.toString() + ":" + position + ":" + log2bs + ":" + seeks;
+ }
+}
Modified: projects/xa2/object-pool/src/scheduler/IOScheduler.java
===================================================================
--- projects/xa2/object-pool/src/scheduler/IOScheduler.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/scheduler/IOScheduler.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -27,7 +27,7 @@
public FileHandle open(String name, int magic, int blocksize) throws IOException {
File file = new File(dir, name);
- System.err.println("Opening: " + file);
+// System.err.println("Opening: " + file);
return fileHandleFactory.open(file, magic, blocksize);
}
Added: projects/xa2/object-pool/src/scheduler/Writable.java
===================================================================
--- projects/xa2/object-pool/src/scheduler/Writable.java (rev 0)
+++ projects/xa2/object-pool/src/scheduler/Writable.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,38 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 3rd September 2008
+ */
+package scheduler;
+
+import java.io.IOException;
+import java.nio.ByteBuffer;
+import java.nio.channels.FileChannel;
+
+/**
+ * This interface is provided to permit unit-tests to provide test harnesses for the basic IO operation.
+ */
+public interface Writable {
+ /**
+ * Write an array of buffers to this writable, ensuring that the first 'headerSize' bytes do not cross a
+ * block-boundary.
+ *
+ * Note: The header is guaranteed by padding with 0x00 to the next block boundary if the header would
+ * overlap it.
+ *
+ * @param buffers A sequence of buffers to be written to this Writable.
+ * @param headerSize The number of bytes in the header that cannot cross a block boundary.
+ * @return The offset into this writable where the first byte of the first buffer was written.
+ */
+ public long writeBuffers(ByteBuffer[] buffers, int headerSize) throws IOException;
+
+ /**
+ * Write 'length' bytes from 'position' in this writable to the provided handle.
+ */
+ public void transferTo(Writable handle, long position, int length) throws IOException;
+
+ /**
+ * Return the FileChannel associated with this Writable if one exists.
+ */
+ public FileChannel getChannel();
+}
Modified: projects/xa2/object-pool/src/trie/ByteMap.java
===================================================================
--- projects/xa2/object-pool/src/trie/ByteMap.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/trie/ByteMap.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -138,6 +138,22 @@
}
}
+ public T getFirst() {
+ if (data.length == 0) {
+ return null;
+ } else {
+ return data[0];
+ }
+ }
+
+ public T getLast() {
+ if (data.length == 0) {
+ return null;
+ } else {
+ return data[data.length - 1];
+ }
+ }
+
public Iterator<T> iterator() {
return new Iterator<T>() {
private int index = 0;
@@ -171,14 +187,4 @@
block.putShort(low[i]);
}
}
-
- public static ByteMap<T> merge(ByteMap<T> lhs, ByteMap<T> rhs) {
- for (short highI = 0x0000; highI <= 0x8000; highI = highI << 1) {
- if (lhs.high & highI) {
- if (rhs.high & highI) {
- }
- } else if (rhs.high & highI) {
- }
- }
- }
}
Modified: projects/xa2/object-pool/src/trie/DiskTrie.java
===================================================================
--- projects/xa2/object-pool/src/trie/DiskTrie.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/trie/DiskTrie.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -11,6 +11,7 @@
import data.DataEntry;
import data.DataFile;
+import data.IndexEntry;
import scheduler.Block;
import scheduler.FileHandle;
@@ -25,10 +26,11 @@
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.
+ static final byte TYPE_ROOT_LOC = 0x01; // Indicates the following short indicates a branch.
+ static final byte TYPE_BRANCH_TERM = 0x02; // Indicates a trie branch with a termination entry..
+ static final byte TYPE_BRANCH_NOTERM = 0x03; // Indicates a trie branch without a termination entry..
+ static final byte TYPE_LEAF_DATA = 0x04; // Indicates a trie leaf terminating in a single data value.
+ static final byte TYPE_LEAF_INDEX = 0x05; // Indicates a trie leaf terminating in another index block.
// Calculated as the worst case size per entry.
// Assumes a full leaf and branch per entry.
@@ -95,9 +97,12 @@
case TYPE_BRANCH_NOTERM:
nodeMap.put(location, readTrieBranch(indexBlock, false, nodeMap));
break;
- case TYPE_LEAF:
- nodeMap.put(location, readTrieLeaf(indexBlock, data));
+ case TYPE_LEAF_DATA:
+ nodeMap.put(location, readTrieDataLeaf(indexBlock, data));
break;
+ case TYPE_LEAF_INDEX:
+ nodeMap.put(location, readTrieIndexLeaf(indexBlock, data));
+ break;
case TYPE_ROOT_LOC:
indexBlock.getByte(); // Skip padding.
rootLocation = indexBlock.getShort();
@@ -119,7 +124,7 @@
int size = totalIndexSize(root);
space = (short)((indexBlock.getBlockSize() - size - 8) / WORST_CASE_ENTRY_SIZE);
if (space < 0) {
- throw new IllegalStateException("Overfilled CompBlockTrie");
+ throw new IllegalStateException("Overfilled DiskTrie");
} else if (space == 0) {
return false;
}
@@ -156,8 +161,8 @@
private static Map<Class, TrieNodeWriter> writerMap = new HashMap<Class, TrieNodeWriter>();
static {
- writerMap.put(TrieBranch.class, new TrieBranchWriter());
- writerMap.put(TrieLeaf.class, new TrieLeafWriter());
+ writerMap.put(TrieNode.TrieBranch.class, new TrieBranchWriter());
+ writerMap.put(TrieNode.TrieLeaf.class, new TrieLeafWriter());
}
protected static void writeTrieNode(TrieNode node, Block index, DataFile data,
@@ -178,7 +183,7 @@
private static class TrieBranchWriter implements TrieNodeWriter {
public void write(TrieNode node, Block index, DataFile data, Map<TrieNode, Short> locationMap) throws IOException {
- TrieBranch branch = (TrieBranch)node;
+ TrieNode.TrieBranch branch = (TrieNode.TrieBranch)node;
if (branch.term != null) {
writeTrieNode(branch.term, index, data, locationMap);
}
@@ -203,24 +208,35 @@
private static class TrieLeafWriter implements TrieNodeWriter {
public void write(TrieNode node, Block index, DataFile data, Map<TrieNode, Short> locationMap) throws IOException {
- TrieLeaf leaf = (TrieLeaf)node;
+ TrieNode.TrieLeaf leaf = (TrieNode.TrieLeaf)node;
+ switch (leaf.entry.getTrieEntryType()) {
+ case DATA:
+ data.write(leaf.entry.asDataEntry());
+ locationMap.put(leaf, (short)index.position());
+ index.putByte(TYPE_LEAF_DATA);
+ index.putByte((byte)0xFF); // Pad to 16-bit aligned.
+ index.putLong(leaf.entry.asDataEntry().getLocation());
- long keyLocation = data.write(leaf.entry);
+ break;
+ case INDEX:
+ locationMap.put(leaf, (short)index.position());
+ index.putByte(TYPE_LEAF_INDEX);
+ index.putByte((byte)0xFF); // Pad to 16-bit aligned.
+ index.putLong(leaf.entry.asIndexEntry().getDataLocation());
+ index.putLong(leaf.entry.asIndexEntry().getIndexOffset());
- locationMap.put(leaf, (short)index.position());
- index.putByte(TYPE_LEAF);
- index.putByte((byte)0xFF); // Pad to 16-bit aligned.
- index.putLong(keyLocation);
+ break;
+ }
}
}
- private TrieBranch readTrieBranch(Block index, boolean hasTerm, Map<Short, TrieNode> nodeMap) throws IOException {
- TrieBranch branch = new TrieBranch();
+ private TrieNode.TrieBranch readTrieBranch(Block index, boolean hasTerm, Map<Short, TrieNode> nodeMap) throws IOException {
+ TrieNode.TrieBranch branch = new TrieNode.TrieBranch();
index.getByte(); // skip padding.
branch.offset = index.getInt();
if (hasTerm) {
- branch.term = (TrieLeaf)nodeMap.get(index.getShort());
+ branch.term = (TrieNode.TrieLeaf)nodeMap.get(index.getShort());
}
branch.children = new ByteMap<TrieNode>(index, nodeMap);
if (branch.term == null) {
@@ -237,19 +253,29 @@
return branch;
}
- private TrieLeaf readTrieLeaf(Block index, DataFile dataFile) throws IOException {
+ private TrieNode.TrieLeaf readTrieDataLeaf(Block index, DataFile dataFile) throws IOException {
index.getByte(); // skip padding.
long keyLocation = index.getLong();
DataEntry entry = dataFile.getEntry(keyLocation);
- return new TrieLeaf(entry);
+ return new TrieNode.TrieLeaf(entry);
}
+ private TrieNode.TrieLeaf readTrieIndexLeaf(Block index, DataFile dataFile) throws IOException {
+ index.getByte(); // skip padding.
+ long dataLocation = index.getLong();
+ long indexLocation = index.getLong();
+
+ IndexEntry entry = new IndexEntry(dataFile.getEntry(dataLocation), indexLocation);
+
+ return new TrieNode.TrieLeaf(entry);
+ }
+
private static Map<Class, TrieNodeSizer> sizerMap = new HashMap<Class, TrieNodeSizer>();
static {
- sizerMap.put(TrieBranch.class, new TrieBranchSizer());
- sizerMap.put(TrieLeaf.class, new TrieLeafSizer());
+ sizerMap.put(TrieNode.TrieBranch.class, new TrieBranchSizer());
+ sizerMap.put(TrieNode.TrieLeaf.class, new TrieLeafSizer());
}
protected static int totalIndexSize(TrieNode node) {
@@ -266,12 +292,12 @@
}
private static class TrieBranchSizer implements TrieNodeSizer {
- protected int memSize(TrieBranch branch) {
+ protected int memSize(TrieNode.TrieBranch branch) {
return 4 + 1 + 1 + branch.children.memSize() + (branch.term == null ? 0 : 2);
}
public int indexSize(TrieNode node) {
- TrieBranch branch = (TrieBranch)node;
+ TrieNode.TrieBranch branch = (TrieNode.TrieBranch)node;
int total = memSize(branch);
if (branch.term != null) {
total += totalIndexSize(branch.term);
@@ -284,7 +310,7 @@
}
public int dataSize(TrieNode node) {
- TrieBranch branch = (TrieBranch)node;
+ TrieNode.TrieBranch branch = (TrieNode.TrieBranch)node;
int total = 0;
if (branch.term != null) {
total += totalDataSize(branch.term);
@@ -299,12 +325,13 @@
private static class TrieLeafSizer implements TrieNodeSizer {
public int indexSize(TrieNode node) {
- return 1 + 1 + 8;
+ TrieNode.TrieLeaf leaf = (TrieNode.TrieLeaf)node;
+ return 2 + leaf.indexSize();
}
public int dataSize(TrieNode node) {
- TrieLeaf leaf = (TrieLeaf)node;
- return leaf.entry.totalSize();
+ TrieNode.TrieLeaf leaf = (TrieNode.TrieLeaf)node;
+ return leaf.dataSize();
}
}
}
Modified: projects/xa2/object-pool/src/trie/DiskTrieTest.java
===================================================================
--- projects/xa2/object-pool/src/trie/DiskTrieTest.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/trie/DiskTrieTest.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -17,6 +17,8 @@
import java.nio.channels.FileChannel;
import data.DataEntry;
+import data.TrieEntry;
+import data.Key;
import index.IndexFile;
import scheduler.FileHandleFactory;
import scheduler.IOScheduler;
@@ -108,8 +110,8 @@
for (byte[] key : namesMap.keySet()) {
boolean found = false;
for (DiskTrie t : tries) {
- long value = t.lookup(DataEntry.getKey(key), valid);
- if (valid[0] && value == namesMap.get(key)) {
+ TrieEntry value = t.lookup(new Key(key), valid);
+ if (valid[0] && value.asDataEntry().getValue() == namesMap.get(key)) {
found = true;
break;
}
@@ -119,8 +121,8 @@
}
found = false;
for (DiskTrie t : readTries) {
- long value = t.lookup(DataEntry.getKey(key), valid);
- if (valid[0] && value == namesMap.get(key)) {
+ TrieEntry value = t.lookup(new Key(key), valid);
+ if (valid[0] && value.asDataEntry().getValue() == namesMap.get(key)) {
found = true;
break;
}
@@ -280,8 +282,8 @@
int i = 0;
boolean found = false;
for (DiskTrie t : readTries) {
- long value = t.lookup(DataEntry.getKey(keyBytes.getBytes()), valid);
- if (valid[0] && value == namesMap.get(keyBytes)) {
+ TrieEntry value = t.lookup(new Key(keyBytes.getBytes()), valid);
+ if (valid[0] && value.asDataEntry().getValue() == namesMap.get(keyBytes)) {
found = true;
break;
}
Modified: projects/xa2/object-pool/src/trie/MemoryTrie.java
===================================================================
--- projects/xa2/object-pool/src/trie/MemoryTrie.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/trie/MemoryTrie.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -7,7 +7,8 @@
import java.io.IOException;
-import data.DataEntry;
+import data.Entry;
+import data.TrieEntry;
/**
* Implements an in-memory trie - uses ByteMaps to implement trie nodes.
@@ -22,21 +23,21 @@
this.root = null;
}
- public boolean insert(DataEntry entry) {
+ public boolean insert(TrieEntry entry) {
if (root == null) {
- root = new TrieLeaf(entry);
+ root = new TrieNode.TrieLeaf(entry);
} else {
if (!root.insert(entry)) {
- root = new TrieBranch(root, entry);
+ root = new TrieNode.TrieBranch(root, entry);
}
}
return true;
}
- public long lookup(DataEntry key) throws NotFound {
+ public TrieEntry lookup(Entry key) throws NotFound {
boolean[] valid = new boolean[1];
- long result = lookup(key, valid);
+ TrieEntry result = lookup(key, valid);
if (valid[0]) {
return result;
} else {
@@ -45,221 +46,27 @@
}
- public long lookup(DataEntry key, boolean[] valid) {
+ public TrieEntry lookup(Entry key, boolean[] valid) {
if (root == null) {
valid[0] = false;
- return 0;
+ return null;
} else {
return root.lookup(key, valid);
}
}
- protected abstract static class TrieNode {
- protected TrieLeaf aLeaf;
-
- /**
- * @return false if we need to insert key above this node.
- */
- public boolean insert(DataEntry entry) {
- return insert(new TrieLeaf(entry), 0);
+ /**
+ * Returns null if a valid entry is not found, otherwise returns the node with the greatest entry still
+ * less than the key.
+ *
+ * If we assume each entry contains multiple keys and is indexed by the min-entry in each key-set; this will
+ * identify the entry that contains the specified key if the key exists at all.
+ */
+ public TrieNode.TrieLeaf lookupGreatestLessThan(Entry entry) throws IOException {
+ if (root == null) {
+ return null;
}
- public long lookup(DataEntry key, boolean[] valid) {
- return lookup(key, 0, valid);
- }
-
- protected abstract boolean insert(TrieLeaf node, int parentLcd);
- protected abstract long lookup(DataEntry key, int parentLcd, boolean[] valid);
-
- protected static boolean regionMatches(DataEntry lhs, int lhsOff, DataEntry rhs, int rhsOff, int len) {
- if (lhsOff < 0 || rhsOff < 0) {
- return false;
- }
- if (lhs.dataSize() < lhsOff + len || rhs.dataSize() < rhsOff + len) {
- return false;
- }
-
- try {
- int cmp = lhs.slice(lhsOff, len).compareTo(rhs.slice(rhsOff, len));
-
- return (cmp == 0);
- } catch (IOException ei) {
- throw new IllegalStateException("Failed to compare entries", ei);
- }
- }
+ return root.lookupGreatestLessThan(entry, 0);
}
-
- protected static class TrieBranch extends TrieNode {
- protected int offset;
- protected ByteMap<TrieNode> children;
- protected TrieLeaf term;
-
- protected TrieBranch() {}
-
- public TrieBranch(DataEntry entry) {
- this.children = new ByteMap<TrieNode>();
- this.term = new TrieLeaf(entry);
- this.offset = term.entry.dataSize();
- this.aLeaf = this.term;
- }
-
- public TrieBranch(TrieNode oldRoot, DataEntry entry) {
- this(oldRoot, new TrieLeaf(entry));
- }
-
- private TrieBranch(TrieNode oldNode, TrieLeaf newNode) {
- super();
- assert oldNode != null;
- assert newNode != null;
-
- offset = 0;
- children = new ByteMap<TrieNode>();
- term = null;
-
- // as every child node shares a common lcp, any child will suffice when preparing the new
- // lcp/offset of the new node.
- aLeaf = newNode;
-
- try {
- DataEntry lhs = oldNode.aLeaf.entry.rewind();
- DataEntry rhs = newNode.entry.rewind();
-
- // FIXME: Replace this loop with a compareTo.
- int i = 0;
- while (i < lhs.dataSize() && i < rhs.dataSize()) {
- byte lb = lhs.get();
- byte rb = rhs.get();
- if (lb != rb) {
- offset = i;
- children.insert(lb, oldNode);
- children.insert(rb, newNode);
-
- return; // Escape here.
- }
- i++;
- }
-
- if (i < lhs.dataSize()) {
- offset = i;
- children.insert(lhs.get(), oldNode);
- term = newNode;
- } else if (i < rhs.dataSize()) {
- if (oldNode instanceof TrieLeaf) {
- offset = i;
- children.insert(rhs.get(), newNode);
- term = (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");
- }
- } catch (IOException ei) {
- throw new IllegalStateException("Unable to insert entry into trie", ei);
- }
- }
-
- protected boolean insert(TrieLeaf node, int parentLcp) {
- if (!regionMatches(aLeaf.entry, parentLcp, node.entry, parentLcp, offset - parentLcp)) {
- return false;
- } else {
- // new node matches the lcp of this node.
- if (node.entry.dataSize() == offset) {
- // new node is expected to terminate here.
- if (term == null) {
- term = node;
- } else {
- return term.insert(node, offset);
- }
- } else {
- try {
- // new node is expected to terminate in one of this nodes children.
- TrieNode child = children.lookup(node.entry.get(offset));
- if (child == null) {
- // this is the first node to be inserted on this branching key.
- children.insert(node.entry.get(offset), node);
- } else {
- // there is an existing child node branching on this branching key.
- if (!child.insert(node, offset)) {
- children.insert(node.entry.get(offset), new TrieBranch(child, node));
- }
- }
- } catch (IOException ei) {
- throw new IllegalStateException("Failed to insert leaf into trie", ei);
- }
- }
-
- return true;
- }
- }
-
- protected long lookup(DataEntry key, int parentLcd, boolean[] valid) {
- if (!regionMatches(aLeaf.entry, 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.
- valid[0] = false;
- return 0;
- } else {
- // new node matches the lcp of this node.
- TrieNode child;
- if (key.dataSize() == offset) {
- // new node is expected to terminate here.
- if (term != null) {
- valid[0] = true;
- return term.entry.getValue();
- } else {
- valid[0] = false;
- return 0;
- }
- } else {
- try {
- // new node is expected to terminate in one of this nodes children.
- child = children.lookup(key.get(offset));
- if (child != null) {
- return child.lookup(key, offset, valid);
- } else {
- valid[0] = false;
- return 0;
- }
- } catch (IOException ei) {
- throw new IllegalStateException("Failed to lookup entry in trie", ei);
- }
- }
- }
- }
-
- public String toString() {
- return "Trie-BRANCH[" + (term != null) + " on " + offset + " with " + children.size() + " and aLeaf[" + aLeaf + "]";
- }
- }
-
- protected static class TrieLeaf extends TrieNode {
- final DataEntry entry;
-
- protected TrieLeaf(DataEntry entry) {
- this.entry = entry;
- this.aLeaf = this;
- }
-
- protected boolean insert(TrieLeaf node, int parentLcp) {
- if (entry.dataSize() != node.entry.dataSize()) {
- return false;
- } else if (!regionMatches(entry, parentLcp, node.entry, parentLcp, node.entry.dataSize() - parentLcp)) {
- return false;
- } else if (entry.getValue() == node.entry.getValue()) {
- return true; // Duplicate key/value pair.
- } else {
- throw new IllegalArgumentException("Attempt to insert multiple values for same key");
- }
- }
-
- protected long lookup(DataEntry key, int parentLcd, boolean[] valid) {
- assert regionMatches(this.entry, 0, key, 0, key.dataSize());
- valid[0] = true;
- return entry.getValue();
- }
-
- public String toString() {
- return "Trie-LEAF: " + entry;
- }
- }
}
Modified: projects/xa2/object-pool/src/trie/MemoryTrieUnitTest.java
===================================================================
--- projects/xa2/object-pool/src/trie/MemoryTrieUnitTest.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/trie/MemoryTrieUnitTest.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -22,6 +22,7 @@
import junit.framework.TestSuite;
import data.DataEntry;
+import data.Key;
/**
* Basic tests of the MemoryTrie
@@ -44,7 +45,6 @@
suite.addTest(new MemoryTrieUnitTest(new File("bulk/random70M"), 5000, 10));
suite.addTest(new MemoryTrieUnitTest(new File("/dev/urandom")));
- suite.addTest(new MemoryTrieUnitTest(new File("/dev/urandom")));
return suite;
}
@@ -78,7 +78,7 @@
Set<DataEntry> namesSet = new HashSet<DataEntry>();
MemoryTrie namesTrie = new MemoryTrie();
- System.out.println("Inserting lines from " + file);
+ System.err.println("Inserting lines from " + file);
BufferedReader names = new BufferedReader(new FileReader(file));
long n = 0;
String name = names.readLine();
@@ -93,16 +93,16 @@
long _endInsert = System.currentTimeMillis();
names.close();
- System.out.println("Checking " + n + " lines from " + file);
+ System.err.println("Checking " + n + " lines from " + file);
long _startLookup = System.currentTimeMillis();
for (DataEntry key : namesSet) {
- if (namesTrie.lookup(key) != key.getValue()) {
+ if (namesTrie.lookup(key).asDataEntry().getValue() != key.getValue()) {
throw new IllegalStateException("Trie doesn't match Map");
}
}
long _endLookup = System.currentTimeMillis();
- System.out.println("Test Succeeded with " + file +
+ System.err.println("Test Succeeded with " + file +
" insert:" + (_endInsert - _startInsert) + " lookup:" + (_endLookup - _startLookup));
}
@@ -132,7 +132,7 @@
Map<Bytes, Long> namesMap = new HashMap<Bytes, Long>();
MemoryTrie namesTrie = new MemoryTrie();
- System.out.println("Inserting random bytes from " + file);
+ System.err.println("Inserting random bytes from " + file);
FileChannel chan = new FileInputStream(file).getChannel();
ByteBuffer buffer = ByteBuffer.allocate(134*1024);
@@ -167,7 +167,7 @@
_avlL += key.length;
nL++;
- if (namesTrie.lookup(DataEntry.getEntry(key, 0)) != n) {
+ if (namesTrie.lookup(new Key(key)).asDataEntry().getValue() != n) {
throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
}
}
@@ -185,26 +185,26 @@
_avlS += key.length;
nS++;
- if (namesTrie.lookup(DataEntry.getEntry(key, 0)) != n) {
+ if (namesTrie.lookup(new Key(key)).asDataEntry().getValue() != n) {
throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
}
}
}
}
long _endInsert = System.currentTimeMillis();
- System.out.println("Input " + namesMap.size() + " entries");
- System.out.printf(" %d long entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
+ System.err.println("Input " + namesMap.size() + " entries");
+ System.err.printf(" %d long entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
nL, (_avlL / nL), _aggregateL, (_aggregateL * 1000 / nL), (_aggregateL * 1000000 / _avlL));
- System.out.printf(" %d short entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
+ System.err.printf(" %d short entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
nS, (_avlS / nS), _aggregateS, (_aggregateS * 1000 / nS), (_aggregateS * 1000000 / _avlS));
- System.out.println(chan.position() + " bytes read from " + file);
+ System.err.println(chan.position() + " bytes read from " + file);
chan.close();
long _startLookup = System.currentTimeMillis();
- System.out.println("Checking random bytes from " + file);
+ System.err.println("Checking random bytes from " + file);
for (Bytes k : namesMap.keySet()) {
int i = 0;
- if (namesTrie.lookup(DataEntry.getEntry(k.bytes, 0)) != namesMap.get(k)) {
+ if (namesTrie.lookup(new Key(k.bytes)).asDataEntry().getValue() != namesMap.get(k)) {
throw new IllegalStateException("Trie doesn't match Map on entry: " + i + " key:" +
Arrays.toString(k.bytes) + " value: " + namesTrie.lookup(DataEntry.getEntry(k.bytes, 0)) +
" value': " + namesMap.get(k));
@@ -213,7 +213,7 @@
}
long _endLookup = System.currentTimeMillis();
- System.out.println("Test Succeeded with " + file +
+ System.err.println("Test Succeeded with " + file +
" insert:" + (_endInsert - _startInsert) + " lookup:" + (_endLookup - _startLookup));
}
@@ -222,7 +222,7 @@
Map<Bytes, Long> namesMap = new HashMap<Bytes, Long>();
MemoryTrie namesTrie = new MemoryTrie();
- System.out.println("Inserting random bytes from " + file + " to max records " + max + " with small " + small);
+ System.err.println("Inserting random bytes from " + file + " to max records " + max + " with small " + small);
FileChannel chan = new FileInputStream(file).getChannel();
ByteBuffer buffer = ByteBuffer.allocate(134*1024);
@@ -257,7 +257,7 @@
_avlL += key.length;
nL++;
- if (namesTrie.lookup(DataEntry.getEntry(key, 0)) != n) {
+ if (namesTrie.lookup(new Key(key)).asDataEntry().getValue() != n) {
throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
}
}
@@ -275,26 +275,26 @@
_avlS += key.length;
nS++;
- if (namesTrie.lookup(DataEntry.getEntry(key, 0)) != n) {
+ if (namesTrie.lookup(new Key(key)).asDataEntry().getValue() != n) {
throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
}
}
}
}
long _endInsert = System.currentTimeMillis();
- System.out.println("Input " + namesMap.size() + " entries");
- System.out.printf(" %d long entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
+ System.err.println("Input " + namesMap.size() + " entries");
+ System.err.printf(" %d long entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
nL, (_avlL / nL), _aggregateL, (_aggregateL * 1000 / nL), (_aggregateL * 1000000 / _avlL));
- System.out.printf(" %d short entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
+ System.err.printf(" %d short entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
nS, (_avlS / nS), _aggregateS, (_aggregateS * 1000 / nS), (_aggregateS * 1000000 / _avlS));
- System.out.println(chan.position() + " bytes read from " + file);
+ System.err.println(chan.position() + " bytes read from " + file);
chan.close();
long _startLookup = System.currentTimeMillis();
- System.out.println("Checking random bytes from " + file);
+ System.err.println("Checking random bytes from " + file);
for (Bytes k : namesMap.keySet()) {
int i = 0;
- if (namesTrie.lookup(DataEntry.getEntry(k.bytes, 0)) != namesMap.get(k)) {
+ if (namesTrie.lookup(new Key(k.bytes)).asDataEntry().getValue() != namesMap.get(k)) {
throw new IllegalStateException("Trie doesn't match Map on entry: " + i + " key:" +
Arrays.toString(k.bytes) + " value: " + namesTrie.lookup(DataEntry.getEntry(k.bytes, 0)) +
" value': " + namesMap.get(k));
@@ -303,7 +303,7 @@
}
long _endLookup = System.currentTimeMillis();
- System.out.println("Test Succeeded with " + file +
+ System.err.println("Test Succeeded with " + file +
" insert:" + (_endInsert - _startInsert) + " lookup:" + (_endLookup - _startLookup));
}
@@ -311,7 +311,7 @@
Map<Bytes, Long> namesMap = new HashMap<Bytes, Long>();
MemoryTrie namesTrie = new MemoryTrie();
- System.out.println("Inserting random bytes from " + file);
+ System.err.println("Inserting random bytes from " + file);
FileChannel chan = new FileInputStream(file).getChannel();
ByteBuffer buffer = ByteBuffer.allocate(8*1024*1024);
@@ -333,7 +333,7 @@
long _avlSS = 0;
int nSS = 0;
- for (int i = 0; i < 200; i++) {
+ for (int i = 0; i < 100; i++) {
if (buffer.remaining() < 2*1024*1024 && chan.read(buffer.compact()) == -1) {
break;
}
@@ -352,7 +352,7 @@
_avlLL += key.length;
nLL++;
- if (namesTrie.lookup(DataEntry.getEntry(key, 0)) != n) {
+ if (namesTrie.lookup(new Key(key)).asDataEntry().getValue() != n) {
throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
}
}
@@ -370,7 +370,7 @@
_avlL += key.length;
nL++;
- if (namesTrie.lookup(DataEntry.getEntry(key, 0)) != n) {
+ if (namesTrie.lookup(new Key(key)).asDataEntry().getValue() != n) {
throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
}
}
@@ -388,7 +388,7 @@
_avlS += key.length;
nS++;
- if (namesTrie.lookup(DataEntry.getEntry(key, 0)) != n) {
+ if (namesTrie.lookup(new Key(key)).asDataEntry().getValue() != n) {
throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
}
}
@@ -406,7 +406,7 @@
_avlSS += key.length;
nSS++;
- if (namesTrie.lookup(DataEntry.getEntry(key, 0)) != n) {
+ if (namesTrie.lookup(new Key(key)).asDataEntry().getValue() != n) {
throw new IllegalStateException("lookup failed key: " + Arrays.toString(key) + " value: " + n);
}
}
@@ -415,22 +415,22 @@
}
}
long _endInsert = System.currentTimeMillis();
- System.out.println("Input " + namesMap.size() + " entries");
- System.out.printf(" %d very long entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
+ System.err.println("Input " + namesMap.size() + " entries");
+ System.err.printf(" %d very long entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
nLL, (_avlLL / nLL), _aggregateLL, (_aggregateLL * 1000 / nLL), (_aggregateLL * 1000000 / _avlLL));
- System.out.printf(" %d long entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
+ System.err.printf(" %d long entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
nL, (_avlL / nL), _aggregateL, (_aggregateL * 1000 / nL), (_aggregateL * 1000000 / _avlL));
- System.out.printf(" %d short entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
+ System.err.printf(" %d short entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
nS, (_avlS / nS), _aggregateS, (_aggregateS * 1000 / nS), (_aggregateS * 1000000 / _avlS));
- System.out.printf(" %d very short entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
+ System.err.printf(" %d very short entries ave: %d in: %dms; ave %dus per entry, %dns per byte\n",
nSS, (_avlSS / nSS), _aggregateSS, (_aggregateSS * 1000 / nSS), (_aggregateSS * 1000000 / _avlSS));
chan.close();
long _startLookup = System.currentTimeMillis();
- System.out.println("Checking random bytes from " + file);
+ System.err.println("Checking random bytes from " + file);
for (Bytes k : namesMap.keySet()) {
int i = 0;
- if (namesTrie.lookup(DataEntry.getEntry(k.bytes, 0)) != namesMap.get(k)) {
+ if (namesTrie.lookup(new Key(k.bytes)).asDataEntry().getValue() != namesMap.get(k)) {
throw new IllegalStateException("Trie doesn't match Map on entry: " + i + " key:" +
Arrays.toString(k.bytes) + " value: " + namesTrie.lookup(DataEntry.getEntry(k.bytes, 0)) +
" value': " + namesMap.get(k));
@@ -439,7 +439,7 @@
}
long _endLookup = System.currentTimeMillis();
- System.out.println("Test Succeeded with " + file +
+ System.err.println("Test Succeeded with " + file +
" insert:" + (_endInsert - _startInsert) + " lookup:" + (_endLookup - _startLookup));
}
}
Modified: projects/xa2/object-pool/src/trie/OnesTable.java
===================================================================
--- projects/xa2/object-pool/src/trie/OnesTable.java 2008-09-04 20:14:44 UTC (rev 1237)
+++ projects/xa2/object-pool/src/trie/OnesTable.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -46,7 +46,8 @@
static {
try {
- FileChannel fc = new FileInputStream("OnesTable.dat").getChannel();
+ String datafile = System.getProperty("org.mulgara.trie.OnesTable", "OnesTable.dat");
+ FileChannel fc = new FileInputStream(datafile).getChannel();
shortOnesTable = new byte[64*1024];
fc.read(ByteBuffer.wrap(shortOnesTable));
onesTable = new byte[64*1024 * 2*256];
Added: projects/xa2/object-pool/src/trie/TrieNode.java
===================================================================
--- projects/xa2/object-pool/src/trie/TrieNode.java (rev 0)
+++ projects/xa2/object-pool/src/trie/TrieNode.java 2008-09-05 05:45:15 UTC (rev 1238)
@@ -0,0 +1,375 @@
+/*
+ * Copyright Topaz Foundation 2008
+ * Author Andrae Muys
+ * Date 29th August 2008
+ */
+package trie;
+
+import java.io.IOException;
+
+import data.Entry;
+import data.TrieEntry;
+
+/**
+ * Implements an in-memory trie - uses ByteMaps to implement trie nodes.
+ *
+ * FIXME: Need to introduce a suitable exception type here so I'm not wrapping IOExceptions as
+ * IllegalStateExceptions.
+ */
+public abstract class TrieNode {
+ protected TrieLeaf aLeaf;
+
+ /**
+ * @return false if we need to insert key above this node.
+ */
+ public boolean insert(TrieEntry entry) {
+ return insert(new TrieLeaf(entry), 0);
+ }
+
+ public TrieEntry lookup(Entry key, boolean[] valid) {
+ return lookup(key, 0, valid);
+ }
+
+ public abstract TrieLeaf getMaxLeaf();
+
+ protected abstract boolean insert(TrieLeaf node, int parentLcp);
+ protected abstract TrieEntry lookup(Entry key, int parentLcp, boolean[] valid);
+ protected abstract TrieLeaf lookupGreatestLessThan(Entry key, int pOff);
+
+ // The current approach of checking aLeaf at each level, instead of probing for the best Approx match, and
+ // using that to provide aLeaf for the matching lcp in a second pass may prove inefficient due to the need
+ // to fetch multiple dataentries per pass. If this proves to be the case lookupApprox can be used to
+ // perform the initial probe, and then passed to lookupLGT to provide the LCP.
+ //
+ // protected abstract TrieLeaf lookupApprox(Entry keybest);
+
+ protected static boolean regionMatches(Entry lhs, int lhsOff, Entry rhs, int rhsOff, int len) {
+ if (lhsOff < 0 || rhsOff < 0) {
+ return false;
+ }
+ if (lhs.keySize() < lhsOff + len || rhs.keySize() < rhsOff + len) {
+ return false;
+ }
+
+ try {
+ int cmp = lhs.keySlice(lhsOff, len).compareTo(rhs.keySlice(rhsOff, len));
+
+ return (cmp == 0);
+ } catch (IOException ei) {
+ throw new IllegalStateException("Failed to compare entries", ei);
+ }
+ }
+
+ protected static int regionCompare(Entry lhs, Entry rhs, int offset, int len) {
+ if (offset < 0 || len < 0) {
+ throw new IllegalArgumentException("Negative slice params passed to compare (" + offset + ", " + len + ")");
+ } else if (lhs.keySize() < offset && rhs.keySize() < offset) {
+ throw new IllegalArgumentException("Insufficient data for offset:" + offset +
+ " keySizes:(" + lhs.keySize() + ", " + rhs.keySize() + ")");
+ }
+
+ try {
+ if (lhs.keySize() < offset + len) {
+ return lhs.keySlice(offset, lhs.keySize() - offset).compareTo(rhs.keySlice(offset, len));
+ } else if (rhs.keySize() < offset + len) {
+ return lhs.keySlice(offset, len).compareTo(rhs.keySlice(offset, rhs.keySize() - offset));
+ } else {
+ return lhs.keySlice(offset, len).compareTo(rhs.keySlice(offset, len));
+ }
+ } catch (IOException ei) {
+ throw new IllegalStateException("Failed to compare entries", ei);
+ }
+ }
+
+ protected static class TrieBranch extends TrieNode {
+ protected int offset;
+ protected ByteMap<TrieNode> children;
+ protected TrieLeaf term;
+
+ protected TrieBranch() {}
+
+ public TrieBranch(TrieEntry entry) {
+ this.children = new ByteMap<TrieNode>();
+ this.term = new TrieLeaf(entry);
+ this.offset = term.entry.keySize();
+ this.aLeaf = this.term;
+ }
+
+ public TrieBranch(TrieNode oldRoot, TrieEntry entry) {
+ this(oldRoot, new TrieLeaf(entry));
+ }
+
+ private TrieBranch(TrieNode oldNode, TrieLeaf newNode) {
+ super();
+ assert oldNode != null;
+ assert newNode != null;
+
+ offset = 0;
+ children = new ByteMap<TrieNode>();
+ term = null;
+
+ // as every child node shares a common lcp, any child will suffice when preparing the new
+ // lcp/offset of the new node.
+ aLeaf = newNode;
+
+ try {
+ Entry lhs = oldNode.aLeaf.entry.rewind();
+ Entry rhs = newNode.entry.rewind();
+
+ // FIXME: Replace this loop with a compareTo.
+ int i = 0;
+ while (i < lhs.keySize() && i < rhs.keySize()) {
+ byte lb = lhs.get();
+ byte rb = rhs.get();
+ if (lb != rb) {
+ offset = i;
+ children.insert(lb, oldNode);
+ children.insert(rb, newNode);
+
+ return; // Escape here.
+ }
+ i++;
+ }
+
+ if (i < lhs.keySize()) {
+ offset = i;
+ children.insert(lhs.get(), oldNode);
+ term = newNode;
+ } else if (i < rhs.keySize()) {
+ if (oldNode instanceof TrieLeaf) {
+ offset = i;
+ children.insert(rhs.get(), newNode);
+ term = (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");
+ }
+ } catch (IOException ei) {
+ throw new IllegalStateException("Unable to insert entry into trie", ei);
+ }
+ }
+
+ protected boolean insert(TrieLeaf node, int parentLcp) {
+ if (!regionMatches(aLeaf.entry, parentLcp, node.entry, parentLcp, offset - parentLcp)) {
+ return false;
+ } else {
+ // new node matches the lcp of this node.
+ if (node.entry.keySize() == offset) {
+ // new node is expected to terminate here.
+ if (term == null) {
+ term = node;
+ } else {
+ return term.insert(node, offset);
+ }
+ } else {
+ try {
+ // new node is expected to terminate in one of this nodes children.
+ TrieNode child = children.lookup(node.entry.get(offset));
+ if (child == null) {
+ // this is the first node to be inserted on this branching key.
+ children.insert(node.entry.get(offset), node);
+ } else {
+ // there is an existing child node branching on this branching key.
+ if (!child.insert(node, offset)) {
+ children.insert(node.entry.get(offset), new TrieBranch(child, node));
+ }
+ }
+ } catch (IOException ei) {
+ throw new IllegalStateException("Failed to insert leaf into trie", ei);
+ }
+ }
+
+ return true;
+ }
+ }
+
+ protected TrieEntry lookup(Entry key, int parentLcp, boolean[] valid) {
+ if (!regionMatches(aLeaf.entry, parentLcp, key, parentLcp, offset - parentLcp)) {
+ //FIXME: I need to migrate this to the end of the search to avoid needing access to the key at each level.
+ valid[0] = false;
+ return null;
+ } else {
+ // new node matches the lcp of this node.
+ TrieNode child;
+ if (key.keySize() == offset) {
+ // new node is expected to terminate here.
+ if (term != null) {
+ valid[0] = true;
+ return term.entry;
+ } else {
+ valid[0] = false;
+ return null;
+ }
+ } else {
+ try {
+ // new node is expected to terminate in one of this nodes children.
+ child = children.lookup(key.get(offset));
+ if (child != null) {
+ return child.lookup(key, offset, valid);
+ } else {
+ valid[0] = false;
+ return null;
+ }
+ } catch (IOException ei) {
+ throw new IllegalStateException("Failed to lookup entry in trie", ei);
+ }
+ }
+ }
+ }
+
+ /* Enable this and integrate to reduce data-entry lookups when lookups become a performance issue.
+ protected TrieLeaf lookupApprox(Key key) {
+ if (key.keySize() <= offset) {
+ // Children > key; This-node <= key; Ancestors < key.
+ return term; // Note: this may be null, in which case it devolves upon the parent.
+ } else {
+ try {
+ // new node is expected to terminate in one of this nodes children.
+ TrieNode child = children.lookup(key.get(offset));
+ TrieNode best;
+ if (child != null) {
+ // There is a child matching this key at offset, so initially assume the key is in the child and
+ // recurse.
+ best = child.lookupApprox(key);
+ if (best != null) {
+ // If best != null then (assuming lcp also matches) we have found match (<=) under the child.
+ return best;
+ } else if (term != null) {
+ // Otherwise we have proven that it is impossible for anything under child to be <= key if our
+ // lcp assumption is correct. So the only viable matches will be exact 'term' matches in this
+ // or an ancestor. So return 'term' if it exists
+ return term;
+ } else {
+ // Defer to the parent for partial match.
+ return null;
+ }
+ } else {
+ // There is no child matching this key at offset, so we need to consider the closest match less-than
+ // key.
+ TrieNode best = children.lookupGreatestLessThan(key.get(offset));
+ if (best != null) {
+ // If there is a child less-than key, then as we have eliminated equality, the greatest
+ // less-than key will be the max-leaf of this child.
+ return best.getMaxLeaf();
+ } else if (term != null) {
+ // No child less-than key, so return 'term'...
+ return term;
+ } else {
+ // ...or devolve upon parent.
+ return null;
+ }
+ }
+ } catch (IOException ei) {
+ throw new IllegalStateException("Failed to lookup entry in trie", ei);
+ }
+ }
+ }
+ */
+
+ protected TrieLeaf lookupGreatestLessThan(Entry key, int parentLcp) {
+ try {
+ int cmp = regionCompare(aLeaf.entry, key, parentLcp, offset - parentLcp);
+ if (cmp < 0) {
+ // lcp < key
+ // Any node above, at, or below this is valid, so we will find the key in the max-node.
+ return getMaxLeaf();
+ } else if (cmp == 0) {
+ if (key.keySize() == offset) {
+ // lcp === key
+ return term; // if null this devolves to parent's term.
+ } else {
+ // lcp ~== key
+ byte keyByte = key.get(offset);
+ for (byte k = keyByte; k > 0; k--) {
+ TrieNode child = children.lookup(k);
+ if (child != null) {
+ return child.lookupGreatestLessThan(key, offset);
+ }
+ }
+
+ return term; // There is no child <= key[offset] so devolve to term/parent.
+ }
+ } else {
+ // lcp > key
+ // No node at or below this is valid, so it must be found in an ancestor.
+ return null;
+ }
+ } catch (IOException ei) {
+ throw new IllegalStateException("Failed to lookupGLT", ei);
+ }
+ }
+
+ public TrieLeaf getMaxLeaf() {
+ TrieNode node = children.getLast();
+ if (node != null) {
+ return node.getMaxLeaf();
+ } else if (term != null) {
+ return term;
+ } else {
+ throw new IllegalStateException("Internal Trie node contains no children and no term");
+ }
+ }
+
+ public String toString() {
+ return "Trie-BRANCH[" + (term != null) + " on " + offset + " with " + children.size() + " and aLeaf[" + aLeaf + "]";
+ }
+ }
+
+ protected static class TrieLeaf extends TrieNode {
+ final TrieEntry entry;
+
+ protected TrieLeaf(TrieEntry entry) {
+ this.entry = entry;
+ this.aLeaf = this;
+ }
+
+ protected boolean insert(TrieLeaf node, int parentLcp) {
+ if (entry.keySize() != node.entry.keySize()) {
+ // Key lengths aren't equal so nodes aren't equal and we need to insert a new branch above this node.
+ return false;
+ } else if (!regionMatches(entry, parentLcp, node.entry, parentLcp, node.entry.keySize() - parentLcp)) {
+ // Suffix doesn't match so these nodes aren't equal and we need to insert a new branch above this node.
+ return false;
+ } else {
+ // Key lengths are equal; lcp is equal (precondition to function); and suffixes are equal. Either we
+ // have a duplicate key/value pair or we have a key conflict. So either return true; or throw
+ // exception.
+ if (entry.equals(node.entry)) {
+ return true; // Duplicate key/value pair.
+ } else {
+ throw new IllegalArgumentException("Attempt to insert multiple values for same key");
+ }
+ }
+ }
+
+ protected TrieEntry lookup(Entry key, int parentLcp, boolean[] valid) {
+ assert regionMatches(entry, 0, key, 0, key.keySize());
+ valid[0] = true;
+ return entry;
+ }
+
+ protected TrieLeaf lookupGreatestLessThan(Entry key, int parentLcp) {
+ assert regionCompare(entry, key, 0, entry.keySize()) <= 0;
+ return this;
+ }
+
+ public TrieLeaf getMaxLeaf() {
+ return this;
+ }
+
+ public int indexSize() {
+ return entry.referenceSize();
+ }
+
+ public int dataSize() {
+ return entry.entrySize();
+ }
+
+ public String toString() {
+ return "Trie-LEAF: " + entry;
+ }
+ }
+}
+
More information about the Mulgara-svn
mailing list