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 import java.util.Iterator;
  41
  42 /**
  43  * Fast, efficient map specifically for {@link ObjectId} subclasses.
  44  * <p>
  45  * This map provides an efficient translation from any ObjectId instance to a
  46  * cached subclass of ObjectId that has the same value.
  47  * <p>
  48  * Raw value equality is tested when comparing two ObjectIds (or subclasses),
  49  * not reference equality and not <code>.equals(Object)</code> equality. This
  50  * allows subclasses to override <code>equals</code> to supply their own
  51  * extended semantics.
  52  *
  53  * @param <V>
  54  *            type of subclass of ObjectId that will be stored in the map.
  55  */
  56 public class ObjectIdSubclassMap<V extends ObjectId> implements Iterable<V> {
  57         private int size;
  58
  59         private V[] obj_hash;
  60
  61         /** Create an empty map. */
  62         public ObjectIdSubclassMap() {
  63                 obj_hash = createArray(32);
  64         }
  65
  66         /** Remove all entries from this map. */
  67         public void clear() {
  68                 size = 0;
  69                 obj_hash = createArray(32);
  70         }
  71
  72         /**
  73          * Lookup an existing mapping.
  74          *
  75          * @param toFind
  76          *            the object identifier to find.
  77          * @return the instance mapped to toFind, or null if no mapping exists.
  78          */
  79         public V get(final AnyObjectId toFind) {
  80                 int i = index(toFind);
  81                 V obj;
  82
  83                 while ((obj = obj_hash[i]) != null) {
  84                         if (AnyObjectId.equals(obj, toFind))
  85                                 return obj;
  86                         if (++i == obj_hash.length)
  87                                 i = 0;
  88                 }
  89                 return null;
  90         }
  91
  92         /**
  93          * Store an object for future lookup.
  94          * <p>
  95          * An existing mapping for <b>must not</b> be in this map. Callers must
  96          * first call {@link #get(AnyObjectId)} to verify there is no current
  97          * mapping prior to adding a new mapping.
  98          *
  99          * @param newValue
 100          *            the object to store.
 101          * @param
 102          *            <Q>
 103          *            type of instance to store.
 104          */
 105         public <Q extends V> void add(final Q newValue) {
 106                 if (obj_hash.length - 1 <= size * 2)
 107                         grow();
 108                 insert(newValue);
 109                 size++;
 110         }
 111
 112         /**
 113          * @return number of objects in map
 114          */
 115         public int size() {
 116                 return size;
 117         }
 118
 119         public Iterator<V> iterator() {
 120                 return new Iterator<V>() {
 121                         private int found;
 122
 123                         private int i;
 124
 125                         public boolean hasNext() {
 126                                 return found < size;
 127                         }
 128
 129                         public V next() {
 130                                 while (i < obj_hash.length) {
 131                                         final V v = obj_hash[i++];
 132                                         if (v != null) {
 133                                                 found++;
 134                                                 return v;
 135                                         }
 136                                 }
 137                                 throw new IllegalStateException();
 138                         }
 139
 140                         public void remove() {
 141                                 throw new UnsupportedOperationException();
 142                         }
 143                 };
 144         }
 145
 146         private final int index(final AnyObjectId id) {
 147                 return (id.w1 >>> 1) % obj_hash.length;
 148         }
 149
 150         private void insert(final V newValue) {
 151                 int j = index(newValue);
 152                 while (obj_hash[j] != null) {
 153                         if (++j >= obj_hash.length)
 154                                 j = 0;
 155                 }
 156                 obj_hash[j] = newValue;
 157         }
 158
 159         private void grow() {
 160                 final V[] old_hash = obj_hash;
 161                 final int old_hash_size = obj_hash.length;
 162
 163                 obj_hash = createArray(2 * old_hash_size);
 164                 for (int i = 0; i < old_hash_size; i++) {
 165                         final V obj = old_hash[i];
 166                         if (obj != null)
 167                                 insert(obj);
 168                 }
 169         }
 170
 171         @SuppressWarnings("unchecked")
 172         private final V[] createArray(final int sz) {
 173                 return (V[]) new ObjectId[sz];
 174         }
 175 }