bsd/hfs/rangelist.c

   1 /*
   2  * Copyright (c) 2001 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22
  23 #include <sys/param.h>
  24 #include <mach/boolean.h>
  25 #include <sys/time.h>
  26 #include <sys/malloc.h>
  27
  28 #include "rangelist.h"
  29
  30 static enum rl_overlaptype rl_scan_from(struct rl_head *rangelist, off_t start, off_t end, struct rl_entry **overlap, struct rl_entry *range);
  31 static void rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range);
  32 static void rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range);
  33 static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range);
  34
  35
  36 #ifdef RL_DIAGNOSTIC
  37 static void
  38 rl_verify(struct rl_head *rangelist) {
  39         struct rl_entry *entry;
  40         off_t limit = 0;
  41
  42         if (CIRCLEQ_EMPTY(rangelist)) return;
  43         entry = CIRCLEQ_FIRST(rangelist);
  44         while (1) {
  45                 if (CIRCLEQ_NEXT(entry, rl_link) == entry) panic("rl_verify: circular rangelist?!");
  46                 if ((limit > 0) && (entry->rl_start <= limit)) panic("rl_verify: bad entry start?!");
  47                 if (entry->rl_end < entry->rl_start) panic("rl_verify: bad entry end?!");
  48                 limit = entry->rl_end;
  49                 if (entry == CIRCLEQ_LAST(rangelist)) return;
  50                 entry = CIRCLEQ_NEXT(entry, rl_link);
  51         };
  52 }
  53 #endif
  54
  55
  56
  57 /*
  58  * Initialize a range list head
  59  */
  60 void
  61 rl_init(struct rl_head *rangelist)
  62 {
  63     CIRCLEQ_INIT(rangelist);
  64 }
  65
  66
  67
  68 /*
  69  * Add a range to the list
  70  */
  71 void
  72 rl_add(off_t start, off_t end, struct rl_head *rangelist)
  73 {
  74         struct rl_entry *range;
  75         struct rl_entry *overlap;
  76         enum rl_overlaptype ovcase;
  77
  78 #ifdef RL_DIAGNOSTIC
  79         if (end < start) panic("rl_add: end < start?!");
  80 #endif
  81
  82         ovcase = rl_scan(rangelist, start, end, &overlap);
  83
  84         /*
  85          * Six cases:
  86          *      0) no overlap
  87          *      1) overlap == range
  88          *      2) overlap contains range
  89          *      3) range contains overlap
  90          *      4) overlap starts before range
  91          *      5) overlap ends after range
  92          */
  93         switch (ovcase) {
  94                 case RL_NOOVERLAP: /* 0: no overlap */
  95                         /*
  96                                 * If the list was empty 'prev' is undisturbed and 'overlap' == NULL;
  97                                 * if the search hit a non-overlapping entry PAST the start of the
  98                                 * new range, 'prev' points to ITS predecessor, and 'overlap' points
  99                                 * to that entry:
 100                                 */
 101                         MALLOC(range, struct rl_entry *, sizeof(*range), M_TEMP, M_WAITOK);
 102                         range->rl_start = start;
 103                         range->rl_end = end;
 104
 105                         /* Link in the new range: */
 106                         if (overlap) {
 107                                 CIRCLEQ_INSERT_AFTER(rangelist, overlap, range, rl_link);
 108                         } else {
 109                                 CIRCLEQ_INSERT_HEAD(rangelist, range, rl_link);
 110                         }
 111
 112                         /* Check to see if any ranges can be combined (possibly including the immediately
 113                            preceding range entry)
 114                          */
 115                         rl_collapse_neighbors(rangelist, range);
 116                         break;
 117
 118                 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
 119                 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range */
 120                         range = overlap; /* for debug output below */
 121                         break;
 122
 123                 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
 124                         /*
 125                          * Replace the overlap with the new, larger range:
 126                          */
 127                         overlap->rl_start = start;
 128                         overlap->rl_end = end;
 129                         rl_collapse_neighbors(rangelist, overlap);
 130                         range = overlap; /* for debug output below */
 131                         break;
 132
 133                 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
 134                         /*
 135                          * Expand the overlap area to cover the new range:
 136                          */
 137                         overlap->rl_end = end;
 138                         rl_collapse_forwards(rangelist, overlap);
 139                         range = overlap; /* for debug output below */
 140                         break;
 141
 142                 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
 143                         /*
 144                          * Expand the overlap area to cover the new range:
 145                          */
 146                         overlap->rl_start = start;
 147                         rl_collapse_backwards(rangelist, overlap);
 148                         range = overlap; /* for debug output below */
 149                         break;
 150         }
 151
 152 #ifdef RL_DIAGNOSTIC
 153         rl_verify(rangelist);
 154 #endif
 155 }
 156
 157
 158
 159 /*
 160  * Remove a range from a range list.
 161  *
 162  * Generally, find the range (or an overlap to that range)
 163  * and remove it (or shrink it), then wakeup anyone we can.
 164  */
 165 void
 166 rl_remove(off_t start, off_t end, struct rl_head *rangelist)
 167 {
 168         struct rl_entry *range, *next_range, *overlap, *splitrange;
 169         int ovcase, moretotest;
 170
 171 #ifdef RL_DIAGNOSTIC
 172         if (end < start) panic("rl_remove: end < start?!");
 173 #endif
 174
 175         if (CIRCLEQ_EMPTY(rangelist)) {
 176                 return;
 177         };
 178
 179         range = CIRCLEQ_FIRST(rangelist);
 180         while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
 181                 switch (ovcase) {
 182
 183                 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
 184                         CIRCLEQ_REMOVE(rangelist, overlap, rl_link);
 185                         FREE(overlap, M_TEMP);
 186                         break;
 187
 188                 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range: split it */
 189                         if (overlap->rl_start == start) {
 190                                 overlap->rl_start = end + 1;
 191                                 break;
 192                         };
 193
 194                         if (overlap->rl_end == end) {
 195                                 overlap->rl_end = start - 1;
 196                                 break;
 197                         };
 198
 199                         /*
 200                         * Make a new range consisting of the last part of the encompassing range
 201                         */
 202                         MALLOC(splitrange, struct rl_entry *, sizeof *splitrange, M_TEMP, M_WAITOK);
 203                         splitrange->rl_start = end + 1;
 204                         splitrange->rl_end = overlap->rl_end;
 205                         overlap->rl_end = start - 1;
 206
 207                         /*
 208                         * Now link the new entry into the range list after the range from which it was split:
 209                         */
 210                         CIRCLEQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
 211                         break;
 212
 213                 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
 214                         moretotest = (overlap != CIRCLEQ_LAST(rangelist));
 215 #ifdef RL_DIAGNOSTIC
 216                         if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!");
 217 #endif
 218                         next_range = CIRCLEQ_NEXT(overlap, rl_link);    /* Check before discarding overlap entry */
 219                         CIRCLEQ_REMOVE(rangelist, overlap, rl_link);
 220                         FREE(overlap, M_TEMP);
 221                         if (moretotest) {
 222                                 range = next_range;
 223                                 continue;
 224                         };
 225                         break;
 226
 227                 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
 228                         moretotest = (overlap != CIRCLEQ_LAST(rangelist));
 229                         overlap->rl_end = start - 1;
 230                         if (moretotest) {
 231 #ifdef RL_DIAGNOSTIC
 232                                 if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!");
 233 #endif
 234                                 range = CIRCLEQ_NEXT(overlap, rl_link);
 235                                 continue;
 236                         };
 237                         break;
 238
 239                 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
 240                         overlap->rl_start = (end == RL_INFINITY ? RL_INFINITY : end + 1);
 241                         break;
 242                 }
 243                 break;
 244         }
 245
 246 #ifdef RL_DIAGNOSTIC
 247         rl_verify(rangelist);
 248 #endif
 249 }
 250
 251
 252
 253 /*
 254  * Scan a range list for an entry in a specified range (if any):
 255  *
 256  * NOTE: this returns only the FIRST overlapping range.
 257  *           There may be more than one.
 258  */
 259
 260 enum rl_overlaptype
 261 rl_scan(struct rl_head *rangelist,
 262                 off_t start,
 263                 off_t end,
 264                 struct rl_entry **overlap) {
 265
 266         if (CIRCLEQ_EMPTY(rangelist)) {
 267                 *overlap = NULL;
 268                 return RL_NOOVERLAP;
 269         };
 270
 271         return rl_scan_from(rangelist, start, end, overlap, CIRCLEQ_FIRST(rangelist));
 272 }
 273
 274
 275
 276 /*
 277  * Walk the list of ranges for an entry to
 278  * find an overlapping range (if any).
 279  *
 280  * NOTE: this returns only the FIRST overlapping range.
 281  *           There may be more than one.
 282  */
 283 static enum rl_overlaptype
 284 rl_scan_from(struct rl_head *rangelist,
 285                          off_t start,
 286                          off_t end,
 287                          struct rl_entry **overlap,
 288                         struct rl_entry *range)
 289 {
 290         if (CIRCLEQ_EMPTY(rangelist)) {
 291                 *overlap = NULL;
 292                 return RL_NOOVERLAP;
 293         };
 294
 295 #ifdef RL_DIAGNOSTIC
 296                 rl_verify(rangelist);
 297 #endif
 298
 299         *overlap = range;
 300
 301         while (1) {
 302                 /*
 303                  * OK, check for overlap
 304                  *
 305                  * Six cases:
 306                  *      0) no overlap (RL_NOOVERLAP)
 307                  *      1) overlap == range (RL_MATCHINGOVERLAP)
 308                  *      2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
 309                  *      3) range contains overlap (RL_OVERLAPISCONTAINED)
 310                  *      4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
 311                  *      5) overlap ends after range (RL_OVERLAPENDSAFTER)
 312                  */
 313                 if (((range->rl_end != RL_INFINITY) && (start > range->rl_end)) ||
 314                         ((end != RL_INFINITY) && (range->rl_start > end))) {
 315                         /* Case 0 (RL_NOOVERLAP), at least with the current entry: */
 316                         if ((end != RL_INFINITY) && (range->rl_start > end)) {
 317                                 return RL_NOOVERLAP;
 318                         };
 319
 320                         /* Check the other entries in the list: */
 321                         if (range == CIRCLEQ_LAST(rangelist)) {
 322                                 return RL_NOOVERLAP;
 323                         };
 324 #ifdef RL_DIAGNOSTIC
 325                         if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_scan_from: circular range list?!");
 326 #endif
 327                         *overlap = range = CIRCLEQ_NEXT(range, rl_link);
 328                         continue;
 329                 }
 330
 331                 if ((range->rl_start == start) && (range->rl_end == end)) {
 332                         /* Case 1 (RL_MATCHINGOVERLAP) */
 333                         return RL_MATCHINGOVERLAP;
 334                 }
 335
 336                 if ((range->rl_start <= start) &&
 337                         (end != RL_INFINITY) &&
 338                         ((range->rl_end >= end) || (range->rl_end == RL_INFINITY))) {
 339                                 /* Case 2 (RL_OVERLAPCONTAINSRANGE) */
 340                         return RL_OVERLAPCONTAINSRANGE;
 341                 }
 342
 343                 if ((start <= range->rl_start) &&
 344                         ((end == RL_INFINITY) ||
 345                          ((range->rl_end != RL_INFINITY) && (end >= range->rl_end)))) {
 346                         /* Case 3 (RL_OVERLAPISCONTAINED) */
 347                         return RL_OVERLAPISCONTAINED;
 348                 }
 349
 350                 if ((range->rl_start < start) &&
 351                         ((range->rl_end >= start) || (range->rl_end == RL_INFINITY))) {
 352                         /* Case 4 (RL_OVERLAPSTARTSBEFORE) */
 353                         return RL_OVERLAPSTARTSBEFORE;
 354                 }
 355
 356                 if ((range->rl_start > start) &&
 357                         (end != RL_INFINITY) &&
 358                         ((range->rl_end > end) || (range->rl_end == RL_INFINITY))) {
 359                         /* Case 5 (RL_OVERLAPENDSAFTER) */
 360                         return RL_OVERLAPENDSAFTER;
 361                 }
 362
 363                 /* Control should never reach here... */
 364 #ifdef RL_DIAGNOSTIC
 365                 panic("rl_scan_from: unhandled overlap condition?!");
 366 #endif
 367         }
 368
 369         return RL_NOOVERLAP;
 370 }
 371
 372
 373 static void
 374 rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {
 375     struct rl_entry *next_range;
 376
 377     while (1) {
 378                 if (range == CIRCLEQ_LAST(rangelist)) return;
 379
 380 #ifdef RL_DIAGNOSTIC
 381                 if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_collapse_forwards: circular range list?!");
 382 #endif
 383                 next_range = CIRCLEQ_NEXT(range, rl_link);
 384         if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
 385
 386         /* Expand this range to include the next range: */
 387         range->rl_end = next_range->rl_end;
 388
 389         /* Remove the now covered range from the list: */
 390         CIRCLEQ_REMOVE(rangelist, next_range, rl_link);
 391         FREE(next_range, M_TEMP);
 392
 393 #ifdef RL_DIAGNOSTIC
 394                 rl_verify(rangelist);
 395 #endif
 396     };
 397 }
 398
 399
 400
 401 static void
 402 rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
 403     struct rl_entry *prev_range;
 404
 405     while (1) {
 406         if (range == CIRCLEQ_FIRST(rangelist)) return;
 407
 408 #ifdef RL_DIAGNOSTIC
 409                 if (CIRCLEQ_PREV(range, rl_link) == range) panic("rl_collapse_backwards: circular range list?!");
 410 #endif
 411         prev_range = CIRCLEQ_PREV(range, rl_link);
 412         if (prev_range->rl_end < range->rl_start - 1) {
 413 #ifdef RL_DIAGNOSTIC
 414                         rl_verify(rangelist);
 415 #endif
 416                 return;
 417         };
 418
 419         /* Expand this range to include the previous range: */
 420         range->rl_start = prev_range->rl_start;
 421
 422         /* Remove the now covered range from the list: */
 423         CIRCLEQ_REMOVE(rangelist, prev_range, rl_link);
 424         FREE(prev_range, M_TEMP);
 425     };
 426 }
 427
 428
 429
 430 static void
 431 rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
 432 {
 433     rl_collapse_forwards(rangelist, range);
 434     rl_collapse_backwards(rangelist, range);
 435 }