diff options
5 files changed, 1703 insertions, 3 deletions
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefListTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefListTest.java new file mode 100644 index 0000000000..c9522341b0 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefListTest.java @@ -0,0 +1,431 @@ +/* + * Copyright (C) 2010, Google Inc. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.eclipse.jgit.util; + +import java.util.Iterator; +import java.util.NoSuchElementException; + +import junit.framework.TestCase; + +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.Ref; + +public class RefListTest extends TestCase { + private static final ObjectId ID = ObjectId + .fromString("41eb0d88f833b558bddeb269b7ab77399cdf98ed"); + + private static final Ref REF_A = newRef("A"); + + private static final Ref REF_B = newRef("B"); + + private static final Ref REF_c = newRef("c"); + + public void testEmpty() { + RefList<Ref> list = RefList.emptyList(); + assertEquals(0, list.size()); + assertTrue(list.isEmpty()); + assertFalse(list.iterator().hasNext()); + assertEquals(-1, list.find("a")); + assertEquals(-1, list.find("z")); + assertFalse(list.contains("a")); + assertNull(list.get("a")); + try { + list.get(0); + fail("RefList.emptyList should have 0 element array"); + } catch (ArrayIndexOutOfBoundsException err) { + // expected + } + } + + public void testEmptyBuilder() { + RefList<Ref> list = new RefList.Builder<Ref>().toRefList(); + assertEquals(0, list.size()); + assertFalse(list.iterator().hasNext()); + assertEquals(-1, list.find("a")); + assertEquals(-1, list.find("z")); + assertFalse(list.contains("a")); + assertNull(list.get("a")); + assertTrue(list.asList().isEmpty()); + assertEquals("[]", list.toString()); + + // default array capacity should be 16, with no bounds checking. + assertNull(list.get(16 - 1)); + try { + list.get(16); + fail("default RefList should have 16 element array"); + } catch (ArrayIndexOutOfBoundsException err) { + // expected + } + } + + public void testBuilder_AddThenSort() { + RefList.Builder<Ref> builder = new RefList.Builder<Ref>(1); + builder.add(REF_B); + builder.add(REF_A); + + RefList<Ref> list = builder.toRefList(); + assertEquals(2, list.size()); + assertSame(REF_B, list.get(0)); + assertSame(REF_A, list.get(1)); + + builder.sort(); + list = builder.toRefList(); + assertEquals(2, list.size()); + assertSame(REF_A, list.get(0)); + assertSame(REF_B, list.get(1)); + } + + public void testBuilder_AddAll() { + RefList.Builder<Ref> builder = new RefList.Builder<Ref>(1); + Ref[] src = { REF_A, REF_B, REF_c, REF_A }; + builder.addAll(src, 1, 2); + + RefList<Ref> list = builder.toRefList(); + assertEquals(2, list.size()); + assertSame(REF_B, list.get(0)); + assertSame(REF_c, list.get(1)); + } + + public void testBuilder_Set() { + RefList.Builder<Ref> builder = new RefList.Builder<Ref>(); + builder.add(REF_A); + builder.add(REF_A); + + assertEquals(2, builder.size()); + assertSame(REF_A, builder.get(0)); + assertSame(REF_A, builder.get(1)); + + RefList<Ref> list = builder.toRefList(); + assertEquals(2, list.size()); + assertSame(REF_A, list.get(0)); + assertSame(REF_A, list.get(1)); + builder.set(1, REF_B); + + list = builder.toRefList(); + assertEquals(2, list.size()); + assertSame(REF_A, list.get(0)); + assertSame(REF_B, list.get(1)); + } + + public void testBuilder_Remove() { + RefList.Builder<Ref> builder = new RefList.Builder<Ref>(); + builder.add(REF_A); + builder.add(REF_B); + builder.remove(0); + + assertEquals(1, builder.size()); + assertSame(REF_B, builder.get(0)); + } + + public void testSet() { + RefList<Ref> one = toList(REF_A, REF_A); + RefList<Ref> two = one.set(1, REF_B); + assertNotSame(one, two); + + // one is not modified + assertEquals(2, one.size()); + assertSame(REF_A, one.get(0)); + assertSame(REF_A, one.get(1)); + + // but two is + assertEquals(2, two.size()); + assertSame(REF_A, one.get(0)); + assertSame(REF_B, two.get(1)); + } + + public void testAddToEmptyList() { + RefList<Ref> one = toList(); + RefList<Ref> two = one.add(0, REF_B); + assertNotSame(one, two); + + // one is not modified, but two is + assertEquals(0, one.size()); + assertEquals(1, two.size()); + assertFalse(two.isEmpty()); + assertSame(REF_B, two.get(0)); + } + + public void testAddToFrontOfList() { + RefList<Ref> one = toList(REF_A); + RefList<Ref> two = one.add(0, REF_B); + assertNotSame(one, two); + + // one is not modified, but two is + assertEquals(1, one.size()); + assertSame(REF_A, one.get(0)); + assertEquals(2, two.size()); + assertSame(REF_B, two.get(0)); + assertSame(REF_A, two.get(1)); + } + + public void testAddToEndOfList() { + RefList<Ref> one = toList(REF_A); + RefList<Ref> two = one.add(1, REF_B); + assertNotSame(one, two); + + // one is not modified, but two is + assertEquals(1, one.size()); + assertSame(REF_A, one.get(0)); + assertEquals(2, two.size()); + assertSame(REF_A, two.get(0)); + assertSame(REF_B, two.get(1)); + } + + public void testAddToMiddleOfListByInsertionPosition() { + RefList<Ref> one = toList(REF_A, REF_c); + + assertEquals(-2, one.find(REF_B.getName())); + + RefList<Ref> two = one.add(one.find(REF_B.getName()), REF_B); + assertNotSame(one, two); + + // one is not modified, but two is + assertEquals(2, one.size()); + assertSame(REF_A, one.get(0)); + assertSame(REF_c, one.get(1)); + + assertEquals(3, two.size()); + assertSame(REF_A, two.get(0)); + assertSame(REF_B, two.get(1)); + assertSame(REF_c, two.get(2)); + } + + public void testPutNewEntry() { + RefList<Ref> one = toList(REF_A, REF_c); + RefList<Ref> two = one.put(REF_B); + assertNotSame(one, two); + + // one is not modified, but two is + assertEquals(2, one.size()); + assertSame(REF_A, one.get(0)); + assertSame(REF_c, one.get(1)); + + assertEquals(3, two.size()); + assertSame(REF_A, two.get(0)); + assertSame(REF_B, two.get(1)); + assertSame(REF_c, two.get(2)); + } + + public void testPutReplaceEntry() { + Ref otherc = newRef(REF_c.getName()); + assertNotSame(REF_c, otherc); + + RefList<Ref> one = toList(REF_A, REF_c); + RefList<Ref> two = one.put(otherc); + assertNotSame(one, two); + + // one is not modified, but two is + assertEquals(2, one.size()); + assertSame(REF_A, one.get(0)); + assertSame(REF_c, one.get(1)); + + assertEquals(2, two.size()); + assertSame(REF_A, two.get(0)); + assertSame(otherc, two.get(1)); + } + + public void testRemoveFrontOfList() { + RefList<Ref> one = toList(REF_A, REF_B, REF_c); + RefList<Ref> two = one.remove(0); + assertNotSame(one, two); + + assertEquals(3, one.size()); + assertSame(REF_A, one.get(0)); + assertSame(REF_B, one.get(1)); + assertSame(REF_c, one.get(2)); + + assertEquals(2, two.size()); + assertSame(REF_B, two.get(0)); + assertSame(REF_c, two.get(1)); + } + + public void testRemoveMiddleOfList() { + RefList<Ref> one = toList(REF_A, REF_B, REF_c); + RefList<Ref> two = one.remove(1); + assertNotSame(one, two); + + assertEquals(3, one.size()); + assertSame(REF_A, one.get(0)); + assertSame(REF_B, one.get(1)); + assertSame(REF_c, one.get(2)); + + assertEquals(2, two.size()); + assertSame(REF_A, two.get(0)); + assertSame(REF_c, two.get(1)); + } + + public void testRemoveEndOfList() { + RefList<Ref> one = toList(REF_A, REF_B, REF_c); + RefList<Ref> two = one.remove(2); + assertNotSame(one, two); + + assertEquals(3, one.size()); + assertSame(REF_A, one.get(0)); + assertSame(REF_B, one.get(1)); + assertSame(REF_c, one.get(2)); + + assertEquals(2, two.size()); + assertSame(REF_A, two.get(0)); + assertSame(REF_B, two.get(1)); + } + + public void testRemoveMakesEmpty() { + RefList<Ref> one = toList(REF_A); + RefList<Ref> two = one.remove(1); + assertNotSame(one, two); + assertSame(two, RefList.emptyList()); + } + + public void testToString() { + StringBuilder exp = new StringBuilder(); + exp.append("["); + exp.append(REF_A); + exp.append(", "); + exp.append(REF_B); + exp.append("]"); + + RefList<Ref> list = toList(REF_A, REF_B); + assertEquals(exp.toString(), list.toString()); + } + + public void testBuilder_ToString() { + StringBuilder exp = new StringBuilder(); + exp.append("["); + exp.append(REF_A); + exp.append(", "); + exp.append(REF_B); + exp.append("]"); + + RefList.Builder<Ref> list = new RefList.Builder<Ref>(); + list.add(REF_A); + list.add(REF_B); + assertEquals(exp.toString(), list.toString()); + } + + public void testFindContainsGet() { + RefList<Ref> list = toList(REF_A, REF_B, REF_c); + + assertEquals(0, list.find("A")); + assertEquals(1, list.find("B")); + assertEquals(2, list.find("c")); + + assertEquals(-1, list.find("0")); + assertEquals(-2, list.find("AB")); + assertEquals(-3, list.find("a")); + assertEquals(-4, list.find("z")); + + assertSame(REF_A, list.get("A")); + assertSame(REF_B, list.get("B")); + assertSame(REF_c, list.get("c")); + assertNull(list.get("AB")); + assertNull(list.get("z")); + + assertTrue(list.contains("A")); + assertTrue(list.contains("B")); + assertTrue(list.contains("c")); + assertFalse(list.contains("AB")); + assertFalse(list.contains("z")); + } + + public void testIterable() { + RefList<Ref> list = toList(REF_A, REF_B, REF_c); + + int idx = 0; + for (Ref ref : list) + assertSame(list.get(idx++), ref); + assertEquals(3, idx); + + Iterator<Ref> i = RefList.emptyList().iterator(); + try { + i.next(); + fail("did not throw NoSuchElementException"); + } catch (NoSuchElementException err) { + // expected + } + + i = list.iterator(); + assertTrue(i.hasNext()); + assertSame(REF_A, i.next()); + try { + i.remove(); + fail("did not throw UnsupportedOperationException"); + } catch (UnsupportedOperationException err) { + // expected + } + } + + public void testCopyLeadingPrefix() { + RefList<Ref> one = toList(REF_A, REF_B, REF_c); + RefList<Ref> two = one.copy(2).toRefList(); + assertNotSame(one, two); + + assertEquals(3, one.size()); + assertSame(REF_A, one.get(0)); + assertSame(REF_B, one.get(1)); + assertSame(REF_c, one.get(2)); + + assertEquals(2, two.size()); + assertSame(REF_A, two.get(0)); + assertSame(REF_B, two.get(1)); + } + + public void testCopyConstructorReusesArray() { + RefList.Builder<Ref> one = new RefList.Builder<Ref>(); + one.add(REF_A); + + RefList<Ref> two = new RefList<Ref>(one.toRefList()); + one.set(0, REF_B); + assertSame(REF_B, two.get(0)); + } + + private RefList<Ref> toList(Ref... refs) { + RefList.Builder<Ref> b = new RefList.Builder<Ref>(refs.length); + b.addAll(refs, 0, refs.length); + return b.toRefList(); + } + + private static Ref newRef(final String name) { + return new Ref(Ref.Storage.LOOSE, name, ID); + } +} diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefMapTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefMapTest.java new file mode 100644 index 0000000000..6ce206e013 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/RefMapTest.java @@ -0,0 +1,382 @@ +/* + * Copyright (C) 2010, Google Inc. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.eclipse.jgit.util; + +import java.util.Iterator; +import java.util.Map; +import java.util.NoSuchElementException; + +import junit.framework.TestCase; + +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.Ref; + +public class RefMapTest extends TestCase { + private static final ObjectId ID_ONE = ObjectId + .fromString("41eb0d88f833b558bddeb269b7ab77399cdf98ed"); + + private static final ObjectId ID_TWO = ObjectId + .fromString("698dd0b8d0c299f080559a1cffc7fe029479a408"); + + private RefList<Ref> packed; + + private RefList<Ref> loose; + + private RefList<Ref> resolved; + + protected void setUp() throws Exception { + super.setUp(); + packed = RefList.emptyList(); + loose = RefList.emptyList(); + resolved = RefList.emptyList(); + } + + public void testEmpty_NoPrefix1() { + RefMap map = new RefMap("", packed, loose, resolved); + assertTrue(map.isEmpty()); // before size was computed + assertEquals(0, map.size()); + assertTrue(map.isEmpty()); // after size was computed + + assertFalse(map.entrySet().iterator().hasNext()); + assertFalse(map.keySet().iterator().hasNext()); + assertFalse(map.containsKey("a")); + assertNull(map.get("a")); + } + + public void testEmpty_NoPrefix2() { + RefMap map = new RefMap(); + assertTrue(map.isEmpty()); // before size was computed + assertEquals(0, map.size()); + assertTrue(map.isEmpty()); // after size was computed + + assertFalse(map.entrySet().iterator().hasNext()); + assertFalse(map.keySet().iterator().hasNext()); + assertFalse(map.containsKey("a")); + assertNull(map.get("a")); + } + + public void testNotEmpty_NoPrefix() { + final Ref master = newRef("refs/heads/master", ID_ONE); + packed = toList(master); + + RefMap map = new RefMap("", packed, loose, resolved); + assertFalse(map.isEmpty()); // before size was computed + assertEquals(1, map.size()); + assertFalse(map.isEmpty()); // after size was computed + assertSame(master, map.values().iterator().next()); + } + + public void testEmpty_WithPrefix() { + final Ref master = newRef("refs/heads/master", ID_ONE); + packed = toList(master); + + RefMap map = new RefMap("refs/tags/", packed, loose, resolved); + assertTrue(map.isEmpty()); // before size was computed + assertEquals(0, map.size()); + assertTrue(map.isEmpty()); // after size was computed + + assertFalse(map.entrySet().iterator().hasNext()); + assertFalse(map.keySet().iterator().hasNext()); + } + + public void testNotEmpty_WithPrefix() { + final Ref master = newRef("refs/heads/master", ID_ONE); + packed = toList(master); + + RefMap map = new RefMap("refs/heads/", packed, loose, resolved); + assertFalse(map.isEmpty()); // before size was computed + assertEquals(1, map.size()); + assertFalse(map.isEmpty()); // after size was computed + assertSame(master, map.values().iterator().next()); + } + + public void testClear() { + final Ref master = newRef("refs/heads/master", ID_ONE); + loose = toList(master); + + RefMap map = new RefMap("", packed, loose, resolved); + assertSame(master, map.get("refs/heads/master")); + + map.clear(); + assertNull(map.get("refs/heads/master")); + assertTrue(map.isEmpty()); + assertEquals(0, map.size()); + } + + public void testIterator_RefusesRemove() { + final Ref master = newRef("refs/heads/master", ID_ONE); + loose = toList(master); + + RefMap map = new RefMap("", packed, loose, resolved); + Iterator<Ref> itr = map.values().iterator(); + assertTrue(itr.hasNext()); + assertSame(master, itr.next()); + try { + itr.remove(); + fail("iterator allowed remove"); + } catch (UnsupportedOperationException err) { + // expected + } + } + + public void testIterator_FailsAtEnd() { + final Ref master = newRef("refs/heads/master", ID_ONE); + loose = toList(master); + + RefMap map = new RefMap("", packed, loose, resolved); + Iterator<Ref> itr = map.values().iterator(); + assertTrue(itr.hasNext()); + assertSame(master, itr.next()); + try { + itr.next(); + fail("iterator allowed next"); + } catch (NoSuchElementException err) { + // expected + } + } + + public void testMerge_PackedLooseLoose() { + final Ref refA = newRef("A", ID_ONE); + final Ref refB_ONE = newRef("B", ID_ONE); + final Ref refB_TWO = newRef("B", ID_TWO); + final Ref refc = newRef("c", ID_ONE); + + packed = toList(refA, refB_ONE); + loose = toList(refB_TWO, refc); + + RefMap map = new RefMap("", packed, loose, resolved); + assertEquals(3, map.size()); + assertFalse(map.isEmpty()); + assertTrue(map.containsKey(refA.getName())); + assertSame(refA, map.get(refA.getName())); + + // loose overrides packed given same name + assertSame(refB_TWO, map.get(refB_ONE.getName())); + + Iterator<Ref> itr = map.values().iterator(); + assertTrue(itr.hasNext()); + assertSame(refA, itr.next()); + assertTrue(itr.hasNext()); + assertSame(refB_TWO, itr.next()); + assertTrue(itr.hasNext()); + assertSame(refc, itr.next()); + assertFalse(itr.hasNext()); + } + + public void testMerge_WithPrefix() { + final Ref a = newRef("refs/heads/A", ID_ONE); + final Ref b = newRef("refs/heads/foo/bar/B", ID_TWO); + final Ref c = newRef("refs/heads/foo/rab/C", ID_TWO); + final Ref g = newRef("refs/heads/g", ID_ONE); + packed = toList(a, b, c, g); + + RefMap map = new RefMap("refs/heads/foo/", packed, loose, resolved); + assertEquals(2, map.size()); + + assertSame(b, map.get("bar/B")); + assertSame(c, map.get("rab/C")); + assertNull(map.get("refs/heads/foo/bar/B")); + assertNull(map.get("refs/heads/A")); + + assertTrue(map.containsKey("bar/B")); + assertTrue(map.containsKey("rab/C")); + assertFalse(map.containsKey("refs/heads/foo/bar/B")); + assertFalse(map.containsKey("refs/heads/A")); + + Iterator<Map.Entry<String, Ref>> itr = map.entrySet().iterator(); + Map.Entry<String, Ref> ent; + assertTrue(itr.hasNext()); + ent = itr.next(); + assertEquals("bar/B", ent.getKey()); + assertSame(b, ent.getValue()); + assertTrue(itr.hasNext()); + ent = itr.next(); + assertEquals("rab/C", ent.getKey()); + assertSame(c, ent.getValue()); + assertFalse(itr.hasNext()); + } + + public void testPut_KeyMustMatchName_NoPrefix() { + final Ref refA = newRef("refs/heads/A", ID_ONE); + RefMap map = new RefMap("", packed, loose, resolved); + try { + map.put("FOO", refA); + fail("map accepted invalid key/value pair"); + } catch (IllegalArgumentException err) { + // expected + } + } + + public void testPut_KeyMustMatchName_WithPrefix() { + final Ref refA = newRef("refs/heads/A", ID_ONE); + RefMap map = new RefMap("refs/heads/", packed, loose, resolved); + try { + map.put("FOO", refA); + fail("map accepted invalid key/value pair"); + } catch (IllegalArgumentException err) { + // expected + } + } + + public void testPut_NoPrefix() { + final Ref refA_one = newRef("refs/heads/A", ID_ONE); + final Ref refA_two = newRef("refs/heads/A", ID_TWO); + + packed = toList(refA_one); + + RefMap map = new RefMap("", packed, loose, resolved); + assertSame(refA_one, map.get(refA_one.getName())); + assertSame(refA_one, map.put(refA_one.getName(), refA_two)); + + // map changed, but packed, loose did not + assertSame(refA_two, map.get(refA_one.getName())); + assertSame(refA_one, packed.get(0)); + assertEquals(0, loose.size()); + + assertSame(refA_two, map.put(refA_one.getName(), refA_one)); + assertSame(refA_one, map.get(refA_one.getName())); + } + + public void testPut_WithPrefix() { + final Ref refA_one = newRef("refs/heads/A", ID_ONE); + final Ref refA_two = newRef("refs/heads/A", ID_TWO); + + packed = toList(refA_one); + + RefMap map = new RefMap("refs/heads/", packed, loose, resolved); + assertSame(refA_one, map.get("A")); + assertSame(refA_one, map.put("A", refA_two)); + + // map changed, but packed, loose did not + assertSame(refA_two, map.get("A")); + assertSame(refA_one, packed.get(0)); + assertEquals(0, loose.size()); + + assertSame(refA_two, map.put("A", refA_one)); + assertSame(refA_one, map.get("A")); + } + + public void testToString_NoPrefix() { + final Ref a = newRef("refs/heads/A", ID_ONE); + final Ref b = newRef("refs/heads/B", ID_TWO); + + packed = toList(a, b); + + StringBuilder exp = new StringBuilder(); + exp.append("["); + exp.append(a.toString()); + exp.append(", "); + exp.append(b.toString()); + exp.append("]"); + + RefMap map = new RefMap("", packed, loose, resolved); + assertEquals(exp.toString(), map.toString()); + } + + public void testToString_WithPrefix() { + final Ref a = newRef("refs/heads/A", ID_ONE); + final Ref b = newRef("refs/heads/foo/B", ID_TWO); + final Ref c = newRef("refs/heads/foo/C", ID_TWO); + final Ref g = newRef("refs/heads/g", ID_ONE); + + packed = toList(a, b, c, g); + + StringBuilder exp = new StringBuilder(); + exp.append("["); + exp.append(b.toString()); + exp.append(", "); + exp.append(c.toString()); + exp.append("]"); + + RefMap map = new RefMap("refs/heads/foo/", packed, loose, resolved); + assertEquals(exp.toString(), map.toString()); + } + + public void testEntryType() { + final Ref a = newRef("refs/heads/A", ID_ONE); + final Ref b = newRef("refs/heads/B", ID_TWO); + + packed = toList(a, b); + + RefMap map = new RefMap("refs/heads/", packed, loose, resolved); + Iterator<Map.Entry<String, Ref>> itr = map.entrySet().iterator(); + Map.Entry<String, Ref> ent_a = itr.next(); + Map.Entry<String, Ref> ent_b = itr.next(); + + assertEquals(ent_a.hashCode(), "A".hashCode()); + assertTrue(ent_a.equals(ent_a)); + assertFalse(ent_a.equals(ent_b)); + + assertEquals(a.toString(), ent_a.toString()); + } + + public void testEntryTypeSet() { + final Ref refA_one = newRef("refs/heads/A", ID_ONE); + final Ref refA_two = newRef("refs/heads/A", ID_TWO); + + packed = toList(refA_one); + + RefMap map = new RefMap("refs/heads/", packed, loose, resolved); + assertSame(refA_one, map.get("A")); + + Map.Entry<String, Ref> ent = map.entrySet().iterator().next(); + assertEquals("A", ent.getKey()); + assertSame(refA_one, ent.getValue()); + + assertSame(refA_one, ent.setValue(refA_two)); + assertSame(refA_two, ent.getValue()); + assertSame(refA_two, map.get("A")); + assertEquals(1, map.size()); + } + + private RefList<Ref> toList(Ref... refs) { + RefList.Builder<Ref> b = new RefList.Builder<Ref>(refs.length); + b.addAll(refs, 0, refs.length); + return b.toRefList(); + } + + private static Ref newRef(String name, ObjectId id) { + return new Ref(Ref.Storage.LOOSE, name, id); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefComparator.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefComparator.java index fe6d210c11..f14488b73e 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefComparator.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefComparator.java @@ -1,6 +1,6 @@ /* * Copyright (C) 2008, Charles O'Farrell <charleso@charleso.org> - * Copyright (C) 2008, Google Inc. + * Copyright (C) 2010, Google Inc. * and other copyright owners as documented in the project's IP log. * * This program and the accompanying materials are made available @@ -61,12 +61,12 @@ public class RefComparator implements Comparator<Ref> { public static final RefComparator INSTANCE = new RefComparator(); public int compare(final Ref o1, final Ref o2) { - return o1.getOrigName().compareTo(o2.getOrigName()); + return compareTo(o1, o2); } /** * Sorts the collection of refs, returning a new collection. - * + * * @param refs * collection to be sorted * @return sorted collection of refs @@ -76,4 +76,30 @@ public class RefComparator implements Comparator<Ref> { Collections.sort(r, INSTANCE); return r; } + + /** + * Compare a reference to a name. + * + * @param o1 + * the reference instance. + * @param o2 + * the name to compare to. + * @return standard Comparator result of < 0, 0, > 0. + */ + public static int compareTo(Ref o1, String o2) { + return o1.getName().compareTo(o2); + } + + /** + * Compare two references by name. + * + * @param o1 + * the reference instance. + * @param o2 + * the other reference instance. + * @return standard Comparator result of < 0, 0, > 0. + */ + public static int compareTo(final Ref o1, final Ref o2) { + return o1.getName().compareTo(o2.getName()); + } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/RefList.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/RefList.java new file mode 100644 index 0000000000..45b065999c --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/RefList.java @@ -0,0 +1,438 @@ +/* + * Copyright (C) 2010, Google Inc. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.eclipse.jgit.util; + +import java.util.Arrays; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; +import java.util.NoSuchElementException; + +import org.eclipse.jgit.lib.Ref; +import org.eclipse.jgit.lib.RefComparator; + +/** + * Specialized variant of an ArrayList to support a {@code RefDatabase}. + * <p> + * This list is a hybrid of a Map<String,Ref> and of a List<Ref>. It + * tracks reference instances by name by keeping them sorted and performing + * binary search to locate an entry. Lookup time is O(log N), but addition and + * removal is O(N + log N) due to the list expansion or contraction costs. + * <p> + * This list type is copy-on-write. Mutation methods return a new copy of the + * list, leaving {@code this} unmodified. As a result we cannot easily implement + * the {@link java.util.List} interface contract. + * + * @param <T> + * the type of reference being stored in the collection. + */ +public class RefList<T extends Ref> implements Iterable<Ref> { + private static final RefList<Ref> EMPTY = new RefList<Ref>(new Ref[0], 0); + + /** + * @return an empty unmodifiable reference list. + * @param <T> + * the type of reference being stored in the collection. + */ + @SuppressWarnings("unchecked") + public static <T extends Ref> RefList<T> emptyList() { + return (RefList<T>) EMPTY; + } + + private final Ref[] list; + + private final int cnt; + + RefList(Ref[] list, int cnt) { + this.list = list; + this.cnt = cnt; + } + + /** + * Initialize this list to use the same backing array as another list. + * + * @param src + * the source list. + */ + protected RefList(RefList<T> src) { + this.list = src.list; + this.cnt = src.cnt; + } + + public Iterator<Ref> iterator() { + return new Iterator<Ref>() { + private int idx; + + public boolean hasNext() { + return idx < cnt; + } + + public Ref next() { + if (idx < cnt) + return list[idx++]; + throw new NoSuchElementException(); + } + + public void remove() { + throw new UnsupportedOperationException(); + } + }; + } + + /** @return this cast as an immutable, standard {@link java.util.List}. */ + public final List<Ref> asList() { + final List<Ref> r = Arrays.asList(list).subList(0, cnt); + return Collections.unmodifiableList(r); + } + + /** @return number of items in this list. */ + public final int size() { + return cnt; + } + + /** @return true if the size of this list is 0. */ + public final boolean isEmpty() { + return cnt == 0; + } + + /** + * Locate an entry by name. + * + * @param name + * the name of the reference to find. + * @return the index the reference is at. If the entry is not present + * returns a negative value. The insertion position for the given + * name can be computed from {@code -(index + 1)}. + */ + public final int find(String name) { + int high = cnt; + if (high == 0) + return -1; + int low = 0; + do { + final int mid = (low + high) >>> 1; + final int cmp = RefComparator.compareTo(list[mid], name); + if (cmp < 0) + low = mid + 1; + else if (cmp == 0) + return mid; + else + high = mid; + } while (low < high); + return -(low + 1); + } + + /** + * Determine if a reference is present. + * + * @param name + * name of the reference to find. + * @return true if the reference is present; false if it is not. + */ + public final boolean contains(String name) { + return 0 <= find(name); + } + + /** + * Get a reference object by name. + * + * @param name + * the name of the reference. + * @return the reference object; null if it does not exist in this list. + */ + public final T get(String name) { + int idx = find(name); + return 0 <= idx ? get(idx) : null; + } + + /** + * Get the reference at a particular index. + * + * @param idx + * the index to obtain. Must be {@code 0 <= idx < size()}. + * @return the reference value, never null. + */ + @SuppressWarnings("unchecked") + public final T get(int idx) { + return (T) list[idx]; + } + + /** + * Obtain a builder initialized with the first {@code n} elements. + * <p> + * Copies the first {@code n} elements from this list into a new builder, + * which can be used by the caller to add additional elements. + * + * @param n + * the number of elements to copy. + * @return a new builder with the first {@code n} elements already added. + */ + public final Builder<T> copy(int n) { + Builder<T> r = new Builder<T>(Math.max(16, n)); + r.addAll(list, 0, n); + return r; + } + + /** + * Obtain a new copy of the list after changing one element. + * <p> + * This list instance is not affected by the replacement. Because this + * method copies the entire list, it runs in O(N) time. + * + * @param idx + * index of the element to change. + * @param ref + * the new value, must not be null. + * @return copy of this list, after replacing {@code idx} with {@code ref} . + */ + public final RefList<T> set(int idx, T ref) { + Ref[] newList = new Ref[cnt]; + System.arraycopy(list, 0, newList, 0, cnt); + newList[idx] = ref; + return new RefList<T>(newList, cnt); + } + + /** + * Add an item at a specific index. + * <p> + * This list instance is not affected by the addition. Because this method + * copies the entire list, it runs in O(N) time. + * + * @param idx + * position to add the item at. If negative the method assumes it + * was a direct return value from {@link #find(String)} and will + * adjust it to the correct position. + * @param ref + * the new reference to insert. + * @return copy of this list, after making space for and adding {@code ref}. + */ + public final RefList<T> add(int idx, T ref) { + if (idx < 0) + idx = -(idx + 1); + + Ref[] newList = new Ref[cnt + 1]; + if (0 < idx) + System.arraycopy(list, 0, newList, 0, idx); + newList[idx] = ref; + if (idx < cnt) + System.arraycopy(list, idx, newList, idx + 1, cnt - idx); + return new RefList<T>(newList, cnt + 1); + } + + /** + * Remove an item at a specific index. + * <p> + * This list instance is not affected by the addition. Because this method + * copies the entire list, it runs in O(N) time. + * + * @param idx + * position to remove the item from. + * @return copy of this list, after making removing the item at {@code idx}. + */ + public final RefList<T> remove(int idx) { + if (cnt == 1) + return emptyList(); + Ref[] newList = new Ref[cnt - 1]; + if (0 < idx) + System.arraycopy(list, 0, newList, 0, idx); + if (idx + 1 < cnt) + System.arraycopy(list, idx + 1, newList, idx, cnt - (idx + 1)); + return new RefList<T>(newList, cnt - 1); + } + + /** + * Store a reference, adding or replacing as necessary. + * <p> + * This list instance is not affected by the store. The correct position is + * determined, and the item is added if missing, or replaced if existing. + * Because this method copies the entire list, it runs in O(N + log N) time. + * + * @param ref + * the reference to store. + * @return copy of this list, after performing the addition or replacement. + */ + public final RefList<T> put(T ref) { + int idx = find(ref.getName()); + if (0 <= idx) + return set(idx, ref); + return add(idx, ref); + } + + @Override + public String toString() { + StringBuilder r = new StringBuilder(); + r.append('['); + if (cnt > 0) { + r.append(list[0]); + for (int i = 1; i < cnt; i++) { + r.append(", "); + r.append(list[i]); + } + } + r.append(']'); + return r.toString(); + } + + /** + * Builder to facilitate fast construction of an immutable RefList. + * + * @param <T> + * type of reference being stored. + */ + public static class Builder<T extends Ref> { + private Ref[] list; + + private int size; + + /** Create an empty list ready for items to be added. */ + public Builder() { + this(16); + } + + /** + * Create an empty list with at least the specified capacity. + * + * @param capacity + * the new capacity. + */ + public Builder(int capacity) { + list = new Ref[capacity]; + } + + /** @return number of items in this builder's internal collection. */ + public int size() { + return size; + } + + /** + * Get the reference at a particular index. + * + * @param idx + * the index to obtain. Must be {@code 0 <= idx < size()}. + * @return the reference value, never null. + */ + @SuppressWarnings("unchecked") + public T get(int idx) { + return (T) list[idx]; + } + + /** + * Remove an item at a specific index. + * + * @param idx + * position to remove the item from. + */ + public void remove(int idx) { + System.arraycopy(list, idx + 1, list, idx, size - (idx + 1)); + size--; + } + + /** + * Add the reference to the end of the array. + * <p> + * References must be added in sort order, or the array must be sorted + * after additions are complete using {@link #sort()}. + * + * @param ref + */ + public void add(T ref) { + if (list.length == size) { + Ref[] n = new Ref[size * 2]; + System.arraycopy(list, 0, n, 0, size); + list = n; + } + list[size++] = ref; + } + + /** + * Add all items from a source array. + * <p> + * References must be added in sort order, or the array must be sorted + * after additions are complete using {@link #sort()}. + * + * @param src + * the source array. + * @param off + * position within {@code src} to start copying from. + * @param cnt + * number of items to copy from {@code src}. + */ + public void addAll(Ref[] src, int off, int cnt) { + if (list.length < size + cnt) { + Ref[] n = new Ref[Math.max(size * 2, size + cnt)]; + System.arraycopy(list, 0, n, 0, size); + list = n; + } + System.arraycopy(src, off, list, size, cnt); + size += cnt; + } + + /** + * Replace a single existing element. + * + * @param idx + * index, must have already been added previously. + * @param ref + * the new reference. + */ + public void set(int idx, T ref) { + list[idx] = ref; + } + + /** Sort the list's backing array in-place. */ + public void sort() { + Arrays.sort(list, 0, size, RefComparator.INSTANCE); + } + + /** @return an unmodifiable list using this collection's backing array. */ + public RefList<T> toRefList() { + return new RefList<T>(list, size); + } + + @Override + public String toString() { + return toRefList().toString(); + } + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/RefMap.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/RefMap.java new file mode 100644 index 0000000000..8a21cff73b --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/RefMap.java @@ -0,0 +1,423 @@ +/* + * Copyright (C) 2010, Google Inc. + * and other copyright owners as documented in the project's IP log. + * + * This program and the accompanying materials are made available + * under the terms of the Eclipse Distribution License v1.0 which + * accompanies this distribution, is reproduced below, and is + * available at http://www.eclipse.org/org/documents/edl-v10.php + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Eclipse Foundation, Inc. nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.eclipse.jgit.util; + +import java.util.AbstractMap; +import java.util.AbstractSet; +import java.util.Iterator; +import java.util.Map; +import java.util.NoSuchElementException; +import java.util.Set; + +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.Ref; +import org.eclipse.jgit.lib.RefComparator; + +/** + * Specialized Map to present a {@code RefDatabase} namespace. + * <p> + * Although not declared as a {@link java.util.SortedMap}, iterators from this + * map's projections always return references in {@link RefComparator} ordering. + * The map's internal representation is a sorted array of {@link Ref} objects, + * which means lookup and replacement is O(log N), while insertion and removal + * can be as expensive as O(N + log N) while the list expands or contracts. + * Since this is not a general map implementation, all entries must be keyed by + * the reference name. + * <p> + * This class is really intended as a helper for {@code RefDatabase}, which + * needs to perform a merge-join of three sorted {@link RefList}s in order to + * present the unified namespace of the packed-refs file, the loose refs/ + * directory tree, and the resolved form of any symbolic references. + */ +public class RefMap extends AbstractMap<String, Ref> { + /** + * Prefix denoting the reference subspace this map contains. + * <p> + * All reference names in this map must start with this prefix. If the + * prefix is not the empty string, it must end with a '/'. + */ + private final String prefix; + + /** Immutable collection of the packed references at construction time. */ + private RefList<Ref> packed; + + /** + * Immutable collection of the loose references at construction time. + * <p> + * If an entry appears here and in {@link #packed}, this entry must take + * precedence, as its more current. Symbolic references in this collection + * are typically unresolved, so they only tell us who their target is, but + * not the current value of the target. + */ + private RefList<Ref> loose; + + /** + * Immutable collection of resolved symbolic references. + * <p> + * This collection contains only the symbolic references we were able to + * resolve at map construction time. Other loose references must be read + * from {@link #loose}. Every entry in this list must be matched by an entry + * in {@code loose}, otherwise it might be omitted by the map. + */ + private RefList<Ref> resolved; + + private int size; + + private boolean sizeIsValid; + + private Set<Entry<String, Ref>> entrySet; + + /** Construct an empty map with a small initial capacity. */ + public RefMap() { + prefix = ""; + packed = RefList.emptyList(); + loose = RefList.emptyList(); + resolved = RefList.emptyList(); + } + + /** + * Construct a map to merge 3 collections together. + * + * @param prefix + * prefix used to slice the lists down. Only references whose + * names start with this prefix will appear to reside in the map. + * Must not be null, use {@code ""} (the empty string) to select + * all list items. + * @param packed + * items from the packed reference list, this is the last list + * searched. + * @param loose + * items from the loose reference list, this list overrides + * {@code packed} if a name appears in both. + * @param resolved + * resolved symbolic references. This list overrides the prior + * list {@code loose}, if an item appears in both. Items in this + * list <b>must</b> also appear in {@code loose}. + */ + public RefMap(String prefix, RefList<Ref> packed, RefList<Ref> loose, + RefList<Ref> resolved) { + this.prefix = prefix; + this.packed = packed; + this.loose = loose; + this.resolved = resolved; + } + + @Override + public boolean containsKey(Object name) { + return get(name) != null; + } + + @Override + public Ref get(Object key) { + String name = toRefName((String) key); + Ref ref = resolved.get(name); + if (ref == null) + ref = loose.get(name); + if (ref == null) + ref = packed.get(name); + return ref; + } + + @Override + public Ref put(final String keyName, Ref value) { + String name = toRefName(keyName); + + if (!name.equals(value.getName())) + throw new IllegalArgumentException(); + + if (!resolved.isEmpty()) { + // Collapse the resolved list into the loose list so we + // can discard it and stop joining the two together. + for (Ref ref : resolved) + loose = loose.put(ref); + resolved = RefList.emptyList(); + } + + int idx = loose.find(name); + if (0 <= idx) { + Ref prior = loose.get(name); + loose = loose.set(idx, value); + return prior; + } else { + Ref prior = get(keyName); + loose = loose.add(idx, value); + sizeIsValid = false; + return prior; + } + } + + @Override + public Ref remove(Object key) { + String name = toRefName((String) key); + Ref res = null; + int idx; + if (0 <= (idx = packed.find(name))) { + res = packed.get(name); + packed = packed.remove(idx); + sizeIsValid = false; + } + if (0 <= (idx = loose.find(name))) { + res = loose.get(name); + loose = loose.remove(idx); + sizeIsValid = false; + } + if (0 <= (idx = resolved.find(name))) { + res = resolved.get(name); + resolved = resolved.remove(idx); + sizeIsValid = false; + } + return res; + } + + @Override + public boolean isEmpty() { + return entrySet().isEmpty(); + } + + @Override + public Set<Entry<String, Ref>> entrySet() { + if (entrySet == null) { + entrySet = new AbstractSet<Entry<String, Ref>>() { + @Override + public Iterator<Entry<String, Ref>> iterator() { + return new SetIterator(); + } + + @Override + public int size() { + if (!sizeIsValid) { + size = 0; + Iterator<?> i = entrySet().iterator(); + for (; i.hasNext(); i.next()) + size++; + sizeIsValid = true; + } + return size; + } + + @Override + public boolean isEmpty() { + if (sizeIsValid) + return 0 == size; + return !iterator().hasNext(); + } + + @Override + public void clear() { + packed = RefList.emptyList(); + loose = RefList.emptyList(); + resolved = RefList.emptyList(); + size = 0; + sizeIsValid = true; + } + }; + } + return entrySet; + } + + @Override + public String toString() { + StringBuilder r = new StringBuilder(); + boolean first = true; + r.append('['); + for (Ref ref : values()) { + if (first) + first = false; + else + r.append(", "); + r.append(ref); + } + r.append(']'); + return r.toString(); + } + + private String toRefName(String name) { + if (0 < prefix.length()) + name = prefix + name; + return name; + } + + private String toMapKey(Ref ref) { + String name = ref.getName(); + if (0 < prefix.length()) + name = name.substring(prefix.length()); + return name; + } + + private class SetIterator implements Iterator<Entry<String, Ref>> { + private int packedIdx; + + private int looseIdx; + + private int resolvedIdx; + + private Entry<String, Ref> next; + + SetIterator() { + if (0 < prefix.length()) { + packedIdx = -(packed.find(prefix) + 1); + looseIdx = -(loose.find(prefix) + 1); + resolvedIdx = -(resolved.find(prefix) + 1); + } + } + + public boolean hasNext() { + if (next == null) + next = peek(); + return next != null; + } + + public Entry<String, Ref> next() { + if (hasNext()) { + Entry<String, Ref> r = next; + next = peek(); + return r; + } + throw new NoSuchElementException(); + } + + public Entry<String, Ref> peek() { + if (packedIdx < packed.size() && looseIdx < loose.size()) { + Ref p = packed.get(packedIdx); + Ref l = loose.get(looseIdx); + int cmp = RefComparator.compareTo(p, l); + if (cmp < 0) { + packedIdx++; + return toEntry(p); + } + + if (cmp == 0) + packedIdx++; + looseIdx++; + return toEntry(resolveLoose(l)); + } + + if (looseIdx < loose.size()) + return toEntry(resolveLoose(loose.get(looseIdx++))); + if (packedIdx < packed.size()) + return toEntry(packed.get(packedIdx++)); + return null; + } + + private Ref resolveLoose(final Ref l) { + if (resolvedIdx < resolved.size()) { + Ref r = resolved.get(resolvedIdx); + int cmp = RefComparator.compareTo(l, r); + if (cmp == 0) { + resolvedIdx++; + return r; + } else if (cmp > 0) { + // WTF, we have a symbolic entry but no match + // in the loose collection. That's an error. + throw new IllegalStateException(); + } + } + return l; + } + + private Ent toEntry(Ref p) { + if (p.getName().startsWith(prefix)) + return new Ent(p); + packedIdx = packed.size(); + looseIdx = loose.size(); + resolvedIdx = resolved.size(); + return null; + } + + public void remove() { + throw new UnsupportedOperationException(); + } + } + + private class Ent implements Entry<String, Ref> { + private Ref ref; + + Ent(Ref ref) { + this.ref = ref; + } + + public String getKey() { + return toMapKey(ref); + } + + public Ref getValue() { + return ref; + } + + public Ref setValue(Ref value) { + Ref prior = put(getKey(), value); + ref = value; + return prior; + } + + @Override + public int hashCode() { + return getKey().hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (obj instanceof Map.Entry) { + final Object key = ((Map.Entry) obj).getKey(); + final Object val = ((Map.Entry) obj).getValue(); + if (key instanceof String && val instanceof Ref) { + final Ref r = (Ref) val; + if (r.getName().equals(ref.getName())) { + final ObjectId a = r.getObjectId(); + final ObjectId b = ref.getObjectId(); + if (a != null && b != null && AnyObjectId.equals(a, b)) + return true; + } + } + } + return false; + } + + @Override + public String toString() { + return ref.toString(); + } + } +} |