[Mulgara-svn] r780 - projects/xa2/object-pool/src
andrae at mulgara.org
andrae at mulgara.org
Mon Apr 14 08:07:43 UTC 2008
Author: andrae
Date: 2008-04-14 01:07:42 -0700 (Mon, 14 Apr 2008)
New Revision: 780
Added:
projects/xa2/object-pool/src/ByteMapTest.java
Modified:
projects/xa2/object-pool/src/ByteMap.java
Log:
ByteMap is now functional.
Passes a basic sequential insertion test, but will need more testing before I can move to the next stage which
is to replace the use of HashMap in MemoryTrie with this more space-efficient class.
Once that is done we need to modify ByteMap::insert() to return the number of serialized bytes required to
satisfy the operation, so we can start working on ExternalTrie.
Modified: projects/xa2/object-pool/src/ByteMap.java
===================================================================
--- projects/xa2/object-pool/src/ByteMap.java 2008-04-14 01:21:58 UTC (rev 779)
+++ projects/xa2/object-pool/src/ByteMap.java 2008-04-14 08:07:42 UTC (rev 780)
@@ -4,37 +4,68 @@
* Date 8th April 2008
*/
+import java.util.ArrayList;
+
/**
* Represents a map from a byte to data.
* ie. a compressed 256 element array.
*/
-public static class ByteMap<T> {
+public class ByteMap<T> {
short high;
short[] low;
ArrayList<T> data;
- public TrieNode() {
+ public ByteMap() {
+ high = 0;
+ low = new short[0];
data = new ArrayList<T>();
}
- public void insert(byte key, T datum) {
- short h = hiNibbleAsBitInShort(key);
- short l;
- if (high & h != 0) {
+ /**
+ * @param datum Value to be associated with key. Note: Must not be null.
+ * @return true if map now contains key->datum; false if entry for key already exists and
+ * !datum.equals(existing_value).
+ */
+ public boolean insert(byte key, T datum) {
+ if (datum == null) {
+ throw new IllegalArgumentException("Attempted to insert null into ByteMap");
+ }
+
+ int h = hiNibbleAsBitInShort(key);
+ if ((high & h) != 0) {
// We already have a low entry for this hi-nibble.
int lowOffset = ones(HIGH, high, key);
- l = lowNibbleAsBitInShort(key);
- if (low[lowOffset] & l != 0) {
+ int dataOffset = 0;
+ for (int i = 0; i < lowOffset; i++) {
+ dataOffset += ones(low[i]);
+ }
+ dataOffset += ones(LOW, low[lowOffset], key);
+
+ int l = lowNibbleAsBitInShort(key);
+ if ((low[lowOffset] & l) != 0) {
// We already have a data entry for this byte.
+ if (data.get(dataOffset).equals(datum)) {
+ // Pre-existing data matches datum;
+ return true;
+ } else {
+ return false;
+ }
} else {
- // We need to insert a low entry for this byte.
+ // We need to insert a data entry for this byte.
+ low[lowOffset] = (short)(low[lowOffset] | l);
+ data.add(dataOffset, datum);
+ return true;
}
} else {
// We need to insert a new low entry for this hi-nibble.
- short[] newlow = new short[low.length + 1];
+ short[] newLow = new short[low.length + 1];
int lowOffset = ones(HIGH, high, key);
System.arraycopy(low, 0, newLow, 0, lowOffset);
System.arraycopy(low, lowOffset, newLow, lowOffset + 1, low.length - lowOffset);
+ newLow[lowOffset] = 0;
+ high = (short)(high | h);
+ low = newLow;
+ return insert(key, datum);
}
}
@@ -42,33 +73,35 @@
* Returns the forwarding pointer corresponding to the key in this trie node.
* Note: The result is a *signed* short. +ve pointers correspond to references to Trie-Nodes; -ve
* pointers correspond to references to child pointers.
+ * @return Value corresponding to key; or null if not found.
*/
public T lookup(byte key) {
// the low-nibble index is the ones left of the key's high-nibble bit in high.
int lowOffset = ones(HIGH, high, key);
// the ptrs index is the sum of the ones in the low-nibble array prior to low-nibble index + the ones
- // left of the key's low-nibble bit in low[lowOffset - 1].
- int ptrOffset = 0;
- for (int i = 0; i < lowOffset - 1; i++) {
- ptrOffset += ones(low[i]);
+ // left of the key's low-nibble bit in low[lowOffset].
+ if (lowOffset >= low.length) {
+ return null;
}
- ptrOffset += ones(LOW, low[lowOffset - 1], key);
+ int dataOffset = 0;
+ for (int i = 0; i < lowOffset; i++) {
+ dataOffset += ones(low[i]);
+ }
+ dataOffset += ones(LOW, low[lowOffset], key);
// the resulting index is a direct index into the forwarding-pointer array.
- return data.get(ptrOffset);
+ return data.get(dataOffset);
}
- private int ones(short index) {
- shortOnesTable[index & 0x0000FFFF];
+ private static int ones(short index) {
+ return shortOnesTable[index & 0x0000FFFF];
}
- enum Nibble {
- HIGH = 0;
- LOW = 1;
- };
+ static private final int HIGH = 0;
+ static private final int LOW = 1;
- private int ones(Nibble nibble, short index, byte key) {
+ private static int ones(int nibble, short index, byte key) {
// Conversions from signed to unsigned.
int idx = index & 0x0000FFFF;
int ky = key & 0x000000FF;
@@ -76,12 +109,12 @@
return onesTable[idx * 512 + 2 * ky + nibble];
}
- public short hiNibbleAsBitInShort(byte b) {
- int nibbleBit = 0x00008000 >> (b & 0x000000F0 >> 4);
+ public static int hiNibbleAsBitInShort(byte b) {
+ return 0x00008000 >> ((b & 0x000000F0) >> 4);
}
- public short lowNibbleAsBitInShort(byte b) {
- int nibbleBit = 0x00008000 >> (b & 0x0000000F);
+ public static int lowNibbleAsBitInShort(byte b) {
+ return 0x00008000 >> (b & 0x0000000F);
}
// The number of ones in a 16-bit binary number indexed by 16-bit int.
@@ -97,27 +130,27 @@
static {
shortOnesTable = new byte[64*1024];
- for (i = 0; i < shortOnesTable.length; i++) {
- short bit = 0x8000;
+ for (int i = 0; i < shortOnesTable.length; i++) {
+ int bit = 0x00008000;
while (bit != 0) {
- shortOnesTable[i] += (i & bit == 0) ? 0 : 1;
- bit >> 1;
+ shortOnesTable[i] += ((i & bit) == 0) ? 0 : 1;
+ bit = bit >> 1;
}
}
onesTable = new byte[64*1024 * 2*256];
- for (int i = 0; i < 64*1024; i++) {
- for (int b = 0; b < 0x000000FF; b++) {
- int nibbleBit = 0x00008000 >> (b & 0x000000F0 >> 4);
- while (nibbleBit != 0) {
+ for (int i = 0; i < 0x00010000; i++) {
+ for (int b = 0; b < 0x00000100; b++) {
+ int nibbleBit = hiNibbleAsBitInShort((byte)b);
+ while (nibbleBit < 0x00010000) {
nibbleBit = nibbleBit << 1;
- onesTable[i*512 + b*2 + HIGH] = (i & nibbleBit == 0) ? 0 : 1;
+ onesTable[i*512 + b*2 + HIGH] += ((i & nibbleBit) == 0) ? 0 : 1;
}
- nibbleBit = 0x00008000 >> (b & 0x0000000F);
+ nibbleBit = lowNibbleAsBitInShort((byte)b);
while (nibbleBit != 0) {
nibbleBit = nibbleBit << 1;
- onesTable[i*512 + b*2 + LOW] = (i & nibbleBit == 0) ? 0 : 1;
+ onesTable[i*512 + b*2 + LOW] += ((i & nibbleBit) == 0) ? 0 : 1;
}
}
}
Added: projects/xa2/object-pool/src/ByteMapTest.java
===================================================================
--- projects/xa2/object-pool/src/ByteMapTest.java (rev 0)
+++ projects/xa2/object-pool/src/ByteMapTest.java 2008-04-14 08:07:42 UTC (rev 780)
@@ -0,0 +1,54 @@
+
+
+/**
+ * Represents a map from a byte to data.
+ * ie. a compressed 256 element array.
+ */
+public class ByteMapTest {
+ public static void main(String[] args) throws Exception {
+ testEmpty();
+ testSequential();
+ }
+
+ public static void testEmpty() throws Exception {
+ System.out.println("running testEmpty...");
+ ByteMap<Long> byteMap = new ByteMap<Long>();
+
+ for (int i = 0; i < 0x00000100; i++) {
+ assertNull("Found result for i = " + i + " in empty map", byteMap.lookup((byte)i));
+ }
+ System.out.println("testEmpty Successful");
+ }
+
+ public static void testSequential() throws Exception {
+ System.out.println("running testSequential...");
+ ByteMap<Long> byteMap = new ByteMap<Long>();
+
+ for (int i = 0; i < 0x00000100; i++) {
+ assertTrue("Found double entry for i = " + i + " in sequential map", byteMap.insert((byte)i, new Long(i)));
+ }
+ for (int i = 0; i < 0x00000100; i++) {
+ Long l = byteMap.lookup((byte)i);
+ assertEquals("Found mismatching entry for i = " + i + " in sequential map: Received " + l, new Long(i), l);
+ }
+ System.out.println("testSequential Successful");
+ }
+
+ public static void assertNull(String str, Object obj) throws Exception {
+ if (obj != null) {
+ throw new IllegalStateException(str);
+ }
+ }
+
+ public static void assertTrue(String str, boolean b) throws Exception {
+ if (!b) {
+ throw new IllegalStateException(str);
+ }
+ }
+
+ public static void assertEquals(String str, Object lhs, Object rhs) throws Exception {
+ if (lhs == null && rhs == null) return;
+ if (lhs == null || rhs == null) throw new IllegalStateException(str);
+ if (!lhs.equals(rhs)) throw new IllegalStateException(str);
+ }
+}
More information about the Mulgara-svn
mailing list