summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rwxr-xr-xmake/build.xml24
-rw-r--r--src/java/com/jogamp/common/util/LongIntHashMap.java199
-rw-r--r--test/junit/com/jogamp/common/util/LongIntHashMapTest.java140
3 files changed, 360 insertions, 3 deletions
diff --git a/make/build.xml b/make/build.xml
index 3284d19..3301125 100755
--- a/make/build.xml
+++ b/make/build.xml
@@ -425,27 +425,45 @@
-->
<target name="pre-build">
+ <!-- Int*Maps -->
<antcall target="create-map" inheritrefs="true">
+ <param name="map.src" value="IntIntHashMap"/>
<param name="map.name" value="IntObjectHashMap"/>
<param name="map.value" value="Object"/>
<param name="map.null" value="null"/>
</antcall>
<antcall target="create-map" inheritrefs="true">
+ <param name="map.src" value="IntIntHashMap"/>
<param name="map.name" value="IntLongHashMap"/>
<param name="map.value" value="long"/>
<param name="map.null" value="0"/>
</antcall>
+ <!-- Long*Maps -->
+ <antcall target="create-map" inheritrefs="true">
+ <param name="map.src" value="LongIntHashMap"/>
+ <param name="map.name" value="LongObjectHashMap"/>
+ <param name="map.value" value="Object"/>
+ <param name="map.null" value="null"/>
+ </antcall>
+
+ <antcall target="create-map" inheritrefs="true">
+ <param name="map.src" value="LongIntHashMap"/>
+ <param name="map.name" value="LongLongHashMap"/>
+ <param name="map.value" value="long"/>
+ <param name="map.null" value="0"/>
+ </antcall>
+
</target>
<target name="create-map">
<!-- substitutes certain token in IntIntHashmap to create new primitive HasmMap-->
- <copy file="${src.java}/com/jogamp/common/util/IntIntHashMap.java"
+ <copy file="${src.java}/com/jogamp/common/util/${map.src}.java"
tofile="${src.generated.java}/com/jogamp/common/util/${map.name}.java" overwrite="true">
<filterchain>
- <replaceregex pattern="IntIntHashMap" replace="${map.name}"/>
- <replaceregex pattern="@see ${map.name}" replace="@see IntIntHashMap"/>
+ <replaceregex pattern="${map.src}" replace="${map.name}"/>
+ <replaceregex pattern="@see ${map.name}" replace="@see ${map.src}"/>
<replaceregex pattern="/\*value\*/int/\*value\*/" replace="${map.value}"/>
<replaceregex pattern="/\*null\*/0/\*null\*/" replace="${map.null}"/>
</filterchain>
diff --git a/src/java/com/jogamp/common/util/LongIntHashMap.java b/src/java/com/jogamp/common/util/LongIntHashMap.java
new file mode 100644
index 0000000..e17155d
--- /dev/null
+++ b/src/java/com/jogamp/common/util/LongIntHashMap.java
@@ -0,0 +1,199 @@
+/*
+ * 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 for primitive data..
+ * 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
+ * @author Simon Goller
+ * @see IntObjectHashMap
+ * @see IntLongHashMap
+ * @see LongObjectHashMap
+ * @see LongLongHashMap
+ */
+public class /*name*/LongIntHashMap/*name*/ {
+
+ private final float loadFactor;
+
+ private Entry[] table;
+
+ private int size;
+ private int mask;
+ private int capacity;
+ private int threshold;
+
+ public /*name*/LongIntHashMap/*name*/() {
+ this(16, 0.75f);
+ }
+
+ public /*name*/LongIntHashMap/*name*/(int initialCapacity) {
+ this(initialCapacity, 0.75f);
+ }
+
+ public /*name*/LongIntHashMap/*name*/(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(/*value*/int/*value*/ 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(/*key*/long/*key*/ key) {
+ /*key*/int/*key*/ index = (int) (key & mask);
+ for (Entry e = table[index]; e != null; e = e.next) {
+ if (e.key == key) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public /*value*/int/*value*/ get(/*key*/long/*key*/ key) {
+ int index = (int) (key & mask);
+ for (Entry e = table[index]; e != null; e = e.next) {
+ if (e.key == key) {
+ return e.value;
+ }
+ }
+ return /*null*/0/*null*/;
+ }
+
+ public /*value*/int/*value*/ put(/*key*/long/*key*/ key, /*value*/int/*value*/ value) {
+ int index = (int) (key & mask);
+ // Check if key already exists.
+ for (Entry e = table[index]; e != null; e = e.next) {
+ if (e.key != key) {
+ continue;
+ }
+ /*value*/int/*value*/ 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;
+ long 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 = (int) (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 /*null*/0/*null*/;
+ }
+
+ public /*value*/int/*value*/ remove(/*key*/long/*key*/ key) {
+ int index = (int) (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 /*null*/0/*null*/;
+ }
+
+ 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 /*key*/long/*key*/ key;
+ private /*value*/int/*value*/ value;
+ private Entry next;
+
+ private Entry(/*key*/long/*key*/ k, /*value*/int/*value*/ v, Entry n) {
+ key = k;
+ value = v;
+ next = n;
+ }
+ }
+}
diff --git a/test/junit/com/jogamp/common/util/LongIntHashMapTest.java b/test/junit/com/jogamp/common/util/LongIntHashMapTest.java
new file mode 100644
index 0000000..67a610f
--- /dev/null
+++ b/test/junit/com/jogamp/common/util/LongIntHashMapTest.java
@@ -0,0 +1,140 @@
+/**
+ * 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
+ * @author Simon Goller
+ */
+public class LongIntHashMapTest {
+
+ private static int iterations;
+ private static long[] 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 long[iterations];
+ rndValues = new int[iterations];
+ for (int i = 0; i < iterations; i++) {
+ rndValues[i] = valueRnd.nextInt();
+ rndKeys[i] = keyRnd.nextLong();
+ }
+
+ }
+ /**
+ * Test of put method, of class LongIntHashMap.
+ */
+ @Test
+ public void testPutRemove() {
+
+ final LongIntHashMap intmap = new LongIntHashMap();
+ final HashMap<Long, Integer> map = new HashMap<Long, 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<Long, Integer> entry : map.entrySet()) {
+ assertTrue(intmap.containsKey(entry.getKey()));
+ assertTrue(intmap.containsValue(entry.getValue()));
+ }
+
+ int i = 0;
+ for (Entry<Long, 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 LongIntHashMap intmap = new LongIntHashMap(1024);
+ final HashMap<Long, Integer> map = new HashMap<Long, 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);
+ }
+
+
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-01 18:50:39 +0000