org.spearce.jgit/src/org/spearce/jgit/lib/AnyObjectId.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.io.IOException;
  41 import java.io.OutputStream;
  42 import java.io.Writer;
  43 import java.nio.ByteBuffer;
  44 import java.util.Arrays;
  45
  46 import org.spearce.jgit.util.NB;
  47
  48 /**
  49  * A (possibly mutable) SHA-1 abstraction.
  50  * <p>
  51  * If this is an instance of {@link MutableObjectId} the concept of equality
  52  * with this instance can alter at any time, if this instance is modified to
  53  * represent a different object name.
  54  */
  55 public abstract class AnyObjectId implements Comparable {
  56         static final int RAW_LEN = Constants.OBJECT_ID_LENGTH;
  57
  58         static final int STR_LEN = RAW_LEN * 2;
  59
  60         static final byte fromhex[];
  61
  62         static {
  63                 fromhex = new byte['f' + 1];
  64                 Arrays.fill(fromhex, (byte) -1);
  65                 for (char i = '0'; i <= '9'; i++)
  66                         fromhex[i] = (byte) (i - '0');
  67                 for (char i = 'a'; i <= 'f'; i++)
  68                         fromhex[i] = (byte) ((i - 'a') + 10);
  69
  70                 if (RAW_LEN != 20)
  71                         throw new LinkageError("ObjectId expects"
  72                                         + " Constants.OBJECT_ID_LENGTH = 20; it is " + RAW_LEN
  73                                         + ".");
  74         }
  75
  76         /**
  77          * Compare to object identifier byte sequences for equality.
  78          *
  79          * @param firstObjectId
  80          *            the first identifier to compare. Must not be null.
  81          * @param secondObjectId
  82          *            the second identifier to compare. Must not be null.
  83          * @return true if the two identifiers are the same.
  84          */
  85         public static boolean equals(final AnyObjectId firstObjectId,
  86                         final AnyObjectId secondObjectId) {
  87                 if (firstObjectId == secondObjectId)
  88                         return true;
  89
  90                 // We test word 2 first as odds are someone already used our
  91                 // word 1 as a hash code, and applying that came up with these
  92                 // two instances we are comparing for equality. Therefore the
  93                 // first two words are very likely to be identical. We want to
  94                 // break away from collisions as quickly as possible.
  95                 //
  96                 return firstObjectId.w2 == secondObjectId.w2
  97                                 && firstObjectId.w3 == secondObjectId.w3
  98                                 && firstObjectId.w4 == secondObjectId.w4
  99                                 && firstObjectId.w5 == secondObjectId.w5
 100                                 && firstObjectId.w1 == secondObjectId.w1;
 101         }
 102
 103         static final int hexUInt32(final byte[] bs, final int p) {
 104                 int r = fromhex[bs[p]] << 4;
 105
 106                 r |= fromhex[bs[p + 1]];
 107                 r <<= 4;
 108
 109                 r |= fromhex[bs[p + 2]];
 110                 r <<= 4;
 111
 112                 r |= fromhex[bs[p + 3]];
 113                 r <<= 4;
 114
 115                 r |= fromhex[bs[p + 4]];
 116                 r <<= 4;
 117
 118                 r |= fromhex[bs[p + 5]];
 119                 r <<= 4;
 120
 121                 r |= fromhex[bs[p + 6]];
 122
 123                 final int last = fromhex[bs[p + 7]];
 124                 if (r < 0 || last < 0)
 125                         throw new ArrayIndexOutOfBoundsException();
 126                 return (r << 4) | last;
 127         }
 128
 129         int w1;
 130
 131         int w2;
 132
 133         int w3;
 134
 135         int w4;
 136
 137         int w5;
 138
 139         /**
 140          * For ObjectIdMap
 141          *
 142          * @return a discriminator usable for a fan-out style map
 143          */
 144         public final int getFirstByte() {
 145                 return w1 >>> 24;
 146         }
 147
 148         /**
 149          * Compare this ObjectId to another and obtain a sort ordering.
 150          *
 151          * @param other
 152          *            the other id to compare to. Must not be null.
 153          * @return < 0 if this id comes before other; 0 if this id is equal to
 154          *         other; > 0 if this id comes after other.
 155          */
 156         public int compareTo(final ObjectId other) {
 157                 if (this == other)
 158                         return 0;
 159
 160                 int cmp;
 161
 162                 cmp = NB.compareUInt32(w1, other.w1);
 163                 if (cmp != 0)
 164                         return cmp;
 165
 166                 cmp = NB.compareUInt32(w2, other.w2);
 167                 if (cmp != 0)
 168                         return cmp;
 169
 170                 cmp = NB.compareUInt32(w3, other.w3);
 171                 if (cmp != 0)
 172                         return cmp;
 173
 174                 cmp = NB.compareUInt32(w4, other.w4);
 175                 if (cmp != 0)
 176                         return cmp;
 177
 178                 return NB.compareUInt32(w5, other.w5);
 179         }
 180
 181         public int compareTo(final Object other) {
 182                 return compareTo(((ObjectId) other));
 183         }
 184
 185         int compareTo(final byte[] bs, final int p) {
 186                 int cmp;
 187
 188                 cmp = NB.compareUInt32(w1, NB.decodeInt32(bs, p));
 189                 if (cmp != 0)
 190                         return cmp;
 191
 192                 cmp = NB.compareUInt32(w2, NB.decodeInt32(bs, p + 4));
 193                 if (cmp != 0)
 194                         return cmp;
 195
 196                 cmp = NB.compareUInt32(w3, NB.decodeInt32(bs, p + 8));
 197                 if (cmp != 0)
 198                         return cmp;
 199
 200                 cmp = NB.compareUInt32(w4, NB.decodeInt32(bs, p + 12));
 201                 if (cmp != 0)
 202                         return cmp;
 203
 204                 return NB.compareUInt32(w5, NB.decodeInt32(bs, p + 16));
 205         }
 206
 207         int compareTo(final int[] bs, final int p) {
 208                 int cmp;
 209
 210                 cmp = NB.compareUInt32(w1, bs[p]);
 211                 if (cmp != 0)
 212                         return cmp;
 213
 214                 cmp = NB.compareUInt32(w2, bs[p + 1]);
 215                 if (cmp != 0)
 216                         return cmp;
 217
 218                 cmp = NB.compareUInt32(w3, bs[p + 2]);
 219                 if (cmp != 0)
 220                         return cmp;
 221
 222                 cmp = NB.compareUInt32(w4, bs[p + 3]);
 223                 if (cmp != 0)
 224                         return cmp;
 225
 226                 return NB.compareUInt32(w5, bs[p + 4]);
 227         }
 228
 229         public int hashCode() {
 230                 return w2;
 231         }
 232
 233         /**
 234          * Determine if this ObjectId has exactly the same value as another.
 235          *
 236          * @param other
 237          *            the other id to compare to. May be null.
 238          * @return true only if both ObjectIds have identical bits.
 239          */
 240         public boolean equals(final ObjectId other) {
 241                 return other != null ? equals(this, other) : false;
 242         }
 243
 244         public boolean equals(final Object o) {
 245                 return equals((ObjectId) o);
 246         }
 247
 248         /**
 249          * Copy this ObjectId to an output writer in raw binary.
 250          *
 251          * @param w
 252          *            the buffer to copy to. Must be in big endian order.
 253          */
 254         public void copyRawTo(final ByteBuffer w) {
 255                 w.putInt(w1);
 256                 w.putInt(w2);
 257                 w.putInt(w3);
 258                 w.putInt(w4);
 259                 w.putInt(w5);
 260         }
 261
 262         /**
 263          * Copy this ObjectId to a byte array.
 264          *
 265          * @param b
 266          *            the buffer to copy to.
 267          * @param o
 268          *            the offset within b to write at.
 269          */
 270         public void copyRawTo(final byte[] b, final int o) {
 271                 NB.encodeInt32(b, o, w1);
 272                 NB.encodeInt32(b, o + 4, w2);
 273                 NB.encodeInt32(b, o + 8, w3);
 274                 NB.encodeInt32(b, o + 12, w4);
 275                 NB.encodeInt32(b, o + 16, w5);
 276         }
 277
 278         /**
 279          * Copy this ObjectId to an int array.
 280          *
 281          * @param b
 282          *            the buffer to copy to.
 283          * @param o
 284          *            the offset within b to write at.
 285          */
 286         public void copyRawTo(final int[] b, final int o) {
 287                 b[o] = w1;
 288                 b[o + 1] = w2;
 289                 b[o + 2] = w3;
 290                 b[o + 3] = w4;
 291                 b[o + 4] = w5;
 292         }
 293
 294         /**
 295          * Copy this ObjectId to an output writer in raw binary.
 296          *
 297          * @param w
 298          *            the stream to write to.
 299          * @throws IOException
 300          *             the stream writing failed.
 301          */
 302         public void copyRawTo(final OutputStream w) throws IOException {
 303                 writeRawInt(w, w1);
 304                 writeRawInt(w, w2);
 305                 writeRawInt(w, w3);
 306                 writeRawInt(w, w4);
 307                 writeRawInt(w, w5);
 308         }
 309
 310         private static void writeRawInt(final OutputStream w, int v)
 311                         throws IOException {
 312                 w.write(v >>> 24);
 313                 w.write(v >>> 16);
 314                 w.write(v >>> 8);
 315                 w.write(v);
 316         }
 317
 318         /**
 319          * Copy this ObjectId to an output writer in hex format.
 320          *
 321          * @param w
 322          *            the stream to copy to.
 323          * @throws IOException
 324          *             the stream writing failed.
 325          */
 326         public void copyTo(final OutputStream w) throws IOException {
 327                 w.write(toHexByteArray());
 328         }
 329
 330         private byte[] toHexByteArray() {
 331                 final byte[] dst = new byte[STR_LEN];
 332                 formatHexByte(dst, 0, w1);
 333                 formatHexByte(dst, 8, w2);
 334                 formatHexByte(dst, 16, w3);
 335                 formatHexByte(dst, 24, w4);
 336                 formatHexByte(dst, 32, w5);
 337                 return dst;
 338         }
 339
 340         private static final byte[] hexbyte = { '0', '1', '2', '3', '4', '5', '6',
 341                         '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
 342
 343         private static void formatHexByte(final byte[] dst, final int p, int w) {
 344                 int o = p + 7;
 345                 while (o >= p && w != 0) {
 346                         dst[o--] = hexbyte[w & 0xf];
 347                         w >>>= 4;
 348                 }
 349                 while (o >= p)
 350                         dst[o--] = '0';
 351         }
 352
 353         /**
 354          * Copy this ObjectId to an output writer in hex format.
 355          *
 356          * @param w
 357          *            the stream to copy to.
 358          * @throws IOException
 359          *             the stream writing failed.
 360          */
 361         public void copyTo(final Writer w) throws IOException {
 362                 w.write(toHexCharArray());
 363         }
 364
 365         /**
 366          * Copy this ObjectId to an output writer in hex format.
 367          *
 368          * @param tmp
 369          *            temporary char array to buffer construct into before writing.
 370          *            Must be at least large enough to hold 2 digits for each byte
 371          *            of object id (40 characters or larger).
 372          * @param w
 373          *            the stream to copy to.
 374          * @throws IOException
 375          *             the stream writing failed.
 376          */
 377         public void copyTo(final char[] tmp, final Writer w) throws IOException {
 378                 toHexCharArray(tmp);
 379                 w.write(tmp);
 380         }
 381
 382         private char[] toHexCharArray() {
 383                 final char[] dst = new char[STR_LEN];
 384                 toHexCharArray(dst);
 385                 return dst;
 386         }
 387
 388         private void toHexCharArray(final char[] dst) {
 389                 formatHexChar(dst, 0, w1);
 390                 formatHexChar(dst, 8, w2);
 391                 formatHexChar(dst, 16, w3);
 392                 formatHexChar(dst, 24, w4);
 393                 formatHexChar(dst, 32, w5);
 394         }
 395
 396         private static final char[] hexchar = { '0', '1', '2', '3', '4', '5', '6',
 397                         '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
 398
 399         private static void formatHexChar(final char[] dst, final int p, int w) {
 400                 int o = p + 7;
 401                 while (o >= p && w != 0) {
 402                         dst[o--] = hexchar[w & 0xf];
 403                         w >>>= 4;
 404                 }
 405                 while (o >= p)
 406                         dst[o--] = '0';
 407         }
 408
 409         public String toString() {
 410                 return new String(toHexCharArray());
 411         }
 412
 413         /**
 414          * Obtain an immutable copy of this current object name value.
 415          * <p>
 416          * Only returns <code>this</code> if this instance is an unsubclassed
 417          * instance of {@link ObjectId}; otherwise a new instance is returned
 418          * holding the same value.
 419          * <p>
 420          * This method is useful to shed any additional memory that may be tied to
 421          * the subclass, yet retain the unique identity of the object id for future
 422          * lookups within maps and repositories.
 423          *
 424          * @return an immutable copy, using the smallest memory footprint possible.
 425          */
 426         public final ObjectId copy() {
 427                 if (getClass() == ObjectId.class)
 428                         return (ObjectId) this;
 429                 return new ObjectId(this);
 430         }
 431
 432         /**
 433          * Obtain an immutable copy of this current object name value.
 434          * <p>
 435          * See {@link #copy()} if <code>this</code> is a possibly subclassed (but
 436          * immutable) identity and the application needs a lightweight identity
 437          * <i>only</i> reference.
 438          *
 439          * @return an immutable copy. May be <code>this</code> if this is already
 440          *         an immutable instance.
 441          */
 442         public abstract ObjectId toObjectId();
 443 }