e2fsck/region.c

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