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 { 70 struct pack_idx_entry idx; 71 unsigned long size; /* uncompressed size */ 72 unsigned in_pack_idx:OE_IN_PACK_BITS; /* already in pack */ 73 off_t in_pack_offset; 74 uint32_t delta_idx; /* delta base object */ 75 uint32_t delta_child_idx; /* deltified objects who bases me */ 76 uint32_t delta_sibling_idx; /* other deltified objects who 77 * uses the same base as me 78 */ 79 void *delta_data; /* cached delta (uncompressed) */ 80 unsigned long delta_size; /* delta data size (uncompressed) */ 81 unsigned z_delta_size:OE_Z_DELTA_BITS; 82 unsigned type_:TYPE_BITS; 83 unsigned in_pack_type:TYPE_BITS; /* could be delta */ 84 unsigned type_valid:1; 85 uint32_t hash; /* name hint hash */ 86 unsigned char in_pack_header_size; 87 unsigned 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 */ 92 unsigned no_try_delta:1; 93 unsigned tagged:1; /* near the very tip of refs */ 94 unsigned filled:1; /* assigned write-order */ 95 unsigned dfs_state:OE_DFS_STATE_BITS; 96 unsigned depth:OE_DEPTH_BITS; 97}; 98 99struct packing_data { 100 struct object_entry *objects; 101 uint32_t nr_objects, nr_alloc; 102 103 int32_t *index; 104 uint32_t index_size; 105 106 unsigned 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 */ 114 struct packed_git **in_pack_by_idx; 115 struct packed_git **in_pack; 116}; 117 118void prepare_packing_data(struct packing_data *pdata); 119struct object_entry *packlist_alloc(struct packing_data *pdata, 120 const unsigned char *sha1, 121 uint32_t index_pos); 122 123struct object_entry *packlist_find(struct packing_data *pdata, 124 const unsigned char *sha1, 125 uint32_t *index_pos); 126 127static inline uint32_t pack_name_hash(const char *name) 128{ 129 uint32_t c, hash = 0; 130 131 if (!name) 132 return 0; 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 */ 139 while ((c = *name++) != 0) { 140 if (isspace(c)) 141 continue; 142 hash = (hash >> 2) + (c << 24); 143 } 144 return hash; 145} 146 147static inline enum object_type oe_type(const struct object_entry *e) 148{ 149 return e->type_valid ? e->type_ : OBJ_BAD; 150} 151 152static inline void oe_set_type(struct object_entry *e, 153 enum object_type type) 154{ 155 if (type >= OBJ_ANY) 156 BUG("OBJ_ANY cannot be set in pack-objects code"); 157 158 e->type_valid = type >= OBJ_NONE; 159 e->type_ = (unsigned)type; 160} 161 162static inline unsigned int oe_in_pack_pos(const struct packing_data *pack, 163 const struct object_entry *e) 164{ 165 return pack->in_pack_pos[e - pack->objects]; 166} 167 168static inline void oe_set_in_pack_pos(const struct packing_data *pack, 169 const struct object_entry *e, 170 unsigned int pos) 171{ 172 pack->in_pack_pos[e - pack->objects] = pos; 173} 174 175static inline struct packed_git *oe_in_pack(const struct packing_data *pack, 176 const struct object_entry *e) 177{ 178 if (pack->in_pack_by_idx) 179 return pack->in_pack_by_idx[e->in_pack_idx]; 180 else 181 return pack->in_pack[e - pack->objects]; 182} 183 184void oe_map_new_pack(struct packing_data *pack, 185 struct packed_git *p); 186static inline void oe_set_in_pack(struct packing_data *pack, 187 struct object_entry *e, 188 struct packed_git *p) 189{ 190 if (!p->index) 191 oe_map_new_pack(pack, p); 192 if (pack->in_pack_by_idx) 193 e->in_pack_idx = p->index; 194 else 195 pack->in_pack[e - pack->objects] = p; 196} 197 198static inline struct object_entry *oe_delta( 199 const struct packing_data *pack, 200 const struct object_entry *e) 201{ 202 if (e->delta_idx) 203 return &pack->objects[e->delta_idx - 1]; 204 return NULL; 205} 206 207static inline void oe_set_delta(struct packing_data *pack, 208 struct object_entry *e, 209 struct object_entry *delta) 210{ 211 if (delta) 212 e->delta_idx = (delta - pack->objects) + 1; 213 else 214 e->delta_idx = 0; 215} 216 217static inline struct object_entry *oe_delta_child( 218 const struct packing_data *pack, 219 const struct object_entry *e) 220{ 221 if (e->delta_child_idx) 222 return &pack->objects[e->delta_child_idx - 1]; 223 return NULL; 224} 225 226static inline void oe_set_delta_child(struct packing_data *pack, 227 struct object_entry *e, 228 struct object_entry *delta) 229{ 230 if (delta) 231 e->delta_child_idx = (delta - pack->objects) + 1; 232 else 233 e->delta_child_idx = 0; 234} 235 236static inline struct object_entry *oe_delta_sibling( 237 const struct packing_data *pack, 238 const struct object_entry *e) 239{ 240 if (e->delta_sibling_idx) 241 return &pack->objects[e->delta_sibling_idx - 1]; 242 return NULL; 243} 244 245static inline void oe_set_delta_sibling(struct packing_data *pack, 246 struct object_entry *e, 247 struct object_entry *delta) 248{ 249 if (delta) 250 e->delta_sibling_idx = (delta - pack->objects) + 1; 251 else 252 e->delta_sibling_idx = 0; 253} 254 255#endif