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)
41 retval = ext2fs_get_memzero(sizeof(struct region_struct), ®ion);
51 void region_free(region_t region)
53 struct region_el *r, *next;
55 for (r = region->allocated; r; r = next) {
59 memset(region, 0, sizeof(struct region_struct));
60 ext2fs_free_mem(®ion);
63 int region_allocate(region_t region, region_addr_t start, int n)
65 struct region_el *r, *new_region, *prev, *next;
70 if ((start < region->min) || (end > region->max))
75 if (region->last && region->last->end == start &&
76 !region->last->next) {
77 region->last->end = end;
80 if (region->last && start > region->last->end &&
81 !region->last->next) {
88 * Search through the linked list. If we find that it
89 * conflicts with something that's already allocated, return
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.
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)))
99 if (end == r->start) {
103 if (start == r->end) {
104 if ((next = r->next)) {
105 if (end > next->start)
107 if (end == next->start) {
109 r->next = next->next;
110 ext2fs_free_mem(&next);
119 if (start < r->start)
123 * Insert a new region element structure into the linked list
126 retval = ext2fs_get_mem(sizeof(struct region_el), &new_region);
129 new_region->start = start;
130 new_region->end = start + n;
131 new_region->next = r;
132 if (!new_region->next)
133 region->last = new_region;
135 prev->next = new_region;
137 region->allocated = new_region;
145 #define BCODE_CREATE 1
147 #define BCODE_ALLOCATE 3
148 #define BCODE_PRINT 4
150 int bcode_program[] = {
151 BCODE_CREATE, 1, 1001,
153 BCODE_ALLOCATE, 10, 10,
154 BCODE_ALLOCATE, 30, 10,
156 BCODE_ALLOCATE, 1, 15,
157 BCODE_ALLOCATE, 15, 8,
158 BCODE_ALLOCATE, 1, 20,
159 BCODE_ALLOCATE, 1, 8,
161 BCODE_ALLOCATE, 40, 10,
163 BCODE_ALLOCATE, 22, 5,
165 BCODE_ALLOCATE, 27, 3,
167 BCODE_ALLOCATE, 20, 2,
169 BCODE_ALLOCATE, 49, 1,
170 BCODE_ALLOCATE, 50, 5,
171 BCODE_ALLOCATE, 9, 2,
172 BCODE_ALLOCATE, 9, 1,
178 void region_print(region_t region, FILE *f)
183 fprintf(f, "Printing region (min=%llu. max=%llu)\n\t",
184 (unsigned long long) region->min,
185 (unsigned long long) region->max);
186 for (r = region->allocated; r; r = r->next) {
187 fprintf(f, "(%llu, %llu) ",
188 (unsigned long long) r->start,
189 (unsigned long long) r->end);
196 int main(int argc, char **argv)
200 region_addr_t start, end;
204 switch (bcode_program[pc++]) {
208 start = bcode_program[pc++];
209 end = bcode_program[pc++];
210 printf("Creating region with args(%llu, %llu)\n",
211 (unsigned long long) start,
212 (unsigned long long) end);
213 r = region_create(start, end);
215 fprintf(stderr, "Couldn't create region.\n");
220 start = bcode_program[pc++];
221 end = bcode_program[pc++];
222 ret = region_allocate(r, start, end);
223 printf("Region_allocate(%llu, %llu) returns %d\n",
224 (unsigned long long) start,
225 (unsigned long long) end, ret);
228 region_print(r, stdout);
236 #endif /* TEST_PROGRAM */