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 (unsigned long long) extent->num,
205 (unsigned long long) extent->size,
206 (unsigned long long) extent->cursor,
207 (unsigned long long) extent->sorted);
208 for (i=0, ent=extent->list; i < extent->num; i++, ent++) {
209 fprintf(out, "#\t\t %llu -> %llu (%llu)\n",
210 (unsigned long long) ent->old_loc,
211 (unsigned long long) ent->new_loc,
212 (unsigned long long) ent->size);
217 * Iterate over the contents of the extent table
219 errcode_t ext2fs_iterate_extent(ext2_extent extent, __u64 *old_loc,
220 __u64 *new_loc, __u64 *size)
222 struct ext2_extent_entry *ent;
229 if (extent->cursor >= extent->num) {
236 ent = extent->list + extent->cursor++;
238 *old_loc = ent->old_loc;
239 *new_loc = ent->new_loc;