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
.EOFException
;
41 import java
.io
.IOException
;
42 import java
.io
.InputStream
;
43 import java
.util
.Arrays
;
44 import java
.util
.Iterator
;
45 import java
.util
.NoSuchElementException
;
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 /** 64 bit offset table. */
70 private byte[] offset64
;
72 PackIndexV2(final InputStream fd
) throws IOException
{
73 final byte[] fanoutRaw
= new byte[4 * FANOUT
];
74 NB
.readFully(fd
, fanoutRaw
, 0, fanoutRaw
.length
);
75 fanoutTable
= new long[FANOUT
];
76 for (int k
= 0; k
< FANOUT
; k
++)
77 fanoutTable
[k
] = NB
.decodeUInt32(fanoutRaw
, k
* 4);
78 objectCnt
= fanoutTable
[FANOUT
- 1];
80 names
= new int[FANOUT
][];
81 offset32
= new byte[FANOUT
][];
83 // Object name table. The size we can permit per fan-out bucket
84 // is limited to Java's 2 GB per byte array limitation. That is
85 // no more than 107,374,182 objects per fan-out.
87 for (int k
= 0; k
< FANOUT
; k
++) {
90 bucketCnt
= fanoutTable
[k
];
92 bucketCnt
= fanoutTable
[k
] - fanoutTable
[k
- 1];
96 offset32
[k
] = NO_BYTES
;
100 final long nameLen
= bucketCnt
* Constants
.OBJECT_ID_LENGTH
;
101 if (nameLen
> Integer
.MAX_VALUE
)
102 throw new IOException("Index file is too large for jgit");
104 final int intNameLen
= (int) nameLen
;
105 final byte[] raw
= new byte[intNameLen
];
106 final int[] bin
= new int[intNameLen
>> 2];
107 NB
.readFully(fd
, raw
, 0, raw
.length
);
108 for (int i
= 0; i
< bin
.length
; i
++)
109 bin
[i
] = NB
.decodeInt32(raw
, i
<< 2);
112 offset32
[k
] = new byte[(int) (bucketCnt
* 4)];
115 // CRC32 table. Currently unused.
117 skipFully(fd
, objectCnt
* 4);
119 // 32 bit offset table. Any entries with the most significant bit
120 // set require a 64 bit offset entry in another table.
123 for (int k
= 0; k
< FANOUT
; k
++) {
124 final byte[] ofs
= offset32
[k
];
125 NB
.readFully(fd
, ofs
, 0, ofs
.length
);
126 for (int p
= 0; p
< ofs
.length
; p
+= 4)
131 // 64 bit offset table. Most objects should not require an entry.
134 offset64
= new byte[o64cnt
* 8];
135 NB
.readFully(fd
, offset64
, 0, offset64
.length
);
141 private static void skipFully(final InputStream fd
, long toSkip
)
144 final long r
= fd
.skip(toSkip
);
146 throw new EOFException("Cannot skip index section.");
152 long getObjectCount() {
157 long getOffset64Count() {
158 return offset64
.length
/ 8;
162 ObjectId
getObjectId(final long nthPosition
) {
163 int levelOne
= Arrays
.binarySearch(fanoutTable
, nthPosition
+ 1);
166 // If we hit the bucket exactly the item is in the bucket, or
167 // any bucket before it which has the same object count.
169 base
= fanoutTable
[levelOne
];
170 while (levelOne
> 0 && base
== fanoutTable
[levelOne
- 1])
173 // The item is in the bucket we would insert it into.
175 levelOne
= -(levelOne
+ 1);
178 base
= levelOne
> 0 ? fanoutTable
[levelOne
- 1] : 0;
179 final int p
= (int) (nthPosition
- base
);
180 final int p4
= p
<< 2;
181 return ObjectId
.fromRaw(names
[levelOne
], p4
+ p
); // p * 5
185 long findOffset(final AnyObjectId objId
) {
186 final int levelOne
= objId
.getFirstByte();
187 final int levelTwo
= binarySearchLevelTwo(objId
, levelOne
);
190 final long p
= NB
.decodeUInt32(offset32
[levelOne
], levelTwo
<< 2);
191 if ((p
& IS_O64
) != 0)
192 return NB
.decodeUInt64(offset64
, (8 * (int) (p
& ~IS_O64
)));
196 public Iterator
<MutableEntry
> iterator() {
197 return new EntriesIteratorV2();
200 private int binarySearchLevelTwo(final AnyObjectId objId
, final int levelOne
) {
201 final int[] data
= names
[levelOne
];
202 int high
= offset32
[levelOne
].length
>> 2;
207 final int mid
= (low
+ high
) >> 1;
208 final int mid4
= mid
<< 2;
211 cmp
= objId
.compareTo(data
, mid4
+ mid
); // mid * 5
218 } while (low
< high
);
222 private class EntriesIteratorV2
extends EntriesIterator
{
223 private int levelOne
;
225 private int levelTwo
;
227 public MutableEntry
next() {
228 for (; levelOne
< names
.length
; levelOne
++) {
229 if (levelTwo
< names
[levelOne
].length
) {
230 objectId
.fromRaw(names
[levelOne
], levelTwo
);
231 int arrayIdx
= levelTwo
/ (Constants
.OBJECT_ID_LENGTH
/ 4)
233 long offset
= NB
.decodeUInt32(offset32
[levelOne
], arrayIdx
);
234 if ((offset
& IS_O64
) != 0) {
235 arrayIdx
= (8 * (int) (offset
& ~IS_O64
));
236 offset
= NB
.decodeUInt64(offset64
, arrayIdx
);
238 objectId
.setOffset(offset
);
240 levelTwo
+= Constants
.OBJECT_ID_LENGTH
/ 4;
247 throw new NoSuchElementException();