Author: genman Date: 2007-10-16 23:11:06 -0400 (Tue, 16 Oct 2007) New Revision: 4628 Added: core/trunk/src/main/java/org/jboss/cache/util/DeltaMap.java core/trunk/src/test/java/org/jboss/cache/util/DeltaMapTest.java Log: Wrapper for a Map that tracks changes against the wrapped map Saves data copying for a small set of modifications Added: core/trunk/src/main/java/org/jboss/cache/util/DeltaMap.java =================================================================== --- core/trunk/src/main/java/org/jboss/cache/util/DeltaMap.java (rev 0) +++ core/trunk/src/main/java/org/jboss/cache/util/DeltaMap.java 2007-10-17 03:11:06 UTC (rev 4628) @@ -0,0 +1,252 @@ +package org.jboss.cache.util; + +import java.util.AbstractMap; +import java.util.AbstractSet; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.Map; +import java.util.NoSuchElementException; +import java.util.Set; + +/** + * Wraps an existing map, which is not modified, reflecting modifications + * in an internal modification set. + * + * This is to minimize the amount of data copying, for instance in the + * case few changes are applied. + * + * Example usage: + <pre> +HashMap&lt;String, String> hm = new HashMap&lt;String, String>(); +hm.put("a", "apple"); +DeltaMap<String, String> dm = DeltaMap.create(hm); +dm.remove("a"); +assert hm.containsKey("a"); +assert !dm.containsKey("a"); +dm.commit(); +assert !hm.containsKey("a"); +</pre> + * + * @author Elias Ross + * @param <K> key type + * @param <V> value type + */ +public class DeltaMap<K, V> extends AbstractMap<K, V> +{ + + /** + * Wrapped instance. + */ + private Map<K, V> original; + + /** + * Keys removed. + * This should not exceed the size of the original map. + */ + private Set<K> removed = new HashSet<K>(); + + /** + * Keys changed. + * This may contain new entries or entries modified. + */ + private Map<K, V> changed = new HashMap<K, V>(); + + /** + * Constructs a new DeltaMap. + * @param original will not be modified. + */ + private DeltaMap(Map<K, V> original) + { + if (original == null) + throw new NullPointerException("original"); + this.original = original; + } + + /** + * Creates and returns a DeltaMap for an original map. + * + * @param original will not be modified, except by {@link #commit()} + * @return a new instance + */ + public static <K, V> DeltaMap<K, V> create(Map<K, V> original) + { + return new DeltaMap<K, V>(original); + } + + @Override + public Set<java.util.Map.Entry<K, V>> entrySet() + { + return new AbstractSet<Entry<K, V>>() + { + + @Override + public Iterator<java.util.Map.Entry<K, V>> iterator() + { + return new WrappedIterator(); + } + + @Override + public int size() + { + int size = original.size() - removed.size(); + for (Object o : changed.keySet()) + { + if (!original.containsKey(o)) + size++; + } + return size; + } + }; + } + + @Override + public boolean containsKey(Object key) + { + if (removed.contains(key)) + return false; + if (changed.containsKey(key)) + return true; + return original.containsKey(key); + } + + @Override + public V get(Object key) + { + if (removed.contains(key)) + return null; + if (changed.containsKey(key)) + return changed.get(key); + return original.get(key); + } + + @Override + public V put(K key, V value) + { + V old; + if (changed.containsKey(key)) + old = changed.get(key); + else + old = original.get(key); + changed.put(key, value); + if (removed.contains(key)) + { + removed.remove(key); + return null; + } + return old; + } + + @SuppressWarnings("unchecked") + @Override + public V remove(Object key) + { + if (changed.containsKey(key)) + { + if (original.containsKey(key)) + removed.add((K) key); + return changed.remove(key); + } + if (removed.contains(key)) + { + return null; + } + if (original.containsKey(key)) + { + removed.add((K) key); + return original.get(key); + } + return null; + } + + /** + * Commits the changes to the original map. + * Clears the list of removed keys. + */ + public void commit() + { + original.keySet().removeAll(removed); + original.putAll(changed); + removed.clear(); + changed.clear(); + } + + /** + * Iterator that skips over removed entries. + * @author Elias Ross + */ + private class WrappedIterator implements Iterator<Entry<K, V>> + { + + private boolean orig = true; + private boolean nextSet = false; + private Entry<K, V> next; + private Iterator<Entry<K, V>> i = original.entrySet().iterator(); + + private boolean redef(Entry<K, V> e) + { + K key = e.getKey(); + return removed.contains(key) || changed.containsKey(key); + } + + public boolean hasNext() + { + if (nextSet) + return true; + if (orig) + { + while (i.hasNext() && redef(next = i.next())); + nextSet = true; + if (!i.hasNext()) + { + orig = false; + i = changed.entrySet().iterator(); + } + } + else + { + if (!i.hasNext()) + return false; + next = i.next(); + nextSet = true; + return true; + } + return i.hasNext(); + } + + public java.util.Map.Entry<K, V> next() + { + if (!hasNext()) + throw new NoSuchElementException(); + try + { + return next; + } + finally + { + nextSet = false; + } + } + + public void remove() + { + DeltaMap.this.remove(next.getKey()); + } + + } + + /** + * Returns a debug string. + */ + public String toDebugString() { + return "DeltaMap original=" + original + " removed=" + removed + " changed=" + changed; + } + + @Override + public void clear() + { + removed.addAll(original.keySet()); + changed.clear(); + } + +} Added: core/trunk/src/test/java/org/jboss/cache/util/DeltaMapTest.java =================================================================== --- core/trunk/src/test/java/org/jboss/cache/util/DeltaMapTest.java (rev 0) +++ core/trunk/src/test/java/org/jboss/cache/util/DeltaMapTest.java 2007-10-17 03:11:06 UTC (rev 4628) @@ -0,0 +1,111 @@ +package org.jboss.cache.util; + +import static org.testng.AssertJUnit.assertEquals; +import static org.testng.AssertJUnit.fail; + +import java.util.HashMap; +import java.util.Iterator; +import java.util.NoSuchElementException; +import java.util.Map.Entry; + +import org.testng.annotations.Test; + +@Test(groups = {"functional", "transaction"}) +public class DeltaMapTest +{ + + public static String Y = "y"; + + public static String Z = "z"; + + public static String K = "k"; + + HashMap<String, String> hm = new HashMap<String, String>(); + { + hm.put(null, null); + hm.put(Y, Z); + hm.put(K, Y); + } + + HashMap<String, String> backup = new HashMap<String, String>(hm); + + DeltaMap<String, String> dm = DeltaMap.create(hm); + + public void testChanges() throws Exception + { + assertEquals(backup, dm); + assertEquals(Z, dm.remove(Y)); + assertEquals(null, dm.remove(Y)); + assertEquals("changes not made to underlying map", backup, hm); + assertEquals(false, dm.containsKey(Y)); + assertEquals(false, dm.containsValue(Z)); + assertEquals(null, dm.put(Y, Z)); + assertEquals(Z, dm.put(Y, Z)); + assertEquals("changes not made to underlying map", backup, hm); + assertEquals(backup.size(), dm.size()); + assertEquals(backup, dm); + dm.commit(); + assertEquals(hm, dm); + dm.commit(); + assertEquals(hm, dm); + } + + public void testAddRemove() throws Exception + { + dm.remove(K); + dm.put(K, Z); + assertEquals(Z, dm.get(K)); + assertEquals(Z, dm.remove(K)); + assertEquals(null, dm.remove(K)); + } + + public void testClear() throws Exception + { + dm.clear(); + assertEquals(0, dm.size()); + assertEquals(backup, hm); + assertEquals(null, dm.remove(Y)); + } + + public void testIterator() throws Exception + { + dm.remove(null); + dm.put(K, Y); + System.out.println(dm.toDebugString()); + System.out.println(dm.toString()); + Iterator<Entry<String, String>> i = dm.entrySet().iterator(); + assertEquals(true, i.hasNext()); + assertEquals(true, i.hasNext()); + i.next(); + assertEquals(true, i.hasNext()); + i.next(); + assertEquals("" + dm, false, i.hasNext()); + try + { + i.next(); + fail("no next"); + } + catch (NoSuchElementException e) + { + } + try + { + i.next(); + fail("no next"); + } + catch (NoSuchElementException e) + { + } + } + + public void testEx() { +HashMap<String, String> hm = new HashMap<String, String>(); +hm.put("a", "apple"); +DeltaMap<String, String> dm = DeltaMap.create(hm); +dm.remove("a"); +assert hm.containsKey("a"); +assert !dm.containsKey("a"); +dm.commit(); +assert !hm.containsKey("a"); + } +}