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