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
  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 */