Home | History | Annotate | Download | only in e2fsck
      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 
     22 struct region_el {
     23 	region_addr_t	start;
     24 	region_addr_t	end;
     25 	struct region_el *next;
     26 };
     27 
     28 struct region_struct {
     29 	region_addr_t	min;
     30 	region_addr_t	max;
     31 	struct region_el *allocated;
     32 };
     33 
     34 region_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 
     47 void 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 
     59 int 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 
    128 int 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 
    156 void 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 
    171 int main(int argc, char **argv)
    172 {
    173 	region_t	r;
    174 	int		pc = 0, ret;
    175 	region_addr_t	start, end, len;
    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