[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-&gt;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