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 0e0a217..a1dde6d 100644 (file)
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -83,21 +83,21 @@ static void print_tree(struct rb_root *root)
 
 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 = node_to_extent(node);
-               if (ext->count <= 0) {
-                       printf("Tree Error: count is crazy\n");
-                       printf("extent: %llu -> %llu (%u)\n", ext->start,
+               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;
                }
@@ -105,20 +105,20 @@ static void 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;
@@ -809,6 +809,90 @@ static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
        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
 static void rb_print_stats(ext2fs_generic_bitmap bitmap)
 {
@@ -890,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,
 };