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 3 first since the git file-based ODB
77 // uses the first byte of w1, and we use w2 as the
78 // hash code, one of those probably came up with these
79 // two instances which we are comparing for equality.
80 // Therefore the first two words are very likely to be
81 // identical. We want to break away from collisions as
82 // quickly as possible.
83 //
84 return firstObjectId.w3 == secondObjectId.w3
85 && firstObjectId.w4 == secondObjectId.w4
86 && firstObjectId.w5 == secondObjectId.w5
87 && firstObjectId.w1 == secondObjectId.w1
88 && firstObjectId.w2 == secondObjectId.w2;
89 }
90
91 int w1;
92
93 int w2;
94
95 int w3;
96
97 int w4;
98
99 int w5;
100
101 /**
102 * Get the first 8 bits of the ObjectId.
103 *
104 * This is a faster version of {@code getByte(0)}.
105 *
106 * @return a discriminator usable for a fan-out style map. Returned values
107 * are unsigned and thus are in the range [0,255] rather than the
108 * signed byte range of [-128, 127].
109 */
110 public final int getFirstByte() {
111 return w1 >>> 24;
112 }
113
114 /**
115 * Get any byte from the ObjectId.
116 *
117 * Callers hard-coding {@code getByte(0)} should instead use the much faster
118 * special case variant {@link #getFirstByte()}.
119 *
120 * @param index
121 * index of the byte to obtain from the raw form of the ObjectId.
122 * Must be in range [0,
123 * {@link org.eclipse.jgit.lib.Constants#OBJECT_ID_LENGTH}).
124 * @return the value of the requested byte at {@code index}. Returned values
125 * are unsigned and thus are in the range [0,255] rather than the
126 * signed byte range of [-128, 127].
127 * @throws java.lang.ArrayIndexOutOfBoundsException
128 * {@code index} is less than 0, equal to
129 * {@link org.eclipse.jgit.lib.Constants#OBJECT_ID_LENGTH}, or
130 * greater than
131 * {@link org.eclipse.jgit.lib.Constants#OBJECT_ID_LENGTH}.
132 */
133 public final int getByte(int index) {
134 int w;
135 switch (index >> 2) {
136 case 0:
137 w = w1;
138 break;
139 case 1:
140 w = w2;
141 break;
142 case 2:
143 w = w3;
144 break;
145 case 3:
146 w = w4;
147 break;
148 case 4:
149 w = w5;
150 break;
151 default:
152 throw new ArrayIndexOutOfBoundsException(index);
153 }
154
155 return (w >>> (8 * (3 - (index & 3)))) & 0xff;
156 }
157
158 /**
159 * {@inheritDoc}
160 * <p>
161 * Compare this ObjectId to another and obtain a sort ordering.
162 */
163 @Override
164 public final int compareTo(AnyObjectId other) {
165 if (this == other)
166 return 0;
167
168 int cmp;
169
170 cmp = NB.compareUInt32(w1, other.w1);
171 if (cmp != 0)
172 return cmp;
173
174 cmp = NB.compareUInt32(w2, other.w2);
175 if (cmp != 0)
176 return cmp;
177
178 cmp = NB.compareUInt32(w3, other.w3);
179 if (cmp != 0)
180 return cmp;
181
182 cmp = NB.compareUInt32(w4, other.w4);
183 if (cmp != 0)
184 return cmp;
185
186 return NB.compareUInt32(w5, other.w5);
187 }
188
189 /**
190 * Compare this ObjectId to a network-byte-order ObjectId.
191 *
192 * @param bs
193 * array containing the other ObjectId in network byte order.
194 * @param p
195 * position within {@code bs} to start the compare at. At least
196 * 20 bytes, starting at this position are required.
197 * @return a negative integer, zero, or a positive integer as this object is
198 * less than, equal to, or greater than the specified object.
199 */
200 public final int compareTo(byte[] bs, int p) {
201 int cmp;
202
203 cmp = NB.compareUInt32(w1, NB.decodeInt32(bs, p));
204 if (cmp != 0)
205 return cmp;
206
207 cmp = NB.compareUInt32(w2, NB.decodeInt32(bs, p + 4));
208 if (cmp != 0)
209 return cmp;
210
211 cmp = NB.compareUInt32(w3, NB.decodeInt32(bs, p + 8));
212 if (cmp != 0)
213 return cmp;
214
215 cmp = NB.compareUInt32(w4, NB.decodeInt32(bs, p + 12));
216 if (cmp != 0)
217 return cmp;
218
219 return NB.compareUInt32(w5, NB.decodeInt32(bs, p + 16));
220 }
221
222 /**
223 * Compare this ObjectId to a network-byte-order ObjectId.
224 *
225 * @param bs
226 * array containing the other ObjectId in network byte order.
227 * @param p
228 * position within {@code bs} to start the compare at. At least 5
229 * integers, starting at this position are required.
230 * @return a negative integer, zero, or a positive integer as this object is
231 * less than, equal to, or greater than the specified object.
232 */
233 public final int compareTo(int[] bs, int p) {
234 int cmp;
235
236 cmp = NB.compareUInt32(w1, bs[p]);
237 if (cmp != 0)
238 return cmp;
239
240 cmp = NB.compareUInt32(w2, bs[p + 1]);
241 if (cmp != 0)
242 return cmp;
243
244 cmp = NB.compareUInt32(w3, bs[p + 2]);
245 if (cmp != 0)
246 return cmp;
247
248 cmp = NB.compareUInt32(w4, bs[p + 3]);
249 if (cmp != 0)
250 return cmp;
251
252 return NB.compareUInt32(w5, bs[p + 4]);
253 }
254
255 /**
256 * Tests if this ObjectId starts with the given abbreviation.
257 *
258 * @param abbr
259 * the abbreviation.
260 * @return true if this ObjectId begins with the abbreviation; else false.
261 */
262 public boolean startsWith(AbbreviatedObjectId abbr) {
263 return abbr.prefixCompare(this) == 0;
264 }
265
266 /** {@inheritDoc} */
267 @Override
268 public final int hashCode() {
269 return w2;
270 }
271
272 /**
273 * Determine if this ObjectId has exactly the same value as another.
274 *
275 * @param other
276 * the other id to compare to. May be null.
277 * @return true only if both ObjectIds have identical bits.
278 */
279 public final boolean equals(AnyObjectId other) {
280 return other != null ? equals(this, other) : false;
281 }
282
283 /** {@inheritDoc} */
284 @Override
285 public final boolean equals(Object o) {
286 if (o instanceof AnyObjectId)
287 return equals((AnyObjectId) o);
288 else
289 return false;
290 }
291
292 /**
293 * Copy this ObjectId to an output writer in raw binary.
294 *
295 * @param w
296 * the buffer to copy to. Must be in big endian order.
297 */
298 public void copyRawTo(ByteBuffer w) {
299 w.putInt(w1);
300 w.putInt(w2);
301 w.putInt(w3);
302 w.putInt(w4);
303 w.putInt(w5);
304 }
305
306 /**
307 * Copy this ObjectId to a byte array.
308 *
309 * @param b
310 * the buffer to copy to.
311 * @param o
312 * the offset within b to write at.
313 */
314 public void copyRawTo(byte[] b, int o) {
315 NB.encodeInt32(b, o, w1);
316 NB.encodeInt32(b, o + 4, w2);
317 NB.encodeInt32(b, o + 8, w3);
318 NB.encodeInt32(b, o + 12, w4);
319 NB.encodeInt32(b, o + 16, w5);
320 }
321
322 /**
323 * Copy this ObjectId to an int array.
324 *
325 * @param b
326 * the buffer to copy to.
327 * @param o
328 * the offset within b to write at.
329 */
330 public void copyRawTo(int[] b, int o) {
331 b[o] = w1;
332 b[o + 1] = w2;
333 b[o + 2] = w3;
334 b[o + 3] = w4;
335 b[o + 4] = w5;
336 }
337
338 /**
339 * Copy this ObjectId to an output writer in raw binary.
340 *
341 * @param w
342 * the stream to write to.
343 * @throws java.io.IOException
344 * the stream writing failed.
345 */
346 public void copyRawTo(OutputStream w) throws IOException {
347 writeRawInt(w, w1);
348 writeRawInt(w, w2);
349 writeRawInt(w, w3);
350 writeRawInt(w, w4);
351 writeRawInt(w, w5);
352 }
353
354 private static void writeRawInt(OutputStream w, int v)
355 throws IOException {
356 w.write(v >>> 24);
357 w.write(v >>> 16);
358 w.write(v >>> 8);
359 w.write(v);
360 }
361
362 /**
363 * Copy this ObjectId to an output writer in hex format.
364 *
365 * @param w
366 * the stream to copy to.
367 * @throws java.io.IOException
368 * the stream writing failed.
369 */
370 public void copyTo(OutputStream w) throws IOException {
371 w.write(toHexByteArray());
372 }
373
374 /**
375 * Copy this ObjectId to a byte array in hex format.
376 *
377 * @param b
378 * the buffer to copy to.
379 * @param o
380 * the offset within b to write at.
381 */
382 public void copyTo(byte[] b, int o) {
383 formatHexByte(b, o + 0, w1);
384 formatHexByte(b, o + 8, w2);
385 formatHexByte(b, o + 16, w3);
386 formatHexByte(b, o + 24, w4);
387 formatHexByte(b, o + 32, w5);
388 }
389
390 /**
391 * Copy this ObjectId to a ByteBuffer in hex format.
392 *
393 * @param b
394 * the buffer to copy to.
395 */
396 public void copyTo(ByteBuffer b) {
397 b.put(toHexByteArray());
398 }
399
400 private byte[] toHexByteArray() {
401 final byte[] dst = new byte[Constants.OBJECT_ID_STRING_LENGTH];
402 formatHexByte(dst, 0, w1);
403 formatHexByte(dst, 8, w2);
404 formatHexByte(dst, 16, w3);
405 formatHexByte(dst, 24, w4);
406 formatHexByte(dst, 32, w5);
407 return dst;
408 }
409
410 private static final byte[] hexbyte = { '0', '1', '2', '3', '4', '5', '6',
411 '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
412
413 private static void formatHexByte(byte[] dst, int p, int w) {
414 int o = p + 7;
415 while (o >= p && w != 0) {
416 dst[o--] = hexbyte[w & 0xf];
417 w >>>= 4;
418 }
419 while (o >= p)
420 dst[o--] = '0';
421 }
422
423 /**
424 * Copy this ObjectId to an output writer in hex format.
425 *
426 * @param w
427 * the stream to copy to.
428 * @throws java.io.IOException
429 * the stream writing failed.
430 */
431 public void copyTo(Writer w) throws IOException {
432 w.write(toHexCharArray());
433 }
434
435 /**
436 * Copy this ObjectId to an output writer in hex format.
437 *
438 * @param tmp
439 * temporary char array to buffer construct into before writing.
440 * Must be at least large enough to hold 2 digits for each byte
441 * of object id (40 characters or larger).
442 * @param w
443 * the stream to copy to.
444 * @throws java.io.IOException
445 * the stream writing failed.
446 */
447 public void copyTo(char[] tmp, Writer w) throws IOException {
448 toHexCharArray(tmp);
449 w.write(tmp, 0, Constants.OBJECT_ID_STRING_LENGTH);
450 }
451
452 /**
453 * Copy this ObjectId to a StringBuilder in hex format.
454 *
455 * @param tmp
456 * temporary char array to buffer construct into before writing.
457 * Must be at least large enough to hold 2 digits for each byte
458 * of object id (40 characters or larger).
459 * @param w
460 * the string to append onto.
461 */
462 public void copyTo(char[] tmp, StringBuilder w) {
463 toHexCharArray(tmp);
464 w.append(tmp, 0, Constants.OBJECT_ID_STRING_LENGTH);
465 }
466
467 private char[] toHexCharArray() {
468 final char[] dst = new char[Constants.OBJECT_ID_STRING_LENGTH];
469 toHexCharArray(dst);
470 return dst;
471 }
472
473 private void toHexCharArray(char[] dst) {
474 formatHexChar(dst, 0, w1);
475 formatHexChar(dst, 8, w2);
476 formatHexChar(dst, 16, w3);
477 formatHexChar(dst, 24, w4);
478 formatHexChar(dst, 32, w5);
479 }
480
481 private static final char[] hexchar = { '0', '1', '2', '3', '4', '5', '6',
482 '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
483
484 static void formatHexChar(char[] dst, int p, int w) {
485 int o = p + 7;
486 while (o >= p && w != 0) {
487 dst[o--] = hexchar[w & 0xf];
488 w >>>= 4;
489 }
490 while (o >= p)
491 dst[o--] = '0';
492 }
493
494 /** {@inheritDoc} */
495 @SuppressWarnings("nls")
496 @Override
497 public String toString() {
498 return "AnyObjectId[" + name() + "]";
499 }
500
501 /**
502 * <p>name.</p>
503 *
504 * @return string form of the SHA-1, in lower case hexadecimal.
505 */
506 public final String name() {
507 return new String(toHexCharArray());
508 }
509
510 /**
511 * Get string form of the SHA-1, in lower case hexadecimal.
512 *
513 * @return string form of the SHA-1, in lower case hexadecimal.
514 */
515 public final String getName() {
516 return name();
517 }
518
519 /**
520 * Return an abbreviation (prefix) of this object SHA-1.
521 * <p>
522 * This implementation does not guarantee uniqueness. Callers should instead
523 * use
524 * {@link org.eclipse.jgit.lib.ObjectReader#abbreviate(AnyObjectId, int)} to
525 * obtain a unique abbreviation within the scope of a particular object
526 * database.
527 *
528 * @param len
529 * length of the abbreviated string.
530 * @return SHA-1 abbreviation.
531 */
532 public AbbreviatedObjectId abbreviate(int len) {
533 final int a = AbbreviatedObjectId.mask(len, 1, w1);
534 final int b = AbbreviatedObjectId.mask(len, 2, w2);
535 final int c = AbbreviatedObjectId.mask(len, 3, w3);
536 final int d = AbbreviatedObjectId.mask(len, 4, w4);
537 final int e = AbbreviatedObjectId.mask(len, 5, w5);
538 return new AbbreviatedObjectId(len, a, b, c, d, e);
539 }
540
541 /**
542 * Obtain an immutable copy of this current object name value.
543 * <p>
544 * Only returns <code>this</code> if this instance is an unsubclassed
545 * instance of {@link org.eclipse.jgit.lib.ObjectId}; otherwise a new
546 * instance is returned holding the same value.
547 * <p>
548 * This method is useful to shed any additional memory that may be tied to
549 * the subclass, yet retain the unique identity of the object id for future
550 * lookups within maps and repositories.
551 *
552 * @return an immutable copy, using the smallest memory footprint possible.
553 */
554 public final ObjectId copy() {
555 if (getClass() == ObjectId.class)
556 return (ObjectId) this;
557 return new ObjectId(this);
558 }
559
560 /**
561 * Obtain an immutable copy of this current object name value.
562 * <p>
563 * See {@link #copy()} if <code>this</code> is a possibly subclassed (but
564 * immutable) identity and the application needs a lightweight identity
565 * <i>only</i> reference.
566 *
567 * @return an immutable copy. May be <code>this</code> if this is already
568 * an immutable instance.
569 */
570 public abstract ObjectId toObjectId();
571 }