]>
git.ipfire.org Git - thirdparty/e2fsprogs.git/blob - resize/extent.c
2 * extent.c --- ext2 extent abstraction
4 * This abstraction is used to provide a compact way of representing a
5 * translation table, for moving multiple contiguous ranges (extents)
8 * Copyright (C) 1997, 1998 by Theodore Ts'o and
11 * Copyright (C) 1999, 2000 by Theodore Ts'o
14 * This file may be redistributed under the terms of the GNU Public
20 #include "resize2fs.h"
22 struct ext2_extent_entry
{
23 __u64 old_loc
, new_loc
;
28 struct ext2_extent_entry
*list
;
36 * Create an extent table
38 errcode_t
ext2fs_create_extent_table(ext2_extent
*ret_extent
, __u64 size
)
43 retval
= ext2fs_get_mem(sizeof(struct _ext2_extent
), &extent
);
46 memset(extent
, 0, sizeof(struct _ext2_extent
));
48 extent
->size
= size
? size
: 50;
53 retval
= ext2fs_get_array(sizeof(struct ext2_extent_entry
),
54 extent
->size
, &extent
->list
);
56 ext2fs_free_mem(&extent
);
59 memset(extent
->list
, 0,
60 sizeof(struct ext2_extent_entry
) * extent
->size
);
66 * Free an extent table
68 void ext2fs_free_extent_table(ext2_extent extent
)
71 ext2fs_free_mem(&extent
->list
);
75 ext2fs_free_mem(&extent
);
79 * Add an entry to the extent table
81 errcode_t
ext2fs_add_extent_entry(ext2_extent extent
, __u64 old_loc
, __u64 new_loc
)
83 struct ext2_extent_entry
*ent
;
88 if (extent
->num
>= extent
->size
) {
89 newsize
= extent
->size
+ 100;
90 retval
= ext2fs_resize_mem(sizeof(struct ext2_extent_entry
) *
92 sizeof(struct ext2_extent_entry
) *
93 newsize
, &extent
->list
);
96 extent
->size
= newsize
;
99 ent
= extent
->list
+ curr
;
102 * Check to see if this can be coalesced with the last
106 if ((ent
->old_loc
+ ent
->size
== old_loc
) &&
107 (ent
->new_loc
+ ent
->size
== new_loc
)) {
112 * Now see if we're going to ruin the sorting
114 if (ent
->old_loc
+ ent
->size
> old_loc
)
118 ent
->old_loc
= old_loc
;
119 ent
->new_loc
= new_loc
;
126 * Helper function for qsort
128 static EXT2_QSORT_TYPE
extent_cmp(const void *a
, const void *b
)
130 const struct ext2_extent_entry
*db_a
;
131 const struct ext2_extent_entry
*db_b
;
133 db_a
= (const struct ext2_extent_entry
*) a
;
134 db_b
= (const struct ext2_extent_entry
*) b
;
136 return (db_a
->old_loc
- db_b
->old_loc
);
140 * Given an inode map and inode number, look up the old inode number
141 * and return the new inode number.
143 __u64
ext2fs_extent_translate(ext2_extent extent
, __u64 old_loc
)
145 __s64 low
, high
, mid
;
146 __u64 lowval
, highval
;
149 if (!extent
->sorted
) {
150 qsort(extent
->list
, extent
->num
,
151 sizeof(struct ext2_extent_entry
), extent_cmp
);
155 high
= extent
->num
-1;
156 while (low
<= high
) {
163 /* Interpolate for efficiency */
164 lowval
= extent
->list
[low
].old_loc
;
165 highval
= extent
->list
[high
].old_loc
;
167 if (old_loc
< lowval
)
169 else if (old_loc
> highval
)
172 range
= ((float) (old_loc
- lowval
)) /
179 mid
= low
+ ((__u64
) (range
* (high
-low
)));
182 if ((old_loc
>= extent
->list
[mid
].old_loc
) &&
183 (old_loc
< extent
->list
[mid
].old_loc
+ extent
->list
[mid
].size
))
184 return (extent
->list
[mid
].new_loc
+
185 (old_loc
- extent
->list
[mid
].old_loc
));
186 if (old_loc
< extent
->list
[mid
].old_loc
)
197 void ext2fs_extent_dump(ext2_extent extent
, FILE *out
)
200 struct ext2_extent_entry
*ent
;
202 fputs(_("# Extent dump:\n"), out
);
203 fprintf(out
, _("#\tNum=%llu, Size=%llu, Cursor=%llu, Sorted=%llu\n"),
204 extent
->num
, extent
->size
, extent
->cursor
, extent
->sorted
);
205 for (i
=0, ent
=extent
->list
; i
< extent
->num
; i
++, ent
++) {
206 fprintf(out
, "#\t\t %llu -> %llu (%llu)\n", ent
->old_loc
,
207 ent
->new_loc
, ent
->size
);
212 * Iterate over the contents of the extent table
214 errcode_t
ext2fs_iterate_extent(ext2_extent extent
, __u64
*old_loc
,
215 __u64
*new_loc
, __u64
*size
)
217 struct ext2_extent_entry
*ent
;
224 if (extent
->cursor
>= extent
->num
) {
231 ent
= extent
->list
+ extent
->cursor
++;
233 *old_loc
= ent
->old_loc
;
234 *new_loc
= ent
->new_loc
;