]>
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
;
35 region_t
region_create(region_addr_t min
, region_addr_t max
)
39 region
= malloc(sizeof(struct region_struct
));
42 memset(region
, 0, sizeof(struct region_struct
));
48 void region_free(region_t region
)
50 struct region_el
*r
, *next
;
52 for (r
= region
->allocated
; r
; r
= next
) {
56 memset(region
, 0, sizeof(struct region_struct
));
60 int region_allocate(region_t region
, region_addr_t start
, int n
)
62 struct region_el
*r
, *new_region
, *prev
, *next
;
66 if ((start
< region
->min
) || (end
> region
->max
))
72 * Search through the linked list. If we find that it
73 * conflicts witih something that's already allocated, return
74 * 1; if we can find an existing region which we can grow, do
75 * so. Otherwise, stop when we find the appropriate place
76 * insert a new region element into the linked list.
78 for (r
= region
->allocated
, prev
=NULL
; r
; prev
= r
, r
= r
->next
) {
79 if (((start
>= r
->start
) && (start
< r
->end
)) ||
80 ((end
> r
->start
) && (end
<= r
->end
)) ||
81 ((start
<= r
->start
) && (end
>= r
->end
)))
83 if (end
== r
->start
) {
87 if (start
== r
->end
) {
88 if ((next
= r
->next
)) {
89 if (end
> next
->start
)
91 if (end
== next
->start
) {
101 if (start
< r
->start
)
105 * Insert a new region element structure into the linked list
107 new_region
= malloc(sizeof(struct region_el
));
110 new_region
->start
= start
;
111 new_region
->end
= start
+ n
;
112 new_region
->next
= r
;
114 prev
->next
= new_region
;
116 region
->allocated
= new_region
;
124 #define BCODE_CREATE 1
126 #define BCODE_ALLOCATE 3
127 #define BCODE_PRINT 4
129 int bcode_program
[] = {
130 BCODE_CREATE
, 1, 1001,
132 BCODE_ALLOCATE
, 10, 10,
133 BCODE_ALLOCATE
, 30, 10,
135 BCODE_ALLOCATE
, 1, 15,
136 BCODE_ALLOCATE
, 15, 8,
137 BCODE_ALLOCATE
, 1, 20,
138 BCODE_ALLOCATE
, 1, 8,
140 BCODE_ALLOCATE
, 40, 10,
142 BCODE_ALLOCATE
, 22, 5,
144 BCODE_ALLOCATE
, 27, 3,
146 BCODE_ALLOCATE
, 20, 2,
148 BCODE_ALLOCATE
, 49, 1,
149 BCODE_ALLOCATE
, 50, 5,
150 BCODE_ALLOCATE
, 9, 2,
151 BCODE_ALLOCATE
, 9, 1,
157 void region_print(region_t region
, FILE *f
)
162 fprintf(f
, "Printing region (min=%llu. max=%llu)\n\t", region
->min
,
164 for (r
= region
->allocated
; r
; r
= r
->next
) {
165 fprintf(f
, "(%llu, %llu) ", r
->start
, r
->end
);
172 int main(int argc
, char **argv
)
176 region_addr_t start
, end
;
180 switch (bcode_program
[pc
++]) {
184 start
= bcode_program
[pc
++];
185 end
= bcode_program
[pc
++];
186 printf("Creating region with args(%llu, %llu)\n",
188 r
= region_create(start
, end
);
190 fprintf(stderr
, "Couldn't create region.\n");
195 start
= bcode_program
[pc
++];
196 end
= bcode_program
[pc
++];
197 ret
= region_allocate(r
, start
, end
);
198 printf("Region_allocate(%llu, %llu) returns %d\n",
202 region_print(r
, stdout
);
210 #endif /* TEST_PROGRAM */