region.c revision 55fd07ed0a5f4ed3dcc770526ee1ad3be967ac98 
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
19struct region_el {
20	region_addr_t	start;
21	region_addr_t	end;
22	struct region_el *next;
23};
24
25struct region_struct {
26	region_addr_t	min;
27	region_addr_t	max;
28	struct region_el *allocated;
29};
30
31region_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
44void 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
56int 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
125int 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
153void 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
168int 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