ntfs/libntfs/runlist.c

56  * @src:
63 static void ntfs_rl_mm(runlist_element *base, int dst, int src, int size)
65 	if ((dst != src) && (size > 0))
66 		memmove(base + dst, base + src, size * sizeof(*base));
74  * @src:
82 		       runlist_element *srcbase, int src, int size)
85 		memcpy(dstbase + dst, srcbase + src, size * sizeof(*dstbase));
154  * @src:	new runlist to test for mergeability with @dst
162 static BOOL ntfs_rl_are_mergeable(runlist_element *dst, runlist_element *src)
164 	if (!dst || !src) {
171 	if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED))
174 	if ((dst->vcn + dst->length) != src->vcn)
177 	if ((dst->lcn >= 0) && (src->lcn >= 0) &&
178 		((dst->lcn + dst->length) == src->lcn))
181 	if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE))
190  * @src:	new runlist to merge with @dst
196 static void __ntfs_rl_merge(runlist_element *dst, runlist_element *src)
198 	dst->length += src->length;
205  * @src:	runlist to be inserted into @dst
206  * @ssize:	number of elements in @src (excluding end marker)
207  * @loc:	append the new runlist @src after this element in @dst
209  * Append the runlist @src after element @loc in @dst.  Merge the right end of
214  * runlists @dst and @src are deallocated before returning so you cannot use
222 				       runlist_element *src, int ssize, int loc)
224 	BOOL right = FALSE;	/* Right end of @src needs merging */
227 	if (!dst || !src) {
236 		right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);
238 	/* Space required: @dst size + @src size, less one if we merged. */
249 		__ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
251 	/* marker - First run after the @src runs that have been inserted */
254 	/* Move the tail of @dst out of the way, then copy in @src. */
256 	ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
272  * @src:	new runlist to be inserted
273  * @ssize:	number of elements in @src (excluding end marker)
274  * @loc:	insert the new runlist @src before this element in @dst
276  * Insert the runlist @src before element @loc in the runlist @dst. Merge the
281  * runlists @dst and @src are deallocated before returning so you cannot use
289 				       runlist_element *src, int ssize, int loc)
291 	BOOL left = FALSE;	/* Left end of @src needs merging */
292 	BOOL disc = FALSE;	/* Discontinuity between @dst and @src */
295 	if (!dst || !src) {
302 	/* disc => Discontinuity between the end of @dst and the start of @src.
306 		disc = (src[0].vcn > 0);
310 		left = ntfs_rl_are_mergeable(dst + loc - 1, src);
314 			merged_length += src->length;
316 		disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
319 	/* Space required: @dst size + @src size, less one if we merged, plus
331 		__ntfs_rl_merge(dst + loc - 1, src);
334 	 * marker - First run after the @src runs that have been inserted
335 	 * Nominally: marker = @loc + @ssize (location + number of runs in @src)
336 	 * If "left", then the first run in @src has been merged with one in @dst.
337 	 * If "disc", then @dst and @src don't meet and we need an extra run to fill the gap.
341 	/* Move the tail of @dst out of the way, then copy in @src. */
343 	ntfs_rl_mc(dst, loc + disc, src, left, ssize - left);
369  * @src:	new runlist to be inserted
370  * @ssize:	number of elements in @src (excluding end marker)
371  * @loc:	index in runlist @dst to overwrite with @src
373  * Replace the runlist element @dst at @loc with @src. Merge the left and
377  * runlists @dst and @src are deallocated before returning so you cannot use
385 					runlist_element *src, int ssize,
389 	BOOL left  = FALSE;	/* Left end of @src needs merging */
390 	BOOL right = FALSE;	/* Right end of @src needs merging */
394 	if (!dst || !src) {
403 		right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);
405 		left = ntfs_rl_are_mergeable(dst + loc - 1, src);
423 		__ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
425 		__ntfs_rl_merge(dst + loc - 1, src);
430 	 * If "right", then one of @dst's runs is already merged into @src.
435 	 * marker - First run after the @src runs that have been inserted
436 	 * Nominally: @marker = @loc + @ssize (location + number of runs in @src)
437 	 * If "left", then the first run in @src has been merged with one in @dst.
441 	/* Move the tail of @dst out of the way, then copy in @src. */
443 	ntfs_rl_mc(dst, loc, src, left, ssize - left);
456  * @src:	new runlist to be inserted
457  * @ssize:	number of elements in @src (excluding end marker)
458  * @loc:	index in runlist @dst at which to split and insert @src
465  * runlists @dst and @src are deallocated before returning so you cannot use
473 				      runlist_element *src, int ssize, int loc)
475 	if (!dst || !src) {
481 	/* Space required: @dst size + @src size + one new hole. */
490 	/* Move the tail of @dst out of the way, then copy in @src. */
492 	ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
494 	/* Adjust the size of the holes either size of @src. */
520 	ntfs_log_debug("src:\n");
1849 	printf("src:\n");
1943 	runlist_element *src;
1947 	src = test_rl_pure_src(contig, multi, vcn, len);
1949 	if (!src || !dst) {
1957 	res = test_rl_runlists_merge(dst, src);