xnu-2782.40.9.tar.gz

[apple/xnu.git] / bsd / hfs / rangelist.c

diff --git a/bsd/hfs/rangelist.c b/bsd/hfs/rangelist.c
index e21a962dd26d28a93b0ae9936f24841366d1c2f0..0a1b412b6b7223ec88d769463aa2fb161941b644 100644 (file)
--- a/bsd/hfs/rangelist.c
+++ b/bsd/hfs/rangelist.c
@@ -1,5 +1,5 @@
 /*
 /*

- * Copyright (c) 2001 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2001-2014 Apple Inc. All rights reserved.

  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  * 
  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
  * 


@@ -45,17 +45,13 @@ static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *ra
 static void
 rl_verify(struct rl_head *rangelist) {
        struct rl_entry *entry;
 static void
 rl_verify(struct rl_head *rangelist) {
        struct rl_entry *entry;

+       struct rl_entry *next;

        off_t limit = 0;
        
        off_t limit = 0;
        

-       if (CIRCLEQ_EMPTY(rangelist)) return;
-       entry = CIRCLEQ_FIRST(rangelist);
-       while (1) {
-               if (CIRCLEQ_NEXT(entry, rl_link) == entry) panic("rl_verify: circular rangelist?!");
-               if ((limit > 0) && (entry->rl_start <= limit)) panic("rl_verify: bad entry start?!");
-               if (entry->rl_end < entry->rl_start) panic("rl_verify: bad entry end?!");
+       TAILQ_FOREACH_SAFE(rangelist, entry, rl_link, next) {
+               if ((limit > 0) && (entry->rl_start <= limit)) panic("hfs: rl_verify: bad entry start?!");
+               if (entry->rl_end < entry->rl_start) panic("hfs: rl_verify: bad entry end?!");

                limit = entry->rl_end;
                limit = entry->rl_end;

-               if (entry == CIRCLEQ_LAST(rangelist)) return;
-               entry = CIRCLEQ_NEXT(entry, rl_link);

        };
 }
 #endif
        };
 }
 #endif


@@ -68,7 +64,7 @@ rl_verify(struct rl_head *rangelist) {
 void
 rl_init(struct rl_head *rangelist)
 {
 void
 rl_init(struct rl_head *rangelist)
 {

-    CIRCLEQ_INIT(rangelist);
+    TAILQ_INIT(rangelist);

 }
 
 
 }
 
 


@@ -84,7 +80,7 @@ rl_add(off_t start, off_t end, struct rl_head *rangelist)
        enum rl_overlaptype ovcase;
 
 #ifdef RL_DIAGNOSTIC
        enum rl_overlaptype ovcase;
 
 #ifdef RL_DIAGNOSTIC

-       if (end < start) panic("rl_add: end < start?!");
+       if (end < start) panic("hfs: rl_add: end < start?!");

 #endif
 
        ovcase = rl_scan(rangelist, start, end, &overlap);
 #endif
 
        ovcase = rl_scan(rangelist, start, end, &overlap);


@@ -101,20 +97,18 @@ rl_add(off_t start, off_t end, struct rl_head *rangelist)
        switch (ovcase) {
                case RL_NOOVERLAP: /* 0: no overlap */
                        /*
        switch (ovcase) {
                case RL_NOOVERLAP: /* 0: no overlap */
                        /*

-                               * If the list was empty 'prev' is undisturbed and 'overlap' == NULL;
-                               * if the search hit a non-overlapping entry PAST the start of the
-                               * new range, 'prev' points to ITS predecessor, and 'overlap' points
-                               * to that entry:
-                               */
+                        * overlap points to the entry we should insert before, or
+                        * if NULL, we should insert at the end.
+                        */

                        MALLOC(range, struct rl_entry *, sizeof(*range), M_TEMP, M_WAITOK);
                        range->rl_start = start;
                        range->rl_end = end;
                        
                        /* Link in the new range: */
                        if (overlap) {
                        MALLOC(range, struct rl_entry *, sizeof(*range), M_TEMP, M_WAITOK);
                        range->rl_start = start;
                        range->rl_end = end;
                        
                        /* Link in the new range: */
                        if (overlap) {

-                               CIRCLEQ_INSERT_AFTER(rangelist, overlap, range, rl_link);
+                               TAILQ_INSERT_BEFORE(overlap, range, rl_link);

                        } else {
                        } else {

-                               CIRCLEQ_INSERT_HEAD(rangelist, range, rl_link);
+                               TAILQ_INSERT_TAIL(rangelist, range, rl_link);

                        }
                        
                        /* Check to see if any ranges can be combined (possibly including the immediately
                        }
                        
                        /* Check to see if any ranges can be combined (possibly including the immediately


@@ -174,22 +168,22 @@ void
 rl_remove(off_t start, off_t end, struct rl_head *rangelist)
 {
        struct rl_entry *range, *next_range, *overlap, *splitrange;
 rl_remove(off_t start, off_t end, struct rl_head *rangelist)
 {
        struct rl_entry *range, *next_range, *overlap, *splitrange;

-       int ovcase, moretotest;
+       int ovcase;

 
 #ifdef RL_DIAGNOSTIC
 
 #ifdef RL_DIAGNOSTIC

-       if (end < start) panic("rl_remove: end < start?!");
+       if (end < start) panic("hfs: rl_remove: end < start?!");

 #endif
 
 #endif
 

-       if (CIRCLEQ_EMPTY(rangelist)) {
+       if (TAILQ_EMPTY(rangelist)) {

                return;
        };
         
                return;
        };
         

-       range = CIRCLEQ_FIRST(rangelist);
+       range = TAILQ_FIRST(rangelist);

        while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
                switch (ovcase) {
 
                case RL_MATCHINGOVERLAP: /* 1: overlap == range */
        while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
                switch (ovcase) {
 
                case RL_MATCHINGOVERLAP: /* 1: overlap == range */

-                       CIRCLEQ_REMOVE(rangelist, overlap, rl_link);
+                       TAILQ_REMOVE(rangelist, overlap, rl_link);

                        FREE(overlap, M_TEMP);
                        break;
 
                        FREE(overlap, M_TEMP);
                        break;
 


@@ -215,33 +209,26 @@ rl_remove(off_t start, off_t end, struct rl_head *rangelist)
                        /*
                        * Now link the new entry into the range list after the range from which it was split:
                        */
                        /*
                        * Now link the new entry into the range list after the range from which it was split:
                        */

-                       CIRCLEQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
+                       TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);

                        break;
 
                case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
                        break;
 
                case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */

-                       moretotest = (overlap != CIRCLEQ_LAST(rangelist));
-#ifdef RL_DIAGNOSTIC
-                       if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!");
-#endif
-                       next_range = CIRCLEQ_NEXT(overlap, rl_link);    /* Check before discarding overlap entry */
-                       CIRCLEQ_REMOVE(rangelist, overlap, rl_link);
+                       /* Check before discarding overlap entry */
+                       next_range = TAILQ_NEXT(overlap, rl_link);
+                       TAILQ_REMOVE(rangelist, overlap, rl_link);

                        FREE(overlap, M_TEMP);
                        FREE(overlap, M_TEMP);

-                       if (moretotest) {
+                       if (next_range) {

                                range = next_range;
                                continue;
                        };
                        break;
 
                case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
                                range = next_range;
                                continue;
                        };
                        break;
 
                case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */

-                       moretotest = (overlap != CIRCLEQ_LAST(rangelist));

                        overlap->rl_end = start - 1;
                        overlap->rl_end = start - 1;

-                       if (moretotest) {
-#ifdef RL_DIAGNOSTIC
-                               if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!");
-#endif
-                               range = CIRCLEQ_NEXT(overlap, rl_link);
+                       range = TAILQ_NEXT(overlap, rl_link);
+                       if (range) {

                                continue;
                                continue;

-                       };
+                       }

                        break;
 
                case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
                        break;
 
                case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */


@@ -271,12 +258,12 @@ rl_scan(struct rl_head *rangelist,
                off_t end,
                struct rl_entry **overlap) {
                
                off_t end,
                struct rl_entry **overlap) {
                

-       if (CIRCLEQ_EMPTY(rangelist)) {
+       if (TAILQ_EMPTY(rangelist)) {

                *overlap = NULL;
                return RL_NOOVERLAP;
        };
         
                *overlap = NULL;
                return RL_NOOVERLAP;
        };
         

-       return rl_scan_from(rangelist, start, end, overlap, CIRCLEQ_FIRST(rangelist));  
+       return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist));    

 }
 
 
 }
 
 


