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