[thirdparty/e2fsprogs.git] / e2fsck / region.c

/*
 * region.c --- code which manages allocations within a region.
 *
 * Copyright (C) 2001 Theodore Ts'o.
 *
 * %Begin-Header%
 * This file may be redistributed under the terms of the GNU Public
 * License.
 * %End-Header%
 */

#include "config.h"
#if HAVE_UNISTD_H
#include <unistd.h>
#endif
#include <string.h>

#ifdef TEST_PROGRAM
#undef ENABLE_NLS
#endif
#include "e2fsck.h"

struct region_el {
	region_addr_t	start;
	region_addr_t	end;
	struct region_el *next;
};

struct region_struct {
	region_addr_t	min;
	region_addr_t	max;
	struct region_el *allocated;
};

region_t region_create(region_addr_t min, region_addr_t max)
{
	region_t	region;

	region = malloc(sizeof(struct region_struct));
	if (!region)
		return NULL;
	memset(region, 0, sizeof(struct region_struct));
	region->min = min;
	region->max = max;
	return region;
}

void region_free(region_t region)
{
	struct region_el	*r, *next;

	for (r = region->allocated; r; r = next) {
		next = r->next;
		free(r);
	}
	memset(region, 0, sizeof(struct region_struct));
	free(region);
}

int region_allocate(region_t region, region_addr_t start, int n)
{
	struct region_el	*r, *new_region, *prev, *next;
	region_addr_t end;

	end = start+n;
	if ((start < region->min) || (end > region->max))
		return -1;
	if (n == 0)
		return 1;

	/*
	 * Search through the linked list.  If we find that it
	 * conflicts witih something that's already allocated, return
	 * 1; if we can find an existing region which we can grow, do
	 * so.  Otherwise, stop when we find the appropriate place
	 * insert a new region element into the linked list.
	 */
	for (r = region->allocated, prev=NULL; r; prev = r, r = r->next) {
		if (((start >= r->start) && (start < r->end)) ||
		    ((end > r->start) && (end <= r->end)) ||
		    ((start <= r->start) && (end >= r->end)))
			return 1;
		if (end == r->start) {
			r->start = start;
			return 0;
		}
		if (start == r->end) {
			if ((next = r->next)) {
				if (end > next->start)
					return 1;
				if (end == next->start) {
					r->end = next->end;
					r->next = next->next;
					free(next);
					return 0;
				}
			}
			r->end = end;
			return 0;
		}
		if (start < r->start)
			break;
	}
	/*
	 * Insert a new region element structure into the linked list
	 */
	new_region = malloc(sizeof(struct region_el));
	if (!new_region)
		return -1;
	new_region->start = start;
	new_region->end = start + n;
	new_region->next = r;
	if (prev)
		prev->next = new_region;
	else
		region->allocated = new_region;
	return 0;
}

#ifdef TEST_PROGRAM
#include <stdio.h>

#define BCODE_END	0
#define BCODE_CREATE	1
#define BCODE_FREE	2
#define BCODE_ALLOCATE	3
#define BCODE_PRINT	4

int bcode_program[] = {
	BCODE_CREATE, 1, 1001,
	BCODE_PRINT,
	BCODE_ALLOCATE, 10, 10,
	BCODE_ALLOCATE, 30, 10,
	BCODE_PRINT,
	BCODE_ALLOCATE, 1, 15,
	BCODE_ALLOCATE, 15, 8,
	BCODE_ALLOCATE, 1, 20,
	BCODE_ALLOCATE, 1, 8,
	BCODE_PRINT,
	BCODE_ALLOCATE, 40, 10,
	BCODE_PRINT,
	BCODE_ALLOCATE, 22, 5,
	BCODE_PRINT,
	BCODE_ALLOCATE, 27, 3,
	BCODE_PRINT,
	BCODE_ALLOCATE, 20, 2,
	BCODE_PRINT,
	BCODE_ALLOCATE, 49, 1,
	BCODE_ALLOCATE, 50, 5,
	BCODE_ALLOCATE, 9, 2,
	BCODE_ALLOCATE, 9, 1,
	BCODE_PRINT,
	BCODE_FREE,
	BCODE_END
};

void region_print(region_t region, FILE *f)
{
	struct region_el	*r;
	int	i = 0;

	fprintf(f, "Printing region (min=%d. max=%d)\n\t", region->min,
		region->max);
	for (r = region->allocated; r; r = r->next) {
		fprintf(f, "(%d, %d)  ", r->start, r->end);
		if (++i >= 8)
			fprintf(f, "\n\t");
	}
	fprintf(f, "\n");
}

int main(int argc, char **argv)
{
	region_t	r;
	int		pc = 0, ret;
	region_addr_t	start, end;


	while (1) {
		switch (bcode_program[pc++]) {
		case BCODE_END:
			exit(0);
		case BCODE_CREATE:
			start = bcode_program[pc++];
			end = bcode_program[pc++];
			printf("Creating region with args(%d, %d)\n",
			       start, end);
			r = region_create(start, end);
			if (!r) {
				fprintf(stderr, "Couldn't create region.\n");
				exit(1);
			}
			break;
		case BCODE_ALLOCATE:
			start = bcode_program[pc++];
			end = bcode_program[pc++];
			ret = region_allocate(r, start, end);
			printf("Region_allocate(%d, %d) returns %d\n",
			       start, end, ret);
			break;
		case BCODE_PRINT:
			region_print(r, stdout);
			break;
		}
	}
}

#endif /* TEST_PROGRAM */
Commit	Line	Data
55fd07ed TT	1	/*
55fd07ed TT	2	* region.c --- code which manages allocations within a region.
efc6f628	3	*
55fd07ed TT	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
d1154eb4	12	#include "config.h"
55fd07ed TT	13	#if HAVE_UNISTD_H
	14	#include <unistd.h>
	15	#endif
	16	#include <string.h>
	17
0eeec8ac TT	18	#ifdef TEST_PROGRAM
	19	#undef ENABLE_NLS
	20	#endif
55fd07ed TT	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
	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
	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
	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
157	void region_print(region_t region, FILE *f)
158	{
159	struct region_el *r;
160	int i = 0;
efc6f628	161
55fd07ed TT	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
	172	int main(int argc, char **argv)
	173	{
	174	region_t r;
	175	int pc = 0, ret;
6b56f3d9	176	region_addr_t start, end;
55fd07ed	177
efc6f628	178
55fd07ed TT	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 */