bsd/hfs/rangelist.c

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