1#include"cache.h" 2#include"pack-revindex.h" 3#include"object-store.h" 4#include"packfile.h" 5 6/* 7 * Pack index for existing packs give us easy access to the offsets into 8 * corresponding pack file where each object's data starts, but the entries 9 * do not store the size of the compressed representation (uncompressed 10 * size is easily available by examining the pack entry header). It is 11 * also rather expensive to find the sha1 for an object given its offset. 12 * 13 * The pack index file is sorted by object name mapping to offset; 14 * this revindex array is a list of offset/index_nr pairs 15 * ordered by offset, so if you know the offset of an object, next offset 16 * is where its packed representation ends and the index_nr can be used to 17 * get the object sha1 from the main index. 18 */ 19 20/* 21 * This is a least-significant-digit radix sort. 22 * 23 * It sorts each of the "n" items in "entries" by its offset field. The "max" 24 * parameter must be at least as large as the largest offset in the array, 25 * and lets us quit the sort early. 26 */ 27static voidsort_revindex(struct revindex_entry *entries,unsigned n, off_t max) 28{ 29/* 30 * We use a "digit" size of 16 bits. That keeps our memory 31 * usage reasonable, and we can generally (for a 4G or smaller 32 * packfile) quit after two rounds of radix-sorting. 33 */ 34#define DIGIT_SIZE (16) 35#define BUCKETS (1 << DIGIT_SIZE) 36/* 37 * We want to know the bucket that a[i] will go into when we are using 38 * the digit that is N bits from the (least significant) end. 39 */ 40#define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1)) 41 42/* 43 * We need O(n) temporary storage. Rather than do an extra copy of the 44 * partial results into "entries", we sort back and forth between the 45 * real array and temporary storage. In each iteration of the loop, we 46 * keep track of them with alias pointers, always sorting from "from" 47 * to "to". 48 */ 49struct revindex_entry *tmp, *from, *to; 50int bits; 51unsigned*pos; 52 53ALLOC_ARRAY(pos, BUCKETS); 54ALLOC_ARRAY(tmp, n); 55 from = entries; 56 to = tmp; 57 58/* 59 * If (max >> bits) is zero, then we know that the radix digit we are 60 * on (and any higher) will be zero for all entries, and our loop will 61 * be a no-op, as everybody lands in the same zero-th bucket. 62 */ 63for(bits =0; max >> bits; bits += DIGIT_SIZE) { 64unsigned i; 65 66memset(pos,0, BUCKETS *sizeof(*pos)); 67 68/* 69 * We want pos[i] to store the index of the last element that 70 * will go in bucket "i" (actually one past the last element). 71 * To do this, we first count the items that will go in each 72 * bucket, which gives us a relative offset from the last 73 * bucket. We can then cumulatively add the index from the 74 * previous bucket to get the true index. 75 */ 76for(i =0; i < n; i++) 77 pos[BUCKET_FOR(from, i, bits)]++; 78for(i =1; i < BUCKETS; i++) 79 pos[i] += pos[i-1]; 80 81/* 82 * Now we can drop the elements into their correct buckets (in 83 * our temporary array). We iterate the pos counter backwards 84 * to avoid using an extra index to count up. And since we are 85 * going backwards there, we must also go backwards through the 86 * array itself, to keep the sort stable. 87 * 88 * Note that we use an unsigned iterator to make sure we can 89 * handle 2^32-1 objects, even on a 32-bit system. But this 90 * means we cannot use the more obvious "i >= 0" loop condition 91 * for counting backwards, and must instead check for 92 * wrap-around with UINT_MAX. 93 */ 94for(i = n -1; i != UINT_MAX; i--) 95 to[--pos[BUCKET_FOR(from, i, bits)]] = from[i]; 96 97/* 98 * Now "to" contains the most sorted list, so we swap "from" and 99 * "to" for the next iteration. 100 */ 101SWAP(from, to); 102} 103 104/* 105 * If we ended with our data in the original array, great. If not, 106 * we have to move it back from the temporary storage. 107 */ 108if(from != entries) 109COPY_ARRAY(entries, tmp, n); 110free(tmp); 111free(pos); 112 113#undef BUCKET_FOR 114#undef BUCKETS 115#undef DIGIT_SIZE 116} 117 118/* 119 * Ordered list of offsets of objects in the pack. 120 */ 121static voidcreate_pack_revindex(struct packed_git *p) 122{ 123const unsigned num_ent = p->num_objects; 124unsigned i; 125const char*index = p->index_data; 126const unsigned hashsz = the_hash_algo->rawsz; 127 128ALLOC_ARRAY(p->revindex, num_ent +1); 129 index +=4*256; 130 131if(p->index_version >1) { 132const uint32_t*off_32 = 133(uint32_t*)(index +8+ p->num_objects * (hashsz +4)); 134const uint32_t*off_64 = off_32 + p->num_objects; 135for(i =0; i < num_ent; i++) { 136const uint32_t off =ntohl(*off_32++); 137if(!(off &0x80000000)) { 138 p->revindex[i].offset = off; 139}else{ 140 p->revindex[i].offset =get_be64(off_64); 141 off_64 +=2; 142} 143 p->revindex[i].nr = i; 144} 145}else{ 146for(i =0; i < num_ent; i++) { 147const uint32_t hl = *((uint32_t*)(index + (hashsz +4) * i)); 148 p->revindex[i].offset =ntohl(hl); 149 p->revindex[i].nr = i; 150} 151} 152 153/* 154 * This knows the pack format -- the hash trailer 155 * follows immediately after the last object data. 156 */ 157 p->revindex[num_ent].offset = p->pack_size - hashsz; 158 p->revindex[num_ent].nr = -1; 159sort_revindex(p->revindex, num_ent, p->pack_size); 160} 161 162intload_pack_revindex(struct packed_git *p) 163{ 164if(!p->revindex) { 165if(open_pack_index(p)) 166return-1; 167create_pack_revindex(p); 168} 169return0; 170} 171 172intfind_revindex_position(struct packed_git *p, off_t ofs) 173{ 174int lo =0; 175int hi = p->num_objects +1; 176const struct revindex_entry *revindex = p->revindex; 177 178do{ 179const unsigned mi = lo + (hi - lo) /2; 180if(revindex[mi].offset == ofs) { 181return mi; 182}else if(ofs < revindex[mi].offset) 183 hi = mi; 184else 185 lo = mi +1; 186}while(lo < hi); 187 188error("bad offset for revindex"); 189return-1; 190} 191 192struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs) 193{ 194int pos; 195 196if(load_pack_revindex(p)) 197return NULL; 198 199 pos =find_revindex_position(p, ofs); 200 201if(pos <0) 202return NULL; 203 204return p->revindex + pos; 205}