1 /*
2 * region.c --- code which manages allocations within a region.
3 *
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
12 #if HAVE_UNISTD_H
13 #include <unistd.h>
14 #endif
15 #include <string.h>
16
17 #include "e2fsck.h"
18
19 struct region_el {
20 region_addr_t start;
21 region_addr_t end;
22 struct region_el *next;
23 };
24
25 struct region_struct {
26 region_addr_t min;
27 region_addr_t max;
28 struct region_el *allocated;
29 };
30
region_create(region_addr_t min,region_addr_t max)31 region_t region_create(region_addr_t min, region_addr_t max)
32 {
33 region_t region;
34
35 region = malloc(sizeof(struct region_struct));
36 if (!region)
37 return NULL;
38 memset(region, 0, sizeof(struct region_struct));
39 region->min = min;
40 region->max = max;
41 return region;
42 }
43
region_free(region_t region)44 void region_free(region_t region)
45 {
46 struct region_el *r, *next;
47
48 for (r = region->allocated; r; r = next) {
49 next = r->next;
50 free(r);
51 }
52 memset(region, 0, sizeof(struct region_struct));
53 free(region);
54 }
55
region_allocate(region_t region,region_addr_t start,int n)56 int region_allocate(region_t region, region_addr_t start, int n)
57 {
58 struct region_el *r, *new_region, *prev, *next;
59 region_addr_t end;
60
61 end = start+n;
62 if ((start < region->min) || (end > region->max))
63 return -1;
64 if (n == 0)
65 return 1;
66
67 /*
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.
73 */
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)))
78 return 1;
79 if (end == r->start) {
80 r->start = start;
81 return 0;
82 }
83 if (start == r->end) {
84 if ((next = r->next)) {
85 if (end > next->start)
86 return 1;
87 if (end == next->start) {
88 r->end = next->end;
89 r->next = next->next;
90 free(next);
91 return 0;
92 }
93 }
94 r->end = end;
95 return 0;
96 }
97 if (start < r->start)
98 break;
99 }
100 /*
101 * Insert a new region element structure into the linked list
102 */
103 new_region = malloc(sizeof(struct region_el));
104 if (!new_region)
105 return -1;
106 new_region->start = start;
107 new_region->end = start + n;
108 new_region->next = r;
109 if (prev)
110 prev->next = new_region;
111 else
112 region->allocated = new_region;
113 return 0;
114 }
115
116 #ifdef TEST_PROGRAM
117 #include <stdio.h>
118
119 #define BCODE_END 0
120 #define BCODE_CREATE 1
121 #define BCODE_FREE 2
122 #define BCODE_ALLOCATE 3
123 #define BCODE_PRINT 4
124
125 int bcode_program[] = {
126 BCODE_CREATE, 1, 1001,
127 BCODE_PRINT,
128 BCODE_ALLOCATE, 10, 10,
129 BCODE_ALLOCATE, 30, 10,
130 BCODE_PRINT,
131 BCODE_ALLOCATE, 1, 15,
132 BCODE_ALLOCATE, 15, 8,
133 BCODE_ALLOCATE, 1, 20,
134 BCODE_ALLOCATE, 1, 8,
135 BCODE_PRINT,
136 BCODE_ALLOCATE, 40, 10,
137 BCODE_PRINT,
138 BCODE_ALLOCATE, 22, 5,
139 BCODE_PRINT,
140 BCODE_ALLOCATE, 27, 3,
141 BCODE_PRINT,
142 BCODE_ALLOCATE, 20, 2,
143 BCODE_PRINT,
144 BCODE_ALLOCATE, 49, 1,
145 BCODE_ALLOCATE, 50, 5,
146 BCODE_ALLOCATE, 9, 2,
147 BCODE_ALLOCATE, 9, 1,
148 BCODE_PRINT,
149 BCODE_FREE,
150 BCODE_END
151 };
152
region_print(region_t region,FILE * f)153 void region_print(region_t region, FILE *f)
154 {
155 struct region_el *r;
156 int i = 0;
157
158 fprintf(f, "Printing region (min=%d. max=%d)\n\t", region->min,
159 region->max);
160 for (r = region->allocated; r; r = r->next) {
161 fprintf(f, "(%d, %d) ", r->start, r->end);
162 if (++i >= 8)
163 fprintf(f, "\n\t");
164 }
165 fprintf(f, "\n");
166 }
167
main(int argc,char ** argv)168 int main(int argc, char **argv)
169 {
170 region_t r;
171 int pc = 0, ret;
172 region_addr_t start, end, len;
173
174
175 while (1) {
176 switch (bcode_program[pc++]) {
177 case BCODE_END:
178 exit(0);
179 case BCODE_CREATE:
180 start = bcode_program[pc++];
181 end = bcode_program[pc++];
182 printf("Creating region with args(%d, %d)\n",
183 start, end);
184 r = region_create(start, end);
185 if (!r) {
186 fprintf(stderr, "Couldn't create region.\n");
187 exit(1);
188 }
189 break;
190 case BCODE_ALLOCATE:
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",
195 start, end, ret);
196 break;
197 case BCODE_PRINT:
198 region_print(r, stdout);
199 break;
200 }
201 }
202 }
203
204 #endif /* TEST_PROGRAM */
205