pack-objects: refer to delta objects by index instead of pointer
[git/git.git] / pack-objects.h
CommitLineData
2834bc27
VM
1#ifndef PACK_OBJECTS_H
2#define PACK_OBJECTS_H
3
43fa44fa
NTND
4#include "object-store.h"
5
0c6804ab 6#define OE_DFS_STATE_BITS 2
b5c0cbd8 7#define OE_DEPTH_BITS 12
43fa44fa 8#define OE_IN_PACK_BITS 10
0c6804ab
NTND
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 */
16enum dfs_state {
17 DFS_NONE = 0,
18 DFS_ACTIVE,
19 DFS_DONE,
20 DFS_NUM_STATES
21};
22
8d6ccce1
NTND
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 */
2834bc27
VM
68struct object_entry {
69 struct pack_idx_entry idx;
70 unsigned long size; /* uncompressed size */
43fa44fa 71 unsigned in_pack_idx:OE_IN_PACK_BITS; /* already in pack */
2834bc27 72 off_t in_pack_offset;
898eba5e
NTND
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 */
2834bc27
VM
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) */
fd9b1bae
NTND
81 unsigned type_:TYPE_BITS;
82 unsigned in_pack_type:TYPE_BITS; /* could be delta */
83 unsigned type_valid:1;
2834bc27
VM
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 */
0c6804ab 94 unsigned dfs_state:OE_DFS_STATE_BITS;
b5c0cbd8 95 unsigned depth:OE_DEPTH_BITS;
2834bc27
VM
96};
97
98struct packing_data {
99 struct object_entry *objects;
100 uint32_t nr_objects, nr_alloc;
101
102 int32_t *index;
103 uint32_t index_size;
06af3bba
NTND
104
105 unsigned int *in_pack_pos;
43fa44fa
NTND
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;
2834bc27
VM
115};
116
43fa44fa 117void prepare_packing_data(struct packing_data *pdata);
2834bc27
VM
118struct object_entry *packlist_alloc(struct packing_data *pdata,
119 const unsigned char *sha1,
120 uint32_t index_pos);
121
122struct object_entry *packlist_find(struct packing_data *pdata,
123 const unsigned char *sha1,
124 uint32_t *index_pos);
125
68fb36eb
VM
126static 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
fd9b1bae
NTND
146static inline enum object_type oe_type(const struct object_entry *e)
147{
148 return e->type_valid ? e->type_ : OBJ_BAD;
149}
150
151static 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
06af3bba
NTND
161static 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
167static 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
43fa44fa
NTND
174static 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
183void oe_map_new_pack(struct packing_data *pack,
184 struct packed_git *p);
185static 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
898eba5e
NTND
197static 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
206static 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
216static 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
225static 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
235static 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
244static 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
2834bc27 254#endif