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 };
  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=%d. max=%d)\n\t", region->min,
 163                 region->max);
 164         for (r = region->allocated; r; r = r->next) {
 165                 fprintf(f, "(%d, %d)  ", 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(%d, %d)\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(%d, %d) 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 */