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 = 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
