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