From: Shawn O. Pearce Date: Wed, 29 Apr 2009 18:54:44 GMT Subject: [JGIT PATCH 07/11] Remove ObjectIdMap from the JGit library Message-ID: <1241031288-23437-8-git-send-email-spearce@spearce.org> In-Reply-To: <1241031288-23437-7-git-send-email-spearce@spearce.org> Nobody within the library uses it anymore. Applications should consider ObjectIdSubclassMap, or just use a normal JDK map type like HashMap or TreeMap. In general ObjectIdSubclassMap supports major map functionality, runs faster, and uses less memory for the same sized data set. Signed-off-by: Shawn O. Pearce --- Unchanged. .../tst/org/spearce/jgit/lib/ObjectIdMapTest.java | 103 ---------- .../src/org/spearce/jgit/lib/ObjectIdMap.java | 201 -------------------- 2 files changed, 0 insertions(+), 304 deletions(-) delete mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/ObjectIdMapTest.java delete mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/ObjectIdMap.java diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ObjectIdMapTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ObjectIdMapTest.java deleted file mode 100644 index f1c1c0c..0000000 --- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/ObjectIdMapTest.java +++ /dev/null @@ -1,103 +0,0 @@ -/* - * Copyright (C) 2008, Robin Rosenberg - * - * 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 Git Development Community 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.spearce.jgit.lib; - -import java.util.Arrays; -import java.util.Collection; -import java.util.Map; -import java.util.TreeMap; - -import junit.framework.TestCase; - -/** - * Test functionality of ObjectIdMap - * - * The reason this class exists is performance, but those figures - * are hard to make stable. - */ -public class ObjectIdMapTest extends TestCase { - - ObjectId[] ids = new ObjectId[500]; - - protected void setUp() throws Exception { - int b=0; - for (int i=0; i - * - * 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 Git Development Community 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.spearce.jgit.lib; - -import java.lang.reflect.InvocationTargetException; -import java.lang.reflect.Method; -import java.util.AbstractMap; -import java.util.AbstractSet; -import java.util.Iterator; -import java.util.Map; -import java.util.Set; -import java.util.TreeMap; - -/** - * Very much like a map, but specialized to partition the data on the first byte - * of the key. This is about twice as fast. See test class. - * - * Inspiration is taken from the Git pack file format which uses this technique - * to improve lookup performance. - * - * @param - * The value we map ObjectId's to. - * - */ -public class ObjectIdMap extends AbstractMap { - - @SuppressWarnings("unchecked") - final Map[] level0 = new Map[256]; - - /** - * Construct an ObjectIdMap with an underlying TreeMap implementation - */ - public ObjectIdMap() { - this(new TreeMap()); - } - - /** - * Construct an ObjectIdMap with the same underlying map implementation as - * the provided example. - * - * @param sample - */ - @SuppressWarnings("unchecked") - public ObjectIdMap(Map sample) { - try { - Method m=sample.getClass().getMethod("clone", (Class[])null); - for (int i=0; i<256; ++i) { - level0[i] = (Map)m.invoke(sample, (Object[])null); - } - } catch (IllegalAccessException e) { - throw new IllegalArgumentException(e); - } catch (IllegalArgumentException e) { - throw new IllegalArgumentException(e); - } catch (InvocationTargetException e) { - throw new IllegalArgumentException(e); - } catch (SecurityException e) { - throw new IllegalArgumentException(e); - } catch (NoSuchMethodException e) { - throw new IllegalArgumentException(e); - } - } - - public void clear() { - for (int i=0; i<256; ++i) - level0[i].clear(); - } - - public boolean containsKey(Object key) { - return submap((ObjectId)key).containsKey(key); - } - - private final Map submap(ObjectId key) { - return level0[key.getFirstByte()]; - } - - public boolean containsValue(Object value) { - for (int i=0; i<256; ++i) - if (level0[i].containsValue(value)) - return true; - return false; - } - - private Set> entrySet = - new AbstractSet>() { - - @Override - final public Iterator> iterator() { - return new Iterator>() { - private int levelIndex; - private boolean hasNext; - private Iterator> levelIterator; - private Iterator> lastIterator; - { - step(); - } - public boolean hasNext() { - return hasNext; - } - public java.util.Map.Entry next() { - Entry ret = levelIterator.next(); - step(); - return ret; - } - public void remove() { - lastIterator.remove(); - } - - private void step() { - hasNext = false; - lastIterator = levelIterator; - while ((levelIterator==null || !(hasNext=levelIterator.hasNext()))) { - if (levelIndex < level0.length) - levelIterator = level0[levelIndex++].entrySet().iterator(); - else - break; - } - } - }; - } - - @Override - public int size() { - int ret=0; - for (int i=0; i<256; ++i) - ret += level0[i].size(); - return ret; - } - }; - - - public Set> entrySet() { - return entrySet; - } - - public V get(Object key) { - return submap((ObjectId)key).get(key); - } - - public boolean isEmpty() { - for (int i=0; i<256; ++i) - if (!level0[i].isEmpty()) - return false; - return true; - } - - public V put(ObjectId key, V value) { - return submap(key).put(key, value); - } - - public void putAll(Map arg0) { - for (Map.Entry entry : arg0.entrySet()) { - final ObjectId k = entry.getKey(); - final V v = entry.getValue(); - put(k,v); - } - } - - public V remove(Object key) { - return submap((ObjectId) key).remove(key); - } - - public int size() { - return entrySet().size(); - } - -} -- 1.6.3.rc3.199.g24398