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
22 struct region_el *next;
25 struct region_struct {
28 struct region_el *allocated;
31 region_t region_create(region_addr_t min, region_addr_t max)
35 region = malloc(sizeof(struct region_struct));
38 memset(region, 0, sizeof(struct region_struct));
44 void region_free(region_t region)
46 struct region_el *r, *next;
48 for (r = region->allocated; r; r = next) {
52 memset(region, 0, sizeof(struct region_struct));
56 int region_allocate(region_t region, region_addr_t start, int n)
58 struct region_el *r, *new_region, *prev, *next;
62 if ((start < region->min) || (end > region->max))
68 * Search through the linked list. If we find that it
69 * conflicts witih something that's already allocated, return
70 * 1; if we can find an existing region which we can grow, do
71 * so. Otherwise, stop when we find the appropriate place
72 * insert a new region element into the linked list.
74 for (r = region->allocated, prev=NULL; r; prev = r, r = r->next) {
75 if (((start >= r->start) && (start < r->end)) ||
76 ((end > r->start) && (end <= r->end)) ||
77 ((start <= r->start) && (end >= r->end)))
79 if (end == r->start) {
83 if (start == r->end) {
84 if ((next = r->next)) {
85 if (end > next->start)
87 if (end == next->start) {
101 * Insert a new region element structure into the linked list
103 new_region = malloc(sizeof(struct region_el));
106 new_region->start = start;
107 new_region->end = start + n;
108 new_region->next = r;
110 prev->next = new_region;
112 region->allocated = new_region;
120 #define BCODE_CREATE 1
122 #define BCODE_ALLOCATE 3
123 #define BCODE_PRINT 4
125 int bcode_program[] = {
126 BCODE_CREATE, 1, 1001,
128 BCODE_ALLOCATE, 10, 10,
129 BCODE_ALLOCATE, 30, 10,
131 BCODE_ALLOCATE, 1, 15,
132 BCODE_ALLOCATE, 15, 8,
133 BCODE_ALLOCATE, 1, 20,
134 BCODE_ALLOCATE, 1, 8,
136 BCODE_ALLOCATE, 40, 10,
138 BCODE_ALLOCATE, 22, 5,
140 BCODE_ALLOCATE, 27, 3,
142 BCODE_ALLOCATE, 20, 2,
144 BCODE_ALLOCATE, 49, 1,
145 BCODE_ALLOCATE, 50, 5,
146 BCODE_ALLOCATE, 9, 2,
147 BCODE_ALLOCATE, 9, 1,
153 void region_print(region_t region, FILE *f)
158 fprintf(f, "Printing region (min=%d. max=%d)\n\t", region->min,
160 for (r = region->allocated; r; r = r->next) {
161 fprintf(f, "(%d, %d) ", r->start, r->end);
168 int main(int argc, char **argv)
172 region_addr_t start, end, len;
176 switch (bcode_program[pc++]) {
180 start = bcode_program[pc++];
181 end = bcode_program[pc++];
182 printf("Creating region with args(%d, %d)\n",
184 r = region_create(start, end);
186 fprintf(stderr, "Couldn't create region.\n");
191 start = bcode_program[pc++];
192 end = bcode_program[pc++];
193 ret = region_allocate(r, start, end);
194 printf("Region_allocate(%d, %d) returns %d\n",
198 region_print(r, stdout);
204 #endif /* TEST_PROGRAM */