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