From mboxrd@z Thu Jan 1 00:00:00 1970 From: "Shawn O. Pearce" Subject: [JGIT PATCH 13/13] Remove ObjectIdMap from the JGit library Date: Tue, 28 Apr 2009 14:12:26 -0700 Message-ID: <1240953146-12878-14-git-send-email-spearce@spearce.org> References: <1240953146-12878-1-git-send-email-spearce@spearce.org> <1240953146-12878-2-git-send-email-spearce@spearce.org> <1240953146-12878-3-git-send-email-spearce@spearce.org> <1240953146-12878-4-git-send-email-spearce@spearce.org> <1240953146-12878-5-git-send-email-spearce@spearce.org> <1240953146-12878-6-git-send-email-spearce@spearce.org> <1240953146-12878-7-git-send-email-spearce@spearce.org> <1240953146-12878-8-git-send-email-spearce@spearce.org> <1240953146-12878-9-git-send-email-spearce@spearce.org> <1240953146-12878-10-git-send-email-spearce@spearce.org> <1240953146-12878-11-git-send-email-spearce@spearce.org> <1240953146-12878-12-git-send-email-spearce@spearce.org> <1240953146-12878-13-git-send-email-spearce@spearce.org> Cc: git@vger.kernel.org To: Robin Rosenberg X-From: git-owner@vger.kernel.org Tue Apr 28 23:16:04 2009 Return-path: Envelope-to: gcvg-git-2@gmane.org Received: from vger.kernel.org ([209.132.176.167]) by lo.gmane.org with esmtp (Exim 4.50) id 1LyueU-0006Nh-DY for gcvg-git-2@gmane.org; Tue, 28 Apr 2009 23:15:42 +0200 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758035AbZD1VNK (ORCPT ); Tue, 28 Apr 2009 17:13:10 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1756940AbZD1VNF (ORCPT ); Tue, 28 Apr 2009 17:13:05 -0400 Received: from george.spearce.org ([209.20.77.23]:58325 "EHLO george.spearce.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752254AbZD1VMi (ORCPT ); Tue, 28 Apr 2009 17:12:38 -0400 Received: by george.spearce.org (Postfix, from userid 1000) id 71EC838260; Tue, 28 Apr 2009 21:12:38 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.2.4 (2008-01-01) on george.spearce.org X-Spam-Level: X-Spam-Status: No, score=-3.5 required=4.0 tests=ALL_TRUSTED,AWL,BAYES_00, FRT_LEVITRA autolearn=no version=3.2.4 Received: from localhost.localdomain (localhost [127.0.0.1]) by george.spearce.org (Postfix) with ESMTP id 1F16338268; Tue, 28 Apr 2009 21:12:31 +0000 (UTC) X-Mailer: git-send-email 1.6.3.rc1.205.g37f8 In-Reply-To: <1240953146-12878-13-git-send-email-spearce@spearce.org> Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Archived-At: 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 --- .../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.rc1.205.g37f8