]>
Commit | Line | Data |
---|---|---|
55fd07ed TT |
1 | /* |
2 | * region.c --- code which manages allocations within a region. | |
efc6f628 | 3 | * |
55fd07ed TT |
4 | * Copyright (C) 2001 Theodore Ts'o. |
5 | * | |
6 | * %Begin-Header% | |
7 | * This file may be redistributed under the terms of the GNU Public | |
8 | * License. | |
9 | * %End-Header% | |
10 | */ | |
11 | ||
d1154eb4 | 12 | #include "config.h" |
55fd07ed TT |
13 | #if HAVE_UNISTD_H |
14 | #include <unistd.h> | |
15 | #endif | |
16 | #include <string.h> | |
17 | ||
0eeec8ac TT |
18 | #ifdef TEST_PROGRAM |
19 | #undef ENABLE_NLS | |
20 | #endif | |
55fd07ed TT |
21 | #include "e2fsck.h" |
22 | ||
23 | struct region_el { | |
24 | region_addr_t start; | |
25 | region_addr_t end; | |
26 | struct region_el *next; | |
27 | }; | |
28 | ||
29 | struct region_struct { | |
30 | region_addr_t min; | |
31 | region_addr_t max; | |
32 | struct region_el *allocated; | |
8a48ce07 | 33 | struct region_el *last; |
55fd07ed TT |
34 | }; |
35 | ||
36 | region_t region_create(region_addr_t min, region_addr_t max) | |
37 | { | |
38 | region_t region; | |
70303df1 | 39 | errcode_t retval; |
55fd07ed | 40 | |
70303df1 AD |
41 | retval = ext2fs_get_memzero(sizeof(struct region_struct), ®ion); |
42 | if (retval) | |
55fd07ed | 43 | return NULL; |
70303df1 | 44 | |
55fd07ed TT |
45 | region->min = min; |
46 | region->max = max; | |
8a48ce07 | 47 | region->last = NULL; |
55fd07ed TT |
48 | return region; |
49 | } | |
50 | ||
51 | void region_free(region_t region) | |
52 | { | |
53 | struct region_el *r, *next; | |
54 | ||
55 | for (r = region->allocated; r; r = next) { | |
56 | next = r->next; | |
70303df1 | 57 | ext2fs_free_mem(&r); |
55fd07ed TT |
58 | } |
59 | memset(region, 0, sizeof(struct region_struct)); | |
70303df1 | 60 | ext2fs_free_mem(®ion); |
55fd07ed TT |
61 | } |
62 | ||
63 | int region_allocate(region_t region, region_addr_t start, int n) | |
64 | { | |
65 | struct region_el *r, *new_region, *prev, *next; | |
66 | region_addr_t end; | |
70303df1 | 67 | errcode_t retval; |
55fd07ed TT |
68 | |
69 | end = start+n; | |
70 | if ((start < region->min) || (end > region->max)) | |
71 | return -1; | |
72 | if (n == 0) | |
73 | return 1; | |
74 | ||
8a48ce07 TT |
75 | if (region->last && region->last->end == start && |
76 | !region->last->next) { | |
77 | region->last->end = end; | |
78 | return 0; | |
79 | } | |
80 | if (region->last && start > region->last->end && | |
81 | !region->last->next) { | |
82 | r = NULL; | |
83 | prev = region->last; | |
84 | goto append_to_list; | |
85 | } | |
86 | ||
55fd07ed TT |
87 | /* |
88 | * Search through the linked list. If we find that it | |
055866d8 | 89 | * conflicts with something that's already allocated, return |
55fd07ed TT |
90 | * 1; if we can find an existing region which we can grow, do |
91 | * so. Otherwise, stop when we find the appropriate place | |
92 | * insert a new region element into the linked list. | |
93 | */ | |
94 | for (r = region->allocated, prev=NULL; r; prev = r, r = r->next) { | |
95 | if (((start >= r->start) && (start < r->end)) || | |
96 | ((end > r->start) && (end <= r->end)) || | |
97 | ((start <= r->start) && (end >= r->end))) | |
98 | return 1; | |
99 | if (end == r->start) { | |
100 | r->start = start; | |
101 | return 0; | |
102 | } | |
103 | if (start == r->end) { | |
104 | if ((next = r->next)) { | |
105 | if (end > next->start) | |
106 | return 1; | |
107 | if (end == next->start) { | |
108 | r->end = next->end; | |
109 | r->next = next->next; | |
70303df1 | 110 | ext2fs_free_mem(&next); |
8a48ce07 TT |
111 | if (!r->next) |
112 | region->last = r; | |
55fd07ed TT |
113 | return 0; |
114 | } | |
115 | } | |
116 | r->end = end; | |
117 | return 0; | |
118 | } | |
119 | if (start < r->start) | |
120 | break; | |
121 | } | |
122 | /* | |
123 | * Insert a new region element structure into the linked list | |
124 | */ | |
8a48ce07 | 125 | append_to_list: |
70303df1 AD |
126 | retval = ext2fs_get_mem(sizeof(struct region_el), &new_region); |
127 | if (retval) | |
55fd07ed TT |
128 | return -1; |
129 | new_region->start = start; | |
130 | new_region->end = start + n; | |
131 | new_region->next = r; | |
8a48ce07 TT |
132 | if (!new_region->next) |
133 | region->last = new_region; | |
55fd07ed TT |
134 | if (prev) |
135 | prev->next = new_region; | |
136 | else | |
137 | region->allocated = new_region; | |
138 | return 0; | |
139 | } | |
140 | ||
141 | #ifdef TEST_PROGRAM | |
142 | #include <stdio.h> | |
143 | ||
144 | #define BCODE_END 0 | |
145 | #define BCODE_CREATE 1 | |
146 | #define BCODE_FREE 2 | |
147 | #define BCODE_ALLOCATE 3 | |
148 | #define BCODE_PRINT 4 | |
149 | ||
150 | int bcode_program[] = { | |
151 | BCODE_CREATE, 1, 1001, | |
152 | BCODE_PRINT, | |
153 | BCODE_ALLOCATE, 10, 10, | |
154 | BCODE_ALLOCATE, 30, 10, | |
155 | BCODE_PRINT, | |
156 | BCODE_ALLOCATE, 1, 15, | |
157 | BCODE_ALLOCATE, 15, 8, | |
158 | BCODE_ALLOCATE, 1, 20, | |
159 | BCODE_ALLOCATE, 1, 8, | |
160 | BCODE_PRINT, | |
161 | BCODE_ALLOCATE, 40, 10, | |
162 | BCODE_PRINT, | |
163 | BCODE_ALLOCATE, 22, 5, | |
164 | BCODE_PRINT, | |
165 | BCODE_ALLOCATE, 27, 3, | |
166 | BCODE_PRINT, | |
167 | BCODE_ALLOCATE, 20, 2, | |
168 | BCODE_PRINT, | |
169 | BCODE_ALLOCATE, 49, 1, | |
170 | BCODE_ALLOCATE, 50, 5, | |
171 | BCODE_ALLOCATE, 9, 2, | |
172 | BCODE_ALLOCATE, 9, 1, | |
173 | BCODE_PRINT, | |
174 | BCODE_FREE, | |
175 | BCODE_END | |
176 | }; | |
177 | ||
178 | void region_print(region_t region, FILE *f) | |
179 | { | |
180 | struct region_el *r; | |
181 | int i = 0; | |
efc6f628 | 182 | |
180f376b | 183 | fprintf(f, "Printing region (min=%llu. max=%llu)\n\t", region->min, |
55fd07ed TT |
184 | region->max); |
185 | for (r = region->allocated; r; r = r->next) { | |
180f376b | 186 | fprintf(f, "(%llu, %llu) ", r->start, r->end); |
55fd07ed TT |
187 | if (++i >= 8) |
188 | fprintf(f, "\n\t"); | |
189 | } | |
190 | fprintf(f, "\n"); | |
191 | } | |
192 | ||
193 | int main(int argc, char **argv) | |
194 | { | |
00eb0eee | 195 | region_t r = NULL; |
55fd07ed | 196 | int pc = 0, ret; |
6b56f3d9 | 197 | region_addr_t start, end; |
55fd07ed | 198 | |
efc6f628 | 199 | |
55fd07ed TT |
200 | while (1) { |
201 | switch (bcode_program[pc++]) { | |
202 | case BCODE_END: | |
203 | exit(0); | |
204 | case BCODE_CREATE: | |
205 | start = bcode_program[pc++]; | |
206 | end = bcode_program[pc++]; | |
180f376b | 207 | printf("Creating region with args(%llu, %llu)\n", |
55fd07ed TT |
208 | start, end); |
209 | r = region_create(start, end); | |
210 | if (!r) { | |
211 | fprintf(stderr, "Couldn't create region.\n"); | |
212 | exit(1); | |
213 | } | |
214 | break; | |
215 | case BCODE_ALLOCATE: | |
216 | start = bcode_program[pc++]; | |
217 | end = bcode_program[pc++]; | |
218 | ret = region_allocate(r, start, end); | |
180f376b | 219 | printf("Region_allocate(%llu, %llu) returns %d\n", |
55fd07ed TT |
220 | start, end, ret); |
221 | break; | |
222 | case BCODE_PRINT: | |
223 | region_print(r, stdout); | |
224 | break; | |
225 | } | |
226 | } | |
24997f1c DW |
227 | if (r) |
228 | region_free(r); | |
55fd07ed TT |
229 | } |
230 | ||
231 | #endif /* TEST_PROGRAM */ |