bsd/hfs/rangelist.c

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