@@ -295,7 +282,7 @@ rl_scan_from(struct rl_head *rangelist,
                         struct rl_entry **overlap,
                        struct rl_entry *range)
 {
                         struct rl_entry **overlap,
                        struct rl_entry *range)
 {

-       if (CIRCLEQ_EMPTY(rangelist)) {
+       if (TAILQ_EMPTY(rangelist)) {

                *overlap = NULL;
                return RL_NOOVERLAP;
        };
                *overlap = NULL;
                return RL_NOOVERLAP;
        };


@@ -326,13 +313,11 @@ rl_scan_from(struct rl_head *rangelist,
                        };
                        
                        /* Check the other entries in the list: */
                        };
                        
                        /* Check the other entries in the list: */

-                       if (range == CIRCLEQ_LAST(rangelist)) {
+                       range = TAILQ_NEXT(range, rl_link);
+                       *overlap = range;
+                       if (range == NULL)

                                return RL_NOOVERLAP;
                                return RL_NOOVERLAP;

-                       };
-#ifdef RL_DIAGNOSTIC
-                       if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_scan_from: circular range list?!");
-#endif
-                       *overlap = range = CIRCLEQ_NEXT(range, rl_link);
+                       

                        continue;
                }
                
                        continue;
                }
                


@@ -370,38 +355,30 @@ rl_scan_from(struct rl_head *rangelist,
 
                /* Control should never reach here... */
 #ifdef RL_DIAGNOSTIC
 
                /* Control should never reach here... */
 #ifdef RL_DIAGNOSTIC

-               panic("rl_scan_from: unhandled overlap condition?!");
+               panic("hfs: rl_scan_from: unhandled overlap condition?!");

 #endif
        }
 #endif
        }

