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 }; 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; 161 162 fprintf(f, "Printing region (min=%llu. max=%llu)\n\t", region->min, 163 region->max); 164 for (r = region->allocated; r; r = r->next) { 165 fprintf(f, "(%llu, %llu) ", 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 = NULL; 175 int pc = 0, ret; 176 region_addr_t start, end; 177 178 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(%llu, %llu)\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(%llu, %llu) returns %d\n", 199 start, end, ret); 200 break; 201 case BCODE_PRINT: 202 region_print(r, stdout); 203 break; 204 } 205 } 206 if (r) 207 region_free(r); 208 } 209 210 #endif /* TEST_PROGRAM */ 211
