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

   1 /*
   2  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   3  *
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or
   7  * without modification, are permitted provided that the following
   8  * conditions are met:
   9  *
  10  * - Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  *
  13  * - Redistributions in binary form must reproduce the above
  14  *   copyright notice, this list of conditions and the following
  15  *   disclaimer in the documentation and/or other materials provided
  16  *   with the distribution.
  17  *
  18  * - Neither the name of the Git Development Community nor the
  19  *   names of its contributors may be used to endorse or promote
  20  *   products derived from this software without specific prior
  21  *   written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  24  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  25  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  26  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  28  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  29  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  30  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  32  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  33  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  35  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 package org.spearce.jgit.lib;
  39
  40 /**
  41  * Fast, efficient map specifically for {@link ObjectId} subclasses.
  42  * <p>
  43  * This map provides an efficient translation from any ObjectId instance to a
  44  * cached subclass of ObjectId that has the same value.
  45  * <p>
  46  * Raw value equality is tested when comparing two ObjectIds (or subclasses),
  47  * not reference equality and not <code>.equals(Object)</code> equality. This
  48  * allows subclasses to override <code>equals</code> to supply their own
  49  * extended semantics.
  50  *
  51  * @param <V>
  52  *            type of subclass of ObjectId that will be stored in the map.
  53  */
  54 public class ObjectIdSubclassMap<V extends ObjectId> {
  55         private int size;
  56
  57         private V[] obj_hash;
  58
  59         /** Create an empty map. */
  60         public ObjectIdSubclassMap() {
  61                 obj_hash = createArray(32);
  62         }
  63
  64         /** Remove all entries from this map. */
  65         public void clear() {
  66                 size = 0;
  67                 obj_hash = createArray(32);
  68         }
  69
  70         /**
  71          * Lookup an existing mapping.
  72          *
  73          * @param toFind
  74          *            the object identifier to find.
  75          * @return the instance mapped to toFind, or null if no mapping exists.
  76          */
  77         public V get(final AnyObjectId toFind) {
  78                 int i = index(toFind);
  79                 V obj;
  80
  81                 while ((obj = obj_hash[i]) != null) {
  82                         if (AnyObjectId.equals(obj, toFind))
  83                                 return obj;
  84                         if (++i == obj_hash.length)
  85                                 i = 0;
  86                 }
  87                 return null;
  88         }
  89
  90         /**
  91          * Store an object for future lookup.
  92          * <p>
  93          * An existing mapping for <b>must not</b> be in this map. Callers must
  94          * first call {@link #get(AnyObjectId)} to verify there is no current
  95          * mapping prior to adding a new mapping.
  96          *
  97          * @param newValue
  98          *            the object to store.
  99          * @param
 100          *            <Q>
 101          *            type of instance to store.
 102          */
 103         public <Q extends V> void add(final Q newValue) {
 104                 if (obj_hash.length - 1 <= size * 2)
 105                         grow();
 106                 insert(newValue);
 107                 size++;
 108         }
 109
 110         /**
 111          * @return number of objects in map
 112          */
 113         public int size() {
 114                 return size;
 115         }
 116
 117         private final int index(final AnyObjectId id) {
 118                 return (id.w1 >>> 1) % obj_hash.length;
 119         }
 120
 121         private void insert(final V newValue) {
 122                 int j = index(newValue);
 123                 while (obj_hash[j] != null) {
 124                         if (++j >= obj_hash.length)
 125                                 j = 0;
 126                 }
 127                 obj_hash[j] = newValue;
 128         }
 129
 130         private void grow() {
 131                 final V[] old_hash = obj_hash;
 132                 final int old_hash_size = obj_hash.length;
 133
 134                 obj_hash = createArray(2 * old_hash_size);
 135                 for (int i = 0; i < old_hash_size; i++) {
 136                         final V obj = old_hash[i];
 137                         if (obj != null)
 138                                 insert(obj);
 139                 }
 140         }
 141
 142         @SuppressWarnings("unchecked")
 143         private final V[] createArray(final int sz) {
 144                 return (V[]) new ObjectId[sz];
 145         }
 146 }