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

   1 /*
   2  *  Copyright (C) 2008  Shawn Pearce <spearce@spearce.org>
   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 /**
  20  * Fast, efficient map specifically for {@link ObjectId} subclasses.
  21  * <p>
  22  * This map provides an efficient translation from any ObjectId instance to a
  23  * cached subclass of ObjectId that has the same value.
  24  * <p>
  25  * Raw value equality is tested when comparing two ObjectIds (or subclasses),
  26  * not reference equality and not <code>.equals(Object)</code> equality. This
  27  * allows subclasses to override <code>equals</code> to supply their own
  28  * extended semantics.
  29  *
  30  * @param <V>
  31  *            type of subclass of ObjectId that will be stored in the map.
  32  */
  33 public class ObjectIdSubclassMap<V extends ObjectId> {
  34         private int size;
  35
  36         private V[] obj_hash;
  37
  38         /** Create an empty map. */
  39         public ObjectIdSubclassMap() {
  40                 obj_hash = createArray(32);
  41         }
  42
  43         /** Remove all entries from this map. */
  44         public void clear() {
  45                 size = 0;
  46                 obj_hash = createArray(32);
  47         }
  48
  49         /**
  50          * Lookup an existing mapping.
  51          *
  52          * @param toFind
  53          *            the object identifier to find.
  54          * @return the instance mapped to toFind, or null if no mapping exists.
  55          */
  56         public V get(final AnyObjectId toFind) {
  57                 int i = index(toFind);
  58                 V obj;
  59
  60                 while ((obj = obj_hash[i]) != null) {
  61                         if (AnyObjectId.equals(obj, toFind))
  62                                 return obj;
  63                         if (++i == obj_hash.length)
  64                                 i = 0;
  65                 }
  66                 return null;
  67         }
  68
  69         /**
  70          * Store an object for future lookup.
  71          * <p>
  72          * An existing mapping for <b>must not</b> be in this map. Callers must
  73          * first call {@link #get(AnyObjectId)} to verify there is no current
  74          * mapping prior to adding a new mapping.
  75          *
  76          * @param newValue
  77          *            the object to store.
  78          * @param
  79          *            <Q>
  80          *            type of instance to store.
  81          */
  82         public <Q extends V> void add(final Q newValue) {
  83                 if (obj_hash.length - 1 <= size * 2)
  84                         grow();
  85                 insert(newValue);
  86                 size++;
  87         }
  88
  89         private final int index(final AnyObjectId id) {
  90                 return (id.w1 >>> 1) % obj_hash.length;
  91         }
  92
  93         private void insert(final V newValue) {
  94                 int j = index(newValue);
  95                 while (obj_hash[j] != null) {
  96                         if (++j >= obj_hash.length)
  97                                 j = 0;
  98                 }
  99                 obj_hash[j] = newValue;
 100         }
 101
 102         private void grow() {
 103                 final V[] old_hash = obj_hash;
 104                 final int old_hash_size = obj_hash.length;
 105
 106                 obj_hash = createArray(2 * old_hash_size);
 107                 for (int i = 0; i < old_hash_size; i++) {
 108                         final V obj = old_hash[i];
 109                         if (obj != null)
 110                                 insert(obj);
 111                 }
 112         }
 113
 114         @SuppressWarnings("unchecked")
 115         private final V[] createArray(final int sz) {
 116                 return (V[]) new ObjectId[sz];
 117         }
 118 }