region.c revision 18a1444b4f1e6a0948fd38fa0de382d86cfe04de 
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
22struct region_el {
23	region_addr_t	start;
24	region_addr_t	end;
25	struct region_el *next;
26};
27
28struct region_struct {
29	region_addr_t	min;
30	region_addr_t	max;
31	struct region_el *allocated;
32};
33
34region_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
47void 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
59int 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
128int 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
156void 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
171int 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