1 #ifndef PACK_REVINDEX_H 2 #define PACK_REVINDEX_H 3 4 /** 5 * A revindex allows converting efficiently between three properties 6 * of an object within a pack: 7 * 8 * - index position: the numeric position within the list of sorted object ids 9 * found in the .idx file 10 * 11 * - pack position: the numeric position within the list of objects in their 12 * order within the actual .pack file (i.e., 0 is the first object in the 13 * .pack, 1 is the second, and so on) 14 * 15 * - offset: the byte offset within the .pack file at which the object contents 16 * can be found 17 * 18 * The revindex can also be used with a multi-pack index (MIDX). In this 19 * setting: 20 * 21 * - index position refers to an object's numeric position within the MIDX 22 * 23 * - pack position refers to an object's position within a non-existent pack 24 * described by the MIDX. The pack structure is described in 25 * Documentation/technical/pack-format.txt. 26 * 27 * It is effectively a concatanation of all packs in the MIDX (ordered by 28 * their numeric ID within the MIDX) in their original order within each 29 * pack), removing duplicates, and placing the preferred pack (if any) 30 * first. 31 */ 32 33 34 #define RIDX_SIGNATURE 0x52494458 /* "RIDX" */ 35 #define RIDX_VERSION 1 36 37 #define GIT_TEST_WRITE_REV_INDEX "GIT_TEST_WRITE_REV_INDEX" 38 #define GIT_TEST_REV_INDEX_DIE_IN_MEMORY "GIT_TEST_REV_INDEX_DIE_IN_MEMORY" 39 40 struct packed_git; 41 struct multi_pack_index; 42 43 /* 44 * load_pack_revindex populates the revindex's internal data-structures for the 45 * given pack, returning zero on success and a negative value otherwise. 46 * 47 * If a '.rev' file is present it is mmap'd, and pointers are assigned into it 48 * (instead of using the in-memory variant). 49 */ 50 int load_pack_revindex(struct packed_git *p); 51 52 /* 53 * load_midx_revindex loads the '.rev' file corresponding to the given 54 * multi-pack index by mmap-ing it and assigning pointers in the 55 * multi_pack_index to point at it. 56 * 57 * A negative number is returned on error. 58 */ 59 int load_midx_revindex(struct multi_pack_index *m); 60 61 /* 62 * Frees resources associated with a multi-pack reverse index. 63 * 64 * A negative number is returned on error. 65 */ 66 int close_midx_revindex(struct multi_pack_index *m); 67 68 /* 69 * offset_to_pack_pos converts an object offset to a pack position. This 70 * function returns zero on success, and a negative number otherwise. The 71 * parameter 'pos' is usable only on success. 72 * 73 * If the reverse index has not yet been loaded, this function loads it lazily, 74 * and returns an negative number if an error was encountered. 75 * 76 * This function runs in time O(log N) with the number of objects in the pack. 77 */ 78 int offset_to_pack_pos(struct packed_git *p, off_t ofs, uint32_t *pos); 79 80 /* 81 * pack_pos_to_index converts the given pack-relative position 'pos' by 82 * returning an index-relative position. 83 * 84 * If the reverse index has not yet been loaded, or the position is out of 85 * bounds, this function aborts. 86 * 87 * This function runs in constant time. 88 */ 89 uint32_t pack_pos_to_index(struct packed_git *p, uint32_t pos); 90 91 /* 92 * pack_pos_to_offset converts the given pack-relative position 'pos' into a 93 * pack offset. For a pack with 'N' objects, asking for position 'N' will return 94 * the total size (in bytes) of the pack. 95 * 96 * If the reverse index has not yet been loaded, or the position is out of 97 * bounds, this function aborts. 98 * 99 * This function runs in constant time under both in-memory and on-disk reverse 100 * indexes, but an additional step is taken to consult the corresponding .idx 101 * file when using the on-disk format. 102 */ 103 off_t pack_pos_to_offset(struct packed_git *p, uint32_t pos); 104 105 /* 106 * pack_pos_to_midx converts the object at position "pos" within the MIDX 107 * pseudo-pack into a MIDX position. 108 * 109 * If the reverse index has not yet been loaded, or the position is out of 110 * bounds, this function aborts. 111 * 112 * This function runs in constant time. 113 */ 114 uint32_t pack_pos_to_midx(struct multi_pack_index *m, uint32_t pos); 115 116 /* 117 * midx_to_pack_pos converts from the MIDX-relative position at "at" to the 118 * corresponding pack position. 119 * 120 * If the reverse index has not yet been loaded, or the position is out of 121 * bounds, this function aborts. 122 * 123 * This function runs in time O(log N) with the number of objects in the MIDX. 124 */ 125 int midx_to_pack_pos(struct multi_pack_index *midx, uint32_t at, uint32_t *pos); 126 127 #endif 128