xnu-2422.115.4.tar.gz

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

diff --git a/bsd/hfs/rangelist.c b/bsd/hfs/rangelist.c
index 55f7dcdbc797c44eed904f9e734c00707970fe66..74ced2e58b115e898c1efc3aca82143fea4b6586 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, 2006-2008 Apple Inc. All rights reserved.

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


@@ -26,6 +26,8 @@
  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  */
 
  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  */
 

+#if HFS
+

 #include <sys/param.h>
 #include <mach/boolean.h>
 #include <sys/time.h>
 #include <sys/param.h>
 #include <mach/boolean.h>
 #include <sys/time.h>


@@ -43,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


@@ -66,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);

 }
 
 
 }
 
 


@@ -82,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);


@@ -110,9 +108,9 @@ rl_add(off_t start, off_t end, struct rl_head *rangelist)
                        
                        /* Link in the new range: */
                        if (overlap) {
                        
                        /* Link in the new range: */
                        if (overlap) {

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

                        } else {
                        } else {

-                               CIRCLEQ_INSERT_HEAD(rangelist, range, rl_link);
+                               TAILQ_INSERT_HEAD(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


@@ -172,22 +170,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;
 


@@ -213,33 +211,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 */


@@ -269,12 +260,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));    

 }
 
 
 }
 
 


@@ -293,7 +284,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;
        };


@@ -323,14 +314,13 @@ rl_scan_from(struct rl_head *rangelist,
                                return RL_NOOVERLAP;
                        };
                        
                                return RL_NOOVERLAP;
                        };
                        

+                       range = TAILQ_NEXT(range, rl_link);

                        /* Check the other entries in the list: */
                        /* Check the other entries in the list: */

-                       if (range == CIRCLEQ_LAST(rangelist)) {
+                       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);
+                       }
+                       
+                       *overlap = range;

                        continue;
                }
                
                        continue;
                }
                


@@ -368,7 +358,7 @@ 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
        }
         


@@ -378,28 +368,22 @@ rl_scan_from(struct rl_head *rangelist,
 
 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

-    };
+       };

 }
 
 
 }
 
 


@@ -408,14 +392,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


@@ -426,7 +404,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);
     };
 }


@@ -439,3 +417,35 @@ rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
     rl_collapse_forwards(rangelist, range);
     rl_collapse_backwards(rangelist, range);
 }
     rl_collapse_forwards(rangelist, range);
     rl_collapse_backwards(rangelist, range);
 }

+
+#else /* not HFS - temp workaround until 4277828 is fixed */
+/* stubs for exported routines that aren't present when we build kernel without HFS */
+
+#include <sys/types.h>
+
+void rl_add(off_t start, off_t end, void *rangelist);
+void rl_init(void *rangelist);
+void rl_remove(off_t start, off_t end, void *rangelist);
+int rl_scan(void *rangelist, off_t start, off_t end, void **overlap);
+
+void rl_add(__unused off_t start, __unused off_t end, __unused void *rangelist)
+{
+       return;
+}
+
+void rl_init(__unused void *rangelist)
+{
+       return;
+}
+
+void rl_remove(__unused off_t start, __unused off_t end, __unused void *rangelist)
+{
+       return;
+}
+
+int rl_scan(__unused void *rangelist, __unused off_t start, __unused off_t end, __unused void **overlap)
+{
+       return(0);
+}
+
+#endif /* HFS */