build: fix unused/uninitialized variable warnings

[tools/e2fsprogs.git] / lib / ext2fs / blkmap64_rb.c

diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index eb56c85..a1dde6d 100644 (file)
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -47,6 +47,17 @@ struct ext2fs_rb_private {
 #endif
 };
 
+inline static struct bmap_rb_extent *node_to_extent(struct rb_node *node)
+{
+       /*
+        * This depends on the fact the struct rb_node is at the
+        * beginning of the bmap_rb_extent structure.  We use this
+        * instead of the ext2fs_rb_entry macro because it causes gcc
+        * -Wall to generate a huge amount of noise.
+        */
+       return (struct bmap_rb_extent *) node;
+}
+
 static int rb_insert_extent(__u64 start, __u64 count,
                            struct ext2fs_rb_private *);
 static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64);
@@ -63,30 +74,30 @@ static void print_tree(struct rb_root *root)
        node = ext2fs_rb_first(root);
        for (node = ext2fs_rb_first(root); node != NULL; 
             node = ext2fs_rb_next(node)) {
-               ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+               ext = node_to_extent(node);
                printf("\t\t\t--> (%llu -> %llu)\n",
                        ext->start, ext->start + ext->count);
        }
        printf("\t\t\t=================================\n");
 }
 
-static int check_tree(struct rb_root *root, const char *msg)
+static void check_tree(struct rb_root *root, const char *msg)
 {
-       struct rb_node *new_node, *node, *next;
+       struct rb_node *node;
        struct bmap_rb_extent *ext, *old = NULL;
 
        for (node = ext2fs_rb_first(root); node;
             node = ext2fs_rb_next(node)) {
-               ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
-               if (ext->count <= 0) {
-                       printf("Tree Error: count is crazy\n");
-                       printf("extent: %llu -> %llu (%u)\n", ext->start,
+               ext = node_to_extent(node);
+               if (ext->count == 0) {
+                       printf("Tree Error: count is zero\n");
+                       printf("extent: %llu -> %llu (%llu)\n", ext->start,
                                ext->start + ext->count, ext->count);
                        goto err_out;
                }
-               if (ext->start < 0) {
-                       printf("Tree Error: start is crazy\n");
-                       printf("extent: %llu -> %llu (%u)\n", ext->start,
+               if (ext->start + ext->count < ext->start) {
+                       printf("Tree Error: start or count is crazy\n");
+                       printf("extent: %llu -> %llu (%llu)\n", ext->start,
                                ext->start + ext->count, ext->count);
                        goto err_out;
                }
@@ -94,20 +105,20 @@ static int check_tree(struct rb_root *root, const char *msg)
                if (old) {
                        if (old->start > ext->start) {
                                printf("Tree Error: start is crazy\n");
-                               printf("extent: %llu -> %llu (%u)\n",
+                               printf("extent: %llu -> %llu (%llu)\n",
                                        old->start, old->start + old->count,
                                        old->count);
-                               printf("extent next: %llu -> %llu (%u)\n",
+                               printf("extent next: %llu -> %llu (%llu)\n",
                                        ext->start, ext->start + ext->count,
                                        ext->count);
                                goto err_out;
                        }
                        if ((old->start + old->count) >= ext->start) {
                                printf("Tree Error: extent is crazy\n");
-                               printf("extent: %llu -> %llu (%u)\n",
+                               printf("extent: %llu -> %llu (%llu)\n",
                                        old->start, old->start + old->count,
                                        old->count);
-                               printf("extent next: %llu -> %llu (%u)\n",
+                               printf("extent next: %llu -> %llu (%llu)\n",
                                        ext->start, ext->start + ext->count,
                                        ext->count);
                                goto err_out;
@@ -115,7 +126,7 @@ static int check_tree(struct rb_root *root, const char *msg)
                }
                old = ext;
        }
-       return 0;
+       return;
 
 err_out:
        printf("%s\n", msg);
@@ -123,8 +134,8 @@ err_out:
        exit(1);
 }
 #else
-#define check_tree(root, msg) 0
-#define print_tree(root, msg) 0
+#define check_tree(root, msg) do {} while (0)
+#define print_tree(root) do {} while (0)
 #endif
 
 static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start,
@@ -200,7 +211,7 @@ static void rb_free_tree(struct rb_root *root)
 
        for (node = ext2fs_rb_first(root); node; node = next) {
                next = ext2fs_rb_next(node);
-               ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+               ext = node_to_extent(node);
                ext2fs_rb_erase(node, root);
                ext2fs_free_mem(&ext);
        }
@@ -236,7 +247,7 @@ static errcode_t rb_copy_bmap(ext2fs_generic_bitmap src,
 
        src_node = ext2fs_rb_first(&src_bp->root);
        while (src_node) {
-               src_ext = ext2fs_rb_entry(src_node, struct bmap_rb_extent, node);
+               src_ext = node_to_extent(src_node);
                retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
                                        &dest_ext);
                if (retval)
@@ -269,7 +280,7 @@ static void rb_truncate(__u64 new_max, struct rb_root *root)
 
        node = ext2fs_rb_last(root);
        while (node) {
-               ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+               ext = node_to_extent(node);
 
                if ((ext->start + ext->count - 1) <= new_max)
                        break;
@@ -330,8 +341,7 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
        if (!next_ext) {
                next = ext2fs_rb_next(&rcursor->node);
                if (next)
-                       next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent,
-                                                  node);
+                       next_ext = node_to_extent(next);
                bp->rcursor_next = next_ext;
        }
        if (next_ext) {
@@ -357,7 +367,7 @@ search_tree:
 
        while (*n) {
                parent = *n;
-               ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+               ext = node_to_extent(parent);
                if (bit < ext->start)
                        n = &(*n)->rb_left;
                else if (bit >= (ext->start + ext->count))
@@ -395,7 +405,7 @@ static int rb_insert_extent(__u64 start, __u64 count,
 
        while (*n) {
                parent = *n;
-               ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+               ext = node_to_extent(parent);
 
                if (start < ext->start) {
                        n = &(*n)->rb_left;
@@ -429,7 +439,7 @@ got_extent:
 
        node = ext2fs_rb_prev(new_node);
        if (node) {
-               ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+               ext = node_to_extent(node);
                if ((ext->start + ext->count) == start) {
                        start = ext->start;
                        count += ext->count;
@@ -442,7 +452,7 @@ skip_insert:
        /* See if we can merge extent to the right */
        for (node = ext2fs_rb_next(new_node); node != NULL; node = next) {
                next = ext2fs_rb_next(node);
-               ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+               ext = node_to_extent(node);
 
                if ((ext->start + ext->count) <= start)
                        continue;
@@ -487,7 +497,7 @@ static int rb_remove_extent(__u64 start, __u64 count,
 
        while (*n) {
                parent = *n;
-               ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+               ext = node_to_extent(parent);
                if (start < ext->start) {
                        n = &(*n)->rb_left;
                        continue;
@@ -530,7 +540,7 @@ static int rb_remove_extent(__u64 start, __u64 count,
        /* See if we should delete or truncate extent on the right */
        for (; parent != NULL; parent = node) {
                node = ext2fs_rb_next(parent);
-               ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+               ext = node_to_extent(parent);
                if ((ext->start + ext->count) <= start)
                        continue;
 
@@ -559,11 +569,14 @@ static int rb_remove_extent(__u64 start, __u64 count,
 static int rb_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
 {
        struct ext2fs_rb_private *bp;
+       int retval;
 
        bp = (struct ext2fs_rb_private *) bitmap->private;
        arg -= bitmap->start;
 
-       return rb_insert_extent(arg, 1, bp);
+       retval = rb_insert_extent(arg, 1, bp);
+       check_tree(&bp->root, __func__);
+       return retval;
 }
 
 static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
@@ -600,6 +613,7 @@ static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
        arg -= bitmap->start;
 
        rb_insert_extent(arg, num, bp);
+       check_tree(&bp->root, __func__);
 }
 
 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
@@ -637,7 +651,7 @@ static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
         */
        while (*n) {
                parent = *n;
-               ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+               ext = node_to_extent(parent);
                if (start < ext->start) {
                        n = &(*n)->rb_left;
                } else if (start >= (ext->start + ext->count)) {
@@ -654,7 +668,7 @@ static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
        node = parent;
        while (node) {
                next = ext2fs_rb_next(node);
-               ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+               ext = node_to_extent(node);
                node = next;
 
                if ((ext->start + ext->count) <= start)
@@ -677,12 +691,11 @@ static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap,
        unsigned char *cp = in;
        size_t i;
        int first_set = -1;
-       int ret;
 
        bp = (struct ext2fs_rb_private *) bitmap->private;
 
        for (i = 0; i < num; i++) {
-               if (i & 7 == 0) {
+               if ((i & 7) == 0) {
                        unsigned char c = cp[i/8];
                        if (c == 0xFF) {
                                if (first_set == -1)
@@ -705,11 +718,14 @@ static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap,
 
                rb_insert_extent(start + first_set - bitmap->start,
                                 i - first_set, bp);
+               check_tree(&bp->root, __func__);
                first_set = -1;
        }
-       if (first_set != -1)
+       if (first_set != -1) {
                rb_insert_extent(start + first_set - bitmap->start,
                                 num - first_set, bp);
+               check_tree(&bp->root, __func__);
+       }
 
        return 0;
 }
@@ -721,6 +737,7 @@ static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap,
        struct rb_node *parent = NULL, *next, **n;
        struct ext2fs_rb_private *bp;
        struct bmap_rb_extent *ext;
+       int count;
        __u64 pos;
 
        bp = (struct ext2fs_rb_private *) bitmap->private;
@@ -732,7 +749,7 @@ static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap,
 
        while (*n) {
                parent = *n;
-               ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+               ext = node_to_extent(parent);
                if (start < ext->start) {
                        n = &(*n)->rb_left;
                } else if (start >= (ext->start + ext->count)) {
@@ -745,17 +762,35 @@ static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap,
 
        for (; parent != NULL; parent = next) {
                next = ext2fs_rb_next(parent);
-               ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+               ext = node_to_extent(parent);
 
                pos = ext->start;
-               if (pos < start)
+               count = ext->count;
+               if (pos >= start + num)
+                       break;
+               if (pos < start) {
+                       count -= start - pos;
+                       if (count < 0)
+                               continue;
                        pos = start;
-
-               while (pos < (ext->start + ext->count)) {
-                       if ((pos - start) >= num)
-                               return 0;
+               }
+               if (pos + count > start + num)
+                       count = start + num - pos;
+
+               while (count > 0) {
+                       if ((count >= 8) &&
+                           ((pos - start) % 8) == 0) {
+                               int nbytes = count >> 3;
+                               int offset = (pos - start) >> 3;
+
+                               memset(((char *) out) + offset, 0xFF, nbytes);
+                               pos += nbytes << 3;
+                               count -= nbytes << 3;
+                               continue;
+                       }
                        ext2fs_fast_set_bit64((pos - start), out);
                        pos++;
+                       count--;
                }
        }
        return 0;
@@ -771,6 +806,91 @@ static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
        bp->rcursor = NULL;
        bp->rcursor_next = NULL;
        bp->wcursor = NULL;
+       check_tree(&bp->root, __func__);
+}
+
+static errcode_t rb_find_first_zero(ext2fs_generic_bitmap bitmap,
+                                  __u64 start, __u64 end, __u64 *out)
+{
+       struct rb_node *parent = NULL, **n;
+       struct ext2fs_rb_private *bp;
+       struct bmap_rb_extent *ext;
+
+       bp = (struct ext2fs_rb_private *) bitmap->private;
+       n = &bp->root.rb_node;
+       start -= bitmap->start;
+       end -= bitmap->start;
+
+       if (start > end)
+               return EINVAL;
+
+       if (EXT2FS_RB_EMPTY_ROOT(&bp->root))
+               return ENOENT;
+
+       while (*n) {
+               parent = *n;
+               ext = node_to_extent(parent);
+               if (start < ext->start) {
+                       n = &(*n)->rb_left;
+               } else if (start >= (ext->start + ext->count)) {
+                       n = &(*n)->rb_right;
+               } else if (ext->start + ext->count <= end) {
+                       *out = ext->start + ext->count + bitmap->start;
+                       return 0;
+               } else
+                       return ENOENT;
+       }
+
+       *out = start + bitmap->start;
+       return 0;
+}
+
+static errcode_t rb_find_first_set(ext2fs_generic_bitmap bitmap,
+                                  __u64 start, __u64 end, __u64 *out)
+{
+       struct rb_node *parent = NULL, **n;
+       struct rb_node *node;
+       struct ext2fs_rb_private *bp;
+       struct bmap_rb_extent *ext;
+
+       bp = (struct ext2fs_rb_private *) bitmap->private;
+       n = &bp->root.rb_node;
+       start -= bitmap->start;
+       end -= bitmap->start;
+
+       if (start > end)
+               return EINVAL;
+
+       if (EXT2FS_RB_EMPTY_ROOT(&bp->root))
+               return ENOENT;
+
+       while (*n) {
+               parent = *n;
+               ext = node_to_extent(parent);
+               if (start < ext->start) {
+                       n = &(*n)->rb_left;
+               } else if (start >= (ext->start + ext->count)) {
+                       n = &(*n)->rb_right;
+               } else {
+                       /* The start bit is set */
+                       *out = start + bitmap->start;
+                       return 0;
+               }
+       }
+
+       node = parent;
+       ext = node_to_extent(node);
+       if (ext->start < start) {
+               node = ext2fs_rb_next(node);
+               if (node == NULL)
+                       return ENOENT;
+               ext = node_to_extent(node);
+       }
+       if (ext->start <= end) {
+               *out = ext->start + bitmap->start;
+               return 0;
+       }
+       return ENOENT;
 }
 
 #ifdef BMAP_STATS
@@ -791,10 +911,9 @@ static void rb_print_stats(ext2fs_generic_bitmap bitmap)
 
        bp = (struct ext2fs_rb_private *) bitmap->private;
 
-       node = ext2fs_rb_first(&bp->root);
        for (node = ext2fs_rb_first(&bp->root); node != NULL;
             node = ext2fs_rb_next(node)) {
-               ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+               ext = node_to_extent(node);
                count++;
                if (ext->count > max_size)
                        max_size = ext->count;
@@ -855,4 +974,6 @@ struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
        .get_bmap_range = rb_get_bmap_range,
        .clear_bmap = rb_clear_bmap,
        .print_stats = rb_print_stats,
+       .find_first_zero = rb_find_first_zero,
+       .find_first_set = rb_find_first_set,
 };