You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@geode.apache.org by ja...@apache.org on 2015/11/24 19:19:23 UTC
[1/2] incubator-geode git commit: [GEODE-585]: Simplify hash index
code Refactored hash index and hash index set Using modified versions of the
fastutil methods for adding and finding index positions for objects Added
hash index set unit tests Removes Pr
Repository: incubator-geode
Updated Branches:
refs/heads/develop 4b0925e30 -> abad018a9
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/abad018a/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexSetJUnitTest.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexSetJUnitTest.java b/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexSetJUnitTest.java
new file mode 100644
index 0000000..de5cebd
--- /dev/null
+++ b/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexSetJUnitTest.java
@@ -0,0 +1,504 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 at
+ *
+ * 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 com.gemstone.gemfire.cache.query.internal.index;
+
+import static org.mockito.Matchers.any;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.IntStream;
+
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.experimental.categories.Category;
+import org.mockito.invocation.InvocationOnMock;
+import org.mockito.stubbing.Answer;
+
+import com.gemstone.gemfire.cache.query.TypeMismatchException;
+import com.gemstone.gemfire.cache.query.data.Portfolio;
+import com.gemstone.gemfire.test.junit.categories.UnitTest;
+
+@Category(UnitTest.class)
+public class HashIndexSetJUnitTest {
+
+ Map<Integer, Portfolio> portfoliosMap;
+ Set<Portfolio> portfolioSet;
+ HashIndexSet his;
+
+ public void setupHashIndexSet(int numEntries) {
+ his = createHashIndexSet();
+ portfoliosMap = createPortfolioObjects(numEntries, 0);
+ portfolioSet = new HashSet<Portfolio>(portfoliosMap.values());
+ addPortfoliosToHashIndexSet(portfoliosMap, his);
+ }
+
+ private void addPortfoliosToHashIndexSet(Map<Integer, Portfolio> portfoliosMap, HashIndexSet hashIndexSet) {
+ portfoliosMap.forEach((k,v) -> {
+ try {
+ hashIndexSet.add(k, v);
+ }
+ catch (TypeMismatchException exception) {
+ throw new Error(exception);
+ }
+ });
+ }
+
+ private HashIndexSet createHashIndexSet() {
+ HashIndexSet his = new HashIndexSet();
+ HashIndex.IMQEvaluator mockEvaluator = mock(HashIndex.IMQEvaluator.class);
+ when(mockEvaluator.evaluateKey(any(Object.class))).thenAnswer(new EvaluateKeyAnswer());
+ his.setEvaluator(mockEvaluator);
+ return his;
+ }
+
+ /**
+ * we are "indexed" on indexKey. Equality of portfolios is based on ID
+ * indexKeys are based on 0 -> numEntries
+ * IDs are startID -> startID + numEntries
+ * @param numToCreate how many portfolios to create
+ * @param startID the ID value to start incrementing from
+ * @return
+ */
+ public Map<Integer, Portfolio> createPortfolioObjects(int numToCreate, int startID) {
+ Map<Integer, Portfolio> portfoliosMap = new HashMap<>();
+ IntStream.range(0, numToCreate).forEach(e -> {
+ Portfolio p = new Portfolio(e + startID);
+ p.indexKey = e;
+ portfoliosMap.put(p.indexKey, p);
+ });
+ return portfoliosMap;
+ }
+
+ @Test
+ public void testHashIndexSetAdd() throws Exception {
+ int numEntries = 100;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ his.iterator().forEachRemaining((e ->portfolioSet.remove(e)));
+ Assert.assertTrue(portfolioSet.isEmpty());
+ }
+
+ @Test
+ public void testHashIndexSetAddWithNullKey() throws Exception {
+ int numEntries = 100;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ his.add(null, new Portfolio(numEntries + 1));
+ Assert.assertEquals(numEntries + 1, his.size());
+ }
+
+ //we have to be sure that we dont cause a compaction or growth or else
+ //removed tokens will be removed and a new backing array created
+ @Test
+ public void testHashIndexSetAddUseRemoveTokenSlot() throws Exception {
+ int numEntries = 20;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ his.removeAll(portfolioSet);
+ Assert.assertEquals(numEntries, his._removedTokens);
+ Assert.assertEquals(0, his.size());
+ addPortfoliosToHashIndexSet(portfoliosMap, his);
+
+ Assert.assertEquals(0, his._removedTokens);
+ Assert.assertEquals(numEntries, his.size());
+ }
+
+ @Test
+ public void testCompactDueToTooManyRemoveTokens() throws Exception {
+ int numEntries = 100;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ his.removeAll(portfolioSet);
+ Assert.assertEquals(numEntries, his._removedTokens);
+
+ Assert.assertEquals(0, his.size());
+
+ //Very very bad but we fake out the number of removed tokens
+ his._removedTokens = his._maxSize;
+ addPortfoliosToHashIndexSet(portfoliosMap, his);
+
+ //compaction should have occured, removed tokens should now be gone
+ Assert.assertEquals(0, his._removedTokens);
+ Assert.assertEquals(numEntries, his.size());
+ }
+
+ @Test
+ public void testRehashRetainsAllValues() throws Exception {
+ int numEntries = 80;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ his.rehash(1000);
+ Assert.assertEquals(numEntries, his.size());
+ his.iterator().forEachRemaining((e ->portfolioSet.remove(e)));
+ Assert.assertTrue(portfolioSet.isEmpty());
+ }
+
+ @Test
+ public void testShrinkByRehashRetainsAllValues() throws Exception {
+ int numEntries = 20;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ his.rehash(64);
+ Assert.assertEquals(numEntries, his.size());
+ his.iterator().forEachRemaining((e ->portfolioSet.remove(e)));
+ Assert.assertTrue(portfolioSet.isEmpty());
+ }
+
+ @Test
+ public void testGetByKey() throws Exception {
+ int numEntries = 20;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ his.get(1).forEachRemaining((e ->portfolioSet.remove(e)));
+ Assert.assertEquals(numEntries - 1, portfolioSet.size());
+ }
+
+ @Test
+ public void testGetByKeyMultipleCollisions() throws Exception {
+ int numEntries = 20;
+ int keyToLookup = 1;
+ his = createHashIndexSet();
+ Map<Integer, Portfolio> collectionOfPorts1 = this.createPortfolioObjects(numEntries, 0);
+ Map<Integer, Portfolio> collectionOfPorts2 = this.createPortfolioObjects(numEntries, numEntries);
+
+ addPortfoliosToHashIndexSet(collectionOfPorts1, his);
+ addPortfoliosToHashIndexSet(collectionOfPorts2, his);
+
+ Assert.assertEquals(numEntries * 2, his.size());
+ Iterator iterator = his.get(keyToLookup);
+ int numIterated = 0;
+ while (iterator.hasNext()) {
+ numIterated ++;
+ //verify that the returned values match what we lookedup
+ Assert.assertEquals(keyToLookup, ((Portfolio)iterator.next()).indexKey);
+ }
+ Assert.assertEquals(2, numIterated);
+ }
+
+ @Test
+ public void testGetByKeyLocatesAfterMultipleColiisionsAndRemoveToken() throws Exception {
+ int numEntries = 20;
+ int keyToLookup = 1;
+ his = createHashIndexSet();
+ Map<Integer, Portfolio> collectionOfPorts1 = this.createPortfolioObjects(numEntries, 0);
+ Map<Integer, Portfolio> collectionOfPorts2 = this.createPortfolioObjects(numEntries, numEntries);
+ Map<Integer, Portfolio> collectionOfPorts3 = this.createPortfolioObjects(numEntries, numEntries * 2);
+
+ addPortfoliosToHashIndexSet(collectionOfPorts1, his);
+ addPortfoliosToHashIndexSet(collectionOfPorts2, his);
+ addPortfoliosToHashIndexSet(collectionOfPorts3, his);
+
+ Assert.assertEquals(numEntries * 3, his.size());
+ Iterator iterator = his.get(keyToLookup);
+ int numIterated = 0;
+ while (iterator.hasNext()) {
+ numIterated ++;
+ //verify that the returned values match what we lookedup
+ Assert.assertEquals(keyToLookup, ((Portfolio)iterator.next()).indexKey);
+ }
+ Assert.assertEquals(3, numIterated);
+
+ //let's remove the second collision
+ his.remove(keyToLookup, collectionOfPorts2.get(keyToLookup));
+
+ iterator = his.get(keyToLookup);
+ numIterated = 0;
+ while (iterator.hasNext()) {
+ numIterated ++;
+ //verify that the returned values match what we lookedup
+ Assert.assertEquals(keyToLookup, ((Portfolio)iterator.next()).indexKey);
+ }
+ Assert.assertEquals(2, numIterated);
+
+ //Add it back in and make sure we can iterate all 3 again
+ his.add(keyToLookup, collectionOfPorts2.get(keyToLookup));
+ iterator = his.get(keyToLookup);
+ numIterated = 0;
+ while (iterator.hasNext()) {
+ numIterated ++;
+ //verify that the returned values match what we lookedup
+ Assert.assertEquals(keyToLookup, ((Portfolio)iterator.next()).indexKey);
+ }
+ Assert.assertEquals(3, numIterated);
+
+ }
+
+ @Test
+ public void testGetAllNotMatching() throws Exception {
+ int numEntries = 20;
+ his = createHashIndexSet();
+ Map<Integer, Portfolio> collectionOfPorts1 = this.createPortfolioObjects(numEntries, 0);
+ Map<Integer, Portfolio> collectionOfPorts2 = this.createPortfolioObjects(numEntries, numEntries);
+
+ addPortfoliosToHashIndexSet(collectionOfPorts1, his);
+ addPortfoliosToHashIndexSet(collectionOfPorts2, his);
+
+ Assert.assertEquals(numEntries * 2, his.size());
+ List<Integer> keysNotToMatch = new LinkedList<>();
+ keysNotToMatch.add(3);
+ keysNotToMatch.add(4);
+ Iterator iterator = his.getAllNotMatching(keysNotToMatch);
+ int numIterated = 0;
+ while (iterator.hasNext()) {
+ numIterated ++;
+ int idFound = ((Portfolio)iterator.next()).indexKey;
+ Assert.assertTrue(idFound != 3 && idFound != 4);
+ }
+ //Make sure we iterated all the entries minus the entries that we decided not to match
+ Assert.assertEquals(numEntries * 2 - 4, numIterated);
+ }
+
+ @Test
+ public void testIndexOfObject() throws Exception {
+ int numEntries = 10;
+ his = createHashIndexSet();
+ portfoliosMap = createPortfolioObjects(numEntries, 0);
+ portfoliosMap.forEach((k,v) -> {
+ try {
+ int index = his.add(k, portfoliosMap.get(k));
+ int foundIndex = his.index(portfoliosMap.get(k));
+ Assert.assertEquals(index, foundIndex);
+ }
+ catch (TypeMismatchException ex) {
+ throw new Error(ex);
+ }
+ });
+ }
+
+ //Add multiple portfolios with the same id
+ //they should collide, we should then be able to look up each one correctly
+ @Test
+ public void testIndexOfObjectWithCollision() throws Exception {
+ int numEntries = 10;
+ his = createHashIndexSet();
+ Map<Integer, Portfolio> portfoliosMap1 = createPortfolioObjects(numEntries, 0);
+ Map<Integer, Portfolio> portfoliosMap2 = createPortfolioObjects(numEntries, numEntries);
+
+ portfoliosMap1.forEach((k,v) -> {
+ try {
+ int index = his.add(k, portfoliosMap1.get(k));
+ int foundIndex = his.index(portfoliosMap1.get(k));
+ Assert.assertEquals(index, foundIndex);
+ }
+ catch (TypeMismatchException ex) {
+ throw new Error(ex);
+ }
+ });
+ portfoliosMap2.forEach((k,v) -> {
+ try {
+ int index = his.add(k, portfoliosMap2.get(k));
+ int foundIndex = his.index(portfoliosMap2.get(k));
+ Assert.assertEquals(index, foundIndex);
+ }
+ catch (TypeMismatchException ex) {
+ throw new Error(ex);
+ }
+ });
+ }
+
+
+ @Test
+ public void testIndexWhenObjectNotInSet() {
+ int numEntries = 10;
+ his = createHashIndexSet();
+ portfoliosMap = createPortfolioObjects(numEntries, 0);
+ Assert.assertEquals(-1, his.index(portfoliosMap.get(1)));
+ }
+
+ @Test
+ public void testIndexWhenObjectNotInSetWhenPopulated() {
+ int numEntries = 10;
+ this.setupHashIndexSet(numEntries);
+ Assert.assertEquals(-1, his.index(new Portfolio(numEntries+1)));
+ }
+
+
+ @Test
+ public void testRemove() throws Exception {
+ int numEntries = 20;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ portfoliosMap.forEach((k,v) -> his.remove(k, v));
+ Assert.assertEquals(0, his.size());
+ }
+
+ //Test remove where we look for an instance that is not at the specified index slot
+ @Test
+ public void testRemoveIgnoreSlot() throws Exception {
+ int numEntries = 20;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ portfoliosMap.forEach((k,v) -> his.remove(k, v, his.index(v)));
+ Assert.assertEquals(numEntries, his.size());
+ }
+
+ @Test
+ public void testRemoveAtWithNull() throws Exception {
+ his = createHashIndexSet();
+ Assert.assertTrue(his.isEmpty());
+ Assert.assertFalse(his.removeAt(0));
+ }
+
+ @Test
+ public void testRemoveAtWithRemoveToken() throws Exception {
+ his = createHashIndexSet();
+ int index = his.add(1, new Portfolio(1));
+ Assert.assertTrue(his.removeAt(index));
+ Assert.assertFalse(his.removeAt(index));
+ }
+
+ @Test
+ public void testHashIndexRemoveAll() throws Exception {
+ int numEntries = 100;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ his.removeAll(portfolioSet);
+ Assert.assertTrue(his.isEmpty());
+ }
+
+ //Remove all should still remove all portfolios provided, even if there are more provided then contained
+ @Test
+ public void testHashIndexRemoveAllWithAdditionalPortfolios() throws Exception {
+ int numEntries = 100;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ portfolioSet.add(new Portfolio(numEntries + 1));
+ his.removeAll(portfolioSet);
+ Assert.assertTrue(his.isEmpty());
+ }
+
+ @Test
+ public void testHashIndexContainsAll() throws Exception {
+ int numEntries = 100;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ Assert.assertTrue(his.containsAll(portfolioSet));
+ }
+
+ @Test
+ public void testHashIndexRetainAll() throws Exception {
+ int numEntries = 10;
+ setupHashIndexSet(numEntries);
+ Set subset = new HashSet();
+ portfolioSet.forEach(e -> {if (e.indexKey % 2 == 0) {subset.add(e);}});
+ Assert.assertEquals(numEntries, his.size());
+ his.retainAll(subset);
+ his.iterator().forEachRemaining((e ->subset.remove(e)));
+ Assert.assertTrue(subset.isEmpty());
+ Assert.assertEquals(numEntries/2, his.size());
+ }
+
+ @Test
+ public void testHashIndexContainsAllShouldReturnFalse() throws Exception {
+ int numEntries = 100;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ portfolioSet.add(new Portfolio(numEntries + 1));
+ Assert.assertFalse(his.containsAll(portfolioSet));
+ }
+
+ @Test
+ public void testClear() throws Exception {
+ int numEntries = 100;
+ setupHashIndexSet(numEntries);
+
+ Assert.assertEquals(numEntries, his.size());
+ his.clear();
+ Assert.assertTrue(his.isEmpty());
+ Assert.assertTrue(his._removedTokens == 0);
+ }
+
+ @Test
+ public void testAreNullObjectsEqual() throws Exception {
+ his = createHashIndexSet();
+ Assert.assertTrue(his.areObjectsEqual(null, null));
+ }
+
+ @Test
+ public void testAreIndexeSetsEqualAndHashCodeSame() throws Exception {
+ Map<Integer, Portfolio> portfolioMap = createPortfolioObjects(100, 0);
+ HashIndexSet indexSet1 = createHashIndexSet();
+ HashIndexSet indexSet2 = createHashIndexSet();
+
+ addPortfoliosToHashIndexSet(portfolioMap, indexSet1);
+ addPortfoliosToHashIndexSet(portfolioMap, indexSet2);
+
+ Assert.assertTrue(indexSet1.equals(indexSet2));
+ Assert.assertTrue(indexSet2.equals(indexSet1));
+ Assert.assertEquals(indexSet1.hashCode(), indexSet2.hashCode());
+ }
+
+ @Test
+ public void testAreIndexeSetsNotEqualAndHashCodeDifferent() throws Exception {
+ Map<Integer, Portfolio> portfolioMap = createPortfolioObjects(100, 0);
+ HashIndexSet indexSet1 = createHashIndexSet();
+ HashIndexSet indexSet2 = createHashIndexSet();
+
+ addPortfoliosToHashIndexSet(portfolioMap, indexSet1);
+
+ indexSet2.add(1, portfolioMap.get(1));
+ Assert.assertFalse(indexSet2.equals(indexSet1));
+ Assert.assertFalse(indexSet1.equals(indexSet2));
+ Assert.assertNotEquals(indexSet1.hashCode(), indexSet2.hashCode());
+ }
+
+ @Test
+ public void testIndexSetNotEqualsOtherObjectType() {
+ HashIndexSet indexSet = createHashIndexSet();
+ Assert.assertFalse(indexSet.equals("Other type"));
+ Assert.assertFalse(indexSet.equals(new Object()));
+ }
+
+ private static class EvaluateKeyAnswer implements Answer {
+
+ @Override
+ public Object answer(InvocationOnMock invocation) throws Throwable {
+ Object evalOn = invocation.getArgumentAt(0, Object.class);
+ if (evalOn instanceof Portfolio) {
+ Portfolio p = (Portfolio) evalOn;
+ return p.indexKey;
+ }
+ return null;
+ }
+
+ }
+
+
+}
[2/2] incubator-geode git commit: [GEODE-585]: Simplify hash index
code Refactored hash index and hash index set Using modified versions of the
fastutil methods for adding and finding index positions for objects Added
hash index set unit tests Removes Pr
Posted by ja...@apache.org.
[GEODE-585]: Simplify hash index code
Refactored hash index and hash index set
Using modified versions of the fastutil methods for adding and finding index positions for objects
Added hash index set unit tests
Removes PrimeFinder, ObjectProcedure, and HashIndexStrategy
Project: http://git-wip-us.apache.org/repos/asf/incubator-geode/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-geode/commit/abad018a
Tree: http://git-wip-us.apache.org/repos/asf/incubator-geode/tree/abad018a
Diff: http://git-wip-us.apache.org/repos/asf/incubator-geode/diff/abad018a
Branch: refs/heads/develop
Commit: abad018a944e870b418de81ebefad0524010f225
Parents: 4b0925e
Author: Jason Huynh <hu...@gmail.com>
Authored: Fri Nov 20 16:03:33 2015 -0800
Committer: Jason Huynh <hu...@gmail.com>
Committed: Tue Nov 24 10:18:31 2015 -0800
----------------------------------------------------------------------
.../cache/query/internal/index/HashIndex.java | 176 ++-
.../query/internal/index/HashIndexSet.java | 1086 ++++++------------
.../query/internal/index/HashIndexStrategy.java | 90 --
.../gemfire/internal/util/ObjectProcedure.java | 30 -
.../gemfire/internal/util/PrimeFinder.java | 159 ---
.../internal/index/HashIndexJUnitTest.java | 23 +-
.../internal/index/HashIndexSetJUnitTest.java | 504 ++++++++
7 files changed, 922 insertions(+), 1146 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/abad018a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndex.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndex.java b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndex.java
index 911fd6e..465c038 100755
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndex.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndex.java
@@ -160,7 +160,7 @@ public class HashIndex extends AbstractIndex {
}
}
- entriesSet = new HashIndexSet(entryToValuesMap, entryToOldKeysMap, internalIndexStats);
+ entriesSet = new HashIndexSet();
}
/**
@@ -233,17 +233,49 @@ public class HashIndex extends AbstractIndex {
if (logger.isDebugEnabled()) {
logger.debug("A removed or invalid token was being added, and we had an old mapping.");
}
- entriesSet.remove(oldKey, entry, true);
+ removeFromEntriesSet(oldKey, entry, true);
}
return;
}
}
- this.entriesSet.add(newKey, entry);
+
+ // Before adding the entry with new value, remove it from reverse map and
+ // using the oldValue remove entry from the forward map.
+ // Reverse-map is used based on the system property
+ Object oldKey = getOldKey(entry);
+
+ int indexSlot = this.entriesSet.add(newKey, entry);
+
+ if (indexSlot >= 0) {
+ // Update the reverse map
+ if (IndexManager.isObjectModificationInplace()) {
+ this.entryToValuesMap.put(entry, newKey);
+ }
+ if (newKey != null && oldKey != null) {
+ removeFromEntriesSet(oldKey, entry, false, indexSlot);
+ }
+ // Update Stats after real addition
+ internalIndexStats.incNumValues(1);
+
+ }
} catch (TypeMismatchException ex) {
throw new IMQException("Could not add object of type "
+ key.getClass().getName(), ex);
}
}
+
+ private Object getOldKey(RegionEntry entry) throws TypeMismatchException {
+ Object oldKey = null;
+ if (IndexManager.isObjectModificationInplace() && this.entryToValuesMap.containsKey(entry)) {
+ oldKey = this.entryToValuesMap.get(entry);
+ } else if (!IndexManager.isObjectModificationInplace() && this.entryToOldKeysMap != null) {
+ Map oldKeyMap = this.entryToOldKeysMap.get();
+ if (oldKeyMap != null) {
+ oldKey = TypeUtils.indexKeyFor(oldKeyMap.get(entry));
+ }
+ }
+ return oldKey;
+ }
/**
* @param opCode
@@ -293,15 +325,27 @@ public class HashIndex extends AbstractIndex {
// space, but there is no way to ask an ArrayList what
// it's current capacity is..so we trim after every
// removal
- boolean found = false;
try {
Object newKey = TypeUtils.indexKeyFor(key);
- found = this.entriesSet.remove(newKey, entry, updateReverseMap);
+ removeFromEntriesSet(newKey, entry, updateReverseMap);
} catch (TypeMismatchException ex) {
throw new IMQException("Could not add object of type "
+ key.getClass().getName(), ex);
}
}
+
+ private void removeFromEntriesSet(Object newKey, RegionEntry entry, boolean updateReverseMap) {
+ removeFromEntriesSet(newKey, entry, updateReverseMap, -1);
+ }
+
+ private void removeFromEntriesSet(Object newKey, RegionEntry entry, boolean updateReverseMap, int ignoreThisSlot) {
+ if (this.entriesSet.remove(newKey, entry, ignoreThisSlot)) {
+ if (updateReverseMap && IndexManager.isObjectModificationInplace()) {
+ entryToValuesMap.remove(entry);
+ }
+ internalIndexStats.incNumValues(-1);
+ }
+ }
// // IndexProtocol interface implementation
public boolean clear() throws QueryException {
@@ -628,8 +672,7 @@ public class HashIndex extends AbstractIndex {
@Override
void instantiateEvaluator(IndexCreationHelper ich) {
this.evaluator = new IMQEvaluator(ich);
- this.entriesSet.setHashIndexStrategy(new HashStrategy(
- (IMQEvaluator) evaluator));
+ this.entriesSet.setEvaluator((HashIndex.IMQEvaluator)evaluator);
this.comparator = ((IMQEvaluator) evaluator).comparator;
}
@@ -672,9 +715,9 @@ public class HashIndex extends AbstractIndex {
Object obj = entriesIter.next();
Object key = null;
if (obj != null && obj != HashIndexSet.REMOVED) {
-
RegionEntry re = (RegionEntry) obj;
if (applyOrderBy) {
+ key = ((HashIndex.IMQEvaluator)evaluator).evaluateKey(obj);
orderedKeys.add(new Object[]{key,i++});
addValueToResultSet(re, orderedResults, iterOps, runtimeItr, context, projAttrib, intermediateResults, isIntersection, limit, observer, iteratorCreationTime);
} else {
@@ -856,19 +899,22 @@ public class HashIndex extends AbstractIndex {
void recreateIndexData() throws IMQException {
// Mark the data maps to null & call the initialization code of index
this.entriesSet.clear();
- int numKeys = (int) this.internalIndexStats.getNumberOfKeys();
- if (numKeys > 0) {
- this.internalIndexStats.incNumKeys(-numKeys);
- }
- int numValues = (int) this.internalIndexStats.getNumberOfValues();
- if (numValues > 0) {
- this.internalIndexStats.incNumValues(-numValues);
- }
- int updates = (int) this.internalIndexStats.getNumUpdates();
- if (updates > 0) {
- this.internalIndexStats.incNumUpdates(updates);
- }
- this.initializeIndex(true);
+ if (IndexManager.isObjectModificationInplace()) {
+ entryToValuesMap.clear();
+ }
+ int numKeys = (int) this.internalIndexStats.getNumberOfKeys();
+ if (numKeys > 0) {
+ this.internalIndexStats.incNumKeys(-numKeys);
+ }
+ int numValues = (int) this.internalIndexStats.getNumberOfValues();
+ if (numValues > 0) {
+ this.internalIndexStats.incNumValues(-numValues);
+ }
+ int updates = (int) this.internalIndexStats.getNumUpdates();
+ if (updates > 0) {
+ this.internalIndexStats.incNumUpdates(updates);
+ }
+ this.initializeIndex(true);
}
public String dump() {
@@ -1435,7 +1481,7 @@ public class HashIndex extends AbstractIndex {
return context;
}
- Object evaluateKey(Object object) {
+ public Object evaluateKey(Object object) {
Object value = object;
ExecutionContext newContext = null;
@@ -1459,6 +1505,10 @@ public class HashIndex extends AbstractIndex {
logger.debug("Could not reevaluate key for hash index");
}
}
+
+ if (key == null) {
+ key = IndexManager.NULL;
+ }
return key;
}
@@ -1471,8 +1521,8 @@ public class HashIndex extends AbstractIndex {
//We check to see if an update was in progress. If so (and is the way these turn to undefined),
//the value is reevaluated and removed from the result set if it does not match the
//search criteria. This occurs in addToResultsFromEntries()
- Object key0 = ((Object[])arg0)[1];
- Object key1 = ((Object[])arg1)[1];
+ Object key0 = ((Object[])arg0)[0];
+ Object key1 = ((Object[])arg1)[0];
Comparable comp0 = (Comparable) key0;
Comparable comp1 = (Comparable) key1;
@@ -1512,82 +1562,12 @@ public class HashIndex extends AbstractIndex {
throws IMQException {
// TODO Auto-generated method stub
}
-
- private class HashStrategy implements HashIndexStrategy {
-
- private AttributeDescriptor attDesc;
-
- private IMQEvaluator evaluator;
-
- public HashStrategy(IMQEvaluator evaluator) {
- this.evaluator = evaluator;
- }
-
- public final int computeHashCode(Object o) {
- return computeHashCode(o, false);
- }
-
- public final int computeHashCode(Object o, boolean reevaluateKey) {
- if (reevaluateKey) {
- return computeKey(o).hashCode();
- }
- return o.hashCode();
- }
-
- public final Object computeKey(Object o) {
- Object key = evaluator.evaluateKey(o);
- if (key == null) {
- key = IndexManager.NULL;
- }
- return key;
- }
-
- public final boolean equalsOnAdd(Object o1, Object o2) {
- if (o1 == null) {
- return o2 == null;
- }
- try {
- return TypeUtils.compare(o1, o2, OQLLexerTokenTypes.TOK_EQ).equals(Boolean.TRUE);
- }
- catch (TypeMismatchException e) {
- return o1.equals(o2);
- }
- }
-
- /*
- * expects object o to be a region entry
- */
- public boolean equalsOnGet(Object indexKey, Object o) {
- Object fieldValue = evaluator.evaluateKey(o);
-
- if (fieldValue == null && indexKey == IndexManager.NULL) {
- return true;
- } else {
- try {
- if (fieldValue instanceof PdxString) {
- if (indexKey instanceof String) {
- fieldValue = ((PdxString) fieldValue).toString();
- }
- }
- else if (indexKey instanceof PdxString) {
- if (fieldValue instanceof String) {
- fieldValue = new PdxString((String)fieldValue);
- }
- }
- return TypeUtils.compare(fieldValue, indexKey, OQLLexerTokenTypes.TOK_EQ).equals(Boolean.TRUE);
- }
- catch (TypeMismatchException e) {
- return fieldValue.equals(indexKey);
- }
- }
- }
- }
-
+
public boolean isEmpty() {
return entriesSet.isEmpty();
}
- public String printAll() {
- return this.entriesSet.printAll();
- }
+// public String printAll() {
+// return this.entriesSet.printAll();
+// }
}
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/abad018a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexSet.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexSet.java b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexSet.java
index 85887d4..2fa72d1 100755
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexSet.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexSet.java
@@ -14,8 +14,29 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
+
+/*
+ * insertionIndex(), index(), trimToSize() are based on code provided by fastutil
+ * They are based from add(), contains() and other methods from ObjectOpenHashSet
+ * We have used the traversing mechanism and the HashCommon.mix()
+ * Copyright (C) 2002-2014 Sebastiano Vigna
+ *
+ * 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 at
+ *
+ * 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 com.gemstone.gemfire.cache.query.internal.index;
+import static it.unimi.dsi.fastutil.HashCommon.arraySize;
+import it.unimi.dsi.fastutil.HashCommon;
import it.unimi.dsi.fastutil.objects.Object2ObjectOpenHashMap;
import java.util.Collection;
@@ -24,27 +45,23 @@ import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
-import java.util.concurrent.ConcurrentMap;
import com.gemstone.gemfire.cache.query.TypeMismatchException;
-import com.gemstone.gemfire.cache.query.internal.AttributeDescriptor;
import com.gemstone.gemfire.cache.query.internal.index.AbstractIndex.InternalIndexStatistics;
+import com.gemstone.gemfire.cache.query.internal.parse.OQLLexerTokenTypes;
import com.gemstone.gemfire.cache.query.internal.types.TypeUtils;
import com.gemstone.gemfire.internal.cache.CachePerfStats;
import com.gemstone.gemfire.internal.cache.CachedDeserializable;
import com.gemstone.gemfire.internal.cache.RegionEntry;
import com.gemstone.gemfire.internal.offheap.StoredObject;
-import com.gemstone.gemfire.internal.util.ObjectProcedure;
-import com.gemstone.gemfire.internal.util.PrimeFinder;
+import com.gemstone.gemfire.pdx.internal.PdxString;
/**
- * An implementation of the <tt>Set</tt> interface that uses an open-addressed
- * hash table to store its contents.
- *
- * On collisions, will store contents in an IndexElemArray and once a threshold
- * has been hit, will store in ConcurrentHashSets.
+ * An implementation of the <tt>Set</tt> interface for the HashIndex
+ * Not exactly a set as the hash keys can actually collide but will
+ * continue to look for an empty location to store the value
+ *
*/
-
public class HashIndexSet implements Set {
/**
@@ -53,113 +70,59 @@ public class HashIndexSet implements Set {
*/
private transient CachePerfStats cacheStats;
- /** the current number of occupied slots in the hash. */
+ /** the current number of entries in the set */
protected transient int _size;
-
- /** the current number of free slots in the hash. */
+
+ /** the current number of open slots in the hash.
+ * Originally used when we collapsed collided keys into collections
+ * Not really used now */
protected transient int _free;
-
- /** the current number of occupied slots in the hash. */
- protected transient int _removedTokens;
+
+ /** number of removed tokens in the set, these are index positions that may be reused*/
+ transient int _removedTokens;
/** the load above which rehashing occurs. */
protected static final float DEFAULT_LOAD_FACTOR = 0.5f;
- /**
- * the default initial capacity for the hash table. This is one less than a
- * prime value because one is added to it when searching for a prime capacity
- * to account for the free slot required by open addressing. Thus, the real
- * default capacity is 11.
- */
- protected static final int DEFAULT_INITIAL_CAPACITY = 100;
+ protected static final int DEFAULT_INITIAL_CAPACITY = 128;
- /**
- * Determines how full the internal table can become before rehashing is
- * required. This must be a value in the range: 0.0 < loadFactor < 1.0. The
- * default value is 0.5, which is about as large as you can get in open
- * addressing without hurting performance. Cf. Knuth, Volume 3., Chapter 6.
- */
protected float _loadFactor;
+
+ /** size of the backing table (-1)**/
+ protected int n;
+
+ /** used for hashing into the table**/
+ protected int _mask;
/**
- * The maximum number of elements allowed without allocating more space.
+ * The maximum number of elements before rehashing
*/
protected int _maxSize;
- protected static final int CONDITIONAL_COMPACT_FACTOR = 2;
-
- //If after an update, the number of removed tokens X percent of the max size,
- //we will compact and rehash to remove the tokens.
+ /** If after an update, the number of removed tokens X percent of the max size,
+ * we will compact and rehash to remove the tokens.
+ */
protected static final float CONDITIONAL_REMOVED_TOKEN_REHASH_FACTOR = .7f;
/** the set of Objects */
protected transient Object[] _set;
- /** the strategy used to hash objects in this collection. */
- protected HashIndexStrategy _hashingStrategy;
+ protected HashIndex.IMQEvaluator _imqEvaluator;
+ /**
+ * The removed token
+ */
protected static final Object REMOVED = new Object();
-
+
static boolean TEST_ALWAYS_REHASH = false;
/**
- * Map for RegionEntries=>value of indexedExpression (reverse map)
+ * This is used when inplace modification is off to detect old key
*/
- private ConcurrentMap<Object, Object> entryToValuesMap;
- protected ThreadLocal<Object2ObjectOpenHashMap> entryToOldKeysMap;
- protected InternalIndexStatistics internalIndexStats;
-
- private AttributeDescriptor attDesc;
- /**
- * Creates a new <code>HashIndexSet</code> instance with the default capacity
- * and load factor.
- */
public HashIndexSet() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
- }
-
- public HashIndexSet(ConcurrentMap reverseMap, ThreadLocal<Object2ObjectOpenHashMap> entryToOldKeysMap, InternalIndexStatistics internalIndexStats) {
- this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
- this.entryToValuesMap = reverseMap;
- this.entryToOldKeysMap = entryToOldKeysMap;
- this.internalIndexStats = internalIndexStats;
- }
-
- /**
- * Creates a new <code>HashIndexSet</code> instance with the default capacity
- * and load factor.
- *
- * @param strategy used to compute hash codes and to compare objects.
- */
- public HashIndexSet(HashIndexStrategy strategy) {
- this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
- this._hashingStrategy = strategy;
- }
-
- /**
- * Creates a new <code>HashIndexSet</code> instance with a prime capacity
- * equal to or greater than <tt>initialCapacity</tt> and with the default load
- * factor.
- *
- * @param initialCapacity
- * an <code>int</code> value
- */
- public HashIndexSet(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
- /**
- * Creates a new <code>HashIndexSet</code> instance with a prime capacity
- * equal to or greater than <tt>initialCapacity</tt> and with the default load
- * factor.
- *
- * @param initialCapacity an <code>int</code> value
- * @param strategy used to compute hash codes and to compare objects.
- */
- public HashIndexSet(int initialCapacity, HashIndexStrategy strategy) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- this._hashingStrategy = strategy;
}
/**
@@ -170,57 +133,12 @@ public class HashIndexSet implements Set {
* @param initialCapacity an <code>int</code> value
* @param loadFactor a <code>float</code> value
*/
- public HashIndexSet(int initialCapacity, float loadFactor) {
- _loadFactor = loadFactor;
- setUp((int) Math.ceil(initialCapacity / loadFactor));
- }
-
- /**
- * Creates a new <code>HashIndexSet</code> instance with a prime capacity
- * equal to or greater than <tt>initialCapacity</tt> and with the specified
- * load factor.
- *
- * @param initialCapacity
- * an <code>int</code> value
- * @param loadFactor
- * a <code>float</code> value
- * @param strategy
- * used to compute hash codes and to compare objects.
- */
- public HashIndexSet(int initialCapacity, float loadFactor,
- HashIndexStrategy strategy) {
- this(initialCapacity, loadFactor);
- this._hashingStrategy = strategy;
- }
-
- /**
- * Creates a new <code>HashIndexSet</code> instance containing the elements of
- * <tt>collection</tt>.
- *
- * @param collection
- * a <code>Collection</code> value
- */
- public HashIndexSet(Collection collection) {
- this(collection.size());
- addAll(collection);
- }
-
- /**
- * Creates a new <code>HashIndexSet</code> instance containing the elements of
- * <tt>collection</tt>.
- *
- * @param collection
- * a <code>Collection</code> value
- * @param strategy
- * used to compute hash codes and to compare objects.
- */
- public HashIndexSet(Collection collection, HashIndexStrategy strategy) {
- this(collection.size(), strategy);
- addAll(collection);
+ private HashIndexSet(int initialCapacity, float loadFactor) {
+ setUp(initialCapacity , loadFactor);
}
- public void setHashIndexStrategy(HashIndexStrategy hashingStrategy) {
- this._hashingStrategy = hashingStrategy;
+ public void setEvaluator(HashIndex.IMQEvaluator evaluator) {
+ this._imqEvaluator = evaluator;
}
/**
@@ -241,71 +159,62 @@ public class HashIndexSet implements Set {
public boolean contains(Object obj) {
return index(obj) >= 0;
}
-
+
/**
- * @param object can be either a region entry or index key
- * @param recomputeKey
- whether the object is a region entry and needs to have the key recomputed
+ * @param object is the index key
* @return the hash key
*/
-
- private int computeHash(Object object, boolean recomputeKey) {
- return _hashingStrategy.computeHashCode(object, recomputeKey) & 0x7fffffff;
+
+ private int computeHash(Object object) {
+ return object.hashCode();
}
/**
* Locates the index of <tt>obj</tt>.
*
- * @param obj an <code>Object</code> value, expected to be a
+ * @param obj an <code>Object</code> value, expected to be the value object
* @return the index of <tt>obj</tt> or -1 if it isn't in the set.
*/
protected int index(Object obj) {
- return index(_hashingStrategy.computeKey(obj), obj);
+ return index(_imqEvaluator.evaluateKey(obj), obj);
}
-
+
protected int index(Object key, Object obj) {
return index(key, obj, -1);
}
-
+
/**
* Locates index slot of object using the provided key (in this case we are passing in old key)
+ *
* @param key
* @param obj
* @return the indexSlot of the given key/object combination
*/
protected int index(Object key, Object obj, int ignoreThisSlot) {
- int hash, probe, index, length;
+ int hash;
+ int pos;
Object[] set;
- Object cur;
-
+ int mask = _mask;
set = _set;
- length = set.length;
- hash = computeHash(key, false);
- index = hash % length;
- cur = set[index];
-
- long start = -1L;
- if (this.cacheStats != null) {
- start = this.cacheStats.getStatTime();
- }
- //Find the correct collection that matches key of the object we are looking for
- //if one exists, we then look to see if the element exists in the collection
- //If a collection is not correct, we probe for the next collection until a null is found
- while (cur != null) {
- if (cur != REMOVED && index != ignoreThisSlot) {
- if (cur instanceof RegionEntry) {
- if (_hashingStrategy.equalsOnAdd(obj, cur)) {
- return index;
- }
- }
- }
-
- probe = 1 + (hash % (length - 2));
- index -= probe;
- if (index < 0) {
- index += length;
+ Object curr;
+ hash = computeHash(key);
+
+ /* Code originated from fastutils
+ * Copyright (C) 2002-2014 Sebastiano Vigna
+ *
+ * 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 at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ */
+ if (!((curr = set[pos = (it.unimi.dsi.fastutil.HashCommon.mix(hash)) & mask]) == null || curr == REMOVED)) {
+ if (((curr).equals(obj) && pos != ignoreThisSlot))
+ return pos;
+ while (!((curr = set[pos = (pos + 1) & mask]) == null || curr == REMOVED)) {
+ if (((curr).equals(obj)) && pos != ignoreThisSlot)
+ return pos;
}
- cur = set[index];
}
return -1;
}
@@ -313,18 +222,17 @@ public class HashIndexSet implements Set {
public Iterator getAll() {
return getAllNotMatching(Collections.EMPTY_LIST);
}
-
+
public Iterator getAllNotMatching(Collection keysToRemove) {
return new HashIndexSetIterator(keysToRemove, _set);
}
-
+
/**
* Locates the index of <tt>obj</tt>.
*
* @param indexKey
* an <code>Object</code> value that represents the index key
- * @return the a collection of objects that match the index key or an empty
- * collection if none match
+ * @return Iterator over a collection of objects that match the key
*/
public Iterator get(Object indexKey) {
return new HashIndexSetIterator(indexKey, _set);
@@ -332,7 +240,7 @@ public class HashIndexSet implements Set {
/**
*
- * @param set the array that all elements are stored in
+ * @param set represents the array that all elements are stored in
* @param index
* the array index location to store the object. This should be
* calculated by one of the insertionIndex methods
@@ -342,60 +250,36 @@ public class HashIndexSet implements Set {
private boolean addObjectToSet(Object[] set, int index, Object newObject) {
boolean added = true;
if (index < 0) {
- throwObjectContractViolation(set[(-index - 1)], newObject);
+ throw new ArrayIndexOutOfBoundsException("Cannot add:" + newObject + " into array position:" + index);
}
Object oldObject = set[index];
if (oldObject == null || oldObject == REMOVED) {
set[index] = newObject;
- } else if (oldObject instanceof RegionEntry) {
- IndexElemArray elemArray = new IndexElemArray();
- elemArray.add(oldObject);
- elemArray.add(newObject);
- set[index] = elemArray;
- } else if (oldObject instanceof IndexConcurrentHashSet) {
- added = ((IndexConcurrentHashSet) oldObject).add(newObject);
- } else if (oldObject instanceof IndexElemArray) {
- IndexElemArray elemArray = (IndexElemArray) oldObject;
- if (elemArray.size() >= IndexManager.INDEX_ELEMARRAY_THRESHOLD) {
- IndexConcurrentHashSet newSet = new IndexConcurrentHashSet(
- IndexManager.INDEX_ELEMARRAY_THRESHOLD + 20, 0.75f, 1);
- newSet.addAll(elemArray);
- newSet.add(newObject);
- set[index] = newSet;
- } else {
- elemArray.add(newObject);
- }
- }
+ }
return added;
}
/**
- * Inserts a value into the set.
- *
- * @param obj an <code>Object</code> value
- * @return true if the set was modified by the add operation
+ * Unsupported, we do not use HashIndexSet as a general all purpose set
*/
- public synchronized boolean add(Object obj){
- throw new UnsupportedOperationException(
- "add(Object) not supported, try add(Object key, Object obj) instead");
+ public synchronized boolean add(Object obj) {
+ throw new UnsupportedOperationException("add(Object) not supported, try add(Object key, Object obj) instead");
}
- public synchronized boolean add(Object indexKey, Object obj) throws TypeMismatchException {
- // Before adding the entry with new value, remove it from reverse map and
- // using the oldValue remove entry from the forward map.
- // Reverse-map is used based on the system property
- Object oldKey = null;
- if (IndexManager.isObjectModificationInplace() && this.entryToValuesMap.containsKey(obj)){
- oldKey = this.entryToValuesMap.get(obj);
- }
- else if (!IndexManager.isObjectModificationInplace() && this.entryToOldKeysMap != null) {
- Map oldKeyMap = this.entryToOldKeysMap.get();
- if (oldKeyMap != null) {
- oldKey = TypeUtils.indexKeyFor(oldKeyMap.get(obj));
- }
+ /**
+ * Add an object using the hash value of the provided indexKey
+ *
+ * @param indexKey
+ * @param obj the object to add
+ * @return true if object has been added
+ * @throws TypeMismatchException
+ */
+ public synchronized int add(Object indexKey, Object obj) throws TypeMismatchException {
+ if (indexKey == null) {
+ indexKey = IndexManager.NULL;
}
- // Note we cannot make the optimization for hash index. Due to in place modification
+ // Note we cannot make the below optimization for hash index. Due to in place modification
// where old key == new key (when no reverse map) we end up not updating to the correct slot in this case
// If oldKey and the newKey are same there is no need to update the
// index-maps.
@@ -403,132 +287,70 @@ public class HashIndexSet implements Set {
// || indexKey.equals(oldKey)) {
// return false;
// }
-
- //grow/shrink capacity if needed
+
+ // grow/shrink capacity if needed
preInsertHook();
int indexSlot = insertionIndex(indexKey, obj, _set);
- if (indexSlot < 0) {
- return false; // already present in set, nothing to add
- }
Object old = _set[indexSlot];
- boolean added = addObjectToSet(_set, indexSlot, obj);
-
- if (added) {
- //Update the reverse map
- if ( IndexManager.isObjectModificationInplace()) {
- this.entryToValuesMap.put(obj, indexKey);
- }
- if (indexKey != null && oldKey != null) {
- remove(oldKey, obj, false, indexSlot);
- }
- // Update Stats after real addition
- internalIndexStats.incNumValues(1);
- }
-
+ addObjectToSet(_set, indexSlot, obj);
+
// only call this now if we are adding to an actual empty slot, otherwise we
// have reused
// and inserted into a set or array
if (old == null) {
postInsertHook(true);
- }
- else {
+ } else {
postInsertHook(false);
}
- return added; // yes, we added something
+ return indexSlot; // yes, we added something
}
/**
- * Locates the index at which <tt>obj</tt> can be inserted. if there is
- * already a value equal()ing <tt>obj</tt> in the set, returns that value's
- * index as <tt>-index - 1</tt>.
+ * Locates the next available insertion index for the provided indexKey and set
*
* @param obj
* an <code>Object</code> value
- * @return the index of a FREE slot at which obj can be inserted or, if obj is
- * already stored in the hash, the negative value of that index, minus
- * 1: -index -1.
- */
- protected int insertionIndex(Object obj) {
- return insertionIndex(_hashingStrategy.computeKey(obj), obj, _set);
- }
-
- protected int insertionIndex(Object obj, Object[] set) {
- return insertionIndex(_hashingStrategy.computeKey(obj), obj, set);
- }
-
-
- /**
- * Locates the index at which <tt>obj</tt> can be inserted. if there is
- * already a value equal()ing <tt>obj</tt> in the set, returns that value's
- * index as <tt>-index - 1</tt>.
- *
- * @param obj
- * an <code>Object</code> value
- * @return the index of a FREE slot at which obj can be inserted or, if obj is
- * already stored in the hash, the negative value of that index, minus
- * 1: -index -1.
+ * @return the index of an open or resused position
*/
protected int insertionIndex(Object indexKey, Object obj, Object[] set) {
- int hash, probe, indexSlot, length;
- Object cur;
-
- length = set.length;
- hash = computeHash(indexKey, false);
- indexSlot = hash % length;
-
- cur = set[indexSlot];
+ int hash;
+ int pos;
+ int mask = _mask;
+ Object curr;
+ final Object[] array = set;
+ hash = computeHash(indexKey);
- if (cur == null) {
- return indexSlot; // empty, all done
- }
-
- // Getting here means we have yet to find the correct key collection
- // so we must find the double hash
long start = -1L;
if (this.cacheStats != null) {
start = this.cacheStats.getStatTime();
this.cacheStats.incQueryResultsHashCollisions();
}
try {
-
- // compute the double hash
- probe = 1 + (hash % (length - 2));
- // if the slot we landed on is FULL (but not removed), probe
- // until we find an empty slot, a REMOVED slot, or an element
- // equal to the one we are trying to insert.
- // finding an empty slot means that the value is not present
- // and that we should use that slot as the insertion point;
- // finding a REMOVED slot means that we need to keep searching,
- // however we want to remember the offset of that REMOVED slot
- // so we can reuse it in case a "new" insertion (i.e. not an update)
- // is possible.
- // finding a matching value means that we've found that our desired
- // key is already in the table
- if (cur != REMOVED) {
- // starting at the natural offset, probe until we find an
- // offset that isn't full.
- do {
-
- indexSlot -= probe;
- if (indexSlot < 0) {
- indexSlot += length;
- }
- cur = set[indexSlot];
- } while (cur != null && cur != REMOVED);
+ /* Code originated from fastutils
+ * Copyright (C) 2002-2014 Sebastiano Vigna
+ *
+ * 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 at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ */
+ if (!((curr = array[pos = (it.unimi.dsi.fastutil.HashCommon.mix(hash)) & mask]) == null || curr == REMOVED)) {
+ while (!((curr = array[pos = (pos + 1) & mask]) == null || curr == REMOVED)) {
+ }
}
- return indexSlot;
+ return pos;
} finally {
if (this.cacheStats != null) {
this.cacheStats.endQueryResultsHashCollisionProbe(start);
}
}
}
-
+
@Override
- // GemStoneAddition
public boolean equals(Object other) {
- if (!(other instanceof Set)) {
+ if (!(other instanceof HashIndexSet)) {
return false;
}
Set that = (Set) other;
@@ -539,164 +361,82 @@ public class HashIndexSet implements Set {
}
@Override
- // GemStoneAddition
public int hashCode() {
- HashProcedure p = new HashProcedure();
- forEach(p);
- return p.getHashCode();
- }
-
- /**
- * Executes <tt>procedure</tt> for each element in the set.
- *
- * @param procedure
- * a <code>TObjectProcedure</code> value
- * @return false if the loop over the set terminated because the procedure
- * returned false for some value.
- */
- public boolean forEach(ObjectProcedure procedure) {
+ int hash = 0;
Object[] set = _set;
for (int i = set.length; i-- > 0;) {
- if (set[i] != null && set[i] != REMOVED && !procedure.executeWith(set[i])) {
- return false;
+ if (set[i] != null && set[i] != REMOVED) {
+ hash += set[i].hashCode();
}
}
- return true;
- }
-
- protected/* GemStoneAddition */final class HashProcedure implements
- ObjectProcedure {
- private int h = 0;
-
- public int getHashCode() {
- return h;
- }
-
- public final boolean executeWith(Object key) {
- h += _hashingStrategy.computeHashCode(key);
- return true;
- }
+ return hash;
}
/**
- * Expands the set to accomodate new values.
+ * Expands or contracts a set to the new specified n.
*
- * @param newCapacity
- * an <code>int</code> value
+ * @param newN the expected size
*/
- // GemStoneAddition
- protected void rehash(int newCapacity) {
+ protected void rehash(int newN) {
if (TEST_ALWAYS_REHASH) {
- Thread.yield();
+ Thread.yield();
}
int oldCapacity = _set.length;
Object[] oldSet = _set;
-
- Object[] newSet = new Object[newCapacity];
+
_removedTokens = 0;
- //adds/removes/rehash should all be synchronized by the hashindex
- //we are ok to clear this map and repopulate
- //we do not do this for _set because we could still be querying
- //but the reversemap is only used for adds/removes/rehash
- if (IndexManager.isObjectModificationInplace()) {
- entryToValuesMap.clear();
- }
+
+ n = newN;
+ _mask = n - 1;
+ _maxSize = computeMaxSize(n, _loadFactor);
+ _free = computeNumFree();
+ Object[] newSet = new Object[n + 1];
+
for (int i = oldCapacity; i-- > 0;) {
if (oldSet[i] != null && oldSet[i] != REMOVED) {
Object o = oldSet[i];
- if (o instanceof RegionEntry) {
- Object key = _hashingStrategy.computeKey(o);
- if (key == null) {
- key = IndexManager.NULL;
- }
- int index = insertionIndex(key, o, newSet);
- if (index >= 0)
- if (addObjectToSet(newSet, index, o)) {
- updateReverseMap(o, key);
- }
- }
+ Object key = _imqEvaluator.evaluateKey(o);
+ if (key == null) {
+ key = IndexManager.NULL;
+ }
+ int index = insertionIndex(key, o, newSet);
+ if (index >= 0) {
+ addObjectToSet(newSet, index, o);
+ }
}
}
_set = newSet;
}
-
- private void updateReverseMap(Object regionEntry, Object key) {
- if (IndexManager.isObjectModificationInplace()) {
- entryToValuesMap.put(regionEntry, key);
- }
- }
- /**
- * Convenience methods for subclasses to use in throwing exceptions about
- * badly behaved user objects employed as keys. We have to throw an
- * IllegalArgumentException with a rather verbose message telling the user
- * that they need to fix their object implementation to conform to the general
- * contract for java.lang.Object.
- *
- * @param o1
- * the first of the equal elements with unequal hash codes.
- * @param o2
- * the second of the equal elements with unequal hash codes.
- * @exception IllegalArgumentException
- * the whole point of this method.
- */
- protected final void throwObjectContractViolation(Object o1, Object o2)
- throws IllegalArgumentException {
- throw new IllegalArgumentException(
- "Equal objects must have equal hashcodes. "
- + "During rehashing, Trove discovered that "
- + "the following two objects claim to be "
- + "equal (as in java.lang.Object.equals()) "
- + "but their hashCodes (or those calculated by "
- + "your HashIndexStrategy) are not equal."
- + "This violates the general contract of "
- + "java.lang.Object.hashCode(). See bullet point two "
- + "in that method's documentation. " + "object #1 ="
- + objToString(o1) + "; object #2 =" + objToString(o2));
- }
-
- private static String objToString(Object o) {
- if (o instanceof Object[]) {
- return java.util.Arrays.toString((Object[]) o);
- } else {
- return String.valueOf(o);
- }
- }
/**
- * Returns a new array containing the objects in the set.
+ * Unsupported as the hash index does not use this method call
*
* @return an <code>Object[]</code> value
*/
public Object[] toArray() {
- throw new UnsupportedOperationException(
- "toArray not yet supported");
+ throw new UnsupportedOperationException("toArray not yet supported");
}
/**
- * Returns a typed array of the objects in the set.
- *
+ * Unsupported as the hash index does not use this method call
* @param a
* an <code>Object[]</code> value
* @return an <code>Object[]</code> value
*/
public Object[] toArray(Object[] a) {
- throw new UnsupportedOperationException(
- "toArray(Object[] a) not yet supported");
+ throw new UnsupportedOperationException("toArray(Object[] a) not yet supported");
}
/**
* Empties the set.
*/
- // GemStoneAddition
public void clear() {
_size = 0;
_free = capacity();
_removedTokens = 0;
- if (IndexManager.isObjectModificationInplace()) {
- entryToValuesMap.clear();
- }
+
Object[] set = _set;
for (int i = set.length; i-- > 0;) {
@@ -708,66 +448,58 @@ public class HashIndexSet implements Set {
return _set.length;
}
- /**
- * Removes <tt>obj</tt> from the set.
- * Currently not implemented correctly, use {@link HashIndexSet#remove(Object, Object, boolean)}
- *
- * @param obj an <code>Object</code> value
- * @return true if the set was modified by the remove operation.
- */
- public boolean remove(Object obj) {
- throw new UnsupportedOperationException(
- "remove(Object) not supported, try remove(Object key, Object obj) instead");
+ public boolean remove(Object obj) {
+ return remove(_imqEvaluator.evaluateKey(obj), obj);
}
-
-
- public synchronized boolean remove(Object key, Object obj, boolean updateReverseMap) {
- return remove(key, obj, updateReverseMap, -1);
+
+ public synchronized boolean remove(Object key, Object obj) {
+ return remove(key, obj, -1);
}
-
+
/**
*
* @param key assumed to not be null, rather needs to be NULL token
* @param obj
- * @param updateReverseMap
* @param newIndexSlot if inplace modification occurs with out having a reversemap
- * we end up scanning the entire index. We want to remove the region entry from the index slot
- * but not the newly added (correct) slot. Rather only the "old/wrong" slot
+ * we end up scanning the entire index. We want to remove the region entry from the index slot
+ * but not the newly added (correct) slot. Rather only the "old/wrong" slot
* @return true if object was removed, false otherwise
*/
- public synchronized boolean remove(Object key, Object obj, boolean updateReverseMap, int newIndexSlot) {
+ public synchronized boolean remove(Object key, Object obj, int newIndexSlot) {
int indexSlot = index(key, obj, newIndexSlot);
boolean removed = false;
- //The check for newIndexSlot != indexSlot is incase of in place modification.
- //When inplace occurs, oldkey == newkey and we end up wiping out the "new key" slow rather
- //than the old key slot. Instead let's get to the else portion
+ // The check for newIndexSlot != indexSlot is incase of in place modification.
+ // When inplace occurs, oldkey == newkey and we end up wiping out the "new key" slow rather
+ // than the old key slot. Instead let's get to the else portion
if (indexSlot >= 0 && indexSlot != newIndexSlot) {
removed = removeAt(indexSlot);
- if (removed) {
- if (updateReverseMap && IndexManager.isObjectModificationInplace()) {
- entryToValuesMap.remove(obj);
- }
- internalIndexStats.incNumValues(-1);
- }
return removed;
- }
- else if (!IndexManager.isObjectModificationInplace()){
- //object could not be found so it's possible there was an inplace modification
- HashIndexSetIterator iterator = (HashIndexSetIterator)getAll();
- while (iterator.hasNext()) {
- Object indexedObject = iterator.next();
- if (_hashingStrategy.equalsOnAdd(indexedObject, obj) && iterator.currentObjectIndex() != newIndexSlot) {
- iterator.remove();
- internalIndexStats.incNumValues(-1);
- return true;
- }
+ } else if (!IndexManager.isObjectModificationInplace()) {
+ // object could not be found so it's possible there was an inplace modification
+ HashIndexSetIterator iterator = (HashIndexSetIterator) getAll();
+ while (iterator.hasNext()) {
+ Object indexedObject = iterator.next();
+ if (areObjectsEqual(indexedObject, obj) && iterator.currentObjectIndex() != newIndexSlot) {
+ iterator.remove();
+ return true;
}
+ }
}
return false;
}
-
+ public final boolean areObjectsEqual(Object o1, Object o2) {
+ if (o1 == null) {
+ return o2 == null;
+ }
+ try {
+ return TypeUtils.compare(o1, o2, OQLLexerTokenTypes.TOK_EQ).equals(Boolean.TRUE);
+ }
+ catch (TypeMismatchException e) {
+ return o1.equals(o2);
+ }
+ }
/**
* Creates an iterator over the values of the set. The iterator supports
@@ -780,11 +512,10 @@ public class HashIndexSet implements Set {
}
/**
- * Tests the set to determine if all of the elements in <tt>collection</tt>
- * are present.
+ * Determine if all of the elements in <tt>collection</tt> are present.
*
* @param collection a <code>Collection</code> value
- * @return true if all elements were present in the set.
+ * @return true if all elements are present.
*/
public boolean containsAll(Collection collection) {
for (Iterator i = collection.iterator(); i.hasNext();) {
@@ -796,25 +527,10 @@ public class HashIndexSet implements Set {
}
/**
- * Adds all of the elements in <tt>collection</tt> to the set.
- *
- * @param collection a <code>Collection</code> value
- * @return true if the set was modified by the add all operation.
+ * Unsupported because type mismatch exception cannot be thrown from Set interface
*/
public boolean addAll(Collection collection) {
- boolean changed = false;
- int size = collection.size();
- Iterator it;
-
- ensureCapacity(size);
- it = collection.iterator();
- while (size-- > 0) {
- Object obj = it.next();
- if (obj != null && add(obj)) {
- changed = true;
- }
- }
- return changed;
+ throw new UnsupportedOperationException("Add all not implemented");
}
/**
@@ -826,9 +542,8 @@ public class HashIndexSet implements Set {
public boolean removeAll(Collection collection) {
boolean changed = false;
int size = collection.size();
- Iterator it;
- it = collection.iterator();
+ Iterator it = collection.iterator();
while (size-- > 0) {
if (remove(it.next())) {
changed = true;
@@ -838,8 +553,7 @@ public class HashIndexSet implements Set {
}
/**
- * Removes any values in the set which are not contained in
- * <tt>collection</tt>.
+ * Removes any values in the set which are not contained in <tt>collection</tt>.
*
* @param collection a <code>Collection</code> value
* @return true if the set was modified by the retain all operation
@@ -847,11 +561,11 @@ public class HashIndexSet implements Set {
public boolean retainAll(Collection collection) {
boolean changed = false;
int size = size();
- Iterator it;
- it = iterator();
- while (size-- > 0) {
- if (!collection.contains(it.next())) {
+ Iterator it = iterator();
+ while (it.hasNext()) {
+ Object object = it.next();
+ if (!collection.contains(object)) {
it.remove();
changed = true;
}
@@ -859,133 +573,54 @@ public class HashIndexSet implements Set {
return changed;
}
-
@Override
- // GemStoneAddition
-
/**
- * Tells whether this set is currently holding any elements.
- *
- * @return a <code>boolean</code> value
+ * return true if no elements exist in the array that are non null or REMOVED tokens
*/
public boolean isEmpty() {
return 0 == _size;
}
/**
- * Returns the number of slots used in the backing array
+ * Returns the number of positions used in the backing array
* Is not a true representation of the number of elements in the array
+ * as the array may contain REMOVED tokens
*
* @return an <code>int</code> value
*/
public int size() {
return _size;
}
-
- public int size(Object indexKey) {
- int hash, probe, index, length;
- Object[] set;
- Object cur;
- int size = 0;
- //find the first array index location
- set = _set;
- length = set.length;
- hash = computeHash(indexKey, false);
- index = hash % length;
- cur = set[index];
-
- if (cur == null) {
- // return
- return 0;
- }
-
- while (cur != null) {
- if (cur != REMOVED) {
- if (cur instanceof RegionEntry) {
- if (_hashingStrategy.equalsOnGet(indexKey, cur)) {
- size++;
- }
- }
- break;
- }
- //If this is not the correct collection, one that does not match the key
- //we are looking for, then continue our search
- probe = 1 + (hash % (length - 2));
- index -= probe;
- if (index < 0) {
- index += length;
- }
- cur = set[index];
- }
- return size;
- }
-
/**
- * Ensure that this hashtable has sufficient capacity to hold
- * <tt>desiredCapacity<tt> <b>additional</b> elements without
- * requiring a rehash. This is a tuning method you can call
- * before doing a large insert.
- *
- * @param desiredCapacity an <code>int</code> value
+ * only used for query optimization. Instead of crawling the entire array doing matches
+ * let's just return the size of the array as that is the worst case size
*/
- public void ensureCapacity(int desiredCapacity) {
- if (desiredCapacity > (_maxSize - size())) {
- rehash(PrimeFinder.nextPrime((int) Math.ceil(desiredCapacity + size()
- / _loadFactor) + 1));
- computeMaxSize(capacity());
- }
+ public int size(Object indexKey) {
+ return _size;
}
/**
- * Compresses the hashtable to the minimum prime size (as defined by
- * PrimeFinder) that will hold all of the elements currently in the table. If
- * you have done a lot of <tt>remove</tt> operations and plan to do a lot of
- * queries or insertions or iteration, it is a good idea to invoke this
- * method. Doing so will accomplish two things:
- *
- * <ol>
- * <li>You'll free memory allocated to the table but no longer needed because
- * of the remove()s.</li>
- *
- * <li>You'll get better query/insert/iterator performance because there won't
- * be any <tt>REMOVED</tt> slots to skip over when probing for indices in the
- * table.</li>
- * </ol>
+ * Compress the backing array if possible
*/
public void compact() {
- // need at least one free spot for open addressing
- rehash(PrimeFinder.nextPrime((int) Math.ceil(size() / _loadFactor) + 1));
- computeMaxSize(capacity());
+ trimToSize(_size);
}
-
- // GemStoneAddition
- /**
- * Calls compact by taking next set expansion into account. The set is
- * expanded based on the capacity and load factor (default .5) this method
- * calls the compact if the size is well below next expansion.
- */
- public void conditionalCompact() {
- if (_size < (capacity() * (_loadFactor / CONDITIONAL_COMPACT_FACTOR))) {
- compact();
+
+ public boolean trimToSize( final int n ) {
+ final int l = HashCommon.nextPowerOfTwo( (int)Math.ceil( n / _loadFactor ) );
+ if ( this.n <= l ) return true;
+ try {
+ rehash( l );
}
- }
-
- /**
- * This simply calls {@link #compact compact}. It is included for symmetry
- * with other collection classes. Note that the name of this method is
- * somewhat misleading (which is why we prefer <tt>compact</tt>) as the load
- * factor may require capacity above and beyond the size of this collection.
- *
- * @see #compact
- */
- public final void trimToSize() {
- compact();
- }
+ catch ( OutOfMemoryError cantDoIt ) {
+ return false;
+ }
+ return true;
+}
/**
- * Delete the record at <tt>index</tt>. Reduces the size of the collection by
- * one.
+ * Remove the object at <tt>index</tt>.
*
* @param index an <code>int</code> value
*/
@@ -994,210 +629,136 @@ public class HashIndexSet implements Set {
cur = _set[index];
if (cur == null || cur == REMOVED) {
- //nothing removed
+ // nothing removed
return false;
} else {
_set[index] = REMOVED;
_size--;
- _removedTokens ++;
+ _removedTokens++;
return true;
- }
+ }
}
/**
- * initializes the hashtable to a prime capacity which is at least
- * <tt>initialCapacity + 1</tt>.
- *
- * @param initialCapacity an <code>int</code> value
- * @return the actual capacity chosen
+ * initializes this index set
*/
- protected int setUp(int initialCapacity) {
- int capacity;
- capacity = PrimeFinder.nextPrime(initialCapacity);
- computeMaxSize(capacity);
- _set = new Object[capacity];
- return capacity;
+ protected int setUp(final int expectedCapacity, final float loadFactor) {
+ n = arraySize( expectedCapacity, loadFactor );
+ this._loadFactor = loadFactor;
+ _maxSize = computeMaxSize(n, loadFactor);
+ _mask = n - 1;
+ _free = computeNumFree();
+ _set = new Object[n + 1];
+ return n;
}
-
- /**
- * Computes the values of maxSize. There will always be at least one free slot
- * required.
- *
- * @param capacity an <code>int</code> value
- */
- private final void computeMaxSize(int capacity) {
- // need at least one free slot for open addressing
- _maxSize = Math.min(capacity - 1, (int) Math.floor(capacity * _loadFactor));
- _free = capacity - _size; // reset the free element count
+
+ private int computeNumFree() {
+ return n - _size;
+ }
+
+ private int computeMaxSize(int n, float loadFactor) {
+ return Math.min( (int)Math.ceil( n * loadFactor ), n - 1 );
}
/**
- * After an insert, this hook is called to adjust the size/free values of the
- * set and to perform rehashing if necessary.
+ * After insert, allows for calculating metadata
*/
protected final void postInsertHook(boolean usedFreeSlot) {
if (usedFreeSlot) {
_free--;
- }
- else {
- //we used a removeToken
+ } else {
+ // we used a removeToken
_removedTokens--;
}
_size++;
}
-
+
+ /**
+ * Before inserting we can ensure we have capacity
+ */
protected final void preInsertHook() {
- // rehash whenever we exhaust the available space in the table
if (_size > _maxSize || _free == 0 || TEST_ALWAYS_REHASH) {
- // choose a new capacity suited to the new state of the table
- // if we've grown beyond our maximum size, double capacity;
- // if we've exhausted the free spots, rehash to the same capacity,
- // which will free up any stale removed slots for reuse.
- int newCapacity = _size > _maxSize ? PrimeFinder
- .nextPrime(capacity() << 1) : capacity();
- rehash(newCapacity);
- computeMaxSize(capacity());
- }
- else if (_removedTokens > _maxSize * CONDITIONAL_REMOVED_TOKEN_REHASH_FACTOR) {
+ rehash(arraySize(_size + 1, _loadFactor));
+ computeMaxSize(capacity(), _loadFactor);
+ _free = computeNumFree();
+ } else if (_removedTokens > _maxSize * CONDITIONAL_REMOVED_TOKEN_REHASH_FACTOR) {
compact();
}
}
- final class ToObjectArrayProcedure implements ObjectProcedure {
- private final Object[] target;
- private int pos = 0;
-
- public ToObjectArrayProcedure(final Object[] target) {
- this.target = target;
- }
-
- public final boolean executeWith(Object value) {
- target[pos++] = value;
- return true;
- }
- } // ToObjectArrayProcedure
-
- public String printAll() {
- StringBuffer s = new StringBuffer();
- for (int i = 0; i < _set.length; i++) {
- Object object = _set[i];
- if (object != null && object != REMOVED) {
- s.append("\n slot[" + i + "]:");
- if (object instanceof Collection) {
- for (Object o : ((Collection) object)) {
- if (o != null) {
- RegionEntry re = (RegionEntry) o;
- Object val = re._getValue(); // OFFHEAP _getValue ok
- if (val instanceof StoredObject) {
- // We don't have enough info here to deserialize an off-heap value
- // so we can't call getDeserializedForReading.
- // Also we can't call _getValueRetain because we do not
- // know what region to pass in to it.
- // So for now we just convert it to a String which all StoredObject
- // impls can do without needing a refcount or to decompress.
- val = val.toString();
- }
- if (val instanceof CachedDeserializable) {
- val = ((CachedDeserializable) val).getDeserializedForReading();
- }
- s.append(re.getKey() + " => " + val + " # ");
- }
- }
- } else {
- RegionEntry re = (RegionEntry) object;
- Object val = re._getValue(); // OFFHEAP _getValue ok
- if (val instanceof StoredObject) {
- // We don't have enough info here to deserialize an off-heap value
- // so we can't call getDeserializedForReading.
- // Also we can't call _getValueRetain because we do not
- // know what region to pass in to it.
- // So for now we just convert it to a String which all StoredObject
- // impls can do without needing a refcount or to decompress.
- val = val.toString();
- }
- if (val instanceof CachedDeserializable) {
- val = ((CachedDeserializable) val).getDeserializedForReading();
- }
- s.append(re.getKey() + " => " + val);
- }
- }
- }
- return s.toString();
- }
-
-
private class HashIndexSetIterator implements Iterator {
private Object keyToMatch;
- //objects at time of iterator creation
+ // objects at time of iterator creation
private final Object[] objects;
- private int indexSlot;
+ private int pos;
+ private int prevPos;
private Collection keysToRemove;
private Object current;
private int hash;
- private int length;
+ private int mask;
private int probe;
-
- private HashIndexSetIterator(Collection keysToRemove, Object[] objects ) {
+
+ private HashIndexSetIterator(Collection keysToRemove, Object[] objects) {
this.keysToRemove = keysToRemove;
- this.indexSlot = 0;
+ this.pos = 0;
+ this.prevPos = 0;
this.objects = objects;
- current = objects[indexSlot];
+ current = objects[pos];
}
-
+
private HashIndexSetIterator(Object keyToMatch, Object[] objects) {
this.keyToMatch = keyToMatch;
this.objects = objects;
-
- length = objects.length;
- hash = computeHash(keyToMatch, false);
- probe = 1 + (hash % (length - 2));
- indexSlot = hash % length;
- current = objects[indexSlot];
+
+ mask = _mask;
+ hash = computeHash(keyToMatch);
+ pos = (it.unimi.dsi.fastutil.HashCommon.mix(hash)) & mask;
+ prevPos = pos;
+ current = objects[pos];
}
+ private void setPos(int pos) {
+ this.prevPos = this.pos;
+ this.pos = pos;
+ }
+
@Override
public boolean hasNext() {
// For Not Equals we need to look in the entire set
if (keysToRemove != null) {
- while (indexSlot < objects.length) {
- current = objects[indexSlot];
+ while (pos < objects.length) {
+ current = objects[pos];
if (current == null || current.equals(REMOVED)) {
- //continue searching
- }
- else if (notMatchingAnyKeyToRemove(keysToRemove, current)) {
+ // continue searching
+ } else if (notMatchingAnyKeyToRemove(keysToRemove, current)) {
return true;
}
-
- indexSlot++;
+ setPos(pos+1);
}
return false;
} else {
-
- current = objects[indexSlot];
+ current = objects[pos];
// For Equals query
while (current != null) {
if (current != REMOVED) {
- if (_hashingStrategy.equalsOnGet(keyToMatch, current)) {
+ if (objectMatchesIndexKey(keyToMatch, current)) {
return true;
}
}
// If this is not the correct collection, one that does not match the
// key we are looking for, then continue our search
- indexSlot -= probe;
- if (indexSlot < 0) {
- indexSlot += length;
- }
-
- current = objects[indexSlot];
- }
+ setPos((pos + 1) & mask);
+ current = objects[pos];
+ }
}
return false;
}
+
private boolean notMatchingAnyKeyToRemove(Collection keysToRemove, Object current) {
Iterator keysToRemoveIterator = keysToRemove.iterator();
while (keysToRemoveIterator.hasNext()) {
Object keyToMatch = keysToRemoveIterator.next();
- if (_hashingStrategy.equalsOnGet(keyToMatch, current)) {
+ if (objectMatchesIndexKey(keyToMatch, current)) {
return false;
}
}
@@ -1206,43 +767,52 @@ public class HashIndexSet implements Set {
@Override
public Object next() throws NoSuchElementException {
- Object obj = current;
- if (keysToRemove != null) {
- // for Not equals we need to continue looking
- // so increment the index here
- indexSlot++;
- } else {
- //advance the pointer
- indexSlot -= probe;
- if (indexSlot < 0) {
- indexSlot += length;
- }
- }
- return obj;
- }
-
- int currentObjectIndex() {
- int indexToRemove = 0;
- //Because we advanced on the next() call, we need to get the indexSlot prior to advancing
+ Object obj = current;
if (keysToRemove != null) {
// for Not equals we need to continue looking
// so increment the index here
- indexToRemove = indexSlot - 1;
+ setPos(pos+1);
} else {
- //move back the pointer
- indexToRemove = indexSlot + probe;
- if (indexSlot >= objects.length) {
- indexToRemove = indexSlot - length;
- }
+ // advance the pointer
+ setPos((pos + 1) & mask);
}
- return indexToRemove;
+ return obj;
}
-
+
+ int currentObjectIndex() {
+ return prevPos;
+ }
+
@Override
public void remove() {
removeAt(currentObjectIndex());
}
+
+ public boolean objectMatchesIndexKey(Object indexKey, Object o) {
+ Object fieldValue = _imqEvaluator.evaluateKey(o);
+
+ if (fieldValue == IndexManager.NULL && indexKey == IndexManager.NULL) {
+ return true;
+ } else {
+ try {
+ if (fieldValue instanceof PdxString) {
+ if (indexKey instanceof String) {
+ fieldValue = ((PdxString) fieldValue).toString();
+ }
+ }
+ else if (indexKey instanceof PdxString) {
+ if (fieldValue instanceof String) {
+ fieldValue = new PdxString((String)fieldValue);
+ }
+ }
+ return TypeUtils.compare(fieldValue, indexKey, OQLLexerTokenTypes.TOK_EQ).equals(Boolean.TRUE);
+ }
+ catch (TypeMismatchException e) {
+ return fieldValue.equals(indexKey);
+ }
+ }
+ }
}
-} // HashIndexSet
+}
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/abad018a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexStrategy.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexStrategy.java b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexStrategy.java
deleted file mode 100755
index 3ed0caf..0000000
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexStrategy.java
+++ /dev/null
@@ -1,90 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You 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 at
- *
- * 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.
- */
-/*
- * IndexCreationHelper.java
- *
- * Created on March 16, 2005, 6:20 PM
- */
-package com.gemstone.gemfire.cache.query.internal.index;
-
-import com.gemstone.gemfire.cache.query.internal.ExecutionContext;
-
-
-/**
- * Interface to support plug-able hashing strategies in maps and sets.
- * Implementors can use this interface to make the hashing
- * algorithms use object values, values provided by the java runtime,
- * or a custom strategy when computing hash codes.
- *
- */
-
-public interface HashIndexStrategy {
-
- /**
- * Computes a hash code for the specified object. Implementors
- * can use the object's own <tt>hashCode</tt> method, the Java
- * runtime's <tt>identityHashCode</tt>, or a custom scheme.
- *
- * @param o object for which the hashcode is to be computed
- * @return the hashCode
- */
- public int computeHashCode(Object o);
-
-
- /**
- * VMware Addition
- * Computes a hash code for the specified object. Implementors
- * can use the object's own <tt>hashCode</tt> method, the Java
- * runtime's <tt>identityHashCode</tt>, or a custom scheme.
- * Used when resizing the internal set structure. Due to not storing
- * the indexKey, we have to recompute the indexKey from the object
- * at this point.
- * @param o object for which the hashcode is to be computed
- * @param recomputeKey
- * @return the hashCode
- */
- public int computeHashCode(Object o, boolean recomputeKey);
-
- /**
- * VMware Addition
- * Computes the object's key
- * @param o object for which the key is to be computed
- * @return the key
- */
- public Object computeKey(Object o);
-
- /**
- * Compares o1 and o2 for equality. Strategy implementors may use
- * the objects' own equals() methods, compare object references,
- * or implement some custom scheme.
- *
- * @param o1 an <code>Object</code> value
- * @param o2 an <code>Object</code> value
- * @return true if the objects are equal according to this strategy.
- */
- public boolean equalsOnAdd(Object o1, Object o2);
-
- /**
- * Compares o1 and o2 for equality. Strategy implementors may use
- * the objects' own equals() methods, compare object references,
- * or implement some custom scheme.
- *
- * @return true if the objects are equal according to this strategy.
- */
- public boolean equalsOnGet(Object getValue, Object o);
-
-}
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/abad018a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/util/ObjectProcedure.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/util/ObjectProcedure.java b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/util/ObjectProcedure.java
deleted file mode 100755
index 421b6c8..0000000
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/util/ObjectProcedure.java
+++ /dev/null
@@ -1,30 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You 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 at
- *
- * 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 com.gemstone.gemfire.internal.util;
-
-/**
- * Similar to the Trove TObjectProcedure, this is used in iterating over some
- * GemFire collections
- *
- * @author bschuchardt
- *
- */
-public interface ObjectProcedure {
-
- public boolean executeWith(Object entry);
-
-}
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/abad018a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/util/PrimeFinder.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/util/PrimeFinder.java b/gemfire-core/src/main/java/com/gemstone/gemfire/internal/util/PrimeFinder.java
deleted file mode 100644
index 529e5a2..0000000
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/internal/util/PrimeFinder.java
+++ /dev/null
@@ -1,159 +0,0 @@
-// Copyright (c) 1999 CERN - European Organization for Nuclear Research.
-//
-// Permission to use, copy, modify, distribute and sell this software
-// and its documentation for any purpose is hereby granted without fee,
-// provided that the above copyright notice appear in all copies and
-// that both that copyright notice and this permission notice appear in
-// supporting documentation. CERN makes no representations about the
-// suitability of this software for any purpose. It is provided "as is"
-// without expressed or implied warranty.
-
-package com.gemstone.gemfire.internal.util;
-
-import java.util.Arrays;
-
-/*
- * Modified for Trove to use the java.util.Arrays sort/search
- * algorithms instead of those provided with colt.
- */
-
-/**
- * Used to keep hash table capacities prime numbers.
- * Not of interest for users; only for implementors of hashtables.
- *
- * <p>Choosing prime numbers as hash table capacities is a good idea
- * to keep them working fast, particularly under hash table
- * expansions.
- *
- * <p>However, JDK 1.2, JGL 3.1 and many other toolkits do nothing to
- * keep capacities prime. This class provides efficient means to
- * choose prime capacities.
- *
- * <p>Choosing a prime is <tt>O(log 300)</tt> (binary search in a list
- * of 300 ints). Memory requirements: 1 KB static memory.
- *
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 09/24/99
- */
-public final class PrimeFinder {
- /**
- * The largest prime this class can generate; currently equal to
- * <tt>Integer.MAX_VALUE</tt>.
- */
- public static final int largestPrime = Integer.MAX_VALUE; //yes, it is prime.
-
- /**
- * The prime number list consists of 11 chunks.
- *
- * Each chunk contains prime numbers.
- *
- * A chunk starts with a prime P1. The next element is a prime
- * P2. P2 is the smallest prime for which holds: P2 >= 2*P1.
- *
- * The next element is P3, for which the same holds with respect
- * to P2, and so on.
- *
- * Chunks are chosen such that for any desired capacity >= 1000
- * the list includes a prime number <= desired capacity * 1.11.
- *
- * Therefore, primes can be retrieved which are quite close to any
- * desired capacity, which in turn avoids wasting memory.
- *
- * For example, the list includes
- * 1039,1117,1201,1277,1361,1439,1523,1597,1759,1907,2081.
- *
- * So if you need a prime >= 1040, you will find a prime <=
- * 1040*1.11=1154.
- *
- * Chunks are chosen such that they are optimized for a hashtable
- * growthfactor of 2.0;
- *
- * If your hashtable has such a growthfactor then, after initially
- * "rounding to a prime" upon hashtable construction, it will
- * later expand to prime capacities such that there exist no
- * better primes.
- *
- * In total these are about 32*10=320 numbers -> 1 KB of static
- * memory needed.
- *
- * If you are stingy, then delete every second or fourth chunk.
- */
-
- private static final int[] primeCapacities = {
- //chunk #0
- largestPrime,
-
- //chunk #1
- 5,11,23,47,97,197,397,797,1597,3203,6421,12853,25717,51437,102877,205759,
- 411527,823117,1646237,3292489,6584983,13169977,26339969,52679969,105359939,
- 210719881,421439783,842879579,1685759167,
-
- //chunk #2
- 433,877,1759,3527,7057,14143,28289,56591,113189,226379,452759,905551,1811107,
- 3622219,7244441,14488931,28977863,57955739,115911563,231823147,463646329,927292699,
- 1854585413,
-
- //chunk #3
- 953,1907,3821,7643,15287,30577,61169,122347,244703,489407,978821,1957651,3915341,
- 7830701,15661423,31322867,62645741,125291483,250582987,501165979,1002331963,
- 2004663929,
-
- //chunk #4
- 1039,2081,4177,8363,16729,33461,66923,133853,267713,535481,1070981,2141977,4283963,
- 8567929,17135863,34271747,68543509,137087021,274174111,548348231,1096696463,
-
- //chunk #5
- 31,67,137,277,557,1117,2237,4481,8963,17929,35863,71741,143483,286973,573953,
- 1147921,2295859,4591721,9183457,18366923,36733847,73467739,146935499,293871013,
- 587742049,1175484103,
-
- //chunk #6
- 599,1201,2411,4831,9677,19373,38747,77509,155027,310081,620171,1240361,2480729,
- 4961459,9922933,19845871,39691759,79383533,158767069,317534141,635068283,1270136683,
-
- //chunk #7
- 311,631,1277,2557,5119,10243,20507,41017,82037,164089,328213,656429,1312867,
- 2625761,5251529,10503061,21006137,42012281,84024581,168049163,336098327,672196673,
- 1344393353,
-
- //chunk #8
- 3,7,17,37,79,163,331,673,1361,2729,5471,10949,21911,43853,87719,175447,350899,
- 701819,1403641,2807303,5614657,11229331,22458671,44917381,89834777,179669557,
- 359339171,718678369,1437356741,
-
- //chunk #9
- 43,89,179,359,719,1439,2879,5779,11579,23159,46327,92657,185323,370661,741337,
- 1482707,2965421,5930887,11861791,23723597,47447201,94894427,189788857,379577741,
- 759155483,1518310967,
-
- //chunk #10
- 379,761,1523,3049,6101,12203,24407,48817,97649,195311,390647,781301,1562611,
- 3125257,6250537,12501169,25002389,50004791,100009607,200019221,400038451,800076929,
- 1600153859
- };
-
- static { //initializer
- // The above prime numbers are formatted for human readability.
- // To find numbers fast, we sort them once and for all.
-
- Arrays.sort(primeCapacities);
- }
-
- /**
- * Returns a prime number which is <code>>= desiredCapacity</code>
- * and very close to <code>desiredCapacity</code> (within 11% if
- * <code>desiredCapacity >= 1000</code>).
- *
- * @param desiredCapacity the capacity desired by the user.
- * @return the capacity which should be used for a hashtable.
- */
- public static final int nextPrime(int desiredCapacity) {
- int i = Arrays.binarySearch(primeCapacities, desiredCapacity);
- if (i<0) {
- // desired capacity not found, choose next prime greater
- // than desired capacity
- i = -i -1; // remember the semantics of binarySearch...
- }
- return primeCapacities[i];
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/abad018a/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexJUnitTest.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexJUnitTest.java b/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexJUnitTest.java
index e3247a7..e2a8643 100755
--- a/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexJUnitTest.java
+++ b/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/HashIndexJUnitTest.java
@@ -189,6 +189,7 @@ public class HashIndexJUnitTest {
}
region.put("" + i, p);
}
+
helpTestHashIndexForQuery("SELECT * FROM /portfolios p WHERE p.status = 'inactive'", "p.status", "/portfolios p");
qs.removeIndexes();
observer = new MyQueryObserverAdapter();
@@ -1382,17 +1383,17 @@ public class HashIndexJUnitTest {
}
- private void printIndex(Index index) {
- if (index instanceof PartitionedIndex) {
- Iterator it = ((PartitionedIndex)index).getBucketIndexes().iterator();
- while (it.hasNext()) {
- ((HashIndex)it.next()).printAll();
- }
- }
- else {
- System.out.println(((HashIndex)index).printAll());
- }
- }
+// private void printIndex(Index index) {
+// if (index instanceof PartitionedIndex) {
+// Iterator it = ((PartitionedIndex)index).getBucketIndexes().iterator();
+// while (it.hasNext()) {
+// ((HashIndex)it.next()).printAll();
+// }
+// }
+// else {
+// System.out.println(((HashIndex)index).printAll());
+// }
+// }
private class RelationshipKey implements Comparable {