blob: 0f0ef4cd7372f188ab96c7dff625024762016261 [file] [log] [blame]
Theodore Ts'oc762c8e1997-06-17 03:52:12 +00001/*
2 * extent.c --- ext2 extent abstraction
3 *
4 * This abstraction is used to provide a compact way of representing a
5 * translation table, for moving multiple contiguous ranges (extents)
6 * of blocks or inodes.
7 *
8 * Copyright (C) 1997 Theodore Ts'o
9 *
10 * %Begin-Header%
11 * All rights reserved.
12 * %End-Header%
13 */
14
15#include "resize2fs.h"
16
17struct ext2_extent_entry {
18 __u32 old, new;
19 int size;
20};
21
22struct _ext2_extent {
23 struct ext2_extent_entry *list;
24 int cursor;
25 int size;
26 int num;
27 int sorted;
28};
29
30/*
31 * Create an extent table
32 */
33errcode_t ext2fs_create_extent_table(ext2_extent *ret_extent, int size)
34{
35 ext2_extent new;
36
37 new = malloc(sizeof(struct _ext2_extent));
38 if (!new)
39 return ENOMEM;
40 memset(new, 0, sizeof(struct _ext2_extent));
41
42 new->size = size ? size : 50;
43 new->cursor = 0;
44 new->num = 0;
45 new->sorted = 1;
46
47 new->list = malloc(sizeof(struct ext2_extent_entry) * new->size);
48 if (!new->list) {
49 free(new);
50 return ENOMEM;
51 }
52 memset(new->list, 0, sizeof(struct ext2_extent_entry) * new->size);
53 *ret_extent = new;
54 return 0;
55}
56
57/*
58 * Free an extent table
59 */
60void ext2fs_free_extent_table(ext2_extent extent)
61{
62 if (extent->list)
63 free(extent->list);
64 extent->list = 0;
65 extent->size = 0;
66 extent->num = 0;
67 free(extent);
68}
69
70/*
71 * Add an entry to the extent table
72 */
73errcode_t ext2fs_add_extent_entry(ext2_extent extent, __u32 old, __u32 new)
74{
75 struct ext2_extent_entry *p;
76 int newsize;
77 int curr;
78 struct ext2_extent_entry *ent;
79
80 if (extent->num >= extent->size) {
81 newsize = extent->size + 100;
82 p = realloc(extent->list,
83 sizeof(struct ext2_extent_entry) * newsize);
84 if (!p)
85 return ENOMEM;
86 extent->list = p;
87 extent->size = newsize;
88 }
89 curr = extent->num;
90 ent = extent->list + curr;
91 if (curr) {
92 /*
93 * Check to see if this can be coalesced with the last
94 * extent
95 */
96 ent--;
97 if ((ent->old + ent->size == old) &&
98 (ent->new + ent->size == new)) {
99 ent->size++;
100 return 0;
101 }
102 /*
103 * Now see if we're going to ruin the sorting
104 */
105 if (ent->old + ent->size > old)
106 extent->sorted = 0;
107 ent++;
108 }
109 ent->old = old;
110 ent->new = new;
111 ent->size = 1;
112 extent->num++;
113 return 0;
114}
115
116/*
117 * Helper function for qsort
118 */
119static int extent_cmp(const void *a, const void *b)
120{
121 const struct ext2_extent_entry *db_a = a;
122 const struct ext2_extent_entry *db_b = b;
123
124 return (db_a->old - db_b->old);
125}
126
127/*
128 * Given an inode map and inode number, look up the old inode number
129 * and return the new inode number
130 */
131__u32 ext2fs_extent_translate(ext2_extent extent, __u32 old)
132{
133 int low, high, mid;
134 ino_t lowval, highval;
135 float range;
136
137 if (!extent->sorted) {
138 qsort(extent->list, extent->num,
139 sizeof(struct ext2_extent_entry), extent_cmp);
140 extent->sorted = 1;
141 }
142 low = 0;
143 high = extent->num-1;
144 while (low <= high) {
145#if 0
146 mid = (low+high)/2;
147#else
148 if (low == high)
149 mid = low;
150 else {
151 /* Interpolate for efficiency */
152 lowval = extent->list[low].old;
153 highval = extent->list[high].old;
154
155 if (old < lowval)
156 range = 0;
157 else if (old > highval)
158 range = 1;
159 else
160 range = ((float) (old - lowval)) /
161 (highval - lowval);
162 mid = low + ((int) (range * (high-low)));
163 }
164#endif
165 if ((old >= extent->list[mid].old) &&
166 (old < extent->list[mid].old + extent->list[mid].size))
167 return (extent->list[mid].new +
168 (old - extent->list[mid].old));
169 if (old < extent->list[mid].old)
170 high = mid-1;
171 else
172 low = mid+1;
173 }
174 return 0;
175}
176
177/*
178 * For debugging only
179 */
180void ext2fs_extent_dump(ext2_extent extent, FILE *out)
181{
182 int i;
183 struct ext2_extent_entry *ent;
184
185 fputs("# Extent dump:\n", out);
186 fprintf(out, "#\tNum=%d, Size=%d, Cursor=%d, Sorted=%d\n",
187 extent->num, extent->size, extent->cursor, extent->sorted);
188 for (i=0, ent=extent->list; i < extent->num; i++, ent++) {
189 fprintf(out, "#\t\t %u -> %u (%d)\n", ent->old,
190 ent->new, ent->size);
191 }
192}
193
194/*
195 * Iterate over the contents of the extent table
196 */
197errcode_t ext2fs_iterate_extent(ext2_extent extent, __u32 *old,
198 __u32 *new, int *size)
199{
200 struct ext2_extent_entry *ent;
201
202 if (!old) {
203 extent->cursor = 0;
204 return 0;
205 }
206
207 if (extent->cursor >= extent->num) {
208 *old = 0;
209 *new = 0;
210 *size = 0;
211 return 0;
212 }
213
214 ent = extent->list + extent->cursor++;
215
216 *old = ent->old;
217 *new = ent->new;
218 *size = ent->size;
219 return 0;
220}
221
222
223
224