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