-        
-       return RL_NOOVERLAP;

 }
 
 
 static void
 rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {
 }
 
 
 static void
 rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {

-    struct rl_entry *next_range;
-    
-    while (1) {
-               if (range == CIRCLEQ_LAST(rangelist)) return;
-    
-#ifdef RL_DIAGNOSTIC
-               if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_collapse_forwards: circular range list?!");
-#endif
-               next_range = CIRCLEQ_NEXT(range, rl_link);
-        if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
+       struct rl_entry *next_range;
+       
+       while ((next_range = TAILQ_NEXT(range, rl_link))) { 
+               if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;

 
 

-        /* Expand this range to include the next range: */
-        range->rl_end = next_range->rl_end;
-        
-        /* Remove the now covered range from the list: */
-        CIRCLEQ_REMOVE(rangelist, next_range, rl_link);
-        FREE(next_range, M_TEMP);
+               /* Expand this range to include the next range: */
+               range->rl_end = next_range->rl_end;
+
+               /* Remove the now covered range from the list: */
+               TAILQ_REMOVE(rangelist, next_range, rl_link);
+               FREE(next_range, M_TEMP);

 
 #ifdef RL_DIAGNOSTIC
                rl_verify(rangelist);
 #endif
 
 #ifdef RL_DIAGNOSTIC
                rl_verify(rangelist);
 #endif

-    };
+       };

 }
 
 
 }
 
 


@@ -410,14 +387,8 @@ static void
 rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
     struct rl_entry *prev_range;
     
 rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
     struct rl_entry *prev_range;
     

-    while (1) {
-        if (range == CIRCLEQ_FIRST(rangelist)) return;
-        
-#ifdef RL_DIAGNOSTIC
-               if (CIRCLEQ_PREV(range, rl_link) == range) panic("rl_collapse_backwards: circular range list?!");
-#endif
-        prev_range = CIRCLEQ_PREV(range, rl_link);
-        if (prev_range->rl_end < range->rl_start - 1) {
+               while ((prev_range = TAILQ_PREV(range, rl_head, rl_link))) {
+                       if (prev_range->rl_end < range->rl_start -1) {

 #ifdef RL_DIAGNOSTIC
                        rl_verify(rangelist);
 #endif
 #ifdef RL_DIAGNOSTIC
                        rl_verify(rangelist);
 #endif


@@ -428,7 +399,7 @@ rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
         range->rl_start = prev_range->rl_start;
     
         /* Remove the now covered range from the list: */
         range->rl_start = prev_range->rl_start;
     
         /* Remove the now covered range from the list: */

-        CIRCLEQ_REMOVE(rangelist, prev_range, rl_link);
+        TAILQ_REMOVE(rangelist, prev_range, rl_link);

         FREE(prev_range, M_TEMP);
     };
 }
         FREE(prev_range, M_TEMP);
     };
 }


@@ -442,6 +413,14 @@ rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
     rl_collapse_backwards(rangelist, range);
 }
 
     rl_collapse_backwards(rangelist, range);
 }
 

+void rl_remove_all(struct rl_head *rangelist)
+{
+       struct rl_entry *r, *nextr;
+       TAILQ_FOREACH_SAFE(r, rangelist, rl_link, nextr)
+               FREE(r, M_TEMP);
+       TAILQ_INIT(rangelist);
+}
+

 #else /* not HFS - temp workaround until 4277828 is fixed */
 /* stubs for exported routines that aren't present when we build kernel without HFS */
 
 #else /* not HFS - temp workaround until 4277828 is fixed */
 /* stubs for exported routines that aren't present when we build kernel without HFS */
 


@@ -472,4 +451,8 @@ int rl_scan(__unused void *rangelist, __unused off_t start, __unused off_t end,
        return(0);
 }
 
        return(0);
 }
 

+void rl_remove_all(struct rl_head *rangelist)
+{
+}
+

 #endif /* HFS */
 #endif /* HFS */