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.ArrayList;
  22 import java.util.Collection;
  23 import java.util.HashSet;
  24 import java.util.Iterator;
  25 import java.util.List;
  26 import java.util.Map;
  27 import java.util.Set;
  28 import java.util.TreeMap;
  29
  30 /** Very much like a map, but specialized
  31  *  to partition the data on the first byte
  32  *  of the key. This is MUCH faster. See test
  33  *  class for how these numbers were derived.
  34  *
  35  *      TreeMap=            2968
  36  *      HashMap=            1689
  37  *      Partitioned TreeMap=1499
  38  *      Partitioned HashMap=1782
  39  *
  40  *  Inspiration from Git pack file format which uses this technique.
  41  *
  42  */
  43 public class ObjectIdMap implements Map {
  44
  45         Map[] level0 = new Map[256];
  46
  47         public ObjectIdMap() {
  48                 this(new TreeMap());
  49         }
  50
  51         public ObjectIdMap(Map sample) {
  52                 try {
  53                         Method m=sample.getClass().getMethod("clone", null);
  54                         for (int i=0; i<256; ++i) {
  55                                 level0[i] = (Map)m.invoke(sample, null);
  56                         }
  57                 } catch (IllegalAccessException e) {
  58                         throw new IllegalArgumentException(e);
  59                 } catch (IllegalArgumentException e) {
  60                         throw new IllegalArgumentException(e);
  61                 } catch (InvocationTargetException e) {
  62                         throw new IllegalArgumentException(e);
  63                 } catch (SecurityException e) {
  64                         throw new IllegalArgumentException(e);
  65                 } catch (NoSuchMethodException e) {
  66                         throw new IllegalArgumentException(e);
  67                 }
  68         }
  69
  70         public void clear() {
  71                 for (int i=0; i<256; ++i)
  72                         level0[i].clear();
  73         }
  74
  75         public boolean containsKey(Object key) {
  76                 return submap(key).containsKey(key);
  77         }
  78
  79         private final Map submap(Object key) {
  80                 return level0[((ObjectId)key).getFirstByte()];
  81         }
  82
  83         public boolean containsValue(Object value) {
  84                 for (int i=0; i<256; ++i)
  85                         if (level0[i].containsValue(value))
  86                                 return true;
  87                 return false;
  88         }
  89
  90         public Set entrySet() {
  91                 Set ret = new HashSet();
  92                 for (int i=0; i<256; ++i)
  93                         ret.addAll(level0[i].entrySet());
  94                 return ret;
  95         }
  96
  97         public Object get(Object key) {
  98                 return submap(key).get(key);
  99         }
 100
 101         public boolean isEmpty() {
 102                 for (int i=0; i<256; ++i)
 103                         if (!level0[i].isEmpty())
 104                                 return false;
 105                 return true;
 106         }
 107
 108         public Set keySet() {
 109                 Set ret = new HashSet();
 110                 for (int i=0; i<256; ++i)
 111                         ret.addAll(level0[i].keySet());
 112                 return ret;
 113         }
 114
 115         public Object put(Object key, Object value) {
 116                 return submap(key).put(key, value);
 117         }
 118
 119         public void putAll(Map arg0) {
 120                 for (Iterator i=arg0.keySet().iterator(); i.hasNext(); ) {
 121                         Object k=i.next();
 122                         Object v=arg0.get(k);
 123                         put(k,v);
 124                 }
 125         }
 126
 127         public Object remove(Object key) {
 128                 return submap(key).remove(key);
 129         }
 130
 131         public int size() {
 132                 int ret=0;
 133                 for (int i=0; i<256; ++i)
 134                         ret += level0[i].size();
 135                 return ret;
 136         }
 137
 138         public Collection values() {
 139                 List ret=new ArrayList(size());
 140                 for (int i=0; i<256; ++i)
 141                         ret.addAll(level0[i].values());
 142                 return ret;
 143         }
 144
 145 }