region.c revision 00eb0eee0addfd3b7ede98b85e00dff1547838a0 
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
23struct region_el {
24	region_addr_t	start;
25	region_addr_t	end;
26	struct region_el *next;
27};
28
29struct region_struct {
30	region_addr_t	min;
31	region_addr_t	max;
32	struct region_el *allocated;
33};
34
35region_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
48void 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
60int 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
129int 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
157void region_print(region_t region, FILE *f)
158{
159	struct region_el	*r;
160	int	i = 0;
161
162	fprintf(f, "Printing region (min=%d. max=%d)\n\t", region->min,
163		region->max);
164	for (r = region->allocated; r; r = r->next) {
165		fprintf(f, "(%d, %d)  ", r->start, r->end);
166		if (++i >= 8)
167			fprintf(f, "\n\t");
168	}
169	fprintf(f, "\n");
170}
171
172int 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(%d, %d)\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(%d, %d) returns %d\n",
199			       start, end, ret);
200			break;
201		case BCODE_PRINT:
202			region_print(r, stdout);
203			break;
204		}
205	}
206}
207
208#endif /* TEST_PROGRAM */
209