org.spearce.jgit/src/org/spearce/jgit/lib/ObjectIdMap.java

   1 /*
   2  *  Copyright (C) 2006  Robin Rosenberg <robin.rosenberg@dewire.com>
   3  *
   4  *  This library is free software; you can redistribute it and/or
   5  *  modify it under the terms of the GNU General Public
   6  *  License, version 2, as published by the Free Software Foundation.
   7  *
   8  *  This library is distributed in the hope that it will be useful,
   9  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  *  General Public License for more details.
  12  *
  13  *  You should have received a copy of the GNU General Public
  14  *  License along with this library; if not, write to the Free Software
  15  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301
  16  */
  17 package org.spearce.jgit.lib;
  18
  19 import java.lang.reflect.InvocationTargetException;
  20 import java.lang.reflect.Method;
  21 import java.util.AbstractMap;
  22 import java.util.ArrayList;
  23 import java.util.Collection;
  24 import java.util.HashSet;
  25 import java.util.List;
  26 import java.util.Map;
  27 import java.util.Set;
  28 import java.util.TreeMap;
  29
  30 /**
  31  * Very much like a map, but specialized to partition the data on the first byte
  32  * of the key. This is about twice as fast. See test class.
  33  *
  34  * Inspiration is taken from the Git pack file format which uses this technique
  35  * to improve lookup performance.
  36  *
  37  * @param <V>
  38  *            The value we map ObjectId's to.
  39  *
  40  */
  41 public class ObjectIdMap<V> extends AbstractMap<ObjectId, V> {
  42
  43         @SuppressWarnings("unchecked")
  44         private Map<ObjectId, V>[] level0 = new Map[256];
  45
  46         /**
  47          * Construct an ObjectIdMap with an underlying TreeMap implementation
  48          */
  49         public ObjectIdMap() {
  50                 this(new TreeMap());
  51         }
  52
  53         /**
  54          * Construct an ObjectIdMap with the same underlying map implementation as
  55          * the provided example.
  56          *
  57          * @param sample
  58          */
  59         @SuppressWarnings("unchecked")
  60         public ObjectIdMap(Map sample) {
  61                 try {
  62                         Method m=sample.getClass().getMethod("clone", (Class[])null);
  63                         for (int i=0; i<256; ++i) {
  64                                 level0[i] = (Map)m.invoke(sample, (Object[])null);
  65                         }
  66                 } catch (IllegalAccessException e) {
  67                         throw new IllegalArgumentException(e);
  68                 } catch (IllegalArgumentException e) {
  69                         throw new IllegalArgumentException(e);
  70                 } catch (InvocationTargetException e) {
  71                         throw new IllegalArgumentException(e);
  72                 } catch (SecurityException e) {
  73                         throw new IllegalArgumentException(e);
  74                 } catch (NoSuchMethodException e) {
  75                         throw new IllegalArgumentException(e);
  76                 }
  77         }
  78
  79         public void clear() {
  80                 for (int i=0; i<256; ++i)
  81                         level0[i].clear();
  82         }
  83
  84         public boolean containsKey(Object key) {
  85                 return submap((ObjectId)key).containsKey(key);
  86         }
  87
  88         private final Map<ObjectId, V> submap(ObjectId key) {
  89                 return level0[key.getFirstByte()];
  90         }
  91
  92         public boolean containsValue(Object value) {
  93                 for (int i=0; i<256; ++i)
  94                         if (level0[i].containsValue(value))
  95                                 return true;
  96                 return false;
  97         }
  98
  99         public Set<Map.Entry<ObjectId, V>> entrySet() {
 100                 Set<Map.Entry<ObjectId, V>> ret = new HashSet<Map.Entry<ObjectId, V>>();
 101                 for (int i=0; i<256; ++i)
 102                         ret.addAll(level0[i].entrySet());
 103                 return ret;
 104         }
 105
 106         public V get(Object key) {
 107                 return submap((ObjectId)key).get(key);
 108         }
 109
 110         public boolean isEmpty() {
 111                 for (int i=0; i<256; ++i)
 112                         if (!level0[i].isEmpty())
 113                                 return false;
 114                 return true;
 115         }
 116
 117         public Set<ObjectId> keySet() {
 118                 Set<ObjectId> ret = new HashSet<ObjectId>();
 119                 for (int i=0; i<256; ++i)
 120                         ret.addAll(level0[i].keySet());
 121                 return ret;
 122         }
 123
 124         @SuppressWarnings("unchecked")
 125         public V put(ObjectId key, V value) {
 126                 return submap(key).put(key, value);
 127         }
 128
 129         public void putAll(Map<? extends ObjectId, ? extends V> arg0) {
 130                 for (ObjectId k : arg0.keySet()) {
 131                         V v=arg0.get(k);
 132                         put(k,v);
 133                 }
 134         }
 135
 136         public V remove(Object key) {
 137                 return submap((ObjectId) key).remove(key);
 138         }
 139
 140         public int size() {
 141                 int ret=0;
 142                 for (int i=0; i<256; ++i)
 143                         ret += level0[i].size();
 144                 return ret;
 145         }
 146
 147         public Collection<V> values() {
 148                 List<V> ret=new ArrayList<V>(size());
 149                 for (int i=0; i<256; ++i)
 150                         ret.addAll(level0[i].values());
 151                 return ret;
 152         }
 153
 154 }