bsd/hfs/rangelist.c

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