1 /*
2 * Copyright (C) 2006-2008, Shawn O. Pearce <spearce@spearce.org>
3 * and other copyright owners as documented in the project's IP log.
4 *
5 * This program and the accompanying materials are made available
6 * under the terms of the Eclipse Distribution License v1.0 which
7 * accompanies this distribution, is reproduced below, and is
8 * available at http://www.eclipse.org/org/documents/edl-v10.php
9 *
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
14 * conditions are met:
15 *
16 * - Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 *
19 * - Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following
21 * disclaimer in the documentation and/or other materials provided
22 * with the distribution.
23 *
24 * - Neither the name of the Eclipse Foundation, Inc. nor the
25 * names of its contributors may be used to endorse or promote
26 * products derived from this software without specific prior
27 * written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42 */
43
44 package org.eclipse.jgit.lib;
45
46 import java.io.IOException;
47 import java.io.OutputStream;
48 import java.io.Writer;
49 import java.nio.ByteBuffer;
50
51 import org.eclipse.jgit.util.NB;
52
53 /**
54 * A (possibly mutable) SHA-1 abstraction.
55 * <p>
56 * If this is an instance of {@link org.eclipse.jgit.lib.MutableObjectId} the
57 * concept of equality with this instance can alter at any time, if this
58 * instance is modified to represent a different object name.
59 */
60 public abstract class AnyObjectId implements Comparable<AnyObjectId> {
61
62 /**
63 * Compare to object identifier byte sequences for equality.
64 *
65 * @param firstObjectId
66 * the first identifier to compare. Must not be null.
67 * @param secondObjectId
68 * the second identifier to compare. Must not be null.
69 * @return true if the two identifiers are the same.
70 */
71 public static boolean equals(final AnyObjectId firstObjectId,
72 final AnyObjectId secondObjectId) {
73 if (firstObjectId == secondObjectId)
74 return true;
75
76 // We test word 2 first as odds are someone already used our
77 // word 1 as a hash code, and applying that came up with these
78 // two instances we are comparing for equality. Therefore the
79 // first two words are very likely to be identical. We want to
80 // break away from collisions as quickly as possible.
81 //
82 return firstObjectId.w2 == secondObjectId.w2
83 && firstObjectId.w3 == secondObjectId.w3
84 && firstObjectId.w4 == secondObjectId.w4
85 && firstObjectId.w5 == secondObjectId.w5
86 && firstObjectId.w1 == secondObjectId.w1;
87 }
88
89 int w1;
90
91 int w2;
92
93 int w3;
94
95 int w4;
96
97 int w5;
98
99 /**
100 * Get the first 8 bits of the ObjectId.
101 *
102 * This is a faster version of {@code getByte(0)}.
103 *
104 * @return a discriminator usable for a fan-out style map. Returned values
105 * are unsigned and thus are in the range [0,255] rather than the
106 * signed byte range of [-128, 127].
107 */
108 public final int getFirstByte() {
109 return w1 >>> 24;
110 }
111
112 /**
113 * Get any byte from the ObjectId.
114 *
115 * Callers hard-coding {@code getByte(0)} should instead use the much faster
116 * special case variant {@link #getFirstByte()}.
117 *
118 * @param index
119 * index of the byte to obtain from the raw form of the ObjectId.
120 * Must be in range [0,
121 * {@link org.eclipse.jgit.lib.Constants#OBJECT_ID_LENGTH}).
122 * @return the value of the requested byte at {@code index}. Returned values
123 * are unsigned and thus are in the range [0,255] rather than the
124 * signed byte range of [-128, 127].
125 * @throws java.lang.ArrayIndexOutOfBoundsException
126 * {@code index} is less than 0, equal to
127 * {@link org.eclipse.jgit.lib.Constants#OBJECT_ID_LENGTH}, or
128 * greater than
129 * {@link org.eclipse.jgit.lib.Constants#OBJECT_ID_LENGTH}.
130 */
131 public final int getByte(int index) {
132 int w;
133 switch (index >> 2) {
134 case 0:
135 w = w1;
136 break;
137 case 1:
138 w = w2;
139 break;
140 case 2:
141 w = w3;
142 break;
143 case 3:
144 w = w4;
145 break;
146 case 4:
147 w = w5;
148 break;
149 default:
150 throw new ArrayIndexOutOfBoundsException(index);
151 }
152
153 return (w >>> (8 * (3 - (index & 3)))) & 0xff;
154 }
155
156 /**
157 * {@inheritDoc}
158 * <p>
159 * Compare this ObjectId to another and obtain a sort ordering.
160 */
161 @Override
162 public final int compareTo(final AnyObjectId other) {
163 if (this == other)
164 return 0;
165
166 int cmp;
167
168 cmp = NB.compareUInt32(w1, other.w1);
169 if (cmp != 0)
170 return cmp;
171
172 cmp = NB.compareUInt32(w2, other.w2);
173 if (cmp != 0)
174 return cmp;
175
176 cmp = NB.compareUInt32(w3, other.w3);
177 if (cmp != 0)
178 return cmp;
179
180 cmp = NB.compareUInt32(w4, other.w4);
181 if (cmp != 0)
182 return cmp;
183
184 return NB.compareUInt32(w5, other.w5);
185 }
186
187 /**
188 * Compare this ObjectId to a network-byte-order ObjectId.
189 *
190 * @param bs
191 * array containing the other ObjectId in network byte order.
192 * @param p
193 * position within {@code bs} to start the compare at. At least
194 * 20 bytes, starting at this position are required.
195 * @return a negative integer, zero, or a positive integer as this object is
196 * less than, equal to, or greater than the specified object.
197 */
198 public final int compareTo(final byte[] bs, final int p) {
199 int cmp;
200
201 cmp = NB.compareUInt32(w1, NB.decodeInt32(bs, p));
202 if (cmp != 0)
203 return cmp;
204
205 cmp = NB.compareUInt32(w2, NB.decodeInt32(bs, p + 4));
206 if (cmp != 0)
207 return cmp;
208
209 cmp = NB.compareUInt32(w3, NB.decodeInt32(bs, p + 8));
210 if (cmp != 0)
211 return cmp;
212
213 cmp = NB.compareUInt32(w4, NB.decodeInt32(bs, p + 12));
214 if (cmp != 0)
215 return cmp;
216
217 return NB.compareUInt32(w5, NB.decodeInt32(bs, p + 16));
218 }
219
220 /**
221 * Compare this ObjectId to a network-byte-order ObjectId.
222 *
223 * @param bs
224 * array containing the other ObjectId in network byte order.
225 * @param p
226 * position within {@code bs} to start the compare at. At least 5
227 * integers, starting at this position are required.
228 * @return a negative integer, zero, or a positive integer as this object is
229 * less than, equal to, or greater than the specified object.
230 */
231 public final int compareTo(final int[] bs, final int p) {
232 int cmp;
233
234 cmp = NB.compareUInt32(w1, bs[p]);
235 if (cmp != 0)
236 return cmp;
237
238 cmp = NB.compareUInt32(w2, bs[p + 1]);
239 if (cmp != 0)
240 return cmp;
241
242 cmp = NB.compareUInt32(w3, bs[p + 2]);
243 if (cmp != 0)
244 return cmp;
245
246 cmp = NB.compareUInt32(w4, bs[p + 3]);
247 if (cmp != 0)
248 return cmp;
249
250 return NB.compareUInt32(w5, bs[p + 4]);
251 }
252
253 /**
254 * Tests if this ObjectId starts with the given abbreviation.
255 *
256 * @param abbr
257 * the abbreviation.
258 * @return true if this ObjectId begins with the abbreviation; else false.
259 */
260 public boolean startsWith(final AbbreviatedObjectId abbr) {
261 return abbr.prefixCompare(this) == 0;
262 }
263
264 /** {@inheritDoc} */
265 @Override
266 public final int hashCode() {
267 return w2;
268 }
269
270 /**
271 * Determine if this ObjectId has exactly the same value as another.
272 *
273 * @param other
274 * the other id to compare to. May be null.
275 * @return true only if both ObjectIds have identical bits.
276 */
277 public final boolean equals(final AnyObjectId other) {
278 return other != null ? equals(this, other) : false;
279 }
280
281 /** {@inheritDoc} */
282 @Override
283 public final boolean equals(final Object o) {
284 if (o instanceof AnyObjectId)
285 return equals((AnyObjectId) o);
286 else
287 return false;
288 }
289
290 /**
291 * Copy this ObjectId to an output writer in raw binary.
292 *
293 * @param w
294 * the buffer to copy to. Must be in big endian order.
295 */
296 public void copyRawTo(final ByteBuffer w) {
297 w.putInt(w1);
298 w.putInt(w2);
299 w.putInt(w3);
300 w.putInt(w4);
301 w.putInt(w5);
302 }
303
304 /**
305 * Copy this ObjectId to a byte array.
306 *
307 * @param b
308 * the buffer to copy to.
309 * @param o
310 * the offset within b to write at.
311 */
312 public void copyRawTo(final byte[] b, final int o) {
313 NB.encodeInt32(b, o, w1);
314 NB.encodeInt32(b, o + 4, w2);
315 NB.encodeInt32(b, o + 8, w3);
316 NB.encodeInt32(b, o + 12, w4);
317 NB.encodeInt32(b, o + 16, w5);
318 }
319
320 /**
321 * Copy this ObjectId to an int array.
322 *
323 * @param b
324 * the buffer to copy to.
325 * @param o
326 * the offset within b to write at.
327 */
328 public void copyRawTo(final int[] b, final int o) {
329 b[o] = w1;
330 b[o + 1] = w2;
331 b[o + 2] = w3;
332 b[o + 3] = w4;
333 b[o + 4] = w5;
334 }
335
336 /**
337 * Copy this ObjectId to an output writer in raw binary.
338 *
339 * @param w
340 * the stream to write to.
341 * @throws java.io.IOException
342 * the stream writing failed.
343 */
344 public void copyRawTo(final OutputStream w) throws IOException {
345 writeRawInt(w, w1);
346 writeRawInt(w, w2);
347 writeRawInt(w, w3);
348 writeRawInt(w, w4);
349 writeRawInt(w, w5);
350 }
351
352 private static void writeRawInt(final OutputStream w, int v)
353 throws IOException {
354 w.write(v >>> 24);
355 w.write(v >>> 16);
356 w.write(v >>> 8);
357 w.write(v);
358 }
359
360 /**
361 * Copy this ObjectId to an output writer in hex format.
362 *
363 * @param w
364 * the stream to copy to.
365 * @throws java.io.IOException
366 * the stream writing failed.
367 */
368 public void copyTo(final OutputStream w) throws IOException {
369 w.write(toHexByteArray());
370 }
371
372 /**
373 * Copy this ObjectId to a byte array in hex format.
374 *
375 * @param b
376 * the buffer to copy to.
377 * @param o
378 * the offset within b to write at.
379 */
380 public void copyTo(byte[] b, int o) {
381 formatHexByte(b, o + 0, w1);
382 formatHexByte(b, o + 8, w2);
383 formatHexByte(b, o + 16, w3);
384 formatHexByte(b, o + 24, w4);
385 formatHexByte(b, o + 32, w5);
386 }
387
388 /**
389 * Copy this ObjectId to a ByteBuffer in hex format.
390 *
391 * @param b
392 * the buffer to copy to.
393 */
394 public void copyTo(ByteBuffer b) {
395 b.put(toHexByteArray());
396 }
397
398 private byte[] toHexByteArray() {
399 final byte[] dst = new byte[Constants.OBJECT_ID_STRING_LENGTH];
400 formatHexByte(dst, 0, w1);
401 formatHexByte(dst, 8, w2);
402 formatHexByte(dst, 16, w3);
403 formatHexByte(dst, 24, w4);
404 formatHexByte(dst, 32, w5);
405 return dst;
406 }
407
408 private static final byte[] hexbyte = { '0', '1', '2', '3', '4', '5', '6',
409 '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
410
411 private static void formatHexByte(final byte[] dst, final int p, int w) {
412 int o = p + 7;
413 while (o >= p && w != 0) {
414 dst[o--] = hexbyte[w & 0xf];
415 w >>>= 4;
416 }
417 while (o >= p)
418 dst[o--] = '0';
419 }
420
421 /**
422 * Copy this ObjectId to an output writer in hex format.
423 *
424 * @param w
425 * the stream to copy to.
426 * @throws java.io.IOException
427 * the stream writing failed.
428 */
429 public void copyTo(final Writer w) throws IOException {
430 w.write(toHexCharArray());
431 }
432
433 /**
434 * Copy this ObjectId to an output writer in hex format.
435 *
436 * @param tmp
437 * temporary char array to buffer construct into before writing.
438 * Must be at least large enough to hold 2 digits for each byte
439 * of object id (40 characters or larger).
440 * @param w
441 * the stream to copy to.
442 * @throws java.io.IOException
443 * the stream writing failed.
444 */
445 public void copyTo(final char[] tmp, final Writer w) throws IOException {
446 toHexCharArray(tmp);
447 w.write(tmp, 0, Constants.OBJECT_ID_STRING_LENGTH);
448 }
449
450 /**
451 * Copy this ObjectId to a StringBuilder in hex format.
452 *
453 * @param tmp
454 * temporary char array to buffer construct into before writing.
455 * Must be at least large enough to hold 2 digits for each byte
456 * of object id (40 characters or larger).
457 * @param w
458 * the string to append onto.
459 */
460 public void copyTo(final char[] tmp, final StringBuilder w) {
461 toHexCharArray(tmp);
462 w.append(tmp, 0, Constants.OBJECT_ID_STRING_LENGTH);
463 }
464
465 private char[] toHexCharArray() {
466 final char[] dst = new char[Constants.OBJECT_ID_STRING_LENGTH];
467 toHexCharArray(dst);
468 return dst;
469 }
470
471 private void toHexCharArray(final char[] dst) {
472 formatHexChar(dst, 0, w1);
473 formatHexChar(dst, 8, w2);
474 formatHexChar(dst, 16, w3);
475 formatHexChar(dst, 24, w4);
476 formatHexChar(dst, 32, w5);
477 }
478
479 private static final char[] hexchar = { '0', '1', '2', '3', '4', '5', '6',
480 '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
481
482 static void formatHexChar(final char[] dst, final int p, int w) {
483 int o = p + 7;
484 while (o >= p && w != 0) {
485 dst[o--] = hexchar[w & 0xf];
486 w >>>= 4;
487 }
488 while (o >= p)
489 dst[o--] = '0';
490 }
491
492 /** {@inheritDoc} */
493 @SuppressWarnings("nls")
494 @Override
495 public String toString() {
496 return "AnyObjectId[" + name() + "]";
497 }
498
499 /**
500 * <p>name.</p>
501 *
502 * @return string form of the SHA-1, in lower case hexadecimal.
503 */
504 public final String name() {
505 return new String(toHexCharArray());
506 }
507
508 /**
509 * Get string form of the SHA-1, in lower case hexadecimal.
510 *
511 * @return string form of the SHA-1, in lower case hexadecimal.
512 */
513 public final String getName() {
514 return name();
515 }
516
517 /**
518 * Return an abbreviation (prefix) of this object SHA-1.
519 * <p>
520 * This implementation does not guarantee uniqueness. Callers should instead
521 * use
522 * {@link org.eclipse.jgit.lib.ObjectReader#abbreviate(AnyObjectId, int)} to
523 * obtain a unique abbreviation within the scope of a particular object
524 * database.
525 *
526 * @param len
527 * length of the abbreviated string.
528 * @return SHA-1 abbreviation.
529 */
530 public AbbreviatedObjectId abbreviate(final int len) {
531 final int a = AbbreviatedObjectId.mask(len, 1, w1);
532 final int b = AbbreviatedObjectId.mask(len, 2, w2);
533 final int c = AbbreviatedObjectId.mask(len, 3, w3);
534 final int d = AbbreviatedObjectId.mask(len, 4, w4);
535 final int e = AbbreviatedObjectId.mask(len, 5, w5);
536 return new AbbreviatedObjectId(len, a, b, c, d, e);
537 }
538
539 /**
540 * Obtain an immutable copy of this current object name value.
541 * <p>
542 * Only returns <code>this</code> if this instance is an unsubclassed
543 * instance of {@link org.eclipse.jgit.lib.ObjectId}; otherwise a new
544 * instance is returned holding the same value.
545 * <p>
546 * This method is useful to shed any additional memory that may be tied to
547 * the subclass, yet retain the unique identity of the object id for future
548 * lookups within maps and repositories.
549 *
550 * @return an immutable copy, using the smallest memory footprint possible.
551 */
552 public final ObjectId copy() {
553 if (getClass() == ObjectId.class)
554 return (ObjectId) this;
555 return new ObjectId(this);
556 }
557
558 /**
559 * Obtain an immutable copy of this current object name value.
560 * <p>
561 * See {@link #copy()} if <code>this</code> is a possibly subclassed (but
562 * immutable) identity and the application needs a lightweight identity
563 * <i>only</i> reference.
564 *
565 * @return an immutable copy. May be <code>this</code> if this is already
566 * an immutable instance.
567 */
568 public abstract ObjectId toObjectId();
569 }