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