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) *
88 sizeof(struct ext2_extent_entry) *
89 newsize, (void **) &extent->list);
92 extent->size = newsize;
95 ent = extent->list + curr;
98 * Check to see if this can be coalesced with the last
102 if ((ent->old_loc + ent->size == old_loc) &&
103 (ent->new_loc + ent->size == new_loc)) {
108 * Now see if we're going to ruin the sorting
110 if (ent->old_loc + ent->size > old_loc)
114 ent->old_loc = old_loc;
115 ent->new_loc = new_loc;
122 * Helper function for qsort
124 static int extent_cmp(const void *a, const void *b)
126 const struct ext2_extent_entry *db_a;
127 const struct ext2_extent_entry *db_b;
129 db_a = (const struct ext2_extent_entry *) a;
130 db_b = (const struct ext2_extent_entry *) b;
132 return (db_a->old_loc - db_b->old_loc);
136 * Given an inode map and inode number, look up the old inode number
137 * and return the new inode number.
139 __u32 ext2fs_extent_translate(ext2_extent extent, __u32 old_loc)
142 ino_t lowval, highval;
145 if (!extent->sorted) {
146 qsort(extent->list, extent->num,
147 sizeof(struct ext2_extent_entry), extent_cmp);
151 high = extent->num-1;
152 while (low <= high) {
159 /* Interpolate for efficiency */
160 lowval = extent->list[low].old_loc;
161 highval = extent->list[high].old_loc;
163 if (old_loc < lowval)
165 else if (old_loc > highval)
168 range = ((float) (old_loc - lowval)) /
170 mid = low + ((int) (range * (high-low)));
173 if ((old_loc >= extent->list[mid].old_loc) &&
174 (old_loc < extent->list[mid].old_loc + extent->list[mid].size))
175 return (extent->list[mid].new_loc +
176 (old_loc - extent->list[mid].old_loc));
177 if (old_loc < extent->list[mid].old_loc)
188 void ext2fs_extent_dump(ext2_extent extent, FILE *out)
191 struct ext2_extent_entry *ent;
193 fputs("# Extent dump:\n", out);
194 fprintf(out, "#\tNum=%d, Size=%d, Cursor=%d, Sorted=%d\n",
195 extent->num, extent->size, extent->cursor, extent->sorted);
196 for (i=0, ent=extent->list; i < extent->num; i++, ent++) {
197 fprintf(out, "#\t\t %u -> %u (%d)\n", ent->old_loc,
198 ent->new_loc, ent->size);
203 * Iterate over the contents of the extent table
205 errcode_t ext2fs_iterate_extent(ext2_extent extent, __u32 *old_loc,
206 __u32 *new_loc, int *size)
208 struct ext2_extent_entry *ent;
215 if (extent->cursor >= extent->num) {
222 ent = extent->list + extent->cursor++;
224 *old_loc = ent->old_loc;
225 *new_loc = ent->new_loc;