Implemented a HashMultiSet for maintaining the expected results in the R-Tree and LSM R-Tree tests. Dramatically reduces the time for tests.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@1632 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/HashMultiSet.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/HashMultiSet.java
new file mode 100644
index 0000000..e4ccdcb
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/HashMultiSet.java
@@ -0,0 +1,113 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed 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 from
+ *
+ * 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.
+ */
+
+package edu.uci.ics.hyracks.storage.am.common.util;
+
+import java.util.AbstractCollection;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Quick and dirty implementation of a HashMultiSet backed by a HashMap.
+ * It only implements a minimal subset of the collection interface to make our tests work.
+ */
+public class HashMultiSet<E> extends AbstractCollection<E> {
+
+ private final Map<E, List<E>> map = new HashMap<E, List<E>>();
+ private int size = 0;
+
+ @Override
+ public boolean add(E e) {
+ List<E> list = map.get(e);
+ if (list == null) {
+ list = new ArrayList<E>();
+ map.put(e, list);
+ }
+ list.add(e);
+ size++;
+ return true;
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return map.containsKey(o);
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ List<E> list = map.get(o);
+ if (list == null) {
+ return false;
+ }
+ list.remove(list.size() - 1);
+ if (list.isEmpty()) {
+ map.remove(o);
+ }
+ size--;
+ return true;
+ }
+
+ @Override
+ public Iterator<E> iterator() {
+ return new HashMultiSetIterator();
+ }
+
+ @Override
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public void clear() {
+ map.clear();
+ size = 0;
+ }
+
+ private class HashMultiSetIterator implements Iterator<E> {
+
+ private Iterator<Map.Entry<E, List<E>>> mapIter;
+ private Iterator<E> listIter;
+
+ public HashMultiSetIterator() {
+ mapIter = map.entrySet().iterator();
+ }
+
+ @Override
+ public boolean hasNext() {
+ if (mapIter.hasNext() || (listIter != null && listIter.hasNext())) {
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public E next() {
+ if (listIter == null || (listIter != null && !listIter.hasNext())) {
+ Map.Entry<E, List<E>> entry = mapIter.next();
+ listIter = entry.getValue().iterator();
+ return listIter.next();
+ }
+ return listIter.next();
+ }
+
+ @Override
+ public void remove() {
+ throw new IllegalStateException("Not implemented");
+ }
+ }
+}
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java
index a053dde..9909e2f 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java
@@ -43,8 +43,8 @@
actual.getFieldLength(i));
DataInput dataIn = new DataInputStream(inStream);
Object actualObj = fieldSerdes[i].deserialize(dataIn);
- if (!actualObj.equals(expected.get(i))) {
- fail("Actual and expected fields do not match on field " + i + ".\nExpected: " + expected.get(i)
+ if (!actualObj.equals(expected.getField(i))) {
+ fail("Actual and expected fields do not match on field " + i + ".\nExpected: " + expected.getField(i)
+ "\nActual : " + actualObj);
}
}
@@ -64,13 +64,13 @@
boolean geLowKey = true;
boolean leHighKey = true;
for (int i = 0; i < lowKey.getNumKeys(); i++) {
- if (t.get(i).compareTo(lowKey.get(i)) < 0) {
+ if (t.getField(i).compareTo(lowKey.getField(i)) < 0) {
geLowKey = false;
break;
}
}
for (int i = 0; i < highKey.getNumKeys(); i++) {
- if (t.get(i).compareTo(highKey.get(i)) > 0) {
+ if (t.getField(i).compareTo(highKey.getField(i)) > 0) {
leHighKey = false;
break;
}
@@ -317,7 +317,7 @@
// Update check tuple's non-key fields.
for (int j = keyFieldCount; j < fieldCount; j++) {
Comparable newValue = getRandomUpdateValue(ctx.getFieldSerdes()[j], rnd);
- checkTuple.set(j, newValue);
+ checkTuple.setField(j, newValue);
}
createTupleFromCheckTuple(checkTuple, updateTupleBuilder, updateTuple, ctx.getFieldSerdes());
@@ -334,7 +334,7 @@
public CheckTuple createStringCheckTuple(String[] fieldValues, int numKeyFields) {
CheckTuple<String> checkTuple = new CheckTuple<String>(fieldValues.length, numKeyFields);
for (String s : fieldValues) {
- checkTuple.add((String) s);
+ checkTuple.appendField((String) s);
}
return checkTuple;
}
@@ -396,7 +396,7 @@
protected CheckTuple createIntCheckTuple(int[] fieldValues, int numKeyFields) {
CheckTuple<Integer> checkTuple = new CheckTuple<Integer>(fieldValues.length, numKeyFields);
for (int v : fieldValues) {
- checkTuple.add(v);
+ checkTuple.appendField(v);
}
return checkTuple;
}
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/CheckTuple.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/CheckTuple.java
index 4b4b90b..9e31f71 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/CheckTuple.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/CheckTuple.java
@@ -17,42 +17,60 @@
@SuppressWarnings({"rawtypes", "unchecked"})
public class CheckTuple<T extends Comparable<T>> implements Comparable<T> {
- protected final int numKeys;
- protected final Comparable[] tuple;
+ protected final int numKeys;
+ protected final Comparable[] fields;
protected int pos;
public CheckTuple(int numFields, int numKeys) {
this.numKeys = numKeys;
- this.tuple = new Comparable[numFields];
+ this.fields = new Comparable[numFields];
pos = 0;
}
- public void add(T e) {
- tuple[pos++] = e;
+ public void appendField(T e) {
+ fields[pos++] = e;
}
- @Override
- public int compareTo(T o) {
- CheckTuple<T> other = (CheckTuple<T>)o;
- for (int i = 0; i < numKeys; i++) {
- int cmp = tuple[i].compareTo(other.get(i));
- if (cmp != 0) {
- return cmp;
- }
- }
- return 0;
- }
+ @Override
+ public int compareTo(T o) {
+ CheckTuple<T> other = (CheckTuple<T>) o;
+ for (int i = 0; i < numKeys; i++) {
+ int cmp = fields[i].compareTo(other.getField(i));
+ if (cmp != 0) {
+ return cmp;
+ }
+ }
+ return 0;
+ }
- public T get(int idx) {
- return (T)tuple[idx];
- }
+ @Override
+ public boolean equals(Object o) {
+ if (!(o instanceof Comparable<?>)) {
+ return false;
+ }
+ return compareTo((T) o) == 0;
+ }
- public void set(int idx, T e) {
- tuple[idx] = e;
+ @Override
+ public int hashCode() {
+ //int hash = 37 * numKeys + fields.length;
+ int hash = 0;
+ for (int i = 0; i < numKeys; i++) {
+ hash = 37 * hash + fields[i].hashCode();
+ }
+ return hash;
+ }
+
+ public T getField(int idx) {
+ return (T) fields[idx];
+ }
+
+ public void setField(int idx, T e) {
+ fields[idx] = e;
}
public int size() {
- return tuple.length;
+ return fields.length;
}
public int getNumKeys() {
@@ -62,9 +80,9 @@
@Override
public String toString() {
StringBuilder strBuilder = new StringBuilder();
- for (int i = 0; i < tuple.length; i++) {
- strBuilder.append(tuple[i].toString());
- if (i != tuple.length-1) {
+ for (int i = 0; i < fields.length; i++) {
+ strBuilder.append(fields[i].toString());
+ if (i != fields.length-1) {
strBuilder.append(" ");
}
}
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java
index 000f7d0..6406a5e 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java
@@ -33,9 +33,9 @@
import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoader;
import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
-import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoader;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
@@ -72,7 +72,7 @@
DataOutput dos = tupleBuilder.getDataOutput();
tupleBuilder.reset();
for (int i = 0; i < fieldCount; i++) {
- fieldSerdes[i].serialize(checkTuple.get(i), dos);
+ fieldSerdes[i].serialize(checkTuple.getField(i), dos);
tupleBuilder.addFieldEndOffset();
}
tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
@@ -88,7 +88,7 @@
tuple.getFieldLength(i));
DataInput dataIn = new DataInputStream(inStream);
Comparable fieldObj = (Comparable) fieldSerdes[i].deserialize(dataIn);
- checkTuple.add(fieldObj);
+ checkTuple.appendField(fieldObj);
}
return checkTuple;
}
@@ -106,7 +106,7 @@
}
public void checkDiskOrderScan(ITreeIndexTestContext ctx) throws Exception {
- try {
+ try {
if (LOGGER.isLoggable(Level.INFO)) {
LOGGER.info("Testing Disk-Order Scan.");
}
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java
index 994db2a..29cf35e 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java
@@ -45,10 +45,10 @@
public static final int RTREE_HYRACKS_FRAME_SIZE = 128;
// Mem configuration for LSMRTree and LSMRTreeWithAntiMatterTuples.
- public static final int LSM_RTREE_DISK_PAGE_SIZE = 256;
+ public static final int LSM_RTREE_DISK_PAGE_SIZE = 512;
public static final int LSM_RTREE_DISK_NUM_PAGES = 1000;
public static final int LSM_RTREE_DISK_MAX_OPEN_FILES = 2000;
- public static final int LSM_RTREE_MEM_PAGE_SIZE = 256;
+ public static final int LSM_RTREE_MEM_PAGE_SIZE = 512;
public static final int LSM_RTREE_MEM_NUM_PAGES = 1000;
public static final int LSM_RTREE_HYRACKS_FRAME_SIZE = 128;
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTestContext.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTestContext.java
index 9affc47..32afdad 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTestContext.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTestContext.java
@@ -15,17 +15,17 @@
package edu.uci.ics.hyracks.storage.am.rtree;
-import java.util.ArrayList;
import java.util.Collection;
import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
import edu.uci.ics.hyracks.storage.am.common.TreeIndexTestContext;
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.util.HashMultiSet;
@SuppressWarnings("rawtypes")
public abstract class AbstractRTreeTestContext extends TreeIndexTestContext<RTreeCheckTuple> {
- private final ArrayList<RTreeCheckTuple> checkTuples = new ArrayList<RTreeCheckTuple>();
-
+ private final HashMultiSet<RTreeCheckTuple> checkTuples = new HashMultiSet<RTreeCheckTuple>();
+
public AbstractRTreeTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
super(fieldSerdes, treeIndex);
}
@@ -34,5 +34,4 @@
public Collection<RTreeCheckTuple> getCheckTuples() {
return checkTuples;
}
-
}
\ No newline at end of file
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeCheckTuple.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeCheckTuple.java
index 98800e5..c498136 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeCheckTuple.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeCheckTuple.java
@@ -27,8 +27,8 @@
@Override
public boolean equals(Object o) {
RTreeCheckTuple<T> other = (RTreeCheckTuple<T>) o;
- for (int i = 0; i < tuple.length; i++) {
- int cmp = tuple[i].compareTo(other.get(i));
+ for (int i = 0; i < fields.length; i++) {
+ int cmp = fields[i].compareTo(other.getField(i));
if (cmp != 0) {
return false;
}
@@ -41,11 +41,11 @@
int maxFieldPos = numKeys / 2;
for (int i = 0; i < maxFieldPos; i++) {
int j = maxFieldPos + i;
- int cmp = tuple[i].compareTo(other.get(j));
+ int cmp = fields[i].compareTo(other.getField(j));
if (cmp > 0) {
return false;
}
- cmp = tuple[j].compareTo(other.get(i));
+ cmp = fields[j].compareTo(other.getField(i));
if (cmp < 0) {
return false;
}
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java
index a23f375..9f5e861 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java
@@ -21,6 +21,7 @@
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.util.HashMultiSet;
import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
@@ -32,9 +33,9 @@
@SuppressWarnings("unchecked")
// Create a new ArrayList containing the elements satisfying the search key
- public ArrayList<RTreeCheckTuple> getRangeSearchExpectedResults(ArrayList<RTreeCheckTuple> checkTuples,
+ public HashMultiSet<RTreeCheckTuple> getRangeSearchExpectedResults(Collection<RTreeCheckTuple> checkTuples,
RTreeCheckTuple key) {
- ArrayList<RTreeCheckTuple> expectedResult = new ArrayList<RTreeCheckTuple>();
+ HashMultiSet<RTreeCheckTuple> expectedResult = new HashMultiSet<RTreeCheckTuple>();
Iterator<RTreeCheckTuple> iter = checkTuples.iterator();
while (iter.hasNext()) {
RTreeCheckTuple t = iter.next();
@@ -61,9 +62,9 @@
RTreeCheckTuple keyCheck = (RTreeCheckTuple) createCheckTupleFromTuple(key, ctx.getFieldSerdes(),
cmp.getKeyFieldCount());
- ArrayList<RTreeCheckTuple> expectedResult = null;
+ HashMultiSet<RTreeCheckTuple> expectedResult = null;
- expectedResult = getRangeSearchExpectedResults((ArrayList<RTreeCheckTuple>) ctx.getCheckTuples(), keyCheck);
+ expectedResult = getRangeSearchExpectedResults(ctx.getCheckTuples(), keyCheck);
checkExpectedResults(searchCursor, expectedResult, ctx.getFieldSerdes(), ctx.getKeyFieldCount(), null);
}
@@ -122,7 +123,7 @@
protected CheckTuple createDoubleCheckTuple(double[] fieldValues, int numKeyFields) {
RTreeCheckTuple<Double> checkTuple = new RTreeCheckTuple<Double>(fieldValues.length, numKeyFields);
for (double v : fieldValues) {
- checkTuple.add(v);
+ checkTuple.appendField(v);
}
return checkTuple;
}
@@ -194,7 +195,7 @@
protected CheckTuple createIntCheckTuple(int[] fieldValues, int numKeyFields) {
RTreeCheckTuple<Integer> checkTuple = new RTreeCheckTuple<Integer>(fieldValues.length, numKeyFields);
for (int v : fieldValues) {
- checkTuple.add(v);
+ checkTuple.appendField(v);
}
return checkTuple;
}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
index 8be3e8c..799cdaa 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
@@ -43,6 +43,7 @@
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.util.HashMultiSet;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
@@ -142,11 +143,11 @@
} catch (TreeIndexException e) {
}
RTreeCheckTuple checkTuple = new RTreeCheckTuple(fieldCount, keyFieldCount);
- checkTuple.add(Math.min(p1x, p2x));
- checkTuple.add(Math.min(p1y, p2y));
- checkTuple.add(Math.max(p1x, p2x));
- checkTuple.add(Math.max(p1y, p2y));
- checkTuple.add(pk);
+ checkTuple.appendField(Math.min(p1x, p2x));
+ checkTuple.appendField(Math.min(p1y, p2y));
+ checkTuple.appendField(Math.max(p1x, p2x));
+ checkTuple.appendField(Math.max(p1y, p2y));
+ checkTuple.appendField(pk);
checkTuples.add(checkTuple);
}
@@ -162,7 +163,7 @@
RTreeCheckTuple keyCheck = (RTreeCheckTuple) rTreeTestUtils.createCheckTupleFromTuple(key, fieldSerdes,
keyFieldCount);
- ArrayList<RTreeCheckTuple> expectedResult = rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
+ HashMultiSet<RTreeCheckTuple> expectedResult = rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
indexAccessor.search(searchCursor, searchPredicate);