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.AbstractSet;
  23 import java.util.Iterator;
  24 import java.util.Map;
  25 import java.util.Set;
  26 import java.util.TreeMap;
  27
  28 /**
  29  * Very much like a map, but specialized to partition the data on the first byte
  30  * of the key. This is about twice as fast. See test class.
  31  *
  32  * Inspiration is taken from the Git pack file format which uses this technique
  33  * to improve lookup performance.
  34  *
  35  * @param <V>
  36  *            The value we map ObjectId's to.
  37  *
  38  */
  39 public class ObjectIdMap<V> extends AbstractMap<ObjectId, V> {
  40
  41         @SuppressWarnings("unchecked")
  42         final Map<ObjectId, V>[] level0 = new Map[256];
  43
  44         /**
  45          * Construct an ObjectIdMap with an underlying TreeMap implementation
  46          */
  47         public ObjectIdMap() {
  48                 this(new TreeMap());
  49         }
  50
  51         /**
  52          * Construct an ObjectIdMap with the same underlying map implementation as
  53          * the provided example.
  54          *
  55          * @param sample
  56          */
  57         @SuppressWarnings("unchecked")
  58         public ObjectIdMap(Map sample) {
  59                 try {
  60                         Method m=sample.getClass().getMethod("clone", (Class[])null);
  61                         for (int i=0; i<256; ++i) {
  62                                 level0[i] = (Map)m.invoke(sample, (Object[])null);
  63                         }
  64                 } catch (IllegalAccessException e) {
  65                         throw new IllegalArgumentException(e);
  66                 } catch (IllegalArgumentException e) {
  67                         throw new IllegalArgumentException(e);
  68                 } catch (InvocationTargetException e) {
  69                         throw new IllegalArgumentException(e);
  70                 } catch (SecurityException e) {
  71                         throw new IllegalArgumentException(e);
  72                 } catch (NoSuchMethodException e) {
  73                         throw new IllegalArgumentException(e);
  74                 }
  75         }
  76
  77         public void clear() {
  78                 for (int i=0; i<256; ++i)
  79                         level0[i].clear();
  80         }
  81
  82         public boolean containsKey(Object key) {
  83                 return submap((ObjectId)key).containsKey(key);
  84         }
  85
  86         private final Map<ObjectId, V> submap(ObjectId key) {
  87                 return level0[key.getFirstByte()];
  88         }
  89
  90         public boolean containsValue(Object value) {
  91                 for (int i=0; i<256; ++i)
  92                         if (level0[i].containsValue(value))
  93                                 return true;
  94                 return false;
  95         }
  96
  97         private Set<Map.Entry<ObjectId, V>> entrySet =
  98                 new AbstractSet<Map.Entry<ObjectId, V>>() {
  99
 100                         @Override
 101                         final public Iterator<Map.Entry<ObjectId, V>> iterator() {
 102                                 return new Iterator<Entry<ObjectId,V>>() {
 103                                         private int levelIndex;
 104                                         private boolean hasNext;
 105                                         private Iterator<Map.Entry<ObjectId, V>> levelIterator;
 106                                         private Iterator<Map.Entry<ObjectId, V>> lastIterator;
 107                                         {
 108                                                 step();
 109                                         }
 110                                         public boolean hasNext() {
 111                                                 return hasNext;
 112                                         }
 113                                         public java.util.Map.Entry<ObjectId, V> next() {
 114                                                 Entry<ObjectId, V> ret = levelIterator.next();
 115                                                 step();
 116                                                 return ret;
 117                                         }
 118                                         public void remove() {
 119                                                 lastIterator.remove();
 120                                         }
 121
 122                                         private void step() {
 123                                                 hasNext = false;
 124                                                 lastIterator = levelIterator;
 125                                                 while ((levelIterator==null || !(hasNext=levelIterator.hasNext()))) {
 126                                                         if (levelIndex < level0.length)
 127                                                                 levelIterator = level0[levelIndex++].entrySet().iterator();
 128                                                         else
 129                                                                 break;
 130                                                 }
 131                                         }
 132                                 };
 133                         }
 134
 135                         @Override
 136                         public int size() {
 137                                 int ret=0;
 138                                 for (int i=0; i<256; ++i)
 139                                         ret += level0[i].size();
 140                                 return ret;
 141                         }
 142         };
 143
 144
 145         public Set<Map.Entry<ObjectId, V>> entrySet() {
 146                 return entrySet;
 147         }
 148
 149         public V get(Object key) {
 150                 return submap((ObjectId)key).get(key);
 151         }
 152
 153         public boolean isEmpty() {
 154                 for (int i=0; i<256; ++i)
 155                         if (!level0[i].isEmpty())
 156                                 return false;
 157                 return true;
 158         }
 159
 160         @SuppressWarnings("unchecked")
 161         public V put(ObjectId key, V value) {
 162                 return submap(key).put(key, value);
 163         }
 164
 165         public void putAll(Map<? extends ObjectId, ? extends V> arg0) {
 166                 for (ObjectId k : arg0.keySet()) {
 167                         V v=arg0.get(k);
 168                         put(k,v);
 169                 }
 170         }
 171
 172         public V remove(Object key) {
 173                 return submap((ObjectId) key).remove(key);
 174         }
 175
 176         public int size() {
 177                 return entrySet().size();
 178         }
 179
 180 }