2 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
6 * Redistribution and use in source and binary forms, with or
7 * without modification, are permitted provided that the following
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
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.
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
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.
38 package org
.spearce
.jgit
.lib
;
40 import java
.io
.IOException
;
41 import java
.io
.InputStream
;
42 import java
.util
.Arrays
;
43 import java
.util
.Iterator
;
44 import java
.util
.NoSuchElementException
;
46 import org
.spearce
.jgit
.errors
.MissingObjectException
;
47 import org
.spearce
.jgit
.util
.NB
;
49 /** Support for the pack index v2 format. */
50 class PackIndexV2
extends PackIndex
{
51 private static final long IS_O64
= 1L << 31;
53 private static final int FANOUT
= 256;
55 private static final int[] NO_INTS
= {};
57 private static final byte[] NO_BYTES
= {};
59 private long objectCnt
;
61 private final long[] fanoutTable
;
63 /** 256 arrays of contiguous object names. */
64 private int[][] names
;
66 /** 256 arrays of the 32 bit offset data, matching {@link #names}. */
67 private byte[][] offset32
;
69 /** 256 arrays of the CRC-32 of objects, matching {@link #names}. */
70 private byte[][] crc32
;
72 /** 64 bit offset table. */
73 private byte[] offset64
;
75 PackIndexV2(final InputStream fd
) throws IOException
{
76 final byte[] fanoutRaw
= new byte[4 * FANOUT
];
77 NB
.readFully(fd
, fanoutRaw
, 0, fanoutRaw
.length
);
78 fanoutTable
= new long[FANOUT
];
79 for (int k
= 0; k
< FANOUT
; k
++)
80 fanoutTable
[k
] = NB
.decodeUInt32(fanoutRaw
, k
* 4);
81 objectCnt
= fanoutTable
[FANOUT
- 1];
83 names
= new int[FANOUT
][];
84 offset32
= new byte[FANOUT
][];
85 crc32
= new byte[FANOUT
][];
87 // Object name table. The size we can permit per fan-out bucket
88 // is limited to Java's 2 GB per byte array limitation. That is
89 // no more than 107,374,182 objects per fan-out.
91 for (int k
= 0; k
< FANOUT
; k
++) {
94 bucketCnt
= fanoutTable
[k
];
96 bucketCnt
= fanoutTable
[k
] - fanoutTable
[k
- 1];
100 offset32
[k
] = NO_BYTES
;
105 final long nameLen
= bucketCnt
* Constants
.OBJECT_ID_LENGTH
;
106 if (nameLen
> Integer
.MAX_VALUE
)
107 throw new IOException("Index file is too large for jgit");
109 final int intNameLen
= (int) nameLen
;
110 final byte[] raw
= new byte[intNameLen
];
111 final int[] bin
= new int[intNameLen
>> 2];
112 NB
.readFully(fd
, raw
, 0, raw
.length
);
113 for (int i
= 0; i
< bin
.length
; i
++)
114 bin
[i
] = NB
.decodeInt32(raw
, i
<< 2);
117 offset32
[k
] = new byte[(int) (bucketCnt
* 4)];
118 crc32
[k
] = new byte[(int) (bucketCnt
* 4)];
122 for (int k
= 0; k
< FANOUT
; k
++)
123 NB
.readFully(fd
, crc32
[k
], 0, crc32
[k
].length
);
125 // 32 bit offset table. Any entries with the most significant bit
126 // set require a 64 bit offset entry in another table.
129 for (int k
= 0; k
< FANOUT
; k
++) {
130 final byte[] ofs
= offset32
[k
];
131 NB
.readFully(fd
, ofs
, 0, ofs
.length
);
132 for (int p
= 0; p
< ofs
.length
; p
+= 4)
137 // 64 bit offset table. Most objects should not require an entry.
140 offset64
= new byte[o64cnt
* 8];
141 NB
.readFully(fd
, offset64
, 0, offset64
.length
);
146 packChecksum
= new byte[20];
147 NB
.readFully(fd
, packChecksum
, 0, packChecksum
.length
);
151 long getObjectCount() {
156 long getOffset64Count() {
157 return offset64
.length
/ 8;
161 ObjectId
getObjectId(final long nthPosition
) {
162 int levelOne
= Arrays
.binarySearch(fanoutTable
, nthPosition
+ 1);
165 // If we hit the bucket exactly the item is in the bucket, or
166 // any bucket before it which has the same object count.
168 base
= fanoutTable
[levelOne
];
169 while (levelOne
> 0 && base
== fanoutTable
[levelOne
- 1])
172 // The item is in the bucket we would insert it into.
174 levelOne
= -(levelOne
+ 1);
177 base
= levelOne
> 0 ? fanoutTable
[levelOne
- 1] : 0;
178 final int p
= (int) (nthPosition
- base
);
179 final int p4
= p
<< 2;
180 return ObjectId
.fromRaw(names
[levelOne
], p4
+ p
); // p * 5
184 long findOffset(final AnyObjectId objId
) {
185 final int levelOne
= objId
.getFirstByte();
186 final int levelTwo
= binarySearchLevelTwo(objId
, levelOne
);
189 final long p
= NB
.decodeUInt32(offset32
[levelOne
], levelTwo
<< 2);
190 if ((p
& IS_O64
) != 0)
191 return NB
.decodeUInt64(offset64
, (8 * (int) (p
& ~IS_O64
)));
196 long findCRC32(AnyObjectId objId
) throws MissingObjectException
{
197 final int levelOne
= objId
.getFirstByte();
198 final int levelTwo
= binarySearchLevelTwo(objId
, levelOne
);
200 throw new MissingObjectException(objId
.copy(), "unknown");
201 return NB
.decodeUInt32(crc32
[levelOne
], levelTwo
<< 2);
205 boolean hasCRC32Support() {
209 public Iterator
<MutableEntry
> iterator() {
210 return new EntriesIteratorV2();
213 private int binarySearchLevelTwo(final AnyObjectId objId
, final int levelOne
) {
214 final int[] data
= names
[levelOne
];
215 int high
= offset32
[levelOne
].length
>> 2;
220 final int mid
= (low
+ high
) >> 1;
221 final int mid4
= mid
<< 2;
224 cmp
= objId
.compareTo(data
, mid4
+ mid
); // mid * 5
231 } while (low
< high
);
235 private class EntriesIteratorV2
extends EntriesIterator
{
236 private int levelOne
;
238 private int levelTwo
;
241 protected MutableEntry
initEntry() {
242 return new MutableEntry() {
243 protected void ensureId() {
244 idBuffer
.fromRaw(names
[levelOne
], levelTwo
245 - Constants
.OBJECT_ID_LENGTH
/ 4);
250 public MutableEntry
next() {
251 for (; levelOne
< names
.length
; levelOne
++) {
252 if (levelTwo
< names
[levelOne
].length
) {
253 int idx
= levelTwo
/ (Constants
.OBJECT_ID_LENGTH
/ 4) * 4;
254 long offset
= NB
.decodeUInt32(offset32
[levelOne
], idx
);
255 if ((offset
& IS_O64
) != 0) {
256 idx
= (8 * (int) (offset
& ~IS_O64
));
257 offset
= NB
.decodeUInt64(offset64
, idx
);
259 entry
.offset
= offset
;
261 levelTwo
+= Constants
.OBJECT_ID_LENGTH
/ 4;
267 throw new NoSuchElementException();