]>
git.ipfire.org Git - thirdparty/e2fsprogs.git/blob - e2fsck/region.c
2 * region.c --- code which manages allocations within a region.
4 * Copyright (C) 2001 Theodore Ts'o.
7 * This file may be redistributed under the terms of the GNU Public
26 struct region_el
*next
;
29 struct region_struct
{
32 struct region_el
*allocated
;
33 struct region_el
*last
;
36 region_t
region_create(region_addr_t min
, region_addr_t max
)
40 region
= malloc(sizeof(struct region_struct
));
43 memset(region
, 0, sizeof(struct region_struct
));
50 void region_free(region_t region
)
52 struct region_el
*r
, *next
;
54 for (r
= region
->allocated
; r
; r
= next
) {
58 memset(region
, 0, sizeof(struct region_struct
));
62 int region_allocate(region_t region
, region_addr_t start
, int n
)
64 struct region_el
*r
, *new_region
, *prev
, *next
;
68 if ((start
< region
->min
) || (end
> region
->max
))
73 if (region
->last
&& region
->last
->end
== start
&&
74 !region
->last
->next
) {
75 region
->last
->end
= end
;
78 if (region
->last
&& start
> region
->last
->end
&&
79 !region
->last
->next
) {
86 * Search through the linked list. If we find that it
87 * conflicts with something that's already allocated, return
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.
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
)))
97 if (end
== r
->start
) {
101 if (start
== r
->end
) {
102 if ((next
= r
->next
)) {
103 if (end
> next
->start
)
105 if (end
== next
->start
) {
107 r
->next
= next
->next
;
117 if (start
< r
->start
)
121 * Insert a new region element structure into the linked list
124 new_region
= malloc(sizeof(struct region_el
));
127 new_region
->start
= start
;
128 new_region
->end
= start
+ n
;
129 new_region
->next
= r
;
130 if (!new_region
->next
)
131 region
->last
= new_region
;
133 prev
->next
= new_region
;
135 region
->allocated
= new_region
;
143 #define BCODE_CREATE 1
145 #define BCODE_ALLOCATE 3
146 #define BCODE_PRINT 4
148 int bcode_program
[] = {
149 BCODE_CREATE
, 1, 1001,
151 BCODE_ALLOCATE
, 10, 10,
152 BCODE_ALLOCATE
, 30, 10,
154 BCODE_ALLOCATE
, 1, 15,
155 BCODE_ALLOCATE
, 15, 8,
156 BCODE_ALLOCATE
, 1, 20,
157 BCODE_ALLOCATE
, 1, 8,
159 BCODE_ALLOCATE
, 40, 10,
161 BCODE_ALLOCATE
, 22, 5,
163 BCODE_ALLOCATE
, 27, 3,
165 BCODE_ALLOCATE
, 20, 2,
167 BCODE_ALLOCATE
, 49, 1,
168 BCODE_ALLOCATE
, 50, 5,
169 BCODE_ALLOCATE
, 9, 2,
170 BCODE_ALLOCATE
, 9, 1,
176 void region_print(region_t region
, FILE *f
)
181 fprintf(f
, "Printing region (min=%llu. max=%llu)\n\t", region
->min
,
183 for (r
= region
->allocated
; r
; r
= r
->next
) {
184 fprintf(f
, "(%llu, %llu) ", r
->start
, r
->end
);
191 int main(int argc
, char **argv
)
195 region_addr_t start
, end
;
199 switch (bcode_program
[pc
++]) {
203 start
= bcode_program
[pc
++];
204 end
= bcode_program
[pc
++];
205 printf("Creating region with args(%llu, %llu)\n",
207 r
= region_create(start
, end
);
209 fprintf(stderr
, "Couldn't create region.\n");
214 start
= bcode_program
[pc
++];
215 end
= bcode_program
[pc
++];
216 ret
= region_allocate(r
, start
, end
);
217 printf("Region_allocate(%llu, %llu) returns %d\n",
221 region_print(r
, stdout
);
229 #endif /* TEST_PROGRAM */