2 #include "split-index.h"
5 struct split_index
*init_split_index(struct index_state
*istate
)
7 if (!istate
->split_index
) {
8 istate
->split_index
= xcalloc(1, sizeof(*istate
->split_index
));
9 istate
->split_index
->refcount
= 1;
11 return istate
->split_index
;
14 int read_link_extension(struct index_state
*istate
,
15 const void *data_
, unsigned long sz
)
17 const unsigned char *data
= data_
;
18 struct split_index
*si
;
22 return error("corrupt link extension (too short)");
23 si
= init_split_index(istate
);
24 hashcpy(si
->base_sha1
, data
);
29 si
->delete_bitmap
= ewah_new();
30 ret
= ewah_read_mmap(si
->delete_bitmap
, data
, sz
);
32 return error("corrupt delete bitmap in link extension");
35 si
->replace_bitmap
= ewah_new();
36 ret
= ewah_read_mmap(si
->replace_bitmap
, data
, sz
);
38 return error("corrupt replace bitmap in link extension");
40 return error("garbage at the end of link extension");
44 int write_link_extension(struct strbuf
*sb
,
45 struct index_state
*istate
)
47 struct split_index
*si
= istate
->split_index
;
48 strbuf_add(sb
, si
->base_sha1
, 20);
49 if (!si
->delete_bitmap
&& !si
->replace_bitmap
)
51 ewah_serialize_strbuf(si
->delete_bitmap
, sb
);
52 ewah_serialize_strbuf(si
->replace_bitmap
, sb
);
56 static void mark_base_index_entries(struct index_state
*base
)
60 * To keep track of the shared entries between
61 * istate->base->cache[] and istate->cache[], base entry
62 * position is stored in each base entry. All positions start
63 * from 1 instead of 0, which is reserved to say "this is a new
66 for (i
= 0; i
< base
->cache_nr
; i
++)
67 base
->cache
[i
]->index
= i
+ 1;
70 void move_cache_to_base_index(struct index_state
*istate
)
72 struct split_index
*si
= istate
->split_index
;
76 * If "si" is shared with another index_state (e.g. by
77 * unpack-trees code), we will need to duplicate split_index
78 * struct. It's not happening now though, luckily.
80 assert(si
->refcount
<= 1);
82 unshare_split_index(istate
, 0);
84 discard_index(si
->base
);
87 si
->base
= xcalloc(1, sizeof(*si
->base
));
88 si
->base
->version
= istate
->version
;
89 /* zero timestamp disables racy test in ce_write_index() */
90 si
->base
->timestamp
= istate
->timestamp
;
91 ALLOC_GROW(si
->base
->cache
, istate
->cache_nr
, si
->base
->cache_alloc
);
92 si
->base
->cache_nr
= istate
->cache_nr
;
93 COPY_ARRAY(si
->base
->cache
, istate
->cache
, istate
->cache_nr
);
94 mark_base_index_entries(si
->base
);
95 for (i
= 0; i
< si
->base
->cache_nr
; i
++)
96 si
->base
->cache
[i
]->ce_flags
&= ~CE_UPDATE_IN_BASE
;
99 static void mark_entry_for_delete(size_t pos
, void *data
)
101 struct index_state
*istate
= data
;
102 if (pos
>= istate
->cache_nr
)
103 die("position for delete %d exceeds base index size %d",
104 (int)pos
, istate
->cache_nr
);
105 istate
->cache
[pos
]->ce_flags
|= CE_REMOVE
;
106 istate
->split_index
->nr_deletions
= 1;
109 static void replace_entry(size_t pos
, void *data
)
111 struct index_state
*istate
= data
;
112 struct split_index
*si
= istate
->split_index
;
113 struct cache_entry
*dst
, *src
;
115 if (pos
>= istate
->cache_nr
)
116 die("position for replacement %d exceeds base index size %d",
117 (int)pos
, istate
->cache_nr
);
118 if (si
->nr_replacements
>= si
->saved_cache_nr
)
119 die("too many replacements (%d vs %d)",
120 si
->nr_replacements
, si
->saved_cache_nr
);
121 dst
= istate
->cache
[pos
];
122 if (dst
->ce_flags
& CE_REMOVE
)
123 die("entry %d is marked as both replaced and deleted",
125 src
= si
->saved_cache
[si
->nr_replacements
];
127 die("corrupt link extension, entry %d should have "
128 "zero length name", (int)pos
);
129 src
->index
= pos
+ 1;
130 src
->ce_flags
|= CE_UPDATE_IN_BASE
;
131 src
->ce_namelen
= dst
->ce_namelen
;
132 copy_cache_entry(dst
, src
);
134 si
->nr_replacements
++;
137 void merge_base_index(struct index_state
*istate
)
139 struct split_index
*si
= istate
->split_index
;
142 mark_base_index_entries(si
->base
);
144 si
->saved_cache
= istate
->cache
;
145 si
->saved_cache_nr
= istate
->cache_nr
;
146 istate
->cache_nr
= si
->base
->cache_nr
;
147 istate
->cache
= NULL
;
148 istate
->cache_alloc
= 0;
149 ALLOC_GROW(istate
->cache
, istate
->cache_nr
, istate
->cache_alloc
);
150 COPY_ARRAY(istate
->cache
, si
->base
->cache
, istate
->cache_nr
);
152 si
->nr_deletions
= 0;
153 si
->nr_replacements
= 0;
154 ewah_each_bit(si
->replace_bitmap
, replace_entry
, istate
);
155 ewah_each_bit(si
->delete_bitmap
, mark_entry_for_delete
, istate
);
156 if (si
->nr_deletions
)
157 remove_marked_cache_entries(istate
);
159 for (i
= si
->nr_replacements
; i
< si
->saved_cache_nr
; i
++) {
160 if (!ce_namelen(si
->saved_cache
[i
]))
161 die("corrupt link extension, entry %d should "
162 "have non-zero length name", i
);
163 add_index_entry(istate
, si
->saved_cache
[i
],
164 ADD_CACHE_OK_TO_ADD
|
165 ADD_CACHE_KEEP_CACHE_TREE
|
167 * we may have to replay what
168 * merge-recursive.c:update_stages()
169 * does, which has this flag on
171 ADD_CACHE_SKIP_DFCHECK
);
172 si
->saved_cache
[i
] = NULL
;
175 ewah_free(si
->delete_bitmap
);
176 ewah_free(si
->replace_bitmap
);
177 FREE_AND_NULL(si
->saved_cache
);
178 si
->delete_bitmap
= NULL
;
179 si
->replace_bitmap
= NULL
;
180 si
->saved_cache_nr
= 0;
183 void prepare_to_write_split_index(struct index_state
*istate
)
185 struct split_index
*si
= init_split_index(istate
);
186 struct cache_entry
**entries
= NULL
, *ce
;
187 int i
, nr_entries
= 0, nr_alloc
= 0;
189 si
->delete_bitmap
= ewah_new();
190 si
->replace_bitmap
= ewah_new();
193 /* Go through istate->cache[] and mark CE_MATCHED to
194 * entry with positive index. We'll go through
195 * base->cache[] later to delete all entries in base
196 * that are not marked with either CE_MATCHED or
197 * CE_UPDATE_IN_BASE. If istate->cache[i] is a
198 * duplicate, deduplicate it.
200 for (i
= 0; i
< istate
->cache_nr
; i
++) {
201 struct cache_entry
*base
;
202 /* namelen is checked separately */
203 const unsigned int ondisk_flags
=
204 CE_STAGEMASK
| CE_VALID
| CE_EXTENDED_FLAGS
;
205 unsigned int ce_flags
, base_flags
, ret
;
206 ce
= istate
->cache
[i
];
209 if (ce
->index
> si
->base
->cache_nr
) {
213 ce
->ce_flags
|= CE_MATCHED
; /* or "shared" */
214 base
= si
->base
->cache
[ce
->index
- 1];
217 if (ce
->ce_namelen
!= base
->ce_namelen
||
218 strcmp(ce
->name
, base
->name
)) {
222 ce_flags
= ce
->ce_flags
;
223 base_flags
= base
->ce_flags
;
224 /* only on-disk flags matter */
225 ce
->ce_flags
&= ondisk_flags
;
226 base
->ce_flags
&= ondisk_flags
;
227 ret
= memcmp(&ce
->ce_stat_data
, &base
->ce_stat_data
,
228 offsetof(struct cache_entry
, name
) -
229 offsetof(struct cache_entry
, ce_stat_data
));
230 ce
->ce_flags
= ce_flags
;
231 base
->ce_flags
= base_flags
;
233 ce
->ce_flags
|= CE_UPDATE_IN_BASE
;
235 si
->base
->cache
[ce
->index
- 1] = ce
;
237 for (i
= 0; i
< si
->base
->cache_nr
; i
++) {
238 ce
= si
->base
->cache
[i
];
239 if ((ce
->ce_flags
& CE_REMOVE
) ||
240 !(ce
->ce_flags
& CE_MATCHED
))
241 ewah_set(si
->delete_bitmap
, i
);
242 else if (ce
->ce_flags
& CE_UPDATE_IN_BASE
) {
243 ewah_set(si
->replace_bitmap
, i
);
244 ce
->ce_flags
|= CE_STRIP_NAME
;
245 ALLOC_GROW(entries
, nr_entries
+1, nr_alloc
);
246 entries
[nr_entries
++] = ce
;
251 for (i
= 0; i
< istate
->cache_nr
; i
++) {
252 ce
= istate
->cache
[i
];
253 if ((!si
->base
|| !ce
->index
) && !(ce
->ce_flags
& CE_REMOVE
)) {
254 assert(!(ce
->ce_flags
& CE_STRIP_NAME
));
255 ALLOC_GROW(entries
, nr_entries
+1, nr_alloc
);
256 entries
[nr_entries
++] = ce
;
258 ce
->ce_flags
&= ~CE_MATCHED
;
262 * take cache[] out temporarily, put entries[] in its place
265 si
->saved_cache
= istate
->cache
;
266 si
->saved_cache_nr
= istate
->cache_nr
;
267 istate
->cache
= entries
;
268 istate
->cache_nr
= nr_entries
;
271 void finish_writing_split_index(struct index_state
*istate
)
273 struct split_index
*si
= init_split_index(istate
);
275 ewah_free(si
->delete_bitmap
);
276 ewah_free(si
->replace_bitmap
);
277 si
->delete_bitmap
= NULL
;
278 si
->replace_bitmap
= NULL
;
280 istate
->cache
= si
->saved_cache
;
281 istate
->cache_nr
= si
->saved_cache_nr
;
284 void unshare_split_index(struct index_state
*istate
, int discard
)
286 struct split_index
*si
= istate
->split_index
;
289 if (!si
|| !si
->base
)
292 for (i
= 0; i
< istate
->cache_nr
; i
++) {
293 struct cache_entry
*ce
= istate
->cache
[i
];
294 struct cache_entry
*new = NULL
;
297 ce
->index
> si
->base
->cache_nr
||
298 ce
!= si
->base
->cache
[ce
->index
- 1])
302 int len
= ce_namelen(ce
);
303 new = xcalloc(1, cache_entry_size(len
));
304 copy_cache_entry(new, ce
);
305 memcpy(new->name
, ce
->name
, len
);
308 istate
->cache
[i
] = new;
313 void discard_split_index(struct index_state
*istate
)
315 struct split_index
*si
= istate
->split_index
;
318 unshare_split_index(istate
, 0);
319 istate
->split_index
= NULL
;
324 discard_index(si
->base
);
330 void save_or_free_index_entry(struct index_state
*istate
, struct cache_entry
*ce
)
333 istate
->split_index
&&
334 istate
->split_index
->base
&&
335 ce
->index
<= istate
->split_index
->base
->cache_nr
&&
336 ce
== istate
->split_index
->base
->cache
[ce
->index
- 1])
337 ce
->ce_flags
|= CE_REMOVE
;
342 void replace_index_entry_in_base(struct index_state
*istate
,
343 struct cache_entry
*old
,
344 struct cache_entry
*new)
347 istate
->split_index
&&
348 istate
->split_index
->base
&&
349 old
->index
<= istate
->split_index
->base
->cache_nr
) {
350 new->index
= old
->index
;
351 if (old
!= istate
->split_index
->base
->cache
[new->index
- 1])
352 free(istate
->split_index
->base
->cache
[new->index
- 1]);
353 istate
->split_index
->base
->cache
[new->index
- 1] = new;
357 void add_split_index(struct index_state
*istate
)
359 if (!istate
->split_index
) {
360 init_split_index(istate
);
361 istate
->cache_changed
|= SPLIT_INDEX_ORDERED
;
365 void remove_split_index(struct index_state
*istate
)
367 if (!istate
->split_index
)
369 discard_split_index(istate
);
370 istate
->cache_changed
|= SOMETHING_CHANGED
;