Author: pcl
Date: Wed Jun 11 16:27:18 2008
New Revision: 666897
URL: http://svn.apache.org/viewvc?rev=666897&view=rev
Log:
OPENJPA-544. Merge from ../active. svn merge -c 652523 ../active
Modified:
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/util/concurrent/NullSafeConcurrentHashMap.java
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/util/concurrent/SizedConcurrentHashMap.java
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/util/concurrent/TestConcurrentMap.java
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/util/concurrent/TestNullSafeConcurrentHashMap.java
Modified:
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/util/concurrent/NullSafeConcurrentHashMap.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/util/concurrent/NullSafeConcurrentHashMap.java?rev=666897&r1=666896&r2=666897&view=diff
==============================================================================
---
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/util/concurrent/NullSafeConcurrentHashMap.java
(original)
+++
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/util/concurrent/NullSafeConcurrentHashMap.java
Wed Jun 11 16:27:18 2008
@@ -19,13 +19,17 @@
package org.apache.openjpa.lib.util.concurrent;
import java.util.concurrent.ConcurrentHashMap;
-import java.util.Map;
import java.util.Enumeration;
import java.util.Set;
import java.util.Collection;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.AbstractCollection;
+import java.util.Random;
+import java.util.HashSet;
+import java.util.TreeSet;
+
+import org.apache.commons.collections.set.MapBackedSet;
/**
* A subclass of [EMAIL PROTECTED] ConcurrentHashMap} that allows null keys
and values.
@@ -36,10 +40,20 @@
*/
public class NullSafeConcurrentHashMap extends ConcurrentHashMap {
- private enum Null {
- MARKER
+ private enum Markers {
+ NULL,
+ MAP_BACKED_SET_DUMMY_VAL
}
+ // The second argument is used within MapBackedSet as the value for
+ // all the key-val pairs that are put into the underlying Map. This
+ // is required for our usage since ConcurrentHashMap does not allow
+ // null values.
+ private Set randomKeys = MapBackedSet.decorate(
+ new ConcurrentHashMap(), Markers.MAP_BACKED_SET_DUMMY_VAL);
+
+ private Random random = new Random();
+
public NullSafeConcurrentHashMap(int size, float load,
int concurrencyLevel) {
super(size, load, concurrencyLevel);
@@ -52,24 +66,135 @@
* Returns internal representation for object.
*/
private static Object maskNull(Object o) {
- return (o == null ? Null.MARKER : o);
+ return (o == null ? Markers.NULL : o);
}
/**
* Returns object represented by specified internal representation.
*/
private static Object unmaskNull(Object o) {
- return (o == Null.MARKER ? null : o);
+ return (o == Markers.NULL ? null : o);
+ }
+
+ public Entry removeRandom() {
+ // this doesn't just use randomEntryIterator() because that iterator
+ // has weaker concurrency guarantees than this method. In particular,
+ // this method will continue to attempt to remove random entries even
+ // as other threads remove the same entries, whereas the random
+ // iterator may return values that have been removed.
+
+ while (!isEmpty()) {
+ while (!randomKeys.isEmpty()) {
+ // randomKeys contains null-masked data
+ Iterator iter = randomKeys.iterator();
+ Object key = iter.next();
+ if (key != null && randomKeys.remove(key)) {
+ Object val = super.remove(key);
+ if (val != null)
+ return new EntryImpl(unmaskNull(key), unmaskNull(val));
+ }
+ }
+
+ // if randomKeys is empty, fall back to non-random behavior.
+ Object key = super.keySet().iterator().next();
+ Object val = super.remove(key);
+ if (val != null)
+ return new EntryImpl(unmaskNull(key), unmaskNull(val));
+ }
+ return null;
+ }
+
+ /**
+ * The returned data structure should not be shared among multiple
+ * threads.
+ */
+ public Iterator<Entry> randomEntryIterator() {
+ return new Iterator<Entry>() {
+
+ Iterator randomIter = randomKeys.iterator();
+ Iterator nonRandomIter = NullSafeConcurrentHashMap.super.keySet()
+ .iterator();
+
+ Set returned = new HashSet();
+ Entry next;
+ boolean nextSet = false;
+
+ public boolean hasNext() {
+ // we've set the next value and we haven't returned it yet
+ if (nextSet)
+ return true;
+
+ // compute the next value. If the computation returns null,
+ // return false. Else, store the next value and return true.
+ Object nextKey;
+ Object nextValue;
+ if (randomIter.hasNext()) {
+ nextKey = randomIter.next();
+ nextValue = NullSafeConcurrentHashMap.super.get(nextKey);
+ if (nextValue != null) {
+ returned.add(nextKey);
+ next = new EntryImpl(unmaskNull(nextKey),
+ unmaskNull(nextValue));
+ nextSet = true;
+ return true;
+ }
+ }
+
+ while (nonRandomIter.hasNext()) {
+ nextKey = nonRandomIter.next();
+
+ if (returned.contains(nextKey))
+ continue;
+
+ nextValue = NullSafeConcurrentHashMap.super.get(nextKey);
+ if (nextValue != null) {
+ returned.add(nextKey);
+ next = new EntryImpl(unmaskNull(nextKey),
+ unmaskNull(nextValue));
+ nextSet = true;
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public Entry next() {
+ // hasNext() will initialize this.next
+ if (!nextSet && !hasNext())
+ return null;
+
+ // if we get here, then we're about to return a next value
+ nextSet = false;
+
+ if (containsKey(next.getKey()))
+ return next;
+
+ // something has changed since the last iteration (presumably
+ // due to multi-threaded access to the underlying data
+ // structure); recurse
+ return next();
+ }
+
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ };
}
@Override
public Object remove(Object key) {
- return unmaskNull(super.remove(maskNull(key)));
+ Object maskedKey = maskNull(key);
+ Object val = unmaskNull(super.remove(maskedKey));
+ randomKeys.remove(maskedKey);
+ return val;
}
@Override
public boolean remove(Object key, Object value) {
- return super.remove(maskNull(key), maskNull(value));
+ Object maskedKey = maskNull(key);
+ boolean val = super.remove(maskedKey, maskNull(value));
+ randomKeys.remove(maskedKey);
+ return val;
}
@Override
@@ -85,12 +210,34 @@
@Override
public Object putIfAbsent(Object key, Object value) {
- return unmaskNull(super.putIfAbsent(maskNull(key), maskNull(value)));
+ Object maskedKey = maskNull(key);
+ Object superVal = super.putIfAbsent(maskedKey, maskNull(value));
+ addRandomKey(maskedKey);
+ return unmaskNull(superVal);
}
@Override
public Object put(Object key, Object value) {
- return unmaskNull(super.put(maskNull(key), maskNull(value)));
+ Object maskedKey = maskNull(key);
+ Object superVal = super.put(maskedKey, maskNull(value));
+ addRandomKey(maskedKey);
+ return unmaskNull(superVal);
+ }
+
+ /**
+ * Potentially adds <code>maskedKey</ccode> to the set of random keys
+ * to be removed by [EMAIL PROTECTED] #removeRandom()}.
+ *
+ * @since 1.1.0
+ */
+ private void addRandomKey(Object maskedKey) {
+ // Add one in every three keys to the set. Only do this when
+ // there are less than 16 elements in the random key set; this
+ // means that the algorithm will be pseudo-random for up to
+ // 16 removes (either via removeRandom() or normal remove()
+ // calls) that have no intervening put() calls.
+ if (random != null && randomKeys.size() < 16 && random.nextInt(10) < 3)
+ randomKeys.add(maskedKey);
}
@Override
@@ -161,11 +308,6 @@
}
@Override
- public void putAll(Map t) {
- super.putAll(t);
- }
-
- @Override
public Collection values() {
return new TranslatingCollection(super.values()) {
@@ -238,4 +380,36 @@
return backingCollection.size();
}
}
+
+ private class EntryImpl implements Entry {
+
+ final Object key;
+ final Object val;
+
+ private EntryImpl(Object key, Object val) {
+ this.key = key;
+ this.val = val;
+ }
+
+ public Object getKey() {
+ return key;
+ }
+
+ public Object getValue() {
+ return val;
+ }
+
+ public Object setValue(Object value) {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ public interface KeyFilter {
+
+ /**
+ * @param key may be null
+ * @return whether or not <code>key</code> shuold be excluded
+ */
+ public boolean exclude(Object key);
+ }
}
Modified:
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/util/concurrent/SizedConcurrentHashMap.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/util/concurrent/SizedConcurrentHashMap.java?rev=666897&r1=666896&r2=666897&view=diff
==============================================================================
---
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/util/concurrent/SizedConcurrentHashMap.java
(original)
+++
openjpa/trunk/openjpa-lib/src/main/java/org/apache/openjpa/lib/util/concurrent/SizedConcurrentHashMap.java
Wed Jun 11 16:27:18 2008
@@ -99,40 +99,6 @@
return size() >= maxSize;
}
- public Map.Entry removeRandom() {
- // this isn't really random, but is concurrent.
- while (true) {
- if (size() == 0)
- return null;
- Set entries = entrySet();
- Entry e = (Entry) entries.iterator().next();
- final Object key = e.getKey();
- final Object val = e.getValue();
- if (remove(key) != null)
- // create a new Entry instance because the ConcurrentHashMap
- // implementation's one is "live" so does not behave as desired
- // after removing the entry.
- return new Entry() {
- public Object getKey() {
- return key;
- }
-
- public Object getValue() {
- return val;
- }
-
- public Object setValue(Object value) {
- throw new UnsupportedOperationException();
- }
- };
- }
- }
-
- public Iterator randomEntryIterator() {
- // this isn't really random, but is concurrent.
- return entrySet().iterator();
- }
-
/**
* This implementation does nothing.
*/
Modified:
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/util/concurrent/TestConcurrentMap.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/util/concurrent/TestConcurrentMap.java?rev=666897&r1=666896&r2=666897&view=diff
==============================================================================
---
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/util/concurrent/TestConcurrentMap.java
(original)
+++
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/util/concurrent/TestConcurrentMap.java
Wed Jun 11 16:27:18 2008
@@ -41,7 +41,7 @@
private static final int SLEEP = 3;
private ConcurrentMap[] _maps = new ConcurrentMap[]{
- new SizedConcurrentHashMap(ENTRIES, .75f, 16),
+ new SizedConcurrentHashMap(ENTRIES, .75f, 16),
new ConcurrentReferenceHashMap(ReferenceMap.HARD, ReferenceMap.HARD),
};
public void setUp() throws Exception {
Modified:
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/util/concurrent/TestNullSafeConcurrentHashMap.java
URL:
http://svn.apache.org/viewvc/openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/util/concurrent/TestNullSafeConcurrentHashMap.java?rev=666897&r1=666896&r2=666897&view=diff
==============================================================================
---
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/util/concurrent/TestNullSafeConcurrentHashMap.java
(original)
+++
openjpa/trunk/openjpa-lib/src/test/java/org/apache/openjpa/lib/util/concurrent/TestNullSafeConcurrentHashMap.java
Wed Jun 11 16:27:18 2008
@@ -19,34 +19,80 @@
package org.apache.openjpa.lib.util.concurrent;
import java.io.IOException;
-import java.util.concurrent.ConcurrentMap;
-import java.util.concurrent.ConcurrentHashMap;
-import java.util.Iterator;
import java.util.Set;
import java.util.Collection;
import java.util.Map;
import java.util.HashMap;
-import java.util.Enumeration;
import java.util.Map.Entry;
import org.apache.openjpa.lib.test.AbstractTestCase;
public class TestNullSafeConcurrentHashMap extends AbstractTestCase {
- private Map newMap() {
+ private NullSafeConcurrentHashMap newMap() {
return new NullSafeConcurrentHashMap();
-// return new HashMap();
+ }
+
+ public void testRemoveRandomIsNotTotallyDeterministic() {
+ removeHelper(false);
+ }
+
+ public void testRandomIteratorIsNotTotallyDeterministic() {
+ removeHelper(true);
+ }
+
+ private void removeHelper(boolean iter) {
+ Map<String,Integer> removedCounts = new HashMap();
+ for (int i = 0; i < 1000; i++) {
+ NullSafeConcurrentHashMap m = new NullSafeConcurrentHashMap();
+ m.put("a", "A");
+ m.put("b", "B");
+ m.put("c", "C");
+ m.put("d", "D");
+ m.put("e", "E");
+ m.put("f", "F");
+ m.put("g", "G");
+
+ String removed;
+ if (iter) {
+ removed = (String) m.removeRandom().getKey();
+ } else {
+ removed = (String) ((Entry) m.randomEntryIterator().next())
+ .getKey();
+ m.remove(removed);
+ }
+
+ Integer count = removedCounts.get(removed);
+ if (count == null)
+ removedCounts.put(removed, 1);
+ else
+ removedCounts.put(removed, count.intValue() + 1);
+ }
+
+ // assume that over 1000 runs, every element should be removed at
+ // least once, and no element should be removed more than 30% of
+ // the time
+ assertEquals(7, removedCounts.size());
+ for (Entry<String,Integer> entry : removedCounts.entrySet()) {
+ if (entry.getValue() == 0)
+ fail("element " + entry.getKey() + " was never removed");
+ if (entry.getValue() > 500)
+ fail("element " + entry.getKey() + " was removed "
+ + entry.getValue() + " times; this is greater than the "
+ + "threshold of 500.");
+ }
}
public void testNullKeys() throws ClassNotFoundException, IOException {
- Map m = newMap();
- helper(m, null, "value 0", "value 1", "value 2");
+ helper(null, "value 0", "value 1", "value 2");
}
- private void helper(Map m, Object key, Object value0,
+ private void helper(Object key, Object value0,
Object value1, Object value2)
throws IOException, ClassNotFoundException {
+ NullSafeConcurrentHashMap m = newMap();
+
// initial put
m.put(key, value0);
@@ -77,7 +123,6 @@
// put
assertEquals(value0, m.put(key, value1));
-// m.putAll(); #####
// remove
assertEquals(value1, m.put(key, value1));
@@ -85,42 +130,50 @@
m.put(key, value1);
// ConcurrentMap stuff
- ConcurrentMap cm = (ConcurrentMap) m;
- assertFalse(cm.remove("invalid key", value0));
- assertTrue(cm.remove(key, value1));
- assertNull(cm.putIfAbsent(key, value0)); // null == prev unset
+ assertFalse(m.remove("invalid key", value0));
+ assertTrue(m.remove(key, value1));
+ assertNull(m.putIfAbsent(key, value0)); // null == prev unset
// value0 might be null; can't disambiguate from above in OpenJPA
// interpretation
- assertEquals(value0, cm.putIfAbsent(key, "invalid value"));
+ assertEquals(value0, m.putIfAbsent(key, "invalid value"));
// replace
- assertEquals(value0, cm.replace(key, value1));
- assertTrue(cm.replace(key, value1, value2));
+ assertEquals(value0, m.replace(key, value1));
+ assertTrue(m.replace(key, value1, value2));
+
+ // putAll. Note that ConcurrentHashMap happens to delegate to put()
+ // from within putAll() calls. This test should help ensure that we
+ // find out if that changes.
+ m = newMap();
+ Map putAllArg = new HashMap();
+ putAllArg.put(key, value0);
+ putAllArg.put("another key", value1);
+ m.putAll(putAllArg);
+ assertEquals(value0, m.get(key));
+ assertEquals(value1, m.get("another key"));
}
public void testNullValues() throws ClassNotFoundException, IOException {
- Map m = newMap();
- nullValsHelper(m, "foo");
+ nullValsHelper("foo");
}
- private void nullValsHelper(Map m, Object key)
+ private void nullValsHelper(Object key)
throws IOException, ClassNotFoundException {
- helper(m, key, null, null, null);
- helper(m, key, "bar", "baz", "quux");
+ helper(key, null, null, null);
+ helper(key, "bar", "baz", "quux");
- helper(m, key, "bar", "baz", null);
- helper(m, key, null, "baz", "quux");
- helper(m, key, "bar", null, "quux");
-
- helper(m, key, "bar", null, null);
- helper(m, key, null, "baz", null);
- helper(m, key, null, null, "quux");
+ helper(key, "bar", "baz", null);
+ helper(key, null, "baz", "quux");
+ helper(key, "bar", null, "quux");
+
+ helper(key, "bar", null, null);
+ helper(key, null, "baz", null);
+ helper(key, null, null, "quux");
}
public void testNullKeysAndValues()
throws ClassNotFoundException, IOException {
- Map m = newMap();
- nullValsHelper(m, null);
+ nullValsHelper(null);
}
}
