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         /**
  44          * Lookup an existing mapping.
  45          *
  46          * @param toFind
  47          *            the object identifier to find.
  48          * @return the instance mapped to toFind, or null if no mapping exists.
  49          */
  50         public V get(final ObjectId toFind) {
  51                 int i = index(toFind);
  52                 V obj;
  53
  54                 while ((obj = obj_hash[i]) != null) {
  55                         if (ObjectId.equals(obj, toFind))
  56                                 return obj;
  57                         if (++i == obj_hash.length)
  58                                 i = 0;
  59                 }
  60                 return null;
  61         }
  62
  63         /**
  64          * Store an object for future lookup.
  65          * <p>
  66          * An existing mapping for <b>must not</b> be in this map. Callers must
  67          * first call {@link #get(ObjectId)} to verify there is no current mapping
  68          * prior to adding a new mapping.
  69          *
  70          * @param newValue
  71          *            the object to store.
  72          * @param
  73          *            <Q>
  74          *            type of instance to store.
  75          */
  76         public <Q extends V> void add(final Q newValue) {
  77                 if (obj_hash.length - 1 <= size * 2)
  78                         grow();
  79                 insert(newValue);
  80                 size++;
  81         }
  82
  83         private final int index(final ObjectId id) {
  84                 return (id.w1 >>> 1) % obj_hash.length;
  85         }
  86
  87         private void insert(final V newValue) {
  88                 int j = index(newValue);
  89                 while (obj_hash[j] != null) {
  90                         if (++j >= obj_hash.length)
  91                                 j = 0;
  92                 }
  93                 obj_hash[j] = newValue;
  94         }
  95
  96         private void grow() {
  97                 final V[] old_hash = obj_hash;
  98                 final int old_hash_size = obj_hash.length;
  99
 100                 obj_hash = createArray(2 * old_hash_size);
 101                 for (int i = 0; i < old_hash_size; i++) {
 102                         final V obj = old_hash[i];
 103                         if (obj != null)
 104                                 insert(obj);
 105                 }
 106         }
 107
 108         @SuppressWarnings("unchecked")
 109         private final V[] createArray(final int sz) {
 110                 return (V[]) new ObjectId[sz];
 111         }
 112 }