Author: manik.surtani(a)jboss.com Date: 2008-07-23 11:25:17 -0400 (Wed, 23 Jul 2008) New Revision: 6380 Added: core/branches/2.2.X/src/main/java/org/jboss/cache/util/ImmutableListCopy.java core/branches/2.2.X/src/main/java/org/jboss/cache/util/ImmutableSetCopy.java core/branches/2.2.X/src/test/java/org/jboss/cache/util/ImmutableListCopyTest.java Modified: core/branches/2.2.X/src/main/java/org/jboss/cache/Fqn.java core/branches/2.2.X/src/main/java/org/jboss/cache/UnversionedNode.java core/branches/2.2.X/src/main/java/org/jboss/cache/buddyreplication/BuddyFqnTransformer.java core/branches/2.2.X/src/main/java/org/jboss/cache/buddyreplication/BuddyGroup.java core/branches/2.2.X/src/main/java/org/jboss/cache/commands/remote/DataGravitationCleanupCommand.java core/branches/2.2.X/src/main/java/org/jboss/cache/invocation/CacheInvocationDelegate.java Log: Performance tweaks using custom immutable collections Modified: core/branches/2.2.X/src/main/java/org/jboss/cache/Fqn.java =================================================================== --- core/branches/2.2.X/src/main/java/org/jboss/cache/Fqn.java 2008-07-23 15:21:40 UTC (rev 6379) +++ core/branches/2.2.X/src/main/java/org/jboss/cache/Fqn.java 2008-07-23 15:25:17 UTC (rev 6380) @@ -10,6 +10,7 @@ import net.jcip.annotations.Immutable; import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; +import org.jboss.cache.util.ImmutableListCopy; import java.io.Externalizable; import java.io.IOException; @@ -124,12 +125,7 @@ if (names != null) { // if not safe make a defensive copy - elements = safe ? names : new ArrayList(names); - if (elements.size() > 0) - { - if (SEPARATOR.equals(elements.get(0))) elements.remove(0); - if ("".equals(elements.get(0))) elements.remove(0); - } + elements = safe ? names : new ImmutableListCopy(names); size = elements.size(); } else @@ -142,10 +138,7 @@ @SuppressWarnings("unchecked") protected Fqn(boolean internalMarker, Fqn<?> base, List<?> relative) { - List elements = new ArrayList(base.elements.size() + relative.size()); - elements.addAll(base.elements); - elements.addAll(relative); - this.elements = elements; + elements = new ImmutableListCopy(base.elements, relative); size = elements.size(); } @@ -344,12 +337,12 @@ @SuppressWarnings("unchecked") public static Fqn<String> fromString(String stringRepresentation) { - if (stringRepresentation == null || stringRepresentation.equals(SEPARATOR)) - { - return ROOT; - } - List<String> elements = Arrays.asList(stringRepresentation.split("/")); - return new Fqn(true, elements, false); + if (stringRepresentation == null || stringRepresentation.equals(SEPARATOR) || stringRepresentation.equals("")) + return root(); + + String toMatch = stringRepresentation.startsWith(SEPARATOR) ? stringRepresentation.substring(1) : stringRepresentation; + Object[] el = toMatch.split("/"); + return new Fqn(new ImmutableListCopy(el), true); } /** @@ -554,6 +547,17 @@ } /** + * Returns true if this Fqn is a <i>direct</i> child of a given Fqn. + * + * @param parentFqn parentFqn to compare with + * @return true if this is a direct child, false otherwise. + */ + public boolean isDirectChildOf(Fqn parentFqn) + { + return size == parentFqn.size() - 1 && isChildOf(parentFqn); + } + + /** * Returns true if this Fqn is equals or the child of parentFqn. * Example usage: * <pre> Modified: core/branches/2.2.X/src/main/java/org/jboss/cache/UnversionedNode.java =================================================================== --- core/branches/2.2.X/src/main/java/org/jboss/cache/UnversionedNode.java 2008-07-23 15:21:40 UTC (rev 6379) +++ core/branches/2.2.X/src/main/java/org/jboss/cache/UnversionedNode.java 2008-07-23 15:25:17 UTC (rev 6380) @@ -16,7 +16,9 @@ import org.jboss.cache.marshall.MarshalledValue; import org.jboss.cache.optimistic.DataVersion; import org.jboss.cache.transaction.GlobalTransaction; +import org.jboss.cache.util.ImmutableSetCopy; +import java.util.Collection; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; @@ -419,11 +421,12 @@ public void addChildDirect(NodeSPI child) { - if (child.getFqn().getParent().equals(getFqn())) + Fqn childFqn = child.getFqn(); + if (childFqn.isDirectChildOf(fqn)) { synchronized (this) { - children().put(child.getFqn().getLastElement(), child); + children().put(childFqn.getLastElement(), child); } } else @@ -490,7 +493,7 @@ { return Collections.emptySet(); } - return Collections.unmodifiableSet(new HashSet<Object>(data.keySet())); + return new ImmutableSetCopy(data.keySet()); } public boolean removeChildDirect(Object childName) @@ -643,7 +646,7 @@ { if (children != null && !children.isEmpty()) { - return Collections.unmodifiableSet(new HashSet(children.values())); + return new ImmutableSetCopy<NodeSPI>((Collection) children.values()); } else { Modified: core/branches/2.2.X/src/main/java/org/jboss/cache/buddyreplication/BuddyFqnTransformer.java =================================================================== --- core/branches/2.2.X/src/main/java/org/jboss/cache/buddyreplication/BuddyFqnTransformer.java 2008-07-23 15:21:40 UTC (rev 6379) +++ core/branches/2.2.X/src/main/java/org/jboss/cache/buddyreplication/BuddyFqnTransformer.java 2008-07-23 15:25:17 UTC (rev 6380) @@ -130,7 +130,7 @@ public boolean isDeadBackupRoot(Fqn f) { - return f.getParent().equals(BUDDY_BACKUP_SUBTREE_FQN) && f.getLastElementAsString().endsWith(":DEAD"); + return f.isDirectChildOf(BUDDY_BACKUP_SUBTREE_FQN) && f.getLastElementAsString().endsWith(":DEAD"); } public String getGroupNameFromAddress(Address address) Modified: core/branches/2.2.X/src/main/java/org/jboss/cache/buddyreplication/BuddyGroup.java =================================================================== --- core/branches/2.2.X/src/main/java/org/jboss/cache/buddyreplication/BuddyGroup.java 2008-07-23 15:21:40 UTC (rev 6379) +++ core/branches/2.2.X/src/main/java/org/jboss/cache/buddyreplication/BuddyGroup.java 2008-07-23 15:25:17 UTC (rev 6380) @@ -7,12 +7,11 @@ package org.jboss.cache.buddyreplication; import net.jcip.annotations.ThreadSafe; +import org.jboss.cache.util.ImmutableListCopy; import org.jgroups.Address; import java.io.Serializable; -import java.util.ArrayList; import java.util.Collection; -import java.util.Collections; import java.util.Date; import java.util.List; import java.util.Vector; @@ -66,7 +65,7 @@ public List<Address> getBuddies() { // defensive copy and immutable. - return Collections.unmodifiableList(new ArrayList<Address>(buddies)); + return new ImmutableListCopy<Address>(buddies); } protected void addBuddies(Collection<Address> buddies) Modified: core/branches/2.2.X/src/main/java/org/jboss/cache/commands/remote/DataGravitationCleanupCommand.java =================================================================== --- core/branches/2.2.X/src/main/java/org/jboss/cache/commands/remote/DataGravitationCleanupCommand.java 2008-07-23 15:21:40 UTC (rev 6379) +++ core/branches/2.2.X/src/main/java/org/jboss/cache/commands/remote/DataGravitationCleanupCommand.java 2008-07-23 15:25:17 UTC (rev 6380) @@ -84,7 +84,7 @@ // only attempt to clean up the backup if the primary did not exist - a waste of a call otherwise. Object result = executeRemove(gtx, backup); if (wasNodeRemoved(result) && - buddyFqnTransformer.isDeadBackupFqn(backup) && buddyFqnTransformer.isDeadBackupRoot(backup.getParent().getParent())) + buddyFqnTransformer.isDeadBackupFqn(backup) && buddyFqnTransformer.isDeadBackupRoot(backup.getAncestor(backup.size() - 2))) { // if this is a DIRECT child of a DEAD buddy backup region, then remove the empty dead region structural node. NodeSPI deadBackupRoot = dataContainer.peek(backup.getParent(), false); Modified: core/branches/2.2.X/src/main/java/org/jboss/cache/invocation/CacheInvocationDelegate.java =================================================================== --- core/branches/2.2.X/src/main/java/org/jboss/cache/invocation/CacheInvocationDelegate.java 2008-07-23 15:21:40 UTC (rev 6379) +++ core/branches/2.2.X/src/main/java/org/jboss/cache/invocation/CacheInvocationDelegate.java 2008-07-23 15:25:17 UTC (rev 6380) @@ -39,12 +39,12 @@ import org.jboss.cache.statetransfer.StateTransferManager; import org.jboss.cache.transaction.GlobalTransaction; import org.jboss.cache.transaction.TransactionTable; +import org.jboss.cache.util.ImmutableSetCopy; import org.jgroups.Address; import javax.transaction.Transaction; import javax.transaction.TransactionManager; import java.util.Collections; -import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; @@ -560,7 +560,7 @@ GetChildrenNamesCommand command = commandsFactory.buildGetChildrenNamesCommand(fqn); Set<E> retval = (Set<E>) invoker.invoke(ctx, command); if (retval != null) - retval = Collections.unmodifiableSet(new HashSet<E>(retval)); + retval = new ImmutableSetCopy<E>(retval); else retval = Collections.emptySet(); return retval; Added: core/branches/2.2.X/src/main/java/org/jboss/cache/util/ImmutableListCopy.java =================================================================== --- core/branches/2.2.X/src/main/java/org/jboss/cache/util/ImmutableListCopy.java (rev 0) +++ core/branches/2.2.X/src/main/java/org/jboss/cache/util/ImmutableListCopy.java 2008-07-23 15:25:17 UTC (rev 6380) @@ -0,0 +1,426 @@ +package org.jboss.cache.util; + +import net.jcip.annotations.Immutable; + +import java.lang.reflect.Array; +import java.util.AbstractList; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; +import java.util.ListIterator; +import java.util.NoSuchElementException; + +/** + * A lightweight, read-only copy of a List. Typically used in place of the common idiom: + * <code> + * return Collections.unmodifiableList(new ArrayList( myInternalList )); + * </code> + * <p/> + * a it is far more efficient than making a defensive copy and then wrapping the defensive copy in a read-only wrapper. + * <p/> + * Also used whenever a read-only reference List is needed (such as in Fqns). + * <p/> + * + * @author Manik Surtani (<a href="mailto:manik@jboss.org">manik@jboss.org</a>) + */ +@Immutable +public class ImmutableListCopy<E> extends AbstractList<E> +{ + private final E[] elements; + private final int size; + + /** + * Only one copy constructor since the list is immutable. + * + * @param c collection to copy from + */ + @SuppressWarnings("unchecked") + public ImmutableListCopy(Collection<? extends E> c) + { + size = c.size(); + Object[] el = new Object[size]; // no room for growth; + el = c.toArray(el); + elements = (E[]) el; + } + + /** + * Assumes that the array passed in is "safe", i.e., is not referenced from elsewhere. Use with care! + * + * @param array to reference + */ + public ImmutableListCopy(E[] array) + { + size = array.length; + elements = array; + } + + /** + * Utility constructors to allow combining collections + * + * @param collection1 collection to copy from + * @param collection2 collection to copy from + */ + @SuppressWarnings("unchecked") + public ImmutableListCopy(Collection<? extends E> collection1, Collection<? extends E> collection2) + { + size = collection1.size() + collection2.size(); + elements = (E[]) new Object[size]; // no room for growth; + Object[] c1 = new Object[collection1.size()]; + Object[] c2 = new Object[collection2.size()]; + c1 = collection1.toArray(c1); + c2 = collection2.toArray(c2); + System.arraycopy(c1, 0, elements, 0, c1.length); + System.arraycopy(c2, 0, elements, c1.length, c2.length); + } + + @Override + public final int size() + { + return size; + } + + @Override + public final boolean isEmpty() + { + return size == 0; + } + + @Override + public final boolean contains(Object o) + { + return indexOf(o) >= 0; + } + + @Override + public final Iterator<E> iterator() + { + return new ImmutableIterator(); + } + + @Override + public final Object[] toArray() + { + Object[] result = new Object[size]; + System.arraycopy(elements, 0, result, 0, size); + return result; + } + + @Override + @SuppressWarnings("unchecked") + public final <T> T[] toArray(T[] a) + { + if (a.length < size) + { + a = (T[]) Array.newInstance(a.getClass().getComponentType(), size); + } + System.arraycopy(elements, 0, a, 0, size); + if (a.length > size) a[size] = null; + return a; + } + + @Override + public final boolean add(E o) + { + throw new UnsupportedOperationException(); + } + + @Override + public final boolean remove(Object o) + { + throw new UnsupportedOperationException(); + } + + @Override + public final boolean addAll(Collection<? extends E> c) + { + throw new UnsupportedOperationException(); + } + + @Override + public final boolean addAll(int index, Collection<? extends E> c) + { + throw new UnsupportedOperationException(); + } + + @Override + public final boolean removeAll(Collection<?> c) + { + throw new UnsupportedOperationException(); + } + + @Override + public final boolean retainAll(Collection<?> c) + { + throw new UnsupportedOperationException(); + } + + public final E get(int index) + { + assertIndexInRange(index); + return elements[index]; + } + + @Override + public final int indexOf(Object o) + { + if (o == null) + { + for (int i = 0; i < size; i++) + { + if (elements[i] == null) return i; + } + } + else + { + for (int i = 0; i < size; i++) + { + if (o.equals(elements[i])) return i; + } + } + return -1; + } + + @Override + public final int lastIndexOf(Object o) + { + if (o == null) + { + for (int i = size - 1; i >= 0; i--) + { + if (elements[i] == null) return i; + } + } + else + { + for (int i = size - 1; i >= 0; i--) + { + if (o.equals(elements[i])) return i; + } + } + return -1; + } + + @Override + public final ListIterator<E> listIterator() + { + return new ImmutableIterator(); + } + + @Override + public final ListIterator<E> listIterator(int index) + { + return new ImmutableIterator(index); + } + + @Override + public final List<E> subList(int fromIndex, int toIndex) + { + return new ImmutableSubList<E>(fromIndex, toIndex); + } + + private void assertIndexInRange(int index) + { + if (index >= size || index < 0) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); + } + + private class ImmutableIterator implements ListIterator<E> + { + int cursor = 0; + + ImmutableIterator(int index) + { + if (index < 0 || index > size()) throw new IndexOutOfBoundsException("Index: " + index); + cursor = index; + } + + ImmutableIterator() + { + } + + public boolean hasNext() + { + return cursor != size; + } + + public E next() + { + try + { + return get(cursor++); + } + catch (IndexOutOfBoundsException e) + { + throw new NoSuchElementException(); + } + } + + public void remove() + { + throw new UnsupportedOperationException(); + } + + public boolean hasPrevious() + { + return cursor != 0; + } + + public E previous() + { + try + { + return get(--cursor); + } + catch (IndexOutOfBoundsException e) + { + throw new NoSuchElementException(); + } + } + + public int nextIndex() + { + return cursor; + } + + public int previousIndex() + { + return cursor - 1; + } + + public void set(E o) + { + throw new UnsupportedOperationException(); + } + + public void add(E o) + { + throw new UnsupportedOperationException(); + } + } + + private class ImmutableSubList<E> extends AbstractList<E> + { + private int offset; + private int size; + + ImmutableSubList(int fromIndex, int toIndex) + { + assertIndexInRange(fromIndex); + assertIndexInRange(toIndex - 1); + if (fromIndex > toIndex) + throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); + offset = fromIndex; + size = toIndex - fromIndex; + } + + @SuppressWarnings("unchecked") + public final E get(int index) + { + rangeCheck(index); + return (E) ImmutableListCopy.this.get(index + offset); + } + + private void rangeCheck(int index) + { + if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ",Size: " + size); + } + + public final int size() + { + return size; + } + + @Override + protected final void removeRange(int fromIndex, int toIndex) + { + throw new UnsupportedOperationException(); + } + + @Override + public final boolean addAll(Collection<? extends E> c) + { + throw new UnsupportedOperationException(); + } + + @Override + public final boolean addAll(int index, Collection<? extends E> c) + { + throw new UnsupportedOperationException(); + } + + @Override + public final Iterator<E> iterator() + { + return listIterator(); + } + + @Override + public final ListIterator<E> listIterator(final int index) + { + rangeCheck(index); + + return new ListIterator<E>() + { + private ListIterator i = ImmutableListCopy.this.listIterator(index + offset); + + public boolean hasNext() + { + return nextIndex() < size; + } + + @SuppressWarnings("unchecked") + public E next() + { + if (hasNext()) + return (E) i.next(); + else + throw new NoSuchElementException(); + } + + public boolean hasPrevious() + { + return previousIndex() >= 0; + } + + @SuppressWarnings("unchecked") + public E previous() + { + if (hasPrevious()) + return (E) i.previous(); + else + throw new NoSuchElementException(); + } + + public int nextIndex() + { + return i.nextIndex() - offset; + } + + public int previousIndex() + { + return i.previousIndex() - offset; + } + + public void remove() + { + throw new UnsupportedOperationException(); + } + + public void set(E o) + { + throw new UnsupportedOperationException(); + } + + public void add(E o) + { + throw new UnsupportedOperationException(); + } + }; + } + + @Override + public final List<E> subList(int fromIndex, int toIndex) + { + return new ImmutableSubList<E>(offset + fromIndex, offset + toIndex); + } + } +} Added: core/branches/2.2.X/src/main/java/org/jboss/cache/util/ImmutableSetCopy.java =================================================================== --- core/branches/2.2.X/src/main/java/org/jboss/cache/util/ImmutableSetCopy.java (rev 0) +++ core/branches/2.2.X/src/main/java/org/jboss/cache/util/ImmutableSetCopy.java 2008-07-23 15:25:17 UTC (rev 6380) @@ -0,0 +1,108 @@ +package org.jboss.cache.util; + +import net.jcip.annotations.Immutable; + +import java.util.AbstractSet; +import java.util.Collection; +import java.util.Iterator; +import java.util.NoSuchElementException; + +/** + * This is based on an ImmutableListCopy, with the assumption that the set passed in would ensure uniqueness of elements. + * <p/> + * The constructor takes in a collection so the onus is on the caller to ensure that the collection passed in adheres to + * Set semantics. + * <p/> + * Typically used in place of the common idiom: + * <code> + * return Collections.unmodifiableSet(new HashSet( myInternalSet )); + * </code> + * + * @author Manik Surtani (<a href="mailto:manik@jboss.org">manik@jboss.org</a>) + * @see org.jboss.cache.util.ImmutableListCopy + */ +@Immutable +public class ImmutableSetCopy<E> extends AbstractSet<E> +{ + private final E[] elements; + private final int size; + + @SuppressWarnings("unchecked") + public ImmutableSetCopy(Collection<E> set) + { + size = set.size(); + E[] tempElements = (E[]) new Object[size]; // no room for growth + elements = set.toArray(tempElements); + } + + /** + * Assumes that the array passed in is "safe", i.e., is not referenced from elsewhere. Also assumes the array contains + * elements such that the uniqueness required by a set is adhered to. Use with care! + * + * @param array to reference + */ + public ImmutableSetCopy(E[] array) + { + elements = array; + size = elements.length; + } + + @Override + public boolean remove(Object o) + { + throw new UnsupportedOperationException(); + } + + @Override + public boolean addAll(Collection<? extends E> c) + { + throw new UnsupportedOperationException(); + } + + @Override + public boolean retainAll(Collection<?> c) + { + throw new UnsupportedOperationException(); + } + + @Override + public boolean removeAll(Collection<?> c) + { + throw new UnsupportedOperationException(); + } + + @Override + public void clear() + { + throw new UnsupportedOperationException(); + } + + public Iterator<E> iterator() + { + return new Iterator<E>() + { + int cursor = 0; + + public boolean hasNext() + { + return cursor < size; + } + + public E next() + { + if (cursor >= size) throw new NoSuchElementException(); + return elements[cursor++]; + } + + public void remove() + { + throw new UnsupportedOperationException(); + } + }; + } + + public int size() + { + return size; + } +} Added: core/branches/2.2.X/src/test/java/org/jboss/cache/util/ImmutableListCopyTest.java =================================================================== --- core/branches/2.2.X/src/test/java/org/jboss/cache/util/ImmutableListCopyTest.java (rev 0) +++ core/branches/2.2.X/src/test/java/org/jboss/cache/util/ImmutableListCopyTest.java 2008-07-23 15:25:17 UTC (rev 6380) @@ -0,0 +1,144 @@ +package org.jboss.cache.util; + +import org.testng.annotations.Test; + +import java.util.Arrays; +import java.util.Collections; +import java.util.List; +import java.util.ListIterator; + +@Test(groups = "unit") +public class ImmutableListCopyTest +{ + public void testImmutability() + { + List<String> l = new ImmutableListCopy<String>(Collections.singletonList("one")); + try + { + l.add("two"); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + + try + { + l.remove(0); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + + try + { + l.clear(); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + + try + { + l.add(0, "x"); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + + try + { + l.set(0, "i"); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + + try + { + l.addAll(Collections.singletonList("l")); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + + try + { + l.addAll(0, Collections.singletonList("l")); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + + try + { + l.removeAll(Collections.singletonList("l")); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + + try + { + l.retainAll(Collections.singletonList("l")); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + + try + { + l.iterator().remove(); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + + try + { + l.listIterator().set("w"); + assert false; + } + catch (UnsupportedOperationException good) + { + + } + } + + public void testListIterator() + { + List<Integer> ints = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); + + List<Integer> list = new ImmutableListCopy<Integer>(ints); + + ListIterator<Integer> li = list.listIterator(); + + int number = 1; + while (li.hasNext()) assert li.next() == number++; + assert number == 11; + + number = 10; + li = list.listIterator(list.size()); + while (li.hasPrevious()) assert li.previous() == number--; + assert number == 0; + } +}