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