1#ifndef PACK_OBJECTS_H 2#define PACK_OBJECTS_H 3 4#include"object-store.h" 5 6#define OE_DFS_STATE_BITS 2 7#define OE_DEPTH_BITS 12 8#define OE_IN_PACK_BITS 10 9#define OE_Z_DELTA_BITS 20 10 11/* 12 * State flags for depth-first search used for analyzing delta cycles. 13 * 14 * The depth is measured in delta-links to the base (so if A is a delta 15 * against B, then A has a depth of 1, and B a depth of 0). 16 */ 17enum dfs_state { 18 DFS_NONE =0, 19 DFS_ACTIVE, 20 DFS_DONE, 21 DFS_NUM_STATES 22}; 23 24/* 25 * basic object info 26 * ----------------- 27 * idx.oid is filled up before delta searching starts. idx.crc32 is 28 * only valid after the object is written out and will be used for 29 * generating the index. idx.offset will be both gradually set and 30 * used in writing phase (base objects get offset first, then deltas 31 * refer to them) 32 * 33 * "size" is the uncompressed object size. Compressed size of the raw 34 * data for an object in a pack is not stored anywhere but is computed 35 * and made available when reverse .idx is made. 36 * 37 * "hash" contains a path name hash which is used for sorting the 38 * delta list and also during delta searching. Once prepare_pack() 39 * returns it's no longer needed. 40 * 41 * source pack info 42 * ---------------- 43 * The (in_pack, in_pack_offset) tuple contains the location of the 44 * object in the source pack. in_pack_header_size allows quickly 45 * skipping the header and going straight to the zlib stream. 46 * 47 * "type" and "in_pack_type" both describe object type. in_pack_type 48 * may contain a delta type, while type is always the canonical type. 49 * 50 * deltas 51 * ------ 52 * Delta links (delta, delta_child and delta_sibling) are created to 53 * reflect that delta graph from the source pack then updated or added 54 * during delta searching phase when we find better deltas. 55 * 56 * delta_child and delta_sibling are last needed in 57 * compute_write_order(). "delta" and "delta_size" must remain valid 58 * at object writing phase in case the delta is not cached. 59 * 60 * If a delta is cached in memory and is compressed, delta_data points 61 * to the data and z_delta_size contains the compressed size. If it's 62 * uncompressed [1], z_delta_size must be zero. delta_size is always 63 * the uncompressed size and must be valid even if the delta is not 64 * cached. 65 * 66 * [1] during try_delta phase we don't bother with compressing because 67 * the delta could be quickly replaced with a better one. 68 */ 69struct object_entry { 70struct pack_idx_entry idx; 71unsigned long size;/* uncompressed size */ 72unsigned in_pack_idx:OE_IN_PACK_BITS;/* already in pack */ 73 off_t in_pack_offset; 74uint32_t delta_idx;/* delta base object */ 75uint32_t delta_child_idx;/* deltified objects who bases me */ 76uint32_t delta_sibling_idx;/* other deltified objects who 77 * uses the same base as me 78 */ 79void*delta_data;/* cached delta (uncompressed) */ 80unsigned long delta_size;/* delta data size (uncompressed) */ 81unsigned z_delta_size:OE_Z_DELTA_BITS; 82unsigned type_:TYPE_BITS; 83unsigned in_pack_type:TYPE_BITS;/* could be delta */ 84unsigned type_valid:1; 85uint32_t hash;/* name hint hash */ 86unsigned char in_pack_header_size; 87unsigned preferred_base:1;/* 88 * we do not pack this, but is available 89 * to be used as the base object to delta 90 * objects against. 91 */ 92unsigned no_try_delta:1; 93unsigned tagged:1;/* near the very tip of refs */ 94unsigned filled:1;/* assigned write-order */ 95unsigned dfs_state:OE_DFS_STATE_BITS; 96unsigned depth:OE_DEPTH_BITS; 97}; 98 99struct packing_data { 100struct object_entry *objects; 101uint32_t nr_objects, nr_alloc; 102 103int32_t*index; 104uint32_t index_size; 105 106unsigned int*in_pack_pos; 107 108/* 109 * Only one of these can be non-NULL and they have different 110 * sizes. if in_pack_by_idx is allocated, oe_in_pack() returns 111 * the pack of an object using in_pack_idx field. If not, 112 * in_pack[] array is used the same way as in_pack_pos[] 113 */ 114struct packed_git **in_pack_by_idx; 115struct packed_git **in_pack; 116}; 117 118voidprepare_packing_data(struct packing_data *pdata); 119struct object_entry *packlist_alloc(struct packing_data *pdata, 120const unsigned char*sha1, 121uint32_t index_pos); 122 123struct object_entry *packlist_find(struct packing_data *pdata, 124const unsigned char*sha1, 125uint32_t*index_pos); 126 127staticinlineuint32_tpack_name_hash(const char*name) 128{ 129uint32_t c, hash =0; 130 131if(!name) 132return0; 133 134/* 135 * This effectively just creates a sortable number from the 136 * last sixteen non-whitespace characters. Last characters 137 * count "most", so things that end in ".c" sort together. 138 */ 139while((c = *name++) !=0) { 140if(isspace(c)) 141continue; 142 hash = (hash >>2) + (c <<24); 143} 144return hash; 145} 146 147staticinlineenum object_type oe_type(const struct object_entry *e) 148{ 149return e->type_valid ? e->type_ : OBJ_BAD; 150} 151 152staticinlinevoidoe_set_type(struct object_entry *e, 153enum object_type type) 154{ 155if(type >= OBJ_ANY) 156BUG("OBJ_ANY cannot be set in pack-objects code"); 157 158 e->type_valid = type >= OBJ_NONE; 159 e->type_ = (unsigned)type; 160} 161 162staticinlineunsigned intoe_in_pack_pos(const struct packing_data *pack, 163const struct object_entry *e) 164{ 165return pack->in_pack_pos[e - pack->objects]; 166} 167 168staticinlinevoidoe_set_in_pack_pos(const struct packing_data *pack, 169const struct object_entry *e, 170unsigned int pos) 171{ 172 pack->in_pack_pos[e - pack->objects] = pos; 173} 174 175staticinlinestruct packed_git *oe_in_pack(const struct packing_data *pack, 176const struct object_entry *e) 177{ 178if(pack->in_pack_by_idx) 179return pack->in_pack_by_idx[e->in_pack_idx]; 180else 181return pack->in_pack[e - pack->objects]; 182} 183 184voidoe_map_new_pack(struct packing_data *pack, 185struct packed_git *p); 186staticinlinevoidoe_set_in_pack(struct packing_data *pack, 187struct object_entry *e, 188struct packed_git *p) 189{ 190if(!p->index) 191oe_map_new_pack(pack, p); 192if(pack->in_pack_by_idx) 193 e->in_pack_idx = p->index; 194else 195 pack->in_pack[e - pack->objects] = p; 196} 197 198staticinlinestruct object_entry *oe_delta( 199const struct packing_data *pack, 200const struct object_entry *e) 201{ 202if(e->delta_idx) 203return&pack->objects[e->delta_idx -1]; 204return NULL; 205} 206 207staticinlinevoidoe_set_delta(struct packing_data *pack, 208struct object_entry *e, 209struct object_entry *delta) 210{ 211if(delta) 212 e->delta_idx = (delta - pack->objects) +1; 213else 214 e->delta_idx =0; 215} 216 217staticinlinestruct object_entry *oe_delta_child( 218const struct packing_data *pack, 219const struct object_entry *e) 220{ 221if(e->delta_child_idx) 222return&pack->objects[e->delta_child_idx -1]; 223return NULL; 224} 225 226staticinlinevoidoe_set_delta_child(struct packing_data *pack, 227struct object_entry *e, 228struct object_entry *delta) 229{ 230if(delta) 231 e->delta_child_idx = (delta - pack->objects) +1; 232else 233 e->delta_child_idx =0; 234} 235 236staticinlinestruct object_entry *oe_delta_sibling( 237const struct packing_data *pack, 238const struct object_entry *e) 239{ 240if(e->delta_sibling_idx) 241return&pack->objects[e->delta_sibling_idx -1]; 242return NULL; 243} 244 245staticinlinevoidoe_set_delta_sibling(struct packing_data *pack, 246struct object_entry *e, 247struct object_entry *delta) 248{ 249if(delta) 250 e->delta_sibling_idx = (delta - pack->objects) +1; 251else 252 e->delta_sibling_idx =0; 253} 254 255#endif