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 static int write_strbuf(void *user_data
, const void *data
, size_t len
)
46 struct strbuf
*sb
= user_data
;
47 strbuf_add(sb
, data
, len
);
51 int write_link_extension(struct strbuf
*sb
,
52 struct index_state
*istate
)
54 struct split_index
*si
= istate
->split_index
;
55 strbuf_add(sb
, si
->base_sha1
, 20);
56 if (!si
->delete_bitmap
&& !si
->replace_bitmap
)
58 ewah_serialize_to(si
->delete_bitmap
, write_strbuf
, sb
);
59 ewah_serialize_to(si
->replace_bitmap
, write_strbuf
, sb
);
63 static void mark_base_index_entries(struct index_state
*base
)
67 * To keep track of the shared entries between
68 * istate->base->cache[] and istate->cache[], base entry
69 * position is stored in each base entry. All positions start
70 * from 1 instead of 0, which is resrved to say "this is a new
73 for (i
= 0; i
< base
->cache_nr
; i
++)
74 base
->cache
[i
]->index
= i
+ 1;
77 static void mark_entry_for_delete(size_t pos
, void *data
)
79 struct index_state
*istate
= data
;
80 if (pos
>= istate
->cache_nr
)
81 die("position for delete %d exceeds base index size %d",
82 (int)pos
, istate
->cache_nr
);
83 istate
->cache
[pos
]->ce_flags
|= CE_REMOVE
;
84 istate
->split_index
->nr_deletions
= 1;
87 static void replace_entry(size_t pos
, void *data
)
89 struct index_state
*istate
= data
;
90 struct split_index
*si
= istate
->split_index
;
91 struct cache_entry
*dst
, *src
;
92 if (pos
>= istate
->cache_nr
)
93 die("position for replacement %d exceeds base index size %d",
94 (int)pos
, istate
->cache_nr
);
95 if (si
->nr_replacements
>= si
->saved_cache_nr
)
96 die("too many replacements (%d vs %d)",
97 si
->nr_replacements
, si
->saved_cache_nr
);
98 dst
= istate
->cache
[pos
];
99 if (dst
->ce_flags
& CE_REMOVE
)
100 die("entry %d is marked as both replaced and deleted",
102 src
= si
->saved_cache
[si
->nr_replacements
];
103 src
->index
= pos
+ 1;
104 src
->ce_flags
|= CE_UPDATE_IN_BASE
;
107 si
->nr_replacements
++;
110 void merge_base_index(struct index_state
*istate
)
112 struct split_index
*si
= istate
->split_index
;
115 mark_base_index_entries(si
->base
);
117 si
->saved_cache
= istate
->cache
;
118 si
->saved_cache_nr
= istate
->cache_nr
;
119 istate
->cache_nr
= si
->base
->cache_nr
;
120 istate
->cache
= NULL
;
121 istate
->cache_alloc
= 0;
122 ALLOC_GROW(istate
->cache
, istate
->cache_nr
, istate
->cache_alloc
);
123 memcpy(istate
->cache
, si
->base
->cache
,
124 sizeof(*istate
->cache
) * istate
->cache_nr
);
126 si
->nr_deletions
= 0;
127 si
->nr_replacements
= 0;
128 ewah_each_bit(si
->replace_bitmap
, replace_entry
, istate
);
129 ewah_each_bit(si
->delete_bitmap
, mark_entry_for_delete
, istate
);
130 if (si
->nr_deletions
)
131 remove_marked_cache_entries(istate
);
133 for (i
= si
->nr_replacements
; i
< si
->saved_cache_nr
; i
++) {
134 add_index_entry(istate
, si
->saved_cache
[i
],
135 ADD_CACHE_OK_TO_ADD
|
137 * we may have to replay what
138 * merge-recursive.c:update_stages()
139 * does, which has this flag on
141 ADD_CACHE_SKIP_DFCHECK
);
142 si
->saved_cache
[i
] = NULL
;
145 ewah_free(si
->delete_bitmap
);
146 ewah_free(si
->replace_bitmap
);
147 free(si
->saved_cache
);
148 si
->delete_bitmap
= NULL
;
149 si
->replace_bitmap
= NULL
;
150 si
->saved_cache
= NULL
;
151 si
->saved_cache_nr
= 0;
154 void prepare_to_write_split_index(struct index_state
*istate
)
156 struct split_index
*si
= init_split_index(istate
);
157 struct cache_entry
**entries
= NULL
, *ce
;
158 int i
, nr_entries
= 0, nr_alloc
= 0;
160 si
->delete_bitmap
= ewah_new();
161 si
->replace_bitmap
= ewah_new();
164 /* Go through istate->cache[] and mark CE_MATCHED to
165 * entry with positive index. We'll go through
166 * base->cache[] later to delete all entries in base
167 * that are not marked eith either CE_MATCHED or
168 * CE_UPDATE_IN_BASE. If istate->cache[i] is a
169 * duplicate, deduplicate it.
171 for (i
= 0; i
< istate
->cache_nr
; i
++) {
172 struct cache_entry
*base
;
173 /* namelen is checked separately */
174 const unsigned int ondisk_flags
=
175 CE_STAGEMASK
| CE_VALID
| CE_EXTENDED_FLAGS
;
176 unsigned int ce_flags
, base_flags
, ret
;
177 ce
= istate
->cache
[i
];
180 if (ce
->index
> si
->base
->cache_nr
) {
184 ce
->ce_flags
|= CE_MATCHED
; /* or "shared" */
185 base
= si
->base
->cache
[ce
->index
- 1];
188 if (ce
->ce_namelen
!= base
->ce_namelen
||
189 strcmp(ce
->name
, base
->name
)) {
193 ce_flags
= ce
->ce_flags
;
194 base_flags
= base
->ce_flags
;
195 /* only on-disk flags matter */
196 ce
->ce_flags
&= ondisk_flags
;
197 base
->ce_flags
&= ondisk_flags
;
198 ret
= memcmp(&ce
->ce_stat_data
, &base
->ce_stat_data
,
199 offsetof(struct cache_entry
, name
) -
200 offsetof(struct cache_entry
, ce_stat_data
));
201 ce
->ce_flags
= ce_flags
;
202 base
->ce_flags
= base_flags
;
204 ce
->ce_flags
|= CE_UPDATE_IN_BASE
;
206 si
->base
->cache
[ce
->index
- 1] = ce
;
208 for (i
= 0; i
< si
->base
->cache_nr
; i
++) {
209 ce
= si
->base
->cache
[i
];
210 if ((ce
->ce_flags
& CE_REMOVE
) ||
211 !(ce
->ce_flags
& CE_MATCHED
))
212 ewah_set(si
->delete_bitmap
, i
);
213 else if (ce
->ce_flags
& CE_UPDATE_IN_BASE
) {
214 ewah_set(si
->replace_bitmap
, i
);
215 ALLOC_GROW(entries
, nr_entries
+1, nr_alloc
);
216 entries
[nr_entries
++] = ce
;
221 for (i
= 0; i
< istate
->cache_nr
; i
++) {
222 ce
= istate
->cache
[i
];
223 if ((!si
->base
|| !ce
->index
) && !(ce
->ce_flags
& CE_REMOVE
)) {
224 ALLOC_GROW(entries
, nr_entries
+1, nr_alloc
);
225 entries
[nr_entries
++] = ce
;
227 ce
->ce_flags
&= ~CE_MATCHED
;
231 * take cache[] out temporarily, put entries[] in its place
234 si
->saved_cache
= istate
->cache
;
235 si
->saved_cache_nr
= istate
->cache_nr
;
236 istate
->cache
= entries
;
237 istate
->cache_nr
= nr_entries
;
240 void finish_writing_split_index(struct index_state
*istate
)
242 struct split_index
*si
= init_split_index(istate
);
244 ewah_free(si
->delete_bitmap
);
245 ewah_free(si
->replace_bitmap
);
246 si
->delete_bitmap
= NULL
;
247 si
->replace_bitmap
= NULL
;
249 istate
->cache
= si
->saved_cache
;
250 istate
->cache_nr
= si
->saved_cache_nr
;
253 void discard_split_index(struct index_state
*istate
)
255 struct split_index
*si
= istate
->split_index
;
258 istate
->split_index
= NULL
;
263 discard_index(si
->base
);
269 void save_or_free_index_entry(struct index_state
*istate
, struct cache_entry
*ce
)
272 istate
->split_index
&&
273 istate
->split_index
->base
&&
274 ce
->index
<= istate
->split_index
->base
->cache_nr
&&
275 ce
== istate
->split_index
->base
->cache
[ce
->index
- 1])
276 ce
->ce_flags
|= CE_REMOVE
;
281 void replace_index_entry_in_base(struct index_state
*istate
,
282 struct cache_entry
*old
,
283 struct cache_entry
*new)
286 istate
->split_index
&&
287 istate
->split_index
->base
&&
288 old
->index
<= istate
->split_index
->base
->cache_nr
) {
289 new->index
= old
->index
;
290 if (old
!= istate
->split_index
->base
->cache
[new->index
- 1])
291 free(istate
->split_index
->base
->cache
[new->index
- 1]);
292 istate
->split_index
->base
->cache
[new->index
- 1] = new;