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