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 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 struct region_el *last; 34 }; 35 36 region_t region_create(region_addr_t min, region_addr_t max) 37 { 38 region_t region; 39 40 region = malloc(sizeof(struct region_struct)); 41 if (!region) 42 return NULL; 43 memset(region, 0, sizeof(struct region_struct)); 44 region->min = min; 45 region->max = max; 46 region->last = NULL; 47 return region; 48 } 49 50 void region_free(region_t region) 51 { 52 struct region_el *r, *next; 53 54 for (r = region->allocated; r; r = next) { 55 next = r->next; 56 free(r); 57 } 58 memset(region, 0, sizeof(struct region_struct)); 59 free(region); 60 } 61 62 int region_allocate(region_t region, region_addr_t start, int n) 63 { 64 struct region_el *r, *new_region, *prev, *next; 65 region_addr_t end; 66 67 end = start+n; 68 if ((start < region->min) || (end > region->max)) 69 return -1; 70 if (n == 0) 71 return 1; 72 73 if (region->last && region->last->end == start && 74 !region->last->next) { 75 region->last->end = end; 76 return 0; 77 } 78 if (region->last && start > region->last->end && 79 !region->last->next) { 80 r = NULL; 81 prev = region->last; 82 goto append_to_list; 83 } 84 85 /* 86 * Search through the linked list. If we find that it 87 * conflicts with something that's already allocated, return 88 * 1; if we can find an existing region which we can grow, do 89 * so. Otherwise, stop when we find the appropriate place 90 * insert a new region element into the linked list. 91 */ 92 for (r = region->allocated, prev=NULL; r; prev = r, r = r->next) { 93 if (((start >= r->start) && (start < r->end)) || 94 ((end > r->start) && (end <= r->end)) || 95 ((start <= r->start) && (end >= r->end))) 96 return 1; 97 if (end == r->start) { 98 r->start = start; 99 return 0; 100 } 101 if (start == r->end) { 102 if ((next = r->next)) { 103 if (end > next->start) 104 return 1; 105 if (end == next->start) { 106 r->end = next->end; 107 r->next = next->next; 108 free(next); 109 if (!r->next) 110 region->last = r; 111 return 0; 112 } 113 } 114 r->end = end; 115 return 0; 116 } 117 if (start < r->start) 118 break; 119 } 120 /* 121 * Insert a new region element structure into the linked list 122 */ 123 append_to_list: 124 new_region = malloc(sizeof(struct region_el)); 125 if (!new_region) 126 return -1; 127 new_region->start = start; 128 new_region->end = start + n; 129 new_region->next = r; 130 if (!new_region->next) 131 region->last = new_region; 132 if (prev) 133 prev->next = new_region; 134 else 135 region->allocated = new_region; 136 return 0; 137 } 138 139 #ifdef TEST_PROGRAM 140 #include <stdio.h> 141 142 #define BCODE_END 0 143 #define BCODE_CREATE 1 144 #define BCODE_FREE 2 145 #define BCODE_ALLOCATE 3 146 #define BCODE_PRINT 4 147 148 int bcode_program[] = { 149 BCODE_CREATE, 1, 1001, 150 BCODE_PRINT, 151 BCODE_ALLOCATE, 10, 10, 152 BCODE_ALLOCATE, 30, 10, 153 BCODE_PRINT, 154 BCODE_ALLOCATE, 1, 15, 155 BCODE_ALLOCATE, 15, 8, 156 BCODE_ALLOCATE, 1, 20, 157 BCODE_ALLOCATE, 1, 8, 158 BCODE_PRINT, 159 BCODE_ALLOCATE, 40, 10, 160 BCODE_PRINT, 161 BCODE_ALLOCATE, 22, 5, 162 BCODE_PRINT, 163 BCODE_ALLOCATE, 27, 3, 164 BCODE_PRINT, 165 BCODE_ALLOCATE, 20, 2, 166 BCODE_PRINT, 167 BCODE_ALLOCATE, 49, 1, 168 BCODE_ALLOCATE, 50, 5, 169 BCODE_ALLOCATE, 9, 2, 170 BCODE_ALLOCATE, 9, 1, 171 BCODE_PRINT, 172 BCODE_FREE, 173 BCODE_END 174 }; 175 176 void region_print(region_t region, FILE *f) 177 { 178 struct region_el *r; 179 int i = 0; 180 181 fprintf(f, "Printing region (min=%llu. max=%llu)\n\t", region->min, 182 region->max); 183 for (r = region->allocated; r; r = r->next) { 184 fprintf(f, "(%llu, %llu) ", r->start, r->end); 185 if (++i >= 8) 186 fprintf(f, "\n\t"); 187 } 188 fprintf(f, "\n"); 189 } 190 191 int main(int argc, char **argv) 192 { 193 region_t r = NULL; 194 int pc = 0, ret; 195 region_addr_t start, end; 196 197 198 while (1) { 199 switch (bcode_program[pc++]) { 200 case BCODE_END: 201 exit(0); 202 case BCODE_CREATE: 203 start = bcode_program[pc++]; 204 end = bcode_program[pc++]; 205 printf("Creating region with args(%llu, %llu)\n", 206 start, end); 207 r = region_create(start, end); 208 if (!r) { 209 fprintf(stderr, "Couldn't create region.\n"); 210 exit(1); 211 } 212 break; 213 case BCODE_ALLOCATE: 214 start = bcode_program[pc++]; 215 end = bcode_program[pc++]; 216 ret = region_allocate(r, start, end); 217 printf("Region_allocate(%llu, %llu) returns %d\n", 218 start, end, ret); 219 break; 220 case BCODE_PRINT: 221 region_print(r, stdout); 222 break; 223 } 224 } 225 if (r) 226 region_free(r); 227 } 228 229 #endif /* TEST_PROGRAM */ 230
