initial import of IntIntHashmap + JUnitTest including a benchmark.

3 files changed, 335 insertions, 0 deletions

diff --git a/make/build.xml b/make/build.xml
index c41f21c..f9eb19b 100755
--- a/make/build.xml
+++ b/make/build.xml
@@ -596,6 +596,7 @@
           <batchtest todir="${build}/test/results">
               <fileset dir="${build}/test/build/classes">
                   <include name="com/sun/gluegen/**Test*"/>
+                  <include name="com/jogamp/common/util/**Test*"/>
               </fileset>
               <formatter usefile="false" type="plain"/>
               <formatter usefile="true" type="xml"/>
diff --git a/src/java/com/jogamp/common/util/IntIntHashMap.java b/src/java/com/jogamp/common/util/IntIntHashMap.java
new file mode 100644
index 0000000..7a32654
--- /dev/null
+++ b/src/java/com/jogamp/common/util/IntIntHashMap.java
@@ -0,0 +1,195 @@
+/*
+ * Copyright (c) 2010, Michael Bien
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in the
+ *       documentation and/or other materials provided with the distribution.
+ *     * Neither the name of JogAmp nor the
+ *       names of its contributors may be used to endorse or promote products
+ *       derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL Michael Bien BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/**
+ * Created on Sunday, March 28 2010 21:01
+ */
+package com.jogamp.common.util;
+
+/**
+ * Fast HashMap with int keys and int values.
+ * Original code is based on the <a href="http://code.google.com/p/skorpios/"> skorpios project</a>
+ * released under new BSD license.
+ * @author Michael Bien
+ * @see IntObjectHashMap
+ */
+public class IntIntHashMap {
+
+    private final float loadFactor;
+
+    private Entry[] table;
+    
+    private int size;
+    private int mask;
+    private int capacity;
+    private int threshold;
+
+    public IntIntHashMap() {
+        this(16, 0.75f);
+    }
+
+    public IntIntHashMap(int initialCapacity) {
+        this(initialCapacity, 0.75f);
+    }
+
+    public IntIntHashMap(int initialCapacity, float loadFactor) {
+        if (initialCapacity > 1 << 30) {
+            throw new IllegalArgumentException("initialCapacity is too large.");
+        }
+        if (initialCapacity < 0) {
+            throw new IllegalArgumentException("initialCapacity must be greater than zero.");
+        }
+        if (loadFactor <= 0) {
+            throw new IllegalArgumentException("initialCapacity must be greater than zero.");
+        }
+        capacity = 1;
+        while (capacity < initialCapacity) {
+            capacity <<= 1;
+        }
+        this.loadFactor = loadFactor;
+        this.threshold = (int) (capacity * loadFactor);
+        this.table = new Entry[capacity];
+        this.mask = capacity - 1;
+    }
+
+    public boolean containsValue(int value) {
+        Entry[] table = this.table;
+        for (int i = table.length; i-- > 0;) {
+            for (Entry e = table[i]; e != null; e = e.next) {
+                if (e.value == value) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    public boolean containsKey(int key) {
+        int index = key & mask;
+        for (Entry e = table[index]; e != null; e = e.next) {
+            if (e.key == key) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    public int get(int key) {
+        int index = key & mask;
+        for (Entry e = table[index]; e != null; e = e.next) {
+            if (e.key == key) {
+                return e.value;
+            }
+        }
+        return 0;
+    }
+
+    public int put(int key, int value) {
+        int index = key & mask;
+        // Check if key already exists.
+        for (Entry e = table[index]; e != null; e = e.next) {
+            if (e.key != key) {
+                continue;
+            }
+            int oldValue = e.value;
+            e.value = value;
+            return oldValue;
+        }
+        table[index] = new Entry(key, value, table[index]);
+        if (size++ >= threshold) {
+            // Rehash.
+            int newCapacity = 2 * capacity;
+            Entry[] newTable = new Entry[newCapacity];
+            Entry[] src = table;
+            int bucketmask = newCapacity - 1;
+            for (int j = 0; j < src.length; j++) {
+                Entry e = src[j];
+                if (e != null) {
+                    src[j] = null;
+                    do {
+                        Entry next = e.next;
+                        index = e.key & bucketmask;
+                        e.next = newTable[index];
+                        newTable[index] = e;
+                        e = next;
+                    } while (e != null);
+                }
+            }
+            table = newTable;
+            capacity = newCapacity;
+            threshold = (int) (newCapacity * loadFactor);
+            mask = capacity - 1;
+        }
+        return 0;
+    }
+
+    public int remove(int key) {
+        int index = key & mask;
+        Entry prev = table[index];
+        Entry e = prev;
+        while (e != null) {
+            Entry next = e.next;
+            if (e.key == key) {
+                size--;
+                if (prev == e) {
+                    table[index] = next;
+                } else {
+                    prev.next = next;
+                }
+                return e.value;
+            }
+            prev = e;
+            e = next;
+        }
+        return 0;
+    }
+
+    public int size() {
+        return size;
+    }
+
+    public void clear() {
+        Entry[] table = this.table;
+        for (int index = table.length; --index >= 0;) {
+            table[index] = null;
+        }
+        size = 0;
+    }
+
+    private final static class Entry {
+
+        private final int key;
+        private int value;
+        private Entry next;
+
+        private Entry(int k, int v, Entry n) {
+            key = k;
+            value = v;
+            next = n;
+        }
+    }
+}
diff --git a/test/junit/com/jogamp/common/util/IntIntHashMapTest.java b/test/junit/com/jogamp/common/util/IntIntHashMapTest.java
new file mode 100644
index 0000000..6ccf0e3
--- /dev/null
+++ b/test/junit/com/jogamp/common/util/IntIntHashMapTest.java
@@ -0,0 +1,139 @@
+/**
+ * Created on Sunday, March 28 2010 21:01
+ */
+package com.jogamp.common.util;
+
+import java.util.HashMap;
+import java.util.Map.Entry;
+import java.util.Random;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import static org.junit.Assert.*;
+import static java.lang.System.*;
+
+/**
+ *
+ * @author Michael Bien
+ */
+public class IntIntHashMapTest {
+
+    private static int iterations;
+    private static int[] rndKeys;
+    private static int[] rndValues;
+
+    @BeforeClass
+    public static void init() {
+
+        iterations = 20000;
+        final int keySeed = 42;
+        final int valueSeed = 23;
+
+        Random keyRnd = new Random(/*keySeed*/);
+        Random valueRnd = new Random(/*valueSeed*/);
+
+        rndKeys = new int[iterations];
+        rndValues = new int[iterations];
+        for (int i = 0; i < iterations; i++) {
+            rndValues[i] = valueRnd.nextInt();
+            rndKeys[i] = keyRnd.nextInt();
+        }
+
+    }
+    /**
+     * Test of put method, of class IntIntHashMap.
+     */
+    @Test
+    public void testPutRemove() {
+
+        final IntIntHashMap intmap = new IntIntHashMap();
+        final HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
+
+        // put
+        for (int i = 0; i < iterations; i++) {
+            intmap.put(rndKeys[i], rndValues[i]);
+
+            assertTrue(intmap.containsValue(rndValues[i]));
+            assertTrue(intmap.containsKey(rndKeys[i]));
+        }
+
+        for (int i = 0; i < iterations; i++) {
+            map.put(rndKeys[i], rndValues[i]);
+        }
+
+        assertEquals(map.size(), intmap.size());
+
+        for (Entry<Integer, Integer> entry : map.entrySet()) {
+            assertTrue(intmap.containsKey(entry.getKey()));
+            assertTrue(intmap.containsValue(entry.getValue()));
+        }
+
+        int i = 0;
+        for (Entry<Integer, Integer> entry : map.entrySet()) {
+            assertEquals((int)entry.getValue(), intmap.remove(entry.getKey()));
+            assertEquals(map.size() - i - 1, intmap.size());
+            i++;
+        }
+
+    }
+
+    @Test
+    public void benchmark() {
+
+        // simple benchmark
+        final IntIntHashMap intmap          = new IntIntHashMap(1024);
+        final HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(1024);
+
+        out.println("put");
+        long time = currentTimeMillis();
+        for (int i = 0; i < iterations; i++) {
+            intmap.put(rndKeys[i], rndValues[i]);
+        }
+        long intmapTime = (currentTimeMillis() - time);
+        out.println("   iimap: " + intmapTime+"ms");
+
+
+        time = currentTimeMillis();
+        for (int i = 0; i < iterations; i++) {
+            map.put(rndKeys[i], rndValues[i]);
+        }
+        long mapTime = (currentTimeMillis() - time);
+        out.println("   map:   " + mapTime+"ms");
+
+        assertTrue(intmapTime < mapTime);
+
+
+        System.out.println();
+        System.out.println("get");
+        intmapTime = (currentTimeMillis() - time);
+        out.println("   iimap: " + intmapTime+"ms");
+        for (int i = 0; i < iterations; i++) {
+            intmap.get(rndValues[i]);
+        }
+        
+        mapTime = (currentTimeMillis() - time);
+        out.println("   map:   " + mapTime+"ms");
+        for (int i = 0; i < iterations; i++) {
+            map.get(rndValues[i]);
+        }
+        assertTrue(intmapTime < mapTime);
+
+
+        out.println();
+        out.println("remove");
+        intmapTime = (currentTimeMillis() - time);
+        out.println("   iimap: " + intmapTime+"ms");
+        for (int i = 0; i < iterations; i++) {
+            intmap.remove(rndValues[i]);
+        }
+
+        mapTime = (currentTimeMillis() - time);
+        out.println("   map:   " + mapTime+"ms");
+        for (int i = 0; i < iterations; i++) {
+            map.remove(rndValues[i]);
+        }
+
+        assertTrue(intmapTime < mapTime);
+    }
+
+
+}