]>
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 Theodore Ts'o
11 * All rights reserved.
15 #include "resize2fs.h"
17 struct ext2_extent_entry
{
18 __u32 old_loc
, new_loc
;
23 struct ext2_extent_entry
*list
;
31 * Create an extent table
33 errcode_t
ext2fs_create_extent_table(ext2_extent
*ret_extent
, int size
)
38 retval
= ext2fs_get_mem(sizeof(struct _ext2_extent
),
42 memset(extent
, 0, sizeof(struct _ext2_extent
));
44 extent
->size
= size
? size
: 50;
49 retval
= ext2fs_get_mem(sizeof(struct ext2_extent_entry
) *
50 extent
->size
, (void **) &extent
->list
);
55 memset(extent
->list
, 0,
56 sizeof(struct ext2_extent_entry
) * extent
->size
);
62 * Free an extent table
64 void ext2fs_free_extent_table(ext2_extent extent
)
67 ext2fs_free_mem((void **) &extent
->list
);
71 ext2fs_free_mem((void **) &extent
);
75 * Add an entry to the extent table
77 errcode_t
ext2fs_add_extent_entry(ext2_extent extent
, __u32 old_loc
, __u32 new_loc
)
79 struct ext2_extent_entry
*ent
;
84 if (extent
->num
>= extent
->size
) {
85 newsize
= extent
->size
+ 100;
86 retval
= ext2fs_resize_mem(sizeof(struct ext2_extent_entry
) *
87 newsize
, (void **) &extent
->list
);
90 extent
->size
= newsize
;
93 ent
= extent
->list
+ curr
;
96 * Check to see if this can be coalesced with the last
100 if ((ent
->old_loc
+ ent
->size
== old_loc
) &&
101 (ent
->new_loc
+ ent
->size
== new_loc
)) {
106 * Now see if we're going to ruin the sorting
108 if (ent
->old_loc
+ ent
->size
> old_loc
)
112 ent
->old_loc
= old_loc
;
113 ent
->new_loc
= new_loc
;
120 * Helper function for qsort
122 static int extent_cmp(const void *a
, const void *b
)
124 const struct ext2_extent_entry
*db_a
;
125 const struct ext2_extent_entry
*db_b
;
127 db_a
= (const struct ext2_extent_entry
*) a
;
128 db_b
= (const struct ext2_extent_entry
*) b
;
130 return (db_a
->old_loc
- db_b
->old_loc
);
134 * Given an inode map and inode number, look up the old inode number
135 * and return the new inode number.
137 __u32
ext2fs_extent_translate(ext2_extent extent
, __u32 old_loc
)
140 ino_t lowval
, highval
;
143 if (!extent
->sorted
) {
144 qsort(extent
->list
, extent
->num
,
145 sizeof(struct ext2_extent_entry
), extent_cmp
);
149 high
= extent
->num
-1;
150 while (low
<= high
) {
157 /* Interpolate for efficiency */
158 lowval
= extent
->list
[low
].old_loc
;
159 highval
= extent
->list
[high
].old_loc
;
161 if (old_loc
< lowval
)
163 else if (old_loc
> highval
)
166 range
= ((float) (old_loc
- lowval
)) /
168 mid
= low
+ ((int) (range
* (high
-low
)));
171 if ((old_loc
>= extent
->list
[mid
].old_loc
) &&
172 (old_loc
< extent
->list
[mid
].old_loc
+ extent
->list
[mid
].size
))
173 return (extent
->list
[mid
].new_loc
+
174 (old_loc
- extent
->list
[mid
].old_loc
));
175 if (old_loc
< extent
->list
[mid
].old_loc
)
186 void ext2fs_extent_dump(ext2_extent extent
, FILE *out
)
189 struct ext2_extent_entry
*ent
;
191 fputs("# Extent dump:\n", out
);
192 fprintf(out
, "#\tNum=%d, Size=%d, Cursor=%d, Sorted=%d\n",
193 extent
->num
, extent
->size
, extent
->cursor
, extent
->sorted
);
194 for (i
=0, ent
=extent
->list
; i
< extent
->num
; i
++, ent
++) {
195 fprintf(out
, "#\t\t %u -> %u (%d)\n", ent
->old_loc
,
196 ent
->new_loc
, ent
->size
);
201 * Iterate over the contents of the extent table
203 errcode_t
ext2fs_iterate_extent(ext2_extent extent
, __u32
*old_loc
,
204 __u32
*new_loc
, int *size
)
206 struct ext2_extent_entry
*ent
;
213 if (extent
->cursor
>= extent
->num
) {
220 ent
= extent
->list
+ extent
->cursor
++;
222 *old_loc
= ent
->old_loc
;
223 *new_loc
= ent
->new_loc
;